Annotation of embedaddon/bird2/filter/trie_test.c, revision 1.1
1.1 ! misho 1: /*
! 2: * Filters: Utility Functions Tests
! 3: *
! 4: * (c) 2015 CZ.NIC z.s.p.o.
! 5: *
! 6: * Can be freely distributed and used under the terms of the GNU GPL.
! 7: */
! 8:
! 9: #include "test/birdtest.h"
! 10: #include "test/bt-utils.h"
! 11:
! 12: #include "filter/filter.h"
! 13: #include "filter/data.h"
! 14: #include "conf/conf.h"
! 15:
! 16: #define TESTS_NUM 10
! 17: #define PREFIXES_NUM 10
! 18: #define PREFIX_TESTS_NUM 10000
! 19:
! 20: #define BIG_BUFFER_SIZE 10000
! 21:
! 22: /* Wrapping structure for storing f_prefixes structures in list */
! 23: struct f_prefix_node {
! 24: node n;
! 25: struct f_prefix prefix;
! 26: };
! 27:
! 28: static u32
! 29: xrandom(u32 max)
! 30: {
! 31: return (bt_random() % max);
! 32: }
! 33:
! 34: static int
! 35: is_prefix_included(list *prefixes, struct f_prefix *needle)
! 36: {
! 37: struct f_prefix_node *n;
! 38: WALK_LIST(n, *prefixes)
! 39: {
! 40: ip6_addr cmask = ip6_mkmask(MIN(n->prefix.net.pxlen, needle->net.pxlen));
! 41:
! 42: ip6_addr ip = net6_prefix(&n->prefix.net);
! 43: ip6_addr needle_ip = net6_prefix(&needle->net);
! 44:
! 45: if ((ipa_compare(ipa_and(ip, cmask), ipa_and(needle_ip, cmask)) == 0) &&
! 46: (n->prefix.lo <= needle->net.pxlen) && (needle->net.pxlen <= n->prefix.hi))
! 47: {
! 48: bt_debug("FOUND\t" PRIip6 "/%d %d-%d\n", ARGip6(net6_prefix(&n->prefix.net)), n->prefix.net.pxlen, n->prefix.lo, n->prefix.hi);
! 49: return 1; /* OK */
! 50: }
! 51: }
! 52: return 0; /* FAIL */
! 53: }
! 54:
! 55: static struct f_prefix
! 56: get_random_ip6_prefix(void)
! 57: {
! 58: struct f_prefix p;
! 59: u8 pxlen = xrandom(120)+8;
! 60: ip6_addr ip6 = ip6_build(bt_random(),bt_random(),bt_random(),bt_random());
! 61: net_addr_ip6 net6 = NET_ADDR_IP6(ip6, pxlen);
! 62:
! 63: p.net = *((net_addr*) &net6);
! 64:
! 65: if (bt_random() % 2)
! 66: {
! 67: p.lo = 0;
! 68: p.hi = p.net.pxlen;
! 69: }
! 70: else
! 71: {
! 72: p.lo = p.net.pxlen;
! 73: p.hi = net_max_prefix_length[p.net.type];
! 74: }
! 75:
! 76: return p;
! 77: }
! 78:
! 79: static void
! 80: generate_random_ipv6_prefixes(list *prefixes)
! 81: {
! 82: int i;
! 83: for (i = 0; i < PREFIXES_NUM; i++)
! 84: {
! 85: struct f_prefix f = get_random_ip6_prefix();
! 86:
! 87: struct f_prefix_node *px = calloc(1, sizeof(struct f_prefix_node));
! 88: px->prefix = f;
! 89:
! 90: bt_debug("ADD\t" PRIip6 "/%d %d-%d\n", ARGip6(net6_prefix(&px->prefix.net)), px->prefix.net.pxlen, px->prefix.lo, px->prefix.hi);
! 91: add_tail(prefixes, &px->n);
! 92: }
! 93: }
! 94:
! 95: static int
! 96: t_match_net(void)
! 97: {
! 98: bt_bird_init();
! 99: bt_config_parse(BT_CONFIG_SIMPLE);
! 100:
! 101: uint round;
! 102: for (round = 0; round < TESTS_NUM; round++)
! 103: {
! 104: list prefixes; /* of structs f_extended_prefix */
! 105: init_list(&prefixes);
! 106: struct f_trie *trie = f_new_trie(config->mem, sizeof(struct f_trie_node));
! 107:
! 108: generate_random_ipv6_prefixes(&prefixes);
! 109: struct f_prefix_node *n;
! 110: WALK_LIST(n, prefixes)
! 111: {
! 112: trie_add_prefix(trie, &n->prefix.net, n->prefix.lo, n->prefix.hi);
! 113: }
! 114:
! 115: int i;
! 116: for (i = 0; i < PREFIX_TESTS_NUM; i++)
! 117: {
! 118: struct f_prefix f = get_random_ip6_prefix();
! 119: bt_debug("TEST\t" PRIip6 "/%d\n", ARGip6(net6_prefix(&f.net)), f.net.pxlen);
! 120:
! 121: int should_be = is_prefix_included(&prefixes, &f);
! 122: int is_there = trie_match_net(trie, &f.net);
! 123: bt_assert_msg(should_be == is_there, "Prefix " PRIip6 "/%d %s", ARGip6(net6_prefix(&f.net)), f.net.pxlen, (should_be ? "should be found in trie" : "should not be found in trie"));
! 124: }
! 125:
! 126: struct f_prefix_node *nxt;
! 127: WALK_LIST_DELSAFE(n, nxt, prefixes)
! 128: {
! 129: free(n);
! 130: }
! 131: }
! 132:
! 133: bt_bird_cleanup();
! 134: return 1;
! 135: }
! 136:
! 137: static int
! 138: t_trie_same(void)
! 139: {
! 140: bt_bird_init();
! 141: bt_config_parse(BT_CONFIG_SIMPLE);
! 142:
! 143: int round;
! 144: for (round = 0; round < TESTS_NUM*4; round++)
! 145: {
! 146: struct f_trie * trie1 = f_new_trie(config->mem, sizeof(struct f_trie_node));
! 147: struct f_trie * trie2 = f_new_trie(config->mem, sizeof(struct f_trie_node));
! 148:
! 149: list prefixes; /* a list of f_extended_prefix structures */
! 150: init_list(&prefixes);
! 151: int i;
! 152: for (i = 0; i < 100; i++)
! 153: generate_random_ipv6_prefixes(&prefixes);
! 154:
! 155: struct f_prefix_node *n;
! 156: WALK_LIST(n, prefixes)
! 157: {
! 158: trie_add_prefix(trie1, &n->prefix.net, n->prefix.lo, n->prefix.hi);
! 159: }
! 160: WALK_LIST_BACKWARDS(n, prefixes)
! 161: {
! 162: trie_add_prefix(trie2, &n->prefix.net, n->prefix.lo, n->prefix.hi);
! 163: }
! 164:
! 165: bt_assert(trie_same(trie1, trie2));
! 166:
! 167: struct f_prefix_node *nxt;
! 168: WALK_LIST_DELSAFE(n, nxt, prefixes)
! 169: {
! 170: free(n);
! 171: }
! 172: }
! 173:
! 174: return 1;
! 175: }
! 176:
! 177: int
! 178: main(int argc, char *argv[])
! 179: {
! 180: bt_init(argc, argv);
! 181:
! 182: bt_test_suite(t_match_net, "Testing random prefix matching");
! 183: bt_test_suite(t_trie_same, "A trie filled forward should be same with a trie filled backward.");
! 184:
! 185: return bt_exit_value();
! 186: }
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>
![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to trie_test.c CVS log ![[TXT]](/icons/cvsweb/text.gif){kind=icon}
![[DIR]](/icons/cvsweb/dir.gif){kind=icon}
Up to [ELWIX - Embedded LightWeight unIX -] / embedaddon / bird2 / filter