radix.c revision c793af95640863cd29868fc7c419c5d2496b207b
c793af95640863cd29868fc7c419c5d2496b207bsangeeta * Copyright 2006 Sun Microsystems, Inc. All rights reserved.
c793af95640863cd29868fc7c419c5d2496b207bsangeeta * Use is subject to license terms.
c793af95640863cd29868fc7c419c5d2496b207bsangeeta * Copyright (c) 1988, 1989, 1993
c793af95640863cd29868fc7c419c5d2496b207bsangeeta * The Regents of the University of California. All rights reserved.
c793af95640863cd29868fc7c419c5d2496b207bsangeeta * Redistribution and use in source and binary forms, with or without
c793af95640863cd29868fc7c419c5d2496b207bsangeeta * modification, are permitted provided that the following conditions
c793af95640863cd29868fc7c419c5d2496b207bsangeeta * 1. Redistributions of source code must retain the above copyright
c793af95640863cd29868fc7c419c5d2496b207bsangeeta * notice, this list of conditions and the following disclaimer.
c793af95640863cd29868fc7c419c5d2496b207bsangeeta * 2. Redistributions in binary form must reproduce the above copyright
c793af95640863cd29868fc7c419c5d2496b207bsangeeta * notice, this list of conditions and the following disclaimer in the
c793af95640863cd29868fc7c419c5d2496b207bsangeeta * documentation and/or other materials provided with the distribution.
c793af95640863cd29868fc7c419c5d2496b207bsangeeta * 4. Neither the name of the University nor the names of its contributors
c793af95640863cd29868fc7c419c5d2496b207bsangeeta * may be used to endorse or promote products derived from this software
c793af95640863cd29868fc7c419c5d2496b207bsangeeta * without specific prior written permission.
c793af95640863cd29868fc7c419c5d2496b207bsangeeta * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
c793af95640863cd29868fc7c419c5d2496b207bsangeeta * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
c793af95640863cd29868fc7c419c5d2496b207bsangeeta * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
c793af95640863cd29868fc7c419c5d2496b207bsangeeta * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
c793af95640863cd29868fc7c419c5d2496b207bsangeeta * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
c793af95640863cd29868fc7c419c5d2496b207bsangeeta * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
c793af95640863cd29868fc7c419c5d2496b207bsangeeta * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
c793af95640863cd29868fc7c419c5d2496b207bsangeeta * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
c793af95640863cd29868fc7c419c5d2496b207bsangeeta * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
c793af95640863cd29868fc7c419c5d2496b207bsangeeta * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
c793af95640863cd29868fc7c419c5d2496b207bsangeeta * SUCH DAMAGE.
c793af95640863cd29868fc7c419c5d2496b207bsangeeta * @(#)radix.c 8.5 (Berkeley) 5/19/95
c793af95640863cd29868fc7c419c5d2496b207bsangeeta * $FreeBSD: /repoman/r/ncvs/src/sys/net/radix.c,v 1.36.2.1 2005/01/31 23:26:23
c793af95640863cd29868fc7c419c5d2496b207bsangeeta * imp Exp $
c793af95640863cd29868fc7c419c5d2496b207bsangeeta#pragma ident "%Z%%M% %I% %E% SMI"
c793af95640863cd29868fc7c419c5d2496b207bsangeeta * Routines to build and maintain radix trees for routing lookups.
c793af95640863cd29868fc7c419c5d2496b207bsangeeta#endif /* _KERNEL */
c793af95640863cd29868fc7c419c5d2496b207bsangeeta#endif /* _KERNEL */
c793af95640863cd29868fc7c419c5d2496b207bsangeetastatic int rn_walktree(struct radix_node_head *, walktree_f_t *, void *);
c793af95640863cd29868fc7c419c5d2496b207bsangeeta *rn_insert(void *, struct radix_node_head *, int *,
c793af95640863cd29868fc7c419c5d2496b207bsangeeta *rn_lookup(void *, void *, struct radix_node_head *),
c793af95640863cd29868fc7c419c5d2496b207bsangeeta *rn_match_args(void *, struct radix_node_head *, match_leaf_t *,
c793af95640863cd29868fc7c419c5d2496b207bsangeeta *rn_addmask(void *, int, int),
c793af95640863cd29868fc7c419c5d2496b207bsangeeta *rn_addroute(void *, void *, struct radix_node_head *,
c793af95640863cd29868fc7c419c5d2496b207bsangeeta *rn_delete(void *, void *, struct radix_node_head *);
c793af95640863cd29868fc7c419c5d2496b207bsangeetastatic struct kmem_cache *radix_mask_cache; /* for rn_mkfreelist */
c793af95640863cd29868fc7c419c5d2496b207bsangeetastatic char *radix_mask_cache, *radix_node_cache; /* dummy vars. never inited */
c793af95640863cd29868fc7c419c5d2496b207bsangeeta#endif /* _KERNEL */
c793af95640863cd29868fc7c419c5d2496b207bsangeeta * Work area -- the following point to 2 buffers of size max_keylen,
c793af95640863cd29868fc7c419c5d2496b207bsangeeta * allocated in this order in a block of memory malloc'ed by rn_init.
c793af95640863cd29868fc7c419c5d2496b207bsangeeta * A third buffer of size MAX_KEYLEN is allocated from the stack.
c793af95640863cd29868fc7c419c5d2496b207bsangeeta#define MKGet(m) R_Malloc(m, radix_mask_cache, sizeof (struct radix_mask))
c793af95640863cd29868fc7c419c5d2496b207bsangeetastatic boolean_t rn_lexobetter(void *m_arg, void *n_arg);
c793af95640863cd29868fc7c419c5d2496b207bsangeetastatic struct radix_mask *
c793af95640863cd29868fc7c419c5d2496b207bsangeeta rn_satisfies_leaf(char *trial, struct radix_node *leaf,
c793af95640863cd29868fc7c419c5d2496b207bsangeeta int skip, match_leaf_t *rn_leaf_fn, void *rn_leaf_arg);
c793af95640863cd29868fc7c419c5d2496b207bsangeeta#define RN_MATCHF(rn, f, arg) (f == NULL || (*f)((rn), arg))
c793af95640863cd29868fc7c419c5d2496b207bsangeeta * The data structure for the keys is a radix tree with one way
c793af95640863cd29868fc7c419c5d2496b207bsangeeta * branching removed. The index rn_bit at an internal node n represents a bit
c793af95640863cd29868fc7c419c5d2496b207bsangeeta * position to be tested. The tree is arranged so that all descendants
c793af95640863cd29868fc7c419c5d2496b207bsangeeta * of a node n have keys whose bits all agree up to position rn_bit - 1.
c793af95640863cd29868fc7c419c5d2496b207bsangeeta * (We say the index of n is rn_bit.)
c793af95640863cd29868fc7c419c5d2496b207bsangeeta * There is at least one descendant which has a one bit at position rn_bit,
c793af95640863cd29868fc7c419c5d2496b207bsangeeta * and at least one with a zero there.
c793af95640863cd29868fc7c419c5d2496b207bsangeeta * A route is determined by a pair of key and mask. We require that the
c793af95640863cd29868fc7c419c5d2496b207bsangeeta * bit-wise logical and of the key and mask to be the key.
c793af95640863cd29868fc7c419c5d2496b207bsangeeta * We define the index of a route associated with the mask to be
c793af95640863cd29868fc7c419c5d2496b207bsangeeta * the first bit number in the mask where 0 occurs (with bit number 0
c793af95640863cd29868fc7c419c5d2496b207bsangeeta * representing the highest order bit).
c793af95640863cd29868fc7c419c5d2496b207bsangeeta * We say a mask is normal if every bit is 0, past the index of the mask.
c793af95640863cd29868fc7c419c5d2496b207bsangeeta * If a node n has a descendant (k, m) with index(m) == index(n) == rn_bit,
c793af95640863cd29868fc7c419c5d2496b207bsangeeta * and m is a normal mask, then the route applies to every descendant of n.
c793af95640863cd29868fc7c419c5d2496b207bsangeeta * If the index(m) < rn_bit, this implies the trailing last few bits of k
c793af95640863cd29868fc7c419c5d2496b207bsangeeta * before bit b are all 0, (and hence consequently true of every descendant
c793af95640863cd29868fc7c419c5d2496b207bsangeeta * of n), so the route applies to all descendants of the node as well.
c793af95640863cd29868fc7c419c5d2496b207bsangeeta * Similar logic shows that a non-normal mask m such that
c793af95640863cd29868fc7c419c5d2496b207bsangeeta * index(m) <= index(n) could potentially apply to many children of n.
c793af95640863cd29868fc7c419c5d2496b207bsangeeta * Thus, for each non-host route, we attach its mask to a list at an internal
c793af95640863cd29868fc7c419c5d2496b207bsangeeta * node as high in the tree as we can go.
c793af95640863cd29868fc7c419c5d2496b207bsangeeta * The present version of the code makes use of normal routes in short-
c793af95640863cd29868fc7c419c5d2496b207bsangeeta * circuiting an explict mask and compare operation when testing whether
c793af95640863cd29868fc7c419c5d2496b207bsangeeta * a key satisfies a normal route, and also in remembering the unique leaf
c793af95640863cd29868fc7c419c5d2496b207bsangeeta * that governs a subtree.
c793af95640863cd29868fc7c419c5d2496b207bsangeeta * Most of the functions in this code assume that the key/mask arguments
c793af95640863cd29868fc7c419c5d2496b207bsangeeta * are sockaddr-like structures, where the first byte is an uchar_t
c793af95640863cd29868fc7c419c5d2496b207bsangeeta * indicating the size of the entire structure.
c793af95640863cd29868fc7c419c5d2496b207bsangeeta * To make the assumption more explicit, we use the LEN() macro to access
c793af95640863cd29868fc7c419c5d2496b207bsangeeta * this field. It is safe to pass an expression with side effects
c793af95640863cd29868fc7c419c5d2496b207bsangeeta * to LEN() as the argument is evaluated only once.
c793af95640863cd29868fc7c419c5d2496b207bsangeeta * Search a node in the tree matching the key.
c793af95640863cd29868fc7c419c5d2496b207bsangeetastatic struct radix_node *
c793af95640863cd29868fc7c419c5d2496b207bsangeeta return (x);
c793af95640863cd29868fc7c419c5d2496b207bsangeeta * Same as above, but with an additional mask.
c793af95640863cd29868fc7c419c5d2496b207bsangeetastatic struct radix_node *
c793af95640863cd29868fc7c419c5d2496b207bsangeeta return (x);
c793af95640863cd29868fc7c419c5d2496b207bsangeeta * Returns true if there are no bits set in n_arg that are zero in
c793af95640863cd29868fc7c419c5d2496b207bsangeeta * m_arg and the masks aren't equal. In other words, it returns true
c793af95640863cd29868fc7c419c5d2496b207bsangeeta * when m_arg is a finer-granularity netmask -- it represents a subset
c793af95640863cd29868fc7c419c5d2496b207bsangeeta * of the destinations implied by n_arg.
c793af95640863cd29868fc7c419c5d2496b207bsangeeta while (n < lim) {
c793af95640863cd29868fc7c419c5d2496b207bsangeeta if (*n & ~(*m))
c793af95640863cd29868fc7c419c5d2496b207bsangeeta return (0);
c793af95640863cd29868fc7c419c5d2496b207bsangeeta if (*n++ != *m++)
c793af95640863cd29868fc7c419c5d2496b207bsangeeta while (n < lim2)
c793af95640863cd29868fc7c419c5d2496b207bsangeetastatic struct radix_node *
c793af95640863cd29868fc7c419c5d2496b207bsangeeta x = rn_addmask(m_arg, 1, head->rnh_treetop->rn_offset);
c793af95640863cd29868fc7c419c5d2496b207bsangeeta return (x);
c793af95640863cd29868fc7c419c5d2496b207bsangeeta * Returns true if address 'trial' has no bits differing from the
c793af95640863cd29868fc7c419c5d2496b207bsangeeta * leaf's key when compared under the leaf's mask. In other words,
c793af95640863cd29868fc7c419c5d2496b207bsangeeta * returns true when 'trial' matches leaf.
c793af95640863cd29868fc7c419c5d2496b207bsangeeta * In addition, if a rn_leaf_fn is passed in, that is used to find
c793af95640863cd29868fc7c419c5d2496b207bsangeeta * a match on conditions defined by the caller of rn_match. This is
c793af95640863cd29868fc7c419c5d2496b207bsangeeta * used by the kernel ftable to match on IRE_MATCH_* conditions.
c793af95640863cd29868fc7c419c5d2496b207bsangeetarn_satisfies_leaf(trial, leaf, skip, rn_leaf_fn, rn_leaf_arg)
c793af95640863cd29868fc7c419c5d2496b207bsangeeta char *cp = trial, *cp2 = leaf->rn_key, *cp3 = leaf->rn_mask;
c793af95640863cd29868fc7c419c5d2496b207bsangeetastatic struct radix_node *
c793af95640863cd29868fc7c419c5d2496b207bsangeetastatic struct radix_node *
c793af95640863cd29868fc7c419c5d2496b207bsangeeta int off = t->rn_offset, vlen = LEN(cp), matched_off;
c793af95640863cd29868fc7c419c5d2496b207bsangeeta * Open code rn_search(v, top) to avoid overhead of extra
c793af95640863cd29868fc7c419c5d2496b207bsangeeta * subroutine call.
c793af95640863cd29868fc7c419c5d2496b207bsangeeta for (; t->rn_bit >= 0; ) {
c793af95640863cd29868fc7c419c5d2496b207bsangeeta * See if we match exactly as a host destination
c793af95640863cd29868fc7c419c5d2496b207bsangeeta * or at least learn how many bits match, for normal mask finesse.
c793af95640863cd29868fc7c419c5d2496b207bsangeeta * It doesn't hurt us to limit how many bytes to check
c793af95640863cd29868fc7c419c5d2496b207bsangeeta * to the length of the mask, since if it matches we had a genuine
c793af95640863cd29868fc7c419c5d2496b207bsangeeta * match and the leaf we have is the most specific one anyway;
c793af95640863cd29868fc7c419c5d2496b207bsangeeta * if it didn't match with a shorter length it would fail
c793af95640863cd29868fc7c419c5d2496b207bsangeeta * with a long one. This wins big for class B&C netmasks which
c793af95640863cd29868fc7c419c5d2496b207bsangeeta * are probably the most common case...
c793af95640863cd29868fc7c419c5d2496b207bsangeeta cp += off; cp2 = t->rn_key + off; cplim = v + vlen;
c793af95640863cd29868fc7c419c5d2496b207bsangeeta * This extra grot is in case we are explicitly asked
c793af95640863cd29868fc7c419c5d2496b207bsangeeta * to look up the default. Ugh!
c793af95640863cd29868fc7c419c5d2496b207bsangeeta * Never return the root node itself, it seems to cause a
c793af95640863cd29868fc7c419c5d2496b207bsangeeta * lot of confusion.
c793af95640863cd29868fc7c419c5d2496b207bsangeeta if (t == NULL || RN_MATCHF(t, rn_leaf_fn, rn_leaf_arg)) {
c793af95640863cd29868fc7c419c5d2496b207bsangeeta return (t);
c793af95640863cd29868fc7c419c5d2496b207bsangeeta * Although we found an exact match on the key, rn_leaf_fn
c793af95640863cd29868fc7c419c5d2496b207bsangeeta * is looking for some other criteria as well. Continue
c793af95640863cd29868fc7c419c5d2496b207bsangeeta * looking as if the exact match failed.
c793af95640863cd29868fc7c419c5d2496b207bsangeeta /* hit the top. have to give up */
c793af95640863cd29868fc7c419c5d2496b207bsangeeta test = (*cp ^ *cp2) & 0xff; /* find first bit that differs */
c793af95640863cd29868fc7c419c5d2496b207bsangeeta * If there is a host route in a duped-key chain, it will be first.
c793af95640863cd29868fc7c419c5d2496b207bsangeeta * Even if we don't match exactly as a host,
c793af95640863cd29868fc7c419c5d2496b207bsangeeta * we may match if the leaf we wound up at is
c793af95640863cd29868fc7c419c5d2496b207bsangeeta * a route to a net.
c793af95640863cd29868fc7c419c5d2496b207bsangeeta return (t);
c793af95640863cd29868fc7c419c5d2496b207bsangeeta } else if (rn_satisfies_leaf(v, t, matched_off, rn_leaf_fn,
c793af95640863cd29868fc7c419c5d2496b207bsangeeta return (t);
c793af95640863cd29868fc7c419c5d2496b207bsangeeta /* start searching up the tree */
c793af95640863cd29868fc7c419c5d2496b207bsangeeta * If non-contiguous masks ever become important
c793af95640863cd29868fc7c419c5d2496b207bsangeeta * we can restore the masking and open coding of
c793af95640863cd29868fc7c419c5d2496b207bsangeeta * the search and satisfaction test and put the
c793af95640863cd29868fc7c419c5d2496b207bsangeeta * calculation of "off" back before the "do".
c793af95640863cd29868fc7c419c5d2496b207bsangeeta while (m) {
c793af95640863cd29868fc7c419c5d2496b207bsangeeta return (m->rm_leaf);
c793af95640863cd29868fc7c419c5d2496b207bsangeeta return (x);
c793af95640863cd29868fc7c419c5d2496b207bsangeeta } while (t != top);
c793af95640863cd29868fc7c419c5d2496b207bsangeeta return (0);
c793af95640863cd29868fc7c419c5d2496b207bsangeeta * Whenever we add a new leaf to the tree, we also add a parent node,
c793af95640863cd29868fc7c419c5d2496b207bsangeeta * so we allocate them as an array of two elements: the first one must be
c793af95640863cd29868fc7c419c5d2496b207bsangeeta * the leaf (see RNTORT() in route.c), the second one is the parent.
c793af95640863cd29868fc7c419c5d2496b207bsangeeta * This routine initializes the relevant fields of the nodes, so that
c793af95640863cd29868fc7c419c5d2496b207bsangeeta * the leaf is the left child of the parent node, and both nodes have
c793af95640863cd29868fc7c419c5d2496b207bsangeeta * (almost) all all fields filled as appropriate.
c793af95640863cd29868fc7c419c5d2496b207bsangeeta * The function returns a pointer to the parent node.
c793af95640863cd29868fc7c419c5d2496b207bsangeetastatic struct radix_node *
c793af95640863cd29868fc7c419c5d2496b207bsangeeta * t->rn_parent, r->rn_right, tt->rn_mask, tt->rn_dupedkey
c793af95640863cd29868fc7c419c5d2496b207bsangeeta * and tt->rn_bmask must have been zeroed by caller.
c793af95640863cd29868fc7c419c5d2496b207bsangeeta return (t);
c793af95640863cd29868fc7c419c5d2496b207bsangeetastatic struct radix_node *
c793af95640863cd29868fc7c419c5d2496b207bsangeeta * Find first bit at which v and t->rn_key differ
c793af95640863cd29868fc7c419c5d2496b207bsangeeta return (t);
c793af95640863cd29868fc7c419c5d2496b207bsangeeta } while (b > (unsigned)x->rn_bit);
c793af95640863cd29868fc7c419c5d2496b207bsangeeta /* x->rn_bit < b && x->rn_bit >= 0 */
c793af95640863cd29868fc7c419c5d2496b207bsangeetastatic struct radix_node *
c793af95640863cd29868fc7c419c5d2496b207bsangeeta int b = 0, mlen, j;
c793af95640863cd29868fc7c419c5d2496b207bsangeeta bcopy(netmask + skip, addmask_key + skip, mlen - skip);
c793af95640863cd29868fc7c419c5d2496b207bsangeeta * Trim trailing zeroes.
c793af95640863cd29868fc7c419c5d2496b207bsangeeta for (cp = addmask_key + mlen; (cp > addmask_key) && cp[-1] == 0; )
c793af95640863cd29868fc7c419c5d2496b207bsangeeta return (x);
c793af95640863cd29868fc7c419c5d2496b207bsangeeta R_Zalloc(x, radix_node_cache, max_keylen + 2 * sizeof (*x));
c793af95640863cd29868fc7c419c5d2496b207bsangeeta if ((saved_x = x) == 0)
c793af95640863cd29868fc7c419c5d2496b207bsangeeta return (0);
c793af95640863cd29868fc7c419c5d2496b207bsangeeta x = rn_insert(cp, mask_rnhead, &maskduplicated, x);
c793af95640863cd29868fc7c419c5d2496b207bsangeeta cmn_err(CE_WARN, "rn_addmask: mask impossibly already in tree");
c793af95640863cd29868fc7c419c5d2496b207bsangeeta syslog(LOG_ERR, "rn_addmask: mask impossibly already in tree");
c793af95640863cd29868fc7c419c5d2496b207bsangeeta#endif /* _KERNEL */
c793af95640863cd29868fc7c419c5d2496b207bsangeeta return (x);
c793af95640863cd29868fc7c419c5d2496b207bsangeeta * Calculate index of mask, and check for normalcy.
c793af95640863cd29868fc7c419c5d2496b207bsangeeta * First find the first byte with a 0 bit, then if there are
c793af95640863cd29868fc7c419c5d2496b207bsangeeta * more bits left (remember we already trimmed the trailing 0's),
c793af95640863cd29868fc7c419c5d2496b207bsangeeta * the pattern must be one of those in normal_chars[], or we have
c793af95640863cd29868fc7c419c5d2496b207bsangeeta * a non-contiguous mask.
c793af95640863cd29868fc7c419c5d2496b207bsangeeta for (cp = netmask + skip; (cp < cplim) && *(uchar_t *)cp == 0xff; )
c793af95640863cd29868fc7c419c5d2496b207bsangeeta 0, 0x80, 0xc0, 0xe0, 0xf0, 0xf8, 0xfc, 0xfe, 0xff};
c793af95640863cd29868fc7c419c5d2496b207bsangeeta return (x);
c793af95640863cd29868fc7c419c5d2496b207bsangeeta/* arbitrary ordering for non-contiguous masks */
c793af95640863cd29868fc7c419c5d2496b207bsangeeta /* not really, but need to check longer one first */
c793af95640863cd29868fc7c419c5d2496b207bsangeetastatic struct radix_mask *
c793af95640863cd29868fc7c419c5d2496b207bsangeeta if (m == 0) {
c793af95640863cd29868fc7c419c5d2496b207bsangeeta#endif /* _KERNEL */
c793af95640863cd29868fc7c419c5d2496b207bsangeeta return (0);
c793af95640863cd29868fc7c419c5d2496b207bsangeeta bzero(m, sizeof (*m));
c793af95640863cd29868fc7c419c5d2496b207bsangeeta return (m);
c793af95640863cd29868fc7c419c5d2496b207bsangeetastatic struct radix_node *
c793af95640863cd29868fc7c419c5d2496b207bsangeeta caddr_t v = (caddr_t)v_arg, netmask = (caddr_t)n_arg;
c793af95640863cd29868fc7c419c5d2496b207bsangeeta struct radix_node *saved_tt, *top = head->rnh_treetop;
c793af95640863cd29868fc7c419c5d2496b207bsangeeta short b = 0, b_leaf = 0;
c793af95640863cd29868fc7c419c5d2496b207bsangeeta * In dealing with non-contiguous masks, there may be
c793af95640863cd29868fc7c419c5d2496b207bsangeeta * many different routes which have the same mask.
c793af95640863cd29868fc7c419c5d2496b207bsangeeta * We will find it useful to have a unique pointer to
c793af95640863cd29868fc7c419c5d2496b207bsangeeta * the mask to speed avoiding duplicate references at
c793af95640863cd29868fc7c419c5d2496b207bsangeeta * nodes and possibly save time in calculating indices.
c793af95640863cd29868fc7c419c5d2496b207bsangeeta if ((x = rn_addmask(netmask, 0, top->rn_offset)) == 0)
c793af95640863cd29868fc7c419c5d2496b207bsangeeta return (0);
c793af95640863cd29868fc7c419c5d2496b207bsangeeta * Deal with duplicated keys: attach node to previous instance
c793af95640863cd29868fc7c419c5d2496b207bsangeeta saved_tt = tt = rn_insert(v, head, &keyduplicated, treenodes);
c793af95640863cd29868fc7c419c5d2496b207bsangeeta return (0);
c793af95640863cd29868fc7c419c5d2496b207bsangeeta /* index (netmask) > node */
c793af95640863cd29868fc7c419c5d2496b207bsangeeta * If the mask is not duplicated, we wouldn't
c793af95640863cd29868fc7c419c5d2496b207bsangeeta * find it among possible duplicate key entries
c793af95640863cd29868fc7c419c5d2496b207bsangeeta * anyway, so the above test doesn't hurt.
c793af95640863cd29868fc7c419c5d2496b207bsangeeta * We sort the masks for a duplicated key the same way as
c793af95640863cd29868fc7c419c5d2496b207bsangeeta * in a masklist -- most specific to least specific.
c793af95640863cd29868fc7c419c5d2496b207bsangeeta * This may require the unfortunate nuisance of relocating
c793af95640863cd29868fc7c419c5d2496b207bsangeeta * the head of the list.
c793af95640863cd29868fc7c419c5d2496b207bsangeeta * We also reverse, or doubly link the list through the
c793af95640863cd29868fc7c419c5d2496b207bsangeeta * parent pointer.
c793af95640863cd29868fc7c419c5d2496b207bsangeeta /* link in at head of list */
c793af95640863cd29868fc7c419c5d2496b207bsangeeta if (x->rn_left == t)
c793af95640863cd29868fc7c419c5d2496b207bsangeeta /* Set rn_parent value for tt and tt->rn_dupedkey */
c793af95640863cd29868fc7c419c5d2496b207bsangeeta * Put mask in tree.
c793af95640863cd29868fc7c419c5d2496b207bsangeeta /* Promote general routes from below */
c793af95640863cd29868fc7c419c5d2496b207bsangeeta if (x->rn_bit < 0) {
c793af95640863cd29868fc7c419c5d2496b207bsangeeta if (x->rn_mask && (x->rn_bit >= b_leaf) && x->rn_mklist == 0) {
c793af95640863cd29868fc7c419c5d2496b207bsangeeta } else if (x->rn_mklist) {
c793af95640863cd29868fc7c419c5d2496b207bsangeeta * Skip over masks whose index is > that of new node
c793af95640863cd29868fc7c419c5d2496b207bsangeeta for (mp = &x->rn_mklist; (m = *mp) != NULL; mp = &m->rm_mklist)
c793af95640863cd29868fc7c419c5d2496b207bsangeeta /* Add new route to highest possible ancestor's list */
c793af95640863cd29868fc7c419c5d2496b207bsangeeta * Search through routes associated with node to
c793af95640863cd29868fc7c419c5d2496b207bsangeeta * insert new route according to index.
c793af95640863cd29868fc7c419c5d2496b207bsangeeta * Need same criteria as when sorting dupedkeys to avoid
c793af95640863cd29868fc7c419c5d2496b207bsangeeta * double loop on deletion.
c793af95640863cd29868fc7c419c5d2496b207bsangeeta for (mp = &x->rn_mklist; (m = *mp) != NULL; mp = &m->rm_mklist) {
c793af95640863cd29868fc7c419c5d2496b207bsangeeta "mask not entered\n");
c793af95640863cd29868fc7c419c5d2496b207bsangeeta "mask not entered\n");
c793af95640863cd29868fc7c419c5d2496b207bsangeeta#endif /* _KERNEL */
c793af95640863cd29868fc7c419c5d2496b207bsangeetastatic struct radix_node *
c793af95640863cd29868fc7c419c5d2496b207bsangeeta if (tt == 0 ||
c793af95640863cd29868fc7c419c5d2496b207bsangeeta bcmp(v + head_off, tt->rn_key + head_off, vlen - head_off))
c793af95640863cd29868fc7c419c5d2496b207bsangeeta return (0);
c793af95640863cd29868fc7c419c5d2496b207bsangeeta * Delete our route from mask lists.
c793af95640863cd29868fc7c419c5d2496b207bsangeeta return (0);
c793af95640863cd29868fc7c419c5d2496b207bsangeeta return (0);
c793af95640863cd29868fc7c419c5d2496b207bsangeeta if (tt->rn_mask == 0 || (saved_m = m = tt->rn_mklist) == 0)
c793af95640863cd29868fc7c419c5d2496b207bsangeeta "rn_delete: inconsistent annotation\n");
c793af95640863cd29868fc7c419c5d2496b207bsangeeta syslog(LOG_ERR, "rn_delete: inconsistent annotation\n");
c793af95640863cd29868fc7c419c5d2496b207bsangeeta#endif /* _KERNEL */
c793af95640863cd29868fc7c419c5d2496b207bsangeeta return (0); /* dangling ref could cause disaster */
c793af95640863cd29868fc7c419c5d2496b207bsangeeta "rn_delete: inconsistent annotation 2\n");
c793af95640863cd29868fc7c419c5d2496b207bsangeeta "rn_delete: inconsistent annotation 2\n");
c793af95640863cd29868fc7c419c5d2496b207bsangeeta#endif /* _KERNEL */
c793af95640863cd29868fc7c419c5d2496b207bsangeeta if (--m->rm_refs >= 0)
c793af95640863cd29868fc7c419c5d2496b207bsangeeta for (mp = &x->rn_mklist; (m = *mp) != NULL; mp = &m->rm_mklist)
c793af95640863cd29868fc7c419c5d2496b207bsangeeta if (m == 0) {
c793af95640863cd29868fc7c419c5d2496b207bsangeeta cmn_err(CE_WARN, "rn_delete: couldn't find our annotation\n");
c793af95640863cd29868fc7c419c5d2496b207bsangeeta syslog(LOG_ERR, "rn_delete: couldn't find our annotation\n");
c793af95640863cd29868fc7c419c5d2496b207bsangeeta#endif /* _KERNEL */
c793af95640863cd29868fc7c419c5d2496b207bsangeeta return (0); /* Dangling ref to us */
c793af95640863cd29868fc7c419c5d2496b207bsangeeta * Eliminate us from tree
c793af95640863cd29868fc7c419c5d2496b207bsangeeta return (0);
c793af95640863cd29868fc7c419c5d2496b207bsangeeta * Here, tt is the deletion target and
c793af95640863cd29868fc7c419c5d2496b207bsangeeta * saved_tt is the head of the dupekey chain.
c793af95640863cd29868fc7c419c5d2496b207bsangeeta /* remove from head of chain */
c793af95640863cd29868fc7c419c5d2496b207bsangeeta /* find node in front of tt on the chain */
c793af95640863cd29868fc7c419c5d2496b207bsangeeta for (x = p = saved_tt; p && p->rn_dupedkey != tt; )
c793af95640863cd29868fc7c419c5d2496b207bsangeeta /* parent */
c793af95640863cd29868fc7c419c5d2496b207bsangeeta "rn_delete: couldn't find us\n");
c793af95640863cd29868fc7c419c5d2496b207bsangeeta "rn_delete: couldn't find us\n");
c793af95640863cd29868fc7c419c5d2496b207bsangeeta#endif /* _KERNEL */
c793af95640863cd29868fc7c419c5d2496b207bsangeeta if (p->rn_left == t)
c793af95640863cd29868fc7c419c5d2496b207bsangeeta if (p->rn_right == t)
c793af95640863cd29868fc7c419c5d2496b207bsangeeta * Demote routes attached to us.
c793af95640863cd29868fc7c419c5d2496b207bsangeeta if (x->rn_bit >= 0) {
c793af95640863cd29868fc7c419c5d2496b207bsangeeta * If there are any key,mask pairs in a sibling
c793af95640863cd29868fc7c419c5d2496b207bsangeeta * duped-key chain, some subset will appear sorted
c793af95640863cd29868fc7c419c5d2496b207bsangeeta * in the same order attached to our mklist
c793af95640863cd29868fc7c419c5d2496b207bsangeeta if (m == x->rn_mklist) {
c793af95640863cd29868fc7c419c5d2496b207bsangeeta if (--(m->rm_refs) < 0)
c793af95640863cd29868fc7c419c5d2496b207bsangeeta "rn_delete: Orphaned Mask %p at %p\n",
c793af95640863cd29868fc7c419c5d2496b207bsangeeta (void *)m, (void *)x);
c793af95640863cd29868fc7c419c5d2496b207bsangeeta "rn_delete: Orphaned Mask %p at %p\n",
c793af95640863cd29868fc7c419c5d2496b207bsangeeta (void *)m, (void *)x);
c793af95640863cd29868fc7c419c5d2496b207bsangeeta#endif /* _KERNEL */
c793af95640863cd29868fc7c419c5d2496b207bsangeeta * We may be holding an active internal node in the tree.
c793af95640863cd29868fc7c419c5d2496b207bsangeeta if (t != x) {
c793af95640863cd29868fc7c419c5d2496b207bsangeeta if (p->rn_left == x)
c793af95640863cd29868fc7c419c5d2496b207bsangeeta * Walk the radix tree; For the kernel routing table, we hold additional
c793af95640863cd29868fc7c419c5d2496b207bsangeeta * refs on the ire_bucket to ensure that the walk function f() does not
c793af95640863cd29868fc7c419c5d2496b207bsangeeta * run into trashed memory. The kernel routing table is identified by
c793af95640863cd29868fc7c419c5d2496b207bsangeeta * a rnh_treetop that has RNF_SUNW_FT set in the rn_flags.
c793af95640863cd29868fc7c419c5d2496b207bsangeeta * Note that all refs takein in rn_walktree are released before it returns,
c793af95640863cd29868fc7c419c5d2496b207bsangeeta * so that f() will need to take any additional references on memory
c793af95640863cd29868fc7c419c5d2496b207bsangeeta * to be passed back to the caller of rn_walktree.
c793af95640863cd29868fc7c419c5d2496b207bsangeeta * this is a kernel ip ftable with rt_t leaf structures.
c793af95640863cd29868fc7c419c5d2496b207bsangeeta * This gets complicated because we may delete the node
c793af95640863cd29868fc7c419c5d2496b207bsangeeta * while applying the function f to it, so we need to calculate
c793af95640863cd29868fc7c419c5d2496b207bsangeeta * the successor node in advance.
c793af95640863cd29868fc7c419c5d2496b207bsangeeta /* First time through node, go left */
c793af95640863cd29868fc7c419c5d2496b207bsangeeta /* If at right child go back up, otherwise, go right */
c793af95640863cd29868fc7c419c5d2496b207bsangeeta /* Find the next *leaf* since next node might vanish, too */
c793af95640863cd29868fc7c419c5d2496b207bsangeeta for (rn = rn->rn_parent->rn_right; rn->rn_bit >= 0; ) {
c793af95640863cd29868fc7c419c5d2496b207bsangeeta /* Process leaves */
c793af95640863cd29868fc7c419c5d2496b207bsangeeta return (0);
c793af95640863cd29868fc7c419c5d2496b207bsangeeta /* NOTREACHED */
c793af95640863cd29868fc7c419c5d2496b207bsangeeta * Allocate and initialize an empty tree. This has 3 nodes, which are
c793af95640863cd29868fc7c419c5d2496b207bsangeeta * part of the radix_node_head (in the order <left,root,right>) and are
c793af95640863cd29868fc7c419c5d2496b207bsangeeta * marked RNF_ROOT so they cannot be freed.
c793af95640863cd29868fc7c419c5d2496b207bsangeeta * The leaves have all-zero and all-one keys, with significant
c793af95640863cd29868fc7c419c5d2496b207bsangeeta * bits starting at 'off'.
c793af95640863cd29868fc7c419c5d2496b207bsangeeta * Return 1 on success, 0 on error.
c793af95640863cd29868fc7c419c5d2496b207bsangeeta return (1);
c793af95640863cd29868fc7c419c5d2496b207bsangeeta R_ZallocSleep(rnh, struct radix_node_head *, sizeof (*rnh));
c793af95640863cd29868fc7c419c5d2496b207bsangeeta return (0);
c793af95640863cd29868fc7c419c5d2496b207bsangeeta tt = t->rn_left; /* ... which in turn is rnh->rnh_nodes */
c793af95640863cd29868fc7c419c5d2496b207bsangeeta tt->rn_flags = t->rn_flags = RNF_ROOT | RNF_ACTIVE;
c793af95640863cd29868fc7c419c5d2496b207bsangeeta rnh->rnh_walktree_from = NULL; /* not implemented */
c793af95640863cd29868fc7c419c5d2496b207bsangeeta return (1);
c793af95640863cd29868fc7c419c5d2496b207bsangeeta sizeof (struct radix_mask), 0, NULL, NULL, NULL, NULL, NULL, 0);
c793af95640863cd29868fc7c419c5d2496b207bsangeeta#endif /* _KERNEL */
c793af95640863cd29868fc7c419c5d2496b207bsangeeta if (rn_inithead((void **)(void *)&mask_rnhead, 0) == 0)
c793af95640863cd29868fc7c419c5d2496b207bsangeeta if (d != NULL) {
c793af95640863cd29868fc7c419c5d2496b207bsangeeta return (0);
c793af95640863cd29868fc7c419c5d2496b207bsangeeta#endif /* _KERNEL */