diff options
| -rw-r--r-- | netinet/ip_dstlist.c | 1351 | ||||
| -rw-r--r-- | netinet/ip_dstlist.h | 68 | ||||
| -rw-r--r-- | netinet/ipf_rb.h | 364 | ||||
| -rw-r--r-- | netinet/radix_ipf.c | 1528 | ||||
| -rw-r--r-- | netinet/radix_ipf.h | 95 |
5 files changed, 3406 insertions, 0 deletions
diff --git a/netinet/ip_dstlist.c b/netinet/ip_dstlist.c new file mode 100644 index 0000000..ce2e72e --- /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 0000000..e2885e5 --- /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 0000000..3d7a59d --- /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 0000000..f145c38 --- /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 0000000..73e66b0 --- /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__ */ |
