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
nhops_init_rib(struct rib_head * rh)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
destroy_ctl(struct nh_control * ctl)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
destroy_ctl_epoch(epoch_context_t ctx)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
nhops_destroy_rib(struct rib_head * rh)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
djb_hash(const unsigned char * h,const int len)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
hash_priv(const struct nhop_priv * priv)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
consider_resize(struct nh_control * ctl,uint32_t new_nh_buckets,uint32_t new_idx_items)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
link_nhop(struct nh_control * ctl,struct nhop_priv * nh_priv)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 *
unlink_nhop(struct nh_control * ctl,struct nhop_priv * nh_priv_del)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 *
find_nhop(struct nh_control * ctl,const struct nhop_priv * nh_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 }
392