Import an alternative routing table backend based on Yoichi Hariguchi's

ART implementation.

ART (Allotment Routing Table) is a multibit-trie algorithm invented by
D. Knuth while reviewing Yoichi's SMART [0] (Smart Multi-Array Routing
Table) paper.

This implementation, unlike the one from the KAME project, supports
variable stride lengths which makes it easier to adapt the consumed
memory/speed trade-off.  It also let you use a bigger first-level
table, what other algorithms such as POPTRIE [1] need to implement
separately.

Adaptation to the OpenBSD kernel has been done with two different data
structures.  ART nodes and route entries are managed separately which
makes the algorithm implementation free of any MULTIPATH logic.

This implementation does not include Path Compression.

[0] http://www.hariguchi.org/art/smart.pdf
[1] http://conferences.sigcomm.org/sigcomm/2015/pdf/papers/p57.pdf

ok dlg@, reyk@

1 files changed, 3 insertions, 1 deletions

diff --git a/sys/net/route.c b/sys/net/route.c
index c8d75fee77e..56adb555ec9 100644
--- a/sys/net/route.c
+++ b/sys/net/route.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: route.c,v 1.223 2015/08/19 13:27:38 bluhm Exp $	*/
+/*	$OpenBSD: route.c,v 1.224 2015/08/20 12:39:43 mpi Exp $	*/
 /*	$NetBSD: route.c,v 1.14 1996/02/13 22:00:46 christos Exp $	*/
 
 /*
@@ -1238,6 +1238,7 @@ rt_ifa_del(struct ifaddr *ifa, int flags, struct sockaddr *dst)
 	}
 	if ((rt = rtalloc(dst, 0, rtableid)) != NULL) {
 		rt->rt_refcnt--;
+#ifndef ART
 		/* try to find the right route */
 		while (rt && rt->rt_ifa != ifa)
 			rt = (struct rtentry *)
@@ -1248,6 +1249,7 @@ rt_ifa_del(struct ifaddr *ifa, int flags, struct sockaddr *dst)
 			return (flags & RTF_HOST ? EHOSTUNREACH
 						: ENETUNREACH);
 		}
+#endif
 	}
 
 	memset(&info, 0, sizeof(info));