1/*- 2 * SPDX-License-Identifier: BSD-2-Clause-FreeBSD 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 75struct bsearch4_record { 76 uint32_t addr4; 77 uint32_t mask4; 78 struct nhop_object *nh; 79}; 80 81struct 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 */ 96static struct nhop_object * 97bsearch4_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 */ 134static uint8_t 135bsearch4_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 146static enum flm_op_result 147bsearch4_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 183static void 184bsearch4_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 */ 197static enum flm_op_result 198bsearch4_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 */ 222static int 223rr_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 245struct bsearch4_array { 246 uint32_t alloc_items; 247 uint32_t num_items; 248 struct bsearch4_record *arr; 249}; 250 251static bool 252add_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 262static struct bsearch4_record * 263get_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 */ 276static bool 277pop_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 */ 313static bool 314bsearch4_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 384static enum flm_op_result 385bsearch4_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 421static enum flm_op_result 422bsearch4_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 464static enum flm_op_result 465bsearch4_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 479static enum flm_op_result 480bsearch4_change_cb(struct rib_head *rnh, struct rib_cmd_info *rc, 481 void *_data) 482{ 483 484 return (FLM_REBUILD); 485} 486 487struct 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)) 511struct 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 518struct 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 527static struct nhop_object * 528lradix4_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 */ 547static uint8_t 548lradix4_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 559static enum flm_op_result 560lradix4_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 587static void 588lradix4_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 599static enum flm_op_result 600lradix4_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 638static enum flm_op_result 639lradix4_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 649static enum flm_op_result 650lradix4_change_cb(struct rib_head *rnh, struct rib_cmd_info *rc, 651 void *_data) 652{ 653 654 return (FLM_REBUILD); 655} 656 657struct 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 673struct radix4_data { 674 struct fib_data *fd; 675 struct rib_head *rh; 676}; 677 678static struct nhop_object * 679radix4_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 703static uint8_t 704radix4_get_pref(const struct rib_rtable_info *rinfo) 705{ 706 707 return (50); 708} 709 710static enum flm_op_result 711radix4_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 726static void 727radix4_destroy(void *_data) 728{ 729 730 free(_data, M_RTABLE); 731} 732 733static enum flm_op_result 734radix4_add_route_cb(struct rtentry *rt, void *_data) 735{ 736 737 return (FLM_SUCCESS); 738} 739 740static enum flm_op_result 741radix4_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 751static enum flm_op_result 752radix4_change_cb(struct rib_head *rnh, struct rib_cmd_info *rc, 753 void *_data) 754{ 755 756 return (FLM_SUCCESS); 757} 758 759struct 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 770static void 771fib4_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} 778SYSINIT(fib4_algo_init, SI_SUB_PROTO_DOMAIN, SI_ORDER_THIRD, fib4_algo_init, NULL); 779