Allotment routing table implementationart

4 files changed, 1518 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
diff --git a/main.c b/main.c
new file mode 100644
index 0000000..01adf2c
--- /dev/null
+++ b/main.c
@@ -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..ac25977
--- /dev/null
+++ b/routing-table.c
@@ -0,0 +1,1401 @@
+/* Copyright 2015 Jason A. Donenfeld <Jason@zx2c4.com>. All Rights Reserved.
+ * Copyright 2015 Martin Pieuchot <mpi@openbsd.org>.
+ * Copyright 2001 Yoichi Hariguchi <ayasdad@gmail.com>.
+ *
+ * Based on src/sys/net/art.c from OpenBSD and this paper:
+ * http://www.hariguchi.org/art/art.pdf
+ */
+
+#include "routing-table.h"
+
+/*
+ * A node is the internal representation of a route entry.
+ */
+struct art_node {
+	uint8_t an_cidr;	/* Prefix length */
+	void *an_data;		/* Data related to this node */
+	uint8_t an_addr[];	/* Address */
+};
+
+/*
+ * Allotment Table.
+ */
+struct art_table {
+	struct art_table *at_parent;	/* Parent table */
+	uint32_t at_index;		/* Index in the parent table */
+	uint32_t at_minfringe;		/* Index that fringe begins */
+	uint32_t at_level;		/* Level of the table */
+	uint8_t at_bits;		/* Stride length of the table */
+	uint8_t at_offset;		/* Sum of parents' stride len */
+
+	/*
+	 * Items stored in the heap are pointers to nodes, in the leaf
+	 * case, or tables otherwise.  One exception is index 0 which
+	 * is a route counter.
+	 */
+	union {
+		struct art_node *node;
+		struct art_table *child;
+		unsigned long count;
+	} *at_heap; /* Array of 2^(slen+1) items */
+};
+
+#define ISLEAF(e) (((unsigned long)(e).node & 1) == 0)
+#define SUBTABLE(e) (((struct art_table *)((unsigned long)(e).child & ~1)))
+#define ASNODE(t) ((struct art_node *)((unsigned long)(t) | 1))
+
+#define at_refcnt at_heap[0].count /* Refcounter (1 per different route) */
+#define at_default at_heap[1].node /* Default route (was in parent heap) */
+
+static inline void art_table_ref(struct art_table *at);
+static struct art_table *art_table_get(struct art_root *ar, struct art_table *parent, int j);
+static struct art_table *art_table_put(struct art_table *at);
+
+/*
+ * Per routing table initialization API function.
+ */
+static int art_init_v4(struct art_root *ar)
+{
+	memset(ar, 0, sizeof(*ar));
+	ar->ar_alen = 32;
+	ar->ar_nlvl = 3;
+	ar->ar_bits[0] = 16;
+	ar->ar_bits[1] = 8;
+	ar->ar_bits[2] = 8;
+	ar->ar_root = art_table_get(ar, NULL, -1);
+	if (!ar->ar_root)
+		return -ENOMEM;
+
+	return 0;
+}
+static int art_init_v6(struct art_root *ar)
+{
+	int i;
+
+	memset(ar, 0, sizeof(*ar));
+	ar->ar_alen = 128;
+	ar->ar_nlvl = 16;
+	for (i = 0; i < ar->ar_nlvl; ++i)
+		ar->ar_bits[i] = 8;
+	ar->ar_root = art_table_get(ar, NULL, -1);
+	if (!ar->ar_root)
+		return -ENOMEM;
+
+	return 0;
+}
+static void art_uninit(struct art_root *ar)
+{
+	art_table_put(ar->ar_root);
+}
+
+/*
+ * Return true if ``old'' and ``new`` are identical, false otherwise.
+ */
+static inline bool art_check_duplicate(struct art_node *old, struct art_node *new)
+{
+	if (!old)
+		return false;
+
+	if (old->an_cidr == new->an_cidr)
+		return true;
+
+	return false;
+}
+
+/*
+ * Return the base index of the part of ``addr'' and ``cidr''
+ * corresponding to the range covered by the table ``at''.
+ *
+ * In other words, this function take the multi-level (complete)
+ * address ``addr'' and prefix length ``cidr'' and return the
+ * single level base index for the table ``at''.
+ *
+ * For example with an address size of 32bit divided into four
+ * 8bit-long tables, there's a maximum of 4 base indexes if the
+ * prefix length is > 24.
+ */
+static int art_bindex(struct art_table *at, uint8_t *addr, uint8_t cidr)
+{
+	uint8_t boff, bend;
+	uint32_t k;
+
+	if (cidr < at->at_offset || cidr > (at->at_offset + at->at_bits))
+		return -1;
+
+	/*
+	 * We are only interested in the part of the prefix length
+	 * corresponding to the range of this table.
+	 */
+	cidr -= at->at_offset;
+
+	/*
+	 * Jump to the first byte of the address containing bits
+	 * covered by this table.
+	 */
+	addr += (at->at_offset / 8);
+
+	/* ``at'' covers the bit range between ``boff'' & ``bend''. */
+	boff = (at->at_offset % 8);
+	bend = (at->at_bits + boff);
+
+	if (bend > 24) {
+		k = (addr[0] & ((1 << (8 - boff)) - 1)) << (bend - 8);
+		k |= addr[1] << (bend - 16);
+		k |= addr[2] << (bend - 24);
+		k |= addr[3] >> (32 - bend);
+	} else if (bend > 16) {
+		k = (addr[0] & ((1 << (8 - boff)) - 1)) << (bend - 8);
+		k |= addr[1] << (bend - 16);
+		k |= addr[2] >> (24 - bend);
+	} else if (bend > 8) {
+		k = (addr[0] & ((1 << (8 - boff)) - 1)) << (bend - 8);
+		k |= addr[1] >> (16 - bend);
+	} else {
+		k = (addr[0] >> (8 - bend)) & ((1 << at->at_bits) - 1);
+	}
+
+	/*
+	 * Single level base index formula:
+	 */
+	return ((k >> (at->at_bits - cidr)) + (1 << cidr));
+}
+
+/*
+ * Single level lookup function.
+ *
+ * Return the fringe index of the part of ``addr''
+ * corresponding to the range covered by the table ``at''.
+ */
+static inline int art_findex(struct art_table *at, uint8_t *addr)
+{
+	return art_bindex(at, addr, (at->at_offset + at->at_bits));
+}
+
+/*
+ * (Non-perfect) lookup API function.
+ *
+ * Return the best existing match for a destination.
+ */
+static struct art_node *art_match(struct art_root *ar, uint8_t *addr)
+{
+	struct art_table *at = ar->ar_root;
+	struct art_node *dflt = NULL;
+	int j;
+
+	/*
+	 * Iterate until we find a leaf.
+	 */
+	for (;;) {
+		/*
+		 * Rember the default route of this table in case
+		 * we do not find a better matching route.
+		 */
+		if (at->at_default)
+			dflt = at->at_default;
+
+		/* Do a single level route lookup. */
+		j = art_findex(at, addr);
+
+		/* If this is a leaf we're done. */
+		if (ISLEAF(at->at_heap[j]))
+			break;
+
+		at = SUBTABLE(at->at_heap[j]);
+	}
+
+	if (at->at_heap[j].node)
+		return at->at_heap[j].node;
+
+	return dflt;
+}
+
+/*
+ * Perfect lookup API function.
+ *
+ * Return a perfect match for a destination/prefix-length pair or NULL if
+ * it does not exist.
+ */
+static struct art_node *art_lookup(struct art_root *ar, uint8_t *addr, uint8_t cidr)
+{
+	struct art_table *at = ar->ar_root;
+	struct art_node *an;
+	int i, j;
+
+	/* Default route */
+	if (cidr == 0)
+		return at->at_default;
+
+	/*
+	 * If the prefix length is smaller than the sum of
+	 * the stride length at this level the entry must
+	 * be in the current table.
+	 */
+	while (cidr > (at->at_offset + at->at_bits)) {
+		/* Do a single level route lookup. */
+		j = art_findex(at, addr);
+
+		/* A leaf is a match, but not a perfect one. */
+		if (ISLEAF(at->at_heap[j]))
+			return NULL;
+
+		at = SUBTABLE(at->at_heap[j]);
+	}
+
+	i = art_bindex(at, addr, cidr);
+	if (i == -1)
+		return NULL;
+
+	if (!ISLEAF(at->at_heap[i]))
+		an = SUBTABLE(at->at_heap[i])->at_default;
+	else
+		an = at->at_heap[i].node;
+
+	return an;
+}
+
+/*
+ * Substitute a node by another in the subtree whose root index is given.
+ *
+ * This function iterates on the table ``at'' at index ``i'' until no
+ * more ``old'' node can be replaced by ``new''.
+ *
+ * This function was originally written by Don Knuth in CWEB. The
+ * complicated ``goto''s are the result of expansion of the two
+ * following recursions:
+ *
+ *	art_allot(at, i, old, new)
+ *	{
+ *		int k = i;
+ *		if (at->at_heap[k] == old)
+ *			at->at_heap[k] = new;
+ *		if (k >= at->at_minfringe)
+ *			 return;
+ *		k <<= 1;
+ *		art_allot(at, k, old, new);
+ *		k++;
+ *		art_allot(at, k, old, new);
+ *	}
+ */
+static void art_allot(struct art_table *at, int i, struct art_node *old, struct art_node *new)
+{
+	int k = i;
+
+again:
+	k <<= 1;
+	if (k < at->at_minfringe)
+		goto nonfringe;
+
+	/* Change fringe nodes. */
+	for (;;) {
+		if (!ISLEAF(at->at_heap[k])) {
+			if (SUBTABLE(at->at_heap[k])->at_default == old)
+				SUBTABLE(at->at_heap[k])->at_default = new;
+		} else if (at->at_heap[k].node == old) {
+			at->at_heap[k].node = new;
+		}
+		if (k % 2)
+			goto moveup;
+		k++;
+	}
+
+nonfringe:
+	if (at->at_heap[k].node == old)
+		goto again;
+moveon:
+	if (k % 2)
+		goto moveup;
+	k++;
+	goto nonfringe;
+moveup:
+	k >>= 1;
+	at->at_heap[k].node = new;
+
+	/* Change non-fringe node. */
+	if (k != i)
+		goto moveon;
+}
+
+/*
+ * Single level insertion.
+ */
+static struct art_node *art_table_insert(struct art_root *ar, struct art_table *at, int i, struct art_node *an)
+{
+	struct art_node *prev;
+
+	if (!ISLEAF(at->at_heap[i]))
+		prev = SUBTABLE(at->at_heap[i])->at_default;
+	else
+		prev = at->at_heap[i].node;
+
+	if (art_check_duplicate(prev, an))
+		return prev;
+
+	art_table_ref(at);
+
+	/*
+	 * If the index `i' of the route that we are inserting is not
+	 * a fringe index, we need to allot this new route pointer to
+	 * all the corresponding fringe indices.
+	 */
+	if (i < at->at_minfringe)
+		art_allot(at, i, prev, an);
+	else if (!ISLEAF(at->at_heap[i]))
+		SUBTABLE(at->at_heap[i])->at_default = an;
+	else
+		at->at_heap[i].node = an;
+
+	return an;
+}
+
+/*
+ * Insertion API function.
+ *
+ * Insert the given node or return an existing one if a node with the
+ * same destination/mask pair is already present.
+ */
+static struct art_node *art_insert(struct art_root *ar, struct art_node *an)
+{
+	struct art_table *at = ar->ar_root;
+	int i, j;
+
+	/* Default route */
+	if (an->an_cidr == 0) {
+		if (art_check_duplicate(at->at_default, an))
+			return at->at_default;
+
+		at->at_default = an;
+		return an;
+	}
+
+	/*
+	 * If the prefix length is smaller than the sum of
+	 * the stride length at this level the entry must
+	 * be in the current table.
+	 */
+	while (an->an_cidr > (at->at_offset + at->at_bits)) {
+		/* Do a single level route lookup. */
+		j = art_findex(at, an->an_addr);
+
+		/*
+		 * If the node corresponding to the fringe index is
+		 * a leaf we need to allocate a subtable.  The route
+		 * entry of this node will then become the default
+		 * route of the subtable.
+		 */
+		if (ISLEAF(at->at_heap[j])) {
+			struct art_table *child;
+
+			child = art_table_get(ar, at, j);
+			if (!child)
+				return NULL;
+
+			at->at_heap[j].node = ASNODE(child);
+		}
+
+		at = SUBTABLE(at->at_heap[j]);
+	}
+
+	i = art_bindex(at, an->an_addr, an->an_cidr);
+	if (i == -1)
+		return NULL;
+
+	return art_table_insert(ar, at, i, an);
+}
+
+static bool art_insert_or_change_and_free(struct art_root *ar, struct art_node *an)
+{
+	struct art_node *inserted = art_insert(ar, an);
+	if (!inserted) {
+		kfree(an);
+		return false;
+	}
+	if (an == inserted)
+		return true;
+	inserted->an_data = an->an_data;
+	kfree(an);
+	return true;
+}
+
+static inline int art_table_free(struct art_table *at)
+{
+	at->at_refcnt--;
+
+	if (at->at_refcnt == 0) {
+		/*
+		 * Garbage collect this table and all its parents
+		 * that are empty.
+		 */
+		do
+			at = art_table_put(at);
+		while (at->at_refcnt == 0);
+
+		return 1;
+	}
+
+	return 0;
+}
+
+static inline void art_table_ref(struct art_table *at)
+{
+	++at->at_refcnt;
+}
+
+/*
+ * Single level deletion.
+ */
+static struct art_node *art_table_delete(struct art_root *ar, struct art_table *at, int i, struct art_node *node)
+{
+	struct art_node *next;
+
+	/* We are removing an entry from this table. */
+	if (art_table_free(at))
+		return node;
+
+	/* Get the next most specific route for the index `i'. */
+	if ((i >> 1) > 1)
+		next = at->at_heap[i >> 1].node;
+	else
+		next = NULL;
+
+	/*
+	 * If the index `i' of the route that we are removing is not
+	 * a fringe index, we need to allot the next most specific
+	 * route pointer to all the corresponding fringe indices.
+	 */
+	if (i < at->at_minfringe)
+		art_allot(at, i, node, next);
+	else if (!ISLEAF(at->at_heap[i]))
+		SUBTABLE(at->at_heap[i])->at_default = next;
+	else
+		at->at_heap[i].node = next;
+
+	return node;
+}
+
+/*
+ * Deletion API function.
+ */
+static struct art_node *art_delete(struct art_root *ar, struct art_node *an)
+{
+	struct art_table *at = ar->ar_root;
+	struct art_node *dflt;
+	int i, j;
+
+	/* Default route */
+	if (an->an_cidr == 0) {
+		dflt = at->at_default;
+		if (!art_check_duplicate(dflt, an))
+			return NULL;
+		at->at_default = NULL;
+		return dflt;
+	}
+
+	/*
+	 * If the prefix length is smaller than the sum of
+	 * the stride length at this level the entry must
+	 * be in the current table.
+	 */
+	while (an->an_cidr > (at->at_offset + at->at_bits)) {
+		/* Do a single level route lookup. */
+		j = art_findex(at, an->an_addr);
+
+		/* If this is a leaf, there is no route to delete. */
+		if (ISLEAF(at->at_heap[j]))
+			return NULL;
+
+		at = SUBTABLE(at->at_heap[j]);
+	}
+
+	i = art_bindex(at, an->an_addr, an->an_cidr);
+	if (i == -1)
+		return NULL;
+
+	return art_table_delete(ar, at, i, an);
+}
+
+static int art_table_walk(struct art_table *at, int (*f) (struct art_node *, void *), void *arg)
+{
+	struct art_node *next, *an = NULL;
+	int i, j, error = 0;
+	uint32_t maxfringe;
+
+	art_table_ref(at);
+
+	maxfringe = (at->at_minfringe << 1);
+
+	/*
+	 * Iterate non-fringe nodes in the ``natural'' order.
+	 */
+	for (j = 1; j < at->at_minfringe; j += 2) {
+		/*
+		 * The default route (index 1) is processed by the
+		 * parent table (where it belongs) otherwise it could
+		 * be processed more than once.
+		 */
+		for (i = max(j, 2); i < at->at_minfringe; i <<= 1) {
+			next = at->at_heap[i >> 1].node;
+			an = at->at_heap[i].node;
+			if (an && an != next) {
+				error = (*f)(an, arg);
+				if (error)
+					goto out;
+			}
+		}
+	}
+
+	/*
+	 * Iterate fringe nodes.
+	 */
+	for (i = at->at_minfringe; i < maxfringe; i++) {
+		next = at->at_heap[i >> 1].node;
+		if (!ISLEAF(at->at_heap[i]))
+			an = SUBTABLE(at->at_heap[i])->at_default;
+		else
+			an = at->at_heap[i].node;
+		if (an && an != next) {
+			error = (*f)(an, arg);
+			if (error)
+				goto out;
+		}
+
+		if (ISLEAF(at->at_heap[i]))
+			continue;
+
+		error = art_table_walk(SUBTABLE(at->at_heap[i]), f, arg);
+		if (error)
+			break;
+	}
+
+out:
+	art_table_free(at);
+	return error;
+}
+
+/*
+ * Iteration API function.
+ */
+static int art_walk(struct art_root *ar, int (*f) (struct art_node *, void *), void *arg)
+{
+	struct art_table *at = ar->ar_root;
+	int error;
+
+	/*
+	 * The default route should be processed here because the root
+	 * table does not have a parent.
+	 */
+	if (at->at_default) {
+		error = (*f)(at->at_default, arg);
+		if (error)
+			return error;
+	}
+
+	return art_table_walk(at, f, arg);
+}
+
+/*
+ * Create a table and use the given index to set its default route.
+ *
+ * Note:  This function does not modify the root or the parent.
+ */
+static struct art_table *art_table_get(struct art_root *ar, struct art_table *parent, int j)
+{
+	struct art_table *at;
+	size_t size;
+	uint32_t lvl;
+
+	if (parent)
+		lvl = parent->at_level + 1;
+	else
+		lvl = 0;
+
+	size = sizeof(*at) + (1 << (ar->ar_bits[lvl] + 1)) * sizeof(void *);
+	at = kzalloc(size, GFP_KERNEL);
+	if (!at)
+		return NULL;
+
+	at->at_parent = parent;
+	at->at_index = j;
+	at->at_minfringe = (1 << ar->ar_bits[lvl]);
+	at->at_level = lvl;
+	at->at_bits = ar->ar_bits[lvl];
+	at->at_heap = (void *)(at + 1);
+
+	art_table_ref(at);
+
+	if (parent) {
+		at->at_default = parent->at_heap[j].node;
+		at->at_offset = (parent->at_offset + parent->at_bits);
+	}
+
+	return at;
+}
+
+/*
+ * Delete a table and use its index to restore its parent's default route.
+ *
+ * Note:  Modify its parent to unlink the table from it.
+ */
+static struct art_table *art_table_put(struct art_table *at)
+{
+	struct art_table *parent = at->at_parent;
+
+	if (parent) {
+		/* Give the route back to its parent. */
+		parent->at_heap[at->at_index].node = at->at_default;
+		art_table_free(parent);
+	}
+
+	kfree(at);
+
+	return parent;
+}
+
+
+/***** Begin routing_table wrappers: ******/
+
+int routing_table_init(struct routing_table *table)
+{
+	int ret;
+	ret = art_init_v4(&table->v4);
+	if (ret)
+		return ret;
+	ret = art_init_v6(&table->v6);
+	if (ret) {
+		art_uninit(&table->v4);
+		return ret;
+	}
+	rwlock_init(&table->lock);
+	return 0;
+}
+
+static int remove_all(struct art_node *an, void *arg)
+{
+	struct art_root *ar = arg;
+	art_delete(ar, an);
+	kfree(an);
+	return 0;
+}
+
+void routing_table_free(struct routing_table *table)
+{
+	write_lock_bh(&table->lock);
+	art_walk(&table->v4, remove_all, &table->v4);
+	art_uninit(&table->v4);
+	art_walk(&table->v6, remove_all, &table->v6);
+	art_uninit(&table->v6);
+	write_unlock_bh(&table->lock);
+}
+
+int routing_table_insert_v4(struct routing_table *table, struct in_addr ip, uint8_t cidr, void *value)
+{
+	bool success;
+	struct art_node *an = kmalloc(sizeof(struct art_node) + sizeof(struct in_addr), GFP_KERNEL);
+	if (!an)
+		return -ENOMEM;
+	memcpy(an->an_addr, &ip, sizeof(struct in_addr));
+	an->an_cidr = cidr;
+	an->an_data = value;
+	write_lock_bh(&table->lock);
+	success = art_insert_or_change_and_free(&table->v4, an);
+	write_unlock_bh(&table->lock);
+	if (!success)
+		return -EINVAL;
+	return 0;
+}
+
+int routing_table_insert_v6(struct routing_table *table, struct in6_addr ip, uint8_t cidr, void *value)
+{
+	bool success;
+	struct art_node *an = kmalloc(sizeof(struct art_node) + sizeof(struct in6_addr), GFP_KERNEL);
+	if (!an)
+		return -ENOMEM;
+	memcpy(an->an_addr, &ip, sizeof(struct in6_addr));
+	an->an_cidr = cidr;
+	an->an_data = value;
+	write_lock_bh(&table->lock);
+	success = art_insert_or_change_and_free(&table->v6, an);
+	write_unlock_bh(&table->lock);
+	if (!success)
+		return -EINVAL;
+	return 0;
+}
+
+void *routing_table_lookup_v4(struct routing_table *table, struct in_addr ip)
+{
+	struct art_node *an;
+	void *data = NULL;
+	read_lock_bh(&table->lock);
+	an = art_match(&table->v4, (uint8_t *)&ip);
+	if (an)
+		data = an->an_data;
+	read_unlock_bh(&table->lock);
+	return data;
+}
+
+void *routing_table_lookup_v6(struct routing_table *table, struct in6_addr ip)
+{
+	struct art_node *an;
+	void *data = NULL;
+	read_lock_bh(&table->lock);
+	an = art_match(&table->v6, (uint8_t *)&ip);
+	if (an)
+		data = an->an_data;
+	read_unlock_bh(&table->lock);
+	return data;
+}
+
+int routing_table_remove_v4(struct routing_table *table, struct in_addr ip, uint8_t cidr)
+{
+	int ret = -EINVAL;
+	struct art_node *an;
+	write_lock_bh(&table->lock);
+	an = art_lookup(&table->v4, (uint8_t *)&ip, cidr);
+	if (!an)
+		goto out;
+	if (art_delete(&table->v4, an)) {
+		kfree(an);
+		ret = 0;
+	}
+out:
+	write_unlock_bh(&table->lock);
+	return ret;
+}
+
+int routing_table_remove_v6(struct routing_table *table, struct in6_addr ip, uint8_t cidr)
+{
+	int ret = -EINVAL;
+	struct art_node *an;
+	write_lock_bh(&table->lock);
+	an = art_lookup(&table->v6, (uint8_t *)&ip, cidr);
+	if (!an)
+		goto out;
+	if (art_delete(&table->v6, an)) {
+		kfree(an);
+		ret = 0;
+	}
+out:
+	write_unlock_bh(&table->lock);
+	return ret;
+}
+
+struct remove_ctx {
+	void *data;
+	struct art_root *ar;
+	bool found;
+};
+static int remove(struct art_node *an, void *arg)
+{
+	struct remove_ctx *ctx = arg;
+	if (an->an_data == ctx->data) {
+		if (art_delete(ctx->ar, an)) {
+			kfree(an);
+			ctx->found = true;
+		}
+	}
+	return 0;
+}
+int routing_table_remove_by_value(struct routing_table *table, void *value)
+{
+	struct remove_ctx ctx = {
+		.data = value,
+		.found = false
+	};
+	write_lock_bh(&table->lock);
+	ctx.ar = &table->v4;
+	art_walk(ctx.ar, remove, &ctx);
+	ctx.ar = &table->v6;
+	art_walk(ctx.ar, remove, &ctx);
+	write_unlock_bh(&table->lock);
+	return ctx.found ? 0 : -EINVAL;
+}
+
+struct walk_ctx {
+	void *ctx;
+	int (*func) (void *, void *, union nf_inet_addr, uint8_t, uint8_t);
+	uint8_t ip_version;
+};
+static int walk(struct art_node *an, void *arg)
+{
+	struct walk_ctx *ctx = arg;
+	return ctx->func(ctx->ctx, an->an_data, *(union nf_inet_addr *)an->an_addr, an->an_cidr, ctx->ip_version);
+}
+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 ret;
+	struct walk_ctx arg = {
+		.ctx = ctx,
+		.func = func
+	};
+
+	read_lock_bh(&table->lock);
+	arg.ip_version = 4;
+	ret = art_walk(&table->v4, walk, &arg);
+	if (ret)
+		goto out;
+	arg.ip_version = 6;
+	ret = art_walk(&table->v6, walk, &arg);
+out:
+	read_unlock_bh(&table->lock);
+	return ret;
+}
+
+struct walk_ip_ctx {
+	void *ctx;
+	void *value;
+	int (*func) (void *, union nf_inet_addr, uint8_t, uint8_t);
+	uint8_t ip_version;
+};
+static int walk_ip(struct art_node *an, void *arg)
+{
+	struct walk_ip_ctx *ctx = arg;
+	if (ctx->value != an->an_data)
+		return 0;
+	return ctx->func(ctx->ctx, *(union nf_inet_addr *)an->an_addr, an->an_cidr, ctx->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))
+{
+	int ret;
+	struct walk_ip_ctx arg = {
+		.ctx = ctx,
+		.value = value,
+		.func = func
+	};
+
+	read_lock_bh(&table->lock);
+	arg.ip_version = 4;
+	ret = art_walk(&table->v4, walk_ip, &arg);
+	if (ret)
+		goto out;
+	arg.ip_version = 6;
+	ret = art_walk(&table->v6, walk_ip, &arg);
+out:
+	read_unlock_bh(&table->lock);
+	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;
+
+	if (routing_table_init(&t) < 0) {
+		pr_info("routing table " GIT_REVISION " self-test: initialization FAIL\n");
+		return;
+	}
+#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..184c735
--- /dev/null
+++ b/routing-table.h
@@ -0,0 +1,68 @@
+/* Copyright 2015 Jason A. Donenfeld <Jason@zx2c4.com>. All Rights Reserved. */
+
+#ifndef ROUTINGTABLE_H
+#define ROUTINGTABLE_H
+
+#include <linux/spinlock.h>
+#include <linux/ip.h>
+#include <linux/ipv6.h>
+
+#define ART_MAXLVL 16 /* We currently use 16 levels for IPv6. */
+
+/*
+ * Root of the ART tables.
+ */
+struct art_root {
+	struct art_table *ar_root;	/* First table */
+	uint8_t ar_bits[ART_MAXLVL];	/* Per level stride */
+	uint8_t ar_nlvl;		/* Number of levels */
+	uint8_t ar_alen;		/* Address length in bits */
+};
+
+struct routing_table {
+	struct art_root v4;
+	struct art_root v6;
+	rwlock_t lock;
+};
+
+int 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