sys/net/route/fib_algo.c

   1 /*-
   2  * SPDX-License-Identifier: BSD-2-Clause-FreeBSD
   3  *
   4  * Copyright (c) 2020 Alexander V. Chernikov
   5  *
   6  * Redistribution and use in source and binary forms, with or without
   7  * modification, are permitted provided that the following conditions
   8  * are met:
   9  * 1. Redistributions of source code must retain the above copyright
  10  *    notice, this list of conditions and the following disclaimer.
  11  * 2. Redistributions in binary form must reproduce the above copyright
  12  *    notice, this list of conditions and the following disclaimer in the
  13  *    documentation and/or other materials provided with the distribution.
  14  *
  15  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
  16  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  17  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  18  * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
  19  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  20  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  21  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  22  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  23  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  24  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  25  * SUCH DAMAGE.
  26  */
  27
  28 #include <sys/cdefs.h>
  29 __FBSDID("$FreeBSD$");
  30 #include "opt_inet.h"
  31 #include "opt_inet6.h"
  32 #include "opt_route.h"
  33
  34 #include <sys/param.h>
  35 #include <sys/eventhandler.h>
  36 #include <sys/kernel.h>
  37 #include <sys/sbuf.h>
  38 #include <sys/lock.h>
  39 #include <sys/rmlock.h>
  40 #include <sys/malloc.h>
  41 #include <sys/mbuf.h>
  42 #include <sys/module.h>
  43 #include <sys/kernel.h>
  44 #include <sys/priv.h>
  45 #include <sys/proc.h>
  46 #include <sys/socket.h>
  47 #include <sys/socketvar.h>
  48 #include <sys/sysctl.h>
  49 #include <sys/syslog.h>
  50 #include <sys/queue.h>
  51 #include <net/vnet.h>
  52
  53 #include <net/if.h>
  54 #include <net/if_var.h>
  55
  56 #include <netinet/in.h>
  57 #include <netinet/in_var.h>
  58 #include <netinet/ip.h>
  59 #include <netinet/ip_var.h>
  60 #ifdef INET6
  61 #include <netinet/ip6.h>
  62 #include <netinet6/ip6_var.h>
  63 #endif
  64
  65 #include <net/route.h>
  66 #include <net/route/nhop.h>
  67 #include <net/route/route_ctl.h>
  68 #include <net/route/route_var.h>
  69 #include <net/route/fib_algo.h>
  70
  71 #include <machine/stdarg.h>
  72
  73 /*
  74  * Fib lookup framework.
  75  *
  76  * This framework enables accelerated longest-prefix-match lookups for the
  77  *  routing tables by adding the ability to dynamically attach/detach lookup
  78  *  algorithms implementation to/from the datapath.
  79  *
  80  * flm - fib lookup modules - implementation of particular lookup algorithm
  81  * fd - fib data - instance of an flm bound to specific routing table
  82  *
  83  * This file provides main framework functionality.
  84  *
  85  * The following are the features provided by the framework
  86  *
  87  * 1) nexhops abstraction -> provides transparent referencing, indexing
  88  *   and efficient idx->ptr mappings for nexthop and nexthop groups.
  89  * 2) Routing table synchronisation
  90  * 3) dataplane attachment points
  91  * 4) automatic algorithm selection based on the provided preference.
  92  *
  93  *
  94  * DATAPATH
  95  * For each supported address family, there is a an allocated array of fib_dp
  96  *  structures, indexed by fib number. Each array entry contains callback function
  97  *  and its argument. This function will be called with a family-specific lookup key,
  98  *  scope and provided argument. This array gets re-created every time when new algo
  99  *  instance gets created. Please take a look at the replace_rtables_family() function
 100  *  for more details.
 101  *
 102  */
 103
 104 SYSCTL_DECL(_net_route);
 105 SYSCTL_NODE(_net_route, OID_AUTO, algo, CTLFLAG_RW | CTLFLAG_MPSAFE, 0,
 106     "Fib algorithm lookups");
 107
 108 /* Algorithm sync policy */
 109
 110 /* Time interval to bucket updates */
 111 VNET_DEFINE(unsigned int, bucket_time_ms) = 50;
 112 #define V_bucket_time_ms        VNET(bucket_time_ms)
 113 SYSCTL_UINT(_net_route_algo, OID_AUTO, bucket_time_ms, CTLFLAG_RW | CTLFLAG_VNET,
 114     &VNET_NAME(bucket_time_ms), 0, "Time interval to calculate update rate");
 115
 116 /* Minimum update rate to delay sync */
 117 VNET_DEFINE(unsigned int, bucket_change_threshold_rate) = 500;
 118 #define V_bucket_change_threshold_rate  VNET(bucket_change_threshold_rate)
 119 SYSCTL_UINT(_net_route_algo, OID_AUTO, bucket_change_threshold_rate, CTLFLAG_RW | CTLFLAG_VNET,
 120     &VNET_NAME(bucket_change_threshold_rate), 0, "Minimum update rate to delay sync");
 121
 122 /* Max allowed delay to sync */
 123 VNET_DEFINE(unsigned int, fib_max_sync_delay_ms) = 1000;
 124 #define V_fib_max_sync_delay_ms VNET(fib_max_sync_delay_ms)
 125 SYSCTL_UINT(_net_route_algo, OID_AUTO, fib_max_sync_delay_ms, CTLFLAG_RW | CTLFLAG_VNET,
 126     &VNET_NAME(fib_max_sync_delay_ms), 0, "Maximum time to delay sync (ms)");
 127
 128
 129 #ifdef INET6
 130 VNET_DEFINE_STATIC(bool, algo_fixed_inet6) = false;
 131 #define V_algo_fixed_inet6      VNET(algo_fixed_inet6)
 132 SYSCTL_NODE(_net_route_algo, OID_AUTO, inet6, CTLFLAG_RW | CTLFLAG_MPSAFE, 0,
 133     "IPv6 longest prefix match lookups");
 134 #endif
 135 #ifdef INET
 136 VNET_DEFINE_STATIC(bool, algo_fixed_inet) = false;
 137 #define V_algo_fixed_inet       VNET(algo_fixed_inet)
 138 SYSCTL_NODE(_net_route_algo, OID_AUTO, inet, CTLFLAG_RW | CTLFLAG_MPSAFE, 0,
 139     "IPv4 longest prefix match lookups");
 140 #endif
 141
 142 /* Fib instance counter */
 143 static uint32_t fib_gen = 0;
 144
 145 struct nhop_ref_table {
 146         uint32_t                count;
 147         int32_t                 refcnt[0];
 148 };
 149
 150 enum fib_callout_action {
 151         FDA_NONE,       /* No callout scheduled */
 152         FDA_REBUILD,    /* Asks to rebuild algo instance */
 153         FDA_EVAL,       /* Asks to evaluate if the current algo is still be best */
 154         FDA_BATCH,      /* Asks to submit batch of updates to the algo */
 155 };
 156
 157 struct fib_sync_status {
 158         struct timeval          diverge_time;   /* ts when diverged */
 159         uint32_t                num_changes;    /* number of changes since sync */
 160         uint32_t                bucket_changes; /* num changes within the current bucket */
 161         uint64_t                bucket_id;      /* 50ms bucket # */
 162         struct fib_change_queue fd_change_queue;/* list of scheduled entries */
 163 };
 164
 165 /*
 166  * Data structure for the fib lookup instance tied to the particular rib.
 167  */
 168 struct fib_data {
 169         uint32_t                number_nhops;   /* current # of nhops */
 170         uint8_t                 hit_nhops;      /* true if out of nhop limit */
 171         uint8_t                 init_done;      /* true if init is competed */
 172         uint32_t                fd_dead:1;      /* Scheduled for deletion */
 173         uint32_t                fd_linked:1;    /* true if linked */
 174         uint32_t                fd_need_rebuild:1;      /* true if rebuild scheduled */
 175         uint32_t                fd_batch:1;     /* true if batched notification scheduled */
 176         uint8_t                 fd_family;      /* family */
 177         uint32_t                fd_fibnum;      /* fibnum */
 178         uint32_t                fd_failed_rebuilds;     /* stat: failed rebuilds */
 179         uint32_t                fd_gen;         /* instance gen# */
 180         struct callout          fd_callout;     /* rebuild callout */
 181         enum fib_callout_action fd_callout_action;      /* Callout action to take */
 182         void                    *fd_algo_data;  /* algorithm data */
 183         struct nhop_object      **nh_idx;       /* nhop idx->ptr array */
 184         struct nhop_ref_table   *nh_ref_table;  /* array with # of nhop references */
 185         struct rib_head         *fd_rh;         /* RIB table we're attached to */
 186         struct rib_subscription *fd_rs;         /* storing table subscription */
 187         struct fib_dp           fd_dp;          /* fib datapath data */
 188         struct vnet             *fd_vnet;       /* vnet fib belongs to */
 189         struct epoch_context    fd_epoch_ctx;   /* epoch context for deletion */
 190         struct fib_lookup_module        *fd_flm;/* pointer to the lookup module */
 191         struct fib_sync_status  fd_ss;          /* State relevant to the rib sync  */
 192         uint32_t                fd_num_changes; /* number of changes since last callout */
 193         TAILQ_ENTRY(fib_data)   entries;        /* list of all fds in vnet */
 194 };
 195
 196 static bool rebuild_fd(struct fib_data *fd, const char *reason);
 197 static bool rebuild_fd_flm(struct fib_data *fd, struct fib_lookup_module *flm_new);
 198 static void handle_fd_callout(void *_data);
 199 static void destroy_fd_instance_epoch(epoch_context_t ctx);
 200 static bool is_idx_free(struct fib_data *fd, uint32_t index);
 201 static void set_algo_fixed(struct rib_head *rh);
 202 static bool is_algo_fixed(struct rib_head *rh);
 203
 204 static uint32_t fib_ref_nhop(struct fib_data *fd, struct nhop_object *nh);
 205 static void fib_unref_nhop(struct fib_data *fd, struct nhop_object *nh);
 206
 207 static struct fib_lookup_module *fib_check_best_algo(struct rib_head *rh,
 208     struct fib_lookup_module *orig_flm);
 209 static void fib_unref_algo(struct fib_lookup_module *flm);
 210 static bool flm_error_check(const struct fib_lookup_module *flm, uint32_t fibnum);
 211
 212 struct mtx fib_mtx;
 213 #define FIB_MOD_LOCK()          mtx_lock(&fib_mtx)
 214 #define FIB_MOD_UNLOCK()        mtx_unlock(&fib_mtx)
 215 #define FIB_MOD_LOCK_ASSERT()   mtx_assert(&fib_mtx, MA_OWNED)
 216
 217 MTX_SYSINIT(fib_mtx, &fib_mtx, "algo list mutex", MTX_DEF);
 218
 219 /* Algorithm has to be this percent better than the current to switch */
 220 #define BEST_DIFF_PERCENT       (5 * 256 / 100)
 221 /* Schedule algo re-evaluation X seconds after a change */
 222 #define ALGO_EVAL_DELAY_MS      30000
 223 /* Force algo re-evaluation after X changes */
 224 #define ALGO_EVAL_NUM_ROUTES    100
 225 /* Try to setup algorithm X times */
 226 #define FIB_MAX_TRIES           32
 227 /* Max amount of supported nexthops */
 228 #define FIB_MAX_NHOPS           262144
 229 #define FIB_CALLOUT_DELAY_MS    50
 230
 231
 232 /* Debug */
 233 static int flm_debug_level = LOG_NOTICE;
 234 SYSCTL_INT(_net_route_algo, OID_AUTO, debug_level, CTLFLAG_RW | CTLFLAG_RWTUN,
 235     &flm_debug_level, 0, "debuglevel");
 236 #define FLM_MAX_DEBUG_LEVEL     LOG_DEBUG
 237 #ifndef LOG_DEBUG2
 238 #define LOG_DEBUG2      8
 239 #endif
 240
 241 #define _PASS_MSG(_l)   (flm_debug_level >= (_l))
 242 #define ALGO_PRINTF(_fmt, ...)  printf("[fib_algo] %s: " _fmt "\n", __func__, ##__VA_ARGS__)
 243 #define _ALGO_PRINTF(_fib, _fam, _aname, _gen, _func, _fmt, ...) \
 244     printf("[fib_algo] %s.%u (%s#%u) %s: " _fmt "\n",\
 245     print_family(_fam), _fib, _aname, _gen, _func, ## __VA_ARGS__)
 246 #define _RH_PRINTF(_fib, _fam, _func, _fmt, ...) \
 247     printf("[fib_algo] %s.%u %s: " _fmt "\n", print_family(_fam), _fib, _func, ## __VA_ARGS__)
 248 #define RH_PRINTF(_l, _rh, _fmt, ...)   if (_PASS_MSG(_l)) {    \
 249     _RH_PRINTF(_rh->rib_fibnum, _rh->rib_family, __func__, _fmt, ## __VA_ARGS__);\
 250 }
 251 #define FD_PRINTF(_l, _fd, _fmt, ...)   FD_PRINTF_##_l(_l, _fd, _fmt, ## __VA_ARGS__)
 252 #define _FD_PRINTF(_l, _fd, _fmt, ...)  if (_PASS_MSG(_l)) {            \
 253     _ALGO_PRINTF(_fd->fd_fibnum, _fd->fd_family, _fd->fd_flm->flm_name, \
 254     _fd->fd_gen, __func__, _fmt, ## __VA_ARGS__);                       \
 255 }
 256 #if FLM_MAX_DEBUG_LEVEL>=LOG_DEBUG2
 257 #define FD_PRINTF_LOG_DEBUG2    _FD_PRINTF
 258 #else
 259 #define FD_PRINTF_LOG_DEBUG2(_l, _fd, _fmt, ...)
 260 #endif
 261 #if FLM_MAX_DEBUG_LEVEL>=LOG_DEBUG
 262 #define FD_PRINTF_LOG_DEBUG     _FD_PRINTF
 263 #else
 264 #define FD_PRINTF_LOG_DEBUG()
 265 #endif
 266 #if FLM_MAX_DEBUG_LEVEL>=LOG_INFO
 267 #define FD_PRINTF_LOG_INFO      _FD_PRINTF
 268 #else
 269 #define FD_PRINTF_LOG_INFO()
 270 #endif
 271 #define FD_PRINTF_LOG_NOTICE    _FD_PRINTF
 272 #define FD_PRINTF_LOG_ERR       _FD_PRINTF
 273 #define FD_PRINTF_LOG_WARNING   _FD_PRINTF
 274
 275
 276 /* List of all registered lookup algorithms */
 277 static TAILQ_HEAD(, fib_lookup_module) all_algo_list = TAILQ_HEAD_INITIALIZER(all_algo_list);
 278
 279 /* List of all fib lookup instances in the vnet */
 280 VNET_DEFINE_STATIC(TAILQ_HEAD(fib_data_head, fib_data), fib_data_list);
 281 #define V_fib_data_list VNET(fib_data_list)
 282
 283 /* Datastructure for storing non-transient fib lookup module failures */
 284 struct fib_error {
 285         int                             fe_family;
 286         uint32_t                        fe_fibnum;      /* failed rtable */
 287         struct fib_lookup_module        *fe_flm;        /* failed module */
 288         TAILQ_ENTRY(fib_error)          entries;/* list of all errored entries */
 289 };
 290 VNET_DEFINE_STATIC(TAILQ_HEAD(fib_error_head, fib_error), fib_error_list);
 291 #define V_fib_error_list VNET(fib_error_list)
 292
 293 /* Per-family array of fibnum -> {func, arg} mappings used in datapath */
 294 struct fib_dp_header {
 295         struct epoch_context    fdh_epoch_ctx;
 296         uint32_t                fdh_num_tables;
 297         struct fib_dp           fdh_idx[0];
 298 };
 299
 300 /*
 301  * Tries to add new non-transient algorithm error to the list of
 302  *  errors.
 303  * Returns true on success.
 304  */
 305 static bool
 306 flm_error_add(struct fib_lookup_module *flm, uint32_t fibnum)
 307 {
 308         struct fib_error *fe;
 309
 310         fe = malloc(sizeof(struct fib_error), M_TEMP, M_NOWAIT | M_ZERO);
 311         if (fe == NULL)
 312                 return (false);
 313         fe->fe_flm = flm;
 314         fe->fe_family = flm->flm_family;
 315         fe->fe_fibnum = fibnum;
 316
 317         FIB_MOD_LOCK();
 318         /* Avoid duplicates by checking if error already exists first */
 319         if (flm_error_check(flm, fibnum)) {
 320                 FIB_MOD_UNLOCK();
 321                 free(fe, M_TEMP);
 322                 return (true);
 323         }
 324         TAILQ_INSERT_HEAD(&V_fib_error_list, fe, entries);
 325         FIB_MOD_UNLOCK();
 326
 327         return (true);
 328 }
 329
 330 /*
 331  * True if non-transient error has been registered for @flm in @fibnum.
 332  */
 333 static bool
 334 flm_error_check(const struct fib_lookup_module *flm, uint32_t fibnum)
 335 {
 336         const struct fib_error *fe;
 337
 338         TAILQ_FOREACH(fe, &V_fib_error_list, entries) {
 339                 if ((fe->fe_flm == flm) && (fe->fe_fibnum == fibnum))
 340                         return (true);
 341         }
 342
 343         return (false);
 344 }
 345
 346 /*
 347  * Clear all errors of algo specified by @flm.
 348  */
 349 static void
 350 fib_error_clear_flm(struct fib_lookup_module *flm)
 351 {
 352         struct fib_error *fe, *fe_tmp;
 353
 354         FIB_MOD_LOCK_ASSERT();
 355
 356         TAILQ_FOREACH_SAFE(fe, &V_fib_error_list, entries, fe_tmp) {
 357                 if (fe->fe_flm == flm) {
 358                         TAILQ_REMOVE(&V_fib_error_list, fe, entries);
 359                         free(fe, M_TEMP);
 360                 }
 361         }
 362 }
 363
 364 /*
 365  * Clears all errors in current VNET.
 366  */
 367 static void
 368 fib_error_clear()
 369 {
 370         struct fib_error *fe, *fe_tmp;
 371
 372         FIB_MOD_LOCK_ASSERT();
 373
 374         TAILQ_FOREACH_SAFE(fe, &V_fib_error_list, entries, fe_tmp) {
 375                 TAILQ_REMOVE(&V_fib_error_list, fe, entries);
 376                 free(fe, M_TEMP);
 377         }
 378 }
 379
 380 static const char *
 381 print_op_result(enum flm_op_result result)
 382 {
 383         switch (result) {
 384         case FLM_SUCCESS:
 385                 return "success";
 386         case FLM_REBUILD:
 387                 return "rebuild";
 388         case FLM_BATCH:
 389                 return "batch";
 390         case FLM_ERROR:
 391                 return "error";
 392         }
 393
 394         return "unknown";
 395 }
 396
 397 static const char *
 398 print_family(int family)
 399 {
 400
 401         if (family == AF_INET)
 402                 return ("inet");
 403         else if (family == AF_INET6)
 404                 return ("inet6");
 405         else
 406                 return ("unknown");
 407 }
 408
 409 /*
 410  * Debug function used by lookup algorithms.
 411  * Outputs message denoted by @fmt, prepended by "[fib_algo] inetX.Y (algo) "
 412  */
 413 void
 414 fib_printf(int level, struct fib_data *fd, const char *func, char *fmt, ...)
 415 {
 416         char buf[128];
 417         va_list ap;
 418
 419         if (level > flm_debug_level)
 420                 return;
 421
 422         va_start(ap, fmt);
 423         vsnprintf(buf, sizeof(buf), fmt, ap);
 424         va_end(ap);
 425
 426         _ALGO_PRINTF(fd->fd_fibnum, fd->fd_family, fd->fd_flm->flm_name,
 427             fd->fd_gen, func, "%s", buf);
 428 }
 429
 430 /*
 431  * Outputs list of algorithms supported by the provided address family.
 432  */
 433 static int
 434 print_algos_sysctl(struct sysctl_req *req, int family)
 435 {
 436         struct fib_lookup_module *flm;
 437         struct sbuf sbuf;
 438         int error, count = 0;
 439
 440         error = sysctl_wire_old_buffer(req, 0);
 441         if (error == 0) {
 442                 sbuf_new_for_sysctl(&sbuf, NULL, 512, req);
 443                 TAILQ_FOREACH(flm, &all_algo_list, entries) {
 444                         if (flm->flm_family == family) {
 445                                 if (count++ > 0)
 446                                         sbuf_cat(&sbuf, ", ");
 447                                 sbuf_cat(&sbuf, flm->flm_name);
 448                         }
 449                 }
 450                 error = sbuf_finish(&sbuf);
 451                 sbuf_delete(&sbuf);
 452         }
 453         return (error);
 454 }
 455
 456 #ifdef INET6
 457 static int
 458 print_algos_sysctl_inet6(SYSCTL_HANDLER_ARGS)
 459 {
 460
 461         return (print_algos_sysctl(req, AF_INET6));
 462 }
 463 SYSCTL_PROC(_net_route_algo_inet6, OID_AUTO, algo_list,
 464     CTLTYPE_STRING | CTLFLAG_RD | CTLFLAG_MPSAFE, NULL, 0,
 465     print_algos_sysctl_inet6, "A", "List of IPv6 lookup algorithms");
 466 #endif
 467
 468 #ifdef INET
 469 static int
 470 print_algos_sysctl_inet(SYSCTL_HANDLER_ARGS)
 471 {
 472
 473         return (print_algos_sysctl(req, AF_INET));
 474 }
 475 SYSCTL_PROC(_net_route_algo_inet, OID_AUTO, algo_list,
 476     CTLTYPE_STRING | CTLFLAG_RD | CTLFLAG_MPSAFE, NULL, 0,
 477     print_algos_sysctl_inet, "A", "List of IPv4 lookup algorithms");
 478 #endif
 479
 480 /*
 481  * Calculate delay between repeated failures.
 482  * Returns current delay in milliseconds.
 483  */
 484 static uint32_t
 485 callout_calc_delay_ms(struct fib_data *fd)
 486 {
 487         uint32_t shift;
 488
 489         if (fd->fd_failed_rebuilds > 10)
 490                 shift = 10;
 491         else
 492                 shift = fd->fd_failed_rebuilds;
 493
 494         return ((1 << shift) * FIB_CALLOUT_DELAY_MS);
 495 }
 496
 497 static void
 498 schedule_callout(struct fib_data *fd, enum fib_callout_action action, int delay_ms)
 499 {
 500
 501         FD_PRINTF(LOG_DEBUG, fd, "delay=%d action=%d", delay_ms, action);
 502         fd->fd_callout_action = action;
 503         callout_reset_sbt(&fd->fd_callout, SBT_1MS * delay_ms, 0,
 504             handle_fd_callout, fd, 0);
 505 }
 506
 507 static void
 508 schedule_fd_rebuild(struct fib_data *fd, const char *reason)
 509 {
 510
 511         RIB_WLOCK_ASSERT(fd->fd_rh);
 512
 513         if (!fd->fd_need_rebuild) {
 514                 fd->fd_need_rebuild = true;
 515                 /* Stop batch updates */
 516                 fd->fd_batch = false;
 517
 518                 /*
 519                  * Potentially re-schedules pending callout
 520                  *  initiated by schedule_algo_eval.
 521                  */
 522                 FD_PRINTF(LOG_INFO, fd, "Scheduling rebuild: %s (failures=%d)",
 523                     reason, fd->fd_failed_rebuilds);
 524                 schedule_callout(fd, FDA_REBUILD, callout_calc_delay_ms(fd));
 525         }
 526 }
 527
 528 static int64_t
 529 get_tv_diff_ms(const struct timeval *old_tv, const struct timeval *new_tv)
 530 {
 531         int64_t diff = 0;
 532
 533         diff = ((int64_t)(new_tv->tv_sec - old_tv->tv_sec)) * 1000;
 534         diff += (new_tv->tv_usec - old_tv->tv_usec) / 1000;
 535
 536         return (diff);
 537 }
 538
 539 static void
 540 add_tv_diff_ms(struct timeval *tv, int ms)
 541 {
 542         tv->tv_sec += ms / 1000;
 543         ms = ms % 1000;
 544         if (ms * 1000 + tv->tv_usec < 1000000)
 545                 tv->tv_usec += ms * 1000;
 546         else {
 547                 tv->tv_sec += 1;
 548                 tv->tv_usec = ms * 1000 + tv->tv_usec - 1000000;
 549         }
 550 }
 551
 552 /*
 553  * Marks the time when algo state diverges from the rib state.
 554  */
 555 static void
 556 mark_diverge_time(struct fib_data *fd)
 557 {
 558         struct fib_sync_status *fd_ss = &fd->fd_ss;
 559
 560         getmicrouptime(&fd_ss->diverge_time);
 561         fd_ss->bucket_id = 0;
 562         fd_ss->bucket_changes = 0;
 563 }
 564
 565 /*
 566  * Calculates and updates the next algorithm sync time, based on the current activity.
 567  *
 568  * The intent is to provide reasonable balance between the update
 569  *  latency and efficient batching when changing large amount of routes.
 570  *
 571  * High-level algorithm looks the following:
 572  * 1) all changes are bucketed in 50ms intervals
 573  * 2) If amount of changes within the bucket is greater than the threshold,
 574  *   the update gets delayed, up to maximum delay threshold.
 575  */
 576 static void
 577 update_rebuild_delay(struct fib_data *fd, enum fib_callout_action action)
 578 {
 579         uint32_t bucket_id, new_delay = 0;
 580         struct timeval tv;
 581
 582         /* Fetch all variables at once to ensure consistent reads */
 583         uint32_t bucket_time_ms = V_bucket_time_ms;
 584         uint32_t threshold_rate = V_bucket_change_threshold_rate;
 585         uint32_t max_delay_ms = V_fib_max_sync_delay_ms;
 586
 587         if (bucket_time_ms == 0)
 588                 bucket_time_ms = 50;
 589         /* calculate per-bucket threshold rate */
 590         threshold_rate = threshold_rate * bucket_time_ms / 1000;
 591
 592         getmicrouptime(&tv);
 593
 594         struct fib_sync_status *fd_ss = &fd->fd_ss;
 595
 596         bucket_id = get_tv_diff_ms(&fd_ss->diverge_time, &tv) / bucket_time_ms;
 597
 598         if (fd_ss->bucket_id == bucket_id) {
 599                 fd_ss->bucket_changes++;
 600                 if (fd_ss->bucket_changes == threshold_rate) {
 601                         new_delay = (bucket_id + 2) * bucket_time_ms;
 602                         if (new_delay <= max_delay_ms) {
 603                                 FD_PRINTF(LOG_DEBUG, fd,
 604                                     "hit threshold of %u routes, delay update,"
 605                                     "bucket: %u, total delay: %u",
 606                                     threshold_rate, bucket_id + 1, new_delay);
 607                         } else {
 608                                 new_delay = 0;
 609                                 FD_PRINTF(LOG_DEBUG, fd,
 610                                     "maximum sync delay (%u ms) reached", max_delay_ms);
 611                         }
 612                 } else if ((bucket_id == 0) && (fd_ss->bucket_changes == 1))
 613                         new_delay = bucket_time_ms;
 614         } else {
 615                 fd_ss->bucket_id = bucket_id;
 616                 fd_ss->bucket_changes = 1;
 617         }
 618
 619         if (new_delay > 0) {
 620                 /* Calculated time has been updated */
 621                 struct timeval new_tv = fd_ss->diverge_time;
 622                 add_tv_diff_ms(&new_tv, new_delay);
 623
 624                 int32_t delay_ms = get_tv_diff_ms(&tv, &new_tv);
 625                 schedule_callout(fd, action, delay_ms);
 626         }
 627 }
 628
 629 static void
 630 update_algo_state(struct fib_data *fd)
 631 {
 632
 633         RIB_WLOCK_ASSERT(fd->fd_rh);
 634
 635         if (fd->fd_batch || fd->fd_need_rebuild) {
 636                 enum fib_callout_action action = fd->fd_need_rebuild ? FDA_REBUILD : FDA_BATCH;
 637                 update_rebuild_delay(fd, action);
 638                 return;
 639         }
 640
 641         if (fd->fd_num_changes++ == 0) {
 642                 /* Start callout to consider switch */
 643                 if (!callout_pending(&fd->fd_callout))
 644                         schedule_callout(fd, FDA_EVAL, ALGO_EVAL_DELAY_MS);
 645         } else if (fd->fd_num_changes == ALGO_EVAL_NUM_ROUTES) {
 646                 /* Reset callout to exec immediately */
 647                 if (fd->fd_callout_action == FDA_EVAL)
 648                         schedule_callout(fd, FDA_EVAL, 1);
 649         }
 650 }
 651
 652 static bool
 653 need_immediate_sync(struct fib_data *fd, struct rib_cmd_info *rc)
 654 {
 655         struct nhop_object *nh;
 656
 657         /* Sync addition/removal of interface routes */
 658         switch (rc->rc_cmd) {
 659         case RTM_ADD:
 660                 nh = rc->rc_nh_new;
 661                 if (!NH_IS_NHGRP(nh) && (!(nh->nh_flags & NHF_GATEWAY)))
 662                         return (true);
 663                 break;
 664         case RTM_DELETE:
 665                 nh = rc->rc_nh_old;
 666                 if (!NH_IS_NHGRP(nh) && (!(nh->nh_flags & NHF_GATEWAY)))
 667                         return (true);
 668                 break;
 669         }
 670
 671         return (false);
 672 }
 673
 674 static bool
 675 apply_rtable_changes(struct fib_data *fd)
 676 {
 677         enum flm_op_result result;
 678         struct fib_change_queue *q = &fd->fd_ss.fd_change_queue;
 679
 680         result = fd->fd_flm->flm_change_rib_items_cb(fd->fd_rh, q, fd->fd_algo_data);
 681
 682         if (result == FLM_SUCCESS) {
 683                 for (int i = 0; i < q->count; i++)
 684                         if (q->entries[i].nh_old)
 685                                 fib_unref_nhop(fd, q->entries[i].nh_old);
 686                 q->count = 0;
 687         }
 688         fd->fd_batch = false;
 689
 690         return (result == FLM_SUCCESS);
 691 }
 692
 693 static bool
 694 fill_change_entry(struct fib_data *fd, struct fib_change_entry *ce, struct rib_cmd_info *rc)
 695 {
 696         int plen = 0;
 697
 698         switch (fd->fd_family) {
 699         case AF_INET:
 700                 rt_get_inet_prefix_plen(rc->rc_rt, &ce->addr4, &plen, &ce->scopeid);
 701                 break;
 702         case AF_INET6:
 703                 rt_get_inet6_prefix_plen(rc->rc_rt, &ce->addr6, &plen, &ce->scopeid);
 704                 break;
 705         }
 706
 707         ce->plen = plen;
 708         ce->nh_old = rc->rc_nh_old;
 709         ce->nh_new = rc->rc_nh_new;
 710         if (ce->nh_new != NULL) {
 711                 if (fib_ref_nhop(fd, ce->nh_new) == 0)
 712                         return (false);
 713         }
 714
 715         return (true);
 716 }
 717
 718 static bool
 719 queue_rtable_change(struct fib_data *fd, struct rib_cmd_info *rc)
 720 {
 721         struct fib_change_queue *q = &fd->fd_ss.fd_change_queue;
 722
 723         if (q->count >= q->size) {
 724                 uint32_t q_size;
 725
 726                 if (q->size == 0)
 727                         q_size = 256; /* ~18k memory */
 728                 else
 729                         q_size = q->size * 2;
 730
 731                 size_t size = q_size * sizeof(struct fib_change_entry);
 732                 void *a = realloc(q->entries, size, M_TEMP, M_NOWAIT | M_ZERO);
 733                 if (a == NULL) {
 734                         FD_PRINTF(LOG_INFO, fd, "Unable to realloc queue for %u elements",
 735                             q_size);
 736                         return (false);
 737                 }
 738                 q->entries = a;
 739                 q->size = q_size;
 740         }
 741
 742         return (fill_change_entry(fd, &q->entries[q->count++], rc));
 743 }
 744
 745 /*
 746  * Rib subscription handler. Checks if the algorithm is ready to
 747  *  receive updates, handles nexthop refcounting and passes change
 748  *  data to the algorithm callback.
 749  */
 750 static void
 751 handle_rtable_change_cb(struct rib_head *rnh, struct rib_cmd_info *rc,
 752     void *_data)
 753 {
 754         struct fib_data *fd = (struct fib_data *)_data;
 755         enum flm_op_result result;
 756
 757         RIB_WLOCK_ASSERT(rnh);
 758
 759         /*
 760          * There is a small gap between subscribing for route changes
 761          *  and initiating rtable dump. Avoid receiving route changes
 762          *  prior to finishing rtable dump by checking `init_done`.
 763          */
 764         if (!fd->init_done)
 765                 return;
 766
 767         bool immediate_sync = need_immediate_sync(fd, rc);
 768
 769         /* Consider scheduling algorithm re-evaluation */
 770         update_algo_state(fd);
 771
 772         /*
 773          * If algo requested rebuild, stop sending updates by default.
 774          * This simplifies nexthop refcount handling logic.
 775          */
 776         if (fd->fd_need_rebuild) {
 777                 if (immediate_sync)
 778                         rebuild_fd(fd, "rtable change type enforced sync");
 779                 return;
 780         }
 781
 782         /*
 783          * Algo requested updates to be delivered in batches.
 784          * Add the current change to the queue and return.
 785          */
 786         if (fd->fd_batch) {
 787                 if (immediate_sync) {
 788                         if (!queue_rtable_change(fd, rc) || !apply_rtable_changes(fd))
 789                                 rebuild_fd(fd, "batch sync failed");
 790                 } else {
 791                         if (!queue_rtable_change(fd, rc))
 792                                 schedule_fd_rebuild(fd, "batch queue failed");
 793                 }
 794                 return;
 795         }
 796
 797         /*
 798          * Maintain guarantee that every nexthop returned by the dataplane
 799          *  lookup has > 0 refcount, so can be safely referenced within current
 800          *  epoch.
 801          */
 802         if (rc->rc_nh_new != NULL) {
 803                 if (fib_ref_nhop(fd, rc->rc_nh_new) == 0) {
 804                         /* ran out of indexes */
 805                         schedule_fd_rebuild(fd, "ran out of nhop indexes");
 806                         return;
 807                 }
 808         }
 809
 810         result = fd->fd_flm->flm_change_rib_item_cb(rnh, rc, fd->fd_algo_data);
 811
 812         switch (result) {
 813         case FLM_SUCCESS:
 814                 /* Unref old nexthop on success */
 815                 if (rc->rc_nh_old != NULL)
 816                         fib_unref_nhop(fd, rc->rc_nh_old);
 817                 break;
 818         case FLM_BATCH:
 819
 820                 /*
 821                  * Algo asks to batch the changes.
 822                  */
 823                 if (queue_rtable_change(fd, rc)) {
 824                         if (!immediate_sync) {
 825                                 fd->fd_batch = true;
 826                                 mark_diverge_time(fd);
 827                                 update_rebuild_delay(fd, FDA_BATCH);
 828                                 break;
 829                         }
 830                         if (apply_rtable_changes(fd))
 831                                 break;
 832                 }
 833                 FD_PRINTF(LOG_ERR, fd, "batched sync failed, force the rebuild");
 834
 835         case FLM_REBUILD:
 836
 837                 /*
 838                  * Algo is not able to apply the update.
 839                  * Schedule algo rebuild.
 840                  */
 841                 if (!immediate_sync) {
 842                         mark_diverge_time(fd);
 843                         schedule_fd_rebuild(fd, "algo requested rebuild");
 844                         break;
 845                 }
 846
 847                 FD_PRINTF(LOG_INFO, fd, "running sync rebuild");
 848                 rebuild_fd(fd, "rtable change type enforced sync");
 849                 break;
 850         case FLM_ERROR:
 851
 852                 /*
 853                  * Algo reported a non-recoverable error.
 854                  * Record the error and schedule rebuild, which will
 855                  *  trigger best algo selection.
 856                  */
 857                 FD_PRINTF(LOG_ERR, fd, "algo reported non-recoverable error");
 858                 if (!flm_error_add(fd->fd_flm, fd->fd_fibnum))
 859                         FD_PRINTF(LOG_ERR, fd, "failed to ban algo");
 860                 schedule_fd_rebuild(fd, "algo reported non-recoverable error");
 861         }
 862 }
 863
 864 static void
 865 estimate_nhop_scale(const struct fib_data *old_fd, struct fib_data *fd)
 866 {
 867
 868         if (old_fd == NULL) {
 869                 // TODO: read from rtable
 870                 fd->number_nhops = 16;
 871                 return;
 872         }
 873
 874         if (old_fd->hit_nhops && old_fd->number_nhops < FIB_MAX_NHOPS)
 875                 fd->number_nhops = 2 * old_fd->number_nhops;
 876         else
 877                 fd->number_nhops = old_fd->number_nhops;
 878 }
 879
 880 struct walk_cbdata {
 881         struct fib_data         *fd;
 882         flm_dump_t              *func;
 883         enum flm_op_result      result;
 884 };
 885
 886 /*
 887  * Handler called after all rtenties have been dumped.
 888  * Performs post-dump framework checks and calls
 889  * algo:flm_dump_end_cb().
 890  *
 891  * Updates walk_cbdata result.
 892  */
 893 static void
 894 sync_algo_end_cb(struct rib_head *rnh, enum rib_walk_hook stage, void *_data)
 895 {
 896         struct walk_cbdata *w = (struct walk_cbdata *)_data;
 897         struct fib_data *fd = w->fd;
 898
 899         RIB_WLOCK_ASSERT(w->fd->fd_rh);
 900
 901         if (rnh->rib_dying) {
 902                 w->result = FLM_ERROR;
 903                 return;
 904         }
 905
 906         if (fd->hit_nhops) {
 907                 FD_PRINTF(LOG_INFO, fd, "ran out of nexthops at %u nhops",
 908                     fd->nh_ref_table->count);
 909                 if (w->result == FLM_SUCCESS)
 910                         w->result = FLM_REBUILD;
 911                 return;
 912         }
 913
 914         if (stage != RIB_WALK_HOOK_POST || w->result != FLM_SUCCESS)
 915                 return;
 916
 917         /* Post-dump hook, dump successful */
 918         w->result = fd->fd_flm->flm_dump_end_cb(fd->fd_algo_data, &fd->fd_dp);
 919
 920         if (w->result == FLM_SUCCESS) {
 921                 /* Mark init as done to allow routing updates */
 922                 fd->init_done = 1;
 923         }
 924 }
 925
 926 /*
 927  * Callback for each entry in rib.
 928  * Calls algo:flm_dump_rib_item_cb func as a part of initial
 929  *  route table synchronisation.
 930  */
 931 static int
 932 sync_algo_cb(struct rtentry *rt, void *_data)
 933 {
 934         struct walk_cbdata *w = (struct walk_cbdata *)_data;
 935
 936         RIB_WLOCK_ASSERT(w->fd->fd_rh);
 937
 938         if (w->result == FLM_SUCCESS && w->func) {
 939
 940                 /*
 941                  * Reference nexthops to maintain guarantee that
 942                  *  each nexthop returned by datapath has > 0 references
 943                  *  and can be safely referenced within current epoch.
 944                  */
 945                 struct nhop_object *nh = rt_get_raw_nhop(rt);
 946                 if (fib_ref_nhop(w->fd, nh) != 0)
 947                         w->result = w->func(rt, w->fd->fd_algo_data);
 948                 else
 949                         w->result = FLM_REBUILD;
 950         }
 951
 952         return (0);
 953 }
 954
 955 /*
 956  * Dump all routing table state to the algo instance.
 957  */
 958 static enum flm_op_result
 959 sync_algo(struct fib_data *fd)
 960 {
 961         struct walk_cbdata w = {
 962                 .fd = fd,
 963                 .func = fd->fd_flm->flm_dump_rib_item_cb,
 964                 .result = FLM_SUCCESS,
 965         };
 966
 967         rib_walk_ext_locked(fd->fd_rh, sync_algo_cb, sync_algo_end_cb, &w);
 968
 969         FD_PRINTF(LOG_INFO, fd,
 970             "initial dump completed (rtable version: %d), result: %s",
 971             fd->fd_rh->rnh_gen, print_op_result(w.result));
 972
 973         return (w.result);
 974 }
 975
 976 /*
 977  * Schedules epoch-backed @fd instance deletion.
 978  * * Unlinks @fd from the list of active algo instances.
 979  * * Removes rib subscription.
 980  * * Stops callout.
 981  * * Schedules actual deletion.
 982  *
 983  * Assume @fd is already unlinked from the datapath.
 984  */
 985 static int
 986 schedule_destroy_fd_instance(struct fib_data *fd, bool in_callout)
 987 {
 988         bool is_dead;
 989
 990         NET_EPOCH_ASSERT();
 991         RIB_WLOCK_ASSERT(fd->fd_rh);
 992
 993         FIB_MOD_LOCK();
 994         is_dead = fd->fd_dead;
 995         if (!is_dead)
 996                 fd->fd_dead = true;
 997         if (fd->fd_linked) {
 998                 TAILQ_REMOVE(&V_fib_data_list, fd, entries);
 999                 fd->fd_linked = false;
1000         }
1001         FIB_MOD_UNLOCK();
1002         if (is_dead)
1003                 return (0);
1004
1005         FD_PRINTF(LOG_INFO, fd, "DETACH");
1006
1007         if (fd->fd_rs != NULL)
1008                 rib_unsibscribe_locked(fd->fd_rs);
1009
1010         /*
1011          * After rib_unsubscribe() no _new_ handle_rtable_change_cb() calls
1012          * will be executed, hence no _new_ callout schedules will happen.
1013          */
1014         callout_stop(&fd->fd_callout);
1015
1016         fib_epoch_call(destroy_fd_instance_epoch, &fd->fd_epoch_ctx);
1017
1018         return (0);
1019 }
1020
1021 /*
1022  * Wipe all fd instances from the list matching rib specified by @rh.
1023  * If @keep_first is set, remove all but the first record.
1024  */
1025 static void
1026 fib_cleanup_algo(struct rib_head *rh, bool keep_first, bool in_callout)
1027 {
1028         struct fib_data_head tmp_head = TAILQ_HEAD_INITIALIZER(tmp_head);
1029         struct fib_data *fd, *fd_tmp;
1030         struct epoch_tracker et;
1031
1032         FIB_MOD_LOCK();
1033         TAILQ_FOREACH_SAFE(fd, &V_fib_data_list, entries, fd_tmp) {
1034                 if (fd->fd_rh == rh) {
1035                         if (keep_first) {
1036                                 keep_first = false;
1037                                 continue;
1038                         }
1039                         TAILQ_REMOVE(&V_fib_data_list, fd, entries);
1040                         fd->fd_linked = false;
1041                         TAILQ_INSERT_TAIL(&tmp_head, fd, entries);
1042                 }
1043         }
1044         FIB_MOD_UNLOCK();
1045
1046         /* Pass 2: remove each entry */
1047         NET_EPOCH_ENTER(et);
1048         TAILQ_FOREACH_SAFE(fd, &tmp_head, entries, fd_tmp) {
1049                 if (!in_callout)
1050                         RIB_WLOCK(fd->fd_rh);
1051                 schedule_destroy_fd_instance(fd, in_callout);
1052                 if (!in_callout)
1053                         RIB_WUNLOCK(fd->fd_rh);
1054         }
1055         NET_EPOCH_EXIT(et);
1056 }
1057
1058 void
1059 fib_destroy_rib(struct rib_head *rh)
1060 {
1061
1062         /*
1063          * rnh has `is_dying` flag set, so setup of new fd's will fail at
1064          *  sync_algo() stage, preventing new entries to be added to the list
1065          *  of active algos. Remove all existing entries for the particular rib.
1066          */
1067         fib_cleanup_algo(rh, false, false);
1068 }
1069
1070 /*
1071  * Finalises fd destruction by freeing all fd resources.
1072  */
1073 static void
1074 destroy_fd_instance(struct fib_data *fd)
1075 {
1076
1077         FD_PRINTF(LOG_INFO, fd, "destroy fd %p", fd);
1078
1079         /* Call destroy callback first */
1080         if (fd->fd_algo_data != NULL)
1081                 fd->fd_flm->flm_destroy_cb(fd->fd_algo_data);
1082
1083         /* Nhop table */
1084         if ((fd->nh_idx != NULL) && (fd->nh_ref_table != NULL)) {
1085                 for (int i = 0; i < fd->number_nhops; i++) {
1086                         if (!is_idx_free(fd, i)) {
1087                                 FD_PRINTF(LOG_DEBUG2, fd, " FREE nhop %d %p",
1088                                     i, fd->nh_idx[i]);
1089                                 nhop_free_any(fd->nh_idx[i]);
1090                         }
1091                 }
1092                 free(fd->nh_idx, M_RTABLE);
1093         }
1094         if (fd->nh_ref_table != NULL)
1095                 free(fd->nh_ref_table, M_RTABLE);
1096
1097         if (fd->fd_ss.fd_change_queue.entries != NULL)
1098                 free(fd->fd_ss.fd_change_queue.entries, M_TEMP);
1099
1100         fib_unref_algo(fd->fd_flm);
1101
1102         free(fd, M_RTABLE);
1103 }
1104
1105 /*
1106  * Epoch callback indicating fd is safe to destroy
1107  */
1108 static void
1109 destroy_fd_instance_epoch(epoch_context_t ctx)
1110 {
1111         struct fib_data *fd;
1112
1113         fd = __containerof(ctx, struct fib_data, fd_epoch_ctx);
1114
1115         destroy_fd_instance(fd);
1116 }
1117
1118 /*
1119  * Tries to setup fd instance.
1120  * - Allocates fd/nhop table
1121  * - Runs algo:flm_init_cb algo init
1122  * - Subscribes fd to the rib
1123  * - Runs rtable dump
1124  * - Adds instance to the list of active instances.
1125  *
1126  * Returns: operation result. Fills in @pfd with resulting fd on success.
1127  *
1128  */
1129 static enum flm_op_result
1130 try_setup_fd_instance(struct fib_lookup_module *flm, struct rib_head *rh,
1131     struct fib_data *old_fd, struct fib_data **pfd)
1132 {
1133         struct fib_data *fd;
1134         size_t size;
1135         enum flm_op_result result;
1136
1137         /* Allocate */
1138         fd = malloc(sizeof(struct fib_data), M_RTABLE, M_NOWAIT | M_ZERO);
1139         if (fd == NULL)  {
1140                 *pfd = NULL;
1141                 RH_PRINTF(LOG_INFO, rh, "Unable to allocate fib_data structure");
1142                 return (FLM_REBUILD);
1143         }
1144         *pfd = fd;
1145
1146         estimate_nhop_scale(old_fd, fd);
1147
1148         fd->fd_rh = rh;
1149         fd->fd_gen = ++fib_gen;
1150         fd->fd_family = rh->rib_family;
1151         fd->fd_fibnum = rh->rib_fibnum;
1152         callout_init_rm(&fd->fd_callout, &rh->rib_lock, 0);
1153         fd->fd_vnet = curvnet;
1154         fd->fd_flm = flm;
1155
1156         FD_PRINTF(LOG_DEBUG, fd, "allocated fd %p", fd);
1157
1158         FIB_MOD_LOCK();
1159         flm->flm_refcount++;
1160         FIB_MOD_UNLOCK();
1161
1162         /* Allocate nhidx -> nhop_ptr table */
1163         size = fd->number_nhops * sizeof(void *);
1164         fd->nh_idx = malloc(size, M_RTABLE, M_NOWAIT | M_ZERO);
1165         if (fd->nh_idx == NULL) {
1166                 FD_PRINTF(LOG_INFO, fd, "Unable to allocate nhop table idx (sz:%zu)", size);
1167                 return (FLM_REBUILD);
1168         }
1169
1170         /* Allocate nhop index refcount table */
1171         size = sizeof(struct nhop_ref_table);
1172         size += fd->number_nhops * sizeof(uint32_t);
1173         fd->nh_ref_table = malloc(size, M_RTABLE, M_NOWAIT | M_ZERO);
1174         if (fd->nh_ref_table == NULL) {
1175                 FD_PRINTF(LOG_INFO, fd, "Unable to allocate nhop refcount table (sz:%zu)", size);
1176                 return (FLM_REBUILD);
1177         }
1178         FD_PRINTF(LOG_DEBUG, fd, "Allocated %u nhop indexes", fd->number_nhops);
1179
1180         /* Okay, we're ready for algo init */
1181         void *old_algo_data = (old_fd != NULL) ? old_fd->fd_algo_data : NULL;
1182         result = flm->flm_init_cb(fd->fd_fibnum, fd, old_algo_data, &fd->fd_algo_data);
1183         if (result != FLM_SUCCESS) {
1184                 FD_PRINTF(LOG_INFO, fd, "%s algo init failed", flm->flm_name);
1185                 return (result);
1186         }
1187
1188         /* Try to subscribe */
1189         if (flm->flm_change_rib_item_cb != NULL) {
1190                 fd->fd_rs = rib_subscribe_locked(fd->fd_rh,
1191                     handle_rtable_change_cb, fd, RIB_NOTIFY_IMMEDIATE);
1192                 if (fd->fd_rs == NULL) {
1193                         FD_PRINTF(LOG_INFO, fd, "failed to subscribe to the rib changes");
1194                         return (FLM_REBUILD);
1195                 }
1196         }
1197
1198         /* Dump */
1199         result = sync_algo(fd);
1200         if (result != FLM_SUCCESS) {
1201                 FD_PRINTF(LOG_INFO, fd, "rib sync failed");
1202                 return (result);
1203         }
1204         FD_PRINTF(LOG_INFO, fd, "DUMP completed successfully.");
1205
1206         FIB_MOD_LOCK();
1207         /*
1208          * Insert fd in the beginning of a list, to maintain invariant
1209          *  that first matching entry for the AF/fib is always the active
1210          *  one.
1211          */
1212         TAILQ_INSERT_HEAD(&V_fib_data_list, fd, entries);
1213         fd->fd_linked = true;
1214         FIB_MOD_UNLOCK();
1215
1216         return (FLM_SUCCESS);
1217 }
1218
1219 /*
1220  * Sets up algo @flm for table @rh and links it to the datapath.
1221  *
1222  */
1223 static enum flm_op_result
1224 setup_fd_instance(struct fib_lookup_module *flm, struct rib_head *rh,
1225     struct fib_data *orig_fd, struct fib_data **pfd, bool attach)
1226 {
1227         struct fib_data *prev_fd, *new_fd;
1228         enum flm_op_result result;
1229
1230         NET_EPOCH_ASSERT();
1231         RIB_WLOCK_ASSERT(rh);
1232
1233         prev_fd = orig_fd;
1234         new_fd = NULL;
1235         for (int i = 0; i < FIB_MAX_TRIES; i++) {
1236                 result = try_setup_fd_instance(flm, rh, prev_fd, &new_fd);
1237
1238                 if ((result == FLM_SUCCESS) && attach) {
1239                         if (!fib_set_datapath_ptr(new_fd, &new_fd->fd_dp))
1240                                 result = FLM_REBUILD;
1241                 }
1242
1243                 if ((prev_fd != NULL) && (prev_fd != orig_fd)) {
1244                         schedule_destroy_fd_instance(prev_fd, false);
1245                         prev_fd = NULL;
1246                 }
1247
1248                 RH_PRINTF(LOG_INFO, rh, "try %d: fib algo result: %s", i,
1249                     print_op_result(result));
1250
1251                 if (result == FLM_REBUILD) {
1252                         prev_fd = new_fd;
1253                         new_fd = NULL;
1254                         continue;
1255                 }
1256
1257                 break;
1258         }
1259
1260         if (result != FLM_SUCCESS) {
1261                 RH_PRINTF(LOG_WARNING, rh,
1262                     "%s algo instance setup failed, failures=%d", flm->flm_name,
1263                     orig_fd ? orig_fd->fd_failed_rebuilds + 1 : 0);
1264                 /* update failure count */
1265                 FIB_MOD_LOCK();
1266                 if (orig_fd != NULL)
1267                         orig_fd->fd_failed_rebuilds++;
1268                 FIB_MOD_UNLOCK();
1269
1270                 /* Ban algo on non-recoverable error */
1271                 if (result == FLM_ERROR)
1272                         flm_error_add(flm, rh->rib_fibnum);
1273
1274                 if ((prev_fd != NULL) && (prev_fd != orig_fd))
1275                         schedule_destroy_fd_instance(prev_fd, false);
1276                 if (new_fd != NULL) {
1277                         schedule_destroy_fd_instance(new_fd, false);
1278                         new_fd = NULL;
1279                 }
1280         }
1281
1282         *pfd = new_fd;
1283         return (result);
1284 }
1285
1286 /*
1287  * Tries to sync algo with the current rtable state, either
1288  * by executing batch update or rebuilding.
1289  * Returns true on success.
1290  */
1291 static bool
1292 execute_callout_action(struct fib_data *fd)
1293 {
1294         enum fib_callout_action action = fd->fd_callout_action;
1295         struct fib_lookup_module *flm_new = NULL;
1296         bool result = true;
1297
1298         NET_EPOCH_ASSERT();
1299         RIB_WLOCK_ASSERT(fd->fd_rh);
1300
1301         fd->fd_need_rebuild = false;
1302         fd->fd_batch = false;
1303         fd->fd_num_changes = 0;
1304
1305         /* First, check if we're still OK to use this algo */
1306         if (!is_algo_fixed(fd->fd_rh))
1307                 flm_new = fib_check_best_algo(fd->fd_rh, fd->fd_flm);
1308         if (flm_new != NULL)
1309                 action = FDA_REBUILD;
1310
1311         if (action == FDA_BATCH) {
1312                 /* Try to sync */
1313                 if (!apply_rtable_changes(fd))
1314                         action = FDA_REBUILD;
1315         }
1316
1317         if (action == FDA_REBUILD)
1318                 result = rebuild_fd_flm(fd, flm_new != NULL ? flm_new : fd->fd_flm);
1319         if (flm_new != NULL)
1320                 fib_unref_algo(flm_new);
1321
1322         return (result);
1323 }
1324
1325 /*
1326  * Callout for all scheduled fd-related work.
1327  * - Checks if the current algo is still the best algo
1328  * - Synchronises algo instance to the rtable (batch usecase)
1329  * - Creates a new instance of an algo for af/fib if desired.
1330  */
1331 static void
1332 handle_fd_callout(void *_data)
1333 {
1334         struct fib_data *fd = (struct fib_data *)_data;
1335         struct epoch_tracker et;
1336
1337         FD_PRINTF(LOG_INFO, fd, "running callout type=%d", fd->fd_callout_action);
1338
1339         NET_EPOCH_ENTER(et);
1340         CURVNET_SET(fd->fd_vnet);
1341         execute_callout_action(fd);
1342         CURVNET_RESTORE();
1343         NET_EPOCH_EXIT(et);
1344 }
1345
1346 /*
1347  * Tries to create new algo instance based on @fd data.
1348  * Returns true on success.
1349  */
1350 static bool
1351 rebuild_fd_flm(struct fib_data *fd, struct fib_lookup_module *flm_new)
1352 {
1353         struct fib_data *fd_new, *fd_tmp = NULL;
1354         bool result;
1355
1356         if (flm_new == fd->fd_flm)
1357                 fd_tmp = fd;
1358         else
1359                 FD_PRINTF(LOG_NOTICE, fd, "switching algo to %s", flm_new->flm_name);
1360
1361         result = setup_fd_instance(flm_new, fd->fd_rh, fd_tmp, &fd_new, true);
1362         if (result != FLM_SUCCESS) {
1363                 FD_PRINTF(LOG_NOTICE, fd, "table rebuild failed");
1364                 return (false);
1365         }
1366         FD_PRINTF(LOG_INFO, fd_new, "switched to new instance");
1367
1368         /* Remove old instance */
1369         schedule_destroy_fd_instance(fd, true);
1370
1371         return (true);
1372 }
1373
1374 static bool
1375 rebuild_fd(struct fib_data *fd, const char *reason)
1376 {
1377         struct fib_lookup_module *flm_new = NULL;
1378         bool result;
1379
1380         if (!is_algo_fixed(fd->fd_rh))
1381                 flm_new = fib_check_best_algo(fd->fd_rh, fd->fd_flm);
1382
1383         FD_PRINTF(LOG_INFO, fd, "running sync rebuild: %s", reason);
1384         result = rebuild_fd_flm(fd, flm_new != NULL ? flm_new : fd->fd_flm);
1385         if (flm_new != NULL)
1386                 fib_unref_algo(flm_new);
1387
1388         if (!result) {
1389                 FD_PRINTF(LOG_ERR, fd, "sync rebuild failed");
1390                 schedule_fd_rebuild(fd, "sync rebuild failed");
1391         }
1392
1393         return (result);
1394 }
1395
1396 /*
1397  * Finds algo by name/family.
1398  * Returns referenced algo or NULL.
1399  */
1400 static struct fib_lookup_module *
1401 fib_find_algo(const char *algo_name, int family)
1402 {
1403         struct fib_lookup_module *flm;
1404
1405         FIB_MOD_LOCK();
1406         TAILQ_FOREACH(flm, &all_algo_list, entries) {
1407                 if ((strcmp(flm->flm_name, algo_name) == 0) &&
1408                     (family == flm->flm_family)) {
1409                         flm->flm_refcount++;
1410                         FIB_MOD_UNLOCK();
1411                         return (flm);
1412                 }
1413         }
1414         FIB_MOD_UNLOCK();
1415
1416         return (NULL);
1417 }
1418
1419 static void
1420 fib_unref_algo(struct fib_lookup_module *flm)
1421 {
1422
1423         FIB_MOD_LOCK();
1424         flm->flm_refcount--;
1425         FIB_MOD_UNLOCK();
1426 }
1427
1428 static int
1429 set_fib_algo(uint32_t fibnum, int family, struct sysctl_oid *oidp, struct sysctl_req *req)
1430 {
1431         struct fib_lookup_module *flm = NULL;
1432         struct fib_data *fd = NULL;
1433         char old_algo_name[32], algo_name[32];
1434         struct rib_head *rh = NULL;
1435         enum flm_op_result result;
1436         struct epoch_tracker et;
1437         int error;
1438
1439         /* Fetch current algo/rib for af/family */
1440         FIB_MOD_LOCK();
1441         TAILQ_FOREACH(fd, &V_fib_data_list, entries) {
1442                 if ((fd->fd_family == family) && (fd->fd_fibnum == fibnum))
1443                         break;
1444         }
1445         if (fd == NULL) {
1446                 FIB_MOD_UNLOCK();
1447                 return (ENOENT);
1448         }
1449         rh = fd->fd_rh;
1450         strlcpy(old_algo_name, fd->fd_flm->flm_name,
1451             sizeof(old_algo_name));
1452         FIB_MOD_UNLOCK();
1453
1454         strlcpy(algo_name, old_algo_name, sizeof(algo_name));
1455         error = sysctl_handle_string(oidp, algo_name, sizeof(algo_name), req);
1456         if (error != 0 || req->newptr == NULL)
1457                 return (error);
1458
1459         if (strcmp(algo_name, old_algo_name) == 0)
1460                 return (0);
1461
1462         /* New algorithm name is different */
1463         flm = fib_find_algo(algo_name, family);
1464         if (flm == NULL) {
1465                 RH_PRINTF(LOG_INFO, rh, "unable to find algo %s", algo_name);
1466                 return (ESRCH);
1467         }
1468
1469         fd = NULL;
1470         NET_EPOCH_ENTER(et);
1471         RIB_WLOCK(rh);
1472         result = setup_fd_instance(flm, rh, NULL, &fd, true);
1473         RIB_WUNLOCK(rh);
1474         NET_EPOCH_EXIT(et);
1475         fib_unref_algo(flm);
1476         if (result != FLM_SUCCESS)
1477                 return (EINVAL);
1478
1479         /* Disable automated jumping between algos */
1480         FIB_MOD_LOCK();
1481         set_algo_fixed(rh);
1482         FIB_MOD_UNLOCK();
1483         /* Remove old instance(s) */
1484         fib_cleanup_algo(rh, true, false);
1485
1486         /* Drain cb so user can unload the module after userret if so desired */
1487         epoch_drain_callbacks(net_epoch_preempt);
1488
1489         return (0);
1490 }
1491
1492 #ifdef INET
1493 static int
1494 set_algo_inet_sysctl_handler(SYSCTL_HANDLER_ARGS)
1495 {
1496
1497         return (set_fib_algo(curthread->td_proc->p_fibnum, AF_INET, oidp, req));
1498 }
1499 SYSCTL_PROC(_net_route_algo_inet, OID_AUTO, algo,
1500     CTLFLAG_VNET | CTLTYPE_STRING | CTLFLAG_RW | CTLFLAG_MPSAFE, NULL, 0,
1501     set_algo_inet_sysctl_handler, "A", "Set IPv4 lookup algo");
1502 #endif
1503
1504 #ifdef INET6
1505 static int
1506 set_algo_inet6_sysctl_handler(SYSCTL_HANDLER_ARGS)
1507 {
1508
1509         return (set_fib_algo(curthread->td_proc->p_fibnum, AF_INET6, oidp, req));
1510 }
1511 SYSCTL_PROC(_net_route_algo_inet6, OID_AUTO, algo,
1512     CTLFLAG_VNET | CTLTYPE_STRING | CTLFLAG_RW | CTLFLAG_MPSAFE, NULL, 0,
1513     set_algo_inet6_sysctl_handler, "A", "Set IPv6 lookup algo");
1514 #endif
1515
1516 static void
1517 destroy_fdh_epoch(epoch_context_t ctx)
1518 {
1519         struct fib_dp_header *fdh;
1520
1521         fdh = __containerof(ctx, struct fib_dp_header, fdh_epoch_ctx);
1522         free(fdh, M_RTABLE);
1523 }
1524
1525 static struct fib_dp_header *
1526 alloc_fib_dp_array(uint32_t num_tables, bool waitok)
1527 {
1528         size_t sz;
1529         struct fib_dp_header *fdh;
1530
1531         sz = sizeof(struct fib_dp_header);
1532         sz += sizeof(struct fib_dp) * num_tables;
1533         fdh = malloc(sz, M_RTABLE, (waitok ? M_WAITOK : M_NOWAIT) | M_ZERO);
1534         if (fdh != NULL)
1535                 fdh->fdh_num_tables = num_tables;
1536         return (fdh);
1537 }
1538
1539 static struct fib_dp_header *
1540 get_fib_dp_header(struct fib_dp *dp)
1541 {
1542
1543         return (__containerof((void *)dp, struct fib_dp_header, fdh_idx));
1544 }
1545
1546 /*
1547  * Replace per-family index pool @pdp with a new one which
1548  * contains updated callback/algo data from @fd.
1549  * Returns true on success.
1550  */
1551 static bool
1552 replace_rtables_family(struct fib_dp **pdp, struct fib_data *fd, struct fib_dp *dp)
1553 {
1554         struct fib_dp_header *new_fdh, *old_fdh;
1555
1556         NET_EPOCH_ASSERT();
1557
1558         FD_PRINTF(LOG_DEBUG, fd, "[vnet %p] replace with f:%p arg:%p",
1559             curvnet, dp->f, dp->arg);
1560
1561         FIB_MOD_LOCK();
1562         old_fdh = get_fib_dp_header(*pdp);
1563
1564         if (old_fdh->fdh_idx[fd->fd_fibnum].f == dp->f) {
1565                 /*
1566                  * Function is the same, data pointer needs update.
1567                  * Perform in-line replace without reallocation.
1568                  */
1569                 old_fdh->fdh_idx[fd->fd_fibnum].arg = dp->arg;
1570                 FD_PRINTF(LOG_DEBUG, fd, "FDH %p inline update", old_fdh);
1571                 FIB_MOD_UNLOCK();
1572                 return (true);
1573         }
1574
1575         new_fdh = alloc_fib_dp_array(old_fdh->fdh_num_tables, false);
1576         FD_PRINTF(LOG_DEBUG, fd, "OLD FDH: %p NEW FDH: %p", old_fdh, new_fdh);
1577         if (new_fdh == NULL) {
1578                 FIB_MOD_UNLOCK();
1579                 FD_PRINTF(LOG_WARNING, fd, "error attaching datapath");
1580                 return (false);
1581         }
1582
1583         memcpy(&new_fdh->fdh_idx[0], &old_fdh->fdh_idx[0],
1584             old_fdh->fdh_num_tables * sizeof(struct fib_dp));
1585         /* Update relevant data structure for @fd */
1586         new_fdh->fdh_idx[fd->fd_fibnum] = *dp;
1587
1588         /* Ensure memcpy() writes have completed */
1589         atomic_thread_fence_rel();
1590         /* Set new datapath pointer */
1591         *pdp = &new_fdh->fdh_idx[0];
1592         FIB_MOD_UNLOCK();
1593         FD_PRINTF(LOG_DEBUG, fd, "update %p -> %p", old_fdh, new_fdh);
1594
1595         fib_epoch_call(destroy_fdh_epoch, &old_fdh->fdh_epoch_ctx);
1596
1597         return (true);
1598 }
1599
1600 static struct fib_dp **
1601 get_family_dp_ptr(int family)
1602 {
1603         switch (family) {
1604         case AF_INET:
1605                 return (&V_inet_dp);
1606         case AF_INET6:
1607                 return (&V_inet6_dp);
1608         }
1609         return (NULL);
1610 }
1611
1612 /*
1613  * Make datapath use fib instance @fd
1614  */
1615 bool
1616 fib_set_datapath_ptr(struct fib_data *fd, struct fib_dp *dp)
1617 {
1618         struct fib_dp **pdp;
1619
1620         pdp = get_family_dp_ptr(fd->fd_family);
1621         return (replace_rtables_family(pdp, fd, dp));
1622 }
1623
1624 /*
1625  * Grow datapath pointers array.
1626  * Called from sysctl handler on growing number of routing tables.
1627  */
1628 static void
1629 grow_rtables_family(struct fib_dp **pdp, uint32_t new_num_tables)
1630 {
1631         struct fib_dp_header *new_fdh, *old_fdh = NULL;
1632
1633         new_fdh = alloc_fib_dp_array(new_num_tables, true);
1634
1635         FIB_MOD_LOCK();
1636         if (*pdp != NULL) {
1637                 old_fdh = get_fib_dp_header(*pdp);
1638                 memcpy(&new_fdh->fdh_idx[0], &old_fdh->fdh_idx[0],
1639                     old_fdh->fdh_num_tables * sizeof(struct fib_dp));
1640         }
1641
1642         /* Wait till all writes completed */
1643         atomic_thread_fence_rel();
1644
1645         *pdp = &new_fdh->fdh_idx[0];
1646         FIB_MOD_UNLOCK();
1647
1648         if (old_fdh != NULL)
1649                 fib_epoch_call(destroy_fdh_epoch, &old_fdh->fdh_epoch_ctx);
1650 }
1651
1652 /*
1653  * Grows per-AF arrays of datapath pointers for each supported family.
1654  * Called from fibs resize sysctl handler.
1655  */
1656 void
1657 fib_grow_rtables(uint32_t new_num_tables)
1658 {
1659
1660 #ifdef INET
1661         grow_rtables_family(get_family_dp_ptr(AF_INET), new_num_tables);
1662 #endif
1663 #ifdef INET6
1664         grow_rtables_family(get_family_dp_ptr(AF_INET6), new_num_tables);
1665 #endif
1666 }
1667
1668 void
1669 fib_get_rtable_info(struct rib_head *rh, struct rib_rtable_info *rinfo)
1670 {
1671
1672         bzero(rinfo, sizeof(struct rib_rtable_info));
1673         rinfo->num_prefixes = rh->rnh_prefixes;
1674         rinfo->num_nhops = nhops_get_count(rh);
1675 #ifdef ROUTE_MPATH
1676         rinfo->num_nhgrp = nhgrp_get_count(rh);
1677 #endif
1678 }
1679
1680 /*
1681  * Updates pointer to the algo data for the @fd.
1682  */
1683 void
1684 fib_set_algo_ptr(struct fib_data *fd, void *algo_data)
1685 {
1686         RIB_WLOCK_ASSERT(fd->fd_rh);
1687
1688         fd->fd_algo_data = algo_data;
1689 }
1690
1691 /*
1692  * Calls @callback with @ctx after the end of a current epoch.
1693  */
1694 void
1695 fib_epoch_call(epoch_callback_t callback, epoch_context_t ctx)
1696 {
1697         epoch_call(net_epoch_preempt, callback, ctx);
1698 }
1699
1700 /*
1701  * Accessor to get rib instance @fd is attached to.
1702  */
1703 struct rib_head *
1704 fib_get_rh(struct fib_data *fd)
1705 {
1706
1707         return (fd->fd_rh);
1708 }
1709
1710 /*
1711  * Accessor to export idx->nhop array
1712  */
1713 struct nhop_object **
1714 fib_get_nhop_array(struct fib_data *fd)
1715 {
1716
1717         return (fd->nh_idx);
1718 }
1719
1720 static uint32_t
1721 get_nhop_idx(struct nhop_object *nh)
1722 {
1723 #ifdef ROUTE_MPATH
1724         if (NH_IS_NHGRP(nh))
1725                 return (nhgrp_get_idx((struct nhgrp_object *)nh) * 2 - 1);
1726         else
1727                 return (nhop_get_idx(nh) * 2);
1728 #else
1729         return (nhop_get_idx(nh));
1730 #endif
1731 }
1732
1733 uint32_t
1734 fib_get_nhop_idx(struct fib_data *fd, struct nhop_object *nh)
1735 {
1736
1737         return (get_nhop_idx(nh));
1738 }
1739
1740 static bool
1741 is_idx_free(struct fib_data *fd, uint32_t index)
1742 {
1743
1744         return (fd->nh_ref_table->refcnt[index] == 0);
1745 }
1746
1747 static uint32_t
1748 fib_ref_nhop(struct fib_data *fd, struct nhop_object *nh)
1749 {
1750         uint32_t idx = get_nhop_idx(nh);
1751
1752         if (idx >= fd->number_nhops) {
1753                 fd->hit_nhops = 1;
1754                 return (0);
1755         }
1756
1757         if (is_idx_free(fd, idx)) {
1758                 nhop_ref_any(nh);
1759                 fd->nh_idx[idx] = nh;
1760                 fd->nh_ref_table->count++;
1761                 FD_PRINTF(LOG_DEBUG2, fd, " REF nhop %u %p", idx, fd->nh_idx[idx]);
1762         }
1763         fd->nh_ref_table->refcnt[idx]++;
1764
1765         return (idx);
1766 }
1767
1768 struct nhop_release_data {
1769         struct nhop_object      *nh;
1770         struct epoch_context    ctx;
1771 };
1772
1773 static void
1774 release_nhop_epoch(epoch_context_t ctx)
1775 {
1776         struct nhop_release_data *nrd;
1777
1778         nrd = __containerof(ctx, struct nhop_release_data, ctx);
1779         nhop_free_any(nrd->nh);
1780         free(nrd, M_TEMP);
1781 }
1782
1783 /*
1784  * Delays nexthop refcount release.
1785  * Datapath may have the datastructures not updated yet, so the old
1786  *  nexthop may still be returned till the end of current epoch. Delay
1787  *  refcount removal, as we may be removing the last instance, which will
1788  *  trigger nexthop deletion, rendering returned nexthop invalid.
1789  */
1790 static void
1791 fib_schedule_release_nhop(struct fib_data *fd, struct nhop_object *nh)
1792 {
1793         struct nhop_release_data *nrd;
1794
1795         nrd = malloc(sizeof(struct nhop_release_data), M_TEMP, M_NOWAIT | M_ZERO);
1796         if (nrd != NULL) {
1797                 nrd->nh = nh;
1798                 fib_epoch_call(release_nhop_epoch, &nrd->ctx);
1799         } else {
1800                 /*
1801                  * Unable to allocate memory. Leak nexthop to maintain guarantee
1802                  *  that each nhop can be referenced.
1803                  */
1804                 FD_PRINTF(LOG_ERR, fd, "unable to schedule nhop %p deletion", nh);
1805         }
1806 }
1807
1808 static void
1809 fib_unref_nhop(struct fib_data *fd, struct nhop_object *nh)
1810 {
1811         uint32_t idx = get_nhop_idx(nh);
1812
1813         KASSERT((idx < fd->number_nhops), ("invalid nhop index"));
1814         KASSERT((nh == fd->nh_idx[idx]), ("index table contains whong nh"));
1815
1816         fd->nh_ref_table->refcnt[idx]--;
1817         if (fd->nh_ref_table->refcnt[idx] == 0) {
1818                 FD_PRINTF(LOG_DEBUG, fd, " FREE nhop %d %p", idx, fd->nh_idx[idx]);
1819                 fib_schedule_release_nhop(fd, fd->nh_idx[idx]);
1820         }
1821 }
1822
1823 static void
1824 set_algo_fixed(struct rib_head *rh)
1825 {
1826         switch (rh->rib_family) {
1827 #ifdef INET
1828         case AF_INET:
1829                 V_algo_fixed_inet = true;
1830                 break;
1831 #endif
1832 #ifdef INET6
1833         case AF_INET6:
1834                 V_algo_fixed_inet6 = true;
1835                 break;
1836 #endif
1837         }
1838 }
1839
1840 static bool
1841 is_algo_fixed(struct rib_head *rh)
1842 {
1843
1844         switch (rh->rib_family) {
1845 #ifdef INET
1846         case AF_INET:
1847                 return (V_algo_fixed_inet);
1848 #endif
1849 #ifdef INET6
1850         case AF_INET6:
1851                 return (V_algo_fixed_inet6);
1852 #endif
1853         }
1854         return (false);
1855 }
1856
1857 /*
1858  * Runs the check on what would be the best algo for rib @rh, assuming
1859  *  that the current algo is the one specified by @orig_flm. Note that
1860  *  it can be NULL for initial selection.
1861  *
1862  * Returns referenced new algo or NULL if the current one is the best.
1863  */
1864 static struct fib_lookup_module *
1865 fib_check_best_algo(struct rib_head *rh, struct fib_lookup_module *orig_flm)
1866 {
1867         uint8_t preference, curr_preference = 0, best_preference = 0;
1868         struct fib_lookup_module *flm, *best_flm = NULL;
1869         struct rib_rtable_info rinfo;
1870         int candidate_algos = 0;
1871
1872         fib_get_rtable_info(rh, &rinfo);
1873
1874         FIB_MOD_LOCK();
1875         TAILQ_FOREACH(flm, &all_algo_list, entries) {
1876                 if (flm->flm_family != rh->rib_family)
1877                         continue;
1878                 candidate_algos++;
1879                 preference = flm->flm_get_pref(&rinfo);
1880                 if (preference > best_preference) {
1881                         if (!flm_error_check(flm, rh->rib_fibnum)) {
1882                                 best_preference = preference;
1883                                 best_flm = flm;
1884                         }
1885                 }
1886                 if (flm == orig_flm)
1887                         curr_preference = preference;
1888         }
1889         if ((best_flm != NULL) && (curr_preference + BEST_DIFF_PERCENT < best_preference))
1890                 best_flm->flm_refcount++;
1891         else
1892                 best_flm = NULL;
1893         FIB_MOD_UNLOCK();
1894
1895         RH_PRINTF(LOG_DEBUG, rh, "candidate_algos: %d, curr: %s(%d) result: %s(%d)",
1896             candidate_algos, orig_flm ? orig_flm->flm_name : "NULL", curr_preference,
1897             best_flm ? best_flm->flm_name : (orig_flm ? orig_flm->flm_name : "NULL"),
1898             best_preference);
1899
1900         return (best_flm);
1901 }
1902
1903 /*
1904  * Called when new route table is created.
1905  * Selects, allocates and attaches fib algo for the table.
1906  */
1907 int
1908 fib_select_algo_initial(struct rib_head *rh)
1909 {
1910         struct fib_lookup_module *flm;
1911         struct fib_data *fd = NULL;
1912         enum flm_op_result result;
1913         struct epoch_tracker et;
1914         int error = 0;
1915
1916         flm = fib_check_best_algo(rh, NULL);
1917         if (flm == NULL) {
1918                 RH_PRINTF(LOG_CRIT, rh, "no algo selected");
1919                 return (ENOENT);
1920         }
1921         RH_PRINTF(LOG_INFO, rh, "selected algo %s", flm->flm_name);
1922
1923         NET_EPOCH_ENTER(et);
1924         RIB_WLOCK(rh);
1925         result = setup_fd_instance(flm, rh, NULL, &fd, false);
1926         RIB_WUNLOCK(rh);
1927         NET_EPOCH_EXIT(et);
1928
1929         RH_PRINTF(LOG_DEBUG, rh, "result=%d fd=%p", result, fd);
1930         if (result == FLM_SUCCESS) {
1931
1932                 /*
1933                  * Attach datapath directly to avoid multiple reallocations
1934                  * during fib growth
1935                  */
1936                 struct fib_dp_header *fdp;
1937                 struct fib_dp **pdp;
1938
1939                 pdp = get_family_dp_ptr(rh->rib_family);
1940                 if (pdp != NULL) {
1941                         fdp = get_fib_dp_header(*pdp);
1942                         fdp->fdh_idx[fd->fd_fibnum] = fd->fd_dp;
1943                         FD_PRINTF(LOG_INFO, fd, "datapath attached");
1944                 }
1945         } else {
1946                 error = EINVAL;
1947                 RH_PRINTF(LOG_CRIT, rh, "unable to setup algo %s", flm->flm_name);
1948         }
1949
1950         fib_unref_algo(flm);
1951
1952         return (error);
1953 }
1954
1955 /*
1956  * Registers fib lookup module within the subsystem.
1957  */
1958 int
1959 fib_module_register(struct fib_lookup_module *flm)
1960 {
1961
1962         FIB_MOD_LOCK();
1963         ALGO_PRINTF("attaching %s to %s", flm->flm_name,
1964             print_family(flm->flm_family));
1965         TAILQ_INSERT_TAIL(&all_algo_list, flm, entries);
1966         FIB_MOD_UNLOCK();
1967
1968         return (0);
1969 }
1970
1971 /*
1972  * Tries to unregister fib lookup module.
1973  *
1974  * Returns 0 on success, EBUSY if module is still used
1975  *  by some of the tables.
1976  */
1977 int
1978 fib_module_unregister(struct fib_lookup_module *flm)
1979 {
1980
1981         FIB_MOD_LOCK();
1982         if (flm->flm_refcount > 0) {
1983                 FIB_MOD_UNLOCK();
1984                 return (EBUSY);
1985         }
1986         fib_error_clear_flm(flm);
1987         ALGO_PRINTF("detaching %s from %s", flm->flm_name,
1988             print_family(flm->flm_family));
1989         TAILQ_REMOVE(&all_algo_list, flm, entries);
1990         FIB_MOD_UNLOCK();
1991
1992         return (0);
1993 }
1994
1995 void
1996 vnet_fib_init(void)
1997 {
1998
1999         TAILQ_INIT(&V_fib_data_list);
2000 }
2001
2002 void
2003 vnet_fib_destroy(void)
2004 {
2005
2006         FIB_MOD_LOCK();
2007         fib_error_clear();
2008         FIB_MOD_UNLOCK();
2009 }