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