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