1 /* 2 * Copyright (c) 1988, 1989 Regents of the University of California. 3 * All rights reserved. 4 * 5 * %sccs.include.redist.c% 6 * 7 * @(#)radix.c 7.15 (Berkeley) 07/09/92 8 */ 9 10 /* 11 * Routines to build and maintain radix trees for routing lookups. 12 */ 13 #ifndef RNF_NORMAL 14 #include "param.h" 15 #include "radix.h" 16 #include "malloc.h" 17 #define M_DONTWAIT M_NOWAIT 18 #ifdef KERNEL 19 #include "domain.h" 20 #endif 21 #endif 22 int max_keylen; 23 struct radix_mask *rn_mkfreelist; 24 struct radix_node_head *mask_rnhead; 25 static int gotOddMasks; 26 static char *maskedKey; 27 static char *rn_zeros, *rn_ones; 28 29 #define rn_maskhead (mask_rnhead->rnh_treetop) 30 #undef Bcmp 31 #define Bcmp(a, b, l) (l == 0 ? 0 : bcmp((caddr_t)(a), (caddr_t)(b), (u_long)l)) 32 /* 33 * The data structure for the keys is a radix tree with one way 34 * branching removed. The index rn_b at an internal node n represents a bit 35 * position to be tested. The tree is arranged so that all descendants 36 * of a node n have keys whose bits all agree up to position rn_b - 1. 37 * (We say the index of n is rn_b.) 38 * 39 * There is at least one descendant which has a one bit at position rn_b, 40 * and at least one with a zero there. 41 * 42 * A route is determined by a pair of key and mask. We require that the 43 * bit-wise logical and of the key and mask to be the key. 44 * We define the index of a route to associated with the mask to be 45 * the first bit number in the mask where 0 occurs (with bit number 0 46 * representing the highest order bit). 47 * 48 * We say a mask is normal if every bit is 0, past the index of the mask. 49 * If a node n has a descendant (k, m) with index(m) == index(n) == rn_b, 50 * and m is a normal mask, then the route applies to every descendant of n. 51 * If the index(m) < rn_b, this implies the trailing last few bits of k 52 * before bit b are all 0, (and hence consequently true of every descendant 53 * of n), so the route applies to all descendants of the node as well. 54 * 55 * The present version of the code makes no use of normal routes, 56 * but similar logic shows that a non-normal mask m such that 57 * index(m) <= index(n) could potentially apply to many children of n. 58 * Thus, for each non-host route, we attach its mask to a list at an internal 59 * node as high in the tree as we can go. 60 */ 61 62 struct radix_node * 63 rn_search(v, head) 64 struct radix_node *head; 65 register caddr_t v; 66 { 67 register struct radix_node *x; 68 69 for (x = head; x->rn_b >= 0;) { 70 if (x->rn_bmask & v[x->rn_off]) 71 x = x->rn_r; 72 else 73 x = x->rn_l; 74 } 75 return x; 76 }; 77 78 struct radix_node * 79 rn_search_m(v, head, m) 80 struct radix_node *head; 81 register caddr_t v, m; 82 { 83 register struct radix_node *x; 84 85 for (x = head; x->rn_b >= 0;) { 86 if ((x->rn_bmask & m[x->rn_off]) && 87 (x->rn_bmask & v[x->rn_off])) 88 x = x->rn_r; 89 else 90 x = x->rn_l; 91 } 92 return x; 93 }; 94 95 rn_refines(m, n) 96 register caddr_t m, n; 97 { 98 register caddr_t lim, lim2 = lim = n + *(u_char *)n; 99 int longer = (*(u_char *)n++) - (int)(*(u_char *)m++); 100 int masks_are_equal = 1; 101 102 if (longer > 0) 103 lim -= longer; 104 while (n < lim) { 105 if (*n & ~(*m)) 106 return 0; 107 if (*n++ != *m++) 108 masks_are_equal = 0; 109 110 } 111 while (n < lim2) 112 if (*n++) 113 return 0; 114 if (masks_are_equal && (longer < 0)) 115 for (lim2 = m - longer; m < lim2; ) 116 if (*m++) 117 return 1; 118 return (!masks_are_equal); 119 } 120 121 122 struct radix_node * 123 rn_match(v, head) 124 struct radix_node *head; 125 caddr_t v; 126 { 127 register struct radix_node *t = head, *x; 128 register caddr_t cp = v, cp2, cp3; 129 caddr_t cplim, mstart; 130 struct radix_node *saved_t; 131 int off = t->rn_off, vlen = *(u_char *)cp, matched_off; 132 133 /* 134 * Open code rn_search(v, head) to avoid overhead of extra 135 * subroutine call. 136 */ 137 for (; t->rn_b >= 0; ) { 138 if (t->rn_bmask & cp[t->rn_off]) 139 t = t->rn_r; 140 else 141 t = t->rn_l; 142 } 143 /* 144 * See if we match exactly as a host destination 145 */ 146 cp += off; cp2 = t->rn_key + off; cplim = v + vlen; 147 for (; cp < cplim; cp++, cp2++) 148 if (*cp != *cp2) 149 goto on1; 150 /* 151 * This extra grot is in case we are explicitly asked 152 * to look up the default. Ugh! 153 */ 154 if ((t->rn_flags & RNF_ROOT) && t->rn_dupedkey) 155 t = t->rn_dupedkey; 156 return t; 157 on1: 158 matched_off = cp - v; 159 saved_t = t; 160 do { 161 if (t->rn_mask) { 162 /* 163 * Even if we don't match exactly as a hosts; 164 * we may match if the leaf we wound up at is 165 * a route to a net. 166 */ 167 cp3 = matched_off + t->rn_mask; 168 cp2 = matched_off + t->rn_key; 169 for (; cp < cplim; cp++) 170 if ((*cp2++ ^ *cp) & *cp3++) 171 break; 172 if (cp == cplim) 173 return t; 174 cp = matched_off + v; 175 } 176 } while (t = t->rn_dupedkey); 177 t = saved_t; 178 /* start searching up the tree */ 179 do { 180 register struct radix_mask *m; 181 t = t->rn_p; 182 if (m = t->rn_mklist) { 183 /* 184 * After doing measurements here, it may 185 * turn out to be faster to open code 186 * rn_search_m here instead of always 187 * copying and masking. 188 */ 189 off = min(t->rn_off, matched_off); 190 mstart = maskedKey + off; 191 do { 192 cp2 = mstart; 193 cp3 = m->rm_mask + off; 194 for (cp = v + off; cp < cplim;) 195 *cp2++ = *cp++ & *cp3++; 196 x = rn_search(maskedKey, t); 197 while (x && x->rn_mask != m->rm_mask) 198 x = x->rn_dupedkey; 199 if (x && 200 (Bcmp(mstart, x->rn_key + off, 201 vlen - off) == 0)) 202 return x; 203 } while (m = m->rm_mklist); 204 } 205 } while (t != head); 206 return 0; 207 }; 208 209 #ifdef RN_DEBUG 210 int rn_nodenum; 211 struct radix_node *rn_clist; 212 int rn_saveinfo; 213 #endif 214 215 struct radix_node * 216 rn_newpair(v, b, nodes) 217 caddr_t v; 218 int b; 219 struct radix_node nodes[2]; 220 { 221 register struct radix_node *tt = nodes, *t = tt + 1; 222 t->rn_b = b; t->rn_bmask = 0x80 >> (b & 7); 223 t->rn_l = tt; t->rn_off = b >> 3; 224 tt->rn_b = -1; tt->rn_key = v; tt->rn_p = t; 225 tt->rn_flags = t->rn_flags = RNF_ACTIVE; 226 #ifdef RN_DEBUG 227 tt->rn_info = rn_nodenum++; t->rn_info = rn_nodenum++; 228 tt->rn_twin = t; tt->rn_ybro = rn_clist; rn_clist = tt; 229 #endif 230 return t; 231 } 232 233 int rn_debug = 1; 234 struct radix_node * 235 rn_insert(v, head, dupentry, nodes) 236 caddr_t v; 237 struct radix_node *head; 238 int *dupentry; 239 struct radix_node nodes[2]; 240 { 241 int head_off = head->rn_off, vlen = (int)*((u_char *)v); 242 register struct radix_node *t = rn_search(v, head); 243 register caddr_t cp = v + head_off; 244 register int b; 245 struct radix_node *tt; 246 /* 247 *find first bit at which v and t->rn_key differ 248 */ 249 { 250 register caddr_t cp2 = t->rn_key + head_off; 251 register int cmp_res; 252 caddr_t cplim = v + vlen; 253 254 while (cp < cplim) 255 if (*cp2++ != *cp++) 256 goto on1; 257 *dupentry = 1; 258 return t; 259 on1: 260 *dupentry = 0; 261 cmp_res = (cp[-1] ^ cp2[-1]) & 0xff; 262 for (b = (cp - v) << 3; cmp_res; b--) 263 cmp_res >>= 1; 264 } 265 { 266 register struct radix_node *p, *x = head; 267 cp = v; 268 do { 269 p = x; 270 if (cp[x->rn_off] & x->rn_bmask) 271 x = x->rn_r; 272 else x = x->rn_l; 273 } while (b > (unsigned) x->rn_b); /* x->rn_b < b && x->rn_b >= 0 */ 274 #ifdef RN_DEBUG 275 if (rn_debug) 276 printf("Going In:\n"), traverse(p); 277 #endif 278 t = rn_newpair(v, b, nodes); tt = t->rn_l; 279 if ((cp[p->rn_off] & p->rn_bmask) == 0) 280 p->rn_l = t; 281 else 282 p->rn_r = t; 283 x->rn_p = t; t->rn_p = p; /* frees x, p as temp vars below */ 284 if ((cp[t->rn_off] & t->rn_bmask) == 0) { 285 t->rn_r = x; 286 } else { 287 t->rn_r = tt; t->rn_l = x; 288 } 289 #ifdef RN_DEBUG 290 if (rn_debug) 291 printf("Coming out:\n"), traverse(p); 292 #endif 293 } 294 return (tt); 295 } 296 297 struct radix_node * 298 rn_addmask(netmask, search, skip) 299 caddr_t netmask; 300 int search, skip; 301 { 302 register struct radix_node *x; 303 register caddr_t cp, cplim; 304 register int b, mlen, j; 305 int maskduplicated; 306 307 mlen = *(u_char *)netmask; 308 if (search) { 309 x = rn_search(netmask, rn_maskhead); 310 mlen = *(u_char *)netmask; 311 if (Bcmp(netmask, x->rn_key, mlen) == 0) 312 return (x); 313 } 314 R_Malloc(x, struct radix_node *, max_keylen + 2 * sizeof (*x)); 315 if (x == 0) 316 return (0); 317 Bzero(x, max_keylen + 2 * sizeof (*x)); 318 cp = (caddr_t)(x + 2); 319 Bcopy(netmask, cp, mlen); 320 netmask = cp; 321 x = rn_insert(netmask, rn_maskhead, &maskduplicated, x); 322 /* 323 * Calculate index of mask. 324 */ 325 cplim = netmask + mlen; 326 for (cp = netmask + skip; cp < cplim; cp++) 327 if (*(u_char *)cp != 0xff) 328 break; 329 b = (cp - netmask) << 3; 330 if (cp != cplim) { 331 if (*cp != 0) { 332 gotOddMasks = 1; 333 for (j = 0x80; j; b++, j >>= 1) 334 if ((j & *cp) == 0) 335 break; 336 } 337 } 338 x->rn_b = -1 - b; 339 return (x); 340 } 341 342 struct radix_node * 343 rn_addroute(v, netmask, head, treenodes) 344 caddr_t v, netmask; 345 struct radix_node *head; 346 struct radix_node treenodes[2]; 347 { 348 register int j; 349 register caddr_t cp; 350 register struct radix_node *t, *x, *tt; 351 short b = 0, b_leaf; 352 int vlen = *(u_char *)v, mlen, keyduplicated; 353 caddr_t cplim; unsigned char *maskp; 354 struct radix_mask *m, **mp; 355 struct radix_node *saved_tt; 356 357 /* 358 * In dealing with non-contiguous masks, there may be 359 * many different routes which have the same mask. 360 * We will find it useful to have a unique pointer to 361 * the mask to speed avoiding duplicate references at 362 * nodes and possibly save time in calculating indices. 363 */ 364 if (netmask) { 365 x = rn_search(netmask, rn_maskhead); 366 mlen = *(u_char *)netmask; 367 if (Bcmp(netmask, x->rn_key, mlen) != 0) { 368 x = rn_addmask(netmask, 0, head->rn_off); 369 if (x == 0) 370 return (0); 371 } 372 netmask = x->rn_key; 373 b = -1 - x->rn_b; 374 } 375 /* 376 * Deal with duplicated keys: attach node to previous instance 377 */ 378 saved_tt = tt = rn_insert(v, head, &keyduplicated, treenodes); 379 if (keyduplicated) { 380 do { 381 if (tt->rn_mask == netmask) 382 return (0); 383 t = tt; 384 if (netmask == 0 || 385 (tt->rn_mask && rn_refines(netmask, tt->rn_mask))) 386 break; 387 } while (tt = tt->rn_dupedkey); 388 /* 389 * If the mask is not duplicated, we wouldn't 390 * find it among possible duplicate key entries 391 * anyway, so the above test doesn't hurt. 392 * 393 * We sort the masks for a duplicated key the same way as 394 * in a masklist -- most specific to least specific. 395 * This may require the unfortunate nuisance of relocating 396 * the head of the list. 397 */ 398 if (tt && t == saved_tt) { 399 struct radix_node *xx = x; 400 /* link in at head of list */ 401 (tt = treenodes)->rn_dupedkey = t; 402 tt->rn_flags = t->rn_flags; 403 tt->rn_p = x = t->rn_p; 404 if (x->rn_l == t) x->rn_l = tt; else x->rn_r = tt; 405 saved_tt = tt; x = xx; 406 } else { 407 (tt = treenodes)->rn_dupedkey = t->rn_dupedkey; 408 t->rn_dupedkey = tt; 409 } 410 #ifdef RN_DEBUG 411 t=tt+1; tt->rn_info = rn_nodenum++; t->rn_info = rn_nodenum++; 412 tt->rn_twin = t; tt->rn_ybro = rn_clist; rn_clist = tt; 413 #endif 414 t = saved_tt; 415 tt->rn_key = (caddr_t) v; 416 tt->rn_b = -1; 417 tt->rn_flags = t->rn_flags & ~RNF_ROOT; 418 } 419 /* 420 * Put mask in tree. 421 */ 422 if (netmask) { 423 tt->rn_mask = netmask; 424 tt->rn_b = x->rn_b; 425 } 426 t = saved_tt->rn_p; 427 b_leaf = -1 - t->rn_b; 428 if (t->rn_r == saved_tt) x = t->rn_l; else x = t->rn_r; 429 /* Promote general routes from below */ 430 if (x->rn_b < 0) { 431 if (x->rn_mask && (x->rn_b >= b_leaf) && x->rn_mklist == 0) { 432 MKGet(m); 433 if (m) { 434 Bzero(m, sizeof *m); 435 m->rm_b = x->rn_b; 436 m->rm_mask = x->rn_mask; 437 x->rn_mklist = t->rn_mklist = m; 438 } 439 } 440 } else if (x->rn_mklist) { 441 /* 442 * Skip over masks whose index is > that of new node 443 */ 444 for (mp = &x->rn_mklist; m = *mp; mp = &m->rm_mklist) 445 if (m->rm_b >= b_leaf) 446 break; 447 t->rn_mklist = m; *mp = 0; 448 } 449 /* Add new route to highest possible ancestor's list */ 450 if ((netmask == 0) || (b > t->rn_b )) 451 return tt; /* can't lift at all */ 452 b_leaf = tt->rn_b; 453 do { 454 x = t; 455 t = t->rn_p; 456 } while (b <= t->rn_b && x != head); 457 /* 458 * Search through routes associated with node to 459 * insert new route according to index. 460 * For nodes of equal index, place more specific 461 * masks first. 462 */ 463 cplim = netmask + mlen; 464 for (mp = &x->rn_mklist; m = *mp; mp = &m->rm_mklist) { 465 if (m->rm_b < b_leaf) 466 continue; 467 if (m->rm_b > b_leaf) 468 break; 469 if (m->rm_mask == netmask) { 470 m->rm_refs++; 471 tt->rn_mklist = m; 472 return tt; 473 } 474 if (rn_refines(netmask, m->rm_mask)) 475 break; 476 } 477 MKGet(m); 478 if (m == 0) { 479 printf("Mask for route not entered\n"); 480 return (tt); 481 } 482 Bzero(m, sizeof *m); 483 m->rm_b = b_leaf; 484 m->rm_mask = netmask; 485 m->rm_mklist = *mp; 486 *mp = m; 487 tt->rn_mklist = m; 488 return tt; 489 } 490 491 struct radix_node * 492 rn_delete(v, netmask, head) 493 caddr_t v, netmask; 494 struct radix_node *head; 495 { 496 register struct radix_node *t, *p, *x = head; 497 register struct radix_node *tt = rn_search(v, x); 498 int b, head_off = x->rn_off, vlen = * (u_char *) v; 499 struct radix_mask *m, *saved_m, **mp; 500 struct radix_node *dupedkey, *saved_tt = tt; 501 502 if (tt == 0 || 503 Bcmp(v + head_off, tt->rn_key + head_off, vlen - head_off)) 504 return (0); 505 /* 506 * Delete our route from mask lists. 507 */ 508 if (dupedkey = tt->rn_dupedkey) { 509 if (netmask) 510 netmask = rn_search(netmask, rn_maskhead)->rn_key; 511 while (tt->rn_mask != netmask) 512 if ((tt = tt->rn_dupedkey) == 0) 513 return (0); 514 } 515 if (tt->rn_mask == 0 || (saved_m = m = tt->rn_mklist) == 0) 516 goto on1; 517 if (m->rm_mask != tt->rn_mask) { 518 printf("rn_delete: inconsistent annotation\n"); 519 goto on1; 520 } 521 if (--m->rm_refs >= 0) 522 goto on1; 523 b = -1 - tt->rn_b; 524 t = saved_tt->rn_p; 525 if (b > t->rn_b) 526 goto on1; /* Wasn't lifted at all */ 527 do { 528 x = t; 529 t = t->rn_p; 530 } while (b <= t->rn_b && x != head); 531 for (mp = &x->rn_mklist; m = *mp; mp = &m->rm_mklist) 532 if (m == saved_m) { 533 *mp = m->rm_mklist; 534 MKFree(m); 535 break; 536 } 537 if (m == 0) 538 printf("rn_delete: couldn't find our annotation\n"); 539 on1: 540 /* 541 * Eliminate us from tree 542 */ 543 if (tt->rn_flags & RNF_ROOT) 544 return (0); 545 #ifdef RN_DEBUG 546 /* Get us out of the creation list */ 547 for (t = rn_clist; t && t->rn_ybro != tt; t = t->rn_ybro) {} 548 if (t) t->rn_ybro = tt->rn_ybro; 549 #endif RN_DEBUG 550 t = tt->rn_p; 551 if (dupedkey) { 552 if (tt == saved_tt) { 553 x = dupedkey; x->rn_p = t; 554 if (t->rn_l == tt) t->rn_l = x; else t->rn_r = x; 555 } else { 556 for (x = p = saved_tt; p && p->rn_dupedkey != tt;) 557 p = p->rn_dupedkey; 558 if (p) p->rn_dupedkey = tt->rn_dupedkey; 559 else printf("rn_delete: couldn't find us\n"); 560 } 561 t = tt + 1; 562 if (t->rn_flags & RNF_ACTIVE) { 563 #ifndef RN_DEBUG 564 *++x = *t; p = t->rn_p; 565 #else 566 b = t->rn_info; *++x = *t; t->rn_info = b; p = t->rn_p; 567 #endif 568 if (p->rn_l == t) p->rn_l = x; else p->rn_r = x; 569 x->rn_l->rn_p = x; x->rn_r->rn_p = x; 570 } 571 goto out; 572 } 573 if (t->rn_l == tt) x = t->rn_r; else x = t->rn_l; 574 p = t->rn_p; 575 if (p->rn_r == t) p->rn_r = x; else p->rn_l = x; 576 x->rn_p = p; 577 /* 578 * Demote routes attached to us. 579 */ 580 if (t->rn_mklist) { 581 if (x->rn_b >= 0) { 582 for (mp = &x->rn_mklist; m = *mp;) 583 mp = &m->rm_mklist; 584 *mp = t->rn_mklist; 585 } else { 586 for (m = t->rn_mklist; m;) { 587 struct radix_mask *mm = m->rm_mklist; 588 if (m == x->rn_mklist && (--(m->rm_refs) < 0)) { 589 x->rn_mklist = 0; 590 MKFree(m); 591 } else 592 printf("%s %x at %x\n", 593 "rn_delete: Orphaned Mask", m, x); 594 m = mm; 595 } 596 } 597 } 598 /* 599 * We may be holding an active internal node in the tree. 600 */ 601 x = tt + 1; 602 if (t != x) { 603 #ifndef RN_DEBUG 604 *t = *x; 605 #else 606 b = t->rn_info; *t = *x; t->rn_info = b; 607 #endif 608 t->rn_l->rn_p = t; t->rn_r->rn_p = t; 609 p = x->rn_p; 610 if (p->rn_l == x) p->rn_l = t; else p->rn_r = t; 611 } 612 out: 613 tt->rn_flags &= ~RNF_ACTIVE; 614 tt[1].rn_flags &= ~RNF_ACTIVE; 615 return (tt); 616 } 617 618 rn_walk(rn, f, w) 619 register struct radix_node *rn; 620 register int (*f)(); 621 caddr_t w; 622 { 623 int error; 624 struct radix_node *base, *next; 625 /* 626 * This gets complicated because we may delete the node 627 * while applying the function f to it, so we need to calculate 628 * the successor node in advance. 629 */ 630 /* First time through node, go left */ 631 while (rn->rn_b >= 0) 632 rn = rn->rn_l; 633 for (;;) { 634 base = rn; 635 /* If at right child go back up, otherwise, go right */ 636 while (rn->rn_p->rn_r == rn && (rn->rn_flags & RNF_ROOT) == 0) 637 rn = rn->rn_p; 638 /* Find the next *leaf* since next node might vanish, too */ 639 for (rn = rn->rn_p->rn_r; rn->rn_b >= 0;) 640 rn = rn->rn_l; 641 next = rn; 642 /* Process leaves */ 643 while (rn = base) { 644 base = rn->rn_dupedkey; 645 if (!(rn->rn_flags & RNF_ROOT) && (error = (*f)(rn, w))) 646 return (error); 647 } 648 rn = next; 649 if (rn->rn_flags & RNF_ROOT) 650 return (0); 651 } 652 } 653 654 rn_inithead(head, off) 655 void **head; 656 int off; 657 { 658 register struct radix_node_head *rnh; 659 register struct radix_node *t, *tt, *ttt; 660 if (*head) 661 return (1); 662 R_Malloc(rnh, struct radix_node_head *, sizeof (*rnh)); 663 if (rnh == 0) 664 return (0); 665 Bzero(rnh, sizeof (*rnh)); 666 *head = rnh; 667 t = rn_newpair(rn_zeros, off, rnh->rnh_nodes); 668 ttt = rnh->rnh_nodes + 2; 669 t->rn_r = ttt; 670 t->rn_p = t; 671 tt = t->rn_l; 672 tt->rn_flags = t->rn_flags = RNF_ROOT | RNF_ACTIVE; 673 tt->rn_b = -1 - off; 674 *ttt = *tt; 675 ttt->rn_key = rn_ones; 676 rnh->rnh_add = rn_addroute; 677 rnh->rnh_delete = rn_delete; 678 rnh->rnh_match = rn_match; 679 rnh->rnh_walk = rn_walk; 680 rnh->rnh_treetop = t; 681 return (1); 682 } 683 684 rn_init() 685 { 686 char *cp, *cplim; 687 #ifdef KERNEL 688 struct domain *dom; 689 690 for (dom = domains; dom; dom = dom->dom_next) 691 if (dom->dom_maxrtkey > max_keylen) 692 max_keylen = dom->dom_maxrtkey; 693 #endif 694 if (max_keylen == 0) { 695 printf("rn_init: radix functions require max_keylen be set\n"); 696 return; 697 } 698 R_Malloc(rn_zeros, char *, 3 * max_keylen); 699 if (rn_zeros == NULL) 700 panic("rn_init"); 701 Bzero(rn_zeros, 3 * max_keylen); 702 rn_ones = cp = rn_zeros + max_keylen; 703 maskedKey = cplim = rn_ones + max_keylen; 704 while (cp < cplim) 705 *cp++ = -1; 706 if (rn_inithead((void **)&mask_rnhead, 0) == 0) 707 panic("rn_init 2"); 708 } 709