1 /* 2 * Copyright 2001-2003 Sun Microsystems, Inc. All rights reserved. 3 * Use is subject to license terms. 4 * 5 * Copyright (c) 1988, 1989, 1993 6 * The Regents of the University of California. All rights reserved. 7 * 8 * Redistribution and use in source and binary forms, with or without 9 * modification, are permitted provided that the following conditions 10 * are met: 11 * 1. Redistributions of source code must retain the above copyright 12 * notice, this list of conditions and the following disclaimer. 13 * 2. Redistributions in binary form must reproduce the above copyright 14 * notice, this list of conditions and the following disclaimer in the 15 * documentation and/or other materials provided with the distribution. 16 * 3. All advertising materials mentioning features or use of this software 17 * must display the following acknowledgment: 18 * This product includes software developed by the University of 19 * California, Berkeley and its contributors. 20 * 4. Neither the name of the University nor the names of its contributors 21 * may be used to endorse or promote products derived from this software 22 * without specific prior written permission. 23 * 24 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 25 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 26 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 27 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 28 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 29 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 30 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 31 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 32 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 33 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 34 * SUCH DAMAGE. 35 * 36 * @(#)radix.c 8.4 (Berkeley) 11/2/94 37 * 38 * $FreeBSD: src/sbin/routed/radix.c,v 1.6 2000/08/11 08:24:38 sheldonh Exp $ 39 */ 40 41 /* 42 * Routines to build and maintain radix trees for routing lookups. 43 */ 44 45 #include "defs.h" 46 47 static const size_t max_keylen = sizeof (struct sockaddr_in); 48 static struct radix_mask *rn_mkfreelist; 49 static struct radix_node_head *mask_rnhead; 50 static uint8_t *rn_zeros, *rn_ones, *addmask_key; 51 52 #define rn_masktop (mask_rnhead->rnh_treetop) 53 54 static boolean_t rn_satisfies_leaf(uint8_t *, struct radix_node *, int); 55 56 static boolean_t rn_refines(void *, void *); 57 58 static struct radix_node 59 *rn_addmask(void *, uint_t, uint_t), 60 *rn_addroute(void *, void *, struct radix_node_head *, 61 struct radix_node [2]), 62 *rn_delete(void *, void *, struct radix_node_head *), 63 *rn_insert(void *, struct radix_node_head *, boolean_t *, 64 struct radix_node [2]), 65 *rn_match(void *, struct radix_node_head *), 66 *rn_newpair(void *, uint_t, struct radix_node[2]), 67 *rn_search(void *, struct radix_node *), 68 *rn_search_m(void *, struct radix_node *, void *); 69 70 static struct radix_node *rn_lookup(void *, void *, struct radix_node_head *); 71 72 #ifdef DEBUG 73 #define DBGMSG(x) msglog x 74 #else 75 #define DBGMSG(x) (void) 0 76 #endif 77 78 /* 79 * The data structure for the keys is a radix tree with one way 80 * branching removed. The index rn_b at an internal node n represents a bit 81 * position to be tested. The tree is arranged so that all descendants 82 * of a node n have keys whose bits all agree up to position rn_b - 1. 83 * (We say the index of n is rn_b.) 84 * 85 * There is at least one descendant which has a one bit at position rn_b, 86 * and at least one with a zero there. 87 * 88 * A route is determined by a pair of key and mask. We require that the 89 * bit-wise logical and of the key and mask to be the key. 90 * We define the index of a route to associated with the mask to be 91 * the first bit number in the mask where 0 occurs (with bit number 0 92 * representing the highest order bit). 93 * 94 * We say a mask is normal if every bit is 0, past the index of the mask. 95 * If a node n has a descendant (k, m) with index(m) == index(n) == rn_b, 96 * and m is a normal mask, then the route applies to every descendant of n. 97 * If the index(m) < rn_b, this implies the trailing last few bits of k 98 * before bit b are all 0, (and hence consequently true of every descendant 99 * of n), so the route applies to all descendants of the node as well. 100 * 101 * Similar logic shows that a non-normal mask m such that 102 * index(m) <= index(n) could potentially apply to many children of n. 103 * Thus, for each non-host route, we attach its mask to a list at an internal 104 * node as high in the tree as we can go. 105 * 106 * The present version of the code makes use of normal routes in short- 107 * circuiting an explict mask and compare operation when testing whether 108 * a key satisfies a normal route, and also in remembering the unique leaf 109 * that governs a subtree. 110 */ 111 112 static struct radix_node * 113 rn_search(void *v_arg, struct radix_node *head) 114 { 115 struct radix_node *x; 116 uint8_t *v; 117 118 for (x = head, v = v_arg; x->rn_b >= 0; ) { 119 if (x->rn_bmask & v[x->rn_off]) 120 x = x->rn_r; 121 else 122 x = x->rn_l; 123 } 124 return (x); 125 } 126 127 static struct radix_node * 128 rn_search_m(void *v_arg, struct radix_node *head, void *m_arg) 129 { 130 struct radix_node *x; 131 uint8_t *v = v_arg, *m = m_arg; 132 133 for (x = head; x->rn_b >= 0; ) { 134 if (x->rn_bmask & m[x->rn_off] & v[x->rn_off]) 135 x = x->rn_r; 136 else 137 x = x->rn_l; 138 } 139 return (x); 140 } 141 142 /* 143 * Returns true if there are no bits set in n_arg that are zero in 144 * m_arg and the masks aren't equal. In other words, it returns true 145 * when m_arg is a finer-granularity netmask -- it represents a subset 146 * of the destinations implied by n_arg. 147 */ 148 static boolean_t 149 rn_refines(void* m_arg, void *n_arg) 150 { 151 uint8_t *m = m_arg, *n = n_arg; 152 uint8_t *lim; 153 boolean_t masks_are_equal = _B_TRUE; 154 155 lim = n + sizeof (struct sockaddr); 156 157 while (n < lim) { 158 if (*n & ~(*m)) 159 return (_B_FALSE); 160 if (*n++ != *m++) 161 masks_are_equal = _B_FALSE; 162 } 163 return (!masks_are_equal); 164 } 165 166 static struct radix_node * 167 rn_lookup(void *v_arg, void *m_arg, struct radix_node_head *head) 168 { 169 struct radix_node *x; 170 uint8_t *netmask = NULL; 171 172 if (m_arg) { 173 if ((x = rn_addmask(m_arg, 1, head->rnh_treetop->rn_off)) == 174 NULL) { 175 DBGMSG(("rn_lookup: failed to add mask")); 176 return (NULL); 177 } 178 netmask = x->rn_key; 179 } 180 x = rn_match(v_arg, head); 181 if (x && netmask) { 182 while (x && x->rn_mask != netmask) 183 x = x->rn_dupedkey; 184 } 185 return (x); 186 } 187 188 /* 189 * Returns true if address 'trial' has no bits differing from the 190 * leaf's key when compared under the leaf's mask. In other words, 191 * returns true when 'trial' matches leaf. 192 */ 193 static boolean_t 194 rn_satisfies_leaf(uint8_t *trial, 195 struct radix_node *leaf, 196 int skip) 197 { 198 uint8_t *cp = trial, *cp2 = leaf->rn_key, *cp3 = leaf->rn_mask; 199 uint8_t *cplim; 200 size_t length; 201 202 length = sizeof (struct sockaddr); 203 204 if (cp3 == NULL) 205 cp3 = rn_ones; 206 cplim = cp + length; 207 cp3 += skip; 208 cp2 += skip; 209 for (cp += skip; cp < cplim; cp++, cp2++, cp3++) 210 if ((*cp ^ *cp2) & *cp3) 211 return (_B_FALSE); 212 return (_B_TRUE); 213 } 214 215 static struct radix_node * 216 rn_match(void *v_arg, struct radix_node_head *head) 217 { 218 uint8_t *v = v_arg; 219 struct radix_node *t = head->rnh_treetop, *x; 220 uint8_t *cp = v, *cp2; 221 uint8_t *cplim; 222 struct radix_node *saved_t, *top = t; 223 uint_t off = t->rn_off, vlen, matched_off; 224 int test, b, rn_b; 225 226 vlen = sizeof (struct sockaddr); 227 228 /* 229 * Open code rn_search(v, top) to avoid overhead of extra 230 * subroutine call. 231 */ 232 for (; t->rn_b >= 0; ) { 233 if (t->rn_bmask & cp[t->rn_off]) 234 t = t->rn_r; 235 else 236 t = t->rn_l; 237 } 238 239 cp += off; 240 cp2 = t->rn_key + off; 241 cplim = v + vlen; 242 for (; cp < cplim; cp++, cp2++) 243 if (*cp != *cp2) 244 goto found_difference_with_key; 245 /* 246 * This extra grot is in case we are explicitly asked 247 * to look up the default. Ugh! 248 * Or 255.255.255.255 249 * 250 * In this case, we have a complete match of the key. Unless 251 * the node is one of the roots, we are finished. 252 * If it is the zeros root, then take what we have, prefering 253 * any real data. 254 * If it is the ones root, then pretend the target key was followed 255 * by a byte of zeros. 256 */ 257 if (!(t->rn_flags & RNF_ROOT)) 258 return (t); /* not a root */ 259 if (t->rn_dupedkey) { 260 t = t->rn_dupedkey; 261 return (t); /* have some real data */ 262 } 263 if (*(cp-1) == 0) 264 return (t); /* not the ones root */ 265 b = 0; /* fake a zero after 255.255.255.255 */ 266 goto calculated_differing_bit; 267 found_difference_with_key: 268 test = (*cp ^ *cp2) & 0xff; /* find first bit that differs */ 269 for (b = 7; (test >>= 1) > 0; ) 270 b--; 271 calculated_differing_bit: 272 matched_off = cp - v; 273 b += matched_off << 3; 274 rn_b = -1 - b; 275 /* 276 * If there is a host route in a duped-key chain, it will be first. 277 */ 278 if ((saved_t = t)->rn_mask == NULL) 279 t = t->rn_dupedkey; 280 for (; t; t = t->rn_dupedkey) { 281 /* 282 * Even if we don't match exactly as a host, 283 * we may match if the leaf we wound up at is 284 * a route to a net. 285 */ 286 if (t->rn_flags & RNF_NORMAL) { 287 if (rn_b <= t->rn_b) 288 return (t); 289 } else if (rn_satisfies_leaf(v, t, matched_off)) { 290 return (t); 291 } 292 } 293 t = saved_t; 294 /* start searching up the tree */ 295 do { 296 struct radix_mask *m; 297 t = t->rn_p; 298 if ((m = t->rn_mklist) != NULL) { 299 /* 300 * If non-contiguous masks ever become important 301 * we can restore the masking and open coding of 302 * the search and satisfaction test and put the 303 * calculation of "off" back before the "do". 304 */ 305 do { 306 if (m->rm_flags & RNF_NORMAL) { 307 if (rn_b <= m->rm_b) 308 return (m->rm_leaf); 309 } else { 310 off = MIN(t->rn_off, matched_off); 311 x = rn_search_m(v, t, m->rm_mask); 312 while (x != NULL && 313 x->rn_mask != m->rm_mask) 314 x = x->rn_dupedkey; 315 if (x != NULL && 316 rn_satisfies_leaf(v, x, off)) 317 return (x); 318 } 319 } while ((m = m->rm_mklist) != NULL); 320 } 321 } while (t != top); 322 return (NULL); 323 } 324 325 #ifdef RN_DEBUG 326 int rn_nodenum; 327 struct radix_node *rn_clist; 328 int rn_saveinfo; 329 boolean_t rn_debug = 1; 330 #endif 331 332 static struct radix_node * 333 rn_newpair(void *v, uint_t b, struct radix_node nodes[2]) 334 { 335 struct radix_node *tt = nodes, *t = tt + 1; 336 337 t->rn_b = b; 338 t->rn_bmask = 0x80 >> (b & 7); 339 t->rn_l = tt; 340 t->rn_off = b >> 3; 341 tt->rn_b = -1; 342 tt->rn_key = v; 343 tt->rn_p = t; 344 tt->rn_flags = t->rn_flags = RNF_ACTIVE; 345 #ifdef RN_DEBUG 346 tt->rn_info = rn_nodenum++; 347 t->rn_info = rn_nodenum++; 348 tt->rn_twin = t; 349 tt->rn_ybro = rn_clist; 350 rn_clist = tt; 351 #endif 352 return (t); 353 } 354 355 static struct radix_node * 356 rn_insert(void* v_arg, struct radix_node_head *head, boolean_t *dupentry, 357 struct radix_node nodes[2]) 358 { 359 uint8_t *v = v_arg; 360 struct radix_node *top = head->rnh_treetop; 361 uint_t head_off = top->rn_off, vlen; 362 struct radix_node *t = rn_search(v_arg, top); 363 uint8_t *cp = v + head_off, b; 364 struct radix_node *tt; 365 366 vlen = sizeof (struct sockaddr); 367 368 /* 369 * Find first bit at which v and t->rn_key differ 370 */ 371 { 372 uint8_t *cp2 = t->rn_key + head_off; 373 uint8_t cmp_res; 374 uint8_t *cplim = v + vlen; 375 376 while (cp < cplim) 377 if (*cp2++ != *cp++) 378 goto found_differing_byte; 379 /* handle adding 255.255.255.255 */ 380 if (!(t->rn_flags & RNF_ROOT) || *(cp2-1) == 0) { 381 *dupentry = _B_TRUE; 382 return (t); 383 } 384 found_differing_byte: 385 *dupentry = _B_FALSE; 386 cmp_res = cp[-1] ^ cp2[-1]; 387 for (b = (cp - v) << 3; cmp_res != 0; b--) 388 cmp_res >>= 1; 389 } 390 { 391 struct radix_node *p, *x = top; 392 cp = v; 393 do { 394 p = x; 395 if (cp[x->rn_off] & x->rn_bmask) 396 x = x->rn_r; 397 else 398 x = x->rn_l; 399 } while (b > (unsigned)x->rn_b); 400 #ifdef RN_DEBUG 401 if (rn_debug) { 402 msglog("rn_insert: Going In:"); 403 traverse(p); 404 } 405 #endif 406 t = rn_newpair(v_arg, b, nodes); 407 tt = t->rn_l; 408 if (!(cp[p->rn_off] & p->rn_bmask)) 409 p->rn_l = t; 410 else 411 p->rn_r = t; 412 x->rn_p = t; /* frees x, p as temp vars below */ 413 t->rn_p = p; 414 if (!(cp[t->rn_off] & t->rn_bmask)) { 415 t->rn_r = x; 416 } else { 417 t->rn_r = tt; 418 t->rn_l = x; 419 } 420 #ifdef RN_DEBUG 421 if (rn_debug) { 422 msglog("rn_insert: Coming Out:"); 423 traverse(p); 424 } 425 #endif 426 } 427 return (tt); 428 } 429 430 static struct radix_node * 431 rn_addmask(void *n_arg, uint_t search, uint_t skip) 432 { 433 uint8_t *netmask = n_arg; 434 struct radix_node *x; 435 uint8_t *cp, *cplim; 436 int b = 0, mlen, j, m0; 437 boolean_t maskduplicated; 438 struct radix_node *saved_x; 439 static int last_zeroed = 0; 440 441 mlen = sizeof (struct sockaddr); 442 if (skip == 0) 443 skip = 1; 444 if (mlen <= skip) 445 return (mask_rnhead->rnh_nodes); 446 if (skip > 1) 447 (void) memmove(addmask_key + 1, rn_ones + 1, skip - 1); 448 if ((m0 = mlen) > skip) 449 (void) memmove(addmask_key + skip, netmask + skip, mlen - skip); 450 /* 451 * Trim trailing zeroes. 452 */ 453 for (cp = addmask_key + mlen; (cp > addmask_key) && cp[-1] == 0; ) 454 cp--; 455 mlen = cp - addmask_key; 456 if (mlen <= skip) { 457 if (m0 >= last_zeroed) 458 last_zeroed = mlen; 459 return (mask_rnhead->rnh_nodes); 460 } 461 if (m0 < last_zeroed) 462 (void) memset(addmask_key + m0, 0, last_zeroed - m0); 463 *addmask_key = last_zeroed = mlen; 464 x = rn_search(addmask_key, rn_masktop); 465 if (memcmp(addmask_key, x->rn_key, mlen) != 0) 466 x = NULL; 467 if (x != NULL || search != 0) 468 return (x); 469 x = rtmalloc(max_keylen + 2*sizeof (*x), "rn_addmask"); 470 saved_x = x; 471 (void) memset(x, 0, max_keylen + 2 * sizeof (*x)); 472 netmask = cp = (uint8_t *)(x + 2); 473 (void) memmove(cp, addmask_key, mlen); 474 x = rn_insert(cp, mask_rnhead, &maskduplicated, x); 475 if (maskduplicated) { 476 #ifdef DEBUG 477 logbad(1, "rn_addmask: mask impossibly already in tree"); 478 #else 479 msglog("rn_addmask: mask impossibly already in tree"); 480 #endif 481 free(saved_x); 482 return (x); 483 } 484 /* 485 * Calculate index of mask, and check for normalcy. 486 */ 487 cplim = netmask + mlen; 488 x->rn_flags |= RNF_NORMAL; 489 for (cp = netmask + skip; (cp < cplim) && *cp == 0xff; ) 490 cp++; 491 if (cp != cplim) { 492 for (j = 0x80; (j & *cp) != 0; j >>= 1) 493 b++; 494 if (*cp != (0xFF & ~(0xFF >> b)) || cp != (cplim - 1)) 495 x->rn_flags &= ~RNF_NORMAL; 496 } 497 b += (cp - netmask) << 3; 498 x->rn_b = -1 - b; 499 return (x); 500 } 501 502 static boolean_t /* Note: arbitrary ordering for non-contiguous masks */ 503 rn_lexobetter(void *m_arg, void *n_arg) 504 { 505 uint8_t *mp = m_arg, *np = n_arg, *lim; 506 507 lim = mp + sizeof (struct sockaddr); 508 while (mp < lim) 509 if (*mp++ > *np++) 510 return (_B_TRUE); 511 return (_B_FALSE); 512 } 513 514 static struct radix_mask * 515 rn_new_radix_mask(struct radix_node *tt, 516 struct radix_mask *next) 517 { 518 struct radix_mask *m; 519 520 MKGet(m); 521 if (m == NULL) { 522 #ifdef DEBUG 523 logbad(1, "Mask for route not entered"); 524 #else 525 msglog("Mask for route not entered"); 526 #endif 527 return (NULL); 528 } 529 (void) memset(m, 0, sizeof (*m)); 530 m->rm_b = tt->rn_b; 531 m->rm_flags = tt->rn_flags; 532 if (tt->rn_flags & RNF_NORMAL) 533 m->rm_leaf = tt; 534 else 535 m->rm_mask = tt->rn_mask; 536 m->rm_mklist = next; 537 tt->rn_mklist = m; 538 return (m); 539 } 540 541 static struct radix_node * 542 rn_addroute(void *v_arg, void *n_arg, struct radix_node_head *head, 543 struct radix_node treenodes[2]) 544 { 545 uint8_t *v = v_arg, *netmask = n_arg; 546 struct radix_node *t, *x = 0, *tt; 547 struct radix_node *saved_tt, *top = head->rnh_treetop; 548 short b = 0, b_leaf = 0; 549 boolean_t keyduplicated; 550 uint8_t *mmask; 551 struct radix_mask *m, **mp; 552 553 /* 554 * In dealing with non-contiguous masks, there may be 555 * many different routes which have the same mask. 556 * We will find it useful to have a unique pointer to 557 * the mask to speed avoiding duplicate references at 558 * nodes and possibly save time in calculating indices. 559 */ 560 if (netmask) { 561 if ((x = rn_addmask(netmask, 0, top->rn_off)) == NULL) { 562 DBGMSG(("rn_addroute: addmask failed")); 563 return (NULL); 564 } 565 b_leaf = x->rn_b; 566 b = -1 - x->rn_b; 567 netmask = x->rn_key; 568 } 569 /* 570 * Deal with duplicated keys: attach node to previous instance 571 */ 572 saved_tt = tt = rn_insert(v, head, &keyduplicated, treenodes); 573 if (keyduplicated) { 574 for (t = tt; tt; t = tt, tt = tt->rn_dupedkey) { 575 if (tt->rn_mask == netmask) { 576 DBGMSG(("rn_addroute: duplicated route and " 577 "mask")); 578 return (NULL); 579 } 580 if (netmask == NULL || 581 (tt->rn_mask && 582 ((b_leaf < tt->rn_b) || 583 rn_refines(netmask, tt->rn_mask) || 584 rn_lexobetter(netmask, tt->rn_mask)))) 585 break; 586 } 587 /* 588 * If the mask is not duplicated, we wouldn't 589 * find it among possible duplicate key entries 590 * anyway, so the above test doesn't hurt. 591 * 592 * We sort the masks for a duplicated key the same way as 593 * in a masklist -- most specific to least specific. 594 * This may require the unfortunate nuisance of relocating 595 * the head of the list. 596 */ 597 if (tt == saved_tt) { 598 struct radix_node *xx = x; 599 /* link in at head of list */ 600 (tt = treenodes)->rn_dupedkey = t; 601 tt->rn_flags = t->rn_flags; 602 tt->rn_p = x = t->rn_p; 603 if (x->rn_l == t) 604 x->rn_l = tt; 605 else 606 x->rn_r = tt; 607 saved_tt = tt; 608 x = xx; 609 } else { 610 (tt = treenodes)->rn_dupedkey = t->rn_dupedkey; 611 t->rn_dupedkey = tt; 612 } 613 #ifdef RN_DEBUG 614 t = tt + 1; 615 tt->rn_info = rn_nodenum++; 616 t->rn_info = rn_nodenum++; 617 tt->rn_twin = t; 618 tt->rn_ybro = rn_clist; 619 rn_clist = tt; 620 #endif 621 tt->rn_key = v; 622 tt->rn_b = -1; 623 tt->rn_flags = RNF_ACTIVE; 624 } 625 /* 626 * Put mask in tree. 627 */ 628 if (netmask) { 629 tt->rn_mask = netmask; 630 tt->rn_b = x->rn_b; 631 tt->rn_flags |= x->rn_flags & RNF_NORMAL; 632 } 633 t = saved_tt->rn_p; 634 if (keyduplicated) 635 goto key_already_in_tree; 636 b_leaf = -1 - t->rn_b; 637 if (t->rn_r == saved_tt) 638 x = t->rn_l; 639 else 640 x = t->rn_r; 641 /* Promote general routes from below */ 642 if (x->rn_b < 0) { 643 for (mp = &t->rn_mklist; x; x = x->rn_dupedkey) 644 if (x->rn_mask != NULL && (x->rn_b >= b_leaf) && 645 x->rn_mklist == NULL) { 646 if ((*mp = m = rn_new_radix_mask(x, 0)) != NULL) 647 mp = &m->rm_mklist; 648 } 649 } else if (x->rn_mklist) { 650 /* 651 * Skip over masks whose index is > that of new node 652 */ 653 for (mp = &x->rn_mklist; (m = *mp) != NULL; mp = &m->rm_mklist) 654 if (m->rm_b >= b_leaf) 655 break; 656 t->rn_mklist = m; 657 *mp = 0; 658 } 659 key_already_in_tree: 660 /* Add new route to highest possible ancestor's list */ 661 if ((netmask == NULL) || (b > t->rn_b)) { 662 return (tt); /* can't lift at all */ 663 } 664 b_leaf = tt->rn_b; 665 do { 666 x = t; 667 t = t->rn_p; 668 } while (b <= t->rn_b && x != top); 669 /* 670 * Search through routes associated with node to 671 * insert new route according to index. 672 * Need same criteria as when sorting dupedkeys to avoid 673 * double loop on deletion. 674 */ 675 for (mp = &x->rn_mklist; (m = *mp) != NULL; mp = &m->rm_mklist) { 676 if (m->rm_b < b_leaf) 677 continue; 678 if (m->rm_b > b_leaf) 679 break; 680 if (m->rm_flags & RNF_NORMAL) { 681 mmask = m->rm_leaf->rn_mask; 682 if (tt->rn_flags & RNF_NORMAL) { 683 #ifdef DEBUG 684 logbad(1, "Non-unique normal route, mask " 685 "not entered"); 686 #else 687 msglog("Non-unique normal route, mask " 688 "not entered"); 689 #endif 690 return (tt); 691 } 692 } else 693 mmask = m->rm_mask; 694 if (mmask == netmask) { 695 m->rm_refs++; 696 tt->rn_mklist = m; 697 return (tt); 698 } 699 if (rn_refines(netmask, mmask) || rn_lexobetter(netmask, mmask)) 700 break; 701 } 702 *mp = rn_new_radix_mask(tt, *mp); 703 return (tt); 704 } 705 706 static struct radix_node * 707 rn_delete(void *v_arg, void *netmask_arg, struct radix_node_head *head) 708 { 709 struct radix_node *t, *p, *x, *tt; 710 struct radix_mask *m, *saved_m, **mp; 711 struct radix_node *dupedkey, *saved_tt, *top; 712 uint8_t *v, *netmask; 713 int b; 714 uint_t head_off, vlen; 715 716 v = v_arg; 717 netmask = netmask_arg; 718 x = head->rnh_treetop; 719 tt = rn_search(v, x); 720 head_off = x->rn_off; 721 vlen = sizeof (struct sockaddr); 722 saved_tt = tt; 723 top = x; 724 if (tt == NULL || 725 memcmp(v + head_off, tt->rn_key + head_off, vlen - head_off) != 0) { 726 DBGMSG(("rn_delete: unable to locate route to delete")); 727 return (NULL); 728 } 729 /* 730 * Delete our route from mask lists. 731 */ 732 if (netmask) { 733 if ((x = rn_addmask(netmask, 1, head_off)) == NULL) { 734 DBGMSG(("rn_delete: cannot add mask")); 735 return (NULL); 736 } 737 netmask = x->rn_key; 738 while (tt->rn_mask != netmask) 739 if ((tt = tt->rn_dupedkey) == NULL) { 740 DBGMSG(("rn_delete: cannot locate mask")); 741 return (NULL); 742 } 743 } 744 if (tt->rn_mask == NULL || (saved_m = m = tt->rn_mklist) == NULL) 745 goto annotation_removed; 746 if (tt->rn_flags & RNF_NORMAL) { 747 if (m->rm_leaf != tt || m->rm_refs > 0) { 748 #ifdef DEBUG 749 logbad(1, "rn_delete: inconsistent annotation"); 750 #else 751 msglog("rn_delete: inconsistent annotation"); 752 #endif 753 return (NULL); /* dangling ref could cause disaster */ 754 } 755 } else { 756 if (m->rm_mask != tt->rn_mask) { 757 #ifdef DEBUG 758 logbad(1, "rn_delete: inconsistent annotation"); 759 #else 760 msglog("rn_delete: inconsistent annotation"); 761 #endif 762 goto annotation_removed; 763 } 764 if (--m->rm_refs >= 0) 765 goto annotation_removed; 766 } 767 b = -1 - tt->rn_b; 768 t = saved_tt->rn_p; 769 if (b > t->rn_b) 770 goto annotation_removed; /* Wasn't lifted at all */ 771 do { 772 x = t; 773 t = t->rn_p; 774 } while (b <= t->rn_b && x != top); 775 for (mp = &x->rn_mklist; (m = *mp) != NULL; mp = &m->rm_mklist) 776 if (m == saved_m) { 777 *mp = m->rm_mklist; 778 MKFree(m); 779 break; 780 } 781 if (m == NULL) { 782 #ifdef DEBUG 783 logbad(1, "rn_delete: couldn't find our annotation"); 784 #else 785 msglog("rn_delete: couldn't find our annotation"); 786 #endif 787 if (tt->rn_flags & RNF_NORMAL) 788 return (NULL); /* Dangling ref to us */ 789 } 790 annotation_removed: 791 /* 792 * Eliminate us from tree 793 */ 794 if (tt->rn_flags & RNF_ROOT) { 795 DBGMSG(("rn_delete: cannot delete root")); 796 return (NULL); 797 } 798 #ifdef RN_DEBUG 799 /* Get us out of the creation list */ 800 for (t = rn_clist; t && t->rn_ybro != tt; t = t->rn_ybro) {} 801 if (t != NULL) 802 t->rn_ybro = tt->rn_ybro; 803 #endif 804 t = tt->rn_p; 805 if ((dupedkey = saved_tt->rn_dupedkey) != NULL) { 806 if (tt == saved_tt) { 807 x = dupedkey; 808 x->rn_p = t; 809 if (t->rn_l == tt) 810 t->rn_l = x; 811 else 812 t->rn_r = x; 813 } else { 814 for (x = p = saved_tt; p && p->rn_dupedkey != tt; ) 815 p = p->rn_dupedkey; 816 if (p != NULL) { 817 p->rn_dupedkey = tt->rn_dupedkey; 818 } else { 819 #ifdef DEBUG 820 logbad(1, "rn_delete: couldn't find us"); 821 #else 822 msglog("rn_delete: couldn't find us"); 823 #endif 824 } 825 } 826 t = tt + 1; 827 if (t->rn_flags & RNF_ACTIVE) { 828 #ifndef RN_DEBUG 829 *++x = *t; 830 p = t->rn_p; 831 #else 832 b = t->rn_info; 833 *++x = *t; 834 t->rn_info = b; 835 p = t->rn_p; 836 #endif 837 if (p->rn_l == t) 838 p->rn_l = x; 839 else 840 p->rn_r = x; 841 x->rn_l->rn_p = x; 842 x->rn_r->rn_p = x; 843 } 844 goto out; 845 } 846 if (t->rn_l == tt) 847 x = t->rn_r; 848 else 849 x = t->rn_l; 850 p = t->rn_p; 851 if (p->rn_r == t) 852 p->rn_r = x; 853 else 854 p->rn_l = x; 855 x->rn_p = p; 856 /* 857 * Demote routes attached to us. 858 */ 859 if (t->rn_mklist) { 860 if (x->rn_b >= 0) { 861 for (mp = &x->rn_mklist; (m = *mp) != NULL; ) 862 mp = &m->rm_mklist; 863 *mp = t->rn_mklist; 864 } else { 865 /* 866 * If there are any key,mask pairs in a sibling 867 * duped-key chain, some subset will appear sorted 868 * in the same order attached to our mklist 869 */ 870 for (m = t->rn_mklist; m && x; x = x->rn_dupedkey) 871 if (m == x->rn_mklist) { 872 struct radix_mask *mm = m->rm_mklist; 873 x->rn_mklist = 0; 874 if (--(m->rm_refs) < 0) 875 MKFree(m); 876 m = mm; 877 } 878 if (m != NULL) { 879 #ifdef DEBUG 880 logbad(1, "rn_delete: Orphaned Mask %p at %p\n", 881 m, x); 882 #else 883 msglog("rn_delete: Orphaned Mask %p at %p\n", m, 884 x); 885 #endif 886 } 887 } 888 } 889 /* 890 * We may be holding an active internal node in the tree. 891 */ 892 x = tt + 1; 893 if (t != x) { 894 #ifndef RN_DEBUG 895 *t = *x; 896 #else 897 b = t->rn_info; 898 *t = *x; 899 t->rn_info = b; 900 #endif 901 t->rn_l->rn_p = t; 902 t->rn_r->rn_p = t; 903 p = x->rn_p; 904 if (p->rn_l == x) 905 p->rn_l = t; 906 else 907 p->rn_r = t; 908 } 909 out: 910 tt->rn_flags &= ~RNF_ACTIVE; 911 tt[1].rn_flags &= ~RNF_ACTIVE; 912 return (tt); 913 } 914 915 int 916 rn_walktree(struct radix_node_head *h, 917 int (*f)(struct radix_node *, void *), 918 void *w) 919 { 920 int error; 921 struct radix_node *base, *next; 922 struct radix_node *rn = h->rnh_treetop; 923 /* 924 * This gets complicated because we may delete the node 925 * while applying the function f to it, so we need to calculate 926 * the successor node in advance. 927 */ 928 /* First time through node, go left */ 929 while (rn->rn_b >= 0) 930 rn = rn->rn_l; 931 do { 932 base = rn; 933 /* If at right child go back up, otherwise, go right */ 934 while (rn->rn_p->rn_r == rn && !(rn->rn_flags & RNF_ROOT)) 935 rn = rn->rn_p; 936 /* Find the next *leaf* since next node might vanish, too */ 937 for (rn = rn->rn_p->rn_r; rn->rn_b >= 0; ) 938 rn = rn->rn_l; 939 next = rn; 940 /* Process leaves */ 941 while ((rn = base) != NULL) { 942 base = rn->rn_dupedkey; 943 if (!(rn->rn_flags & RNF_ROOT) && (error = (*f)(rn, w))) 944 return (error); 945 } 946 rn = next; 947 } while (!(rn->rn_flags & RNF_ROOT)); 948 return (0); 949 } 950 951 int 952 rn_inithead(void **head, uint_t off) 953 { 954 struct radix_node_head *rnh; 955 struct radix_node *t, *tt, *ttt; 956 if (*head) 957 return (1); 958 rnh = rtmalloc(sizeof (*rnh), "rn_inithead"); 959 (void) memset(rnh, 0, sizeof (*rnh)); 960 *head = rnh; 961 t = rn_newpair(rn_zeros, off, rnh->rnh_nodes); 962 ttt = rnh->rnh_nodes + 2; 963 t->rn_r = ttt; 964 t->rn_p = t; 965 tt = t->rn_l; 966 tt->rn_flags = t->rn_flags = RNF_ROOT | RNF_ACTIVE; 967 tt->rn_b = -1 - off; 968 *ttt = *tt; 969 ttt->rn_key = rn_ones; 970 rnh->rnh_addaddr = rn_addroute; 971 rnh->rnh_deladdr = rn_delete; 972 rnh->rnh_matchaddr = rn_match; 973 rnh->rnh_lookup = rn_lookup; 974 rnh->rnh_walktree = rn_walktree; 975 rnh->rnh_treetop = t; 976 return (1); 977 } 978 979 void 980 rn_init(void) 981 { 982 uint8_t *cp, *cplim; 983 984 if (max_keylen == 0) { 985 logbad(1, "radix functions require max_keylen be set"); 986 return; 987 } 988 rn_zeros = rtmalloc(3 * max_keylen, "rn_init"); 989 (void) memset(rn_zeros, 0, 3 * max_keylen); 990 rn_ones = cp = rn_zeros + max_keylen; 991 addmask_key = cplim = rn_ones + max_keylen; 992 while (cp < cplim) 993 *cp++ = 0xFF; 994 if (rn_inithead((void **)&mask_rnhead, 0) == 0) { 995 logbad(0, "rn_init: could not initialize radix tree"); 996 } 997 } 998