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 /*
64 * This file contains data structures management logic for the nexthop
65 * groups ("nhgrp") route subsystem.
66 *
67 * Nexthop groups are used to store multiple routes available for the specific
68 * prefix. Nexthop groups are immutable and can be shared across multiple
69 * prefixes.
70 *
71 * Each group consists of a control plane part and a dataplane part.
72 * Control plane is basically a collection of nexthop objects with
73 * weights and refcount.
74 *
75 * Datapath consists of a array of nexthop pointers, compiled from control
76 * plane data to support O(1) nexthop selection.
77 *
78 * For example, consider the following group:
79 * [(nh1, weight=100), (nh2, weight=200)]
80 * It will compile to the following array:
81 * [nh1, nh2, nh2]
82 *
83 */
84
85 static void consider_resize(struct nh_control *ctl, uint32_t new_nh_buckets,
86 uint32_t new_idx_items);
87
88 static int cmp_nhgrp(const struct nhgrp_priv *a, const struct nhgrp_priv *b);
89 static unsigned int hash_nhgrp(const struct nhgrp_priv *obj);
90
91 static unsigned
djb_hash(const unsigned char * h,const int len)92 djb_hash(const unsigned char *h, const int len)
93 {
94 unsigned int result = 0;
95 int i;
96
97 for (i = 0; i < len; i++)
98 result = 33 * result ^ h[i];
99
100 return (result);
101 }
102
103 static int
cmp_nhgrp(const struct nhgrp_priv * a,const struct nhgrp_priv * b)104 cmp_nhgrp(const struct nhgrp_priv *a, const struct nhgrp_priv *b)
105 {
106
107 /*
108 * In case of consistent hashing, there can be multiple nexthop groups
109 * with the same "control plane" list of nexthops with weights and a
110 * different set of "data plane" nexthops.
111 * For now, ignore the data plane and focus on the control plane list.
112 */
113 if (a->nhg_nh_count != b->nhg_nh_count)
114 return (0);
115 return !memcmp(a->nhg_nh_weights, b->nhg_nh_weights,
116 sizeof(struct weightened_nhop) * a->nhg_nh_count);
117 }
118
119 /*
120 * Hash callback: calculate hash of an object
121 */
122 static unsigned int
hash_nhgrp(const struct nhgrp_priv * obj)123 hash_nhgrp(const struct nhgrp_priv *obj)
124 {
125 const unsigned char *key;
126
127 key = (const unsigned char *)obj->nhg_nh_weights;
128
129 return (djb_hash(key, sizeof(struct weightened_nhop) * obj->nhg_nh_count));
130 }
131
132 /*
133 * Returns object referenced and unlocked
134 */
135 struct nhgrp_priv *
find_nhgrp(struct nh_control * ctl,const struct nhgrp_priv * key)136 find_nhgrp(struct nh_control *ctl, const struct nhgrp_priv *key)
137 {
138 struct nhgrp_priv *priv_ret;
139
140 NHOPS_RLOCK(ctl);
141 CHT_SLIST_FIND_BYOBJ(&ctl->gr_head, mpath, key, priv_ret);
142 if (priv_ret != NULL) {
143 if (refcount_acquire_if_not_zero(&priv_ret->nhg_refcount) == 0) {
144 /* refcount is 0 -> group is being deleted */
145 priv_ret = NULL;
146 }
147 }
148 NHOPS_RUNLOCK(ctl);
149
150 return (priv_ret);
151 }
152
153 int
link_nhgrp(struct nh_control * ctl,struct nhgrp_priv * grp_priv)154 link_nhgrp(struct nh_control *ctl, struct nhgrp_priv *grp_priv)
155 {
156 uint16_t idx;
157 uint32_t new_num_buckets, new_num_items;
158
159 NHOPS_WLOCK(ctl);
160 /* Check if we need to resize hash and index */
161 new_num_buckets = CHT_SLIST_GET_RESIZE_BUCKETS(&ctl->gr_head);
162 new_num_items = bitmask_get_resize_items(&ctl->gr_idx_head);
163
164 if (bitmask_alloc_idx(&ctl->gr_idx_head, &idx) != 0) {
165 NHOPS_WUNLOCK(ctl);
166 DPRINTF("Unable to allocate mpath index");
167 consider_resize(ctl, new_num_buckets, new_num_items);
168 return (0);
169 }
170
171 grp_priv->nhg_idx = idx;
172 grp_priv->nh_control = ctl;
173 CHT_SLIST_INSERT_HEAD(&ctl->gr_head, mpath, grp_priv);
174
175 NHOPS_WUNLOCK(ctl);
176
177 consider_resize(ctl, new_num_buckets, new_num_items);
178
179 return (1);
180 }
181
182 struct nhgrp_priv *
unlink_nhgrp(struct nh_control * ctl,struct nhgrp_priv * key)183 unlink_nhgrp(struct nh_control *ctl, struct nhgrp_priv *key)
184 {
185 struct nhgrp_priv *nhg_priv_ret;
186 int ret, idx;
187
188 NHOPS_WLOCK(ctl);
189
190 CHT_SLIST_REMOVE_BYOBJ(&ctl->gr_head, mpath, key, nhg_priv_ret);
191
192 if (nhg_priv_ret == NULL) {
193 DPRINTF("Unable to find nhop group!");
194 NHOPS_WUNLOCK(ctl);
195 return (NULL);
196 }
197
198 idx = nhg_priv_ret->nhg_idx;
199 ret = bitmask_free_idx(&ctl->gr_idx_head, idx);
200 nhg_priv_ret->nhg_idx = 0;
201 nhg_priv_ret->nh_control = NULL;
202
203 NHOPS_WUNLOCK(ctl);
204
205 return (nhg_priv_ret);
206 }
207
208 /*
209 * Checks if hash needs resizing and performs this resize if necessary
210 *
211 */
212 __noinline static void
consider_resize(struct nh_control * ctl,uint32_t new_nh_buckets,uint32_t new_idx_items)213 consider_resize(struct nh_control *ctl, uint32_t new_nh_buckets, uint32_t new_idx_items)
214 {
215 void *nh_ptr, *nh_idx_ptr;
216 void *old_idx_ptr;
217 size_t alloc_size;
218
219 nh_ptr = NULL ;
220 if (new_nh_buckets != 0) {
221 alloc_size = CHT_SLIST_GET_RESIZE_SIZE(new_nh_buckets);
222 nh_ptr = malloc(alloc_size, M_NHOP, M_NOWAIT | M_ZERO);
223 }
224
225 nh_idx_ptr = NULL;
226 if (new_idx_items != 0) {
227 alloc_size = bitmask_get_size(new_idx_items);
228 nh_idx_ptr = malloc(alloc_size, M_NHOP, M_NOWAIT | M_ZERO);
229 }
230
231 if (nh_ptr == NULL && nh_idx_ptr == NULL) {
232 /* Either resize is not required or allocations have failed. */
233 return;
234 }
235
236 DPRINTF("mp: going to resize: nh:[ptr:%p sz:%u] idx:[ptr:%p sz:%u]",
237 nh_ptr, new_nh_buckets, nh_idx_ptr, new_idx_items);
238
239 old_idx_ptr = NULL;
240
241 NHOPS_WLOCK(ctl);
242 if (nh_ptr != NULL) {
243 CHT_SLIST_RESIZE(&ctl->gr_head, mpath, nh_ptr, new_nh_buckets);
244 }
245 if (nh_idx_ptr != NULL) {
246 if (bitmask_copy(&ctl->gr_idx_head, nh_idx_ptr, new_idx_items) == 0)
247 bitmask_swap(&ctl->gr_idx_head, nh_idx_ptr, new_idx_items, &old_idx_ptr);
248 }
249 NHOPS_WUNLOCK(ctl);
250
251 if (nh_ptr != NULL)
252 free(nh_ptr, M_NHOP);
253 if (old_idx_ptr != NULL)
254 free(old_idx_ptr, M_NHOP);
255 }
256
257 /*
258 * Function allocating the necessary group data structures.
259 */
260 bool
nhgrp_ctl_alloc_default(struct nh_control * ctl,int malloc_flags)261 nhgrp_ctl_alloc_default(struct nh_control *ctl, int malloc_flags)
262 {
263 size_t alloc_size;
264 uint32_t num_buckets, num_items;
265 void *cht_ptr, *mask_ptr;
266
267 malloc_flags = (malloc_flags & (M_NOWAIT | M_WAITOK)) | M_ZERO;
268
269 num_buckets = 8;
270 alloc_size = CHT_SLIST_GET_RESIZE_SIZE(num_buckets);
271 cht_ptr = malloc(alloc_size, M_NHOP, malloc_flags);
272
273 if (cht_ptr == NULL) {
274 DPRINTF("mpath init failed");
275 return (false);
276 }
277
278 /*
279 * Allocate nexthop index bitmask.
280 */
281 num_items = 128;
282 mask_ptr = malloc(bitmask_get_size(num_items), M_NHOP, malloc_flags);
283 if (mask_ptr == NULL) {
284 DPRINTF("mpath bitmask init failed");
285 free(cht_ptr, M_NHOP);
286 return (false);
287 }
288
289 NHOPS_WLOCK(ctl);
290
291 if (ctl->gr_head.hash_size == 0) {
292 /* Init hash and bitmask */
293 CHT_SLIST_INIT(&ctl->gr_head, cht_ptr, num_buckets);
294 bitmask_init(&ctl->gr_idx_head, mask_ptr, num_items);
295 NHOPS_WUNLOCK(ctl);
296 } else {
297 /* Other thread has already initiliazed hash/bitmask */
298 NHOPS_WUNLOCK(ctl);
299 free(cht_ptr, M_NHOP);
300 free(mask_ptr, M_NHOP);
301 }
302
303 DPRINTF("mpath init done for fib/af %d/%d", ctl->rh->rib_fibnum,
304 ctl->rh->rib_family);
305
306 return (true);
307 }
308
309 int
nhgrp_ctl_init(struct nh_control * ctl)310 nhgrp_ctl_init(struct nh_control *ctl)
311 {
312
313 /*
314 * By default, do not allocate datastructures as multipath
315 * routes will not be necessarily used.
316 */
317 CHT_SLIST_INIT(&ctl->gr_head, NULL, 0);
318 bitmask_init(&ctl->gr_idx_head, NULL, 0);
319 return (0);
320 }
321
322 void
nhgrp_ctl_free(struct nh_control * ctl)323 nhgrp_ctl_free(struct nh_control *ctl)
324 {
325
326 if (ctl->gr_head.ptr != NULL)
327 free(ctl->gr_head.ptr, M_NHOP);
328 if (ctl->gr_idx_head.idx != NULL)
329 free(ctl->gr_idx_head.idx, M_NHOP);
330 }
331
332 void
nhgrp_ctl_unlink_all(struct nh_control * ctl)333 nhgrp_ctl_unlink_all(struct nh_control *ctl)
334 {
335 struct nhgrp_priv *nhg_priv;
336
337 NHOPS_WLOCK_ASSERT(ctl);
338
339 CHT_SLIST_FOREACH(&ctl->gr_head, mpath, nhg_priv) {
340 DPRINTF("Marking nhgrp %u unlinked", nhg_priv->nhg_idx);
341 refcount_release(&nhg_priv->nhg_linked);
342 } CHT_SLIST_FOREACH_END;
343 }
344
345