1 /* 2 * Copyright (c) 1982, 1988 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.1 (Berkeley) 11/09/88 18 */ 19 20 /* 21 * Routines to build and maintain radix trees for routing lookups. 22 */ 23 #ifndef RNF_NORMAL 24 typedef unsigned char u_char; 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 char *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 77 static int gotOddMasks; 78 static char maskedKey[MAXKEYLEN]; 79 80 struct radix_node * 81 rn_match(v, head) 82 struct radix_node *head; 83 char *v; 84 { 85 register struct radix_node *t = head, *x; 86 register char *cp = v, *cp2, *cp3; 87 char *cplim, *mstart; 88 struct radix_node *saved_t; 89 int off = t->rn_off, vlen = *(u_char *)cp, head_off, matched_off; 90 91 /* 92 * Open code rn_search(v, head) to avoid overhead of extra 93 * subroutine call. 94 */ 95 for (; t->rn_b >= 0; ) { 96 if (t->rn_bmask & cp[t->rn_off]) 97 t = t->rn_r; 98 else 99 t = t->rn_l; 100 } 101 /* 102 * See if we match exactly as a host destination 103 */ 104 cp += off; cp2 = t->rn_key + off; cplim = v + vlen; 105 for (; cp < cplim; cp++, cp2++) 106 if (*cp != *cp2) 107 goto on1; 108 return t; 109 on1: 110 matched_off = cp - v; 111 saved_t = t; 112 do { 113 if (t->rn_mask) { 114 /* 115 * Even if we don't match exactly as a hosts; 116 * we may match if the leaf we wound up at is 117 * a route to a net. 118 */ 119 cp3 = matched_off + t->rn_mask; 120 for (; cp < cplim; cp++) 121 if ((*cp2++ ^ *cp) & *cp3++) 122 break; 123 if (cp == cplim) 124 return t; 125 } 126 } while (t = t->rn_dupedkey); 127 t = saved_t; 128 /* start searching up the tree */ 129 do { 130 register struct radix_mask *m; 131 t = t->rn_p; 132 if (m = t->rn_mklist) { 133 off = min(t->rn_off, matched_off); 134 mstart = maskedKey + off; 135 do { 136 cp2 = mstart; 137 cp3 = m->rm_mask + off; 138 for (cp = v + off; cp < cplim;) 139 *cp2++ = *cp++ & *cp3++; 140 x = rn_search(maskedKey, t); 141 while (x && x->rn_mask != m->rm_mask) 142 x = x->rn_dupedkey; 143 if (x && 144 (Bcmp(mstart, x->rn_key + off, 145 vlen - off) == 0)) 146 return x; 147 } while (m = m->rm_mklist); 148 } 149 } while (t != head); 150 return 0; 151 }; 152 153 #ifdef RN_DEBUG 154 int rn_nodenum; 155 struct radix_node *rn_clist; 156 int rn_saveinfo; 157 #endif 158 159 struct radix_node * 160 rn_newpair(v, b, nodes) 161 char *v; 162 struct radix_node nodes[2]; 163 { 164 register struct radix_node *tt = nodes, *t = tt + 1; 165 t->rn_b = b; t->rn_bmask = 0x80 >> (b & 7); 166 t->rn_l = tt; t->rn_off = b >> 3; 167 tt->rn_b = -1; tt->rn_key = v; tt->rn_p = t; 168 tt->rn_flags = t->rn_flags = RNF_ACTIVE; 169 #ifdef RN_DEBUG 170 tt->rn_info = rn_nodenum++; t->rn_info = rn_nodenum++; 171 tt->rn_twin = t; tt->rn_ybro = rn_clist; rn_clist = tt; 172 #endif 173 return t; 174 } 175 176 int rn_debug = 1; 177 struct radix_node * 178 rn_insert(v, head, dupentry, nodes) 179 char *v; 180 struct radix_node *head; 181 int *dupentry; 182 struct radix_node nodes[2]; 183 { 184 int head_off = head->rn_off, vlen = (int)*((u_char *)v); 185 register struct radix_node *t = rn_search(v, head); 186 register char *cp = v + head_off; 187 register int b; 188 struct radix_node *tt; 189 /* 190 *find first bit at which v and t->rn_key differ 191 */ 192 { 193 register char *cp2 = t->rn_key + head_off; 194 register int cmp_res; 195 char *cplim = v + vlen; 196 197 while (cp < cplim) 198 if (*cp2++ != *cp++) 199 goto on1; 200 *dupentry = 1; 201 return t; 202 on1: 203 *dupentry = 0; 204 cmp_res = (cp[-1] ^ cp2[-1]) & 0xff; 205 for (b = (cp - v) << 3; cmp_res; b--) 206 cmp_res >>= 1; 207 } 208 { 209 register struct radix_node *p, *x = head; 210 cp = v; 211 do { 212 p = x; 213 if (cp[x->rn_off] & x->rn_bmask) 214 x = x->rn_r; 215 else x = x->rn_l; 216 } while (b > (unsigned) x->rn_b); /* x->rn_b < b && x->rn_b >= 0 */ 217 #ifdef RN_DEBUG 218 if (rn_debug) 219 printf("Going In:\n"), traverse(p); 220 #endif 221 t = rn_newpair(v, b, nodes); tt = t->rn_l; 222 if ((cp[p->rn_off] & p->rn_bmask) == 0) 223 p->rn_l = t; 224 else 225 p->rn_r = t; 226 x->rn_p = t; t->rn_p = p; /* frees x, p as temp vars below */ 227 if ((cp[t->rn_off] & t->rn_bmask) == 0) { 228 t->rn_r = x; 229 } else { 230 t->rn_r = tt; t->rn_l = x; 231 } 232 #ifdef RN_DEBUG 233 if (rn_debug) 234 printf("Coming out:\n"), traverse(p); 235 #endif 236 } 237 return (tt); 238 } 239 240 struct radix_node * 241 rn_addroute(v, netmask, head, treenodes) 242 struct radix_node *head; 243 char *netmask, *v; 244 struct radix_node treenodes[2]; 245 { 246 register int j; 247 register char *cp; 248 register struct radix_node *t, *x, *tt; 249 short b = 0, b_leaf; 250 int vlen = *(u_char *)v, maskduplicated = 0, mlen, keyduplicated; 251 char *cplim; unsigned char *maskp; 252 struct radix_mask *m, **mp; 253 struct radix_node *saved_tt; 254 255 /* 256 * In dealing with non-contiguous masks, there may be 257 * many different routes which have the same mask. 258 * We will find it useful to have a unique pointer to 259 * the mask to speed avoiding duplicate references at 260 * nodes and possibly save time in calculating indices. 261 */ 262 if (netmask) { 263 x = rn_search(netmask, rn_maskhead); 264 mlen = *(u_char *)netmask; 265 if (Bcmp(netmask, x->rn_key, mlen) == 0) { 266 maskduplicated = 1; 267 netmask = x->rn_key; 268 b = -1 - x->rn_b; 269 } 270 } 271 /* 272 * Deal with duplicated keys: attach node to previous instance 273 */ 274 saved_tt = tt = rn_insert(v, head, &keyduplicated, treenodes); 275 if (keyduplicated) { 276 if (tt->rn_mask == netmask) 277 return (0); 278 for (; tt->rn_dupedkey; tt = tt->rn_dupedkey) 279 if (tt->rn_mask == netmask) 280 return (0); 281 /* 282 * If the mask is not duplicated, we wouldn't 283 * find it among possible duplicate key entries 284 * anyway, so the above test doesn't hurt. 285 * 286 * XXX: we really ought to sort the masks 287 * for a duplicated key the same way as in a masklist. 288 * It is an unfortunate pain having to relocate 289 * the head of the list. 290 */ 291 tt->rn_dupedkey = treenodes; 292 tt = treenodes; 293 #ifdef RN_DEBUG 294 t=tt+1; tt->rn_info = rn_nodenum++; t->rn_info = rn_nodenum++; 295 tt->rn_twin = t; tt->rn_ybro = rn_clist; rn_clist = tt; 296 #endif 297 t = saved_tt; 298 tt->rn_key = t->rn_key; 299 tt->rn_b = t->rn_b; 300 tt->rn_flags = t->rn_flags & ~RNF_ROOT; 301 } 302 /* 303 * Put mask in tree. 304 */ 305 if (netmask == 0) 306 goto on1; 307 if (maskduplicated == 0) { 308 Malloc(x, struct radix_node *, MAXKEYLEN + 2 * sizeof (*x)); 309 if (x == 0) 310 return (0); 311 Bzero(x, MAXKEYLEN + 2 * sizeof (*x)); 312 cp = (char *)(x + 2); 313 bcopy(netmask, cp, mlen); 314 netmask = cp; 315 x = rn_insert(netmask, rn_maskhead, &maskduplicated, x); 316 /* 317 * Calculate index of mask. 318 */ 319 cplim = netmask + vlen; 320 for (cp = netmask + head->rn_off; cp < cplim; cp++) 321 if (*(u_char *)cp != 0xff) 322 break; 323 b = (cp - netmask) << 3; 324 if (cp != cplim) { 325 if (*cp != 0) { 326 gotOddMasks = 1; 327 for (j = 0x80; j; b++, j >>= 1) 328 if ((j & *cp) == 0) 329 break; 330 } 331 } 332 x->rn_b = -1 - b; 333 } 334 /* 335 * Set up usual parameters 336 */ 337 tt->rn_mask = netmask; 338 tt->rn_b = x->rn_b; 339 on1: 340 t = saved_tt->rn_p; 341 b_leaf = -1 - t->rn_b; 342 if (t->rn_r == saved_tt) x = t->rn_l; else x = t->rn_r; 343 /* Promote general routes from below */ 344 if (x->rn_b < 0) { 345 if (x->rn_mask && (x->rn_b >= b_leaf)) { 346 MKGet(m); 347 if (m) { 348 Bzero(m, sizeof *m); 349 m->rm_b = x->rn_b; 350 m->rm_mask = x->rn_mask; 351 t->rn_mklist = m; 352 } 353 } 354 } else if (x->rn_mklist) { 355 /* 356 * Skip over masks whose index is > that of new node 357 */ 358 for (mp = &x->rn_mklist; m = *mp; mp = &m->rm_mklist) 359 if (m->rm_b >= b_leaf) 360 break; 361 t->rn_mklist = m; *mp = 0; 362 } 363 /* Add new route to highest possible ancestor's list */ 364 if ((netmask == 0) || (b > t->rn_b )) 365 return tt; /* can't lift at all */ 366 b_leaf = tt->rn_b; 367 do { 368 x = t; 369 t = t->rn_p; 370 } while (b <= t->rn_b && x != head); 371 /* 372 * Search through routes associated with node to 373 * insert new route according to index. 374 * For nodes of equal index, place more specific 375 * masks first. 376 */ 377 cplim = netmask + mlen; 378 for (mp = &x->rn_mklist; m = *mp; mp = &m->rm_mklist) { 379 if (m->rm_b < b_leaf) 380 continue; 381 if (m->rm_b > b_leaf) 382 break; 383 if (m->rm_mask == netmask) { 384 m->rm_refs++; 385 tt->rn_mklist = m; 386 return tt; 387 } 388 maskp = (u_char *)m->rm_mask; 389 for (cp = netmask; cp < cplim; cp++) 390 if (*(u_char *)cp > *maskp++) 391 goto on2; 392 } 393 on2: 394 MKGet(m); 395 if (m == 0) { 396 printf("Mask for route not entered\n"); 397 return (tt); 398 } 399 Bzero(m, sizeof *m); 400 m->rm_b = b_leaf; 401 m->rm_mask = netmask; 402 m->rm_mklist = *mp; 403 *mp = m; 404 tt->rn_mklist = m; 405 return tt; 406 } 407 408 struct radix_node * 409 rn_delete(v, netmask, head) 410 char *v, *netmask; 411 struct radix_node *head; 412 { 413 register struct radix_node *t, *p, *x = head; 414 register struct radix_node *tt = rn_search(v, x); 415 int b, head_off = x->rn_off, vlen = * (u_char *) v; 416 struct radix_mask *m, **mp; 417 struct radix_node *dupedkey, *saved_tt = tt; 418 419 if (tt == 0 || 420 Bcmp(v + head_off, tt->rn_key + head_off, vlen - head_off)) 421 return (0); 422 /* 423 * Delete our route from mask lists. 424 */ 425 if (dupedkey = tt->rn_dupedkey) { 426 if (netmask) 427 netmask = rn_search(netmask, rn_maskhead)->rn_key; 428 for (; tt->rn_mask != netmask; tt = tt->rn_dupedkey) 429 if (tt == 0) 430 return (0); 431 } 432 if (tt->rn_mask == 0) 433 goto on1; 434 if ((m = tt->rn_mklist) && --m->rm_refs >= 0) 435 goto on1; 436 b = -1 - tt->rn_b; 437 t = saved_tt->rn_p; 438 if (b > t->rn_b) 439 goto on1; /* Wasn't lifted at all */ 440 do { 441 x = t; 442 t = t->rn_p; 443 } while (b <= t->rn_b && x != head); 444 for (mp = &x->rn_mklist; m = *mp; mp = &m->rm_mklist) 445 if (m->rm_mask == tt->rn_mask) 446 break; 447 if (m) { 448 if (m->rm_refs < 0) { 449 *mp = m->rm_mklist; 450 MKFree(m); 451 } 452 } else 453 printf("rn_delete: couldn't find our mask\n"); 454 on1: 455 /* 456 * Eliminate us from tree 457 */ 458 if (tt->rn_flags & RNF_ROOT) 459 return (0); 460 #ifdef RN_DEBUG 461 /* Get us out of the creation list */ 462 for (t = rn_clist; t && t->rn_ybro != tt; t = t->rn_ybro) {} 463 if (t) t->rn_ybro = tt->rn_ybro; 464 #endif RN_DEBUG 465 t = tt->rn_p; 466 if (dupedkey) { 467 if (tt == saved_tt) { 468 x = dupedkey; x->rn_p = t; 469 if (t->rn_l == tt) t->rn_l = x; else t->rn_r = x; 470 #ifndef RN_DEBUG 471 x++; t = tt + 1; *x = *t; p = t->rn_p; 472 #else 473 x++; b = x->rn_info; t = tt + 1; *x = *t; p = t->rn_p; 474 x->rn_info = b; 475 #endif 476 if (p->rn_l == t) p->rn_l = x; else p->rn_r = x; 477 x->rn_l->rn_p = x; x->rn_r->rn_p = x; 478 } else { 479 for (p = saved_tt; p && p->rn_dupedkey != tt;) 480 p = p->rn_dupedkey; 481 if (p) p->rn_dupedkey = tt->rn_dupedkey; 482 else printf("rn_delete: couldn't find us\n"); 483 } 484 goto out; 485 } 486 if (t->rn_l == tt) x = t->rn_r; else x = t->rn_l; 487 p = t->rn_p; 488 if (p->rn_r == t) p->rn_r = x; else p->rn_l = x; 489 x->rn_p = p; 490 /* 491 * Demote routes attached to us. 492 */ 493 if (t->rn_mklist) { 494 if (x->rn_b >= 0) { 495 if (m = x->rn_mklist) { 496 while (m->rm_mklist) 497 m = m->rm_mklist; 498 m->rm_mklist = t->rn_mklist; 499 } else 500 x->rn_mklist = m; 501 } else { 502 for (m = t->rn_mklist; m;) { 503 struct radix_mask *mm = m->rm_mklist; 504 MKFree(m); 505 m = mm; 506 } 507 } 508 } 509 /* 510 * We may be holding an active internal node in the tree. 511 */ 512 x = tt + 1; 513 if (t != x) { 514 #ifndef RN_DEBUG 515 *t = *x; 516 #else 517 b = t->rn_info; *t = *x; t->rn_info = b; 518 #endif 519 t->rn_l->rn_p = t; t->rn_r->rn_p = t; 520 p = x->rn_p; 521 if (p->rn_l == x) p->rn_l = t; else p->rn_r = t; 522 } 523 out: 524 tt->rn_flags &= ~RNF_ACTIVE; 525 tt[1].rn_flags &= ~RNF_ACTIVE; 526 return (tt); 527 } 528 char rn_zeros[MAXKEYLEN], rn_ones[MAXKEYLEN]; 529 530 rn_inithead(head, off, af) 531 struct radix_node_head **head; 532 int off; 533 { 534 register struct radix_node_head *hp; 535 register struct radix_node *t, *tt, *ttt; 536 if (*head) 537 return (1); 538 Malloc(hp, struct radix_node_head *, sizeof (*hp)); 539 if (hp == 0) 540 return (0); 541 Bzero(hp, sizeof (*hp)); 542 *head = hp; 543 t = rn_newpair(rn_zeros, off, hp->rnh_nrt.nrt_nodes); 544 ttt = &(hp->rnh_upper); 545 t->rn_r = ttt; 546 t->rn_p = t; 547 tt = t->rn_l; 548 tt->rn_flags = t->rn_flags = RNF_ROOT | RNF_ACTIVE; 549 tt->rn_b = -1 - off; 550 *ttt = *tt; 551 ttt->rn_key = rn_ones; 552 hp->rnh_af = af; 553 hp->rnh_treetop = t; 554 if (radix_node_head == 0) { 555 char *cp = rn_ones, *cplim = rn_ones + MAXKEYLEN; 556 while (cp < cplim) 557 *cp++ = -1; 558 if (rn_inithead(&radix_node_head, 0, 0) == 0) { 559 Free(hp); 560 *head = 0; 561 return (0); 562 } 563 } 564 hp->rnh_next = radix_node_head->rnh_next; 565 if (radix_node_head != hp) 566 radix_node_head->rnh_next = hp; 567 return (1); 568 } 569