aboutsummaryrefslogtreecommitdiff
path: root/sys/netinet
diff options
context:
space:
mode:
Diffstat (limited to 'sys/netinet')
-rw-r--r--sys/netinet/in_fib.c37
-rw-r--r--sys/netinet/in_fib_algo.c765
2 files changed, 802 insertions, 0 deletions
diff --git a/sys/netinet/in_fib.c b/sys/netinet/in_fib.c
index ee54d524c3e2..8a6e64876b3d 100644
--- a/sys/netinet/in_fib.c
+++ b/sys/netinet/in_fib.c
@@ -49,6 +49,7 @@ __FBSDID("$FreeBSD$");
#include <net/route.h>
#include <net/route/route_ctl.h>
#include <net/route/route_var.h>
+#include <net/route/fib_algo.h>
#include <net/route/nhop.h>
#include <net/toeplitz.h>
#include <net/vnet.h>
@@ -63,6 +64,10 @@ __FBSDID("$FreeBSD$");
/* Assert 'struct route_in' is compatible with 'struct route' */
CHK_STRUCT_ROUTE_COMPAT(struct route_in, ro_dst4);
+#ifdef FIB_ALGO
+VNET_DEFINE(struct fib_dp *, inet_dp);
+#endif
+
#ifdef ROUTE_MPATH
struct _hash_5tuple_ipv4 {
struct in_addr src;
@@ -103,6 +108,29 @@ fib4_calc_software_hash(struct in_addr src, struct in_addr dst,
* one needs to pass NHR_REF as a flag. This will return referenced
* nexthop.
*/
+#ifdef FIB_ALGO
+struct nhop_object *
+fib4_lookup(uint32_t fibnum, struct in_addr dst, uint32_t scopeid,
+ uint32_t flags, uint32_t flowid)
+{
+ struct nhop_object *nh;
+ struct fib_dp *dp = &V_inet_dp[fibnum];
+ struct flm_lookup_key key = {.addr4 = dst };
+
+ nh = dp->f(dp->arg, key, scopeid);
+ if (nh != NULL) {
+ nh = nhop_select(nh, flowid);
+ /* Ensure route & ifp is UP */
+ if (RT_LINK_IS_UP(nh->nh_ifp)) {
+ if (flags & NHR_REF)
+ nhop_ref_object(nh);
+ return (nh);
+ }
+ }
+ RTSTAT_INC(rts_unreach);
+ return (NULL);
+}
+#else
struct nhop_object *
fib4_lookup(uint32_t fibnum, struct in_addr dst, uint32_t scopeid,
uint32_t flags, uint32_t flowid)
@@ -142,6 +170,7 @@ fib4_lookup(uint32_t fibnum, struct in_addr dst, uint32_t scopeid,
RTSTAT_INC(rts_unreach);
return (NULL);
}
+#endif
inline static int
check_urpf_nhop(const struct nhop_object *nh, uint32_t flags,
@@ -180,6 +209,7 @@ check_urpf(struct nhop_object *nh, uint32_t flags,
return (check_urpf_nhop(nh, flags, src_if));
}
+#ifndef FIB_ALGO
static struct nhop_object *
lookup_nhop(uint32_t fibnum, struct in_addr dst, uint32_t scopeid)
{
@@ -208,6 +238,7 @@ lookup_nhop(uint32_t fibnum, struct in_addr dst, uint32_t scopeid)
return (nh);
}
+#endif
/*
* Performs reverse path forwarding lookup.
@@ -223,8 +254,14 @@ fib4_check_urpf(uint32_t fibnum, struct in_addr dst, uint32_t scopeid,
uint32_t flags, const struct ifnet *src_if)
{
struct nhop_object *nh;
+#ifdef FIB_ALGO
+ struct fib_dp *dp = &V_inet_dp[fibnum];
+ struct flm_lookup_key key = {.addr4 = dst };
+ nh = dp->f(dp->arg, key, scopeid);
+#else
nh = lookup_nhop(fibnum, dst, scopeid);
+#endif
if (nh != NULL)
return (check_urpf(nh, flags, src_if));
diff --git a/sys/netinet/in_fib_algo.c b/sys/netinet/in_fib_algo.c
new file mode 100644
index 000000000000..a5048c52b75d
--- /dev/null
+++ b/sys/netinet/in_fib_algo.c
@@ -0,0 +1,765 @@
+/*-
+ * SPDX-License-Identifier: BSD-2-Clause-FreeBSD
+ *
+ * Copyright (c) 2020 Alexander V. Chernikov
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in the
+ * documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
+ * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
+ * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
+ * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
+ * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
+ * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+ * SUCH DAMAGE.
+ */
+
+#include <sys/cdefs.h>
+__FBSDID("$FreeBSD$");
+#include "opt_inet.h"
+
+#include <sys/param.h>
+#include <sys/kernel.h>
+#include <sys/lock.h>
+#include <sys/rmlock.h>
+#include <sys/malloc.h>
+#include <sys/kernel.h>
+#include <sys/priv.h>
+#include <sys/socket.h>
+#include <sys/sysctl.h>
+#include <net/vnet.h>
+
+#include <net/if.h>
+#include <netinet/in.h>
+
+#include <net/route.h>
+#include <net/route/nhop.h>
+#include <net/route/route_ctl.h>
+#include <net/route/route_var.h>
+#include <net/route/fib_algo.h>
+
+/*
+ * Binary search lookup algo.
+ *
+ * Compiles route table into a sorted array.
+ * Used with small amount of routes (< 16).
+ * As array is immutable, it is rebuild on each rtable change.
+ *
+ * Example:
+ *
+ * 0.0.0.0/0 -> nh1
+ * 10.0.0.0/24 -> nh2
+ * 10.0.0.1/32 -> nh3
+ *
+ * gets compiled to:
+ *
+ * 0.0.0.0 -> nh1
+ * 10.0.0.0 -> nh2
+ * 10.0.0.1 -> nh3
+ * 10.0.0.2 -> nh2
+ * 10.0.1.0 -> nh1
+ *
+ */
+
+struct bsearch4_record {
+ uint32_t addr4;
+ uint32_t mask4;
+ struct nhop_object *nh;
+};
+
+struct bsearch4_data {
+ struct fib_data *fd;
+ uint32_t alloc_items;
+ uint32_t num_items;
+ void *mem;
+ struct bsearch4_record *rr;
+ struct bsearch4_record br[0];
+};
+
+/*
+ * Main IPv4 address lookup function.
+ *
+ * Finds array record with maximum index that is <= provided key.
+ * Assumes 0.0.0.0/0 always exists (may be with NULL nhop)
+ */
+static struct nhop_object *
+bsearch4_lookup(void *algo_data, const struct flm_lookup_key key, uint32_t scopeid)
+{
+ const struct bsearch4_data *bd = (const struct bsearch4_data *)algo_data;
+ const struct bsearch4_record *br;
+ uint32_t addr4 = ntohl(key.addr4.s_addr);
+
+ int start = 0;
+ int end = bd->num_items;
+
+ int i = (start + end) / 2;
+ while (start + 1 < end) {
+ i = (start + end) / 2;
+ br = &bd->br[i];
+ if (addr4 < br->addr4) {
+ /* key < average, reduce right boundary */
+ end = i;
+ continue;
+ } else if (addr4 > br->addr4) {
+ /* key > average, increase left aboundary */
+ start = i;
+ continue;
+ } else {
+ /* direct match */
+ return (br->nh);
+ }
+ }
+ /* start + 1 == end */
+ return (bd->br[start].nh);
+}
+
+/*
+ * Preference function.
+ * Assume ideal for < 10 (typical single-interface setup has 5)
+ * Then gradually degrade.
+ * Assume 30 prefixes is at least 60 records, so it will require 8 lookup,
+ * which is even worse than radix.
+ */
+static uint8_t
+bsearch4_get_pref(const struct rib_rtable_info *rinfo)
+{
+
+ if (rinfo->num_prefixes < 10)
+ return (253);
+ else if (rinfo->num_prefixes < 30)
+ return (255 - rinfo->num_prefixes * 8);
+ else
+ return (1);
+}
+
+static enum flm_op_result
+bsearch4_init(uint32_t fibnum, struct fib_data *fd, void *_old_data, void **_data)
+{
+ struct bsearch4_data *bd;
+ struct rib_rtable_info rinfo;
+ uint32_t count;
+ size_t sz;
+ void *mem;
+
+ fib_get_rtable_info(fib_get_rh(fd), &rinfo);
+ count = rinfo.num_prefixes * 11 / 10 + 64;
+
+ sz = sizeof(struct bsearch4_data) + sizeof(struct bsearch4_record) * count;
+ /* add cache line sz to ease alignment */
+ sz += CACHE_LINE_SIZE;
+ mem = malloc(sz, M_RTABLE, M_NOWAIT | M_ZERO);
+ if (mem == NULL)
+ return (FLM_REBUILD);
+ /* Align datapath-usable structure to cache line boundary */
+ bd = (struct bsearch4_data *)roundup2((uintptr_t)mem, CACHE_LINE_SIZE);
+ bd->mem = mem;
+ bd->alloc_items = count;
+ bd->fd = fd;
+
+ *_data = bd;
+
+ /*
+ * Allocate temporary array to store all rtable data.
+ * This step is required to provide the required prefix iteration order.
+ */
+ bd->rr = mallocarray(count, sizeof(struct bsearch4_record), M_TEMP, M_NOWAIT | M_ZERO);
+ if (bd->rr == NULL)
+ return (FLM_REBUILD);
+
+ return (FLM_SUCCESS);
+}
+
+static void
+bsearch4_destroy(void *_data)
+{
+ struct bsearch4_data *bd = (struct bsearch4_data *)_data;
+
+ if (bd->rr != NULL)
+ free(bd->rr, M_TEMP);
+ free(bd->mem, M_RTABLE);
+}
+
+/*
+ * Callback storing converted rtable prefixes in the temporary array.
+ * Addresses are converted to a host order.
+ */
+static enum flm_op_result
+bsearch4_add_route_cb(struct rtentry *rt, void *_data)
+{
+ struct bsearch4_data *bd = (struct bsearch4_data *)_data;
+ struct bsearch4_record *rr;
+ struct in_addr addr4, mask4;
+ uint32_t scopeid;
+
+ if (bd->num_items >= bd->alloc_items)
+ return (FLM_REBUILD);
+
+ rr = &bd->rr[bd->num_items++];
+ rt_get_inet_prefix_pmask(rt, &addr4, &mask4, &scopeid);
+ rr->addr4 = ntohl(addr4.s_addr);
+ rr->mask4 = ntohl(mask4.s_addr);
+ rr->nh = rt_get_raw_nhop(rt);
+
+ return (FLM_SUCCESS);
+}
+
+/*
+ * Prefix comparison function.
+ * 10.0.0.0/24 < 10.0.0.0/25 <- less specific wins
+ * 10.0.0.0/25 < 10.0.0.1/32 <- bigger base wins
+ */
+static int
+rr_cmp(const void *_rec1, const void *_rec2)
+{
+ const struct bsearch4_record *rec1, *rec2;
+ rec1 = _rec1;
+ rec2 = _rec2;
+
+ if (rec1->addr4 < rec2->addr4)
+ return (-1);
+ else if (rec1->addr4 > rec2->addr4)
+ return (1);
+
+ /*
+ * wider mask value is lesser mask
+ * we want less specific come first, e.g. <
+ */
+ if (rec1->mask4 < rec2->mask4)
+ return (-1);
+ else if (rec1->mask4 > rec2->mask4)
+ return (1);
+ return (0);
+}
+
+struct bsearch4_array {
+ uint32_t alloc_items;
+ uint32_t num_items;
+ struct bsearch4_record *arr;
+};
+
+static bool
+add_array_entry(struct bsearch4_array *ba, struct bsearch4_record *br_new)
+{
+
+ if (ba->num_items < ba->alloc_items) {
+ ba->arr[ba->num_items++] = *br_new;
+ return (true);
+ }
+ return (false);
+}
+
+static struct bsearch4_record *
+get_last_entry(struct bsearch4_array *ba)
+{
+
+ return (&ba->arr[ba->num_items - 1]);
+}
+
+/*
+ *
+ * Example:
+ * stack: 10.0.1.0/24,nh=3 array: 10.0.1.0/25,nh=4 -> ++10.0.1.128/24,nh=3
+ *
+ *
+ */
+static bool
+pop_stack_entry(struct bsearch4_array *dst_array, struct bsearch4_array *stack)
+{
+ uint32_t last_stack_addr, last_array_addr;
+
+ struct bsearch4_record *br_prev = get_last_entry(dst_array);
+ struct bsearch4_record *pstack = get_last_entry(stack);
+
+ /* Regardless of the result, pop stack entry */
+ stack->num_items--;
+
+ /* Prefix last address for the last entry in lookup array */
+ last_array_addr = (br_prev->addr4 | ~br_prev->mask4);
+ /* Prefix last address for the stack record entry */
+ last_stack_addr = (pstack->addr4 | ~pstack->mask4);
+
+ if (last_stack_addr > last_array_addr) {
+ /*
+ * Stack record covers > address space than
+ * the last entry in the lookup array.
+ * Add the remaining parts of a stack record to
+ * the lookup array.
+ */
+ struct bsearch4_record br_new = {
+ .addr4 = last_array_addr + 1,
+ .mask4 = pstack->mask4,
+ .nh = pstack->nh,
+ };
+ return (add_array_entry(dst_array, &br_new));
+ }
+
+ return (true);
+}
+
+/*
+ * Updates resulting array @dst_array with a rib entry @rib_entry.
+ */
+static bool
+bsearch4_process_record(struct bsearch4_array *dst_array,
+ struct bsearch4_array *stack, struct bsearch4_record *rib_entry)
+{
+
+ /*
+ * Maintain invariant: current rib_entry is always contained
+ * in the top stack entry.
+ * Note we always have 0.0.0.0/0.
+ */
+ while (stack->num_items > 0) {
+ struct bsearch4_record *pst = get_last_entry(stack);
+
+ /*
+ * Check if we need to pop stack.
+ * Rely on the ordering - larger prefixes comes up first
+ * Pop any entry that doesn't contain current prefix.
+ */
+ if (pst->addr4 == (rib_entry->addr4 & pst->mask4))
+ break;
+
+ if (!pop_stack_entry(dst_array, stack))
+ return (false);
+ }
+
+ if (dst_array->num_items > 0) {
+
+ /*
+ * Check if there is a gap between previous entry and a
+ * current entry. Code above guarantees that both previous
+ * and current entry are contained in the top stack entry.
+ *
+ * Example: last: 10.0.0.1(/32,nh=3) cur: 10.0.0.3(/32,nh=4),
+ * stack: 10.0.0.0/24,nh=2.
+ * Cover a gap between previous and current by adding stack
+ * nexthop.
+ */
+ struct bsearch4_record *br_tmp = get_last_entry(dst_array);
+ uint32_t last_declared_addr = br_tmp->addr4 | ~br_tmp->mask4;
+ if (last_declared_addr < rib_entry->addr4 - 1) {
+ /* Cover a hole */
+ struct bsearch4_record *pst = get_last_entry(stack);
+ struct bsearch4_record new_entry = {
+ .addr4 = last_declared_addr + 1,
+ .mask4 = pst->mask4,
+ .nh = pst->nh,
+ };
+ if (!add_array_entry(dst_array, &new_entry))
+ return (false);
+ }
+ }
+
+ if (!add_array_entry(dst_array, rib_entry))
+ return (false);
+ add_array_entry(stack, rib_entry);
+
+ return (true);
+}
+
+static enum flm_op_result
+bsearch4_build_array(struct bsearch4_array *dst_array, struct bsearch4_array *src_array)
+{
+
+ /*
+ * During iteration, we keep track of all prefixes in rtable
+ * we currently match, by maintaining stack. As there can be only
+ * 32 prefixes for a single address, pre-allocate stack of size 32.
+ */
+ struct bsearch4_array stack = {
+ .alloc_items = 32,
+ .arr = mallocarray(32, sizeof(struct bsearch4_record), M_TEMP, M_NOWAIT | M_ZERO),
+ };
+ if (stack.arr == NULL)
+ return (FLM_REBUILD);
+
+ for (int i = 0; i < src_array->num_items; i++) {
+ struct bsearch4_record *rib_entry = &src_array->arr[i];
+
+ if (!bsearch4_process_record(dst_array, &stack, rib_entry)) {
+ free(stack.arr, M_TEMP);
+ return (FLM_REBUILD);
+ }
+ }
+
+ /*
+ * We know that last record is contained in the top stack entry.
+ */
+ while (stack.num_items > 0) {
+ if (!pop_stack_entry(dst_array, &stack))
+ return (FLM_REBUILD);
+ }
+ free(stack.arr, M_TEMP);
+
+ return (FLM_SUCCESS);
+}
+
+static enum flm_op_result
+bsearch4_build(struct bsearch4_data *bd)
+{
+ enum flm_op_result ret;
+
+ struct bsearch4_array prefixes_array = {
+ .alloc_items = bd->alloc_items,
+ .num_items = bd->num_items,
+ .arr = bd->rr,
+ };
+
+ /* Add default route if not exists */
+ bool default_found = false;
+ for (int i = 0; i < prefixes_array.num_items; i++) {
+ if (prefixes_array.arr[i].mask4 == 0) {
+ default_found = true;
+ break;
+ }
+ }
+ if (!default_found) {
+ /* Add default route with NULL nhop */
+ struct bsearch4_record default_entry = {};
+ if (!add_array_entry(&prefixes_array, &default_entry))
+ return (FLM_REBUILD);
+ }
+
+ /* Sort prefixes */
+ qsort(prefixes_array.arr, prefixes_array.num_items, sizeof(struct bsearch4_record), rr_cmp);
+
+ struct bsearch4_array dst_array = {
+ .alloc_items = bd->alloc_items,
+ .arr = bd->br,
+ };
+
+ ret = bsearch4_build_array(&dst_array, &prefixes_array);
+ bd->num_items = dst_array.num_items;
+
+ free(bd->rr, M_TEMP);
+ bd->rr = NULL;
+ return (ret);
+}
+
+
+static enum flm_op_result
+bsearch4_end_dump(void *_data, struct fib_dp *dp)
+{
+ struct bsearch4_data *bd = (struct bsearch4_data *)_data;
+ enum flm_op_result ret;
+
+ ret = bsearch4_build(bd);
+ if (ret == FLM_SUCCESS) {
+ dp->f = bsearch4_lookup;
+ dp->arg = bd;
+ }
+
+ return (ret);
+}
+
+static enum flm_op_result
+bsearch4_change_cb(struct rib_head *rnh, struct rib_cmd_info *rc,
+ void *_data)
+{
+
+ return (FLM_REBUILD);
+}
+
+struct fib_lookup_module flm_bsearch4= {
+ .flm_name = "bsearch4",
+ .flm_family = AF_INET,
+ .flm_init_cb = bsearch4_init,
+ .flm_destroy_cb = bsearch4_destroy,
+ .flm_dump_rib_item_cb = bsearch4_add_route_cb,
+ .flm_dump_end_cb = bsearch4_end_dump,
+ .flm_change_rib_item_cb = bsearch4_change_cb,
+ .flm_get_pref = bsearch4_get_pref,
+};
+
+/*
+ * Lockless radix lookup algo.
+ *
+ * Compiles immutable radix from the current routing table.
+ * Used with small amount of routes (<1000).
+ * As datastructure is immutable, it gets rebuild on each rtable change.
+ *
+ * Lookups are slightly faster as shorter lookup keys are used
+ * (4 bytes instead of 8 in stock radix).
+ */
+
+#define KEY_LEN_INET (offsetof(struct sockaddr_in, sin_addr) + sizeof(in_addr_t))
+#define OFF_LEN_INET (8 * offsetof(struct sockaddr_in, sin_addr))
+struct radix4_addr_entry {
+ struct radix_node rn[2];
+ struct sockaddr_in addr;
+ struct nhop_object *nhop;
+};
+#define LRADIX4_ITEM_SZ roundup2(sizeof(struct radix4_addr_entry), 64)
+
+struct lradix4_data {
+ struct radix_node_head *rnh;
+ struct fib_data *fd;
+ void *mem;
+ char *rt_base;
+ uint32_t alloc_items;
+ uint32_t num_items;
+};
+
+static struct nhop_object *
+lradix4_lookup(void *algo_data, const struct flm_lookup_key key, uint32_t scopeid)
+{
+ struct radix_node_head *rnh = (struct radix_node_head *)algo_data;
+ struct radix4_addr_entry *ent;
+ struct sockaddr_in addr4 = {
+ .sin_len = KEY_LEN_INET,
+ .sin_addr = key.addr4,
+ };
+ ent = (struct radix4_addr_entry *)(rnh->rnh_matchaddr(&addr4, &rnh->rh));
+ if (ent != NULL)
+ return (ent->nhop);
+ return (NULL);
+}
+
+/*
+ * Preference function.
+ * Assume close-to-ideal of < 10 routes (though worse than bsearch), then
+ * gradually degrade until 1000 routes are reached.
+ */
+static uint8_t
+lradix4_get_pref(const struct rib_rtable_info *rinfo)
+{
+
+ if (rinfo->num_prefixes < 10)
+ return (250);
+ else if (rinfo->num_prefixes < 1000)
+ return (254 - rinfo->num_prefixes / 4);
+ else
+ return (1);
+}
+
+static enum flm_op_result
+lradix4_init(uint32_t fibnum, struct fib_data *fd, void *_old_data, void **_data)
+{
+ struct lradix4_data *lr;
+ struct rib_rtable_info rinfo;
+ uint32_t count;
+ size_t sz;
+
+ lr = malloc(sizeof(struct lradix4_data), M_RTABLE, M_NOWAIT | M_ZERO);
+ if (lr == NULL || !rn_inithead((void **)&lr->rnh, OFF_LEN_INET))
+ return (FLM_REBUILD);
+ fib_get_rtable_info(fib_get_rh(fd), &rinfo);
+
+ count = rinfo.num_prefixes * 11 / 10;
+ sz = count * LRADIX4_ITEM_SZ + CACHE_LINE_SIZE;
+ lr->mem = malloc(sz, M_RTABLE, M_NOWAIT | M_ZERO);
+ if (lr->mem == NULL)
+ return (FLM_REBUILD);
+ /* Align all rtentries to a cacheline boundary */
+ lr->rt_base = (char *)roundup2((uintptr_t)lr->mem, CACHE_LINE_SIZE);
+ lr->alloc_items = count;
+ lr->fd = fd;
+
+ *_data = lr;
+
+ return (FLM_SUCCESS);
+}
+
+static void
+lradix4_destroy(void *_data)
+{
+ struct lradix4_data *lr = (struct lradix4_data *)_data;
+
+ if (lr->rnh != NULL)
+ rn_detachhead((void **)&lr->rnh);
+ if (lr->mem != NULL)
+ free(lr->mem, M_RTABLE);
+ free(lr, M_RTABLE);
+}
+
+static enum flm_op_result
+lradix4_add_route_cb(struct rtentry *rt, void *_data)
+{
+ struct lradix4_data *lr = (struct lradix4_data *)_data;
+ struct radix4_addr_entry *ae;
+ struct sockaddr_in mask;
+ struct sockaddr *rt_mask = NULL;
+ struct radix_node *rn;
+ struct in_addr addr4, mask4;
+ uint32_t scopeid;
+
+ if (lr->num_items >= lr->alloc_items)
+ return (FLM_REBUILD);
+
+ ae = (struct radix4_addr_entry *)(lr->rt_base + lr->num_items * LRADIX4_ITEM_SZ);
+ lr->num_items++;
+
+ ae->nhop = rt_get_raw_nhop(rt);
+
+ rt_get_inet_prefix_pmask(rt, &addr4, &mask4, &scopeid);
+ ae->addr.sin_len = KEY_LEN_INET;
+ ae->addr.sin_addr = addr4;
+
+ if (mask4.s_addr != INADDR_ANY) {
+ bzero(&mask, sizeof(mask));
+ mask.sin_len = KEY_LEN_INET;
+ mask.sin_addr = mask4;
+ rt_mask = (struct sockaddr *)&mask;
+ }
+
+ rn = lr->rnh->rnh_addaddr((struct sockaddr *)&ae->addr, rt_mask,
+ &lr->rnh->rh, ae->rn);
+ if (rn == NULL)
+ return (FLM_REBUILD);
+
+ return (FLM_SUCCESS);
+}
+
+static enum flm_op_result
+lradix4_end_dump(void *_data, struct fib_dp *dp)
+{
+ struct lradix4_data *lr = (struct lradix4_data *)_data;
+
+ dp->f = lradix4_lookup;
+ dp->arg = lr->rnh;
+
+ return (FLM_SUCCESS);
+}
+
+static enum flm_op_result
+lradix4_change_cb(struct rib_head *rnh, struct rib_cmd_info *rc,
+ void *_data)
+{
+
+ return (FLM_REBUILD);
+}
+
+struct fib_lookup_module flm_radix4_lockless = {
+ .flm_name = "radix4_lockless",
+ .flm_family = AF_INET,
+ .flm_init_cb = lradix4_init,
+ .flm_destroy_cb = lradix4_destroy,
+ .flm_dump_rib_item_cb = lradix4_add_route_cb,
+ .flm_dump_end_cb = lradix4_end_dump,
+ .flm_change_rib_item_cb = lradix4_change_cb,
+ .flm_get_pref = lradix4_get_pref,
+};
+
+/*
+ * Fallback lookup algorithm.
+ * This is a simple wrapper around system radix.
+ */
+
+struct radix4_data {
+ struct fib_data *fd;
+ struct rib_head *rh;
+};
+
+static struct nhop_object *
+radix4_lookup(void *algo_data, const struct flm_lookup_key key, uint32_t scopeid)
+{
+ RIB_RLOCK_TRACKER;
+ struct rib_head *rh = (struct rib_head *)algo_data;
+ struct radix_node *rn;
+ struct nhop_object *nh;
+
+ /* Prepare lookup key */
+ struct sockaddr_in sin4 = {
+ .sin_family = AF_INET,
+ .sin_len = sizeof(struct sockaddr_in),
+ .sin_addr = key.addr4,
+ };
+
+ nh = NULL;
+ RIB_RLOCK(rh);
+ rn = rh->rnh_matchaddr((void *)&sin4, &rh->head);
+ if (rn != NULL && ((rn->rn_flags & RNF_ROOT) == 0))
+ nh = (RNTORT(rn))->rt_nhop;
+ RIB_RUNLOCK(rh);
+
+ return (nh);
+}
+
+static uint8_t
+radix4_get_pref(const struct rib_rtable_info *rinfo)
+{
+
+ return (50);
+}
+
+static enum flm_op_result
+radix4_init(uint32_t fibnum, struct fib_data *fd, void *_old_data, void **_data)
+{
+ struct radix4_data *r4;
+
+ r4 = malloc(sizeof(struct radix4_data), M_RTABLE, M_NOWAIT | M_ZERO);
+ if (r4 == NULL)
+ return (FLM_REBUILD);
+ r4->fd = fd;
+ r4->rh = fib_get_rh(fd);
+
+ *_data = r4;
+
+ return (FLM_SUCCESS);
+}
+
+static void
+radix4_destroy(void *_data)
+{
+
+ free(_data, M_RTABLE);
+}
+
+static enum flm_op_result
+radix4_add_route_cb(struct rtentry *rt, void *_data)
+{
+
+ return (FLM_SUCCESS);
+}
+
+static enum flm_op_result
+radix4_end_dump(void *_data, struct fib_dp *dp)
+{
+ struct radix4_data *r4 = (struct radix4_data *)_data;
+
+ dp->f = radix4_lookup;
+ dp->arg = r4->rh;
+
+ return (FLM_SUCCESS);
+}
+
+static enum flm_op_result
+radix4_change_cb(struct rib_head *rnh, struct rib_cmd_info *rc,
+ void *_data)
+{
+
+ return (FLM_SUCCESS);
+}
+
+struct fib_lookup_module flm_radix4 = {
+ .flm_name = "radix4",
+ .flm_family = AF_INET,
+ .flm_init_cb = radix4_init,
+ .flm_destroy_cb = radix4_destroy,
+ .flm_dump_rib_item_cb = radix4_add_route_cb,
+ .flm_dump_end_cb = radix4_end_dump,
+ .flm_change_rib_item_cb = radix4_change_cb,
+ .flm_get_pref = radix4_get_pref,
+};
+
+static void
+fib4_algo_init(void)
+{
+
+ fib_module_register(&flm_bsearch4);
+ fib_module_register(&flm_radix4_lockless);
+ fib_module_register(&flm_radix4);
+}
+SYSINIT(fib4_algo_init, SI_SUB_PROTO_DOMAIN, SI_ORDER_THIRD, fib4_algo_init, NULL);