aboutsummaryrefslogtreecommitdiff
path: root/sys/net/route/fib_algo.c
diff options
context:
space:
mode:
Diffstat (limited to 'sys/net/route/fib_algo.c')
-rw-r--r--sys/net/route/fib_algo.c1608
1 files changed, 1608 insertions, 0 deletions
diff --git a/sys/net/route/fib_algo.c b/sys/net/route/fib_algo.c
new file mode 100644
index 000000000000..afb009d4c8cf
--- /dev/null
+++ b/sys/net/route/fib_algo.c
@@ -0,0 +1,1608 @@
+/*-
+ * 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 "opt_inet6.h"
+#include "opt_route.h"
+
+#include <sys/param.h>
+#include <sys/eventhandler.h>
+#include <sys/kernel.h>
+#include <sys/sbuf.h>
+#include <sys/lock.h>
+#include <sys/rmlock.h>
+#include <sys/malloc.h>
+#include <sys/mbuf.h>
+#include <sys/module.h>
+#include <sys/kernel.h>
+#include <sys/priv.h>
+#include <sys/proc.h>
+#include <sys/socket.h>
+#include <sys/socketvar.h>
+#include <sys/sysctl.h>
+#include <sys/syslog.h>
+#include <sys/queue.h>
+#include <net/vnet.h>
+
+#include <net/if.h>
+#include <net/if_var.h>
+
+#include <netinet/in.h>
+#include <netinet/in_var.h>
+#include <netinet/ip.h>
+#include <netinet/ip_var.h>
+#ifdef INET6
+#include <netinet/ip6.h>
+#include <netinet6/ip6_var.h>
+#endif
+
+#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>
+
+#include <machine/stdarg.h>
+
+/*
+ * Fib lookup framework.
+ *
+ * This framework enables accelerated longest-prefix-match lookups for the
+ * routing tables by adding the ability to dynamically attach/detach lookup
+ * algorithms implementation to/from the datapath.
+ *
+ * flm - fib lookup modules - implementation of particular lookup algorithm
+ * fd - fib data - instance of an flm bound to specific routing table
+ *
+ * This file provides main framework functionality.
+ *
+ * The following are the features provided by the framework
+ *
+ * 1) nexhops abstraction -> provides transparent referencing, indexing
+ * and efficient idx->ptr mappings for nexthop and nexthop groups.
+ * 2) Routing table synchronisation
+ * 3) dataplane attachment points
+ * 4) automatic algorithm selection based on the provided preference.
+ *
+ *
+ * DATAPATH
+ * 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.
+ *
+ */
+
+SYSCTL_DECL(_net_route);
+SYSCTL_NODE(_net_route, OID_AUTO, algo, CTLFLAG_RW | CTLFLAG_MPSAFE, 0,
+ "Fib algorithm lookups");
+
+#ifdef INET6
+bool algo_fixed_inet6 = false;
+SYSCTL_NODE(_net_route_algo, OID_AUTO, inet6, CTLFLAG_RW | CTLFLAG_MPSAFE, 0,
+ "IPv6 longest prefix match lookups");
+#endif
+#ifdef INET
+bool algo_fixed_inet = false;
+SYSCTL_NODE(_net_route_algo, OID_AUTO, inet, CTLFLAG_RW | CTLFLAG_MPSAFE, 0,
+ "IPv4 longest prefix match lookups");
+#endif
+
+struct nhop_ref_table {
+ uint32_t count;
+ int32_t refcnt[0];
+};
+
+/*
+ * Data structure for the fib lookup instance tied to the particular rib.
+ */
+struct fib_data {
+ uint32_t number_nhops; /* current # of nhops */
+ 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 */
+ uint32_t fd_algo_mask; /* bitmask for algo data */
+ 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_dp fd_dp; /* fib datapath data */
+ struct vnet *fd_vnet; /* vnet fib belongs to */
+ struct epoch_context fd_epoch_ctx; /* epoch context for deletion */
+ struct fib_lookup_module *fd_flm;/* pointer to the lookup module */
+ 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_fd_callout(void *_data);
+static void destroy_fd_instance_epoch(epoch_context_t ctx);
+static enum flm_op_result attach_datapath(struct fib_data *fd);
+static bool is_idx_free(struct fib_data *fd, uint32_t index);
+static void set_algo_fixed(struct rib_head *rh);
+
+static uint32_t fib_ref_nhop(struct fib_data *fd, struct nhop_object *nh);
+static void fib_unref_nhop(struct fib_data *fd, struct nhop_object *nh);
+
+static struct fib_lookup_module *fib_check_best_algo(struct rib_head *rh,
+ struct fib_lookup_module *orig_flm);
+static void fib_unref_algo(struct fib_lookup_module *flm);
+static bool flm_error_check(const struct fib_lookup_module *flm, uint32_t fibnum);
+
+struct mtx fib_mtx;
+#define FIB_MOD_LOCK() mtx_lock(&fib_mtx)
+#define FIB_MOD_UNLOCK() mtx_unlock(&fib_mtx)
+#define FIB_MOD_LOCK_ASSERT() mtx_assert(&fib_mtx, MA_OWNED)
+
+
+/* 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
+
+/* Debug */
+static int flm_debug_level = LOG_NOTICE;
+SYSCTL_INT(_net_route_algo, OID_AUTO, debug_level, CTLFLAG_RW | CTLFLAG_RWTUN,
+ &flm_debug_level, 0, "debuglevel");
+#define FLM_MAX_DEBUG_LEVEL LOG_DEBUG
+
+#define _PASS_MSG(_l) (flm_debug_level >= (_l))
+#define ALGO_PRINTF(_fmt, ...) printf("[fib_algo] %s: " _fmt "\n", __func__, ##__VA_ARGS__)
+#define _ALGO_PRINTF(_fib, _fam, _aname, _func, _fmt, ...) \
+ printf("[fib_algo] %s.%u (%s) %s: " _fmt "\n",\
+ print_family(_fam), _fib, _aname, _func, ## __VA_ARGS__)
+#define _RH_PRINTF(_fib, _fam, _func, _fmt, ...) \
+ printf("[fib_algo] %s.%u %s: " _fmt "\n", print_family(_fam), _fib, _func, ## __VA_ARGS__)
+#define RH_PRINTF(_l, _rh, _fmt, ...) if (_PASS_MSG(_l)) { \
+ _RH_PRINTF(_rh->rib_fibnum, _rh->rib_family, __func__, _fmt, ## __VA_ARGS__);\
+}
+#define FD_PRINTF(_l, _fd, _fmt, ...) FD_PRINTF_##_l(_l, _fd, _fmt, ## __VA_ARGS__)
+#define _FD_PRINTF(_l, _fd, _fmt, ...) if (_PASS_MSG(_l)) { \
+ _ALGO_PRINTF(_fd->fd_fibnum, _fd->fd_family, _fd->fd_flm->flm_name, \
+ __func__, _fmt, ## __VA_ARGS__); \
+}
+#if FLM_MAX_DEBUG_LEVEL>=LOG_DEBUG
+#define FD_PRINTF_LOG_DEBUG _FD_PRINTF
+#else
+#define FD_PRINTF_LOG_DEBUG()
+#endif
+#if FLM_MAX_DEBUG_LEVEL>=LOG_INFO
+#define FD_PRINTF_LOG_INFO _FD_PRINTF
+#else
+#define FD_PRINTF_LOG_INFO()
+#endif
+#define FD_PRINTF_LOG_NOTICE _FD_PRINTF
+#define FD_PRINTF_LOG_ERR _FD_PRINTF
+#define FD_PRINTF_LOG_WARNING _FD_PRINTF
+
+
+/* List of all registered lookup algorithms */
+static TAILQ_HEAD(, fib_lookup_module) all_algo_list;
+
+/* List of all fib lookup instances in the vnet */
+VNET_DEFINE_STATIC(TAILQ_HEAD(fib_data_head, fib_data), fib_data_list);
+#define V_fib_data_list VNET(fib_data_list)
+
+/* Datastructure for storing non-transient fib lookup module failures */
+struct fib_error {
+ int fe_family;
+ uint32_t fe_fibnum; /* failed rtable */
+ struct fib_lookup_module *fe_flm; /* failed module */
+ TAILQ_ENTRY(fib_error) entries;/* list of all errored entries */
+};
+VNET_DEFINE_STATIC(TAILQ_HEAD(fib_error_head, fib_error), fib_error_list);
+#define V_fib_error_list VNET(fib_error_list)
+
+/* Per-family array of fibnum -> {func, arg} mappings used in datapath */
+struct fib_dp_header {
+ struct epoch_context fdh_epoch_ctx;
+ uint32_t fdh_num_tables;
+ struct fib_dp fdh_idx[0];
+};
+
+/*
+ * Tries to add new non-transient algorithm error to the list of
+ * errors.
+ * Returns true on success.
+ */
+static bool
+flm_error_add(struct fib_lookup_module *flm, uint32_t fibnum)
+{
+ struct fib_error *fe;
+
+ fe = malloc(sizeof(struct fib_error), M_TEMP, M_NOWAIT | M_ZERO);
+ if (fe == NULL)
+ return (false);
+ fe->fe_flm = flm;
+ fe->fe_family = flm->flm_family;
+ fe->fe_fibnum = fibnum;
+
+ FIB_MOD_LOCK();
+ /* Avoid duplicates by checking if error already exists first */
+ if (flm_error_check(flm, fibnum)) {
+ FIB_MOD_UNLOCK();
+ free(fe, M_TEMP);
+ return (true);
+ }
+ TAILQ_INSERT_HEAD(&V_fib_error_list, fe, entries);
+ FIB_MOD_UNLOCK();
+
+ return (true);
+}
+
+/*
+ * True if non-transient error has been registered for @flm in @fibnum.
+ */
+static bool
+flm_error_check(const struct fib_lookup_module *flm, uint32_t fibnum)
+{
+ const struct fib_error *fe;
+
+ TAILQ_FOREACH(fe, &V_fib_error_list, entries) {
+ if ((fe->fe_flm == flm) && (fe->fe_fibnum == fibnum))
+ return (true);
+ }
+
+ return (false);
+}
+
+/*
+ * Clear all errors of algo specified by @flm.
+ */
+static void
+fib_error_clear_flm(struct fib_lookup_module *flm)
+{
+ struct fib_error *fe, *fe_tmp;
+
+ FIB_MOD_LOCK_ASSERT();
+
+ TAILQ_FOREACH_SAFE(fe, &V_fib_error_list, entries, fe_tmp) {
+ if (fe->fe_flm == flm) {
+ TAILQ_REMOVE(&V_fib_error_list, fe, entries);
+ free(fe, M_TEMP);
+ }
+ }
+}
+
+/*
+ * Clears all errors in current VNET.
+ */
+static void
+fib_error_clear()
+{
+ struct fib_error *fe, *fe_tmp;
+
+ FIB_MOD_LOCK_ASSERT();
+
+ TAILQ_FOREACH_SAFE(fe, &V_fib_error_list, entries, fe_tmp) {
+ TAILQ_REMOVE(&V_fib_error_list, fe, entries);
+ free(fe, M_TEMP);
+ }
+}
+
+static const char *
+print_family(int family)
+{
+
+ if (family == AF_INET)
+ return ("inet");
+ else if (family == AF_INET6)
+ return ("inet6");
+ else
+ return ("unknown");
+}
+
+/*
+ * Debug function used by lookup algorithms.
+ * Outputs message denoted by @fmt, prepended by "[fib_algo] inetX.Y (algo) "
+ */
+void
+fib_printf(int level, struct fib_data *fd, const char *func, char *fmt, ...)
+{
+ char buf[128];
+ va_list ap;
+
+ if (level > flm_debug_level)
+ return;
+
+ va_start(ap, fmt);
+ vsnprintf(buf, sizeof(buf), fmt, ap);
+ va_end(ap);
+
+ _ALGO_PRINTF(fd->fd_fibnum, fd->fd_family, fd->fd_flm->flm_name,
+ func, "%s", buf);
+}
+
+/*
+ * Outputs list of algorithms supported by the provided address family.
+ */
+static int
+print_algos_sysctl(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, 512, 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);
+}
+
+#ifdef INET6
+static int
+print_algos_sysctl_inet6(SYSCTL_HANDLER_ARGS)
+{
+
+ return (print_algos_sysctl(req, AF_INET6));
+}
+SYSCTL_PROC(_net_route_algo_inet6, OID_AUTO, algo_list,
+ CTLTYPE_STRING | CTLFLAG_RD | CTLFLAG_MPSAFE, NULL, 0,
+ print_algos_sysctl_inet6, "A", "List of IPv6 lookup algorithms");
+#endif
+
+#ifdef INET
+static int
+print_algos_sysctl_inet(SYSCTL_HANDLER_ARGS)
+{
+
+ return (print_algos_sysctl(req, AF_INET));
+}
+SYSCTL_PROC(_net_route_algo_inet, OID_AUTO, algo_list,
+ CTLTYPE_STRING | CTLFLAG_RD | CTLFLAG_MPSAFE, NULL, 0,
+ print_algos_sysctl_inet, "A", "List of IPv4 lookup algorithms");
+#endif
+
+/*
+ * Calculate delay between repeated failures.
+ * Returns current delay in milliseconds.
+ */
+static uint32_t
+callout_calc_delay_ms(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_fd_callout, fd, 0);
+}
+
+static void
+schedule_fd_rebuild(struct fib_data *fd)
+{
+
+ FIB_MOD_LOCK();
+ if (!fd->fd_need_rebuild) {
+ fd->fd_need_rebuild = true;
+
+ /*
+ * Potentially re-schedules pending callout
+ * initiated by schedule_algo_eval.
+ */
+ FD_PRINTF(LOG_INFO, fd, "Scheduling rebuilt");
+ schedule_callout(fd, callout_calc_delay_ms(fd));
+ }
+ FIB_MOD_UNLOCK();
+}
+
+static void
+schedule_algo_eval(struct fib_data *fd)
+{
+
+ if (fd->fd_num_changes++ == 0) {
+ /* Start callout to consider switch */
+ FIB_MOD_LOCK();
+ if (!callout_pending(&fd->fd_callout))
+ schedule_callout(fd, ALGO_EVAL_DELAY_MS);
+ FIB_MOD_UNLOCK();
+ } else if (fd->fd_num_changes > ALGO_EVAL_NUM_ROUTES && !fd->fd_force_eval) {
+ /* Reset callout to exec immediately */
+ FIB_MOD_LOCK();
+ if (!fd->fd_need_rebuild) {
+ fd->fd_force_eval = true;
+ schedule_callout(fd, 1);
+ }
+ FIB_MOD_UNLOCK();
+ }
+}
+
+/*
+ * Rib subscription handler. Checks if the algorithm is ready to
+ * receive updates, handles nexthop refcounting and passes change
+ * data to the algorithm callback.
+ */
+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);
+
+ /*
+ * There is a small gap between subscribing for route changes
+ * and initiating rtable dump. Avoid receiving route changes
+ * prior to finishing rtable dump by checking `init_done`.
+ */
+ if (!fd->init_done)
+ return;
+ /*
+ * If algo requested rebuild, stop sending updates by default.
+ * This simplifies nexthop refcount handling logic.
+ */
+ if (fd->fd_need_rebuild)
+ return;
+
+ /* Consider scheduling algorithm re-evaluation */
+ schedule_algo_eval(fd);
+
+ /*
+ * Maintain guarantee that every nexthop returned by the dataplane
+ * lookup has > 0 refcount, so can be safely referenced within current
+ * epoch.
+ */
+ if (rc->rc_nh_new != NULL) {
+ if (fib_ref_nhop(fd, rc->rc_nh_new) == 0) {
+ /* ran out of indexes */
+ schedule_fd_rebuild(fd);
+ return;
+ }
+ }
+
+ result = fd->fd_flm->flm_change_rib_item_cb(rnh, rc, fd->fd_algo_data);
+
+ switch (result) {
+ case FLM_SUCCESS:
+ /* Unref old nexthop on success */
+ if (rc->rc_nh_old != NULL)
+ fib_unref_nhop(fd, rc->rc_nh_old);
+ break;
+ case FLM_REBUILD:
+
+ /*
+ * Algo is not able to apply the update.
+ * Schedule algo rebuild.
+ */
+ schedule_fd_rebuild(fd);
+ break;
+ case FLM_ERROR:
+
+ /*
+ * Algo reported a non-recoverable error.
+ * Record the error and schedule rebuild, which will
+ * trigger best algo selection.
+ */
+ FD_PRINTF(LOG_ERR, fd, "algo reported non-recoverable error");
+ if (!flm_error_add(fd->fd_flm, fd->fd_fibnum))
+ FD_PRINTF(LOG_ERR, fd, "failed to ban algo");
+ schedule_fd_rebuild(fd);
+ }
+}
+
+static void
+estimate_nhop_scale(const struct fib_data *old_fd, struct fib_data *fd)
+{
+
+ if (old_fd == NULL) {
+ // TODO: read from rtable
+ 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;
+};
+
+/*
+ * Handler called after all rtenties have been dumped.
+ * Performs post-dump framework checks and calls
+ * algo:flm_dump_end_cb().
+ *
+ * Updates walk_cbdata 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;
+
+ RIB_WLOCK_ASSERT(w->fd->fd_rh);
+
+ if (rnh->rib_dying) {
+ w->result = FLM_ERROR;
+ return;
+ }
+
+ if (stage != RIB_WALK_HOOK_POST || w->result != FLM_SUCCESS)
+ return;
+
+ /* Post-dump hook, dump successful */
+
+ if (fd->hit_nhops) {
+ FD_PRINTF(LOG_INFO, 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;
+ }
+}
+
+/*
+ * Callback for each entry in rib.
+ * Calls algo:flm_dump_rib_item_cb func as a part of initial
+ * route table synchronisation.
+ */
+static int
+sync_algo_cb(struct rtentry *rt, void *_data)
+{
+ struct walk_cbdata *w = (struct walk_cbdata *)_data;
+
+ RIB_WLOCK_ASSERT(w->fd->fd_rh);
+
+ if (w->result == FLM_SUCCESS && w->func) {
+
+ /*
+ * Reference nexthops to maintain guarantee that
+ * each nexthop returned by datapath has > 0 references
+ * and can be safely referenced within current epoch.
+ */
+ struct nhop_object *nh = rt_get_raw_nhop(rt);
+ if (fib_ref_nhop(w->fd, nh) != 0)
+ w->result = w->func(rt, w->fd->fd_algo_data);
+ else
+ w->result = FLM_REBUILD;
+ }
+
+ return (0);
+}
+
+/*
+ * Dump all routing table state to the algo instance.
+ */
+static enum flm_op_result
+sync_algo(struct fib_data *fd)
+{
+ struct walk_cbdata w = {
+ .fd = fd,
+ .func = fd->fd_flm->flm_dump_rib_item_cb,
+ .result = FLM_SUCCESS,
+ };
+
+ rib_walk_ext_internal(fd->fd_rh, true, sync_algo_cb, sync_algo_end_cb, &w);
+
+ FD_PRINTF(LOG_INFO, fd, "initial dump completed.");
+
+ return (w.result);
+}
+
+/*
+ * Schedules epoch-backed @fd instance deletion.
+ * * Unlinks @fd from the list of active algo instances.
+ * * Removes rib subscription.
+ * * Stops callout.
+ * * Schedules actual deletion.
+ *
+ * Assume @fd is already unlinked from the datapath.
+ */
+static int
+schedule_destroy_fd_instance(struct fib_data *fd, bool in_callout)
+{
+ bool is_dead;
+
+ NET_EPOCH_ASSERT();
+
+ FIB_MOD_LOCK();
+ is_dead = fd->fd_dead;
+ if (!is_dead)
+ fd->fd_dead = true;
+ if (fd->fd_linked) {
+ TAILQ_REMOVE(&V_fib_data_list, fd, entries);
+ fd->fd_linked = false;
+ }
+ FIB_MOD_UNLOCK();
+ if (is_dead)
+ return (0);
+
+ FD_PRINTF(LOG_INFO, 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 2 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);
+
+ FD_PRINTF(LOG_INFO, fd, "destroying old instance");
+ epoch_call(net_epoch_preempt, destroy_fd_instance_epoch,
+ &fd->fd_epoch_ctx);
+
+ return (0);
+}
+
+/*
+ * Wipe all fd instances from the list matching rib specified by @rh.
+ * If @keep_first is set, remove all but the first record.
+ */
+static void
+fib_cleanup_algo(struct rib_head *rh, bool keep_first, bool in_callout)
+{
+ struct fib_data_head tmp_head = TAILQ_HEAD_INITIALIZER(tmp_head);
+ struct fib_data *fd, *fd_tmp;
+ struct epoch_tracker et;
+
+ FIB_MOD_LOCK();
+ TAILQ_FOREACH_SAFE(fd, &V_fib_data_list, entries, fd_tmp) {
+ if (fd->fd_rh == rh) {
+ if (keep_first) {
+ keep_first = false;
+ continue;
+ }
+ TAILQ_REMOVE(&V_fib_data_list, fd, entries);
+ fd->fd_linked = false;
+ TAILQ_INSERT_TAIL(&tmp_head, fd, entries);
+ }
+ }
+ FIB_MOD_UNLOCK();
+
+ /* Pass 2: remove each entry */
+ NET_EPOCH_ENTER(et);
+ TAILQ_FOREACH_SAFE(fd, &tmp_head, entries, fd_tmp) {
+ schedule_destroy_fd_instance(fd, in_callout);
+ }
+ NET_EPOCH_EXIT(et);
+}
+
+void
+fib_destroy_rib(struct rib_head *rh)
+{
+
+ /*
+ * rnh has `is_dying` flag set, so setup of new fd's will fail at
+ * sync_algo() stage, preventing new entries to be added to the list
+ * of active algos. Remove all existing entries for the particular rib.
+ */
+ fib_cleanup_algo(rh, false, false);
+}
+
+/*
+ * Finalises fd destruction by freeing all fd resources.
+ */
+static void
+destroy_fd_instance(struct fib_data *fd)
+{
+
+ FD_PRINTF(LOG_INFO, 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) && (fd->nh_ref_table != NULL)) {
+ for (int i = 0; i < fd->number_nhops; i++) {
+ if (!is_idx_free(fd, i)) {
+ FD_PRINTF(LOG_DEBUG, 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);
+
+ fib_unref_algo(fd->fd_flm);
+
+ free(fd, M_RTABLE);
+}
+
+/*
+ * Epoch callback indicating fd is safe to destroy
+ */
+static void
+destroy_fd_instance_epoch(epoch_context_t ctx)
+{
+ struct fib_data *fd;
+
+ fd = __containerof(ctx, struct fib_data, fd_epoch_ctx);
+
+ destroy_fd_instance(fd);
+}
+
+/*
+ * Tries to setup fd instance.
+ * - Allocates fd/nhop table
+ * - Runs algo:flm_init_cb algo init
+ * - Subscribes fd to the rib
+ * - Runs rtable dump
+ * - Adds instance to the list of active instances.
+ *
+ * Returns: operation result. Fills in @pfd with resulting fd on success.
+ *
+ */
+static enum flm_op_result
+try_setup_fd_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_nhop_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;
+
+ FIB_MOD_LOCK();
+ flm->flm_refcount++;
+ FIB_MOD_UNLOCK();
+
+ /* Allocate nhidx -> nhop_ptr table */
+ size = fd->number_nhops * sizeof(void *);
+ fd->nh_idx = malloc(size, M_RTABLE, M_NOWAIT | M_ZERO);
+ if (fd->nh_idx == NULL) {
+ FD_PRINTF(LOG_INFO, 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->nh_ref_table = malloc(size, M_RTABLE, M_NOWAIT | M_ZERO);
+ if (fd->nh_ref_table == NULL) {
+ FD_PRINTF(LOG_INFO, 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(LOG_INFO, fd, "DUMP completed successfully.");
+
+ FIB_MOD_LOCK();
+ /*
+ * Insert fd in the beginning of a list, to maintain invariant
+ * that first matching entry for the AF/fib is always the active
+ * one.
+ */
+ TAILQ_INSERT_HEAD(&V_fib_data_list, fd, entries);
+ fd->fd_linked = true;
+ FIB_MOD_UNLOCK();
+
+ return (FLM_SUCCESS);
+}
+
+/*
+ * Sets up algo @flm for table @rh and links it to the datapath.
+ *
+ */
+static enum flm_op_result
+setup_fd_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_fd_instance(flm, rh, prev_fd, &new_fd);
+
+ if ((result == FLM_SUCCESS) && attach)
+ result = attach_datapath(new_fd);
+
+ if ((prev_fd != NULL) && (prev_fd != orig_fd)) {
+ schedule_destroy_fd_instance(prev_fd, false);
+ prev_fd = NULL;
+ }
+ NET_EPOCH_EXIT(et);
+
+ RH_PRINTF(LOG_INFO, 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 */
+ FIB_MOD_LOCK();
+ if (orig_fd != NULL)
+ orig_fd->fd_failed_rebuilds++;
+ FIB_MOD_UNLOCK();
+
+ /* Ban algo on non-recoverable error */
+ if (result == FLM_ERROR)
+ flm_error_add(flm, rh->rib_fibnum);
+
+ NET_EPOCH_ENTER(et);
+ if ((prev_fd != NULL) && (prev_fd != orig_fd))
+ schedule_destroy_fd_instance(prev_fd, false);
+ if (new_fd != NULL) {
+ schedule_destroy_fd_instance(new_fd, false);
+ new_fd = NULL;
+ }
+ NET_EPOCH_EXIT(et);
+ }
+
+ *pfd = new_fd;
+ return (result);
+}
+
+/*
+ * Callout for all scheduled fd-related work.
+ * - Checks if the current algo is still the best algo
+ * - Creates a new instance of an algo for af/fib if desired.
+ */
+static void
+rebuild_fd_callout(void *_data)
+{
+ struct fib_data *fd, *fd_new, *fd_tmp;
+ struct fib_lookup_module *flm_new;
+ struct epoch_tracker et;
+ enum flm_op_result result;
+ bool need_rebuild = false;
+
+ fd = (struct fib_data *)_data;
+
+ FIB_MOD_LOCK();
+ need_rebuild = fd->fd_need_rebuild;
+ fd->fd_need_rebuild = false;
+ fd->fd_force_eval = false;
+ fd->fd_num_changes = 0;
+ FIB_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;
+ }
+
+ if (flm_new == NULL) {
+ flm_new = fd->fd_flm;
+ fd_tmp = fd;
+ } else {
+ fd_tmp = NULL;
+ FD_PRINTF(LOG_NOTICE, fd, "switching algo to %s", flm_new->flm_name);
+ }
+ result = setup_fd_instance(flm_new, fd->fd_rh, fd_tmp, &fd_new, true);
+ if (fd_tmp == NULL) {
+ /* fd_new represents new algo */
+ fib_unref_algo(flm_new);
+ }
+ if (result != FLM_SUCCESS) {
+ FD_PRINTF(LOG_NOTICE, fd, "table rebuild failed");
+ CURVNET_RESTORE();
+ return;
+ }
+ FD_PRINTF(LOG_INFO, fd_new, "switched to new instance");
+
+ /* Remove old instance removal */
+ if (fd != NULL) {
+ NET_EPOCH_ENTER(et);
+ schedule_destroy_fd_instance(fd, true);
+ NET_EPOCH_EXIT(et);
+ }
+
+ CURVNET_RESTORE();
+}
+
+/*
+ * Finds algo by name/family.
+ * Returns referenced algo or NULL.
+ */
+static struct fib_lookup_module *
+fib_find_algo(const char *algo_name, int family)
+{
+ struct fib_lookup_module *flm;
+
+ FIB_MOD_LOCK();
+ TAILQ_FOREACH(flm, &all_algo_list, entries) {
+ if ((strcmp(flm->flm_name, algo_name) == 0) &&
+ (family == flm->flm_family)) {
+ flm->flm_refcount++;
+ FIB_MOD_UNLOCK();
+ return (flm);
+ }
+ }
+ FIB_MOD_UNLOCK();
+
+ return (NULL);
+}
+
+static void
+fib_unref_algo(struct fib_lookup_module *flm)
+{
+
+ FIB_MOD_LOCK();
+ flm->flm_refcount--;
+ FIB_MOD_UNLOCK();
+}
+
+static int
+set_fib_algo(uint32_t fibnum, int family, struct sysctl_oid *oidp, struct sysctl_req *req)
+{
+ struct fib_lookup_module *flm = NULL;
+ struct fib_data *fd = NULL;
+ char old_algo_name[32], algo_name[32];
+ struct rib_head *rh = NULL;
+ enum flm_op_result result;
+ int error;
+
+ /* Fetch current algo/rib for af/family */
+ FIB_MOD_LOCK();
+ TAILQ_FOREACH(fd, &V_fib_data_list, entries) {
+ if ((fd->fd_family == family) && (fd->fd_fibnum == fibnum))
+ break;
+ }
+ if (fd == NULL) {
+ FIB_MOD_UNLOCK();
+ return (ENOENT);
+ }
+ rh = fd->fd_rh;
+ strlcpy(old_algo_name, fd->fd_flm->flm_name,
+ sizeof(old_algo_name));
+ FIB_MOD_UNLOCK();
+
+ 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);
+
+ /* New algorithm name is different */
+ flm = fib_find_algo(algo_name, family);
+ if (flm == NULL) {
+ RH_PRINTF(LOG_INFO, rh, "unable to find algo %s", algo_name);
+ return (ESRCH);
+ }
+
+ fd = NULL;
+ result = setup_fd_instance(flm, rh, NULL, &fd, true);
+ fib_unref_algo(flm);
+ if (result != FLM_SUCCESS)
+ return (EINVAL);
+
+ /* Disable automated jumping between algos */
+ FIB_MOD_LOCK();
+ set_algo_fixed(rh);
+ FIB_MOD_UNLOCK();
+ /* Remove old instance(s) */
+ fib_cleanup_algo(rh, true, false);
+
+ /* Drain cb so user can unload the module after userret if so desired */
+ epoch_drain_callbacks(net_epoch_preempt);
+
+ return (0);
+}
+
+#ifdef INET
+static int
+set_algo_inet_sysctl_handler(SYSCTL_HANDLER_ARGS)
+{
+
+ return (set_fib_algo(RT_DEFAULT_FIB, AF_INET, oidp, req));
+}
+SYSCTL_PROC(_net_route_algo_inet, OID_AUTO, algo,
+ CTLTYPE_STRING | CTLFLAG_RW | CTLFLAG_MPSAFE, NULL, 0,
+ set_algo_inet_sysctl_handler, "A", "Set IPv4 lookup algo");
+#endif
+
+#ifdef INET6
+static int
+set_algo_inet6_sysctl_handler(SYSCTL_HANDLER_ARGS)
+{
+
+ return (set_fib_algo(RT_DEFAULT_FIB, AF_INET6, oidp, req));
+}
+SYSCTL_PROC(_net_route_algo_inet6, OID_AUTO, algo,
+ CTLTYPE_STRING | CTLFLAG_RW | CTLFLAG_MPSAFE, NULL, 0,
+ set_algo_inet6_sysctl_handler, "A", "Set IPv6 lookup algo");
+#endif
+
+static void
+destroy_fdh_epoch(epoch_context_t ctx)
+{
+ struct fib_dp_header *fdh;
+
+ fdh = __containerof(ctx, struct fib_dp_header, fdh_epoch_ctx);
+ free(fdh, M_RTABLE);
+}
+
+static struct fib_dp_header *
+alloc_fib_dp_array(uint32_t num_tables, bool waitok)
+{
+ size_t sz;
+ struct fib_dp_header *fdh;
+
+ sz = sizeof(struct fib_dp_header);
+ sz += sizeof(struct fib_dp) * num_tables;
+ fdh = malloc(sz, M_RTABLE, (waitok ? M_WAITOK : M_NOWAIT) | M_ZERO);
+ if (fdh != NULL)
+ fdh->fdh_num_tables = num_tables;
+ return (fdh);
+}
+
+static struct fib_dp_header *
+get_fib_dp_header(struct fib_dp *dp)
+{
+
+ return (__containerof((void *)dp, struct fib_dp_header, fdh_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_fdh, *old_fdh;
+
+ NET_EPOCH_ASSERT();
+
+ FD_PRINTF(LOG_DEBUG, fd, "[vnet %p] replace with f:%p arg:%p",
+ curvnet, fd->fd_dp.f, fd->fd_dp.arg);
+
+ FIB_MOD_LOCK();
+ old_fdh = get_fib_dp_header(*pdp);
+ new_fdh = alloc_fib_dp_array(old_fdh->fdh_num_tables, false);
+ FD_PRINTF(LOG_DEBUG, fd, "OLD FDH: %p NEW FDH: %p", old_fdh, new_fdh);
+ if (new_fdh == NULL) {
+ FIB_MOD_UNLOCK();
+ FD_PRINTF(LOG_WARNING, fd, "error attaching datapath");
+ return (FLM_REBUILD);
+ }
+
+ memcpy(&new_fdh->fdh_idx[0], &old_fdh->fdh_idx[0],
+ old_fdh->fdh_num_tables * sizeof(struct fib_dp));
+ /* Update relevant data structure for @fd */
+ new_fdh->fdh_idx[fd->fd_fibnum] = fd->fd_dp;
+
+ /* Ensure memcpy() writes have completed */
+ atomic_thread_fence_rel();
+ /* Set new datapath pointer */
+ *pdp = &new_fdh->fdh_idx[0];
+ FIB_MOD_UNLOCK();
+ FD_PRINTF(LOG_DEBUG, fd, "update %p -> %p", old_fdh, new_fdh);
+
+ epoch_call(net_epoch_preempt, destroy_fdh_epoch,
+ &old_fdh->fdh_epoch_ctx);
+
+ return (FLM_SUCCESS);
+}
+
+static struct fib_dp **
+get_family_dp_ptr(int family)
+{
+ switch (family) {
+ case AF_INET:
+ return (&V_inet_dp);
+ case AF_INET6:
+ return (&V_inet6_dp);
+ }
+ return (NULL);
+}
+
+/*
+ * Make datapath use fib instance @fd
+ */
+static enum flm_op_result
+attach_datapath(struct fib_data *fd)
+{
+ struct fib_dp **pdp;
+
+ pdp = get_family_dp_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);
+
+ FIB_MOD_LOCK();
+ if (*pdp != NULL) {
+ old_fdh = get_fib_dp_header(*pdp);
+ memcpy(&new_fdh->fdh_idx[0], &old_fdh->fdh_idx[0],
+ old_fdh->fdh_num_tables * sizeof(struct fib_dp));
+ }
+
+ /* Wait till all writes completed */
+ atomic_thread_fence_rel();
+
+ *pdp = &new_fdh->fdh_idx[0];
+ FIB_MOD_UNLOCK();
+
+ if (old_fdh != NULL)
+ epoch_call(net_epoch_preempt, destroy_fdh_epoch,
+ &old_fdh->fdh_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)
+{
+
+#ifdef INET
+ grow_rtables_family(get_family_dp_ptr(AF_INET), new_num_tables);
+#endif
+#ifdef INET6
+ grow_rtables_family(get_family_dp_ptr(AF_INET6), new_num_tables);
+#endif
+}
+
+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
+}
+
+/*
+ * Accessor to get rib instance @fd is attached to.
+ */
+struct rib_head *
+fib_get_rh(struct fib_data *fd)
+{
+
+ return (fd->fd_rh);
+}
+
+/*
+ * Accessor to export idx->nhop array
+ */
+struct nhop_object **
+fib_get_nhop_array(struct fib_data *fd)
+{
+
+ return (fd->nh_idx);
+}
+
+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)
+{
+
+ return (get_nhop_idx(nh));
+}
+
+static bool
+is_idx_free(struct fib_data *fd, uint32_t index)
+{
+
+ return (fd->nh_ref_table->refcnt[index] == 0);
+}
+
+static uint32_t
+fib_ref_nhop(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 (is_idx_free(fd, idx)) {
+ nhop_ref_any(nh);
+ fd->nh_idx[idx] = nh;
+ fd->nh_ref_table->count++;
+ FD_PRINTF(LOG_DEBUG, 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_TEMP);
+}
+
+/*
+ * Delays nexthop refcount release.
+ * Datapath may have the datastructures not updated yet, so the old
+ * nexthop may still be returned till the end of current epoch. Delay
+ * refcount removal, as we may be removing the last instance, which will
+ * trigger nexthop deletion, rendering returned nexthop invalid.
+ */
+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_TEMP, 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 can be referenced.
+ */
+ FD_PRINTF(LOG_ERR, fd, "unable to schedule nhop %p deletion", nh);
+ }
+}
+
+static void
+fib_unref_nhop(struct fib_data *fd, struct nhop_object *nh)
+{
+ uint32_t idx = get_nhop_idx(nh);
+
+ KASSERT((idx < fd->number_nhops), ("invalid nhop index"));
+ KASSERT((nh == fd->nh_idx[idx]), ("index table contains whong nh"));
+
+ fd->nh_ref_table->refcnt[idx]--;
+ if (fd->nh_ref_table->refcnt[idx] == 0) {
+ FD_PRINTF(LOG_DEBUG, fd, " FREE nhop %d %p", idx, fd->nh_idx[idx]);
+ fib_schedule_release_nhop(fd, fd->nh_idx[idx]);
+ }
+}
+
+static void
+set_algo_fixed(struct rib_head *rh)
+{
+ switch (rh->rib_family) {
+#ifdef INET
+ case AF_INET:
+ algo_fixed_inet = true;
+ break;
+#endif
+#ifdef INET6
+ case AF_INET6:
+ algo_fixed_inet6 = true;
+ break;
+#endif
+ }
+}
+
+static bool
+is_algo_fixed(struct rib_head *rh)
+{
+
+ switch (rh->rib_family) {
+#ifdef INET
+ case AF_INET:
+ return (algo_fixed_inet);
+#endif
+#ifdef INET6
+ case AF_INET6:
+ return (algo_fixed_inet6);
+#endif
+ }
+ return (false);
+}
+
+/*
+ * Runs the check on what would be the best algo for rib @rh, assuming
+ * that the current algo is the one specified by @orig_flm. Note that
+ * it can be NULL for initial selection.
+ *
+ * Returns referenced new algo or NULL if the current one is the best.
+ */
+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);
+
+ FIB_MOD_LOCK();
+ if (is_algo_fixed(rh)) {
+ FIB_MOD_UNLOCK();
+ return (NULL);
+ }
+
+ 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) {
+ if (!flm_error_check(flm, rh->rib_fibnum)) {
+ best_preference = preference;
+ best_flm = flm;
+ }
+ }
+ if (flm == orig_flm)
+ curr_preference = preference;
+ }
+ if ((best_flm != NULL) && (curr_preference + BEST_DIFF_PERCENT < best_preference))
+ best_flm->flm_refcount++;
+ else
+ best_flm = NULL;
+ FIB_MOD_UNLOCK();
+
+ RH_PRINTF(LOG_DEBUG, 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 : (orig_flm ? orig_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;
+ int error = 0;
+
+ flm = fib_check_best_algo(rh, NULL);
+ if (flm == NULL) {
+ RH_PRINTF(LOG_CRIT, rh, "no algo selected");
+ return (ENOENT);
+ }
+ RH_PRINTF(LOG_INFO, rh, "selected algo %s", flm->flm_name);
+
+ result = setup_fd_instance(flm, rh, NULL, &fd, false);
+ RH_PRINTF(LOG_DEBUG, rh, "result=%d fd=%p", result, fd);
+ if (result == FLM_SUCCESS) {
+
+ /*
+ * Attach datapath directly to avoid multiple reallocations
+ * during fib growth
+ */
+ struct fib_dp_header *fdp;
+ struct fib_dp **pdp;
+
+ pdp = get_family_dp_ptr(rh->rib_family);
+ if (pdp != NULL) {
+ fdp = get_fib_dp_header(*pdp);
+ fdp->fdh_idx[fd->fd_fibnum] = fd->fd_dp;
+ FD_PRINTF(LOG_INFO, fd, "datapath attached");
+ }
+ } else {
+ error = EINVAL;
+ RH_PRINTF(LOG_CRIT, rh, "unable to setup algo %s", flm->flm_name);
+ }
+
+ fib_unref_algo(flm);
+
+ return (error);
+}
+
+/*
+ * Registers fib lookup module within the subsystem.
+ */
+int
+fib_module_register(struct fib_lookup_module *flm)
+{
+
+ FIB_MOD_LOCK();
+ ALGO_PRINTF("attaching %s to %s", flm->flm_name,
+ print_family(flm->flm_family));
+ TAILQ_INSERT_TAIL(&all_algo_list, flm, entries);
+ FIB_MOD_UNLOCK();
+
+ return (0);
+}
+
+/*
+ * Tries to unregister fib lookup module.
+ *
+ * Returns 0 on success, EBUSY if module is still used
+ * by some of the tables.
+ */
+int
+fib_module_unregister(struct fib_lookup_module *flm)
+{
+
+ FIB_MOD_LOCK();
+ if (flm->flm_refcount > 0) {
+ FIB_MOD_UNLOCK();
+ return (EBUSY);
+ }
+ fib_error_clear_flm(flm);
+ ALGO_PRINTF("detaching %s from %s", flm->flm_name,
+ print_family(flm->flm_family));
+ TAILQ_REMOVE(&all_algo_list, flm, entries);
+ FIB_MOD_UNLOCK();
+
+ return (0);
+}
+
+void
+vnet_fib_init(void)
+{
+
+ TAILQ_INIT(&V_fib_data_list);
+}
+
+void
+vnet_fib_destroy(void)
+{
+
+ FIB_MOD_LOCK();
+ fib_error_clear();
+ FIB_MOD_UNLOCK();
+}
+
+static void
+fib_init(void)
+{
+
+ mtx_init(&fib_mtx, "algo list mutex", NULL, MTX_DEF);
+ TAILQ_INIT(&all_algo_list);
+}
+SYSINIT(fib_init, SI_SUB_PROTO_DOMAIN, SI_ORDER_SECOND, fib_init, NULL);
+