1 /* $OpenBSD: radish.c,v 1.8 2023/04/19 12:58:16 jsg Exp $ */ 2 /* 3 * Copyright (C) 1995, 1996, 1997, and 1998 WIDE Project. 4 * All rights reserved. 5 * 6 * Redistribution and use in source and binary forms, with or without 7 * modification, are permitted provided that the following conditions 8 * are met: 9 * 1. Redistributions of source code must retain the above copyright 10 * notice, this list of conditions and the following disclaimer. 11 * 2. Redistributions in binary form must reproduce the above copyright 12 * notice, this list of conditions and the following disclaimer in the 13 * documentation and/or other materials provided with the distribution. 14 * 3. Neither the name of the project nor the names of its contributors 15 * may be used to endorse or promote products derived from this software 16 * without specific prior written permission. 17 * 18 * THIS SOFTWARE IS PROVIDED BY THE PROJECT AND CONTRIBUTORS ``AS IS'' AND 19 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 20 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 21 * ARE DISCLAIMED. IN NO EVENT SHALL THE PROJECT OR CONTRIBUTORS BE LIABLE 22 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 23 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 24 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 25 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 26 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 27 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 28 * SUCH DAMAGE. 29 * 30 */ 31 32 /* 33 * radish.c 34 * 35 * Version: 0.9 36 * Created: May 27, 1995 37 * Modified: January 28, 1997 38 * Author: Kazu YAMAMOTO 39 * Email: kazu@is.aist-nara.ac.jp 40 */ 41 42 #include <sys/types.h> 43 #include <sys/socket.h> 44 #include <string.h> 45 #include <stdlib.h> 46 #include <errno.h> 47 48 #include "radish.h" 49 50 #include <netinet/in.h> 51 #include <strings.h> 52 #include <stdio.h> 53 54 #define FATAL(x) \ 55 do { \ 56 fputs(x, stderr); \ 57 abort(); \ 58 } while (0/* CONSTCOND */) 59 60 static u_char rd_bmask [] = { 61 0x00, 0x80, 0xc0, 0xe0, 0xf0, 0xf8, 0xfc, 0xfe, 62 }; 63 64 static u_char rd_btest [] = { 65 0x80, 0x40, 0x20, 0x10, 0x08, 0x04, 0x02, 0x01, 66 }; 67 68 u_char rd_deleted_km[1024]; 69 70 /* 71 * return 1 if success 72 * return 0 if error 73 */ 74 int 75 rd_inithead(void **headp, int family, int slen, int off, int alen, 76 int (*match)(void *, void *)) 77 { 78 struct radish_head *head; 79 struct radish *new; 80 struct sockaddr *masks; 81 u_char *m; 82 int num = alen * 8 + 1, i, j, q, r; 83 int len = sizeof(*head) + sizeof(*new) + slen * num; 84 85 if (*headp) return (1); 86 R_Malloc(head, struct radish_head *, len); 87 if (head == NULL) 88 return 0; 89 Bzero(head, len); 90 new = (struct radish *)(head + 1); 91 masks = (struct sockaddr *)(new +1); 92 *headp = head; 93 94 /* 95 * prepare all continuous masks 96 */ 97 m = (u_char *)masks; 98 for (i = 0; i < num; i++, m += slen) { 99 *m = slen; 100 *(m + 1) = family; 101 q = i >> 3; 102 r = i & 7; 103 for(j = 0; j < q; j++) 104 *(m + off + j) = 0xff; 105 *(m + off + j) = rd_bmask[r]; 106 } 107 108 head->rdh_slen = slen; 109 head->rdh_offset = off; 110 head->rdh_alen = alen; 111 head->rdh_masks = masks; 112 head->rdh_match = match; 113 head->rdh_top = new; 114 115 new->rd_route = masks; 116 new->rd_mask = masks; 117 new->rd_btest = rd_btest[0]; 118 /* other nembers are 0 */ 119 120 return(1); 121 } 122 123 struct sockaddr * 124 rd_mask(struct sockaddr *m_arg, struct radish_head *head, int *maskp) 125 { 126 u_char *mp, *masks = (u_char *)head->rdh_masks; 127 int off = head->rdh_offset; 128 int slen = head->rdh_slen; 129 int alen = head->rdh_alen; 130 int i = 0, masklen = 0; 131 132 if (m_arg == NULL) { 133 masklen = alen * 8; 134 *maskp = masklen; 135 return((struct sockaddr *)(masks + slen * masklen)); 136 } 137 mp = (u_char *)m_arg + off; 138 while ((i < alen) && (mp[i] == 0xff)) { 139 masklen += 8; 140 i++; 141 } 142 if (i < alen) 143 switch (mp[i]) { 144 case 0xfe: masklen += 7; break; 145 case 0xfc: masklen += 6; break; 146 case 0xf8: masklen += 5; break; 147 case 0xf0: masklen += 4; break; 148 case 0xe0: masklen += 3; break; 149 case 0xc0: masklen += 2; break; 150 case 0x80: masklen += 1; break; 151 case 0x00: break; 152 } 153 *maskp = masklen; 154 return((struct sockaddr *)(masks + slen * masklen)); 155 } 156 157 int 158 rd_insert(struct sockaddr *d_arg, struct sockaddr *m_arg, 159 struct radish_head *head, void *rt) 160 { 161 struct radish *cur = head->rdh_top, *parent, *new; 162 int off = head->rdh_offset; 163 int slen = head->rdh_slen; 164 int alen = head->rdh_alen; 165 int i, lim, q, r, masklen; 166 u_char *dp, *np, *rp; 167 struct sockaddr *mask; 168 169 mask = rd_mask(m_arg, head, &masklen); 170 q = masklen >> 3; 171 r = masklen & 7; 172 173 /* Allocate a new radish. 174 * This may be overhead in the case that 175 * masklen == cur->rd_masklen 176 * and 177 * route == dest. 178 */ 179 R_Malloc(new, struct radish *, sizeof(*new) + slen); 180 if (new == NULL) 181 return ENOBUFS; 182 Bzero(new, sizeof(*new) + slen); 183 new->rd_route = (struct sockaddr *)(new + 1); 184 new->rd_mask = mask; 185 new->rd_masklen = masklen; 186 new->rd_masklim = q; 187 new->rd_bmask = rd_bmask[r]; 188 new->rd_btest = rd_btest[r]; 189 new->rd_rtent = rt; 190 191 /* masked copy from dest to route */ 192 np = (u_char *)new->rd_route; 193 dp = (u_char *)d_arg; 194 *np = *dp; /* sa_len */ 195 np[1] = dp[1]; /* sa_family */ 196 dp += off; 197 np += off; 198 i = 0; 199 while (i < q) { 200 np[i] = dp[i]; 201 i++; 202 } 203 np[i] = dp[i] & rd_bmask[r]; /* just in case */ 204 205 while (cur) { 206 if (masklen == cur->rd_masklen) { 207 rp = (u_char *)cur->rd_route + off; 208 for (i = 0; i < alen; i++) 209 if (np[i] != rp[i]) { 210 /* 211 * masklen == cur->rd_masklen 212 * dest != route 213 */ 214 return rd_glue(cur, new, i, head); 215 } 216 /* 217 * masklen == cur->rd_masklen 218 * dest == route 219 */ 220 Free(new); 221 if (cur->rd_rtent != NULL) 222 return EEXIST; 223 cur->rd_rtent = rt; 224 return 0; 225 } 226 /* 227 * masklen != cur->rd_masklen 228 */ 229 if (masklen > cur->rd_masklen) { 230 /* 231 * See if dest matches with cur node. 232 * (dest & mask) == route 233 */ 234 rp = (u_char *)cur->rd_route + off; 235 lim = cur->rd_masklim; 236 237 /* mask is continuous, thus mask is 0xff here. */ 238 for (i = 0; i < lim; i++) 239 if(np[i] != rp[i]) { 240 /* 241 * masklen > cur->rd_masklen 242 * (dest & mask) != route 243 */ 244 return rd_glue(cur, new, i, head); 245 } 246 if (cur->rd_bmask) 247 if ((np[lim] & cur->rd_bmask) != rp[lim]) { 248 /* 249 * masklen > cur->rd_masklen 250 * (dest & mask) != route 251 */ 252 return rd_glue(cur, new, lim, head); 253 } 254 /* 255 * masklen > cur->rd_masklen 256 * (dest & mask) == route 257 */ 258 if (cur->rd_btest & np[cur->rd_masklim]) { 259 if (cur->rd_r != NULL) { 260 cur = cur->rd_r; 261 continue; 262 } 263 cur->rd_r = new; 264 new->rd_p = cur; 265 return 0; 266 } else { 267 if (cur->rd_l != NULL) { 268 cur = cur->rd_l; 269 continue; 270 } 271 cur->rd_l = new; 272 new->rd_p = cur; 273 return 0; 274 } 275 } 276 /* 277 * masklen < cur->rd_masklen 278 */ 279 280 /* See if route matches with dest, be careful! 281 * dest == (route & dest_mask) 282 */ 283 rp = (u_char *)cur->rd_route + off; 284 lim = new->rd_masklim; 285 286 /* mask is continuous, thus mask is 0xff here. */ 287 for (i = 0; i < lim; i++) 288 if(np[i] != rp[i]) { 289 /* 290 * masklen < cur->rd_masklen 291 * dest != (route & dest_mask) 292 */ 293 return rd_glue(cur, new, i, head); 294 } 295 if (new->rd_bmask) 296 if (np[lim] != (rp[lim] & new->rd_bmask)) { 297 /* 298 * masklen < cur->rd_masklen 299 * dest != (route & dest_mask) 300 */ 301 return rd_glue(cur, new, lim, head); 302 } 303 /* 304 * masklen < cur->rd_masklen 305 * dest == (route & dest_mask) 306 */ 307 308 /* put the new radish between cur and its parent */ 309 parent = cur->rd_p; 310 new->rd_p = parent; 311 if (parent->rd_l == cur) 312 parent->rd_l = new; 313 else if (parent->rd_r == cur) 314 parent->rd_r = new; 315 else 316 FATAL("rd_insert"); 317 if (new->rd_btest & rp[new->rd_masklim]) 318 new->rd_r = cur; 319 else 320 new->rd_l = cur; 321 322 cur->rd_p = new; 323 return 0; 324 } 325 return 1; 326 } 327 328 /* 329 * Insert a glue radish between the current and its parent. 330 * Let the current radish one child of glue radish. 331 * Let the new radish the other child of glue radish. 332 */ 333 int 334 rd_glue(struct radish *cur, struct radish *new, int misbyte, 335 struct radish_head *head) 336 { 337 struct radish *parent = cur->rd_p, *glue; 338 u_char *cp = (u_char *)cur->rd_route; 339 u_char *np = (u_char *)new->rd_route; 340 u_char *gp; 341 int off = head->rdh_offset, slen = head->rdh_slen; 342 int maskb, xor, i; 343 344 /* 345 * Glue radish 346 */ 347 R_Malloc(glue, struct radish *, sizeof(*glue) + slen); 348 if (glue == NULL) { 349 Free (new); 350 return ENOBUFS; 351 } 352 Bzero(glue, sizeof(*glue) + slen); 353 354 /* calculate a bit to test */ 355 xor = (*(cp + off + misbyte) ^ *(np + off + misbyte)) & 0xff; 356 maskb = 8; 357 while(xor) { 358 xor >>= 1; 359 maskb--; 360 } 361 362 glue->rd_route = (struct sockaddr *)(glue + 1); 363 glue->rd_masklen = 8 * misbyte + maskb; 364 glue->rd_masklim = misbyte; 365 glue->rd_bmask = rd_bmask[maskb]; 366 glue->rd_btest = rd_btest[maskb]; 367 glue->rd_rtent = NULL; 368 glue->rd_p = parent; 369 glue->rd_mask = (struct sockaddr *) 370 ((u_char *)head->rdh_masks + slen * glue->rd_masklen); 371 372 /* masked copy of route */ 373 gp = (u_char *)glue->rd_route; 374 *gp = *cp; /* sa_len */ 375 *(gp + 1) = *(cp + 1); /* sa_family */ 376 cp += off; 377 gp += off; 378 for(i = 0; i < misbyte; i++) 379 gp[i] = cp[i]; 380 gp[misbyte] = cp[misbyte] & glue->rd_bmask; 381 382 if (glue->rd_btest & cp[misbyte]) { 383 glue->rd_r = cur; 384 glue->rd_l = new; 385 } else { 386 glue->rd_r = new; 387 glue->rd_l = cur; 388 } 389 390 /* 391 * Children 392 */ 393 new->rd_p = cur->rd_p = glue; 394 395 /* 396 * Parent 397 */ 398 if (parent->rd_l == cur) 399 parent->rd_l = glue; 400 else if (parent->rd_r == cur) 401 parent->rd_r = glue; 402 else 403 FATAL("rd_insert"); 404 return 0; 405 } 406 407 /* 408 * Find the longest-match radish with the destination. 409 * Return 1 if success, otherwise return 0. 410 */ 411 412 int 413 rd_match(struct sockaddr *d_arg, struct radish_head *head, struct radish **rdp) 414 { 415 return rd_match_next(d_arg, head, rdp, NULL); 416 } 417 418 int 419 rd_match_next(struct sockaddr *d_arg, struct radish_head *head, 420 struct radish **rdp, struct radish *cur) 421 { 422 struct radish *target = NULL; 423 int off = head->rdh_offset, i, lim; 424 u_char *dp = (u_char *)d_arg + off, *cp; 425 426 if (cur == NULL) { 427 cur = head->rdh_top; 428 while (cur) { 429 target = cur; 430 if (cur->rd_btest & *(dp + cur->rd_masklim)) 431 cur = cur->rd_r; 432 else 433 cur = cur->rd_l; 434 } 435 } else { 436 target = cur->rd_p; 437 if (target == NULL) { 438 *rdp = NULL; 439 return 0; 440 } 441 } 442 443 /* We are now on the leaf radish. Backtrace to find the radish 444 which contains route to match. */ 445 do { 446 /* If this radish doesn't have route, 447 we skip it and chase the next parent. */ 448 if (target->rd_rtent != NULL) { 449 cp = (u_char *)target->rd_route + off; 450 lim = target->rd_masklim; 451 452 /* Check the edge for slight speed up */ 453 if (target->rd_bmask) 454 if ((*(dp + lim) & target->rd_bmask) 455 != *(cp + lim)){ 456 nextparent: 457 continue; 458 } 459 460 /* mask is always 0xff */ 461 for (i = 0; i < lim; i++) 462 if(dp[i] != cp[i]) 463 /* to break the for loop */ 464 goto nextparent; 465 /* Matched to this radish! */ 466 *rdp = target; 467 return 1; 468 } 469 } while ((target = target->rd_p)); 470 *rdp = NULL; 471 return 0; 472 } 473 474 /* 475 * Lookup the same radish according to a pair of destination and mask. 476 * Return a pointer to rtentry if exists. Otherwise, return NULL. 477 */ 478 479 void * 480 rd_lookup(struct sockaddr *d_arg, struct sockaddr *m_arg, 481 struct radish_head *head) 482 { 483 struct radish *cur = head->rdh_top; 484 int off = head->rdh_offset, i, lim, olim = 0, masklen; 485 u_char *dp = (u_char *)d_arg + off, *cp; 486 487 rd_mask(m_arg, head, &masklen); 488 489 /* Skipping forward search */ 490 while (cur) { 491 /* Skip a radish if it doesn't have a route */ 492 if (cur->rd_rtent != NULL) { 493 cp = (u_char *)(cur->rd_route) + off; 494 lim = cur->rd_masklim; 495 /* check the edge to speed up a bit */ 496 if (cur->rd_bmask) 497 if ((*(dp + lim) & cur->rd_bmask) 498 != *(cp + lim)) 499 return NULL; 500 /* mask is always 0xff */ 501 for (i = olim; i < lim; i++) 502 if(dp[i] != cp[i]) 503 return NULL; 504 if (masklen == cur->rd_masklen) 505 return cur->rd_rtent; 506 olim = lim; 507 } 508 if (cur->rd_btest & *(dp + cur->rd_masklim)) 509 cur = cur->rd_r; 510 else 511 cur = cur->rd_l; 512 } 513 return NULL; 514 } 515 516 /* 517 * Delete the radish for dest and mask. 518 * Return 0 if success. 519 * Return ENOENT if no such radish exists. 520 * Return EFAULT if try to delete intermediate radish which doesn't have route. 521 */ 522 523 int 524 rd_delete(struct sockaddr *d_arg, struct sockaddr *m_arg, 525 struct radish_head *head, void **item) 526 { 527 struct radish *cur = head->rdh_top; 528 int off = head->rdh_offset, i, lim, masklen; 529 u_char *dp = (u_char *)d_arg + off, *cp; 530 531 rd_mask(m_arg, head, &masklen); 532 *item = NULL; /* just in case */ 533 534 while (cur) { 535 /* exit loop if dest does not match with the current node 536 * (dest & mask) != route 537 */ 538 cp = (u_char *)cur->rd_route + off; 539 /* check the edge to speed up */ 540 if (cur->rd_bmask) 541 if ((*(dp + cur->rd_masklim) & cur->rd_bmask) 542 != *(cp + cur->rd_masklim)) 543 return ENOENT; 544 /* mask is always 0xff */ 545 lim = cur->rd_masklim; 546 for (i = 0; i < lim; i++) 547 if(dp[i] != cp[i]) 548 return ENOENT; 549 550 /* See if cur is exactly what we delete */ 551 552 /* Check mask to speed up */ 553 if (cur->rd_masklen != masklen) 554 goto next; 555 556 cp = (u_char *)cur->rd_route + off; 557 lim = head->rdh_alen; 558 for (i = 0; i < lim; i++) 559 if (dp[i] != cp[i]) 560 goto next; 561 /* 562 * Both route and mask are the same. 563 */ 564 if (cur->rd_rtent == NULL) { 565 /* Leaf always has route, so this radish 566 * must be intermediate. 567 * Can't delete intermediate radish which 568 * doesn't have route. 569 */ 570 return EFAULT; 571 } 572 *item = cur->rd_rtent; 573 { 574 /* used to report the deleted entry back */ 575 u_char rl = cur->rd_route->sa_len; 576 u_char ml = cur->rd_mask->sa_len; 577 578 bcopy(cur->rd_route, rd_deleted_km, rl); 579 bcopy(cur->rd_mask, rd_deleted_km + rl, ml); 580 } 581 if (cur->rd_l && cur->rd_r) { 582 /* This radish has two children */ 583 cur->rd_rtent = NULL; 584 return 0; 585 } 586 /* Unlink the radish that has 0 or 1 child 587 * and surely has a route. 588 */ 589 rd_unlink(cur, head->rdh_top); 590 return 0; 591 592 next: 593 /* search corresponding subtree */ 594 if (cur->rd_btest & *(dp + cur->rd_masklim)) { 595 if (cur->rd_r) { 596 cur = cur->rd_r; 597 continue; 598 } else 599 break; 600 } else { 601 if (cur->rd_l) { 602 cur = cur->rd_l; 603 continue; 604 } else 605 break; 606 } 607 } 608 return ENOENT; 609 } 610 611 /* 612 * Free radish and refine radish tree. 613 * rd_unlink is called with radish which have 0 or 1 child and route. 614 * Error causes panic, so return only when success. 615 */ 616 617 void 618 rd_unlink(struct radish *cur, struct radish *top) 619 { 620 struct radish *parent, *child; 621 622 if (cur == top) { 623 cur->rd_rtent = NULL; 624 return; 625 } 626 627 if ((cur->rd_l == 0) && (cur->rd_r == 0)) { 628 /* No child, just delete it. */ 629 parent = cur->rd_p; 630 if (parent->rd_l == cur) { 631 parent->rd_l = NULL; 632 Free(cur); 633 } else if (parent->rd_r == cur) { 634 parent->rd_r = NULL; 635 Free(cur); 636 } else 637 FATAL("rd_unlink"); 638 if (parent->rd_rtent == NULL && parent != top) 639 /* Parent is not necessary, refine radish. */ 640 rd_unlink(parent, top); 641 } else { 642 /* 643 * There is one child, never two. 644 * Make its child its parent's child. 645 */ 646 if (cur->rd_l) 647 child = cur->rd_l; 648 else 649 child = cur->rd_r; 650 parent = cur->rd_p; 651 child->rd_p = parent; 652 if (parent->rd_l == cur) { 653 parent->rd_l = child; 654 Free(cur); 655 } else if (parent->rd_r == cur) { 656 parent->rd_r = child; 657 Free(cur); 658 } else 659 FATAL("rd_unlink"); 660 } 661 } 662 663 int 664 rd_walktree(struct radish_head *h, register int (*f)(struct radish *, void *), 665 void *w) 666 { 667 int error = 0; 668 struct radish *par = NULL, *cur, *top = h->rdh_top; 669 670 cur = top; 671 for (;;) { 672 while (cur) { 673 if (cur->rd_rtent != NULL) 674 if ((error = (*f)(cur, w))) 675 return error; 676 par = cur; 677 cur = cur->rd_l; 678 } 679 cur = par; 680 while (cur->rd_r == NULL || par == cur->rd_r) { 681 par = cur; 682 cur = cur->rd_p; 683 if (cur == NULL) return 0; 684 } 685 par = cur; 686 cur = cur->rd_r; 687 } 688 } 689 690 /* This function can be mush easier in the context of radish. 691 * For instance, using rd_mask. But we stay the original because 692 * it works. 693 */ 694 int 695 rd_refines(void *m_arg, void *n_arg) 696 { 697 register caddr_t m = m_arg, n = n_arg; 698 register caddr_t lim, lim2 = lim = n + *(u_char *)n; 699 int longer = (*(u_char *)n++) - (int)(*(u_char *)m++); 700 int masks_are_equal = 1; 701 702 if (longer > 0) 703 lim -= longer; 704 while (n < lim) { 705 if (*n & ~(*m)) 706 return 0; 707 if (*n++ != *m++) 708 masks_are_equal = 0; 709 710 } 711 while (n < lim2) 712 if (*n++) 713 return 0; 714 if (masks_are_equal && (longer < 0)) 715 for (lim2 = m - longer; m < lim2; ) 716 if (*m++) 717 return 1; 718 return (!masks_are_equal); 719 } 720