diff options
author | Jason A. Donenfeld <Jason@zx2c4.com> | 2015-08-20 04:39:16 +0200 |
---|---|---|
committer | Jason A. Donenfeld <Jason@zx2c4.com> | 2015-10-07 03:26:18 +0200 |
commit | caed07571cd9cb8c23b6cc7aa37fefa06f379a3d (patch) | |
tree | 7fbd6f6bd9cb9101115365e259f43644f7fe6fdf | |
download | kernel-routing-table-caed07571cd9cb8c23b6cc7aa37fefa06f379a3d.tar.xz kernel-routing-table-caed07571cd9cb8c23b6cc7aa37fefa06f379a3d.zip |
Very basic linked list implementationHEADlinked-list
-rw-r--r-- | Makefile | 26 | ||||
-rw-r--r-- | main.c | 23 | ||||
-rw-r--r-- | routing-table.c | 781 | ||||
-rw-r--r-- | routing-table.h | 54 |
4 files changed, 884 insertions, 0 deletions
diff --git a/Makefile b/Makefile new file mode 100644 index 0000000..986102e --- /dev/null +++ b/Makefile @@ -0,0 +1,26 @@ +ifneq ($(KERNELRELEASE),) +obj-m := lctrie.o +ccflags-y += -DDEBUG -g -DGIT_REVISION="KBUILD_STR($(shell git --git-dir="$(M)/.git" rev-parse --abbrev-ref HEAD):$(shell git --git-dir="$(M)/.git" rev-parse --short HEAD))" +lctrie-y := main.o routing-table.o +else +KERNELDIR ?= /lib/modules/$(shell uname -r)/build +PWD := $(shell pwd) + +all: + $(MAKE) -C $(KERNELDIR) M=$(PWD) modules +clean: + $(MAKE) -C $(KERNELDIR) M=$(PWD) clean + + +REMOTE_HOST ?= root@172.16.48.128 +SSH_OPTS := -q -o ControlMaster=auto -o ControlPath=.ssh-deployment.sock +RSYNC_OPTS := --include="*.c" --include="*.h" --include="Makefile" --include=".git/***" --exclude="*" -aq + +remote: + ssh $(SSH_OPTS) -Nf $(REMOTE_HOST) + rsync --rsh="ssh $(SSH_OPTS)" $(RSYNC_OPTS) . $(REMOTE_HOST):lctrie-build/ + -ssh $(SSH_OPTS) $(REMOTE_HOST) 'rmmod lctrie; cd lctrie-build && make -j5 all && insmod lctrie.ko' + ssh $(SSH_OPTS) -O exit $(REMOTE_HOST) + +.PHONY: all clean +endif @@ -0,0 +1,23 @@ +/* Copyright 2015 Jason A. Donenfeld <Jason@zx2c4.com>. All Rights Reserved. */ + +#include "routing-table.h" +#include <linux/init.h> +#include <linux/module.h> + +static int __init mod_init(void) +{ +#ifdef DEBUG + routing_table_selftest(); +#endif + return 0; +} + +static void __exit mod_exit(void) +{ +} + +module_init(mod_init); +module_exit(mod_exit); +MODULE_LICENSE("GPL v2"); +MODULE_DESCRIPTION("LC-Trie"); +MODULE_AUTHOR("Jason A. Donenfeld <Jason@zx2c4.com>"); diff --git a/routing-table.c b/routing-table.c new file mode 100644 index 0000000..379aa84 --- /dev/null +++ b/routing-table.c @@ -0,0 +1,781 @@ +/* Copyright 2015 Jason A. Donenfeld <Jason@zx2c4.com>. All Rights Reserved. */ + +#include "routing-table.h" + +/****************************************************************** + * + * TODO TODO TODO TODO TODO TODO TODO TODO TODO TODO TODO TODO TODO + * + * This needs to be rewritten to use an LC-Trie instead of this + * silly stub that follows below. + * + * TODO TODO TODO TODO TODO TODO TODO TODO TODO TODO TODO TODO TODO + * + ******************************************************************/ + +struct routing_table_node_worlds_worst_implementation { + struct hlist_node table; + union nf_inet_addr ip; + union nf_inet_addr mask; + uint8_t ip_version; + void *value; + struct rcu_head rcu; +}; + +void routing_table_init(struct routing_table *table) +{ + INIT_HLIST_HEAD(&table->head); +} + +void routing_table_free(struct routing_table *table) +{ + struct hlist_node *_h; + struct routing_table_node_worlds_worst_implementation *node; + hlist_for_each_entry_safe(node, _h, &table->head, table) { + hlist_del_rcu(&node->table); + kfree_rcu(node, rcu); + }; +} + +static inline union nf_inet_addr cidr_to_mask(uint8_t cidr) +{ + union nf_inet_addr mask; + memset(&mask, 0x00, 128 / 8); + memset(&mask, 0xff, cidr / 8); + if (cidr % 32) + mask.all[cidr / 32] = htonl((0xFFFFFFFFUL << (32 - (cidr % 32))) & 0xFFFFFFFFUL); + return mask; +} + +static inline uint8_t mask_to_cidr(union nf_inet_addr subnet) +{ + return hweight32(subnet.all[0]) + + hweight32(subnet.all[1]) + + hweight32(subnet.all[2]) + + hweight32(subnet.all[3]); +} + +static inline void mask_self(struct routing_table_node_worlds_worst_implementation *node) +{ + if (node->ip_version == 4) + node->ip.ip &= node->mask.ip; + else if (node->ip_version == 6) { + node->ip.ip6[0] &= node->mask.ip6[0]; + node->ip.ip6[1] &= node->mask.ip6[1]; + node->ip.ip6[2] &= node->mask.ip6[2]; + node->ip.ip6[3] &= node->mask.ip6[3]; + } +} + +static inline bool match_v4(const struct routing_table_node_worlds_worst_implementation *node, struct in_addr *ip) +{ + return (ip->s_addr & node->mask.ip) == node->ip.ip; +} + +static inline bool match_v6(const struct routing_table_node_worlds_worst_implementation *node, struct in6_addr *ip) +{ + return (ip->in6_u.u6_addr32[0] & node->mask.ip6[0]) == node->ip.ip6[0] && + (ip->in6_u.u6_addr32[1] & node->mask.ip6[1]) == node->ip.ip6[1] && + (ip->in6_u.u6_addr32[2] & node->mask.ip6[2]) == node->ip.ip6[2] && + (ip->in6_u.u6_addr32[3] & node->mask.ip6[3]) == node->ip.ip6[3]; +} + +static void insert_ordered(struct routing_table *table, struct routing_table_node_worlds_worst_implementation *node) +{ + struct routing_table_node_worlds_worst_implementation *other = NULL, *where = NULL; + uint8_t my_cidr = mask_to_cidr(node->mask); + rcu_read_lock(); + hlist_for_each_entry_rcu(other, &table->head, table) { + if (!memcmp(&other->mask, &node->mask, sizeof(union nf_inet_addr)) && + !memcmp(&other->ip, &node->ip, sizeof(union nf_inet_addr)) && + other->ip_version == node->ip_version) { + other->value = node->value; + kfree(node); + rcu_read_unlock(); + return; + } + where = other; + if (mask_to_cidr(other->mask) <= my_cidr) + break; + } + if (!other && !where) + hlist_add_head_rcu(&node->table, &table->head); + else if (!other) + hlist_add_behind_rcu(&node->table, &where->table); + else + hlist_add_before_rcu(&node->table, &where->table); + rcu_read_unlock(); +} + +int routing_table_insert_v4(struct routing_table *table, struct in_addr ip, uint8_t cidr, void *value) +{ + struct routing_table_node_worlds_worst_implementation *node = kzalloc(sizeof(struct routing_table_node_worlds_worst_implementation), GFP_KERNEL); + if (!node) + return -ENOMEM; + node->ip.in = ip; + node->mask = cidr_to_mask(cidr); + node->ip_version = 4; + node->value = value; + mask_self(node); + insert_ordered(table, node); + return 0; +} + +int routing_table_insert_v6(struct routing_table *table, struct in6_addr ip, uint8_t cidr, void *value) +{ + struct routing_table_node_worlds_worst_implementation *node = kzalloc(sizeof(struct routing_table_node_worlds_worst_implementation), GFP_KERNEL); + if (!node) + return -ENOMEM; + node->ip.in6 = ip; + node->mask = cidr_to_mask(cidr); + node->ip_version = 6; + node->value = value; + mask_self(node); + insert_ordered(table, node); + return 0; +} + +void *routing_table_lookup_v4(struct routing_table *table, struct in_addr ip) +{ + struct routing_table_node_worlds_worst_implementation *node; + void *ret = NULL; + rcu_read_lock(); + hlist_for_each_entry_rcu(node, &table->head, table) { + if (node->ip_version != 4) + continue; + if (match_v4(node, &ip)) { + ret = node->value; + break; + } + }; + rcu_read_unlock(); + return ret; +} + +void *routing_table_lookup_v6(struct routing_table *table, struct in6_addr ip) +{ + struct routing_table_node_worlds_worst_implementation *node; + void *ret = NULL; + rcu_read_lock(); + hlist_for_each_entry_rcu(node, &table->head, table) { + if (node->ip_version != 6) + continue; + if (match_v6(node, &ip)) { + ret = node->value; + break; + } + }; + rcu_read_unlock(); + return ret; +} + +int routing_table_remove_v4(struct routing_table *table, struct in_addr ip, uint8_t cidr) +{ + bool ret = false; + struct hlist_node *_h; + struct routing_table_node_worlds_worst_implementation *node; + hlist_for_each_entry_safe(node, _h, &table->head, table) { + if (node->ip_version != 4) + continue; + if (memcmp(&node->ip.in, &ip, sizeof(struct in_addr))) + continue; + if (mask_to_cidr(node->mask) != cidr) + continue; + hlist_del_rcu(&node->table); + kfree_rcu(node, rcu); + ret = true; + } + return ret ? 0 : -EINVAL; +} + +int routing_table_remove_v6(struct routing_table *table, struct in6_addr ip, uint8_t cidr) +{ + bool ret = false; + struct hlist_node *_h; + struct routing_table_node_worlds_worst_implementation *node; + hlist_for_each_entry_safe(node, _h, &table->head, table) { + if (node->ip_version != 6) + continue; + if (memcmp(&node->ip.in6, &ip, sizeof(struct in6_addr))) + continue; + if (mask_to_cidr(node->mask) != cidr) + continue; + hlist_del_rcu(&node->table); + kfree_rcu(node, rcu); + ret = true; + } + return ret ? 0 : -EINVAL; +} + +int routing_table_remove_by_value(struct routing_table *table, void *value) +{ + bool ret = false; + struct hlist_node *_h; + struct routing_table_node_worlds_worst_implementation *node; + hlist_for_each_entry_safe(node, _h, &table->head, table) { + if (node->value != value) + continue; + hlist_del_rcu(&node->table); + kfree_rcu(node, rcu); + ret = true; + } + return ret ? 0 : -EINVAL; +} + +int routing_table_walk_ips(struct routing_table *table, void *ctx, int (*func)(void *ctx, void *value, union nf_inet_addr ip, uint8_t cidr, uint8_t ip_version)) +{ + struct routing_table_node_worlds_worst_implementation *node; + int ret = 0; + rcu_read_lock(); + hlist_for_each_entry_rcu(node, &table->head, table) { + ret = func(ctx, node->value, node->ip, mask_to_cidr(node->mask), node->ip_version); + if (ret < 0) { + rcu_read_unlock(); + return ret; + } + }; + rcu_read_unlock(); + return ret; +} + +int routing_table_walk_ips_by_value(struct routing_table *table, void *ctx, void *value, int (*func)(void *ctx, union nf_inet_addr ip, uint8_t cidr, uint8_t ip_version)) +{ + struct routing_table_node_worlds_worst_implementation *node; + int ret = 0; + rcu_read_lock(); + hlist_for_each_entry_rcu(node, &table->head, table) { + if (value != node->value) + continue; + ret = func(ctx, node->ip, mask_to_cidr(node->mask), node->ip_version); + if (ret < 0) { + rcu_read_unlock(); + return ret; + } + }; + rcu_read_unlock(); + return ret; +} + +#ifdef DEBUG +static inline struct in_addr ip4(uint8_t a, uint8_t b, uint8_t c, uint8_t d) +{ + struct in_addr ip; + uint8_t *split = (uint8_t *)&ip; + split[0] = a; + split[1] = b; + split[2] = c; + split[3] = d; + return ip; +} +static inline struct in6_addr ip6(uint32_t a, uint32_t b, uint32_t c, uint32_t d) +{ + struct in6_addr ip; + uint32_t *split = (uint32_t *)&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; +} + +void routing_table_selftest(void) +{ + struct routing_table t; + char a, b, c, d, e, f, g, h, k; + size_t i = 0; + unsigned long time; + bool success = true; + + routing_table_init(&t); + +#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 */ + + /* randomly generated: */ + insert(4, k, 92, 84, 251, 175, 28); + insert(4, k, 188, 185, 185, 196, 30); + insert(4, k, 166, 226, 231, 24, 28); + insert(4, k, 21, 129, 64, 23, 29); + insert(4, k, 150, 70, 43, 132, 31); + insert(4, k, 222, 164, 45, 236, 28); + insert(4, k, 14, 4, 88, 251, 28); + insert(4, k, 10, 201, 110, 220, 29); + insert(4, k, 83, 168, 252, 120, 31); + insert(4, k, 118, 15, 15, 101, 30); + insert(4, k, 106, 252, 72, 154, 29); + insert(4, k, 255, 72, 142, 43, 31); + insert(4, k, 31, 242, 201, 203, 29); + insert(4, k, 91, 50, 87, 58, 30); + insert(4, k, 96, 12, 130, 197, 28); + insert(4, k, 165, 104, 85, 101, 28); + insert(4, k, 74, 248, 71, 75, 32); + insert(4, k, 30, 8, 193, 19, 28); + insert(4, k, 51, 90, 62, 80, 29); + insert(4, k, 210, 104, 114, 152, 30); + insert(4, k, 168, 200, 65, 84, 31); + insert(4, k, 191, 153, 149, 203, 30); + insert(4, k, 237, 14, 161, 254, 28); + insert(4, k, 84, 12, 220, 188, 32); + insert(4, k, 173, 117, 138, 158, 29); + insert(4, k, 182, 0, 135, 102, 31); + insert(4, k, 107, 102, 133, 80, 32); + insert(4, k, 235, 199, 227, 206, 30); + insert(4, k, 244, 94, 210, 87, 28); + insert(4, k, 192, 122, 64, 232, 31); + insert(4, k, 82, 37, 119, 176, 28); + insert(4, k, 58, 242, 174, 250, 31); + insert(4, k, 80, 83, 229, 81, 32); + insert(4, k, 131, 153, 207, 101, 32); + insert(4, k, 47, 86, 118, 88, 28); + insert(4, k, 78, 229, 14, 140, 32); + insert(4, k, 156, 183, 67, 122, 31); + insert(4, k, 140, 136, 149, 3, 28); + insert(4, k, 195, 42, 162, 50, 30); + insert(4, k, 18, 72, 213, 254, 30); + insert(4, k, 249, 102, 170, 129, 28); + insert(4, k, 57, 45, 108, 203, 28); + insert(4, k, 30, 147, 1, 145, 29); + insert(4, k, 146, 101, 163, 255, 29); + insert(4, k, 145, 54, 87, 214, 29); + insert(4, k, 88, 238, 150, 107, 32); + insert(4, k, 122, 157, 141, 51, 32); + insert(4, k, 229, 29, 70, 183, 28); + insert(4, k, 11, 166, 190, 227, 31); + insert(4, k, 102, 137, 161, 170, 30); + insert(4, k, 215, 231, 110, 148, 30); + insert(4, k, 18, 121, 146, 32, 28); + insert(4, k, 187, 224, 134, 21, 28); + insert(4, k, 178, 156, 82, 122, 29); + insert(4, k, 111, 43, 60, 249, 31); + insert(4, k, 222, 132, 57, 15, 31); + insert(4, k, 37, 17, 151, 158, 29); + insert(4, k, 153, 16, 18, 66, 30); + insert(4, k, 39, 60, 239, 17, 28); + insert(4, k, 93, 147, 77, 159, 28); + insert(4, k, 109, 70, 110, 27, 30); + insert(4, k, 18, 66, 202, 94, 32); + insert(4, k, 51, 212, 44, 51, 30); + insert(4, k, 131, 100, 4, 210, 32); + insert(4, k, 134, 255, 34, 217, 29); + insert(4, k, 31, 51, 177, 191, 32); + insert(4, k, 110, 110, 34, 7, 32); + insert(4, k, 120, 66, 134, 49, 29); + insert(4, k, 75, 222, 140, 132, 29); + insert(4, k, 65, 131, 205, 238, 31); + insert(4, k, 222, 213, 161, 30, 32); + insert(4, k, 138, 196, 25, 47, 30); + insert(4, k, 113, 54, 209, 63, 28); + insert(4, k, 196, 4, 5, 195, 30); + insert(4, k, 214, 137, 237, 86, 31); + insert(4, k, 231, 156, 69, 100, 28); + insert(4, k, 241, 230, 136, 156, 31); + insert(4, k, 2, 130, 101, 228, 28); + insert(4, k, 104, 49, 149, 93, 29); + insert(4, k, 58, 27, 151, 199, 30); + insert(4, k, 91, 216, 14, 17, 30); + insert(4, k, 92, 25, 134, 182, 29); + insert(4, k, 176, 147, 143, 80, 32); + insert(4, k, 85, 144, 164, 235, 31); + insert(4, k, 177, 128, 225, 104, 30); + insert(4, k, 62, 51, 103, 125, 29); + insert(4, k, 112, 97, 181, 80, 29); + insert(4, k, 48, 154, 31, 194, 31); + insert(4, k, 194, 107, 184, 132, 29); + insert(4, k, 37, 90, 176, 205, 28); + insert(4, k, 221, 233, 177, 140, 31); + insert(4, k, 119, 239, 79, 115, 31); + insert(4, k, 210, 104, 178, 204, 32); + insert(4, k, 167, 17, 109, 229, 30); + insert(4, k, 225, 238, 230, 218, 30); + insert(4, k, 165, 141, 136, 175, 28); + insert(4, k, 112, 55, 218, 252, 30); + insert(4, k, 6, 141, 6, 14, 32); + insert(4, k, 112, 128, 15, 136, 32); + insert(4, k, 51, 88, 153, 250, 29); + insert(4, k, 48, 124, 39, 165, 31); + insert(4, k, 68, 41, 180, 190, 32); + insert(4, k, 60, 222, 39, 153, 28); + insert(4, k, 53, 232, 66, 47, 29); + insert(4, k, 110, 244, 219, 85, 28); + insert(4, k, 141, 92, 201, 56, 28); + insert(4, k, 138, 228, 156, 142, 31); + insert(4, k, 197, 33, 207, 152, 28); + insert(4, k, 253, 48, 48, 65, 30); + insert(4, k, 41, 201, 106, 41, 30); + insert(4, k, 18, 150, 16, 203, 28); + insert(4, k, 91, 239, 120, 118, 32); + insert(4, k, 138, 180, 189, 168, 32); + insert(4, k, 42, 184, 121, 65, 31); + insert(4, k, 217, 224, 85, 36, 29); + insert(4, k, 157, 10, 172, 151, 28); + insert(4, k, 167, 223, 187, 219, 30); + insert(4, k, 254, 127, 238, 52, 30); + insert(4, k, 130, 123, 79, 194, 30); + insert(4, k, 211, 190, 249, 200, 28); + insert(4, k, 255, 3, 11, 53, 30); + insert(4, k, 147, 168, 190, 203, 30); + insert(4, k, 234, 78, 68, 233, 30); + insert(4, k, 217, 105, 173, 164, 28); + insert(4, k, 131, 244, 9, 124, 28); + insert(4, k, 244, 157, 206, 252, 28); + insert(4, k, 201, 59, 239, 115, 31); + insert(4, k, 193, 250, 76, 49, 28); + insert(4, k, 78, 75, 61, 231, 29); + insert(4, k, 235, 67, 93, 207, 28); + insert(4, k, 162, 169, 124, 52, 29); + insert(4, k, 205, 86, 147, 132, 30); + insert(4, k, 215, 14, 14, 80, 32); + insert(4, k, 237, 92, 133, 108, 29); + insert(4, k, 229, 146, 43, 177, 29); + insert(4, k, 230, 70, 199, 21, 31); + insert(4, k, 162, 121, 90, 186, 29); + insert(4, k, 182, 65, 97, 57, 30); + insert(4, k, 160, 253, 18, 190, 29); + insert(4, k, 19, 229, 15, 17, 30); + insert(4, k, 163, 186, 147, 54, 32); + insert(4, k, 97, 180, 150, 41, 31); + insert(4, k, 206, 163, 92, 198, 32); + insert(4, k, 118, 155, 47, 221, 32); + insert(4, k, 88, 5, 157, 40, 31); + insert(4, k, 9, 122, 216, 122, 31); + insert(4, k, 27, 253, 182, 0, 31); + insert(4, k, 93, 240, 60, 63, 31); + insert(4, k, 50, 28, 125, 255, 31); + insert(4, k, 240, 0, 82, 186, 30); + insert(4, k, 248, 161, 33, 185, 31); + insert(4, k, 75, 56, 131, 41, 30); + insert(4, k, 183, 241, 240, 175, 31); + insert(4, k, 126, 236, 65, 239, 28); + insert(4, k, 240, 128, 163, 27, 32); + insert(4, k, 101, 29, 78, 63, 28); + insert(4, k, 155, 99, 48, 1, 31); + insert(4, k, 98, 161, 65, 34, 29); + insert(4, k, 54, 140, 249, 238, 30); + insert(4, k, 125, 237, 80, 193, 30); + insert(4, k, 172, 21, 65, 243, 30); + insert(4, k, 186, 0, 199, 172, 28); + insert(4, k, 193, 42, 182, 40, 30); + insert(4, k, 113, 245, 73, 198, 28); + insert(4, k, 8, 81, 47, 170, 32); + insert(4, k, 104, 92, 111, 42, 32); + insert(4, k, 107, 46, 228, 66, 32); + insert(4, k, 215, 48, 131, 10, 28); + insert(4, k, 216, 51, 220, 219, 31); + insert(4, k, 133, 133, 237, 145, 31); + insert(4, k, 188, 189, 26, 156, 28); + insert(4, k, 187, 96, 142, 2, 30); + insert(4, k, 160, 140, 246, 102, 30); + insert(4, k, 14, 172, 167, 141, 30); + insert(4, k, 19, 15, 235, 240, 30); + insert(4, k, 37, 252, 123, 147, 32); + insert(4, k, 137, 120, 78, 38, 29); + insert(4, k, 107, 234, 184, 133, 28); + insert(4, k, 177, 189, 200, 77, 31); + insert(4, k, 151, 185, 227, 137, 30); + insert(4, k, 252, 74, 35, 64, 30); + insert(4, k, 1, 28, 226, 1, 31); + insert(4, k, 0, 199, 229, 35, 28); + insert(4, k, 66, 247, 162, 178, 29); + insert(4, k, 17, 215, 108, 140, 32); + insert(4, k, 131, 68, 69, 111, 28); + insert(4, k, 51, 214, 104, 19, 31); + insert(4, k, 166, 152, 71, 214, 29); + insert(4, k, 52, 88, 192, 1, 32); + insert(4, k, 219, 234, 115, 146, 30); + insert(4, k, 133, 7, 196, 29, 31); + insert(4, k, 142, 62, 153, 232, 30); + insert(4, k, 79, 129, 67, 160, 29); + insert(4, k, 190, 105, 101, 110, 31); + insert(4, k, 105, 169, 222, 148, 29); + insert(4, k, 19, 28, 45, 59, 28); + insert(4, k, 185, 128, 25, 236, 29); + insert(4, k, 78, 57, 105, 214, 29); + insert(4, k, 253, 165, 46, 100, 30); + insert(4, k, 233, 43, 96, 95, 31); + insert(6, k, 0x05c9998b, 0x0013423f, 0xd6cadac5, 0x01f8cfde, 116); + insert(6, k, 0x8d76562f, 0xaad97417, 0x99ce0339, 0xa358a058, 120); + insert(6, k, 0xcf4c59a9, 0x1561f798, 0xf0fcf5ff, 0xc9c16f53, 123); + insert(6, k, 0xbfe1be28, 0x9caa5f5b, 0xa1ed7b05, 0x1927add1, 122); + insert(6, k, 0x65919dfb, 0x92b0ba2e, 0x0ef02c9a, 0x3ce3b656, 111); + insert(6, k, 0xb62a9f75, 0xee3f10ed, 0xf13610b2, 0xc29a1123, 118); + insert(6, k, 0x43f6b945, 0x75ce383a, 0xae2aef8f, 0x31fd9c5a, 113); + insert(6, k, 0xb2a2ea97, 0x021b9b37, 0xa89acb29, 0x19699670, 123); + insert(6, k, 0xc7215a25, 0xd9eb98cc, 0x0eb82db1, 0x9a073729, 128); + insert(6, k, 0x3424a635, 0x3d7c86b8, 0x31427e68, 0x186cb2ad, 127); + insert(6, k, 0x9e46de6c, 0x7a79aa8e, 0xbfaea561, 0xf16207c2, 120); + insert(6, k, 0x79c2a8e5, 0xfec77d3e, 0x5dd4d368, 0x6ede9ac4, 127); + insert(6, k, 0xc1feb926, 0xc59aaf2f, 0x9e873376, 0xbc4bad82, 124); + insert(6, k, 0x8fd16d56, 0x64bf5232, 0xb99bc6d4, 0xcc2eb21f, 111); + insert(6, k, 0x7c36d46f, 0xe2d51998, 0xd49b004f, 0xc1260931, 113); + insert(6, k, 0xfe88d22e, 0x89ab6230, 0x4f3b9a0e, 0x367e77b3, 111); + insert(6, k, 0xe15f2c01, 0x16ed3d86, 0xe7ca9212, 0x1a7fd5d9, 111); + insert(6, k, 0xbee6d1c2, 0x4af62c15, 0xc8a59f3a, 0x881283fc, 123); + insert(6, k, 0xcc8f8f05, 0xd2ba9c29, 0x33611bab, 0xc18d8edc, 115); + insert(6, k, 0x8c80dfe1, 0xa10e3f85, 0xfe361587, 0xb9dae2ce, 118); + insert(6, k, 0xf4011a49, 0x0ae218d6, 0xf9a5b610, 0xe0f418ea, 116); + insert(6, k, 0x445294ff, 0x92dbbda0, 0x7597f6a7, 0x2d80cc16, 120); + insert(6, k, 0x13b21b10, 0x037eceee, 0x3bc61739, 0x5ee02027, 125); + insert(6, k, 0x72a1b2a0, 0x4c7193e5, 0x2bd6f554, 0xc9180ef5, 112); + insert(6, k, 0x156b9326, 0x90e825fe, 0x8c56d614, 0xbad41efb, 120); + insert(6, k, 0x55a63c08, 0x11b67606, 0x3ae27951, 0xf1a2ec15, 126); + insert(6, k, 0xe82fd42d, 0x0c8a8510, 0x14b3357e, 0x5ebd0a5f, 122); + insert(6, k, 0x3d53a10f, 0xa6fd6114, 0xb50323c5, 0x1c5d0d0f, 113); + insert(6, k, 0xfd644dd2, 0xa6d670fc, 0x877af12e, 0x9b14ee30, 120); + insert(6, k, 0x030a1394, 0x3cfe770c, 0x67739afc, 0x26d7e3c0, 120); + insert(6, k, 0x45f2e9cf, 0x9fa087bc, 0xb4d13230, 0x13dcbdc5, 122); + insert(6, k, 0x466aefdf, 0x59cbcd94, 0x1da25ff6, 0x57034cfb, 115); + insert(6, k, 0x63f77d9e, 0xeddf70b4, 0x03e91c1a, 0x17cdbd4f, 119); + insert(6, k, 0x00de709f, 0x5fc6d4be, 0xa9872759, 0x9e210de6, 112); + insert(6, k, 0xdc171302, 0xc3b3cfcf, 0xb5eb6e44, 0xabd5e5fa, 111); + insert(6, k, 0x8e0ce113, 0x8603aa89, 0x945e811f, 0x8b228e1d, 112); + insert(6, k, 0x50a6d50d, 0x1b5ed534, 0xddf65198, 0xc1caf9bb, 112); + insert(6, k, 0x52de15f9, 0xc7c7e018, 0xf7789415, 0x67773d3d, 125); + insert(6, k, 0x233ee632, 0x54e1f477, 0xf3b4957f, 0x9a513ca5, 120); + insert(6, k, 0x9a457217, 0xd57aaa0a, 0x3f38e346, 0xd41f6827, 119); + insert(6, k, 0x65299889, 0x846e4301, 0xd12c631e, 0x3c794a25, 127); + insert(6, k, 0x70282fec, 0xd442a867, 0x8089d807, 0x1e907d82, 113); + insert(6, k, 0x5aab8ddd, 0x56f23f87, 0xab3df3f7, 0xbacfe1c2, 128); + insert(6, k, 0x619738ea, 0x940e97a8, 0x1b272baf, 0x6c59b99d, 120); + insert(6, k, 0xf45a2304, 0x4d36eb86, 0x66c81ff7, 0xb6df38c9, 121); + insert(6, k, 0xfab1d6d9, 0xeab3b6d4, 0x7f251f9f, 0xa5040317, 114); + insert(6, k, 0x7a14e3ac, 0xdf890365, 0xf58ca9d5, 0xb5eba44f, 118); + insert(6, k, 0xab901068, 0xaff57f66, 0x816079e3, 0x8cc50956, 122); + insert(6, k, 0xd01aaf0d, 0x51cb08a4, 0x672f224f, 0xe8eabd60, 115); + insert(6, k, 0xa56b053e, 0x07a43471, 0x508a4f33, 0x4be9780d, 118); + insert(6, k, 0x061a4f2e, 0x93e45694, 0x0614e3e5, 0x46314f61, 113); + insert(6, k, 0x6e8c73f7, 0x4288143e, 0x34ba579d, 0x59d43a0f, 120); + insert(6, k, 0x187039b2, 0xe030665f, 0x65a98371, 0x90f75319, 128); + insert(6, k, 0x6b4a0d40, 0x8e7a7445, 0x90e4e5b8, 0xabdb7d26, 112); + insert(6, k, 0x08087dd3, 0x7331a475, 0xf4f81016, 0x5200711e, 114); + insert(6, k, 0x2875eab8, 0x44acb26f, 0x7045a526, 0xe05413fd, 113); + insert(6, k, 0x206d11e8, 0xba5bd77a, 0xf6bfda74, 0xa583961f, 124); + insert(6, k, 0x4cec76f8, 0xc483036a, 0x6dd0c775, 0xb5fb4d94, 114); + insert(6, k, 0xe31358db, 0xebaa4c4a, 0xde056fcb, 0x21a665b2, 124); + insert(6, k, 0xcef9d156, 0xf0e36d8e, 0x30124fe3, 0x8f9e5b41, 119); + insert(6, k, 0x917212dc, 0xca21dc68, 0xd88c1615, 0x9291fa2d, 115); + insert(6, k, 0xf1cb392f, 0x11a30298, 0x9dd2ecd6, 0x1355b892, 122); + insert(6, k, 0xfddd67cb, 0x9fe81da7, 0xee70ef82, 0x0a0337b2, 127); + insert(6, k, 0x655f2724, 0xf45cfd49, 0x44c2c476, 0x8ee7ac24, 125); + insert(6, k, 0x2abf8787, 0x2fdf49c4, 0xf3d76a11, 0x5b3892ca, 120); + insert(6, k, 0x64e0ecb0, 0x884e30d4, 0xdcfd8590, 0x74a0b30a, 116); + insert(6, k, 0xddc375cf, 0x18b5070a, 0xfc151d4d, 0x5da64952, 127); + insert(6, k, 0xa22fe359, 0x60a5a194, 0x7d605785, 0x204b3727, 111); + insert(6, k, 0xf27223c7, 0x95cca806, 0x939da2cb, 0x9b881853, 117); + insert(6, k, 0xe58ea430, 0x972de132, 0xedc5a5fa, 0x178ecdf3, 128); + insert(6, k, 0x757c3771, 0x3806ee19, 0x923c8796, 0x699406bb, 125); + insert(6, k, 0xfff6bf6c, 0x0f712146, 0xe590d48b, 0x78a03c80, 113); + insert(6, k, 0x7a44a215, 0xb1ae0d4b, 0xe01481d5, 0xdc24b8a7, 128); + insert(6, k, 0x38846067, 0x446834f8, 0xdb42e4bf, 0xabda128f, 126); + insert(6, k, 0x5a6f9303, 0x7ccfd126, 0x75dd8e78, 0x586cbee7, 121); + insert(6, k, 0xa6db386a, 0x4e6a7ab8, 0x38fd003d, 0xf3a0a2de, 115); + insert(6, k, 0x7e2a9c42, 0xda576498, 0x7d79d93a, 0x2471022d, 127); + insert(6, k, 0xc75bb80a, 0xabe95a63, 0x8bbb31ab, 0xefcaaef7, 116); + insert(6, k, 0xeebfa6dc, 0x344661cf, 0x54ee6785, 0x18d045ac, 127); + insert(6, k, 0x115e7b0c, 0xd61aba20, 0xb9363cce, 0x5e90d42e, 124); + insert(6, k, 0xeffc993f, 0x3ccb15e0, 0xa50017f2, 0x8e05afe1, 118); + insert(6, k, 0x73496382, 0xbc3c9fdd, 0x8bfe5090, 0x2ad38149, 116); + insert(6, k, 0xee753864, 0xb0b403ae, 0xe5bb8d89, 0x29ea463c, 119); + insert(6, k, 0xabcf5582, 0xab589d06, 0xce619333, 0xec4bb5aa, 120); + insert(6, k, 0x70e006e3, 0x4ddb177d, 0x1fd07ff8, 0x1f3db2cd, 119); + insert(6, k, 0xe7fc85cd, 0xc1239d49, 0x416eeb20, 0x8c0485bc, 128); + insert(6, k, 0x707d1a6b, 0xec8f6b43, 0xd6c5e12a, 0xaeee53cd, 118); + insert(6, k, 0xf438300f, 0x05b35955, 0x8c2c15ab, 0x256b6cac, 117); + insert(6, k, 0x165df1fe, 0x5fe5ad53, 0x0216d3fe, 0x0aa77cc1, 120); + insert(6, k, 0x9edc2daf, 0x04731d26, 0xd4d595b3, 0x747dc309, 127); + insert(6, k, 0xec999e19, 0xeb31366b, 0x22d495ca, 0xb7555732, 120); + insert(6, k, 0x77b9f8cc, 0x7525d0ea, 0x1ed8f6e8, 0x75b088e4, 125); + insert(6, k, 0x5508f7ea, 0xaf9ea770, 0x7f5fc6df, 0x0bb9ab4c, 125); + insert(6, k, 0x7a4c8200, 0xe8420bb7, 0x98b2de08, 0xba6ef0bc, 119); + insert(6, k, 0xf2166ba2, 0x56f547aa, 0xa20ea16b, 0xbb46b8a7, 117); + insert(6, k, 0x6aa6a4e3, 0xe0e68ede, 0x590b9c55, 0x405b09cd, 111); + insert(6, k, 0x871e1634, 0xbcb2f0c4, 0x63e86629, 0x4f586a5b, 122); + insert(6, k, 0x6102fc2f, 0xf06f2be2, 0xeffed468, 0x4af003d0, 124); + insert(6, k, 0x7e4ec43d, 0x2be9ef91, 0x3a8e5222, 0x86959997, 125); + insert(6, k, 0xa8aca3ca, 0x9ffcde0c, 0x2ff0e72f, 0x314c5739, 121); + insert(6, k, 0xd983d2db, 0x1f8c1ce3, 0xd1d922a7, 0x8ec1eabf, 119); + insert(6, k, 0xf611cf0f, 0xca092bd2, 0x073f11bf, 0x0b8e0f4c, 125); + insert(6, k, 0xa064bb0b, 0x363cbcd9, 0xd6f6d83c, 0x7d41f173, 127); + insert(6, k, 0x21ed4163, 0x7f9778db, 0x9d3837ca, 0x9a616c50, 128); + insert(6, k, 0x269a4768, 0xcef4f89a, 0xa9550ab7, 0xaa39c160, 124); + insert(6, k, 0xf4679a96, 0xe7c93513, 0xf3706ab1, 0x34cd0d04, 124); + insert(6, k, 0x2811f479, 0xd6bd71e4, 0x02c3d41e, 0xe383582b, 113); + insert(6, k, 0xf644441c, 0x206516bb, 0x4590d3d8, 0xc5fa3d3e, 127); + insert(6, k, 0x396bc648, 0x2d840ff2, 0x98c51013, 0x54d718bc, 116); + insert(6, k, 0xa40798df, 0xd515f693, 0x303b16a7, 0x63448107, 125); + insert(6, k, 0xcd7bbbb1, 0xd7894954, 0x29f2dc59, 0xccb25239, 127); + insert(6, k, 0x7aa0a902, 0x2168e879, 0xa76e9d98, 0x744888ad, 124); + insert(6, k, 0xe3f40b6a, 0xa872c267, 0x0ff326fc, 0x315f8ee7, 123); + insert(6, k, 0xda9ecbce, 0x02fae1ff, 0x4801694e, 0x16405978, 114); + insert(6, k, 0xd73689ac, 0x50536836, 0x7b8d2a6a, 0x66f1092b, 114); + insert(6, k, 0x7bcc20dc, 0x1581e6f0, 0x64d6d160, 0x45af901b, 120); + insert(6, k, 0x37b1b8a1, 0x115004ed, 0xa3ab81c8, 0xff7450ac, 122); + insert(6, k, 0xd2546a23, 0x3d2bdb81, 0x174583e3, 0xd157ac86, 120); + insert(6, k, 0xf489800d, 0xf7fdade6, 0x2dddca13, 0x950262f1, 128); + insert(6, k, 0x6a6165bd, 0x7bd59e2b, 0x1127a0de, 0x88802068, 127); + insert(6, k, 0x6d24b6f5, 0xfb2d6867, 0x18790f7e, 0xf222d4d9, 121); + insert(6, k, 0x05ae02e3, 0xe27f329c, 0x05f30e43, 0x5e272789, 121); + insert(6, k, 0xef35a640, 0x9c9c9bfd, 0xc00a1c41, 0xb187ae0a, 127); + insert(6, k, 0xed3d0441, 0xb8cc1bd5, 0x907ef4af, 0xb4c4eadf, 128); + insert(6, k, 0x6280974e, 0x77a0481b, 0x5b8f27b5, 0xb4dc546b, 127); + insert(6, k, 0xd91873d2, 0x2c5cacd7, 0xd69f928f, 0x72277b13, 126); + insert(6, k, 0x8bf639b3, 0xc2d3d4df, 0x6d49a671, 0x0047eb5c, 111); + insert(6, k, 0xd11c5a10, 0x87d5ee54, 0x7dfda836, 0x80c37ed0, 116); + insert(6, k, 0xce4dc174, 0x854f7a31, 0x258bb22b, 0x84f46ab5, 120); + insert(6, k, 0x3154ae83, 0xb559bdcf, 0xdeb5b6c8, 0xa3a8670c, 111); + insert(6, k, 0x7cac479f, 0x28478395, 0xec4faf87, 0x8bb6c4eb, 112); + insert(6, k, 0xd2cde9d2, 0xc713fd20, 0x6328b706, 0x4d6302b9, 115); + insert(6, k, 0x29b44a75, 0x7073e2b2, 0x61901d28, 0x91d6e3f9, 113); + insert(6, k, 0xf1a75ce0, 0x5fc6b30b, 0x7eb3376e, 0xb6f8cc38, 114); + insert(6, k, 0x6a56e46f, 0xe8e44f37, 0x59df81ee, 0xb4955f30, 117); + insert(6, k, 0x66445b69, 0x9e33fa4e, 0x4e91128a, 0xc7ded069, 123); + insert(6, k, 0xce59e051, 0x76d2973e, 0x4b98fb0e, 0x6d8d1a10, 115); + insert(6, k, 0x121e96a3, 0x88d58529, 0x17fdc23d, 0x8317773d, 124); + insert(6, k, 0x888f9c0c, 0xae300e2b, 0x583bdb92, 0x2e24cceb, 127); + insert(6, k, 0xd6382600, 0xa5971cef, 0x71ae9686, 0xa9835aa0, 115); + insert(6, k, 0x20b99e76, 0xca80cfca, 0x54307677, 0xc12e06e0, 113); + insert(6, k, 0x5c329aa3, 0x7cc7922d, 0x69dfdfb2, 0xbe44e3b7, 116); + insert(6, k, 0x20f81d67, 0x8f71a1c6, 0x2ed5ee74, 0x7096efc7, 115); + insert(6, k, 0x51b711f1, 0x18ef7f2f, 0xd1fa3d4c, 0xfbc5031f, 124); + insert(6, k, 0x49570683, 0x6845cfc9, 0x5033eb10, 0x89020b4b, 127); + insert(6, k, 0x64bcfe45, 0x1c9af4fa, 0x14854aa1, 0x643d1dc9, 128); + insert(6, k, 0x89b56b5b, 0xead64f37, 0x64992e55, 0xdbf0aa97, 117); + insert(6, k, 0x89dd19e5, 0xd0f23851, 0x72e127d0, 0x9b8b0e9f, 113); + insert(6, k, 0x7f2b65e7, 0x12ca67cb, 0x270a9042, 0xff64b24f, 127); + insert(6, k, 0x1e6c2b0e, 0x8b5eb4ab, 0x4636c724, 0x9f37a399, 121); + insert(6, k, 0xae51b6e9, 0xcdc586a2, 0xcd45e446, 0x718a9117, 126); + insert(6, k, 0x6f9cba76, 0xa92e2e08, 0x24c8f6c0, 0xeca0bd6c, 119); + insert(6, k, 0xc0722698, 0xf213ead7, 0xb76b9360, 0xb7821792, 121); + insert(6, k, 0x10a05138, 0xd0e74cc5, 0x1d021dc5, 0xc338c7e0, 127); + insert(6, k, 0x55e284aa, 0x084e7df9, 0x82cca1e0, 0xd6c051bf, 115); + insert(6, k, 0x3d2c8009, 0x2080d135, 0x651a82f5, 0x239d03c0, 122); + insert(6, k, 0x98d615c8, 0x926a014f, 0x838bc671, 0x1f62c70d, 112); + insert(6, k, 0xfda1f334, 0x648d4c29, 0xf1e952cd, 0x291f29c6, 122); + insert(6, k, 0x71006812, 0x1e4ec31c, 0xd3780187, 0x3cc90aee, 117); + insert(6, k, 0x1033f64f, 0x7ddc413d, 0x5967b0a2, 0x857c231a, 124); + insert(6, k, 0xcb4ad6a1, 0xd7f989cc, 0x6ac8fe49, 0x338fc646, 119); + insert(6, k, 0xea823fde, 0x4a349eed, 0x87737f8c, 0x74864941, 120); + insert(6, k, 0x4b5188e2, 0x6ba1cc5c, 0xd564c75e, 0xcf1d9b01, 115); + insert(6, k, 0xed377c10, 0x0fa7ac92, 0x764b9857, 0x3a70f33b, 123); + insert(6, k, 0x86d889f5, 0x174f3994, 0xd3208661, 0xf3dda636, 118); + insert(6, k, 0x32cd0935, 0x63c9146d, 0xefc7a9dc, 0xc943ca9f, 111); + insert(6, k, 0x55648547, 0xb2e2a8a3, 0x1e412d0b, 0xf1821568, 114); + insert(6, k, 0x9713250c, 0x4db8b0c4, 0x78242aa4, 0x00469405, 116); + insert(6, k, 0xec2a65ac, 0xde28182e, 0xa648c485, 0xb94ad7a6, 113); + insert(6, k, 0x1c13c111, 0xf30fd80f, 0x45b5cdf8, 0x6b816fe0, 123); + insert(6, k, 0x8ff3cb97, 0x2cb6f525, 0x82d656ec, 0x08675e77, 127); + insert(6, k, 0x0d8086b0, 0x65dc0c55, 0x673f79d7, 0x6b216a8e, 121); + insert(6, k, 0x1ab72309, 0x003fd48b, 0x341a8329, 0xe1b9b105, 125); + insert(6, k, 0xbb8aa735, 0xf5b54188, 0x36cdbddb, 0xdb9e5ae6, 128); + insert(6, k, 0x4cfb201a, 0xf6340066, 0xbc10a8d0, 0xe1dd6ce2, 127); + insert(6, k, 0xdafb8169, 0x7986d6a9, 0xd7715701, 0xa4e557aa, 116); + insert(6, k, 0xbd63fd1d, 0x422d289a, 0xd61425e2, 0x77af84ae, 127); + insert(6, k, 0x4566d407, 0x2add51ef, 0xbd31e22c, 0x0ffec3f1, 121); + insert(6, k, 0x21d2aca3, 0xfdaff575, 0xf7814884, 0x581314d2, 125); + insert(6, k, 0x31ffa2b6, 0xe3d08ea0, 0xc151a9df, 0x448ce51a, 112); + insert(6, k, 0x2e6ccf8a, 0xd4b7ac38, 0xe9ef84f3, 0x6fb0f171, 117); + insert(6, k, 0x13bf299a, 0x1cf18371, 0x56aa6eb2, 0x9eb1228d, 124); + insert(6, k, 0x988d1e56, 0x821e57d5, 0x2be89b96, 0x2b0a7fb1, 117); + insert(6, k, 0x9f8bbbe1, 0xcd2a7eec, 0x7fe61fcc, 0x942a703e, 122); + insert(6, k, 0x60681692, 0xc4f45132, 0x756d2c51, 0x6835e4c8, 123); + insert(6, k, 0x66c6e595, 0xf53ff5aa, 0xf3ee2700, 0xf515950b, 120); + insert(6, k, 0xc29200b2, 0x2424e1a1, 0x7095574a, 0x2af61fc7, 114); + insert(6, k, 0x76e44a39, 0x59d1e5f3, 0x12a38390, 0xc96cc732, 125); + insert(6, k, 0x21db8a62, 0x94278c1c, 0x38a270c5, 0xccd773f3, 121); + insert(6, k, 0xdc8bae12, 0x8280e7b0, 0x9dd4f97b, 0x390aa1ef, 116); + insert(6, k, 0xe4d60e61, 0x0a6324c7, 0x06f915a9, 0x0fdb93f3, 123); + insert(6, k, 0x28685f9c, 0xcc902d12, 0x0671555e, 0xbcf62166, 112); + insert(6, k, 0xb062ad80, 0x05071c7d, 0x441765ee, 0x9561c4fe, 121); + insert(6, k, 0xcf0232fd, 0xc0ec1978, 0xd1039347, 0x224aaefe, 117); + insert(6, k, 0x8c4d5a46, 0x230b1bde, 0x376b1690, 0xb490b29f, 120); + insert(6, k, 0x0aed0dca, 0x95a130da, 0x196336d5, 0xc473e0e0, 126); + insert(6, k, 0xc220d4c1, 0xde5a3a38, 0xf876696a, 0x03680d9e, 116); + insert(6, k, 0x483185e3, 0xeeaa53f4, 0x81eb96d9, 0xa2164d8c, 121); + insert(6, k, 0xaef25e44, 0x7ad30ebc, 0x7df9cf62, 0xb4c1c51b, 128); + insert(6, k, 0x50f3ff5a, 0x71a6f8e7, 0x78a1158c, 0x92025a4c, 125); +#undef insert + +#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 " GIT_REVISION " 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); +#undef test + + if (success) + pr_info("routing table " GIT_REVISION " self-tests: pass\n"); + else + return; + + time = jiffies; +#define test(version, mem, ipa, ipb, ipc, ipd) routing_table_lookup_v##version(&t, ip##version(ipa, ipb, ipc, ipd)) + for (i = 0; i < 10000000; ++i) { + 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, h, 4, 1, 4, 8); + test(6, h, 0xabcdef, 0xe2323, 0x121212, 0x3333); + } +#undef test + time = jiffies - time; + pr_info("routing table " GIT_REVISION " benchmark: %u msecs\n", jiffies_to_msecs(time)); + routing_table_free(&t); +} +#endif diff --git a/routing-table.h b/routing-table.h new file mode 100644 index 0000000..1044474 --- /dev/null +++ b/routing-table.h @@ -0,0 +1,54 @@ +/* Copyright 2015 Jason A. Donenfeld <Jason@zx2c4.com>. All Rights Reserved. */ + +#ifndef ROUTINGTABLE_H +#define ROUTINGTABLE_H + +#include <linux/list.h> +#include <linux/ip.h> +#include <linux/ipv6.h> + +struct routing_table { + struct hlist_head head; +}; + +void routing_table_init(struct routing_table *table); +void routing_table_free(struct routing_table *table); +int routing_table_insert_v4(struct routing_table *table, struct in_addr ip, uint8_t cidr, void *value); +int routing_table_insert_v6(struct routing_table *table, struct in6_addr ip, uint8_t cidr, void *value); +void *routing_table_lookup_v4(struct routing_table *table, struct in_addr ip); +void *routing_table_lookup_v6(struct routing_table *table, struct in6_addr ip); +int routing_table_remove_v4(struct routing_table *table, struct in_addr ip, uint8_t cidr); +int routing_table_remove_v6(struct routing_table *table, struct in6_addr ip, uint8_t cidr); +int routing_table_remove_by_value(struct routing_table *table, void *value); +int routing_table_walk_ips(struct routing_table *table, void *ctx, int (*func)(void *ctx, void *value, union nf_inet_addr ip, uint8_t cidr, uint8_t ip_version)); +int routing_table_walk_ips_by_value(struct routing_table *table, void *ctx, void *value, int (*func)(void *ctx, union nf_inet_addr ip, uint8_t cidr, uint8_t ip_version)); + +static inline void *routing_table_lookup_dst(struct routing_table *table, struct sk_buff *skb) +{ + switch (ip_hdr(skb)->version) { + case 4: + return routing_table_lookup_v4(table, *(struct in_addr *)&ip_hdr(skb)->daddr); + case 6: + return routing_table_lookup_v6(table, ipv6_hdr(skb)->daddr); + default: + return NULL; + } +} + +static inline void *routing_table_lookup_src(struct routing_table *table, struct sk_buff *skb) +{ + switch (ip_hdr(skb)->version) { + case 4: + return routing_table_lookup_v4(table, *(struct in_addr *)&ip_hdr(skb)->saddr); + case 6: + return routing_table_lookup_v6(table, ipv6_hdr(skb)->saddr); + default: + return NULL; + } +} + +#ifdef DEBUG +void routing_table_selftest(void); +#endif + +#endif |