1*c793af95Ssangeeta /* 2*c793af95Ssangeeta * Copyright 2006 Sun Microsystems, Inc. All rights reserved. 3*c793af95Ssangeeta * Use is subject to license terms. 4*c793af95Ssangeeta * 5*c793af95Ssangeeta * Copyright (c) 1988, 1989, 1993 6*c793af95Ssangeeta * The Regents of the University of California. All rights reserved. 7*c793af95Ssangeeta * 8*c793af95Ssangeeta * Redistribution and use in source and binary forms, with or without 9*c793af95Ssangeeta * modification, are permitted provided that the following conditions 10*c793af95Ssangeeta * are met: 11*c793af95Ssangeeta * 1. Redistributions of source code must retain the above copyright 12*c793af95Ssangeeta * notice, this list of conditions and the following disclaimer. 13*c793af95Ssangeeta * 2. Redistributions in binary form must reproduce the above copyright 14*c793af95Ssangeeta * notice, this list of conditions and the following disclaimer in the 15*c793af95Ssangeeta * documentation and/or other materials provided with the distribution. 16*c793af95Ssangeeta * 4. Neither the name of the University nor the names of its contributors 17*c793af95Ssangeeta * may be used to endorse or promote products derived from this software 18*c793af95Ssangeeta * without specific prior written permission. 19*c793af95Ssangeeta * 20*c793af95Ssangeeta * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 21*c793af95Ssangeeta * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 22*c793af95Ssangeeta * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 23*c793af95Ssangeeta * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 24*c793af95Ssangeeta * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 25*c793af95Ssangeeta * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 26*c793af95Ssangeeta * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 27*c793af95Ssangeeta * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 28*c793af95Ssangeeta * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 29*c793af95Ssangeeta * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 30*c793af95Ssangeeta * SUCH DAMAGE. 31*c793af95Ssangeeta * 32*c793af95Ssangeeta * @(#)radix.c 8.5 (Berkeley) 5/19/95 33*c793af95Ssangeeta * $FreeBSD: /repoman/r/ncvs/src/sys/net/radix.c,v 1.36.2.1 2005/01/31 23:26:23 34*c793af95Ssangeeta * imp Exp $ 35*c793af95Ssangeeta */ 36*c793af95Ssangeeta 37*c793af95Ssangeeta #pragma ident "%Z%%M% %I% %E% SMI" 38*c793af95Ssangeeta 39*c793af95Ssangeeta /* 40*c793af95Ssangeeta * Routines to build and maintain radix trees for routing lookups. 41*c793af95Ssangeeta */ 42*c793af95Ssangeeta #include <sys/types.h> 43*c793af95Ssangeeta 44*c793af95Ssangeeta #ifndef _RADIX_H_ 45*c793af95Ssangeeta #include <sys/param.h> 46*c793af95Ssangeeta #ifdef _KERNEL 47*c793af95Ssangeeta #include <sys/lock.h> 48*c793af95Ssangeeta #include <sys/mutex.h> 49*c793af95Ssangeeta #include <sys/systm.h> 50*c793af95Ssangeeta #include <sys/cmn_err.h> 51*c793af95Ssangeeta #else 52*c793af95Ssangeeta #include <assert.h> 53*c793af95Ssangeeta #define ASSERT assert 54*c793af95Ssangeeta #include <stdio.h> 55*c793af95Ssangeeta #include <stdlib.h> 56*c793af95Ssangeeta #include <syslog.h> 57*c793af95Ssangeeta #include <strings.h> 58*c793af95Ssangeeta #endif /* _KERNEL */ 59*c793af95Ssangeeta #include <net/radix.h> 60*c793af95Ssangeeta #include <inet/ip_ftable.h> 61*c793af95Ssangeeta #endif 62*c793af95Ssangeeta 63*c793af95Ssangeeta #ifndef _KERNEL 64*c793af95Ssangeeta void 65*c793af95Ssangeeta panic(const char *str) 66*c793af95Ssangeeta { 67*c793af95Ssangeeta fprintf(stderr, "Panic - %s\n", str); 68*c793af95Ssangeeta abort(); 69*c793af95Ssangeeta } 70*c793af95Ssangeeta #endif /* _KERNEL */ 71*c793af95Ssangeeta 72*c793af95Ssangeeta static int rn_walktree(struct radix_node_head *, walktree_f_t *, void *); 73*c793af95Ssangeeta static struct radix_node 74*c793af95Ssangeeta *rn_insert(void *, struct radix_node_head *, int *, 75*c793af95Ssangeeta struct radix_node [2]), 76*c793af95Ssangeeta *rn_newpair(void *, int, struct radix_node[2]), 77*c793af95Ssangeeta *rn_search(void *, struct radix_node *), 78*c793af95Ssangeeta *rn_search_m(void *, struct radix_node *, void *), 79*c793af95Ssangeeta *rn_lookup(void *, void *, struct radix_node_head *), 80*c793af95Ssangeeta *rn_match(void *, struct radix_node_head *), 81*c793af95Ssangeeta *rn_match_args(void *, struct radix_node_head *, match_leaf_t *, 82*c793af95Ssangeeta void *), 83*c793af95Ssangeeta *rn_addmask(void *, int, int), 84*c793af95Ssangeeta *rn_addroute(void *, void *, struct radix_node_head *, 85*c793af95Ssangeeta struct radix_node [2]), 86*c793af95Ssangeeta *rn_delete(void *, void *, struct radix_node_head *); 87*c793af95Ssangeeta static boolean_t rn_refines(void *, void *); 88*c793af95Ssangeeta 89*c793af95Ssangeeta #define MAX_KEYLEN 16 90*c793af95Ssangeeta static int max_keylen = MAX_KEYLEN; 91*c793af95Ssangeeta 92*c793af95Ssangeeta #ifdef _KERNEL 93*c793af95Ssangeeta static struct kmem_cache *radix_mask_cache; /* for rn_mkfreelist */ 94*c793af95Ssangeeta static struct kmem_cache *radix_node_cache; 95*c793af95Ssangeeta #else 96*c793af95Ssangeeta static char *radix_mask_cache, *radix_node_cache; /* dummy vars. never inited */ 97*c793af95Ssangeeta #endif /* _KERNEL */ 98*c793af95Ssangeeta 99*c793af95Ssangeeta static struct radix_mask *rn_mkfreelist; 100*c793af95Ssangeeta static struct radix_node_head *mask_rnhead; 101*c793af95Ssangeeta /* 102*c793af95Ssangeeta * Work area -- the following point to 2 buffers of size max_keylen, 103*c793af95Ssangeeta * allocated in this order in a block of memory malloc'ed by rn_init. 104*c793af95Ssangeeta * A third buffer of size MAX_KEYLEN is allocated from the stack. 105*c793af95Ssangeeta */ 106*c793af95Ssangeeta static char *rn_zeros, *rn_ones; 107*c793af95Ssangeeta 108*c793af95Ssangeeta #define MKGet(m) R_Malloc(m, radix_mask_cache, sizeof (struct radix_mask)) 109*c793af95Ssangeeta #define MKFree(m) Free(m, radix_mask_cache) 110*c793af95Ssangeeta #define rn_masktop (mask_rnhead->rnh_treetop) 111*c793af95Ssangeeta 112*c793af95Ssangeeta static boolean_t rn_lexobetter(void *m_arg, void *n_arg); 113*c793af95Ssangeeta static struct radix_mask * 114*c793af95Ssangeeta rn_new_radix_mask(struct radix_node *tt, 115*c793af95Ssangeeta struct radix_mask *next); 116*c793af95Ssangeeta static boolean_t 117*c793af95Ssangeeta rn_satisfies_leaf(char *trial, struct radix_node *leaf, 118*c793af95Ssangeeta int skip, match_leaf_t *rn_leaf_fn, void *rn_leaf_arg); 119*c793af95Ssangeeta 120*c793af95Ssangeeta #define RN_MATCHF(rn, f, arg) (f == NULL || (*f)((rn), arg)) 121*c793af95Ssangeeta 122*c793af95Ssangeeta /* 123*c793af95Ssangeeta * The data structure for the keys is a radix tree with one way 124*c793af95Ssangeeta * branching removed. The index rn_bit at an internal node n represents a bit 125*c793af95Ssangeeta * position to be tested. The tree is arranged so that all descendants 126*c793af95Ssangeeta * of a node n have keys whose bits all agree up to position rn_bit - 1. 127*c793af95Ssangeeta * (We say the index of n is rn_bit.) 128*c793af95Ssangeeta * 129*c793af95Ssangeeta * There is at least one descendant which has a one bit at position rn_bit, 130*c793af95Ssangeeta * and at least one with a zero there. 131*c793af95Ssangeeta * 132*c793af95Ssangeeta * A route is determined by a pair of key and mask. We require that the 133*c793af95Ssangeeta * bit-wise logical and of the key and mask to be the key. 134*c793af95Ssangeeta * We define the index of a route associated with the mask to be 135*c793af95Ssangeeta * the first bit number in the mask where 0 occurs (with bit number 0 136*c793af95Ssangeeta * representing the highest order bit). 137*c793af95Ssangeeta * 138*c793af95Ssangeeta * We say a mask is normal if every bit is 0, past the index of the mask. 139*c793af95Ssangeeta * If a node n has a descendant (k, m) with index(m) == index(n) == rn_bit, 140*c793af95Ssangeeta * and m is a normal mask, then the route applies to every descendant of n. 141*c793af95Ssangeeta * If the index(m) < rn_bit, this implies the trailing last few bits of k 142*c793af95Ssangeeta * before bit b are all 0, (and hence consequently true of every descendant 143*c793af95Ssangeeta * of n), so the route applies to all descendants of the node as well. 144*c793af95Ssangeeta * 145*c793af95Ssangeeta * Similar logic shows that a non-normal mask m such that 146*c793af95Ssangeeta * index(m) <= index(n) could potentially apply to many children of n. 147*c793af95Ssangeeta * Thus, for each non-host route, we attach its mask to a list at an internal 148*c793af95Ssangeeta * node as high in the tree as we can go. 149*c793af95Ssangeeta * 150*c793af95Ssangeeta * The present version of the code makes use of normal routes in short- 151*c793af95Ssangeeta * circuiting an explict mask and compare operation when testing whether 152*c793af95Ssangeeta * a key satisfies a normal route, and also in remembering the unique leaf 153*c793af95Ssangeeta * that governs a subtree. 154*c793af95Ssangeeta */ 155*c793af95Ssangeeta 156*c793af95Ssangeeta /* 157*c793af95Ssangeeta * Most of the functions in this code assume that the key/mask arguments 158*c793af95Ssangeeta * are sockaddr-like structures, where the first byte is an uchar_t 159*c793af95Ssangeeta * indicating the size of the entire structure. 160*c793af95Ssangeeta * 161*c793af95Ssangeeta * To make the assumption more explicit, we use the LEN() macro to access 162*c793af95Ssangeeta * this field. It is safe to pass an expression with side effects 163*c793af95Ssangeeta * to LEN() as the argument is evaluated only once. 164*c793af95Ssangeeta */ 165*c793af95Ssangeeta #define LEN(x) (*(const uchar_t *)(x)) 166*c793af95Ssangeeta 167*c793af95Ssangeeta 168*c793af95Ssangeeta /* 169*c793af95Ssangeeta * Search a node in the tree matching the key. 170*c793af95Ssangeeta */ 171*c793af95Ssangeeta static struct radix_node * 172*c793af95Ssangeeta rn_search(v_arg, head) 173*c793af95Ssangeeta void *v_arg; 174*c793af95Ssangeeta struct radix_node *head; 175*c793af95Ssangeeta { 176*c793af95Ssangeeta struct radix_node *x; 177*c793af95Ssangeeta caddr_t v; 178*c793af95Ssangeeta 179*c793af95Ssangeeta for (x = head, v = v_arg; x->rn_bit >= 0; ) { 180*c793af95Ssangeeta if (x->rn_bmask & v[x->rn_offset]) 181*c793af95Ssangeeta x = x->rn_right; 182*c793af95Ssangeeta else 183*c793af95Ssangeeta x = x->rn_left; 184*c793af95Ssangeeta } 185*c793af95Ssangeeta return (x); 186*c793af95Ssangeeta } 187*c793af95Ssangeeta 188*c793af95Ssangeeta /* 189*c793af95Ssangeeta * Same as above, but with an additional mask. 190*c793af95Ssangeeta */ 191*c793af95Ssangeeta static struct radix_node * 192*c793af95Ssangeeta rn_search_m(v_arg, head, m_arg) 193*c793af95Ssangeeta struct radix_node *head; 194*c793af95Ssangeeta void *v_arg, *m_arg; 195*c793af95Ssangeeta { 196*c793af95Ssangeeta struct radix_node *x; 197*c793af95Ssangeeta caddr_t v = v_arg, m = m_arg; 198*c793af95Ssangeeta 199*c793af95Ssangeeta for (x = head; x->rn_bit >= 0; ) { 200*c793af95Ssangeeta if ((x->rn_bmask & m[x->rn_offset]) && 201*c793af95Ssangeeta (x->rn_bmask & v[x->rn_offset])) 202*c793af95Ssangeeta x = x->rn_right; 203*c793af95Ssangeeta else 204*c793af95Ssangeeta x = x->rn_left; 205*c793af95Ssangeeta } 206*c793af95Ssangeeta return (x); 207*c793af95Ssangeeta } 208*c793af95Ssangeeta 209*c793af95Ssangeeta /* 210*c793af95Ssangeeta * Returns true if there are no bits set in n_arg that are zero in 211*c793af95Ssangeeta * m_arg and the masks aren't equal. In other words, it returns true 212*c793af95Ssangeeta * when m_arg is a finer-granularity netmask -- it represents a subset 213*c793af95Ssangeeta * of the destinations implied by n_arg. 214*c793af95Ssangeeta */ 215*c793af95Ssangeeta static boolean_t 216*c793af95Ssangeeta rn_refines(m_arg, n_arg) 217*c793af95Ssangeeta void *m_arg, *n_arg; 218*c793af95Ssangeeta { 219*c793af95Ssangeeta caddr_t m = m_arg, n = n_arg; 220*c793af95Ssangeeta caddr_t lim = n + LEN(n), lim2 = lim; 221*c793af95Ssangeeta int longer = LEN(n++) - (int)LEN(m++); 222*c793af95Ssangeeta boolean_t masks_are_equal = B_TRUE; 223*c793af95Ssangeeta 224*c793af95Ssangeeta if (longer > 0) 225*c793af95Ssangeeta lim -= longer; 226*c793af95Ssangeeta while (n < lim) { 227*c793af95Ssangeeta if (*n & ~(*m)) 228*c793af95Ssangeeta return (0); 229*c793af95Ssangeeta if (*n++ != *m++) 230*c793af95Ssangeeta masks_are_equal = B_FALSE; 231*c793af95Ssangeeta } 232*c793af95Ssangeeta while (n < lim2) 233*c793af95Ssangeeta if (*n++) 234*c793af95Ssangeeta return (B_FALSE); 235*c793af95Ssangeeta if (masks_are_equal && (longer < 0)) 236*c793af95Ssangeeta for (lim2 = m - longer; m < lim2; ) 237*c793af95Ssangeeta if (*m++) 238*c793af95Ssangeeta return (B_TRUE); 239*c793af95Ssangeeta return (!masks_are_equal); 240*c793af95Ssangeeta } 241*c793af95Ssangeeta 242*c793af95Ssangeeta static struct radix_node * 243*c793af95Ssangeeta rn_lookup(v_arg, m_arg, head) 244*c793af95Ssangeeta void *v_arg, *m_arg; 245*c793af95Ssangeeta struct radix_node_head *head; 246*c793af95Ssangeeta { 247*c793af95Ssangeeta struct radix_node *x; 248*c793af95Ssangeeta caddr_t netmask = NULL; 249*c793af95Ssangeeta 250*c793af95Ssangeeta if (m_arg) { 251*c793af95Ssangeeta x = rn_addmask(m_arg, 1, head->rnh_treetop->rn_offset); 252*c793af95Ssangeeta if (x == NULL) 253*c793af95Ssangeeta return (NULL); 254*c793af95Ssangeeta netmask = x->rn_key; 255*c793af95Ssangeeta } 256*c793af95Ssangeeta x = rn_match(v_arg, head); 257*c793af95Ssangeeta if (x && netmask) { 258*c793af95Ssangeeta while (x && x->rn_mask != netmask) 259*c793af95Ssangeeta x = x->rn_dupedkey; 260*c793af95Ssangeeta } 261*c793af95Ssangeeta return (x); 262*c793af95Ssangeeta } 263*c793af95Ssangeeta 264*c793af95Ssangeeta /* 265*c793af95Ssangeeta * Returns true if address 'trial' has no bits differing from the 266*c793af95Ssangeeta * leaf's key when compared under the leaf's mask. In other words, 267*c793af95Ssangeeta * returns true when 'trial' matches leaf. 268*c793af95Ssangeeta * In addition, if a rn_leaf_fn is passed in, that is used to find 269*c793af95Ssangeeta * a match on conditions defined by the caller of rn_match. This is 270*c793af95Ssangeeta * used by the kernel ftable to match on IRE_MATCH_* conditions. 271*c793af95Ssangeeta */ 272*c793af95Ssangeeta static boolean_t 273*c793af95Ssangeeta rn_satisfies_leaf(trial, leaf, skip, rn_leaf_fn, rn_leaf_arg) 274*c793af95Ssangeeta caddr_t trial; 275*c793af95Ssangeeta struct radix_node *leaf; 276*c793af95Ssangeeta int skip; 277*c793af95Ssangeeta match_leaf_t *rn_leaf_fn; 278*c793af95Ssangeeta void *rn_leaf_arg; 279*c793af95Ssangeeta { 280*c793af95Ssangeeta char *cp = trial, *cp2 = leaf->rn_key, *cp3 = leaf->rn_mask; 281*c793af95Ssangeeta char *cplim; 282*c793af95Ssangeeta int length = min(LEN(cp), LEN(cp2)); 283*c793af95Ssangeeta 284*c793af95Ssangeeta if (cp3 == 0) 285*c793af95Ssangeeta cp3 = rn_ones; 286*c793af95Ssangeeta else 287*c793af95Ssangeeta length = min(length, LEN(cp3)); 288*c793af95Ssangeeta cplim = cp + length; 289*c793af95Ssangeeta cp3 += skip; 290*c793af95Ssangeeta cp2 += skip; 291*c793af95Ssangeeta 292*c793af95Ssangeeta for (cp += skip; cp < cplim; cp++, cp2++, cp3++) 293*c793af95Ssangeeta if ((*cp ^ *cp2) & *cp3) 294*c793af95Ssangeeta return (B_FALSE); 295*c793af95Ssangeeta 296*c793af95Ssangeeta return (RN_MATCHF(leaf, rn_leaf_fn, rn_leaf_arg)); 297*c793af95Ssangeeta } 298*c793af95Ssangeeta 299*c793af95Ssangeeta static struct radix_node * 300*c793af95Ssangeeta rn_match(v_arg, head) 301*c793af95Ssangeeta void *v_arg; 302*c793af95Ssangeeta struct radix_node_head *head; 303*c793af95Ssangeeta { 304*c793af95Ssangeeta return (rn_match_args(v_arg, head, NULL, NULL)); 305*c793af95Ssangeeta } 306*c793af95Ssangeeta 307*c793af95Ssangeeta static struct radix_node * 308*c793af95Ssangeeta rn_match_args(v_arg, head, rn_leaf_fn, rn_leaf_arg) 309*c793af95Ssangeeta void *v_arg; 310*c793af95Ssangeeta struct radix_node_head *head; 311*c793af95Ssangeeta match_leaf_t *rn_leaf_fn; 312*c793af95Ssangeeta void *rn_leaf_arg; 313*c793af95Ssangeeta { 314*c793af95Ssangeeta caddr_t v = v_arg; 315*c793af95Ssangeeta struct radix_node *t = head->rnh_treetop, *x; 316*c793af95Ssangeeta caddr_t cp = v, cp2; 317*c793af95Ssangeeta caddr_t cplim; 318*c793af95Ssangeeta struct radix_node *saved_t, *top = t; 319*c793af95Ssangeeta int off = t->rn_offset, vlen = LEN(cp), matched_off; 320*c793af95Ssangeeta int test, b, rn_bit; 321*c793af95Ssangeeta 322*c793af95Ssangeeta /* 323*c793af95Ssangeeta * Open code rn_search(v, top) to avoid overhead of extra 324*c793af95Ssangeeta * subroutine call. 325*c793af95Ssangeeta */ 326*c793af95Ssangeeta for (; t->rn_bit >= 0; ) { 327*c793af95Ssangeeta if (t->rn_bmask & cp[t->rn_offset]) 328*c793af95Ssangeeta t = t->rn_right; 329*c793af95Ssangeeta else 330*c793af95Ssangeeta t = t->rn_left; 331*c793af95Ssangeeta } 332*c793af95Ssangeeta /* 333*c793af95Ssangeeta * See if we match exactly as a host destination 334*c793af95Ssangeeta * or at least learn how many bits match, for normal mask finesse. 335*c793af95Ssangeeta * 336*c793af95Ssangeeta * It doesn't hurt us to limit how many bytes to check 337*c793af95Ssangeeta * to the length of the mask, since if it matches we had a genuine 338*c793af95Ssangeeta * match and the leaf we have is the most specific one anyway; 339*c793af95Ssangeeta * if it didn't match with a shorter length it would fail 340*c793af95Ssangeeta * with a long one. This wins big for class B&C netmasks which 341*c793af95Ssangeeta * are probably the most common case... 342*c793af95Ssangeeta */ 343*c793af95Ssangeeta if (t->rn_mask) 344*c793af95Ssangeeta vlen = LEN(t->rn_mask); 345*c793af95Ssangeeta cp += off; cp2 = t->rn_key + off; cplim = v + vlen; 346*c793af95Ssangeeta for (; cp < cplim; cp++, cp2++) 347*c793af95Ssangeeta if (*cp != *cp2) 348*c793af95Ssangeeta goto keydiff; 349*c793af95Ssangeeta /* 350*c793af95Ssangeeta * This extra grot is in case we are explicitly asked 351*c793af95Ssangeeta * to look up the default. Ugh! 352*c793af95Ssangeeta * 353*c793af95Ssangeeta * Never return the root node itself, it seems to cause a 354*c793af95Ssangeeta * lot of confusion. 355*c793af95Ssangeeta */ 356*c793af95Ssangeeta if (t->rn_flags & RNF_ROOT) 357*c793af95Ssangeeta t = t->rn_dupedkey; 358*c793af95Ssangeeta if (t == NULL || RN_MATCHF(t, rn_leaf_fn, rn_leaf_arg)) { 359*c793af95Ssangeeta return (t); 360*c793af95Ssangeeta } else { 361*c793af95Ssangeeta /* 362*c793af95Ssangeeta * Although we found an exact match on the key, rn_leaf_fn 363*c793af95Ssangeeta * is looking for some other criteria as well. Continue 364*c793af95Ssangeeta * looking as if the exact match failed. 365*c793af95Ssangeeta */ 366*c793af95Ssangeeta if (t->rn_parent->rn_flags & RNF_ROOT) { 367*c793af95Ssangeeta /* hit the top. have to give up */ 368*c793af95Ssangeeta return (NULL); 369*c793af95Ssangeeta } 370*c793af95Ssangeeta b = 0; 371*c793af95Ssangeeta goto keeplooking; 372*c793af95Ssangeeta 373*c793af95Ssangeeta } 374*c793af95Ssangeeta keydiff: 375*c793af95Ssangeeta test = (*cp ^ *cp2) & 0xff; /* find first bit that differs */ 376*c793af95Ssangeeta for (b = 7; (test >>= 1) > 0; ) 377*c793af95Ssangeeta b--; 378*c793af95Ssangeeta keeplooking: 379*c793af95Ssangeeta matched_off = cp - v; 380*c793af95Ssangeeta b += matched_off << 3; 381*c793af95Ssangeeta rn_bit = -1 - b; 382*c793af95Ssangeeta 383*c793af95Ssangeeta /* 384*c793af95Ssangeeta * If there is a host route in a duped-key chain, it will be first. 385*c793af95Ssangeeta */ 386*c793af95Ssangeeta if ((saved_t = t)->rn_mask == 0) 387*c793af95Ssangeeta t = t->rn_dupedkey; 388*c793af95Ssangeeta for (; t != NULL; t = t->rn_dupedkey) { 389*c793af95Ssangeeta /* 390*c793af95Ssangeeta * Even if we don't match exactly as a host, 391*c793af95Ssangeeta * we may match if the leaf we wound up at is 392*c793af95Ssangeeta * a route to a net. 393*c793af95Ssangeeta */ 394*c793af95Ssangeeta 395*c793af95Ssangeeta if (t->rn_flags & RNF_NORMAL) { 396*c793af95Ssangeeta if ((rn_bit <= t->rn_bit) && 397*c793af95Ssangeeta RN_MATCHF(t, rn_leaf_fn, rn_leaf_arg)) { 398*c793af95Ssangeeta return (t); 399*c793af95Ssangeeta } 400*c793af95Ssangeeta } else if (rn_satisfies_leaf(v, t, matched_off, rn_leaf_fn, 401*c793af95Ssangeeta rn_leaf_arg)) { 402*c793af95Ssangeeta return (t); 403*c793af95Ssangeeta } 404*c793af95Ssangeeta } 405*c793af95Ssangeeta t = saved_t; 406*c793af95Ssangeeta /* start searching up the tree */ 407*c793af95Ssangeeta do { 408*c793af95Ssangeeta struct radix_mask *m; 409*c793af95Ssangeeta 410*c793af95Ssangeeta t = t->rn_parent; 411*c793af95Ssangeeta m = t->rn_mklist; 412*c793af95Ssangeeta /* 413*c793af95Ssangeeta * If non-contiguous masks ever become important 414*c793af95Ssangeeta * we can restore the masking and open coding of 415*c793af95Ssangeeta * the search and satisfaction test and put the 416*c793af95Ssangeeta * calculation of "off" back before the "do". 417*c793af95Ssangeeta */ 418*c793af95Ssangeeta while (m) { 419*c793af95Ssangeeta if (m->rm_flags & RNF_NORMAL) { 420*c793af95Ssangeeta if ((rn_bit <= m->rm_bit) && 421*c793af95Ssangeeta RN_MATCHF(m->rm_leaf, rn_leaf_fn, 422*c793af95Ssangeeta rn_leaf_arg)) { 423*c793af95Ssangeeta return (m->rm_leaf); 424*c793af95Ssangeeta } 425*c793af95Ssangeeta } else { 426*c793af95Ssangeeta off = min(t->rn_offset, matched_off); 427*c793af95Ssangeeta x = rn_search_m(v, t, m->rm_mask); 428*c793af95Ssangeeta while (x != NULL && x->rn_mask != m->rm_mask) 429*c793af95Ssangeeta x = x->rn_dupedkey; 430*c793af95Ssangeeta if (x && rn_satisfies_leaf(v, x, off, 431*c793af95Ssangeeta rn_leaf_fn, rn_leaf_arg)) { 432*c793af95Ssangeeta return (x); 433*c793af95Ssangeeta } 434*c793af95Ssangeeta } 435*c793af95Ssangeeta m = m->rm_mklist; 436*c793af95Ssangeeta } 437*c793af95Ssangeeta } while (t != top); 438*c793af95Ssangeeta return (0); 439*c793af95Ssangeeta } 440*c793af95Ssangeeta 441*c793af95Ssangeeta /* 442*c793af95Ssangeeta * Whenever we add a new leaf to the tree, we also add a parent node, 443*c793af95Ssangeeta * so we allocate them as an array of two elements: the first one must be 444*c793af95Ssangeeta * the leaf (see RNTORT() in route.c), the second one is the parent. 445*c793af95Ssangeeta * This routine initializes the relevant fields of the nodes, so that 446*c793af95Ssangeeta * the leaf is the left child of the parent node, and both nodes have 447*c793af95Ssangeeta * (almost) all all fields filled as appropriate. 448*c793af95Ssangeeta * The function returns a pointer to the parent node. 449*c793af95Ssangeeta */ 450*c793af95Ssangeeta 451*c793af95Ssangeeta static struct radix_node * 452*c793af95Ssangeeta rn_newpair(v, b, nodes) 453*c793af95Ssangeeta void *v; 454*c793af95Ssangeeta int b; 455*c793af95Ssangeeta struct radix_node nodes[2]; 456*c793af95Ssangeeta { 457*c793af95Ssangeeta struct radix_node *tt = nodes, *t = tt + 1; 458*c793af95Ssangeeta 459*c793af95Ssangeeta t->rn_bit = b; 460*c793af95Ssangeeta t->rn_bmask = 0x80 >> (b & 7); 461*c793af95Ssangeeta t->rn_left = tt; 462*c793af95Ssangeeta t->rn_offset = b >> 3; 463*c793af95Ssangeeta 464*c793af95Ssangeeta /* 465*c793af95Ssangeeta * t->rn_parent, r->rn_right, tt->rn_mask, tt->rn_dupedkey 466*c793af95Ssangeeta * and tt->rn_bmask must have been zeroed by caller. 467*c793af95Ssangeeta */ 468*c793af95Ssangeeta tt->rn_bit = -1; 469*c793af95Ssangeeta tt->rn_key = v; 470*c793af95Ssangeeta tt->rn_parent = t; 471*c793af95Ssangeeta tt->rn_flags = t->rn_flags = RNF_ACTIVE; 472*c793af95Ssangeeta tt->rn_mklist = t->rn_mklist = 0; 473*c793af95Ssangeeta return (t); 474*c793af95Ssangeeta } 475*c793af95Ssangeeta 476*c793af95Ssangeeta static struct radix_node * 477*c793af95Ssangeeta rn_insert(v_arg, head, dupentry, nodes) 478*c793af95Ssangeeta void *v_arg; 479*c793af95Ssangeeta struct radix_node_head *head; 480*c793af95Ssangeeta int *dupentry; 481*c793af95Ssangeeta struct radix_node nodes[2]; 482*c793af95Ssangeeta { 483*c793af95Ssangeeta caddr_t v = v_arg; 484*c793af95Ssangeeta struct radix_node *top = head->rnh_treetop; 485*c793af95Ssangeeta int head_off = top->rn_offset, vlen = (int)LEN(v); 486*c793af95Ssangeeta struct radix_node *t = rn_search(v_arg, top); 487*c793af95Ssangeeta caddr_t cp = v + head_off; 488*c793af95Ssangeeta int b; 489*c793af95Ssangeeta struct radix_node *tt; 490*c793af95Ssangeeta 491*c793af95Ssangeeta /* 492*c793af95Ssangeeta * Find first bit at which v and t->rn_key differ 493*c793af95Ssangeeta */ 494*c793af95Ssangeeta { 495*c793af95Ssangeeta caddr_t cp2 = t->rn_key + head_off; 496*c793af95Ssangeeta int cmp_res; 497*c793af95Ssangeeta caddr_t cplim = v + vlen; 498*c793af95Ssangeeta 499*c793af95Ssangeeta while (cp < cplim) 500*c793af95Ssangeeta if (*cp2++ != *cp++) 501*c793af95Ssangeeta goto on1; 502*c793af95Ssangeeta *dupentry = 1; 503*c793af95Ssangeeta return (t); 504*c793af95Ssangeeta on1: 505*c793af95Ssangeeta *dupentry = 0; 506*c793af95Ssangeeta cmp_res = (cp[-1] ^ cp2[-1]) & 0xff; 507*c793af95Ssangeeta for (b = (cp - v) << 3; cmp_res; b--) 508*c793af95Ssangeeta cmp_res >>= 1; 509*c793af95Ssangeeta } 510*c793af95Ssangeeta { 511*c793af95Ssangeeta struct radix_node *p, *x = top; 512*c793af95Ssangeeta cp = v; 513*c793af95Ssangeeta do { 514*c793af95Ssangeeta p = x; 515*c793af95Ssangeeta if (cp[x->rn_offset] & x->rn_bmask) 516*c793af95Ssangeeta x = x->rn_right; 517*c793af95Ssangeeta else 518*c793af95Ssangeeta x = x->rn_left; 519*c793af95Ssangeeta } while (b > (unsigned)x->rn_bit); 520*c793af95Ssangeeta /* x->rn_bit < b && x->rn_bit >= 0 */ 521*c793af95Ssangeeta t = rn_newpair(v_arg, b, nodes); 522*c793af95Ssangeeta tt = t->rn_left; 523*c793af95Ssangeeta if ((cp[p->rn_offset] & p->rn_bmask) == 0) 524*c793af95Ssangeeta p->rn_left = t; 525*c793af95Ssangeeta else 526*c793af95Ssangeeta p->rn_right = t; 527*c793af95Ssangeeta x->rn_parent = t; 528*c793af95Ssangeeta t->rn_parent = p; 529*c793af95Ssangeeta if ((cp[t->rn_offset] & t->rn_bmask) == 0) { 530*c793af95Ssangeeta t->rn_right = x; 531*c793af95Ssangeeta } else { 532*c793af95Ssangeeta t->rn_right = tt; 533*c793af95Ssangeeta t->rn_left = x; 534*c793af95Ssangeeta } 535*c793af95Ssangeeta } 536*c793af95Ssangeeta return (tt); 537*c793af95Ssangeeta } 538*c793af95Ssangeeta 539*c793af95Ssangeeta static struct radix_node * 540*c793af95Ssangeeta rn_addmask(n_arg, search, skip) 541*c793af95Ssangeeta int search, skip; 542*c793af95Ssangeeta void *n_arg; 543*c793af95Ssangeeta { 544*c793af95Ssangeeta caddr_t netmask = (caddr_t)n_arg; 545*c793af95Ssangeeta struct radix_node *x; 546*c793af95Ssangeeta caddr_t cp, cplim; 547*c793af95Ssangeeta int b = 0, mlen, j; 548*c793af95Ssangeeta int maskduplicated, m0, isnormal; 549*c793af95Ssangeeta struct radix_node *saved_x; 550*c793af95Ssangeeta int last_zeroed = 0; 551*c793af95Ssangeeta char addmask_key[MAX_KEYLEN]; 552*c793af95Ssangeeta 553*c793af95Ssangeeta if ((mlen = LEN(netmask)) > max_keylen) 554*c793af95Ssangeeta mlen = max_keylen; 555*c793af95Ssangeeta if (skip == 0) 556*c793af95Ssangeeta skip = 1; 557*c793af95Ssangeeta if (mlen <= skip) 558*c793af95Ssangeeta return (mask_rnhead->rnh_nodes); 559*c793af95Ssangeeta if (skip > 1) 560*c793af95Ssangeeta bcopy(rn_ones + 1, addmask_key + 1, skip - 1); 561*c793af95Ssangeeta if ((m0 = mlen) > skip) 562*c793af95Ssangeeta bcopy(netmask + skip, addmask_key + skip, mlen - skip); 563*c793af95Ssangeeta /* 564*c793af95Ssangeeta * Trim trailing zeroes. 565*c793af95Ssangeeta */ 566*c793af95Ssangeeta for (cp = addmask_key + mlen; (cp > addmask_key) && cp[-1] == 0; ) 567*c793af95Ssangeeta cp--; 568*c793af95Ssangeeta mlen = cp - addmask_key; 569*c793af95Ssangeeta if (mlen <= skip) { 570*c793af95Ssangeeta if (m0 >= last_zeroed) 571*c793af95Ssangeeta last_zeroed = mlen; 572*c793af95Ssangeeta return (mask_rnhead->rnh_nodes); 573*c793af95Ssangeeta } 574*c793af95Ssangeeta if (m0 < last_zeroed) 575*c793af95Ssangeeta bzero(addmask_key + m0, last_zeroed - m0); 576*c793af95Ssangeeta *addmask_key = last_zeroed = mlen; 577*c793af95Ssangeeta x = rn_search(addmask_key, rn_masktop); 578*c793af95Ssangeeta if (bcmp(addmask_key, x->rn_key, mlen) != 0) 579*c793af95Ssangeeta x = 0; 580*c793af95Ssangeeta if (x || search) 581*c793af95Ssangeeta return (x); 582*c793af95Ssangeeta R_Zalloc(x, radix_node_cache, max_keylen + 2 * sizeof (*x)); 583*c793af95Ssangeeta 584*c793af95Ssangeeta if ((saved_x = x) == 0) 585*c793af95Ssangeeta return (0); 586*c793af95Ssangeeta netmask = cp = (caddr_t)(x + 2); 587*c793af95Ssangeeta bcopy(addmask_key, cp, mlen); 588*c793af95Ssangeeta x = rn_insert(cp, mask_rnhead, &maskduplicated, x); 589*c793af95Ssangeeta if (maskduplicated) { 590*c793af95Ssangeeta #ifdef _KERNEL 591*c793af95Ssangeeta cmn_err(CE_WARN, "rn_addmask: mask impossibly already in tree"); 592*c793af95Ssangeeta #else 593*c793af95Ssangeeta syslog(LOG_ERR, "rn_addmask: mask impossibly already in tree"); 594*c793af95Ssangeeta #endif /* _KERNEL */ 595*c793af95Ssangeeta Free(saved_x, radix_node_cache); 596*c793af95Ssangeeta return (x); 597*c793af95Ssangeeta } 598*c793af95Ssangeeta /* 599*c793af95Ssangeeta * Calculate index of mask, and check for normalcy. 600*c793af95Ssangeeta * First find the first byte with a 0 bit, then if there are 601*c793af95Ssangeeta * more bits left (remember we already trimmed the trailing 0's), 602*c793af95Ssangeeta * the pattern must be one of those in normal_chars[], or we have 603*c793af95Ssangeeta * a non-contiguous mask. 604*c793af95Ssangeeta */ 605*c793af95Ssangeeta cplim = netmask + mlen; 606*c793af95Ssangeeta isnormal = 1; 607*c793af95Ssangeeta for (cp = netmask + skip; (cp < cplim) && *(uchar_t *)cp == 0xff; ) 608*c793af95Ssangeeta cp++; 609*c793af95Ssangeeta if (cp != cplim) { 610*c793af95Ssangeeta static uint8_t normal_chars[] = { 611*c793af95Ssangeeta 0, 0x80, 0xc0, 0xe0, 0xf0, 0xf8, 0xfc, 0xfe, 0xff}; 612*c793af95Ssangeeta 613*c793af95Ssangeeta for (j = 0x80; (j & *cp) != 0; j >>= 1) 614*c793af95Ssangeeta b++; 615*c793af95Ssangeeta if (*cp != normal_chars[b] || cp != (cplim - 1)) 616*c793af95Ssangeeta isnormal = 0; 617*c793af95Ssangeeta } 618*c793af95Ssangeeta b += (cp - netmask) << 3; 619*c793af95Ssangeeta x->rn_bit = -1 - b; 620*c793af95Ssangeeta if (isnormal) 621*c793af95Ssangeeta x->rn_flags |= RNF_NORMAL; 622*c793af95Ssangeeta return (x); 623*c793af95Ssangeeta } 624*c793af95Ssangeeta 625*c793af95Ssangeeta /* arbitrary ordering for non-contiguous masks */ 626*c793af95Ssangeeta static boolean_t 627*c793af95Ssangeeta rn_lexobetter(m_arg, n_arg) 628*c793af95Ssangeeta void *m_arg, *n_arg; 629*c793af95Ssangeeta { 630*c793af95Ssangeeta uchar_t *mp = m_arg, *np = n_arg, *lim; 631*c793af95Ssangeeta 632*c793af95Ssangeeta if (LEN(mp) > LEN(np)) 633*c793af95Ssangeeta /* not really, but need to check longer one first */ 634*c793af95Ssangeeta return (B_TRUE); 635*c793af95Ssangeeta if (LEN(mp) == LEN(np)) 636*c793af95Ssangeeta for (lim = mp + LEN(mp); mp < lim; ) 637*c793af95Ssangeeta if (*mp++ > *np++) 638*c793af95Ssangeeta return (B_TRUE); 639*c793af95Ssangeeta return (B_FALSE); 640*c793af95Ssangeeta } 641*c793af95Ssangeeta 642*c793af95Ssangeeta static struct radix_mask * 643*c793af95Ssangeeta rn_new_radix_mask(tt, next) 644*c793af95Ssangeeta struct radix_node *tt; 645*c793af95Ssangeeta struct radix_mask *next; 646*c793af95Ssangeeta { 647*c793af95Ssangeeta struct radix_mask *m; 648*c793af95Ssangeeta 649*c793af95Ssangeeta MKGet(m); 650*c793af95Ssangeeta if (m == 0) { 651*c793af95Ssangeeta #ifndef _KERNEL 652*c793af95Ssangeeta syslog(LOG_ERR, "Mask for route not entered\n"); 653*c793af95Ssangeeta #endif /* _KERNEL */ 654*c793af95Ssangeeta return (0); 655*c793af95Ssangeeta } 656*c793af95Ssangeeta bzero(m, sizeof (*m)); 657*c793af95Ssangeeta m->rm_bit = tt->rn_bit; 658*c793af95Ssangeeta m->rm_flags = tt->rn_flags; 659*c793af95Ssangeeta if (tt->rn_flags & RNF_NORMAL) 660*c793af95Ssangeeta m->rm_leaf = tt; 661*c793af95Ssangeeta else 662*c793af95Ssangeeta m->rm_mask = tt->rn_mask; 663*c793af95Ssangeeta m->rm_mklist = next; 664*c793af95Ssangeeta tt->rn_mklist = m; 665*c793af95Ssangeeta return (m); 666*c793af95Ssangeeta } 667*c793af95Ssangeeta 668*c793af95Ssangeeta static struct radix_node * 669*c793af95Ssangeeta rn_addroute(v_arg, n_arg, head, treenodes) 670*c793af95Ssangeeta void *v_arg, *n_arg; 671*c793af95Ssangeeta struct radix_node_head *head; 672*c793af95Ssangeeta struct radix_node treenodes[2]; 673*c793af95Ssangeeta { 674*c793af95Ssangeeta caddr_t v = (caddr_t)v_arg, netmask = (caddr_t)n_arg; 675*c793af95Ssangeeta struct radix_node *t, *x = 0, *tt; 676*c793af95Ssangeeta struct radix_node *saved_tt, *top = head->rnh_treetop; 677*c793af95Ssangeeta short b = 0, b_leaf = 0; 678*c793af95Ssangeeta int keyduplicated; 679*c793af95Ssangeeta caddr_t mmask; 680*c793af95Ssangeeta struct radix_mask *m, **mp; 681*c793af95Ssangeeta 682*c793af95Ssangeeta /* 683*c793af95Ssangeeta * In dealing with non-contiguous masks, there may be 684*c793af95Ssangeeta * many different routes which have the same mask. 685*c793af95Ssangeeta * We will find it useful to have a unique pointer to 686*c793af95Ssangeeta * the mask to speed avoiding duplicate references at 687*c793af95Ssangeeta * nodes and possibly save time in calculating indices. 688*c793af95Ssangeeta */ 689*c793af95Ssangeeta if (netmask) { 690*c793af95Ssangeeta if ((x = rn_addmask(netmask, 0, top->rn_offset)) == 0) 691*c793af95Ssangeeta return (0); 692*c793af95Ssangeeta b_leaf = x->rn_bit; 693*c793af95Ssangeeta b = -1 - x->rn_bit; 694*c793af95Ssangeeta netmask = x->rn_key; 695*c793af95Ssangeeta } 696*c793af95Ssangeeta /* 697*c793af95Ssangeeta * Deal with duplicated keys: attach node to previous instance 698*c793af95Ssangeeta */ 699*c793af95Ssangeeta saved_tt = tt = rn_insert(v, head, &keyduplicated, treenodes); 700*c793af95Ssangeeta if (keyduplicated) { 701*c793af95Ssangeeta for (t = tt; tt; t = tt, tt = tt->rn_dupedkey) { 702*c793af95Ssangeeta if (tt->rn_mask == netmask) 703*c793af95Ssangeeta return (0); 704*c793af95Ssangeeta if (netmask == 0 || 705*c793af95Ssangeeta (tt->rn_mask && 706*c793af95Ssangeeta /* index (netmask) > node */ 707*c793af95Ssangeeta ((b_leaf < tt->rn_bit) || 708*c793af95Ssangeeta rn_refines(netmask, tt->rn_mask) || 709*c793af95Ssangeeta rn_lexobetter(netmask, tt->rn_mask)))) 710*c793af95Ssangeeta break; 711*c793af95Ssangeeta } 712*c793af95Ssangeeta /* 713*c793af95Ssangeeta * If the mask is not duplicated, we wouldn't 714*c793af95Ssangeeta * find it among possible duplicate key entries 715*c793af95Ssangeeta * anyway, so the above test doesn't hurt. 716*c793af95Ssangeeta * 717*c793af95Ssangeeta * We sort the masks for a duplicated key the same way as 718*c793af95Ssangeeta * in a masklist -- most specific to least specific. 719*c793af95Ssangeeta * This may require the unfortunate nuisance of relocating 720*c793af95Ssangeeta * the head of the list. 721*c793af95Ssangeeta * 722*c793af95Ssangeeta * We also reverse, or doubly link the list through the 723*c793af95Ssangeeta * parent pointer. 724*c793af95Ssangeeta */ 725*c793af95Ssangeeta if (tt == saved_tt) { 726*c793af95Ssangeeta struct radix_node *xx = x; 727*c793af95Ssangeeta /* link in at head of list */ 728*c793af95Ssangeeta (tt = treenodes)->rn_dupedkey = t; 729*c793af95Ssangeeta tt->rn_flags = t->rn_flags; 730*c793af95Ssangeeta tt->rn_parent = x = t->rn_parent; 731*c793af95Ssangeeta t->rn_parent = tt; /* parent */ 732*c793af95Ssangeeta if (x->rn_left == t) 733*c793af95Ssangeeta x->rn_left = tt; 734*c793af95Ssangeeta else 735*c793af95Ssangeeta x->rn_right = tt; 736*c793af95Ssangeeta saved_tt = tt; x = xx; 737*c793af95Ssangeeta } else { 738*c793af95Ssangeeta (tt = treenodes)->rn_dupedkey = t->rn_dupedkey; 739*c793af95Ssangeeta t->rn_dupedkey = tt; 740*c793af95Ssangeeta /* Set rn_parent value for tt and tt->rn_dupedkey */ 741*c793af95Ssangeeta tt->rn_parent = t; 742*c793af95Ssangeeta if (tt->rn_dupedkey) 743*c793af95Ssangeeta tt->rn_dupedkey->rn_parent = tt; 744*c793af95Ssangeeta } 745*c793af95Ssangeeta tt->rn_key = v; 746*c793af95Ssangeeta tt->rn_bit = -1; 747*c793af95Ssangeeta tt->rn_flags = RNF_ACTIVE; 748*c793af95Ssangeeta } 749*c793af95Ssangeeta /* 750*c793af95Ssangeeta * Put mask in tree. 751*c793af95Ssangeeta */ 752*c793af95Ssangeeta if (netmask) { 753*c793af95Ssangeeta tt->rn_mask = netmask; 754*c793af95Ssangeeta tt->rn_bit = x->rn_bit; 755*c793af95Ssangeeta tt->rn_flags |= x->rn_flags & RNF_NORMAL; 756*c793af95Ssangeeta } 757*c793af95Ssangeeta t = saved_tt->rn_parent; 758*c793af95Ssangeeta if (keyduplicated) 759*c793af95Ssangeeta goto key_exists; 760*c793af95Ssangeeta b_leaf = -1 - t->rn_bit; 761*c793af95Ssangeeta if (t->rn_right == saved_tt) 762*c793af95Ssangeeta x = t->rn_left; 763*c793af95Ssangeeta else 764*c793af95Ssangeeta x = t->rn_right; 765*c793af95Ssangeeta /* Promote general routes from below */ 766*c793af95Ssangeeta if (x->rn_bit < 0) { 767*c793af95Ssangeeta for (mp = &t->rn_mklist; x; x = x->rn_dupedkey) 768*c793af95Ssangeeta if (x->rn_mask && (x->rn_bit >= b_leaf) && x->rn_mklist == 0) { 769*c793af95Ssangeeta *mp = m = rn_new_radix_mask(x, 0); 770*c793af95Ssangeeta if (m) 771*c793af95Ssangeeta mp = &m->rm_mklist; 772*c793af95Ssangeeta } 773*c793af95Ssangeeta } else if (x->rn_mklist) { 774*c793af95Ssangeeta /* 775*c793af95Ssangeeta * Skip over masks whose index is > that of new node 776*c793af95Ssangeeta */ 777*c793af95Ssangeeta for (mp = &x->rn_mklist; (m = *mp) != NULL; mp = &m->rm_mklist) 778*c793af95Ssangeeta if (m->rm_bit >= b_leaf) 779*c793af95Ssangeeta break; 780*c793af95Ssangeeta t->rn_mklist = m; *mp = 0; 781*c793af95Ssangeeta } 782*c793af95Ssangeeta key_exists: 783*c793af95Ssangeeta /* Add new route to highest possible ancestor's list */ 784*c793af95Ssangeeta if ((netmask == 0) || (b > t->rn_bit)) 785*c793af95Ssangeeta return (tt); /* can't lift at all */ 786*c793af95Ssangeeta b_leaf = tt->rn_bit; 787*c793af95Ssangeeta do { 788*c793af95Ssangeeta x = t; 789*c793af95Ssangeeta t = t->rn_parent; 790*c793af95Ssangeeta } while (b <= t->rn_bit && x != top); 791*c793af95Ssangeeta /* 792*c793af95Ssangeeta * Search through routes associated with node to 793*c793af95Ssangeeta * insert new route according to index. 794*c793af95Ssangeeta * Need same criteria as when sorting dupedkeys to avoid 795*c793af95Ssangeeta * double loop on deletion. 796*c793af95Ssangeeta */ 797*c793af95Ssangeeta for (mp = &x->rn_mklist; (m = *mp) != NULL; mp = &m->rm_mklist) { 798*c793af95Ssangeeta if (m->rm_bit < b_leaf) 799*c793af95Ssangeeta continue; 800*c793af95Ssangeeta if (m->rm_bit > b_leaf) 801*c793af95Ssangeeta break; 802*c793af95Ssangeeta if (m->rm_flags & RNF_NORMAL) { 803*c793af95Ssangeeta mmask = m->rm_leaf->rn_mask; 804*c793af95Ssangeeta if (tt->rn_flags & RNF_NORMAL) { 805*c793af95Ssangeeta #ifdef _KERNEL 806*c793af95Ssangeeta cmn_err(CE_WARN, "Non-unique normal route, " 807*c793af95Ssangeeta "mask not entered\n"); 808*c793af95Ssangeeta #else 809*c793af95Ssangeeta syslog(LOG_ERR, "Non-unique normal route, " 810*c793af95Ssangeeta "mask not entered\n"); 811*c793af95Ssangeeta #endif /* _KERNEL */ 812*c793af95Ssangeeta return (tt); 813*c793af95Ssangeeta } 814*c793af95Ssangeeta } else 815*c793af95Ssangeeta mmask = m->rm_mask; 816*c793af95Ssangeeta if (mmask == netmask) { 817*c793af95Ssangeeta m->rm_refs++; 818*c793af95Ssangeeta tt->rn_mklist = m; 819*c793af95Ssangeeta return (tt); 820*c793af95Ssangeeta } 821*c793af95Ssangeeta if (rn_refines(netmask, mmask) || 822*c793af95Ssangeeta rn_lexobetter(netmask, mmask)) 823*c793af95Ssangeeta break; 824*c793af95Ssangeeta } 825*c793af95Ssangeeta *mp = rn_new_radix_mask(tt, *mp); 826*c793af95Ssangeeta return (tt); 827*c793af95Ssangeeta } 828*c793af95Ssangeeta 829*c793af95Ssangeeta static struct radix_node * 830*c793af95Ssangeeta rn_delete(v_arg, netmask_arg, head) 831*c793af95Ssangeeta void *v_arg, *netmask_arg; 832*c793af95Ssangeeta struct radix_node_head *head; 833*c793af95Ssangeeta { 834*c793af95Ssangeeta struct radix_node *t, *p, *x, *tt; 835*c793af95Ssangeeta struct radix_mask *m, *saved_m, **mp; 836*c793af95Ssangeeta struct radix_node *dupedkey, *saved_tt, *top; 837*c793af95Ssangeeta caddr_t v, netmask; 838*c793af95Ssangeeta int b, head_off, vlen; 839*c793af95Ssangeeta 840*c793af95Ssangeeta v = v_arg; 841*c793af95Ssangeeta netmask = netmask_arg; 842*c793af95Ssangeeta x = head->rnh_treetop; 843*c793af95Ssangeeta tt = rn_search(v, x); 844*c793af95Ssangeeta head_off = x->rn_offset; 845*c793af95Ssangeeta vlen = LEN(v); 846*c793af95Ssangeeta saved_tt = tt; 847*c793af95Ssangeeta top = x; 848*c793af95Ssangeeta if (tt == 0 || 849*c793af95Ssangeeta bcmp(v + head_off, tt->rn_key + head_off, vlen - head_off)) 850*c793af95Ssangeeta return (0); 851*c793af95Ssangeeta /* 852*c793af95Ssangeeta * Delete our route from mask lists. 853*c793af95Ssangeeta */ 854*c793af95Ssangeeta if (netmask) { 855*c793af95Ssangeeta if ((x = rn_addmask(netmask, 1, head_off)) == 0) 856*c793af95Ssangeeta return (0); 857*c793af95Ssangeeta netmask = x->rn_key; 858*c793af95Ssangeeta while (tt->rn_mask != netmask) 859*c793af95Ssangeeta if ((tt = tt->rn_dupedkey) == 0) 860*c793af95Ssangeeta return (0); 861*c793af95Ssangeeta } 862*c793af95Ssangeeta if (tt->rn_mask == 0 || (saved_m = m = tt->rn_mklist) == 0) 863*c793af95Ssangeeta goto on1; 864*c793af95Ssangeeta if (tt->rn_flags & RNF_NORMAL) { 865*c793af95Ssangeeta if (m->rm_leaf != tt || m->rm_refs > 0) { 866*c793af95Ssangeeta #ifdef _KERNEL 867*c793af95Ssangeeta cmn_err(CE_WARN, 868*c793af95Ssangeeta "rn_delete: inconsistent annotation\n"); 869*c793af95Ssangeeta #else 870*c793af95Ssangeeta syslog(LOG_ERR, "rn_delete: inconsistent annotation\n"); 871*c793af95Ssangeeta #endif /* _KERNEL */ 872*c793af95Ssangeeta return (0); /* dangling ref could cause disaster */ 873*c793af95Ssangeeta } 874*c793af95Ssangeeta } else { 875*c793af95Ssangeeta if (m->rm_mask != tt->rn_mask) { 876*c793af95Ssangeeta #ifdef _KERNEL 877*c793af95Ssangeeta cmn_err(CE_WARN, 878*c793af95Ssangeeta "rn_delete: inconsistent annotation 2\n"); 879*c793af95Ssangeeta #else 880*c793af95Ssangeeta syslog(LOG_ERR, 881*c793af95Ssangeeta "rn_delete: inconsistent annotation 2\n"); 882*c793af95Ssangeeta #endif /* _KERNEL */ 883*c793af95Ssangeeta goto on1; 884*c793af95Ssangeeta } 885*c793af95Ssangeeta if (--m->rm_refs >= 0) 886*c793af95Ssangeeta goto on1; 887*c793af95Ssangeeta } 888*c793af95Ssangeeta b = -1 - tt->rn_bit; 889*c793af95Ssangeeta t = saved_tt->rn_parent; 890*c793af95Ssangeeta if (b > t->rn_bit) 891*c793af95Ssangeeta goto on1; /* Wasn't lifted at all */ 892*c793af95Ssangeeta do { 893*c793af95Ssangeeta x = t; 894*c793af95Ssangeeta t = t->rn_parent; 895*c793af95Ssangeeta } while (b <= t->rn_bit && x != top); 896*c793af95Ssangeeta for (mp = &x->rn_mklist; (m = *mp) != NULL; mp = &m->rm_mklist) 897*c793af95Ssangeeta if (m == saved_m) { 898*c793af95Ssangeeta *mp = m->rm_mklist; 899*c793af95Ssangeeta MKFree(m); 900*c793af95Ssangeeta break; 901*c793af95Ssangeeta } 902*c793af95Ssangeeta if (m == 0) { 903*c793af95Ssangeeta #ifdef _KERNEL 904*c793af95Ssangeeta cmn_err(CE_WARN, "rn_delete: couldn't find our annotation\n"); 905*c793af95Ssangeeta #else 906*c793af95Ssangeeta syslog(LOG_ERR, "rn_delete: couldn't find our annotation\n"); 907*c793af95Ssangeeta #endif /* _KERNEL */ 908*c793af95Ssangeeta if (tt->rn_flags & RNF_NORMAL) 909*c793af95Ssangeeta return (0); /* Dangling ref to us */ 910*c793af95Ssangeeta } 911*c793af95Ssangeeta on1: 912*c793af95Ssangeeta /* 913*c793af95Ssangeeta * Eliminate us from tree 914*c793af95Ssangeeta */ 915*c793af95Ssangeeta if (tt->rn_flags & RNF_ROOT) 916*c793af95Ssangeeta return (0); 917*c793af95Ssangeeta t = tt->rn_parent; 918*c793af95Ssangeeta dupedkey = saved_tt->rn_dupedkey; 919*c793af95Ssangeeta if (dupedkey) { 920*c793af95Ssangeeta /* 921*c793af95Ssangeeta * Here, tt is the deletion target and 922*c793af95Ssangeeta * saved_tt is the head of the dupekey chain. 923*c793af95Ssangeeta */ 924*c793af95Ssangeeta if (tt == saved_tt) { 925*c793af95Ssangeeta /* remove from head of chain */ 926*c793af95Ssangeeta x = dupedkey; x->rn_parent = t; 927*c793af95Ssangeeta if (t->rn_left == tt) 928*c793af95Ssangeeta t->rn_left = x; 929*c793af95Ssangeeta else 930*c793af95Ssangeeta t->rn_right = x; 931*c793af95Ssangeeta } else { 932*c793af95Ssangeeta /* find node in front of tt on the chain */ 933*c793af95Ssangeeta for (x = p = saved_tt; p && p->rn_dupedkey != tt; ) 934*c793af95Ssangeeta p = p->rn_dupedkey; 935*c793af95Ssangeeta if (p) { 936*c793af95Ssangeeta p->rn_dupedkey = tt->rn_dupedkey; 937*c793af95Ssangeeta if (tt->rn_dupedkey) /* parent */ 938*c793af95Ssangeeta tt->rn_dupedkey->rn_parent = p; 939*c793af95Ssangeeta /* parent */ 940*c793af95Ssangeeta } else 941*c793af95Ssangeeta #ifdef _KERNEL 942*c793af95Ssangeeta cmn_err(CE_WARN, 943*c793af95Ssangeeta "rn_delete: couldn't find us\n"); 944*c793af95Ssangeeta #else 945*c793af95Ssangeeta syslog(LOG_ERR, 946*c793af95Ssangeeta "rn_delete: couldn't find us\n"); 947*c793af95Ssangeeta #endif /* _KERNEL */ 948*c793af95Ssangeeta } 949*c793af95Ssangeeta t = tt + 1; 950*c793af95Ssangeeta if (t->rn_flags & RNF_ACTIVE) { 951*c793af95Ssangeeta *++x = *t; 952*c793af95Ssangeeta p = t->rn_parent; 953*c793af95Ssangeeta if (p->rn_left == t) 954*c793af95Ssangeeta p->rn_left = x; 955*c793af95Ssangeeta else 956*c793af95Ssangeeta p->rn_right = x; 957*c793af95Ssangeeta x->rn_left->rn_parent = x; 958*c793af95Ssangeeta x->rn_right->rn_parent = x; 959*c793af95Ssangeeta } 960*c793af95Ssangeeta goto out; 961*c793af95Ssangeeta } 962*c793af95Ssangeeta if (t->rn_left == tt) 963*c793af95Ssangeeta x = t->rn_right; 964*c793af95Ssangeeta else 965*c793af95Ssangeeta x = t->rn_left; 966*c793af95Ssangeeta p = t->rn_parent; 967*c793af95Ssangeeta if (p->rn_right == t) 968*c793af95Ssangeeta p->rn_right = x; 969*c793af95Ssangeeta else 970*c793af95Ssangeeta p->rn_left = x; 971*c793af95Ssangeeta x->rn_parent = p; 972*c793af95Ssangeeta /* 973*c793af95Ssangeeta * Demote routes attached to us. 974*c793af95Ssangeeta */ 975*c793af95Ssangeeta if (t->rn_mklist) { 976*c793af95Ssangeeta if (x->rn_bit >= 0) { 977*c793af95Ssangeeta for (mp = &x->rn_mklist; (m = *mp) != NULL; ) 978*c793af95Ssangeeta mp = &m->rm_mklist; 979*c793af95Ssangeeta *mp = t->rn_mklist; 980*c793af95Ssangeeta } else { 981*c793af95Ssangeeta /* 982*c793af95Ssangeeta * If there are any key,mask pairs in a sibling 983*c793af95Ssangeeta * duped-key chain, some subset will appear sorted 984*c793af95Ssangeeta * in the same order attached to our mklist 985*c793af95Ssangeeta */ 986*c793af95Ssangeeta for (m = t->rn_mklist; m && x; x = x->rn_dupedkey) 987*c793af95Ssangeeta if (m == x->rn_mklist) { 988*c793af95Ssangeeta struct radix_mask *mm = m->rm_mklist; 989*c793af95Ssangeeta x->rn_mklist = 0; 990*c793af95Ssangeeta if (--(m->rm_refs) < 0) 991*c793af95Ssangeeta MKFree(m); 992*c793af95Ssangeeta m = mm; 993*c793af95Ssangeeta } 994*c793af95Ssangeeta if (m) 995*c793af95Ssangeeta #ifdef _KERNEL 996*c793af95Ssangeeta cmn_err(CE_WARN, 997*c793af95Ssangeeta "rn_delete: Orphaned Mask %p at %p\n", 998*c793af95Ssangeeta (void *)m, (void *)x); 999*c793af95Ssangeeta #else 1000*c793af95Ssangeeta syslog(LOG_ERR, 1001*c793af95Ssangeeta "rn_delete: Orphaned Mask %p at %p\n", 1002*c793af95Ssangeeta (void *)m, (void *)x); 1003*c793af95Ssangeeta #endif /* _KERNEL */ 1004*c793af95Ssangeeta } 1005*c793af95Ssangeeta } 1006*c793af95Ssangeeta /* 1007*c793af95Ssangeeta * We may be holding an active internal node in the tree. 1008*c793af95Ssangeeta */ 1009*c793af95Ssangeeta x = tt + 1; 1010*c793af95Ssangeeta if (t != x) { 1011*c793af95Ssangeeta *t = *x; 1012*c793af95Ssangeeta t->rn_left->rn_parent = t; 1013*c793af95Ssangeeta t->rn_right->rn_parent = t; 1014*c793af95Ssangeeta p = x->rn_parent; 1015*c793af95Ssangeeta if (p->rn_left == x) 1016*c793af95Ssangeeta p->rn_left = t; 1017*c793af95Ssangeeta else 1018*c793af95Ssangeeta p->rn_right = t; 1019*c793af95Ssangeeta } 1020*c793af95Ssangeeta out: 1021*c793af95Ssangeeta tt->rn_flags &= ~RNF_ACTIVE; 1022*c793af95Ssangeeta tt[1].rn_flags &= ~RNF_ACTIVE; 1023*c793af95Ssangeeta return (tt); 1024*c793af95Ssangeeta } 1025*c793af95Ssangeeta 1026*c793af95Ssangeeta /* 1027*c793af95Ssangeeta * Walk the radix tree; For the kernel routing table, we hold additional 1028*c793af95Ssangeeta * refs on the ire_bucket to ensure that the walk function f() does not 1029*c793af95Ssangeeta * run into trashed memory. The kernel routing table is identified by 1030*c793af95Ssangeeta * a rnh_treetop that has RNF_SUNW_FT set in the rn_flags. 1031*c793af95Ssangeeta * Note that all refs takein in rn_walktree are released before it returns, 1032*c793af95Ssangeeta * so that f() will need to take any additional references on memory 1033*c793af95Ssangeeta * to be passed back to the caller of rn_walktree. 1034*c793af95Ssangeeta */ 1035*c793af95Ssangeeta static int 1036*c793af95Ssangeeta rn_walktree(h, f, w) 1037*c793af95Ssangeeta struct radix_node_head *h; 1038*c793af95Ssangeeta walktree_f_t *f; 1039*c793af95Ssangeeta void *w; 1040*c793af95Ssangeeta { 1041*c793af95Ssangeeta int error; 1042*c793af95Ssangeeta struct radix_node *base, *next; 1043*c793af95Ssangeeta struct radix_node *rn = h->rnh_treetop; 1044*c793af95Ssangeeta boolean_t is_ftable = B_FALSE; 1045*c793af95Ssangeeta 1046*c793af95Ssangeeta if (h->rnh_treetop->rn_flags & RNF_SUNW_FT) { 1047*c793af95Ssangeeta /* 1048*c793af95Ssangeeta * this is a kernel ip ftable with rt_t leaf structures. 1049*c793af95Ssangeeta */ 1050*c793af95Ssangeeta is_ftable = B_TRUE; 1051*c793af95Ssangeeta } 1052*c793af95Ssangeeta /* 1053*c793af95Ssangeeta * This gets complicated because we may delete the node 1054*c793af95Ssangeeta * while applying the function f to it, so we need to calculate 1055*c793af95Ssangeeta * the successor node in advance. 1056*c793af95Ssangeeta */ 1057*c793af95Ssangeeta RADIX_NODE_HEAD_RLOCK(h); 1058*c793af95Ssangeeta /* First time through node, go left */ 1059*c793af95Ssangeeta while (rn->rn_bit >= 0) { 1060*c793af95Ssangeeta rn = rn->rn_left; 1061*c793af95Ssangeeta } 1062*c793af95Ssangeeta 1063*c793af95Ssangeeta if (is_ftable) 1064*c793af95Ssangeeta IRB_REFHOLD_RN(rn); 1065*c793af95Ssangeeta 1066*c793af95Ssangeeta for (;;) { 1067*c793af95Ssangeeta base = rn; 1068*c793af95Ssangeeta /* If at right child go back up, otherwise, go right */ 1069*c793af95Ssangeeta while (rn->rn_parent->rn_right == rn && 1070*c793af95Ssangeeta (rn->rn_flags & RNF_ROOT) == 0) { 1071*c793af95Ssangeeta rn = rn->rn_parent; 1072*c793af95Ssangeeta } 1073*c793af95Ssangeeta /* Find the next *leaf* since next node might vanish, too */ 1074*c793af95Ssangeeta for (rn = rn->rn_parent->rn_right; rn->rn_bit >= 0; ) { 1075*c793af95Ssangeeta rn = rn->rn_left; 1076*c793af95Ssangeeta } 1077*c793af95Ssangeeta next = rn; 1078*c793af95Ssangeeta 1079*c793af95Ssangeeta if (is_ftable && next != NULL) 1080*c793af95Ssangeeta IRB_REFHOLD_RN(next); 1081*c793af95Ssangeeta 1082*c793af95Ssangeeta /* Process leaves */ 1083*c793af95Ssangeeta while ((rn = base) != NULL) { 1084*c793af95Ssangeeta base = rn->rn_dupedkey; 1085*c793af95Ssangeeta 1086*c793af95Ssangeeta if (is_ftable && base != NULL) 1087*c793af95Ssangeeta IRB_REFHOLD_RN(base); 1088*c793af95Ssangeeta 1089*c793af95Ssangeeta RADIX_NODE_HEAD_UNLOCK(h); 1090*c793af95Ssangeeta if (!(rn->rn_flags & RNF_ROOT) && 1091*c793af95Ssangeeta (error = (*f)(rn, w))) { 1092*c793af95Ssangeeta if (is_ftable) { 1093*c793af95Ssangeeta if (rn != NULL) 1094*c793af95Ssangeeta IRB_REFRELE_RN(rn); 1095*c793af95Ssangeeta if (base != NULL) 1096*c793af95Ssangeeta IRB_REFRELE_RN(base); 1097*c793af95Ssangeeta if (next != NULL) 1098*c793af95Ssangeeta IRB_REFRELE_RN(next); 1099*c793af95Ssangeeta } 1100*c793af95Ssangeeta return (error); 1101*c793af95Ssangeeta } 1102*c793af95Ssangeeta if (is_ftable && rn != NULL) 1103*c793af95Ssangeeta IRB_REFRELE_RN(rn); 1104*c793af95Ssangeeta RADIX_NODE_HEAD_RLOCK(h); 1105*c793af95Ssangeeta } 1106*c793af95Ssangeeta rn = next; 1107*c793af95Ssangeeta if (rn->rn_flags & RNF_ROOT) { 1108*c793af95Ssangeeta RADIX_NODE_HEAD_UNLOCK(h); 1109*c793af95Ssangeeta return (0); 1110*c793af95Ssangeeta } 1111*c793af95Ssangeeta } 1112*c793af95Ssangeeta /* NOTREACHED */ 1113*c793af95Ssangeeta } 1114*c793af95Ssangeeta 1115*c793af95Ssangeeta /* 1116*c793af95Ssangeeta * Allocate and initialize an empty tree. This has 3 nodes, which are 1117*c793af95Ssangeeta * part of the radix_node_head (in the order <left,root,right>) and are 1118*c793af95Ssangeeta * marked RNF_ROOT so they cannot be freed. 1119*c793af95Ssangeeta * The leaves have all-zero and all-one keys, with significant 1120*c793af95Ssangeeta * bits starting at 'off'. 1121*c793af95Ssangeeta * Return 1 on success, 0 on error. 1122*c793af95Ssangeeta */ 1123*c793af95Ssangeeta int 1124*c793af95Ssangeeta rn_inithead(head, off) 1125*c793af95Ssangeeta void **head; 1126*c793af95Ssangeeta int off; 1127*c793af95Ssangeeta { 1128*c793af95Ssangeeta struct radix_node_head *rnh; 1129*c793af95Ssangeeta struct radix_node *t, *tt, *ttt; 1130*c793af95Ssangeeta if (*head) 1131*c793af95Ssangeeta return (1); 1132*c793af95Ssangeeta R_ZallocSleep(rnh, struct radix_node_head *, sizeof (*rnh)); 1133*c793af95Ssangeeta if (rnh == 0) 1134*c793af95Ssangeeta return (0); 1135*c793af95Ssangeeta #ifdef _KERNEL 1136*c793af95Ssangeeta RADIX_NODE_HEAD_LOCK_INIT(rnh); 1137*c793af95Ssangeeta #endif 1138*c793af95Ssangeeta *head = rnh; 1139*c793af95Ssangeeta t = rn_newpair(rn_zeros, off, rnh->rnh_nodes); 1140*c793af95Ssangeeta ttt = rnh->rnh_nodes + 2; 1141*c793af95Ssangeeta t->rn_right = ttt; 1142*c793af95Ssangeeta t->rn_parent = t; 1143*c793af95Ssangeeta tt = t->rn_left; /* ... which in turn is rnh->rnh_nodes */ 1144*c793af95Ssangeeta tt->rn_flags = t->rn_flags = RNF_ROOT | RNF_ACTIVE; 1145*c793af95Ssangeeta tt->rn_bit = -1 - off; 1146*c793af95Ssangeeta *ttt = *tt; 1147*c793af95Ssangeeta ttt->rn_key = rn_ones; 1148*c793af95Ssangeeta rnh->rnh_addaddr = rn_addroute; 1149*c793af95Ssangeeta rnh->rnh_deladdr = rn_delete; 1150*c793af95Ssangeeta rnh->rnh_matchaddr = rn_match; 1151*c793af95Ssangeeta rnh->rnh_matchaddr_args = rn_match_args; 1152*c793af95Ssangeeta rnh->rnh_lookup = rn_lookup; 1153*c793af95Ssangeeta rnh->rnh_walktree = rn_walktree; 1154*c793af95Ssangeeta rnh->rnh_walktree_from = NULL; /* not implemented */ 1155*c793af95Ssangeeta rnh->rnh_treetop = t; 1156*c793af95Ssangeeta return (1); 1157*c793af95Ssangeeta } 1158*c793af95Ssangeeta 1159*c793af95Ssangeeta void 1160*c793af95Ssangeeta rn_init() 1161*c793af95Ssangeeta { 1162*c793af95Ssangeeta char *cp, *cplim; 1163*c793af95Ssangeeta 1164*c793af95Ssangeeta #ifdef _KERNEL 1165*c793af95Ssangeeta radix_mask_cache = kmem_cache_create("radix_mask", 1166*c793af95Ssangeeta sizeof (struct radix_mask), 0, NULL, NULL, NULL, NULL, NULL, 0); 1167*c793af95Ssangeeta radix_node_cache = kmem_cache_create("radix_node", 1168*c793af95Ssangeeta max_keylen + 2 * sizeof (struct radix_node), 1169*c793af95Ssangeeta 0, NULL, NULL, NULL, NULL, NULL, 0); 1170*c793af95Ssangeeta #endif /* _KERNEL */ 1171*c793af95Ssangeeta R_ZallocSleep(rn_zeros, char *, 2 * max_keylen); 1172*c793af95Ssangeeta 1173*c793af95Ssangeeta ASSERT(rn_zeros != NULL); 1174*c793af95Ssangeeta bzero(rn_zeros, 2 * max_keylen); 1175*c793af95Ssangeeta rn_ones = cp = rn_zeros + max_keylen; 1176*c793af95Ssangeeta cplim = rn_ones + max_keylen; 1177*c793af95Ssangeeta while (cp < cplim) 1178*c793af95Ssangeeta *cp++ = -1; 1179*c793af95Ssangeeta if (rn_inithead((void **)(void *)&mask_rnhead, 0) == 0) 1180*c793af95Ssangeeta panic("rn_init: could not init mask_rnhead "); 1181*c793af95Ssangeeta } 1182*c793af95Ssangeeta 1183*c793af95Ssangeeta int 1184*c793af95Ssangeeta rn_freenode(n, p) 1185*c793af95Ssangeeta struct radix_node *n; 1186*c793af95Ssangeeta void *p; 1187*c793af95Ssangeeta { 1188*c793af95Ssangeeta struct radix_node_head *rnh = p; 1189*c793af95Ssangeeta struct radix_node *d; 1190*c793af95Ssangeeta 1191*c793af95Ssangeeta d = rnh->rnh_deladdr(n->rn_key, NULL, rnh); 1192*c793af95Ssangeeta if (d != NULL) { 1193*c793af95Ssangeeta Free(d, radix_node_cache); 1194*c793af95Ssangeeta } 1195*c793af95Ssangeeta return (0); 1196*c793af95Ssangeeta } 1197*c793af95Ssangeeta 1198*c793af95Ssangeeta 1199*c793af95Ssangeeta void 1200*c793af95Ssangeeta rn_freehead(rnh) 1201*c793af95Ssangeeta struct radix_node_head *rnh; 1202*c793af95Ssangeeta { 1203*c793af95Ssangeeta (void) rn_walktree(rnh, rn_freenode, rnh); 1204*c793af95Ssangeeta 1205*c793af95Ssangeeta rnh->rnh_addaddr = NULL; 1206*c793af95Ssangeeta rnh->rnh_deladdr = NULL; 1207*c793af95Ssangeeta rnh->rnh_matchaddr = NULL; 1208*c793af95Ssangeeta rnh->rnh_lookup = NULL; 1209*c793af95Ssangeeta rnh->rnh_walktree = NULL; 1210*c793af95Ssangeeta 1211*c793af95Ssangeeta #ifdef _KERNEL 1212*c793af95Ssangeeta FreeHead(rnh, sizeof (*rnh)); 1213*c793af95Ssangeeta #else 1214*c793af95Ssangeeta Free(rnh, NULL); 1215*c793af95Ssangeeta #endif /* _KERNEL */ 1216*c793af95Ssangeeta } 1217*c793af95Ssangeeta 1218*c793af95Ssangeeta void 1219*c793af95Ssangeeta rn_fini() 1220*c793af95Ssangeeta { 1221*c793af95Ssangeeta struct radix_mask *m; 1222*c793af95Ssangeeta 1223*c793af95Ssangeeta if (rn_zeros != NULL) { 1224*c793af95Ssangeeta #ifdef _KERNEL 1225*c793af95Ssangeeta FreeHead(rn_zeros, 2 * max_keylen); 1226*c793af95Ssangeeta #else 1227*c793af95Ssangeeta Free(rn_zeros, NULL); 1228*c793af95Ssangeeta #endif 1229*c793af95Ssangeeta rn_zeros = NULL; 1230*c793af95Ssangeeta } 1231*c793af95Ssangeeta 1232*c793af95Ssangeeta 1233*c793af95Ssangeeta if (mask_rnhead != NULL) { 1234*c793af95Ssangeeta rn_freehead(mask_rnhead); 1235*c793af95Ssangeeta mask_rnhead = NULL; 1236*c793af95Ssangeeta } 1237*c793af95Ssangeeta 1238*c793af95Ssangeeta while ((m = rn_mkfreelist) != NULL) { 1239*c793af95Ssangeeta rn_mkfreelist = m->rm_mklist; 1240*c793af95Ssangeeta Free(m, NULL); 1241*c793af95Ssangeeta } 1242*c793af95Ssangeeta } 1243