From 2c7cac91ed6e7db0f6937923d2b57f97dbdbc337 Mon Sep 17 00:00:00 2001 From: Daniel Baumann Date: Sun, 28 Apr 2024 11:53:30 +0200 Subject: Adding upstream version 8.4.4. Signed-off-by: Daniel Baumann --- tests/lib/test_table.c | 509 +++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 509 insertions(+) create mode 100644 tests/lib/test_table.c (limited to 'tests/lib/test_table.c') diff --git a/tests/lib/test_table.c b/tests/lib/test_table.c new file mode 100644 index 0000000..cef93ad --- /dev/null +++ b/tests/lib/test_table.c @@ -0,0 +1,509 @@ +/* + * Routing table test + * Copyright (C) 2012 OSR. + * + * This file is part of Quagga + * + * Quagga is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License as published by the + * Free Software Foundation; either version 2, or (at your option) any + * later version. + * + * Quagga is distributed in the hope that it will be useful, but + * WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * General Public License for more details. + * + * You should have received a copy of the GNU General Public License along + * with this program; see the file COPYING; if not, write to the Free Software + * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA + */ + +#include +#include "printfrr.h" +#include "prefix.h" +#include "table.h" + +/* + * test_node_t + * + * Information that is kept for each node in the radix tree. + */ +typedef struct test_node_t_ { + + /* + * Human readable representation of the string. Allocated using + * malloc()/dup(). + */ + char *prefix_str; +} test_node_t; + +struct thread_master *master; + +/* + * add_node + * + * Add the given prefix (passed in as a string) to the given table. + */ +static void add_node(struct route_table *table, const char *prefix_str) +{ + struct prefix_ipv4 p; + test_node_t *node; + struct route_node *rn; + + assert(prefix_str); + + if (str2prefix_ipv4(prefix_str, &p) <= 0) { + assert(0); + } + + rn = route_node_get(table, (struct prefix *)&p); + if (rn->info) { + assert(0); + return; + } + + node = malloc(sizeof(test_node_t)); + assert(node); + node->prefix_str = strdup(prefix_str); + assert(node->prefix_str); + rn->info = node; +} + +/* + * add_nodes + * + * Convenience function to add a bunch of nodes together. + * + * The arguments must be prefixes in string format, with a NULL as the + * last argument. + */ +static void add_nodes(struct route_table *table, ...) +{ + va_list arglist; + char *prefix; + + va_start(arglist, table); + + prefix = va_arg(arglist, char *); + while (prefix) { + add_node(table, prefix); + prefix = va_arg(arglist, char *); + } + + va_end(arglist); +} + +/* + * print_subtree + * + * Recursive function to print a route node and its children. + * + * @see print_table + */ +static void print_subtree(struct route_node *rn, const char *legend, + int indent_level) +{ + int i; + + /* + * Print this node first. + */ + for (i = 0; i < indent_level; i++) { + printf(" "); + } + + printfrr("%s: %pFX", legend, &rn->p); + if (!rn->info) { + printf(" (internal)"); + } + printf("\n"); + if (rn->l_left) { + print_subtree(rn->l_left, "Left", indent_level + 1); + } + if (rn->l_right) { + print_subtree(rn->l_right, "Right", indent_level + 1); + } +} + +/* + * print_table + * + * Function that prints out the internal structure of a route table. + */ +static void print_table(struct route_table *table) +{ + struct route_node *rn; + + rn = table->top; + + if (!rn) { + printf("\n"); + return; + } + + print_subtree(rn, "Top", 0); +} + +/* + * clear_table + * + * Remove all nodes from the given table. + */ +static void clear_table(struct route_table *table) +{ + route_table_iter_t iter; + struct route_node *rn; + test_node_t *node; + + route_table_iter_init(&iter, table); + + while ((rn = route_table_iter_next(&iter))) { + node = rn->info; + if (!node) { + continue; + } + rn->info = NULL; + route_unlock_node(rn); + free(node->prefix_str); + free(node); + } + + route_table_iter_cleanup(&iter); + + assert(table->top == NULL); +} + +/* + * verify_next_by_iterating + * + * Iterate over the tree to make sure that the first prefix after + * target_pfx is the expected one. Note that target_pfx may not be + * present in the tree. + */ +static void verify_next_by_iterating(struct route_table *table, + struct prefix *target_pfx, + struct prefix *next_pfx) +{ + route_table_iter_t iter; + struct route_node *rn; + + route_table_iter_init(&iter, table); + while ((rn = route_table_iter_next(&iter))) { + if (route_table_prefix_iter_cmp(&rn->p, target_pfx) > 0) { + assert(!prefix_cmp(&rn->p, next_pfx)); + break; + } + } + + if (!rn) { + assert(!next_pfx); + } + + route_table_iter_cleanup(&iter); +} + +/* + * verify_next + * + * Verifies that route_table_get_next() returns the expected result + * (result) for the prefix string 'target'. + */ +static void verify_next(struct route_table *table, const char *target, + const char *next) +{ + struct prefix_ipv4 target_pfx, next_pfx; + struct route_node *rn; + char result_buf[PREFIX2STR_BUFFER]; + + if (str2prefix_ipv4(target, &target_pfx) <= 0) { + assert(0); + } + + rn = route_table_get_next(table, (struct prefix *)&target_pfx); + if (rn) { + prefix2str(&rn->p, result_buf, sizeof(result_buf)); + } else { + snprintf(result_buf, sizeof(result_buf), "(Null)"); + } + + printf("\n"); + print_table(table); + printf("Verifying successor of %s. Expected: %s, Result: %s\n", target, + next ? next : "(Null)", result_buf); + + if (!rn) { + assert(!next); + verify_next_by_iterating(table, (struct prefix *)&target_pfx, + NULL); + return; + } + + assert(next); + + if (str2prefix_ipv4(next, &next_pfx) <= 0) { + assert(0); + } + + if (prefix_cmp(&rn->p, (struct prefix *)&next_pfx)) { + assert(0); + } + route_unlock_node(rn); + + verify_next_by_iterating(table, (struct prefix *)&target_pfx, + (struct prefix *)&next_pfx); +} + +/* + * test_get_next + */ +static void test_get_next(void) +{ + struct route_table *table; + + printf("\n\nTesting route_table_get_next()\n"); + table = route_table_init(); + + /* + * Target exists in tree, but has no successor. + */ + add_nodes(table, "1.0.1.0/24", NULL); + verify_next(table, "1.0.1.0/24", NULL); + clear_table(table); + + /* + * Target exists in tree, and there is a node in its left subtree. + */ + add_nodes(table, "1.0.1.0/24", "1.0.1.0/25", NULL); + verify_next(table, "1.0.1.0/24", "1.0.1.0/25"); + clear_table(table); + + /* + * Target exists in tree, and there is a node in its right subtree. + */ + add_nodes(table, "1.0.1.0/24", "1.0.1.128/25", NULL); + verify_next(table, "1.0.1.0/24", "1.0.1.128/25"); + clear_table(table); + + /* + * Target exists in the tree, next node is outside subtree. + */ + add_nodes(table, "1.0.1.0/24", "1.1.0.0/16", NULL); + verify_next(table, "1.0.1.0/24", "1.1.0.0/16"); + clear_table(table); + + /* + * The target node does not exist in the tree for all the test cases + * below this point. + */ + + /* + * There is no successor in the tree. + */ + add_nodes(table, "1.0.0.0/16", NULL); + verify_next(table, "1.0.1.0/24", NULL); + clear_table(table); + + /* + * There exists a node that would be in the target's left subtree. + */ + add_nodes(table, "1.0.0.0/16", "1.0.1.0/25", NULL); + verify_next(table, "1.0.1.0/24", "1.0.1.0/25"); + clear_table(table); + + /* + * There exists a node would be in the target's right subtree. + */ + add_nodes(table, "1.0.0.0/16", "1.0.1.128/25", NULL); + verify_next(table, "1.0.1.0/24", "1.0.1.128/25"); + clear_table(table); + + /* + * A search for the target reaches a node where there are no child + * nodes in the direction of the target (left), but the node has a + * right child. + */ + add_nodes(table, "1.0.0.0/16", "1.0.128.0/17", NULL); + verify_next(table, "1.0.0.0/17", "1.0.128.0/17"); + clear_table(table); + + /* + * A search for the target reaches a node with no children. We have + * to go upwards in the tree to find a successor. + */ + add_nodes(table, "1.0.0.0/16", "1.0.0.0/24", "1.0.1.0/24", + "1.0.128.0/17", NULL); + verify_next(table, "1.0.1.0/25", "1.0.128.0/17"); + clear_table(table); + + /* + * A search for the target reaches a node where neither the node nor + * the target prefix contain each other. + * + * In first case below the node succeeds the target. + * + * In the second case, the node comes before the target, so we have + * to go up the tree looking for a successor. + */ + add_nodes(table, "1.0.0.0/16", "1.0.1.0/24", NULL); + verify_next(table, "1.0.0.0/24", "1.0.1.0/24"); + clear_table(table); + + add_nodes(table, "1.0.0.0/16", "1.0.0.0/24", "1.0.1.0/25", + "1.0.128.0/17", NULL); + verify_next(table, "1.0.1.128/25", "1.0.128.0/17"); + clear_table(table); + + route_table_finish(table); +} + +/* + * verify_prefix_iter_cmp + */ +static void verify_prefix_iter_cmp(const char *p1, const char *p2, + int exp_result) +{ + struct prefix_ipv4 p1_pfx, p2_pfx; + int result; + + if (str2prefix_ipv4(p1, &p1_pfx) <= 0) { + assert(0); + } + + if (str2prefix_ipv4(p2, &p2_pfx) <= 0) { + assert(0); + } + + result = route_table_prefix_iter_cmp((struct prefix *)&p1_pfx, + (struct prefix *)&p2_pfx); + + printf("Verifying cmp(%s, %s) returns %d\n", p1, p2, exp_result); + + assert(exp_result == result); + + /* + * Also check the reverse comparison. + */ + result = route_table_prefix_iter_cmp((struct prefix *)&p2_pfx, + (struct prefix *)&p1_pfx); + + if (exp_result) { + exp_result = -exp_result; + } + + printf("Verifying cmp(%s, %s) returns %d\n", p1, p2, exp_result); + assert(result == exp_result); +} + +/* + * test_prefix_iter_cmp + * + * Tests comparison of prefixes according to order of iteration. + */ +static void test_prefix_iter_cmp(void) +{ + printf("\n\nTesting route_table_prefix_iter_cmp()\n"); + + verify_prefix_iter_cmp("1.0.0.0/8", "1.0.0.0/8", 0); + + verify_prefix_iter_cmp("1.0.0.0/8", "1.0.0.0/16", -1); + + verify_prefix_iter_cmp("1.0.0.0/16", "1.128.0.0/16", -1); +} + +/* + * verify_iter_with_pause + * + * Iterates over a tree using two methods: 'normal' iteration, and an + * iterator that pauses at each node. Verifies that the two methods + * yield the same results. + */ +static void verify_iter_with_pause(struct route_table *table) +{ + unsigned long num_nodes; + struct route_node *rn, *iter_rn; + route_table_iter_t iter_space; + route_table_iter_t *iter = &iter_space; + + route_table_iter_init(iter, table); + num_nodes = 0; + + for (rn = route_top(table); rn; rn = route_next(rn)) { + num_nodes++; + route_table_iter_pause(iter); + + assert(iter->current == NULL); + if (route_table_iter_started(iter)) { + assert(iter->state == RT_ITER_STATE_PAUSED); + } else { + assert(rn == table->top); + assert(iter->state == RT_ITER_STATE_INIT); + } + + iter_rn = route_table_iter_next(iter); + + /* + * Make sure both iterations return the same node. + */ + assert(rn == iter_rn); + } + + assert(num_nodes == route_table_count(table)); + + route_table_iter_pause(iter); + iter_rn = route_table_iter_next(iter); + + assert(iter_rn == NULL); + assert(iter->state == RT_ITER_STATE_DONE); + + assert(route_table_iter_next(iter) == NULL); + assert(iter->state == RT_ITER_STATE_DONE); + + route_table_iter_cleanup(iter); + + print_table(table); + printf("Verified pausing iteration on tree with %lu nodes\n", + num_nodes); +} + +/* + * test_iter_pause + */ +static void test_iter_pause(void) +{ + struct route_table *table; + int i, num_prefixes; + const char *prefixes[] = {"1.0.1.0/24", "1.0.1.0/25", "1.0.1.128/25", + "1.0.2.0/24", "2.0.0.0/8"}; + + num_prefixes = array_size(prefixes); + + printf("\n\nTesting that route_table_iter_pause() works as expected\n"); + table = route_table_init(); + for (i = 0; i < num_prefixes; i++) { + add_nodes(table, prefixes[i], NULL); + } + + verify_iter_with_pause(table); + + clear_table(table); + route_table_finish(table); +} + +/* + * run_tests + */ +static void run_tests(void) +{ + test_prefix_iter_cmp(); + test_get_next(); + test_iter_pause(); +} + +/* + * main + */ +int main(void) +{ + run_tests(); +} -- cgit v1.2.3