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 * $FreeBSD$ 28 */ 29 30 #include "opt_inet.h" 31 #include "opt_route.h" 32 33 #include <sys/cdefs.h> 34 #include <sys/param.h> 35 #include <sys/systm.h> 36 #include <sys/lock.h> 37 #include <sys/rmlock.h> 38 #include <sys/rwlock.h> 39 #include <sys/malloc.h> 40 #include <sys/mbuf.h> 41 #include <sys/refcount.h> 42 #include <sys/socket.h> 43 #include <sys/sysctl.h> 44 #include <sys/kernel.h> 45 46 #include <net/if.h> 47 #include <net/if_var.h> 48 #include <net/if_dl.h> 49 #include <net/route.h> 50 #include <net/route/route_ctl.h> 51 #include <net/route/route_var.h> 52 #include <net/vnet.h> 53 54 #include <netinet/in.h> 55 #include <netinet/in_var.h> 56 #include <netinet/in_fib.h> 57 58 #include <net/route/nhop_utils.h> 59 #include <net/route/nhop.h> 60 #include <net/route/nhop_var.h> 61 #include <net/route/nhgrp_var.h> 62 63 #define DEBUG_MOD_NAME nhgrp 64 #define DEBUG_MAX_LEVEL LOG_DEBUG 65 #include <net/route/route_debug.h> 66 _DECLARE_DEBUG(LOG_INFO); 67 68 /* 69 * This file contains data structures management logic for the nexthop 70 * groups ("nhgrp") route subsystem. 71 * 72 * Nexthop groups are used to store multiple routes available for the specific 73 * prefix. Nexthop groups are immutable and can be shared across multiple 74 * prefixes. 75 * 76 * Each group consists of a control plane part and a dataplane part. 77 * Control plane is basically a collection of nexthop objects with 78 * weights and refcount. 79 * 80 * Datapath consists of a array of nexthop pointers, compiled from control 81 * plane data to support O(1) nexthop selection. 82 * 83 * For example, consider the following group: 84 * [(nh1, weight=100), (nh2, weight=200)] 85 * It will compile to the following array: 86 * [nh1, nh2, nh2] 87 * 88 */ 89 90 static void consider_resize(struct nh_control *ctl, uint32_t new_gr_buckets, 91 uint32_t new_idx_items); 92 93 static int cmp_nhgrp(const struct nhgrp_priv *a, const struct nhgrp_priv *b); 94 static unsigned int hash_nhgrp(const struct nhgrp_priv *obj); 95 96 static unsigned 97 djb_hash(const unsigned char *h, const int len) 98 { 99 unsigned int result = 0; 100 int i; 101 102 for (i = 0; i < len; i++) 103 result = 33 * result ^ h[i]; 104 105 return (result); 106 } 107 108 static int 109 cmp_nhgrp(const struct nhgrp_priv *a, const struct nhgrp_priv *b) 110 { 111 112 /* 113 * In case of consistent hashing, there can be multiple nexthop groups 114 * with the same "control plane" list of nexthops with weights and a 115 * different set of "data plane" nexthops. 116 * For now, ignore the data plane and focus on the control plane list. 117 */ 118 if (a->nhg_nh_count != b->nhg_nh_count) 119 return (0); 120 return !memcmp(a->nhg_nh_weights, b->nhg_nh_weights, 121 sizeof(struct weightened_nhop) * a->nhg_nh_count); 122 } 123 124 /* 125 * Hash callback: calculate hash of an object 126 */ 127 static unsigned int 128 hash_nhgrp(const struct nhgrp_priv *obj) 129 { 130 const unsigned char *key; 131 132 key = (const unsigned char *)obj->nhg_nh_weights; 133 134 return (djb_hash(key, sizeof(struct weightened_nhop) * obj->nhg_nh_count)); 135 } 136 137 /* 138 * Returns object referenced and unlocked 139 */ 140 struct nhgrp_priv * 141 find_nhgrp(struct nh_control *ctl, const struct nhgrp_priv *key) 142 { 143 struct nhgrp_priv *priv_ret; 144 145 NHOPS_RLOCK(ctl); 146 CHT_SLIST_FIND_BYOBJ(&ctl->gr_head, mpath, key, priv_ret); 147 if (priv_ret != NULL) { 148 if (refcount_acquire_if_not_zero(&priv_ret->nhg_refcount) == 0) { 149 /* refcount is 0 -> group is being deleted */ 150 priv_ret = NULL; 151 } 152 } 153 NHOPS_RUNLOCK(ctl); 154 155 return (priv_ret); 156 } 157 158 int 159 link_nhgrp(struct nh_control *ctl, struct nhgrp_priv *grp_priv) 160 { 161 uint16_t idx; 162 uint32_t new_num_buckets, new_num_items; 163 164 NHOPS_WLOCK(ctl); 165 /* Check if we need to resize hash and index */ 166 new_num_buckets = CHT_SLIST_GET_RESIZE_BUCKETS(&ctl->gr_head); 167 new_num_items = bitmask_get_resize_items(&ctl->nh_idx_head); 168 169 if (bitmask_alloc_idx(&ctl->nh_idx_head, &idx) != 0) { 170 NHOPS_WUNLOCK(ctl); 171 FIB_RH_LOG(LOG_DEBUG, ctl->ctl_rh, "Unable to allocate nhg index"); 172 consider_resize(ctl, new_num_buckets, new_num_items); 173 return (0); 174 } 175 176 grp_priv->nhg_idx = idx; 177 grp_priv->nh_control = ctl; 178 CHT_SLIST_INSERT_HEAD(&ctl->gr_head, mpath, grp_priv); 179 180 NHOPS_WUNLOCK(ctl); 181 182 #if DEBUG_MAX_LEVEL >= LOG_DEBUG2 183 { 184 char nhgrp_buf[NHOP_PRINT_BUFSIZE]; 185 nhgrp_print_buf(grp_priv->nhg, nhgrp_buf, sizeof(nhgrp_buf)); 186 FIB_RH_LOG(LOG_DEBUG2, ctl->ctl_rh, "linked %s", nhgrp_buf); 187 } 188 #endif 189 consider_resize(ctl, new_num_buckets, new_num_items); 190 191 return (1); 192 } 193 194 struct nhgrp_priv * 195 unlink_nhgrp(struct nh_control *ctl, struct nhgrp_priv *key) 196 { 197 struct nhgrp_priv *nhg_priv_ret; 198 int idx; 199 200 NHOPS_WLOCK(ctl); 201 202 CHT_SLIST_REMOVE(&ctl->gr_head, mpath, key, nhg_priv_ret); 203 204 if (nhg_priv_ret == NULL) { 205 FIB_RH_LOG(LOG_DEBUG, ctl->ctl_rh, "Unable to find nhg"); 206 NHOPS_WUNLOCK(ctl); 207 return (NULL); 208 } 209 210 idx = nhg_priv_ret->nhg_idx; 211 bitmask_free_idx(&ctl->nh_idx_head, idx); 212 nhg_priv_ret->nhg_idx = 0; 213 nhg_priv_ret->nh_control = NULL; 214 215 NHOPS_WUNLOCK(ctl); 216 217 #if DEBUG_MAX_LEVEL >= LOG_DEBUG2 218 { 219 char nhgrp_buf[NHOP_PRINT_BUFSIZE]; 220 nhgrp_print_buf(nhg_priv_ret->nhg, nhgrp_buf, sizeof(nhgrp_buf)); 221 FIB_RH_LOG(LOG_DEBUG2, ctl->ctl_rh, "unlinked idx#%d %s", idx, 222 nhgrp_buf); 223 } 224 #endif 225 return (nhg_priv_ret); 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_gr_bucket, uint32_t new_idx_items) 234 { 235 void *gr_ptr, *gr_idx_ptr; 236 void *old_idx_ptr; 237 size_t alloc_size; 238 239 gr_ptr = NULL ; 240 if (new_gr_bucket != 0) { 241 alloc_size = CHT_SLIST_GET_RESIZE_SIZE(new_gr_bucket); 242 gr_ptr = malloc(alloc_size, M_NHOP, M_NOWAIT | M_ZERO); 243 } 244 245 gr_idx_ptr = NULL; 246 if (new_idx_items != 0) { 247 alloc_size = bitmask_get_size(new_idx_items); 248 gr_idx_ptr = malloc(alloc_size, M_NHOP, M_NOWAIT | M_ZERO); 249 } 250 251 if (gr_ptr == NULL && gr_idx_ptr == NULL) { 252 /* Either resize is not required or allocations have failed. */ 253 return; 254 } 255 256 FIB_RH_LOG(LOG_DEBUG, ctl->ctl_rh, 257 "going to resize nhg hash: [ptr:%p sz:%u] idx:[ptr:%p sz:%u]", 258 gr_ptr, new_gr_bucket, gr_idx_ptr, new_idx_items); 259 260 old_idx_ptr = NULL; 261 262 NHOPS_WLOCK(ctl); 263 if (gr_ptr != NULL) { 264 CHT_SLIST_RESIZE(&ctl->gr_head, mpath, gr_ptr, new_gr_bucket); 265 } 266 if (gr_idx_ptr != NULL) { 267 if (bitmask_copy(&ctl->nh_idx_head, gr_idx_ptr, new_idx_items) == 0) 268 bitmask_swap(&ctl->nh_idx_head, gr_idx_ptr, new_idx_items, &old_idx_ptr); 269 } 270 NHOPS_WUNLOCK(ctl); 271 272 if (gr_ptr != NULL) 273 free(gr_ptr, M_NHOP); 274 if (old_idx_ptr != NULL) 275 free(old_idx_ptr, M_NHOP); 276 } 277 278 /* 279 * Function allocating the necessary group data structures. 280 */ 281 bool 282 nhgrp_ctl_alloc_default(struct nh_control *ctl, int malloc_flags) 283 { 284 size_t alloc_size; 285 uint32_t num_buckets; 286 void *cht_ptr; 287 288 malloc_flags = (malloc_flags & (M_NOWAIT | M_WAITOK)) | M_ZERO; 289 290 num_buckets = 8; 291 alloc_size = CHT_SLIST_GET_RESIZE_SIZE(num_buckets); 292 cht_ptr = malloc(alloc_size, M_NHOP, malloc_flags); 293 294 if (cht_ptr == NULL) { 295 FIB_RH_LOG(LOG_WARNING, ctl->ctl_rh, "multipath init failed"); 296 return (false); 297 } 298 299 NHOPS_WLOCK(ctl); 300 301 if (ctl->gr_head.hash_size == 0) { 302 /* Init hash and bitmask */ 303 CHT_SLIST_INIT(&ctl->gr_head, cht_ptr, num_buckets); 304 NHOPS_WUNLOCK(ctl); 305 } else { 306 /* Other thread has already initiliazed hash/bitmask */ 307 NHOPS_WUNLOCK(ctl); 308 free(cht_ptr, M_NHOP); 309 } 310 311 FIB_RH_LOG(LOG_DEBUG, ctl->ctl_rh, "multipath init done"); 312 313 return (true); 314 } 315 316 int 317 nhgrp_ctl_init(struct nh_control *ctl) 318 { 319 320 /* 321 * By default, do not allocate datastructures as multipath 322 * routes will not be necessarily used. 323 */ 324 CHT_SLIST_INIT(&ctl->gr_head, NULL, 0); 325 return (0); 326 } 327 328 void 329 nhgrp_ctl_free(struct nh_control *ctl) 330 { 331 if (ctl->gr_head.ptr != NULL) 332 free(ctl->gr_head.ptr, M_NHOP); 333 } 334 335 void 336 nhgrp_ctl_unlink_all(struct nh_control *ctl) 337 { 338 struct nhgrp_priv *nhg_priv; 339 340 NHOPS_WLOCK_ASSERT(ctl); 341 342 CHT_SLIST_FOREACH(&ctl->gr_head, mpath, nhg_priv) { 343 #if DEBUG_MAX_LEVEL >= LOG_DEBUG 344 char nhgbuf[NHOP_PRINT_BUFSIZE]; 345 FIB_RH_LOG(LOG_DEBUG, ctl->ctl_rh, "marking %s unlinked", 346 nhgrp_print_buf(nhg_priv->nhg, nhgbuf, sizeof(nhgbuf))); 347 #endif 348 refcount_release(&nhg_priv->nhg_linked); 349 } CHT_SLIST_FOREACH_END; 350 } 351 352