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