radix.c revision 256281
1130803Smarcel/* 2130803Smarcel * Copyright (c) 1988, 1989, 1993 3130803Smarcel * The Regents of the University of California. All rights reserved. 4130803Smarcel * 5130803Smarcel * Redistribution and use in source and binary forms, with or without 6130803Smarcel * modification, are permitted provided that the following conditions 7130803Smarcel * are met: 8130803Smarcel * 1. Redistributions of source code must retain the above copyright 9130803Smarcel * notice, this list of conditions and the following disclaimer. 10130803Smarcel * 2. Redistributions in binary form must reproduce the above copyright 11130803Smarcel * notice, this list of conditions and the following disclaimer in the 12130803Smarcel * documentation and/or other materials provided with the distribution. 13130803Smarcel * 4. Neither the name of the University nor the names of its contributors 14130803Smarcel * may be used to endorse or promote products derived from this software 15130803Smarcel * without specific prior written permission. 16130803Smarcel * 17130803Smarcel * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 18130803Smarcel * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 19130803Smarcel * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 20130803Smarcel * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 21130803Smarcel * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 22130803Smarcel * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 23130803Smarcel * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 24130803Smarcel * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 25130803Smarcel * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 26130803Smarcel * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 27130803Smarcel * SUCH DAMAGE. 28130803Smarcel * 29130803Smarcel * @(#)radix.c 8.4 (Berkeley) 11/2/94 30130803Smarcel * 31130803Smarcel * $FreeBSD: stable/10/sbin/routed/radix.c 229778 2012-01-07 16:09:33Z uqs $ 32130803Smarcel */ 33130803Smarcel 34130803Smarcel/* 35130803Smarcel * Routines to build and maintain radix trees for routing lookups. 36130803Smarcel */ 37130803Smarcel 38130803Smarcel#include "defs.h" 39130803Smarcel 40130803Smarcel#ifdef __NetBSD__ 41130803Smarcel__RCSID("$NetBSD$"); 42130803Smarcel#elif defined(__FreeBSD__) 43130803Smarcel__RCSID("$FreeBSD: stable/10/sbin/routed/radix.c 229778 2012-01-07 16:09:33Z uqs $"); 44130803Smarcel#else 45130803Smarcel__RCSID("$Revision: 2.23 $"); 46130803Smarcel#ident "$Revision: 2.23 $" 47130803Smarcel#endif 48130803Smarcel 49130803Smarcel#define log(x, msg) syslog(x, msg) 50130803Smarcel#define panic(s) {log(LOG_ERR,s); exit(1);} 51130803Smarcel#define min(a,b) (((a)<(b))?(a):(b)) 52130803Smarcel 53130803Smarcelint max_keylen; 54130803Smarcelstatic struct radix_mask *rn_mkfreelist; 55130803Smarcelstatic struct radix_node_head *mask_rnhead; 56130803Smarcelstatic char *addmask_key; 57130803Smarcelstatic const uint8_t normal_chars[] = 58130803Smarcel { 0, 0x80, 0xc0, 0xe0, 0xf0, 0xf8, 0xfc, 0xfe, 0xff}; 59130803Smarcelstatic char *rn_zeros, *rn_ones; 60130803Smarcel 61130803Smarcel#define rn_masktop (mask_rnhead->rnh_treetop) 62130803Smarcel#define Bcmp(a, b, l) (l == 0 ? 0 \ 63130803Smarcel : memcmp((caddr_t)(a), (caddr_t)(b), (size_t)l)) 64130803Smarcel 65130803Smarcelstatic int rn_satisfies_leaf(char *, struct radix_node *, int); 66130803Smarcelstatic struct radix_node *rn_addmask(void *n_arg, int search, int skip); 67130803Smarcelstatic struct radix_node *rn_addroute(void *v_arg, void *n_arg, 68130803Smarcel struct radix_node_head *head, struct radix_node treenodes[2]); 69130803Smarcelstatic struct radix_node *rn_match(void *v_arg, struct radix_node_head *head); 70130803Smarcel 71130803Smarcel/* 72130803Smarcel * The data structure for the keys is a radix tree with one way 73130803Smarcel * branching removed. The index rn_b at an internal node n represents a bit 74130803Smarcel * position to be tested. The tree is arranged so that all descendants 75130803Smarcel * of a node n have keys whose bits all agree up to position rn_b - 1. 76130803Smarcel * (We say the index of n is rn_b.) 77130803Smarcel * 78130803Smarcel * There is at least one descendant which has a one bit at position rn_b, 79130803Smarcel * and at least one with a zero there. 80130803Smarcel * 81130803Smarcel * A route is determined by a pair of key and mask. We require that the 82130803Smarcel * bit-wise logical and of the key and mask to be the key. 83130803Smarcel * We define the index of a route to associated with the mask to be 84130803Smarcel * the first bit number in the mask where 0 occurs (with bit number 0 85130803Smarcel * representing the highest order bit). 86130803Smarcel * 87130803Smarcel * We say a mask is normal if every bit is 0, past the index of the mask. 88130803Smarcel * If a node n has a descendant (k, m) with index(m) == index(n) == rn_b, 89130803Smarcel * and m is a normal mask, then the route applies to every descendant of n. 90130803Smarcel * If the index(m) < rn_b, this implies the trailing last few bits of k 91130803Smarcel * before bit b are all 0, (and hence consequently true of every descendant 92130803Smarcel * of n), so the route applies to all descendants of the node as well. 93130803Smarcel * 94130803Smarcel * Similar logic shows that a non-normal mask m such that 95130803Smarcel * index(m) <= index(n) could potentially apply to many children of n. 96130803Smarcel * Thus, for each non-host route, we attach its mask to a list at an internal 97130803Smarcel * node as high in the tree as we can go. 98130803Smarcel * 99130803Smarcel * The present version of the code makes use of normal routes in short- 100130803Smarcel * circuiting an explicit mask and compare operation when testing whether 101130803Smarcel * a key satisfies a normal route, and also in remembering the unique leaf 102130803Smarcel * that governs a subtree. 103130803Smarcel */ 104130803Smarcel 105130803Smarcelstatic struct radix_node * 106130803Smarcelrn_search(void *v_arg, 107130803Smarcel struct radix_node *head) 108130803Smarcel{ 109130803Smarcel struct radix_node *x; 110130803Smarcel caddr_t v; 111130803Smarcel 112130803Smarcel for (x = head, v = v_arg; x->rn_b >= 0;) { 113130803Smarcel if (x->rn_bmask & v[x->rn_off]) 114130803Smarcel x = x->rn_r; 115130803Smarcel else 116130803Smarcel x = x->rn_l; 117130803Smarcel } 118130803Smarcel return (x); 119130803Smarcel} 120130803Smarcel 121130803Smarcelstatic struct radix_node * 122130803Smarcelrn_search_m(void *v_arg, 123130803Smarcel struct radix_node *head, 124130803Smarcel void *m_arg) 125130803Smarcel{ 126130803Smarcel struct radix_node *x; 127130803Smarcel caddr_t v = v_arg, m = m_arg; 128130803Smarcel 129130803Smarcel for (x = head; x->rn_b >= 0;) { 130130803Smarcel if ((x->rn_bmask & m[x->rn_off]) && 131130803Smarcel (x->rn_bmask & v[x->rn_off])) 132130803Smarcel x = x->rn_r; 133130803Smarcel else 134130803Smarcel x = x->rn_l; 135130803Smarcel } 136130803Smarcel return x; 137130803Smarcel} 138130803Smarcel 139130803Smarcelstatic int 140130803Smarcelrn_refines(void* m_arg, void *n_arg) 141130803Smarcel{ 142130803Smarcel caddr_t m = m_arg, n = n_arg; 143130803Smarcel caddr_t lim, lim2 = lim = n + *(u_char *)n; 144130803Smarcel int longer = (*(u_char *)n++) - (int)(*(u_char *)m++); 145130803Smarcel int masks_are_equal = 1; 146130803Smarcel 147130803Smarcel if (longer > 0) 148130803Smarcel lim -= longer; 149130803Smarcel while (n < lim) { 150130803Smarcel if (*n & ~(*m)) 151130803Smarcel return 0; 152130803Smarcel if (*n++ != *m++) 153130803Smarcel masks_are_equal = 0; 154130803Smarcel } 155130803Smarcel while (n < lim2) 156130803Smarcel if (*n++) 157130803Smarcel return 0; 158130803Smarcel if (masks_are_equal && (longer < 0)) 159130803Smarcel for (lim2 = m - longer; m < lim2; ) 160130803Smarcel if (*m++) 161130803Smarcel return 1; 162130803Smarcel return (!masks_are_equal); 163130803Smarcel} 164130803Smarcel 165130803Smarcelstatic struct radix_node * 166130803Smarcelrn_lookup(void *v_arg, void *m_arg, struct radix_node_head *head) 167130803Smarcel{ 168130803Smarcel struct radix_node *x; 169130803Smarcel caddr_t netmask = 0; 170130803Smarcel 171130803Smarcel if (m_arg) { 172130803Smarcel if ((x = rn_addmask(m_arg, 1, head->rnh_treetop->rn_off)) == 0) 173130803Smarcel return (0); 174130803Smarcel netmask = x->rn_key; 175130803Smarcel } 176130803Smarcel x = rn_match(v_arg, head); 177130803Smarcel if (x && netmask) { 178130803Smarcel while (x && x->rn_mask != netmask) 179130803Smarcel x = x->rn_dupedkey; 180130803Smarcel } 181130803Smarcel return x; 182130803Smarcel} 183130803Smarcel 184130803Smarcelstatic int 185130803Smarcelrn_satisfies_leaf(char *trial, 186130803Smarcel struct radix_node *leaf, 187130803Smarcel int skip) 188130803Smarcel{ 189130803Smarcel char *cp = trial, *cp2 = leaf->rn_key, *cp3 = leaf->rn_mask; 190130803Smarcel char *cplim; 191130803Smarcel int length = min(*(u_char *)cp, *(u_char *)cp2); 192130803Smarcel 193130803Smarcel if (cp3 == 0) 194130803Smarcel cp3 = rn_ones; 195130803Smarcel else 196130803Smarcel length = min(length, *(u_char *)cp3); 197130803Smarcel cplim = cp + length; cp3 += skip; cp2 += skip; 198130803Smarcel for (cp += skip; cp < cplim; cp++, cp2++, cp3++) 199130803Smarcel if ((*cp ^ *cp2) & *cp3) 200130803Smarcel return 0; 201130803Smarcel return 1; 202130803Smarcel} 203130803Smarcel 204130803Smarcelstatic struct radix_node * 205130803Smarcelrn_match(void *v_arg, 206130803Smarcel struct radix_node_head *head) 207130803Smarcel{ 208130803Smarcel caddr_t v = v_arg; 209130803Smarcel struct radix_node *t = head->rnh_treetop, *x; 210130803Smarcel caddr_t cp = v, cp2; 211130803Smarcel caddr_t cplim; 212130803Smarcel struct radix_node *saved_t, *top = t; 213130803Smarcel int off = t->rn_off, vlen = *(u_char *)cp, matched_off; 214130803Smarcel int test, b, rn_b; 215130803Smarcel 216130803Smarcel /* 217130803Smarcel * Open code rn_search(v, top) to avoid overhead of extra 218130803Smarcel * subroutine call. 219130803Smarcel */ 220130803Smarcel for (; t->rn_b >= 0; ) { 221130803Smarcel if (t->rn_bmask & cp[t->rn_off]) 222130803Smarcel t = t->rn_r; 223130803Smarcel else 224130803Smarcel t = t->rn_l; 225130803Smarcel } 226130803Smarcel /* 227130803Smarcel * See if we match exactly as a host destination 228130803Smarcel * or at least learn how many bits match, for normal mask finesse. 229130803Smarcel * 230130803Smarcel * It doesn't hurt us to limit how many bytes to check 231130803Smarcel * to the length of the mask, since if it matches we had a genuine 232130803Smarcel * match and the leaf we have is the most specific one anyway; 233130803Smarcel * if it didn't match with a shorter length it would fail 234130803Smarcel * with a long one. This wins big for class B&C netmasks which 235130803Smarcel * are probably the most common case... 236130803Smarcel */ 237130803Smarcel if (t->rn_mask) 238130803Smarcel vlen = *(u_char *)t->rn_mask; 239130803Smarcel cp += off; cp2 = t->rn_key + off; cplim = v + vlen; 240130803Smarcel for (; cp < cplim; cp++, cp2++) 241130803Smarcel if (*cp != *cp2) 242130803Smarcel goto on1; 243130803Smarcel /* 244130803Smarcel * This extra grot is in case we are explicitly asked 245130803Smarcel * to look up the default. Ugh! 246130803Smarcel * Or 255.255.255.255 247130803Smarcel * 248130803Smarcel * In this case, we have a complete match of the key. Unless 249130803Smarcel * the node is one of the roots, we are finished. 250130803Smarcel * If it is the zeros root, then take what we have, preferring 251130803Smarcel * any real data. 252130803Smarcel * If it is the ones root, then pretend the target key was followed 253130803Smarcel * by a byte of zeros. 254130803Smarcel */ 255130803Smarcel if (!(t->rn_flags & RNF_ROOT)) 256130803Smarcel return t; /* not a root */ 257130803Smarcel if (t->rn_dupedkey) { 258130803Smarcel t = t->rn_dupedkey; 259130803Smarcel return t; /* have some real data */ 260130803Smarcel } 261130803Smarcel if (*(cp-1) == 0) 262130803Smarcel return t; /* not the ones root */ 263130803Smarcel b = 0; /* fake a zero after 255.255.255.255 */ 264130803Smarcel goto on2; 265130803Smarcelon1: 266130803Smarcel test = (*cp ^ *cp2) & 0xff; /* find first bit that differs */ 267130803Smarcel for (b = 7; (test >>= 1) > 0;) 268130803Smarcel b--; 269130803Smarcelon2: 270130803Smarcel matched_off = cp - v; 271130803Smarcel b += matched_off << 3; 272130803Smarcel rn_b = -1 - b; 273130803Smarcel /* 274130803Smarcel * If there is a host route in a duped-key chain, it will be first. 275130803Smarcel */ 276130803Smarcel if ((saved_t = t)->rn_mask == 0) 277130803Smarcel t = t->rn_dupedkey; 278130803Smarcel for (; t; t = t->rn_dupedkey) { 279130803Smarcel /* 280130803Smarcel * Even if we don't match exactly as a host, 281130803Smarcel * we may match if the leaf we wound up at is 282130803Smarcel * a route to a net. 283130803Smarcel */ 284130803Smarcel if (t->rn_flags & RNF_NORMAL) { 285130803Smarcel if (rn_b <= t->rn_b) 286130803Smarcel return t; 287130803Smarcel } else if (rn_satisfies_leaf(v, t, matched_off)) { 288130803Smarcel return t; 289130803Smarcel } 290130803Smarcel } 291130803Smarcel t = saved_t; 292130803Smarcel /* start searching up the tree */ 293130803Smarcel do { 294130803Smarcel struct radix_mask *m; 295130803Smarcel t = t->rn_p; 296130803Smarcel if ((m = t->rn_mklist)) { 297130803Smarcel /* 298130803Smarcel * If non-contiguous masks ever become important 299130803Smarcel * we can restore the masking and open coding of 300130803Smarcel * the search and satisfaction test and put the 301130803Smarcel * calculation of "off" back before the "do". 302130803Smarcel */ 303130803Smarcel do { 304130803Smarcel if (m->rm_flags & RNF_NORMAL) { 305130803Smarcel if (rn_b <= m->rm_b) 306130803Smarcel return (m->rm_leaf); 307130803Smarcel } else { 308130803Smarcel off = min(t->rn_off, matched_off); 309130803Smarcel x = rn_search_m(v, t, m->rm_mask); 310130803Smarcel while (x && x->rn_mask != m->rm_mask) 311130803Smarcel x = x->rn_dupedkey; 312130803Smarcel if (x && rn_satisfies_leaf(v, x, off)) 313130803Smarcel return x; 314130803Smarcel } 315130803Smarcel } while ((m = m->rm_mklist)); 316130803Smarcel } 317130803Smarcel } while (t != top); 318130803Smarcel return 0; 319130803Smarcel} 320130803Smarcel 321130803Smarcel#ifdef RN_DEBUG 322130803Smarcelint rn_nodenum; 323130803Smarcelstruct radix_node *rn_clist; 324130803Smarcelint rn_saveinfo; 325130803Smarcelint rn_debug = 1; 326130803Smarcel#endif 327130803Smarcel 328130803Smarcelstatic struct radix_node * 329130803Smarcelrn_newpair(void *v, int b, struct radix_node nodes[2]) 330130803Smarcel{ 331130803Smarcel struct radix_node *tt = nodes, *t = tt + 1; 332130803Smarcel t->rn_b = b; t->rn_bmask = 0x80 >> (b & 7); 333130803Smarcel t->rn_l = tt; t->rn_off = b >> 3; 334130803Smarcel tt->rn_b = -1; tt->rn_key = (caddr_t)v; tt->rn_p = t; 335130803Smarcel tt->rn_flags = t->rn_flags = RNF_ACTIVE; 336130803Smarcel#ifdef RN_DEBUG 337130803Smarcel tt->rn_info = rn_nodenum++; t->rn_info = rn_nodenum++; 338130803Smarcel tt->rn_twin = t; tt->rn_ybro = rn_clist; rn_clist = tt; 339130803Smarcel#endif 340130803Smarcel return t; 341130803Smarcel} 342130803Smarcel 343130803Smarcelstatic struct radix_node * 344130803Smarcelrn_insert(void* v_arg, 345130803Smarcel struct radix_node_head *head, 346130803Smarcel int *dupentry, 347130803Smarcel struct radix_node nodes[2]) 348130803Smarcel{ 349130803Smarcel caddr_t v = v_arg; 350130803Smarcel struct radix_node *top = head->rnh_treetop; 351130803Smarcel int head_off = top->rn_off, vlen = (int)*((u_char *)v); 352130803Smarcel struct radix_node *t = rn_search(v_arg, top); 353130803Smarcel caddr_t cp = v + head_off; 354130803Smarcel int b; 355130803Smarcel struct radix_node *tt; 356130803Smarcel 357130803Smarcel /* 358130803Smarcel * Find first bit at which v and t->rn_key differ 359130803Smarcel */ 360130803Smarcel { 361130803Smarcel caddr_t cp2 = t->rn_key + head_off; 362130803Smarcel int cmp_res; 363130803Smarcel caddr_t cplim = v + vlen; 364130803Smarcel 365130803Smarcel while (cp < cplim) 366130803Smarcel if (*cp2++ != *cp++) 367130803Smarcel goto on1; 368130803Smarcel /* handle adding 255.255.255.255 */ 369130803Smarcel if (!(t->rn_flags & RNF_ROOT) || *(cp2-1) == 0) { 370130803Smarcel *dupentry = 1; 371130803Smarcel return t; 372130803Smarcel } 373130803Smarcelon1: 374130803Smarcel *dupentry = 0; 375130803Smarcel cmp_res = (cp[-1] ^ cp2[-1]) & 0xff; 376130803Smarcel for (b = (cp - v) << 3; cmp_res; b--) 377130803Smarcel cmp_res >>= 1; 378130803Smarcel } 379130803Smarcel { 380130803Smarcel struct radix_node *p, *x = top; 381130803Smarcel cp = v; 382130803Smarcel do { 383130803Smarcel p = x; 384130803Smarcel if (cp[x->rn_off] & x->rn_bmask) 385130803Smarcel x = x->rn_r; 386130803Smarcel else x = x->rn_l; 387130803Smarcel } while ((unsigned)b > (unsigned)x->rn_b); 388130803Smarcel#ifdef RN_DEBUG 389130803Smarcel if (rn_debug) 390130803Smarcel log(LOG_DEBUG, "rn_insert: Going In:\n"), traverse(p); 391130803Smarcel#endif 392130803Smarcel t = rn_newpair(v_arg, b, nodes); tt = t->rn_l; 393130803Smarcel if ((cp[p->rn_off] & p->rn_bmask) == 0) 394130803Smarcel p->rn_l = t; 395130803Smarcel else 396130803Smarcel p->rn_r = t; 397130803Smarcel x->rn_p = t; t->rn_p = p; /* frees x, p as temp vars below */ 398130803Smarcel if ((cp[t->rn_off] & t->rn_bmask) == 0) { 399130803Smarcel t->rn_r = x; 400130803Smarcel } else { 401130803Smarcel t->rn_r = tt; t->rn_l = x; 402130803Smarcel } 403130803Smarcel#ifdef RN_DEBUG 404130803Smarcel if (rn_debug) 405130803Smarcel log(LOG_DEBUG, "rn_insert: Coming Out:\n"), traverse(p); 406130803Smarcel#endif 407130803Smarcel } 408130803Smarcel return (tt); 409130803Smarcel} 410130803Smarcel 411130803Smarcelstatic struct radix_node * 412130803Smarcelrn_addmask(void *n_arg, int search, int skip) 413130803Smarcel{ 414130803Smarcel caddr_t netmask = (caddr_t)n_arg; 415130803Smarcel struct radix_node *x; 416130803Smarcel caddr_t cp, cplim; 417130803Smarcel int b = 0, mlen, j; 418130803Smarcel int maskduplicated, m0, isnormal; 419130803Smarcel struct radix_node *saved_x; 420130803Smarcel static int last_zeroed = 0; 421130803Smarcel 422130803Smarcel if ((mlen = *(u_char *)netmask) > max_keylen) 423130803Smarcel mlen = max_keylen; 424130803Smarcel if (skip == 0) 425130803Smarcel skip = 1; 426130803Smarcel if (mlen <= skip) 427130803Smarcel return (mask_rnhead->rnh_nodes); 428130803Smarcel if (skip > 1) 429130803Smarcel Bcopy(rn_ones + 1, addmask_key + 1, skip - 1); 430130803Smarcel if ((m0 = mlen) > skip) 431130803Smarcel Bcopy(netmask + skip, addmask_key + skip, mlen - skip); 432130803Smarcel /* 433130803Smarcel * Trim trailing zeroes. 434130803Smarcel */ 435130803Smarcel for (cp = addmask_key + mlen; (cp > addmask_key) && cp[-1] == 0;) 436130803Smarcel cp--; 437130803Smarcel mlen = cp - addmask_key; 438130803Smarcel if (mlen <= skip) { 439130803Smarcel if (m0 >= last_zeroed) 440130803Smarcel last_zeroed = mlen; 441130803Smarcel return (mask_rnhead->rnh_nodes); 442130803Smarcel } 443130803Smarcel if (m0 < last_zeroed) 444130803Smarcel Bzero(addmask_key + m0, last_zeroed - m0); 445130803Smarcel *addmask_key = last_zeroed = mlen; 446130803Smarcel x = rn_search(addmask_key, rn_masktop); 447130803Smarcel if (Bcmp(addmask_key, x->rn_key, mlen) != 0) 448130803Smarcel x = 0; 449130803Smarcel if (x || search) 450130803Smarcel return (x); 451130803Smarcel x = (struct radix_node *)rtmalloc(max_keylen + 2*sizeof(*x), 452130803Smarcel "rn_addmask"); 453130803Smarcel saved_x = x; 454130803Smarcel Bzero(x, max_keylen + 2 * sizeof (*x)); 455130803Smarcel netmask = cp = (caddr_t)(x + 2); 456130803Smarcel Bcopy(addmask_key, cp, mlen); 457130803Smarcel x = rn_insert(cp, mask_rnhead, &maskduplicated, x); 458130803Smarcel if (maskduplicated) { 459130803Smarcel log(LOG_ERR, "rn_addmask: mask impossibly already in tree"); 460130803Smarcel Free(saved_x); 461130803Smarcel return (x); 462130803Smarcel } 463130803Smarcel /* 464130803Smarcel * Calculate index of mask, and check for normalcy. 465130803Smarcel */ 466130803Smarcel cplim = netmask + mlen; isnormal = 1; 467130803Smarcel for (cp = netmask + skip; (cp < cplim) && *(u_char *)cp == 0xff;) 468130803Smarcel cp++; 469130803Smarcel if (cp != cplim) { 470130803Smarcel for (j = 0x80; (j & *cp) != 0; j >>= 1) 471130803Smarcel b++; 472130803Smarcel if (*cp != normal_chars[b] || cp != (cplim - 1)) 473130803Smarcel isnormal = 0; 474130803Smarcel } 475130803Smarcel b += (cp - netmask) << 3; 476130803Smarcel x->rn_b = -1 - b; 477130803Smarcel if (isnormal) 478130803Smarcel x->rn_flags |= RNF_NORMAL; 479130803Smarcel return (x); 480130803Smarcel} 481130803Smarcel 482130803Smarcelstatic int /* XXX: arbitrary ordering for non-contiguous masks */ 483130803Smarcelrn_lexobetter(void *m_arg, void *n_arg) 484130803Smarcel{ 485130803Smarcel u_char *mp = m_arg, *np = n_arg, *lim; 486130803Smarcel 487130803Smarcel if (*mp > *np) 488130803Smarcel return 1; /* not really, but need to check longer one first */ 489130803Smarcel if (*mp == *np) 490130803Smarcel for (lim = mp + *mp; mp < lim;) 491130803Smarcel if (*mp++ > *np++) 492130803Smarcel return 1; 493130803Smarcel return 0; 494130803Smarcel} 495130803Smarcel 496130803Smarcelstatic struct radix_mask * 497130803Smarcelrn_new_radix_mask(struct radix_node *tt, 498130803Smarcel struct radix_mask *next) 499130803Smarcel{ 500130803Smarcel struct radix_mask *m; 501130803Smarcel 502130803Smarcel MKGet(m); 503130803Smarcel if (m == 0) { 504130803Smarcel log(LOG_ERR, "Mask for route not entered\n"); 505130803Smarcel return (0); 506130803Smarcel } 507130803Smarcel Bzero(m, sizeof *m); 508130803Smarcel m->rm_b = tt->rn_b; 509130803Smarcel m->rm_flags = tt->rn_flags; 510130803Smarcel if (tt->rn_flags & RNF_NORMAL) 511130803Smarcel m->rm_leaf = tt; 512130803Smarcel else 513130803Smarcel m->rm_mask = tt->rn_mask; 514130803Smarcel m->rm_mklist = next; 515130803Smarcel tt->rn_mklist = m; 516130803Smarcel return m; 517130803Smarcel} 518130803Smarcel 519130803Smarcelstatic struct radix_node * 520130803Smarcelrn_addroute(void *v_arg, 521130803Smarcel void *n_arg, 522130803Smarcel struct radix_node_head *head, 523130803Smarcel struct radix_node treenodes[2]) 524130803Smarcel{ 525130803Smarcel caddr_t v = (caddr_t)v_arg, netmask = (caddr_t)n_arg; 526130803Smarcel struct radix_node *t, *x = 0, *tt; 527130803Smarcel struct radix_node *saved_tt, *top = head->rnh_treetop; 528130803Smarcel short b = 0, b_leaf = 0; 529130803Smarcel int keyduplicated; 530130803Smarcel caddr_t mmask; 531130803Smarcel struct radix_mask *m, **mp; 532130803Smarcel 533130803Smarcel /* 534130803Smarcel * In dealing with non-contiguous masks, there may be 535130803Smarcel * many different routes which have the same mask. 536130803Smarcel * We will find it useful to have a unique pointer to 537130803Smarcel * the mask to speed avoiding duplicate references at 538130803Smarcel * nodes and possibly save time in calculating indices. 539130803Smarcel */ 540130803Smarcel if (netmask) { 541130803Smarcel if ((x = rn_addmask(netmask, 0, top->rn_off)) == 0) 542130803Smarcel return (0); 543130803Smarcel b_leaf = x->rn_b; 544130803Smarcel b = -1 - x->rn_b; 545130803Smarcel netmask = x->rn_key; 546130803Smarcel } 547130803Smarcel /* 548130803Smarcel * Deal with duplicated keys: attach node to previous instance 549130803Smarcel */ 550130803Smarcel saved_tt = tt = rn_insert(v, head, &keyduplicated, treenodes); 551130803Smarcel if (keyduplicated) { 552130803Smarcel for (t = tt; tt; t = tt, tt = tt->rn_dupedkey) { 553130803Smarcel if (tt->rn_mask == netmask) 554130803Smarcel return (0); 555130803Smarcel if (netmask == 0 || 556130803Smarcel (tt->rn_mask && 557130803Smarcel ((b_leaf < tt->rn_b) || /* index(netmask) > node */ 558130803Smarcel rn_refines(netmask, tt->rn_mask) || 559130803Smarcel rn_lexobetter(netmask, tt->rn_mask)))) 560130803Smarcel break; 561130803Smarcel } 562130803Smarcel /* 563130803Smarcel * If the mask is not duplicated, we wouldn't 564130803Smarcel * find it among possible duplicate key entries 565130803Smarcel * anyway, so the above test doesn't hurt. 566130803Smarcel * 567130803Smarcel * We sort the masks for a duplicated key the same way as 568130803Smarcel * in a masklist -- most specific to least specific. 569130803Smarcel * This may require the unfortunate nuisance of relocating 570130803Smarcel * the head of the list. 571130803Smarcel */ 572130803Smarcel if (tt == saved_tt) { 573130803Smarcel struct radix_node *xx = x; 574130803Smarcel /* link in at head of list */ 575130803Smarcel (tt = treenodes)->rn_dupedkey = t; 576130803Smarcel tt->rn_flags = t->rn_flags; 577130803Smarcel tt->rn_p = x = t->rn_p; 578130803Smarcel if (x->rn_l == t) x->rn_l = tt; else x->rn_r = tt; 579130803Smarcel saved_tt = tt; x = xx; 580130803Smarcel } else { 581130803Smarcel (tt = treenodes)->rn_dupedkey = t->rn_dupedkey; 582130803Smarcel t->rn_dupedkey = tt; 583130803Smarcel } 584130803Smarcel#ifdef RN_DEBUG 585130803Smarcel t=tt+1; tt->rn_info = rn_nodenum++; t->rn_info = rn_nodenum++; 586130803Smarcel tt->rn_twin = t; tt->rn_ybro = rn_clist; rn_clist = tt; 587130803Smarcel#endif 588130803Smarcel tt->rn_key = (caddr_t) v; 589130803Smarcel tt->rn_b = -1; 590130803Smarcel tt->rn_flags = RNF_ACTIVE; 591130803Smarcel } 592130803Smarcel /* 593130803Smarcel * Put mask in tree. 594130803Smarcel */ 595130803Smarcel if (netmask) { 596130803Smarcel tt->rn_mask = netmask; 597130803Smarcel tt->rn_b = x->rn_b; 598130803Smarcel tt->rn_flags |= x->rn_flags & RNF_NORMAL; 599130803Smarcel } 600130803Smarcel t = saved_tt->rn_p; 601130803Smarcel if (keyduplicated) 602130803Smarcel goto on2; 603130803Smarcel b_leaf = -1 - t->rn_b; 604130803Smarcel if (t->rn_r == saved_tt) x = t->rn_l; else x = t->rn_r; 605130803Smarcel /* Promote general routes from below */ 606130803Smarcel if (x->rn_b < 0) { 607130803Smarcel for (mp = &t->rn_mklist; x; x = x->rn_dupedkey) 608130803Smarcel if (x->rn_mask && (x->rn_b >= b_leaf) && x->rn_mklist == 0) { 609130803Smarcel if ((*mp = m = rn_new_radix_mask(x, 0))) 610130803Smarcel mp = &m->rm_mklist; 611130803Smarcel } 612130803Smarcel } else if (x->rn_mklist) { 613130803Smarcel /* 614130803Smarcel * Skip over masks whose index is > that of new node 615130803Smarcel */ 616130803Smarcel for (mp = &x->rn_mklist; (m = *mp); mp = &m->rm_mklist) 617130803Smarcel if (m->rm_b >= b_leaf) 618130803Smarcel break; 619130803Smarcel t->rn_mklist = m; *mp = 0; 620130803Smarcel } 621130803Smarcelon2: 622130803Smarcel /* Add new route to highest possible ancestor's list */ 623130803Smarcel if ((netmask == 0) || (b > t->rn_b )) 624130803Smarcel return tt; /* can't lift at all */ 625130803Smarcel b_leaf = tt->rn_b; 626130803Smarcel do { 627130803Smarcel x = t; 628130803Smarcel t = t->rn_p; 629130803Smarcel } while (b <= t->rn_b && x != top); 630130803Smarcel /* 631130803Smarcel * Search through routes associated with node to 632130803Smarcel * insert new route according to index. 633130803Smarcel * Need same criteria as when sorting dupedkeys to avoid 634130803Smarcel * double loop on deletion. 635130803Smarcel */ 636130803Smarcel for (mp = &x->rn_mklist; (m = *mp); mp = &m->rm_mklist) { 637130803Smarcel if (m->rm_b < b_leaf) 638130803Smarcel continue; 639130803Smarcel if (m->rm_b > b_leaf) 640130803Smarcel break; 641130803Smarcel if (m->rm_flags & RNF_NORMAL) { 642130803Smarcel mmask = m->rm_leaf->rn_mask; 643130803Smarcel if (tt->rn_flags & RNF_NORMAL) { 644130803Smarcel log(LOG_ERR, 645130803Smarcel "Non-unique normal route, mask not entered"); 646130803Smarcel return tt; 647130803Smarcel } 648130803Smarcel } else 649130803Smarcel mmask = m->rm_mask; 650130803Smarcel if (mmask == netmask) { 651130803Smarcel m->rm_refs++; 652130803Smarcel tt->rn_mklist = m; 653130803Smarcel return tt; 654130803Smarcel } 655130803Smarcel if (rn_refines(netmask, mmask) || rn_lexobetter(netmask, mmask)) 656130803Smarcel break; 657130803Smarcel } 658130803Smarcel *mp = rn_new_radix_mask(tt, *mp); 659130803Smarcel return tt; 660130803Smarcel} 661130803Smarcel 662130803Smarcelstatic struct radix_node * 663130803Smarcelrn_delete(void *v_arg, 664130803Smarcel void *netmask_arg, 665130803Smarcel struct radix_node_head *head) 666130803Smarcel{ 667130803Smarcel struct radix_node *t, *p, *x, *tt; 668130803Smarcel struct radix_mask *m, *saved_m, **mp; 669130803Smarcel struct radix_node *dupedkey, *saved_tt, *top; 670130803Smarcel caddr_t v, netmask; 671130803Smarcel int b, head_off, vlen; 672130803Smarcel 673130803Smarcel v = v_arg; 674130803Smarcel netmask = netmask_arg; 675130803Smarcel x = head->rnh_treetop; 676130803Smarcel tt = rn_search(v, x); 677130803Smarcel head_off = x->rn_off; 678130803Smarcel vlen = *(u_char *)v; 679130803Smarcel saved_tt = tt; 680130803Smarcel top = x; 681130803Smarcel if (tt == 0 || 682130803Smarcel Bcmp(v + head_off, tt->rn_key + head_off, vlen - head_off)) 683130803Smarcel return (0); 684130803Smarcel /* 685130803Smarcel * Delete our route from mask lists. 686130803Smarcel */ 687130803Smarcel if (netmask) { 688130803Smarcel if ((x = rn_addmask(netmask, 1, head_off)) == 0) 689130803Smarcel return (0); 690130803Smarcel netmask = x->rn_key; 691130803Smarcel while (tt->rn_mask != netmask) 692130803Smarcel if ((tt = tt->rn_dupedkey) == 0) 693130803Smarcel return (0); 694130803Smarcel } 695130803Smarcel if (tt->rn_mask == 0 || (saved_m = m = tt->rn_mklist) == 0) 696130803Smarcel goto on1; 697130803Smarcel if (tt->rn_flags & RNF_NORMAL) { 698130803Smarcel if (m->rm_leaf != tt || m->rm_refs > 0) { 699130803Smarcel log(LOG_ERR, "rn_delete: inconsistent annotation\n"); 700130803Smarcel return 0; /* dangling ref could cause disaster */ 701130803Smarcel } 702130803Smarcel } else { 703130803Smarcel if (m->rm_mask != tt->rn_mask) { 704130803Smarcel log(LOG_ERR, "rn_delete: inconsistent annotation\n"); 705130803Smarcel goto on1; 706130803Smarcel } 707130803Smarcel if (--m->rm_refs >= 0) 708130803Smarcel goto on1; 709130803Smarcel } 710130803Smarcel b = -1 - tt->rn_b; 711130803Smarcel t = saved_tt->rn_p; 712130803Smarcel if (b > t->rn_b) 713130803Smarcel goto on1; /* Wasn't lifted at all */ 714130803Smarcel do { 715130803Smarcel x = t; 716130803Smarcel t = t->rn_p; 717130803Smarcel } while (b <= t->rn_b && x != top); 718130803Smarcel for (mp = &x->rn_mklist; (m = *mp); mp = &m->rm_mklist) 719130803Smarcel if (m == saved_m) { 720130803Smarcel *mp = m->rm_mklist; 721130803Smarcel MKFree(m); 722130803Smarcel break; 723130803Smarcel } 724130803Smarcel if (m == 0) { 725130803Smarcel log(LOG_ERR, "rn_delete: couldn't find our annotation\n"); 726130803Smarcel if (tt->rn_flags & RNF_NORMAL) 727130803Smarcel return (0); /* Dangling ref to us */ 728130803Smarcel } 729130803Smarcelon1: 730130803Smarcel /* 731130803Smarcel * Eliminate us from tree 732130803Smarcel */ 733130803Smarcel if (tt->rn_flags & RNF_ROOT) 734130803Smarcel return (0); 735130803Smarcel#ifdef RN_DEBUG 736130803Smarcel /* Get us out of the creation list */ 737130803Smarcel for (t = rn_clist; t && t->rn_ybro != tt; t = t->rn_ybro) {} 738130803Smarcel if (t) t->rn_ybro = tt->rn_ybro; 739130803Smarcel#endif 740130803Smarcel t = tt->rn_p; 741130803Smarcel if ((dupedkey = saved_tt->rn_dupedkey)) { 742130803Smarcel if (tt == saved_tt) { 743130803Smarcel x = dupedkey; x->rn_p = t; 744130803Smarcel if (t->rn_l == tt) t->rn_l = x; else t->rn_r = x; 745130803Smarcel } else { 746130803Smarcel for (x = p = saved_tt; p && p->rn_dupedkey != tt;) 747130803Smarcel p = p->rn_dupedkey; 748130803Smarcel if (p) p->rn_dupedkey = tt->rn_dupedkey; 749130803Smarcel else log(LOG_ERR, "rn_delete: couldn't find us\n"); 750130803Smarcel } 751130803Smarcel t = tt + 1; 752130803Smarcel if (t->rn_flags & RNF_ACTIVE) { 753130803Smarcel#ifndef RN_DEBUG 754130803Smarcel *++x = *t; p = t->rn_p; 755130803Smarcel#else 756130803Smarcel b = t->rn_info; *++x = *t; t->rn_info = b; p = t->rn_p; 757130803Smarcel#endif 758130803Smarcel if (p->rn_l == t) p->rn_l = x; else p->rn_r = x; 759130803Smarcel x->rn_l->rn_p = x; x->rn_r->rn_p = x; 760130803Smarcel } 761130803Smarcel goto out; 762130803Smarcel } 763130803Smarcel if (t->rn_l == tt) x = t->rn_r; else x = t->rn_l; 764130803Smarcel p = t->rn_p; 765130803Smarcel if (p->rn_r == t) p->rn_r = x; else p->rn_l = x; 766130803Smarcel x->rn_p = p; 767130803Smarcel /* 768130803Smarcel * Demote routes attached to us. 769130803Smarcel */ 770130803Smarcel if (t->rn_mklist) { 771130803Smarcel if (x->rn_b >= 0) { 772130803Smarcel for (mp = &x->rn_mklist; (m = *mp);) 773130803Smarcel mp = &m->rm_mklist; 774130803Smarcel *mp = t->rn_mklist; 775130803Smarcel } else { 776130803Smarcel /* If there are any key,mask pairs in a sibling 777130803Smarcel duped-key chain, some subset will appear sorted 778130803Smarcel in the same order attached to our mklist */ 779130803Smarcel for (m = t->rn_mklist; m && x; x = x->rn_dupedkey) 780130803Smarcel if (m == x->rn_mklist) { 781130803Smarcel struct radix_mask *mm = m->rm_mklist; 782130803Smarcel x->rn_mklist = 0; 783130803Smarcel if (--(m->rm_refs) < 0) 784130803Smarcel MKFree(m); 785130803Smarcel m = mm; 786130803Smarcel } 787130803Smarcel if (m) 788130803Smarcel syslog(LOG_ERR, "%s 0x%lx at 0x%lx\n", 789130803Smarcel "rn_delete: Orphaned Mask", 790130803Smarcel (unsigned long)m, 791130803Smarcel (unsigned long)x); 792130803Smarcel } 793130803Smarcel } 794130803Smarcel /* 795130803Smarcel * We may be holding an active internal node in the tree. 796130803Smarcel */ 797130803Smarcel x = tt + 1; 798130803Smarcel if (t != x) { 799130803Smarcel#ifndef RN_DEBUG 800130803Smarcel *t = *x; 801130803Smarcel#else 802130803Smarcel b = t->rn_info; *t = *x; t->rn_info = b; 803130803Smarcel#endif 804130803Smarcel t->rn_l->rn_p = t; t->rn_r->rn_p = t; 805130803Smarcel p = x->rn_p; 806130803Smarcel if (p->rn_l == x) p->rn_l = t; else p->rn_r = t; 807130803Smarcel } 808130803Smarcelout: 809130803Smarcel tt->rn_flags &= ~RNF_ACTIVE; 810130803Smarcel tt[1].rn_flags &= ~RNF_ACTIVE; 811130803Smarcel return (tt); 812130803Smarcel} 813130803Smarcel 814130803Smarcelint 815130803Smarcelrn_walktree(struct radix_node_head *h, 816130803Smarcel int (*f)(struct radix_node *, struct walkarg *), 817130803Smarcel struct walkarg *w) 818130803Smarcel{ 819130803Smarcel int error; 820130803Smarcel struct radix_node *base, *next; 821130803Smarcel struct radix_node *rn = h->rnh_treetop; 822130803Smarcel /* 823130803Smarcel * This gets complicated because we may delete the node 824130803Smarcel * while applying the function f to it, so we need to calculate 825130803Smarcel * the successor node in advance. 826130803Smarcel */ 827130803Smarcel /* First time through node, go left */ 828130803Smarcel while (rn->rn_b >= 0) 829130803Smarcel rn = rn->rn_l; 830130803Smarcel for (;;) { 831130803Smarcel base = rn; 832130803Smarcel /* If at right child go back up, otherwise, go right */ 833130803Smarcel while (rn->rn_p->rn_r == rn && (rn->rn_flags & RNF_ROOT) == 0) 834130803Smarcel rn = rn->rn_p; 835130803Smarcel /* Find the next *leaf* since next node might vanish, too */ 836130803Smarcel for (rn = rn->rn_p->rn_r; rn->rn_b >= 0;) 837130803Smarcel rn = rn->rn_l; 838130803Smarcel next = rn; 839130803Smarcel /* Process leaves */ 840130803Smarcel while ((rn = base)) { 841130803Smarcel base = rn->rn_dupedkey; 842130803Smarcel if (!(rn->rn_flags & RNF_ROOT) && (error = (*f)(rn, w))) 843130803Smarcel return (error); 844130803Smarcel } 845130803Smarcel rn = next; 846130803Smarcel if (rn->rn_flags & RNF_ROOT) 847130803Smarcel return (0); 848130803Smarcel } 849130803Smarcel /* NOTREACHED */ 850130803Smarcel} 851130803Smarcel 852130803Smarcelint 853130803Smarcelrn_inithead(struct radix_node_head **head, int off) 854130803Smarcel{ 855130803Smarcel struct radix_node_head *rnh; 856130803Smarcel struct radix_node *t, *tt, *ttt; 857130803Smarcel if (*head) 858130803Smarcel return (1); 859130803Smarcel rnh = (struct radix_node_head *)rtmalloc(sizeof(*rnh), "rn_inithead"); 860130803Smarcel Bzero(rnh, sizeof (*rnh)); 861130803Smarcel *head = rnh; 862130803Smarcel t = rn_newpair(rn_zeros, off, rnh->rnh_nodes); 863130803Smarcel ttt = rnh->rnh_nodes + 2; 864130803Smarcel t->rn_r = ttt; 865130803Smarcel t->rn_p = t; 866130803Smarcel tt = t->rn_l; 867130803Smarcel tt->rn_flags = t->rn_flags = RNF_ROOT | RNF_ACTIVE; 868130803Smarcel tt->rn_b = -1 - off; 869130803Smarcel *ttt = *tt; 870130803Smarcel ttt->rn_key = rn_ones; 871130803Smarcel rnh->rnh_addaddr = rn_addroute; 872130803Smarcel rnh->rnh_deladdr = rn_delete; 873130803Smarcel rnh->rnh_matchaddr = rn_match; 874130803Smarcel rnh->rnh_lookup = rn_lookup; 875130803Smarcel rnh->rnh_walktree = rn_walktree; 876130803Smarcel rnh->rnh_treetop = t; 877130803Smarcel return (1); 878130803Smarcel} 879130803Smarcel 880130803Smarcelvoid 881130803Smarcelrn_init(void) 882130803Smarcel{ 883130803Smarcel char *cp, *cplim; 884130803Smarcel if (max_keylen == 0) { 885130803Smarcel printf("rn_init: radix functions require max_keylen be set\n"); 886130803Smarcel return; 887130803Smarcel } 888130803Smarcel rn_zeros = (char *)rtmalloc(3 * max_keylen, "rn_init"); 889130803Smarcel Bzero(rn_zeros, 3 * max_keylen); 890130803Smarcel rn_ones = cp = rn_zeros + max_keylen; 891130803Smarcel addmask_key = cplim = rn_ones + max_keylen; 892130803Smarcel while (cp < cplim) 893130803Smarcel *cp++ = -1; 894130803Smarcel if (rn_inithead(&mask_rnhead, 0) == 0) 895130803Smarcel panic("rn_init 2"); 896130803Smarcel} 897130803Smarcel 898130803Smarcel