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