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