test-nexthop-iter.c 6.3 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291
  1. /*
  2. * Recursive Nexthop Iterator test.
  3. * This tests the ALL_NEXTHOPS_RO macro.
  4. *
  5. * Copyright (C) 2012 by Open Source Routing.
  6. * Copyright (C) 2012 by Internet Systems Consortium, Inc. ("ISC")
  7. *
  8. * This file is part of Quagga
  9. *
  10. * Quagga is free software; you can redistribute it and/or modify it
  11. * under the terms of the GNU General Public License as published by the
  12. * Free Software Foundation; either version 2, or (at your option) any
  13. * later version.
  14. *
  15. * Quagga is distributed in the hope that it will be useful, but
  16. * WITHOUT ANY WARRANTY; without even the implied warranty of
  17. * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
  18. * General Public License for more details.
  19. *
  20. * You should have received a copy of the GNU General Public License
  21. * along with Quagga; see the file COPYING. If not, write to the Free
  22. * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
  23. * 02111-1307, USA.
  24. */
  25. #include <zebra.h>
  26. #include "zebra/rib.h"
  27. #include "prng.h"
  28. struct thread_master *master;
  29. static int verbose;
  30. static void
  31. str_append(char **buf, const char *repr)
  32. {
  33. if (*buf)
  34. {
  35. *buf = realloc(*buf, strlen(*buf) + strlen(repr) + 1);
  36. assert(*buf);
  37. strncpy((*buf) + strlen(*buf), repr, strlen(repr) + 1);
  38. }
  39. else
  40. {
  41. *buf = strdup(repr);
  42. assert(*buf);
  43. }
  44. }
  45. static void
  46. str_appendf(char **buf, const char *format, ...)
  47. {
  48. va_list ap;
  49. int rv;
  50. char *pbuf;
  51. va_start(ap, format);
  52. rv = vasprintf(&pbuf, format, ap);
  53. va_end(ap);
  54. assert(rv >= 0);
  55. str_append(buf, pbuf);
  56. free(pbuf);
  57. }
  58. /* This structure contains a nexthop chain
  59. * and its expected representation */
  60. struct nexthop_chain
  61. {
  62. /* Head of the chain */
  63. struct nexthop *head;
  64. /* Last nexthop in top chain */
  65. struct nexthop *current_top;
  66. /* Last nexthop in current recursive chain */
  67. struct nexthop *current_recursive;
  68. /* Expected string representation. */
  69. char *repr;
  70. };
  71. static struct nexthop_chain*
  72. nexthop_chain_new(void)
  73. {
  74. struct nexthop_chain *rv;
  75. rv = calloc(sizeof(*rv), 1);
  76. assert(rv);
  77. return rv;
  78. }
  79. static void
  80. nexthop_chain_add_top(struct nexthop_chain *nc)
  81. {
  82. struct nexthop *nh;
  83. nh = calloc(sizeof(*nh), 1);
  84. assert(nh);
  85. if (nc->head)
  86. {
  87. nc->current_top->next = nh;
  88. nh->prev = nc->current_top;
  89. nc->current_top = nh;
  90. }
  91. else
  92. {
  93. nc->head = nc->current_top = nh;
  94. }
  95. nc->current_recursive = NULL;
  96. str_appendf(&nc->repr, "%p\n", nh);
  97. }
  98. static void
  99. nexthop_chain_add_recursive(struct nexthop_chain *nc)
  100. {
  101. struct nexthop *nh;
  102. nh = calloc(sizeof(*nh), 1);
  103. assert(nh);
  104. assert(nc->current_top);
  105. if (nc->current_recursive)
  106. {
  107. nc->current_recursive->next = nh;
  108. nh->prev = nc->current_recursive;
  109. nc->current_recursive = nh;
  110. }
  111. else
  112. {
  113. SET_FLAG(nc->current_top->flags, NEXTHOP_FLAG_RECURSIVE);
  114. nc->current_top->resolved = nh;
  115. nc->current_recursive = nh;
  116. }
  117. str_appendf(&nc->repr, " %p\n", nh);
  118. }
  119. static void
  120. nexthop_chain_clear(struct nexthop_chain *nc)
  121. {
  122. struct nexthop *tcur, *tnext;
  123. for (tcur = nc->head; tcur; tcur = tnext)
  124. {
  125. tnext = tcur->next;
  126. if (CHECK_FLAG(tcur->flags, NEXTHOP_FLAG_RECURSIVE))
  127. {
  128. struct nexthop *rcur, *rnext;
  129. for (rcur = tcur->resolved; rcur; rcur = rnext)
  130. {
  131. rnext = rcur->next;
  132. free(rcur);
  133. }
  134. }
  135. free(tcur);
  136. }
  137. nc->head = nc->current_top = nc->current_recursive = NULL;
  138. free(nc->repr);
  139. nc->repr = NULL;
  140. }
  141. static void
  142. nexthop_chain_free(struct nexthop_chain *nc)
  143. {
  144. if (!nc)
  145. return;
  146. nexthop_chain_clear(nc);
  147. free(nc);
  148. }
  149. /* This function builds a string representation of
  150. * the nexthop chain using the ALL_NEXTHOPS_RO macro.
  151. * It verifies that the ALL_NEXTHOPS_RO macro iterated
  152. * correctly over the nexthop chain by comparing the
  153. * generated representation with the expected representation.
  154. */
  155. static void
  156. nexthop_chain_verify_iter(struct nexthop_chain *nc)
  157. {
  158. struct nexthop *nh, *tnh;
  159. int recursing;
  160. char *repr = NULL;
  161. for (ALL_NEXTHOPS_RO(nc->head, nh, tnh, recursing))
  162. {
  163. if (recursing)
  164. str_appendf(&repr, " %p\n", nh);
  165. else
  166. str_appendf(&repr, "%p\n", nh);
  167. }
  168. if (repr && verbose)
  169. printf("===\n%s", repr);
  170. assert((!repr && !nc->repr) || (repr && nc->repr && !strcmp(repr, nc->repr)));
  171. free(repr);
  172. }
  173. /* This test run builds a simple nexthop chain
  174. * with some recursive nexthops and verifies that
  175. * the iterator works correctly in each stage along
  176. * the way.
  177. */
  178. static void
  179. test_run_first(void)
  180. {
  181. struct nexthop_chain *nc;
  182. nc = nexthop_chain_new();
  183. nexthop_chain_verify_iter(nc);
  184. nexthop_chain_add_top(nc);
  185. nexthop_chain_verify_iter(nc);
  186. nexthop_chain_add_top(nc);
  187. nexthop_chain_verify_iter(nc);
  188. nexthop_chain_add_recursive(nc);
  189. nexthop_chain_verify_iter(nc);
  190. nexthop_chain_add_recursive(nc);
  191. nexthop_chain_verify_iter(nc);
  192. nexthop_chain_add_top(nc);
  193. nexthop_chain_verify_iter(nc);
  194. nexthop_chain_add_top(nc);
  195. nexthop_chain_verify_iter(nc);
  196. nexthop_chain_add_top(nc);
  197. nexthop_chain_verify_iter(nc);
  198. nexthop_chain_add_recursive(nc);
  199. nexthop_chain_verify_iter(nc);
  200. nexthop_chain_add_recursive(nc);
  201. nexthop_chain_verify_iter(nc);
  202. nexthop_chain_add_recursive(nc);
  203. nexthop_chain_verify_iter(nc);
  204. nexthop_chain_free(nc);
  205. }
  206. /* This test run builds numerous random
  207. * nexthop chain configurations and verifies
  208. * that the iterator correctly progresses
  209. * through each. */
  210. static void
  211. test_run_prng(void)
  212. {
  213. struct nexthop_chain *nc;
  214. struct prng *prng;
  215. int i;
  216. nc = nexthop_chain_new();
  217. prng = prng_new(0);
  218. for (i = 0; i < 1000000; i++)
  219. {
  220. switch (prng_rand(prng) % 10)
  221. {
  222. case 0:
  223. nexthop_chain_clear(nc);
  224. break;
  225. case 1:
  226. case 2:
  227. case 3:
  228. case 4:
  229. case 5:
  230. nexthop_chain_add_top(nc);
  231. break;
  232. case 6:
  233. case 7:
  234. case 8:
  235. case 9:
  236. if (nc->current_top)
  237. nexthop_chain_add_recursive(nc);
  238. break;
  239. }
  240. nexthop_chain_verify_iter(nc);
  241. }
  242. nexthop_chain_free(nc);
  243. prng_free(prng);
  244. }
  245. int main(int argc, char **argv)
  246. {
  247. if (argc >= 2 && !strcmp("-v", argv[1]))
  248. verbose = 1;
  249. test_run_first();
  250. printf("Simple test passed.\n");
  251. test_run_prng();
  252. printf("PRNG test passed.\n");
  253. }