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, 18 insertions, 1 deletions

diff --git a/sys/net/rtable.h b/sys/net/rtable.h
index 9a6a9c74b66..df07c538945 100644
--- a/sys/net/rtable.h
+++ b/sys/net/rtable.h
@@ -1,4 +1,4 @@
-/*	$OpenBSD: rtable.h,v 1.1 2015/07/18 15:51:16 mpi Exp $ */
+/*	$OpenBSD: rtable.h,v 1.2 2015/08/20 12:39:43 mpi Exp $ */
 
 /*
  * Copyright (c) 2014-2015 Martin Pieuchot
@@ -19,6 +19,8 @@
 #ifndef	_NET_RTABLE_H_
 #define	_NET_RTABLE_H_
 
+#ifndef ART
+
 /*
  * Traditional BSD routing table implementation based on a radix tree.
  */
@@ -32,6 +34,21 @@
 #define	RT_ACTIVE(rt)	((rt)->rt_nodes[0].rn_flags & RNF_ACTIVE)
 #define	RT_ROOT(rt)	((rt)->rt_nodes[0].rn_flags & RNF_ROOT)
 
+#else /* ART */
+
+/*
+ * Newer routing table implementation based on ART (Allotment Routing
+ * Table).
+ */
+#include <net/art.h>
+
+#define	rt_key(rt)	((rt)->rt_dest)
+#define	rt_mask(rt)	((rt)->rt_mask)
+#define	RT_ACTIVE(rt)	((rt)->rt_node != NULL)
+#define	RT_ROOT(rt)	(0)
+
+#endif /* ART */
+
 void		 rtable_init(void);
 int		 rtable_attach(void **, int);
 struct rtentry	*rtable_lookup(unsigned int, struct sockaddr *,