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