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))
75 struct sa_in6 {
76 uint8_t sin6_len;
77 uint8_t sin6_family;
78 uint8_t pad[6];
79 struct in6_addr sin6_addr;
80 };
81 struct 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
88 struct 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
97 static struct nhop_object *
lradix6_lookup(void * algo_data,const struct flm_lookup_key key,uint32_t scopeid)98 lradix6_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
114 static uint8_t
lradix6_get_pref(const struct rib_rtable_info * rinfo)115 lradix6_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
126 static enum flm_op_result
lradix6_init(uint32_t fibnum,struct fib_data * fd,void * _old_data,void ** _data)127 lradix6_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
154 static void
lradix6_destroy(void * _data)155 lradix6_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
166 static enum flm_op_result
lradix6_add_route_cb(struct rtentry * rt,void * _data)167 lradix6_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
207 static enum flm_op_result
lradix6_end_dump(void * _data,struct fib_dp * dp)208 lradix6_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
218 static enum flm_op_result
lradix6_change_cb(struct rib_head * rnh,struct rib_cmd_info * rc,void * _data)219 lradix6_change_cb(struct rib_head *rnh, struct rib_cmd_info *rc,
220 void *_data)
221 {
222
223 return (FLM_REBUILD);
224 }
225
226 struct 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
242 struct radix6_data {
243 struct fib_data *fd;
244 struct rib_head *rh;
245 };
246
247 static struct nhop_object *
radix6_lookup(void * algo_data,const struct flm_lookup_key key,uint32_t scopeid)248 radix6_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
274 struct nhop_object *
fib6_radix_lookup_nh(uint32_t fibnum,const struct in6_addr * dst6,uint32_t scopeid)275 fib6_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
286 static uint8_t
radix6_get_pref(const struct rib_rtable_info * rinfo)287 radix6_get_pref(const struct rib_rtable_info *rinfo)
288 {
289
290 return (50);
291 }
292
293 static enum flm_op_result
radix6_init(uint32_t fibnum,struct fib_data * fd,void * _old_data,void ** _data)294 radix6_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
309 static void
radix6_destroy(void * _data)310 radix6_destroy(void *_data)
311 {
312
313 free(_data, M_RTABLE);
314 }
315
316 static enum flm_op_result
radix6_add_route_cb(struct rtentry * rt,void * _data)317 radix6_add_route_cb(struct rtentry *rt, void *_data)
318 {
319
320 return (FLM_SUCCESS);
321 }
322
323 static enum flm_op_result
radix6_end_dump(void * _data,struct fib_dp * dp)324 radix6_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
334 static enum flm_op_result
radix6_change_cb(struct rib_head * rnh,struct rib_cmd_info * rc,void * _data)335 radix6_change_cb(struct rib_head *rnh, struct rib_cmd_info *rc,
336 void *_data)
337 {
338
339 return (FLM_SUCCESS);
340 }
341
342 struct 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
353 static void
fib6_algo_init(void)354 fib6_algo_init(void)
355 {
356
357 fib_module_register(&flm_radix6_lockless);
358 fib_module_register(&flm_radix6);
359 }
360 SYSINIT(fib6_algo_init, SI_SUB_PROTO_DOMAIN, SI_ORDER_THIRD, fib6_algo_init, NULL);
361