diff options
Diffstat (limited to 'tests/lib/test_srcdest_table.c')
| -rw-r--r-- | tests/lib/test_srcdest_table.c | 436 |
1 files changed, 436 insertions, 0 deletions
diff --git a/tests/lib/test_srcdest_table.c b/tests/lib/test_srcdest_table.c new file mode 100644 index 0000000..2d8f024 --- /dev/null +++ b/tests/lib/test_srcdest_table.c @@ -0,0 +1,436 @@ +/* + * Test srcdest table for correctness. + * + * Copyright (C) 2017 by David Lamparter & Christian Franke, + * Open Source Routing / NetDEF Inc. + * + * This file is part of FRRouting (FRR) + * + * FRR is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License as published by the + * Free Software Foundation; either version 2, or (at your option) any + * later version. + * + * FRR is distributed in the hope that it will be useful, but + * WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * General Public License for more details. + * + * You should have received a copy of the GNU General Public License along + * with this program; see the file COPYING; if not, write to the Free Software + * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA + */ + +#include <zebra.h> + +#include "hash.h" +#include "memory.h" +#include "prefix.h" +#include "prng.h" +#include "srcdest_table.h" +#include "table.h" + +/* Copied from ripngd/ripng_nexthop.h - maybe the whole s6_addr32 thing + * should be added by autoconf if not present? + */ +#ifndef s6_addr32 +#define s6_addr32 __u6_addr.__u6_addr32 +#endif /*s6_addr32*/ + +struct thread_master *master; + +/* This structure is copied from lib/srcdest_table.c to which it is + * private as far as other parts of Quagga are concerned. + */ +struct srcdest_rnode { + /* must be first in structure for casting to/from route_node */ + ROUTE_NODE_FIELDS; + + struct route_table *src_table; +}; + +struct test_state { + struct route_table *table; + struct hash *log; +}; + +static char *format_srcdest(const struct prefix_ipv6 *dst_p, + const struct prefix_ipv6 *src_p) +{ + char dst_str[BUFSIZ]; + char src_str[BUFSIZ]; + char *rv; + int ec; + + prefix2str((const struct prefix *)dst_p, dst_str, sizeof(dst_str)); + if (src_p && src_p->prefixlen) + prefix2str((const struct prefix *)src_p, src_str, + sizeof(src_str)); + else + src_str[0] = '\0'; + + ec = asprintf(&rv, "%s%s%s", dst_str, + (src_str[0] != '\0') ? " from " : "", src_str); + + assert(ec > 0); + return rv; +} + +static unsigned int log_key(const void *data) +{ + const struct prefix *hash_entry = data; + struct prefix_ipv6 *dst_p = (struct prefix_ipv6 *)&hash_entry[0]; + struct prefix_ipv6 *src_p = (struct prefix_ipv6 *)&hash_entry[1]; + unsigned int hash = 0; + unsigned int i; + + hash = (hash * 33) ^ (unsigned int)dst_p->prefixlen; + for (i = 0; i < 4; i++) + hash = (hash * 33) ^ (unsigned int)dst_p->prefix.s6_addr32[i]; + + hash = (hash * 33) ^ (unsigned int)src_p->prefixlen; + if (src_p->prefixlen) + for (i = 0; i < 4; i++) + hash = (hash * 33) + ^ (unsigned int)src_p->prefix.s6_addr32[i]; + + return hash; +} + +static bool log_cmp(const void *a, const void *b) +{ + if (a == NULL || b == NULL) + return false; + + return !memcmp(a, b, 2 * sizeof(struct prefix)); +} + +static void log_free(void *data) +{ + XFREE(MTYPE_TMP, data); +} + +static void *log_alloc(void *data) +{ + void *rv = XMALLOC(MTYPE_TMP, 2 * sizeof(struct prefix)); + memcpy(rv, data, 2 * sizeof(struct prefix)); + return rv; +} + +static struct test_state *test_state_new(void) +{ + struct test_state *rv; + + rv = XCALLOC(MTYPE_TMP, sizeof(*rv)); + assert(rv); + + rv->table = srcdest_table_init(); + assert(rv->table); + + rv->log = hash_create(log_key, log_cmp, NULL); + return rv; +} + +static void test_state_free(struct test_state *test) +{ + route_table_finish(test->table); + hash_clean(test->log, log_free); + hash_free(test->log); + XFREE(MTYPE_TMP, test); +} + +static void test_state_add_route(struct test_state *test, + struct prefix_ipv6 *dst_p, + struct prefix_ipv6 *src_p) +{ + struct route_node *rn = + srcdest_rnode_get(test->table, (struct prefix *)dst_p, src_p); + struct prefix hash_entry[2]; + + memset(hash_entry, 0, sizeof(hash_entry)); + memcpy(&hash_entry[0], dst_p, sizeof(*dst_p)); + memcpy(&hash_entry[1], src_p, sizeof(*src_p)); + + if (rn->info) { + route_unlock_node(rn); + assert(hash_lookup(test->log, hash_entry) != NULL); + return; + } else { + assert(hash_lookup(test->log, hash_entry) == NULL); + } + + rn->info = (void *)0xdeadbeef; + (void)hash_get(test->log, hash_entry, log_alloc); +}; + +static void test_state_del_route(struct test_state *test, + struct prefix_ipv6 *dst_p, + struct prefix_ipv6 *src_p) +{ + struct route_node *rn = srcdest_rnode_lookup( + test->table, (struct prefix *)dst_p, src_p); + struct prefix hash_entry[2]; + + memset(hash_entry, 0, sizeof(hash_entry)); + memcpy(&hash_entry[0], dst_p, sizeof(*dst_p)); + memcpy(&hash_entry[1], src_p, sizeof(*src_p)); + + if (!rn) { + assert(!hash_lookup(test->log, hash_entry)); + return; + } + + assert(rn->info == (void *)0xdeadbeef); + rn->info = NULL; + route_unlock_node(rn); + route_unlock_node(rn); + + struct prefix *hash_entry_intern = hash_release(test->log, hash_entry); + assert(hash_entry_intern != NULL); + XFREE(MTYPE_TMP, hash_entry_intern); +} + +static void verify_log(struct hash_bucket *bucket, void *arg) +{ + struct test_state *test = arg; + struct prefix *hash_entry = bucket->data; + struct prefix *dst_p = &hash_entry[0]; + struct prefix_ipv6 *src_p = (struct prefix_ipv6 *)&hash_entry[1]; + struct route_node *rn = srcdest_rnode_lookup(test->table, dst_p, src_p); + + assert(rn); + assert(rn->info == (void *)0xdeadbeef); + + route_unlock_node(rn); +} + +static void dump_log(struct hash_bucket *bucket, void *arg) +{ + struct prefix *hash_entry = bucket->data; + struct prefix_ipv6 *dst_p = (struct prefix_ipv6 *)&hash_entry[0]; + struct prefix_ipv6 *src_p = (struct prefix_ipv6 *)&hash_entry[1]; + char *route_id = format_srcdest(dst_p, src_p); + + fprintf(stderr, " %s\n", route_id); + free(route_id); +} + +static void test_dump(struct test_state *test) +{ + fprintf(stderr, "Contents of hash table:\n"); + hash_iterate(test->log, dump_log, test); + fprintf(stderr, "\n"); +} + +static void test_failed(struct test_state *test, const char *message, + const struct prefix_ipv6 *dst_p, + const struct prefix_ipv6 *src_p) +{ + char *route_id = format_srcdest(dst_p, src_p); + + fprintf(stderr, "Test failed. Error: %s\n", message); + fprintf(stderr, "Route in question: %s\n", route_id); + free(route_id); + + test_dump(test); + assert(3 == 4); +} + +static void test_state_verify(struct test_state *test) +{ + struct route_node *rn; + struct prefix hash_entry[2]; + + memset(hash_entry, 0, sizeof(hash_entry)); + + /* Verify that there are no elements in the table which have never + * been added */ + for (rn = route_top(test->table); rn; rn = srcdest_route_next(rn)) { + const struct prefix_ipv6 *dst_p, *src_p; + + /* While we are iterating, we hold a lock on the current + * route_node, + * so all the lock counts we check for take that into account; + * in idle + * state all the numbers will be exactly one less. + * + * Also this makes quite some assumptions based on the current + * implementation details of route_table and srcdest_table - + * another + * valid implementation might trigger assertions here. + */ + + if (rnode_is_dstnode(rn)) { + struct srcdest_rnode *srn = (struct srcdest_rnode *)rn; + unsigned int expected_lock = 1; /* We are in the loop */ + + if (rn->info + != NULL) /* The route node is not internal */ + expected_lock++; + if (srn->src_table != NULL) /* There's a source table + associated with rn */ + expected_lock++; + + if (route_node_get_lock_count(rn) != expected_lock) + test_failed( + test, + "Dest rnode lock count doesn't match expected count!", + (struct prefix_ipv6 *)&rn->p, NULL); + } else { + unsigned int expected_lock = 1; /* We are in the loop */ + + if (rn->info + != NULL) /* The route node is not internal */ + expected_lock++; + + if (route_node_get_lock_count(rn) != expected_lock) { + srcdest_rnode_prefixes( + rn, (const struct prefix **)&dst_p, + (const struct prefix **)&src_p); + + test_failed( + test, + "Src rnode lock count doesn't match expected count!", + dst_p, src_p); + } + } + + if (!rn->info) + continue; + + assert(rn->info == (void *)0xdeadbeef); + + srcdest_rnode_prefixes(rn, (const struct prefix **)&dst_p, + (const struct prefix **)&src_p); + memcpy(&hash_entry[0], dst_p, sizeof(*dst_p)); + if (src_p) + memcpy(&hash_entry[1], src_p, sizeof(*src_p)); + else + memset(&hash_entry[1], 0, sizeof(hash_entry[1])); + + if (hash_lookup(test->log, hash_entry) == NULL) + test_failed(test, "Route is missing in hash", dst_p, + src_p); + } + + /* Verify that all added elements are still in the table */ + hash_iterate(test->log, verify_log, test); +} + +static void get_rand_prefix(struct prng *prng, struct prefix_ipv6 *p) +{ + int i; + + memset(p, 0, sizeof(*p)); + + for (i = 0; i < 4; i++) + p->prefix.s6_addr32[i] = prng_rand(prng); + p->prefixlen = prng_rand(prng) % 129; + p->family = AF_INET6; + + apply_mask(p); +} + +static void get_rand_prefix_pair(struct prng *prng, struct prefix_ipv6 *dst_p, + struct prefix_ipv6 *src_p) +{ + get_rand_prefix(prng, dst_p); + if ((prng_rand(prng) % 4) == 0) { + get_rand_prefix(prng, src_p); + if (src_p->prefixlen) + return; + } + + memset(src_p, 0, sizeof(*src_p)); +} + +static void test_state_add_rand_route(struct test_state *test, + struct prng *prng) +{ + struct prefix_ipv6 dst_p, src_p; + + get_rand_prefix_pair(prng, &dst_p, &src_p); + test_state_add_route(test, &dst_p, &src_p); +} + +static void test_state_del_rand_route(struct test_state *test, + struct prng *prng) +{ + struct prefix_ipv6 dst_p, src_p; + + get_rand_prefix_pair(prng, &dst_p, &src_p); + test_state_del_route(test, &dst_p, &src_p); +} + +static void test_state_del_one_route(struct test_state *test, struct prng *prng) +{ + unsigned int which_route; + + if (test->log->count == 0) + return; + + which_route = prng_rand(prng) % test->log->count; + + struct route_node *rn; + const struct prefix *dst_p, *src_p; + struct prefix_ipv6 dst6_p, src6_p; + + for (rn = route_top(test->table); rn; rn = srcdest_route_next(rn)) { + if (!rn->info) + continue; + if (!which_route) { + route_unlock_node(rn); + break; + } + which_route--; + } + + assert(rn); + srcdest_rnode_prefixes(rn, &dst_p, &src_p); + memcpy(&dst6_p, dst_p, sizeof(dst6_p)); + if (src_p) + memcpy(&src6_p, src_p, sizeof(src6_p)); + else + memset(&src6_p, 0, sizeof(src6_p)); + + test_state_del_route(test, &dst6_p, &src6_p); +} + +static void run_prng_test(void) +{ + struct test_state *test = test_state_new(); + struct prng *prng = prng_new(0); + size_t i; + + for (i = 0; i < 1000; i++) { + switch (prng_rand(prng) % 10) { + case 0: + case 1: + case 2: + case 3: + case 4: + test_state_add_rand_route(test, prng); + break; + case 5: + case 6: + case 7: + test_state_del_one_route(test, prng); + break; + case 8: + case 9: + test_state_del_rand_route(test, prng); + break; + } + test_state_verify(test); + } + + prng_free(prng); + test_state_free(test); +} + +int main(int argc, char *argv[]) +{ + run_prng_test(); + printf("PRNG Test successful.\n"); + return 0; +} |