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 5993084Sbdestatic int rn_walktree_from(struct radix_node_head *h, void *a, void *m, 6093084Sbde walktree_f_t *f, void *w); 6192725Salfredstatic int rn_walktree(struct radix_node_head *, walktree_f_t *, void *); 6212820Sphkstatic struct radix_node 6392725Salfred *rn_insert(void *, struct radix_node_head *, int *, 6493084Sbde struct radix_node [2]), 6592725Salfred *rn_newpair(void *, int, struct radix_node[2]), 6692725Salfred *rn_search(void *, struct radix_node *), 6792725Salfred *rn_search_m(void *, struct radix_node *, void *); 6812579Sbde 69257330Smelifarostatic void rn_detachhead_internal(void **head); 70257330Smelifarostatic int rn_inithead_internal(void **head, int off); 71257330Smelifaro 72257330Smelifaro#define RADIX_MAX_KEY_LEN 32 73257330Smelifaro 74257330Smelifarostatic char rn_zeros[RADIX_MAX_KEY_LEN]; 75257330Smelifarostatic char rn_ones[RADIX_MAX_KEY_LEN] = { 76257330Smelifaro -1, -1, -1, -1, -1, -1, -1, -1, 77257330Smelifaro -1, -1, -1, -1, -1, -1, -1, -1, 78257330Smelifaro -1, -1, -1, -1, -1, -1, -1, -1, 79257330Smelifaro -1, -1, -1, -1, -1, -1, -1, -1, 80257330Smelifaro}; 81257330Smelifaro 82128433Sluigi/* 83257330Smelifaro * XXX: Compat stuff for old rn_addmask() users 84128433Sluigi */ 85257330Smelifarostatic struct radix_node_head *mask_rnhead_compat; 86257330Smelifaro#ifdef _KERNEL 87257330Smelifarostatic struct mtx mask_mtx; 88257330Smelifaro#endif 891541Srgrimes 90128401Sluigi 9192725Salfredstatic int rn_lexobetter(void *m_arg, void *n_arg); 9212579Sbdestatic struct radix_mask * 9392725Salfred rn_new_radix_mask(struct radix_node *tt, 9493084Sbde struct radix_mask *next); 95108273Srustatic int rn_satisfies_leaf(char *trial, struct radix_node *leaf, 9693084Sbde int skip); 9712579Sbde 981541Srgrimes/* 991541Srgrimes * The data structure for the keys is a radix tree with one way 10059529Swollman * branching removed. The index rn_bit at an internal node n represents a bit 1011541Srgrimes * position to be tested. The tree is arranged so that all descendants 10259529Swollman * of a node n have keys whose bits all agree up to position rn_bit - 1. 10359529Swollman * (We say the index of n is rn_bit.) 1041541Srgrimes * 10559529Swollman * There is at least one descendant which has a one bit at position rn_bit, 1061541Srgrimes * and at least one with a zero there. 1071541Srgrimes * 1081541Srgrimes * A route is determined by a pair of key and mask. We require that the 1091541Srgrimes * bit-wise logical and of the key and mask to be the key. 1101541Srgrimes * We define the index of a route to associated with the mask to be 1111541Srgrimes * the first bit number in the mask where 0 occurs (with bit number 0 1121541Srgrimes * representing the highest order bit). 1138876Srgrimes * 1141541Srgrimes * We say a mask is normal if every bit is 0, past the index of the mask. 11559529Swollman * If a node n has a descendant (k, m) with index(m) == index(n) == rn_bit, 1161541Srgrimes * and m is a normal mask, then the route applies to every descendant of n. 11759529Swollman * If the index(m) < rn_bit, this implies the trailing last few bits of k 1181541Srgrimes * before bit b are all 0, (and hence consequently true of every descendant 1191541Srgrimes * of n), so the route applies to all descendants of the node as well. 1208876Srgrimes * 1218152Spst * Similar logic shows that a non-normal mask m such that 1221541Srgrimes * index(m) <= index(n) could potentially apply to many children of n. 1231541Srgrimes * Thus, for each non-host route, we attach its mask to a list at an internal 1248876Srgrimes * node as high in the tree as we can go. 1258152Spst * 1268152Spst * The present version of the code makes use of normal routes in short- 1278152Spst * circuiting an explict mask and compare operation when testing whether 1288152Spst * a key satisfies a normal route, and also in remembering the unique leaf 1298152Spst * that governs a subtree. 1301541Srgrimes */ 1311541Srgrimes 132128525Sluigi/* 133128525Sluigi * Most of the functions in this code assume that the key/mask arguments 134128525Sluigi * are sockaddr-like structures, where the first byte is an u_char 135128525Sluigi * indicating the size of the entire structure. 136128525Sluigi * 137128525Sluigi * To make the assumption more explicit, we use the LEN() macro to access 138128525Sluigi * this field. It is safe to pass an expression with side effects 139128525Sluigi * to LEN() as the argument is evaluated only once. 140200354Sluigi * We cast the result to int as this is the dominant usage. 141128525Sluigi */ 142200354Sluigi#define LEN(x) ( (int) (*(const u_char *)(x)) ) 143128525Sluigi 144128525Sluigi/* 145128525Sluigi * XXX THIS NEEDS TO BE FIXED 146128525Sluigi * In the code, pointers to keys and masks are passed as either 147128525Sluigi * 'void *' (because callers use to pass pointers of various kinds), or 148128525Sluigi * 'caddr_t' (which is fine for pointer arithmetics, but not very 149128525Sluigi * clean when you dereference it to access data). Furthermore, caddr_t 150128525Sluigi * is really 'char *', while the natural type to operate on keys and 151128525Sluigi * masks would be 'u_char'. This mismatch require a lot of casts and 152128525Sluigi * intermediate variables to adapt types that clutter the code. 153128525Sluigi */ 154128525Sluigi 155128525Sluigi/* 156128525Sluigi * Search a node in the tree matching the key. 157128525Sluigi */ 15812820Sphkstatic struct radix_node * 159265708Smelifarorn_search(void *v_arg, struct radix_node *head) 1601541Srgrimes{ 161265708Smelifaro struct radix_node *x; 162265708Smelifaro caddr_t v; 1631541Srgrimes 16459529Swollman for (x = head, v = v_arg; x->rn_bit >= 0;) { 16559529Swollman if (x->rn_bmask & v[x->rn_offset]) 16659529Swollman x = x->rn_right; 1671541Srgrimes else 16859529Swollman x = x->rn_left; 1691541Srgrimes } 1701541Srgrimes return (x); 17131390Sbde} 1721541Srgrimes 173128525Sluigi/* 174128525Sluigi * Same as above, but with an additional mask. 175128525Sluigi * XXX note this function is used only once. 176128525Sluigi */ 17712820Sphkstatic struct radix_node * 178265708Smelifarorn_search_m(void *v_arg, struct radix_node *head, void *m_arg) 1791541Srgrimes{ 180265708Smelifaro struct radix_node *x; 181265708Smelifaro caddr_t v = v_arg, m = m_arg; 1821541Srgrimes 18359529Swollman for (x = head; x->rn_bit >= 0;) { 18459529Swollman if ((x->rn_bmask & m[x->rn_offset]) && 18559529Swollman (x->rn_bmask & v[x->rn_offset])) 18659529Swollman x = x->rn_right; 1871541Srgrimes else 18859529Swollman x = x->rn_left; 1891541Srgrimes } 190265708Smelifaro return (x); 19131390Sbde} 1921541Srgrimes 1931541Srgrimesint 194265708Smelifarorn_refines(void *m_arg, void *n_arg) 1951541Srgrimes{ 196265708Smelifaro caddr_t m = m_arg, n = n_arg; 197265708Smelifaro caddr_t lim, lim2 = lim = n + LEN(n); 198200354Sluigi int longer = LEN(n++) - LEN(m++); 1991541Srgrimes int masks_are_equal = 1; 2001541Srgrimes 2011541Srgrimes if (longer > 0) 2021541Srgrimes lim -= longer; 2031541Srgrimes while (n < lim) { 2041541Srgrimes if (*n & ~(*m)) 205265708Smelifaro return (0); 2061541Srgrimes if (*n++ != *m++) 2071541Srgrimes masks_are_equal = 0; 2081541Srgrimes } 2091541Srgrimes while (n < lim2) 2101541Srgrimes if (*n++) 211265708Smelifaro return (0); 2121541Srgrimes if (masks_are_equal && (longer < 0)) 2131541Srgrimes for (lim2 = m - longer; m < lim2; ) 2141541Srgrimes if (*m++) 215265708Smelifaro return (1); 2161541Srgrimes return (!masks_are_equal); 2171541Srgrimes} 2181541Srgrimes 219265708Smelifaro/* 220265708Smelifaro * Search for exact match in given @head. 221265708Smelifaro * Assume host bits are cleared in @v_arg if @m_arg is not NULL 222265708Smelifaro * Note that prefixes with /32 or /128 masks are treated differently 223265708Smelifaro * from host routes. 224265708Smelifaro */ 2258152Spststruct radix_node * 226265708Smelifarorn_lookup(void *v_arg, void *m_arg, struct radix_node_head *head) 2278152Spst{ 228265708Smelifaro struct radix_node *x; 229265708Smelifaro caddr_t netmask; 2301541Srgrimes 231265708Smelifaro if (m_arg != NULL) { 232265708Smelifaro /* 233265708Smelifaro * Most common case: search exact prefix/mask 234265708Smelifaro */ 235257330Smelifaro x = rn_addmask_r(m_arg, head->rnh_masks, 1, 236257330Smelifaro head->rnh_treetop->rn_offset); 237265708Smelifaro if (x == NULL) 238265708Smelifaro return (NULL); 2398152Spst netmask = x->rn_key; 240265708Smelifaro 241265708Smelifaro x = rn_match(v_arg, head); 242265708Smelifaro 243265708Smelifaro while (x != NULL && x->rn_mask != netmask) 2448152Spst x = x->rn_dupedkey; 245265708Smelifaro 246265708Smelifaro return (x); 2478152Spst } 248265708Smelifaro 249265708Smelifaro /* 250265708Smelifaro * Search for host address. 251265708Smelifaro */ 252265708Smelifaro if ((x = rn_match(v_arg, head)) == NULL) 253265708Smelifaro return (NULL); 254265708Smelifaro 255265708Smelifaro /* Check if found key is the same */ 256265708Smelifaro if (LEN(x->rn_key) != LEN(v_arg) || bcmp(x->rn_key, v_arg, LEN(v_arg))) 257265708Smelifaro return (NULL); 258265708Smelifaro 259265708Smelifaro /* Check if this is not host route */ 260265708Smelifaro if (x->rn_mask != NULL) 261265708Smelifaro return (NULL); 262265708Smelifaro 263265708Smelifaro return (x); 2648152Spst} 2658152Spst 2668152Spststatic int 267265708Smelifarorn_satisfies_leaf(char *trial, struct radix_node *leaf, int skip) 2688152Spst{ 269265708Smelifaro char *cp = trial, *cp2 = leaf->rn_key, *cp3 = leaf->rn_mask; 2708152Spst char *cplim; 271128525Sluigi int length = min(LEN(cp), LEN(cp2)); 2728152Spst 273200354Sluigi if (cp3 == NULL) 2748152Spst cp3 = rn_ones; 2758152Spst else 276200354Sluigi length = min(length, LEN(cp3)); 2778152Spst cplim = cp + length; cp3 += skip; cp2 += skip; 2788152Spst for (cp += skip; cp < cplim; cp++, cp2++, cp3++) 2798152Spst if ((*cp ^ *cp2) & *cp3) 280265708Smelifaro return (0); 281265708Smelifaro return (1); 2828152Spst} 2838152Spst 284265708Smelifaro/* 285265708Smelifaro * Search for longest-prefix match in given @head 286265708Smelifaro */ 2871541Srgrimesstruct radix_node * 288265708Smelifarorn_match(void *v_arg, struct radix_node_head *head) 2891541Srgrimes{ 2901541Srgrimes caddr_t v = v_arg; 291265708Smelifaro struct radix_node *t = head->rnh_treetop, *x; 292265708Smelifaro caddr_t cp = v, cp2; 2938152Spst caddr_t cplim; 2941541Srgrimes struct radix_node *saved_t, *top = t; 295128525Sluigi int off = t->rn_offset, vlen = LEN(cp), matched_off; 296265708Smelifaro int test, b, rn_bit; 2971541Srgrimes 2981541Srgrimes /* 2991541Srgrimes * Open code rn_search(v, top) to avoid overhead of extra 3001541Srgrimes * subroutine call. 3011541Srgrimes */ 30259529Swollman for (; t->rn_bit >= 0; ) { 30359529Swollman if (t->rn_bmask & cp[t->rn_offset]) 30459529Swollman t = t->rn_right; 3051541Srgrimes else 30659529Swollman t = t->rn_left; 3071541Srgrimes } 3081541Srgrimes /* 3091541Srgrimes * See if we match exactly as a host destination 3108152Spst * or at least learn how many bits match, for normal mask finesse. 3118152Spst * 3128152Spst * It doesn't hurt us to limit how many bytes to check 3138152Spst * to the length of the mask, since if it matches we had a genuine 3148152Spst * match and the leaf we have is the most specific one anyway; 3158152Spst * if it didn't match with a shorter length it would fail 3168152Spst * with a long one. This wins big for class B&C netmasks which 3178152Spst * are probably the most common case... 3181541Srgrimes */ 3198152Spst if (t->rn_mask) 3208152Spst vlen = *(u_char *)t->rn_mask; 3211541Srgrimes cp += off; cp2 = t->rn_key + off; cplim = v + vlen; 3221541Srgrimes for (; cp < cplim; cp++, cp2++) 3231541Srgrimes if (*cp != *cp2) 3241541Srgrimes goto on1; 3251541Srgrimes /* 3261541Srgrimes * This extra grot is in case we are explicitly asked 3271541Srgrimes * to look up the default. Ugh! 32848215Spb * 32948215Spb * Never return the root node itself, it seems to cause a 33048215Spb * lot of confusion. 3311541Srgrimes */ 33248215Spb if (t->rn_flags & RNF_ROOT) 3331541Srgrimes t = t->rn_dupedkey; 334265708Smelifaro return (t); 3351541Srgrimeson1: 3368152Spst test = (*cp ^ *cp2) & 0xff; /* find first bit that differs */ 3378152Spst for (b = 7; (test >>= 1) > 0;) 3388152Spst b--; 3391541Srgrimes matched_off = cp - v; 3408152Spst b += matched_off << 3; 34159529Swollman rn_bit = -1 - b; 3428152Spst /* 3438152Spst * If there is a host route in a duped-key chain, it will be first. 3448152Spst */ 3458152Spst if ((saved_t = t)->rn_mask == 0) 3468152Spst t = t->rn_dupedkey; 3478152Spst for (; t; t = t->rn_dupedkey) 3481541Srgrimes /* 3498152Spst * Even if we don't match exactly as a host, 3501541Srgrimes * we may match if the leaf we wound up at is 3511541Srgrimes * a route to a net. 3521541Srgrimes */ 3538152Spst if (t->rn_flags & RNF_NORMAL) { 35459529Swollman if (rn_bit <= t->rn_bit) 355265708Smelifaro return (t); 356108273Sru } else if (rn_satisfies_leaf(v, t, matched_off)) 357265708Smelifaro return (t); 3581541Srgrimes t = saved_t; 3591541Srgrimes /* start searching up the tree */ 3601541Srgrimes do { 361265708Smelifaro struct radix_mask *m; 36259529Swollman t = t->rn_parent; 3633443Sphk m = t->rn_mklist; 36459529Swollman /* 36559529Swollman * If non-contiguous masks ever become important 36659529Swollman * we can restore the masking and open coding of 36759529Swollman * the search and satisfaction test and put the 36859529Swollman * calculation of "off" back before the "do". 36959529Swollman */ 37059529Swollman while (m) { 37159529Swollman if (m->rm_flags & RNF_NORMAL) { 37259529Swollman if (rn_bit <= m->rm_bit) 37359529Swollman return (m->rm_leaf); 37459529Swollman } else { 37559529Swollman off = min(t->rn_offset, matched_off); 37659529Swollman x = rn_search_m(v, t, m->rm_mask); 37759529Swollman while (x && x->rn_mask != m->rm_mask) 37859529Swollman x = x->rn_dupedkey; 379108273Sru if (x && rn_satisfies_leaf(v, x, off)) 380265708Smelifaro return (x); 38159529Swollman } 38259529Swollman m = m->rm_mklist; 3831541Srgrimes } 3841541Srgrimes } while (t != top); 385265708Smelifaro return (0); 38631390Sbde} 3878876Srgrimes 3881541Srgrimes#ifdef RN_DEBUG 3891541Srgrimesint rn_nodenum; 3901541Srgrimesstruct radix_node *rn_clist; 3911541Srgrimesint rn_saveinfo; 3921541Srgrimesint rn_debug = 1; 3931541Srgrimes#endif 3941541Srgrimes 395128525Sluigi/* 396128525Sluigi * Whenever we add a new leaf to the tree, we also add a parent node, 397128525Sluigi * so we allocate them as an array of two elements: the first one must be 398128525Sluigi * the leaf (see RNTORT() in route.c), the second one is the parent. 399128525Sluigi * This routine initializes the relevant fields of the nodes, so that 400128525Sluigi * the leaf is the left child of the parent node, and both nodes have 401128525Sluigi * (almost) all all fields filled as appropriate. 402128525Sluigi * (XXX some fields are left unset, see the '#if 0' section). 403128525Sluigi * The function returns a pointer to the parent node. 404128525Sluigi */ 405128525Sluigi 40612820Sphkstatic struct radix_node * 407265708Smelifarorn_newpair(void *v, int b, struct radix_node nodes[2]) 4081541Srgrimes{ 409265708Smelifaro struct radix_node *tt = nodes, *t = tt + 1; 41059529Swollman t->rn_bit = b; 41159529Swollman t->rn_bmask = 0x80 >> (b & 7); 41259529Swollman t->rn_left = tt; 41359529Swollman t->rn_offset = b >> 3; 414128525Sluigi 415128525Sluigi#if 0 /* XXX perhaps we should fill these fields as well. */ 416128525Sluigi t->rn_parent = t->rn_right = NULL; 417128525Sluigi 418128525Sluigi tt->rn_mask = NULL; 419128525Sluigi tt->rn_dupedkey = NULL; 420128525Sluigi tt->rn_bmask = 0; 421128525Sluigi#endif 42259529Swollman tt->rn_bit = -1; 42359529Swollman tt->rn_key = (caddr_t)v; 42459529Swollman tt->rn_parent = t; 4251541Srgrimes tt->rn_flags = t->rn_flags = RNF_ACTIVE; 42667727Swollman tt->rn_mklist = t->rn_mklist = 0; 4271541Srgrimes#ifdef RN_DEBUG 4281541Srgrimes tt->rn_info = rn_nodenum++; t->rn_info = rn_nodenum++; 42959529Swollman tt->rn_twin = t; 43059529Swollman tt->rn_ybro = rn_clist; 43159529Swollman rn_clist = tt; 4321541Srgrimes#endif 433265708Smelifaro return (t); 4341541Srgrimes} 4351541Srgrimes 43612820Sphkstatic struct radix_node * 437265708Smelifarorn_insert(void *v_arg, struct radix_node_head *head, int *dupentry, 438265708Smelifaro struct radix_node nodes[2]) 4391541Srgrimes{ 4401541Srgrimes caddr_t v = v_arg; 4411541Srgrimes struct radix_node *top = head->rnh_treetop; 442200354Sluigi int head_off = top->rn_offset, vlen = LEN(v); 443265708Smelifaro struct radix_node *t = rn_search(v_arg, top); 444265708Smelifaro caddr_t cp = v + head_off; 445265708Smelifaro int b; 446265708Smelifaro struct radix_node *p, *tt, *x; 4471541Srgrimes /* 4488152Spst * Find first bit at which v and t->rn_key differ 4491541Srgrimes */ 450265708Smelifaro caddr_t cp2 = t->rn_key + head_off; 451265708Smelifaro int cmp_res; 4521541Srgrimes caddr_t cplim = v + vlen; 4531541Srgrimes 4541541Srgrimes while (cp < cplim) 4551541Srgrimes if (*cp2++ != *cp++) 4561541Srgrimes goto on1; 4571541Srgrimes *dupentry = 1; 458265708Smelifaro return (t); 4591541Srgrimeson1: 4601541Srgrimes *dupentry = 0; 4611541Srgrimes cmp_res = (cp[-1] ^ cp2[-1]) & 0xff; 4621541Srgrimes for (b = (cp - v) << 3; cmp_res; b--) 4631541Srgrimes cmp_res >>= 1; 464265708Smelifaro 465265708Smelifaro x = top; 4661541Srgrimes cp = v; 4671541Srgrimes do { 4681541Srgrimes p = x; 46959529Swollman if (cp[x->rn_offset] & x->rn_bmask) 47059529Swollman x = x->rn_right; 47159529Swollman else 47259529Swollman x = x->rn_left; 47359529Swollman } while (b > (unsigned) x->rn_bit); 47459529Swollman /* x->rn_bit < b && x->rn_bit >= 0 */ 4751541Srgrimes#ifdef RN_DEBUG 4761541Srgrimes if (rn_debug) 4778152Spst log(LOG_DEBUG, "rn_insert: Going In:\n"), traverse(p); 4781541Srgrimes#endif 47959529Swollman t = rn_newpair(v_arg, b, nodes); 48059529Swollman tt = t->rn_left; 48159529Swollman if ((cp[p->rn_offset] & p->rn_bmask) == 0) 48259529Swollman p->rn_left = t; 4831541Srgrimes else 48459529Swollman p->rn_right = t; 48559529Swollman x->rn_parent = t; 48659529Swollman t->rn_parent = p; /* frees x, p as temp vars below */ 48759529Swollman if ((cp[t->rn_offset] & t->rn_bmask) == 0) { 48859529Swollman t->rn_right = x; 4891541Srgrimes } else { 49059529Swollman t->rn_right = tt; 49159529Swollman t->rn_left = x; 4921541Srgrimes } 4931541Srgrimes#ifdef RN_DEBUG 4941541Srgrimes if (rn_debug) 4958152Spst log(LOG_DEBUG, "rn_insert: Coming Out:\n"), traverse(p); 4961541Srgrimes#endif 4971541Srgrimes return (tt); 4981541Srgrimes} 4991541Srgrimes 5001541Srgrimesstruct radix_node * 501257330Smelifarorn_addmask_r(void *arg, struct radix_node_head *maskhead, int search, int skip) 5021541Srgrimes{ 503265708Smelifaro unsigned char *netmask = arg; 504265708Smelifaro unsigned char *cp, *cplim; 505265708Smelifaro struct radix_node *x; 506265708Smelifaro int b = 0, mlen, j; 507257330Smelifaro int maskduplicated, isnormal; 5088152Spst struct radix_node *saved_x; 509265708Smelifaro unsigned char addmask_key[RADIX_MAX_KEY_LEN]; 5101541Srgrimes 511257330Smelifaro if ((mlen = LEN(netmask)) > RADIX_MAX_KEY_LEN) 512257330Smelifaro mlen = RADIX_MAX_KEY_LEN; 5138152Spst if (skip == 0) 5148152Spst skip = 1; 5158152Spst if (mlen <= skip) 516257330Smelifaro return (maskhead->rnh_nodes); 517257330Smelifaro 518257330Smelifaro bzero(addmask_key, RADIX_MAX_KEY_LEN); 5198152Spst if (skip > 1) 520128401Sluigi bcopy(rn_ones + 1, addmask_key + 1, skip - 1); 521257330Smelifaro bcopy(netmask + skip, addmask_key + skip, mlen - skip); 5228152Spst /* 5238152Spst * Trim trailing zeroes. 5248152Spst */ 5258152Spst for (cp = addmask_key + mlen; (cp > addmask_key) && cp[-1] == 0;) 5268152Spst cp--; 5278152Spst mlen = cp - addmask_key; 528257330Smelifaro if (mlen <= skip) 529257330Smelifaro return (maskhead->rnh_nodes); 530257330Smelifaro *addmask_key = mlen; 531257330Smelifaro x = rn_search(addmask_key, maskhead->rnh_treetop); 532128401Sluigi if (bcmp(addmask_key, x->rn_key, mlen) != 0) 5338152Spst x = 0; 5348152Spst if (x || search) 5358152Spst return (x); 536257330Smelifaro R_Zalloc(x, struct radix_node *, RADIX_MAX_KEY_LEN + 2 * sizeof (*x)); 5378152Spst if ((saved_x = x) == 0) 5381541Srgrimes return (0); 5398152Spst netmask = cp = (caddr_t)(x + 2); 540128401Sluigi bcopy(addmask_key, cp, mlen); 541257330Smelifaro x = rn_insert(cp, maskhead, &maskduplicated, x); 5428152Spst if (maskduplicated) { 5438152Spst log(LOG_ERR, "rn_addmask: mask impossibly already in tree"); 5448152Spst Free(saved_x); 5458152Spst return (x); 5468152Spst } 5471541Srgrimes /* 5488152Spst * Calculate index of mask, and check for normalcy. 549128433Sluigi * First find the first byte with a 0 bit, then if there are 550128433Sluigi * more bits left (remember we already trimmed the trailing 0's), 551265708Smelifaro * the bits should be contiguous, otherwise we have got 552128433Sluigi * a non-contiguous mask. 5531541Srgrimes */ 554265708Smelifaro#define CONTIG(_c) (((~(_c) + 1) & (_c)) == (unsigned char)(~(_c) + 1)) 555128433Sluigi cplim = netmask + mlen; 556128433Sluigi isnormal = 1; 5578152Spst for (cp = netmask + skip; (cp < cplim) && *(u_char *)cp == 0xff;) 5588152Spst cp++; 5591541Srgrimes if (cp != cplim) { 5608876Srgrimes for (j = 0x80; (j & *cp) != 0; j >>= 1) 5618152Spst b++; 562265708Smelifaro if (!CONTIG(*cp) || 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 572257330Smelifarostruct radix_node * 573257330Smelifarorn_addmask(void *n_arg, int search, int skip) 574257330Smelifaro{ 575257330Smelifaro struct radix_node *tt; 576257330Smelifaro 577257330Smelifaro#ifdef _KERNEL 578257330Smelifaro mtx_lock(&mask_mtx); 579257330Smelifaro#endif 580257330Smelifaro tt = rn_addmask_r(&mask_rnhead_compat, n_arg, search, skip); 581257330Smelifaro 582257330Smelifaro#ifdef _KERNEL 583257330Smelifaro mtx_unlock(&mask_mtx); 584257330Smelifaro#endif 585257330Smelifaro 586257330Smelifaro return (tt); 587257330Smelifaro} 588257330Smelifaro 5898152Spststatic int /* XXX: arbitrary ordering for non-contiguous masks */ 590265708Smelifarorn_lexobetter(void *m_arg, void *n_arg) 5918152Spst{ 592265708Smelifaro u_char *mp = m_arg, *np = n_arg, *lim; 5938152Spst 594128525Sluigi if (LEN(mp) > LEN(np)) 595265708Smelifaro return (1); /* not really, but need to check longer one first */ 596128525Sluigi if (LEN(mp) == LEN(np)) 597128525Sluigi for (lim = mp + LEN(mp); mp < lim;) 5988152Spst if (*mp++ > *np++) 599265708Smelifaro return (1); 600265708Smelifaro return (0); 6018152Spst} 6028152Spst 6038152Spststatic struct radix_mask * 604265708Smelifarorn_new_radix_mask(struct radix_node *tt, struct radix_mask *next) 6058152Spst{ 606265708Smelifaro struct radix_mask *m; 6078152Spst 608257330Smelifaro R_Malloc(m, struct radix_mask *, sizeof (struct radix_mask)); 609265708Smelifaro if (m == NULL) { 610257330Smelifaro log(LOG_ERR, "Failed to allocate route mask\n"); 6118152Spst return (0); 6128152Spst } 613257330Smelifaro bzero(m, sizeof(*m)); 61459529Swollman m->rm_bit = tt->rn_bit; 6158152Spst m->rm_flags = tt->rn_flags; 6168152Spst if (tt->rn_flags & RNF_NORMAL) 6178152Spst m->rm_leaf = tt; 6188152Spst else 6198152Spst m->rm_mask = tt->rn_mask; 6208152Spst m->rm_mklist = next; 6218152Spst tt->rn_mklist = m; 622265708Smelifaro return (m); 6238152Spst} 6248152Spst 6251541Srgrimesstruct radix_node * 626265708Smelifarorn_addroute(void *v_arg, void *n_arg, struct radix_node_head *head, 627265708Smelifaro struct radix_node treenodes[2]) 6281541Srgrimes{ 6291541Srgrimes caddr_t v = (caddr_t)v_arg, netmask = (caddr_t)n_arg; 630265708Smelifaro struct radix_node *t, *x = 0, *tt; 6311541Srgrimes struct radix_node *saved_tt, *top = head->rnh_treetop; 6328152Spst short b = 0, b_leaf = 0; 6338152Spst int keyduplicated; 6348152Spst caddr_t mmask; 6351541Srgrimes struct radix_mask *m, **mp; 6361541Srgrimes 6371541Srgrimes /* 6381541Srgrimes * In dealing with non-contiguous masks, there may be 6391541Srgrimes * many different routes which have the same mask. 6401541Srgrimes * We will find it useful to have a unique pointer to 6411541Srgrimes * the mask to speed avoiding duplicate references at 6421541Srgrimes * nodes and possibly save time in calculating indices. 6431541Srgrimes */ 6441541Srgrimes if (netmask) { 645257330Smelifaro x = rn_addmask_r(netmask, head->rnh_masks, 0, top->rn_offset); 646257330Smelifaro if (x == NULL) 6478152Spst return (0); 64859529Swollman b_leaf = x->rn_bit; 64959529Swollman b = -1 - x->rn_bit; 6501541Srgrimes netmask = x->rn_key; 6511541Srgrimes } 6521541Srgrimes /* 6531541Srgrimes * Deal with duplicated keys: attach node to previous instance 6541541Srgrimes */ 6551541Srgrimes saved_tt = tt = rn_insert(v, head, &keyduplicated, treenodes); 6561541Srgrimes if (keyduplicated) { 6578152Spst for (t = tt; tt; t = tt, tt = tt->rn_dupedkey) { 658178167Sqingli#ifdef RADIX_MPATH 659178167Sqingli /* permit multipath, if enabled for the family */ 660178167Sqingli if (rn_mpath_capable(head) && netmask == tt->rn_mask) { 661178167Sqingli /* 662178167Sqingli * go down to the end of multipaths, so that 663178167Sqingli * new entry goes into the end of rn_dupedkey 664178167Sqingli * chain. 665178167Sqingli */ 666178167Sqingli do { 667178167Sqingli t = tt; 668178167Sqingli tt = tt->rn_dupedkey; 669178167Sqingli } while (tt && t->rn_mask == tt->rn_mask); 670178167Sqingli break; 671178167Sqingli } 672178167Sqingli#endif 6731541Srgrimes if (tt->rn_mask == netmask) 6741541Srgrimes return (0); 6751541Srgrimes if (netmask == 0 || 6768152Spst (tt->rn_mask && 67759529Swollman ((b_leaf < tt->rn_bit) /* index(netmask) > node */ 67859529Swollman || rn_refines(netmask, tt->rn_mask) 67959529Swollman || rn_lexobetter(netmask, tt->rn_mask)))) 6801541Srgrimes break; 6818152Spst } 6821541Srgrimes /* 6831541Srgrimes * If the mask is not duplicated, we wouldn't 6841541Srgrimes * find it among possible duplicate key entries 6851541Srgrimes * anyway, so the above test doesn't hurt. 6861541Srgrimes * 6871541Srgrimes * We sort the masks for a duplicated key the same way as 6881541Srgrimes * in a masklist -- most specific to least specific. 6891541Srgrimes * This may require the unfortunate nuisance of relocating 6901541Srgrimes * the head of the list. 691108268Sru * 692108268Sru * We also reverse, or doubly link the list through the 693108268Sru * parent pointer. 6941541Srgrimes */ 6958152Spst if (tt == saved_tt) { 6961541Srgrimes struct radix_node *xx = x; 6971541Srgrimes /* link in at head of list */ 6981541Srgrimes (tt = treenodes)->rn_dupedkey = t; 6991541Srgrimes tt->rn_flags = t->rn_flags; 70059529Swollman tt->rn_parent = x = t->rn_parent; 70159529Swollman t->rn_parent = tt; /* parent */ 70259529Swollman if (x->rn_left == t) 70359529Swollman x->rn_left = tt; 70459529Swollman else 70559529Swollman x->rn_right = tt; 7061541Srgrimes saved_tt = tt; x = xx; 7071541Srgrimes } else { 7081541Srgrimes (tt = treenodes)->rn_dupedkey = t->rn_dupedkey; 7091541Srgrimes t->rn_dupedkey = tt; 71059529Swollman tt->rn_parent = t; /* parent */ 7118152Spst if (tt->rn_dupedkey) /* parent */ 71259529Swollman tt->rn_dupedkey->rn_parent = tt; /* parent */ 7131541Srgrimes } 7141541Srgrimes#ifdef RN_DEBUG 7151541Srgrimes t=tt+1; tt->rn_info = rn_nodenum++; t->rn_info = rn_nodenum++; 7161541Srgrimes tt->rn_twin = t; tt->rn_ybro = rn_clist; rn_clist = tt; 7171541Srgrimes#endif 7181541Srgrimes tt->rn_key = (caddr_t) v; 71959529Swollman tt->rn_bit = -1; 7208152Spst tt->rn_flags = RNF_ACTIVE; 7211541Srgrimes } 7221541Srgrimes /* 7231541Srgrimes * Put mask in tree. 7241541Srgrimes */ 7251541Srgrimes if (netmask) { 7261541Srgrimes tt->rn_mask = netmask; 72759529Swollman tt->rn_bit = x->rn_bit; 7288152Spst tt->rn_flags |= x->rn_flags & RNF_NORMAL; 7291541Srgrimes } 73059529Swollman t = saved_tt->rn_parent; 7318152Spst if (keyduplicated) 7328152Spst goto on2; 73359529Swollman b_leaf = -1 - t->rn_bit; 73459529Swollman if (t->rn_right == saved_tt) 73559529Swollman x = t->rn_left; 73659529Swollman else 73759529Swollman x = t->rn_right; 7381541Srgrimes /* Promote general routes from below */ 73959529Swollman if (x->rn_bit < 0) { 7408152Spst for (mp = &t->rn_mklist; x; x = x->rn_dupedkey) 74159529Swollman if (x->rn_mask && (x->rn_bit >= b_leaf) && x->rn_mklist == 0) { 7428152Spst *mp = m = rn_new_radix_mask(x, 0); 7438152Spst if (m) 7448152Spst mp = &m->rm_mklist; 7451541Srgrimes } 7461541Srgrimes } else if (x->rn_mklist) { 7471541Srgrimes /* 7481541Srgrimes * Skip over masks whose index is > that of new node 7491541Srgrimes */ 7508152Spst for (mp = &x->rn_mklist; (m = *mp); mp = &m->rm_mklist) 75159529Swollman if (m->rm_bit >= b_leaf) 7521541Srgrimes break; 7531541Srgrimes t->rn_mklist = m; *mp = 0; 7541541Srgrimes } 7558152Spston2: 7561541Srgrimes /* Add new route to highest possible ancestor's list */ 75759529Swollman if ((netmask == 0) || (b > t->rn_bit )) 758265708Smelifaro return (tt); /* can't lift at all */ 75959529Swollman b_leaf = tt->rn_bit; 7601541Srgrimes do { 7611541Srgrimes x = t; 76259529Swollman t = t->rn_parent; 76359529Swollman } while (b <= t->rn_bit && x != top); 7641541Srgrimes /* 7651541Srgrimes * Search through routes associated with node to 7661541Srgrimes * insert new route according to index. 7678152Spst * Need same criteria as when sorting dupedkeys to avoid 7688152Spst * double loop on deletion. 7691541Srgrimes */ 7708152Spst for (mp = &x->rn_mklist; (m = *mp); mp = &m->rm_mklist) { 77159529Swollman if (m->rm_bit < b_leaf) 7721541Srgrimes continue; 77359529Swollman if (m->rm_bit > b_leaf) 7741541Srgrimes break; 7758152Spst if (m->rm_flags & RNF_NORMAL) { 7768152Spst mmask = m->rm_leaf->rn_mask; 7778152Spst if (tt->rn_flags & RNF_NORMAL) { 778204902Sqingli#if !defined(RADIX_MPATH) 77959529Swollman log(LOG_ERR, 78095023Ssuz "Non-unique normal route, mask not entered\n"); 781204902Sqingli#endif 782265708Smelifaro return (tt); 7838152Spst } 7848152Spst } else 7858152Spst mmask = m->rm_mask; 7868152Spst if (mmask == netmask) { 7871541Srgrimes m->rm_refs++; 7881541Srgrimes tt->rn_mklist = m; 789265708Smelifaro return (tt); 7901541Srgrimes } 79159529Swollman if (rn_refines(netmask, mmask) 79259529Swollman || rn_lexobetter(netmask, mmask)) 7931541Srgrimes break; 7941541Srgrimes } 7958152Spst *mp = rn_new_radix_mask(tt, *mp); 796265708Smelifaro return (tt); 7971541Srgrimes} 7981541Srgrimes 79931390Sbdestruct radix_node * 800265708Smelifarorn_delete(void *v_arg, void *netmask_arg, struct radix_node_head *head) 8011541Srgrimes{ 802265708Smelifaro struct radix_node *t, *p, *x, *tt; 8031541Srgrimes struct radix_mask *m, *saved_m, **mp; 8041541Srgrimes struct radix_node *dupedkey, *saved_tt, *top; 8051541Srgrimes caddr_t v, netmask; 8061541Srgrimes int b, head_off, vlen; 8071541Srgrimes 8081541Srgrimes v = v_arg; 8091541Srgrimes netmask = netmask_arg; 8101541Srgrimes x = head->rnh_treetop; 8111541Srgrimes tt = rn_search(v, x); 81259529Swollman head_off = x->rn_offset; 813128525Sluigi vlen = LEN(v); 8141541Srgrimes saved_tt = tt; 8151541Srgrimes top = x; 8161541Srgrimes if (tt == 0 || 817128401Sluigi bcmp(v + head_off, tt->rn_key + head_off, vlen - head_off)) 8181541Srgrimes return (0); 8191541Srgrimes /* 8201541Srgrimes * Delete our route from mask lists. 8211541Srgrimes */ 8228152Spst if (netmask) { 823257330Smelifaro x = rn_addmask_r(netmask, head->rnh_masks, 1, head_off); 824257330Smelifaro if (x == NULL) 8258152Spst return (0); 8268152Spst netmask = x->rn_key; 8271541Srgrimes while (tt->rn_mask != netmask) 8281541Srgrimes if ((tt = tt->rn_dupedkey) == 0) 8291541Srgrimes return (0); 8301541Srgrimes } 8311541Srgrimes if (tt->rn_mask == 0 || (saved_m = m = tt->rn_mklist) == 0) 8321541Srgrimes goto on1; 8338152Spst if (tt->rn_flags & RNF_NORMAL) { 8348152Spst if (m->rm_leaf != tt || m->rm_refs > 0) { 8358152Spst log(LOG_ERR, "rn_delete: inconsistent annotation\n"); 836265708Smelifaro return (0); /* dangling ref could cause disaster */ 8378152Spst } 8388876Srgrimes } else { 8398152Spst if (m->rm_mask != tt->rn_mask) { 8408152Spst log(LOG_ERR, "rn_delete: inconsistent annotation\n"); 8418152Spst goto on1; 8428152Spst } 8438152Spst if (--m->rm_refs >= 0) 8448152Spst goto on1; 8451541Srgrimes } 84659529Swollman b = -1 - tt->rn_bit; 84759529Swollman t = saved_tt->rn_parent; 84859529Swollman if (b > t->rn_bit) 8491541Srgrimes goto on1; /* Wasn't lifted at all */ 8501541Srgrimes do { 8511541Srgrimes x = t; 85259529Swollman t = t->rn_parent; 85359529Swollman } while (b <= t->rn_bit && x != top); 8548152Spst for (mp = &x->rn_mklist; (m = *mp); mp = &m->rm_mklist) 8551541Srgrimes if (m == saved_m) { 8561541Srgrimes *mp = m->rm_mklist; 857257330Smelifaro Free(m); 8581541Srgrimes break; 8591541Srgrimes } 8608152Spst if (m == 0) { 8618152Spst log(LOG_ERR, "rn_delete: couldn't find our annotation\n"); 8628152Spst if (tt->rn_flags & RNF_NORMAL) 8638152Spst return (0); /* Dangling ref to us */ 8648152Spst } 8651541Srgrimeson1: 8661541Srgrimes /* 8671541Srgrimes * Eliminate us from tree 8681541Srgrimes */ 8691541Srgrimes if (tt->rn_flags & RNF_ROOT) 8701541Srgrimes return (0); 8711541Srgrimes#ifdef RN_DEBUG 8721541Srgrimes /* Get us out of the creation list */ 8731541Srgrimes for (t = rn_clist; t && t->rn_ybro != tt; t = t->rn_ybro) {} 8741541Srgrimes if (t) t->rn_ybro = tt->rn_ybro; 8751541Srgrimes#endif 87659529Swollman t = tt->rn_parent; 8778152Spst dupedkey = saved_tt->rn_dupedkey; 8781541Srgrimes if (dupedkey) { 8798152Spst /* 880108268Sru * Here, tt is the deletion target and 881108268Sru * saved_tt is the head of the dupekey chain. 8828152Spst */ 8831541Srgrimes if (tt == saved_tt) { 8848152Spst /* remove from head of chain */ 88559529Swollman x = dupedkey; x->rn_parent = t; 88659529Swollman if (t->rn_left == tt) 88759529Swollman t->rn_left = x; 88859529Swollman else 88959529Swollman t->rn_right = x; 8901541Srgrimes } else { 8918152Spst /* find node in front of tt on the chain */ 8921541Srgrimes for (x = p = saved_tt; p && p->rn_dupedkey != tt;) 8931541Srgrimes p = p->rn_dupedkey; 8948152Spst if (p) { 8958152Spst p->rn_dupedkey = tt->rn_dupedkey; 89659529Swollman if (tt->rn_dupedkey) /* parent */ 89759529Swollman tt->rn_dupedkey->rn_parent = p; 89859529Swollman /* parent */ 8998152Spst } else log(LOG_ERR, "rn_delete: couldn't find us\n"); 9001541Srgrimes } 9011541Srgrimes t = tt + 1; 9021541Srgrimes if (t->rn_flags & RNF_ACTIVE) { 9031541Srgrimes#ifndef RN_DEBUG 90459529Swollman *++x = *t; 90559529Swollman p = t->rn_parent; 9061541Srgrimes#else 90759529Swollman b = t->rn_info; 90859529Swollman *++x = *t; 90959529Swollman t->rn_info = b; 91059529Swollman p = t->rn_parent; 9111541Srgrimes#endif 91259529Swollman if (p->rn_left == t) 91359529Swollman p->rn_left = x; 91459529Swollman else 91559529Swollman p->rn_right = x; 91659529Swollman x->rn_left->rn_parent = x; 91759529Swollman x->rn_right->rn_parent = x; 9181541Srgrimes } 9191541Srgrimes goto out; 9201541Srgrimes } 92159529Swollman if (t->rn_left == tt) 92259529Swollman x = t->rn_right; 92359529Swollman else 92459529Swollman x = t->rn_left; 92559529Swollman p = t->rn_parent; 92659529Swollman if (p->rn_right == t) 92759529Swollman p->rn_right = x; 92859529Swollman else 92959529Swollman p->rn_left = x; 93059529Swollman x->rn_parent = p; 9311541Srgrimes /* 9321541Srgrimes * Demote routes attached to us. 9331541Srgrimes */ 9341541Srgrimes if (t->rn_mklist) { 93559529Swollman if (x->rn_bit >= 0) { 9368152Spst for (mp = &x->rn_mklist; (m = *mp);) 9371541Srgrimes mp = &m->rm_mklist; 9381541Srgrimes *mp = t->rn_mklist; 9391541Srgrimes } else { 9408152Spst /* If there are any key,mask pairs in a sibling 9418152Spst duped-key chain, some subset will appear sorted 9428152Spst in the same order attached to our mklist */ 9438152Spst for (m = t->rn_mklist; m && x; x = x->rn_dupedkey) 9448152Spst if (m == x->rn_mklist) { 9458152Spst struct radix_mask *mm = m->rm_mklist; 9461541Srgrimes x->rn_mklist = 0; 9478152Spst if (--(m->rm_refs) < 0) 948257330Smelifaro Free(m); 9498152Spst m = mm; 9508152Spst } 9518152Spst if (m) 95237560Sbde log(LOG_ERR, 95337560Sbde "rn_delete: Orphaned Mask %p at %p\n", 954204582Sluigi m, x); 9551541Srgrimes } 9561541Srgrimes } 9571541Srgrimes /* 9581541Srgrimes * We may be holding an active internal node in the tree. 9591541Srgrimes */ 9601541Srgrimes x = tt + 1; 9611541Srgrimes if (t != x) { 9621541Srgrimes#ifndef RN_DEBUG 9631541Srgrimes *t = *x; 9641541Srgrimes#else 96559529Swollman b = t->rn_info; 96659529Swollman *t = *x; 96759529Swollman t->rn_info = b; 9681541Srgrimes#endif 96959529Swollman t->rn_left->rn_parent = t; 97059529Swollman t->rn_right->rn_parent = t; 97159529Swollman p = x->rn_parent; 97259529Swollman if (p->rn_left == x) 97359529Swollman p->rn_left = t; 97459529Swollman else 97559529Swollman p->rn_right = t; 9761541Srgrimes } 9771541Srgrimesout: 9781541Srgrimes tt->rn_flags &= ~RNF_ACTIVE; 9791541Srgrimes tt[1].rn_flags &= ~RNF_ACTIVE; 9801541Srgrimes return (tt); 9811541Srgrimes} 9821541Srgrimes 9837197Swollman/* 9847197Swollman * This is the same as rn_walktree() except for the parameters and the 9857197Swollman * exit. 9867197Swollman */ 98712820Sphkstatic int 988265708Smelifarorn_walktree_from(struct radix_node_head *h, void *a, void *m, 989265708Smelifaro walktree_f_t *f, void *w) 9907197Swollman{ 9917197Swollman int error; 9927197Swollman struct radix_node *base, *next; 9937197Swollman u_char *xa = (u_char *)a; 9947197Swollman u_char *xm = (u_char *)m; 995265708Smelifaro struct radix_node *rn, *last = NULL; /* shut up gcc */ 9967197Swollman int stopping = 0; 9977197Swollman int lastb; 9987197Swollman 9997197Swollman /* 1000128525Sluigi * rn_search_m is sort-of-open-coded here. We cannot use the 1001128525Sluigi * function because we need to keep track of the last node seen. 10027197Swollman */ 10037279Swollman /* printf("about to search\n"); */ 100459529Swollman for (rn = h->rnh_treetop; rn->rn_bit >= 0; ) { 10057197Swollman last = rn; 100659529Swollman /* printf("rn_bit %d, rn_bmask %x, xm[rn_offset] %x\n", 100759529Swollman rn->rn_bit, rn->rn_bmask, xm[rn->rn_offset]); */ 100859529Swollman if (!(rn->rn_bmask & xm[rn->rn_offset])) { 10097197Swollman break; 10107279Swollman } 101159529Swollman if (rn->rn_bmask & xa[rn->rn_offset]) { 101259529Swollman rn = rn->rn_right; 10137197Swollman } else { 101459529Swollman rn = rn->rn_left; 10157197Swollman } 10167197Swollman } 10177279Swollman /* printf("done searching\n"); */ 10187197Swollman 10197197Swollman /* 10207197Swollman * Two cases: either we stepped off the end of our mask, 10217197Swollman * in which case last == rn, or we reached a leaf, in which 10227197Swollman * case we want to start from the last node we looked at. 10237197Swollman * Either way, last is the node we want to start from. 10247197Swollman */ 10257197Swollman rn = last; 102659529Swollman lastb = rn->rn_bit; 10277197Swollman 10287279Swollman /* printf("rn %p, lastb %d\n", rn, lastb);*/ 10297279Swollman 10307197Swollman /* 10317197Swollman * This gets complicated because we may delete the node 10327197Swollman * while applying the function f to it, so we need to calculate 10337197Swollman * the successor node in advance. 10347197Swollman */ 103559529Swollman while (rn->rn_bit >= 0) 103659529Swollman rn = rn->rn_left; 10377197Swollman 10387197Swollman while (!stopping) { 103959529Swollman /* printf("node %p (%d)\n", rn, rn->rn_bit); */ 10407197Swollman base = rn; 10417197Swollman /* If at right child go back up, otherwise, go right */ 104259529Swollman while (rn->rn_parent->rn_right == rn 104359529Swollman && !(rn->rn_flags & RNF_ROOT)) { 104459529Swollman rn = rn->rn_parent; 10457197Swollman 10468876Srgrimes /* if went up beyond last, stop */ 1047155442Sqingli if (rn->rn_bit <= lastb) { 10487197Swollman stopping = 1; 10497279Swollman /* printf("up too far\n"); */ 1050128525Sluigi /* 1051128525Sluigi * XXX we should jump to the 'Process leaves' 1052128525Sluigi * part, because the values of 'rn' and 'next' 1053128525Sluigi * we compute will not be used. Not a big deal 1054128525Sluigi * because this loop will terminate, but it is 1055128525Sluigi * inefficient and hard to understand! 1056128525Sluigi */ 10577197Swollman } 10587197Swollman } 1059155442Sqingli 1060155442Sqingli /* 1061155442Sqingli * At the top of the tree, no need to traverse the right 1062155442Sqingli * half, prevent the traversal of the entire tree in the 1063155442Sqingli * case of default route. 1064155442Sqingli */ 1065155442Sqingli if (rn->rn_parent->rn_flags & RNF_ROOT) 1066155442Sqingli stopping = 1; 10677197Swollman 10687197Swollman /* Find the next *leaf* since next node might vanish, too */ 106959529Swollman for (rn = rn->rn_parent->rn_right; rn->rn_bit >= 0;) 107059529Swollman rn = rn->rn_left; 10717197Swollman next = rn; 10727197Swollman /* Process leaves */ 10737197Swollman while ((rn = base) != 0) { 10747197Swollman base = rn->rn_dupedkey; 10757279Swollman /* printf("leaf %p\n", rn); */ 10768876Srgrimes if (!(rn->rn_flags & RNF_ROOT) 10777197Swollman && (error = (*f)(rn, w))) 10787197Swollman return (error); 10797197Swollman } 10807197Swollman rn = next; 10817279Swollman 10827279Swollman if (rn->rn_flags & RNF_ROOT) { 10837279Swollman /* printf("root, stopping"); */ 10847279Swollman stopping = 1; 10857279Swollman } 10867279Swollman 10877197Swollman } 1088265708Smelifaro return (0); 10897197Swollman} 10907197Swollman 109112820Sphkstatic int 1092265708Smelifarorn_walktree(struct radix_node_head *h, walktree_f_t *f, void *w) 10931541Srgrimes{ 10941541Srgrimes int error; 10951541Srgrimes struct radix_node *base, *next; 1096265708Smelifaro struct radix_node *rn = h->rnh_treetop; 10971541Srgrimes /* 10981541Srgrimes * This gets complicated because we may delete the node 10991541Srgrimes * while applying the function f to it, so we need to calculate 11001541Srgrimes * the successor node in advance. 11011541Srgrimes */ 1102186166Skmacy 11031541Srgrimes /* First time through node, go left */ 110459529Swollman while (rn->rn_bit >= 0) 110559529Swollman rn = rn->rn_left; 11061541Srgrimes for (;;) { 11071541Srgrimes base = rn; 11081541Srgrimes /* If at right child go back up, otherwise, go right */ 110959529Swollman while (rn->rn_parent->rn_right == rn 111059529Swollman && (rn->rn_flags & RNF_ROOT) == 0) 111159529Swollman rn = rn->rn_parent; 11121541Srgrimes /* Find the next *leaf* since next node might vanish, too */ 111359529Swollman for (rn = rn->rn_parent->rn_right; rn->rn_bit >= 0;) 111459529Swollman rn = rn->rn_left; 11151541Srgrimes next = rn; 11161541Srgrimes /* Process leaves */ 11178152Spst while ((rn = base)) { 11181541Srgrimes base = rn->rn_dupedkey; 111959529Swollman if (!(rn->rn_flags & RNF_ROOT) 112059529Swollman && (error = (*f)(rn, w))) 11211541Srgrimes return (error); 11221541Srgrimes } 11231541Srgrimes rn = next; 11241541Srgrimes if (rn->rn_flags & RNF_ROOT) 11251541Srgrimes return (0); 11261541Srgrimes } 11271541Srgrimes /* NOTREACHED */ 11281541Srgrimes} 11291541Srgrimes 1130128525Sluigi/* 1131128525Sluigi * Allocate and initialize an empty tree. This has 3 nodes, which are 1132128525Sluigi * part of the radix_node_head (in the order <left,root,right>) and are 1133128525Sluigi * marked RNF_ROOT so they cannot be freed. 1134128525Sluigi * The leaves have all-zero and all-one keys, with significant 1135128525Sluigi * bits starting at 'off'. 1136128525Sluigi * Return 1 on success, 0 on error. 1137128525Sluigi */ 1138257330Smelifarostatic int 1139257330Smelifarorn_inithead_internal(void **head, int off) 11401541Srgrimes{ 1141265708Smelifaro struct radix_node_head *rnh; 1142265708Smelifaro struct radix_node *t, *tt, *ttt; 11431541Srgrimes if (*head) 11441541Srgrimes return (1); 1145128433Sluigi R_Zalloc(rnh, struct radix_node_head *, sizeof (*rnh)); 11461541Srgrimes if (rnh == 0) 11471541Srgrimes return (0); 1148110527Shsu#ifdef _KERNEL 1149108250Shsu RADIX_NODE_HEAD_LOCK_INIT(rnh); 1150110527Shsu#endif 11511541Srgrimes *head = rnh; 11521541Srgrimes t = rn_newpair(rn_zeros, off, rnh->rnh_nodes); 11531541Srgrimes ttt = rnh->rnh_nodes + 2; 115459529Swollman t->rn_right = ttt; 115559529Swollman t->rn_parent = t; 1156128525Sluigi tt = t->rn_left; /* ... which in turn is rnh->rnh_nodes */ 11571541Srgrimes tt->rn_flags = t->rn_flags = RNF_ROOT | RNF_ACTIVE; 115859529Swollman tt->rn_bit = -1 - off; 11591541Srgrimes *ttt = *tt; 11601541Srgrimes ttt->rn_key = rn_ones; 11611541Srgrimes rnh->rnh_addaddr = rn_addroute; 11621541Srgrimes rnh->rnh_deladdr = rn_delete; 11631541Srgrimes rnh->rnh_matchaddr = rn_match; 11648152Spst rnh->rnh_lookup = rn_lookup; 11651541Srgrimes rnh->rnh_walktree = rn_walktree; 11667197Swollman rnh->rnh_walktree_from = rn_walktree_from; 11671541Srgrimes rnh->rnh_treetop = t; 11681541Srgrimes return (1); 11691541Srgrimes} 11701541Srgrimes 1171257330Smelifarostatic void 1172257330Smelifarorn_detachhead_internal(void **head) 1173204808Sbz{ 1174204808Sbz struct radix_node_head *rnh; 1175204808Sbz 1176204808Sbz KASSERT((head != NULL && *head != NULL), 1177204808Sbz ("%s: head already freed", __func__)); 1178204808Sbz rnh = *head; 1179204808Sbz 1180204808Sbz /* Free <left,root,right> nodes. */ 1181204808Sbz Free(rnh); 1182204808Sbz 1183204808Sbz *head = NULL; 1184257330Smelifaro} 1185257330Smelifaro 1186257330Smelifaroint 1187257330Smelifarorn_inithead(void **head, int off) 1188257330Smelifaro{ 1189257330Smelifaro struct radix_node_head *rnh; 1190257330Smelifaro 1191257330Smelifaro if (*head != NULL) 1192257330Smelifaro return (1); 1193257330Smelifaro 1194257330Smelifaro if (rn_inithead_internal(head, off) == 0) 1195257330Smelifaro return (0); 1196257330Smelifaro 1197257330Smelifaro rnh = (struct radix_node_head *)(*head); 1198257330Smelifaro 1199257330Smelifaro if (rn_inithead_internal((void **)&rnh->rnh_masks, 0) == 0) { 1200257330Smelifaro rn_detachhead_internal(head); 1201257330Smelifaro return (0); 1202257330Smelifaro } 1203257330Smelifaro 1204204808Sbz return (1); 1205204808Sbz} 1206204808Sbz 1207273196Sglebiusstatic int 1208273196Sglebiusrn_freeentry(struct radix_node *rn, void *arg) 1209273196Sglebius{ 1210273196Sglebius struct radix_node_head * const rnh = arg; 1211273196Sglebius struct radix_node *x; 1212273196Sglebius 1213273196Sglebius x = (struct radix_node *)rn_delete(rn + 2, NULL, rnh); 1214273196Sglebius if (x != NULL) 1215273196Sglebius Free(x); 1216273196Sglebius return (0); 1217273196Sglebius} 1218273196Sglebius 1219257330Smelifaroint 1220257330Smelifarorn_detachhead(void **head) 1221257330Smelifaro{ 1222257330Smelifaro struct radix_node_head *rnh; 1223257330Smelifaro 1224257330Smelifaro KASSERT((head != NULL && *head != NULL), 1225257330Smelifaro ("%s: head already freed", __func__)); 1226257330Smelifaro 1227257330Smelifaro rnh = *head; 1228257330Smelifaro 1229273196Sglebius rn_walktree(rnh->rnh_masks, rn_freeentry, rnh->rnh_masks); 1230257330Smelifaro rn_detachhead_internal((void **)&rnh->rnh_masks); 1231257330Smelifaro rn_detachhead_internal(head); 1232257330Smelifaro return (1); 1233257330Smelifaro} 1234257330Smelifaro 12351541Srgrimesvoid 1236200537Sluigirn_init(int maxk) 12371541Srgrimes{ 1238257330Smelifaro if ((maxk <= 0) || (maxk > RADIX_MAX_KEY_LEN)) { 12398152Spst log(LOG_ERR, 1240257330Smelifaro "rn_init: max_keylen must be within 1..%d\n", 1241257330Smelifaro RADIX_MAX_KEY_LEN); 12421541Srgrimes return; 12431541Srgrimes } 1244257330Smelifaro 1245257330Smelifaro /* 1246257330Smelifaro * XXX: Compat for old rn_addmask() users 1247257330Smelifaro */ 1248257330Smelifaro if (rn_inithead((void **)(void *)&mask_rnhead_compat, 0) == 0) 12491541Srgrimes panic("rn_init 2"); 1250257330Smelifaro#ifdef _KERNEL 1251257330Smelifaro mtx_init(&mask_mtx, "radix_mask", NULL, MTX_DEF); 1252257330Smelifaro#endif 12531541Srgrimes} 1254