sys/net/route/nhop.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_route.h"
  32
  33 #include <sys/param.h>
  34 #include <sys/systm.h>
  35 #include <sys/lock.h>
  36 #include <sys/rwlock.h>
  37 #include <sys/malloc.h>
  38 #include <sys/mbuf.h>
  39 #include <sys/socket.h>
  40 #include <sys/kernel.h>
  41
  42 #include <net/if.h>
  43 #include <net/if_var.h>
  44 #include <net/route.h>
  45 #include <net/route/route_var.h>
  46 #include <net/route/nhop_utils.h>
  47 #include <net/route/nhop.h>
  48 #include <net/route/nhop_var.h>
  49 #include <net/vnet.h>
  50
  51 /*
  52  * This file contains data structures management logic for the nexthop ("nhop")
  53  *   route subsystem.
  54  *
  55  * Nexthops in the original sense are the objects containing all the necessary
  56  * information to forward the packet to the selected destination.
  57  * In particular, nexthop is defined by a combination of
  58  *  ifp, ifa, aifp, mtu, gw addr(if set), nh_type, nh_family, mask of rt_flags and
  59  *    NHF_DEFAULT
  60  *
  61  * All nexthops are stored in the resizable hash table.
  62  * Additionally, each nexthop gets assigned its unique index (nexthop index)
  63  * so userland programs can interact with the nexthops easier. Index allocation
  64  * is backed by the bitmask array.
  65  */
  66
  67 static MALLOC_DEFINE(M_NHOP, "nhops", "nexthops data");
  68
  69 /* Hash management functions */
  70
  71 int
  72 nhops_init_rib(struct rib_head *rh)
  73 {
  74         struct nh_control *ctl;
  75         size_t alloc_size;
  76         uint32_t num_buckets, num_items;
  77         void *ptr;
  78
  79         ctl = malloc(sizeof(struct nh_control), M_NHOP, M_WAITOK | M_ZERO);
  80
  81         /*
  82          * Allocate nexthop hash. Start with 16 items by default (128 bytes).
  83          * This will be enough for most of the cases.
  84          */
  85         num_buckets = 16;
  86         alloc_size = CHT_SLIST_GET_RESIZE_SIZE(num_buckets);
  87         ptr = malloc(alloc_size, M_NHOP, M_WAITOK | M_ZERO);
  88         CHT_SLIST_INIT(&ctl->nh_head, ptr, num_buckets);
  89
  90         /*
  91          * Allocate nexthop index bitmask.
  92          */
  93         num_items = 128 * 8; /* 128 bytes */
  94         ptr = malloc(bitmask_get_size(num_items), M_NHOP, M_WAITOK | M_ZERO);
  95         bitmask_init(&ctl->nh_idx_head, ptr, num_items);
  96
  97         NHOPS_LOCK_INIT(ctl);
  98
  99         rh->nh_control = ctl;
 100         ctl->ctl_rh = rh;
 101
 102         DPRINTF("NHOPS init for fib %u af %u: ctl %p rh %p", rh->rib_fibnum,
 103             rh->rib_family, ctl, rh);
 104
 105         return (0);
 106 }
 107
 108 static void
 109 destroy_ctl(struct nh_control *ctl)
 110 {
 111
 112         NHOPS_LOCK_DESTROY(ctl);
 113         free(ctl->nh_head.ptr, M_NHOP);
 114         free(ctl->nh_idx_head.idx, M_NHOP);
 115         free(ctl, M_NHOP);
 116 }
 117
 118 /*
 119  * Epoch callback indicating ctl is safe to destroy
 120  */
 121 static void
 122 destroy_ctl_epoch(epoch_context_t ctx)
 123 {
 124         struct nh_control *ctl;
 125
 126         ctl = __containerof(ctx, struct nh_control, ctl_epoch_ctx);
 127
 128         destroy_ctl(ctl);
 129 }
 130
 131 void
 132 nhops_destroy_rib(struct rib_head *rh)
 133 {
 134         struct nh_control *ctl;
 135         struct nhop_priv *nh_priv;
 136
 137         ctl = rh->nh_control;
 138
 139         /*
 140          * All routes should have been deleted in rt_table_destroy().
 141          * However, TCP stack or other consumers may store referenced
 142          *  nexthop pointers. When these references go to zero,
 143          *  nhop_free() will try to unlink these records from the
 144          *  datastructures, most likely leading to panic.
 145          *
 146          * Avoid that by explicitly marking all of the remaining
 147          *  nexthops as unlinked by removing a reference from a special
 148          *  counter. Please see nhop_free() comments for more
 149          *  details.
 150          */
 151
 152         NHOPS_WLOCK(ctl);
 153         CHT_SLIST_FOREACH(&ctl->nh_head, nhops, nh_priv) {
 154                 DPRINTF("Marking nhop %u unlinked", nh_priv->nh_idx);
 155                 refcount_release(&nh_priv->nh_linked);
 156         } CHT_SLIST_FOREACH_END;
 157         NHOPS_WUNLOCK(ctl);
 158
 159         /*
 160          * Postpone destruction till the end of current epoch
 161          * so nhop_free() can safely use nh_control pointer.
 162          */
 163         epoch_call(net_epoch_preempt, destroy_ctl_epoch,
 164             &ctl->ctl_epoch_ctx);
 165 }
 166
 167 /*
 168  * Nexhop hash calculation:
 169  *
 170  * Nexthops distribution:
 171  * 2 "mandatory" nexthops per interface ("interface route", "loopback").
 172  * For direct peering: 1 nexthop for the peering router per ifp/af.
 173  * For Ix-like peering: tens to hundreds nexthops of neghbors per ifp/af.
 174  * IGP control plane & broadcast segment: tens of nexthops per ifp/af.
 175  *
 176  * Each fib/af combination has its own hash table.
 177  * With that in mind, hash nexthops by the combination of the interface
 178  *  and GW IP address.
 179  *
 180  * To optimize hash calculation, ignore higher bytes of ifindex, as they
 181  *  give very little entropy.
 182  * Similarly, use lower 4 bytes of IPv6 address to distinguish between the
 183  *  neighbors.
 184  */
 185 struct _hash_data {
 186         uint16_t        ifindex;
 187         uint8_t         family;
 188         uint8_t         nh_type;
 189         uint32_t        gw_addr;
 190 };
 191
 192 static unsigned
 193 djb_hash(const unsigned char *h, const int len)
 194 {
 195         unsigned int result = 0;
 196         int i;
 197
 198         for (i = 0; i < len; i++)
 199                 result = 33 * result ^ h[i];
 200
 201         return (result);
 202 }
 203
 204 static uint32_t
 205 hash_priv(const struct nhop_priv *priv)
 206 {
 207         struct nhop_object *nh;
 208         uint16_t ifindex;
 209         struct _hash_data key;
 210
 211         nh = priv->nh;
 212         ifindex = nh->nh_ifp->if_index & 0xFFFF;
 213         memset(&key, 0, sizeof(key));
 214
 215         key.ifindex = ifindex;
 216         key.family = nh->gw_sa.sa_family;
 217         key.nh_type = priv->nh_type & 0xFF;
 218         if (nh->gw_sa.sa_family == AF_INET6)
 219                 memcpy(&key.gw_addr, &nh->gw6_sa.sin6_addr.s6_addr32[3], 4);
 220         else if (nh->gw_sa.sa_family == AF_INET)
 221                 memcpy(&key.gw_addr, &nh->gw4_sa.sin_addr, 4);
 222
 223         return (uint32_t)(djb_hash((const unsigned char *)&key, sizeof(key)));
 224 }
 225
 226 /*
 227  * Checks if hash needs resizing and performs this resize if necessary
 228  *
 229  */
 230 static void
 231 consider_resize(struct nh_control *ctl, uint32_t new_nh_buckets, uint32_t new_idx_items)
 232 {
 233         void *nh_ptr, *nh_idx_ptr;
 234         void *old_idx_ptr;
 235         size_t alloc_size;
 236
 237         nh_ptr = NULL;
 238         if (new_nh_buckets != 0) {
 239                 alloc_size = CHT_SLIST_GET_RESIZE_SIZE(new_nh_buckets);
 240                 nh_ptr = malloc(alloc_size, M_NHOP, M_NOWAIT | M_ZERO);
 241         }
 242
 243         nh_idx_ptr = NULL;
 244         if (new_idx_items != 0) {
 245                 alloc_size = bitmask_get_size(new_idx_items);
 246                 nh_idx_ptr = malloc(alloc_size, M_NHOP, M_NOWAIT | M_ZERO);
 247         }
 248
 249         if (nh_ptr == NULL && nh_idx_ptr == NULL) {
 250                 /* Either resize is not required or allocations have failed. */
 251                 return;
 252         }
 253
 254         DPRINTF("going to resize: nh:[ptr:%p sz:%u] idx:[ptr:%p sz:%u]", nh_ptr,
 255             new_nh_buckets, nh_idx_ptr, new_idx_items);
 256
 257         old_idx_ptr = NULL;
 258
 259         NHOPS_WLOCK(ctl);
 260         if (nh_ptr != NULL) {
 261                 CHT_SLIST_RESIZE(&ctl->nh_head, nhops, nh_ptr, new_nh_buckets);
 262         }
 263         if (nh_idx_ptr != NULL) {
 264                 if (bitmask_copy(&ctl->nh_idx_head, nh_idx_ptr, new_idx_items) == 0)
 265                         bitmask_swap(&ctl->nh_idx_head, nh_idx_ptr, new_idx_items, &old_idx_ptr);
 266         }
 267         NHOPS_WUNLOCK(ctl);
 268
 269         if (nh_ptr != NULL)
 270                 free(nh_ptr, M_NHOP);
 271         if (old_idx_ptr != NULL)
 272                 free(old_idx_ptr, M_NHOP);
 273 }
 274
 275 /*
 276  * Links nextop @nh_priv to the nexhop hash table and allocates
 277  *  nexhop index.
 278  * Returns allocated index or 0 on failure.
 279  */
 280 int
 281 link_nhop(struct nh_control *ctl, struct nhop_priv *nh_priv)
 282 {
 283         uint16_t idx;
 284         uint32_t num_buckets_new, num_items_new;
 285
 286         KASSERT((nh_priv->nh_idx == 0), ("nhop index is already allocated"));
 287         NHOPS_WLOCK(ctl);
 288
 289         /*
 290          * Check if we need to resize hash and index.
 291          * The following 2 functions returns either new size or 0
 292          *  if resize is not required.
 293          */
 294         num_buckets_new = CHT_SLIST_GET_RESIZE_BUCKETS(&ctl->nh_head);
 295         num_items_new = bitmask_get_resize_items(&ctl->nh_idx_head);
 296
 297         if (bitmask_alloc_idx(&ctl->nh_idx_head, &idx) != 0) {
 298                 NHOPS_WUNLOCK(ctl);
 299                 DPRINTF("Unable to allocate nhop index");
 300                 RTSTAT_INC(rts_nh_idx_alloc_failure);
 301                 consider_resize(ctl, num_buckets_new, num_items_new);
 302                 return (0);
 303         }
 304
 305         nh_priv->nh_idx = idx;
 306         nh_priv->nh_control = ctl;
 307
 308         CHT_SLIST_INSERT_HEAD(&ctl->nh_head, nhops, nh_priv);
 309
 310         NHOPS_WUNLOCK(ctl);
 311
 312         DPRINTF("Linked nhop priv %p to %d, hash %u, ctl %p", nh_priv, idx,
 313             hash_priv(nh_priv), ctl);
 314         consider_resize(ctl, num_buckets_new, num_items_new);
 315
 316         return (idx);
 317 }
 318
 319 /*
 320  * Unlinks nexthop specified by @nh_priv data from the hash.
 321  *
 322  * Returns found nexthop or NULL.
 323  */
 324 struct nhop_priv *
 325 unlink_nhop(struct nh_control *ctl, struct nhop_priv *nh_priv_del)
 326 {
 327         struct nhop_priv *priv_ret;
 328         int idx;
 329         uint32_t num_buckets_new, num_items_new;
 330
 331         idx = 0;
 332
 333         NHOPS_WLOCK(ctl);
 334         CHT_SLIST_REMOVE_BYOBJ(&ctl->nh_head, nhops, nh_priv_del, priv_ret);
 335
 336         if (priv_ret != NULL) {
 337                 idx = priv_ret->nh_idx;
 338                 priv_ret->nh_idx = 0;
 339
 340                 KASSERT((idx != 0), ("bogus nhop index 0"));
 341                 if ((bitmask_free_idx(&ctl->nh_idx_head, idx)) != 0) {
 342                         DPRINTF("Unable to remove index %d from fib %u af %d",
 343                             idx, ctl->ctl_rh->rib_fibnum,
 344                             ctl->ctl_rh->rib_family);
 345                 }
 346         }
 347
 348         /* Check if hash or index needs to be resized */
 349         num_buckets_new = CHT_SLIST_GET_RESIZE_BUCKETS(&ctl->nh_head);
 350         num_items_new = bitmask_get_resize_items(&ctl->nh_idx_head);
 351
 352         NHOPS_WUNLOCK(ctl);
 353
 354         if (priv_ret == NULL)
 355                 DPRINTF("Unable to unlink nhop priv %p from hash, hash %u ctl %p",
 356                     nh_priv_del, hash_priv(nh_priv_del), ctl);
 357         else
 358                 DPRINTF("Unlinked nhop %p priv idx %d", priv_ret, idx);
 359
 360         consider_resize(ctl, num_buckets_new, num_items_new);
 361
 362         return (priv_ret);
 363 }
 364
 365 /*
 366  * Searches for the nexthop by data specifcied in @nh_priv.
 367  * Returns referenced nexthop or NULL.
 368  */
 369 struct nhop_priv *
 370 find_nhop(struct nh_control *ctl, const struct nhop_priv *nh_priv)
 371 {
 372         struct nhop_priv *nh_priv_ret;
 373
 374         NHOPS_RLOCK(ctl);
 375         CHT_SLIST_FIND_BYOBJ(&ctl->nh_head, nhops, nh_priv, nh_priv_ret);
 376         if (nh_priv_ret != NULL) {
 377                 if (refcount_acquire_if_not_zero(&nh_priv_ret->nh_refcnt) == 0){
 378                         /* refcount was 0 -> nhop is being deleted */
 379                         nh_priv_ret = NULL;
 380                 }
 381         }
 382         NHOPS_RUNLOCK(ctl);
 383
 384         return (nh_priv_ret);
 385 }