From 28971c8cb1138700e87dc7da673e59b5596bb51b Mon Sep 17 00:00:00 2001 From: Avneesh Sachdev Date: Fri, 17 Aug 2012 08:19:50 -0700 Subject: lib/table: add route_table_get_next() and iterator * lib/table.[ch] - Add a function (route_table_get_next()) to get the route_node in a tree that succeeds a given prefix in iteration order. This allows one to reliably walk nodes in a tree while allowing modifications, and is useful for achieving scale and performance. Other approaches are also possible -- the main plus point of this one is that it does not require any state about the walk to be maintained in the table data structures. - Add an iterator for walking the nodes in a tree. This introduces a new structure (route_table_iter_t) and the following main functions. route_table_iter_init() route_table_iter_pause() route_table_iter_next() route_table_iter_cleanup() The iterator normally uses node pointers and the existing route_next() function to walk nodes efficiently. When an iteration is 'paused' with route_table_iter_pause(), it stores the last prefix processed. The next call to route_table_iter_next() transparently invokes route_table_get_next() with the prefix to resume iteration. * bgpd/bgp_table.[ch] Add wrappers for the new table features described above. * tests/table_test.c Add tests for the new table code. Signed-off-by: David Lamparter --- tests/.gitignore | 1 + tests/Makefile.am | 4 +- tests/table_test.c | 555 +++++++++++++++++++++++++++++++++++++++++++++++++++++ 3 files changed, 559 insertions(+), 1 deletion(-) create mode 100644 tests/table_test.c (limited to 'tests') diff --git a/tests/.gitignore b/tests/.gitignore index ca085943..e6ab706c 100644 --- a/tests/.gitignore +++ b/tests/.gitignore @@ -8,6 +8,7 @@ TAGS *.lo *.la *.libs +tabletest testsig .arch-inventory .arch-ids diff --git a/tests/Makefile.am b/tests/Makefile.am index 0c262a4a..e510a158 100644 --- a/tests/Makefile.am +++ b/tests/Makefile.am @@ -6,7 +6,7 @@ AM_LDFLAGS = $(PILDFLAGS) noinst_PROGRAMS = testsig testbuffer testmemory heavy heavywq heavythread \ aspathtest testprivs teststream testbgpcap ecommtest \ - testbgpmpattr testchecksum testbgpmpath + testbgpmpattr testchecksum testbgpmpath tabletest testsig_SOURCES = test-sig.c testbuffer_SOURCES = test-buffer.c @@ -22,6 +22,7 @@ ecommtest_SOURCES = ecommunity_test.c testbgpmpattr_SOURCES = bgp_mp_attr_test.c testchecksum_SOURCES = test-checksum.c testbgpmpath_SOURCES = bgp_mpath_test.c +tabletest_SOURCES = table_test.c testsig_LDADD = ../lib/libzebra.la @LIBCAP@ testbuffer_LDADD = ../lib/libzebra.la @LIBCAP@ @@ -37,3 +38,4 @@ ecommtest_LDADD = ../lib/libzebra.la @LIBCAP@ -lm ../bgpd/libbgp.a testbgpmpattr_LDADD = ../lib/libzebra.la @LIBCAP@ -lm ../bgpd/libbgp.a testchecksum_LDADD = ../lib/libzebra.la @LIBCAP@ testbgpmpath_LDADD = ../lib/libzebra.la @LIBCAP@ -lm ../bgpd/libbgp.a +tabletest_LDADD = ../lib/libzebra.la @LIBCAP@ -lm diff --git a/tests/table_test.c b/tests/table_test.c new file mode 100644 index 00000000..fc9cc3dd --- /dev/null +++ b/tests/table_test.c @@ -0,0 +1,555 @@ +/* $QuaggaId: Format:%an, %ai, %h$ $ + * + * 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 Quagga; see the file COPYING. If not, write to the Free + * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA + * 02111-1307, USA. + */ + +#include + +#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) +{ + char buf[INET_ADDRSTRLEN + 4]; + int i; + + /* + * Print this node first. + */ + for (i = 0; i < indent_level; i++) + { + printf (" "); + } + + prefix2str (&rn->p, buf, sizeof (buf)); + printf ("%s: %s", legend, buf); + 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[INET_ADDRSTRLEN + 4]; + + 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 comparision. + */ + 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 comparision of prefixes according to order of iteration. + */ +static void +test_prefix_iter_cmp () +{ + 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 = sizeof (prefixes) / sizeof (prefixes[0]); + + 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.1