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