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 thread_master *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(test->log, log_free);
 125         hash_free(test->log);
 126         XFREE(MTYPE_TMP, test);
 127 }
 128
 129 static void test_state_add_route(struct test_state *test,
 130                                  struct prefix_ipv6 *dst_p,
 131                                  struct prefix_ipv6 *src_p)
 132 {
 133         struct route_node *rn =
 134                 srcdest_rnode_get(test->table, (struct prefix *)dst_p, src_p);
 135         struct prefix hash_entry[2];
 136
 137         memset(hash_entry, 0, sizeof(hash_entry));
 138         memcpy(&hash_entry[0], dst_p, sizeof(*dst_p));
 139         memcpy(&hash_entry[1], src_p, sizeof(*src_p));
 140
 141         if (rn->info) {
 142                 route_unlock_node(rn);
 143                 assert(hash_lookup(test->log, hash_entry) != NULL);
 144                 return;
 145         } else {
 146                 assert(hash_lookup(test->log, hash_entry) == NULL);
 147         }
 148
 149         rn->info = (void *)0xdeadbeef;
 150         (void)hash_get(test->log, hash_entry, log_alloc);
 151 };
 152
 153 static void test_state_del_route(struct test_state *test,
 154                                  struct prefix_ipv6 *dst_p,
 155                                  struct prefix_ipv6 *src_p)
 156 {
 157         struct route_node *rn = srcdest_rnode_lookup(
 158                 test->table, (struct prefix *)dst_p, src_p);
 159         struct prefix hash_entry[2];
 160
 161         memset(hash_entry, 0, sizeof(hash_entry));
 162         memcpy(&hash_entry[0], dst_p, sizeof(*dst_p));
 163         memcpy(&hash_entry[1], src_p, sizeof(*src_p));
 164
 165         if (!rn) {
 166                 assert(!hash_lookup(test->log, hash_entry));
 167                 return;
 168         }
 169
 170         assert(rn->info == (void *)0xdeadbeef);
 171         rn->info = NULL;
 172         route_unlock_node(rn);
 173         route_unlock_node(rn);
 174
 175         struct prefix *hash_entry_intern = hash_release(test->log, hash_entry);
 176         assert(hash_entry_intern != NULL);
 177         XFREE(MTYPE_TMP, hash_entry_intern);
 178 }
 179
 180 static void verify_log(struct hash_bucket *bucket, void *arg)
 181 {
 182         struct test_state *test = arg;
 183         struct prefix *hash_entry = bucket->data;
 184         struct prefix *dst_p = &hash_entry[0];
 185         struct prefix_ipv6 *src_p = (struct prefix_ipv6 *)&hash_entry[1];
 186         struct route_node *rn = srcdest_rnode_lookup(test->table, dst_p, src_p);
 187
 188         assert(rn);
 189         assert(rn->info == (void *)0xdeadbeef);
 190
 191         route_unlock_node(rn);
 192 }
 193
 194 static void dump_log(struct hash_bucket *bucket, void *arg)
 195 {
 196         struct prefix *hash_entry = bucket->data;
 197         struct prefix_ipv6 *dst_p = (struct prefix_ipv6 *)&hash_entry[0];
 198         struct prefix_ipv6 *src_p = (struct prefix_ipv6 *)&hash_entry[1];
 199         char *route_id = format_srcdest(dst_p, src_p);
 200
 201         fprintf(stderr, "  %s\n", route_id);
 202         free(route_id);
 203 }
 204
 205 static void test_dump(struct test_state *test)
 206 {
 207         fprintf(stderr, "Contents of hash table:\n");
 208         hash_iterate(test->log, dump_log, test);
 209         fprintf(stderr, "\n");
 210 }
 211
 212 static void test_failed(struct test_state *test, const char *message,
 213                         const struct prefix_ipv6 *dst_p,
 214                         const struct prefix_ipv6 *src_p)
 215 {
 216         char *route_id = format_srcdest(dst_p, src_p);
 217
 218         fprintf(stderr, "Test failed. Error: %s\n", message);
 219         fprintf(stderr, "Route in question: %s\n", route_id);
 220         free(route_id);
 221
 222         test_dump(test);
 223         assert(3 == 4);
 224 }
 225
 226 static void test_state_verify(struct test_state *test)
 227 {
 228         struct route_node *rn;
 229         struct prefix hash_entry[2];
 230
 231         memset(hash_entry, 0, sizeof(hash_entry));
 232
 233         /* Verify that there are no elements in the table which have never
 234          * been added */
 235         for (rn = route_top(test->table); rn; rn = srcdest_route_next(rn)) {
 236                 const struct prefix_ipv6 *dst_p, *src_p;
 237
 238                 /* While we are iterating, we hold a lock on the current
 239                  * route_node,
 240                  * so all the lock counts we check for take that into account;
 241                  * in idle
 242                  * state all the numbers will be exactly one less.
 243                  *
 244                  * Also this makes quite some assumptions based on the current
 245                  * implementation details of route_table and srcdest_table -
 246                  * another
 247                  * valid implementation might trigger assertions here.
 248                  */
 249
 250                 if (rnode_is_dstnode(rn)) {
 251                         struct srcdest_rnode *srn = (struct srcdest_rnode *)rn;
 252                         unsigned int expected_lock = 1; /* We are in the loop */
 253
 254                         if (rn->info
 255                             != NULL) /* The route node is not internal */
 256                                 expected_lock++;
 257                         if (srn->src_table != NULL) /* There's a source table
 258                                                        associated with rn */
 259                                 expected_lock++;
 260
 261                         if (route_node_get_lock_count(rn) != expected_lock)
 262                                 test_failed(
 263                                         test,
 264                                         "Dest rnode lock count doesn't match expected count!",
 265                                         (struct prefix_ipv6 *)&rn->p, NULL);
 266                 } else {
 267                         unsigned int expected_lock = 1; /* We are in the loop */
 268
 269                         if (rn->info
 270                             != NULL) /* The route node is not internal */
 271                                 expected_lock++;
 272
 273                         if (route_node_get_lock_count(rn) != expected_lock) {
 274                                 srcdest_rnode_prefixes(
 275                                         rn, (const struct prefix **)&dst_p,
 276                                         (const struct prefix **)&src_p);
 277
 278                                 test_failed(
 279                                         test,
 280                                         "Src rnode lock count doesn't match expected count!",
 281                                         dst_p, src_p);
 282                         }
 283                 }
 284
 285                 if (!rn->info)
 286                         continue;
 287
 288                 assert(rn->info == (void *)0xdeadbeef);
 289
 290                 srcdest_rnode_prefixes(rn, (const struct prefix **)&dst_p,
 291                                        (const struct prefix **)&src_p);
 292                 memcpy(&hash_entry[0], dst_p, sizeof(*dst_p));
 293                 if (src_p)
 294                         memcpy(&hash_entry[1], src_p, sizeof(*src_p));
 295                 else
 296                         memset(&hash_entry[1], 0, sizeof(hash_entry[1]));
 297
 298                 if (hash_lookup(test->log, hash_entry) == NULL)
 299                         test_failed(test, "Route is missing in hash", dst_p,
 300                                     src_p);
 301         }
 302
 303         /* Verify that all added elements are still in the table */
 304         hash_iterate(test->log, verify_log, test);
 305 }
 306
 307 static void get_rand_prefix(struct prng *prng, struct prefix_ipv6 *p)
 308 {
 309         int i;
 310
 311         memset(p, 0, sizeof(*p));
 312
 313         for (i = 0; i < 4; i++)
 314                 p->prefix.s6_addr32[i] = prng_rand(prng);
 315         p->prefixlen = prng_rand(prng) % 129;
 316         p->family = AF_INET6;
 317
 318         apply_mask(p);
 319 }
 320
 321 static void get_rand_prefix_pair(struct prng *prng, struct prefix_ipv6 *dst_p,
 322                                  struct prefix_ipv6 *src_p)
 323 {
 324         get_rand_prefix(prng, dst_p);
 325         if ((prng_rand(prng) % 4) == 0) {
 326                 get_rand_prefix(prng, src_p);
 327                 if (src_p->prefixlen)
 328                         return;
 329         }
 330
 331         memset(src_p, 0, sizeof(*src_p));
 332 }
 333
 334 static void test_state_add_rand_route(struct test_state *test,
 335                                       struct prng *prng)
 336 {
 337         struct prefix_ipv6 dst_p, src_p;
 338
 339         get_rand_prefix_pair(prng, &dst_p, &src_p);
 340         test_state_add_route(test, &dst_p, &src_p);
 341 }
 342
 343 static void test_state_del_rand_route(struct test_state *test,
 344                                       struct prng *prng)
 345 {
 346         struct prefix_ipv6 dst_p, src_p;
 347
 348         get_rand_prefix_pair(prng, &dst_p, &src_p);
 349         test_state_del_route(test, &dst_p, &src_p);
 350 }
 351
 352 static void test_state_del_one_route(struct test_state *test, struct prng *prng)
 353 {
 354         unsigned int which_route;
 355
 356         if (test->log->count == 0)
 357                 return;
 358
 359         which_route = prng_rand(prng) % test->log->count;
 360
 361         struct route_node *rn;
 362         const struct prefix *dst_p, *src_p;
 363         struct prefix_ipv6 dst6_p, src6_p;
 364
 365         for (rn = route_top(test->table); rn; rn = srcdest_route_next(rn)) {
 366                 if (!rn->info)
 367                         continue;
 368                 if (!which_route) {
 369                         route_unlock_node(rn);
 370                         break;
 371                 }
 372                 which_route--;
 373         }
 374
 375         assert(rn);
 376         srcdest_rnode_prefixes(rn, &dst_p, &src_p);
 377         memcpy(&dst6_p, dst_p, sizeof(dst6_p));
 378         if (src_p)
 379                 memcpy(&src6_p, src_p, sizeof(src6_p));
 380         else
 381                 memset(&src6_p, 0, sizeof(src6_p));
 382
 383         test_state_del_route(test, &dst6_p, &src6_p);
 384 }
 385
 386 static void run_prng_test(void)
 387 {
 388         struct test_state *test = test_state_new();
 389         struct prng *prng = prng_new(0);
 390         size_t i;
 391
 392         for (i = 0; i < 1000; i++) {
 393                 switch (prng_rand(prng) % 10) {
 394                 case 0:
 395                 case 1:
 396                 case 2:
 397                 case 3:
 398                 case 4:
 399                         test_state_add_rand_route(test, prng);
 400                         break;
 401                 case 5:
 402                 case 6:
 403                 case 7:
 404                         test_state_del_one_route(test, prng);
 405                         break;
 406                 case 8:
 407                 case 9:
 408                         test_state_del_rand_route(test, prng);
 409                         break;
 410                 }
 411                 test_state_verify(test);
 412         }
 413
 414         prng_free(prng);
 415         test_state_free(test);
 416 }
 417
 418 int main(int argc, char *argv[])
 419 {
 420         run_prng_test();
 421         printf("PRNG Test successful.\n");
 422         return 0;
 423 }