radix.c revision 1541
11541Srgrimes/* 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 * 3. All advertising materials mentioning features or use of this software 141541Srgrimes * must display the following acknowledgement: 151541Srgrimes * This product includes software developed by the University of 161541Srgrimes * California, Berkeley and its contributors. 171541Srgrimes * 4. Neither the name of the University nor the names of its contributors 181541Srgrimes * may be used to endorse or promote products derived from this software 191541Srgrimes * without specific prior written permission. 201541Srgrimes * 211541Srgrimes * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 221541Srgrimes * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 231541Srgrimes * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 241541Srgrimes * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 251541Srgrimes * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 261541Srgrimes * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 271541Srgrimes * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 281541Srgrimes * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 291541Srgrimes * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 301541Srgrimes * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 311541Srgrimes * SUCH DAMAGE. 321541Srgrimes * 331541Srgrimes * @(#)radix.c 8.2 (Berkeley) 1/4/94 341541Srgrimes */ 351541Srgrimes 361541Srgrimes/* 371541Srgrimes * Routines to build and maintain radix trees for routing lookups. 381541Srgrimes */ 391541Srgrimes#ifndef RNF_NORMAL 401541Srgrimes#include <sys/param.h> 411541Srgrimes#include <sys/systm.h> 421541Srgrimes#include <sys/malloc.h> 431541Srgrimes#define M_DONTWAIT M_NOWAIT 441541Srgrimes#ifdef KERNEL 451541Srgrimes#include <sys/domain.h> 461541Srgrimes#endif 471541Srgrimes#endif 481541Srgrimes 491541Srgrimes#include <net/radix.h> 501541Srgrimes 511541Srgrimesint max_keylen; 521541Srgrimesstruct radix_mask *rn_mkfreelist; 531541Srgrimesstruct radix_node_head *mask_rnhead; 541541Srgrimesstatic int gotOddMasks; 551541Srgrimesstatic char *maskedKey; 561541Srgrimesstatic char *rn_zeros, *rn_ones; 571541Srgrimes 581541Srgrimes#define rn_masktop (mask_rnhead->rnh_treetop) 591541Srgrimes#undef Bcmp 601541Srgrimes#define Bcmp(a, b, l) (l == 0 ? 0 : bcmp((caddr_t)(a), (caddr_t)(b), (u_long)l)) 611541Srgrimes/* 621541Srgrimes * The data structure for the keys is a radix tree with one way 631541Srgrimes * branching removed. The index rn_b at an internal node n represents a bit 641541Srgrimes * position to be tested. The tree is arranged so that all descendants 651541Srgrimes * of a node n have keys whose bits all agree up to position rn_b - 1. 661541Srgrimes * (We say the index of n is rn_b.) 671541Srgrimes * 681541Srgrimes * There is at least one descendant which has a one bit at position rn_b, 691541Srgrimes * and at least one with a zero there. 701541Srgrimes * 711541Srgrimes * A route is determined by a pair of key and mask. We require that the 721541Srgrimes * bit-wise logical and of the key and mask to be the key. 731541Srgrimes * We define the index of a route to associated with the mask to be 741541Srgrimes * the first bit number in the mask where 0 occurs (with bit number 0 751541Srgrimes * representing the highest order bit). 761541Srgrimes * 771541Srgrimes * We say a mask is normal if every bit is 0, past the index of the mask. 781541Srgrimes * If a node n has a descendant (k, m) with index(m) == index(n) == rn_b, 791541Srgrimes * and m is a normal mask, then the route applies to every descendant of n. 801541Srgrimes * If the index(m) < rn_b, this implies the trailing last few bits of k 811541Srgrimes * before bit b are all 0, (and hence consequently true of every descendant 821541Srgrimes * of n), so the route applies to all descendants of the node as well. 831541Srgrimes * 841541Srgrimes * The present version of the code makes no use of normal routes, 851541Srgrimes * but similar logic shows that a non-normal mask m such that 861541Srgrimes * index(m) <= index(n) could potentially apply to many children of n. 871541Srgrimes * Thus, for each non-host route, we attach its mask to a list at an internal 881541Srgrimes * node as high in the tree as we can go. 891541Srgrimes */ 901541Srgrimes 911541Srgrimesstruct radix_node * 921541Srgrimesrn_search(v_arg, head) 931541Srgrimes void *v_arg; 941541Srgrimes struct radix_node *head; 951541Srgrimes{ 961541Srgrimes register struct radix_node *x; 971541Srgrimes register caddr_t v; 981541Srgrimes 991541Srgrimes for (x = head, v = v_arg; x->rn_b >= 0;) { 1001541Srgrimes if (x->rn_bmask & v[x->rn_off]) 1011541Srgrimes x = x->rn_r; 1021541Srgrimes else 1031541Srgrimes x = x->rn_l; 1041541Srgrimes } 1051541Srgrimes return (x); 1061541Srgrimes}; 1071541Srgrimes 1081541Srgrimesstruct radix_node * 1091541Srgrimesrn_search_m(v_arg, head, m_arg) 1101541Srgrimes struct radix_node *head; 1111541Srgrimes void *v_arg, *m_arg; 1121541Srgrimes{ 1131541Srgrimes register struct radix_node *x; 1141541Srgrimes register caddr_t v = v_arg, m = m_arg; 1151541Srgrimes 1161541Srgrimes for (x = head; x->rn_b >= 0;) { 1171541Srgrimes if ((x->rn_bmask & m[x->rn_off]) && 1181541Srgrimes (x->rn_bmask & v[x->rn_off])) 1191541Srgrimes x = x->rn_r; 1201541Srgrimes else 1211541Srgrimes x = x->rn_l; 1221541Srgrimes } 1231541Srgrimes return x; 1241541Srgrimes}; 1251541Srgrimes 1261541Srgrimesint 1271541Srgrimesrn_refines(m_arg, n_arg) 1281541Srgrimes void *m_arg, *n_arg; 1291541Srgrimes{ 1301541Srgrimes register caddr_t m = m_arg, n = n_arg; 1311541Srgrimes register caddr_t lim, lim2 = lim = n + *(u_char *)n; 1321541Srgrimes int longer = (*(u_char *)n++) - (int)(*(u_char *)m++); 1331541Srgrimes int masks_are_equal = 1; 1341541Srgrimes 1351541Srgrimes if (longer > 0) 1361541Srgrimes lim -= longer; 1371541Srgrimes while (n < lim) { 1381541Srgrimes if (*n & ~(*m)) 1391541Srgrimes return 0; 1401541Srgrimes if (*n++ != *m++) 1411541Srgrimes masks_are_equal = 0; 1421541Srgrimes 1431541Srgrimes } 1441541Srgrimes while (n < lim2) 1451541Srgrimes if (*n++) 1461541Srgrimes return 0; 1471541Srgrimes if (masks_are_equal && (longer < 0)) 1481541Srgrimes for (lim2 = m - longer; m < lim2; ) 1491541Srgrimes if (*m++) 1501541Srgrimes return 1; 1511541Srgrimes return (!masks_are_equal); 1521541Srgrimes} 1531541Srgrimes 1541541Srgrimes 1551541Srgrimesstruct radix_node * 1561541Srgrimesrn_match(v_arg, head) 1571541Srgrimes void *v_arg; 1581541Srgrimes struct radix_node_head *head; 1591541Srgrimes{ 1601541Srgrimes caddr_t v = v_arg; 1611541Srgrimes register struct radix_node *t = head->rnh_treetop, *x; 1621541Srgrimes register caddr_t cp = v, cp2, cp3; 1631541Srgrimes caddr_t cplim, mstart; 1641541Srgrimes struct radix_node *saved_t, *top = t; 1651541Srgrimes int off = t->rn_off, vlen = *(u_char *)cp, matched_off; 1661541Srgrimes 1671541Srgrimes /* 1681541Srgrimes * Open code rn_search(v, top) to avoid overhead of extra 1691541Srgrimes * subroutine call. 1701541Srgrimes */ 1711541Srgrimes for (; t->rn_b >= 0; ) { 1721541Srgrimes if (t->rn_bmask & cp[t->rn_off]) 1731541Srgrimes t = t->rn_r; 1741541Srgrimes else 1751541Srgrimes t = t->rn_l; 1761541Srgrimes } 1771541Srgrimes /* 1781541Srgrimes * See if we match exactly as a host destination 1791541Srgrimes */ 1801541Srgrimes cp += off; cp2 = t->rn_key + off; cplim = v + vlen; 1811541Srgrimes for (; cp < cplim; cp++, cp2++) 1821541Srgrimes if (*cp != *cp2) 1831541Srgrimes goto on1; 1841541Srgrimes /* 1851541Srgrimes * This extra grot is in case we are explicitly asked 1861541Srgrimes * to look up the default. Ugh! 1871541Srgrimes */ 1881541Srgrimes if ((t->rn_flags & RNF_ROOT) && t->rn_dupedkey) 1891541Srgrimes t = t->rn_dupedkey; 1901541Srgrimes return t; 1911541Srgrimeson1: 1921541Srgrimes matched_off = cp - v; 1931541Srgrimes saved_t = t; 1941541Srgrimes do { 1951541Srgrimes if (t->rn_mask) { 1961541Srgrimes /* 1971541Srgrimes * Even if we don't match exactly as a hosts; 1981541Srgrimes * we may match if the leaf we wound up at is 1991541Srgrimes * a route to a net. 2001541Srgrimes */ 2011541Srgrimes cp3 = matched_off + t->rn_mask; 2021541Srgrimes cp2 = matched_off + t->rn_key; 2031541Srgrimes for (; cp < cplim; cp++) 2041541Srgrimes if ((*cp2++ ^ *cp) & *cp3++) 2051541Srgrimes break; 2061541Srgrimes if (cp == cplim) 2071541Srgrimes return t; 2081541Srgrimes cp = matched_off + v; 2091541Srgrimes } 2101541Srgrimes } while (t = t->rn_dupedkey); 2111541Srgrimes t = saved_t; 2121541Srgrimes /* start searching up the tree */ 2131541Srgrimes do { 2141541Srgrimes register struct radix_mask *m; 2151541Srgrimes t = t->rn_p; 2161541Srgrimes if (m = t->rn_mklist) { 2171541Srgrimes /* 2181541Srgrimes * After doing measurements here, it may 2191541Srgrimes * turn out to be faster to open code 2201541Srgrimes * rn_search_m here instead of always 2211541Srgrimes * copying and masking. 2221541Srgrimes */ 2231541Srgrimes off = min(t->rn_off, matched_off); 2241541Srgrimes mstart = maskedKey + off; 2251541Srgrimes do { 2261541Srgrimes cp2 = mstart; 2271541Srgrimes cp3 = m->rm_mask + off; 2281541Srgrimes for (cp = v + off; cp < cplim;) 2291541Srgrimes *cp2++ = *cp++ & *cp3++; 2301541Srgrimes x = rn_search(maskedKey, t); 2311541Srgrimes while (x && x->rn_mask != m->rm_mask) 2321541Srgrimes x = x->rn_dupedkey; 2331541Srgrimes if (x && 2341541Srgrimes (Bcmp(mstart, x->rn_key + off, 2351541Srgrimes vlen - off) == 0)) 2361541Srgrimes return x; 2371541Srgrimes } while (m = m->rm_mklist); 2381541Srgrimes } 2391541Srgrimes } while (t != top); 2401541Srgrimes return 0; 2411541Srgrimes}; 2421541Srgrimes 2431541Srgrimes#ifdef RN_DEBUG 2441541Srgrimesint rn_nodenum; 2451541Srgrimesstruct radix_node *rn_clist; 2461541Srgrimesint rn_saveinfo; 2471541Srgrimesint rn_debug = 1; 2481541Srgrimes#endif 2491541Srgrimes 2501541Srgrimesstruct radix_node * 2511541Srgrimesrn_newpair(v, b, nodes) 2521541Srgrimes void *v; 2531541Srgrimes int b; 2541541Srgrimes struct radix_node nodes[2]; 2551541Srgrimes{ 2561541Srgrimes register struct radix_node *tt = nodes, *t = tt + 1; 2571541Srgrimes t->rn_b = b; t->rn_bmask = 0x80 >> (b & 7); 2581541Srgrimes t->rn_l = tt; t->rn_off = b >> 3; 2591541Srgrimes tt->rn_b = -1; tt->rn_key = (caddr_t)v; tt->rn_p = t; 2601541Srgrimes tt->rn_flags = t->rn_flags = RNF_ACTIVE; 2611541Srgrimes#ifdef RN_DEBUG 2621541Srgrimes tt->rn_info = rn_nodenum++; t->rn_info = rn_nodenum++; 2631541Srgrimes tt->rn_twin = t; tt->rn_ybro = rn_clist; rn_clist = tt; 2641541Srgrimes#endif 2651541Srgrimes return t; 2661541Srgrimes} 2671541Srgrimes 2681541Srgrimesstruct radix_node * 2691541Srgrimesrn_insert(v_arg, head, dupentry, nodes) 2701541Srgrimes void *v_arg; 2711541Srgrimes struct radix_node_head *head; 2721541Srgrimes int *dupentry; 2731541Srgrimes struct radix_node nodes[2]; 2741541Srgrimes{ 2751541Srgrimes caddr_t v = v_arg; 2761541Srgrimes struct radix_node *top = head->rnh_treetop; 2771541Srgrimes int head_off = top->rn_off, vlen = (int)*((u_char *)v); 2781541Srgrimes register struct radix_node *t = rn_search(v_arg, top); 2791541Srgrimes register caddr_t cp = v + head_off; 2801541Srgrimes register int b; 2811541Srgrimes struct radix_node *tt; 2821541Srgrimes /* 2831541Srgrimes *find first bit at which v and t->rn_key differ 2841541Srgrimes */ 2851541Srgrimes { 2861541Srgrimes register caddr_t cp2 = t->rn_key + head_off; 2871541Srgrimes register int cmp_res; 2881541Srgrimes caddr_t cplim = v + vlen; 2891541Srgrimes 2901541Srgrimes while (cp < cplim) 2911541Srgrimes if (*cp2++ != *cp++) 2921541Srgrimes goto on1; 2931541Srgrimes *dupentry = 1; 2941541Srgrimes return t; 2951541Srgrimeson1: 2961541Srgrimes *dupentry = 0; 2971541Srgrimes cmp_res = (cp[-1] ^ cp2[-1]) & 0xff; 2981541Srgrimes for (b = (cp - v) << 3; cmp_res; b--) 2991541Srgrimes cmp_res >>= 1; 3001541Srgrimes } 3011541Srgrimes { 3021541Srgrimes register struct radix_node *p, *x = top; 3031541Srgrimes cp = v; 3041541Srgrimes do { 3051541Srgrimes p = x; 3061541Srgrimes if (cp[x->rn_off] & x->rn_bmask) 3071541Srgrimes x = x->rn_r; 3081541Srgrimes else x = x->rn_l; 3091541Srgrimes } while (b > (unsigned) x->rn_b); /* x->rn_b < b && x->rn_b >= 0 */ 3101541Srgrimes#ifdef RN_DEBUG 3111541Srgrimes if (rn_debug) 3121541Srgrimes printf("Going In:\n"), traverse(p); 3131541Srgrimes#endif 3141541Srgrimes t = rn_newpair(v_arg, b, nodes); tt = t->rn_l; 3151541Srgrimes if ((cp[p->rn_off] & p->rn_bmask) == 0) 3161541Srgrimes p->rn_l = t; 3171541Srgrimes else 3181541Srgrimes p->rn_r = t; 3191541Srgrimes x->rn_p = t; t->rn_p = p; /* frees x, p as temp vars below */ 3201541Srgrimes if ((cp[t->rn_off] & t->rn_bmask) == 0) { 3211541Srgrimes t->rn_r = x; 3221541Srgrimes } else { 3231541Srgrimes t->rn_r = tt; t->rn_l = x; 3241541Srgrimes } 3251541Srgrimes#ifdef RN_DEBUG 3261541Srgrimes if (rn_debug) 3271541Srgrimes printf("Coming out:\n"), traverse(p); 3281541Srgrimes#endif 3291541Srgrimes } 3301541Srgrimes return (tt); 3311541Srgrimes} 3321541Srgrimes 3331541Srgrimesstruct radix_node * 3341541Srgrimesrn_addmask(n_arg, search, skip) 3351541Srgrimes int search, skip; 3361541Srgrimes void *n_arg; 3371541Srgrimes{ 3381541Srgrimes caddr_t netmask = (caddr_t)n_arg; 3391541Srgrimes register struct radix_node *x; 3401541Srgrimes register caddr_t cp, cplim; 3411541Srgrimes register int b, mlen, j; 3421541Srgrimes int maskduplicated; 3431541Srgrimes 3441541Srgrimes mlen = *(u_char *)netmask; 3451541Srgrimes if (search) { 3461541Srgrimes x = rn_search(netmask, rn_masktop); 3471541Srgrimes mlen = *(u_char *)netmask; 3481541Srgrimes if (Bcmp(netmask, x->rn_key, mlen) == 0) 3491541Srgrimes return (x); 3501541Srgrimes } 3511541Srgrimes R_Malloc(x, struct radix_node *, max_keylen + 2 * sizeof (*x)); 3521541Srgrimes if (x == 0) 3531541Srgrimes return (0); 3541541Srgrimes Bzero(x, max_keylen + 2 * sizeof (*x)); 3551541Srgrimes cp = (caddr_t)(x + 2); 3561541Srgrimes Bcopy(netmask, cp, mlen); 3571541Srgrimes netmask = cp; 3581541Srgrimes x = rn_insert(netmask, mask_rnhead, &maskduplicated, x); 3591541Srgrimes /* 3601541Srgrimes * Calculate index of mask. 3611541Srgrimes */ 3621541Srgrimes cplim = netmask + mlen; 3631541Srgrimes for (cp = netmask + skip; cp < cplim; cp++) 3641541Srgrimes if (*(u_char *)cp != 0xff) 3651541Srgrimes break; 3661541Srgrimes b = (cp - netmask) << 3; 3671541Srgrimes if (cp != cplim) { 3681541Srgrimes if (*cp != 0) { 3691541Srgrimes gotOddMasks = 1; 3701541Srgrimes for (j = 0x80; j; b++, j >>= 1) 3711541Srgrimes if ((j & *cp) == 0) 3721541Srgrimes break; 3731541Srgrimes } 3741541Srgrimes } 3751541Srgrimes x->rn_b = -1 - b; 3761541Srgrimes return (x); 3771541Srgrimes} 3781541Srgrimes 3791541Srgrimesstruct radix_node * 3801541Srgrimesrn_addroute(v_arg, n_arg, head, treenodes) 3811541Srgrimes void *v_arg, *n_arg; 3821541Srgrimes struct radix_node_head *head; 3831541Srgrimes struct radix_node treenodes[2]; 3841541Srgrimes{ 3851541Srgrimes caddr_t v = (caddr_t)v_arg, netmask = (caddr_t)n_arg; 3861541Srgrimes register struct radix_node *t, *x, *tt; 3871541Srgrimes struct radix_node *saved_tt, *top = head->rnh_treetop; 3881541Srgrimes short b = 0, b_leaf; 3891541Srgrimes int mlen, keyduplicated; 3901541Srgrimes caddr_t cplim; 3911541Srgrimes struct radix_mask *m, **mp; 3921541Srgrimes 3931541Srgrimes /* 3941541Srgrimes * In dealing with non-contiguous masks, there may be 3951541Srgrimes * many different routes which have the same mask. 3961541Srgrimes * We will find it useful to have a unique pointer to 3971541Srgrimes * the mask to speed avoiding duplicate references at 3981541Srgrimes * nodes and possibly save time in calculating indices. 3991541Srgrimes */ 4001541Srgrimes if (netmask) { 4011541Srgrimes x = rn_search(netmask, rn_masktop); 4021541Srgrimes mlen = *(u_char *)netmask; 4031541Srgrimes if (Bcmp(netmask, x->rn_key, mlen) != 0) { 4041541Srgrimes x = rn_addmask(netmask, 0, top->rn_off); 4051541Srgrimes if (x == 0) 4061541Srgrimes return (0); 4071541Srgrimes } 4081541Srgrimes netmask = x->rn_key; 4091541Srgrimes b = -1 - x->rn_b; 4101541Srgrimes } 4111541Srgrimes /* 4121541Srgrimes * Deal with duplicated keys: attach node to previous instance 4131541Srgrimes */ 4141541Srgrimes saved_tt = tt = rn_insert(v, head, &keyduplicated, treenodes); 4151541Srgrimes if (keyduplicated) { 4161541Srgrimes do { 4171541Srgrimes if (tt->rn_mask == netmask) 4181541Srgrimes return (0); 4191541Srgrimes t = tt; 4201541Srgrimes if (netmask == 0 || 4211541Srgrimes (tt->rn_mask && rn_refines(netmask, tt->rn_mask))) 4221541Srgrimes break; 4231541Srgrimes } while (tt = tt->rn_dupedkey); 4241541Srgrimes /* 4251541Srgrimes * If the mask is not duplicated, we wouldn't 4261541Srgrimes * find it among possible duplicate key entries 4271541Srgrimes * anyway, so the above test doesn't hurt. 4281541Srgrimes * 4291541Srgrimes * We sort the masks for a duplicated key the same way as 4301541Srgrimes * in a masklist -- most specific to least specific. 4311541Srgrimes * This may require the unfortunate nuisance of relocating 4321541Srgrimes * the head of the list. 4331541Srgrimes */ 4341541Srgrimes if (tt && t == saved_tt) { 4351541Srgrimes struct radix_node *xx = x; 4361541Srgrimes /* link in at head of list */ 4371541Srgrimes (tt = treenodes)->rn_dupedkey = t; 4381541Srgrimes tt->rn_flags = t->rn_flags; 4391541Srgrimes tt->rn_p = x = t->rn_p; 4401541Srgrimes if (x->rn_l == t) x->rn_l = tt; else x->rn_r = tt; 4411541Srgrimes saved_tt = tt; x = xx; 4421541Srgrimes } else { 4431541Srgrimes (tt = treenodes)->rn_dupedkey = t->rn_dupedkey; 4441541Srgrimes t->rn_dupedkey = tt; 4451541Srgrimes } 4461541Srgrimes#ifdef RN_DEBUG 4471541Srgrimes t=tt+1; tt->rn_info = rn_nodenum++; t->rn_info = rn_nodenum++; 4481541Srgrimes tt->rn_twin = t; tt->rn_ybro = rn_clist; rn_clist = tt; 4491541Srgrimes#endif 4501541Srgrimes t = saved_tt; 4511541Srgrimes tt->rn_key = (caddr_t) v; 4521541Srgrimes tt->rn_b = -1; 4531541Srgrimes tt->rn_flags = t->rn_flags & ~RNF_ROOT; 4541541Srgrimes } 4551541Srgrimes /* 4561541Srgrimes * Put mask in tree. 4571541Srgrimes */ 4581541Srgrimes if (netmask) { 4591541Srgrimes tt->rn_mask = netmask; 4601541Srgrimes tt->rn_b = x->rn_b; 4611541Srgrimes } 4621541Srgrimes t = saved_tt->rn_p; 4631541Srgrimes b_leaf = -1 - t->rn_b; 4641541Srgrimes if (t->rn_r == saved_tt) x = t->rn_l; else x = t->rn_r; 4651541Srgrimes /* Promote general routes from below */ 4661541Srgrimes if (x->rn_b < 0) { 4671541Srgrimes if (x->rn_mask && (x->rn_b >= b_leaf) && x->rn_mklist == 0) { 4681541Srgrimes MKGet(m); 4691541Srgrimes if (m) { 4701541Srgrimes Bzero(m, sizeof *m); 4711541Srgrimes m->rm_b = x->rn_b; 4721541Srgrimes m->rm_mask = x->rn_mask; 4731541Srgrimes x->rn_mklist = t->rn_mklist = m; 4741541Srgrimes } 4751541Srgrimes } 4761541Srgrimes } else if (x->rn_mklist) { 4771541Srgrimes /* 4781541Srgrimes * Skip over masks whose index is > that of new node 4791541Srgrimes */ 4801541Srgrimes for (mp = &x->rn_mklist; m = *mp; mp = &m->rm_mklist) 4811541Srgrimes if (m->rm_b >= b_leaf) 4821541Srgrimes break; 4831541Srgrimes t->rn_mklist = m; *mp = 0; 4841541Srgrimes } 4851541Srgrimes /* Add new route to highest possible ancestor's list */ 4861541Srgrimes if ((netmask == 0) || (b > t->rn_b )) 4871541Srgrimes return tt; /* can't lift at all */ 4881541Srgrimes b_leaf = tt->rn_b; 4891541Srgrimes do { 4901541Srgrimes x = t; 4911541Srgrimes t = t->rn_p; 4921541Srgrimes } while (b <= t->rn_b && x != top); 4931541Srgrimes /* 4941541Srgrimes * Search through routes associated with node to 4951541Srgrimes * insert new route according to index. 4961541Srgrimes * For nodes of equal index, place more specific 4971541Srgrimes * masks first. 4981541Srgrimes */ 4991541Srgrimes cplim = netmask + mlen; 5001541Srgrimes for (mp = &x->rn_mklist; m = *mp; mp = &m->rm_mklist) { 5011541Srgrimes if (m->rm_b < b_leaf) 5021541Srgrimes continue; 5031541Srgrimes if (m->rm_b > b_leaf) 5041541Srgrimes break; 5051541Srgrimes if (m->rm_mask == netmask) { 5061541Srgrimes m->rm_refs++; 5071541Srgrimes tt->rn_mklist = m; 5081541Srgrimes return tt; 5091541Srgrimes } 5101541Srgrimes if (rn_refines(netmask, m->rm_mask)) 5111541Srgrimes break; 5121541Srgrimes } 5131541Srgrimes MKGet(m); 5141541Srgrimes if (m == 0) { 5151541Srgrimes printf("Mask for route not entered\n"); 5161541Srgrimes return (tt); 5171541Srgrimes } 5181541Srgrimes Bzero(m, sizeof *m); 5191541Srgrimes m->rm_b = b_leaf; 5201541Srgrimes m->rm_mask = netmask; 5211541Srgrimes m->rm_mklist = *mp; 5221541Srgrimes *mp = m; 5231541Srgrimes tt->rn_mklist = m; 5241541Srgrimes return tt; 5251541Srgrimes} 5261541Srgrimes 5271541Srgrimesstruct radix_node * 5281541Srgrimesrn_delete(v_arg, netmask_arg, head) 5291541Srgrimes void *v_arg, *netmask_arg; 5301541Srgrimes struct radix_node_head *head; 5311541Srgrimes{ 5321541Srgrimes register struct radix_node *t, *p, *x, *tt; 5331541Srgrimes struct radix_mask *m, *saved_m, **mp; 5341541Srgrimes struct radix_node *dupedkey, *saved_tt, *top; 5351541Srgrimes caddr_t v, netmask; 5361541Srgrimes int b, head_off, vlen; 5371541Srgrimes 5381541Srgrimes v = v_arg; 5391541Srgrimes netmask = netmask_arg; 5401541Srgrimes x = head->rnh_treetop; 5411541Srgrimes tt = rn_search(v, x); 5421541Srgrimes head_off = x->rn_off; 5431541Srgrimes vlen = *(u_char *)v; 5441541Srgrimes saved_tt = tt; 5451541Srgrimes top = x; 5461541Srgrimes if (tt == 0 || 5471541Srgrimes Bcmp(v + head_off, tt->rn_key + head_off, vlen - head_off)) 5481541Srgrimes return (0); 5491541Srgrimes /* 5501541Srgrimes * Delete our route from mask lists. 5511541Srgrimes */ 5521541Srgrimes if (dupedkey = tt->rn_dupedkey) { 5531541Srgrimes if (netmask) 5541541Srgrimes netmask = rn_search(netmask, rn_masktop)->rn_key; 5551541Srgrimes while (tt->rn_mask != netmask) 5561541Srgrimes if ((tt = tt->rn_dupedkey) == 0) 5571541Srgrimes return (0); 5581541Srgrimes } 5591541Srgrimes if (tt->rn_mask == 0 || (saved_m = m = tt->rn_mklist) == 0) 5601541Srgrimes goto on1; 5611541Srgrimes if (m->rm_mask != tt->rn_mask) { 5621541Srgrimes printf("rn_delete: inconsistent annotation\n"); 5631541Srgrimes goto on1; 5641541Srgrimes } 5651541Srgrimes if (--m->rm_refs >= 0) 5661541Srgrimes goto on1; 5671541Srgrimes b = -1 - tt->rn_b; 5681541Srgrimes t = saved_tt->rn_p; 5691541Srgrimes if (b > t->rn_b) 5701541Srgrimes goto on1; /* Wasn't lifted at all */ 5711541Srgrimes do { 5721541Srgrimes x = t; 5731541Srgrimes t = t->rn_p; 5741541Srgrimes } while (b <= t->rn_b && x != top); 5751541Srgrimes for (mp = &x->rn_mklist; m = *mp; mp = &m->rm_mklist) 5761541Srgrimes if (m == saved_m) { 5771541Srgrimes *mp = m->rm_mklist; 5781541Srgrimes MKFree(m); 5791541Srgrimes break; 5801541Srgrimes } 5811541Srgrimes if (m == 0) 5821541Srgrimes printf("rn_delete: couldn't find our annotation\n"); 5831541Srgrimeson1: 5841541Srgrimes /* 5851541Srgrimes * Eliminate us from tree 5861541Srgrimes */ 5871541Srgrimes if (tt->rn_flags & RNF_ROOT) 5881541Srgrimes return (0); 5891541Srgrimes#ifdef RN_DEBUG 5901541Srgrimes /* Get us out of the creation list */ 5911541Srgrimes for (t = rn_clist; t && t->rn_ybro != tt; t = t->rn_ybro) {} 5921541Srgrimes if (t) t->rn_ybro = tt->rn_ybro; 5931541Srgrimes#endif 5941541Srgrimes t = tt->rn_p; 5951541Srgrimes if (dupedkey) { 5961541Srgrimes if (tt == saved_tt) { 5971541Srgrimes x = dupedkey; x->rn_p = t; 5981541Srgrimes if (t->rn_l == tt) t->rn_l = x; else t->rn_r = x; 5991541Srgrimes } else { 6001541Srgrimes for (x = p = saved_tt; p && p->rn_dupedkey != tt;) 6011541Srgrimes p = p->rn_dupedkey; 6021541Srgrimes if (p) p->rn_dupedkey = tt->rn_dupedkey; 6031541Srgrimes else printf("rn_delete: couldn't find us\n"); 6041541Srgrimes } 6051541Srgrimes t = tt + 1; 6061541Srgrimes if (t->rn_flags & RNF_ACTIVE) { 6071541Srgrimes#ifndef RN_DEBUG 6081541Srgrimes *++x = *t; p = t->rn_p; 6091541Srgrimes#else 6101541Srgrimes b = t->rn_info; *++x = *t; t->rn_info = b; p = t->rn_p; 6111541Srgrimes#endif 6121541Srgrimes if (p->rn_l == t) p->rn_l = x; else p->rn_r = x; 6131541Srgrimes x->rn_l->rn_p = x; x->rn_r->rn_p = x; 6141541Srgrimes } 6151541Srgrimes goto out; 6161541Srgrimes } 6171541Srgrimes if (t->rn_l == tt) x = t->rn_r; else x = t->rn_l; 6181541Srgrimes p = t->rn_p; 6191541Srgrimes if (p->rn_r == t) p->rn_r = x; else p->rn_l = x; 6201541Srgrimes x->rn_p = p; 6211541Srgrimes /* 6221541Srgrimes * Demote routes attached to us. 6231541Srgrimes */ 6241541Srgrimes if (t->rn_mklist) { 6251541Srgrimes if (x->rn_b >= 0) { 6261541Srgrimes for (mp = &x->rn_mklist; m = *mp;) 6271541Srgrimes mp = &m->rm_mklist; 6281541Srgrimes *mp = t->rn_mklist; 6291541Srgrimes } else { 6301541Srgrimes for (m = t->rn_mklist; m;) { 6311541Srgrimes struct radix_mask *mm = m->rm_mklist; 6321541Srgrimes if (m == x->rn_mklist && (--(m->rm_refs) < 0)) { 6331541Srgrimes x->rn_mklist = 0; 6341541Srgrimes MKFree(m); 6351541Srgrimes } else 6361541Srgrimes printf("%s %x at %x\n", 6371541Srgrimes "rn_delete: Orphaned Mask", m, x); 6381541Srgrimes m = mm; 6391541Srgrimes } 6401541Srgrimes } 6411541Srgrimes } 6421541Srgrimes /* 6431541Srgrimes * We may be holding an active internal node in the tree. 6441541Srgrimes */ 6451541Srgrimes x = tt + 1; 6461541Srgrimes if (t != x) { 6471541Srgrimes#ifndef RN_DEBUG 6481541Srgrimes *t = *x; 6491541Srgrimes#else 6501541Srgrimes b = t->rn_info; *t = *x; t->rn_info = b; 6511541Srgrimes#endif 6521541Srgrimes t->rn_l->rn_p = t; t->rn_r->rn_p = t; 6531541Srgrimes p = x->rn_p; 6541541Srgrimes if (p->rn_l == x) p->rn_l = t; else p->rn_r = t; 6551541Srgrimes } 6561541Srgrimesout: 6571541Srgrimes tt->rn_flags &= ~RNF_ACTIVE; 6581541Srgrimes tt[1].rn_flags &= ~RNF_ACTIVE; 6591541Srgrimes return (tt); 6601541Srgrimes} 6611541Srgrimes 6621541Srgrimesint 6631541Srgrimesrn_walktree(h, f, w) 6641541Srgrimes struct radix_node_head *h; 6651541Srgrimes register int (*f)(); 6661541Srgrimes void *w; 6671541Srgrimes{ 6681541Srgrimes int error; 6691541Srgrimes struct radix_node *base, *next; 6701541Srgrimes register struct radix_node *rn = h->rnh_treetop; 6711541Srgrimes /* 6721541Srgrimes * This gets complicated because we may delete the node 6731541Srgrimes * while applying the function f to it, so we need to calculate 6741541Srgrimes * the successor node in advance. 6751541Srgrimes */ 6761541Srgrimes /* First time through node, go left */ 6771541Srgrimes while (rn->rn_b >= 0) 6781541Srgrimes rn = rn->rn_l; 6791541Srgrimes for (;;) { 6801541Srgrimes base = rn; 6811541Srgrimes /* If at right child go back up, otherwise, go right */ 6821541Srgrimes while (rn->rn_p->rn_r == rn && (rn->rn_flags & RNF_ROOT) == 0) 6831541Srgrimes rn = rn->rn_p; 6841541Srgrimes /* Find the next *leaf* since next node might vanish, too */ 6851541Srgrimes for (rn = rn->rn_p->rn_r; rn->rn_b >= 0;) 6861541Srgrimes rn = rn->rn_l; 6871541Srgrimes next = rn; 6881541Srgrimes /* Process leaves */ 6891541Srgrimes while (rn = base) { 6901541Srgrimes base = rn->rn_dupedkey; 6911541Srgrimes if (!(rn->rn_flags & RNF_ROOT) && (error = (*f)(rn, w))) 6921541Srgrimes return (error); 6931541Srgrimes } 6941541Srgrimes rn = next; 6951541Srgrimes if (rn->rn_flags & RNF_ROOT) 6961541Srgrimes return (0); 6971541Srgrimes } 6981541Srgrimes /* NOTREACHED */ 6991541Srgrimes} 7001541Srgrimes 7011541Srgrimesint 7021541Srgrimesrn_inithead(head, off) 7031541Srgrimes void **head; 7041541Srgrimes int off; 7051541Srgrimes{ 7061541Srgrimes register struct radix_node_head *rnh; 7071541Srgrimes register struct radix_node *t, *tt, *ttt; 7081541Srgrimes if (*head) 7091541Srgrimes return (1); 7101541Srgrimes R_Malloc(rnh, struct radix_node_head *, sizeof (*rnh)); 7111541Srgrimes if (rnh == 0) 7121541Srgrimes return (0); 7131541Srgrimes Bzero(rnh, sizeof (*rnh)); 7141541Srgrimes *head = rnh; 7151541Srgrimes t = rn_newpair(rn_zeros, off, rnh->rnh_nodes); 7161541Srgrimes ttt = rnh->rnh_nodes + 2; 7171541Srgrimes t->rn_r = ttt; 7181541Srgrimes t->rn_p = t; 7191541Srgrimes tt = t->rn_l; 7201541Srgrimes tt->rn_flags = t->rn_flags = RNF_ROOT | RNF_ACTIVE; 7211541Srgrimes tt->rn_b = -1 - off; 7221541Srgrimes *ttt = *tt; 7231541Srgrimes ttt->rn_key = rn_ones; 7241541Srgrimes rnh->rnh_addaddr = rn_addroute; 7251541Srgrimes rnh->rnh_deladdr = rn_delete; 7261541Srgrimes rnh->rnh_matchaddr = rn_match; 7271541Srgrimes rnh->rnh_walktree = rn_walktree; 7281541Srgrimes rnh->rnh_treetop = t; 7291541Srgrimes return (1); 7301541Srgrimes} 7311541Srgrimes 7321541Srgrimesvoid 7331541Srgrimesrn_init() 7341541Srgrimes{ 7351541Srgrimes char *cp, *cplim; 7361541Srgrimes#ifdef KERNEL 7371541Srgrimes struct domain *dom; 7381541Srgrimes 7391541Srgrimes for (dom = domains; dom; dom = dom->dom_next) 7401541Srgrimes if (dom->dom_maxrtkey > max_keylen) 7411541Srgrimes max_keylen = dom->dom_maxrtkey; 7421541Srgrimes#endif 7431541Srgrimes if (max_keylen == 0) { 7441541Srgrimes printf("rn_init: radix functions require max_keylen be set\n"); 7451541Srgrimes return; 7461541Srgrimes } 7471541Srgrimes R_Malloc(rn_zeros, char *, 3 * max_keylen); 7481541Srgrimes if (rn_zeros == NULL) 7491541Srgrimes panic("rn_init"); 7501541Srgrimes Bzero(rn_zeros, 3 * max_keylen); 7511541Srgrimes rn_ones = cp = rn_zeros + max_keylen; 7521541Srgrimes maskedKey = cplim = rn_ones + max_keylen; 7531541Srgrimes while (cp < cplim) 7541541Srgrimes *cp++ = -1; 7551541Srgrimes if (rn_inithead((void **)&mask_rnhead, 0) == 0) 7561541Srgrimes panic("rn_init 2"); 7571541Srgrimes} 758