From f2c9cd05c8a9f96e6f4073af13f45960a2b29ab1 Mon Sep 17 00:00:00 2001 From: "Jason A. Donenfeld" Date: Fri, 14 Apr 2017 18:51:15 +0200 Subject: routingtable: rewrite core functions When removing by peer, prev needs to be set to *nptr in order to traverse that part of the trie. The other remove by IP function can simply be removed, as it's not in use. The root freeing function can use pre-order traversal instead of post-order. The pre-order traversal code in general is now a nice iterator macro. The common bits function can use the fast fls instructions and the match function can be rewritten to simply compare common bits. While we're at it, let's add tons of new tests, randomized checking against a dumb implementation, and graphviz output. And in general, it's nice to clean things up. Signed-off-by: Jason A. Donenfeld --- src/selftest/routing-table.h | 133 ------------------------------------------- 1 file changed, 133 deletions(-) delete mode 100644 src/selftest/routing-table.h (limited to 'src/selftest/routing-table.h') diff --git a/src/selftest/routing-table.h b/src/selftest/routing-table.h deleted file mode 100644 index a603401..0000000 --- a/src/selftest/routing-table.h +++ /dev/null @@ -1,133 +0,0 @@ -/* Copyright (C) 2015-2017 Jason A. Donenfeld . All Rights Reserved. */ - -#ifdef DEBUG -static inline struct in_addr *ip4(u8 a, u8 b, u8 c, u8 d) -{ - static struct in_addr ip; - u8 *split = (u8 *)&ip; - split[0] = a; - split[1] = b; - split[2] = c; - split[3] = d; - return &ip; -} -static inline struct in6_addr *ip6(u32 a, u32 b, u32 c, u32 d) -{ - static struct in6_addr ip; - __be32 *split = (__be32 *)&ip; - split[0] = cpu_to_be32(a); - split[1] = cpu_to_be32(b); - split[2] = cpu_to_be32(c); - split[3] = cpu_to_be32(d); - return &ip; -} - -bool routing_table_selftest(void) -{ - struct routing_table t; - struct wireguard_peer *a = NULL, *b = NULL, *c = NULL, *d = NULL, *e = NULL, *f = NULL, *g = NULL, *h = NULL; - size_t i = 0; - bool success = false; - struct in6_addr ip; - __be64 part; - - routing_table_init(&t); -#define init_peer(name) do { name = kzalloc(sizeof(struct wireguard_peer), GFP_KERNEL); if (!name) goto free; kref_init(&name->refcount); } while (0) - init_peer(a); - init_peer(b); - init_peer(c); - init_peer(d); - init_peer(e); - init_peer(f); - init_peer(g); - init_peer(h); -#undef init_peer - -#define insert(version, mem, ipa, ipb, ipc, ipd, cidr) routing_table_insert_v##version(&t, ip##version(ipa, ipb, ipc, ipd), cidr, mem) - insert(4, a, 192, 168, 4, 0, 24); - insert(4, b, 192, 168, 4, 4, 32); - insert(4, c, 192, 168, 0, 0, 16); - insert(4, d, 192, 95, 5, 64, 27); - insert(4, c, 192, 95, 5, 65, 27); /* replaces previous entry, and maskself is required */ - insert(6, d, 0x26075300, 0x60006b00, 0, 0xc05f0543, 128); - insert(6, c, 0x26075300, 0x60006b00, 0, 0, 64); - insert(4, e, 0, 0, 0, 0, 0); - insert(6, e, 0, 0, 0, 0, 0); - insert(6, f, 0, 0, 0, 0, 0); /* replaces previous entry */ - insert(6, g, 0x24046800, 0, 0, 0, 32); - insert(6, h, 0x24046800, 0x40040800, 0xdeadbeef, 0xdeadbeef, 64); /* maskself is required */ - insert(6, a, 0x24046800, 0x40040800, 0xdeadbeef, 0xdeadbeef, 128); - insert(4, g, 64, 15, 112, 0, 20); - insert(4, h, 64, 15, 123, 211, 25); /* maskself is required */ - insert(4, a, 10, 0, 0, 0, 25); - insert(4, b, 10, 0, 0, 128, 25); - insert(4, a, 10, 1, 0, 0, 30); - insert(4, b, 10, 1, 0, 4, 30); - insert(4, c, 10, 1, 0, 8, 29); - insert(4, d, 10, 1, 0, 16, 29); -#undef insert - - success = true; -#define test(version, mem, ipa, ipb, ipc, ipd) do { \ - bool _s = routing_table_lookup_v##version(&t, ip##version(ipa, ipb, ipc, ipd)) == mem; \ - ++i; \ - if (!_s) { \ - pr_info("routing table self-test %zu: FAIL\n", i); \ - success = false; \ - } \ -} while (0) - test(4, a, 192, 168, 4, 20); - test(4, a, 192, 168, 4, 0); - test(4, b, 192, 168, 4, 4); - test(4, c, 192, 168, 200, 182); - test(4, c, 192, 95, 5, 68); - test(4, e, 192, 95, 5, 96); - test(6, d, 0x26075300, 0x60006b00, 0, 0xc05f0543); - test(6, c, 0x26075300, 0x60006b00, 0, 0xc02e01ee); - test(6, f, 0x26075300, 0x60006b01, 0, 0); - test(6, g, 0x24046800, 0x40040806, 0, 0x1006); - test(6, g, 0x24046800, 0x40040806, 0x1234, 0x5678); - test(6, f, 0x240467ff, 0x40040806, 0x1234, 0x5678); - test(6, f, 0x24046801, 0x40040806, 0x1234, 0x5678); - test(6, h, 0x24046800, 0x40040800, 0x1234, 0x5678); - test(6, h, 0x24046800, 0x40040800, 0, 0); - test(6, h, 0x24046800, 0x40040800, 0x10101010, 0x10101010); - test(6, a, 0x24046800, 0x40040800, 0xdeadbeef, 0xdeadbeef); - test(4, g, 64, 15, 116, 26); - test(4, g, 64, 15, 127, 3); - test(4, g, 64, 15, 123, 1); - test(4, h, 64, 15, 123, 128); - test(4, h, 64, 15, 123, 129); - test(4, a, 10, 0, 0, 52); - test(4, b, 10, 0, 0, 220); - test(4, a, 10, 1, 0, 2); - test(4, b, 10, 1, 0, 6); - test(4, c, 10, 1, 0, 10); - test(4, d, 10, 1, 0, 20); -#undef test - - /* These will hit the BUG_ON(len >= 128) in free_node if something goes wrong. */ - for (i = 0; i < 128; ++i) { - part = cpu_to_be64(~(1LLU << (i % 64))); - memset(&ip, 0xff, 16); - memcpy((u8 *)&ip + (i < 64) * 8, &part, 8); - routing_table_insert_v6(&t, &ip, 128, a); - } - - if (success) - pr_info("routing table self-tests: pass\n"); - -free: - routing_table_free(&t); - kfree(a); - kfree(b); - kfree(c); - kfree(d); - kfree(e); - kfree(f); - kfree(g); - kfree(h); - - return success; -} -#endif -- cgit v1.2.3