path: root/routing-table.c

/* 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