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