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, 61 insertions, 0 deletions

diff --git a/sys/net/art.h b/sys/net/art.h
new file mode 100644
index 00000000000..2cc33f57209
--- /dev/null
+++ b/sys/net/art.h
@@ -0,0 +1,61 @@
+/* $OpenBSD: art.h,v 1.1 2015/08/20 12:39:43 mpi Exp $ */
+
+/*
+ * Copyright (c) 2015 Martin Pieuchot
+ *
+ * Permission to use, copy, modify, and distribute this software for any
+ * purpose with or without fee is hereby granted, provided that the above
+ * copyright notice and this permission notice appear in all copies.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
+ * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
+ * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
+ * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
+ * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
+ * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
+ * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
+ */
+
+#ifndef _NET_ART_H_
+#define _NET_ART_H_
+
+#define ART_MAXLVL	16	/* We currently use 16 levels for IPv6. */
+
+/*
+ * Root of the ART tables, equivalent to the radix head.
+ */
+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 */
+	uint8_t			 ar_off;	/* Offset of the key in bytes */
+	unsigned int		 ar_rtableid;	/* ID of this routing table */
+};
+
+/*
+ * Forward declaration needed for the list of mpath routes
+ * attached to a single ART node.
+ */
+struct rtentry;
+
+/*
+ * A node is the internal representation of a route entry.
+ */
+struct art_node {
+	struct sockaddr		*an_dst;	/* Destination address (key) */
+	int			 an_plen;	/* Prefix length */
+
+	LIST_HEAD(, rtentry)	 an_rtlist;	/* Route related to this node */
+};
+
+void		 art_init(void);
+int		 art_attach(void **, int);
+struct art_node *art_insert(struct art_root *, struct art_node *);
+struct art_node *art_delete(struct art_root *, struct art_node *);
+struct art_node	*art_match(struct art_root *, struct sockaddr *);
+struct art_node *art_lookup(struct art_root *, struct sockaddr *, int);
+int		 art_walk(struct art_root *,
+		     int (*)(struct art_node *, void *), void *);
+
+#endif /* _NET_ART_H_ */