tests/lib/test_srcdest_table.c

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