123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555 |
- /* $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 <zebra.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)
- {
- 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 ("<Empty Table>\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 ();
- }
|