Index: sys/conf/files =================================================================== --- sys/conf/files +++ sys/conf/files @@ -4175,6 +4175,7 @@ net/route/nhop.c standard net/route/nhop_ctl.c standard net/route/nhop_utils.c standard +net/route/route_algo.c optional route_algo net/route/route_ctl.c standard net/route/route_ddb.c optional ddb net/route/route_helpers.c standard @@ -4325,6 +4326,7 @@ netinet/in_kdtrace.c optional inet | inet6 netinet/ip_carp.c optional inet carp | inet6 carp netinet/in_fib.c optional inet +netinet/in_fib_algo.c optional inet route_algo netinet/in_gif.c optional gif inet | netgraph_gif inet netinet/ip_gre.c optional gre inet netinet/ip_id.c optional inet @@ -4401,6 +4403,7 @@ netinet6/in6.c optional inet6 netinet6/in6_cksum.c optional inet6 netinet6/in6_fib.c optional inet6 +netinet6/in6_fib_algo.c optional inet6 route_algo netinet6/in6_gif.c optional gif inet6 | netgraph_gif inet6 netinet6/in6_ifattach.c optional inet6 netinet6/in6_jail.c optional inet6 Index: sys/conf/options =================================================================== --- sys/conf/options +++ sys/conf/options @@ -453,6 +453,7 @@ PCBGROUP opt_pcbgroup.h PF_DEFAULT_TO_DROP opt_pf.h ROUTE_MPATH opt_route.h +ROUTE_ALGO opt_route.h ROUTETABLES opt_route.h RSS opt_rss.h SLIP_IFF_OPTS opt_slip.h Index: sys/net/route.h =================================================================== --- sys/net/route.h +++ sys/net/route.h @@ -453,6 +453,8 @@ /* New API */ struct nhop_object *rib_lookup(uint32_t fibnum, const struct sockaddr *dst, uint32_t flags, uint32_t flowid); +struct rib_rtable_info; +bool rib_get_rtable_info(uint32_t fibnum, int family, struct rib_rtable_info *info); #endif #endif Index: sys/net/route.c =================================================================== --- sys/net/route.c +++ sys/net/route.c @@ -151,6 +151,12 @@ rt_table_destroy(struct rib_head *rh) { + RIB_WLOCK(rh); + rh->rib_dying = true; + RIB_WUNLOCK(rh); + + fib_destroy_rib(rh); + tmproutes_destroy(rh); rn_walktree(&rh->rmhead.head, rt_freeentry, &rh->rmhead.head); Index: sys/net/route/route_algo.h =================================================================== --- /dev/null +++ sys/net/route/route_algo.h @@ -0,0 +1,111 @@ +/*- + * 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. + * 3. Neither the name of the University nor the names of its contributors + * may be used to endorse or promote products derived from this software + * without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE REGENTS 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 REGENTS 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. + * + * $FreeBSD$ + */ + + +struct fib_data; +struct fib_dp; +enum flm_op_result { + FLM_SUCCESS, /* No errors, operation successful */ + FLM_REBUILD, /* Operation cannot be completed, schedule algorithm rebuild */ + FLM_ERROR, /* Operation failed, this algo cannot be used */ +}; + +struct rib_rtable_info { + uint32_t num_prefixes; + uint32_t num_nhops; + uint32_t num_nhgrp; +}; + +struct flm_lookup_key { + union { + const struct in6_addr *addr6; + struct in_addr addr4; + }; +}; + +typedef struct nhop_object *flm_lookup_t(void *algo_data, + const struct flm_lookup_key key, uint32_t scopeid); +typedef enum flm_op_result flm_init_t (uint32_t fibnum, struct fib_data *fd, + void *_old_data, void **new_data); +typedef void flm_destroy_t(void *data); +typedef enum flm_op_result flm_dump_t(struct rtentry *rt, void *data); +typedef enum flm_op_result flm_dump_end_t(void *data, struct fib_dp *dp); +typedef enum flm_op_result flm_change_t(struct rib_head *rnh, + struct rib_cmd_info *rc, void *data); +typedef uint8_t flm_get_pref_t(const struct rib_rtable_info *rinfo); + +#define FIB_M_NEED_NHOPS 0x01 /* need nexthop index map allocation */ +#define FIB_M_NO_CALLOUT 0x02 /* does not need callouts */ + +struct fib_lookup_module { + char *flm_name; /* algo name */ + int flm_family; /* address family this module supports */ + int flm_refcount; /* # of references */ + uint32_t flm_flags; /* flags */ + uint8_t flm_index; /* internal algo index */ + flm_init_t *flm_init_cb; /* instance init */ + flm_destroy_t *flm_destroy_cb; /* destroy instance */ + flm_change_t *flm_change_rib_item_cb;/* routing table change hook */ + flm_dump_t *flm_dump_rib_item_cb; /* routing table dump cb */ + flm_dump_end_t *flm_dump_end_cb; /* end of dump */ + flm_lookup_t *flm_lookup; /* lookup function */ + flm_get_pref_t *flm_get_pref; /* get algo preference */ + TAILQ_ENTRY(fib_lookup_module) entries; +}; + +/* Datapath lookup data */ +struct fib_dp { + flm_lookup_t *f; + void *arg; +}; + +VNET_DECLARE(struct fib_dp *, inet_dp); +#define V_inet_dp VNET(inet_dp) +VNET_DECLARE(struct fib_dp *, inet6_dp); +#define V_inet6_dp VNET(inet6_dp) + +int fib_module_init(struct fib_lookup_module *flm, uint32_t fibnum, + int family); +int fib_module_clone(const struct fib_lookup_module *flm_orig, + struct fib_lookup_module *flm, bool waitok); +int fib_module_dumptree(struct fib_lookup_module *flm, + enum rib_subscription_type subscription_type); +int fib_module_register(struct fib_lookup_module *flm); +int fib_module_unregister(struct fib_lookup_module *flm); + +uint32_t fib_get_nhop_idx(struct fib_data *fd, struct nhop_object *nh); +void fib_free_nhop_idx(struct fib_data *fd, uint32_t idx); +void fib_free_nhop(struct fib_data *fd, struct nhop_object *nh); +struct nhop_object **fib_get_nhop_array(struct fib_data *fd); +void fib_get_rtable_info(struct rib_head *rh, struct rib_rtable_info *rinfo); +struct rib_head *fib_get_rh(struct fib_data *fd); + + Index: sys/net/route/route_algo.c =================================================================== --- /dev/null +++ sys/net/route/route_algo.c @@ -0,0 +1,1215 @@ +/*- + * 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. + */ +#define RTDEBUG + +#include +__FBSDID("$FreeBSD$"); +#include "opt_inet.h" +#include "opt_inet6.h" +#include "opt_route.h" + +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include + +#include +#include + +#include +#include +#include +#include +#ifdef INET6 +#include +#include +#endif + +#include +#include +#include +#include +#include + +/* + * Route lookup framework. + * + * flm - fib lookup modules - kernel modules implementing particular algo + * fd - fib data - instance of an flm bound to specific routing table + * + * + * For each supported address family, there is a an allocated array of fib_dp + * structures, indexed by fib number. Each array entry contains callback function + * and its argument. This function will be called with a family-specific lookup key, + * scope and provided argument. This array gets re-created every time when new algo + * instance gets created. Please take a look at the replace_rtables_family() function + * for more details. + * + * Control plane for to setup and update the necessary dataplane structures. + * 1) nexhops abstraction -> module has to deal with index, refcounting, nexhtop groups etc + * 2) sync with route tables + * 3) dataplane attachment points + * 3) fail early. Some algorithms are immutable, so any change leads to rebuild. Some + * are mutable till some extent so the module is build over common setup/teardown + * instances, making error handling * easier. + * 4) preference. + * + */ + +SYSCTL_DECL(_net_route); +SYSCTL_NODE(_net_route, OID_AUTO, algo, CTLFLAG_RW | CTLFLAG_MPSAFE, 0, + "Route algorithm lookups"); + +#ifdef INET6 +SYSCTL_NODE(_net_route_algo, OID_AUTO, inet6, CTLFLAG_RW | CTLFLAG_MPSAFE, 0, + "IPv6 algorithm lookups"); +#endif +#ifdef INET +SYSCTL_NODE(_net_route_algo, OID_AUTO, inet, CTLFLAG_RW | CTLFLAG_MPSAFE, 0, + "IPv4 algorithm lookups"); +#endif + +struct nhop_ref_table { + uint32_t count; + int32_t refcnt[0]; +}; + +struct fib_data { + uint32_t number_nhops; /* current # of nhops */ + uint32_t number_records; /* current # of routes */ + uint8_t hit_nhops; /* true if out of nhop limit */ + uint8_t init_done; /* true if init is competed */ + uint32_t fd_dead:1; /* Scheduled for deletion */ + uint32_t fd_linked:1; /* true if linked */ + uint32_t fd_need_rebuild:1; /* true if rebuild scheduled */ + uint32_t fd_force_eval:1;/* true if rebuild scheduled */ + uint8_t fd_family; /* family */ + uint32_t fd_fibnum; /* fibnum */ + uint32_t fd_failed_rebuilds; /* stat: failed rebuilds */ + struct callout fd_callout; /* rebuild callout */ + void *fd_algo_data; /* algorithm data */ + struct nhop_object **nh_idx; /* nhop idx->ptr array */ + struct nhop_ref_table *nh_ref_table; /* array with # of nhop references */ + struct rib_head *fd_rh; /* RIB table we're attached to */ + struct rib_subscription *fd_rs; /* storing table subscription */ + struct fib_algo_calldata *fa; + struct fib_dp fd_dp; /* fib datapath data */ + struct vnet *fd_vnet; /* vnet nhop belongs to */ + struct epoch_context fd_epoch_ctx; + uint64_t gencnt; + struct fib_lookup_module *fd_flm; + uint32_t fd_num_changes; /* number of changes since last callout */ + TAILQ_ENTRY(fib_data) entries; /* list of all fds in vnet */ +}; + +static void rebuild_callout(void *_data); +static void destroy_instance_epoch(epoch_context_t ctx); +static enum flm_op_result switch_algo(struct fib_data *fd); +static struct fib_lookup_module *find_algo(const char *algo_name, int family); + +static struct fib_lookup_module *fib_check_best_algo(struct rib_head *rh, + struct fib_lookup_module *orig_flm); + +struct mtx fib_mtx; +#define MOD_LOCK() mtx_lock(&fib_mtx) +#define MOD_UNLOCK() mtx_unlock(&fib_mtx) + +uint32_t algo_bitmask_idx = 0; + + +/* Algorithm has to be this percent better than the current to switch */ +#define BEST_DIFF_PERCENT (5 * 256 / 100) +/* Schedule algo re-evaluation X seconds after a change */ +#define ALGO_EVAL_DELAY_MS 30000 +/* Force algo re-evaluation after X changes */ +#define ALGO_EVAL_NUM_ROUTES 100 +/* Try to setup algorithm X times */ +#define FIB_MAX_TRIES 32 +/* Max amount of supported nexthops */ +#define FIB_MAX_NHOPS 262144 +#define FIB_CALLOUT_DELAY_MS 50 + + +/* TODO: per-VNET */ +static TAILQ_HEAD(fib_data_head, fib_data) fib_data_list = TAILQ_HEAD_INITIALIZER(fib_data_list); + +struct fib_dp_header { + struct epoch_context ffi_epoch_ctx; + uint32_t ffi_num_tables; + struct fib_dp ffi_idx[0]; +}; + +static TAILQ_HEAD(, fib_lookup_module) all_algo_list; + +#ifdef RTDEBUG +#define RH_PRINTF(_rh, _fmt, ...) printf("[rt_algo] %s.%u %s: " _fmt "\n", \ + print_family(_rh->rib_family), _rh->rib_fibnum, __func__ , ## __VA_ARGS__) +#define RH_PRINTF_RAW(_fmt, ...) printf("[rt_algo] %s: " _fmt "\n", __func__ , ## __VA_ARGS__) +#define FD_PRINTF(fd, _fmt, ...) printf("[rt_algo] %s.%u (%s) %s: " _fmt "\n",\ + print_family(fd->fd_family), fd->fd_fibnum, fd->fd_flm->flm_name, __func__, \ + ##__VA_ARGS__) +#else +#define FD_RH_PRINTF(fd, _fmt, ...) +#define RH_PRINTF(_fmt, ...) +#define RH_PRINTF_RAW(_fmt, ...) +#endif + +static const char * +print_family(int family) +{ + if (family == AF_INET) + return ("inet"); + else if (family == AF_INET6) + return ("inet6"); + else + return ("unknown"); +} + +static int +print_algos(struct sysctl_req *req, int family) +{ + struct fib_lookup_module *flm; + struct sbuf sbuf; + int error, count = 0; + + error = sysctl_wire_old_buffer(req, 0); + if (error == 0) { + sbuf_new_for_sysctl(&sbuf, NULL, 128, req); + TAILQ_FOREACH(flm, &all_algo_list, entries) { + if (flm->flm_family == family) { + if (count++ > 0) + sbuf_cat(&sbuf, ", "); + sbuf_cat(&sbuf, flm->flm_name); + } + } + error = sbuf_finish(&sbuf); + sbuf_delete(&sbuf); + } + return (error); +} + +static int +print_algos_inet6(SYSCTL_HANDLER_ARGS) +{ + + return (print_algos(req, AF_INET6)); +} +SYSCTL_PROC(_net_route_algo_inet6, OID_AUTO, algo_list, + CTLTYPE_STRING | CTLFLAG_RD | CTLFLAG_MPSAFE, NULL, 0, + print_algos_inet6, "A", "List of algos"); + +static int +print_algos_inet(SYSCTL_HANDLER_ARGS) +{ + + return (print_algos(req, AF_INET)); +} +SYSCTL_PROC(_net_route_algo_inet, OID_AUTO, algo_list, + CTLTYPE_STRING | CTLFLAG_RD | CTLFLAG_MPSAFE, NULL, 0, + print_algos_inet, "A", "List of algos"); + + +static struct fib_lookup_module * +find_algo(const char *algo_name, int family) +{ + struct fib_lookup_module *flm; + + TAILQ_FOREACH(flm, &all_algo_list, entries) { + if ((strcmp(flm->flm_name, algo_name) == 0) && + (family == flm->flm_family)) + return (flm); + } + + return (NULL); +} + +static uint32_t +callout_calc_delay(struct fib_data *fd) +{ + uint32_t shift; + + if (fd->fd_failed_rebuilds > 10) + shift = 10; + else + shift = fd->fd_failed_rebuilds; + + return ((1 << shift) * FIB_CALLOUT_DELAY_MS); +} + +static void +schedule_callout(struct fib_data *fd, int delay_ms) +{ + + callout_reset_sbt(&fd->fd_callout, 0, SBT_1MS * delay_ms, + rebuild_callout, fd, 0); +} + +static void +schedule_algo_eval(struct fib_data *fd) +{ + + if (fd->fd_num_changes++ == 0) { + /* Start callout to consider switch */ + MOD_LOCK(); + if (!callout_pending(&fd->fd_callout)) + schedule_callout(fd, ALGO_EVAL_DELAY_MS); + MOD_UNLOCK(); + } else if (fd->fd_num_changes > ALGO_EVAL_NUM_ROUTES && !fd->fd_force_eval) { + /* Reset callout to exec immediately */ + MOD_LOCK(); + if (!fd->fd_need_rebuild) { + fd->fd_force_eval = true; + schedule_callout(fd, 1); + } + MOD_UNLOCK(); + } +} + +/* + * rib subscription handler + */ +static void +handle_rtable_change_cb(struct rib_head *rnh, struct rib_cmd_info *rc, + void *_data) +{ + struct fib_data *fd = (struct fib_data *)_data; + enum flm_op_result result; + + RIB_WLOCK_ASSERT(rnh); + + if (!fd->init_done) + return; + + schedule_algo_eval(fd); + + result = fd->fd_flm->flm_change_rib_item_cb(rnh, rc, fd->fd_algo_data); + + switch (result) { + case FLM_SUCCESS: + break; + case FLM_REBUILD: + /* + * Algo reported inability to handle, + * schedule algo rebuild. + */ + MOD_LOCK(); + if (!fd->fd_need_rebuild) { + fd->fd_need_rebuild = true; + /* + * Potentially rewrites pending callout + * to re-evaluate algo. + */ + FD_PRINTF(fd, "Scheduling rebuilt"); + schedule_callout(fd, callout_calc_delay(fd)); + } + MOD_UNLOCK(); + break; + default: + /* + * Algo reported a non-recoverable error. + * Remove and switch to radix? + */ + FD_PRINTF(fd, "algo reported non-recoverable error"); + // TODO: switch to radix + } +} + +static void +estimate_scale(const struct fib_data *old_fd, struct fib_data *fd) +{ + + if (old_fd == NULL) { + fd->number_nhops = 16; + return; + } + + if (old_fd->hit_nhops && old_fd->number_nhops < FIB_MAX_NHOPS) + fd->number_nhops = 2 * old_fd->number_nhops; + else + fd->number_nhops = old_fd->number_nhops; +} + +struct walk_cbdata { + struct fib_data *fd; + flm_dump_t *func; + enum flm_op_result result; +}; + +static void +sync_algo_end_cb(struct rib_head *rnh, enum rib_walk_hook stage, void *_data) +{ + struct walk_cbdata *w = (struct walk_cbdata *)_data; + struct fib_data *fd = w->fd; + + if (rnh->rib_dying) { + w->result = FLM_ERROR; + return; + } + + if (stage != RIB_WALK_HOOK_POST || w->result != FLM_SUCCESS) + return; + + if (fd->hit_nhops) { + FD_PRINTF(fd, "ran out of nexthops at %u nhops", + fd->nh_ref_table->count); + w->result = FLM_REBUILD; + return; + } + + w->result = fd->fd_flm->flm_dump_end_cb(fd->fd_algo_data, &fd->fd_dp); + + if (w->result == FLM_SUCCESS) { + /* Mark init as done to allow routing updates */ + fd->init_done = 1; + } +} + +static int +sync_algo_cb(struct rtentry *rt, void *_data) +{ + struct walk_cbdata *w = (struct walk_cbdata *)_data; + enum flm_op_result result; + + if (w->result == FLM_SUCCESS && w->func) { + result = w->func(rt, w->fd->fd_algo_data); + if (result != FLM_SUCCESS) + w->result = result; + } + + return (0); +} + +static enum flm_op_result +sync_algo(struct fib_data *fd) +{ + struct walk_cbdata w; + + w.fd = fd; + w.func = fd->fd_flm->flm_dump_rib_item_cb; + w.result = FLM_SUCCESS; + + rib_walk_ext_internal(fd->fd_rh, true, sync_algo_cb, sync_algo_end_cb, &w); + + FD_PRINTF(fd, "initial dump completed."); + + return (w.result); +} + +/* + * Assume already unlinked from datapath + */ +static int +schedule_destroy_instance(struct fib_data *fd, bool in_callout) +{ + bool is_dead; + + NET_EPOCH_ASSERT(); + + MOD_LOCK(); + is_dead = fd->fd_dead; + if (!is_dead) + fd->fd_dead = true; + if (fd->fd_linked) { + TAILQ_REMOVE(&fib_data_list, fd, entries); + fd->fd_linked = false; + } + MOD_UNLOCK(); + if (is_dead) + return (0); + + FD_PRINTF(fd, "DETACH"); + + if (fd->fd_rs != NULL) + rib_unsibscribe(fd->fd_rs); + + /* + * After rib_unsubscribe() no _new_ handle_rtable_change_cb() calls + * will be executed, hence no _new_ callout schedules will happen. + * + * There can be 3 possible scenarious here: + * 1) we're running inside a callout when we're deleting ourselves + * due to migration to a newer fd + * 2) we're running from rt_table_destroy() and callout is scheduled + * for execution OR is executing + * + * For (2) we need to wait for the callout termination, as the routing table + * will be destroyed after this function returns. + * For (1) we cannot call drain, but can ensure that this is the last invocation. + */ + + if (in_callout) + callout_stop(&fd->fd_callout); + else + callout_drain(&fd->fd_callout); + + /* + * At this moment there are no other pending work scheduled. + */ + FD_PRINTF(fd, "destroying old instance"); + epoch_call(net_epoch_preempt, destroy_instance_epoch, + &fd->fd_epoch_ctx); + + return (0); +} + +void +fib_destroy_rib(struct rib_head *rh) +{ + struct fib_data_head tmp_head = TAILQ_HEAD_INITIALIZER(tmp_head); + struct fib_data *fd, *fd_tmp; + struct epoch_tracker et; + + /* + * Atm we have set is_dying flag on rnh, so all new fd's will + * fail at sync_algo() stage, so nothing new will be added to the list. + */ + MOD_LOCK(); + TAILQ_FOREACH_SAFE(fd, &fib_data_list, entries, fd_tmp) { + if (fd->fd_rh == rh) { + TAILQ_REMOVE(&fib_data_list, fd, entries); + fd->fd_linked = false; + TAILQ_INSERT_TAIL(&tmp_head, fd, entries); + } + } + MOD_UNLOCK(); + + /* Pass 2: remove each entry */ + NET_EPOCH_ENTER(et); + TAILQ_FOREACH_SAFE(fd, &tmp_head, entries, fd_tmp) { + schedule_destroy_instance(fd, false); + } + NET_EPOCH_EXIT(et); +} + +static void +destroy_instance(struct fib_data *fd) +{ + + FD_PRINTF(fd, "destroy fd %p", fd); + + /* Call destroy callback first */ + if (fd->fd_algo_data != NULL) + fd->fd_flm->flm_destroy_cb(fd->fd_algo_data); + + /* Nhop table */ + if (fd->nh_idx != NULL) { + for (int i = 0; i < fd->number_nhops; i++) { + if (fd->nh_idx[i] != NULL) { + //FD_PRINTF(fd, " FREE nhop %d %p", i, fd->nh_idx[i]); + nhop_free_any(fd->nh_idx[i]); + } + } + free(fd->nh_idx, M_RTABLE); + } + if (fd->nh_ref_table != NULL) + free(fd->nh_ref_table, M_RTABLE); + + MOD_LOCK(); + fd->fd_flm->flm_refcount--; + MOD_UNLOCK(); + + free(fd, M_RTABLE); +} + +/* + * Epoch callback indicating fd is safe to destroy + */ +static void +destroy_instance_epoch(epoch_context_t ctx) +{ + struct fib_data *fd; + + fd = __containerof(ctx, struct fib_data, fd_epoch_ctx); + + destroy_instance(fd); +} + +static enum flm_op_result +try_setup_instance(struct fib_lookup_module *flm, struct rib_head *rh, + struct fib_data *old_fd, struct fib_data **pfd) +{ + struct fib_data *fd; + size_t size; + enum flm_op_result result; + + /* Allocate */ + fd = malloc(sizeof(struct fib_data), M_RTABLE, M_NOWAIT | M_ZERO); + if (fd == NULL) { + *pfd = NULL; + return (FLM_REBUILD); + } + *pfd = fd; + + estimate_scale(old_fd, fd); + + fd->fd_rh = rh; + fd->fd_family = rh->rib_family; + fd->fd_fibnum = rh->rib_fibnum; + callout_init(&fd->fd_callout, 1); + fd->fd_vnet = curvnet; + fd->fd_flm = flm; + + /* Allocate nhidx -> nhop_ptr table */ + size = fd->number_nhops * sizeof(void *); + //FD_PRINTF(fd, "malloc(%lu)", size); + fd->nh_idx = malloc(size, M_RTABLE, M_NOWAIT | M_ZERO); + if (fd->nh_idx == NULL) { + FD_PRINTF(fd, "Unable to allocate nhop table idx (sz:%zu)", size); + return (FLM_REBUILD); + } + + /* Allocate nhop index refcount table */ + size = sizeof(struct nhop_ref_table); + size += fd->number_nhops * sizeof(uint32_t); + //FD_PRINTF(fd, "malloc(%lu)", size); + fd->nh_ref_table = malloc(size, M_RTABLE, M_NOWAIT | M_ZERO); + if (fd->nh_ref_table == NULL) { + FD_PRINTF(fd, "Unable to allocate nhop refcount table (sz:%zu)", size); + return (FLM_REBUILD); + } + + /* Okay, we're ready for algo init */ + void *old_algo_data = (old_fd != NULL) ? old_fd->fd_algo_data : NULL; + result = flm->flm_init_cb(fd->fd_fibnum, fd, old_algo_data, &fd->fd_algo_data); + if (result != FLM_SUCCESS) + return (result); + + /* Try to subscribe */ + if (flm->flm_change_rib_item_cb != NULL) { + fd->fd_rs = rib_subscribe_internal(fd->fd_rh, + handle_rtable_change_cb, fd, RIB_NOTIFY_IMMEDIATE, 0); + if (fd->fd_rs == NULL) + return (FLM_REBUILD); + } + + /* Dump */ + result = sync_algo(fd); + if (result != FLM_SUCCESS) + return (result); + FD_PRINTF(fd, "DUMP completed successfully."); + + MOD_LOCK(); + /* + * Insert in the beginning of a list, to simplify search + * first matching entry is the one. + */ + TAILQ_INSERT_HEAD(&fib_data_list, fd, entries); + fd->fd_linked = true; + MOD_UNLOCK(); + + return (FLM_SUCCESS); +} + +/* + * Sets up algo @flm for table @rh and links it to the datapath. + * + */ +static enum flm_op_result +setup_instance(struct fib_lookup_module *flm, struct rib_head *rh, + struct fib_data *orig_fd, struct fib_data **pfd, bool attach) +{ + struct fib_data *prev_fd, *new_fd; + struct epoch_tracker et; + enum flm_op_result result; + + prev_fd = orig_fd; + new_fd = NULL; + for (int i = 0; i < FIB_MAX_TRIES; i++) { + NET_EPOCH_ENTER(et); + result = try_setup_instance(flm, rh, prev_fd, &new_fd); + + if ((result == FLM_SUCCESS) && attach) + result = switch_algo(new_fd); + + if ((prev_fd != NULL) && (prev_fd != orig_fd)) { + schedule_destroy_instance(prev_fd, false); + prev_fd = NULL; + } + NET_EPOCH_EXIT(et); + + RH_PRINTF(rh, "try %d: fib algo result: %d", i, result); + + if (result == FLM_REBUILD) { + prev_fd = new_fd; + new_fd = NULL; + continue; + } + + break; + } + + if (result != FLM_SUCCESS) { + /* update failure count */ + MOD_LOCK(); + if (orig_fd != NULL) + orig_fd->fd_failed_rebuilds++; + MOD_UNLOCK(); + + NET_EPOCH_ENTER(et); + if ((prev_fd != NULL) && (prev_fd != orig_fd)) + schedule_destroy_instance(prev_fd, false); + if (new_fd != NULL) { + schedule_destroy_instance(new_fd, false); + new_fd = NULL; + } + NET_EPOCH_EXIT(et); + } + + *pfd = new_fd; + return (result); +} + +static void +rebuild_callout(void *_data) +{ + struct fib_data *fd, *fd_new; + struct fib_lookup_module *flm_new; + struct epoch_tracker et; + enum flm_op_result result; + bool need_rebuild = false; + + fd = (struct fib_data *)_data; + + MOD_LOCK(); + need_rebuild = fd->fd_need_rebuild; + fd->fd_need_rebuild = false; + fd->fd_force_eval = false; + fd->fd_num_changes = 0; + MOD_UNLOCK(); + + CURVNET_SET(fd->fd_vnet); + + /* First, check if we're still OK to use this algo */ + flm_new = fib_check_best_algo(fd->fd_rh, fd->fd_flm); + if ((flm_new == NULL) && (!need_rebuild)) { + /* Keep existing algo, no need to rebuild. */ + CURVNET_RESTORE(); + return; + } + + struct fib_data *fd_tmp = (flm_new == NULL) ? fd : NULL; + result = setup_instance(fd->fd_flm, fd->fd_rh, fd_tmp, &fd_new, true); + if (result != FLM_SUCCESS) { + FD_PRINTF(fd, "table rebuild failed"); + CURVNET_RESTORE(); + return; + } + FD_PRINTF(fd_new, "switched to new instance"); + + /* Remove old */ + if (fd != NULL) { + NET_EPOCH_ENTER(et); + schedule_destroy_instance(fd, true); + NET_EPOCH_EXIT(et); + } + + CURVNET_RESTORE(); +} + +static int +set_algo_sysctl_handler(SYSCTL_HANDLER_ARGS) +{ + int error = 0; +#if 0 + struct epoch_tracker et; + struct fib_lookup_module *flm; + struct fib_data *old_fd, *fd; + char old_algo_name[32], algo_name[32]; + uint32_t fibnum; + int error; + + fibnum = RT_DEFAULT_FIB; + + if (old_fd == NULL) { + strlcpy(old_algo_name, "radix", sizeof(old_algo_name)); + } else { + strlcpy(old_algo_name, fd_ptr->fd_flm->flm_name, + sizeof(old_algo_name)); + } + strlcpy(algo_name, old_algo_name, sizeof(algo_name)); + error = sysctl_handle_string(oidp, algo_name, sizeof(algo_name), req); + if (error != 0 || req->newptr == NULL) + return (error); + + if (strcmp(algo_name, old_algo_name) == 0) + return (0); + + if (strcmp(algo_name, "radix") == 0) { + /* teardown old one */ + NET_EPOCH_ENTER(et); + MOD_LOCK(); + old_fd = fd_ptr; + fd_ptr = NULL; + MOD_UNLOCK(); + + if (old_fd != NULL) + schedule_destroy_instance(old_fd); + NET_EPOCH_EXIT(et); + return (0); + } + + MOD_LOCK(); + flm = find_algo(algo_name, AF_INET6); + if (flm != NULL) + flm->flm_refcount++; + MOD_UNLOCK(); + + if (flm == NULL) { + DPRINTF("unable to find algo %s", algo_name); + return (ESRCH); + } + DPRINTF("inet6.%u: requested fib algo %s", fibnum, algo_name); + + fd = setup_instance(flm, fibnum, NULL, &error); + + if (error != 0) { + MOD_LOCK(); + flm->flm_refcount--; + MOD_UNLOCK(); + return (error); + } + + MOD_LOCK(); + old_fd = fd_ptr; + fd_ptr = fd; + MOD_UNLOCK(); + + /* Remove old */ + NET_EPOCH_ENTER(et); + if (old_fd != NULL) { + error = schedule_destroy_instance(old_fd); + } + NET_EPOCH_EXIT(et); +#endif + + /* Set new */ + + /* Drain cb so user can unload the module after userret if so desired */ + epoch_drain_callbacks(net_epoch_preempt); + + return (error); +} +SYSCTL_PROC(_net_route_algo_inet6, OID_AUTO, algo, + CTLTYPE_STRING | CTLFLAG_RW | CTLFLAG_MPSAFE, NULL, 0, + set_algo_sysctl_handler, "A", + "Set"); + +static void +destroy_fdh_epoch(epoch_context_t ctx) +{ + struct fib_dp_header *ffi; + + ffi = __containerof(ctx, struct fib_dp_header, ffi_epoch_ctx); + free(ffi, M_RTABLE); +} + +static struct fib_dp_header * +alloc_fib_dp_array(uint32_t num_tables, bool waitok) +{ + size_t sz; + struct fib_dp_header *ffi; + + sz = sizeof(struct fib_dp_header); + sz += sizeof(struct fib_dp) * num_tables; + ffi = malloc(sz, M_RTABLE, (waitok ? M_WAITOK : M_NOWAIT) | M_ZERO); + if (ffi != NULL) + ffi->ffi_num_tables = num_tables; + return (ffi); +} + +static struct fib_dp_header * +get_fib_dp_header(struct fib_dp *dp) +{ + + return (__containerof((void *)dp, struct fib_dp_header, ffi_idx)); +} + +/* + * Replace per-family index pool @pdp with a new one which + * contains updated callback/algo data from @fd. + * Returns 0 on success. + */ +static enum flm_op_result +replace_rtables_family(struct fib_dp **pdp, struct fib_data *fd) +{ + struct fib_dp_header *new_ffi, *old_ffi; + + NET_EPOCH_ASSERT(); + + //FD_PRINTF(fd, "[vnet %p] replace with f:%p arg:%p", curvnet, fd->fd_dp.f, fd->fd_dp.arg); + + MOD_LOCK(); + old_ffi = get_fib_dp_header(*pdp); + new_ffi = alloc_fib_dp_array(old_ffi->ffi_num_tables, false); + //FD_PRINTF(fd, "OLD FFI: %p NEW FFI: %p", old_ffi, new_ffi); + if (new_ffi == NULL) { + MOD_UNLOCK(); + FD_PRINTF(fd, "error attaching datapath"); + return (FLM_REBUILD); + } + + memcpy(&new_ffi->ffi_idx[0], &old_ffi->ffi_idx[0], + old_ffi->ffi_num_tables * sizeof(struct fib_dp)); + /* Update relevant data structure for @fd */ + new_ffi->ffi_idx[fd->fd_fibnum] = fd->fd_dp; + + /* Ensure memcpy() writes have completed */ + atomic_thread_fence_rel(); + /* Set new datapath pointer */ + *pdp = &new_ffi->ffi_idx[0]; + MOD_UNLOCK(); + //FD_PRINTF(fd, "update %p -> %p", old_ffi, new_ffi); + + epoch_call(net_epoch_preempt, destroy_fdh_epoch, + &old_ffi->ffi_epoch_ctx); + + return (FLM_SUCCESS); +} + +static struct fib_dp ** +get_family_ptr(int family) +{ + switch (family) { + case AF_INET: + return (&V_inet_dp); + case AF_INET6: + return (&V_inet6_dp); + } + return (NULL); +} + +static enum flm_op_result +switch_algo(struct fib_data *fd) +{ + struct fib_dp **pdp; + + pdp = get_family_ptr(fd->fd_family); + return (replace_rtables_family(pdp, fd)); +} + +/* + * Grow datapath pointers array. + * Called from sysctl handler on growing number of routing tables. + */ +static void +grow_rtables_family(struct fib_dp **pdp, uint32_t new_num_tables) +{ + struct fib_dp_header *new_fdh, *old_fdh = NULL; + + new_fdh = alloc_fib_dp_array(new_num_tables, true); + + MOD_LOCK(); + if (*pdp != NULL) { + old_fdh = get_fib_dp_header(*pdp); + memcpy(&new_fdh->ffi_idx[0], &old_fdh->ffi_idx[0], + old_fdh->ffi_num_tables * sizeof(struct fib_dp)); + } + + /* Wait till all writes completed */ + atomic_thread_fence_rel(); + + *pdp = &new_fdh->ffi_idx[0]; + MOD_UNLOCK(); + + if (old_fdh != NULL) + epoch_call(net_epoch_preempt, destroy_fdh_epoch, + &old_fdh->ffi_epoch_ctx); +} + +/* + * Grows per-AF arrays of datapath pointers for each supported family. + * Called from fibs resize sysctl handler. + */ +void +fib_grow_rtables(uint32_t new_num_tables) +{ + + grow_rtables_family(get_family_ptr(AF_INET), new_num_tables); + grow_rtables_family(get_family_ptr(AF_INET6), new_num_tables); +} + +void +fib_get_rtable_info(struct rib_head *rh, struct rib_rtable_info *rinfo) +{ + + bzero(rinfo, sizeof(struct rib_rtable_info)); + rinfo->num_prefixes = rh->rnh_prefixes; + rinfo->num_nhops = nhops_get_count(rh); +#ifdef ROUTE_MPATH + rinfo->num_nhgrp = nhgrp_get_count(rh); +#endif +} + +struct rib_head * +fib_get_rh(struct fib_data *fd) +{ + + return (fd->fd_rh); +} + +static uint32_t +get_nhop_idx(struct nhop_object *nh) +{ +#ifdef ROUTE_MPATH + if (NH_IS_NHGRP(nh)) + return (nhgrp_get_idx((struct nhgrp_object *)nh) * 2 - 1); + else + return (nhop_get_idx(nh) * 2); +#else + return (nhop_get_idx(nh)); +#endif +} + + +uint32_t +fib_get_nhop_idx(struct fib_data *fd, struct nhop_object *nh) +{ + uint32_t idx = get_nhop_idx(nh); + + if (idx >= fd->number_nhops) { + fd->hit_nhops = 1; + return (0); + } + + if (fd->nh_idx[idx] == NULL) { + nhop_ref_any(nh); + fd->nh_idx[idx] = nh; + fd->nh_ref_table->count++; + //FD_PRINTF(fd, " REF nhop %u %p", idx, fd->nh_idx[idx]); + } + fd->nh_ref_table->refcnt[idx]++; + + return (idx); +} + +struct nhop_release_data { + struct nhop_object *nh; + struct epoch_context ctx; +}; + +static void +release_nhop_epoch(epoch_context_t ctx) +{ + struct nhop_release_data *nrd; + + nrd = __containerof(ctx, struct nhop_release_data, ctx); + nhop_free_any(nrd->nh); + free(nrd, M_RTABLE); +} + +static void +fib_schedule_release_nhop(struct fib_data *fd, struct nhop_object *nh) +{ + struct nhop_release_data *nrd; + + nrd = malloc(sizeof(struct nhop_release_data), M_RTABLE, M_NOWAIT | M_ZERO); + if (nrd != NULL) { + nrd->nh = nh; + epoch_call(net_epoch_preempt, release_nhop_epoch, &nrd->ctx); + } else { + /* + * Unable to allocate memory. Leak nexthop to maintain guarantee + * that each nhop. + */ + FD_PRINTF(fd, "unable to allocate structure for nhop %p deletion", nh); + } +} + +void +fib_free_nhop_idx(struct fib_data *fd, uint32_t idx) +{ + + KASSERT((idx < fd->number_nhops), ("invalid nhop index")); + + fd->nh_ref_table->refcnt[idx]--; + if (fd->nh_ref_table->refcnt[idx] == 0) { + //FD_PRINTF(fd, " FREE nhop %d %p", idx, fd->nh_idx[idx]); + fib_schedule_release_nhop(fd, fd->nh_idx[idx]); + } +} + +void +fib_free_nhop(struct fib_data *fd, struct nhop_object *nh) +{ + + fib_free_nhop_idx(fd, get_nhop_idx(nh)); +} + +struct nhop_object ** +fib_get_nhop_array(struct fib_data *fd) +{ + + return (fd->nh_idx); +} + +static struct fib_lookup_module * +fib_check_best_algo(struct rib_head *rh, struct fib_lookup_module *orig_flm) +{ + uint8_t preference, curr_preference = 0, best_preference = 0; + struct fib_lookup_module *flm, *best_flm = NULL; + struct rib_rtable_info rinfo; + int candidate_algos = 0; + + fib_get_rtable_info(rh, &rinfo); + + MOD_LOCK(); + TAILQ_FOREACH(flm, &all_algo_list, entries) { + if (flm->flm_family != rh->rib_family) + continue; + candidate_algos++; + preference = flm->flm_get_pref(&rinfo); + if (preference > best_preference) { + best_preference = preference; + best_flm = flm; + } + if (flm == orig_flm) + curr_preference = preference; + } + if (best_flm != NULL && best_flm != orig_flm) { + /* Check */ + if (curr_preference + BEST_DIFF_PERCENT < best_preference) + best_flm->flm_refcount++; + else + best_flm = NULL; + } else + best_flm = NULL; + MOD_UNLOCK(); + + RH_PRINTF(rh, "candidate_algos: %d, curr: %s(%d) result: %s(%d)", + candidate_algos, orig_flm ? orig_flm->flm_name : "NULL", curr_preference, + best_flm ? best_flm->flm_name : "NULL", best_preference); + + return (best_flm); +} + +/* + * Called when new route table is created. + * Selects, allocates and attaches fib algo for the table. + */ +int +fib_select_algo_initial(struct rib_head *rh) +{ + struct fib_lookup_module *flm; + struct fib_data *fd = NULL; + enum flm_op_result result; + + flm = fib_check_best_algo(rh, NULL); + if (flm == NULL) { + RH_PRINTF(rh, "no algo selected"); + return (ENOENT); + } + RH_PRINTF(rh, "selected algo %s", flm->flm_name); + + result = setup_instance(flm, rh, NULL, &fd, false); + RH_PRINTF(rh, "result=%d fd=%p", result, fd); + if (result == FLM_SUCCESS) { + /* + * Attach datapath directly to avoid N reallocations + * during fib growth + */ + struct fib_dp_header *fdp; + struct fib_dp **pdp; + + pdp = get_family_ptr(rh->rib_family); + if (pdp != NULL) { + fdp = get_fib_dp_header(*pdp); + fdp->ffi_idx[fd->fd_fibnum] = fd->fd_dp; + FD_PRINTF(fd, "datapath attached"); + } + } + + return (0); +} + +int +fib_module_register(struct fib_lookup_module *flm) +{ + + MOD_LOCK(); + RH_PRINTF_RAW("attaching %s to %s", flm->flm_name, + print_family(flm->flm_family)); + TAILQ_INSERT_TAIL(&all_algo_list, flm, entries); + MOD_UNLOCK(); + + return (0); +} + +int +fib_module_unregister(struct fib_lookup_module *flm) +{ + MOD_LOCK(); + if (flm->flm_refcount > 0) { + MOD_UNLOCK(); + return (EBUSY); + } + RH_PRINTF_RAW("detaching %s from %s", flm->flm_name, + print_family(flm->flm_family)); + TAILQ_REMOVE(&all_algo_list, flm, entries); + MOD_UNLOCK(); + + return (0); +} + +int +fib_module_clone(const struct fib_lookup_module *flm_orig, + struct fib_lookup_module *flm, bool waitok) +{ + + return (0); +} + +int +fib_module_dumptree(struct fib_lookup_module *flm, + enum rib_subscription_type subscription_type) +{ + + + return (0); +} + +static void +fib_algo_init(void) +{ + + mtx_init(&fib_mtx, "algo list mutex", NULL, MTX_DEF); + TAILQ_INIT(&all_algo_list); +} +SYSINIT(route_init, SI_SUB_PROTO_DOMAIN, SI_ORDER_SECOND, fib_algo_init, NULL); + Index: sys/net/route/route_tables.c =================================================================== --- sys/net/route/route_tables.c +++ sys/net/route/route_tables.c @@ -171,7 +171,7 @@ grow_rtables(uint32_t num_tables) { struct domain *dom; - struct rib_head **prnh; + struct rib_head **prnh, *rh; struct rib_head **new_rt_tables, **old_rt_tables; int family; @@ -188,6 +188,8 @@ "by default. Consider tuning %s if needed\n", "net.add_addr_allfibs"); + fib_grow_rtables(num_tables); + /* * Current rt_tables layout: * fib0[af0, af1, af2, .., AF_MAX]fib1[af0, af1, af2, .., Af_MAX].. @@ -206,10 +208,16 @@ prnh = &new_rt_tables[i * (AF_MAX + 1) + family]; if (*prnh != NULL) continue; - *prnh = dom->dom_rtattach(i); - if (*prnh == NULL) - log(LOG_ERR, "unable to create routing tables for domain %d\n", - dom->dom_family); + rh = dom->dom_rtattach(i); + if (rh == NULL) + log(LOG_ERR, "unable to create routing table for %d.%d\n", + dom->dom_family, i); + if (fib_select_algo_initial(rh) != 0) { + log(LOG_ERR, "unable to select algo for table %d.%d\n", + dom->dom_family, i); + // TODO: detach table + } + *prnh = rh; } } Index: sys/net/route/route_var.h =================================================================== --- sys/net/route/route_var.h +++ sys/net/route/route_var.h @@ -68,6 +68,7 @@ struct vnet *rib_vnet; /* vnet pointer */ int rib_family; /* AF of the rtable */ u_int rib_fibnum; /* fib number */ + bool rib_dying; /* rib is detaching */ struct callout expire_callout; /* Callout for expiring dynamic routes */ time_t next_expire; /* Next expire run ts */ uint32_t rnh_prefixes; /* Number of prefixes */ @@ -310,6 +311,12 @@ void nhgrp_ref_object(struct nhgrp_object *nhg); uint32_t nhgrp_get_idx(const struct nhgrp_object *nhg); void nhgrp_free(struct nhgrp_object *nhg); +uint32_t nhgrp_get_idx(const struct nhgrp_object *nhg); + +/* lookup_framework.c */ +void fib_grow_rtables(uint32_t new_num_tables); +int fib_select_algo_initial(struct rib_head *rh); +void fib_destroy_rib(struct rib_head *rh); /* Entropy data used for outbound hashing */ #define MPATH_ENTROPY_KEY_LEN 40 Index: sys/netinet/in_fib.c =================================================================== --- sys/netinet/in_fib.c +++ sys/netinet/in_fib.c @@ -49,6 +49,7 @@ #include #include #include +#include #include #include #include @@ -63,6 +64,10 @@ /* Assert 'struct route_in' is compatible with 'struct route' */ CHK_STRUCT_ROUTE_COMPAT(struct route_in, ro_dst4); +#ifdef ROUTE_ALGO +VNET_DEFINE(struct fib_dp *, inet_dp); +#endif + #ifdef ROUTE_MPATH struct _hash_5tuple_ipv4 { struct in_addr src; @@ -103,6 +108,29 @@ * one needs to pass NHR_REF as a flag. This will return referenced * nexthop. */ +#ifdef ROUTE_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 @@ 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 @@ return (check_urpf_nhop(nh, flags, src_if)); } +#ifndef ROUTE_ALGO static struct nhop_object * lookup_nhop(uint32_t fibnum, struct in_addr dst, uint32_t scopeid) { @@ -208,6 +238,7 @@ return (nh); } +#endif /* * Performs reverse path forwarding lookup. @@ -223,8 +254,14 @@ uint32_t flags, const struct ifnet *src_if) { struct nhop_object *nh; +#ifdef ROUTE_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)); Index: sys/netinet/in_fib_algo.c =================================================================== --- /dev/null +++ sys/netinet/in_fib_algo.c @@ -0,0 +1,315 @@ +/*- + * 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 +__FBSDID("$FreeBSD$"); + +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include + +#include +#include + +#include +#include +#include +#include +#include + + +#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; + 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); +} + +static uint8_t +lradix4_get_pref(const struct rib_rtable_info *rinfo) +{ + + if (rinfo->num_prefixes < 10) + return (255); + else if (rinfo->num_prefixes < 100000) + return (255 - rinfo->num_prefixes / 394); + 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; + + 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; + // XXX: alignment! + lr->mem = malloc(count * LRADIX4_ITEM_SZ, M_RTABLE, M_NOWAIT | M_ZERO); + if (lr->mem == NULL) + return (FLM_REBUILD); + 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 *rt_dst, *rt_mask, mask; + struct radix_node *rn; + + if (fib_get_nhop_idx(lr->fd, rt->rt_nhop) == 0) + return (FLM_REBUILD); + + if (lr->num_items >= lr->alloc_items) + return (FLM_REBUILD); + + ae = (struct radix4_addr_entry *)((char *)lr->mem + lr->num_items * LRADIX4_ITEM_SZ); + lr->num_items++; + + ae->nhop = rt->rt_nhop; + + rt_dst = (struct sockaddr_in *)rt_key(rt); + rt_mask = (struct sockaddr_in *)rt_mask(rt); + + ae->addr.sin_len = KEY_LEN_INET; + ae->addr.sin_addr = rt_dst->sin_addr; + + if (rt_mask != NULL) { + bzero(&mask, sizeof(mask)); + mask.sin_len = KEY_LEN_INET; + mask.sin_addr = rt_mask->sin_addr; + rt_mask = &mask; + } + + rn = lr->rnh->rnh_addaddr((struct sockaddr *)&ae->addr, + (struct sockaddr *)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, +}; + + +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); + if (r4->rh == NULL) + return (FLM_ERROR); + + *_data = r4; + + return (FLM_SUCCESS); +} + +static void +radix4_destroy(void *_data) +{ + + free(_data, M_RTABLE); +} + +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) +{ + struct radix4_data *r4 = (struct radix4_data *)_data; + + /* + * Grab additional reference for each nexthop to maintain guarantee + * that we have non-zero # of reference for each nexthop in radix in + * the epoch. + */ + if (rc->rc_nh_new != NULL) { + if (fib_get_nhop_idx(r4->fd, rc->rc_nh_new) == 0) + return (FLM_REBUILD); + } + if (rc->rc_nh_old != NULL) + fib_free_nhop(r4->fd, rc->rc_nh_old); + + 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_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_radix4_lockless); + fib_module_register(&flm_radix4); +} +SYSINIT(fib4_algo_init, SI_SUB_PROTO_DOMAIN, SI_ORDER_THIRD, fib4_algo_init, NULL); Index: sys/netinet6/in6_fib.c =================================================================== --- sys/netinet6/in6_fib.c +++ sys/netinet6/in6_fib.c @@ -50,6 +50,7 @@ #include #include #include +#include #include #include #include @@ -69,6 +70,10 @@ CHK_STRUCT_ROUTE_COMPAT(struct route_in6, ro_dst); +#ifdef ROUTE_ALGO +VNET_DEFINE(struct fib_dp *, inet6_dp); +#endif + #ifdef ROUTE_MPATH struct _hash_5tuple_ipv6 { struct in6_addr src; @@ -81,6 +86,7 @@ _Static_assert(sizeof(struct _hash_5tuple_ipv6) == 40, "_hash_5tuple_ipv6 size is wrong"); + uint32_t fib6_calc_software_hash(const struct in6_addr *src, const struct in6_addr *dst, unsigned short src_port, unsigned short dst_port, char proto, @@ -111,6 +117,29 @@ * one needs to pass NHR_REF as a flag. This will return referenced * nexthop. */ +#ifdef ROUTE_ALGO +struct nhop_object * +fib6_lookup(uint32_t fibnum, const struct in6_addr *dst6, + uint32_t scopeid, uint32_t flags, uint32_t flowid) +{ + struct nhop_object *nh; + struct fib_dp *dp = &V_inet6_dp[fibnum]; + struct flm_lookup_key key = {.addr6 = dst6 }; + + 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 * fib6_lookup(uint32_t fibnum, const struct in6_addr *dst6, uint32_t scopeid, uint32_t flags, uint32_t flowid) @@ -151,6 +180,7 @@ RTSTAT_INC(rts_unreach); return (NULL); } +#endif inline static int check_urpf_nhop(const struct nhop_object *nh, uint32_t flags, @@ -237,8 +267,14 @@ uint32_t scopeid, uint32_t flags, const struct ifnet *src_if) { struct nhop_object *nh; +#ifndef ROUTE_ALGO + struct fib_dp *dp = &V_inet6_dp[fibnum]; + struct flm_lookup_key key = {.addr6 = dst6 }; + nh = dp->f(dp->arg, key, scopeid); +#else nh = lookup_nhop(fibnum, dst6, scopeid); +#endif if (nh != NULL) return (check_urpf(nh, flags, src_if)); return (0); Index: sys/netinet6/in6_fib_algo.c =================================================================== --- /dev/null +++ sys/netinet6/in6_fib_algo.c @@ -0,0 +1,340 @@ +/*- + * 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 +__FBSDID("$FreeBSD$"); + +#include "opt_inet6.h" + +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include + +#include +#include + +#include +#include +#include +#include +#include +#include + +#include +#include +#include +#include +#include +#define RTDEBUG + +#define KEY_LEN_INET6 (offsetof(struct sa_in6, sin6_addr) + sizeof(struct in6_addr)) +#define OFF_LEN_INET6 (8 * offsetof(struct sa_in6, sin6_addr)) +struct sa_in6 { + uint8_t sin6_len; + uint8_t sin6_family; + uint8_t pad[2]; + struct in6_addr sin6_addr; +}; +struct radix6_addr_entry { + struct radix_node rn[2]; + struct sa_in6 addr; + struct nhop_object *nhop; +}; +#define LRADIX6_ITEM_SZ roundup2(sizeof(struct radix6_addr_entry), 64) + +struct lradix6_data { + struct radix_node_head *rnh; + struct fib_data *fd; + void *mem; + uint32_t alloc_items; + uint32_t num_items; +}; + +static struct nhop_object * +lradix6_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 radix6_addr_entry *ent; + struct sa_in6 addr6 = { + .sin6_len = KEY_LEN_INET6, + .sin6_addr = *key.addr6, + }; + if (IN6_IS_SCOPE_LINKLOCAL(key.addr6)) + addr6.sin6_addr.s6_addr16[1] = htons(scopeid & 0xffff); + ent = (struct radix6_addr_entry *)(rnh->rnh_matchaddr(&addr6, &rnh->rh)); + if (ent != NULL) + return (ent->nhop); + return (NULL); +} + +static uint8_t +lradix6_get_pref(const struct rib_rtable_info *rinfo) +{ + + if (rinfo->num_prefixes < 10) + return (255); + else if (rinfo->num_prefixes < 100000) + return (255 - rinfo->num_prefixes / 394); + else + return (1); +} + +static enum flm_op_result +lradix6_init(uint32_t fibnum, struct fib_data *fd, void *_old_data, void **_data) +{ + struct lradix6_data *lr; + struct rib_rtable_info rinfo; + uint32_t count; + + lr = malloc(sizeof(struct lradix6_data), M_RTABLE, M_NOWAIT | M_ZERO); + if (lr == NULL || !rn_inithead((void **)&lr->rnh, OFF_LEN_INET6)) + return (FLM_REBUILD); + fib_get_rtable_info(fib_get_rh(fd), &rinfo); + + count = rinfo.num_prefixes * 11 / 10; + // XXX: alignment! + lr->mem = malloc(count * LRADIX6_ITEM_SZ, M_RTABLE, M_NOWAIT | M_ZERO); + if (lr->mem == NULL) + return (FLM_REBUILD); + lr->alloc_items = count; + lr->fd = fd; + + *_data = lr; + + return (FLM_SUCCESS); +} + +static void +lradix6_destroy(void *_data) +{ + struct lradix6_data *lr = (struct lradix6_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 +lradix6_add_route_cb(struct rtentry *rt, void *_data) +{ + struct lradix6_data *lr = (struct lradix6_data *)_data; + struct radix6_addr_entry *ae; + struct sockaddr_in6 *rt_dst, *rt_mask; + struct sa_in6 mask; + struct radix_node *rn; + + if (fib_get_nhop_idx(lr->fd, rt->rt_nhop) == 0) + return (FLM_REBUILD); + + if (lr->num_items >= lr->alloc_items) + return (FLM_REBUILD); + + ae = (struct radix6_addr_entry *)((char *)lr->mem + lr->num_items * LRADIX6_ITEM_SZ); + lr->num_items++; + + ae->nhop = rt->rt_nhop; + + rt_dst = (struct sockaddr_in6 *)rt_key(rt); + rt_mask = (struct sockaddr_in6 *)rt_mask(rt); + + ae->addr.sin6_len = KEY_LEN_INET6; + ae->addr.sin6_addr = rt_dst->sin6_addr; + + if (rt_mask != NULL) { + bzero(&mask, sizeof(mask)); + mask.sin6_len = KEY_LEN_INET6; + mask.sin6_addr = rt_mask->sin6_addr; + rt_mask = (struct sockaddr_in6 *)&mask; + } + + rn = lr->rnh->rnh_addaddr((struct sockaddr *)&ae->addr, + (struct sockaddr *)rt_mask, &lr->rnh->rh, ae->rn); + if (rn == NULL) + return (FLM_REBUILD); + + return (FLM_SUCCESS); +} + +static enum flm_op_result +lradix6_end_dump(void *_data, struct fib_dp *dp) +{ + struct lradix6_data *lr = (struct lradix6_data *)_data; + + dp->f = lradix6_lookup; + dp->arg = lr->rnh; + + return (FLM_SUCCESS); +} + +static enum flm_op_result +lradix6_change_cb(struct rib_head *rnh, struct rib_cmd_info *rc, + void *_data) +{ + + return (FLM_REBUILD); +} + +struct fib_lookup_module flm_radix6_lockless = { + .flm_name = "radix6_lockless", + .flm_family = AF_INET6, + .flm_init_cb = lradix6_init, + .flm_destroy_cb = lradix6_destroy, + .flm_dump_rib_item_cb = lradix6_add_route_cb, + .flm_dump_end_cb = lradix6_end_dump, + .flm_change_rib_item_cb = lradix6_change_cb, + .flm_get_pref = lradix6_get_pref, +}; + + +struct radix6_data { + struct fib_data *fd; + struct rib_head *rh; +}; + +static struct nhop_object * +radix6_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_in6 sin6 = { + .sin6_family = AF_INET6, + .sin6_len = sizeof(struct sockaddr_in6), + .sin6_addr = *key.addr6, + }; + if (IN6_IS_SCOPE_LINKLOCAL(key.addr6)) + sin6.sin6_addr.s6_addr16[1] = htons(scopeid & 0xffff); + + nh = NULL; + RIB_RLOCK(rh); + rn = rh->rnh_matchaddr((void *)&sin6, &rh->head); + if (rn != NULL && ((rn->rn_flags & RNF_ROOT) == 0)) + nh = (RNTORT(rn))->rt_nhop; + RIB_RUNLOCK(rh); + + return (nh); +} + +static uint8_t +radix6_get_pref(const struct rib_rtable_info *rinfo) +{ + + return (50); +} + +static enum flm_op_result +radix6_init(uint32_t fibnum, struct fib_data *fd, void *_old_data, void **_data) +{ + struct radix6_data *r6; + + r6 = malloc(sizeof(struct radix6_data), M_RTABLE, M_NOWAIT | M_ZERO); + if (r6 == NULL) + return (FLM_REBUILD); + r6->fd = fd; + r6->rh = fib_get_rh(fd); + if (r6->rh == NULL) + return (FLM_ERROR); + + *_data = r6; + + return (FLM_SUCCESS); +} + +static void +radix6_destroy(void *_data) +{ + + free(_data, M_RTABLE); +} + +static enum flm_op_result +radix6_end_dump(void *_data, struct fib_dp *dp) +{ + struct radix6_data *r6 = (struct radix6_data *)_data; + + dp->f = radix6_lookup; + dp->arg = r6->rh; + + return (FLM_SUCCESS); +} + +static enum flm_op_result +radix6_change_cb(struct rib_head *rnh, struct rib_cmd_info *rc, + void *_data) +{ + struct radix6_data *r6 = (struct radix6_data *)_data; + + /* + * Grab additional reference for each nexthop to maintain guarantee + * that we have non-zero # of reference for each nexthop in radix in + * the epoch. + */ + if (rc->rc_nh_new != NULL) { + if (fib_get_nhop_idx(r6->fd, rc->rc_nh_new) == 0) + return (FLM_REBUILD); + } + if (rc->rc_nh_old != NULL) + fib_free_nhop(r6->fd, rc->rc_nh_old); + + return (FLM_SUCCESS); +} + +struct fib_lookup_module flm_radix6 = { + .flm_name = "radix6", + .flm_family = AF_INET6, + .flm_init_cb = radix6_init, + .flm_destroy_cb = radix6_destroy, + .flm_dump_end_cb = radix6_end_dump, + .flm_change_rib_item_cb = radix6_change_cb, + .flm_get_pref = radix6_get_pref, +}; + +static void +fib6_algo_init(void) +{ + + fib_module_register(&flm_radix6_lockless); + fib_module_register(&flm_radix6); +} +SYSINIT(fib6_algo_init, SI_SUB_PROTO_DOMAIN, SI_ORDER_THIRD, fib6_algo_init, NULL);