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