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