xref: /freebsd/sys/netinet6/in6_fib_algo.c (revision cfd6422a5217410fbd66f7a7a8a64d9d85e61229)
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_inet6.h"
31 
32 #include <sys/param.h>
33 #include <sys/eventhandler.h>
34 #include <sys/kernel.h>
35 #include <sys/lock.h>
36 #include <sys/rmlock.h>
37 #include <sys/malloc.h>
38 #include <sys/mbuf.h>
39 #include <sys/module.h>
40 #include <sys/kernel.h>
41 #include <sys/priv.h>
42 #include <sys/proc.h>
43 #include <sys/socket.h>
44 #include <sys/socketvar.h>
45 #include <sys/sysctl.h>
46 #include <net/vnet.h>
47 
48 #include <net/if.h>
49 #include <net/if_var.h>
50 
51 #include <netinet/in.h>
52 #include <netinet/in_var.h>
53 #include <netinet/ip.h>
54 #include <netinet/ip_var.h>
55 #include <netinet/ip6.h>
56 #include <netinet6/ip6_var.h>
57 #include <netinet6/in6_fib.h>
58 
59 #include <net/route.h>
60 #include <net/route/nhop.h>
61 #include <net/route/route_ctl.h>
62 #include <net/route/route_var.h>
63 #include <net/route/fib_algo.h>
64 
65 /*
66  * Lockless radix lookup algo.
67  *
68  * Compiles immutable radix from the current routing table.
69  * Used with small amount of routes (<1000).
70  * As datastructure is immutable, it gets rebuild on each rtable change.
71  *
72  */
73 
74 #define KEY_LEN_INET6	(offsetof(struct sa_in6, sin6_addr) + sizeof(struct in6_addr))
75 #define OFF_LEN_INET6	(8 * offsetof(struct sa_in6, sin6_addr))
76 struct sa_in6 {
77 	uint8_t			sin6_len;
78 	uint8_t			sin6_family;
79 	uint8_t			pad[6];
80 	struct in6_addr		sin6_addr;
81 };
82 struct radix6_addr_entry {
83 	struct radix_node	rn[2];
84 	struct sa_in6		addr;
85 	struct nhop_object	*nhop;
86 };
87 #define	LRADIX6_ITEM_SZ	roundup2(sizeof(struct radix6_addr_entry), CACHE_LINE_SIZE)
88 
89 struct lradix6_data {
90 	struct radix_node_head	*rnh;
91 	struct fib_data		*fd;
92 	void			*mem; // raw radix_mem pointer to free
93 	void			*radix_mem;
94 	uint32_t		alloc_items;
95 	uint32_t		num_items;
96 };
97 
98 static struct nhop_object *
99 lradix6_lookup(void *algo_data, const struct flm_lookup_key key, uint32_t scopeid)
100 {
101 	struct radix_node_head *rnh = (struct radix_node_head *)algo_data;
102 	struct radix6_addr_entry *ent;
103 	struct sa_in6 addr6 = {
104 		.sin6_len = KEY_LEN_INET6,
105 		.sin6_addr = *key.addr6,
106 	};
107 	if (IN6_IS_SCOPE_LINKLOCAL(key.addr6))
108 		addr6.sin6_addr.s6_addr16[1] = htons(scopeid & 0xffff);
109 	ent = (struct radix6_addr_entry *)(rn_match(&addr6, &rnh->rh));
110 	if (ent != NULL)
111 		return (ent->nhop);
112 	return (NULL);
113 }
114 
115 static uint8_t
116 lradix6_get_pref(const struct rib_rtable_info *rinfo)
117 {
118 
119 	if (rinfo->num_prefixes < 10)
120 		return (255);
121 	else if (rinfo->num_prefixes < 100000)
122 		return (255 - rinfo->num_prefixes / 394);
123 	else
124 		return (1);
125 }
126 
127 static enum flm_op_result
128 lradix6_init(uint32_t fibnum, struct fib_data *fd, void *_old_data, void **_data)
129 {
130 	struct lradix6_data *lr;
131 	struct rib_rtable_info rinfo;
132 	uint32_t count;
133 	void *mem;
134 
135 	lr = malloc(sizeof(struct lradix6_data), M_RTABLE, M_NOWAIT | M_ZERO);
136 	if (lr == NULL || !rn_inithead((void **)&lr->rnh, OFF_LEN_INET6))
137 		return (FLM_REBUILD);
138 	fib_get_rtable_info(fib_get_rh(fd), &rinfo);
139 
140 	count = rinfo.num_prefixes * 11 / 10;
141 	// count+1 adds at least 1 cache line
142 	mem = malloc((count + 1) * LRADIX6_ITEM_SZ, M_RTABLE, M_NOWAIT | M_ZERO);
143 	if (mem == NULL)
144 		return (FLM_REBUILD);
145 	lr->mem = mem;
146 	lr->radix_mem = (void *)roundup2((uintptr_t)mem, CACHE_LINE_SIZE);
147 	lr->alloc_items = count;
148 	lr->fd = fd;
149 
150 	*_data = lr;
151 
152 	return (FLM_SUCCESS);
153 }
154 
155 static void
156 lradix6_destroy(void *_data)
157 {
158 	struct lradix6_data *lr = (struct lradix6_data *)_data;
159 
160 	if (lr->rnh != NULL)
161 		rn_detachhead((void **)&lr->rnh);
162 	if (lr->mem != NULL)
163 		free(lr->mem, M_RTABLE);
164 	free(lr, M_RTABLE);
165 }
166 
167 static enum flm_op_result
168 lradix6_add_route_cb(struct rtentry *rt, void *_data)
169 {
170 	struct lradix6_data *lr = (struct lradix6_data *)_data;
171 	struct radix6_addr_entry *ae;
172 	struct sockaddr_in6 *rt_dst, *rt_mask;
173 	struct sa_in6 mask;
174 	struct radix_node *rn;
175 	struct nhop_object *nh;
176 
177 	nh = rt_get_raw_nhop(rt);
178 
179 	if (lr->num_items >= lr->alloc_items)
180 		return (FLM_REBUILD);
181 
182 	ae = (struct radix6_addr_entry *)((char *)lr->radix_mem + lr->num_items * LRADIX6_ITEM_SZ);
183 	lr->num_items++;
184 
185 	ae->nhop = nh;
186 
187 	rt_dst = (struct sockaddr_in6 *)rt_key(rt);
188 	rt_mask = (struct sockaddr_in6 *)rt_mask(rt);
189 
190 	ae->addr.sin6_len = KEY_LEN_INET6;
191 	ae->addr.sin6_addr = rt_dst->sin6_addr;
192 
193 	if (rt_mask != NULL) {
194 		bzero(&mask, sizeof(mask));
195 		mask.sin6_len = KEY_LEN_INET6;
196 		mask.sin6_addr = rt_mask->sin6_addr;
197 		rt_mask = (struct sockaddr_in6 *)&mask;
198 	}
199 
200 	rn = lr->rnh->rnh_addaddr((struct sockaddr *)&ae->addr,
201 	    (struct sockaddr *)rt_mask, &lr->rnh->rh, ae->rn);
202 	if (rn == NULL)
203 		return (FLM_REBUILD);
204 
205 	return (FLM_SUCCESS);
206 }
207 
208 static enum flm_op_result
209 lradix6_end_dump(void *_data, struct fib_dp *dp)
210 {
211 	struct lradix6_data *lr = (struct lradix6_data *)_data;
212 
213 	dp->f = lradix6_lookup;
214 	dp->arg = lr->rnh;
215 
216 	return (FLM_SUCCESS);
217 }
218 
219 static enum flm_op_result
220 lradix6_change_cb(struct rib_head *rnh, struct rib_cmd_info *rc,
221     void *_data)
222 {
223 
224 	return (FLM_REBUILD);
225 }
226 
227 struct fib_lookup_module flm_radix6_lockless = {
228 	.flm_name = "radix6_lockless",
229 	.flm_family = AF_INET6,
230 	.flm_init_cb = lradix6_init,
231 	.flm_destroy_cb = lradix6_destroy,
232 	.flm_dump_rib_item_cb = lradix6_add_route_cb,
233 	.flm_dump_end_cb = lradix6_end_dump,
234 	.flm_change_rib_item_cb = lradix6_change_cb,
235 	.flm_get_pref = lradix6_get_pref,
236 };
237 
238 /*
239  * Fallback lookup algorithm.
240  * This is a simple wrapper around system radix.
241  */
242 
243 struct radix6_data {
244 	struct fib_data *fd;
245 	struct rib_head *rh;
246 };
247 
248 static struct nhop_object *
249 radix6_lookup(void *algo_data, const struct flm_lookup_key key, uint32_t scopeid)
250 {
251 	RIB_RLOCK_TRACKER;
252 	struct rib_head *rh = (struct rib_head *)algo_data;
253 	struct radix_node *rn;
254 	struct nhop_object *nh;
255 
256 	/* Prepare lookup key */
257 	struct sockaddr_in6 sin6 = {
258 		.sin6_family = AF_INET6,
259 		.sin6_len = sizeof(struct sockaddr_in6),
260 		.sin6_addr = *key.addr6,
261 	};
262 	if (IN6_IS_SCOPE_LINKLOCAL(key.addr6))
263 		sin6.sin6_addr.s6_addr16[1] = htons(scopeid & 0xffff);
264 
265 	nh = NULL;
266 	RIB_RLOCK(rh);
267 	rn = rn_match((void *)&sin6, &rh->head);
268 	if (rn != NULL && ((rn->rn_flags & RNF_ROOT) == 0))
269 		nh = (RNTORT(rn))->rt_nhop;
270 	RIB_RUNLOCK(rh);
271 
272 	return (nh);
273 }
274 
275 struct nhop_object *
276 fib6_radix_lookup_nh(uint32_t fibnum, const struct in6_addr *dst6, uint32_t scopeid)
277 {
278 	struct rib_head *rh = rh = rt_tables_get_rnh(fibnum, AF_INET6);
279 	const struct flm_lookup_key key = { .addr6 = dst6 };
280 
281 	if (rh == NULL)
282 		return (NULL);
283 
284 	return (radix6_lookup(rh, key, scopeid));
285 }
286 
287 static uint8_t
288 radix6_get_pref(const struct rib_rtable_info *rinfo)
289 {
290 
291 	return (50);
292 }
293 
294 static enum flm_op_result
295 radix6_init(uint32_t fibnum, struct fib_data *fd, void *_old_data, void **_data)
296 {
297 	struct radix6_data *r6;
298 
299 	r6 = malloc(sizeof(struct radix6_data), M_RTABLE, M_NOWAIT | M_ZERO);
300 	if (r6 == NULL)
301 		return (FLM_REBUILD);
302 	r6->fd = fd;
303 	r6->rh = fib_get_rh(fd);
304 
305 	*_data = r6;
306 
307 	return (FLM_SUCCESS);
308 }
309 
310 static void
311 radix6_destroy(void *_data)
312 {
313 
314 	free(_data, M_RTABLE);
315 }
316 
317 static enum flm_op_result
318 radix6_add_route_cb(struct rtentry *rt, void *_data)
319 {
320 
321 	return (FLM_SUCCESS);
322 }
323 
324 static enum flm_op_result
325 radix6_end_dump(void *_data, struct fib_dp *dp)
326 {
327 	struct radix6_data *r6 = (struct radix6_data *)_data;
328 
329 	dp->f = radix6_lookup;
330 	dp->arg = r6->rh;
331 
332 	return (FLM_SUCCESS);
333 }
334 
335 static enum flm_op_result
336 radix6_change_cb(struct rib_head *rnh, struct rib_cmd_info *rc,
337     void *_data)
338 {
339 
340 	return (FLM_SUCCESS);
341 }
342 
343 struct fib_lookup_module flm_radix6 = {
344 	.flm_name = "radix6",
345 	.flm_family = AF_INET6,
346 	.flm_init_cb = radix6_init,
347 	.flm_destroy_cb = radix6_destroy,
348 	.flm_dump_rib_item_cb = radix6_add_route_cb,
349 	.flm_dump_end_cb = radix6_end_dump,
350 	.flm_change_rib_item_cb = radix6_change_cb,
351 	.flm_get_pref = radix6_get_pref,
352 };
353 
354 static void
355 fib6_algo_init(void)
356 {
357 
358 	fib_module_register(&flm_radix6_lockless);
359 	fib_module_register(&flm_radix6);
360 }
361 SYSINIT(fib6_algo_init, SI_SUB_PROTO_DOMAIN, SI_ORDER_THIRD, fib6_algo_init, NULL);
362