tests/lib/test_srcdest_table.c

   1 /*
   2  * Test srcdest table for correctness.
   3  *
   4  * Copyright (C) 2017 by David Lamparter & Christian Franke,
   5  *                       Open Source Routing / NetDEF Inc.
   6  *
   7  * This file is part of FreeRangeRouting (FRR)
   8  *
   9  * FRR is free software; you can redistribute it and/or modify it
  10  * under the terms of the GNU General Public License as published by the
  11  * Free Software Foundation; either version 2, or (at your option) any
  12  * later version.
  13  *
  14  * FRR is distributed in the hope that it will be useful, but
  15  * WITHOUT ANY WARRANTY; without even the implied warranty of
  16  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  17  * General Public License for more details.
  18  *
  19  * You should have received a copy of the GNU General Public License along
  20  * with this program; see the file COPYING; if not, write to the Free Software
  21  * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
  22  */
  23
  24 #include <zebra.h>
  25
  26 #include "hash.h"
  27 #include "memory.h"
  28 #include "prefix.h"
  29 #include "prng.h"
  30 #include "srcdest_table.h"
  31 #include "table.h"
  32
  33 /* Copied from ripngd/ripng_nexthop.h - maybe the whole s6_addr32 thing
  34  * should be added by autoconf if not present?
  35  */
  36 #ifndef s6_addr32
  37 #if defined(SUNOS_5)
  38 /* Some SunOS define s6_addr32 only to kernel */
  39 #define s6_addr32 _S6_un._S6_u32
  40 #else
  41 #define s6_addr32 __u6_addr.__u6_addr32
  42 #endif /* SUNOS_5 */
  43 #endif /*s6_addr32*/
  44
  45 struct thread_master *master;
  46
  47 /* This structure is copied from lib/srcdest_table.c to which it is
  48  * private as far as other parts of Quagga are concerned.
  49  */
  50 struct srcdest_rnode
  51 {
  52   /* must be first in structure for casting to/from route_node */
  53   ROUTE_NODE_FIELDS;
  54
  55   struct route_table *src_table;
  56 };
  57
  58 struct test_state
  59 {
  60   struct route_table *table;
  61   struct hash *log;
  62 };
  63
  64 static char *
  65 format_srcdest(const struct prefix_ipv6 *dst_p,
  66                const struct prefix_ipv6 *src_p)
  67 {
  68   char dst_str[BUFSIZ];
  69   char src_str[BUFSIZ];
  70   char *rv;
  71   int ec;
  72
  73   prefix2str((const struct prefix*)dst_p, dst_str, sizeof(dst_str));
  74   if (src_p && src_p->prefixlen)
  75     prefix2str((const struct prefix*)src_p, src_str, sizeof(src_str));
  76   else
  77     src_str[0] = '\0';
  78
  79   ec = asprintf(&rv, "%s%s%s", dst_str,
  80                 (src_str[0] != '\0') ? " from " : "",
  81                 src_str);
  82
  83   assert(ec > 0);
  84   return rv;
  85 }
  86
  87 static unsigned int log_key(void *data)
  88 {
  89   struct prefix *hash_entry = data;
  90   struct prefix_ipv6 *dst_p = (struct prefix_ipv6*) &hash_entry[0];
  91   struct prefix_ipv6 *src_p = (struct prefix_ipv6*) &hash_entry[1];
  92   unsigned int hash = 0;
  93   unsigned int i;
  94
  95   hash = (hash * 33) ^ (unsigned int)dst_p->prefixlen;
  96   for (i = 0; i < 4; i++)
  97     hash = (hash * 33) ^ (unsigned int)dst_p->prefix.s6_addr32[i];
  98
  99   hash = (hash * 33) ^ (unsigned int)src_p->prefixlen;
 100   if (src_p->prefixlen)
 101     for (i = 0; i < 4; i++)
 102       hash = (hash * 33) ^ (unsigned int)src_p->prefix.s6_addr32[i];
 103
 104   return hash;
 105 }
 106
 107 static int
 108 log_cmp(const void *a, const void *b)
 109 {
 110   if (a == NULL && b != NULL)
 111     return 0;
 112   if (b == NULL && a != NULL)
 113     return 0;
 114
 115   return !memcmp(a, b, 2 * sizeof(struct prefix));
 116 }
 117
 118 static void
 119 log_free(void *data)
 120 {
 121   XFREE(MTYPE_TMP, data);
 122 }
 123
 124 static void *
 125 log_alloc(void *data)
 126 {
 127   void *rv = XMALLOC(MTYPE_TMP, 2 * sizeof(struct prefix));
 128   memcpy(rv, data, 2 * sizeof(struct prefix));
 129   return rv;
 130 }
 131
 132 static struct test_state *
 133 test_state_new(void)
 134 {
 135   struct test_state *rv;
 136
 137   rv = XCALLOC(MTYPE_TMP, sizeof(*rv));
 138   assert(rv);
 139
 140   rv->table = srcdest_table_init();
 141   assert(rv->table);
 142
 143   rv->log = hash_create(log_key, log_cmp, NULL);
 144   return rv;
 145 }
 146
 147 static void
 148 test_state_free(struct test_state *test)
 149 {
 150   route_table_finish(test->table);
 151   hash_clean(test->log, log_free);
 152   hash_free(test->log);
 153   XFREE(MTYPE_TMP, test);
 154 }
 155
 156 static void
 157 test_state_add_route(struct test_state *test,
 158                      struct prefix_ipv6 *dst_p,
 159                      struct prefix_ipv6 *src_p)
 160 {
 161   struct route_node *rn = srcdest_rnode_get(
 162       test->table, (struct prefix*)dst_p, src_p
 163   );
 164   struct prefix hash_entry[2];
 165
 166   memset(hash_entry, 0, sizeof(hash_entry));
 167   memcpy(&hash_entry[0], dst_p, sizeof(*dst_p));
 168   memcpy(&hash_entry[1], src_p, sizeof(*src_p));
 169
 170   if (rn->info) {
 171     route_unlock_node(rn);
 172     assert(hash_lookup(test->log, hash_entry) != NULL);
 173     return;
 174   } else {
 175     assert(hash_lookup(test->log, hash_entry) == NULL);
 176   }
 177
 178   rn->info = (void*) 0xdeadbeef;
 179   hash_get(test->log, hash_entry, log_alloc);
 180 };
 181
 182 static void
 183 test_state_del_route(struct test_state *test,
 184                      struct prefix_ipv6 *dst_p,
 185                      struct prefix_ipv6 *src_p)
 186 {
 187   struct route_node *rn = srcdest_rnode_lookup(
 188       test->table, (struct prefix*)dst_p, src_p
 189   );
 190   struct prefix hash_entry[2];
 191
 192   memset(hash_entry, 0, sizeof(hash_entry));
 193   memcpy(&hash_entry[0], dst_p, sizeof(*dst_p));
 194   memcpy(&hash_entry[1], src_p, sizeof(*src_p));
 195
 196   if (!rn) {
 197     assert(!hash_lookup(test->log, hash_entry));
 198     return;
 199   }
 200
 201   assert(rn->info == (void*)0xdeadbeef);
 202   rn->info = NULL;
 203   route_unlock_node(rn);
 204   route_unlock_node(rn);
 205
 206   struct prefix *hash_entry_intern = hash_release(test->log, hash_entry);
 207   assert(hash_entry_intern != NULL);
 208   XFREE(MTYPE_TMP, hash_entry_intern);
 209 }
 210
 211 static void
 212 verify_log(struct hash_backet* backet, void *arg)
 213 {
 214   struct test_state *test = arg;
 215   struct prefix *hash_entry = backet->data;
 216   struct prefix *dst_p = &hash_entry[0];
 217   struct prefix_ipv6 *src_p = (struct prefix_ipv6*)&hash_entry[1];
 218   struct route_node *rn = srcdest_rnode_lookup(test->table, dst_p, src_p);
 219
 220   assert(rn);
 221   assert(rn->info == (void*)0xdeadbeef);
 222
 223   route_unlock_node(rn);
 224 }
 225
 226 static void
 227 dump_log(struct hash_backet* backet, void *arg)
 228 {
 229   struct prefix *hash_entry = backet->data;
 230   struct prefix_ipv6 *dst_p = (struct prefix_ipv6*)&hash_entry[0];
 231   struct prefix_ipv6 *src_p = (struct prefix_ipv6*)&hash_entry[1];
 232   char *route_id = format_srcdest(dst_p, src_p);
 233
 234   fprintf(stderr, "  %s\n", route_id);
 235   free(route_id);
 236 }
 237
 238 static void
 239 test_dump(struct test_state *test)
 240 {
 241   fprintf(stderr, "Contents of hash table:\n");
 242   hash_iterate(test->log, dump_log, test);
 243   fprintf(stderr, "\n");
 244 }
 245
 246 static void
 247 test_failed(struct test_state *test, const char *message,
 248             struct prefix_ipv6 *dst_p, struct prefix_ipv6 *src_p)
 249 {
 250   char *route_id = format_srcdest(dst_p, src_p);
 251
 252   fprintf(stderr, "Test failed. Error: %s\n", message);
 253   fprintf(stderr, "Route in question: %s\n", route_id);
 254   free(route_id);
 255
 256   test_dump(test);
 257   assert(3 == 4);
 258 }
 259
 260 static void
 261 test_state_verify(struct test_state *test)
 262 {
 263   struct route_node *rn;
 264   struct prefix hash_entry[2];
 265
 266   memset(hash_entry, 0, sizeof(hash_entry));
 267
 268   /* Verify that there are no elements in the table which have never
 269    * been added */
 270   for (rn = route_top(test->table); rn; rn = srcdest_route_next(rn))
 271     {
 272       struct prefix_ipv6 *dst_p, *src_p;
 273
 274       /* While we are iterating, we hold a lock on the current route_node,
 275        * so all the lock counts we check for take that into account; in idle
 276        * state all the numbers will be exactly one less.
 277        *
 278        * Also this makes quite some assumptions based on the current
 279        * implementation details of route_table and srcdest_table - another
 280        * valid implementation might trigger assertions here.
 281        */
 282
 283       if (rnode_is_dstnode(rn))
 284         {
 285           struct srcdest_rnode *srn = (struct srcdest_rnode *)rn;
 286           unsigned int expected_lock = 1; /* We are in the loop */
 287
 288           if (rn->info != NULL) /* The route node is not internal */
 289             expected_lock++;
 290           if (srn->src_table != NULL) /* There's a source table associated with rn */
 291             expected_lock++;
 292
 293           if (rn->lock != expected_lock)
 294             test_failed(test, "Dest rnode lock count doesn't match expected count!",
 295                         (struct prefix_ipv6*)&rn->p, NULL);
 296         }
 297       else
 298         {
 299           unsigned int expected_lock = 1; /* We are in the loop */
 300
 301           if (rn->info != NULL) /* The route node is not internal */
 302             expected_lock++;
 303
 304           if (rn->lock != expected_lock)
 305             {
 306               struct prefix_ipv6 *dst_p, *src_p;
 307               srcdest_rnode_prefixes(rn, (struct prefix**)&dst_p,
 308                                          (struct prefix**)&src_p);
 309
 310               test_failed(test, "Src rnode lock count doesn't match expected count!",
 311                           dst_p, src_p);
 312             }
 313         }
 314
 315       if (!rn->info)
 316         continue;
 317
 318       assert(rn->info == (void*)0xdeadbeef);
 319
 320       srcdest_rnode_prefixes(rn, (struct prefix**)&dst_p, (struct prefix**)&src_p);
 321       memcpy(&hash_entry[0], dst_p, sizeof(*dst_p));
 322       if (src_p)
 323         memcpy(&hash_entry[1], src_p, sizeof(*src_p));
 324       else
 325         memset(&hash_entry[1], 0, sizeof(hash_entry[1]));
 326
 327       if (hash_lookup(test->log, hash_entry) == NULL)
 328         test_failed(test, "Route is missing in hash", dst_p, src_p);
 329     }
 330
 331   /* Verify that all added elements are still in the table */
 332   hash_iterate(test->log, verify_log, test);
 333 }
 334
 335 static void
 336 get_rand_prefix(struct prng *prng, struct prefix_ipv6 *p)
 337 {
 338   int i;
 339
 340   memset(p, 0, sizeof(*p));
 341
 342   for (i = 0; i < 4; i++)
 343     p->prefix.s6_addr32[i] = prng_rand(prng);
 344   p->prefixlen = prng_rand(prng) % 129;
 345   p->family = AF_INET6;
 346
 347   apply_mask((struct prefix*)p);
 348 }
 349
 350 static void
 351 get_rand_prefix_pair(struct prng *prng, struct prefix_ipv6 *dst_p,
 352                      struct prefix_ipv6 *src_p)
 353 {
 354   get_rand_prefix(prng, dst_p);
 355   if ((prng_rand(prng) % 4) == 0)
 356     {
 357       get_rand_prefix(prng, src_p);
 358       if (src_p->prefixlen)
 359         return;
 360     }
 361
 362   memset(src_p, 0, sizeof(*src_p));
 363 }
 364
 365 static void
 366 test_state_add_rand_route(struct test_state *test,
 367                           struct prng *prng)
 368 {
 369   struct prefix_ipv6 dst_p, src_p;
 370
 371   get_rand_prefix_pair(prng, &dst_p, &src_p);
 372   test_state_add_route(test, &dst_p, &src_p);
 373 }
 374
 375 static void
 376 test_state_del_rand_route(struct test_state *test,
 377                           struct prng *prng)
 378 {
 379   struct prefix_ipv6 dst_p, src_p;
 380
 381   get_rand_prefix_pair(prng, &dst_p, &src_p);
 382   test_state_del_route(test, &dst_p, &src_p);
 383 }
 384
 385 static void
 386 test_state_del_one_route(struct test_state *test,
 387                          struct prng *prng)
 388 {
 389   unsigned int which_route = prng_rand(prng) % test->log->count;
 390   struct route_node *rn;
 391   struct prefix *dst_p, *src_p;
 392   struct prefix_ipv6 dst6_p, src6_p;
 393
 394   for (rn = route_top(test->table); rn; rn = srcdest_route_next(rn))
 395     {
 396       if (!rn->info)
 397         continue;
 398       if (!which_route) {
 399         route_unlock_node(rn);
 400         break;
 401       }
 402       which_route--;
 403     }
 404
 405   assert(rn);
 406   srcdest_rnode_prefixes(rn, &dst_p, &src_p);
 407   memcpy(&dst6_p, dst_p, sizeof(dst6_p));
 408   if (src_p)
 409     memcpy(&src6_p, src_p, sizeof(src6_p));
 410   else
 411     memset(&src6_p, 0, sizeof(src6_p));
 412
 413   test_state_del_route(test, &dst6_p, &src6_p);
 414 }
 415
 416 static void
 417 run_prng_test(void)
 418 {
 419   struct test_state *test = test_state_new();
 420   struct prng *prng = prng_new(0);
 421   size_t i;
 422
 423   for (i = 0; i < 1000; i++)
 424     {
 425       switch (prng_rand(prng) % 10)
 426         {
 427         case 0:
 428         case 1:
 429         case 2:
 430         case 3:
 431         case 4:
 432           test_state_add_rand_route(test, prng);
 433           break;
 434         case 5:
 435         case 6:
 436         case 7:
 437           test_state_del_one_route(test, prng);
 438           break;
 439         case 8:
 440         case 9:
 441           test_state_del_rand_route(test, prng);
 442           break;
 443         }
 444       test_state_verify(test);
 445     }
 446
 447   prng_free(prng);
 448   test_state_free(test);
 449 }
 450
 451 int main(int argc, char *argv[])
 452 {
 453   run_prng_test();
 454   printf("PRNG Test successful.\n");
 455   return 0;
 456 }