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