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