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