1 /* $OpenBSD: rtable.c,v 1.63 2017/09/05 11:15:39 mpi Exp $ */ 2 3 /* 4 * Copyright (c) 2014-2016 Martin Pieuchot 5 * 6 * Permission to use, copy, modify, and distribute this software for any 7 * purpose with or without fee is hereby granted, provided that the above 8 * copyright notice and this permission notice appear in all copies. 9 * 10 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES 11 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF 12 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR 13 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES 14 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN 15 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF 16 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. 17 */ 18 19 #ifndef _KERNEL 20 #include "kern_compat.h" 21 #else 22 #include <sys/param.h> 23 #include <sys/systm.h> 24 #include <sys/socket.h> 25 #include <sys/malloc.h> 26 #include <sys/queue.h> 27 #include <sys/domain.h> 28 #include <sys/srp.h> 29 #endif 30 31 #include <net/rtable.h> 32 #include <net/route.h> 33 34 /* 35 * Structures used by rtable_get() to retrieve the corresponding 36 * routing table for a given pair of ``af'' and ``rtableid''. 37 * 38 * Note that once allocated routing table heads are never freed. 39 * This way we do not need to reference count them. 40 * 41 * afmap rtmap/dommp 42 * ----------- --------- ----- 43 * | 0 |--------> | 0 | 0 | ... | 0 | Array mapping rtableid (=index) 44 * ----------- --------- ----- to rdomain/loopback (=value). 45 * | AF_INET |. 46 * ----------- `. .---------. .---------. 47 * ... `----> | rtable0 | ... | rtableN | Array of pointers for 48 * ----------- '---------' '---------' IPv4 routing tables 49 * | AF_MPLS | indexed by ``rtableid''. 50 * ----------- 51 */ 52 struct srp *afmap; 53 uint8_t af2idx[AF_MAX+1]; /* To only allocate supported AF */ 54 uint8_t af2idx_max; 55 56 /* Array of routing table pointers. */ 57 struct rtmap { 58 unsigned int limit; 59 void **tbl; 60 }; 61 62 /* 63 * Array of rtableid -> rdomain mapping. 64 * 65 * Only used for the first index as describbed above. 66 */ 67 struct dommp { 68 unsigned int limit; 69 /* 70 * Array to get the routing domain and loopback interface related to 71 * a routing table. Format: 72 * 73 * 8 unused bits | 16 bits for loopback index | 8 bits for rdomain 74 */ 75 unsigned int *value; 76 }; 77 78 unsigned int rtmap_limit = 0; 79 80 void rtmap_init(void); 81 void rtmap_grow(unsigned int, sa_family_t); 82 void rtmap_dtor(void *, void *); 83 84 struct srp_gc rtmap_gc = SRP_GC_INITIALIZER(rtmap_dtor, NULL); 85 86 void rtable_init_backend(unsigned int); 87 void *rtable_alloc(unsigned int, unsigned int, unsigned int); 88 void *rtable_get(unsigned int, sa_family_t); 89 90 void 91 rtmap_init(void) 92 { 93 struct domain *dp; 94 int i; 95 96 /* Start with a single table for every domain that requires it. */ 97 for (i = 0; (dp = domains[i]) != NULL; i++) { 98 if (dp->dom_rtoffset == 0) 99 continue; 100 101 rtmap_grow(1, dp->dom_family); 102 } 103 104 /* Initialize the rtableid->rdomain mapping table. */ 105 rtmap_grow(1, 0); 106 107 rtmap_limit = 1; 108 } 109 110 /* 111 * Grow the size of the array of routing table for AF ``af'' to ``nlimit''. 112 */ 113 void 114 rtmap_grow(unsigned int nlimit, sa_family_t af) 115 { 116 struct rtmap *map, *nmap; 117 int i; 118 119 KERNEL_ASSERT_LOCKED(); 120 121 KASSERT(nlimit > rtmap_limit); 122 123 nmap = malloc(sizeof(*nmap), M_RTABLE, M_WAITOK); 124 nmap->limit = nlimit; 125 nmap->tbl = mallocarray(nlimit, sizeof(*nmap[0].tbl), M_RTABLE, 126 M_WAITOK|M_ZERO); 127 128 map = srp_get_locked(&afmap[af2idx[af]]); 129 if (map != NULL) { 130 KASSERT(map->limit == rtmap_limit); 131 132 for (i = 0; i < map->limit; i++) 133 nmap->tbl[i] = map->tbl[i]; 134 } 135 136 srp_update_locked(&rtmap_gc, &afmap[af2idx[af]], nmap); 137 } 138 139 void 140 rtmap_dtor(void *null, void *xmap) 141 { 142 struct rtmap *map = xmap; 143 144 /* 145 * doesnt need to be serialized since this is the last reference 146 * to this map. there's nothing to race against. 147 */ 148 free(map->tbl, M_RTABLE, map->limit * sizeof(*map[0].tbl)); 149 free(map, M_RTABLE, sizeof(*map)); 150 } 151 152 void 153 rtable_init(void) 154 { 155 struct domain *dp; 156 unsigned int keylen = 0; 157 int i; 158 159 KASSERT(sizeof(struct rtmap) == sizeof(struct dommp)); 160 161 /* We use index 0 for the rtable/rdomain map. */ 162 af2idx_max = 1; 163 memset(af2idx, 0, sizeof(af2idx)); 164 165 /* 166 * Compute the maximum supported key length in case the routing 167 * table backend needs it. 168 */ 169 for (i = 0; (dp = domains[i]) != NULL; i++) { 170 if (dp->dom_rtoffset == 0) 171 continue; 172 173 af2idx[dp->dom_family] = af2idx_max++; 174 if (dp->dom_rtkeylen > keylen) 175 keylen = dp->dom_rtkeylen; 176 177 } 178 rtable_init_backend(keylen); 179 180 /* 181 * Allocate AF-to-id table now that we now how many AFs this 182 * kernel supports. 183 */ 184 afmap = mallocarray(af2idx_max + 1, sizeof(*afmap), M_RTABLE, 185 M_WAITOK|M_ZERO); 186 187 rtmap_init(); 188 189 if (rtable_add(0) != 0) 190 panic("unable to create default routing table"); 191 } 192 193 int 194 rtable_add(unsigned int id) 195 { 196 struct domain *dp; 197 void *tbl; 198 struct rtmap *map; 199 struct dommp *dmm; 200 sa_family_t af; 201 unsigned int off, alen; 202 int i; 203 204 KERNEL_ASSERT_LOCKED(); 205 206 if (id > RT_TABLEID_MAX) 207 return (EINVAL); 208 209 if (rtable_exists(id)) 210 return (EEXIST); 211 212 for (i = 0; (dp = domains[i]) != NULL; i++) { 213 if (dp->dom_rtoffset == 0) 214 continue; 215 216 af = dp->dom_family; 217 off = dp->dom_rtoffset; 218 alen = dp->dom_maxplen; 219 220 if (id >= rtmap_limit) 221 rtmap_grow(id + 1, af); 222 223 tbl = rtable_alloc(id, alen, off); 224 if (tbl == NULL) 225 return (ENOMEM); 226 227 map = srp_get_locked(&afmap[af2idx[af]]); 228 map->tbl[id] = tbl; 229 } 230 231 /* Reflect possible growth. */ 232 if (id >= rtmap_limit) { 233 rtmap_grow(id + 1, 0); 234 rtmap_limit = id + 1; 235 } 236 237 /* Use main rtable/rdomain by default. */ 238 dmm = srp_get_locked(&afmap[0]); 239 dmm->value[id] = 0; 240 241 return (0); 242 } 243 244 void * 245 rtable_get(unsigned int rtableid, sa_family_t af) 246 { 247 struct rtmap *map; 248 void *tbl = NULL; 249 struct srp_ref sr; 250 251 if (af >= nitems(af2idx) || af2idx[af] == 0) 252 return (NULL); 253 254 map = srp_enter(&sr, &afmap[af2idx[af]]); 255 if (rtableid < map->limit) 256 tbl = map->tbl[rtableid]; 257 srp_leave(&sr); 258 259 return (tbl); 260 } 261 262 int 263 rtable_exists(unsigned int rtableid) 264 { 265 struct domain *dp; 266 void *tbl; 267 int i; 268 269 for (i = 0; (dp = domains[i]) != NULL; i++) { 270 if (dp->dom_rtoffset == 0) 271 continue; 272 273 tbl = rtable_get(rtableid, dp->dom_family); 274 if (tbl != NULL) 275 return (1); 276 } 277 278 return (0); 279 } 280 281 unsigned int 282 rtable_l2(unsigned int rtableid) 283 { 284 struct dommp *dmm; 285 unsigned int rdomain = 0; 286 struct srp_ref sr; 287 288 dmm = srp_enter(&sr, &afmap[0]); 289 if (rtableid < dmm->limit) 290 rdomain = (dmm->value[rtableid] & RT_TABLEID_MASK); 291 srp_leave(&sr); 292 293 return (rdomain); 294 } 295 296 unsigned int 297 rtable_loindex(unsigned int rtableid) 298 { 299 struct dommp *dmm; 300 unsigned int loifidx = 0; 301 struct srp_ref sr; 302 303 dmm = srp_enter(&sr, &afmap[0]); 304 if (rtableid < dmm->limit) 305 loifidx = (dmm->value[rtableid] >> RT_TABLEID_BITS); 306 srp_leave(&sr); 307 308 return (loifidx); 309 } 310 311 void 312 rtable_l2set(unsigned int rtableid, unsigned int rdomain, unsigned int loifidx) 313 { 314 struct dommp *dmm; 315 unsigned int value; 316 317 KERNEL_ASSERT_LOCKED(); 318 319 if (!rtable_exists(rtableid) || !rtable_exists(rdomain)) 320 return; 321 322 value = (rdomain & RT_TABLEID_MASK) | (loifidx << RT_TABLEID_BITS); 323 324 dmm = srp_get_locked(&afmap[0]); 325 dmm->value[rtableid] = value; 326 } 327 328 329 static inline uint8_t *satoaddr(struct art_root *, struct sockaddr *); 330 331 int an_match(struct art_node *, struct sockaddr *, int); 332 void rtentry_ref(void *, void *); 333 void rtentry_unref(void *, void *); 334 335 void rtable_mpath_insert(struct art_node *, struct rtentry *); 336 337 struct srpl_rc rt_rc = SRPL_RC_INITIALIZER(rtentry_ref, rtentry_unref, NULL); 338 339 void 340 rtable_init_backend(unsigned int keylen) 341 { 342 art_init(); 343 } 344 345 void * 346 rtable_alloc(unsigned int rtableid, unsigned int alen, unsigned int off) 347 { 348 return (art_alloc(rtableid, alen, off)); 349 } 350 351 struct rtentry * 352 rtable_lookup(unsigned int rtableid, struct sockaddr *dst, 353 struct sockaddr *mask, struct sockaddr *gateway, uint8_t prio) 354 { 355 struct art_root *ar; 356 struct art_node *an; 357 struct rtentry *rt = NULL; 358 struct srp_ref sr, nsr; 359 uint8_t *addr; 360 int plen; 361 362 ar = rtable_get(rtableid, dst->sa_family); 363 if (ar == NULL) 364 return (NULL); 365 366 addr = satoaddr(ar, dst); 367 368 /* No need for a perfect match. */ 369 if (mask == NULL) { 370 an = art_match(ar, addr, &nsr); 371 if (an == NULL) 372 goto out; 373 } else { 374 plen = rtable_satoplen(dst->sa_family, mask); 375 if (plen == -1) 376 return (NULL); 377 378 an = art_lookup(ar, addr, plen, &nsr); 379 380 /* Make sure we've got a perfect match. */ 381 if (!an_match(an, dst, plen)) 382 goto out; 383 } 384 385 SRPL_FOREACH(rt, &sr, &an->an_rtlist, rt_next) { 386 if (prio != RTP_ANY && 387 (rt->rt_priority & RTP_MASK) != (prio & RTP_MASK)) 388 continue; 389 390 if (gateway == NULL) 391 break; 392 393 if (rt->rt_gateway->sa_len == gateway->sa_len && 394 memcmp(rt->rt_gateway, gateway, gateway->sa_len) == 0) 395 break; 396 } 397 if (rt != NULL) 398 rtref(rt); 399 400 SRPL_LEAVE(&sr); 401 out: 402 srp_leave(&nsr); 403 404 return (rt); 405 } 406 407 struct rtentry * 408 rtable_match(unsigned int rtableid, struct sockaddr *dst, uint32_t *src) 409 { 410 struct art_root *ar; 411 struct art_node *an; 412 struct rtentry *rt = NULL; 413 struct srp_ref sr, nsr; 414 uint8_t *addr; 415 int hash; 416 417 ar = rtable_get(rtableid, dst->sa_family); 418 if (ar == NULL) 419 return (NULL); 420 421 addr = satoaddr(ar, dst); 422 423 an = art_match(ar, addr, &nsr); 424 if (an == NULL) 425 goto out; 426 427 rt = SRPL_FIRST(&sr, &an->an_rtlist); 428 rtref(rt); 429 SRPL_LEAVE(&sr); 430 431 /* Gateway selection by Hash-Threshold (RFC 2992) */ 432 if ((hash = rt_hash(rt, dst, src)) != -1) { 433 struct rtentry *mrt; 434 int threshold, npaths = 0; 435 436 KASSERT(hash <= 0xffff); 437 438 SRPL_FOREACH(mrt, &sr, &an->an_rtlist, rt_next) { 439 /* Only count nexthops with the same priority. */ 440 if (mrt->rt_priority == rt->rt_priority) 441 npaths++; 442 } 443 SRPL_LEAVE(&sr); 444 445 threshold = (0xffff / npaths) + 1; 446 447 /* 448 * we have no protection against concurrent modification of the 449 * route list attached to the node, so we won't necessarily 450 * have the same number of routes. for most modifications, 451 * we'll pick a route that we wouldn't have if we only saw the 452 * list before or after the change. if we were going to use 453 * the last available route, but it got removed, we'll hit 454 * the end of the list and then pick the first route. 455 */ 456 457 mrt = SRPL_FIRST(&sr, &an->an_rtlist); 458 while (hash > threshold && mrt != NULL) { 459 if (mrt->rt_priority == rt->rt_priority) 460 hash -= threshold; 461 mrt = SRPL_FOLLOW(&sr, mrt, rt_next); 462 } 463 464 if (mrt != NULL) { 465 rtref(mrt); 466 rtfree(rt); 467 rt = mrt; 468 } 469 SRPL_LEAVE(&sr); 470 } 471 out: 472 srp_leave(&nsr); 473 return (rt); 474 } 475 476 int 477 rtable_insert(unsigned int rtableid, struct sockaddr *dst, 478 struct sockaddr *mask, struct sockaddr *gateway, uint8_t prio, 479 struct rtentry *rt) 480 { 481 struct rtentry *mrt; 482 struct srp_ref sr; 483 struct art_root *ar; 484 struct art_node *an, *prev; 485 uint8_t *addr; 486 int plen; 487 unsigned int rt_flags; 488 int error = 0; 489 490 ar = rtable_get(rtableid, dst->sa_family); 491 if (ar == NULL) 492 return (EAFNOSUPPORT); 493 494 addr = satoaddr(ar, dst); 495 plen = rtable_satoplen(dst->sa_family, mask); 496 if (plen == -1) 497 return (EINVAL); 498 499 rtref(rt); /* guarantee rtfree won't do anything during insert */ 500 rw_enter_write(&ar->ar_lock); 501 502 /* Do not permit exactly the same dst/mask/gw pair. */ 503 an = art_lookup(ar, addr, plen, &sr); 504 srp_leave(&sr); /* an can't go away while we have the lock */ 505 if (an_match(an, dst, plen)) { 506 struct rtentry *mrt; 507 int mpathok = ISSET(rt->rt_flags, RTF_MPATH); 508 509 SRPL_FOREACH_LOCKED(mrt, &an->an_rtlist, rt_next) { 510 if (prio != RTP_ANY && 511 (mrt->rt_priority & RTP_MASK) != (prio & RTP_MASK)) 512 continue; 513 514 if (!mpathok || 515 (mrt->rt_gateway->sa_len == gateway->sa_len && 516 !memcmp(mrt->rt_gateway, gateway, gateway->sa_len))){ 517 error = EEXIST; 518 goto leave; 519 } 520 } 521 } 522 523 an = art_get(dst, plen); 524 if (an == NULL) { 525 error = ENOBUFS; 526 goto leave; 527 } 528 529 /* prepare for immediate operation if insert succeeds */ 530 rt_flags = rt->rt_flags; 531 rt->rt_flags &= ~RTF_MPATH; 532 rt->rt_dest = dst; 533 rt->rt_plen = plen; 534 SRPL_INSERT_HEAD_LOCKED(&rt_rc, &an->an_rtlist, rt, rt_next); 535 536 prev = art_insert(ar, an, addr, plen); 537 if (prev != an) { 538 SRPL_REMOVE_LOCKED(&rt_rc, &an->an_rtlist, rt, rtentry, 539 rt_next); 540 rt->rt_flags = rt_flags; 541 art_put(an); 542 543 if (prev == NULL) { 544 error = ESRCH; 545 goto leave; 546 } 547 548 an = prev; 549 550 mrt = SRPL_FIRST_LOCKED(&an->an_rtlist); 551 KASSERT(mrt != NULL); 552 KASSERT((rt->rt_flags & RTF_MPATH) || mrt->rt_priority != prio); 553 554 /* 555 * An ART node with the same destination/netmask already 556 * exists, MPATH conflict must have been already checked. 557 */ 558 if (rt->rt_flags & RTF_MPATH) { 559 /* 560 * Only keep the RTF_MPATH flag if two routes have 561 * the same gateway. 562 */ 563 rt->rt_flags &= ~RTF_MPATH; 564 SRPL_FOREACH_LOCKED(mrt, &an->an_rtlist, rt_next) { 565 if (mrt->rt_priority == prio) { 566 mrt->rt_flags |= RTF_MPATH; 567 rt->rt_flags |= RTF_MPATH; 568 } 569 } 570 } 571 572 /* Put newly inserted entry at the right place. */ 573 rtable_mpath_insert(an, rt); 574 } 575 leave: 576 rw_exit_write(&ar->ar_lock); 577 rtfree(rt); 578 return (error); 579 } 580 581 int 582 rtable_delete(unsigned int rtableid, struct sockaddr *dst, 583 struct sockaddr *mask, struct rtentry *rt) 584 { 585 struct art_root *ar; 586 struct art_node *an; 587 struct srp_ref sr; 588 uint8_t *addr; 589 int plen; 590 struct rtentry *mrt; 591 int npaths = 0; 592 int error = 0; 593 594 ar = rtable_get(rtableid, dst->sa_family); 595 if (ar == NULL) 596 return (EAFNOSUPPORT); 597 598 addr = satoaddr(ar, dst); 599 plen = rtable_satoplen(dst->sa_family, mask); 600 601 rtref(rt); /* guarantee rtfree won't do anything under ar_lock */ 602 rw_enter_write(&ar->ar_lock); 603 an = art_lookup(ar, addr, plen, &sr); 604 srp_leave(&sr); /* an can't go away while we have the lock */ 605 606 /* Make sure we've got a perfect match. */ 607 if (!an_match(an, dst, plen)) { 608 error = ESRCH; 609 goto leave; 610 } 611 612 /* 613 * If other multipath route entries are still attached to 614 * this ART node we only have to unlink it. 615 */ 616 SRPL_FOREACH_LOCKED(mrt, &an->an_rtlist, rt_next) 617 npaths++; 618 619 if (npaths > 1) { 620 KASSERT(rt->rt_refcnt >= 1); 621 SRPL_REMOVE_LOCKED(&rt_rc, &an->an_rtlist, rt, rtentry, 622 rt_next); 623 624 mrt = SRPL_FIRST_LOCKED(&an->an_rtlist); 625 if (npaths == 2) 626 mrt->rt_flags &= ~RTF_MPATH; 627 628 goto leave; 629 } 630 631 if (art_delete(ar, an, addr, plen) == NULL) 632 panic("art_delete failed to find node %p", an); 633 634 KASSERT(rt->rt_refcnt >= 1); 635 SRPL_REMOVE_LOCKED(&rt_rc, &an->an_rtlist, rt, rtentry, rt_next); 636 art_put(an); 637 638 leave: 639 rw_exit_write(&ar->ar_lock); 640 rtfree(rt); 641 642 return (error); 643 } 644 645 struct rtable_walk_cookie { 646 int (*rwc_func)(struct rtentry *, void *, unsigned int); 647 void *rwc_arg; 648 unsigned int rwc_rid; 649 }; 650 651 /* 652 * Helper for rtable_walk to keep the ART code free from any "struct rtentry". 653 */ 654 int 655 rtable_walk_helper(struct art_node *an, void *xrwc) 656 { 657 struct srp_ref sr; 658 struct rtable_walk_cookie *rwc = xrwc; 659 struct rtentry *rt; 660 int error = 0; 661 662 SRPL_FOREACH(rt, &sr, &an->an_rtlist, rt_next) { 663 if ((error = (*rwc->rwc_func)(rt, rwc->rwc_arg, rwc->rwc_rid))) 664 break; 665 } 666 SRPL_LEAVE(&sr); 667 668 return (error); 669 } 670 671 int 672 rtable_walk(unsigned int rtableid, sa_family_t af, 673 int (*func)(struct rtentry *, void *, unsigned int), void *arg) 674 { 675 struct art_root *ar; 676 struct rtable_walk_cookie rwc; 677 int error; 678 679 ar = rtable_get(rtableid, af); 680 if (ar == NULL) 681 return (EAFNOSUPPORT); 682 683 rwc.rwc_func = func; 684 rwc.rwc_arg = arg; 685 rwc.rwc_rid = rtableid; 686 687 while ((error = art_walk(ar, rtable_walk_helper, &rwc)) == EAGAIN) 688 continue; 689 690 return (error); 691 } 692 693 struct rtentry * 694 rtable_iterate(struct rtentry *rt0) 695 { 696 struct rtentry *rt = NULL; 697 struct srp_ref sr; 698 699 rt = SRPL_NEXT(&sr, rt0, rt_next); 700 if (rt != NULL) 701 rtref(rt); 702 SRPL_LEAVE(&sr); 703 rtfree(rt0); 704 return (rt); 705 } 706 707 int 708 rtable_mpath_capable(unsigned int rtableid, sa_family_t af) 709 { 710 return (1); 711 } 712 713 int 714 rtable_mpath_reprio(unsigned int rtableid, struct sockaddr *dst, 715 struct sockaddr *mask, uint8_t prio, struct rtentry *rt) 716 { 717 struct art_root *ar; 718 struct art_node *an; 719 struct srp_ref sr; 720 uint8_t *addr; 721 int plen; 722 int error = 0; 723 724 ar = rtable_get(rtableid, dst->sa_family); 725 if (ar == NULL) 726 return (EAFNOSUPPORT); 727 728 addr = satoaddr(ar, dst); 729 plen = rtable_satoplen(dst->sa_family, mask); 730 731 rw_enter_write(&ar->ar_lock); 732 an = art_lookup(ar, addr, plen, &sr); 733 srp_leave(&sr); /* an can't go away while we have the lock */ 734 735 /* Make sure we've got a perfect match. */ 736 if (!an_match(an, dst, plen)) { 737 error = ESRCH; 738 } else if (SRPL_FIRST_LOCKED(&an->an_rtlist) == rt && 739 SRPL_NEXT_LOCKED(rt, rt_next) == NULL) { 740 /* 741 * If there's only one entry on the list do not go 742 * through an insert/remove cycle. This is done to 743 * guarantee that ``an->an_rtlist'' is never empty 744 * when a node is in the tree. 745 */ 746 rt->rt_priority = prio; 747 } else { 748 rtref(rt); /* keep rt alive in between remove and insert */ 749 SRPL_REMOVE_LOCKED(&rt_rc, &an->an_rtlist, 750 rt, rtentry, rt_next); 751 rt->rt_priority = prio; 752 rtable_mpath_insert(an, rt); 753 rtfree(rt); 754 error = EAGAIN; 755 } 756 rw_exit_write(&ar->ar_lock); 757 758 return (error); 759 } 760 761 void 762 rtable_mpath_insert(struct art_node *an, struct rtentry *rt) 763 { 764 struct rtentry *mrt, *prt = NULL; 765 uint8_t prio = rt->rt_priority; 766 767 if ((mrt = SRPL_FIRST_LOCKED(&an->an_rtlist)) == NULL) { 768 SRPL_INSERT_HEAD_LOCKED(&rt_rc, &an->an_rtlist, rt, rt_next); 769 return; 770 } 771 772 /* Iterate until we find the route to be placed after ``rt''. */ 773 while (mrt->rt_priority <= prio && SRPL_NEXT_LOCKED(mrt, rt_next)) { 774 prt = mrt; 775 mrt = SRPL_NEXT_LOCKED(mrt, rt_next); 776 } 777 778 if (mrt->rt_priority <= prio) { 779 SRPL_INSERT_AFTER_LOCKED(&rt_rc, mrt, rt, rt_next); 780 } else if (prt != NULL) { 781 SRPL_INSERT_AFTER_LOCKED(&rt_rc, prt, rt, rt_next); 782 } else { 783 SRPL_INSERT_HEAD_LOCKED(&rt_rc, &an->an_rtlist, rt, rt_next); 784 } 785 } 786 787 /* 788 * Returns 1 if ``an'' perfectly matches (``dst'', ``plen''), 0 otherwise. 789 */ 790 int 791 an_match(struct art_node *an, struct sockaddr *dst, int plen) 792 { 793 struct rtentry *rt; 794 struct srp_ref sr; 795 int match; 796 797 if (an == NULL || an->an_plen != plen) 798 return (0); 799 800 rt = SRPL_FIRST(&sr, &an->an_rtlist); 801 match = (memcmp(rt->rt_dest, dst, dst->sa_len) == 0); 802 SRPL_LEAVE(&sr); 803 804 return (match); 805 } 806 807 void 808 rtentry_ref(void *null, void *xrt) 809 { 810 struct rtentry *rt = xrt; 811 812 rtref(rt); 813 } 814 815 void 816 rtentry_unref(void *null, void *xrt) 817 { 818 struct rtentry *rt = xrt; 819 820 rtfree(rt); 821 } 822 823 /* 824 * Return a pointer to the address (key). This is an heritage from the 825 * BSD radix tree needed to skip the non-address fields from the flavor 826 * of "struct sockaddr" used by this routing table. 827 */ 828 static inline uint8_t * 829 satoaddr(struct art_root *at, struct sockaddr *sa) 830 { 831 return (((uint8_t *)sa) + at->ar_off); 832 } 833 834 /* 835 * Return the prefix length of a mask. 836 */ 837 int 838 rtable_satoplen(sa_family_t af, struct sockaddr *mask) 839 { 840 struct domain *dp; 841 uint8_t *ap, *ep; 842 int mlen, plen = 0; 843 int i; 844 845 for (i = 0; (dp = domains[i]) != NULL; i++) { 846 if (dp->dom_rtoffset == 0) 847 continue; 848 849 if (af == dp->dom_family) 850 break; 851 } 852 if (dp == NULL) 853 return (-1); 854 855 /* Host route */ 856 if (mask == NULL) 857 return (dp->dom_maxplen); 858 859 mlen = mask->sa_len; 860 861 /* Default route */ 862 if (mlen == 0) 863 return (0); 864 865 ap = (uint8_t *)((uint8_t *)mask) + dp->dom_rtoffset; 866 ep = (uint8_t *)((uint8_t *)mask) + mlen; 867 if (ap > ep) 868 return (-1); 869 870 if (ap == ep) 871 return (0); 872 873 /* "Beauty" adapted from sbin/route/show.c ... */ 874 while (ap < ep) { 875 switch (*ap) { 876 case 0xff: 877 plen += 8; 878 ap++; 879 break; 880 case 0xfe: 881 plen += 7; 882 ap++; 883 goto out; 884 case 0xfc: 885 plen += 6; 886 ap++; 887 goto out; 888 case 0xf8: 889 plen += 5; 890 ap++; 891 goto out; 892 case 0xf0: 893 plen += 4; 894 ap++; 895 goto out; 896 case 0xe0: 897 plen += 3; 898 ap++; 899 goto out; 900 case 0xc0: 901 plen += 2; 902 ap++; 903 goto out; 904 case 0x80: 905 plen += 1; 906 ap++; 907 goto out; 908 case 0x00: 909 goto out; 910 default: 911 /* Non contiguous mask. */ 912 return (-1); 913 } 914 915 } 916 917 out: 918 #ifdef DIAGNOSTIC 919 for (; ap < ep; ap++) { 920 if (*ap != 0x00) 921 return (-1); 922 } 923 #endif /* DIAGNOSTIC */ 924 925 return (plen); 926 } 927