1 /*- 2 * SPDX-License-Identifier: BSD-3-Clause 3 * 4 * Copyright (c) 1988, 1989, 1993 5 * The Regents of the University of California. All rights reserved. 6 * 7 * Redistribution and use in source and binary forms, with or without 8 * modification, are permitted provided that the following conditions 9 * are met: 10 * 1. Redistributions of source code must retain the above copyright 11 * notice, this list of conditions and the following disclaimer. 12 * 2. Redistributions in binary form must reproduce the above copyright 13 * notice, this list of conditions and the following disclaimer in the 14 * documentation and/or other materials provided with the distribution. 15 * 3. Neither the name of the University nor the names of its contributors 16 * may be used to endorse or promote products derived from this software 17 * without specific prior written permission. 18 * 19 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 20 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 21 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 22 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 23 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 24 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 25 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 26 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 27 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 28 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 29 * SUCH DAMAGE. 30 * 31 * @(#)radix.c 8.5 (Berkeley) 5/19/95 32 * $FreeBSD$ 33 */ 34 35 /* 36 * Routines to build and maintain radix trees for routing lookups. 37 */ 38 #include <sys/param.h> 39 #ifdef _KERNEL 40 #include <sys/lock.h> 41 #include <sys/mutex.h> 42 #include <sys/rmlock.h> 43 #include <sys/systm.h> 44 #include <sys/malloc.h> 45 #include <sys/syslog.h> 46 #include <net/radix.h> 47 #else /* !_KERNEL */ 48 #include <stdio.h> 49 #include <strings.h> 50 #include <stdlib.h> 51 #define log(x, arg...) fprintf(stderr, ## arg) 52 #define panic(x) fprintf(stderr, "PANIC: %s", x), exit(1) 53 #define min(a, b) ((a) < (b) ? (a) : (b) ) 54 #include <net/radix.h> 55 #endif /* !_KERNEL */ 56 57 static struct radix_node 58 *rn_insert(void *, struct radix_head *, int *, 59 struct radix_node [2]), 60 *rn_newpair(void *, int, struct radix_node[2]), 61 *rn_search(void *, struct radix_node *), 62 *rn_search_m(void *, struct radix_node *, void *); 63 static struct radix_node *rn_addmask(void *, struct radix_mask_head *, int,int); 64 65 static void rn_detachhead_internal(struct radix_head *); 66 67 #define RADIX_MAX_KEY_LEN 32 68 69 static char rn_zeros[RADIX_MAX_KEY_LEN]; 70 static char rn_ones[RADIX_MAX_KEY_LEN] = { 71 -1, -1, -1, -1, -1, -1, -1, -1, 72 -1, -1, -1, -1, -1, -1, -1, -1, 73 -1, -1, -1, -1, -1, -1, -1, -1, 74 -1, -1, -1, -1, -1, -1, -1, -1, 75 }; 76 77 static int rn_lexobetter(void *m_arg, void *n_arg); 78 static struct radix_mask * 79 rn_new_radix_mask(struct radix_node *tt, 80 struct radix_mask *next); 81 static int rn_satisfies_leaf(char *trial, struct radix_node *leaf, 82 int skip); 83 84 /* 85 * The data structure for the keys is a radix tree with one way 86 * branching removed. The index rn_bit at an internal node n represents a bit 87 * position to be tested. The tree is arranged so that all descendants 88 * of a node n have keys whose bits all agree up to position rn_bit - 1. 89 * (We say the index of n is rn_bit.) 90 * 91 * There is at least one descendant which has a one bit at position rn_bit, 92 * and at least one with a zero there. 93 * 94 * A route is determined by a pair of key and mask. We require that the 95 * bit-wise logical and of the key and mask to be the key. 96 * We define the index of a route to associated with the mask to be 97 * the first bit number in the mask where 0 occurs (with bit number 0 98 * representing the highest order bit). 99 * 100 * We say a mask is normal if every bit is 0, past the index of the mask. 101 * If a node n has a descendant (k, m) with index(m) == index(n) == rn_bit, 102 * and m is a normal mask, then the route applies to every descendant of n. 103 * If the index(m) < rn_bit, this implies the trailing last few bits of k 104 * before bit b are all 0, (and hence consequently true of every descendant 105 * of n), so the route applies to all descendants of the node as well. 106 * 107 * Similar logic shows that a non-normal mask m such that 108 * index(m) <= index(n) could potentially apply to many children of n. 109 * Thus, for each non-host route, we attach its mask to a list at an internal 110 * node as high in the tree as we can go. 111 * 112 * The present version of the code makes use of normal routes in short- 113 * circuiting an explict mask and compare operation when testing whether 114 * a key satisfies a normal route, and also in remembering the unique leaf 115 * that governs a subtree. 116 */ 117 118 /* 119 * Most of the functions in this code assume that the key/mask arguments 120 * are sockaddr-like structures, where the first byte is an u_char 121 * indicating the size of the entire structure. 122 * 123 * To make the assumption more explicit, we use the LEN() macro to access 124 * this field. It is safe to pass an expression with side effects 125 * to LEN() as the argument is evaluated only once. 126 * We cast the result to int as this is the dominant usage. 127 */ 128 #define LEN(x) ( (int) (*(const u_char *)(x)) ) 129 130 /* 131 * XXX THIS NEEDS TO BE FIXED 132 * In the code, pointers to keys and masks are passed as either 133 * 'void *' (because callers use to pass pointers of various kinds), or 134 * 'caddr_t' (which is fine for pointer arithmetics, but not very 135 * clean when you dereference it to access data). Furthermore, caddr_t 136 * is really 'char *', while the natural type to operate on keys and 137 * masks would be 'u_char'. This mismatch require a lot of casts and 138 * intermediate variables to adapt types that clutter the code. 139 */ 140 141 /* 142 * Search a node in the tree matching the key. 143 */ 144 static struct radix_node * 145 rn_search(void *v_arg, struct radix_node *head) 146 { 147 struct radix_node *x; 148 caddr_t v; 149 150 for (x = head, v = v_arg; x->rn_bit >= 0;) { 151 if (x->rn_bmask & v[x->rn_offset]) 152 x = x->rn_right; 153 else 154 x = x->rn_left; 155 } 156 return (x); 157 } 158 159 /* 160 * Same as above, but with an additional mask. 161 * XXX note this function is used only once. 162 */ 163 static struct radix_node * 164 rn_search_m(void *v_arg, struct radix_node *head, void *m_arg) 165 { 166 struct radix_node *x; 167 caddr_t v = v_arg, m = m_arg; 168 169 for (x = head; x->rn_bit >= 0;) { 170 if ((x->rn_bmask & m[x->rn_offset]) && 171 (x->rn_bmask & v[x->rn_offset])) 172 x = x->rn_right; 173 else 174 x = x->rn_left; 175 } 176 return (x); 177 } 178 179 int 180 rn_refines(void *m_arg, void *n_arg) 181 { 182 caddr_t m = m_arg, n = n_arg; 183 caddr_t lim, lim2 = lim = n + LEN(n); 184 int longer = LEN(n++) - LEN(m++); 185 int masks_are_equal = 1; 186 187 if (longer > 0) 188 lim -= longer; 189 while (n < lim) { 190 if (*n & ~(*m)) 191 return (0); 192 if (*n++ != *m++) 193 masks_are_equal = 0; 194 } 195 while (n < lim2) 196 if (*n++) 197 return (0); 198 if (masks_are_equal && (longer < 0)) 199 for (lim2 = m - longer; m < lim2; ) 200 if (*m++) 201 return (1); 202 return (!masks_are_equal); 203 } 204 205 /* 206 * Search for exact match in given @head. 207 * Assume host bits are cleared in @v_arg if @m_arg is not NULL 208 * Note that prefixes with /32 or /128 masks are treated differently 209 * from host routes. 210 */ 211 struct radix_node * 212 rn_lookup(void *v_arg, void *m_arg, struct radix_head *head) 213 { 214 struct radix_node *x; 215 caddr_t netmask; 216 217 if (m_arg != NULL) { 218 /* 219 * Most common case: search exact prefix/mask 220 */ 221 x = rn_addmask(m_arg, head->rnh_masks, 1, 222 head->rnh_treetop->rn_offset); 223 if (x == NULL) 224 return (NULL); 225 netmask = x->rn_key; 226 227 x = rn_match(v_arg, head); 228 229 while (x != NULL && x->rn_mask != netmask) 230 x = x->rn_dupedkey; 231 232 return (x); 233 } 234 235 /* 236 * Search for host address. 237 */ 238 if ((x = rn_match(v_arg, head)) == NULL) 239 return (NULL); 240 241 /* Check if found key is the same */ 242 if (LEN(x->rn_key) != LEN(v_arg) || bcmp(x->rn_key, v_arg, LEN(v_arg))) 243 return (NULL); 244 245 /* Check if this is not host route */ 246 if (x->rn_mask != NULL) 247 return (NULL); 248 249 return (x); 250 } 251 252 static int 253 rn_satisfies_leaf(char *trial, struct radix_node *leaf, int skip) 254 { 255 char *cp = trial, *cp2 = leaf->rn_key, *cp3 = leaf->rn_mask; 256 char *cplim; 257 int length = min(LEN(cp), LEN(cp2)); 258 259 if (cp3 == NULL) 260 cp3 = rn_ones; 261 else 262 length = min(length, LEN(cp3)); 263 cplim = cp + length; cp3 += skip; cp2 += skip; 264 for (cp += skip; cp < cplim; cp++, cp2++, cp3++) 265 if ((*cp ^ *cp2) & *cp3) 266 return (0); 267 return (1); 268 } 269 270 /* 271 * Search for longest-prefix match in given @head 272 */ 273 struct radix_node * 274 rn_match(void *v_arg, struct radix_head *head) 275 { 276 caddr_t v = v_arg; 277 struct radix_node *t = head->rnh_treetop, *x; 278 caddr_t cp = v, cp2; 279 caddr_t cplim; 280 struct radix_node *saved_t, *top = t; 281 int off = t->rn_offset, vlen = LEN(cp), matched_off; 282 int test, b, rn_bit; 283 284 /* 285 * Open code rn_search(v, top) to avoid overhead of extra 286 * subroutine call. 287 */ 288 for (; t->rn_bit >= 0; ) { 289 if (t->rn_bmask & cp[t->rn_offset]) 290 t = t->rn_right; 291 else 292 t = t->rn_left; 293 } 294 /* 295 * See if we match exactly as a host destination 296 * or at least learn how many bits match, for normal mask finesse. 297 * 298 * It doesn't hurt us to limit how many bytes to check 299 * to the length of the mask, since if it matches we had a genuine 300 * match and the leaf we have is the most specific one anyway; 301 * if it didn't match with a shorter length it would fail 302 * with a long one. This wins big for class B&C netmasks which 303 * are probably the most common case... 304 */ 305 if (t->rn_mask) 306 vlen = *(u_char *)t->rn_mask; 307 cp += off; cp2 = t->rn_key + off; cplim = v + vlen; 308 for (; cp < cplim; cp++, cp2++) 309 if (*cp != *cp2) 310 goto on1; 311 /* 312 * This extra grot is in case we are explicitly asked 313 * to look up the default. Ugh! 314 * 315 * Never return the root node itself, it seems to cause a 316 * lot of confusion. 317 */ 318 if (t->rn_flags & RNF_ROOT) 319 t = t->rn_dupedkey; 320 return (t); 321 on1: 322 test = (*cp ^ *cp2) & 0xff; /* find first bit that differs */ 323 for (b = 7; (test >>= 1) > 0;) 324 b--; 325 matched_off = cp - v; 326 b += matched_off << 3; 327 rn_bit = -1 - b; 328 /* 329 * If there is a host route in a duped-key chain, it will be first. 330 */ 331 if ((saved_t = t)->rn_mask == 0) 332 t = t->rn_dupedkey; 333 for (; t; t = t->rn_dupedkey) 334 /* 335 * Even if we don't match exactly as a host, 336 * we may match if the leaf we wound up at is 337 * a route to a net. 338 */ 339 if (t->rn_flags & RNF_NORMAL) { 340 if (rn_bit <= t->rn_bit) 341 return (t); 342 } else if (rn_satisfies_leaf(v, t, matched_off)) 343 return (t); 344 t = saved_t; 345 /* start searching up the tree */ 346 do { 347 struct radix_mask *m; 348 t = t->rn_parent; 349 m = t->rn_mklist; 350 /* 351 * If non-contiguous masks ever become important 352 * we can restore the masking and open coding of 353 * the search and satisfaction test and put the 354 * calculation of "off" back before the "do". 355 */ 356 while (m) { 357 if (m->rm_flags & RNF_NORMAL) { 358 if (rn_bit <= m->rm_bit) 359 return (m->rm_leaf); 360 } else { 361 off = min(t->rn_offset, matched_off); 362 x = rn_search_m(v, t, m->rm_mask); 363 while (x && x->rn_mask != m->rm_mask) 364 x = x->rn_dupedkey; 365 if (x && rn_satisfies_leaf(v, x, off)) 366 return (x); 367 } 368 m = m->rm_mklist; 369 } 370 } while (t != top); 371 return (0); 372 } 373 374 #ifdef RN_DEBUG 375 int rn_nodenum; 376 struct radix_node *rn_clist; 377 int rn_saveinfo; 378 int rn_debug = 1; 379 #endif 380 381 /* 382 * Whenever we add a new leaf to the tree, we also add a parent node, 383 * so we allocate them as an array of two elements: the first one must be 384 * the leaf (see RNTORT() in route.c), the second one is the parent. 385 * This routine initializes the relevant fields of the nodes, so that 386 * the leaf is the left child of the parent node, and both nodes have 387 * (almost) all all fields filled as appropriate. 388 * (XXX some fields are left unset, see the '#if 0' section). 389 * The function returns a pointer to the parent node. 390 */ 391 392 static struct radix_node * 393 rn_newpair(void *v, int b, struct radix_node nodes[2]) 394 { 395 struct radix_node *tt = nodes, *t = tt + 1; 396 t->rn_bit = b; 397 t->rn_bmask = 0x80 >> (b & 7); 398 t->rn_left = tt; 399 t->rn_offset = b >> 3; 400 401 #if 0 /* XXX perhaps we should fill these fields as well. */ 402 t->rn_parent = t->rn_right = NULL; 403 404 tt->rn_mask = NULL; 405 tt->rn_dupedkey = NULL; 406 tt->rn_bmask = 0; 407 #endif 408 tt->rn_bit = -1; 409 tt->rn_key = (caddr_t)v; 410 tt->rn_parent = t; 411 tt->rn_flags = t->rn_flags = RNF_ACTIVE; 412 tt->rn_mklist = t->rn_mklist = 0; 413 #ifdef RN_DEBUG 414 tt->rn_info = rn_nodenum++; t->rn_info = rn_nodenum++; 415 tt->rn_twin = t; 416 tt->rn_ybro = rn_clist; 417 rn_clist = tt; 418 #endif 419 return (t); 420 } 421 422 static struct radix_node * 423 rn_insert(void *v_arg, struct radix_head *head, int *dupentry, 424 struct radix_node nodes[2]) 425 { 426 caddr_t v = v_arg; 427 struct radix_node *top = head->rnh_treetop; 428 int head_off = top->rn_offset, vlen = LEN(v); 429 struct radix_node *t = rn_search(v_arg, top); 430 caddr_t cp = v + head_off; 431 unsigned b; 432 struct radix_node *p, *tt, *x; 433 /* 434 * Find first bit at which v and t->rn_key differ 435 */ 436 caddr_t cp2 = t->rn_key + head_off; 437 int cmp_res; 438 caddr_t cplim = v + vlen; 439 440 while (cp < cplim) 441 if (*cp2++ != *cp++) 442 goto on1; 443 *dupentry = 1; 444 return (t); 445 on1: 446 *dupentry = 0; 447 cmp_res = (cp[-1] ^ cp2[-1]) & 0xff; 448 for (b = (cp - v) << 3; cmp_res; b--) 449 cmp_res >>= 1; 450 451 x = top; 452 cp = v; 453 do { 454 p = x; 455 if (cp[x->rn_offset] & x->rn_bmask) 456 x = x->rn_right; 457 else 458 x = x->rn_left; 459 } while (b > (unsigned) x->rn_bit); 460 /* x->rn_bit < b && x->rn_bit >= 0 */ 461 #ifdef RN_DEBUG 462 if (rn_debug) 463 log(LOG_DEBUG, "rn_insert: Going In:\n"), traverse(p); 464 #endif 465 t = rn_newpair(v_arg, b, nodes); 466 tt = t->rn_left; 467 if ((cp[p->rn_offset] & p->rn_bmask) == 0) 468 p->rn_left = t; 469 else 470 p->rn_right = t; 471 x->rn_parent = t; 472 t->rn_parent = p; /* frees x, p as temp vars below */ 473 if ((cp[t->rn_offset] & t->rn_bmask) == 0) { 474 t->rn_right = x; 475 } else { 476 t->rn_right = tt; 477 t->rn_left = x; 478 } 479 #ifdef RN_DEBUG 480 if (rn_debug) 481 log(LOG_DEBUG, "rn_insert: Coming Out:\n"), traverse(p); 482 #endif 483 return (tt); 484 } 485 486 static struct radix_node * 487 rn_addmask(void *n_arg, struct radix_mask_head *maskhead, int search, int skip) 488 { 489 unsigned char *netmask = n_arg; 490 unsigned char *cp, *cplim; 491 struct radix_node *x; 492 int b = 0, mlen, j; 493 int maskduplicated, isnormal; 494 struct radix_node *saved_x; 495 unsigned char addmask_key[RADIX_MAX_KEY_LEN]; 496 497 if ((mlen = LEN(netmask)) > RADIX_MAX_KEY_LEN) 498 mlen = RADIX_MAX_KEY_LEN; 499 if (skip == 0) 500 skip = 1; 501 if (mlen <= skip) 502 return (maskhead->mask_nodes); 503 504 bzero(addmask_key, RADIX_MAX_KEY_LEN); 505 if (skip > 1) 506 bcopy(rn_ones + 1, addmask_key + 1, skip - 1); 507 bcopy(netmask + skip, addmask_key + skip, mlen - skip); 508 /* 509 * Trim trailing zeroes. 510 */ 511 for (cp = addmask_key + mlen; (cp > addmask_key) && cp[-1] == 0;) 512 cp--; 513 mlen = cp - addmask_key; 514 if (mlen <= skip) 515 return (maskhead->mask_nodes); 516 *addmask_key = mlen; 517 x = rn_search(addmask_key, maskhead->head.rnh_treetop); 518 if (bcmp(addmask_key, x->rn_key, mlen) != 0) 519 x = NULL; 520 if (x || search) 521 return (x); 522 R_Zalloc(x, struct radix_node *, RADIX_MAX_KEY_LEN + 2 * sizeof (*x)); 523 if ((saved_x = x) == NULL) 524 return (0); 525 netmask = cp = (unsigned char *)(x + 2); 526 bcopy(addmask_key, cp, mlen); 527 x = rn_insert(cp, &maskhead->head, &maskduplicated, x); 528 if (maskduplicated) { 529 log(LOG_ERR, "rn_addmask: mask impossibly already in tree"); 530 R_Free(saved_x); 531 return (x); 532 } 533 /* 534 * Calculate index of mask, and check for normalcy. 535 * First find the first byte with a 0 bit, then if there are 536 * more bits left (remember we already trimmed the trailing 0's), 537 * the bits should be contiguous, otherwise we have got 538 * a non-contiguous mask. 539 */ 540 #define CONTIG(_c) (((~(_c) + 1) & (_c)) == (unsigned char)(~(_c) + 1)) 541 cplim = netmask + mlen; 542 isnormal = 1; 543 for (cp = netmask + skip; (cp < cplim) && *(u_char *)cp == 0xff;) 544 cp++; 545 if (cp != cplim) { 546 for (j = 0x80; (j & *cp) != 0; j >>= 1) 547 b++; 548 if (!CONTIG(*cp) || cp != (cplim - 1)) 549 isnormal = 0; 550 } 551 b += (cp - netmask) << 3; 552 x->rn_bit = -1 - b; 553 if (isnormal) 554 x->rn_flags |= RNF_NORMAL; 555 return (x); 556 } 557 558 static int /* XXX: arbitrary ordering for non-contiguous masks */ 559 rn_lexobetter(void *m_arg, void *n_arg) 560 { 561 u_char *mp = m_arg, *np = n_arg, *lim; 562 563 if (LEN(mp) > LEN(np)) 564 return (1); /* not really, but need to check longer one first */ 565 if (LEN(mp) == LEN(np)) 566 for (lim = mp + LEN(mp); mp < lim;) 567 if (*mp++ > *np++) 568 return (1); 569 return (0); 570 } 571 572 static struct radix_mask * 573 rn_new_radix_mask(struct radix_node *tt, struct radix_mask *next) 574 { 575 struct radix_mask *m; 576 577 R_Malloc(m, struct radix_mask *, sizeof (struct radix_mask)); 578 if (m == NULL) { 579 log(LOG_ERR, "Failed to allocate route mask\n"); 580 return (0); 581 } 582 bzero(m, sizeof(*m)); 583 m->rm_bit = tt->rn_bit; 584 m->rm_flags = tt->rn_flags; 585 if (tt->rn_flags & RNF_NORMAL) 586 m->rm_leaf = tt; 587 else 588 m->rm_mask = tt->rn_mask; 589 m->rm_mklist = next; 590 tt->rn_mklist = m; 591 return (m); 592 } 593 594 struct radix_node * 595 rn_addroute(void *v_arg, void *n_arg, struct radix_head *head, 596 struct radix_node treenodes[2]) 597 { 598 caddr_t v = (caddr_t)v_arg, netmask = (caddr_t)n_arg; 599 struct radix_node *t, *x = NULL, *tt; 600 struct radix_node *saved_tt, *top = head->rnh_treetop; 601 short b = 0, b_leaf = 0; 602 int keyduplicated; 603 caddr_t mmask; 604 struct radix_mask *m, **mp; 605 606 /* 607 * In dealing with non-contiguous masks, there may be 608 * many different routes which have the same mask. 609 * We will find it useful to have a unique pointer to 610 * the mask to speed avoiding duplicate references at 611 * nodes and possibly save time in calculating indices. 612 */ 613 if (netmask) { 614 x = rn_addmask(netmask, head->rnh_masks, 0, top->rn_offset); 615 if (x == NULL) 616 return (0); 617 b_leaf = x->rn_bit; 618 b = -1 - x->rn_bit; 619 netmask = x->rn_key; 620 } 621 /* 622 * Deal with duplicated keys: attach node to previous instance 623 */ 624 saved_tt = tt = rn_insert(v, head, &keyduplicated, treenodes); 625 if (keyduplicated) { 626 for (t = tt; tt; t = tt, tt = tt->rn_dupedkey) { 627 if (tt->rn_mask == netmask) 628 return (0); 629 if (netmask == 0 || 630 (tt->rn_mask && 631 ((b_leaf < tt->rn_bit) /* index(netmask) > node */ 632 || rn_refines(netmask, tt->rn_mask) 633 || rn_lexobetter(netmask, tt->rn_mask)))) 634 break; 635 } 636 /* 637 * If the mask is not duplicated, we wouldn't 638 * find it among possible duplicate key entries 639 * anyway, so the above test doesn't hurt. 640 * 641 * We sort the masks for a duplicated key the same way as 642 * in a masklist -- most specific to least specific. 643 * This may require the unfortunate nuisance of relocating 644 * the head of the list. 645 * 646 * We also reverse, or doubly link the list through the 647 * parent pointer. 648 */ 649 if (tt == saved_tt) { 650 struct radix_node *xx = x; 651 /* link in at head of list */ 652 (tt = treenodes)->rn_dupedkey = t; 653 tt->rn_flags = t->rn_flags; 654 tt->rn_parent = x = t->rn_parent; 655 t->rn_parent = tt; /* parent */ 656 if (x->rn_left == t) 657 x->rn_left = tt; 658 else 659 x->rn_right = tt; 660 saved_tt = tt; x = xx; 661 } else { 662 (tt = treenodes)->rn_dupedkey = t->rn_dupedkey; 663 t->rn_dupedkey = tt; 664 tt->rn_parent = t; /* parent */ 665 if (tt->rn_dupedkey) /* parent */ 666 tt->rn_dupedkey->rn_parent = tt; /* parent */ 667 } 668 #ifdef RN_DEBUG 669 t=tt+1; tt->rn_info = rn_nodenum++; t->rn_info = rn_nodenum++; 670 tt->rn_twin = t; tt->rn_ybro = rn_clist; rn_clist = tt; 671 #endif 672 tt->rn_key = (caddr_t) v; 673 tt->rn_bit = -1; 674 tt->rn_flags = RNF_ACTIVE; 675 } 676 /* 677 * Put mask in tree. 678 */ 679 if (netmask) { 680 tt->rn_mask = netmask; 681 tt->rn_bit = x->rn_bit; 682 tt->rn_flags |= x->rn_flags & RNF_NORMAL; 683 } 684 t = saved_tt->rn_parent; 685 if (keyduplicated) 686 goto on2; 687 b_leaf = -1 - t->rn_bit; 688 if (t->rn_right == saved_tt) 689 x = t->rn_left; 690 else 691 x = t->rn_right; 692 /* Promote general routes from below */ 693 if (x->rn_bit < 0) { 694 for (mp = &t->rn_mklist; x; x = x->rn_dupedkey) 695 if (x->rn_mask && (x->rn_bit >= b_leaf) && x->rn_mklist == 0) { 696 *mp = m = rn_new_radix_mask(x, 0); 697 if (m) 698 mp = &m->rm_mklist; 699 } 700 } else if (x->rn_mklist) { 701 /* 702 * Skip over masks whose index is > that of new node 703 */ 704 for (mp = &x->rn_mklist; (m = *mp); mp = &m->rm_mklist) 705 if (m->rm_bit >= b_leaf) 706 break; 707 t->rn_mklist = m; *mp = NULL; 708 } 709 on2: 710 /* Add new route to highest possible ancestor's list */ 711 if ((netmask == 0) || (b > t->rn_bit )) 712 return (tt); /* can't lift at all */ 713 b_leaf = tt->rn_bit; 714 do { 715 x = t; 716 t = t->rn_parent; 717 } while (b <= t->rn_bit && x != top); 718 /* 719 * Search through routes associated with node to 720 * insert new route according to index. 721 * Need same criteria as when sorting dupedkeys to avoid 722 * double loop on deletion. 723 */ 724 for (mp = &x->rn_mklist; (m = *mp); mp = &m->rm_mklist) { 725 if (m->rm_bit < b_leaf) 726 continue; 727 if (m->rm_bit > b_leaf) 728 break; 729 if (m->rm_flags & RNF_NORMAL) { 730 mmask = m->rm_leaf->rn_mask; 731 if (tt->rn_flags & RNF_NORMAL) { 732 log(LOG_ERR, 733 "Non-unique normal route, mask not entered\n"); 734 return (tt); 735 } 736 } else 737 mmask = m->rm_mask; 738 if (mmask == netmask) { 739 m->rm_refs++; 740 tt->rn_mklist = m; 741 return (tt); 742 } 743 if (rn_refines(netmask, mmask) 744 || rn_lexobetter(netmask, mmask)) 745 break; 746 } 747 *mp = rn_new_radix_mask(tt, *mp); 748 return (tt); 749 } 750 751 struct radix_node * 752 rn_delete(void *v_arg, void *netmask_arg, struct radix_head *head) 753 { 754 struct radix_node *t, *p, *x, *tt; 755 struct radix_mask *m, *saved_m, **mp; 756 struct radix_node *dupedkey, *saved_tt, *top; 757 caddr_t v, netmask; 758 int b, head_off, vlen; 759 760 v = v_arg; 761 netmask = netmask_arg; 762 x = head->rnh_treetop; 763 tt = rn_search(v, x); 764 head_off = x->rn_offset; 765 vlen = LEN(v); 766 saved_tt = tt; 767 top = x; 768 if (tt == NULL || 769 bcmp(v + head_off, tt->rn_key + head_off, vlen - head_off)) 770 return (0); 771 /* 772 * Delete our route from mask lists. 773 */ 774 if (netmask) { 775 x = rn_addmask(netmask, head->rnh_masks, 1, head_off); 776 if (x == NULL) 777 return (0); 778 netmask = x->rn_key; 779 while (tt->rn_mask != netmask) 780 if ((tt = tt->rn_dupedkey) == NULL) 781 return (0); 782 } 783 if (tt->rn_mask == 0 || (saved_m = m = tt->rn_mklist) == NULL) 784 goto on1; 785 if (tt->rn_flags & RNF_NORMAL) { 786 if (m->rm_leaf != tt || m->rm_refs > 0) { 787 log(LOG_ERR, "rn_delete: inconsistent annotation\n"); 788 return (0); /* dangling ref could cause disaster */ 789 } 790 } else { 791 if (m->rm_mask != tt->rn_mask) { 792 log(LOG_ERR, "rn_delete: inconsistent annotation\n"); 793 goto on1; 794 } 795 if (--m->rm_refs >= 0) 796 goto on1; 797 } 798 b = -1 - tt->rn_bit; 799 t = saved_tt->rn_parent; 800 if (b > t->rn_bit) 801 goto on1; /* Wasn't lifted at all */ 802 do { 803 x = t; 804 t = t->rn_parent; 805 } while (b <= t->rn_bit && x != top); 806 for (mp = &x->rn_mklist; (m = *mp); mp = &m->rm_mklist) 807 if (m == saved_m) { 808 *mp = m->rm_mklist; 809 R_Free(m); 810 break; 811 } 812 if (m == NULL) { 813 log(LOG_ERR, "rn_delete: couldn't find our annotation\n"); 814 if (tt->rn_flags & RNF_NORMAL) 815 return (0); /* Dangling ref to us */ 816 } 817 on1: 818 /* 819 * Eliminate us from tree 820 */ 821 if (tt->rn_flags & RNF_ROOT) 822 return (0); 823 #ifdef RN_DEBUG 824 /* Get us out of the creation list */ 825 for (t = rn_clist; t && t->rn_ybro != tt; t = t->rn_ybro) {} 826 if (t) t->rn_ybro = tt->rn_ybro; 827 #endif 828 t = tt->rn_parent; 829 dupedkey = saved_tt->rn_dupedkey; 830 if (dupedkey) { 831 /* 832 * Here, tt is the deletion target and 833 * saved_tt is the head of the dupekey chain. 834 */ 835 if (tt == saved_tt) { 836 /* remove from head of chain */ 837 x = dupedkey; x->rn_parent = t; 838 if (t->rn_left == tt) 839 t->rn_left = x; 840 else 841 t->rn_right = x; 842 } else { 843 /* find node in front of tt on the chain */ 844 for (x = p = saved_tt; p && p->rn_dupedkey != tt;) 845 p = p->rn_dupedkey; 846 if (p) { 847 p->rn_dupedkey = tt->rn_dupedkey; 848 if (tt->rn_dupedkey) /* parent */ 849 tt->rn_dupedkey->rn_parent = p; 850 /* parent */ 851 } else log(LOG_ERR, "rn_delete: couldn't find us\n"); 852 } 853 t = tt + 1; 854 if (t->rn_flags & RNF_ACTIVE) { 855 #ifndef RN_DEBUG 856 *++x = *t; 857 p = t->rn_parent; 858 #else 859 b = t->rn_info; 860 *++x = *t; 861 t->rn_info = b; 862 p = t->rn_parent; 863 #endif 864 if (p->rn_left == t) 865 p->rn_left = x; 866 else 867 p->rn_right = x; 868 x->rn_left->rn_parent = x; 869 x->rn_right->rn_parent = x; 870 } 871 goto out; 872 } 873 if (t->rn_left == tt) 874 x = t->rn_right; 875 else 876 x = t->rn_left; 877 p = t->rn_parent; 878 if (p->rn_right == t) 879 p->rn_right = x; 880 else 881 p->rn_left = x; 882 x->rn_parent = p; 883 /* 884 * Demote routes attached to us. 885 */ 886 if (t->rn_mklist) { 887 if (x->rn_bit >= 0) { 888 for (mp = &x->rn_mklist; (m = *mp);) 889 mp = &m->rm_mklist; 890 *mp = t->rn_mklist; 891 } else { 892 /* If there are any key,mask pairs in a sibling 893 duped-key chain, some subset will appear sorted 894 in the same order attached to our mklist */ 895 for (m = t->rn_mklist; m && x; x = x->rn_dupedkey) 896 if (m == x->rn_mklist) { 897 struct radix_mask *mm = m->rm_mklist; 898 x->rn_mklist = 0; 899 if (--(m->rm_refs) < 0) 900 R_Free(m); 901 m = mm; 902 } 903 if (m) 904 log(LOG_ERR, 905 "rn_delete: Orphaned Mask %p at %p\n", 906 m, x); 907 } 908 } 909 /* 910 * We may be holding an active internal node in the tree. 911 */ 912 x = tt + 1; 913 if (t != x) { 914 #ifndef RN_DEBUG 915 *t = *x; 916 #else 917 b = t->rn_info; 918 *t = *x; 919 t->rn_info = b; 920 #endif 921 t->rn_left->rn_parent = t; 922 t->rn_right->rn_parent = t; 923 p = x->rn_parent; 924 if (p->rn_left == x) 925 p->rn_left = t; 926 else 927 p->rn_right = t; 928 } 929 out: 930 tt->rn_flags &= ~RNF_ACTIVE; 931 tt[1].rn_flags &= ~RNF_ACTIVE; 932 return (tt); 933 } 934 935 /* 936 * This is the same as rn_walktree() except for the parameters and the 937 * exit. 938 */ 939 int 940 rn_walktree_from(struct radix_head *h, void *a, void *m, 941 walktree_f_t *f, void *w) 942 { 943 int error; 944 struct radix_node *base, *next; 945 u_char *xa = (u_char *)a; 946 u_char *xm = (u_char *)m; 947 struct radix_node *rn, *last = NULL; /* shut up gcc */ 948 int stopping = 0; 949 int lastb; 950 951 KASSERT(m != NULL, ("%s: mask needs to be specified", __func__)); 952 953 /* 954 * rn_search_m is sort-of-open-coded here. We cannot use the 955 * function because we need to keep track of the last node seen. 956 */ 957 /* printf("about to search\n"); */ 958 for (rn = h->rnh_treetop; rn->rn_bit >= 0; ) { 959 last = rn; 960 /* printf("rn_bit %d, rn_bmask %x, xm[rn_offset] %x\n", 961 rn->rn_bit, rn->rn_bmask, xm[rn->rn_offset]); */ 962 if (!(rn->rn_bmask & xm[rn->rn_offset])) { 963 break; 964 } 965 if (rn->rn_bmask & xa[rn->rn_offset]) { 966 rn = rn->rn_right; 967 } else { 968 rn = rn->rn_left; 969 } 970 } 971 /* printf("done searching\n"); */ 972 973 /* 974 * Two cases: either we stepped off the end of our mask, 975 * in which case last == rn, or we reached a leaf, in which 976 * case we want to start from the leaf. 977 */ 978 if (rn->rn_bit >= 0) 979 rn = last; 980 lastb = last->rn_bit; 981 982 /* printf("rn %p, lastb %d\n", rn, lastb);*/ 983 984 /* 985 * This gets complicated because we may delete the node 986 * while applying the function f to it, so we need to calculate 987 * the successor node in advance. 988 */ 989 while (rn->rn_bit >= 0) 990 rn = rn->rn_left; 991 992 while (!stopping) { 993 /* printf("node %p (%d)\n", rn, rn->rn_bit); */ 994 base = rn; 995 /* If at right child go back up, otherwise, go right */ 996 while (rn->rn_parent->rn_right == rn 997 && !(rn->rn_flags & RNF_ROOT)) { 998 rn = rn->rn_parent; 999 1000 /* if went up beyond last, stop */ 1001 if (rn->rn_bit <= lastb) { 1002 stopping = 1; 1003 /* printf("up too far\n"); */ 1004 /* 1005 * XXX we should jump to the 'Process leaves' 1006 * part, because the values of 'rn' and 'next' 1007 * we compute will not be used. Not a big deal 1008 * because this loop will terminate, but it is 1009 * inefficient and hard to understand! 1010 */ 1011 } 1012 } 1013 1014 /* 1015 * At the top of the tree, no need to traverse the right 1016 * half, prevent the traversal of the entire tree in the 1017 * case of default route. 1018 */ 1019 if (rn->rn_parent->rn_flags & RNF_ROOT) 1020 stopping = 1; 1021 1022 /* Find the next *leaf* since next node might vanish, too */ 1023 for (rn = rn->rn_parent->rn_right; rn->rn_bit >= 0;) 1024 rn = rn->rn_left; 1025 next = rn; 1026 /* Process leaves */ 1027 while ((rn = base) != NULL) { 1028 base = rn->rn_dupedkey; 1029 /* printf("leaf %p\n", rn); */ 1030 if (!(rn->rn_flags & RNF_ROOT) 1031 && (error = (*f)(rn, w))) 1032 return (error); 1033 } 1034 rn = next; 1035 1036 if (rn->rn_flags & RNF_ROOT) { 1037 /* printf("root, stopping"); */ 1038 stopping = 1; 1039 } 1040 } 1041 return (0); 1042 } 1043 1044 int 1045 rn_walktree(struct radix_head *h, walktree_f_t *f, void *w) 1046 { 1047 int error; 1048 struct radix_node *base, *next; 1049 struct radix_node *rn = h->rnh_treetop; 1050 /* 1051 * This gets complicated because we may delete the node 1052 * while applying the function f to it, so we need to calculate 1053 * the successor node in advance. 1054 */ 1055 1056 /* First time through node, go left */ 1057 while (rn->rn_bit >= 0) 1058 rn = rn->rn_left; 1059 for (;;) { 1060 base = rn; 1061 /* If at right child go back up, otherwise, go right */ 1062 while (rn->rn_parent->rn_right == rn 1063 && (rn->rn_flags & RNF_ROOT) == 0) 1064 rn = rn->rn_parent; 1065 /* Find the next *leaf* since next node might vanish, too */ 1066 for (rn = rn->rn_parent->rn_right; rn->rn_bit >= 0;) 1067 rn = rn->rn_left; 1068 next = rn; 1069 /* Process leaves */ 1070 while ((rn = base)) { 1071 base = rn->rn_dupedkey; 1072 if (!(rn->rn_flags & RNF_ROOT) 1073 && (error = (*f)(rn, w))) 1074 return (error); 1075 } 1076 rn = next; 1077 if (rn->rn_flags & RNF_ROOT) 1078 return (0); 1079 } 1080 /* NOTREACHED */ 1081 } 1082 1083 /* 1084 * Initialize an empty tree. This has 3 nodes, which are passed 1085 * via base_nodes (in the order <left,root,right>) and are 1086 * marked RNF_ROOT so they cannot be freed. 1087 * The leaves have all-zero and all-one keys, with significant 1088 * bits starting at 'off'. 1089 */ 1090 void 1091 rn_inithead_internal(struct radix_head *rh, struct radix_node *base_nodes, int off) 1092 { 1093 struct radix_node *t, *tt, *ttt; 1094 1095 t = rn_newpair(rn_zeros, off, base_nodes); 1096 ttt = base_nodes + 2; 1097 t->rn_right = ttt; 1098 t->rn_parent = t; 1099 tt = t->rn_left; /* ... which in turn is base_nodes */ 1100 tt->rn_flags = t->rn_flags = RNF_ROOT | RNF_ACTIVE; 1101 tt->rn_bit = -1 - off; 1102 *ttt = *tt; 1103 ttt->rn_key = rn_ones; 1104 1105 rh->rnh_treetop = t; 1106 } 1107 1108 static void 1109 rn_detachhead_internal(struct radix_head *head) 1110 { 1111 1112 KASSERT((head != NULL), 1113 ("%s: head already freed", __func__)); 1114 1115 /* Free <left,root,right> nodes. */ 1116 R_Free(head); 1117 } 1118 1119 /* Functions used by 'struct radix_node_head' users */ 1120 1121 int 1122 rn_inithead(void **head, int off) 1123 { 1124 struct radix_node_head *rnh; 1125 struct radix_mask_head *rmh; 1126 1127 rnh = *head; 1128 rmh = NULL; 1129 1130 if (*head != NULL) 1131 return (1); 1132 1133 R_Zalloc(rnh, struct radix_node_head *, sizeof (*rnh)); 1134 R_Zalloc(rmh, struct radix_mask_head *, sizeof (*rmh)); 1135 if (rnh == NULL || rmh == NULL) { 1136 if (rnh != NULL) 1137 R_Free(rnh); 1138 if (rmh != NULL) 1139 R_Free(rmh); 1140 return (0); 1141 } 1142 1143 /* Init trees */ 1144 rn_inithead_internal(&rnh->rh, rnh->rnh_nodes, off); 1145 rn_inithead_internal(&rmh->head, rmh->mask_nodes, 0); 1146 *head = rnh; 1147 rnh->rh.rnh_masks = rmh; 1148 1149 /* Finally, set base callbacks */ 1150 rnh->rnh_addaddr = rn_addroute; 1151 rnh->rnh_deladdr = rn_delete; 1152 rnh->rnh_matchaddr = rn_match; 1153 rnh->rnh_lookup = rn_lookup; 1154 rnh->rnh_walktree = rn_walktree; 1155 rnh->rnh_walktree_from = rn_walktree_from; 1156 1157 return (1); 1158 } 1159 1160 static int 1161 rn_freeentry(struct radix_node *rn, void *arg) 1162 { 1163 struct radix_head * const rnh = arg; 1164 struct radix_node *x; 1165 1166 x = (struct radix_node *)rn_delete(rn + 2, NULL, rnh); 1167 if (x != NULL) 1168 R_Free(x); 1169 return (0); 1170 } 1171 1172 int 1173 rn_detachhead(void **head) 1174 { 1175 struct radix_node_head *rnh; 1176 1177 KASSERT((head != NULL && *head != NULL), 1178 ("%s: head already freed", __func__)); 1179 1180 rnh = (struct radix_node_head *)(*head); 1181 1182 rn_walktree(&rnh->rh.rnh_masks->head, rn_freeentry, rnh->rh.rnh_masks); 1183 rn_detachhead_internal(&rnh->rh.rnh_masks->head); 1184 rn_detachhead_internal(&rnh->rh); 1185 1186 *head = NULL; 1187 1188 return (1); 1189 } 1190