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