radix.c revision 200439
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 200439 2009-12-12 15:49:28Z 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> 431541Srgrimes#include <sys/domain.h> 448152Spst#include <sys/syslog.h> 458152Spst#include <net/radix.h> 46178167Sqingli#include "opt_mpath.h" 47178167Sqingli#ifdef RADIX_MPATH 48178167Sqingli#include <net/radix_mpath.h> 49178167Sqingli#endif 50200439Sluigi#else /* !_KERNEL */ 51200439Sluigi#include <stdio.h> 52200439Sluigi#include <strings.h> 53200439Sluigi#include <stdlib.h> 54200439Sluigi#define log(x, arg...) fprintf(stderr, ## arg) 55200439Sluigi#define panic(x) fprintf(stderr, "PANIC: %s", x), exit(1) 56200439Sluigi#define min(a, b) ((a) < (b) ? (a) : (b) ) 57200439Sluigi#include <net/radix.h> 58200439Sluigi#endif /* !_KERNEL */ 59178167Sqingli 6093084Sbdestatic int rn_walktree_from(struct radix_node_head *h, void *a, void *m, 6193084Sbde walktree_f_t *f, void *w); 6292725Salfredstatic int rn_walktree(struct radix_node_head *, walktree_f_t *, void *); 6312820Sphkstatic struct radix_node 6492725Salfred *rn_insert(void *, struct radix_node_head *, int *, 6593084Sbde struct radix_node [2]), 6692725Salfred *rn_newpair(void *, int, struct radix_node[2]), 6792725Salfred *rn_search(void *, struct radix_node *), 6892725Salfred *rn_search_m(void *, struct radix_node *, void *); 6912579Sbde 7012820Sphkstatic int max_keylen; 7112820Sphkstatic struct radix_mask *rn_mkfreelist; 7212820Sphkstatic struct radix_node_head *mask_rnhead; 73128433Sluigi/* 74128433Sluigi * Work area -- the following point to 3 buffers of size max_keylen, 75128433Sluigi * allocated in this order in a block of memory malloc'ed by rn_init. 76200354Sluigi * rn_zeros, rn_ones are set in rn_init and used in readonly afterwards. 77200354Sluigi * addmask_key is used in rn_addmask in rw mode and not thread-safe. 78128433Sluigi */ 79128433Sluigistatic char *rn_zeros, *rn_ones, *addmask_key; 801541Srgrimes 81128401Sluigi#define MKGet(m) { \ 82128401Sluigi if (rn_mkfreelist) { \ 83128401Sluigi m = rn_mkfreelist; \ 84128401Sluigi rn_mkfreelist = (m)->rm_mklist; \ 85128401Sluigi } else \ 86128401Sluigi R_Malloc(m, struct radix_mask *, sizeof (struct radix_mask)); } 87128401Sluigi 88128401Sluigi#define MKFree(m) { (m)->rm_mklist = rn_mkfreelist; rn_mkfreelist = (m);} 89128401Sluigi 901541Srgrimes#define rn_masktop (mask_rnhead->rnh_treetop) 9112579Sbde 9292725Salfredstatic int rn_lexobetter(void *m_arg, void *n_arg); 9312579Sbdestatic struct radix_mask * 9492725Salfred rn_new_radix_mask(struct radix_node *tt, 9593084Sbde struct radix_mask *next); 96108273Srustatic int rn_satisfies_leaf(char *trial, struct radix_node *leaf, 9793084Sbde int skip); 9812579Sbde 991541Srgrimes/* 1001541Srgrimes * The data structure for the keys is a radix tree with one way 10159529Swollman * branching removed. The index rn_bit at an internal node n represents a bit 1021541Srgrimes * position to be tested. The tree is arranged so that all descendants 10359529Swollman * of a node n have keys whose bits all agree up to position rn_bit - 1. 10459529Swollman * (We say the index of n is rn_bit.) 1051541Srgrimes * 10659529Swollman * There is at least one descendant which has a one bit at position rn_bit, 1071541Srgrimes * and at least one with a zero there. 1081541Srgrimes * 1091541Srgrimes * A route is determined by a pair of key and mask. We require that the 1101541Srgrimes * bit-wise logical and of the key and mask to be the key. 1111541Srgrimes * We define the index of a route to associated with the mask to be 1121541Srgrimes * the first bit number in the mask where 0 occurs (with bit number 0 1131541Srgrimes * representing the highest order bit). 1148876Srgrimes * 1151541Srgrimes * We say a mask is normal if every bit is 0, past the index of the mask. 11659529Swollman * If a node n has a descendant (k, m) with index(m) == index(n) == rn_bit, 1171541Srgrimes * and m is a normal mask, then the route applies to every descendant of n. 11859529Swollman * If the index(m) < rn_bit, this implies the trailing last few bits of k 1191541Srgrimes * before bit b are all 0, (and hence consequently true of every descendant 1201541Srgrimes * of n), so the route applies to all descendants of the node as well. 1218876Srgrimes * 1228152Spst * Similar logic shows that a non-normal mask m such that 1231541Srgrimes * index(m) <= index(n) could potentially apply to many children of n. 1241541Srgrimes * Thus, for each non-host route, we attach its mask to a list at an internal 1258876Srgrimes * node as high in the tree as we can go. 1268152Spst * 1278152Spst * The present version of the code makes use of normal routes in short- 1288152Spst * circuiting an explict mask and compare operation when testing whether 1298152Spst * a key satisfies a normal route, and also in remembering the unique leaf 1308152Spst * that governs a subtree. 1311541Srgrimes */ 1321541Srgrimes 133128525Sluigi/* 134128525Sluigi * Most of the functions in this code assume that the key/mask arguments 135128525Sluigi * are sockaddr-like structures, where the first byte is an u_char 136128525Sluigi * indicating the size of the entire structure. 137128525Sluigi * 138128525Sluigi * To make the assumption more explicit, we use the LEN() macro to access 139128525Sluigi * this field. It is safe to pass an expression with side effects 140128525Sluigi * to LEN() as the argument is evaluated only once. 141200354Sluigi * We cast the result to int as this is the dominant usage. 142128525Sluigi */ 143200354Sluigi#define LEN(x) ( (int) (*(const u_char *)(x)) ) 144128525Sluigi 145128525Sluigi/* 146128525Sluigi * XXX THIS NEEDS TO BE FIXED 147128525Sluigi * In the code, pointers to keys and masks are passed as either 148128525Sluigi * 'void *' (because callers use to pass pointers of various kinds), or 149128525Sluigi * 'caddr_t' (which is fine for pointer arithmetics, but not very 150128525Sluigi * clean when you dereference it to access data). Furthermore, caddr_t 151128525Sluigi * is really 'char *', while the natural type to operate on keys and 152128525Sluigi * masks would be 'u_char'. This mismatch require a lot of casts and 153128525Sluigi * intermediate variables to adapt types that clutter the code. 154128525Sluigi */ 155128525Sluigi 156128525Sluigi/* 157128525Sluigi * Search a node in the tree matching the key. 158128525Sluigi */ 15912820Sphkstatic struct radix_node * 1601541Srgrimesrn_search(v_arg, head) 1611541Srgrimes void *v_arg; 1621541Srgrimes struct radix_node *head; 1631541Srgrimes{ 1641541Srgrimes register struct radix_node *x; 1651541Srgrimes register caddr_t v; 1661541Srgrimes 16759529Swollman for (x = head, v = v_arg; x->rn_bit >= 0;) { 16859529Swollman if (x->rn_bmask & v[x->rn_offset]) 16959529Swollman x = x->rn_right; 1701541Srgrimes else 17159529Swollman x = x->rn_left; 1721541Srgrimes } 1731541Srgrimes return (x); 17431390Sbde} 1751541Srgrimes 176128525Sluigi/* 177128525Sluigi * Same as above, but with an additional mask. 178128525Sluigi * XXX note this function is used only once. 179128525Sluigi */ 18012820Sphkstatic struct radix_node * 1811541Srgrimesrn_search_m(v_arg, head, m_arg) 1821541Srgrimes struct radix_node *head; 1831541Srgrimes void *v_arg, *m_arg; 1841541Srgrimes{ 1851541Srgrimes register struct radix_node *x; 1861541Srgrimes register caddr_t v = v_arg, m = m_arg; 1871541Srgrimes 18859529Swollman for (x = head; x->rn_bit >= 0;) { 18959529Swollman if ((x->rn_bmask & m[x->rn_offset]) && 19059529Swollman (x->rn_bmask & v[x->rn_offset])) 19159529Swollman x = x->rn_right; 1921541Srgrimes else 19359529Swollman x = x->rn_left; 1941541Srgrimes } 1951541Srgrimes return x; 19631390Sbde} 1971541Srgrimes 1981541Srgrimesint 1991541Srgrimesrn_refines(m_arg, n_arg) 2001541Srgrimes void *m_arg, *n_arg; 2011541Srgrimes{ 2021541Srgrimes register caddr_t m = m_arg, n = n_arg; 203128525Sluigi register caddr_t lim, lim2 = lim = n + LEN(n); 204200354Sluigi int longer = LEN(n++) - LEN(m++); 2051541Srgrimes int masks_are_equal = 1; 2061541Srgrimes 2071541Srgrimes if (longer > 0) 2081541Srgrimes lim -= longer; 2091541Srgrimes while (n < lim) { 2101541Srgrimes if (*n & ~(*m)) 2111541Srgrimes return 0; 2121541Srgrimes if (*n++ != *m++) 2131541Srgrimes masks_are_equal = 0; 2141541Srgrimes } 2151541Srgrimes while (n < lim2) 2161541Srgrimes if (*n++) 2171541Srgrimes return 0; 2181541Srgrimes if (masks_are_equal && (longer < 0)) 2191541Srgrimes for (lim2 = m - longer; m < lim2; ) 2201541Srgrimes if (*m++) 2211541Srgrimes return 1; 2221541Srgrimes return (!masks_are_equal); 2231541Srgrimes} 2241541Srgrimes 2258152Spststruct radix_node * 2268152Spstrn_lookup(v_arg, m_arg, head) 2278152Spst void *v_arg, *m_arg; 2288152Spst struct radix_node_head *head; 2298152Spst{ 2308152Spst register struct radix_node *x; 2318152Spst caddr_t netmask = 0; 2321541Srgrimes 2338152Spst if (m_arg) { 23459529Swollman x = rn_addmask(m_arg, 1, head->rnh_treetop->rn_offset); 23559529Swollman if (x == 0) 2368152Spst return (0); 2378152Spst netmask = x->rn_key; 2388152Spst } 2398152Spst x = rn_match(v_arg, head); 2408152Spst if (x && netmask) { 2418152Spst while (x && x->rn_mask != netmask) 2428152Spst x = x->rn_dupedkey; 2438152Spst } 2448152Spst return x; 2458152Spst} 2468152Spst 2478152Spststatic int 248108273Srurn_satisfies_leaf(trial, leaf, skip) 2498152Spst char *trial; 2508152Spst register struct radix_node *leaf; 2518152Spst int skip; 2528152Spst{ 2538152Spst register char *cp = trial, *cp2 = leaf->rn_key, *cp3 = leaf->rn_mask; 2548152Spst char *cplim; 255128525Sluigi int length = min(LEN(cp), LEN(cp2)); 2568152Spst 257200354Sluigi if (cp3 == NULL) 2588152Spst cp3 = rn_ones; 2598152Spst else 260200354Sluigi length = min(length, LEN(cp3)); 2618152Spst cplim = cp + length; cp3 += skip; cp2 += skip; 2628152Spst for (cp += skip; cp < cplim; cp++, cp2++, cp3++) 2638152Spst if ((*cp ^ *cp2) & *cp3) 2648152Spst return 0; 2658152Spst return 1; 2668152Spst} 2678152Spst 2681541Srgrimesstruct radix_node * 2691541Srgrimesrn_match(v_arg, head) 2701541Srgrimes void *v_arg; 2711541Srgrimes struct radix_node_head *head; 2721541Srgrimes{ 2731541Srgrimes caddr_t v = v_arg; 2741541Srgrimes register struct radix_node *t = head->rnh_treetop, *x; 2758152Spst register caddr_t cp = v, cp2; 2768152Spst caddr_t cplim; 2771541Srgrimes struct radix_node *saved_t, *top = t; 278128525Sluigi int off = t->rn_offset, vlen = LEN(cp), matched_off; 27959529Swollman register int test, b, rn_bit; 2801541Srgrimes 2811541Srgrimes /* 2821541Srgrimes * Open code rn_search(v, top) to avoid overhead of extra 2831541Srgrimes * subroutine call. 2841541Srgrimes */ 28559529Swollman for (; t->rn_bit >= 0; ) { 28659529Swollman if (t->rn_bmask & cp[t->rn_offset]) 28759529Swollman t = t->rn_right; 2881541Srgrimes else 28959529Swollman t = t->rn_left; 2901541Srgrimes } 2911541Srgrimes /* 2921541Srgrimes * See if we match exactly as a host destination 2938152Spst * or at least learn how many bits match, for normal mask finesse. 2948152Spst * 2958152Spst * It doesn't hurt us to limit how many bytes to check 2968152Spst * to the length of the mask, since if it matches we had a genuine 2978152Spst * match and the leaf we have is the most specific one anyway; 2988152Spst * if it didn't match with a shorter length it would fail 2998152Spst * with a long one. This wins big for class B&C netmasks which 3008152Spst * are probably the most common case... 3011541Srgrimes */ 3028152Spst if (t->rn_mask) 3038152Spst vlen = *(u_char *)t->rn_mask; 3041541Srgrimes cp += off; cp2 = t->rn_key + off; cplim = v + vlen; 3051541Srgrimes for (; cp < cplim; cp++, cp2++) 3061541Srgrimes if (*cp != *cp2) 3071541Srgrimes goto on1; 3081541Srgrimes /* 3091541Srgrimes * This extra grot is in case we are explicitly asked 3101541Srgrimes * to look up the default. Ugh! 31148215Spb * 31248215Spb * Never return the root node itself, it seems to cause a 31348215Spb * lot of confusion. 3141541Srgrimes */ 31548215Spb if (t->rn_flags & RNF_ROOT) 3161541Srgrimes t = t->rn_dupedkey; 3171541Srgrimes return t; 3181541Srgrimeson1: 3198152Spst test = (*cp ^ *cp2) & 0xff; /* find first bit that differs */ 3208152Spst for (b = 7; (test >>= 1) > 0;) 3218152Spst b--; 3221541Srgrimes matched_off = cp - v; 3238152Spst b += matched_off << 3; 32459529Swollman rn_bit = -1 - b; 3258152Spst /* 3268152Spst * If there is a host route in a duped-key chain, it will be first. 3278152Spst */ 3288152Spst if ((saved_t = t)->rn_mask == 0) 3298152Spst t = t->rn_dupedkey; 3308152Spst for (; t; t = t->rn_dupedkey) 3311541Srgrimes /* 3328152Spst * Even if we don't match exactly as a host, 3331541Srgrimes * we may match if the leaf we wound up at is 3341541Srgrimes * a route to a net. 3351541Srgrimes */ 3368152Spst if (t->rn_flags & RNF_NORMAL) { 33759529Swollman if (rn_bit <= t->rn_bit) 3388152Spst return t; 339108273Sru } else if (rn_satisfies_leaf(v, t, matched_off)) 3408152Spst return t; 3411541Srgrimes t = saved_t; 3421541Srgrimes /* start searching up the tree */ 3431541Srgrimes do { 3441541Srgrimes register struct radix_mask *m; 34559529Swollman t = t->rn_parent; 3463443Sphk m = t->rn_mklist; 34759529Swollman /* 34859529Swollman * If non-contiguous masks ever become important 34959529Swollman * we can restore the masking and open coding of 35059529Swollman * the search and satisfaction test and put the 35159529Swollman * calculation of "off" back before the "do". 35259529Swollman */ 35359529Swollman while (m) { 35459529Swollman if (m->rm_flags & RNF_NORMAL) { 35559529Swollman if (rn_bit <= m->rm_bit) 35659529Swollman return (m->rm_leaf); 35759529Swollman } else { 35859529Swollman off = min(t->rn_offset, matched_off); 35959529Swollman x = rn_search_m(v, t, m->rm_mask); 36059529Swollman while (x && x->rn_mask != m->rm_mask) 36159529Swollman x = x->rn_dupedkey; 362108273Sru if (x && rn_satisfies_leaf(v, x, off)) 36359529Swollman return x; 36459529Swollman } 36559529Swollman m = m->rm_mklist; 3661541Srgrimes } 3671541Srgrimes } while (t != top); 3681541Srgrimes return 0; 36931390Sbde} 3708876Srgrimes 3711541Srgrimes#ifdef RN_DEBUG 3721541Srgrimesint rn_nodenum; 3731541Srgrimesstruct radix_node *rn_clist; 3741541Srgrimesint rn_saveinfo; 3751541Srgrimesint rn_debug = 1; 3761541Srgrimes#endif 3771541Srgrimes 378128525Sluigi/* 379128525Sluigi * Whenever we add a new leaf to the tree, we also add a parent node, 380128525Sluigi * so we allocate them as an array of two elements: the first one must be 381128525Sluigi * the leaf (see RNTORT() in route.c), the second one is the parent. 382128525Sluigi * This routine initializes the relevant fields of the nodes, so that 383128525Sluigi * the leaf is the left child of the parent node, and both nodes have 384128525Sluigi * (almost) all all fields filled as appropriate. 385128525Sluigi * (XXX some fields are left unset, see the '#if 0' section). 386128525Sluigi * The function returns a pointer to the parent node. 387128525Sluigi */ 388128525Sluigi 38912820Sphkstatic struct radix_node * 3901541Srgrimesrn_newpair(v, b, nodes) 3911541Srgrimes void *v; 3921541Srgrimes int b; 3931541Srgrimes struct radix_node nodes[2]; 3941541Srgrimes{ 3951541Srgrimes register struct radix_node *tt = nodes, *t = tt + 1; 39659529Swollman t->rn_bit = b; 39759529Swollman t->rn_bmask = 0x80 >> (b & 7); 39859529Swollman t->rn_left = tt; 39959529Swollman t->rn_offset = b >> 3; 400128525Sluigi 401128525Sluigi#if 0 /* XXX perhaps we should fill these fields as well. */ 402128525Sluigi t->rn_parent = t->rn_right = NULL; 403128525Sluigi 404128525Sluigi tt->rn_mask = NULL; 405128525Sluigi tt->rn_dupedkey = NULL; 406128525Sluigi tt->rn_bmask = 0; 407128525Sluigi#endif 40859529Swollman tt->rn_bit = -1; 40959529Swollman tt->rn_key = (caddr_t)v; 41059529Swollman tt->rn_parent = t; 4111541Srgrimes tt->rn_flags = t->rn_flags = RNF_ACTIVE; 41267727Swollman tt->rn_mklist = t->rn_mklist = 0; 4131541Srgrimes#ifdef RN_DEBUG 4141541Srgrimes tt->rn_info = rn_nodenum++; t->rn_info = rn_nodenum++; 41559529Swollman tt->rn_twin = t; 41659529Swollman tt->rn_ybro = rn_clist; 41759529Swollman rn_clist = tt; 4181541Srgrimes#endif 4191541Srgrimes return t; 4201541Srgrimes} 4211541Srgrimes 42212820Sphkstatic struct radix_node * 4231541Srgrimesrn_insert(v_arg, head, dupentry, nodes) 4241541Srgrimes void *v_arg; 4251541Srgrimes struct radix_node_head *head; 4261541Srgrimes int *dupentry; 4271541Srgrimes struct radix_node nodes[2]; 4281541Srgrimes{ 4291541Srgrimes caddr_t v = v_arg; 4301541Srgrimes struct radix_node *top = head->rnh_treetop; 431200354Sluigi int head_off = top->rn_offset, vlen = LEN(v); 4321541Srgrimes register struct radix_node *t = rn_search(v_arg, top); 4331541Srgrimes register caddr_t cp = v + head_off; 4341541Srgrimes register int b; 4351541Srgrimes struct radix_node *tt; 4361541Srgrimes /* 4378152Spst * Find first bit at which v and t->rn_key differ 4381541Srgrimes */ 4391541Srgrimes { 4401541Srgrimes register caddr_t cp2 = t->rn_key + head_off; 4411541Srgrimes register int cmp_res; 4421541Srgrimes caddr_t cplim = v + vlen; 4431541Srgrimes 4441541Srgrimes while (cp < cplim) 4451541Srgrimes if (*cp2++ != *cp++) 4461541Srgrimes goto on1; 4471541Srgrimes *dupentry = 1; 4481541Srgrimes return t; 4491541Srgrimeson1: 4501541Srgrimes *dupentry = 0; 4511541Srgrimes cmp_res = (cp[-1] ^ cp2[-1]) & 0xff; 4521541Srgrimes for (b = (cp - v) << 3; cmp_res; b--) 4531541Srgrimes cmp_res >>= 1; 4541541Srgrimes } 4551541Srgrimes { 4561541Srgrimes register struct radix_node *p, *x = top; 4571541Srgrimes cp = v; 4581541Srgrimes do { 4591541Srgrimes p = x; 46059529Swollman if (cp[x->rn_offset] & x->rn_bmask) 46159529Swollman x = x->rn_right; 46259529Swollman else 46359529Swollman x = x->rn_left; 46459529Swollman } while (b > (unsigned) x->rn_bit); 46559529Swollman /* x->rn_bit < b && x->rn_bit >= 0 */ 4661541Srgrimes#ifdef RN_DEBUG 4671541Srgrimes if (rn_debug) 4688152Spst log(LOG_DEBUG, "rn_insert: Going In:\n"), traverse(p); 4691541Srgrimes#endif 47059529Swollman t = rn_newpair(v_arg, b, nodes); 47159529Swollman tt = t->rn_left; 47259529Swollman if ((cp[p->rn_offset] & p->rn_bmask) == 0) 47359529Swollman p->rn_left = t; 4741541Srgrimes else 47559529Swollman p->rn_right = t; 47659529Swollman x->rn_parent = t; 47759529Swollman t->rn_parent = p; /* frees x, p as temp vars below */ 47859529Swollman if ((cp[t->rn_offset] & t->rn_bmask) == 0) { 47959529Swollman t->rn_right = x; 4801541Srgrimes } else { 48159529Swollman t->rn_right = tt; 48259529Swollman t->rn_left = x; 4831541Srgrimes } 4841541Srgrimes#ifdef RN_DEBUG 4851541Srgrimes if (rn_debug) 4868152Spst log(LOG_DEBUG, "rn_insert: Coming Out:\n"), traverse(p); 4871541Srgrimes#endif 4881541Srgrimes } 4891541Srgrimes return (tt); 4901541Srgrimes} 4911541Srgrimes 4921541Srgrimesstruct radix_node * 4931541Srgrimesrn_addmask(n_arg, search, skip) 4941541Srgrimes int search, skip; 4951541Srgrimes void *n_arg; 4961541Srgrimes{ 4971541Srgrimes caddr_t netmask = (caddr_t)n_arg; 4981541Srgrimes register struct radix_node *x; 4991541Srgrimes register caddr_t cp, cplim; 5008152Spst register int b = 0, mlen, j; 5018152Spst int maskduplicated, m0, isnormal; 5028152Spst struct radix_node *saved_x; 5038152Spst static int last_zeroed = 0; 5041541Srgrimes 505128525Sluigi if ((mlen = LEN(netmask)) > max_keylen) 5068152Spst mlen = max_keylen; 5078152Spst if (skip == 0) 5088152Spst skip = 1; 5098152Spst if (mlen <= skip) 5108152Spst return (mask_rnhead->rnh_nodes); 5118152Spst if (skip > 1) 512128401Sluigi bcopy(rn_ones + 1, addmask_key + 1, skip - 1); 5138152Spst if ((m0 = mlen) > skip) 514128401Sluigi bcopy(netmask + skip, addmask_key + skip, mlen - skip); 5158152Spst /* 5168152Spst * Trim trailing zeroes. 5178152Spst */ 5188152Spst for (cp = addmask_key + mlen; (cp > addmask_key) && cp[-1] == 0;) 5198152Spst cp--; 5208152Spst mlen = cp - addmask_key; 5218152Spst if (mlen <= skip) { 5228152Spst if (m0 >= last_zeroed) 5238152Spst last_zeroed = mlen; 5248152Spst return (mask_rnhead->rnh_nodes); 5251541Srgrimes } 5268152Spst if (m0 < last_zeroed) 527128401Sluigi bzero(addmask_key + m0, last_zeroed - m0); 5288152Spst *addmask_key = last_zeroed = mlen; 5298152Spst x = rn_search(addmask_key, rn_masktop); 530128401Sluigi if (bcmp(addmask_key, x->rn_key, mlen) != 0) 5318152Spst x = 0; 5328152Spst if (x || search) 5338152Spst return (x); 534128433Sluigi R_Zalloc(x, struct radix_node *, max_keylen + 2 * sizeof (*x)); 5358152Spst if ((saved_x = x) == 0) 5361541Srgrimes return (0); 5378152Spst netmask = cp = (caddr_t)(x + 2); 538128401Sluigi bcopy(addmask_key, cp, mlen); 5398152Spst x = rn_insert(cp, mask_rnhead, &maskduplicated, x); 5408152Spst if (maskduplicated) { 5418152Spst log(LOG_ERR, "rn_addmask: mask impossibly already in tree"); 5428152Spst Free(saved_x); 5438152Spst return (x); 5448152Spst } 5451541Srgrimes /* 5468152Spst * Calculate index of mask, and check for normalcy. 547128433Sluigi * First find the first byte with a 0 bit, then if there are 548128433Sluigi * more bits left (remember we already trimmed the trailing 0's), 549128433Sluigi * the pattern must be one of those in normal_chars[], or we have 550128433Sluigi * a non-contiguous mask. 5511541Srgrimes */ 552128433Sluigi cplim = netmask + mlen; 553128433Sluigi isnormal = 1; 5548152Spst for (cp = netmask + skip; (cp < cplim) && *(u_char *)cp == 0xff;) 5558152Spst cp++; 5561541Srgrimes if (cp != cplim) { 557128433Sluigi static char normal_chars[] = { 558128433Sluigi 0, 0x80, 0xc0, 0xe0, 0xf0, 0xf8, 0xfc, 0xfe, 0xff}; 559128433Sluigi 5608876Srgrimes for (j = 0x80; (j & *cp) != 0; j >>= 1) 5618152Spst b++; 5628152Spst if (*cp != normal_chars[b] || cp != (cplim - 1)) 5638152Spst isnormal = 0; 5641541Srgrimes } 5658152Spst b += (cp - netmask) << 3; 56659529Swollman x->rn_bit = -1 - b; 5678152Spst if (isnormal) 5688152Spst x->rn_flags |= RNF_NORMAL; 5691541Srgrimes return (x); 5701541Srgrimes} 5711541Srgrimes 5728152Spststatic int /* XXX: arbitrary ordering for non-contiguous masks */ 5738152Spstrn_lexobetter(m_arg, n_arg) 5748152Spst void *m_arg, *n_arg; 5758152Spst{ 5768152Spst register u_char *mp = m_arg, *np = n_arg, *lim; 5778152Spst 578128525Sluigi if (LEN(mp) > LEN(np)) 5798152Spst return 1; /* not really, but need to check longer one first */ 580128525Sluigi if (LEN(mp) == LEN(np)) 581128525Sluigi for (lim = mp + LEN(mp); mp < lim;) 5828152Spst if (*mp++ > *np++) 5838152Spst return 1; 5848152Spst return 0; 5858152Spst} 5868152Spst 5878152Spststatic struct radix_mask * 5888152Spstrn_new_radix_mask(tt, next) 5898152Spst register struct radix_node *tt; 5908152Spst register struct radix_mask *next; 5918152Spst{ 5928152Spst register struct radix_mask *m; 5938152Spst 5948152Spst MKGet(m); 5958152Spst if (m == 0) { 5968152Spst log(LOG_ERR, "Mask for route not entered\n"); 5978152Spst return (0); 5988152Spst } 599128401Sluigi bzero(m, sizeof *m); 60059529Swollman m->rm_bit = tt->rn_bit; 6018152Spst m->rm_flags = tt->rn_flags; 6028152Spst if (tt->rn_flags & RNF_NORMAL) 6038152Spst m->rm_leaf = tt; 6048152Spst else 6058152Spst m->rm_mask = tt->rn_mask; 6068152Spst m->rm_mklist = next; 6078152Spst tt->rn_mklist = m; 6088152Spst return m; 6098152Spst} 6108152Spst 6111541Srgrimesstruct radix_node * 6121541Srgrimesrn_addroute(v_arg, n_arg, head, treenodes) 6131541Srgrimes void *v_arg, *n_arg; 6141541Srgrimes struct radix_node_head *head; 6151541Srgrimes struct radix_node treenodes[2]; 6161541Srgrimes{ 6171541Srgrimes caddr_t v = (caddr_t)v_arg, netmask = (caddr_t)n_arg; 6181549Srgrimes register struct radix_node *t, *x = 0, *tt; 6191541Srgrimes struct radix_node *saved_tt, *top = head->rnh_treetop; 6208152Spst short b = 0, b_leaf = 0; 6218152Spst int keyduplicated; 6228152Spst caddr_t mmask; 6231541Srgrimes struct radix_mask *m, **mp; 6241541Srgrimes 6251541Srgrimes /* 6261541Srgrimes * In dealing with non-contiguous masks, there may be 6271541Srgrimes * many different routes which have the same mask. 6281541Srgrimes * We will find it useful to have a unique pointer to 6291541Srgrimes * the mask to speed avoiding duplicate references at 6301541Srgrimes * nodes and possibly save time in calculating indices. 6311541Srgrimes */ 6321541Srgrimes if (netmask) { 63359529Swollman if ((x = rn_addmask(netmask, 0, top->rn_offset)) == 0) 6348152Spst return (0); 63559529Swollman b_leaf = x->rn_bit; 63659529Swollman b = -1 - x->rn_bit; 6371541Srgrimes netmask = x->rn_key; 6381541Srgrimes } 6391541Srgrimes /* 6401541Srgrimes * Deal with duplicated keys: attach node to previous instance 6411541Srgrimes */ 6421541Srgrimes saved_tt = tt = rn_insert(v, head, &keyduplicated, treenodes); 6431541Srgrimes if (keyduplicated) { 6448152Spst for (t = tt; tt; t = tt, tt = tt->rn_dupedkey) { 645178167Sqingli#ifdef RADIX_MPATH 646178167Sqingli /* permit multipath, if enabled for the family */ 647178167Sqingli if (rn_mpath_capable(head) && netmask == tt->rn_mask) { 648178167Sqingli /* 649178167Sqingli * go down to the end of multipaths, so that 650178167Sqingli * new entry goes into the end of rn_dupedkey 651178167Sqingli * chain. 652178167Sqingli */ 653178167Sqingli do { 654178167Sqingli t = tt; 655178167Sqingli tt = tt->rn_dupedkey; 656178167Sqingli } while (tt && t->rn_mask == tt->rn_mask); 657178167Sqingli break; 658178167Sqingli } 659178167Sqingli#endif 6601541Srgrimes if (tt->rn_mask == netmask) 6611541Srgrimes return (0); 6621541Srgrimes if (netmask == 0 || 6638152Spst (tt->rn_mask && 66459529Swollman ((b_leaf < tt->rn_bit) /* index(netmask) > node */ 66559529Swollman || rn_refines(netmask, tt->rn_mask) 66659529Swollman || rn_lexobetter(netmask, tt->rn_mask)))) 6671541Srgrimes break; 6688152Spst } 6691541Srgrimes /* 6701541Srgrimes * If the mask is not duplicated, we wouldn't 6711541Srgrimes * find it among possible duplicate key entries 6721541Srgrimes * anyway, so the above test doesn't hurt. 6731541Srgrimes * 6741541Srgrimes * We sort the masks for a duplicated key the same way as 6751541Srgrimes * in a masklist -- most specific to least specific. 6761541Srgrimes * This may require the unfortunate nuisance of relocating 6771541Srgrimes * the head of the list. 678108268Sru * 679108268Sru * We also reverse, or doubly link the list through the 680108268Sru * parent pointer. 6811541Srgrimes */ 6828152Spst if (tt == saved_tt) { 6831541Srgrimes struct radix_node *xx = x; 6841541Srgrimes /* link in at head of list */ 6851541Srgrimes (tt = treenodes)->rn_dupedkey = t; 6861541Srgrimes tt->rn_flags = t->rn_flags; 68759529Swollman tt->rn_parent = x = t->rn_parent; 68859529Swollman t->rn_parent = tt; /* parent */ 68959529Swollman if (x->rn_left == t) 69059529Swollman x->rn_left = tt; 69159529Swollman else 69259529Swollman x->rn_right = tt; 6931541Srgrimes saved_tt = tt; x = xx; 6941541Srgrimes } else { 6951541Srgrimes (tt = treenodes)->rn_dupedkey = t->rn_dupedkey; 6961541Srgrimes t->rn_dupedkey = tt; 69759529Swollman tt->rn_parent = t; /* parent */ 6988152Spst if (tt->rn_dupedkey) /* parent */ 69959529Swollman tt->rn_dupedkey->rn_parent = tt; /* parent */ 7001541Srgrimes } 7011541Srgrimes#ifdef RN_DEBUG 7021541Srgrimes t=tt+1; tt->rn_info = rn_nodenum++; t->rn_info = rn_nodenum++; 7031541Srgrimes tt->rn_twin = t; tt->rn_ybro = rn_clist; rn_clist = tt; 7041541Srgrimes#endif 7051541Srgrimes tt->rn_key = (caddr_t) v; 70659529Swollman tt->rn_bit = -1; 7078152Spst tt->rn_flags = RNF_ACTIVE; 7081541Srgrimes } 7091541Srgrimes /* 7101541Srgrimes * Put mask in tree. 7111541Srgrimes */ 7121541Srgrimes if (netmask) { 7131541Srgrimes tt->rn_mask = netmask; 71459529Swollman tt->rn_bit = x->rn_bit; 7158152Spst tt->rn_flags |= x->rn_flags & RNF_NORMAL; 7161541Srgrimes } 71759529Swollman t = saved_tt->rn_parent; 7188152Spst if (keyduplicated) 7198152Spst goto on2; 72059529Swollman b_leaf = -1 - t->rn_bit; 72159529Swollman if (t->rn_right == saved_tt) 72259529Swollman x = t->rn_left; 72359529Swollman else 72459529Swollman x = t->rn_right; 7251541Srgrimes /* Promote general routes from below */ 72659529Swollman if (x->rn_bit < 0) { 7278152Spst for (mp = &t->rn_mklist; x; x = x->rn_dupedkey) 72859529Swollman if (x->rn_mask && (x->rn_bit >= b_leaf) && x->rn_mklist == 0) { 7298152Spst *mp = m = rn_new_radix_mask(x, 0); 7308152Spst if (m) 7318152Spst mp = &m->rm_mklist; 7321541Srgrimes } 7331541Srgrimes } else if (x->rn_mklist) { 7341541Srgrimes /* 7351541Srgrimes * Skip over masks whose index is > that of new node 7361541Srgrimes */ 7378152Spst for (mp = &x->rn_mklist; (m = *mp); mp = &m->rm_mklist) 73859529Swollman if (m->rm_bit >= b_leaf) 7391541Srgrimes break; 7401541Srgrimes t->rn_mklist = m; *mp = 0; 7411541Srgrimes } 7428152Spston2: 7431541Srgrimes /* Add new route to highest possible ancestor's list */ 74459529Swollman if ((netmask == 0) || (b > t->rn_bit )) 7451541Srgrimes return tt; /* can't lift at all */ 74659529Swollman b_leaf = tt->rn_bit; 7471541Srgrimes do { 7481541Srgrimes x = t; 74959529Swollman t = t->rn_parent; 75059529Swollman } while (b <= t->rn_bit && x != top); 7511541Srgrimes /* 7521541Srgrimes * Search through routes associated with node to 7531541Srgrimes * insert new route according to index. 7548152Spst * Need same criteria as when sorting dupedkeys to avoid 7558152Spst * double loop on deletion. 7561541Srgrimes */ 7578152Spst for (mp = &x->rn_mklist; (m = *mp); mp = &m->rm_mklist) { 75859529Swollman if (m->rm_bit < b_leaf) 7591541Srgrimes continue; 76059529Swollman if (m->rm_bit > b_leaf) 7611541Srgrimes break; 7628152Spst if (m->rm_flags & RNF_NORMAL) { 7638152Spst mmask = m->rm_leaf->rn_mask; 7648152Spst if (tt->rn_flags & RNF_NORMAL) { 76559529Swollman log(LOG_ERR, 76695023Ssuz "Non-unique normal route, mask not entered\n"); 7678152Spst return tt; 7688152Spst } 7698152Spst } else 7708152Spst mmask = m->rm_mask; 7718152Spst if (mmask == netmask) { 7721541Srgrimes m->rm_refs++; 7731541Srgrimes tt->rn_mklist = m; 7741541Srgrimes return tt; 7751541Srgrimes } 77659529Swollman if (rn_refines(netmask, mmask) 77759529Swollman || rn_lexobetter(netmask, mmask)) 7781541Srgrimes break; 7791541Srgrimes } 7808152Spst *mp = rn_new_radix_mask(tt, *mp); 7811541Srgrimes return tt; 7821541Srgrimes} 7831541Srgrimes 78431390Sbdestruct radix_node * 7851541Srgrimesrn_delete(v_arg, netmask_arg, head) 7861541Srgrimes void *v_arg, *netmask_arg; 7871541Srgrimes struct radix_node_head *head; 7881541Srgrimes{ 7891541Srgrimes register struct radix_node *t, *p, *x, *tt; 7901541Srgrimes struct radix_mask *m, *saved_m, **mp; 7911541Srgrimes struct radix_node *dupedkey, *saved_tt, *top; 7921541Srgrimes caddr_t v, netmask; 7931541Srgrimes int b, head_off, vlen; 7941541Srgrimes 7951541Srgrimes v = v_arg; 7961541Srgrimes netmask = netmask_arg; 7971541Srgrimes x = head->rnh_treetop; 7981541Srgrimes tt = rn_search(v, x); 79959529Swollman head_off = x->rn_offset; 800128525Sluigi vlen = LEN(v); 8011541Srgrimes saved_tt = tt; 8021541Srgrimes top = x; 8031541Srgrimes if (tt == 0 || 804128401Sluigi bcmp(v + head_off, tt->rn_key + head_off, vlen - head_off)) 8051541Srgrimes return (0); 8061541Srgrimes /* 8071541Srgrimes * Delete our route from mask lists. 8081541Srgrimes */ 8098152Spst if (netmask) { 8108152Spst if ((x = rn_addmask(netmask, 1, head_off)) == 0) 8118152Spst return (0); 8128152Spst netmask = x->rn_key; 8131541Srgrimes while (tt->rn_mask != netmask) 8141541Srgrimes if ((tt = tt->rn_dupedkey) == 0) 8151541Srgrimes return (0); 8161541Srgrimes } 8171541Srgrimes if (tt->rn_mask == 0 || (saved_m = m = tt->rn_mklist) == 0) 8181541Srgrimes goto on1; 8198152Spst if (tt->rn_flags & RNF_NORMAL) { 8208152Spst if (m->rm_leaf != tt || m->rm_refs > 0) { 8218152Spst log(LOG_ERR, "rn_delete: inconsistent annotation\n"); 8228152Spst return 0; /* dangling ref could cause disaster */ 8238152Spst } 8248876Srgrimes } else { 8258152Spst if (m->rm_mask != tt->rn_mask) { 8268152Spst log(LOG_ERR, "rn_delete: inconsistent annotation\n"); 8278152Spst goto on1; 8288152Spst } 8298152Spst if (--m->rm_refs >= 0) 8308152Spst goto on1; 8311541Srgrimes } 83259529Swollman b = -1 - tt->rn_bit; 83359529Swollman t = saved_tt->rn_parent; 83459529Swollman if (b > t->rn_bit) 8351541Srgrimes goto on1; /* Wasn't lifted at all */ 8361541Srgrimes do { 8371541Srgrimes x = t; 83859529Swollman t = t->rn_parent; 83959529Swollman } while (b <= t->rn_bit && x != top); 8408152Spst for (mp = &x->rn_mklist; (m = *mp); mp = &m->rm_mklist) 8411541Srgrimes if (m == saved_m) { 8421541Srgrimes *mp = m->rm_mklist; 8431541Srgrimes MKFree(m); 8441541Srgrimes break; 8451541Srgrimes } 8468152Spst if (m == 0) { 8478152Spst log(LOG_ERR, "rn_delete: couldn't find our annotation\n"); 8488152Spst if (tt->rn_flags & RNF_NORMAL) 8498152Spst return (0); /* Dangling ref to us */ 8508152Spst } 8511541Srgrimeson1: 8521541Srgrimes /* 8531541Srgrimes * Eliminate us from tree 8541541Srgrimes */ 8551541Srgrimes if (tt->rn_flags & RNF_ROOT) 8561541Srgrimes return (0); 8571541Srgrimes#ifdef RN_DEBUG 8581541Srgrimes /* Get us out of the creation list */ 8591541Srgrimes for (t = rn_clist; t && t->rn_ybro != tt; t = t->rn_ybro) {} 8601541Srgrimes if (t) t->rn_ybro = tt->rn_ybro; 8611541Srgrimes#endif 86259529Swollman t = tt->rn_parent; 8638152Spst dupedkey = saved_tt->rn_dupedkey; 8641541Srgrimes if (dupedkey) { 8658152Spst /* 866108268Sru * Here, tt is the deletion target and 867108268Sru * saved_tt is the head of the dupekey chain. 8688152Spst */ 8691541Srgrimes if (tt == saved_tt) { 8708152Spst /* remove from head of chain */ 87159529Swollman x = dupedkey; x->rn_parent = t; 87259529Swollman if (t->rn_left == tt) 87359529Swollman t->rn_left = x; 87459529Swollman else 87559529Swollman t->rn_right = x; 8761541Srgrimes } else { 8778152Spst /* find node in front of tt on the chain */ 8781541Srgrimes for (x = p = saved_tt; p && p->rn_dupedkey != tt;) 8791541Srgrimes p = p->rn_dupedkey; 8808152Spst if (p) { 8818152Spst p->rn_dupedkey = tt->rn_dupedkey; 88259529Swollman if (tt->rn_dupedkey) /* parent */ 88359529Swollman tt->rn_dupedkey->rn_parent = p; 88459529Swollman /* parent */ 8858152Spst } else log(LOG_ERR, "rn_delete: couldn't find us\n"); 8861541Srgrimes } 8871541Srgrimes t = tt + 1; 8881541Srgrimes if (t->rn_flags & RNF_ACTIVE) { 8891541Srgrimes#ifndef RN_DEBUG 89059529Swollman *++x = *t; 89159529Swollman p = t->rn_parent; 8921541Srgrimes#else 89359529Swollman b = t->rn_info; 89459529Swollman *++x = *t; 89559529Swollman t->rn_info = b; 89659529Swollman p = t->rn_parent; 8971541Srgrimes#endif 89859529Swollman if (p->rn_left == t) 89959529Swollman p->rn_left = x; 90059529Swollman else 90159529Swollman p->rn_right = x; 90259529Swollman x->rn_left->rn_parent = x; 90359529Swollman x->rn_right->rn_parent = x; 9041541Srgrimes } 9051541Srgrimes goto out; 9061541Srgrimes } 90759529Swollman if (t->rn_left == tt) 90859529Swollman x = t->rn_right; 90959529Swollman else 91059529Swollman x = t->rn_left; 91159529Swollman p = t->rn_parent; 91259529Swollman if (p->rn_right == t) 91359529Swollman p->rn_right = x; 91459529Swollman else 91559529Swollman p->rn_left = x; 91659529Swollman x->rn_parent = p; 9171541Srgrimes /* 9181541Srgrimes * Demote routes attached to us. 9191541Srgrimes */ 9201541Srgrimes if (t->rn_mklist) { 92159529Swollman if (x->rn_bit >= 0) { 9228152Spst for (mp = &x->rn_mklist; (m = *mp);) 9231541Srgrimes mp = &m->rm_mklist; 9241541Srgrimes *mp = t->rn_mklist; 9251541Srgrimes } else { 9268152Spst /* If there are any key,mask pairs in a sibling 9278152Spst duped-key chain, some subset will appear sorted 9288152Spst in the same order attached to our mklist */ 9298152Spst for (m = t->rn_mklist; m && x; x = x->rn_dupedkey) 9308152Spst if (m == x->rn_mklist) { 9318152Spst struct radix_mask *mm = m->rm_mklist; 9321541Srgrimes x->rn_mklist = 0; 9338152Spst if (--(m->rm_refs) < 0) 9348152Spst MKFree(m); 9358152Spst m = mm; 9368152Spst } 9378152Spst if (m) 93837560Sbde log(LOG_ERR, 93937560Sbde "rn_delete: Orphaned Mask %p at %p\n", 94037560Sbde (void *)m, (void *)x); 9411541Srgrimes } 9421541Srgrimes } 9431541Srgrimes /* 9441541Srgrimes * We may be holding an active internal node in the tree. 9451541Srgrimes */ 9461541Srgrimes x = tt + 1; 9471541Srgrimes if (t != x) { 9481541Srgrimes#ifndef RN_DEBUG 9491541Srgrimes *t = *x; 9501541Srgrimes#else 95159529Swollman b = t->rn_info; 95259529Swollman *t = *x; 95359529Swollman t->rn_info = b; 9541541Srgrimes#endif 95559529Swollman t->rn_left->rn_parent = t; 95659529Swollman t->rn_right->rn_parent = t; 95759529Swollman p = x->rn_parent; 95859529Swollman if (p->rn_left == x) 95959529Swollman p->rn_left = t; 96059529Swollman else 96159529Swollman p->rn_right = t; 9621541Srgrimes } 9631541Srgrimesout: 9641541Srgrimes tt->rn_flags &= ~RNF_ACTIVE; 9651541Srgrimes tt[1].rn_flags &= ~RNF_ACTIVE; 9661541Srgrimes return (tt); 9671541Srgrimes} 9681541Srgrimes 9697197Swollman/* 9707197Swollman * This is the same as rn_walktree() except for the parameters and the 9717197Swollman * exit. 9727197Swollman */ 97312820Sphkstatic int 9747197Swollmanrn_walktree_from(h, a, m, f, w) 9757197Swollman struct radix_node_head *h; 9767197Swollman void *a, *m; 97712579Sbde walktree_f_t *f; 9787197Swollman void *w; 9797197Swollman{ 9807197Swollman int error; 9817197Swollman struct radix_node *base, *next; 9827197Swollman u_char *xa = (u_char *)a; 9837197Swollman u_char *xm = (u_char *)m; 9847197Swollman register struct radix_node *rn, *last = 0 /* shut up gcc */; 9857197Swollman int stopping = 0; 9867197Swollman int lastb; 9877197Swollman 9887197Swollman /* 989128525Sluigi * rn_search_m is sort-of-open-coded here. We cannot use the 990128525Sluigi * function because we need to keep track of the last node seen. 9917197Swollman */ 9927279Swollman /* printf("about to search\n"); */ 99359529Swollman for (rn = h->rnh_treetop; rn->rn_bit >= 0; ) { 9947197Swollman last = rn; 99559529Swollman /* printf("rn_bit %d, rn_bmask %x, xm[rn_offset] %x\n", 99659529Swollman rn->rn_bit, rn->rn_bmask, xm[rn->rn_offset]); */ 99759529Swollman if (!(rn->rn_bmask & xm[rn->rn_offset])) { 9987197Swollman break; 9997279Swollman } 100059529Swollman if (rn->rn_bmask & xa[rn->rn_offset]) { 100159529Swollman rn = rn->rn_right; 10027197Swollman } else { 100359529Swollman rn = rn->rn_left; 10047197Swollman } 10057197Swollman } 10067279Swollman /* printf("done searching\n"); */ 10077197Swollman 10087197Swollman /* 10097197Swollman * Two cases: either we stepped off the end of our mask, 10107197Swollman * in which case last == rn, or we reached a leaf, in which 10117197Swollman * case we want to start from the last node we looked at. 10127197Swollman * Either way, last is the node we want to start from. 10137197Swollman */ 10147197Swollman rn = last; 101559529Swollman lastb = rn->rn_bit; 10167197Swollman 10177279Swollman /* printf("rn %p, lastb %d\n", rn, lastb);*/ 10187279Swollman 10197197Swollman /* 10207197Swollman * This gets complicated because we may delete the node 10217197Swollman * while applying the function f to it, so we need to calculate 10227197Swollman * the successor node in advance. 10237197Swollman */ 102459529Swollman while (rn->rn_bit >= 0) 102559529Swollman rn = rn->rn_left; 10267197Swollman 10277197Swollman while (!stopping) { 102859529Swollman /* printf("node %p (%d)\n", rn, rn->rn_bit); */ 10297197Swollman base = rn; 10307197Swollman /* If at right child go back up, otherwise, go right */ 103159529Swollman while (rn->rn_parent->rn_right == rn 103259529Swollman && !(rn->rn_flags & RNF_ROOT)) { 103359529Swollman rn = rn->rn_parent; 10347197Swollman 10358876Srgrimes /* if went up beyond last, stop */ 1036155442Sqingli if (rn->rn_bit <= lastb) { 10377197Swollman stopping = 1; 10387279Swollman /* printf("up too far\n"); */ 1039128525Sluigi /* 1040128525Sluigi * XXX we should jump to the 'Process leaves' 1041128525Sluigi * part, because the values of 'rn' and 'next' 1042128525Sluigi * we compute will not be used. Not a big deal 1043128525Sluigi * because this loop will terminate, but it is 1044128525Sluigi * inefficient and hard to understand! 1045128525Sluigi */ 10467197Swollman } 10477197Swollman } 1048155442Sqingli 1049155442Sqingli /* 1050155442Sqingli * At the top of the tree, no need to traverse the right 1051155442Sqingli * half, prevent the traversal of the entire tree in the 1052155442Sqingli * case of default route. 1053155442Sqingli */ 1054155442Sqingli if (rn->rn_parent->rn_flags & RNF_ROOT) 1055155442Sqingli stopping = 1; 10567197Swollman 10577197Swollman /* Find the next *leaf* since next node might vanish, too */ 105859529Swollman for (rn = rn->rn_parent->rn_right; rn->rn_bit >= 0;) 105959529Swollman rn = rn->rn_left; 10607197Swollman next = rn; 10617197Swollman /* Process leaves */ 10627197Swollman while ((rn = base) != 0) { 10637197Swollman base = rn->rn_dupedkey; 10647279Swollman /* printf("leaf %p\n", rn); */ 10658876Srgrimes if (!(rn->rn_flags & RNF_ROOT) 10667197Swollman && (error = (*f)(rn, w))) 10677197Swollman return (error); 10687197Swollman } 10697197Swollman rn = next; 10707279Swollman 10717279Swollman if (rn->rn_flags & RNF_ROOT) { 10727279Swollman /* printf("root, stopping"); */ 10737279Swollman stopping = 1; 10747279Swollman } 10757279Swollman 10767197Swollman } 10777197Swollman return 0; 10787197Swollman} 10797197Swollman 108012820Sphkstatic int 10811541Srgrimesrn_walktree(h, f, w) 10821541Srgrimes struct radix_node_head *h; 108312579Sbde walktree_f_t *f; 10841541Srgrimes void *w; 10851541Srgrimes{ 10861541Srgrimes int error; 10871541Srgrimes struct radix_node *base, *next; 10881541Srgrimes register struct radix_node *rn = h->rnh_treetop; 10891541Srgrimes /* 10901541Srgrimes * This gets complicated because we may delete the node 10911541Srgrimes * while applying the function f to it, so we need to calculate 10921541Srgrimes * the successor node in advance. 10931541Srgrimes */ 1094186166Skmacy 10951541Srgrimes /* First time through node, go left */ 109659529Swollman while (rn->rn_bit >= 0) 109759529Swollman rn = rn->rn_left; 10981541Srgrimes for (;;) { 10991541Srgrimes base = rn; 11001541Srgrimes /* If at right child go back up, otherwise, go right */ 110159529Swollman while (rn->rn_parent->rn_right == rn 110259529Swollman && (rn->rn_flags & RNF_ROOT) == 0) 110359529Swollman rn = rn->rn_parent; 11041541Srgrimes /* Find the next *leaf* since next node might vanish, too */ 110559529Swollman for (rn = rn->rn_parent->rn_right; rn->rn_bit >= 0;) 110659529Swollman rn = rn->rn_left; 11071541Srgrimes next = rn; 11081541Srgrimes /* Process leaves */ 11098152Spst while ((rn = base)) { 11101541Srgrimes base = rn->rn_dupedkey; 111159529Swollman if (!(rn->rn_flags & RNF_ROOT) 111259529Swollman && (error = (*f)(rn, w))) 11131541Srgrimes return (error); 11141541Srgrimes } 11151541Srgrimes rn = next; 11161541Srgrimes if (rn->rn_flags & RNF_ROOT) 11171541Srgrimes return (0); 11181541Srgrimes } 11191541Srgrimes /* NOTREACHED */ 11201541Srgrimes} 11211541Srgrimes 1122128525Sluigi/* 1123128525Sluigi * Allocate and initialize an empty tree. This has 3 nodes, which are 1124128525Sluigi * part of the radix_node_head (in the order <left,root,right>) and are 1125128525Sluigi * marked RNF_ROOT so they cannot be freed. 1126128525Sluigi * The leaves have all-zero and all-one keys, with significant 1127128525Sluigi * bits starting at 'off'. 1128128525Sluigi * Return 1 on success, 0 on error. 1129128525Sluigi */ 11301541Srgrimesint 11311541Srgrimesrn_inithead(head, off) 11321541Srgrimes void **head; 11331541Srgrimes int off; 11341541Srgrimes{ 11351541Srgrimes register struct radix_node_head *rnh; 11361541Srgrimes register struct radix_node *t, *tt, *ttt; 11371541Srgrimes if (*head) 11381541Srgrimes return (1); 1139128433Sluigi R_Zalloc(rnh, struct radix_node_head *, sizeof (*rnh)); 11401541Srgrimes if (rnh == 0) 11411541Srgrimes return (0); 1142110527Shsu#ifdef _KERNEL 1143108250Shsu RADIX_NODE_HEAD_LOCK_INIT(rnh); 1144110527Shsu#endif 11451541Srgrimes *head = rnh; 11461541Srgrimes t = rn_newpair(rn_zeros, off, rnh->rnh_nodes); 11471541Srgrimes ttt = rnh->rnh_nodes + 2; 114859529Swollman t->rn_right = ttt; 114959529Swollman t->rn_parent = t; 1150128525Sluigi tt = t->rn_left; /* ... which in turn is rnh->rnh_nodes */ 11511541Srgrimes tt->rn_flags = t->rn_flags = RNF_ROOT | RNF_ACTIVE; 115259529Swollman tt->rn_bit = -1 - off; 11531541Srgrimes *ttt = *tt; 11541541Srgrimes ttt->rn_key = rn_ones; 11551541Srgrimes rnh->rnh_addaddr = rn_addroute; 11561541Srgrimes rnh->rnh_deladdr = rn_delete; 11571541Srgrimes rnh->rnh_matchaddr = rn_match; 11588152Spst rnh->rnh_lookup = rn_lookup; 11591541Srgrimes rnh->rnh_walktree = rn_walktree; 11607197Swollman rnh->rnh_walktree_from = rn_walktree_from; 11611541Srgrimes rnh->rnh_treetop = t; 11621541Srgrimes return (1); 11631541Srgrimes} 11641541Srgrimes 11651541Srgrimesvoid 11661541Srgrimesrn_init() 11671541Srgrimes{ 11681541Srgrimes char *cp, *cplim; 116955205Speter#ifdef _KERNEL 11701541Srgrimes struct domain *dom; 11711541Srgrimes 11721541Srgrimes for (dom = domains; dom; dom = dom->dom_next) 11731541Srgrimes if (dom->dom_maxrtkey > max_keylen) 11741541Srgrimes max_keylen = dom->dom_maxrtkey; 11751541Srgrimes#endif 11761541Srgrimes if (max_keylen == 0) { 11778152Spst log(LOG_ERR, 11788152Spst "rn_init: radix functions require max_keylen be set\n"); 11791541Srgrimes return; 11801541Srgrimes } 11811541Srgrimes R_Malloc(rn_zeros, char *, 3 * max_keylen); 11821541Srgrimes if (rn_zeros == NULL) 11831541Srgrimes panic("rn_init"); 1184128401Sluigi bzero(rn_zeros, 3 * max_keylen); 11851541Srgrimes rn_ones = cp = rn_zeros + max_keylen; 11868152Spst addmask_key = cplim = rn_ones + max_keylen; 11871541Srgrimes while (cp < cplim) 11881541Srgrimes *cp++ = -1; 1189120359Speter if (rn_inithead((void **)(void *)&mask_rnhead, 0) == 0) 11901541Srgrimes panic("rn_init 2"); 11911541Srgrimes} 1192200439Sluigi 1193200439Sluigi#ifndef _KERNEL 1194200439Sluigi/* 1195200439Sluigi * A simple function to make the code usable from userland. 1196200439Sluigi * A proper fix (maybe later) would be to change rn_init() so that it 1197200439Sluigi * takes maxkeylen as an argument, and move the scan of 1198200439Sluigi * domains into net/route.c::route_init(). 1199200439Sluigi */ 1200200439Sluigivoid rn_init2(int maxk); 1201200439Sluigivoid 1202200439Sluigirn_init2(int maxk) 1203200439Sluigi{ 1204200439Sluigi max_keylen = maxk; 1205200439Sluigi rn_init(); 1206200439Sluigi} 1207200439Sluigi#endif /* !_KERNEL */ 1208