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