git: 9a563c5e484b - main - ipfilter: radix_ipf is a kernel source file

From: Cy Schubert <cy_at_FreeBSD.org>
Date: Tue, 14 Dec 2021 14:20:15 UTC
The branch main has been updated by cy:

URL: https://cgit.FreeBSD.org/src/commit/?id=9a563c5e484b077d8e689e9ab3f6f4797e47e576

commit 9a563c5e484b077d8e689e9ab3f6f4797e47e576
Author:     Cy Schubert <cy@FreeBSD.org>
AuthorDate: 2021-12-13 21:35:43 +0000
Commit:     Cy Schubert <cy@FreeBSD.org>
CommitDate: 2021-12-14 14:19:21 +0000

    ipfilter: radix_ipf is a kernel source file
    
    Remove duplicate radix_ipf.* files. They live in sys/.
    
    MFC after:      1 week
---
 contrib/ipfilter/radix_ipf.c | 1528 ------------------------------------------
 contrib/ipfilter/radix_ipf.h |   97 ---
 2 files changed, 1625 deletions(-)

diff --git a/contrib/ipfilter/radix_ipf.c b/contrib/ipfilter/radix_ipf.c
deleted file mode 100644
index 4b3804478527..000000000000
--- a/contrib/ipfilter/radix_ipf.c
+++ /dev/null
@@ -1,1528 +0,0 @@
-/*
- * 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(ipf_rdx_head_t *,
-					  ipf_rdx_node_t nodes[2], int *);
-static void ipf_rx_attach_mask(ipf_rdx_node_t *, ipf_rdx_mask_t *);
-static int count_mask_bits(addrfamily_t *, u_32_t **);
-static void buildnodes(addrfamily_t *, addrfamily_t *,
-			    ipf_rdx_node_t n[2]);
-static ipf_rdx_node_t *ipf_rx_find_addr(ipf_rdx_node_t *, u_32_t *);
-static ipf_rdx_node_t *ipf_rx_lookup(ipf_rdx_head_t *, addrfamily_t *,
-					  addrfamily_t *);
-static ipf_rdx_node_t *ipf_rx_match(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" },
*** 670 LINES SKIPPED ***