From nobody Tue Dec 14 14:20:15 2021 X-Original-To: dev-commits-src-all@mlmmj.nyi.freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2610:1c1:1:606c::19:1]) by mlmmj.nyi.freebsd.org (Postfix) with ESMTP id 7948018EB916; Tue, 14 Dec 2021 14:20:17 +0000 (UTC) (envelope-from git@FreeBSD.org) Received: from mxrelay.nyi.freebsd.org (mxrelay.nyi.freebsd.org [IPv6:2610:1c1:1:606c::19:3]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (4096 bits) server-digest SHA256 client-signature RSA-PSS (4096 bits) client-digest SHA256) (Client CN "mxrelay.nyi.freebsd.org", Issuer "R3" (verified OK)) by mx1.freebsd.org (Postfix) with ESMTPS id 4JD0rw2QZMz4mJ1; Tue, 14 Dec 2021 14:20:16 +0000 (UTC) (envelope-from git@FreeBSD.org) Received: from gitrepo.freebsd.org (gitrepo.freebsd.org [IPv6:2610:1c1:1:6068::e6a:5]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (4096 bits) server-digest SHA256) (Client did not present a certificate) by mxrelay.nyi.freebsd.org (Postfix) with ESMTPS id 16D051A8A; Tue, 14 Dec 2021 14:20:16 +0000 (UTC) (envelope-from git@FreeBSD.org) Received: from gitrepo.freebsd.org ([127.0.1.44]) by gitrepo.freebsd.org (8.16.1/8.16.1) with ESMTP id 1BEEKGLs000300; Tue, 14 Dec 2021 14:20:16 GMT (envelope-from git@gitrepo.freebsd.org) Received: (from git@localhost) by gitrepo.freebsd.org (8.16.1/8.16.1/Submit) id 1BEEKF00000288; Tue, 14 Dec 2021 14:20:15 GMT (envelope-from git) Date: Tue, 14 Dec 2021 14:20:15 GMT Message-Id: <202112141420.1BEEKF00000288@gitrepo.freebsd.org> To: src-committers@FreeBSD.org, dev-commits-src-all@FreeBSD.org, dev-commits-src-main@FreeBSD.org From: Cy Schubert Subject: git: 9a563c5e484b - main - ipfilter: radix_ipf is a kernel source file List-Id: Commit messages for all branches of the src repository List-Archive: https://lists.freebsd.org/archives/dev-commits-src-all List-Help: List-Post: List-Subscribe: List-Unsubscribe: Sender: owner-dev-commits-src-all@freebsd.org X-BeenThere: dev-commits-src-all@freebsd.org MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: 8bit X-Git-Committer: cy X-Git-Repository: src X-Git-Refname: refs/heads/main X-Git-Reftype: branch X-Git-Commit: 9a563c5e484b077d8e689e9ab3f6f4797e47e576 Auto-Submitted: auto-generated ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=freebsd.org; s=dkim; t=1639491616; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:mime-version:mime-version:content-type:content-type: content-transfer-encoding:content-transfer-encoding; bh=2gGC1EQorVeeVAa6zXOSesvZNISzRZfwG+roJjKpJnQ=; b=T+CB4p0KpcJ9Bya8bq7OhjZYZoSGn79hja1Wi+l9p1VFk1t+jYRXkC3/JHTCaRErN5SkKp wKxc0qMuvLB+3NAe7voOAuvm4nOF57To5lvLbP2u/HZ0FT4GF5Ov6CsVbfzQ/R4Kpss7CY vG9UHDLX+WJxE1XeEow9wD+S2dZcR+0ElhB5XZqQGuXUifHVUOrQlw7J86I+OFQ/1Wvkms Ygz+cItoShiCdFvEfdlL0SsjuEzJ/uSBM1WfZTOrGOI1uQXseoQA1JB8uo5SRUIEgWy4G5 4WWFkevGbhVkhGPoDt0EiMfLst6+PrZ/C9eR0h6MkXj3vu9U5v+O9/9aZQjURw== ARC-Seal: i=1; s=dkim; d=freebsd.org; t=1639491616; a=rsa-sha256; cv=none; b=MxVop72K9rERejQYKAFAbKKuGnXZFtRffxcT2eeil5+/5CL9Six0m6lLoCKB/qPSmeZuic /hhN5UZ/sP8hPVyfj/DvsfADY/wsOhmGItzkKFQxPaTifx6AP6UNICZ6ObrC9d+LpWm3HZ gL74cBpdzjlC5nhiZvYg1WMG668rSeLIlfqHxA2yGJX/8megFG/p7V/zvogM04xMAQUmpO JNmJyLeSmbmqlX6I4KToNac1DJydNQ1a5KdNBaXGwz0qmoZqrO1si6KTy5BeGs9BPiQpN3 iRzKnUoEOEu78sF0YiU/B4/NhwrC1B3YtqnmShUUah/pqZGP6w2se2C9bPonpw== ARC-Authentication-Results: i=1; mx1.freebsd.org; none X-ThisMailContainsUnwantedMimeParts: N The branch main has been updated by cy: URL: https://cgit.FreeBSD.org/src/commit/?id=9a563c5e484b077d8e689e9ab3f6f4797e47e576 commit 9a563c5e484b077d8e689e9ab3f6f4797e47e576 Author: Cy Schubert AuthorDate: 2021-12-13 21:35:43 +0000 Commit: Cy Schubert 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 -#include -#include -#include -#include -#include -#if !defined(_KERNEL) -# include -# include -# include -# include -#endif -#include "netinet/ip_compat.h" -#include "netinet/ip_fil.h" -#ifdef RDX_DEBUG -# include -# include -# include -#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 ***