radix.c revision 210122
1139823Simp/*- 21541Srgrimes * Copyright (c) 1988, 1989, 1993 31541Srgrimes * The Regents of the University of California. All rights reserved. 41541Srgrimes * 51541Srgrimes * Redistribution and use in source and binary forms, with or without 61541Srgrimes * modification, are permitted provided that the following conditions 71541Srgrimes * are met: 81541Srgrimes * 1. Redistributions of source code must retain the above copyright 91541Srgrimes * notice, this list of conditions and the following disclaimer. 101541Srgrimes * 2. Redistributions in binary form must reproduce the above copyright 111541Srgrimes * notice, this list of conditions and the following disclaimer in the 121541Srgrimes * documentation and/or other materials provided with the distribution. 131541Srgrimes * 4. Neither the name of the University nor the names of its contributors 141541Srgrimes * may be used to endorse or promote products derived from this software 151541Srgrimes * without specific prior written permission. 161541Srgrimes * 171541Srgrimes * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 181541Srgrimes * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 191541Srgrimes * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 201541Srgrimes * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 211541Srgrimes * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 221541Srgrimes * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 231541Srgrimes * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 241541Srgrimes * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 251541Srgrimes * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 261541Srgrimes * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 271541Srgrimes * SUCH DAMAGE. 281541Srgrimes * 29108268Sru * @(#)radix.c 8.5 (Berkeley) 5/19/95 3050477Speter * $FreeBSD: head/sys/net/radix.c 210122 2010-07-15 14:41:59Z luigi $ 311541Srgrimes */ 321541Srgrimes 331541Srgrimes/* 341541Srgrimes * Routines to build and maintain radix trees for routing lookups. 351541Srgrimes */ 361541Srgrimes#include <sys/param.h> 3755205Speter#ifdef _KERNEL 38110527Shsu#include <sys/lock.h> 39110527Shsu#include <sys/mutex.h> 40185747Skmacy#include <sys/rwlock.h> 411541Srgrimes#include <sys/systm.h> 421541Srgrimes#include <sys/malloc.h> 438152Spst#include <sys/syslog.h> 448152Spst#include <net/radix.h> 45178167Sqingli#include "opt_mpath.h" 46178167Sqingli#ifdef RADIX_MPATH 47178167Sqingli#include <net/radix_mpath.h> 48178167Sqingli#endif 49200439Sluigi#else /* !_KERNEL */ 50200439Sluigi#include <stdio.h> 51200439Sluigi#include <strings.h> 52200439Sluigi#include <stdlib.h> 53210122Sluigi#define log(x, arg...) fprintf(stderr, ## arg) 54210122Sluigi#define panic(x) fprintf(stderr, "PANIC: %s", x), exit(1) 55200439Sluigi#define min(a, b) ((a) < (b) ? (a) : (b) ) 56200439Sluigi#include <net/radix.h> 57200439Sluigi#endif /* !_KERNEL */ 58178167Sqingli 5993084Sbdestatic int rn_walktree_from(struct radix_node_head *h, void *a, void *m, 6093084Sbde walktree_f_t *f, void *w); 6192725Salfredstatic int rn_walktree(struct radix_node_head *, walktree_f_t *, void *); 6212820Sphkstatic struct radix_node 6392725Salfred *rn_insert(void *, struct radix_node_head *, int *, 6493084Sbde struct radix_node [2]), 6592725Salfred *rn_newpair(void *, int, struct radix_node[2]), 6692725Salfred *rn_search(void *, struct radix_node *), 6792725Salfred *rn_search_m(void *, struct radix_node *, void *); 6812579Sbde 6912820Sphkstatic int max_keylen; 7012820Sphkstatic struct radix_mask *rn_mkfreelist; 7112820Sphkstatic struct radix_node_head *mask_rnhead; 72128433Sluigi/* 73128433Sluigi * Work area -- the following point to 3 buffers of size max_keylen, 74128433Sluigi * allocated in this order in a block of memory malloc'ed by rn_init. 75200354Sluigi * rn_zeros, rn_ones are set in rn_init and used in readonly afterwards. 76200354Sluigi * addmask_key is used in rn_addmask in rw mode and not thread-safe. 77128433Sluigi */ 78128433Sluigistatic char *rn_zeros, *rn_ones, *addmask_key; 791541Srgrimes 80128401Sluigi#define MKGet(m) { \ 81128401Sluigi if (rn_mkfreelist) { \ 82128401Sluigi m = rn_mkfreelist; \ 83128401Sluigi rn_mkfreelist = (m)->rm_mklist; \ 84128401Sluigi } else \ 85128401Sluigi R_Malloc(m, struct radix_mask *, sizeof (struct radix_mask)); } 86128401Sluigi 87128401Sluigi#define MKFree(m) { (m)->rm_mklist = rn_mkfreelist; rn_mkfreelist = (m);} 88128401Sluigi 891541Srgrimes#define rn_masktop (mask_rnhead->rnh_treetop) 9012579Sbde 9192725Salfredstatic int rn_lexobetter(void *m_arg, void *n_arg); 9212579Sbdestatic struct radix_mask * 9392725Salfred rn_new_radix_mask(struct radix_node *tt, 9493084Sbde struct radix_mask *next); 95108273Srustatic int rn_satisfies_leaf(char *trial, struct radix_node *leaf, 9693084Sbde int skip); 9712579Sbde 981541Srgrimes/* 991541Srgrimes * The data structure for the keys is a radix tree with one way 10059529Swollman * branching removed. The index rn_bit at an internal node n represents a bit 1011541Srgrimes * position to be tested. The tree is arranged so that all descendants 10259529Swollman * of a node n have keys whose bits all agree up to position rn_bit - 1. 10359529Swollman * (We say the index of n is rn_bit.) 1041541Srgrimes * 10559529Swollman * There is at least one descendant which has a one bit at position rn_bit, 1061541Srgrimes * and at least one with a zero there. 1071541Srgrimes * 1081541Srgrimes * A route is determined by a pair of key and mask. We require that the 1091541Srgrimes * bit-wise logical and of the key and mask to be the key. 1101541Srgrimes * We define the index of a route to associated with the mask to be 1111541Srgrimes * the first bit number in the mask where 0 occurs (with bit number 0 1121541Srgrimes * representing the highest order bit). 1138876Srgrimes * 1141541Srgrimes * We say a mask is normal if every bit is 0, past the index of the mask. 11559529Swollman * If a node n has a descendant (k, m) with index(m) == index(n) == rn_bit, 1161541Srgrimes * and m is a normal mask, then the route applies to every descendant of n. 11759529Swollman * If the index(m) < rn_bit, this implies the trailing last few bits of k 1181541Srgrimes * before bit b are all 0, (and hence consequently true of every descendant 1191541Srgrimes * of n), so the route applies to all descendants of the node as well. 1208876Srgrimes * 1218152Spst * Similar logic shows that a non-normal mask m such that 1221541Srgrimes * index(m) <= index(n) could potentially apply to many children of n. 1231541Srgrimes * Thus, for each non-host route, we attach its mask to a list at an internal 1248876Srgrimes * node as high in the tree as we can go. 1258152Spst * 1268152Spst * The present version of the code makes use of normal routes in short- 1278152Spst * circuiting an explict mask and compare operation when testing whether 1288152Spst * a key satisfies a normal route, and also in remembering the unique leaf 1298152Spst * that governs a subtree. 1301541Srgrimes */ 1311541Srgrimes 132128525Sluigi/* 133128525Sluigi * Most of the functions in this code assume that the key/mask arguments 134128525Sluigi * are sockaddr-like structures, where the first byte is an u_char 135128525Sluigi * indicating the size of the entire structure. 136128525Sluigi * 137128525Sluigi * To make the assumption more explicit, we use the LEN() macro to access 138128525Sluigi * this field. It is safe to pass an expression with side effects 139128525Sluigi * to LEN() as the argument is evaluated only once. 140200354Sluigi * We cast the result to int as this is the dominant usage. 141128525Sluigi */ 142200354Sluigi#define LEN(x) ( (int) (*(const u_char *)(x)) ) 143128525Sluigi 144128525Sluigi/* 145128525Sluigi * XXX THIS NEEDS TO BE FIXED 146128525Sluigi * In the code, pointers to keys and masks are passed as either 147128525Sluigi * 'void *' (because callers use to pass pointers of various kinds), or 148128525Sluigi * 'caddr_t' (which is fine for pointer arithmetics, but not very 149128525Sluigi * clean when you dereference it to access data). Furthermore, caddr_t 150128525Sluigi * is really 'char *', while the natural type to operate on keys and 151128525Sluigi * masks would be 'u_char'. This mismatch require a lot of casts and 152128525Sluigi * intermediate variables to adapt types that clutter the code. 153128525Sluigi */ 154128525Sluigi 155128525Sluigi/* 156128525Sluigi * Search a node in the tree matching the key. 157128525Sluigi */ 15812820Sphkstatic struct radix_node * 1591541Srgrimesrn_search(v_arg, head) 1601541Srgrimes void *v_arg; 1611541Srgrimes struct radix_node *head; 1621541Srgrimes{ 1631541Srgrimes register struct radix_node *x; 1641541Srgrimes register caddr_t v; 1651541Srgrimes 16659529Swollman for (x = head, v = v_arg; x->rn_bit >= 0;) { 16759529Swollman if (x->rn_bmask & v[x->rn_offset]) 16859529Swollman x = x->rn_right; 1691541Srgrimes else 17059529Swollman x = x->rn_left; 1711541Srgrimes } 1721541Srgrimes return (x); 17331390Sbde} 1741541Srgrimes 175128525Sluigi/* 176128525Sluigi * Same as above, but with an additional mask. 177128525Sluigi * XXX note this function is used only once. 178128525Sluigi */ 17912820Sphkstatic struct radix_node * 1801541Srgrimesrn_search_m(v_arg, head, m_arg) 1811541Srgrimes struct radix_node *head; 1821541Srgrimes void *v_arg, *m_arg; 1831541Srgrimes{ 1841541Srgrimes register struct radix_node *x; 1851541Srgrimes register caddr_t v = v_arg, m = m_arg; 1861541Srgrimes 18759529Swollman for (x = head; x->rn_bit >= 0;) { 18859529Swollman if ((x->rn_bmask & m[x->rn_offset]) && 18959529Swollman (x->rn_bmask & v[x->rn_offset])) 19059529Swollman x = x->rn_right; 1911541Srgrimes else 19259529Swollman x = x->rn_left; 1931541Srgrimes } 1941541Srgrimes return x; 19531390Sbde} 1961541Srgrimes 1971541Srgrimesint 1981541Srgrimesrn_refines(m_arg, n_arg) 1991541Srgrimes void *m_arg, *n_arg; 2001541Srgrimes{ 2011541Srgrimes register caddr_t m = m_arg, n = n_arg; 202128525Sluigi register caddr_t lim, lim2 = lim = n + LEN(n); 203200354Sluigi int longer = LEN(n++) - LEN(m++); 2041541Srgrimes int masks_are_equal = 1; 2051541Srgrimes 2061541Srgrimes if (longer > 0) 2071541Srgrimes lim -= longer; 2081541Srgrimes while (n < lim) { 2091541Srgrimes if (*n & ~(*m)) 2101541Srgrimes return 0; 2111541Srgrimes if (*n++ != *m++) 2121541Srgrimes masks_are_equal = 0; 2131541Srgrimes } 2141541Srgrimes while (n < lim2) 2151541Srgrimes if (*n++) 2161541Srgrimes return 0; 2171541Srgrimes if (masks_are_equal && (longer < 0)) 2181541Srgrimes for (lim2 = m - longer; m < lim2; ) 2191541Srgrimes if (*m++) 2201541Srgrimes return 1; 2211541Srgrimes return (!masks_are_equal); 2221541Srgrimes} 2231541Srgrimes 2248152Spststruct radix_node * 2258152Spstrn_lookup(v_arg, m_arg, head) 2268152Spst void *v_arg, *m_arg; 2278152Spst struct radix_node_head *head; 2288152Spst{ 2298152Spst register struct radix_node *x; 2308152Spst caddr_t netmask = 0; 2311541Srgrimes 2328152Spst if (m_arg) { 23359529Swollman x = rn_addmask(m_arg, 1, head->rnh_treetop->rn_offset); 23459529Swollman if (x == 0) 2358152Spst return (0); 2368152Spst netmask = x->rn_key; 2378152Spst } 2388152Spst x = rn_match(v_arg, head); 2398152Spst if (x && netmask) { 2408152Spst while (x && x->rn_mask != netmask) 2418152Spst x = x->rn_dupedkey; 2428152Spst } 2438152Spst return x; 2448152Spst} 2458152Spst 2468152Spststatic int 247108273Srurn_satisfies_leaf(trial, leaf, skip) 2488152Spst char *trial; 2498152Spst register struct radix_node *leaf; 2508152Spst int skip; 2518152Spst{ 2528152Spst register char *cp = trial, *cp2 = leaf->rn_key, *cp3 = leaf->rn_mask; 2538152Spst char *cplim; 254128525Sluigi int length = min(LEN(cp), LEN(cp2)); 2558152Spst 256200354Sluigi if (cp3 == NULL) 2578152Spst cp3 = rn_ones; 2588152Spst else 259200354Sluigi length = min(length, LEN(cp3)); 2608152Spst cplim = cp + length; cp3 += skip; cp2 += skip; 2618152Spst for (cp += skip; cp < cplim; cp++, cp2++, cp3++) 2628152Spst if ((*cp ^ *cp2) & *cp3) 2638152Spst return 0; 2648152Spst return 1; 2658152Spst} 2668152Spst 2671541Srgrimesstruct radix_node * 2681541Srgrimesrn_match(v_arg, head) 2691541Srgrimes void *v_arg; 2701541Srgrimes struct radix_node_head *head; 2711541Srgrimes{ 2721541Srgrimes caddr_t v = v_arg; 2731541Srgrimes register struct radix_node *t = head->rnh_treetop, *x; 2748152Spst register caddr_t cp = v, cp2; 2758152Spst caddr_t cplim; 2761541Srgrimes struct radix_node *saved_t, *top = t; 277128525Sluigi int off = t->rn_offset, vlen = LEN(cp), matched_off; 27859529Swollman register int test, b, rn_bit; 2791541Srgrimes 2801541Srgrimes /* 2811541Srgrimes * Open code rn_search(v, top) to avoid overhead of extra 2821541Srgrimes * subroutine call. 2831541Srgrimes */ 28459529Swollman for (; t->rn_bit >= 0; ) { 28559529Swollman if (t->rn_bmask & cp[t->rn_offset]) 28659529Swollman t = t->rn_right; 2871541Srgrimes else 28859529Swollman t = t->rn_left; 2891541Srgrimes } 2901541Srgrimes /* 2911541Srgrimes * See if we match exactly as a host destination 2928152Spst * or at least learn how many bits match, for normal mask finesse. 2938152Spst * 2948152Spst * It doesn't hurt us to limit how many bytes to check 2958152Spst * to the length of the mask, since if it matches we had a genuine 2968152Spst * match and the leaf we have is the most specific one anyway; 2978152Spst * if it didn't match with a shorter length it would fail 2988152Spst * with a long one. This wins big for class B&C netmasks which 2998152Spst * are probably the most common case... 3001541Srgrimes */ 3018152Spst if (t->rn_mask) 3028152Spst vlen = *(u_char *)t->rn_mask; 3031541Srgrimes cp += off; cp2 = t->rn_key + off; cplim = v + vlen; 3041541Srgrimes for (; cp < cplim; cp++, cp2++) 3051541Srgrimes if (*cp != *cp2) 3061541Srgrimes goto on1; 3071541Srgrimes /* 3081541Srgrimes * This extra grot is in case we are explicitly asked 3091541Srgrimes * to look up the default. Ugh! 31048215Spb * 31148215Spb * Never return the root node itself, it seems to cause a 31248215Spb * lot of confusion. 3131541Srgrimes */ 31448215Spb if (t->rn_flags & RNF_ROOT) 3151541Srgrimes t = t->rn_dupedkey; 3161541Srgrimes return t; 3171541Srgrimeson1: 3188152Spst test = (*cp ^ *cp2) & 0xff; /* find first bit that differs */ 3198152Spst for (b = 7; (test >>= 1) > 0;) 3208152Spst b--; 3211541Srgrimes matched_off = cp - v; 3228152Spst b += matched_off << 3; 32359529Swollman rn_bit = -1 - b; 3248152Spst /* 3258152Spst * If there is a host route in a duped-key chain, it will be first. 3268152Spst */ 3278152Spst if ((saved_t = t)->rn_mask == 0) 3288152Spst t = t->rn_dupedkey; 3298152Spst for (; t; t = t->rn_dupedkey) 3301541Srgrimes /* 3318152Spst * Even if we don't match exactly as a host, 3321541Srgrimes * we may match if the leaf we wound up at is 3331541Srgrimes * a route to a net. 3341541Srgrimes */ 3358152Spst if (t->rn_flags & RNF_NORMAL) { 33659529Swollman if (rn_bit <= t->rn_bit) 3378152Spst return t; 338108273Sru } else if (rn_satisfies_leaf(v, t, matched_off)) 3398152Spst return t; 3401541Srgrimes t = saved_t; 3411541Srgrimes /* start searching up the tree */ 3421541Srgrimes do { 3431541Srgrimes register struct radix_mask *m; 34459529Swollman t = t->rn_parent; 3453443Sphk m = t->rn_mklist; 34659529Swollman /* 34759529Swollman * If non-contiguous masks ever become important 34859529Swollman * we can restore the masking and open coding of 34959529Swollman * the search and satisfaction test and put the 35059529Swollman * calculation of "off" back before the "do". 35159529Swollman */ 35259529Swollman while (m) { 35359529Swollman if (m->rm_flags & RNF_NORMAL) { 35459529Swollman if (rn_bit <= m->rm_bit) 35559529Swollman return (m->rm_leaf); 35659529Swollman } else { 35759529Swollman off = min(t->rn_offset, matched_off); 35859529Swollman x = rn_search_m(v, t, m->rm_mask); 35959529Swollman while (x && x->rn_mask != m->rm_mask) 36059529Swollman x = x->rn_dupedkey; 361108273Sru if (x && rn_satisfies_leaf(v, x, off)) 36259529Swollman return x; 36359529Swollman } 36459529Swollman m = m->rm_mklist; 3651541Srgrimes } 3661541Srgrimes } while (t != top); 3671541Srgrimes return 0; 36831390Sbde} 3698876Srgrimes 3701541Srgrimes#ifdef RN_DEBUG 3711541Srgrimesint rn_nodenum; 3721541Srgrimesstruct radix_node *rn_clist; 3731541Srgrimesint rn_saveinfo; 3741541Srgrimesint rn_debug = 1; 3751541Srgrimes#endif 3761541Srgrimes 377128525Sluigi/* 378128525Sluigi * Whenever we add a new leaf to the tree, we also add a parent node, 379128525Sluigi * so we allocate them as an array of two elements: the first one must be 380128525Sluigi * the leaf (see RNTORT() in route.c), the second one is the parent. 381128525Sluigi * This routine initializes the relevant fields of the nodes, so that 382128525Sluigi * the leaf is the left child of the parent node, and both nodes have 383128525Sluigi * (almost) all all fields filled as appropriate. 384128525Sluigi * (XXX some fields are left unset, see the '#if 0' section). 385128525Sluigi * The function returns a pointer to the parent node. 386128525Sluigi */ 387128525Sluigi 38812820Sphkstatic struct radix_node * 3891541Srgrimesrn_newpair(v, b, nodes) 3901541Srgrimes void *v; 3911541Srgrimes int b; 3921541Srgrimes struct radix_node nodes[2]; 3931541Srgrimes{ 3941541Srgrimes register struct radix_node *tt = nodes, *t = tt + 1; 39559529Swollman t->rn_bit = b; 39659529Swollman t->rn_bmask = 0x80 >> (b & 7); 39759529Swollman t->rn_left = tt; 39859529Swollman t->rn_offset = b >> 3; 399128525Sluigi 400128525Sluigi#if 0 /* XXX perhaps we should fill these fields as well. */ 401128525Sluigi t->rn_parent = t->rn_right = NULL; 402128525Sluigi 403128525Sluigi tt->rn_mask = NULL; 404128525Sluigi tt->rn_dupedkey = NULL; 405128525Sluigi tt->rn_bmask = 0; 406128525Sluigi#endif 40759529Swollman tt->rn_bit = -1; 40859529Swollman tt->rn_key = (caddr_t)v; 40959529Swollman tt->rn_parent = t; 4101541Srgrimes tt->rn_flags = t->rn_flags = RNF_ACTIVE; 41167727Swollman tt->rn_mklist = t->rn_mklist = 0; 4121541Srgrimes#ifdef RN_DEBUG 4131541Srgrimes tt->rn_info = rn_nodenum++; t->rn_info = rn_nodenum++; 41459529Swollman tt->rn_twin = t; 41559529Swollman tt->rn_ybro = rn_clist; 41659529Swollman rn_clist = tt; 4171541Srgrimes#endif 4181541Srgrimes return t; 4191541Srgrimes} 4201541Srgrimes 42112820Sphkstatic struct radix_node * 4221541Srgrimesrn_insert(v_arg, head, dupentry, nodes) 4231541Srgrimes void *v_arg; 4241541Srgrimes struct radix_node_head *head; 4251541Srgrimes int *dupentry; 4261541Srgrimes struct radix_node nodes[2]; 4271541Srgrimes{ 4281541Srgrimes caddr_t v = v_arg; 4291541Srgrimes struct radix_node *top = head->rnh_treetop; 430200354Sluigi int head_off = top->rn_offset, vlen = LEN(v); 4311541Srgrimes register struct radix_node *t = rn_search(v_arg, top); 4321541Srgrimes register caddr_t cp = v + head_off; 4331541Srgrimes register int b; 4341541Srgrimes struct radix_node *tt; 4351541Srgrimes /* 4368152Spst * Find first bit at which v and t->rn_key differ 4371541Srgrimes */ 4381541Srgrimes { 4391541Srgrimes register caddr_t cp2 = t->rn_key + head_off; 4401541Srgrimes register int cmp_res; 4411541Srgrimes caddr_t cplim = v + vlen; 4421541Srgrimes 4431541Srgrimes while (cp < cplim) 4441541Srgrimes if (*cp2++ != *cp++) 4451541Srgrimes goto on1; 4461541Srgrimes *dupentry = 1; 4471541Srgrimes return t; 4481541Srgrimeson1: 4491541Srgrimes *dupentry = 0; 4501541Srgrimes cmp_res = (cp[-1] ^ cp2[-1]) & 0xff; 4511541Srgrimes for (b = (cp - v) << 3; cmp_res; b--) 4521541Srgrimes cmp_res >>= 1; 4531541Srgrimes } 4541541Srgrimes { 4551541Srgrimes register struct radix_node *p, *x = top; 4561541Srgrimes cp = v; 4571541Srgrimes do { 4581541Srgrimes p = x; 45959529Swollman if (cp[x->rn_offset] & x->rn_bmask) 46059529Swollman x = x->rn_right; 46159529Swollman else 46259529Swollman x = x->rn_left; 46359529Swollman } while (b > (unsigned) x->rn_bit); 46459529Swollman /* x->rn_bit < b && x->rn_bit >= 0 */ 4651541Srgrimes#ifdef RN_DEBUG 4661541Srgrimes if (rn_debug) 4678152Spst log(LOG_DEBUG, "rn_insert: Going In:\n"), traverse(p); 4681541Srgrimes#endif 46959529Swollman t = rn_newpair(v_arg, b, nodes); 47059529Swollman tt = t->rn_left; 47159529Swollman if ((cp[p->rn_offset] & p->rn_bmask) == 0) 47259529Swollman p->rn_left = t; 4731541Srgrimes else 47459529Swollman p->rn_right = t; 47559529Swollman x->rn_parent = t; 47659529Swollman t->rn_parent = p; /* frees x, p as temp vars below */ 47759529Swollman if ((cp[t->rn_offset] & t->rn_bmask) == 0) { 47859529Swollman t->rn_right = x; 4791541Srgrimes } else { 48059529Swollman t->rn_right = tt; 48159529Swollman t->rn_left = x; 4821541Srgrimes } 4831541Srgrimes#ifdef RN_DEBUG 4841541Srgrimes if (rn_debug) 4858152Spst log(LOG_DEBUG, "rn_insert: Coming Out:\n"), traverse(p); 4861541Srgrimes#endif 4871541Srgrimes } 4881541Srgrimes return (tt); 4891541Srgrimes} 4901541Srgrimes 4911541Srgrimesstruct radix_node * 4921541Srgrimesrn_addmask(n_arg, search, skip) 4931541Srgrimes int search, skip; 4941541Srgrimes void *n_arg; 4951541Srgrimes{ 4961541Srgrimes caddr_t netmask = (caddr_t)n_arg; 4971541Srgrimes register struct radix_node *x; 4981541Srgrimes register caddr_t cp, cplim; 4998152Spst register int b = 0, mlen, j; 5008152Spst int maskduplicated, m0, isnormal; 5018152Spst struct radix_node *saved_x; 5028152Spst static int last_zeroed = 0; 5031541Srgrimes 504128525Sluigi if ((mlen = LEN(netmask)) > max_keylen) 5058152Spst mlen = max_keylen; 5068152Spst if (skip == 0) 5078152Spst skip = 1; 5088152Spst if (mlen <= skip) 5098152Spst return (mask_rnhead->rnh_nodes); 5108152Spst if (skip > 1) 511128401Sluigi bcopy(rn_ones + 1, addmask_key + 1, skip - 1); 5128152Spst if ((m0 = mlen) > skip) 513128401Sluigi bcopy(netmask + skip, addmask_key + skip, mlen - skip); 5148152Spst /* 5158152Spst * Trim trailing zeroes. 5168152Spst */ 5178152Spst for (cp = addmask_key + mlen; (cp > addmask_key) && cp[-1] == 0;) 5188152Spst cp--; 5198152Spst mlen = cp - addmask_key; 5208152Spst if (mlen <= skip) { 5218152Spst if (m0 >= last_zeroed) 5228152Spst last_zeroed = mlen; 5238152Spst return (mask_rnhead->rnh_nodes); 5241541Srgrimes } 5258152Spst if (m0 < last_zeroed) 526128401Sluigi bzero(addmask_key + m0, last_zeroed - m0); 5278152Spst *addmask_key = last_zeroed = mlen; 5288152Spst x = rn_search(addmask_key, rn_masktop); 529128401Sluigi if (bcmp(addmask_key, x->rn_key, mlen) != 0) 5308152Spst x = 0; 5318152Spst if (x || search) 5328152Spst return (x); 533128433Sluigi R_Zalloc(x, struct radix_node *, max_keylen + 2 * sizeof (*x)); 5348152Spst if ((saved_x = x) == 0) 5351541Srgrimes return (0); 5368152Spst netmask = cp = (caddr_t)(x + 2); 537128401Sluigi bcopy(addmask_key, cp, mlen); 5388152Spst x = rn_insert(cp, mask_rnhead, &maskduplicated, x); 5398152Spst if (maskduplicated) { 5408152Spst log(LOG_ERR, "rn_addmask: mask impossibly already in tree"); 5418152Spst Free(saved_x); 5428152Spst return (x); 5438152Spst } 5441541Srgrimes /* 5458152Spst * Calculate index of mask, and check for normalcy. 546128433Sluigi * First find the first byte with a 0 bit, then if there are 547128433Sluigi * more bits left (remember we already trimmed the trailing 0's), 548128433Sluigi * the pattern must be one of those in normal_chars[], or we have 549128433Sluigi * a non-contiguous mask. 5501541Srgrimes */ 551128433Sluigi cplim = netmask + mlen; 552128433Sluigi isnormal = 1; 5538152Spst for (cp = netmask + skip; (cp < cplim) && *(u_char *)cp == 0xff;) 5548152Spst cp++; 5551541Srgrimes if (cp != cplim) { 556128433Sluigi static char normal_chars[] = { 557128433Sluigi 0, 0x80, 0xc0, 0xe0, 0xf0, 0xf8, 0xfc, 0xfe, 0xff}; 558128433Sluigi 5598876Srgrimes for (j = 0x80; (j & *cp) != 0; j >>= 1) 5608152Spst b++; 5618152Spst if (*cp != normal_chars[b] || cp != (cplim - 1)) 5628152Spst isnormal = 0; 5631541Srgrimes } 5648152Spst b += (cp - netmask) << 3; 56559529Swollman x->rn_bit = -1 - b; 5668152Spst if (isnormal) 5678152Spst x->rn_flags |= RNF_NORMAL; 5681541Srgrimes return (x); 5691541Srgrimes} 5701541Srgrimes 5718152Spststatic int /* XXX: arbitrary ordering for non-contiguous masks */ 5728152Spstrn_lexobetter(m_arg, n_arg) 5738152Spst void *m_arg, *n_arg; 5748152Spst{ 5758152Spst register u_char *mp = m_arg, *np = n_arg, *lim; 5768152Spst 577128525Sluigi if (LEN(mp) > LEN(np)) 5788152Spst return 1; /* not really, but need to check longer one first */ 579128525Sluigi if (LEN(mp) == LEN(np)) 580128525Sluigi for (lim = mp + LEN(mp); mp < lim;) 5818152Spst if (*mp++ > *np++) 5828152Spst return 1; 5838152Spst return 0; 5848152Spst} 5858152Spst 5868152Spststatic struct radix_mask * 5878152Spstrn_new_radix_mask(tt, next) 5888152Spst register struct radix_node *tt; 5898152Spst register struct radix_mask *next; 5908152Spst{ 5918152Spst register struct radix_mask *m; 5928152Spst 5938152Spst MKGet(m); 5948152Spst if (m == 0) { 5958152Spst log(LOG_ERR, "Mask for route not entered\n"); 5968152Spst return (0); 5978152Spst } 598128401Sluigi bzero(m, sizeof *m); 59959529Swollman m->rm_bit = tt->rn_bit; 6008152Spst m->rm_flags = tt->rn_flags; 6018152Spst if (tt->rn_flags & RNF_NORMAL) 6028152Spst m->rm_leaf = tt; 6038152Spst else 6048152Spst m->rm_mask = tt->rn_mask; 6058152Spst m->rm_mklist = next; 6068152Spst tt->rn_mklist = m; 6078152Spst return m; 6088152Spst} 6098152Spst 6101541Srgrimesstruct radix_node * 6111541Srgrimesrn_addroute(v_arg, n_arg, head, treenodes) 6121541Srgrimes void *v_arg, *n_arg; 6131541Srgrimes struct radix_node_head *head; 6141541Srgrimes struct radix_node treenodes[2]; 6151541Srgrimes{ 6161541Srgrimes caddr_t v = (caddr_t)v_arg, netmask = (caddr_t)n_arg; 6171549Srgrimes register struct radix_node *t, *x = 0, *tt; 6181541Srgrimes struct radix_node *saved_tt, *top = head->rnh_treetop; 6198152Spst short b = 0, b_leaf = 0; 6208152Spst int keyduplicated; 6218152Spst caddr_t mmask; 6221541Srgrimes struct radix_mask *m, **mp; 6231541Srgrimes 6241541Srgrimes /* 6251541Srgrimes * In dealing with non-contiguous masks, there may be 6261541Srgrimes * many different routes which have the same mask. 6271541Srgrimes * We will find it useful to have a unique pointer to 6281541Srgrimes * the mask to speed avoiding duplicate references at 6291541Srgrimes * nodes and possibly save time in calculating indices. 6301541Srgrimes */ 6311541Srgrimes if (netmask) { 63259529Swollman if ((x = rn_addmask(netmask, 0, top->rn_offset)) == 0) 6338152Spst return (0); 63459529Swollman b_leaf = x->rn_bit; 63559529Swollman b = -1 - x->rn_bit; 6361541Srgrimes netmask = x->rn_key; 6371541Srgrimes } 6381541Srgrimes /* 6391541Srgrimes * Deal with duplicated keys: attach node to previous instance 6401541Srgrimes */ 6411541Srgrimes saved_tt = tt = rn_insert(v, head, &keyduplicated, treenodes); 6421541Srgrimes if (keyduplicated) { 6438152Spst for (t = tt; tt; t = tt, tt = tt->rn_dupedkey) { 644178167Sqingli#ifdef RADIX_MPATH 645178167Sqingli /* permit multipath, if enabled for the family */ 646178167Sqingli if (rn_mpath_capable(head) && netmask == tt->rn_mask) { 647178167Sqingli /* 648178167Sqingli * go down to the end of multipaths, so that 649178167Sqingli * new entry goes into the end of rn_dupedkey 650178167Sqingli * chain. 651178167Sqingli */ 652178167Sqingli do { 653178167Sqingli t = tt; 654178167Sqingli tt = tt->rn_dupedkey; 655178167Sqingli } while (tt && t->rn_mask == tt->rn_mask); 656178167Sqingli break; 657178167Sqingli } 658178167Sqingli#endif 6591541Srgrimes if (tt->rn_mask == netmask) 6601541Srgrimes return (0); 6611541Srgrimes if (netmask == 0 || 6628152Spst (tt->rn_mask && 66359529Swollman ((b_leaf < tt->rn_bit) /* index(netmask) > node */ 66459529Swollman || rn_refines(netmask, tt->rn_mask) 66559529Swollman || rn_lexobetter(netmask, tt->rn_mask)))) 6661541Srgrimes break; 6678152Spst } 6681541Srgrimes /* 6691541Srgrimes * If the mask is not duplicated, we wouldn't 6701541Srgrimes * find it among possible duplicate key entries 6711541Srgrimes * anyway, so the above test doesn't hurt. 6721541Srgrimes * 6731541Srgrimes * We sort the masks for a duplicated key the same way as 6741541Srgrimes * in a masklist -- most specific to least specific. 6751541Srgrimes * This may require the unfortunate nuisance of relocating 6761541Srgrimes * the head of the list. 677108268Sru * 678108268Sru * We also reverse, or doubly link the list through the 679108268Sru * parent pointer. 6801541Srgrimes */ 6818152Spst if (tt == saved_tt) { 6821541Srgrimes struct radix_node *xx = x; 6831541Srgrimes /* link in at head of list */ 6841541Srgrimes (tt = treenodes)->rn_dupedkey = t; 6851541Srgrimes tt->rn_flags = t->rn_flags; 68659529Swollman tt->rn_parent = x = t->rn_parent; 68759529Swollman t->rn_parent = tt; /* parent */ 68859529Swollman if (x->rn_left == t) 68959529Swollman x->rn_left = tt; 69059529Swollman else 69159529Swollman x->rn_right = tt; 6921541Srgrimes saved_tt = tt; x = xx; 6931541Srgrimes } else { 6941541Srgrimes (tt = treenodes)->rn_dupedkey = t->rn_dupedkey; 6951541Srgrimes t->rn_dupedkey = tt; 69659529Swollman tt->rn_parent = t; /* parent */ 6978152Spst if (tt->rn_dupedkey) /* parent */ 69859529Swollman tt->rn_dupedkey->rn_parent = tt; /* parent */ 6991541Srgrimes } 7001541Srgrimes#ifdef RN_DEBUG 7011541Srgrimes t=tt+1; tt->rn_info = rn_nodenum++; t->rn_info = rn_nodenum++; 7021541Srgrimes tt->rn_twin = t; tt->rn_ybro = rn_clist; rn_clist = tt; 7031541Srgrimes#endif 7041541Srgrimes tt->rn_key = (caddr_t) v; 70559529Swollman tt->rn_bit = -1; 7068152Spst tt->rn_flags = RNF_ACTIVE; 7071541Srgrimes } 7081541Srgrimes /* 7091541Srgrimes * Put mask in tree. 7101541Srgrimes */ 7111541Srgrimes if (netmask) { 7121541Srgrimes tt->rn_mask = netmask; 71359529Swollman tt->rn_bit = x->rn_bit; 7148152Spst tt->rn_flags |= x->rn_flags & RNF_NORMAL; 7151541Srgrimes } 71659529Swollman t = saved_tt->rn_parent; 7178152Spst if (keyduplicated) 7188152Spst goto on2; 71959529Swollman b_leaf = -1 - t->rn_bit; 72059529Swollman if (t->rn_right == saved_tt) 72159529Swollman x = t->rn_left; 72259529Swollman else 72359529Swollman x = t->rn_right; 7241541Srgrimes /* Promote general routes from below */ 72559529Swollman if (x->rn_bit < 0) { 7268152Spst for (mp = &t->rn_mklist; x; x = x->rn_dupedkey) 72759529Swollman if (x->rn_mask && (x->rn_bit >= b_leaf) && x->rn_mklist == 0) { 7288152Spst *mp = m = rn_new_radix_mask(x, 0); 7298152Spst if (m) 7308152Spst mp = &m->rm_mklist; 7311541Srgrimes } 7321541Srgrimes } else if (x->rn_mklist) { 7331541Srgrimes /* 7341541Srgrimes * Skip over masks whose index is > that of new node 7351541Srgrimes */ 7368152Spst for (mp = &x->rn_mklist; (m = *mp); mp = &m->rm_mklist) 73759529Swollman if (m->rm_bit >= b_leaf) 7381541Srgrimes break; 7391541Srgrimes t->rn_mklist = m; *mp = 0; 7401541Srgrimes } 7418152Spston2: 7421541Srgrimes /* Add new route to highest possible ancestor's list */ 74359529Swollman if ((netmask == 0) || (b > t->rn_bit )) 7441541Srgrimes return tt; /* can't lift at all */ 74559529Swollman b_leaf = tt->rn_bit; 7461541Srgrimes do { 7471541Srgrimes x = t; 74859529Swollman t = t->rn_parent; 74959529Swollman } while (b <= t->rn_bit && x != top); 7501541Srgrimes /* 7511541Srgrimes * Search through routes associated with node to 7521541Srgrimes * insert new route according to index. 7538152Spst * Need same criteria as when sorting dupedkeys to avoid 7548152Spst * double loop on deletion. 7551541Srgrimes */ 7568152Spst for (mp = &x->rn_mklist; (m = *mp); mp = &m->rm_mklist) { 75759529Swollman if (m->rm_bit < b_leaf) 7581541Srgrimes continue; 75959529Swollman if (m->rm_bit > b_leaf) 7601541Srgrimes break; 7618152Spst if (m->rm_flags & RNF_NORMAL) { 7628152Spst mmask = m->rm_leaf->rn_mask; 7638152Spst if (tt->rn_flags & RNF_NORMAL) { 764204902Sqingli#if !defined(RADIX_MPATH) 76559529Swollman log(LOG_ERR, 76695023Ssuz "Non-unique normal route, mask not entered\n"); 767204902Sqingli#endif 7688152Spst return tt; 7698152Spst } 7708152Spst } else 7718152Spst mmask = m->rm_mask; 7728152Spst if (mmask == netmask) { 7731541Srgrimes m->rm_refs++; 7741541Srgrimes tt->rn_mklist = m; 7751541Srgrimes return tt; 7761541Srgrimes } 77759529Swollman if (rn_refines(netmask, mmask) 77859529Swollman || rn_lexobetter(netmask, mmask)) 7791541Srgrimes break; 7801541Srgrimes } 7818152Spst *mp = rn_new_radix_mask(tt, *mp); 7821541Srgrimes return tt; 7831541Srgrimes} 7841541Srgrimes 78531390Sbdestruct radix_node * 7861541Srgrimesrn_delete(v_arg, netmask_arg, head) 7871541Srgrimes void *v_arg, *netmask_arg; 7881541Srgrimes struct radix_node_head *head; 7891541Srgrimes{ 7901541Srgrimes register struct radix_node *t, *p, *x, *tt; 7911541Srgrimes struct radix_mask *m, *saved_m, **mp; 7921541Srgrimes struct radix_node *dupedkey, *saved_tt, *top; 7931541Srgrimes caddr_t v, netmask; 7941541Srgrimes int b, head_off, vlen; 7951541Srgrimes 7961541Srgrimes v = v_arg; 7971541Srgrimes netmask = netmask_arg; 7981541Srgrimes x = head->rnh_treetop; 7991541Srgrimes tt = rn_search(v, x); 80059529Swollman head_off = x->rn_offset; 801128525Sluigi vlen = LEN(v); 8021541Srgrimes saved_tt = tt; 8031541Srgrimes top = x; 8041541Srgrimes if (tt == 0 || 805128401Sluigi bcmp(v + head_off, tt->rn_key + head_off, vlen - head_off)) 8061541Srgrimes return (0); 8071541Srgrimes /* 8081541Srgrimes * Delete our route from mask lists. 8091541Srgrimes */ 8108152Spst if (netmask) { 8118152Spst if ((x = rn_addmask(netmask, 1, head_off)) == 0) 8128152Spst return (0); 8138152Spst netmask = x->rn_key; 8141541Srgrimes while (tt->rn_mask != netmask) 8151541Srgrimes if ((tt = tt->rn_dupedkey) == 0) 8161541Srgrimes return (0); 8171541Srgrimes } 8181541Srgrimes if (tt->rn_mask == 0 || (saved_m = m = tt->rn_mklist) == 0) 8191541Srgrimes goto on1; 8208152Spst if (tt->rn_flags & RNF_NORMAL) { 8218152Spst if (m->rm_leaf != tt || m->rm_refs > 0) { 8228152Spst log(LOG_ERR, "rn_delete: inconsistent annotation\n"); 8238152Spst return 0; /* dangling ref could cause disaster */ 8248152Spst } 8258876Srgrimes } else { 8268152Spst if (m->rm_mask != tt->rn_mask) { 8278152Spst log(LOG_ERR, "rn_delete: inconsistent annotation\n"); 8288152Spst goto on1; 8298152Spst } 8308152Spst if (--m->rm_refs >= 0) 8318152Spst goto on1; 8321541Srgrimes } 83359529Swollman b = -1 - tt->rn_bit; 83459529Swollman t = saved_tt->rn_parent; 83559529Swollman if (b > t->rn_bit) 8361541Srgrimes goto on1; /* Wasn't lifted at all */ 8371541Srgrimes do { 8381541Srgrimes x = t; 83959529Swollman t = t->rn_parent; 84059529Swollman } while (b <= t->rn_bit && x != top); 8418152Spst for (mp = &x->rn_mklist; (m = *mp); mp = &m->rm_mklist) 8421541Srgrimes if (m == saved_m) { 8431541Srgrimes *mp = m->rm_mklist; 8441541Srgrimes MKFree(m); 8451541Srgrimes break; 8461541Srgrimes } 8478152Spst if (m == 0) { 8488152Spst log(LOG_ERR, "rn_delete: couldn't find our annotation\n"); 8498152Spst if (tt->rn_flags & RNF_NORMAL) 8508152Spst return (0); /* Dangling ref to us */ 8518152Spst } 8521541Srgrimeson1: 8531541Srgrimes /* 8541541Srgrimes * Eliminate us from tree 8551541Srgrimes */ 8561541Srgrimes if (tt->rn_flags & RNF_ROOT) 8571541Srgrimes return (0); 8581541Srgrimes#ifdef RN_DEBUG 8591541Srgrimes /* Get us out of the creation list */ 8601541Srgrimes for (t = rn_clist; t && t->rn_ybro != tt; t = t->rn_ybro) {} 8611541Srgrimes if (t) t->rn_ybro = tt->rn_ybro; 8621541Srgrimes#endif 86359529Swollman t = tt->rn_parent; 8648152Spst dupedkey = saved_tt->rn_dupedkey; 8651541Srgrimes if (dupedkey) { 8668152Spst /* 867108268Sru * Here, tt is the deletion target and 868108268Sru * saved_tt is the head of the dupekey chain. 8698152Spst */ 8701541Srgrimes if (tt == saved_tt) { 8718152Spst /* remove from head of chain */ 87259529Swollman x = dupedkey; x->rn_parent = t; 87359529Swollman if (t->rn_left == tt) 87459529Swollman t->rn_left = x; 87559529Swollman else 87659529Swollman t->rn_right = x; 8771541Srgrimes } else { 8788152Spst /* find node in front of tt on the chain */ 8791541Srgrimes for (x = p = saved_tt; p && p->rn_dupedkey != tt;) 8801541Srgrimes p = p->rn_dupedkey; 8818152Spst if (p) { 8828152Spst p->rn_dupedkey = tt->rn_dupedkey; 88359529Swollman if (tt->rn_dupedkey) /* parent */ 88459529Swollman tt->rn_dupedkey->rn_parent = p; 88559529Swollman /* parent */ 8868152Spst } else log(LOG_ERR, "rn_delete: couldn't find us\n"); 8871541Srgrimes } 8881541Srgrimes t = tt + 1; 8891541Srgrimes if (t->rn_flags & RNF_ACTIVE) { 8901541Srgrimes#ifndef RN_DEBUG 89159529Swollman *++x = *t; 89259529Swollman p = t->rn_parent; 8931541Srgrimes#else 89459529Swollman b = t->rn_info; 89559529Swollman *++x = *t; 89659529Swollman t->rn_info = b; 89759529Swollman p = t->rn_parent; 8981541Srgrimes#endif 89959529Swollman if (p->rn_left == t) 90059529Swollman p->rn_left = x; 90159529Swollman else 90259529Swollman p->rn_right = x; 90359529Swollman x->rn_left->rn_parent = x; 90459529Swollman x->rn_right->rn_parent = x; 9051541Srgrimes } 9061541Srgrimes goto out; 9071541Srgrimes } 90859529Swollman if (t->rn_left == tt) 90959529Swollman x = t->rn_right; 91059529Swollman else 91159529Swollman x = t->rn_left; 91259529Swollman p = t->rn_parent; 91359529Swollman if (p->rn_right == t) 91459529Swollman p->rn_right = x; 91559529Swollman else 91659529Swollman p->rn_left = x; 91759529Swollman x->rn_parent = p; 9181541Srgrimes /* 9191541Srgrimes * Demote routes attached to us. 9201541Srgrimes */ 9211541Srgrimes if (t->rn_mklist) { 92259529Swollman if (x->rn_bit >= 0) { 9238152Spst for (mp = &x->rn_mklist; (m = *mp);) 9241541Srgrimes mp = &m->rm_mklist; 9251541Srgrimes *mp = t->rn_mklist; 9261541Srgrimes } else { 9278152Spst /* If there are any key,mask pairs in a sibling 9288152Spst duped-key chain, some subset will appear sorted 9298152Spst in the same order attached to our mklist */ 9308152Spst for (m = t->rn_mklist; m && x; x = x->rn_dupedkey) 9318152Spst if (m == x->rn_mklist) { 9328152Spst struct radix_mask *mm = m->rm_mklist; 9331541Srgrimes x->rn_mklist = 0; 9348152Spst if (--(m->rm_refs) < 0) 9358152Spst MKFree(m); 9368152Spst m = mm; 9378152Spst } 9388152Spst if (m) 93937560Sbde log(LOG_ERR, 94037560Sbde "rn_delete: Orphaned Mask %p at %p\n", 941204582Sluigi m, x); 9421541Srgrimes } 9431541Srgrimes } 9441541Srgrimes /* 9451541Srgrimes * We may be holding an active internal node in the tree. 9461541Srgrimes */ 9471541Srgrimes x = tt + 1; 9481541Srgrimes if (t != x) { 9491541Srgrimes#ifndef RN_DEBUG 9501541Srgrimes *t = *x; 9511541Srgrimes#else 95259529Swollman b = t->rn_info; 95359529Swollman *t = *x; 95459529Swollman t->rn_info = b; 9551541Srgrimes#endif 95659529Swollman t->rn_left->rn_parent = t; 95759529Swollman t->rn_right->rn_parent = t; 95859529Swollman p = x->rn_parent; 95959529Swollman if (p->rn_left == x) 96059529Swollman p->rn_left = t; 96159529Swollman else 96259529Swollman p->rn_right = t; 9631541Srgrimes } 9641541Srgrimesout: 9651541Srgrimes tt->rn_flags &= ~RNF_ACTIVE; 9661541Srgrimes tt[1].rn_flags &= ~RNF_ACTIVE; 9671541Srgrimes return (tt); 9681541Srgrimes} 9691541Srgrimes 9707197Swollman/* 9717197Swollman * This is the same as rn_walktree() except for the parameters and the 9727197Swollman * exit. 9737197Swollman */ 97412820Sphkstatic int 9757197Swollmanrn_walktree_from(h, a, m, f, w) 9767197Swollman struct radix_node_head *h; 9777197Swollman void *a, *m; 97812579Sbde walktree_f_t *f; 9797197Swollman void *w; 9807197Swollman{ 9817197Swollman int error; 9827197Swollman struct radix_node *base, *next; 9837197Swollman u_char *xa = (u_char *)a; 9847197Swollman u_char *xm = (u_char *)m; 9857197Swollman register struct radix_node *rn, *last = 0 /* shut up gcc */; 9867197Swollman int stopping = 0; 9877197Swollman int lastb; 9887197Swollman 9897197Swollman /* 990128525Sluigi * rn_search_m is sort-of-open-coded here. We cannot use the 991128525Sluigi * function because we need to keep track of the last node seen. 9927197Swollman */ 9937279Swollman /* printf("about to search\n"); */ 99459529Swollman for (rn = h->rnh_treetop; rn->rn_bit >= 0; ) { 9957197Swollman last = rn; 99659529Swollman /* printf("rn_bit %d, rn_bmask %x, xm[rn_offset] %x\n", 99759529Swollman rn->rn_bit, rn->rn_bmask, xm[rn->rn_offset]); */ 99859529Swollman if (!(rn->rn_bmask & xm[rn->rn_offset])) { 9997197Swollman break; 10007279Swollman } 100159529Swollman if (rn->rn_bmask & xa[rn->rn_offset]) { 100259529Swollman rn = rn->rn_right; 10037197Swollman } else { 100459529Swollman rn = rn->rn_left; 10057197Swollman } 10067197Swollman } 10077279Swollman /* printf("done searching\n"); */ 10087197Swollman 10097197Swollman /* 10107197Swollman * Two cases: either we stepped off the end of our mask, 10117197Swollman * in which case last == rn, or we reached a leaf, in which 10127197Swollman * case we want to start from the last node we looked at. 10137197Swollman * Either way, last is the node we want to start from. 10147197Swollman */ 10157197Swollman rn = last; 101659529Swollman lastb = rn->rn_bit; 10177197Swollman 10187279Swollman /* printf("rn %p, lastb %d\n", rn, lastb);*/ 10197279Swollman 10207197Swollman /* 10217197Swollman * This gets complicated because we may delete the node 10227197Swollman * while applying the function f to it, so we need to calculate 10237197Swollman * the successor node in advance. 10247197Swollman */ 102559529Swollman while (rn->rn_bit >= 0) 102659529Swollman rn = rn->rn_left; 10277197Swollman 10287197Swollman while (!stopping) { 102959529Swollman /* printf("node %p (%d)\n", rn, rn->rn_bit); */ 10307197Swollman base = rn; 10317197Swollman /* If at right child go back up, otherwise, go right */ 103259529Swollman while (rn->rn_parent->rn_right == rn 103359529Swollman && !(rn->rn_flags & RNF_ROOT)) { 103459529Swollman rn = rn->rn_parent; 10357197Swollman 10368876Srgrimes /* if went up beyond last, stop */ 1037155442Sqingli if (rn->rn_bit <= lastb) { 10387197Swollman stopping = 1; 10397279Swollman /* printf("up too far\n"); */ 1040128525Sluigi /* 1041128525Sluigi * XXX we should jump to the 'Process leaves' 1042128525Sluigi * part, because the values of 'rn' and 'next' 1043128525Sluigi * we compute will not be used. Not a big deal 1044128525Sluigi * because this loop will terminate, but it is 1045128525Sluigi * inefficient and hard to understand! 1046128525Sluigi */ 10477197Swollman } 10487197Swollman } 1049155442Sqingli 1050155442Sqingli /* 1051155442Sqingli * At the top of the tree, no need to traverse the right 1052155442Sqingli * half, prevent the traversal of the entire tree in the 1053155442Sqingli * case of default route. 1054155442Sqingli */ 1055155442Sqingli if (rn->rn_parent->rn_flags & RNF_ROOT) 1056155442Sqingli stopping = 1; 10577197Swollman 10587197Swollman /* Find the next *leaf* since next node might vanish, too */ 105959529Swollman for (rn = rn->rn_parent->rn_right; rn->rn_bit >= 0;) 106059529Swollman rn = rn->rn_left; 10617197Swollman next = rn; 10627197Swollman /* Process leaves */ 10637197Swollman while ((rn = base) != 0) { 10647197Swollman base = rn->rn_dupedkey; 10657279Swollman /* printf("leaf %p\n", rn); */ 10668876Srgrimes if (!(rn->rn_flags & RNF_ROOT) 10677197Swollman && (error = (*f)(rn, w))) 10687197Swollman return (error); 10697197Swollman } 10707197Swollman rn = next; 10717279Swollman 10727279Swollman if (rn->rn_flags & RNF_ROOT) { 10737279Swollman /* printf("root, stopping"); */ 10747279Swollman stopping = 1; 10757279Swollman } 10767279Swollman 10777197Swollman } 10787197Swollman return 0; 10797197Swollman} 10807197Swollman 108112820Sphkstatic int 10821541Srgrimesrn_walktree(h, f, w) 10831541Srgrimes struct radix_node_head *h; 108412579Sbde walktree_f_t *f; 10851541Srgrimes void *w; 10861541Srgrimes{ 10871541Srgrimes int error; 10881541Srgrimes struct radix_node *base, *next; 10891541Srgrimes register struct radix_node *rn = h->rnh_treetop; 10901541Srgrimes /* 10911541Srgrimes * This gets complicated because we may delete the node 10921541Srgrimes * while applying the function f to it, so we need to calculate 10931541Srgrimes * the successor node in advance. 10941541Srgrimes */ 1095186166Skmacy 10961541Srgrimes /* First time through node, go left */ 109759529Swollman while (rn->rn_bit >= 0) 109859529Swollman rn = rn->rn_left; 10991541Srgrimes for (;;) { 11001541Srgrimes base = rn; 11011541Srgrimes /* If at right child go back up, otherwise, go right */ 110259529Swollman while (rn->rn_parent->rn_right == rn 110359529Swollman && (rn->rn_flags & RNF_ROOT) == 0) 110459529Swollman rn = rn->rn_parent; 11051541Srgrimes /* Find the next *leaf* since next node might vanish, too */ 110659529Swollman for (rn = rn->rn_parent->rn_right; rn->rn_bit >= 0;) 110759529Swollman rn = rn->rn_left; 11081541Srgrimes next = rn; 11091541Srgrimes /* Process leaves */ 11108152Spst while ((rn = base)) { 11111541Srgrimes base = rn->rn_dupedkey; 111259529Swollman if (!(rn->rn_flags & RNF_ROOT) 111359529Swollman && (error = (*f)(rn, w))) 11141541Srgrimes return (error); 11151541Srgrimes } 11161541Srgrimes rn = next; 11171541Srgrimes if (rn->rn_flags & RNF_ROOT) 11181541Srgrimes return (0); 11191541Srgrimes } 11201541Srgrimes /* NOTREACHED */ 11211541Srgrimes} 11221541Srgrimes 1123128525Sluigi/* 1124128525Sluigi * Allocate and initialize an empty tree. This has 3 nodes, which are 1125128525Sluigi * part of the radix_node_head (in the order <left,root,right>) and are 1126128525Sluigi * marked RNF_ROOT so they cannot be freed. 1127128525Sluigi * The leaves have all-zero and all-one keys, with significant 1128128525Sluigi * bits starting at 'off'. 1129128525Sluigi * Return 1 on success, 0 on error. 1130128525Sluigi */ 11311541Srgrimesint 11321541Srgrimesrn_inithead(head, off) 11331541Srgrimes void **head; 11341541Srgrimes int off; 11351541Srgrimes{ 11361541Srgrimes register struct radix_node_head *rnh; 11371541Srgrimes register struct radix_node *t, *tt, *ttt; 11381541Srgrimes if (*head) 11391541Srgrimes return (1); 1140128433Sluigi R_Zalloc(rnh, struct radix_node_head *, sizeof (*rnh)); 11411541Srgrimes if (rnh == 0) 11421541Srgrimes return (0); 1143110527Shsu#ifdef _KERNEL 1144108250Shsu RADIX_NODE_HEAD_LOCK_INIT(rnh); 1145110527Shsu#endif 11461541Srgrimes *head = rnh; 11471541Srgrimes t = rn_newpair(rn_zeros, off, rnh->rnh_nodes); 11481541Srgrimes ttt = rnh->rnh_nodes + 2; 114959529Swollman t->rn_right = ttt; 115059529Swollman t->rn_parent = t; 1151128525Sluigi tt = t->rn_left; /* ... which in turn is rnh->rnh_nodes */ 11521541Srgrimes tt->rn_flags = t->rn_flags = RNF_ROOT | RNF_ACTIVE; 115359529Swollman tt->rn_bit = -1 - off; 11541541Srgrimes *ttt = *tt; 11551541Srgrimes ttt->rn_key = rn_ones; 11561541Srgrimes rnh->rnh_addaddr = rn_addroute; 11571541Srgrimes rnh->rnh_deladdr = rn_delete; 11581541Srgrimes rnh->rnh_matchaddr = rn_match; 11598152Spst rnh->rnh_lookup = rn_lookup; 11601541Srgrimes rnh->rnh_walktree = rn_walktree; 11617197Swollman rnh->rnh_walktree_from = rn_walktree_from; 11621541Srgrimes rnh->rnh_treetop = t; 11631541Srgrimes return (1); 11641541Srgrimes} 11651541Srgrimes 1166204808Sbzint 1167204808Sbzrn_detachhead(void **head) 1168204808Sbz{ 1169204808Sbz struct radix_node_head *rnh; 1170204808Sbz 1171204808Sbz KASSERT((head != NULL && *head != NULL), 1172204808Sbz ("%s: head already freed", __func__)); 1173204808Sbz rnh = *head; 1174204808Sbz 1175204808Sbz /* Free <left,root,right> nodes. */ 1176204808Sbz Free(rnh); 1177204808Sbz 1178204808Sbz *head = NULL; 1179204808Sbz return (1); 1180204808Sbz} 1181204808Sbz 11821541Srgrimesvoid 1183200537Sluigirn_init(int maxk) 11841541Srgrimes{ 11851541Srgrimes char *cp, *cplim; 11861541Srgrimes 1187200537Sluigi max_keylen = maxk; 11881541Srgrimes if (max_keylen == 0) { 11898152Spst log(LOG_ERR, 11908152Spst "rn_init: radix functions require max_keylen be set\n"); 11911541Srgrimes return; 11921541Srgrimes } 11931541Srgrimes R_Malloc(rn_zeros, char *, 3 * max_keylen); 11941541Srgrimes if (rn_zeros == NULL) 11951541Srgrimes panic("rn_init"); 1196128401Sluigi bzero(rn_zeros, 3 * max_keylen); 11971541Srgrimes rn_ones = cp = rn_zeros + max_keylen; 11988152Spst addmask_key = cplim = rn_ones + max_keylen; 11991541Srgrimes while (cp < cplim) 12001541Srgrimes *cp++ = -1; 1201120359Speter if (rn_inithead((void **)(void *)&mask_rnhead, 0) == 0) 12021541Srgrimes panic("rn_init 2"); 12031541Srgrimes} 1204