git: 6802e5f783c3 - stable/13 - ipfilter: radix_ipf is a kernel source file
- Go to: [ bottom of page ] [ top of archives ] [ this month ]
Date: Tue, 21 Dec 2021 23:35:23 UTC
The branch stable/13 has been updated by cy:
URL: https://cgit.FreeBSD.org/src/commit/?id=6802e5f783c3a58a25c212ee750f90f4e055aa33
commit 6802e5f783c3a58a25c212ee750f90f4e055aa33
Author: Cy Schubert <cy@FreeBSD.org>
AuthorDate: 2021-12-13 21:35:43 +0000
Commit: Cy Schubert <cy@FreeBSD.org>
CommitDate: 2021-12-21 23:34:40 +0000
ipfilter: radix_ipf is a kernel source file
Remove duplicate radix_ipf.* files. They live in sys/.
(cherry picked from commit 9a563c5e484b077d8e689e9ab3f6f4797e47e576)
---
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 ***