1 /*- 2 * SPDX-License-Identifier: BSD-2-Clause 3 * 4 * Copyright (c) 2020 Alexander V. Chernikov 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 * 15 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND 16 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 17 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 18 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 19 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 20 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 21 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 22 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 23 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 24 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 25 * SUCH DAMAGE. 26 */ 27 28 #include <sys/cdefs.h> 29 __FBSDID("$FreeBSD$"); 30 #include "opt_inet.h" 31 32 #include <sys/param.h> 33 #include <sys/kernel.h> 34 #include <sys/lock.h> 35 #include <sys/rmlock.h> 36 #include <sys/malloc.h> 37 #include <sys/kernel.h> 38 #include <sys/priv.h> 39 #include <sys/socket.h> 40 #include <sys/sysctl.h> 41 #include <net/vnet.h> 42 43 #include <net/if.h> 44 #include <netinet/in.h> 45 46 #include <net/route.h> 47 #include <net/route/nhop.h> 48 #include <net/route/route_ctl.h> 49 #include <net/route/route_var.h> 50 #include <net/route/fib_algo.h> 51 52 /* 53 * Binary search lookup algo. 54 * 55 * Compiles route table into a sorted array. 56 * Used with small amount of routes (< 16). 57 * As array is immutable, it is rebuild on each rtable change. 58 * 59 * Example: 60 * 61 * 0.0.0.0/0 -> nh1 62 * 10.0.0.0/24 -> nh2 63 * 10.0.0.1/32 -> nh3 64 * 65 * gets compiled to: 66 * 67 * 0.0.0.0 -> nh1 68 * 10.0.0.0 -> nh2 69 * 10.0.0.1 -> nh3 70 * 10.0.0.2 -> nh2 71 * 10.0.1.0 -> nh1 72 * 73 */ 74 75 struct bsearch4_record { 76 uint32_t addr4; 77 uint32_t mask4; 78 struct nhop_object *nh; 79 }; 80 81 struct bsearch4_data { 82 struct fib_data *fd; 83 uint32_t alloc_items; 84 uint32_t num_items; 85 void *mem; 86 struct bsearch4_record *rr; 87 struct bsearch4_record br[0]; 88 }; 89 90 /* 91 * Main IPv4 address lookup function. 92 * 93 * Finds array record with maximum index that is <= provided key. 94 * Assumes 0.0.0.0/0 always exists (may be with NULL nhop) 95 */ 96 static struct nhop_object * 97 bsearch4_lookup(void *algo_data, const struct flm_lookup_key key, uint32_t scopeid) 98 { 99 const struct bsearch4_data *bd = (const struct bsearch4_data *)algo_data; 100 const struct bsearch4_record *br; 101 uint32_t addr4 = ntohl(key.addr4.s_addr); 102 103 int start = 0; 104 int end = bd->num_items; 105 106 int i = (start + end) / 2; 107 while (start + 1 < end) { 108 i = (start + end) / 2; 109 br = &bd->br[i]; 110 if (addr4 < br->addr4) { 111 /* key < average, reduce right boundary */ 112 end = i; 113 continue; 114 } else if (addr4 > br->addr4) { 115 /* key > average, increase left aboundary */ 116 start = i; 117 continue; 118 } else { 119 /* direct match */ 120 return (br->nh); 121 } 122 } 123 /* start + 1 == end */ 124 return (bd->br[start].nh); 125 } 126 127 /* 128 * Preference function. 129 * Assume ideal for < 10 (typical single-interface setup has 5) 130 * Then gradually degrade. 131 * Assume 30 prefixes is at least 60 records, so it will require 8 lookup, 132 * which is even worse than radix. 133 */ 134 static uint8_t 135 bsearch4_get_pref(const struct rib_rtable_info *rinfo) 136 { 137 138 if (rinfo->num_prefixes < 10) 139 return (253); 140 else if (rinfo->num_prefixes < 30) 141 return (255 - rinfo->num_prefixes * 8); 142 else 143 return (1); 144 } 145 146 static enum flm_op_result 147 bsearch4_init(uint32_t fibnum, struct fib_data *fd, void *_old_data, void **_data) 148 { 149 struct bsearch4_data *bd; 150 struct rib_rtable_info rinfo; 151 uint32_t count; 152 size_t sz; 153 void *mem; 154 155 fib_get_rtable_info(fib_get_rh(fd), &rinfo); 156 count = rinfo.num_prefixes * 11 / 10 + 64; 157 158 sz = sizeof(struct bsearch4_data) + sizeof(struct bsearch4_record) * count; 159 /* add cache line sz to ease alignment */ 160 sz += CACHE_LINE_SIZE; 161 mem = malloc(sz, M_RTABLE, M_NOWAIT | M_ZERO); 162 if (mem == NULL) 163 return (FLM_REBUILD); 164 /* Align datapath-usable structure to cache line boundary */ 165 bd = (struct bsearch4_data *)roundup2((uintptr_t)mem, CACHE_LINE_SIZE); 166 bd->mem = mem; 167 bd->alloc_items = count; 168 bd->fd = fd; 169 170 *_data = bd; 171 172 /* 173 * Allocate temporary array to store all rtable data. 174 * This step is required to provide the required prefix iteration order. 175 */ 176 bd->rr = mallocarray(count, sizeof(struct bsearch4_record), M_TEMP, M_NOWAIT | M_ZERO); 177 if (bd->rr == NULL) 178 return (FLM_REBUILD); 179 180 return (FLM_SUCCESS); 181 } 182 183 static void 184 bsearch4_destroy(void *_data) 185 { 186 struct bsearch4_data *bd = (struct bsearch4_data *)_data; 187 188 if (bd->rr != NULL) 189 free(bd->rr, M_TEMP); 190 free(bd->mem, M_RTABLE); 191 } 192 193 /* 194 * Callback storing converted rtable prefixes in the temporary array. 195 * Addresses are converted to a host order. 196 */ 197 static enum flm_op_result 198 bsearch4_add_route_cb(struct rtentry *rt, void *_data) 199 { 200 struct bsearch4_data *bd = (struct bsearch4_data *)_data; 201 struct bsearch4_record *rr; 202 struct in_addr addr4, mask4; 203 uint32_t scopeid; 204 205 if (bd->num_items >= bd->alloc_items) 206 return (FLM_REBUILD); 207 208 rr = &bd->rr[bd->num_items++]; 209 rt_get_inet_prefix_pmask(rt, &addr4, &mask4, &scopeid); 210 rr->addr4 = ntohl(addr4.s_addr); 211 rr->mask4 = ntohl(mask4.s_addr); 212 rr->nh = rt_get_raw_nhop(rt); 213 214 return (FLM_SUCCESS); 215 } 216 217 /* 218 * Prefix comparison function. 219 * 10.0.0.0/24 < 10.0.0.0/25 <- less specific wins 220 * 10.0.0.0/25 < 10.0.0.1/32 <- bigger base wins 221 */ 222 static int 223 rr_cmp(const void *_rec1, const void *_rec2) 224 { 225 const struct bsearch4_record *rec1, *rec2; 226 rec1 = _rec1; 227 rec2 = _rec2; 228 229 if (rec1->addr4 < rec2->addr4) 230 return (-1); 231 else if (rec1->addr4 > rec2->addr4) 232 return (1); 233 234 /* 235 * wider mask value is lesser mask 236 * we want less specific come first, e.g. < 237 */ 238 if (rec1->mask4 < rec2->mask4) 239 return (-1); 240 else if (rec1->mask4 > rec2->mask4) 241 return (1); 242 return (0); 243 } 244 245 struct bsearch4_array { 246 uint32_t alloc_items; 247 uint32_t num_items; 248 struct bsearch4_record *arr; 249 }; 250 251 static bool 252 add_array_entry(struct bsearch4_array *ba, struct bsearch4_record *br_new) 253 { 254 255 if (ba->num_items < ba->alloc_items) { 256 ba->arr[ba->num_items++] = *br_new; 257 return (true); 258 } 259 return (false); 260 } 261 262 static struct bsearch4_record * 263 get_last_entry(struct bsearch4_array *ba) 264 { 265 266 return (&ba->arr[ba->num_items - 1]); 267 } 268 269 /* 270 * 271 * Example: 272 * stack: 10.0.1.0/24,nh=3 array: 10.0.1.0/25,nh=4 -> ++10.0.1.128/24,nh=3 273 * 274 * 275 */ 276 static bool 277 pop_stack_entry(struct bsearch4_array *dst_array, struct bsearch4_array *stack) 278 { 279 uint32_t last_stack_addr, last_array_addr; 280 281 struct bsearch4_record *br_prev = get_last_entry(dst_array); 282 struct bsearch4_record *pstack = get_last_entry(stack); 283 284 /* Regardless of the result, pop stack entry */ 285 stack->num_items--; 286 287 /* Prefix last address for the last entry in lookup array */ 288 last_array_addr = (br_prev->addr4 | ~br_prev->mask4); 289 /* Prefix last address for the stack record entry */ 290 last_stack_addr = (pstack->addr4 | ~pstack->mask4); 291 292 if (last_stack_addr > last_array_addr) { 293 /* 294 * Stack record covers > address space than 295 * the last entry in the lookup array. 296 * Add the remaining parts of a stack record to 297 * the lookup array. 298 */ 299 struct bsearch4_record br_new = { 300 .addr4 = last_array_addr + 1, 301 .mask4 = pstack->mask4, 302 .nh = pstack->nh, 303 }; 304 return (add_array_entry(dst_array, &br_new)); 305 } 306 307 return (true); 308 } 309 310 /* 311 * Updates resulting array @dst_array with a rib entry @rib_entry. 312 */ 313 static bool 314 bsearch4_process_record(struct bsearch4_array *dst_array, 315 struct bsearch4_array *stack, struct bsearch4_record *rib_entry) 316 { 317 318 /* 319 * Maintain invariant: current rib_entry is always contained 320 * in the top stack entry. 321 * Note we always have 0.0.0.0/0. 322 */ 323 while (stack->num_items > 0) { 324 struct bsearch4_record *pst = get_last_entry(stack); 325 326 /* 327 * Check if we need to pop stack. 328 * Rely on the ordering - larger prefixes comes up first 329 * Pop any entry that doesn't contain current prefix. 330 */ 331 if (pst->addr4 == (rib_entry->addr4 & pst->mask4)) 332 break; 333 334 if (!pop_stack_entry(dst_array, stack)) 335 return (false); 336 } 337 338 if (dst_array->num_items > 0) { 339 340 /* 341 * Check if there is a gap between previous entry and a 342 * current entry. Code above guarantees that both previous 343 * and current entry are contained in the top stack entry. 344 * 345 * Example: last: 10.0.0.1(/32,nh=3) cur: 10.0.0.3(/32,nh=4), 346 * stack: 10.0.0.0/24,nh=2. 347 * Cover a gap between previous and current by adding stack 348 * nexthop. 349 */ 350 struct bsearch4_record *br_tmp = get_last_entry(dst_array); 351 uint32_t last_declared_addr = br_tmp->addr4 | ~br_tmp->mask4; 352 if (last_declared_addr < rib_entry->addr4 - 1) { 353 /* Cover a hole */ 354 struct bsearch4_record *pst = get_last_entry(stack); 355 struct bsearch4_record new_entry = { 356 .addr4 = last_declared_addr + 1, 357 .mask4 = pst->mask4, 358 .nh = pst->nh, 359 }; 360 if (!add_array_entry(dst_array, &new_entry)) 361 return (false); 362 } 363 364 /* 365 * Special case: adding more specific prefix at the start of 366 * the previous interval: 367 * 10.0.0.0(/24,nh=3), 10.0.0.0(/25,nh=4) 368 * Alter the last record, seeting new nexthop and mask. 369 */ 370 if (br_tmp->addr4 == rib_entry->addr4) { 371 *br_tmp = *rib_entry; 372 add_array_entry(stack, rib_entry); 373 return (true); 374 } 375 } 376 377 if (!add_array_entry(dst_array, rib_entry)) 378 return (false); 379 add_array_entry(stack, rib_entry); 380 381 return (true); 382 } 383 384 static enum flm_op_result 385 bsearch4_build_array(struct bsearch4_array *dst_array, struct bsearch4_array *src_array) 386 { 387 388 /* 389 * During iteration, we keep track of all prefixes in rtable 390 * we currently match, by maintaining stack. As there can be only 391 * 32 prefixes for a single address, pre-allocate stack of size 32. 392 */ 393 struct bsearch4_array stack = { 394 .alloc_items = 32, 395 .arr = mallocarray(32, sizeof(struct bsearch4_record), M_TEMP, M_NOWAIT | M_ZERO), 396 }; 397 if (stack.arr == NULL) 398 return (FLM_REBUILD); 399 400 for (int i = 0; i < src_array->num_items; i++) { 401 struct bsearch4_record *rib_entry = &src_array->arr[i]; 402 403 if (!bsearch4_process_record(dst_array, &stack, rib_entry)) { 404 free(stack.arr, M_TEMP); 405 return (FLM_REBUILD); 406 } 407 } 408 409 /* 410 * We know that last record is contained in the top stack entry. 411 */ 412 while (stack.num_items > 0) { 413 if (!pop_stack_entry(dst_array, &stack)) 414 return (FLM_REBUILD); 415 } 416 free(stack.arr, M_TEMP); 417 418 return (FLM_SUCCESS); 419 } 420 421 static enum flm_op_result 422 bsearch4_build(struct bsearch4_data *bd) 423 { 424 enum flm_op_result ret; 425 426 struct bsearch4_array prefixes_array = { 427 .alloc_items = bd->alloc_items, 428 .num_items = bd->num_items, 429 .arr = bd->rr, 430 }; 431 432 /* Add default route if not exists */ 433 bool default_found = false; 434 for (int i = 0; i < prefixes_array.num_items; i++) { 435 if (prefixes_array.arr[i].mask4 == 0) { 436 default_found = true; 437 break; 438 } 439 } 440 if (!default_found) { 441 /* Add default route with NULL nhop */ 442 struct bsearch4_record default_entry = {}; 443 if (!add_array_entry(&prefixes_array, &default_entry)) 444 return (FLM_REBUILD); 445 } 446 447 /* Sort prefixes */ 448 qsort(prefixes_array.arr, prefixes_array.num_items, sizeof(struct bsearch4_record), rr_cmp); 449 450 struct bsearch4_array dst_array = { 451 .alloc_items = bd->alloc_items, 452 .arr = bd->br, 453 }; 454 455 ret = bsearch4_build_array(&dst_array, &prefixes_array); 456 bd->num_items = dst_array.num_items; 457 458 free(bd->rr, M_TEMP); 459 bd->rr = NULL; 460 return (ret); 461 } 462 463 464 static enum flm_op_result 465 bsearch4_end_dump(void *_data, struct fib_dp *dp) 466 { 467 struct bsearch4_data *bd = (struct bsearch4_data *)_data; 468 enum flm_op_result ret; 469 470 ret = bsearch4_build(bd); 471 if (ret == FLM_SUCCESS) { 472 dp->f = bsearch4_lookup; 473 dp->arg = bd; 474 } 475 476 return (ret); 477 } 478 479 static enum flm_op_result 480 bsearch4_change_cb(struct rib_head *rnh, struct rib_cmd_info *rc, 481 void *_data) 482 { 483 484 return (FLM_REBUILD); 485 } 486 487 struct fib_lookup_module flm_bsearch4= { 488 .flm_name = "bsearch4", 489 .flm_family = AF_INET, 490 .flm_init_cb = bsearch4_init, 491 .flm_destroy_cb = bsearch4_destroy, 492 .flm_dump_rib_item_cb = bsearch4_add_route_cb, 493 .flm_dump_end_cb = bsearch4_end_dump, 494 .flm_change_rib_item_cb = bsearch4_change_cb, 495 .flm_get_pref = bsearch4_get_pref, 496 }; 497 498 /* 499 * Lockless radix lookup algo. 500 * 501 * Compiles immutable radix from the current routing table. 502 * Used with small amount of routes (<1000). 503 * As datastructure is immutable, it gets rebuild on each rtable change. 504 * 505 * Lookups are slightly faster as shorter lookup keys are used 506 * (4 bytes instead of 8 in stock radix). 507 */ 508 509 #define KEY_LEN_INET (offsetof(struct sockaddr_in, sin_addr) + sizeof(in_addr_t)) 510 #define OFF_LEN_INET (8 * offsetof(struct sockaddr_in, sin_addr)) 511 struct radix4_addr_entry { 512 struct radix_node rn[2]; 513 struct sockaddr_in addr; 514 struct nhop_object *nhop; 515 }; 516 #define LRADIX4_ITEM_SZ roundup2(sizeof(struct radix4_addr_entry), 64) 517 518 struct lradix4_data { 519 struct radix_node_head *rnh; 520 struct fib_data *fd; 521 void *mem; 522 char *rt_base; 523 uint32_t alloc_items; 524 uint32_t num_items; 525 }; 526 527 static struct nhop_object * 528 lradix4_lookup(void *algo_data, const struct flm_lookup_key key, uint32_t scopeid) 529 { 530 struct radix_node_head *rnh = (struct radix_node_head *)algo_data; 531 struct radix4_addr_entry *ent; 532 struct sockaddr_in addr4 = { 533 .sin_len = KEY_LEN_INET, 534 .sin_addr = key.addr4, 535 }; 536 ent = (struct radix4_addr_entry *)(rn_match(&addr4, &rnh->rh)); 537 if (ent != NULL) 538 return (ent->nhop); 539 return (NULL); 540 } 541 542 /* 543 * Preference function. 544 * Assume close-to-ideal of < 10 routes (though worse than bsearch), then 545 * gradually degrade until 1000 routes are reached. 546 */ 547 static uint8_t 548 lradix4_get_pref(const struct rib_rtable_info *rinfo) 549 { 550 551 if (rinfo->num_prefixes < 10) 552 return (250); 553 else if (rinfo->num_prefixes < 1000) 554 return (254 - rinfo->num_prefixes / 4); 555 else 556 return (1); 557 } 558 559 static enum flm_op_result 560 lradix4_init(uint32_t fibnum, struct fib_data *fd, void *_old_data, void **_data) 561 { 562 struct lradix4_data *lr; 563 struct rib_rtable_info rinfo; 564 uint32_t count; 565 size_t sz; 566 567 lr = malloc(sizeof(struct lradix4_data), M_RTABLE, M_NOWAIT | M_ZERO); 568 if (lr == NULL || !rn_inithead((void **)&lr->rnh, OFF_LEN_INET)) 569 return (FLM_REBUILD); 570 fib_get_rtable_info(fib_get_rh(fd), &rinfo); 571 572 count = rinfo.num_prefixes * 11 / 10; 573 sz = count * LRADIX4_ITEM_SZ + CACHE_LINE_SIZE; 574 lr->mem = malloc(sz, M_RTABLE, M_NOWAIT | M_ZERO); 575 if (lr->mem == NULL) 576 return (FLM_REBUILD); 577 /* Align all rtentries to a cacheline boundary */ 578 lr->rt_base = (char *)roundup2((uintptr_t)lr->mem, CACHE_LINE_SIZE); 579 lr->alloc_items = count; 580 lr->fd = fd; 581 582 *_data = lr; 583 584 return (FLM_SUCCESS); 585 } 586 587 static void 588 lradix4_destroy(void *_data) 589 { 590 struct lradix4_data *lr = (struct lradix4_data *)_data; 591 592 if (lr->rnh != NULL) 593 rn_detachhead((void **)&lr->rnh); 594 if (lr->mem != NULL) 595 free(lr->mem, M_RTABLE); 596 free(lr, M_RTABLE); 597 } 598 599 static enum flm_op_result 600 lradix4_add_route_cb(struct rtentry *rt, void *_data) 601 { 602 struct lradix4_data *lr = (struct lradix4_data *)_data; 603 struct radix4_addr_entry *ae; 604 struct sockaddr_in mask; 605 struct sockaddr *rt_mask; 606 struct radix_node *rn; 607 struct in_addr addr4, mask4; 608 uint32_t scopeid; 609 610 if (lr->num_items >= lr->alloc_items) 611 return (FLM_REBUILD); 612 613 ae = (struct radix4_addr_entry *)(lr->rt_base + lr->num_items * LRADIX4_ITEM_SZ); 614 lr->num_items++; 615 616 ae->nhop = rt_get_raw_nhop(rt); 617 618 rt_get_inet_prefix_pmask(rt, &addr4, &mask4, &scopeid); 619 ae->addr.sin_len = KEY_LEN_INET; 620 ae->addr.sin_addr = addr4; 621 622 if (mask4.s_addr != INADDR_BROADCAST) { 623 bzero(&mask, sizeof(mask)); 624 mask.sin_len = KEY_LEN_INET; 625 mask.sin_addr = mask4; 626 rt_mask = (struct sockaddr *)&mask; 627 } else 628 rt_mask = NULL; 629 630 rn = lr->rnh->rnh_addaddr((struct sockaddr *)&ae->addr, rt_mask, 631 &lr->rnh->rh, ae->rn); 632 if (rn == NULL) 633 return (FLM_REBUILD); 634 635 return (FLM_SUCCESS); 636 } 637 638 static enum flm_op_result 639 lradix4_end_dump(void *_data, struct fib_dp *dp) 640 { 641 struct lradix4_data *lr = (struct lradix4_data *)_data; 642 643 dp->f = lradix4_lookup; 644 dp->arg = lr->rnh; 645 646 return (FLM_SUCCESS); 647 } 648 649 static enum flm_op_result 650 lradix4_change_cb(struct rib_head *rnh, struct rib_cmd_info *rc, 651 void *_data) 652 { 653 654 return (FLM_REBUILD); 655 } 656 657 struct fib_lookup_module flm_radix4_lockless = { 658 .flm_name = "radix4_lockless", 659 .flm_family = AF_INET, 660 .flm_init_cb = lradix4_init, 661 .flm_destroy_cb = lradix4_destroy, 662 .flm_dump_rib_item_cb = lradix4_add_route_cb, 663 .flm_dump_end_cb = lradix4_end_dump, 664 .flm_change_rib_item_cb = lradix4_change_cb, 665 .flm_get_pref = lradix4_get_pref, 666 }; 667 668 /* 669 * Fallback lookup algorithm. 670 * This is a simple wrapper around system radix. 671 */ 672 673 struct radix4_data { 674 struct fib_data *fd; 675 struct rib_head *rh; 676 }; 677 678 static struct nhop_object * 679 radix4_lookup(void *algo_data, const struct flm_lookup_key key, uint32_t scopeid) 680 { 681 RIB_RLOCK_TRACKER; 682 struct rib_head *rh = (struct rib_head *)algo_data; 683 struct radix_node *rn; 684 struct nhop_object *nh; 685 686 /* Prepare lookup key */ 687 struct sockaddr_in sin4 = { 688 .sin_family = AF_INET, 689 .sin_len = sizeof(struct sockaddr_in), 690 .sin_addr = key.addr4, 691 }; 692 693 nh = NULL; 694 RIB_RLOCK(rh); 695 rn = rn_match((void *)&sin4, &rh->head); 696 if (rn != NULL && ((rn->rn_flags & RNF_ROOT) == 0)) 697 nh = (RNTORT(rn))->rt_nhop; 698 RIB_RUNLOCK(rh); 699 700 return (nh); 701 } 702 703 static uint8_t 704 radix4_get_pref(const struct rib_rtable_info *rinfo) 705 { 706 707 return (50); 708 } 709 710 static enum flm_op_result 711 radix4_init(uint32_t fibnum, struct fib_data *fd, void *_old_data, void **_data) 712 { 713 struct radix4_data *r4; 714 715 r4 = malloc(sizeof(struct radix4_data), M_RTABLE, M_NOWAIT | M_ZERO); 716 if (r4 == NULL) 717 return (FLM_REBUILD); 718 r4->fd = fd; 719 r4->rh = fib_get_rh(fd); 720 721 *_data = r4; 722 723 return (FLM_SUCCESS); 724 } 725 726 static void 727 radix4_destroy(void *_data) 728 { 729 730 free(_data, M_RTABLE); 731 } 732 733 static enum flm_op_result 734 radix4_add_route_cb(struct rtentry *rt, void *_data) 735 { 736 737 return (FLM_SUCCESS); 738 } 739 740 static enum flm_op_result 741 radix4_end_dump(void *_data, struct fib_dp *dp) 742 { 743 struct radix4_data *r4 = (struct radix4_data *)_data; 744 745 dp->f = radix4_lookup; 746 dp->arg = r4->rh; 747 748 return (FLM_SUCCESS); 749 } 750 751 static enum flm_op_result 752 radix4_change_cb(struct rib_head *rnh, struct rib_cmd_info *rc, 753 void *_data) 754 { 755 756 return (FLM_SUCCESS); 757 } 758 759 struct fib_lookup_module flm_radix4 = { 760 .flm_name = "radix4", 761 .flm_family = AF_INET, 762 .flm_init_cb = radix4_init, 763 .flm_destroy_cb = radix4_destroy, 764 .flm_dump_rib_item_cb = radix4_add_route_cb, 765 .flm_dump_end_cb = radix4_end_dump, 766 .flm_change_rib_item_cb = radix4_change_cb, 767 .flm_get_pref = radix4_get_pref, 768 }; 769 770 static void 771 fib4_algo_init(void) 772 { 773 774 fib_module_register(&flm_bsearch4); 775 fib_module_register(&flm_radix4_lockless); 776 fib_module_register(&flm_radix4); 777 } 778 SYSINIT(fib4_algo_init, SI_SUB_PROTO_DOMAIN, SI_ORDER_THIRD, fib4_algo_init, NULL); 779