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$ 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 5912820Sphkstatic struct radix_node 60294706Smelifaro *rn_insert(void *, struct radix_head *, int *, 6193084Sbde struct radix_node [2]), 6292725Salfred *rn_newpair(void *, int, struct radix_node[2]), 6392725Salfred *rn_search(void *, struct radix_node *), 6492725Salfred *rn_search_m(void *, struct radix_node *, void *); 65294706Smelifarostatic struct radix_node *rn_addmask(void *, struct radix_mask_head *, int,int); 6612579Sbde 67294706Smelifarostatic void rn_detachhead_internal(struct radix_head *); 681541Srgrimes 69256624Smelifaro#define RADIX_MAX_KEY_LEN 32 70128401Sluigi 71256624Smelifarostatic char rn_zeros[RADIX_MAX_KEY_LEN]; 72256624Smelifarostatic char rn_ones[RADIX_MAX_KEY_LEN] = { 73256624Smelifaro -1, -1, -1, -1, -1, -1, -1, -1, 74256624Smelifaro -1, -1, -1, -1, -1, -1, -1, -1, 75256624Smelifaro -1, -1, -1, -1, -1, -1, -1, -1, 76256624Smelifaro -1, -1, -1, -1, -1, -1, -1, -1, 77256624Smelifaro}; 7812579Sbde 79256624Smelifaro 8092725Salfredstatic int rn_lexobetter(void *m_arg, void *n_arg); 8112579Sbdestatic struct radix_mask * 8292725Salfred rn_new_radix_mask(struct radix_node *tt, 8393084Sbde struct radix_mask *next); 84108273Srustatic int rn_satisfies_leaf(char *trial, struct radix_node *leaf, 8593084Sbde int skip); 8612579Sbde 871541Srgrimes/* 881541Srgrimes * The data structure for the keys is a radix tree with one way 8959529Swollman * branching removed. The index rn_bit at an internal node n represents a bit 901541Srgrimes * position to be tested. The tree is arranged so that all descendants 9159529Swollman * of a node n have keys whose bits all agree up to position rn_bit - 1. 9259529Swollman * (We say the index of n is rn_bit.) 931541Srgrimes * 9459529Swollman * There is at least one descendant which has a one bit at position rn_bit, 951541Srgrimes * and at least one with a zero there. 961541Srgrimes * 971541Srgrimes * A route is determined by a pair of key and mask. We require that the 981541Srgrimes * bit-wise logical and of the key and mask to be the key. 991541Srgrimes * We define the index of a route to associated with the mask to be 1001541Srgrimes * the first bit number in the mask where 0 occurs (with bit number 0 1011541Srgrimes * representing the highest order bit). 1028876Srgrimes * 1031541Srgrimes * We say a mask is normal if every bit is 0, past the index of the mask. 10459529Swollman * If a node n has a descendant (k, m) with index(m) == index(n) == rn_bit, 1051541Srgrimes * and m is a normal mask, then the route applies to every descendant of n. 10659529Swollman * If the index(m) < rn_bit, this implies the trailing last few bits of k 1071541Srgrimes * before bit b are all 0, (and hence consequently true of every descendant 1081541Srgrimes * of n), so the route applies to all descendants of the node as well. 1098876Srgrimes * 1108152Spst * Similar logic shows that a non-normal mask m such that 1111541Srgrimes * index(m) <= index(n) could potentially apply to many children of n. 1121541Srgrimes * Thus, for each non-host route, we attach its mask to a list at an internal 1138876Srgrimes * node as high in the tree as we can go. 1148152Spst * 1158152Spst * The present version of the code makes use of normal routes in short- 1168152Spst * circuiting an explict mask and compare operation when testing whether 1178152Spst * a key satisfies a normal route, and also in remembering the unique leaf 1188152Spst * that governs a subtree. 1191541Srgrimes */ 1201541Srgrimes 121128525Sluigi/* 122128525Sluigi * Most of the functions in this code assume that the key/mask arguments 123128525Sluigi * are sockaddr-like structures, where the first byte is an u_char 124128525Sluigi * indicating the size of the entire structure. 125128525Sluigi * 126128525Sluigi * To make the assumption more explicit, we use the LEN() macro to access 127128525Sluigi * this field. It is safe to pass an expression with side effects 128128525Sluigi * to LEN() as the argument is evaluated only once. 129200354Sluigi * We cast the result to int as this is the dominant usage. 130128525Sluigi */ 131200354Sluigi#define LEN(x) ( (int) (*(const u_char *)(x)) ) 132128525Sluigi 133128525Sluigi/* 134128525Sluigi * XXX THIS NEEDS TO BE FIXED 135128525Sluigi * In the code, pointers to keys and masks are passed as either 136128525Sluigi * 'void *' (because callers use to pass pointers of various kinds), or 137128525Sluigi * 'caddr_t' (which is fine for pointer arithmetics, but not very 138128525Sluigi * clean when you dereference it to access data). Furthermore, caddr_t 139128525Sluigi * is really 'char *', while the natural type to operate on keys and 140128525Sluigi * masks would be 'u_char'. This mismatch require a lot of casts and 141128525Sluigi * intermediate variables to adapt types that clutter the code. 142128525Sluigi */ 143128525Sluigi 144128525Sluigi/* 145128525Sluigi * Search a node in the tree matching the key. 146128525Sluigi */ 14712820Sphkstatic struct radix_node * 148260228Smelifarorn_search(void *v_arg, struct radix_node *head) 1491541Srgrimes{ 150260228Smelifaro struct radix_node *x; 151260228Smelifaro caddr_t v; 1521541Srgrimes 15359529Swollman for (x = head, v = v_arg; x->rn_bit >= 0;) { 15459529Swollman if (x->rn_bmask & v[x->rn_offset]) 15559529Swollman x = x->rn_right; 1561541Srgrimes else 15759529Swollman x = x->rn_left; 1581541Srgrimes } 1591541Srgrimes return (x); 16031390Sbde} 1611541Srgrimes 162128525Sluigi/* 163128525Sluigi * Same as above, but with an additional mask. 164128525Sluigi * XXX note this function is used only once. 165128525Sluigi */ 16612820Sphkstatic struct radix_node * 167260228Smelifarorn_search_m(void *v_arg, struct radix_node *head, void *m_arg) 1681541Srgrimes{ 169260228Smelifaro struct radix_node *x; 170260228Smelifaro caddr_t v = v_arg, m = m_arg; 1711541Srgrimes 17259529Swollman for (x = head; x->rn_bit >= 0;) { 17359529Swollman if ((x->rn_bmask & m[x->rn_offset]) && 17459529Swollman (x->rn_bmask & v[x->rn_offset])) 17559529Swollman x = x->rn_right; 1761541Srgrimes else 17759529Swollman x = x->rn_left; 1781541Srgrimes } 179260228Smelifaro return (x); 18031390Sbde} 1811541Srgrimes 1821541Srgrimesint 183260228Smelifarorn_refines(void *m_arg, void *n_arg) 1841541Srgrimes{ 185260228Smelifaro caddr_t m = m_arg, n = n_arg; 186260228Smelifaro caddr_t lim, lim2 = lim = n + LEN(n); 187200354Sluigi int longer = LEN(n++) - LEN(m++); 1881541Srgrimes int masks_are_equal = 1; 1891541Srgrimes 1901541Srgrimes if (longer > 0) 1911541Srgrimes lim -= longer; 1921541Srgrimes while (n < lim) { 1931541Srgrimes if (*n & ~(*m)) 194260228Smelifaro return (0); 1951541Srgrimes if (*n++ != *m++) 1961541Srgrimes masks_are_equal = 0; 1971541Srgrimes } 1981541Srgrimes while (n < lim2) 1991541Srgrimes if (*n++) 200260228Smelifaro return (0); 2011541Srgrimes if (masks_are_equal && (longer < 0)) 2021541Srgrimes for (lim2 = m - longer; m < lim2; ) 2031541Srgrimes if (*m++) 204260228Smelifaro return (1); 2051541Srgrimes return (!masks_are_equal); 2061541Srgrimes} 2071541Srgrimes 208260295Smelifaro/* 209260295Smelifaro * Search for exact match in given @head. 210260295Smelifaro * Assume host bits are cleared in @v_arg if @m_arg is not NULL 211260295Smelifaro * Note that prefixes with /32 or /128 masks are treated differently 212260295Smelifaro * from host routes. 213260295Smelifaro */ 2148152Spststruct radix_node * 215294706Smelifarorn_lookup(void *v_arg, void *m_arg, struct radix_head *head) 2168152Spst{ 217260228Smelifaro struct radix_node *x; 218260295Smelifaro caddr_t netmask; 2191541Srgrimes 220260295Smelifaro if (m_arg != NULL) { 221260295Smelifaro /* 222260295Smelifaro * Most common case: search exact prefix/mask 223260295Smelifaro */ 224256624Smelifaro x = rn_addmask(m_arg, head->rnh_masks, 1, 225256624Smelifaro head->rnh_treetop->rn_offset); 226260295Smelifaro if (x == NULL) 227260295Smelifaro return (NULL); 2288152Spst netmask = x->rn_key; 229260295Smelifaro 230260295Smelifaro x = rn_match(v_arg, head); 231260295Smelifaro 232260295Smelifaro while (x != NULL && x->rn_mask != netmask) 2338152Spst x = x->rn_dupedkey; 234260295Smelifaro 235260295Smelifaro return (x); 2368152Spst } 237260295Smelifaro 238260295Smelifaro /* 239260295Smelifaro * Search for host address. 240260295Smelifaro */ 241260295Smelifaro if ((x = rn_match(v_arg, head)) == NULL) 242260295Smelifaro return (NULL); 243260295Smelifaro 244260295Smelifaro /* Check if found key is the same */ 245260295Smelifaro if (LEN(x->rn_key) != LEN(v_arg) || bcmp(x->rn_key, v_arg, LEN(v_arg))) 246260295Smelifaro return (NULL); 247260295Smelifaro 248260295Smelifaro /* Check if this is not host route */ 249260295Smelifaro if (x->rn_mask != NULL) 250260295Smelifaro return (NULL); 251260295Smelifaro 252260228Smelifaro return (x); 2538152Spst} 2548152Spst 2558152Spststatic int 256260228Smelifarorn_satisfies_leaf(char *trial, struct radix_node *leaf, int skip) 2578152Spst{ 258260228Smelifaro char *cp = trial, *cp2 = leaf->rn_key, *cp3 = leaf->rn_mask; 2598152Spst char *cplim; 260128525Sluigi int length = min(LEN(cp), LEN(cp2)); 2618152Spst 262200354Sluigi if (cp3 == NULL) 2638152Spst cp3 = rn_ones; 2648152Spst else 265200354Sluigi length = min(length, LEN(cp3)); 2668152Spst cplim = cp + length; cp3 += skip; cp2 += skip; 2678152Spst for (cp += skip; cp < cplim; cp++, cp2++, cp3++) 2688152Spst if ((*cp ^ *cp2) & *cp3) 269260228Smelifaro return (0); 270260228Smelifaro return (1); 2718152Spst} 2728152Spst 273260295Smelifaro/* 274260295Smelifaro * Search for longest-prefix match in given @head 275260295Smelifaro */ 2761541Srgrimesstruct radix_node * 277294706Smelifarorn_match(void *v_arg, struct radix_head *head) 2781541Srgrimes{ 2791541Srgrimes caddr_t v = v_arg; 280260228Smelifaro struct radix_node *t = head->rnh_treetop, *x; 281260228Smelifaro caddr_t cp = v, cp2; 2828152Spst caddr_t cplim; 2831541Srgrimes struct radix_node *saved_t, *top = t; 284128525Sluigi int off = t->rn_offset, vlen = LEN(cp), matched_off; 285260228Smelifaro int test, b, rn_bit; 2861541Srgrimes 2871541Srgrimes /* 2881541Srgrimes * Open code rn_search(v, top) to avoid overhead of extra 2891541Srgrimes * subroutine call. 2901541Srgrimes */ 29159529Swollman for (; t->rn_bit >= 0; ) { 29259529Swollman if (t->rn_bmask & cp[t->rn_offset]) 29359529Swollman t = t->rn_right; 2941541Srgrimes else 29559529Swollman t = t->rn_left; 2961541Srgrimes } 2971541Srgrimes /* 2981541Srgrimes * See if we match exactly as a host destination 2998152Spst * or at least learn how many bits match, for normal mask finesse. 3008152Spst * 3018152Spst * It doesn't hurt us to limit how many bytes to check 3028152Spst * to the length of the mask, since if it matches we had a genuine 3038152Spst * match and the leaf we have is the most specific one anyway; 3048152Spst * if it didn't match with a shorter length it would fail 3058152Spst * with a long one. This wins big for class B&C netmasks which 3068152Spst * are probably the most common case... 3071541Srgrimes */ 3088152Spst if (t->rn_mask) 3098152Spst vlen = *(u_char *)t->rn_mask; 3101541Srgrimes cp += off; cp2 = t->rn_key + off; cplim = v + vlen; 3111541Srgrimes for (; cp < cplim; cp++, cp2++) 3121541Srgrimes if (*cp != *cp2) 3131541Srgrimes goto on1; 3141541Srgrimes /* 3151541Srgrimes * This extra grot is in case we are explicitly asked 3161541Srgrimes * to look up the default. Ugh! 31748215Spb * 31848215Spb * Never return the root node itself, it seems to cause a 31948215Spb * lot of confusion. 3201541Srgrimes */ 32148215Spb if (t->rn_flags & RNF_ROOT) 3221541Srgrimes t = t->rn_dupedkey; 323260228Smelifaro return (t); 3241541Srgrimeson1: 3258152Spst test = (*cp ^ *cp2) & 0xff; /* find first bit that differs */ 3268152Spst for (b = 7; (test >>= 1) > 0;) 3278152Spst b--; 3281541Srgrimes matched_off = cp - v; 3298152Spst b += matched_off << 3; 33059529Swollman rn_bit = -1 - b; 3318152Spst /* 3328152Spst * If there is a host route in a duped-key chain, it will be first. 3338152Spst */ 3348152Spst if ((saved_t = t)->rn_mask == 0) 3358152Spst t = t->rn_dupedkey; 3368152Spst for (; t; t = t->rn_dupedkey) 3371541Srgrimes /* 3388152Spst * Even if we don't match exactly as a host, 3391541Srgrimes * we may match if the leaf we wound up at is 3401541Srgrimes * a route to a net. 3411541Srgrimes */ 3428152Spst if (t->rn_flags & RNF_NORMAL) { 34359529Swollman if (rn_bit <= t->rn_bit) 344260228Smelifaro return (t); 345108273Sru } else if (rn_satisfies_leaf(v, t, matched_off)) 346260228Smelifaro return (t); 3471541Srgrimes t = saved_t; 3481541Srgrimes /* start searching up the tree */ 3491541Srgrimes do { 350260228Smelifaro struct radix_mask *m; 35159529Swollman t = t->rn_parent; 3523443Sphk m = t->rn_mklist; 35359529Swollman /* 35459529Swollman * If non-contiguous masks ever become important 35559529Swollman * we can restore the masking and open coding of 35659529Swollman * the search and satisfaction test and put the 35759529Swollman * calculation of "off" back before the "do". 35859529Swollman */ 35959529Swollman while (m) { 36059529Swollman if (m->rm_flags & RNF_NORMAL) { 36159529Swollman if (rn_bit <= m->rm_bit) 36259529Swollman return (m->rm_leaf); 36359529Swollman } else { 36459529Swollman off = min(t->rn_offset, matched_off); 36559529Swollman x = rn_search_m(v, t, m->rm_mask); 36659529Swollman while (x && x->rn_mask != m->rm_mask) 36759529Swollman x = x->rn_dupedkey; 368108273Sru if (x && rn_satisfies_leaf(v, x, off)) 369260228Smelifaro return (x); 37059529Swollman } 37159529Swollman m = m->rm_mklist; 3721541Srgrimes } 3731541Srgrimes } while (t != top); 374260228Smelifaro return (0); 37531390Sbde} 3768876Srgrimes 3771541Srgrimes#ifdef RN_DEBUG 3781541Srgrimesint rn_nodenum; 3791541Srgrimesstruct radix_node *rn_clist; 3801541Srgrimesint rn_saveinfo; 3811541Srgrimesint rn_debug = 1; 3821541Srgrimes#endif 3831541Srgrimes 384128525Sluigi/* 385128525Sluigi * Whenever we add a new leaf to the tree, we also add a parent node, 386128525Sluigi * so we allocate them as an array of two elements: the first one must be 387128525Sluigi * the leaf (see RNTORT() in route.c), the second one is the parent. 388128525Sluigi * This routine initializes the relevant fields of the nodes, so that 389128525Sluigi * the leaf is the left child of the parent node, and both nodes have 390128525Sluigi * (almost) all all fields filled as appropriate. 391128525Sluigi * (XXX some fields are left unset, see the '#if 0' section). 392128525Sluigi * The function returns a pointer to the parent node. 393128525Sluigi */ 394128525Sluigi 39512820Sphkstatic struct radix_node * 396260228Smelifarorn_newpair(void *v, int b, struct radix_node nodes[2]) 3971541Srgrimes{ 398260228Smelifaro struct radix_node *tt = nodes, *t = tt + 1; 39959529Swollman t->rn_bit = b; 40059529Swollman t->rn_bmask = 0x80 >> (b & 7); 40159529Swollman t->rn_left = tt; 40259529Swollman t->rn_offset = b >> 3; 403128525Sluigi 404128525Sluigi#if 0 /* XXX perhaps we should fill these fields as well. */ 405128525Sluigi t->rn_parent = t->rn_right = NULL; 406128525Sluigi 407128525Sluigi tt->rn_mask = NULL; 408128525Sluigi tt->rn_dupedkey = NULL; 409128525Sluigi tt->rn_bmask = 0; 410128525Sluigi#endif 41159529Swollman tt->rn_bit = -1; 41259529Swollman tt->rn_key = (caddr_t)v; 41359529Swollman tt->rn_parent = t; 4141541Srgrimes tt->rn_flags = t->rn_flags = RNF_ACTIVE; 41567727Swollman tt->rn_mklist = t->rn_mklist = 0; 4161541Srgrimes#ifdef RN_DEBUG 4171541Srgrimes tt->rn_info = rn_nodenum++; t->rn_info = rn_nodenum++; 41859529Swollman tt->rn_twin = t; 41959529Swollman tt->rn_ybro = rn_clist; 42059529Swollman rn_clist = tt; 4211541Srgrimes#endif 422260228Smelifaro return (t); 4231541Srgrimes} 4241541Srgrimes 42512820Sphkstatic struct radix_node * 426294706Smelifarorn_insert(void *v_arg, struct radix_head *head, int *dupentry, 427260228Smelifaro 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); 432260228Smelifaro struct radix_node *t = rn_search(v_arg, top); 433260228Smelifaro caddr_t cp = v + head_off; 434260228Smelifaro int b; 435260228Smelifaro struct radix_node *p, *tt, *x; 4361541Srgrimes /* 4378152Spst * Find first bit at which v and t->rn_key differ 4381541Srgrimes */ 439260228Smelifaro caddr_t cp2 = t->rn_key + head_off; 440260228Smelifaro int cmp_res; 4411541Srgrimes caddr_t cplim = v + vlen; 4421541Srgrimes 4431541Srgrimes while (cp < cplim) 4441541Srgrimes if (*cp2++ != *cp++) 4451541Srgrimes goto on1; 4461541Srgrimes *dupentry = 1; 447260228Smelifaro 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; 453260228Smelifaro 454260228Smelifaro x = top; 4551541Srgrimes cp = v; 4561541Srgrimes do { 4571541Srgrimes p = x; 45859529Swollman if (cp[x->rn_offset] & x->rn_bmask) 45959529Swollman x = x->rn_right; 46059529Swollman else 46159529Swollman x = x->rn_left; 46259529Swollman } while (b > (unsigned) x->rn_bit); 46359529Swollman /* x->rn_bit < b && x->rn_bit >= 0 */ 4641541Srgrimes#ifdef RN_DEBUG 4651541Srgrimes if (rn_debug) 4668152Spst log(LOG_DEBUG, "rn_insert: Going In:\n"), traverse(p); 4671541Srgrimes#endif 46859529Swollman t = rn_newpair(v_arg, b, nodes); 46959529Swollman tt = t->rn_left; 47059529Swollman if ((cp[p->rn_offset] & p->rn_bmask) == 0) 47159529Swollman p->rn_left = t; 4721541Srgrimes else 47359529Swollman p->rn_right = t; 47459529Swollman x->rn_parent = t; 47559529Swollman t->rn_parent = p; /* frees x, p as temp vars below */ 47659529Swollman if ((cp[t->rn_offset] & t->rn_bmask) == 0) { 47759529Swollman t->rn_right = x; 4781541Srgrimes } else { 47959529Swollman t->rn_right = tt; 48059529Swollman t->rn_left = x; 4811541Srgrimes } 4821541Srgrimes#ifdef RN_DEBUG 4831541Srgrimes if (rn_debug) 4848152Spst log(LOG_DEBUG, "rn_insert: Coming Out:\n"), traverse(p); 4851541Srgrimes#endif 4861541Srgrimes return (tt); 4871541Srgrimes} 4881541Srgrimes 4891541Srgrimesstruct radix_node * 490294706Smelifarorn_addmask(void *n_arg, struct radix_mask_head *maskhead, int search, int skip) 4911541Srgrimes{ 492259528Smelifaro unsigned char *netmask = n_arg; 493259528Smelifaro unsigned char *cp, *cplim; 494259528Smelifaro struct radix_node *x; 495259528Smelifaro int b = 0, mlen, j; 496256624Smelifaro int maskduplicated, isnormal; 4978152Spst struct radix_node *saved_x; 498259528Smelifaro unsigned char addmask_key[RADIX_MAX_KEY_LEN]; 4991541Srgrimes 500256624Smelifaro if ((mlen = LEN(netmask)) > RADIX_MAX_KEY_LEN) 501256624Smelifaro mlen = RADIX_MAX_KEY_LEN; 5028152Spst if (skip == 0) 5038152Spst skip = 1; 5048152Spst if (mlen <= skip) 505294706Smelifaro return (maskhead->mask_nodes); 506256624Smelifaro 507256624Smelifaro bzero(addmask_key, RADIX_MAX_KEY_LEN); 5088152Spst if (skip > 1) 509128401Sluigi bcopy(rn_ones + 1, addmask_key + 1, skip - 1); 510256624Smelifaro bcopy(netmask + skip, addmask_key + skip, mlen - skip); 5118152Spst /* 5128152Spst * Trim trailing zeroes. 5138152Spst */ 5148152Spst for (cp = addmask_key + mlen; (cp > addmask_key) && cp[-1] == 0;) 5158152Spst cp--; 5168152Spst mlen = cp - addmask_key; 517256624Smelifaro if (mlen <= skip) 518294706Smelifaro return (maskhead->mask_nodes); 519256624Smelifaro *addmask_key = mlen; 520294706Smelifaro x = rn_search(addmask_key, maskhead->head.rnh_treetop); 521128401Sluigi if (bcmp(addmask_key, x->rn_key, mlen) != 0) 522298075Spfg x = NULL; 5238152Spst if (x || search) 5248152Spst return (x); 525256624Smelifaro R_Zalloc(x, struct radix_node *, RADIX_MAX_KEY_LEN + 2 * sizeof (*x)); 526298075Spfg if ((saved_x = x) == NULL) 5271541Srgrimes return (0); 528273479Sluigi netmask = cp = (unsigned char *)(x + 2); 529128401Sluigi bcopy(addmask_key, cp, mlen); 530294706Smelifaro x = rn_insert(cp, &maskhead->head, &maskduplicated, x); 5318152Spst if (maskduplicated) { 5328152Spst log(LOG_ERR, "rn_addmask: mask impossibly already in tree"); 533286057Sloos R_Free(saved_x); 5348152Spst return (x); 5358152Spst } 5361541Srgrimes /* 5378152Spst * Calculate index of mask, and check for normalcy. 538128433Sluigi * First find the first byte with a 0 bit, then if there are 539128433Sluigi * more bits left (remember we already trimmed the trailing 0's), 540259528Smelifaro * the bits should be contiguous, otherwise we have got 541128433Sluigi * a non-contiguous mask. 5421541Srgrimes */ 543259528Smelifaro#define CONTIG(_c) (((~(_c) + 1) & (_c)) == (unsigned char)(~(_c) + 1)) 544128433Sluigi cplim = netmask + mlen; 545128433Sluigi isnormal = 1; 5468152Spst for (cp = netmask + skip; (cp < cplim) && *(u_char *)cp == 0xff;) 5478152Spst cp++; 5481541Srgrimes if (cp != cplim) { 5498876Srgrimes for (j = 0x80; (j & *cp) != 0; j >>= 1) 5508152Spst b++; 551259528Smelifaro if (!CONTIG(*cp) || cp != (cplim - 1)) 5528152Spst isnormal = 0; 5531541Srgrimes } 5548152Spst b += (cp - netmask) << 3; 55559529Swollman x->rn_bit = -1 - b; 5568152Spst if (isnormal) 5578152Spst x->rn_flags |= RNF_NORMAL; 5581541Srgrimes return (x); 5591541Srgrimes} 5601541Srgrimes 5618152Spststatic int /* XXX: arbitrary ordering for non-contiguous masks */ 562260228Smelifarorn_lexobetter(void *m_arg, void *n_arg) 5638152Spst{ 564260228Smelifaro u_char *mp = m_arg, *np = n_arg, *lim; 5658152Spst 566128525Sluigi if (LEN(mp) > LEN(np)) 567260228Smelifaro return (1); /* not really, but need to check longer one first */ 568128525Sluigi if (LEN(mp) == LEN(np)) 569128525Sluigi for (lim = mp + LEN(mp); mp < lim;) 5708152Spst if (*mp++ > *np++) 571260228Smelifaro return (1); 572260228Smelifaro return (0); 5738152Spst} 5748152Spst 5758152Spststatic struct radix_mask * 576260228Smelifarorn_new_radix_mask(struct radix_node *tt, struct radix_mask *next) 5778152Spst{ 578260228Smelifaro struct radix_mask *m; 5798152Spst 580256624Smelifaro R_Malloc(m, struct radix_mask *, sizeof (struct radix_mask)); 581260228Smelifaro if (m == NULL) { 582256624Smelifaro log(LOG_ERR, "Failed to allocate route mask\n"); 5838152Spst return (0); 5848152Spst } 585256624Smelifaro bzero(m, sizeof(*m)); 58659529Swollman m->rm_bit = tt->rn_bit; 5878152Spst m->rm_flags = tt->rn_flags; 5888152Spst if (tt->rn_flags & RNF_NORMAL) 5898152Spst m->rm_leaf = tt; 5908152Spst else 5918152Spst m->rm_mask = tt->rn_mask; 5928152Spst m->rm_mklist = next; 5938152Spst tt->rn_mklist = m; 594260228Smelifaro return (m); 5958152Spst} 5968152Spst 5971541Srgrimesstruct radix_node * 598294706Smelifarorn_addroute(void *v_arg, void *n_arg, struct radix_head *head, 599260228Smelifaro struct radix_node treenodes[2]) 6001541Srgrimes{ 6011541Srgrimes caddr_t v = (caddr_t)v_arg, netmask = (caddr_t)n_arg; 602298075Spfg struct radix_node *t, *x = NULL, *tt; 6031541Srgrimes struct radix_node *saved_tt, *top = head->rnh_treetop; 6048152Spst short b = 0, b_leaf = 0; 6058152Spst int keyduplicated; 6068152Spst caddr_t mmask; 6071541Srgrimes struct radix_mask *m, **mp; 6081541Srgrimes 6091541Srgrimes /* 6101541Srgrimes * In dealing with non-contiguous masks, there may be 6111541Srgrimes * many different routes which have the same mask. 6121541Srgrimes * We will find it useful to have a unique pointer to 6131541Srgrimes * the mask to speed avoiding duplicate references at 6141541Srgrimes * nodes and possibly save time in calculating indices. 6151541Srgrimes */ 6161541Srgrimes if (netmask) { 617256624Smelifaro x = rn_addmask(netmask, head->rnh_masks, 0, top->rn_offset); 618256624Smelifaro if (x == NULL) 6198152Spst return (0); 62059529Swollman b_leaf = x->rn_bit; 62159529Swollman b = -1 - x->rn_bit; 6221541Srgrimes netmask = x->rn_key; 6231541Srgrimes } 6241541Srgrimes /* 6251541Srgrimes * Deal with duplicated keys: attach node to previous instance 6261541Srgrimes */ 6271541Srgrimes saved_tt = tt = rn_insert(v, head, &keyduplicated, treenodes); 6281541Srgrimes if (keyduplicated) { 6298152Spst for (t = tt; tt; t = tt, tt = tt->rn_dupedkey) { 630178167Sqingli#ifdef RADIX_MPATH 631178167Sqingli /* permit multipath, if enabled for the family */ 632178167Sqingli if (rn_mpath_capable(head) && netmask == tt->rn_mask) { 633178167Sqingli /* 634178167Sqingli * go down to the end of multipaths, so that 635178167Sqingli * new entry goes into the end of rn_dupedkey 636178167Sqingli * chain. 637178167Sqingli */ 638178167Sqingli do { 639178167Sqingli t = tt; 640178167Sqingli tt = tt->rn_dupedkey; 641178167Sqingli } while (tt && t->rn_mask == tt->rn_mask); 642178167Sqingli break; 643178167Sqingli } 644178167Sqingli#endif 6451541Srgrimes if (tt->rn_mask == netmask) 6461541Srgrimes return (0); 6471541Srgrimes if (netmask == 0 || 6488152Spst (tt->rn_mask && 64959529Swollman ((b_leaf < tt->rn_bit) /* index(netmask) > node */ 65059529Swollman || rn_refines(netmask, tt->rn_mask) 65159529Swollman || rn_lexobetter(netmask, tt->rn_mask)))) 6521541Srgrimes break; 6538152Spst } 6541541Srgrimes /* 6551541Srgrimes * If the mask is not duplicated, we wouldn't 6561541Srgrimes * find it among possible duplicate key entries 6571541Srgrimes * anyway, so the above test doesn't hurt. 6581541Srgrimes * 6591541Srgrimes * We sort the masks for a duplicated key the same way as 6601541Srgrimes * in a masklist -- most specific to least specific. 6611541Srgrimes * This may require the unfortunate nuisance of relocating 6621541Srgrimes * the head of the list. 663108268Sru * 664108268Sru * We also reverse, or doubly link the list through the 665108268Sru * parent pointer. 6661541Srgrimes */ 6678152Spst if (tt == saved_tt) { 6681541Srgrimes struct radix_node *xx = x; 6691541Srgrimes /* link in at head of list */ 6701541Srgrimes (tt = treenodes)->rn_dupedkey = t; 6711541Srgrimes tt->rn_flags = t->rn_flags; 67259529Swollman tt->rn_parent = x = t->rn_parent; 67359529Swollman t->rn_parent = tt; /* parent */ 67459529Swollman if (x->rn_left == t) 67559529Swollman x->rn_left = tt; 67659529Swollman else 67759529Swollman x->rn_right = tt; 6781541Srgrimes saved_tt = tt; x = xx; 6791541Srgrimes } else { 6801541Srgrimes (tt = treenodes)->rn_dupedkey = t->rn_dupedkey; 6811541Srgrimes t->rn_dupedkey = tt; 68259529Swollman tt->rn_parent = t; /* parent */ 6838152Spst if (tt->rn_dupedkey) /* parent */ 68459529Swollman tt->rn_dupedkey->rn_parent = tt; /* parent */ 6851541Srgrimes } 6861541Srgrimes#ifdef RN_DEBUG 6871541Srgrimes t=tt+1; tt->rn_info = rn_nodenum++; t->rn_info = rn_nodenum++; 6881541Srgrimes tt->rn_twin = t; tt->rn_ybro = rn_clist; rn_clist = tt; 6891541Srgrimes#endif 6901541Srgrimes tt->rn_key = (caddr_t) v; 69159529Swollman tt->rn_bit = -1; 6928152Spst tt->rn_flags = RNF_ACTIVE; 6931541Srgrimes } 6941541Srgrimes /* 6951541Srgrimes * Put mask in tree. 6961541Srgrimes */ 6971541Srgrimes if (netmask) { 6981541Srgrimes tt->rn_mask = netmask; 69959529Swollman tt->rn_bit = x->rn_bit; 7008152Spst tt->rn_flags |= x->rn_flags & RNF_NORMAL; 7011541Srgrimes } 70259529Swollman t = saved_tt->rn_parent; 7038152Spst if (keyduplicated) 7048152Spst goto on2; 70559529Swollman b_leaf = -1 - t->rn_bit; 70659529Swollman if (t->rn_right == saved_tt) 70759529Swollman x = t->rn_left; 70859529Swollman else 70959529Swollman x = t->rn_right; 7101541Srgrimes /* Promote general routes from below */ 71159529Swollman if (x->rn_bit < 0) { 7128152Spst for (mp = &t->rn_mklist; x; x = x->rn_dupedkey) 71359529Swollman if (x->rn_mask && (x->rn_bit >= b_leaf) && x->rn_mklist == 0) { 7148152Spst *mp = m = rn_new_radix_mask(x, 0); 7158152Spst if (m) 7168152Spst mp = &m->rm_mklist; 7171541Srgrimes } 7181541Srgrimes } else if (x->rn_mklist) { 7191541Srgrimes /* 7201541Srgrimes * Skip over masks whose index is > that of new node 7211541Srgrimes */ 7228152Spst for (mp = &x->rn_mklist; (m = *mp); mp = &m->rm_mklist) 72359529Swollman if (m->rm_bit >= b_leaf) 7241541Srgrimes break; 725298075Spfg t->rn_mklist = m; *mp = NULL; 7261541Srgrimes } 7278152Spston2: 7281541Srgrimes /* Add new route to highest possible ancestor's list */ 72959529Swollman if ((netmask == 0) || (b > t->rn_bit )) 730260228Smelifaro return (tt); /* can't lift at all */ 73159529Swollman b_leaf = tt->rn_bit; 7321541Srgrimes do { 7331541Srgrimes x = t; 73459529Swollman t = t->rn_parent; 73559529Swollman } while (b <= t->rn_bit && x != top); 7361541Srgrimes /* 7371541Srgrimes * Search through routes associated with node to 7381541Srgrimes * insert new route according to index. 7398152Spst * Need same criteria as when sorting dupedkeys to avoid 7408152Spst * double loop on deletion. 7411541Srgrimes */ 7428152Spst for (mp = &x->rn_mklist; (m = *mp); mp = &m->rm_mklist) { 74359529Swollman if (m->rm_bit < b_leaf) 7441541Srgrimes continue; 74559529Swollman if (m->rm_bit > b_leaf) 7461541Srgrimes break; 7478152Spst if (m->rm_flags & RNF_NORMAL) { 7488152Spst mmask = m->rm_leaf->rn_mask; 7498152Spst if (tt->rn_flags & RNF_NORMAL) { 750204902Sqingli#if !defined(RADIX_MPATH) 75159529Swollman log(LOG_ERR, 75295023Ssuz "Non-unique normal route, mask not entered\n"); 753204902Sqingli#endif 754260228Smelifaro return (tt); 7558152Spst } 7568152Spst } else 7578152Spst mmask = m->rm_mask; 7588152Spst if (mmask == netmask) { 7591541Srgrimes m->rm_refs++; 7601541Srgrimes tt->rn_mklist = m; 761260228Smelifaro return (tt); 7621541Srgrimes } 76359529Swollman if (rn_refines(netmask, mmask) 76459529Swollman || rn_lexobetter(netmask, mmask)) 7651541Srgrimes break; 7661541Srgrimes } 7678152Spst *mp = rn_new_radix_mask(tt, *mp); 768260228Smelifaro return (tt); 7691541Srgrimes} 7701541Srgrimes 77131390Sbdestruct radix_node * 772294706Smelifarorn_delete(void *v_arg, void *netmask_arg, struct radix_head *head) 7731541Srgrimes{ 774260228Smelifaro struct radix_node *t, *p, *x, *tt; 7751541Srgrimes struct radix_mask *m, *saved_m, **mp; 7761541Srgrimes struct radix_node *dupedkey, *saved_tt, *top; 7771541Srgrimes caddr_t v, netmask; 7781541Srgrimes int b, head_off, vlen; 7791541Srgrimes 7801541Srgrimes v = v_arg; 7811541Srgrimes netmask = netmask_arg; 7821541Srgrimes x = head->rnh_treetop; 7831541Srgrimes tt = rn_search(v, x); 78459529Swollman head_off = x->rn_offset; 785128525Sluigi vlen = LEN(v); 7861541Srgrimes saved_tt = tt; 7871541Srgrimes top = x; 788298075Spfg if (tt == NULL || 789128401Sluigi bcmp(v + head_off, tt->rn_key + head_off, vlen - head_off)) 7901541Srgrimes return (0); 7911541Srgrimes /* 7921541Srgrimes * Delete our route from mask lists. 7931541Srgrimes */ 7948152Spst if (netmask) { 795256624Smelifaro x = rn_addmask(netmask, head->rnh_masks, 1, head_off); 796256624Smelifaro if (x == NULL) 7978152Spst return (0); 7988152Spst netmask = x->rn_key; 7991541Srgrimes while (tt->rn_mask != netmask) 800298075Spfg if ((tt = tt->rn_dupedkey) == NULL) 8011541Srgrimes return (0); 8021541Srgrimes } 803298075Spfg if (tt->rn_mask == 0 || (saved_m = m = tt->rn_mklist) == NULL) 8041541Srgrimes goto on1; 8058152Spst if (tt->rn_flags & RNF_NORMAL) { 8068152Spst if (m->rm_leaf != tt || m->rm_refs > 0) { 8078152Spst log(LOG_ERR, "rn_delete: inconsistent annotation\n"); 808260228Smelifaro return (0); /* dangling ref could cause disaster */ 8098152Spst } 8108876Srgrimes } else { 8118152Spst if (m->rm_mask != tt->rn_mask) { 8128152Spst log(LOG_ERR, "rn_delete: inconsistent annotation\n"); 8138152Spst goto on1; 8148152Spst } 8158152Spst if (--m->rm_refs >= 0) 8168152Spst goto on1; 8171541Srgrimes } 81859529Swollman b = -1 - tt->rn_bit; 81959529Swollman t = saved_tt->rn_parent; 82059529Swollman if (b > t->rn_bit) 8211541Srgrimes goto on1; /* Wasn't lifted at all */ 8221541Srgrimes do { 8231541Srgrimes x = t; 82459529Swollman t = t->rn_parent; 82559529Swollman } while (b <= t->rn_bit && x != top); 8268152Spst for (mp = &x->rn_mklist; (m = *mp); mp = &m->rm_mklist) 8271541Srgrimes if (m == saved_m) { 8281541Srgrimes *mp = m->rm_mklist; 829286057Sloos R_Free(m); 8301541Srgrimes break; 8311541Srgrimes } 832298075Spfg if (m == NULL) { 8338152Spst log(LOG_ERR, "rn_delete: couldn't find our annotation\n"); 8348152Spst if (tt->rn_flags & RNF_NORMAL) 8358152Spst return (0); /* Dangling ref to us */ 8368152Spst } 8371541Srgrimeson1: 8381541Srgrimes /* 8391541Srgrimes * Eliminate us from tree 8401541Srgrimes */ 8411541Srgrimes if (tt->rn_flags & RNF_ROOT) 8421541Srgrimes return (0); 8431541Srgrimes#ifdef RN_DEBUG 8441541Srgrimes /* Get us out of the creation list */ 8451541Srgrimes for (t = rn_clist; t && t->rn_ybro != tt; t = t->rn_ybro) {} 8461541Srgrimes if (t) t->rn_ybro = tt->rn_ybro; 8471541Srgrimes#endif 84859529Swollman t = tt->rn_parent; 8498152Spst dupedkey = saved_tt->rn_dupedkey; 8501541Srgrimes if (dupedkey) { 8518152Spst /* 852108268Sru * Here, tt is the deletion target and 853108268Sru * saved_tt is the head of the dupekey chain. 8548152Spst */ 8551541Srgrimes if (tt == saved_tt) { 8568152Spst /* remove from head of chain */ 85759529Swollman x = dupedkey; x->rn_parent = t; 85859529Swollman if (t->rn_left == tt) 85959529Swollman t->rn_left = x; 86059529Swollman else 86159529Swollman t->rn_right = x; 8621541Srgrimes } else { 8638152Spst /* find node in front of tt on the chain */ 8641541Srgrimes for (x = p = saved_tt; p && p->rn_dupedkey != tt;) 8651541Srgrimes p = p->rn_dupedkey; 8668152Spst if (p) { 8678152Spst p->rn_dupedkey = tt->rn_dupedkey; 86859529Swollman if (tt->rn_dupedkey) /* parent */ 86959529Swollman tt->rn_dupedkey->rn_parent = p; 87059529Swollman /* parent */ 8718152Spst } else log(LOG_ERR, "rn_delete: couldn't find us\n"); 8721541Srgrimes } 8731541Srgrimes t = tt + 1; 8741541Srgrimes if (t->rn_flags & RNF_ACTIVE) { 8751541Srgrimes#ifndef RN_DEBUG 87659529Swollman *++x = *t; 87759529Swollman p = t->rn_parent; 8781541Srgrimes#else 87959529Swollman b = t->rn_info; 88059529Swollman *++x = *t; 88159529Swollman t->rn_info = b; 88259529Swollman p = t->rn_parent; 8831541Srgrimes#endif 88459529Swollman if (p->rn_left == t) 88559529Swollman p->rn_left = x; 88659529Swollman else 88759529Swollman p->rn_right = x; 88859529Swollman x->rn_left->rn_parent = x; 88959529Swollman x->rn_right->rn_parent = x; 8901541Srgrimes } 8911541Srgrimes goto out; 8921541Srgrimes } 89359529Swollman if (t->rn_left == tt) 89459529Swollman x = t->rn_right; 89559529Swollman else 89659529Swollman x = t->rn_left; 89759529Swollman p = t->rn_parent; 89859529Swollman if (p->rn_right == t) 89959529Swollman p->rn_right = x; 90059529Swollman else 90159529Swollman p->rn_left = x; 90259529Swollman x->rn_parent = p; 9031541Srgrimes /* 9041541Srgrimes * Demote routes attached to us. 9051541Srgrimes */ 9061541Srgrimes if (t->rn_mklist) { 90759529Swollman if (x->rn_bit >= 0) { 9088152Spst for (mp = &x->rn_mklist; (m = *mp);) 9091541Srgrimes mp = &m->rm_mklist; 9101541Srgrimes *mp = t->rn_mklist; 9111541Srgrimes } else { 9128152Spst /* If there are any key,mask pairs in a sibling 9138152Spst duped-key chain, some subset will appear sorted 9148152Spst in the same order attached to our mklist */ 9158152Spst for (m = t->rn_mklist; m && x; x = x->rn_dupedkey) 9168152Spst if (m == x->rn_mklist) { 9178152Spst struct radix_mask *mm = m->rm_mklist; 9181541Srgrimes x->rn_mklist = 0; 9198152Spst if (--(m->rm_refs) < 0) 920286057Sloos R_Free(m); 9218152Spst m = mm; 9228152Spst } 9238152Spst if (m) 92437560Sbde log(LOG_ERR, 92537560Sbde "rn_delete: Orphaned Mask %p at %p\n", 926204582Sluigi m, x); 9271541Srgrimes } 9281541Srgrimes } 9291541Srgrimes /* 9301541Srgrimes * We may be holding an active internal node in the tree. 9311541Srgrimes */ 9321541Srgrimes x = tt + 1; 9331541Srgrimes if (t != x) { 9341541Srgrimes#ifndef RN_DEBUG 9351541Srgrimes *t = *x; 9361541Srgrimes#else 93759529Swollman b = t->rn_info; 93859529Swollman *t = *x; 93959529Swollman t->rn_info = b; 9401541Srgrimes#endif 94159529Swollman t->rn_left->rn_parent = t; 94259529Swollman t->rn_right->rn_parent = t; 94359529Swollman p = x->rn_parent; 94459529Swollman if (p->rn_left == x) 94559529Swollman p->rn_left = t; 94659529Swollman else 94759529Swollman p->rn_right = t; 9481541Srgrimes } 9491541Srgrimesout: 9501541Srgrimes tt->rn_flags &= ~RNF_ACTIVE; 9511541Srgrimes tt[1].rn_flags &= ~RNF_ACTIVE; 9521541Srgrimes return (tt); 9531541Srgrimes} 9541541Srgrimes 9557197Swollman/* 9567197Swollman * This is the same as rn_walktree() except for the parameters and the 9577197Swollman * exit. 9587197Swollman */ 959294706Smelifaroint 960294706Smelifarorn_walktree_from(struct radix_head *h, void *a, void *m, 961260228Smelifaro walktree_f_t *f, void *w) 9627197Swollman{ 9637197Swollman int error; 9647197Swollman struct radix_node *base, *next; 9657197Swollman u_char *xa = (u_char *)a; 9667197Swollman u_char *xm = (u_char *)m; 967260228Smelifaro struct radix_node *rn, *last = NULL; /* shut up gcc */ 9687197Swollman int stopping = 0; 9697197Swollman int lastb; 9707197Swollman 971265196Smelifaro KASSERT(m != NULL, ("%s: mask needs to be specified", __func__)); 972265196Smelifaro 9737197Swollman /* 974128525Sluigi * rn_search_m is sort-of-open-coded here. We cannot use the 975128525Sluigi * function because we need to keep track of the last node seen. 9767197Swollman */ 9777279Swollman /* printf("about to search\n"); */ 97859529Swollman for (rn = h->rnh_treetop; rn->rn_bit >= 0; ) { 9797197Swollman last = rn; 98059529Swollman /* printf("rn_bit %d, rn_bmask %x, xm[rn_offset] %x\n", 98159529Swollman rn->rn_bit, rn->rn_bmask, xm[rn->rn_offset]); */ 98259529Swollman if (!(rn->rn_bmask & xm[rn->rn_offset])) { 9837197Swollman break; 9847279Swollman } 98559529Swollman if (rn->rn_bmask & xa[rn->rn_offset]) { 98659529Swollman rn = rn->rn_right; 9877197Swollman } else { 98859529Swollman rn = rn->rn_left; 9897197Swollman } 9907197Swollman } 9917279Swollman /* printf("done searching\n"); */ 9927197Swollman 9937197Swollman /* 9947197Swollman * Two cases: either we stepped off the end of our mask, 9957197Swollman * in which case last == rn, or we reached a leaf, in which 996265196Smelifaro * case we want to start from the leaf. 9977197Swollman */ 998265196Smelifaro if (rn->rn_bit >= 0) 999265196Smelifaro rn = last; 1000265196Smelifaro lastb = last->rn_bit; 10017197Swollman 10027279Swollman /* printf("rn %p, lastb %d\n", rn, lastb);*/ 10037279Swollman 10047197Swollman /* 10057197Swollman * This gets complicated because we may delete the node 10067197Swollman * while applying the function f to it, so we need to calculate 10077197Swollman * the successor node in advance. 10087197Swollman */ 100959529Swollman while (rn->rn_bit >= 0) 101059529Swollman rn = rn->rn_left; 10117197Swollman 10127197Swollman while (!stopping) { 101359529Swollman /* printf("node %p (%d)\n", rn, rn->rn_bit); */ 10147197Swollman base = rn; 10157197Swollman /* If at right child go back up, otherwise, go right */ 101659529Swollman while (rn->rn_parent->rn_right == rn 101759529Swollman && !(rn->rn_flags & RNF_ROOT)) { 101859529Swollman rn = rn->rn_parent; 10197197Swollman 10208876Srgrimes /* if went up beyond last, stop */ 1021155442Sqingli if (rn->rn_bit <= lastb) { 10227197Swollman stopping = 1; 10237279Swollman /* printf("up too far\n"); */ 1024128525Sluigi /* 1025128525Sluigi * XXX we should jump to the 'Process leaves' 1026128525Sluigi * part, because the values of 'rn' and 'next' 1027128525Sluigi * we compute will not be used. Not a big deal 1028128525Sluigi * because this loop will terminate, but it is 1029128525Sluigi * inefficient and hard to understand! 1030128525Sluigi */ 10317197Swollman } 10327197Swollman } 1033155442Sqingli 1034155442Sqingli /* 1035155442Sqingli * At the top of the tree, no need to traverse the right 1036155442Sqingli * half, prevent the traversal of the entire tree in the 1037155442Sqingli * case of default route. 1038155442Sqingli */ 1039155442Sqingli if (rn->rn_parent->rn_flags & RNF_ROOT) 1040155442Sqingli stopping = 1; 10417197Swollman 10427197Swollman /* Find the next *leaf* since next node might vanish, too */ 104359529Swollman for (rn = rn->rn_parent->rn_right; rn->rn_bit >= 0;) 104459529Swollman rn = rn->rn_left; 10457197Swollman next = rn; 10467197Swollman /* Process leaves */ 1047298075Spfg while ((rn = base) != NULL) { 10487197Swollman base = rn->rn_dupedkey; 10497279Swollman /* printf("leaf %p\n", rn); */ 10508876Srgrimes if (!(rn->rn_flags & RNF_ROOT) 10517197Swollman && (error = (*f)(rn, w))) 10527197Swollman return (error); 10537197Swollman } 10547197Swollman rn = next; 10557279Swollman 10567279Swollman if (rn->rn_flags & RNF_ROOT) { 10577279Swollman /* printf("root, stopping"); */ 10587279Swollman stopping = 1; 10597279Swollman } 10607279Swollman 10617197Swollman } 1062260228Smelifaro return (0); 10637197Swollman} 10647197Swollman 1065294706Smelifaroint 1066294706Smelifarorn_walktree(struct radix_head *h, walktree_f_t *f, void *w) 10671541Srgrimes{ 10681541Srgrimes int error; 10691541Srgrimes struct radix_node *base, *next; 1070260228Smelifaro struct radix_node *rn = h->rnh_treetop; 10711541Srgrimes /* 10721541Srgrimes * This gets complicated because we may delete the node 10731541Srgrimes * while applying the function f to it, so we need to calculate 10741541Srgrimes * the successor node in advance. 10751541Srgrimes */ 1076186166Skmacy 10771541Srgrimes /* First time through node, go left */ 107859529Swollman while (rn->rn_bit >= 0) 107959529Swollman rn = rn->rn_left; 10801541Srgrimes for (;;) { 10811541Srgrimes base = rn; 10821541Srgrimes /* If at right child go back up, otherwise, go right */ 108359529Swollman while (rn->rn_parent->rn_right == rn 108459529Swollman && (rn->rn_flags & RNF_ROOT) == 0) 108559529Swollman rn = rn->rn_parent; 10861541Srgrimes /* Find the next *leaf* since next node might vanish, too */ 108759529Swollman for (rn = rn->rn_parent->rn_right; rn->rn_bit >= 0;) 108859529Swollman rn = rn->rn_left; 10891541Srgrimes next = rn; 10901541Srgrimes /* Process leaves */ 10918152Spst while ((rn = base)) { 10921541Srgrimes base = rn->rn_dupedkey; 109359529Swollman if (!(rn->rn_flags & RNF_ROOT) 109459529Swollman && (error = (*f)(rn, w))) 10951541Srgrimes return (error); 10961541Srgrimes } 10971541Srgrimes rn = next; 10981541Srgrimes if (rn->rn_flags & RNF_ROOT) 10991541Srgrimes return (0); 11001541Srgrimes } 11011541Srgrimes /* NOTREACHED */ 11021541Srgrimes} 11031541Srgrimes 1104128525Sluigi/* 1105294706Smelifaro * Initialize an empty tree. This has 3 nodes, which are passed 1106294706Smelifaro * via base_nodes (in the order <left,root,right>) and are 1107128525Sluigi * marked RNF_ROOT so they cannot be freed. 1108128525Sluigi * The leaves have all-zero and all-one keys, with significant 1109128525Sluigi * bits starting at 'off'. 1110128525Sluigi */ 1111294706Smelifarovoid 1112294706Smelifarorn_inithead_internal(struct radix_head *rh, struct radix_node *base_nodes, int off) 11131541Srgrimes{ 1114260228Smelifaro struct radix_node *t, *tt, *ttt; 1115294706Smelifaro 1116294706Smelifaro t = rn_newpair(rn_zeros, off, base_nodes); 1117294706Smelifaro ttt = base_nodes + 2; 111859529Swollman t->rn_right = ttt; 111959529Swollman t->rn_parent = t; 1120294706Smelifaro tt = t->rn_left; /* ... which in turn is base_nodes */ 11211541Srgrimes tt->rn_flags = t->rn_flags = RNF_ROOT | RNF_ACTIVE; 112259529Swollman tt->rn_bit = -1 - off; 11231541Srgrimes *ttt = *tt; 11241541Srgrimes ttt->rn_key = rn_ones; 1125294706Smelifaro 1126294706Smelifaro rh->rnh_treetop = t; 11271541Srgrimes} 11281541Srgrimes 1129256624Smelifarostatic void 1130294706Smelifarorn_detachhead_internal(struct radix_head *head) 1131204808Sbz{ 1132204808Sbz 1133294706Smelifaro KASSERT((head != NULL), 1134204808Sbz ("%s: head already freed", __func__)); 1135204808Sbz 1136204808Sbz /* Free <left,root,right> nodes. */ 1137294706Smelifaro R_Free(head); 1138204808Sbz} 1139204808Sbz 1140294706Smelifaro/* Functions used by 'struct radix_node_head' users */ 1141294706Smelifaro 1142256624Smelifaroint 1143256624Smelifarorn_inithead(void **head, int off) 11441541Srgrimes{ 1145256624Smelifaro struct radix_node_head *rnh; 1146294706Smelifaro struct radix_mask_head *rmh; 11471541Srgrimes 1148294706Smelifaro rnh = *head; 1149294706Smelifaro rmh = NULL; 1150294706Smelifaro 1151256624Smelifaro if (*head != NULL) 1152256624Smelifaro return (1); 1153256624Smelifaro 1154294706Smelifaro R_Zalloc(rnh, struct radix_node_head *, sizeof (*rnh)); 1155294706Smelifaro R_Zalloc(rmh, struct radix_mask_head *, sizeof (*rmh)); 1156294706Smelifaro if (rnh == NULL || rmh == NULL) { 1157294706Smelifaro if (rnh != NULL) 1158294706Smelifaro R_Free(rnh); 1159298329Scem if (rmh != NULL) 1160298329Scem R_Free(rmh); 1161256624Smelifaro return (0); 1162294706Smelifaro } 1163256624Smelifaro 1164294706Smelifaro /* Init trees */ 1165294706Smelifaro rn_inithead_internal(&rnh->rh, rnh->rnh_nodes, off); 1166294706Smelifaro rn_inithead_internal(&rmh->head, rmh->mask_nodes, 0); 1167294706Smelifaro *head = rnh; 1168294706Smelifaro rnh->rh.rnh_masks = rmh; 1169256624Smelifaro 1170294706Smelifaro /* Finally, set base callbacks */ 1171294706Smelifaro rnh->rnh_addaddr = rn_addroute; 1172294706Smelifaro rnh->rnh_deladdr = rn_delete; 1173294706Smelifaro rnh->rnh_matchaddr = rn_match; 1174294706Smelifaro rnh->rnh_lookup = rn_lookup; 1175294706Smelifaro rnh->rnh_walktree = rn_walktree; 1176294706Smelifaro rnh->rnh_walktree_from = rn_walktree_from; 1177256624Smelifaro 1178256624Smelifaro return (1); 11791541Srgrimes} 1180256624Smelifaro 1181272385Smelifarostatic int 1182272385Smelifarorn_freeentry(struct radix_node *rn, void *arg) 1183272385Smelifaro{ 1184294706Smelifaro struct radix_head * const rnh = arg; 1185272385Smelifaro struct radix_node *x; 1186272385Smelifaro 1187272385Smelifaro x = (struct radix_node *)rn_delete(rn + 2, NULL, rnh); 1188272385Smelifaro if (x != NULL) 1189286057Sloos R_Free(x); 1190272385Smelifaro return (0); 1191272385Smelifaro} 1192272385Smelifaro 1193256624Smelifaroint 1194256624Smelifarorn_detachhead(void **head) 1195256624Smelifaro{ 1196256624Smelifaro struct radix_node_head *rnh; 1197256624Smelifaro 1198256624Smelifaro KASSERT((head != NULL && *head != NULL), 1199256624Smelifaro ("%s: head already freed", __func__)); 1200256624Smelifaro 1201294706Smelifaro rnh = (struct radix_node_head *)(*head); 1202256624Smelifaro 1203294706Smelifaro rn_walktree(&rnh->rh.rnh_masks->head, rn_freeentry, rnh->rh.rnh_masks); 1204294706Smelifaro rn_detachhead_internal(&rnh->rh.rnh_masks->head); 1205294706Smelifaro rn_detachhead_internal(&rnh->rh); 1206294706Smelifaro 1207294706Smelifaro *head = NULL; 1208294706Smelifaro 1209256624Smelifaro return (1); 1210256624Smelifaro} 1211256624Smelifaro 1212