table_test.c 12 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556
  1. /* $QuaggaId: Format:%an, %ai, %h$ $
  2. *
  3. * Routing table test
  4. * Copyright (C) 2012 OSR.
  5. *
  6. * This file is part of Quagga
  7. *
  8. * Quagga is free software; you can redistribute it and/or modify it
  9. * under the terms of the GNU General Public License as published by the
  10. * Free Software Foundation; either version 2, or (at your option) any
  11. * later version.
  12. *
  13. * Quagga is distributed in the hope that it will be useful, but
  14. * WITHOUT ANY WARRANTY; without even the implied warranty of
  15. * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
  16. * General Public License for more details.
  17. *
  18. * You should have received a copy of the GNU General Public License
  19. * along with Quagga; see the file COPYING. If not, write to the Free
  20. * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
  21. * 02111-1307, USA.
  22. */
  23. #include <zebra.h>
  24. #include "prefix.h"
  25. #include "table.h"
  26. /*
  27. * test_node_t
  28. *
  29. * Information that is kept for each node in the radix tree.
  30. */
  31. typedef struct test_node_t_
  32. {
  33. /*
  34. * Human readable representation of the string. Allocated using
  35. * malloc()/dup().
  36. */
  37. char *prefix_str;
  38. } test_node_t;
  39. struct thread_master *master;
  40. /*
  41. * add_node
  42. *
  43. * Add the given prefix (passed in as a string) to the given table.
  44. */
  45. static void
  46. add_node (struct route_table *table, const char *prefix_str)
  47. {
  48. struct prefix_ipv4 p;
  49. test_node_t *node;
  50. struct route_node *rn;
  51. assert (prefix_str);
  52. if (str2prefix_ipv4 (prefix_str, &p) <= 0)
  53. {
  54. assert (0);
  55. }
  56. rn = route_node_get (table, (struct prefix *) &p);
  57. if (rn->info)
  58. {
  59. assert (0);
  60. return;
  61. }
  62. node = malloc (sizeof (test_node_t));
  63. assert (node);
  64. node->prefix_str = strdup (prefix_str);
  65. assert (node->prefix_str);
  66. rn->info = node;
  67. }
  68. /*
  69. * add_nodes
  70. *
  71. * Convenience function to add a bunch of nodes together.
  72. *
  73. * The arguments must be prefixes in string format, with a NULL as the
  74. * last argument.
  75. */
  76. static void
  77. add_nodes (struct route_table *table, ...)
  78. {
  79. va_list arglist;
  80. char *prefix;
  81. va_start (arglist, table);
  82. prefix = va_arg (arglist, char *);
  83. while (prefix)
  84. {
  85. add_node (table, prefix);
  86. prefix = va_arg (arglist, char *);
  87. }
  88. va_end (arglist);
  89. }
  90. /*
  91. * print_subtree
  92. *
  93. * Recursive function to print a route node and its children.
  94. *
  95. * @see print_table
  96. */
  97. static void
  98. print_subtree (struct route_node *rn, const char *legend, int indent_level)
  99. {
  100. char buf[INET_ADDRSTRLEN + 4];
  101. int i;
  102. /*
  103. * Print this node first.
  104. */
  105. for (i = 0; i < indent_level; i++)
  106. {
  107. printf (" ");
  108. }
  109. prefix2str (&rn->p, buf, sizeof (buf));
  110. printf ("%s: %s", legend, buf);
  111. if (!rn->info)
  112. {
  113. printf (" (internal)");
  114. }
  115. printf ("\n");
  116. if (rn->l_left)
  117. {
  118. print_subtree (rn->l_left, "Left", indent_level + 1);
  119. }
  120. if (rn->l_right)
  121. {
  122. print_subtree (rn->l_right, "Right", indent_level + 1);
  123. }
  124. }
  125. /*
  126. * print_table
  127. *
  128. * Function that prints out the internal structure of a route table.
  129. */
  130. static void
  131. print_table (struct route_table *table)
  132. {
  133. struct route_node *rn;
  134. rn = table->top;
  135. if (!rn)
  136. {
  137. printf ("<Empty Table>\n");
  138. return;
  139. }
  140. print_subtree (rn, "Top", 0);
  141. }
  142. /*
  143. * clear_table
  144. *
  145. * Remove all nodes from the given table.
  146. */
  147. static void
  148. clear_table (struct route_table *table)
  149. {
  150. route_table_iter_t iter;
  151. struct route_node *rn;
  152. test_node_t *node;
  153. route_table_iter_init (&iter, table);
  154. while ((rn = route_table_iter_next (&iter)))
  155. {
  156. node = rn->info;
  157. if (!node)
  158. {
  159. continue;
  160. }
  161. rn->info = NULL;
  162. route_unlock_node (rn);
  163. free (node->prefix_str);
  164. free (node);
  165. }
  166. route_table_iter_cleanup (&iter);
  167. assert (table->top == NULL);
  168. }
  169. /*
  170. * verify_next_by_iterating
  171. *
  172. * Iterate over the tree to make sure that the first prefix after
  173. * target_pfx is the expected one. Note that target_pfx may not be
  174. * present in the tree.
  175. */
  176. static void
  177. verify_next_by_iterating (struct route_table *table,
  178. struct prefix *target_pfx, struct prefix *next_pfx)
  179. {
  180. route_table_iter_t iter;
  181. struct route_node *rn;
  182. route_table_iter_init (&iter, table);
  183. while ((rn = route_table_iter_next (&iter)))
  184. {
  185. if (route_table_prefix_iter_cmp (&rn->p, target_pfx) > 0)
  186. {
  187. assert (!prefix_cmp (&rn->p, next_pfx));
  188. break;
  189. }
  190. }
  191. if (!rn)
  192. {
  193. assert (!next_pfx);
  194. }
  195. route_table_iter_cleanup (&iter);
  196. }
  197. /*
  198. * verify_next
  199. *
  200. * Verifies that route_table_get_next() returns the expected result
  201. * (result) for the prefix string 'target'.
  202. */
  203. static void
  204. verify_next (struct route_table *table, const char *target, const char *next)
  205. {
  206. struct prefix_ipv4 target_pfx, next_pfx;
  207. struct route_node *rn;
  208. char result_buf[INET_ADDRSTRLEN + 4];
  209. if (str2prefix_ipv4 (target, &target_pfx) <= 0)
  210. {
  211. assert (0);
  212. }
  213. rn = route_table_get_next (table, (struct prefix *) &target_pfx);
  214. if (rn)
  215. {
  216. prefix2str (&rn->p, result_buf, sizeof (result_buf));
  217. }
  218. else
  219. {
  220. snprintf (result_buf, sizeof (result_buf), "(Null)");
  221. }
  222. printf ("\n");
  223. print_table (table);
  224. printf ("Verifying successor of %s. Expected: %s, Result: %s\n", target,
  225. next ? next : "(Null)", result_buf);
  226. if (!rn)
  227. {
  228. assert (!next);
  229. verify_next_by_iterating (table, (struct prefix *) &target_pfx, NULL);
  230. return;
  231. }
  232. assert (next);
  233. if (str2prefix_ipv4 (next, &next_pfx) <= 0)
  234. {
  235. assert (0);
  236. }
  237. if (prefix_cmp (&rn->p, (struct prefix *) &next_pfx))
  238. {
  239. assert (0);
  240. }
  241. route_unlock_node (rn);
  242. verify_next_by_iterating (table, (struct prefix *) &target_pfx,
  243. (struct prefix *) &next_pfx);
  244. }
  245. /*
  246. * test_get_next
  247. */
  248. static void
  249. test_get_next (void)
  250. {
  251. struct route_table *table;
  252. printf ("\n\nTesting route_table_get_next()\n");
  253. table = route_table_init ();
  254. /*
  255. * Target exists in tree, but has no successor.
  256. */
  257. add_nodes (table, "1.0.1.0/24", NULL);
  258. verify_next (table, "1.0.1.0/24", NULL);
  259. clear_table (table);
  260. /*
  261. * Target exists in tree, and there is a node in its left subtree.
  262. */
  263. add_nodes (table, "1.0.1.0/24", "1.0.1.0/25", NULL);
  264. verify_next (table, "1.0.1.0/24", "1.0.1.0/25");
  265. clear_table (table);
  266. /*
  267. * Target exists in tree, and there is a node in its right subtree.
  268. */
  269. add_nodes (table, "1.0.1.0/24", "1.0.1.128/25", NULL);
  270. verify_next (table, "1.0.1.0/24", "1.0.1.128/25");
  271. clear_table (table);
  272. /*
  273. * Target exists in the tree, next node is outside subtree.
  274. */
  275. add_nodes (table, "1.0.1.0/24", "1.1.0.0/16", NULL);
  276. verify_next (table, "1.0.1.0/24", "1.1.0.0/16");
  277. clear_table (table);
  278. /*
  279. * The target node does not exist in the tree for all the test cases
  280. * below this point.
  281. */
  282. /*
  283. * There is no successor in the tree.
  284. */
  285. add_nodes (table, "1.0.0.0/16", NULL);
  286. verify_next (table, "1.0.1.0/24", NULL);
  287. clear_table (table);
  288. /*
  289. * There exists a node that would be in the target's left subtree.
  290. */
  291. add_nodes (table, "1.0.0.0/16", "1.0.1.0/25", NULL);
  292. verify_next (table, "1.0.1.0/24", "1.0.1.0/25");
  293. clear_table (table);
  294. /*
  295. * There exists a node would be in the target's right subtree.
  296. */
  297. add_nodes (table, "1.0.0.0/16", "1.0.1.128/25", NULL);
  298. verify_next (table, "1.0.1.0/24", "1.0.1.128/25");
  299. clear_table (table);
  300. /*
  301. * A search for the target reaches a node where there are no child
  302. * nodes in the direction of the target (left), but the node has a
  303. * right child.
  304. */
  305. add_nodes (table, "1.0.0.0/16", "1.0.128.0/17", NULL);
  306. verify_next (table, "1.0.0.0/17", "1.0.128.0/17");
  307. clear_table (table);
  308. /*
  309. * A search for the target reaches a node with no children. We have
  310. * to go upwards in the tree to find a successor.
  311. */
  312. add_nodes (table, "1.0.0.0/16", "1.0.0.0/24", "1.0.1.0/24",
  313. "1.0.128.0/17", NULL);
  314. verify_next (table, "1.0.1.0/25", "1.0.128.0/17");
  315. clear_table (table);
  316. /*
  317. * A search for the target reaches a node where neither the node nor
  318. * the target prefix contain each other.
  319. *
  320. * In first case below the node succeeds the target.
  321. *
  322. * In the second case, the node comes before the target, so we have
  323. * to go up the tree looking for a successor.
  324. */
  325. add_nodes (table, "1.0.0.0/16", "1.0.1.0/24", NULL);
  326. verify_next (table, "1.0.0.0/24", "1.0.1.0/24");
  327. clear_table (table);
  328. add_nodes (table, "1.0.0.0/16", "1.0.0.0/24", "1.0.1.0/25",
  329. "1.0.128.0/17", NULL);
  330. verify_next (table, "1.0.1.128/25", "1.0.128.0/17");
  331. clear_table (table);
  332. route_table_finish (table);
  333. }
  334. /*
  335. * verify_prefix_iter_cmp
  336. */
  337. static void
  338. verify_prefix_iter_cmp (const char *p1, const char *p2, int exp_result)
  339. {
  340. struct prefix_ipv4 p1_pfx, p2_pfx;
  341. int result;
  342. if (str2prefix_ipv4 (p1, &p1_pfx) <= 0)
  343. {
  344. assert (0);
  345. }
  346. if (str2prefix_ipv4 (p2, &p2_pfx) <= 0)
  347. {
  348. assert (0);
  349. }
  350. result = route_table_prefix_iter_cmp ((struct prefix *) &p1_pfx,
  351. (struct prefix *) &p2_pfx);
  352. printf ("Verifying cmp(%s, %s) returns %d\n", p1, p2, exp_result);
  353. assert (exp_result == result);
  354. /*
  355. * Also check the reverse comparision.
  356. */
  357. result = route_table_prefix_iter_cmp ((struct prefix *) &p2_pfx,
  358. (struct prefix *) &p1_pfx);
  359. if (exp_result)
  360. {
  361. exp_result = -exp_result;
  362. }
  363. printf ("Verifying cmp(%s, %s) returns %d\n", p1, p2, exp_result);
  364. assert (result == exp_result);
  365. }
  366. /*
  367. * test_prefix_iter_cmp
  368. *
  369. * Tests comparision of prefixes according to order of iteration.
  370. */
  371. static void
  372. test_prefix_iter_cmp ()
  373. {
  374. printf ("\n\nTesting route_table_prefix_iter_cmp()\n");
  375. verify_prefix_iter_cmp ("1.0.0.0/8", "1.0.0.0/8", 0);
  376. verify_prefix_iter_cmp ("1.0.0.0/8", "1.0.0.0/16", -1);
  377. verify_prefix_iter_cmp ("1.0.0.0/16", "1.128.0.0/16", -1);
  378. }
  379. /*
  380. * verify_iter_with_pause
  381. *
  382. * Iterates over a tree using two methods: 'normal' iteration, and an
  383. * iterator that pauses at each node. Verifies that the two methods
  384. * yield the same results.
  385. */
  386. static void
  387. verify_iter_with_pause (struct route_table *table)
  388. {
  389. unsigned long num_nodes;
  390. struct route_node *rn, *iter_rn;
  391. route_table_iter_t iter_space;
  392. route_table_iter_t *iter = &iter_space;
  393. route_table_iter_init (iter, table);
  394. num_nodes = 0;
  395. for (rn = route_top (table); rn; rn = route_next (rn))
  396. {
  397. num_nodes++;
  398. route_table_iter_pause (iter);
  399. assert (iter->current == NULL);
  400. if (route_table_iter_started (iter))
  401. {
  402. assert (iter->state == RT_ITER_STATE_PAUSED);
  403. }
  404. else
  405. {
  406. assert (rn == table->top);
  407. assert (iter->state == RT_ITER_STATE_INIT);
  408. }
  409. iter_rn = route_table_iter_next (iter);
  410. /*
  411. * Make sure both iterations return the same node.
  412. */
  413. assert (rn == iter_rn);
  414. }
  415. assert (num_nodes == route_table_count (table));
  416. route_table_iter_pause (iter);
  417. iter_rn = route_table_iter_next (iter);
  418. assert (iter_rn == NULL);
  419. assert (iter->state == RT_ITER_STATE_DONE);
  420. assert (route_table_iter_next (iter) == NULL);
  421. assert (iter->state == RT_ITER_STATE_DONE);
  422. route_table_iter_cleanup (iter);
  423. print_table (table);
  424. printf ("Verified pausing iteration on tree with %lu nodes\n", num_nodes);
  425. }
  426. /*
  427. * test_iter_pause
  428. */
  429. static void
  430. test_iter_pause (void)
  431. {
  432. struct route_table *table;
  433. int i, num_prefixes;
  434. const char *prefixes[] = {
  435. "1.0.1.0/24",
  436. "1.0.1.0/25",
  437. "1.0.1.128/25",
  438. "1.0.2.0/24",
  439. "2.0.0.0/8"
  440. };
  441. num_prefixes = sizeof (prefixes) / sizeof (prefixes[0]);
  442. printf ("\n\nTesting that route_table_iter_pause() works as expected\n");
  443. table = route_table_init ();
  444. for (i = 0; i < num_prefixes; i++)
  445. {
  446. add_nodes (table, prefixes[i], NULL);
  447. }
  448. verify_iter_with_pause (table);
  449. clear_table (table);
  450. route_table_finish (table);
  451. }
  452. /*
  453. * run_tests
  454. */
  455. static void
  456. run_tests (void)
  457. {
  458. test_prefix_iter_cmp ();
  459. test_get_next ();
  460. test_iter_pause ();
  461. }
  462. /*
  463. * main
  464. */
  465. int
  466. main (void)
  467. {
  468. run_tests ();
  469. }