33#include <sys/kernel.h>
35#include <sys/rmlock.h>
36#include <sys/malloc.h>
37#include <sys/kernel.h>
39#include <sys/socket.h>
40#include <sys/sysctl.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>
78 struct nhop_object *
nh;
96static struct nhop_object *
106 int i = (start + end) / 2;
107 while (start + 1 < end) {
108 i = (start + end) / 2;
110 if (addr4 < br->
addr4) {
124 return (bd->
br[start].
nh);
138 if (rinfo->num_prefixes < 10)
140 else if (rinfo->num_prefixes < 30)
141 return (255 - rinfo->num_prefixes * 8);
146static enum flm_op_result
150 struct rib_rtable_info rinfo;
155 fib_get_rtable_info(fib_get_rh(fd), &rinfo);
156 count = rinfo.num_prefixes * 11 / 10 + 64;
160 sz += CACHE_LINE_SIZE;
161 mem = malloc(sz, M_RTABLE, M_NOWAIT | M_ZERO);
163 return (FLM_REBUILD);
178 return (FLM_REBUILD);
180 return (FLM_SUCCESS);
189 free(bd->
rr, M_TEMP);
190 free(bd->
mem, M_RTABLE);
197static enum flm_op_result
206 return (FLM_REBUILD);
209 rt_get_inet_prefix_pmask(rt, &addr4, &mask4, &scopeid);
212 rr->
nh = rt_get_raw_nhop(rt);
214 return (FLM_SUCCESS);
223rr_cmp(
const void *_rec1,
const void *_rec2)
279 uint32_t last_stack_addr, last_array_addr;
288 last_array_addr = (br_prev->
addr4 | ~br_prev->mask4);
290 last_stack_addr = (pstack->
addr4 | ~pstack->mask4);
292 if (last_stack_addr > last_array_addr) {
300 .
addr4 = last_array_addr + 1,
301 .mask4 = pstack->
mask4,
351 uint32_t last_declared_addr = br_tmp->
addr4 | ~br_tmp->mask4;
352 if (last_declared_addr < rib_entry->
addr4 - 1) {
356 .
addr4 = last_declared_addr + 1,
371 *br_tmp = *rib_entry;
384static enum flm_op_result
395 .arr = mallocarray(32,
sizeof(
struct bsearch4_record), M_TEMP, M_NOWAIT | M_ZERO),
397 if (stack.
arr == NULL)
398 return (FLM_REBUILD);
400 for (
int i = 0; i < src_array->
num_items; i++) {
404 free(stack.
arr, M_TEMP);
405 return (FLM_REBUILD);
414 return (FLM_REBUILD);
416 free(stack.
arr, M_TEMP);
418 return (FLM_SUCCESS);
421static enum flm_op_result
424 enum flm_op_result ret;
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;
440 if (!default_found) {
444 return (FLM_REBUILD);
458 free(bd->
rr, M_TEMP);
464static enum flm_op_result
468 enum flm_op_result ret;
471 if (ret == FLM_SUCCESS) {
479static enum flm_op_result
484 return (FLM_REBUILD);
488 .flm_name =
"bsearch4",
489 .flm_family = AF_INET,
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))
512 struct radix_node
rn[2];
516#define LRADIX4_ITEM_SZ roundup2(sizeof(struct radix4_addr_entry), 64)
519 struct radix_node_head *
rnh;
527static struct nhop_object *
530 struct radix_node_head *rnh = (
struct radix_node_head *)algo_data;
534 .sin_addr = key.addr4,
551 if (rinfo->num_prefixes < 10)
553 else if (rinfo->num_prefixes < 1000)
554 return (254 - rinfo->num_prefixes / 4);
559static enum flm_op_result
563 struct rib_rtable_info rinfo;
567 lr = malloc(
sizeof(
struct lradix4_data), M_RTABLE, M_NOWAIT | M_ZERO);
569 return (FLM_REBUILD);
570 fib_get_rtable_info(fib_get_rh(fd), &rinfo);
572 count = rinfo.num_prefixes * 11 / 10;
574 lr->
mem = malloc(sz, M_RTABLE, M_NOWAIT | M_ZERO);
576 return (FLM_REBUILD);
578 lr->
rt_base = (
char *)roundup2((uintptr_t)lr->
mem, CACHE_LINE_SIZE);
584 return (FLM_SUCCESS);
593 rn_detachhead((
void **)&lr->
rnh);
595 free(lr->
mem, M_RTABLE);
599static enum flm_op_result
605 struct sockaddr *rt_mask;
606 struct radix_node *rn;
611 return (FLM_REBUILD);
616 ae->
nhop = rt_get_raw_nhop(rt);
618 rt_get_inet_prefix_pmask(rt, &addr4, &mask4, &scopeid);
623 bzero(&mask,
sizeof(mask));
626 rt_mask = (
struct sockaddr *)&mask;
630 rn = lr->
rnh->rnh_addaddr((
struct sockaddr *)&ae->
addr, rt_mask,
631 &lr->
rnh->rh, ae->
rn);
633 return (FLM_REBUILD);
635 return (FLM_SUCCESS);
638static enum flm_op_result
646 return (FLM_SUCCESS);
649static enum flm_op_result
654 return (FLM_REBUILD);
658 .flm_name =
"radix4_lockless",
659 .flm_family = AF_INET,
678static struct nhop_object *
682 struct rib_head *rh = (
struct rib_head *)algo_data;
683 struct radix_node *rn;
684 struct nhop_object *nh;
695 rn = rn_match((
void *)&sin4, &rh->head);
696 if (rn != NULL && ((rn->rn_flags & RNF_ROOT) == 0))
697 nh = (RNTORT(rn))->rt_nhop;
710static enum flm_op_result
715 r4 = malloc(
sizeof(
struct radix4_data), M_RTABLE, M_NOWAIT | M_ZERO);
717 return (FLM_REBUILD);
719 r4->
rh = fib_get_rh(
fd);
723 return (FLM_SUCCESS);
730 free(_data, M_RTABLE);
733static enum flm_op_result
737 return (FLM_SUCCESS);
740static enum flm_op_result
748 return (FLM_SUCCESS);
751static enum flm_op_result
756 return (FLM_SUCCESS);
760 .flm_name =
"radix4",
761 .flm_family = AF_INET,
struct fib_lookup_module flm_radix4_lockless
static enum flm_op_result lradix4_init(uint32_t fibnum, struct fib_data *fd, void *_old_data, void **_data)
static enum flm_op_result lradix4_end_dump(void *_data, struct fib_dp *dp)
static void radix4_destroy(void *_data)
static enum flm_op_result lradix4_add_route_cb(struct rtentry *rt, void *_data)
static struct nhop_object * lradix4_lookup(void *algo_data, const struct flm_lookup_key key, uint32_t scopeid)
static uint8_t radix4_get_pref(const struct rib_rtable_info *rinfo)
static enum flm_op_result bsearch4_end_dump(void *_data, struct fib_dp *dp)
static void fib4_algo_init(void)
static uint8_t lradix4_get_pref(const struct rib_rtable_info *rinfo)
static uint8_t bsearch4_get_pref(const struct rib_rtable_info *rinfo)
static enum flm_op_result radix4_end_dump(void *_data, struct fib_dp *dp)
static enum flm_op_result lradix4_change_cb(struct rib_head *rnh, struct rib_cmd_info *rc, void *_data)
static enum flm_op_result bsearch4_add_route_cb(struct rtentry *rt, void *_data)
static enum flm_op_result bsearch4_init(uint32_t fibnum, struct fib_data *fd, void *_old_data, void **_data)
static void bsearch4_destroy(void *_data)
static bool bsearch4_process_record(struct bsearch4_array *dst_array, struct bsearch4_array *stack, struct bsearch4_record *rib_entry)
static struct nhop_object * bsearch4_lookup(void *algo_data, const struct flm_lookup_key key, uint32_t scopeid)
static enum flm_op_result bsearch4_change_cb(struct rib_head *rnh, struct rib_cmd_info *rc, void *_data)
static bool pop_stack_entry(struct bsearch4_array *dst_array, struct bsearch4_array *stack)
struct fib_lookup_module flm_bsearch4
static void lradix4_destroy(void *_data)
static enum flm_op_result bsearch4_build(struct bsearch4_data *bd)
static bool add_array_entry(struct bsearch4_array *ba, struct bsearch4_record *br_new)
SYSINIT(fib4_algo_init, SI_SUB_PROTO_DOMAIN, SI_ORDER_THIRD, fib4_algo_init, NULL)
static enum flm_op_result radix4_add_route_cb(struct rtentry *rt, void *_data)
static enum flm_op_result radix4_init(uint32_t fibnum, struct fib_data *fd, void *_old_data, void **_data)
static int rr_cmp(const void *_rec1, const void *_rec2)
static struct bsearch4_record * get_last_entry(struct bsearch4_array *ba)
struct fib_lookup_module flm_radix4
static struct nhop_object * radix4_lookup(void *algo_data, const struct flm_lookup_key key, uint32_t scopeid)
static enum flm_op_result radix4_change_cb(struct rib_head *rnh, struct rib_cmd_info *rc, void *_data)
static enum flm_op_result bsearch4_build_array(struct bsearch4_array *dst_array, struct bsearch4_array *src_array)
struct bsearch4_record * arr
struct bsearch4_record br[0]
struct bsearch4_record * rr
struct radix_node_head * rnh
struct nhop_object * nhop