aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorCy Schubert <cy@FreeBSD.org>2013-08-20 13:24:44 +0000
committerCy Schubert <cy@FreeBSD.org>2013-08-20 13:24:44 +0000
commit2472f6195d393ad615e38aa6b28f490489671d46 (patch)
tree52d2a860347a5e06db6e5fa14ef078bc663dd6a4
parent3d09eb5a27e902b03740ad1c32f3f1d91872b04b (diff)
downloadsrc-2472f6195d393ad615e38aa6b28f490489671d46.tar.gz
src-2472f6195d393ad615e38aa6b28f490489671d46.zip
Add kernel sources from IP-Filter 5.1.2 to vendor-sys/ branch.vendor/ipfilter-sys/5-1-2
Approved by: glebius (mentor)
Notes
Notes: svn path=/vendor-sys/ipfilter/dist/; revision=254562 svn path=/vendor-sys/ipfilter/5-1-2/; revision=254565; tag=vendor/ipfilter-sys/5-1-2
-rw-r--r--netinet/ip_dstlist.c1351
-rw-r--r--netinet/ip_dstlist.h68
-rw-r--r--netinet/ipf_rb.h364
-rw-r--r--netinet/radix_ipf.c1528
-rw-r--r--netinet/radix_ipf.h95
5 files changed, 3406 insertions, 0 deletions
diff --git a/netinet/ip_dstlist.c b/netinet/ip_dstlist.c
new file mode 100644
index 000000000000..ce2e72e8130f
--- /dev/null
+++ b/netinet/ip_dstlist.c
@@ -0,0 +1,1351 @@
+/*
+ * Copyright (C) 2012 by Darren Reed.
+ *
+ * See the IPFILTER.LICENCE file for details on licencing.
+ */
+#if defined(KERNEL) || defined(_KERNEL)
+# undef KERNEL
+# undef _KERNEL
+# define KERNEL 1
+# define _KERNEL 1
+#endif
+#if defined(__osf__)
+# define _PROTO_NET_H_
+#endif
+#include <sys/errno.h>
+#include <sys/types.h>
+#include <sys/param.h>
+#include <sys/file.h>
+#if !defined(_KERNEL) && !defined(__KERNEL__)
+# include <stdio.h>
+# include <stdlib.h>
+# include <string.h>
+# define _KERNEL
+# ifdef __OpenBSD__
+struct file;
+# endif
+# include <sys/uio.h>
+# undef _KERNEL
+#else
+# include <sys/systm.h>
+# if defined(NetBSD) && (__NetBSD_Version__ >= 104000000)
+# include <sys/proc.h>
+# endif
+#endif
+#include <sys/time.h>
+#if !defined(linux)
+# include <sys/protosw.h>
+#endif
+#include <sys/socket.h>
+#if defined(_KERNEL) && (!defined(__SVR4) && !defined(__svr4__))
+# include <sys/mbuf.h>
+#endif
+#if defined(__SVR4) || defined(__svr4__)
+# include <sys/filio.h>
+# include <sys/byteorder.h>
+# ifdef _KERNEL
+# include <sys/dditypes.h>
+# endif
+# include <sys/stream.h>
+# include <sys/kmem.h>
+#endif
+#if defined(__FreeBSD_version) && (__FreeBSD_version >= 300000)
+# include <sys/malloc.h>
+#endif
+
+#include <net/if.h>
+#include <netinet/in.h>
+
+#include "netinet/ip_compat.h"
+#include "netinet/ip_fil.h"
+#include "netinet/ip_nat.h"
+#include "netinet/ip_lookup.h"
+#include "netinet/ip_dstlist.h"
+
+/* END OF INCLUDES */
+
+#ifdef HAS_SYS_MD5_H
+# include <sys/md5.h>
+#else
+# include "md5.h"
+#endif
+
+#if !defined(lint)
+static const char rcsid[] = "@(#)$Id: ip_dstlist.c,v 1.13.2.12 2012/07/20 08:40:19 darren_r Exp $";
+#endif
+
+typedef struct ipf_dstl_softc_s {
+ ippool_dst_t *dstlist[LOOKUP_POOL_SZ];
+ ippool_dst_t **tails[LOOKUP_POOL_SZ];
+ ipf_dstl_stat_t stats;
+} ipf_dstl_softc_t;
+
+
+static void *ipf_dstlist_soft_create __P((ipf_main_softc_t *));
+static void ipf_dstlist_soft_destroy __P((ipf_main_softc_t *, void *));
+static int ipf_dstlist_soft_init __P((ipf_main_softc_t *, void *));
+static void ipf_dstlist_soft_fini __P((ipf_main_softc_t *, void *));
+static int ipf_dstlist_addr_find __P((ipf_main_softc_t *, void *, int,
+ void *, u_int));
+static size_t ipf_dstlist_flush __P((ipf_main_softc_t *, void *,
+ iplookupflush_t *));
+static int ipf_dstlist_iter_deref __P((ipf_main_softc_t *, void *, int, int,
+ void *));
+static int ipf_dstlist_iter_next __P((ipf_main_softc_t *, void *, ipftoken_t *,
+ ipflookupiter_t *));
+static int ipf_dstlist_node_add __P((ipf_main_softc_t *, void *,
+ iplookupop_t *, int));
+static int ipf_dstlist_node_del __P((ipf_main_softc_t *, void *,
+ iplookupop_t *, int));
+static int ipf_dstlist_stats_get __P((ipf_main_softc_t *, void *,
+ iplookupop_t *));
+static int ipf_dstlist_table_add __P((ipf_main_softc_t *, void *,
+ iplookupop_t *));
+static int ipf_dstlist_table_del __P((ipf_main_softc_t *, void *,
+ iplookupop_t *));
+static int ipf_dstlist_table_deref __P((ipf_main_softc_t *, void *, void *));
+static void *ipf_dstlist_table_find __P((void *, int, char *));
+static void ipf_dstlist_table_free __P((ipf_dstl_softc_t *, ippool_dst_t *));
+static void ipf_dstlist_table_remove __P((ipf_main_softc_t *,
+ ipf_dstl_softc_t *, ippool_dst_t *));
+static void ipf_dstlist_table_clearnodes __P((ipf_dstl_softc_t *,
+ ippool_dst_t *));
+static ipf_dstnode_t *ipf_dstlist_select __P((fr_info_t *, ippool_dst_t *));
+static void *ipf_dstlist_select_ref __P((void *, int, char *));
+static void ipf_dstlist_node_free __P((ipf_dstl_softc_t *, ippool_dst_t *, ipf_dstnode_t *));
+static int ipf_dstlist_node_deref __P((void *, ipf_dstnode_t *));
+static void ipf_dstlist_expire __P((ipf_main_softc_t *, void *));
+static void ipf_dstlist_sync __P((ipf_main_softc_t *, void *));
+
+ipf_lookup_t ipf_dstlist_backend = {
+ IPLT_DSTLIST,
+ ipf_dstlist_soft_create,
+ ipf_dstlist_soft_destroy,
+ ipf_dstlist_soft_init,
+ ipf_dstlist_soft_fini,
+ ipf_dstlist_addr_find,
+ ipf_dstlist_flush,
+ ipf_dstlist_iter_deref,
+ ipf_dstlist_iter_next,
+ ipf_dstlist_node_add,
+ ipf_dstlist_node_del,
+ ipf_dstlist_stats_get,
+ ipf_dstlist_table_add,
+ ipf_dstlist_table_del,
+ ipf_dstlist_table_deref,
+ ipf_dstlist_table_find,
+ ipf_dstlist_select_ref,
+ ipf_dstlist_select_node,
+ ipf_dstlist_expire,
+ ipf_dstlist_sync
+};
+
+
+/* ------------------------------------------------------------------------ */
+/* Function: ipf_dstlist_soft_create */
+/* Returns: int - 0 = success, else error */
+/* Parameters: softc(I) - pointer to soft context main structure */
+/* */
+/* Allocating a chunk of memory filled with 0's is enough for the current */
+/* soft context used with destination lists. */
+/* ------------------------------------------------------------------------ */
+static void *
+ipf_dstlist_soft_create(softc)
+ ipf_main_softc_t *softc;
+{
+ ipf_dstl_softc_t *softd;
+ int i;
+
+ KMALLOC(softd, ipf_dstl_softc_t *);
+ if (softd == NULL) {
+ IPFERROR(120028);
+ return NULL;
+ }
+
+ bzero((char *)softd, sizeof(*softd));
+ for (i = 0; i <= IPL_LOGMAX; i++)
+ softd->tails[i] = &softd->dstlist[i];
+
+ return softd;
+}
+
+
+/* ------------------------------------------------------------------------ */
+/* Function: ipf_dstlist_soft_destroy */
+/* Returns: Nil */
+/* Parameters: softc(I) - pointer to soft context main structure */
+/* arg(I) - pointer to local context to use */
+/* */
+/* For destination lists, the only thing we have to do when destroying the */
+/* soft context is free it! */
+/* ------------------------------------------------------------------------ */
+static void
+ipf_dstlist_soft_destroy(softc, arg)
+ ipf_main_softc_t *softc;
+ void *arg;
+{
+ ipf_dstl_softc_t *softd = arg;
+
+ KFREE(softd);
+}
+
+
+/* ------------------------------------------------------------------------ */
+/* Function: ipf_dstlist_soft_init */
+/* Returns: int - 0 = success, else error */
+/* Parameters: softc(I) - pointer to soft context main structure */
+/* arg(I) - pointer to local context to use */
+/* */
+/* There is currently no soft context for destination list management. */
+/* ------------------------------------------------------------------------ */
+static int
+ipf_dstlist_soft_init(softc, arg)
+ ipf_main_softc_t *softc;
+ void *arg;
+{
+ return 0;
+}
+
+
+/* ------------------------------------------------------------------------ */
+/* Function: ipf_dstlist_soft_fini */
+/* Returns: Nil */
+/* Parameters: softc(I) - pointer to soft context main structure */
+/* arg(I) - pointer to local context to use */
+/* */
+/* There is currently no soft context for destination list management. */
+/* ------------------------------------------------------------------------ */
+static void
+ipf_dstlist_soft_fini(softc, arg)
+ ipf_main_softc_t *softc;
+ void *arg;
+{
+ ipf_dstl_softc_t *softd = arg;
+ int i;
+
+ for (i = -1; i <= IPL_LOGMAX; i++) {
+ while (softd->dstlist[i + 1] != NULL) {
+ ipf_dstlist_table_remove(softc, softd,
+ softd->dstlist[i + 1]);
+ }
+ }
+
+ ASSERT(softd->stats.ipls_numderefnodes == 0);
+}
+
+
+/* ------------------------------------------------------------------------ */
+/* Function: ipf_dstlist_addr_find */
+/* Returns: int - 0 = success, else error */
+/* Parameters: softc(I) - pointer to soft context main structure */
+/* arg1(I) - pointer to local context to use */
+/* arg2(I) - pointer to local context to use */
+/* arg3(I) - pointer to local context to use */
+/* arg4(I) - pointer to local context to use */
+/* */
+/* There is currently no such thing as searching a destination list for an */
+/* address so this function becomes a no-op. Its presence is required as */
+/* ipf_lookup_res_name() stores the "addr_find" function pointer in the */
+/* pointer passed in to it as funcptr, although it could be a generic null- */
+/* op function rather than a specific one. */
+/* ------------------------------------------------------------------------ */
+/*ARGSUSED*/
+static int
+ipf_dstlist_addr_find(softc, arg1, arg2, arg3, arg4)
+ ipf_main_softc_t *softc;
+ void *arg1, *arg3;
+ int arg2;
+ u_int arg4;
+{
+ return -1;
+}
+
+
+/* ------------------------------------------------------------------------ */
+/* Function: ipf_dstlist_flush */
+/* Returns: int - number of objects deleted */
+/* Parameters: softc(I) - pointer to soft context main structure */
+/* arg(I) - pointer to local context to use */
+/* fop(I) - pointer to lookup flush operation data */
+/* */
+/* Flush all of the destination tables that match the data passed in with */
+/* the iplookupflush_t. There are two ways to match objects: the device for */
+/* which they are to be used with and their name. */
+/* ------------------------------------------------------------------------ */
+static size_t
+ipf_dstlist_flush(softc, arg, fop)
+ ipf_main_softc_t *softc;
+ void *arg;
+ iplookupflush_t *fop;
+{
+ ipf_dstl_softc_t *softd = arg;
+ ippool_dst_t *node, *next;
+ int n, i;
+
+ for (n = 0, i = -1; i <= IPL_LOGMAX; i++) {
+ if (fop->iplf_unit != IPLT_ALL && fop->iplf_unit != i)
+ continue;
+ for (node = softd->dstlist[i + 1]; node != NULL; node = next) {
+ next = node->ipld_next;
+
+ if ((*fop->iplf_name != '\0') &&
+ strncmp(fop->iplf_name, node->ipld_name,
+ FR_GROUPLEN))
+ continue;
+
+ ipf_dstlist_table_remove(softc, softd, node);
+ n++;
+ }
+ }
+ return n;
+}
+
+
+/* ------------------------------------------------------------------------ */
+/* Function: ipf_dstlist_iter_deref */
+/* Returns: int - 0 = success, else error */
+/* Parameters: softc(I) - pointer to soft context main structure */
+/* arg(I) - pointer to local context to use */
+/* otype(I) - type of data structure to iterate through */
+/* unit(I) - device we are working with */
+/* data(I) - address of object in kernel space */
+/* */
+/* This function is called when the iteration token is being free'd and is */
+/* responsible for dropping the reference count of the structure it points */
+/* to. */
+/* ------------------------------------------------------------------------ */
+static int
+ipf_dstlist_iter_deref(softc, arg, otype, unit, data)
+ ipf_main_softc_t *softc;
+ void *arg;
+ int otype, unit;
+ void *data;
+{
+ if (data == NULL) {
+ IPFERROR(120001);
+ return EINVAL;
+ }
+
+ if (unit < -1 || unit > IPL_LOGMAX) {
+ IPFERROR(120002);
+ return EINVAL;
+ }
+
+ switch (otype)
+ {
+ case IPFLOOKUPITER_LIST :
+ ipf_dstlist_table_deref(softc, arg, (ippool_dst_t *)data);
+ break;
+
+ case IPFLOOKUPITER_NODE :
+ ipf_dstlist_node_deref(arg, (ipf_dstnode_t *)data);
+ break;
+ }
+
+ return 0;
+}
+
+
+/* ------------------------------------------------------------------------ */
+/* Function: ipf_dstlist_iter_next */
+/* Returns: int - 0 = success, else error */
+/* Parameters: softc(I) - pointer to soft context main structure */
+/* arg(I) - pointer to local context to use */
+/* op(I) - pointer to lookup operation data */
+/* uid(I) - uid of process doing the ioctl */
+/* */
+/* This function is responsible for either selecting the next destination */
+/* list or node on a destination list to be returned as a user process */
+/* iterates through the list of destination lists or nodes. */
+/* ------------------------------------------------------------------------ */
+static int
+ipf_dstlist_iter_next(softc, arg, token, iter)
+ ipf_main_softc_t *softc;
+ void *arg;
+ ipftoken_t *token;
+ ipflookupiter_t *iter;
+{
+ ipf_dstnode_t zn, *nextnode = NULL, *node = NULL;
+ ippool_dst_t zero, *next = NULL, *dsttab = NULL;
+ ipf_dstl_softc_t *softd = arg;
+ int err = 0;
+ void *hint;
+
+ switch (iter->ili_otype)
+ {
+ case IPFLOOKUPITER_LIST :
+ dsttab = token->ipt_data;
+ if (dsttab == NULL) {
+ next = softd->dstlist[(int)iter->ili_unit + 1];
+ } else {
+ next = dsttab->ipld_next;
+ }
+
+ if (next != NULL) {
+ ATOMIC_INC32(next->ipld_ref);
+ token->ipt_data = next;
+ hint = next->ipld_next;
+ } else {
+ bzero((char *)&zero, sizeof(zero));
+ next = &zero;
+ token->ipt_data = NULL;
+ hint = NULL;
+ }
+ break;
+
+ case IPFLOOKUPITER_NODE :
+ node = token->ipt_data;
+ if (node == NULL) {
+ dsttab = ipf_dstlist_table_find(arg, iter->ili_unit,
+ iter->ili_name);
+ if (dsttab == NULL) {
+ IPFERROR(120004);
+ err = ESRCH;
+ nextnode = NULL;
+ } else {
+ if (dsttab->ipld_dests == NULL)
+ nextnode = NULL;
+ else
+ nextnode = *dsttab->ipld_dests;
+ dsttab = NULL;
+ }
+ } else {
+ nextnode = node->ipfd_next;
+ }
+
+ if (nextnode != NULL) {
+ MUTEX_ENTER(&nextnode->ipfd_lock);
+ nextnode->ipfd_ref++;
+ MUTEX_EXIT(&nextnode->ipfd_lock);
+ token->ipt_data = nextnode;
+ hint = nextnode->ipfd_next;
+ } else {
+ bzero((char *)&zn, sizeof(zn));
+ nextnode = &zn;
+ token->ipt_data = NULL;
+ hint = NULL;
+ }
+ break;
+ default :
+ IPFERROR(120003);
+ err = EINVAL;
+ break;
+ }
+
+ if (err != 0)
+ return err;
+
+ switch (iter->ili_otype)
+ {
+ case IPFLOOKUPITER_LIST :
+ if (dsttab != NULL)
+ ipf_dstlist_table_deref(softc, arg, dsttab);
+ err = COPYOUT(next, iter->ili_data, sizeof(*next));
+ if (err != 0) {
+ IPFERROR(120005);
+ err = EFAULT;
+ }
+ break;
+
+ case IPFLOOKUPITER_NODE :
+ if (node != NULL)
+ ipf_dstlist_node_deref(arg, node);
+ err = COPYOUT(nextnode, iter->ili_data, sizeof(*nextnode));
+ if (err != 0) {
+ IPFERROR(120006);
+ err = EFAULT;
+ }
+ break;
+ }
+
+ if (hint == NULL)
+ ipf_token_mark_complete(token);
+
+ return err;
+}
+
+
+/* ------------------------------------------------------------------------ */
+/* Function: ipf_dstlist_node_add */
+/* Returns: int - 0 = success, else error */
+/* Parameters: softc(I) - pointer to soft context main structure */
+/* arg(I) - pointer to local context to use */
+/* op(I) - pointer to lookup operation data */
+/* uid(I) - uid of process doing the ioctl */
+/* Locks: WRITE(ipf_poolrw) */
+/* */
+/* Add a new node to a destination list. To do this, we only copy in the */
+/* frdest_t structure because that contains the only data required from the */
+/* application to create a new node. The frdest_t doesn't contain the name */
+/* itself. When loading filter rules, fd_name is a 'pointer' to the name. */
+/* In this case, the 'pointer' does not work, instead it is the length of */
+/* the name and the name is immediately following the frdest_t structure. */
+/* fd_name must include the trailing \0, so it should be strlen(str) + 1. */
+/* For simple sanity checking, an upper bound on the size of fd_name is */
+/* imposed - 128. */
+/* ------------------------------------------------------------------------ */
+static int
+ipf_dstlist_node_add(softc, arg, op, uid)
+ ipf_main_softc_t *softc;
+ void *arg;
+ iplookupop_t *op;
+ int uid;
+{
+ ipf_dstl_softc_t *softd = arg;
+ ipf_dstnode_t *node, **nodes;
+ ippool_dst_t *d;
+ frdest_t dest;
+ int err;
+
+ if (op->iplo_size < sizeof(frdest_t)) {
+ IPFERROR(120007);
+ return EINVAL;
+ }
+
+ err = COPYIN(op->iplo_struct, &dest, sizeof(dest));
+ if (err != 0) {
+ IPFERROR(120009);
+ return EFAULT;
+ }
+
+ d = ipf_dstlist_table_find(arg, op->iplo_unit, op->iplo_name);
+ if (d == NULL) {
+ IPFERROR(120010);
+ return ESRCH;
+ }
+
+ switch (dest.fd_addr.adf_family)
+ {
+ case AF_INET :
+ case AF_INET6 :
+ break;
+ default :
+ IPFERROR(120019);
+ return EINVAL;
+ }
+
+ if (dest.fd_name < -1 || dest.fd_name > 128) {
+ IPFERROR(120018);
+ return EINVAL;
+ }
+
+ KMALLOCS(node, ipf_dstnode_t *, sizeof(*node) + dest.fd_name);
+ if (node == NULL) {
+ softd->stats.ipls_nomem++;
+ IPFERROR(120008);
+ return ENOMEM;
+ }
+ bzero((char *)node, sizeof(*node) + dest.fd_name);
+
+ bcopy(&dest, &node->ipfd_dest, sizeof(dest));
+ node->ipfd_size = sizeof(*node) + dest.fd_name;
+
+ if (dest.fd_name > 0) {
+ /*
+ * fd_name starts out as the length of the string to copy
+ * in (including \0) and ends up being the offset from
+ * fd_names (0).
+ */
+ err = COPYIN((char *)op->iplo_struct + sizeof(dest),
+ node->ipfd_names, dest.fd_name);
+ if (err != 0) {
+ IPFERROR(120017);
+ KFREES(node, node->ipfd_size);
+ return EFAULT;
+ }
+ node->ipfd_dest.fd_name = 0;
+ } else {
+ node->ipfd_dest.fd_name = -1;
+ }
+
+ if (d->ipld_nodes == d->ipld_maxnodes) {
+ KMALLOCS(nodes, ipf_dstnode_t **,
+ sizeof(*nodes) * (d->ipld_maxnodes + 1));
+ if (nodes == NULL) {
+ softd->stats.ipls_nomem++;
+ IPFERROR(120022);
+ KFREES(node, node->ipfd_size);
+ return ENOMEM;
+ }
+ if (d->ipld_dests != NULL) {
+ bcopy(d->ipld_dests, nodes,
+ sizeof(*nodes) * d->ipld_maxnodes);
+ KFREES(d->ipld_dests, sizeof(*nodes) * d->ipld_nodes);
+ nodes[0]->ipfd_pnext = nodes;
+ }
+ d->ipld_dests = nodes;
+ d->ipld_maxnodes++;
+ }
+ d->ipld_dests[d->ipld_nodes] = node;
+ d->ipld_nodes++;
+
+ if (d->ipld_nodes == 1) {
+ node->ipfd_pnext = d->ipld_dests;
+ } else if (d->ipld_nodes > 1) {
+ node->ipfd_pnext = &d->ipld_dests[d->ipld_nodes - 2]->ipfd_next;
+ }
+ *node->ipfd_pnext = node;
+
+ MUTEX_INIT(&node->ipfd_lock, "ipf dst node lock");
+ node->ipfd_uid = uid;
+ node->ipfd_ref = 1;
+ if (node->ipfd_dest.fd_name == 0)
+ (void) ipf_resolvedest(softc, node->ipfd_names,
+ &node->ipfd_dest, AF_INET);
+#ifdef USE_INET6
+ if (node->ipfd_dest.fd_name == 0 &&
+ node->ipfd_dest.fd_ptr == (void *)-1)
+ (void) ipf_resolvedest(softc, node->ipfd_names,
+ &node->ipfd_dest, AF_INET6);
+#endif
+
+ softd->stats.ipls_numnodes++;
+
+ return 0;
+}
+
+
+/* ------------------------------------------------------------------------ */
+/* Function: ipf_dstlist_node_deref */
+/* Returns: int - 0 = success, else error */
+/* Parameters: arg(I) - pointer to local context to use */
+/* node(I) - pointer to destionation node to free */
+/* */
+/* Dereference the use count by one. If it drops to zero then we can assume */
+/* that it has been removed from any lists/tables and is ripe for freeing. */
+/* The pointer to context is required for the purpose of maintaining */
+/* statistics. */
+/* ------------------------------------------------------------------------ */
+static int
+ipf_dstlist_node_deref(arg, node)
+ void *arg;
+ ipf_dstnode_t *node;
+{
+ ipf_dstl_softc_t *softd = arg;
+ int ref;
+
+ MUTEX_ENTER(&node->ipfd_lock);
+ ref = --node->ipfd_ref;
+ MUTEX_EXIT(&node->ipfd_lock);
+
+ if (ref > 0)
+ return 0;
+
+ if ((node->ipfd_flags & IPDST_DELETE) != 0)
+ softd->stats.ipls_numderefnodes--;
+ MUTEX_DESTROY(&node->ipfd_lock);
+ KFREES(node, node->ipfd_size);
+ softd->stats.ipls_numnodes--;
+
+ return 0;
+}
+
+
+/* ------------------------------------------------------------------------ */
+/* Function: ipf_dstlist_node_del */
+/* Returns: int - 0 = success, else error */
+/* Parameters: softc(I) - pointer to soft context main structure */
+/* arg(I) - pointer to local context to use */
+/* op(I) - pointer to lookup operation data */
+/* uid(I) - uid of process doing the ioctl */
+/* */
+/* Look for a matching destination node on the named table and free it if */
+/* found. Because the name embedded in the frdest_t is variable in length, */
+/* it is necessary to allocate some memory locally, to complete this op. */
+/* ------------------------------------------------------------------------ */
+static int
+ipf_dstlist_node_del(softc, arg, op, uid)
+ ipf_main_softc_t *softc;
+ void *arg;
+ iplookupop_t *op;
+ int uid;
+{
+ ipf_dstl_softc_t *softd = arg;
+ ipf_dstnode_t *node;
+ frdest_t frd, *temp;
+ ippool_dst_t *d;
+ size_t size;
+ int err;
+
+ d = ipf_dstlist_table_find(arg, op->iplo_unit, op->iplo_name);
+ if (d == NULL) {
+ IPFERROR(120012);
+ return ESRCH;
+ }
+
+ err = COPYIN(op->iplo_struct, &frd, sizeof(frd));
+ if (err != 0) {
+ IPFERROR(120011);
+ return EFAULT;
+ }
+
+ size = sizeof(*temp) + frd.fd_name;
+ KMALLOCS(temp, frdest_t *, size);
+ if (temp == NULL) {
+ softd->stats.ipls_nomem++;
+ IPFERROR(120026);
+ return ENOMEM;
+ }
+
+ err = COPYIN(op->iplo_struct, temp, size);
+ if (err != 0) {
+ IPFERROR(120027);
+ return EFAULT;
+ }
+
+ MUTEX_ENTER(&d->ipld_lock);
+ for (node = *d->ipld_dests; node != NULL; node = node->ipfd_next) {
+ if ((uid != 0) && (node->ipfd_uid != uid))
+ continue;
+ if (node->ipfd_size != size)
+ continue;
+ if (!bcmp(&node->ipfd_dest.fd_ip6, &frd.fd_ip6,
+ size - offsetof(frdest_t, fd_ip6))) {
+ ipf_dstlist_node_free(softd, d, node);
+ MUTEX_EXIT(&d->ipld_lock);
+ KFREES(temp, size);
+ return 0;
+ }
+ }
+ MUTEX_EXIT(&d->ipld_lock);
+ KFREES(temp, size);
+
+ return ESRCH;
+}
+
+
+/* ------------------------------------------------------------------------ */
+/* Function: ipf_dstlist_node_free */
+/* Returns: Nil */
+/* Parameters: softd(I) - pointer to the destination list context */
+/* d(I) - pointer to destination list */
+/* node(I) - pointer to node to free */
+/* Locks: MUTEX(ipld_lock) or WRITE(ipf_poolrw) */
+/* */
+/* Free the destination node by first removing it from any lists and then */
+/* checking if this was the last reference held to the object. While the */
+/* array of pointers to nodes is compacted, its size isn't reduced (by way */
+/* of allocating a new smaller one and copying) because the belief is that */
+/* it is likely the array will again reach that size. */
+/* ------------------------------------------------------------------------ */
+static void
+ipf_dstlist_node_free(softd, d, node)
+ ipf_dstl_softc_t *softd;
+ ippool_dst_t *d;
+ ipf_dstnode_t *node;
+{
+ int i;
+
+ /*
+ * Compact the array of pointers to nodes.
+ */
+ for (i = 0; i < d->ipld_nodes; i++)
+ if (d->ipld_dests[i] == node)
+ break;
+ if (d->ipld_nodes - i > 1) {
+ bcopy(&d->ipld_dests[i + 1], &d->ipld_dests[i],
+ sizeof(*d->ipld_dests) * (d->ipld_nodes - i - 1));
+ }
+ d->ipld_nodes--;
+
+ if (node->ipfd_pnext != NULL)
+ *node->ipfd_pnext = node->ipfd_next;
+ if (node->ipfd_next != NULL)
+ node->ipfd_next->ipfd_pnext = node->ipfd_pnext;
+ node->ipfd_pnext = NULL;
+ node->ipfd_next = NULL;
+
+ if ((node->ipfd_flags & IPDST_DELETE) == 0) {
+ softd->stats.ipls_numderefnodes++;
+ node->ipfd_flags |= IPDST_DELETE;
+ }
+
+ ipf_dstlist_node_deref(softd, node);
+}
+
+
+/* ------------------------------------------------------------------------ */
+/* Function: ipf_dstlist_stats_get */
+/* Returns: int - 0 = success, else error */
+/* Parameters: softc(I) - pointer to soft context main structure */
+/* arg(I) - pointer to local context to use */
+/* op(I) - pointer to lookup operation data */
+/* */
+/* Return the current statistics for destination lists. This may be for all */
+/* of them or just information pertaining to a particular table. */
+/* ------------------------------------------------------------------------ */
+/*ARGSUSED*/
+static int
+ipf_dstlist_stats_get(softc, arg, op)
+ ipf_main_softc_t *softc;
+ void *arg;
+ iplookupop_t *op;
+{
+ ipf_dstl_softc_t *softd = arg;
+ ipf_dstl_stat_t stats;
+ int unit, i, err = 0;
+
+ if (op->iplo_size != sizeof(ipf_dstl_stat_t)) {
+ IPFERROR(120023);
+ return EINVAL;
+ }
+
+ stats = softd->stats;
+ unit = op->iplo_unit;
+ if (unit == IPL_LOGALL) {
+ for (i = 0; i <= IPL_LOGMAX; i++)
+ stats.ipls_list[i] = softd->dstlist[i];
+ } else if (unit >= 0 && unit <= IPL_LOGMAX) {
+ void *ptr;
+
+ if (op->iplo_name[0] != '\0')
+ ptr = ipf_dstlist_table_find(softd, unit,
+ op->iplo_name);
+ else
+ ptr = softd->dstlist[unit + 1];
+ stats.ipls_list[unit] = ptr;
+ } else {
+ IPFERROR(120024);
+ err = EINVAL;
+ }
+
+ if (err == 0) {
+ err = COPYOUT(&stats, op->iplo_struct, sizeof(stats));
+ if (err != 0) {
+ IPFERROR(120025);
+ return EFAULT;
+ }
+ }
+ return 0;
+}
+
+
+/* ------------------------------------------------------------------------ */
+/* Function: ipf_dstlist_table_add */
+/* Returns: int - 0 = success, else error */
+/* Parameters: softc(I) - pointer to soft context main structure */
+/* arg(I) - pointer to local context to use */
+/* op(I) - pointer to lookup operation data */
+/* */
+/* Add a new destination table to the list of those available for the given */
+/* device. Because we seldom operate on these objects (find/add/delete), */
+/* they are just kept in a simple linked list. */
+/* ------------------------------------------------------------------------ */
+static int
+ipf_dstlist_table_add(softc, arg, op)
+ ipf_main_softc_t *softc;
+ void *arg;
+ iplookupop_t *op;
+{
+ ipf_dstl_softc_t *softd = arg;
+ ippool_dst_t user, *d, *new;
+ int unit, err;
+
+ d = ipf_dstlist_table_find(arg, op->iplo_unit, op->iplo_name);
+ if (d != NULL) {
+ IPFERROR(120013);
+ return EEXIST;
+ }
+
+ err = COPYIN(op->iplo_struct, &user, sizeof(user));
+ if (err != 0) {
+ IPFERROR(120021);
+ return EFAULT;
+ }
+
+ KMALLOC(new, ippool_dst_t *);
+ if (new == NULL) {
+ softd->stats.ipls_nomem++;
+ IPFERROR(120014);
+ return ENOMEM;
+ }
+ bzero((char *)new, sizeof(*new));
+
+ MUTEX_INIT(&new->ipld_lock, "ipf dst table lock");
+
+ strncpy(new->ipld_name, op->iplo_name, FR_GROUPLEN);
+ unit = op->iplo_unit;
+ new->ipld_unit = unit;
+ new->ipld_policy = user.ipld_policy;
+ new->ipld_seed = ipf_random();
+ new->ipld_ref = 1;
+
+ new->ipld_pnext = softd->tails[unit + 1];
+ *softd->tails[unit + 1] = new;
+ softd->tails[unit + 1] = &new->ipld_next;
+ softd->stats.ipls_numlists++;
+
+ return 0;
+}
+
+
+/* ------------------------------------------------------------------------ */
+/* Function: ipf_dstlist_table_del */
+/* Returns: int - 0 = success, else error */
+/* Parameters: softc(I) - pointer to soft context main structure */
+/* arg(I) - pointer to local context to use */
+/* op(I) - pointer to lookup operation data */
+/* */
+/* Find a named destinstion list table and delete it. If there are other */
+/* references to it, the caller isn't told. */
+/* ------------------------------------------------------------------------ */
+static int
+ipf_dstlist_table_del(softc, arg, op)
+ ipf_main_softc_t *softc;
+ void *arg;
+ iplookupop_t *op;
+{
+ ippool_dst_t *d;
+
+ d = ipf_dstlist_table_find(arg, op->iplo_unit, op->iplo_name);
+ if (d == NULL) {
+ IPFERROR(120015);
+ return ESRCH;
+ }
+
+ if (d->ipld_dests != NULL) {
+ IPFERROR(120016);
+ return EBUSY;
+ }
+
+ ipf_dstlist_table_remove(softc, arg, d);
+
+ return 0;
+}
+
+
+/* ------------------------------------------------------------------------ */
+/* Function: ipf_dstlist_table_remove */
+/* Returns: Nil */
+/* Parameters: softc(I) - pointer to soft context main structure */
+/* softd(I) - pointer to the destination list context */
+/* d(I) - pointer to destination list */
+/* */
+/* Remove a given destination list from existance. While the IPDST_DELETE */
+/* flag is set every time we call this function and the reference count is */
+/* non-zero, the "numdereflists" counter is always incremented because the */
+/* decision about whether it will be freed or not is not made here. This */
+/* means that the only action the code can take here is to treat it as if */
+/* it will become a detached. */
+/* ------------------------------------------------------------------------ */
+static void
+ipf_dstlist_table_remove(softc, softd, d)
+ ipf_main_softc_t *softc;
+ ipf_dstl_softc_t *softd;
+ ippool_dst_t *d;
+{
+
+ if (softd->tails[d->ipld_unit + 1] == &d->ipld_next)
+ softd->tails[d->ipld_unit + 1] = d->ipld_pnext;
+
+ if (d->ipld_pnext != NULL)
+ *d->ipld_pnext = d->ipld_next;
+ if (d->ipld_next != NULL)
+ d->ipld_next->ipld_pnext = d->ipld_pnext;
+ d->ipld_pnext = NULL;
+ d->ipld_next = NULL;
+
+ ipf_dstlist_table_clearnodes(softd, d);
+
+ softd->stats.ipls_numdereflists++;
+ d->ipld_flags |= IPDST_DELETE;
+
+ ipf_dstlist_table_deref(softc, softd, d);
+}
+
+
+/* ------------------------------------------------------------------------ */
+/* Function: ipf_dstlist_table_free */
+/* Returns: Nil */
+/* Parameters: softd(I) - pointer to the destination list context */
+/* d(I) - pointer to destination list */
+/* */
+/* Free up a destination list data structure and any other memory that was */
+/* directly allocated as part of creating it. Individual destination list */
+/* nodes are not freed. It is assumed the caller will have already emptied */
+/* the destination list. */
+/* ------------------------------------------------------------------------ */
+static void
+ipf_dstlist_table_free(softd, d)
+ ipf_dstl_softc_t *softd;
+ ippool_dst_t *d;
+{
+ MUTEX_DESTROY(&d->ipld_lock);
+
+ if ((d->ipld_flags & IPDST_DELETE) != 0)
+ softd->stats.ipls_numdereflists--;
+ softd->stats.ipls_numlists--;
+
+ if (d->ipld_dests != NULL) {
+ KFREES(d->ipld_dests,
+ d->ipld_maxnodes * sizeof(*d->ipld_dests));
+ }
+
+ KFREE(d);
+}
+
+
+/* ------------------------------------------------------------------------ */
+/* Function: ipf_dstlist_table_deref */
+/* Returns: int - 0 = success, else error */
+/* Parameters: softc(I) - pointer to soft context main structure */
+/* arg(I) - pointer to local context to use */
+/* op(I) - pointer to lookup operation data */
+/* */
+/* Drops the reference count on a destination list table object and free's */
+/* it if 0 has been reached. */
+/* ------------------------------------------------------------------------ */
+static int
+ipf_dstlist_table_deref(softc, arg, table)
+ ipf_main_softc_t *softc;
+ void *arg;
+ void *table;
+{
+ ippool_dst_t *d = table;
+
+ d->ipld_ref--;
+ if (d->ipld_ref > 0)
+ return d->ipld_ref;
+
+ ipf_dstlist_table_free(arg, d);
+
+ return 0;
+}
+
+
+/* ------------------------------------------------------------------------ */
+/* Function: ipf_dstlist_table_clearnodes */
+/* Returns: Nil */
+/* Parameters: softd(I) - pointer to the destination list context */
+/* dst(I) - pointer to destination list */
+/* */
+/* Free all of the destination nodes attached to the given table. */
+/* ------------------------------------------------------------------------ */
+static void
+ipf_dstlist_table_clearnodes(softd, dst)
+ ipf_dstl_softc_t *softd;
+ ippool_dst_t *dst;
+{
+ ipf_dstnode_t *node;
+
+ if (dst->ipld_dests == NULL)
+ return;
+
+ while ((node = *dst->ipld_dests) != NULL) {
+ ipf_dstlist_node_free(softd, dst, node);
+ }
+}
+
+
+/* ------------------------------------------------------------------------ */
+/* Function: ipf_dstlist_table_find */
+/* Returns: int - 0 = success, else error */
+/* Parameters: arg(I) - pointer to local context to use */
+/* unit(I) - device we are working with */
+/* name(I) - destination table name to find */
+/* */
+/* Return a pointer to a destination table that matches the unit+name that */
+/* is passed in. */
+/* ------------------------------------------------------------------------ */
+static void *
+ipf_dstlist_table_find(arg, unit, name)
+ void *arg;
+ int unit;
+ char *name;
+{
+ ipf_dstl_softc_t *softd = arg;
+ ippool_dst_t *d;
+
+ for (d = softd->dstlist[unit + 1]; d != NULL; d = d->ipld_next) {
+ if ((d->ipld_unit == unit) &&
+ !strncmp(d->ipld_name, name, FR_GROUPLEN)) {
+ return d;
+ }
+ }
+
+ return NULL;
+}
+
+
+/* ------------------------------------------------------------------------ */
+/* Function: ipf_dstlist_select_ref */
+/* Returns: void * - NULL = failure, else pointer to table */
+/* Parameters: arg(I) - pointer to local context to use */
+/* unit(I) - device we are working with */
+/* name(I) - destination table name to find */
+/* */
+/* Attempt to find a destination table that matches the name passed in and */
+/* if successful, bump up the reference count on it because we intend to */
+/* store the pointer to it somewhere else. */
+/* ------------------------------------------------------------------------ */
+static void *
+ipf_dstlist_select_ref(arg, unit, name)
+ void *arg;
+ int unit;
+ char *name;
+{
+ ippool_dst_t *d;
+
+ d = ipf_dstlist_table_find(arg, unit, name);
+ if (d != NULL) {
+ MUTEX_ENTER(&d->ipld_lock);
+ d->ipld_ref++;
+ MUTEX_EXIT(&d->ipld_lock);
+ }
+ return d;
+}
+
+
+/* ------------------------------------------------------------------------ */
+/* Function: ipf_dstlist_select */
+/* Returns: void * - NULL = failure, else pointer to table */
+/* Parameters: fin(I) - pointer to packet information */
+/* d(I) - pointer to destination list */
+/* */
+/* Find the next node in the destination list to be used according to the */
+/* defined policy. Of these, "connection" is the most expensive policy to */
+/* implement as it always looks for the node with the least number of */
+/* connections associated with it. */
+/* */
+/* The hashes exclude the port numbers so that all protocols map to the */
+/* same destination. Otherwise, someone doing a ping would target a */
+/* different server than their TCP connection, etc. MD-5 is used to */
+/* transform the addressese into something random that the other end could */
+/* not easily guess and use in an attack. ipld_seed introduces an unknown */
+/* into the hash calculation to increase the difficult of an attacker */
+/* guessing the bucket. */
+/* */
+/* One final comment: mixing different address families in a single pool */
+/* will currently result in failures as the address family of the node is */
+/* only matched up with that in the packet as the last step. While this can */
+/* be coded around for the weighted connection and round-robin models, it */
+/* cannot be supported for the hash/random models as they do not search and */
+/* nor is the algorithm conducive to searching. */
+/* ------------------------------------------------------------------------ */
+static ipf_dstnode_t *
+ipf_dstlist_select(fin, d)
+ fr_info_t *fin;
+ ippool_dst_t *d;
+{
+ ipf_dstnode_t *node, *sel;
+ int connects;
+ u_32_t hash[4];
+ MD5_CTX ctx;
+ int family;
+ int x;
+
+ if (d->ipld_dests == NULL || *d->ipld_dests == NULL)
+ return NULL;
+
+ family = fin->fin_family;
+
+ MUTEX_ENTER(&d->ipld_lock);
+
+ switch (d->ipld_policy)
+ {
+ case IPLDP_ROUNDROBIN:
+ sel = d->ipld_selected;
+ if (sel == NULL) {
+ sel = *d->ipld_dests;
+ } else {
+ sel = sel->ipfd_next;
+ if (sel == NULL)
+ sel = *d->ipld_dests;
+ }
+ break;
+
+ case IPLDP_CONNECTION:
+ if (d->ipld_selected == NULL) {
+ sel = *d->ipld_dests;
+ break;
+ }
+
+ sel = d->ipld_selected;
+ connects = 0x7fffffff;
+ node = sel->ipfd_next;
+ if (node == NULL)
+ node = *d->ipld_dests;
+ while (node != d->ipld_selected) {
+ if (node->ipfd_states == 0) {
+ sel = node;
+ break;
+ }
+ if (node->ipfd_states < connects) {
+ sel = node;
+ connects = node->ipfd_states;
+ }
+ node = node->ipfd_next;
+ if (node == NULL)
+ node = *d->ipld_dests;
+ }
+ break;
+
+ case IPLDP_RANDOM :
+ x = ipf_random() % d->ipld_nodes;
+ sel = d->ipld_dests[x];
+ break;
+
+ case IPLDP_HASHED :
+ MD5Init(&ctx);
+ MD5Update(&ctx, (u_char *)&d->ipld_seed, sizeof(d->ipld_seed));
+ MD5Update(&ctx, (u_char *)&fin->fin_src6,
+ sizeof(fin->fin_src6));
+ MD5Update(&ctx, (u_char *)&fin->fin_dst6,
+ sizeof(fin->fin_dst6));
+ MD5Final((u_char *)hash, &ctx);
+ x = hash[0] % d->ipld_nodes;
+ sel = d->ipld_dests[x];
+ break;
+
+ case IPLDP_SRCHASH :
+ MD5Init(&ctx);
+ MD5Update(&ctx, (u_char *)&d->ipld_seed, sizeof(d->ipld_seed));
+ MD5Update(&ctx, (u_char *)&fin->fin_src6,
+ sizeof(fin->fin_src6));
+ MD5Final((u_char *)hash, &ctx);
+ x = hash[0] % d->ipld_nodes;
+ sel = d->ipld_dests[x];
+ break;
+
+ case IPLDP_DSTHASH :
+ MD5Init(&ctx);
+ MD5Update(&ctx, (u_char *)&d->ipld_seed, sizeof(d->ipld_seed));
+ MD5Update(&ctx, (u_char *)&fin->fin_dst6,
+ sizeof(fin->fin_dst6));
+ MD5Final((u_char *)hash, &ctx);
+ x = hash[0] % d->ipld_nodes;
+ sel = d->ipld_dests[x];
+ break;
+
+ default :
+ sel = NULL;
+ break;
+ }
+
+ if (sel->ipfd_dest.fd_addr.adf_family != family)
+ sel = NULL;
+ d->ipld_selected = sel;
+
+ MUTEX_EXIT(&d->ipld_lock);
+
+ return sel;
+}
+
+
+/* ------------------------------------------------------------------------ */
+/* Function: ipf_dstlist_select_node */
+/* Returns: int - -1 == failure, 0 == success */
+/* Parameters: fin(I) - pointer to packet information */
+/* group(I) - destination pool to search */
+/* addr(I) - pointer to store selected address */
+/* pfdp(O) - pointer to storage for selected destination node */
+/* */
+/* This function is only responsible for obtaining the next IP address for */
+/* use and storing it in the caller's address space (addr). "addr" is only */
+/* used for storage if pfdp is NULL. No permanent reference is currently */
+/* kept on the node. */
+/* ------------------------------------------------------------------------ */
+int
+ipf_dstlist_select_node(fin, group, addr, pfdp)
+ fr_info_t *fin;
+ void *group;
+ u_32_t *addr;
+ frdest_t *pfdp;
+{
+#ifdef USE_MUTEXES
+ ipf_main_softc_t *softc = fin->fin_main_soft;
+#endif
+ ippool_dst_t *d = group;
+ ipf_dstnode_t *node;
+ frdest_t *fdp;
+
+ READ_ENTER(&softc->ipf_poolrw);
+
+ node = ipf_dstlist_select(fin, d);
+ if (node == NULL) {
+ RWLOCK_EXIT(&softc->ipf_poolrw);
+ return -1;
+ }
+
+ if (pfdp != NULL) {
+ bcopy(&node->ipfd_dest, pfdp, sizeof(*pfdp));
+ } else {
+ if (fin->fin_family == AF_INET) {
+ addr[0] = node->ipfd_dest.fd_addr.adf_addr.i6[0];
+ } else if (fin->fin_family == AF_INET6) {
+ addr[0] = node->ipfd_dest.fd_addr.adf_addr.i6[0];
+ addr[1] = node->ipfd_dest.fd_addr.adf_addr.i6[1];
+ addr[2] = node->ipfd_dest.fd_addr.adf_addr.i6[2];
+ addr[3] = node->ipfd_dest.fd_addr.adf_addr.i6[3];
+ }
+ }
+
+ fdp = &node->ipfd_dest;
+ if (fdp->fd_ptr == NULL)
+ fdp->fd_ptr = fin->fin_ifp;
+
+ MUTEX_ENTER(&node->ipfd_lock);
+ node->ipfd_states++;
+ MUTEX_EXIT(&node->ipfd_lock);
+
+ RWLOCK_EXIT(&softc->ipf_poolrw);
+
+ return 0;
+}
+
+
+/* ------------------------------------------------------------------------ */
+/* Function: ipf_dstlist_expire */
+/* Returns: Nil */
+/* Parameters: softc(I) - pointer to soft context main structure */
+/* arg(I) - pointer to local context to use */
+/* */
+/* There are currently no objects to expire in destination lists. */
+/* ------------------------------------------------------------------------ */
+static void
+ipf_dstlist_expire(softc, arg)
+ ipf_main_softc_t *softc;
+ void *arg;
+{
+ return;
+}
+
+
+/* ------------------------------------------------------------------------ */
+/* Function: ipf_dstlist_sync */
+/* Returns: Nil */
+/* Parameters: softc(I) - pointer to soft context main structure */
+/* arg(I) - pointer to local context to use */
+/* */
+/* When a network interface appears or disappears, we need to revalidate */
+/* all of the network interface names that have been configured as a target */
+/* in a destination list. */
+/* ------------------------------------------------------------------------ */
+void
+ipf_dstlist_sync(softc, arg)
+ ipf_main_softc_t *softc;
+ void *arg;
+{
+ ipf_dstl_softc_t *softd = arg;
+ ipf_dstnode_t *node;
+ ippool_dst_t *list;
+ int i;
+ int j;
+
+ for (i = 0; i < IPL_LOGMAX; i++) {
+ for (list = softd->dstlist[i]; list != NULL;
+ list = list->ipld_next) {
+ for (j = 0; j < list->ipld_maxnodes; j++) {
+ node = list->ipld_dests[j];
+ if (node == NULL)
+ continue;
+ if (node->ipfd_dest.fd_name == -1)
+ continue;
+ (void) ipf_resolvedest(softc,
+ node->ipfd_names,
+ &node->ipfd_dest,
+ AF_INET);
+ }
+ }
+ }
+}
diff --git a/netinet/ip_dstlist.h b/netinet/ip_dstlist.h
new file mode 100644
index 000000000000..e2885e5c47ad
--- /dev/null
+++ b/netinet/ip_dstlist.h
@@ -0,0 +1,68 @@
+/*
+ * Copyright (C) 2012 by Darren Reed.
+ *
+ * See the IPFILTER.LICENCE file for details on licencing.
+ *
+ * $Id: ip_dstlist.h,v 1.5.2.6 2012/07/22 08:04:23 darren_r Exp $
+ */
+
+#ifndef __IP_DSTLIST_H__
+#define __IP_DSTLIST_H__
+
+typedef struct ipf_dstnode {
+ struct ipf_dstnode *ipfd_next;
+ struct ipf_dstnode **ipfd_pnext;
+ ipfmutex_t ipfd_lock;
+ frdest_t ipfd_dest;
+ u_long ipfd_syncat;
+ int ipfd_flags;
+ int ipfd_size;
+ int ipfd_states;
+ int ipfd_ref;
+ int ipfd_uid;
+ char ipfd_names[1];
+} ipf_dstnode_t;
+
+typedef enum ippool_policy_e {
+ IPLDP_NONE = 0,
+ IPLDP_ROUNDROBIN,
+ IPLDP_CONNECTION,
+ IPLDP_RANDOM,
+ IPLDP_HASHED,
+ IPLDP_SRCHASH,
+ IPLDP_DSTHASH
+} ippool_policy_t;
+
+typedef struct ippool_dst {
+ struct ippool_dst *ipld_next;
+ struct ippool_dst **ipld_pnext;
+ ipfmutex_t ipld_lock;
+ int ipld_seed;
+ int ipld_unit;
+ int ipld_ref;
+ int ipld_flags;
+ int ipld_nodes;
+ int ipld_maxnodes;
+ ippool_policy_t ipld_policy;
+ ipf_dstnode_t **ipld_dests;
+ ipf_dstnode_t *ipld_selected;
+ char ipld_name[FR_GROUPLEN];
+} ippool_dst_t;
+
+#define IPDST_DELETE 0x01
+
+typedef struct dstlist_stat_s {
+ void *ipls_list[LOOKUP_POOL_SZ];
+ int ipls_numlists;
+ u_long ipls_nomem;
+ int ipls_numnodes;
+ int ipls_numdereflists;
+ int ipls_numderefnodes;
+} ipf_dstl_stat_t;
+
+extern ipf_lookup_t ipf_dstlist_backend;
+
+extern int ipf_dstlist_select_node __P((fr_info_t *, void *, u_32_t *,
+ frdest_t *));
+
+#endif /* __IP_DSTLIST_H__ */
diff --git a/netinet/ipf_rb.h b/netinet/ipf_rb.h
new file mode 100644
index 000000000000..3d7a59d99d36
--- /dev/null
+++ b/netinet/ipf_rb.h
@@ -0,0 +1,364 @@
+/*
+ * Copyright (C) 2012 by Darren Reed.
+ *
+ * See the IPFILTER.LICENCE file for details on licencing.
+ *
+ */
+typedef enum rbcolour_e {
+ C_BLACK = 0,
+ C_RED = 1
+} rbcolour_t;
+
+#define RBI_LINK(_n, _t) \
+ struct _n##_rb_link { \
+ struct _t *left; \
+ struct _t *right; \
+ struct _t *parent; \
+ rbcolour_t colour; \
+ }
+
+#define RBI_HEAD(_n, _t) \
+struct _n##_rb_head { \
+ struct _t top; \
+ int count; \
+ int (* compare)(struct _t *, struct _t *); \
+}
+
+#define RBI_CODE(_n, _t, _f, _cmp) \
+ \
+typedef void (*_n##_rb_walker_t)(_t *, void *); \
+ \
+_t * _n##_rb_delete(struct _n##_rb_head *, _t *); \
+void _n##_rb_init(struct _n##_rb_head *); \
+void _n##_rb_insert(struct _n##_rb_head *, _t *); \
+_t * _n##_rb_search(struct _n##_rb_head *, void *); \
+void _n##_rb_walktree(struct _n##_rb_head *, _n##_rb_walker_t, void *);\
+ \
+static void \
+rotate_left(struct _n##_rb_head *head, _t *node) \
+{ \
+ _t *parent, *tmp1, *tmp2; \
+ \
+ parent = node->_f.parent; \
+ tmp1 = node->_f.right; \
+ tmp2 = tmp1->_f.left; \
+ node->_f.right = tmp2; \
+ if (tmp2 != & _n##_rb_zero) \
+ tmp2->_f.parent = node; \
+ if (parent == & _n##_rb_zero) \
+ head->top._f.right = tmp1; \
+ else if (parent->_f.right == node) \
+ parent->_f.right = tmp1; \
+ else \
+ parent->_f.left = tmp1; \
+ tmp1->_f.left = node; \
+ tmp1->_f.parent = parent; \
+ node->_f.parent = tmp1; \
+} \
+ \
+static void \
+rotate_right(struct _n##_rb_head *head, _t *node) \
+{ \
+ _t *parent, *tmp1, *tmp2; \
+ \
+ parent = node->_f.parent; \
+ tmp1 = node->_f.left; \
+ tmp2 = tmp1->_f.right; \
+ node->_f.left = tmp2; \
+ if (tmp2 != &_n##_rb_zero) \
+ tmp2->_f.parent = node; \
+ if (parent == &_n##_rb_zero) \
+ head->top._f.right = tmp1; \
+ else if (parent->_f.right == node) \
+ parent->_f.right = tmp1; \
+ else \
+ parent->_f.left = tmp1; \
+ tmp1->_f.right = node; \
+ tmp1->_f.parent = parent; \
+ node->_f.parent = tmp1; \
+} \
+ \
+void \
+_n##_rb_insert(struct _n##_rb_head *head, _t *node) \
+{ \
+ _t *n, *parent, **p, *tmp1, *gparent; \
+ \
+ parent = &head->top; \
+ node->_f.left = &_n##_rb_zero; \
+ node->_f.right = &_n##_rb_zero; \
+ p = &head->top._f.right; \
+ while ((n = *p) != &_n##_rb_zero) { \
+ if (_cmp(node, n) < 0) \
+ p = &n->_f.left; \
+ else \
+ p = &n->_f.right; \
+ parent = n; \
+ } \
+ *p = node; \
+ node->_f.colour = C_RED; \
+ node->_f.parent = parent; \
+ \
+ while ((node != &_n##_rb_zero) && (parent->_f.colour == C_RED)){\
+ gparent = parent->_f.parent; \
+ if (parent == gparent->_f.left) { \
+ tmp1 = gparent->_f.right; \
+ if (tmp1->_f.colour == C_RED) { \
+ parent->_f.colour = C_BLACK; \
+ tmp1->_f.colour = C_BLACK; \
+ gparent->_f.colour = C_RED; \
+ node = gparent; \
+ } else { \
+ if (node == parent->_f.right) { \
+ node = parent; \
+ rotate_left(head, node); \
+ parent = node->_f.parent; \
+ } \
+ parent->_f.colour = C_BLACK; \
+ gparent->_f.colour = C_RED; \
+ rotate_right(head, gparent); \
+ } \
+ } else { \
+ tmp1 = gparent->_f.left; \
+ if (tmp1->_f.colour == C_RED) { \
+ parent->_f.colour = C_BLACK; \
+ tmp1->_f.colour = C_BLACK; \
+ gparent->_f.colour = C_RED; \
+ node = gparent; \
+ } else { \
+ if (node == parent->_f.left) { \
+ node = parent; \
+ rotate_right(head, node); \
+ parent = node->_f.parent; \
+ } \
+ parent->_f.colour = C_BLACK; \
+ gparent->_f.colour = C_RED; \
+ rotate_left(head, parent->_f.parent); \
+ } \
+ } \
+ parent = node->_f.parent; \
+ } \
+ head->top._f.right->_f.colour = C_BLACK; \
+ head->count++; \
+} \
+ \
+static void \
+deleteblack(struct _n##_rb_head *head, _t *parent, _t *node) \
+{ \
+ _t *tmp; \
+ \
+ while ((node == &_n##_rb_zero || node->_f.colour == C_BLACK) && \
+ node != &head->top) { \
+ if (parent->_f.left == node) { \
+ tmp = parent->_f.right; \
+ if (tmp->_f.colour == C_RED) { \
+ tmp->_f.colour = C_BLACK; \
+ parent->_f.colour = C_RED; \
+ rotate_left(head, parent); \
+ tmp = parent->_f.right; \
+ } \
+ if ((tmp->_f.left == &_n##_rb_zero || \
+ tmp->_f.left->_f.colour == C_BLACK) && \
+ (tmp->_f.right == &_n##_rb_zero || \
+ tmp->_f.right->_f.colour == C_BLACK)) { \
+ tmp->_f.colour = C_RED; \
+ node = parent; \
+ parent = node->_f.parent; \
+ } else { \
+ if (tmp->_f.right == &_n##_rb_zero || \
+ tmp->_f.right->_f.colour == C_BLACK) {\
+ _t *tmp2 = tmp->_f.left; \
+ \
+ if (tmp2 != &_n##_rb_zero) \
+ tmp2->_f.colour = C_BLACK;\
+ tmp->_f.colour = C_RED; \
+ rotate_right(head, tmp); \
+ tmp = parent->_f.right; \
+ } \
+ tmp->_f.colour = parent->_f.colour; \
+ parent->_f.colour = C_BLACK; \
+ if (tmp->_f.right != &_n##_rb_zero) \
+ tmp->_f.right->_f.colour = C_BLACK;\
+ rotate_left(head, parent); \
+ node = head->top._f.right; \
+ } \
+ } else { \
+ tmp = parent->_f.left; \
+ if (tmp->_f.colour == C_RED) { \
+ tmp->_f.colour = C_BLACK; \
+ parent->_f.colour = C_RED; \
+ rotate_right(head, parent); \
+ tmp = parent->_f.left; \
+ } \
+ if ((tmp->_f.left == &_n##_rb_zero || \
+ tmp->_f.left->_f.colour == C_BLACK) && \
+ (tmp->_f.right == &_n##_rb_zero || \
+ tmp->_f.right->_f.colour == C_BLACK)) { \
+ tmp->_f.colour = C_RED; \
+ node = parent; \
+ parent = node->_f.parent; \
+ } else { \
+ if (tmp->_f.left == &_n##_rb_zero || \
+ tmp->_f.left->_f.colour == C_BLACK) {\
+ _t *tmp2 = tmp->_f.right; \
+ \
+ if (tmp2 != &_n##_rb_zero) \
+ tmp2->_f.colour = C_BLACK;\
+ tmp->_f.colour = C_RED; \
+ rotate_left(head, tmp); \
+ tmp = parent->_f.left; \
+ } \
+ tmp->_f.colour = parent->_f.colour; \
+ parent->_f.colour = C_BLACK; \
+ if (tmp->_f.left != &_n##_rb_zero) \
+ tmp->_f.left->_f.colour = C_BLACK;\
+ rotate_right(head, parent); \
+ node = head->top._f.right; \
+ break; \
+ } \
+ } \
+ } \
+ if (node != &_n##_rb_zero) \
+ node->_f.colour = C_BLACK; \
+} \
+ \
+_t * \
+_n##_rb_delete(struct _n##_rb_head *head, _t *node) \
+{ \
+ _t *child, *parent, *old = node, *left; \
+ rbcolour_t color; \
+ \
+ if (node->_f.left == &_n##_rb_zero) { \
+ child = node->_f.right; \
+ } else if (node->_f.right == &_n##_rb_zero) { \
+ child = node->_f.left; \
+ } else { \
+ node = node->_f.right; \
+ while ((left = node->_f.left) != &_n##_rb_zero) \
+ node = left; \
+ child = node->_f.right; \
+ parent = node->_f.parent; \
+ color = node->_f.colour; \
+ if (child != &_n##_rb_zero) \
+ child->_f.parent = parent; \
+ if (parent != &_n##_rb_zero) { \
+ if (parent->_f.left == node) \
+ parent->_f.left = child; \
+ else \
+ parent->_f.right = child; \
+ } else { \
+ head->top._f.right = child; \
+ } \
+ if (node->_f.parent == old) \
+ parent = node; \
+ *node = *old; \
+ if (old->_f.parent != &_n##_rb_zero) { \
+ if (old->_f.parent->_f.left == old) \
+ old->_f.parent->_f.left = node; \
+ else \
+ old->_f.parent->_f.right = node; \
+ } else { \
+ head->top._f.right = child; \
+ } \
+ old->_f.left->_f.parent = node; \
+ if (old->_f.right != &_n##_rb_zero) \
+ old->_f.right->_f.parent = node; \
+ if (parent != &_n##_rb_zero) { \
+ left = parent; \
+ } \
+ goto colour; \
+ } \
+ parent = node->_f.parent; \
+ color= node->_f.colour; \
+ if (child != &_n##_rb_zero) \
+ child->_f.parent = parent; \
+ if (parent != &_n##_rb_zero) { \
+ if (parent->_f.left == node) \
+ parent->_f.left = child; \
+ else \
+ parent->_f.right = child; \
+ } else { \
+ head->top._f.right = child; \
+ } \
+colour: \
+ if (color == C_BLACK) \
+ deleteblack(head, parent, node); \
+ head->count--; \
+ return old; \
+} \
+ \
+void \
+_n##_rb_init(struct _n##_rb_head *head) \
+{ \
+ memset(head, 0, sizeof(*head)); \
+ memset(&_n##_rb_zero, 0, sizeof(_n##_rb_zero)); \
+ head->top._f.left = &_n##_rb_zero; \
+ head->top._f.right = &_n##_rb_zero; \
+ head->top._f.parent = &head->top; \
+ _n##_rb_zero._f.left = &_n##_rb_zero; \
+ _n##_rb_zero._f.right = &_n##_rb_zero; \
+ _n##_rb_zero._f.parent = &_n##_rb_zero; \
+} \
+ \
+void \
+_n##_rb_walktree(struct _n##_rb_head *head, _n##_rb_walker_t func, void *arg)\
+{ \
+ _t *prev; \
+ _t *next; \
+ _t *node = head->top._f.right; \
+ _t *base; \
+ \
+ while (node != &_n##_rb_zero) \
+ node = node->_f.left; \
+ \
+ for (;;) { \
+ base = node; \
+ prev = node; \
+ while ((node->_f.parent->_f.right == node) && \
+ (node != &_n##_rb_zero)) { \
+ prev = node; \
+ node = node->_f.parent; \
+ } \
+ \
+ node = prev; \
+ for (node = node->_f.parent->_f.right; node != &_n##_rb_zero;\
+ node = node->_f.left) \
+ prev = node; \
+ next = prev; \
+ \
+ if (node != &_n##_rb_zero) \
+ func(node, arg); \
+ \
+ node = next; \
+ if (node == &_n##_rb_zero) \
+ break; \
+ } \
+} \
+ \
+_t * \
+_n##_rb_search(struct _n##_rb_head *head, void *key) \
+{ \
+ int match; \
+ _t *node; \
+ node = head->top._f.right; \
+ while (node != &_n##_rb_zero) { \
+ match = _cmp(key, node); \
+ if (match == 0) \
+ break; \
+ if (match< 0) \
+ node = node->_f.left; \
+ else \
+ node = node->_f.right; \
+ } \
+ if (node == &_n##_rb_zero || match != 0) \
+ return (NULL); \
+ return (node); \
+}
+
+#define RBI_DELETE(_n, _h, _v) _n##_rb_delete(_h, _v)
+#define RBI_FIELD(_n) struct _n##_rb_link
+#define RBI_INIT(_n, _h) _n##_rb_init(_h)
+#define RBI_INSERT(_n, _h, _v) _n##_rb_insert(_h, _v)
+#define RBI_ISEMPTY(_h) ((_h)->count == 0)
+#define RBI_SEARCH(_n, _h, _k) _n##_rb_search(_h, _k)
+#define RBI_WALK(_n, _h, _w, _a) _n##_rb_walktree(_h, _w, _a)
+#define RBI_ZERO(_n) _n##_rb_zero
diff --git a/netinet/radix_ipf.c b/netinet/radix_ipf.c
new file mode 100644
index 000000000000..f145c38a94d6
--- /dev/null
+++ b/netinet/radix_ipf.c
@@ -0,0 +1,1528 @@
+/*
+ * Copyright (C) 2012 by Darren Reed.
+ *
+ * See the IPFILTER.LICENCE file for details on licencing.
+ */
+#include <sys/types.h>
+#include <sys/time.h>
+#include <sys/socket.h>
+#include <sys/param.h>
+#include <netinet/in.h>
+#include <net/if.h>
+#if !defined(_KERNEL)
+# include <stddef.h>
+# include <stdlib.h>
+# include <strings.h>
+# include <string.h>
+#endif
+#include "netinet/ip_compat.h"
+#include "netinet/ip_fil.h"
+#ifdef RDX_DEBUG
+# include <arpa/inet.h>
+# include <stdlib.h>
+# include <stdio.h>
+#endif
+#include "netinet/radix_ipf.h"
+
+#define ADF_OFF offsetof(addrfamily_t, adf_addr)
+#define ADF_OFF_BITS (ADF_OFF << 3)
+
+static ipf_rdx_node_t *ipf_rx_insert __P((ipf_rdx_head_t *,
+ ipf_rdx_node_t nodes[2], int *));
+static void ipf_rx_attach_mask __P((ipf_rdx_node_t *, ipf_rdx_mask_t *));
+static int count_mask_bits __P((addrfamily_t *, u_32_t **));
+static void buildnodes __P((addrfamily_t *, addrfamily_t *,
+ ipf_rdx_node_t n[2]));
+static ipf_rdx_node_t *ipf_rx_find_addr __P((ipf_rdx_node_t *, u_32_t *));
+static ipf_rdx_node_t *ipf_rx_lookup __P((ipf_rdx_head_t *, addrfamily_t *,
+ addrfamily_t *));
+static ipf_rdx_node_t *ipf_rx_match __P((ipf_rdx_head_t *, addrfamily_t *));
+
+/*
+ * Foreword.
+ * ---------
+ * The code in this file has been written to target using the addrfamily_t
+ * data structure to house the address information and no other. Thus there
+ * are certain aspects of thise code (such as offsets to the address itself)
+ * that are hard coded here whilst they might be more variable elsewhere.
+ * Similarly, this code enforces no maximum key length as that's implied by
+ * all keys needing to be stored in addrfamily_t.
+ */
+
+/* ------------------------------------------------------------------------ */
+/* Function: count_mask_bits */
+/* Returns: number of consecutive bits starting at "mask". */
+/* */
+/* Count the number of bits set in the address section of addrfamily_t and */
+/* return both that number and a pointer to the last word with a bit set if */
+/* lastp is not NULL. The bit count is performed using network byte order */
+/* as the guide for which bit is the most significant bit. */
+/* ------------------------------------------------------------------------ */
+static int
+count_mask_bits(mask, lastp)
+ addrfamily_t *mask;
+ u_32_t **lastp;
+{
+ u_32_t *mp = (u_32_t *)&mask->adf_addr;
+ u_32_t m;
+ int count = 0;
+ int mlen;
+
+ mlen = mask->adf_len - offsetof(addrfamily_t, adf_addr);
+ for (; mlen > 0; mlen -= 4, mp++) {
+ if ((m = ntohl(*mp)) == 0)
+ break;
+ if (lastp != NULL)
+ *lastp = mp;
+ for (; m & 0x80000000; m <<= 1)
+ count++;
+ }
+
+ return count;
+}
+
+
+/* ------------------------------------------------------------------------ */
+/* Function: buildnodes */
+/* Returns: Nil */
+/* Parameters: addr(I) - network address for this radix node */
+/* mask(I) - netmask associated with the above address */
+/* nodes(O) - pair of ipf_rdx_node_t's to initialise with data */
+/* associated with addr and mask. */
+/* */
+/* Initialise the fields in a pair of radix tree nodes according to the */
+/* data supplied in the paramters "addr" and "mask". It is expected that */
+/* "mask" will contain a consecutive string of bits set. Masks with gaps in */
+/* the middle are not handled by this implementation. */
+/* ------------------------------------------------------------------------ */
+static void
+buildnodes(addr, mask, nodes)
+ addrfamily_t *addr, *mask;
+ ipf_rdx_node_t nodes[2];
+{
+ u_32_t maskbits;
+ u_32_t lastbits;
+ u_32_t lastmask;
+ u_32_t *last;
+ int masklen;
+
+ last = NULL;
+ maskbits = count_mask_bits(mask, &last);
+ if (last == NULL) {
+ masklen = 0;
+ lastmask = 0;
+ } else {
+ masklen = last - (u_32_t *)mask;
+ lastmask = *last;
+ }
+ lastbits = maskbits & 0x1f;
+
+ bzero(&nodes[0], sizeof(ipf_rdx_node_t) * 2);
+ nodes[0].maskbitcount = maskbits;
+ nodes[0].index = -1 - (ADF_OFF_BITS + maskbits);
+ nodes[0].addrkey = (u_32_t *)addr;
+ nodes[0].maskkey = (u_32_t *)mask;
+ nodes[0].addroff = nodes[0].addrkey + masklen;
+ nodes[0].maskoff = nodes[0].maskkey + masklen;
+ nodes[0].parent = &nodes[1];
+ nodes[0].offset = masklen;
+ nodes[0].lastmask = lastmask;
+ nodes[1].offset = masklen;
+ nodes[1].left = &nodes[0];
+ nodes[1].maskbitcount = maskbits;
+#ifdef RDX_DEBUG
+ (void) strcpy(nodes[0].name, "_BUILD.0");
+ (void) strcpy(nodes[1].name, "_BUILD.1");
+#endif
+}
+
+
+/* ------------------------------------------------------------------------ */
+/* Function: ipf_rx_find_addr */
+/* Returns: ipf_rdx_node_t * - pointer to a node in the radix tree. */
+/* Parameters: tree(I) - pointer to first right node in tree to search */
+/* addr(I) - pointer to address to match */
+/* */
+/* Walk the radix tree given by "tree", looking for a leaf node that is a */
+/* match for the address given by "addr". */
+/* ------------------------------------------------------------------------ */
+static ipf_rdx_node_t *
+ipf_rx_find_addr(tree, addr)
+ ipf_rdx_node_t *tree;
+ u_32_t *addr;
+{
+ ipf_rdx_node_t *cur;
+
+ for (cur = tree; cur->index >= 0;) {
+ if (cur->bitmask & addr[cur->offset]) {
+ cur = cur->right;
+ } else {
+ cur = cur->left;
+ }
+ }
+
+ return (cur);
+}
+
+
+/* ------------------------------------------------------------------------ */
+/* Function: ipf_rx_match */
+/* Returns: ipf_rdx_node_t * - NULL on error, else pointer to the node */
+/* added to the tree. */
+/* Paramters: head(I) - pointer to tree head to search */
+/* addr(I) - pointer to address to find */
+/* */
+/* Search the radix tree for the best match to the address pointed to by */
+/* "addr" and return a pointer to that node. This search will not match the */
+/* address information stored in either of the root leaves as neither of */
+/* them are considered to be part of the tree of data being stored. */
+/* ------------------------------------------------------------------------ */
+static ipf_rdx_node_t *
+ipf_rx_match(head, addr)
+ ipf_rdx_head_t *head;
+ addrfamily_t *addr;
+{
+ ipf_rdx_mask_t *masknode;
+ ipf_rdx_node_t *prev;
+ ipf_rdx_node_t *node;
+ ipf_rdx_node_t *cur;
+ u_32_t *data;
+ u_32_t *mask;
+ u_32_t *key;
+ u_32_t *end;
+ int len;
+ int i;
+
+ len = addr->adf_len;
+ end = (u_32_t *)((u_char *)addr + len);
+ node = ipf_rx_find_addr(head->root, (u_32_t *)addr);
+
+ /*
+ * Search the dupkey list for a potential match.
+ */
+ for (cur = node; (cur != NULL) && (cur->root == 0); cur = cur->dupkey) {
+ i = cur[0].addroff - cur[0].addrkey;
+ data = cur[0].addrkey + i;
+ mask = cur[0].maskkey + i;
+ key = (u_32_t *)addr + i;
+ for (; key < end; data++, key++, mask++)
+ if ((*key & *mask) != *data)
+ break;
+ if ((end == key) && (cur->root == 0))
+ return (cur); /* Equal keys */
+ }
+ prev = node->parent;
+ key = (u_32_t *)addr;
+
+ for (node = prev; node->root == 0; node = node->parent) {
+ /*
+ * We know that the node hasn't matched so therefore only
+ * the entries in the mask list are searched, not the top
+ * node nor the dupkey list.
+ */
+ masknode = node->masks;
+ for (; masknode != NULL; masknode = masknode->next) {
+ if (masknode->maskbitcount > node->maskbitcount)
+ continue;
+ cur = masknode->node;
+ for (i = ADF_OFF >> 2; i <= node->offset; i++) {
+ if ((key[i] & masknode->mask[i]) ==
+ cur->addrkey[i])
+ return (cur);
+ }
+ }
+ }
+
+ return NULL;
+}
+
+
+/* ------------------------------------------------------------------------ */
+/* Function: ipf_rx_lookup */
+/* Returns: ipf_rdx_node_t * - NULL on error, else pointer to the node */
+/* added to the tree. */
+/* Paramters: head(I) - pointer to tree head to search */
+/* addr(I) - address part of the key to match */
+/* mask(I) - netmask part of the key to match */
+/* */
+/* ipf_rx_lookup searches for an exact match on (addr,mask). The intention */
+/* is to see if a given key is in the tree, not to see if a route exists. */
+/* ------------------------------------------------------------------------ */
+ipf_rdx_node_t *
+ipf_rx_lookup(head, addr, mask)
+ ipf_rdx_head_t *head;
+ addrfamily_t *addr, *mask;
+{
+ ipf_rdx_node_t *found;
+ ipf_rdx_node_t *node;
+ u_32_t *akey;
+ int count;
+
+ found = ipf_rx_find_addr(head->root, (u_32_t *)addr);
+ if (found->root == 1)
+ return NULL;
+
+ /*
+ * It is possible to find a matching address in the tree but for the
+ * netmask to not match. If the netmask does not match and there is
+ * no list of alternatives present at dupkey, return a failure.
+ */
+ count = count_mask_bits(mask, NULL);
+ if (count != found->maskbitcount && found->dupkey == NULL)
+ return (NULL);
+
+ akey = (u_32_t *)addr;
+ if ((found->addrkey[found->offset] & found->maskkey[found->offset]) !=
+ akey[found->offset])
+ return NULL;
+
+ if (found->dupkey != NULL) {
+ node = found;
+ while (node != NULL && node->maskbitcount != count)
+ node = node->dupkey;
+ if (node == NULL)
+ return (NULL);
+ found = node;
+ }
+ return found;
+}
+
+
+/* ------------------------------------------------------------------------ */
+/* Function: ipf_rx_attach_mask */
+/* Returns: Nil */
+/* Parameters: node(I) - pointer to a radix tree node */
+/* mask(I) - pointer to mask structure to add */
+/* */
+/* Add the netmask to the given node in an ordering where the most specific */
+/* netmask is at the top of the list. */
+/* ------------------------------------------------------------------------ */
+static void
+ipf_rx_attach_mask(node, mask)
+ ipf_rdx_node_t *node;
+ ipf_rdx_mask_t *mask;
+{
+ ipf_rdx_mask_t **pm;
+ ipf_rdx_mask_t *m;
+
+ for (pm = &node->masks; (m = *pm) != NULL; pm = &m->next)
+ if (m->maskbitcount < mask->maskbitcount)
+ break;
+ mask->next = *pm;
+ *pm = mask;
+}
+
+
+/* ------------------------------------------------------------------------ */
+/* Function: ipf_rx_insert */
+/* Returns: ipf_rdx_node_t * - NULL on error, else pointer to the node */
+/* added to the tree. */
+/* Paramters: head(I) - pointer to tree head to add nodes to */
+/* nodes(I) - pointer to radix nodes to be added */
+/* dup(O) - set to 1 if node is a duplicate, else 0. */
+/* */
+/* Add the new radix tree entry that owns nodes[] to the tree given by head.*/
+/* If there is already a matching key in the table, "dup" will be set to 1 */
+/* and the existing node pointer returned if there is a complete key match. */
+/* A complete key match is a matching of all key data that is presented by */
+/* by the netmask. */
+/* ------------------------------------------------------------------------ */
+static ipf_rdx_node_t *
+ipf_rx_insert(head, nodes, dup)
+ ipf_rdx_head_t *head;
+ ipf_rdx_node_t nodes[2];
+ int *dup;
+{
+ ipf_rdx_mask_t **pmask;
+ ipf_rdx_node_t *node;
+ ipf_rdx_node_t *prev;
+ ipf_rdx_mask_t *mask;
+ ipf_rdx_node_t *cur;
+ u_32_t nodemask;
+ u_32_t *addr;
+ u_32_t *data;
+ int nodebits;
+ u_32_t *key;
+ u_32_t *end;
+ u_32_t bits;
+ int nodekey;
+ int nodeoff;
+ int nlen;
+ int len;
+
+ addr = nodes[0].addrkey;
+
+ node = ipf_rx_find_addr(head->root, addr);
+ len = ((addrfamily_t *)addr)->adf_len;
+ key = (u_32_t *)&((addrfamily_t *)addr)->adf_addr;
+ data= (u_32_t *)&((addrfamily_t *)node->addrkey)->adf_addr;
+ end = (u_32_t *)((u_char *)addr + len);
+ for (nlen = 0; key < end; data++, key++, nlen += 32)
+ if (*key != *data)
+ break;
+ if (end == data) {
+ *dup = 1;
+ return (node); /* Equal keys */
+ }
+ *dup = 0;
+
+ bits = (ntohl(*data) ^ ntohl(*key));
+ for (; bits != 0; nlen++) {
+ if ((bits & 0x80000000) != 0)
+ break;
+ bits <<= 1;
+ }
+ nlen += ADF_OFF_BITS;
+ nodes[1].index = nlen;
+ nodes[1].bitmask = htonl(0x80000000 >> (nlen & 0x1f));
+ nodes[0].offset = nlen / 32;
+ nodes[1].offset = nlen / 32;
+
+ /*
+ * Walk through the tree and look for the correct place to attach
+ * this node. ipf_rx_fin_addr is not used here because the place
+ * to attach this node may be an internal node (same key, different
+ * netmask.) Additionally, the depth of the search is forcibly limited
+ * here to not exceed the netmask, so that a short netmask will be
+ * added higher up the tree even if there are lower branches.
+ */
+ cur = head->root;
+ key = nodes[0].addrkey;
+ do {
+ prev = cur;
+ if (key[cur->offset] & cur->bitmask) {
+ cur = cur->right;
+ } else {
+ cur = cur->left;
+ }
+ } while (nlen > (unsigned)cur->index);
+
+ if ((key[prev->offset] & prev->bitmask) == 0) {
+ prev->left = &nodes[1];
+ } else {
+ prev->right = &nodes[1];
+ }
+ cur->parent = &nodes[1];
+ nodes[1].parent = prev;
+ if ((key[nodes[1].offset] & nodes[1].bitmask) == 0) {
+ nodes[1].right = cur;
+ } else {
+ nodes[1].right = &nodes[0];
+ nodes[1].left = cur;
+ }
+
+ nodeoff = nodes[0].offset;
+ nodekey = nodes[0].addrkey[nodeoff];
+ nodemask = nodes[0].lastmask;
+ nodebits = nodes[0].maskbitcount;
+ prev = NULL;
+ /*
+ * Find the node up the tree with the largest pattern that still
+ * matches the node being inserted to see if this mask can be
+ * moved there.
+ */
+ for (cur = nodes[1].parent; cur->root == 0; cur = cur->parent) {
+ if (cur->maskbitcount <= nodebits)
+ break;
+ if (((cur - 1)->addrkey[nodeoff] & nodemask) != nodekey)
+ break;
+ prev = cur;
+ }
+
+ KMALLOC(mask, ipf_rdx_mask_t *);
+ if (mask == NULL)
+ return NULL;
+ bzero(mask, sizeof(*mask));
+ mask->next = NULL;
+ mask->node = &nodes[0];
+ mask->maskbitcount = nodebits;
+ mask->mask = nodes[0].maskkey;
+ nodes[0].mymask = mask;
+
+ if (prev != NULL) {
+ ipf_rdx_mask_t *m;
+
+ for (pmask = &prev->masks; (m = *pmask) != NULL;
+ pmask = &m->next) {
+ if (m->maskbitcount < nodebits)
+ break;
+ }
+ } else {
+ /*
+ * No higher up nodes qualify, so attach mask locally.
+ */
+ pmask = &nodes[0].masks;
+ }
+ mask->next = *pmask;
+ *pmask = mask;
+
+ /*
+ * Search the mask list on each child to see if there are any masks
+ * there that can be moved up to this newly inserted node.
+ */
+ cur = nodes[1].right;
+ if (cur->root == 0) {
+ for (pmask = &cur->masks; (mask = *pmask) != NULL; ) {
+ if (mask->maskbitcount < nodebits) {
+ *pmask = mask->next;
+ ipf_rx_attach_mask(&nodes[0], mask);
+ } else {
+ pmask = &mask->next;
+ }
+ }
+ }
+ cur = nodes[1].left;
+ if (cur->root == 0 && cur != &nodes[0]) {
+ for (pmask = &cur->masks; (mask = *pmask) != NULL; ) {
+ if (mask->maskbitcount < nodebits) {
+ *pmask = mask->next;
+ ipf_rx_attach_mask(&nodes[0], mask);
+ } else {
+ pmask = &mask->next;
+ }
+ }
+ }
+ return (&nodes[0]);
+}
+
+/* ------------------------------------------------------------------------ */
+/* Function: ipf_rx_addroute */
+/* Returns: ipf_rdx_node_t * - NULL on error, else pointer to the node */
+/* added to the tree. */
+/* Paramters: head(I) - pointer to tree head to search */
+/* addr(I) - address portion of "route" to add */
+/* mask(I) - netmask portion of "route" to add */
+/* nodes(I) - radix tree data nodes inside allocate structure */
+/* */
+/* Attempt to add a node to the radix tree. The key for the node is the */
+/* (addr,mask). No memory allocation for the radix nodes themselves is */
+/* performed here, the data structure that this radix node is being used to */
+/* find is expected to house the node data itself however the call to */
+/* ipf_rx_insert() will attempt to allocate memory in order for netmask to */
+/* be promoted further up the tree. */
+/* In this case, the ip_pool_node_t structure from ip_pool.h contains both */
+/* the key material (addr,mask) and the radix tree nodes[]. */
+/* */
+/* The mechanics of inserting the node into the tree is handled by the */
+/* function ipf_rx_insert() above. Here, the code deals with the case */
+/* where the data to be inserted is a duplicate. */
+/* ------------------------------------------------------------------------ */
+ipf_rdx_node_t *
+ipf_rx_addroute(head, addr, mask, nodes)
+ ipf_rdx_head_t *head;
+ addrfamily_t *addr, *mask;
+ ipf_rdx_node_t *nodes;
+{
+ ipf_rdx_node_t *node;
+ ipf_rdx_node_t *prev;
+ ipf_rdx_node_t *x;
+ int dup;
+
+ buildnodes(addr, mask, nodes);
+ x = ipf_rx_insert(head, nodes, &dup);
+ if (x == NULL)
+ return NULL;
+
+ if (dup == 1) {
+ node = &nodes[0];
+ prev = NULL;
+ /*
+ * The duplicate list is kept sorted with the longest
+ * mask at the top, meaning that the most specific entry
+ * in the listis found first. This list thus allows for
+ * duplicates such as 128.128.0.0/32 and 128.128.0.0/16.
+ */
+ while ((x != NULL) && (x->maskbitcount > node->maskbitcount)) {
+ prev = x;
+ x = x->dupkey;
+ }
+
+ /*
+ * Is it a complete duplicate? If so, return NULL and
+ * fail the insert. Otherwise, insert it into the list
+ * of netmasks active for this key.
+ */
+ if ((x != NULL) && (x->maskbitcount == node->maskbitcount))
+ return (NULL);
+
+ if (prev != NULL) {
+ nodes[0].dupkey = x;
+ prev->dupkey = &nodes[0];
+ nodes[0].parent = prev;
+ if (x != NULL)
+ x->parent = &nodes[0];
+ } else {
+ nodes[0].dupkey = x->dupkey;
+ prev = x->parent;
+ nodes[0].parent = prev;
+ x->parent = &nodes[0];
+ if (prev->left == x)
+ prev->left = &nodes[0];
+ else
+ prev->right = &nodes[0];
+ }
+ }
+
+ return &nodes[0];
+}
+
+
+/* ------------------------------------------------------------------------ */
+/* Function: ipf_rx_delete */
+/* Returns: ipf_rdx_node_t * - NULL on error, else node removed from */
+/* the tree. */
+/* Paramters: head(I) - pointer to tree head to search */
+/* addr(I) - pointer to the address part of the key */
+/* mask(I) - pointer to the netmask part of the key */
+/* */
+/* Search for an entry in the radix tree that is an exact match for (addr, */
+/* mask) and remove it if it exists. In the case where (addr,mask) is a not */
+/* a unique key, the tree structure itself is not changed - only the list */
+/* of duplicate keys. */
+/* ------------------------------------------------------------------------ */
+ipf_rdx_node_t *
+ipf_rx_delete(head, addr, mask)
+ ipf_rdx_head_t *head;
+ addrfamily_t *addr, *mask;
+{
+ ipf_rdx_mask_t **pmask;
+ ipf_rdx_node_t *parent;
+ ipf_rdx_node_t *found;
+ ipf_rdx_node_t *prev;
+ ipf_rdx_node_t *node;
+ ipf_rdx_node_t *cur;
+ ipf_rdx_mask_t *m;
+ int count;
+
+ found = ipf_rx_find_addr(head->root, (u_32_t *)addr);
+ if (found == NULL)
+ return NULL;
+ if (found->root == 1)
+ return NULL;
+ count = count_mask_bits(mask, NULL);
+ parent = found->parent;
+ if (found->dupkey != NULL) {
+ node = found;
+ while (node != NULL && node->maskbitcount != count)
+ node = node->dupkey;
+ if (node == NULL)
+ return (NULL);
+ if (node != found) {
+ /*
+ * Remove from the dupkey list. Here, "parent" is
+ * the previous node on the list (rather than tree)
+ * and "dupkey" is the next node on the list.
+ */
+ parent = node->parent;
+ parent->dupkey = node->dupkey;
+ node->dupkey->parent = parent;
+ } else {
+ /*
+ *
+ * When removing the top node of the dupkey list,
+ * the pointers at the top of the list that point
+ * to other tree nodes need to be preserved and
+ * any children must have their parent updated.
+ */
+ node = node->dupkey;
+ node->parent = found->parent;
+ node->right = found->right;
+ node->left = found->left;
+ found->right->parent = node;
+ found->left->parent = node;
+ if (parent->left == found)
+ parent->left = node;
+ else
+ parent->right= node;
+ }
+ } else {
+ if (count != found->maskbitcount)
+ return (NULL);
+ /*
+ * Remove the node from the tree and reconnect the subtree
+ * below.
+ */
+ /*
+ * If there is a tree to the left, look for something to
+ * attach in place of "found".
+ */
+ prev = found + 1;
+ cur = parent->parent;
+ if (parent != found + 1) {
+ if ((found + 1)->parent->right == found + 1)
+ (found + 1)->parent->right = parent;
+ else
+ (found + 1)->parent->left = parent;
+ if (cur->right == parent) {
+ if (parent->left == found) {
+ cur->right = parent->right;
+ } else if (parent->left != parent - 1) {
+ cur->right = parent->left;
+ } else {
+ cur->right = parent - 1;
+ }
+ cur->right->parent = cur;
+ } else {
+ if (parent->right == found) {
+ cur->left = parent->left;
+ } else if (parent->right != parent - 1) {
+ cur->left = parent->right;
+ } else {
+ cur->left = parent - 1;
+ }
+ cur->left->parent = cur;
+ }
+ parent->left = (found + 1)->left;
+ if ((found + 1)->right != parent)
+ parent->right = (found + 1)->right;
+ parent->left->parent = parent;
+ parent->right->parent = parent;
+ parent->parent = (found + 1)->parent;
+
+ parent->bitmask = prev->bitmask;
+ parent->offset = prev->offset;
+ parent->index = prev->index;
+ } else {
+ /*
+ * We found an edge node.
+ */
+ cur = parent->parent;
+ if (cur->left == parent) {
+ if (parent->left == found) {
+ cur->left = parent->right;
+ parent->right->parent = cur;
+ } else {
+ cur->left = parent->left;
+ parent->left->parent = cur;
+ }
+ } else {
+ if (parent->right != found) {
+ cur->right = parent->right;
+ parent->right->parent = cur;
+ } else {
+ cur->right = parent->left;
+ prev->left->parent = cur;
+ }
+ }
+ }
+ }
+
+ /*
+ * Remove mask associated with this node.
+ */
+ for (cur = parent; cur->root == 0; cur = cur->parent) {
+ ipf_rdx_mask_t **pm;
+
+ if (cur->maskbitcount <= found->maskbitcount)
+ break;
+ if (((cur - 1)->addrkey[found->offset] & found->bitmask) !=
+ found->addrkey[found->offset])
+ break;
+ for (pm = &cur->masks; (m = *pm) != NULL; )
+ if (m->node == cur) {
+ *pm = m->next;
+ break;
+ } else {
+ pm = &m->next;
+ }
+ }
+ KFREE(found->mymask);
+
+ /*
+ * Masks that have been brought up to this node from below need to
+ * be sent back down.
+ */
+ for (pmask = &parent->masks; (m = *pmask) != NULL; ) {
+ *pmask = m->next;
+ cur = m->node;
+ if (cur == found)
+ continue;
+ if (found->addrkey[cur->offset] & cur->lastmask) {
+ ipf_rx_attach_mask(parent->right, m);
+ } else if (parent->left != found) {
+ ipf_rx_attach_mask(parent->left, m);
+ }
+ }
+
+ return (found);
+}
+
+
+/* ------------------------------------------------------------------------ */
+/* Function: ipf_rx_walktree */
+/* Returns: Nil */
+/* Paramters: head(I) - pointer to tree head to search */
+/* walker(I) - function to call for each node in the tree */
+/* arg(I) - parameter to pass to walker, in addition to the */
+/* node pointer */
+/* */
+/* A standard tree walking function except that it is iterative, rather */
+/* than recursive and tracks the next node in case the "walker" function */
+/* should happen to delete and free the current node. It thus goes without */
+/* saying that the "walker" function is not permitted to cause any change */
+/* in the validity of the data found at either the left or right child. */
+/* ------------------------------------------------------------------------ */
+void
+ipf_rx_walktree(head, walker, arg)
+ ipf_rdx_head_t *head;
+ radix_walk_func_t walker;
+ void *arg;
+{
+ ipf_rdx_node_t *next;
+ ipf_rdx_node_t *node = head->root;
+ ipf_rdx_node_t *base;
+
+ while (node->index >= 0)
+ node = node->left;
+
+ for (;;) {
+ base = node;
+ while ((node->parent->right == node) && (node->root == 0))
+ node = node->parent;
+
+ for (node = node->parent->right; node->index >= 0; )
+ node = node->left;
+ next = node;
+
+ for (node = base; node != NULL; node = base) {
+ base = node->dupkey;
+ if (node->root == 0)
+ walker(node, arg);
+ }
+ node = next;
+ if (node->root)
+ return;
+ }
+}
+
+
+/* ------------------------------------------------------------------------ */
+/* Function: ipf_rx_inithead */
+/* Returns: int - 0 = success, else failure */
+/* Paramters: softr(I) - pointer to radix context */
+/* headp(O) - location for where to store allocated tree head */
+/* */
+/* This function allocates and initialises a radix tree head structure. */
+/* As a traditional radix tree, node 0 is used as the "0" sentinel and node */
+/* "2" is used as the all ones sentinel, leaving node "1" as the root from */
+/* which the tree is hung with node "0" on its left and node "2" to the */
+/* right. The context, "softr", is used here to provide a common source of */
+/* the zeroes and ones data rather than have one per head. */
+/* ------------------------------------------------------------------------ */
+int
+ipf_rx_inithead(softr, headp)
+ radix_softc_t *softr;
+ ipf_rdx_head_t **headp;
+{
+ ipf_rdx_head_t *ptr;
+ ipf_rdx_node_t *node;
+
+ KMALLOC(ptr, ipf_rdx_head_t *);
+ *headp = ptr;
+ if (ptr == NULL)
+ return -1;
+ bzero(ptr, sizeof(*ptr));
+ node = ptr->nodes;
+ ptr->root = node + 1;
+ node[0].index = ADF_OFF_BITS;
+ node[0].index = -1 - node[0].index;
+ node[1].index = ADF_OFF_BITS;
+ node[2].index = node[0].index;
+ node[0].parent = node + 1;
+ node[1].parent = node + 1;
+ node[2].parent = node + 1;
+ node[1].bitmask = htonl(0x80000000);
+ node[0].root = 1;
+ node[1].root = 1;
+ node[2].root = 1;
+ node[0].offset = ADF_OFF_BITS >> 5;
+ node[1].offset = ADF_OFF_BITS >> 5;
+ node[2].offset = ADF_OFF_BITS >> 5;
+ node[1].left = &node[0];
+ node[1].right = &node[2];
+ node[0].addrkey = (u_32_t *)softr->zeros;
+ node[2].addrkey = (u_32_t *)softr->ones;
+#ifdef RDX_DEBUG
+ (void) strcpy(node[0].name, "0_ROOT");
+ (void) strcpy(node[1].name, "1_ROOT");
+ (void) strcpy(node[2].name, "2_ROOT");
+#endif
+
+ ptr->addaddr = ipf_rx_addroute;
+ ptr->deladdr = ipf_rx_delete;
+ ptr->lookup = ipf_rx_lookup;
+ ptr->matchaddr = ipf_rx_match;
+ ptr->walktree = ipf_rx_walktree;
+ return 0;
+}
+
+
+/* ------------------------------------------------------------------------ */
+/* Function: ipf_rx_freehead */
+/* Returns: Nil */
+/* Paramters: head(I) - pointer to tree head to free */
+/* */
+/* This function simply free's up the radix tree head. Prior to calling */
+/* this function, it is expected that the tree will have been emptied. */
+/* ------------------------------------------------------------------------ */
+void
+ipf_rx_freehead(head)
+ ipf_rdx_head_t *head;
+{
+ KFREE(head);
+}
+
+
+/* ------------------------------------------------------------------------ */
+/* Function: ipf_rx_create */
+/* Parameters: Nil */
+/* */
+/* ------------------------------------------------------------------------ */
+void *
+ipf_rx_create()
+{
+ radix_softc_t *softr;
+
+ KMALLOC(softr, radix_softc_t *);
+ if (softr == NULL)
+ return NULL;
+ bzero((char *)softr, sizeof(*softr));
+
+ KMALLOCS(softr->zeros, u_char *, 3 * sizeof(addrfamily_t));
+ if (softr->zeros == NULL) {
+ KFREE(softr);
+ return (NULL);
+ }
+ softr->ones = softr->zeros + sizeof(addrfamily_t);
+
+ return softr;
+}
+
+
+/* ------------------------------------------------------------------------ */
+/* Function: ipf_rx_init */
+/* Returns: int - 0 = success (always) */
+/* */
+/* ------------------------------------------------------------------------ */
+int
+ipf_rx_init(ctx)
+ void *ctx;
+{
+ radix_softc_t *softr = ctx;
+
+ memset(softr->zeros, 0, 3 * sizeof(addrfamily_t));
+ memset(softr->ones, 0xff, sizeof(addrfamily_t));
+
+ return (0);
+}
+
+
+/* ------------------------------------------------------------------------ */
+/* Function: ipf_rx_destroy */
+/* Returns: Nil */
+/* */
+/* ------------------------------------------------------------------------ */
+void
+ipf_rx_destroy(ctx)
+ void *ctx;
+{
+ radix_softc_t *softr = ctx;
+
+ if (softr->zeros != NULL)
+ KFREES(softr->zeros, 3 * sizeof(addrfamily_t));
+ KFREE(softr);
+}
+
+/* ====================================================================== */
+
+#ifdef RDX_DEBUG
+/*
+ * To compile this file as a standalone test unit, use -DRDX_DEBUG=1
+ */
+#define NAME(x) ((x)->index < 0 ? (x)->name : (x)->name)
+#define GNAME(y) ((y) == NULL ? "NULL" : NAME(y))
+
+typedef struct myst {
+ struct ipf_rdx_node nodes[2];
+ addrfamily_t dst;
+ addrfamily_t mask;
+ struct myst *next;
+ int printed;
+} myst_t;
+
+typedef struct tabe_s {
+ char *host;
+ char *mask;
+ char *what;
+} tabe_t;
+
+tabe_t builtin[] = {
+#if 1
+ { "192:168:100::0", "48", "d" },
+ { "192:168:100::2", "128", "d" },
+#else
+ { "127.192.0.0", "255.255.255.0", "d" },
+ { "127.128.0.0", "255.255.255.0", "d" },
+ { "127.96.0.0", "255.255.255.0", "d" },
+ { "127.80.0.0", "255.255.255.0", "d" },
+ { "127.72.0.0", "255.255.255.0", "d" },
+ { "127.64.0.0", "255.255.255.0", "d" },
+ { "127.56.0.0", "255.255.255.0", "d" },
+ { "127.48.0.0", "255.255.255.0", "d" },
+ { "127.40.0.0", "255.255.255.0", "d" },
+ { "127.32.0.0", "255.255.255.0", "d" },
+ { "127.24.0.0", "255.255.255.0", "d" },
+ { "127.16.0.0", "255.255.255.0", "d" },
+ { "127.8.0.0", "255.255.255.0", "d" },
+ { "124.0.0.0", "255.0.0.0", "d" },
+ { "125.0.0.0", "255.0.0.0", "d" },
+ { "126.0.0.0", "255.0.0.0", "d" },
+ { "127.0.0.0", "255.0.0.0", "d" },
+ { "10.0.0.0", "255.0.0.0", "d" },
+ { "128.250.0.0", "255.255.0.0", "d" },
+ { "192.168.0.0", "255.255.0.0", "d" },
+ { "192.168.1.0", "255.255.255.0", "d" },
+#endif
+ { NULL, NULL, NULL }
+};
+
+char *mtable[][1] = {
+#if 1
+ { "192:168:100::2" },
+ { "192:168:101::2" },
+#else
+ { "9.0.0.0" },
+ { "9.0.0.1" },
+ { "11.0.0.0" },
+ { "11.0.0.1" },
+ { "127.0.0.1" },
+ { "127.0.1.0" },
+ { "255.255.255.0" },
+ { "126.0.0.1" },
+ { "128.251.0.0" },
+ { "128.251.0.1" },
+ { "128.251.255.255" },
+ { "129.250.0.0" },
+ { "129.250.0.1" },
+ { "192.168.255.255" },
+#endif
+ { NULL }
+};
+
+
+int forder[22] = {
+ 14, 13, 12, 5, 10, 3, 19, 7, 4, 20, 8,
+ 2, 17, 9, 16, 11, 15, 1, 6, 18, 0, 21
+};
+
+static int nodecount = 0;
+myst_t *myst_top = NULL;
+tabe_t *ttable = NULL;
+
+void add_addr(ipf_rdx_head_t *, int , int);
+void checktree(ipf_rdx_head_t *);
+void delete_addr(ipf_rdx_head_t *rnh, int item);
+void dumptree(ipf_rdx_head_t *rnh);
+void nodeprinter(ipf_rdx_node_t *, void *);
+void printroots(ipf_rdx_head_t *);
+void random_add(ipf_rdx_head_t *);
+void random_delete(ipf_rdx_head_t *);
+void test_addr(ipf_rdx_head_t *rnh, int pref, addrfamily_t *, int);
+
+
+static void
+ipf_rx_freenode(node, arg)
+ ipf_rdx_node_t *node;
+ void *arg;
+{
+ ipf_rdx_head_t *head = arg;
+ ipf_rdx_node_t *rv;
+ myst_t *stp;
+
+ stp = (myst_t *)node;
+ rv = ipf_rx_delete(head, &stp->dst, &stp->mask);
+ if (rv != NULL) {
+ free(rv);
+ }
+}
+
+
+const char *
+addrname(ap)
+ addrfamily_t *ap;
+{
+ static char name[80];
+ const char *txt;
+
+ bzero((char *)name, sizeof(name));
+ txt = inet_ntop(ap->adf_family, &ap->adf_addr, name,
+ sizeof(name));
+ return txt;
+}
+
+
+void
+fill6bits(bits, msk)
+ int bits;
+ u_int *msk;
+{
+ if (bits == 0) {
+ msk[0] = 0;
+ msk[1] = 0;
+ msk[2] = 0;
+ msk[3] = 0;
+ return;
+ }
+
+ msk[0] = 0xffffffff;
+ msk[1] = 0xffffffff;
+ msk[2] = 0xffffffff;
+ msk[3] = 0xffffffff;
+
+ if (bits == 128)
+ return;
+ if (bits > 96) {
+ msk[3] = htonl(msk[3] << (128 - bits));
+ } else if (bits > 64) {
+ msk[3] = 0;
+ msk[2] = htonl(msk[2] << (96 - bits));
+ } else if (bits > 32) {
+ msk[3] = 0;
+ msk[2] = 0;
+ msk[1] = htonl(msk[1] << (64 - bits));
+ } else {
+ msk[3] = 0;
+ msk[2] = 0;
+ msk[1] = 0;
+ msk[0] = htonl(msk[0] << (32 - bits));
+ }
+}
+
+
+void
+setaddr(afp, str)
+ addrfamily_t *afp;
+ char *str;
+{
+
+ bzero((char *)afp, sizeof(*afp));
+
+ if (strchr(str, ':') == NULL) {
+ afp->adf_family = AF_INET;
+ afp->adf_len = offsetof(addrfamily_t, adf_addr) + 4;
+ } else {
+ afp->adf_family = AF_INET6;
+ afp->adf_len = offsetof(addrfamily_t, adf_addr) + 16;
+ }
+ inet_pton(afp->adf_family, str, &afp->adf_addr);
+}
+
+
+void
+setmask(afp, str)
+ addrfamily_t *afp;
+ char *str;
+{
+ if (strchr(str, '.') != NULL) {
+ afp->adf_addr.in4.s_addr = inet_addr(str);
+ afp->adf_len = offsetof(addrfamily_t, adf_addr) + 4;
+ } else if (afp->adf_family == AF_INET) {
+ afp->adf_addr.i6[0] = htonl(0xffffffff << (32 - atoi(str)));
+ afp->adf_len = offsetof(addrfamily_t, adf_addr) + 4;
+ } else if (afp->adf_family == AF_INET6) {
+ fill6bits(atoi(str), afp->adf_addr.i6);
+ afp->adf_len = offsetof(addrfamily_t, adf_addr) + 16;
+ }
+}
+
+
+void
+nodeprinter(node, arg)
+ ipf_rdx_node_t *node;
+ void *arg;
+{
+ myst_t *stp = (myst_t *)node;
+
+ printf("Node %-9.9s L %-9.9s R %-9.9s P %9.9s/%-9.9s %s/%d\n",
+ node[0].name,
+ GNAME(node[1].left), GNAME(node[1].right),
+ GNAME(node[0].parent), GNAME(node[1].parent),
+ addrname(&stp->dst), node[0].maskbitcount);
+ if (stp->printed == -1)
+ printf("!!! %d\n", stp->printed);
+ else
+ stp->printed = 1;
+}
+
+
+void
+printnode(stp)
+ myst_t *stp;
+{
+ ipf_rdx_node_t *node = &stp->nodes[0];
+
+ if (stp->nodes[0].index > 0)
+ stp = (myst_t *)&stp->nodes[-1];
+
+ printf("Node %-9.9s ", node[0].name);
+ printf("L %-9.9s ", GNAME(node[1].left));
+ printf("R %-9.9s ", GNAME(node[1].right));
+ printf("P %9.9s", GNAME(node[0].parent));
+ printf("/%-9.9s ", GNAME(node[1].parent));
+ printf("%s P%d\n", addrname(&stp->dst), stp->printed);
+}
+
+
+void
+buildtab(void)
+{
+ char line[80], *s;
+ tabe_t *tab;
+ int lines;
+ FILE *fp;
+
+ lines = 0;
+ fp = fopen("hosts", "r");
+
+ while (fgets(line, sizeof(line), fp) != NULL) {
+ s = strchr(line, '\n');
+ if (s != NULL)
+ *s = '\0';
+ lines++;
+ if (lines == 1)
+ tab = malloc(sizeof(*tab) * 2);
+ else
+ tab = realloc(tab, (lines + 1) * sizeof(*tab));
+ tab[lines - 1].host = strdup(line);
+ s = strchr(tab[lines - 1].host, '/');
+ *s++ = '\0';
+ tab[lines - 1].mask = s;
+ tab[lines - 1].what = "d";
+ }
+ fclose(fp);
+
+ tab[lines].host = NULL;
+ tab[lines].mask = NULL;
+ tab[lines].what = NULL;
+ ttable = tab;
+}
+
+
+void
+printroots(rnh)
+ ipf_rdx_head_t *rnh;
+{
+ printf("Root.0.%s b %3d p %-9.9s l %-9.9s r %-9.9s\n",
+ GNAME(&rnh->nodes[0]),
+ rnh->nodes[0].index, GNAME(rnh->nodes[0].parent),
+ GNAME(rnh->nodes[0].left), GNAME(rnh->nodes[0].right));
+ printf("Root.1.%s b %3d p %-9.9s l %-9.9s r %-9.9s\n",
+ GNAME(&rnh->nodes[1]),
+ rnh->nodes[1].index, GNAME(rnh->nodes[1].parent),
+ GNAME(rnh->nodes[1].left), GNAME(rnh->nodes[1].right));
+ printf("Root.2.%s b %3d p %-9.9s l %-9.9s r %-9.9s\n",
+ GNAME(&rnh->nodes[2]),
+ rnh->nodes[2].index, GNAME(rnh->nodes[2].parent),
+ GNAME(rnh->nodes[2].left), GNAME(rnh->nodes[2].right));
+}
+
+
+int
+main(int argc, char *argv[])
+{
+ addrfamily_t af;
+ ipf_rdx_head_t *rnh;
+ radix_softc_t *ctx;
+ int j;
+ int i;
+
+ rnh = NULL;
+
+ buildtab();
+ ctx = ipf_rx_create();
+ ipf_rx_init(ctx);
+ ipf_rx_inithead(ctx, &rnh);
+
+ printf("=== ADD-0 ===\n");
+ for (i = 0; ttable[i].host != NULL; i++) {
+ add_addr(rnh, i, i);
+ checktree(rnh);
+ }
+ printroots(rnh);
+ ipf_rx_walktree(rnh, nodeprinter, NULL);
+ printf("=== DELETE-0 ===\n");
+ for (i = 0; ttable[i].host != NULL; i++) {
+ delete_addr(rnh, i);
+ printroots(rnh);
+ ipf_rx_walktree(rnh, nodeprinter, NULL);
+ }
+ printf("=== ADD-1 ===\n");
+ for (i = 0; ttable[i].host != NULL; i++) {
+ setaddr(&af, ttable[i].host);
+ add_addr(rnh, i, i); /*forder[i]); */
+ checktree(rnh);
+ }
+ dumptree(rnh);
+ ipf_rx_walktree(rnh, nodeprinter, NULL);
+ printf("=== TEST-1 ===\n");
+ for (i = 0; ttable[i].host != NULL; i++) {
+ setaddr(&af, ttable[i].host);
+ test_addr(rnh, i, &af, -1);
+ }
+
+ printf("=== TEST-2 ===\n");
+ for (i = 0; mtable[i][0] != NULL; i++) {
+ setaddr(&af, mtable[i][0]);
+ test_addr(rnh, i, &af, -1);
+ }
+ printf("=== DELETE-1 ===\n");
+ for (i = 0; ttable[i].host != NULL; i++) {
+ if (ttable[i].what[0] != 'd')
+ continue;
+ delete_addr(rnh, i);
+ for (j = 0; ttable[j].host != NULL; j++) {
+ setaddr(&af, ttable[j].host);
+ test_addr(rnh, i, &af, 3);
+ }
+ printroots(rnh);
+ ipf_rx_walktree(rnh, nodeprinter, NULL);
+ }
+
+ dumptree(rnh);
+
+ printf("=== ADD-2 ===\n");
+ random_add(rnh);
+ checktree(rnh);
+ dumptree(rnh);
+ ipf_rx_walktree(rnh, nodeprinter, NULL);
+ printf("=== DELETE-2 ===\n");
+ random_delete(rnh);
+ checktree(rnh);
+ dumptree(rnh);
+
+ ipf_rx_walktree(rnh, ipf_rx_freenode, rnh);
+
+ return 0;
+}
+
+
+void
+dumptree(rnh)
+ ipf_rdx_head_t *rnh;
+{
+ myst_t *stp;
+
+ printf("VVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVV\n");
+ printroots(rnh);
+ for (stp = myst_top; stp; stp = stp->next)
+ printnode(stp);
+ printf("^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^\n");
+}
+
+
+void
+test_addr(rnh, pref, addr, limit)
+ ipf_rdx_head_t *rnh;
+ int pref;
+ addrfamily_t *addr;
+{
+ static int extras[14] = { 0, -1, 1, 3, 5, 8, 9,
+ 15, 16, 19, 255, 256, 65535, 65536
+ };
+ ipf_rdx_node_t *rn;
+ addrfamily_t af;
+ char name[80];
+ myst_t *stp;
+ int i;
+
+ memset(&af, 0, sizeof(af));
+#if 0
+ if (limit < 0 || limit > 14)
+ limit = 14;
+
+ for (i = 0; i < limit; i++) {
+ if (ttable[i].host == NULL)
+ break;
+ setaddr(&af, ttable[i].host);
+ printf("%d.%d.LOOKUP(%s)", pref, i, addrname(&af));
+ rn = ipf_rx_match(rnh, &af);
+ stp = (myst_t *)rn;
+ printf(" = %s (%s/%d)\n", GNAME(rn),
+ rn ? addrname(&stp->dst) : "NULL",
+ rn ? rn->maskbitcount : 0);
+ }
+#else
+ printf("%d.%d.LOOKUP(%s)", pref, -1, addrname(addr));
+ rn = ipf_rx_match(rnh, addr);
+ stp = (myst_t *)rn;
+ printf(" = %s (%s/%d)\n", GNAME(rn),
+ rn ? addrname(&stp->dst) : "NULL", rn ? rn->maskbitcount : 0);
+#endif
+}
+
+
+void
+delete_addr(rnh, item)
+ ipf_rdx_head_t *rnh;
+ int item;
+{
+ ipf_rdx_node_t *rn;
+ addrfamily_t mask;
+ addrfamily_t af;
+ myst_t **pstp;
+ myst_t *stp;
+
+ memset(&af, 0, sizeof(af));
+ memset(&mask, 0, sizeof(mask));
+ setaddr(&af, ttable[item].host);
+ mask.adf_family = af.adf_family;
+ setmask(&mask, ttable[item].mask);
+
+ printf("DELETE(%s)\n", addrname(&af));
+ rn = ipf_rx_delete(rnh, &af, &mask);
+ if (rn == NULL) {
+ printf("FAIL LOOKUP DELETE\n");
+ checktree(rnh);
+ for (stp = myst_top; stp != NULL; stp = stp->next)
+ if (stp->printed != -1)
+ stp->printed = -2;
+ ipf_rx_walktree(rnh, nodeprinter, NULL);
+ dumptree(rnh);
+ abort();
+ }
+ printf("%d.delete(%s) = %s\n", item, addrname(&af), GNAME(rn));
+
+ for (pstp = &myst_top; (stp = *pstp) != NULL; pstp = &stp->next)
+ if (stp == (myst_t *)rn)
+ break;
+ stp->printed = -1;
+ stp->nodes[0].parent = &stp->nodes[0];
+ stp->nodes[1].parent = &stp->nodes[1];
+ *pstp = stp->next;
+ free(stp);
+ nodecount--;
+ checktree(rnh);
+}
+
+
+void
+add_addr(rnh, n, item)
+ ipf_rdx_head_t *rnh;
+ int n, item;
+{
+ ipf_rdx_node_t *rn;
+ myst_t *stp;
+
+ stp = calloc(1, sizeof(*stp));
+ rn = (ipf_rdx_node_t *)stp;
+ setaddr(&stp->dst, ttable[item].host);
+ stp->mask.adf_family = stp->dst.adf_family;
+ setmask(&stp->mask, ttable[item].mask);
+ stp->next = myst_top;
+ myst_top = stp;
+ (void) sprintf(rn[0].name, "_BORN.0");
+ (void) sprintf(rn[1].name, "_BORN.1");
+ rn = ipf_rx_addroute(rnh, &stp->dst, &stp->mask, stp->nodes);
+ (void) sprintf(rn[0].name, "%d_NODE.0", item);
+ (void) sprintf(rn[1].name, "%d_NODE.1", item);
+ printf("ADD %d/%d %s/%s\n", n, item, rn[0].name, rn[1].name);
+ nodecount++;
+ checktree(rnh);
+}
+
+
+void
+checktree(ipf_rdx_head_t *head)
+{
+ myst_t *s1;
+ ipf_rdx_node_t *rn;
+
+ if (nodecount <= 1)
+ return;
+
+ for (s1 = myst_top; s1 != NULL; s1 = s1->next) {
+ int fault = 0;
+ if (s1->printed == -1)
+ continue;
+ rn = &s1->nodes[1];
+ if (rn->right->parent != rn)
+ fault |= 1;
+ if (rn->left->parent != rn)
+ fault |= 2;
+ if (rn->parent->left != rn && rn->parent->right != rn)
+ fault |= 4;
+ if (fault != 0) {
+ printf("FAULT %#x %s\n", fault, rn->name);
+ dumptree(head);
+ ipf_rx_walktree(head, nodeprinter, NULL);
+ fflush(stdout);
+ fflush(stderr);
+ printf("--\n");
+ abort();
+ }
+ }
+}
+
+
+int *
+randomize(int *pnitems)
+{
+ int *order;
+ int nitems;
+ int choice;
+ int j;
+ int i;
+
+ nitems = sizeof(ttable) / sizeof(ttable[0]);
+ *pnitems = nitems;
+ order = calloc(nitems, sizeof(*order));
+ srandom(getpid() * time(NULL));
+ memset(order, 0xff, nitems * sizeof(*order));
+ order[21] = 21;
+ for (i = 0; i < nitems - 1; i++) {
+ do {
+ choice = rand() % (nitems - 1);
+ for (j = 0; j < nitems; j++)
+ if (order[j] == choice)
+ break;
+ } while (j != nitems);
+ order[i] = choice;
+ }
+
+ return order;
+}
+
+
+void
+random_add(rnh)
+ ipf_rdx_head_t *rnh;
+{
+ int *order;
+ int nitems;
+ int i;
+
+ order = randomize(&nitems);
+
+ for (i = 0; i < nitems - 1; i++) {
+ add_addr(rnh, i, order[i]);
+ checktree(rnh);
+ }
+}
+
+
+void
+random_delete(rnh)
+ ipf_rdx_head_t *rnh;
+{
+ int *order;
+ int nitems;
+ int i;
+
+ order = randomize(&nitems);
+
+ for (i = 0; i < nitems - 1; i++) {
+ delete_addr(rnh, i);
+ checktree(rnh);
+ }
+}
+#endif /* RDX_DEBUG */
diff --git a/netinet/radix_ipf.h b/netinet/radix_ipf.h
new file mode 100644
index 000000000000..73e66b0aa169
--- /dev/null
+++ b/netinet/radix_ipf.h
@@ -0,0 +1,95 @@
+/*
+ * Copyright (C) 2012 by Darren Reed.
+ *
+ * See the IPFILTER.LICENCE file for details on licencing.
+ */
+#ifndef __RADIX_IPF_H__
+#define __RADIX_IPF_H__
+
+#ifndef U_32_T
+typedef unsigned int u_32_t;
+# define U_32_T 1
+#endif
+
+typedef struct ipf_rdx_mask {
+ struct ipf_rdx_mask *next;
+ struct ipf_rdx_node *node;
+ u_32_t *mask;
+ int maskbitcount;
+} ipf_rdx_mask_t;
+
+typedef struct ipf_rdx_node {
+ struct ipf_rdx_node *left;
+ struct ipf_rdx_node *right;
+ struct ipf_rdx_node *parent;
+ struct ipf_rdx_node *dupkey;
+ struct ipf_rdx_mask *masks;
+ struct ipf_rdx_mask *mymask;
+ u_32_t *addrkey;
+ u_32_t *maskkey;
+ u_32_t *addroff;
+ u_32_t *maskoff;
+ u_32_t lastmask;
+ u_32_t bitmask;
+ int offset;
+ int index;
+ int maskbitcount;
+ int root;
+#ifdef RDX_DEBUG
+ char name[40];
+#endif
+} ipf_rdx_node_t;
+
+struct ipf_rdx_head;
+
+typedef void (* radix_walk_func_t)(ipf_rdx_node_t *, void *);
+typedef ipf_rdx_node_t *(* idx_hamn_func_t)(struct ipf_rdx_head *,
+ addrfamily_t *, addrfamily_t *,
+ ipf_rdx_node_t *);
+typedef ipf_rdx_node_t *(* idx_ham_func_t)(struct ipf_rdx_head *,
+ addrfamily_t *, addrfamily_t *);
+typedef ipf_rdx_node_t *(* idx_ha_func_t)(struct ipf_rdx_head *,
+ addrfamily_t *);
+typedef void (* idx_walk_func_t)(struct ipf_rdx_head *,
+ radix_walk_func_t, void *);
+
+typedef struct ipf_rdx_head {
+ ipf_rdx_node_t *root;
+ ipf_rdx_node_t nodes[3];
+ ipfmutex_t lock;
+ idx_hamn_func_t addaddr; /* add addr/mask to tree */
+ idx_ham_func_t deladdr; /* delete addr/mask from tree */
+ idx_ham_func_t lookup; /* look for specific addr/mask */
+ idx_ha_func_t matchaddr; /* search tree for address match */
+ idx_walk_func_t walktree; /* walk entire tree */
+} ipf_rdx_head_t;
+
+typedef struct radix_softc {
+ u_char *zeros;
+ u_char *ones;
+} radix_softc_t;
+
+#undef RADIX_NODE_HEAD_LOCK
+#undef RADIX_NODE_HEAD_UNLOCK
+#ifdef _KERNEL
+# define RADIX_NODE_HEAD_LOCK(x) MUTEX_ENTER(&(x)->lock)
+# define RADIX_NODE_HEAD_UNLOCK(x) MUTEX_UNLOCK(&(x)->lock)
+#else
+# define RADIX_NODE_HEAD_LOCK(x)
+# define RADIX_NODE_HEAD_UNLOCK(x)
+#endif
+
+extern void *ipf_rx_create __P((void));
+extern int ipf_rx_init __P((void *));
+extern void ipf_rx_destroy __P((void *));
+extern int ipf_rx_inithead __P((radix_softc_t *, ipf_rdx_head_t **));
+extern void ipf_rx_freehead __P((ipf_rdx_head_t *));
+extern ipf_rdx_node_t *ipf_rx_addroute __P((ipf_rdx_head_t *,
+ addrfamily_t *, addrfamily_t *,
+ ipf_rdx_node_t *));
+extern ipf_rdx_node_t *ipf_rx_delete __P((ipf_rdx_head_t *, addrfamily_t *,
+ addrfamily_t *));
+extern void ipf_rx_walktree __P((ipf_rdx_head_t *, radix_walk_func_t,
+ void *));
+
+#endif /* __RADIX_IPF_H__ */