Line data Source code
1 : /* $OpenBSD: rtable.c,v 1.64 2018/09/09 10:07:38 henning Exp $ */
2 :
3 : /*
4 : * Copyright (c) 2014-2016 Martin Pieuchot
5 : *
6 : * Permission to use, copy, modify, and distribute this software for any
7 : * purpose with or without fee is hereby granted, provided that the above
8 : * copyright notice and this permission notice appear in all copies.
9 : *
10 : * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
11 : * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
12 : * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
13 : * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
14 : * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
15 : * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
16 : * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
17 : */
18 :
19 : #ifndef _KERNEL
20 : #include "kern_compat.h"
21 : #else
22 : #include <sys/param.h>
23 : #include <sys/systm.h>
24 : #include <sys/socket.h>
25 : #include <sys/malloc.h>
26 : #include <sys/queue.h>
27 : #include <sys/domain.h>
28 : #include <sys/srp.h>
29 : #endif
30 :
31 : #include <net/rtable.h>
32 : #include <net/route.h>
33 :
34 : /*
35 : * Structures used by rtable_get() to retrieve the corresponding
36 : * routing table for a given pair of ``af'' and ``rtableid''.
37 : *
38 : * Note that once allocated routing table heads are never freed.
39 : * This way we do not need to reference count them.
40 : *
41 : * afmap rtmap/dommp
42 : * ----------- --------- -----
43 : * | 0 |--------> | 0 | 0 | ... | 0 | Array mapping rtableid (=index)
44 : * ----------- --------- ----- to rdomain/loopback (=value).
45 : * | AF_INET |.
46 : * ----------- `. .---------. .---------.
47 : * ... `----> | rtable0 | ... | rtableN | Array of pointers for
48 : * ----------- '---------' '---------' IPv4 routing tables
49 : * | AF_MPLS | indexed by ``rtableid''.
50 : * -----------
51 : */
52 : struct srp *afmap;
53 : uint8_t af2idx[AF_MAX+1]; /* To only allocate supported AF */
54 : uint8_t af2idx_max;
55 :
56 : /* Array of routing table pointers. */
57 : struct rtmap {
58 : unsigned int limit;
59 : void **tbl;
60 : };
61 :
62 : /*
63 : * Array of rtableid -> rdomain mapping.
64 : *
65 : * Only used for the first index as describbed above.
66 : */
67 : struct dommp {
68 : unsigned int limit;
69 : /*
70 : * Array to get the routing domain and loopback interface related to
71 : * a routing table. Format:
72 : *
73 : * 8 unused bits | 16 bits for loopback index | 8 bits for rdomain
74 : */
75 : unsigned int *value;
76 : };
77 :
78 : unsigned int rtmap_limit = 0;
79 :
80 : void rtmap_init(void);
81 : void rtmap_grow(unsigned int, sa_family_t);
82 : void rtmap_dtor(void *, void *);
83 :
84 : struct srp_gc rtmap_gc = SRP_GC_INITIALIZER(rtmap_dtor, NULL);
85 :
86 : void rtable_init_backend(unsigned int);
87 : void *rtable_alloc(unsigned int, unsigned int, unsigned int);
88 : void *rtable_get(unsigned int, sa_family_t);
89 :
90 : void
91 0 : rtmap_init(void)
92 : {
93 : struct domain *dp;
94 : int i;
95 :
96 : /* Start with a single table for every domain that requires it. */
97 0 : for (i = 0; (dp = domains[i]) != NULL; i++) {
98 0 : if (dp->dom_rtoffset == 0)
99 : continue;
100 :
101 0 : rtmap_grow(1, dp->dom_family);
102 0 : }
103 :
104 : /* Initialize the rtableid->rdomain mapping table. */
105 0 : rtmap_grow(1, 0);
106 :
107 0 : rtmap_limit = 1;
108 0 : }
109 :
110 : /*
111 : * Grow the size of the array of routing table for AF ``af'' to ``nlimit''.
112 : */
113 : void
114 0 : rtmap_grow(unsigned int nlimit, sa_family_t af)
115 : {
116 : struct rtmap *map, *nmap;
117 : int i;
118 :
119 0 : KERNEL_ASSERT_LOCKED();
120 :
121 0 : KASSERT(nlimit > rtmap_limit);
122 :
123 0 : nmap = malloc(sizeof(*nmap), M_RTABLE, M_WAITOK);
124 0 : nmap->limit = nlimit;
125 0 : nmap->tbl = mallocarray(nlimit, sizeof(*nmap[0].tbl), M_RTABLE,
126 : M_WAITOK|M_ZERO);
127 :
128 0 : map = srp_get_locked(&afmap[af2idx[af]]);
129 0 : if (map != NULL) {
130 0 : KASSERT(map->limit == rtmap_limit);
131 :
132 0 : for (i = 0; i < map->limit; i++)
133 0 : nmap->tbl[i] = map->tbl[i];
134 : }
135 :
136 0 : srp_update_locked(&rtmap_gc, &afmap[af2idx[af]], nmap);
137 0 : }
138 :
139 : void
140 0 : rtmap_dtor(void *null, void *xmap)
141 : {
142 0 : struct rtmap *map = xmap;
143 :
144 : /*
145 : * doesnt need to be serialized since this is the last reference
146 : * to this map. there's nothing to race against.
147 : */
148 0 : free(map->tbl, M_RTABLE, map->limit * sizeof(*map[0].tbl));
149 0 : free(map, M_RTABLE, sizeof(*map));
150 0 : }
151 :
152 : void
153 0 : rtable_init(void)
154 : {
155 : struct domain *dp;
156 : unsigned int keylen = 0;
157 : int i;
158 :
159 : KASSERT(sizeof(struct rtmap) == sizeof(struct dommp));
160 :
161 : /* We use index 0 for the rtable/rdomain map. */
162 0 : af2idx_max = 1;
163 0 : memset(af2idx, 0, sizeof(af2idx));
164 :
165 : /*
166 : * Compute the maximum supported key length in case the routing
167 : * table backend needs it.
168 : */
169 0 : for (i = 0; (dp = domains[i]) != NULL; i++) {
170 0 : if (dp->dom_rtoffset == 0)
171 : continue;
172 :
173 0 : af2idx[dp->dom_family] = af2idx_max++;
174 0 : if (dp->dom_rtkeylen > keylen)
175 0 : keylen = dp->dom_rtkeylen;
176 :
177 : }
178 0 : rtable_init_backend(keylen);
179 :
180 : /*
181 : * Allocate AF-to-id table now that we now how many AFs this
182 : * kernel supports.
183 : */
184 0 : afmap = mallocarray(af2idx_max + 1, sizeof(*afmap), M_RTABLE,
185 : M_WAITOK|M_ZERO);
186 :
187 0 : rtmap_init();
188 :
189 0 : if (rtable_add(0) != 0)
190 0 : panic("unable to create default routing table");
191 0 : }
192 :
193 : int
194 0 : rtable_add(unsigned int id)
195 : {
196 : struct domain *dp;
197 : void *tbl;
198 : struct rtmap *map;
199 : struct dommp *dmm;
200 : sa_family_t af;
201 : unsigned int off, alen;
202 : int i;
203 :
204 0 : KERNEL_ASSERT_LOCKED();
205 :
206 0 : if (id > RT_TABLEID_MAX)
207 0 : return (EINVAL);
208 :
209 0 : if (rtable_exists(id))
210 0 : return (EEXIST);
211 :
212 0 : for (i = 0; (dp = domains[i]) != NULL; i++) {
213 0 : if (dp->dom_rtoffset == 0)
214 : continue;
215 :
216 0 : af = dp->dom_family;
217 : off = dp->dom_rtoffset;
218 0 : alen = dp->dom_maxplen;
219 :
220 0 : if (id >= rtmap_limit)
221 0 : rtmap_grow(id + 1, af);
222 :
223 0 : tbl = rtable_alloc(id, alen, off);
224 0 : if (tbl == NULL)
225 0 : return (ENOMEM);
226 :
227 0 : map = srp_get_locked(&afmap[af2idx[af]]);
228 0 : map->tbl[id] = tbl;
229 0 : }
230 :
231 : /* Reflect possible growth. */
232 0 : if (id >= rtmap_limit) {
233 0 : rtmap_grow(id + 1, 0);
234 0 : rtmap_limit = id + 1;
235 0 : }
236 :
237 : /* Use main rtable/rdomain by default. */
238 0 : dmm = srp_get_locked(&afmap[0]);
239 0 : dmm->value[id] = 0;
240 :
241 0 : return (0);
242 0 : }
243 :
244 : void *
245 0 : rtable_get(unsigned int rtableid, sa_family_t af)
246 : {
247 : struct rtmap *map;
248 : void *tbl = NULL;
249 0 : struct srp_ref sr;
250 :
251 0 : if (af >= nitems(af2idx) || af2idx[af] == 0)
252 0 : return (NULL);
253 :
254 0 : map = srp_enter(&sr, &afmap[af2idx[af]]);
255 0 : if (rtableid < map->limit)
256 0 : tbl = map->tbl[rtableid];
257 0 : srp_leave(&sr);
258 :
259 0 : return (tbl);
260 0 : }
261 :
262 : int
263 0 : rtable_exists(unsigned int rtableid)
264 : {
265 : struct domain *dp;
266 : void *tbl;
267 : int i;
268 :
269 0 : for (i = 0; (dp = domains[i]) != NULL; i++) {
270 0 : if (dp->dom_rtoffset == 0)
271 : continue;
272 :
273 0 : tbl = rtable_get(rtableid, dp->dom_family);
274 0 : if (tbl != NULL)
275 0 : return (1);
276 : }
277 :
278 0 : return (0);
279 0 : }
280 :
281 : int
282 0 : rtable_empty(unsigned int rtableid)
283 : {
284 : struct domain *dp;
285 : int i;
286 : struct art_root *tbl;
287 :
288 0 : for (i = 0; (dp = domains[i]) != NULL; i++) {
289 0 : if (dp->dom_rtoffset == 0)
290 : continue;
291 :
292 0 : tbl = rtable_get(rtableid, dp->dom_family);
293 0 : if (tbl == NULL)
294 : continue;
295 0 : if (tbl->ar_root.ref != NULL)
296 0 : return (0);
297 : }
298 :
299 0 : return (1);
300 0 : }
301 :
302 : unsigned int
303 0 : rtable_l2(unsigned int rtableid)
304 : {
305 : struct dommp *dmm;
306 : unsigned int rdomain = 0;
307 0 : struct srp_ref sr;
308 :
309 0 : dmm = srp_enter(&sr, &afmap[0]);
310 0 : if (rtableid < dmm->limit)
311 0 : rdomain = (dmm->value[rtableid] & RT_TABLEID_MASK);
312 0 : srp_leave(&sr);
313 :
314 0 : return (rdomain);
315 0 : }
316 :
317 : unsigned int
318 0 : rtable_loindex(unsigned int rtableid)
319 : {
320 : struct dommp *dmm;
321 : unsigned int loifidx = 0;
322 0 : struct srp_ref sr;
323 :
324 0 : dmm = srp_enter(&sr, &afmap[0]);
325 0 : if (rtableid < dmm->limit)
326 0 : loifidx = (dmm->value[rtableid] >> RT_TABLEID_BITS);
327 0 : srp_leave(&sr);
328 :
329 0 : return (loifidx);
330 0 : }
331 :
332 : void
333 0 : rtable_l2set(unsigned int rtableid, unsigned int rdomain, unsigned int loifidx)
334 : {
335 : struct dommp *dmm;
336 : unsigned int value;
337 :
338 0 : KERNEL_ASSERT_LOCKED();
339 :
340 0 : if (!rtable_exists(rtableid) || !rtable_exists(rdomain))
341 0 : return;
342 :
343 0 : value = (rdomain & RT_TABLEID_MASK) | (loifidx << RT_TABLEID_BITS);
344 :
345 0 : dmm = srp_get_locked(&afmap[0]);
346 0 : dmm->value[rtableid] = value;
347 0 : }
348 :
349 :
350 : static inline uint8_t *satoaddr(struct art_root *, struct sockaddr *);
351 :
352 : int an_match(struct art_node *, struct sockaddr *, int);
353 : void rtentry_ref(void *, void *);
354 : void rtentry_unref(void *, void *);
355 :
356 : void rtable_mpath_insert(struct art_node *, struct rtentry *);
357 :
358 : struct srpl_rc rt_rc = SRPL_RC_INITIALIZER(rtentry_ref, rtentry_unref, NULL);
359 :
360 : void
361 0 : rtable_init_backend(unsigned int keylen)
362 : {
363 0 : art_init();
364 0 : }
365 :
366 : void *
367 0 : rtable_alloc(unsigned int rtableid, unsigned int alen, unsigned int off)
368 : {
369 0 : return (art_alloc(rtableid, alen, off));
370 : }
371 :
372 : struct rtentry *
373 0 : rtable_lookup(unsigned int rtableid, struct sockaddr *dst,
374 : struct sockaddr *mask, struct sockaddr *gateway, uint8_t prio)
375 : {
376 : struct art_root *ar;
377 : struct art_node *an;
378 : struct rtentry *rt = NULL;
379 0 : struct srp_ref sr, nsr;
380 : uint8_t *addr;
381 : int plen;
382 :
383 0 : ar = rtable_get(rtableid, dst->sa_family);
384 0 : if (ar == NULL)
385 0 : return (NULL);
386 :
387 0 : addr = satoaddr(ar, dst);
388 :
389 : /* No need for a perfect match. */
390 0 : if (mask == NULL) {
391 0 : an = art_match(ar, addr, &nsr);
392 0 : if (an == NULL)
393 : goto out;
394 : } else {
395 0 : plen = rtable_satoplen(dst->sa_family, mask);
396 0 : if (plen == -1)
397 0 : return (NULL);
398 :
399 0 : an = art_lookup(ar, addr, plen, &nsr);
400 :
401 : /* Make sure we've got a perfect match. */
402 0 : if (!an_match(an, dst, plen))
403 : goto out;
404 : }
405 :
406 0 : SRPL_FOREACH(rt, &sr, &an->an_rtlist, rt_next) {
407 0 : if (prio != RTP_ANY &&
408 0 : (rt->rt_priority & RTP_MASK) != (prio & RTP_MASK))
409 : continue;
410 :
411 0 : if (gateway == NULL)
412 : break;
413 :
414 0 : if (rt->rt_gateway->sa_len == gateway->sa_len &&
415 0 : memcmp(rt->rt_gateway, gateway, gateway->sa_len) == 0)
416 : break;
417 : }
418 0 : if (rt != NULL)
419 0 : rtref(rt);
420 :
421 0 : SRPL_LEAVE(&sr);
422 : out:
423 0 : srp_leave(&nsr);
424 :
425 0 : return (rt);
426 0 : }
427 :
428 : struct rtentry *
429 0 : rtable_match(unsigned int rtableid, struct sockaddr *dst, uint32_t *src)
430 : {
431 : struct art_root *ar;
432 : struct art_node *an;
433 : struct rtentry *rt = NULL;
434 0 : struct srp_ref sr, nsr;
435 : uint8_t *addr;
436 : int hash;
437 :
438 0 : ar = rtable_get(rtableid, dst->sa_family);
439 0 : if (ar == NULL)
440 0 : return (NULL);
441 :
442 0 : addr = satoaddr(ar, dst);
443 :
444 0 : an = art_match(ar, addr, &nsr);
445 0 : if (an == NULL)
446 : goto out;
447 :
448 0 : rt = SRPL_FIRST(&sr, &an->an_rtlist);
449 0 : rtref(rt);
450 0 : SRPL_LEAVE(&sr);
451 :
452 : /* Gateway selection by Hash-Threshold (RFC 2992) */
453 0 : if ((hash = rt_hash(rt, dst, src)) != -1) {
454 : struct rtentry *mrt;
455 : int threshold, npaths = 0;
456 :
457 0 : KASSERT(hash <= 0xffff);
458 :
459 0 : SRPL_FOREACH(mrt, &sr, &an->an_rtlist, rt_next) {
460 : /* Only count nexthops with the same priority. */
461 0 : if (mrt->rt_priority == rt->rt_priority)
462 0 : npaths++;
463 : }
464 0 : SRPL_LEAVE(&sr);
465 :
466 0 : threshold = (0xffff / npaths) + 1;
467 :
468 : /*
469 : * we have no protection against concurrent modification of the
470 : * route list attached to the node, so we won't necessarily
471 : * have the same number of routes. for most modifications,
472 : * we'll pick a route that we wouldn't have if we only saw the
473 : * list before or after the change. if we were going to use
474 : * the last available route, but it got removed, we'll hit
475 : * the end of the list and then pick the first route.
476 : */
477 :
478 0 : mrt = SRPL_FIRST(&sr, &an->an_rtlist);
479 0 : while (hash > threshold && mrt != NULL) {
480 0 : if (mrt->rt_priority == rt->rt_priority)
481 0 : hash -= threshold;
482 0 : mrt = SRPL_FOLLOW(&sr, mrt, rt_next);
483 : }
484 :
485 0 : if (mrt != NULL) {
486 0 : rtref(mrt);
487 0 : rtfree(rt);
488 : rt = mrt;
489 0 : }
490 0 : SRPL_LEAVE(&sr);
491 0 : }
492 : out:
493 0 : srp_leave(&nsr);
494 0 : return (rt);
495 0 : }
496 :
497 : int
498 0 : rtable_insert(unsigned int rtableid, struct sockaddr *dst,
499 : struct sockaddr *mask, struct sockaddr *gateway, uint8_t prio,
500 : struct rtentry *rt)
501 : {
502 : struct rtentry *mrt;
503 0 : struct srp_ref sr;
504 : struct art_root *ar;
505 : struct art_node *an, *prev;
506 : uint8_t *addr;
507 : int plen;
508 : unsigned int rt_flags;
509 : int error = 0;
510 :
511 0 : ar = rtable_get(rtableid, dst->sa_family);
512 0 : if (ar == NULL)
513 0 : return (EAFNOSUPPORT);
514 :
515 0 : addr = satoaddr(ar, dst);
516 0 : plen = rtable_satoplen(dst->sa_family, mask);
517 0 : if (plen == -1)
518 0 : return (EINVAL);
519 :
520 0 : rtref(rt); /* guarantee rtfree won't do anything during insert */
521 0 : rw_enter_write(&ar->ar_lock);
522 :
523 : /* Do not permit exactly the same dst/mask/gw pair. */
524 0 : an = art_lookup(ar, addr, plen, &sr);
525 0 : srp_leave(&sr); /* an can't go away while we have the lock */
526 0 : if (an_match(an, dst, plen)) {
527 : struct rtentry *mrt;
528 0 : int mpathok = ISSET(rt->rt_flags, RTF_MPATH);
529 :
530 0 : SRPL_FOREACH_LOCKED(mrt, &an->an_rtlist, rt_next) {
531 0 : if (prio != RTP_ANY &&
532 0 : (mrt->rt_priority & RTP_MASK) != (prio & RTP_MASK))
533 : continue;
534 :
535 0 : if (!mpathok ||
536 0 : (mrt->rt_gateway->sa_len == gateway->sa_len &&
537 0 : !memcmp(mrt->rt_gateway, gateway, gateway->sa_len))){
538 : error = EEXIST;
539 0 : goto leave;
540 : }
541 : }
542 0 : }
543 :
544 0 : an = art_get(dst, plen);
545 0 : if (an == NULL) {
546 : error = ENOBUFS;
547 0 : goto leave;
548 : }
549 :
550 : /* prepare for immediate operation if insert succeeds */
551 0 : rt_flags = rt->rt_flags;
552 0 : rt->rt_flags &= ~RTF_MPATH;
553 0 : rt->rt_dest = dst;
554 0 : rt->rt_plen = plen;
555 0 : SRPL_INSERT_HEAD_LOCKED(&rt_rc, &an->an_rtlist, rt, rt_next);
556 :
557 0 : prev = art_insert(ar, an, addr, plen);
558 0 : if (prev != an) {
559 0 : SRPL_REMOVE_LOCKED(&rt_rc, &an->an_rtlist, rt, rtentry,
560 : rt_next);
561 0 : rt->rt_flags = rt_flags;
562 0 : art_put(an);
563 :
564 0 : if (prev == NULL) {
565 : error = ESRCH;
566 0 : goto leave;
567 : }
568 :
569 : an = prev;
570 :
571 0 : mrt = SRPL_FIRST_LOCKED(&an->an_rtlist);
572 0 : KASSERT(mrt != NULL);
573 0 : KASSERT((rt->rt_flags & RTF_MPATH) || mrt->rt_priority != prio);
574 :
575 : /*
576 : * An ART node with the same destination/netmask already
577 : * exists, MPATH conflict must have been already checked.
578 : */
579 0 : if (rt->rt_flags & RTF_MPATH) {
580 : /*
581 : * Only keep the RTF_MPATH flag if two routes have
582 : * the same gateway.
583 : */
584 0 : rt->rt_flags &= ~RTF_MPATH;
585 0 : SRPL_FOREACH_LOCKED(mrt, &an->an_rtlist, rt_next) {
586 0 : if (mrt->rt_priority == prio) {
587 0 : mrt->rt_flags |= RTF_MPATH;
588 0 : rt->rt_flags |= RTF_MPATH;
589 0 : }
590 : }
591 : }
592 :
593 : /* Put newly inserted entry at the right place. */
594 0 : rtable_mpath_insert(an, rt);
595 0 : }
596 : leave:
597 0 : rw_exit_write(&ar->ar_lock);
598 0 : rtfree(rt);
599 0 : return (error);
600 0 : }
601 :
602 : int
603 0 : rtable_delete(unsigned int rtableid, struct sockaddr *dst,
604 : struct sockaddr *mask, struct rtentry *rt)
605 : {
606 : struct art_root *ar;
607 : struct art_node *an;
608 0 : struct srp_ref sr;
609 : uint8_t *addr;
610 : int plen;
611 : struct rtentry *mrt;
612 : int npaths = 0;
613 : int error = 0;
614 :
615 0 : ar = rtable_get(rtableid, dst->sa_family);
616 0 : if (ar == NULL)
617 0 : return (EAFNOSUPPORT);
618 :
619 0 : addr = satoaddr(ar, dst);
620 0 : plen = rtable_satoplen(dst->sa_family, mask);
621 :
622 0 : rtref(rt); /* guarantee rtfree won't do anything under ar_lock */
623 0 : rw_enter_write(&ar->ar_lock);
624 0 : an = art_lookup(ar, addr, plen, &sr);
625 0 : srp_leave(&sr); /* an can't go away while we have the lock */
626 :
627 : /* Make sure we've got a perfect match. */
628 0 : if (!an_match(an, dst, plen)) {
629 : error = ESRCH;
630 0 : goto leave;
631 : }
632 :
633 : /*
634 : * If other multipath route entries are still attached to
635 : * this ART node we only have to unlink it.
636 : */
637 0 : SRPL_FOREACH_LOCKED(mrt, &an->an_rtlist, rt_next)
638 0 : npaths++;
639 :
640 0 : if (npaths > 1) {
641 0 : KASSERT(rt->rt_refcnt >= 1);
642 0 : SRPL_REMOVE_LOCKED(&rt_rc, &an->an_rtlist, rt, rtentry,
643 : rt_next);
644 :
645 0 : mrt = SRPL_FIRST_LOCKED(&an->an_rtlist);
646 0 : if (npaths == 2)
647 0 : mrt->rt_flags &= ~RTF_MPATH;
648 :
649 : goto leave;
650 : }
651 :
652 0 : if (art_delete(ar, an, addr, plen) == NULL)
653 0 : panic("art_delete failed to find node %p", an);
654 :
655 0 : KASSERT(rt->rt_refcnt >= 1);
656 0 : SRPL_REMOVE_LOCKED(&rt_rc, &an->an_rtlist, rt, rtentry, rt_next);
657 0 : art_put(an);
658 :
659 : leave:
660 0 : rw_exit_write(&ar->ar_lock);
661 0 : rtfree(rt);
662 :
663 0 : return (error);
664 0 : }
665 :
666 : struct rtable_walk_cookie {
667 : int (*rwc_func)(struct rtentry *, void *, unsigned int);
668 : void *rwc_arg;
669 : unsigned int rwc_rid;
670 : };
671 :
672 : /*
673 : * Helper for rtable_walk to keep the ART code free from any "struct rtentry".
674 : */
675 : int
676 0 : rtable_walk_helper(struct art_node *an, void *xrwc)
677 : {
678 0 : struct srp_ref sr;
679 0 : struct rtable_walk_cookie *rwc = xrwc;
680 : struct rtentry *rt;
681 : int error = 0;
682 :
683 0 : SRPL_FOREACH(rt, &sr, &an->an_rtlist, rt_next) {
684 0 : if ((error = (*rwc->rwc_func)(rt, rwc->rwc_arg, rwc->rwc_rid)))
685 : break;
686 : }
687 0 : SRPL_LEAVE(&sr);
688 :
689 0 : return (error);
690 0 : }
691 :
692 : int
693 0 : rtable_walk(unsigned int rtableid, sa_family_t af,
694 : int (*func)(struct rtentry *, void *, unsigned int), void *arg)
695 : {
696 : struct art_root *ar;
697 0 : struct rtable_walk_cookie rwc;
698 : int error;
699 :
700 0 : ar = rtable_get(rtableid, af);
701 0 : if (ar == NULL)
702 0 : return (EAFNOSUPPORT);
703 :
704 0 : rwc.rwc_func = func;
705 0 : rwc.rwc_arg = arg;
706 0 : rwc.rwc_rid = rtableid;
707 :
708 0 : while ((error = art_walk(ar, rtable_walk_helper, &rwc)) == EAGAIN)
709 0 : continue;
710 :
711 0 : return (error);
712 0 : }
713 :
714 : struct rtentry *
715 0 : rtable_iterate(struct rtentry *rt0)
716 : {
717 : struct rtentry *rt = NULL;
718 0 : struct srp_ref sr;
719 :
720 0 : rt = SRPL_NEXT(&sr, rt0, rt_next);
721 0 : if (rt != NULL)
722 0 : rtref(rt);
723 0 : SRPL_LEAVE(&sr);
724 0 : rtfree(rt0);
725 0 : return (rt);
726 0 : }
727 :
728 : int
729 0 : rtable_mpath_capable(unsigned int rtableid, sa_family_t af)
730 : {
731 0 : return (1);
732 : }
733 :
734 : int
735 0 : rtable_mpath_reprio(unsigned int rtableid, struct sockaddr *dst,
736 : struct sockaddr *mask, uint8_t prio, struct rtentry *rt)
737 : {
738 : struct art_root *ar;
739 : struct art_node *an;
740 0 : struct srp_ref sr;
741 : uint8_t *addr;
742 : int plen;
743 : int error = 0;
744 :
745 0 : ar = rtable_get(rtableid, dst->sa_family);
746 0 : if (ar == NULL)
747 0 : return (EAFNOSUPPORT);
748 :
749 0 : addr = satoaddr(ar, dst);
750 0 : plen = rtable_satoplen(dst->sa_family, mask);
751 :
752 0 : rw_enter_write(&ar->ar_lock);
753 0 : an = art_lookup(ar, addr, plen, &sr);
754 0 : srp_leave(&sr); /* an can't go away while we have the lock */
755 :
756 : /* Make sure we've got a perfect match. */
757 0 : if (!an_match(an, dst, plen)) {
758 : error = ESRCH;
759 0 : } else if (SRPL_FIRST_LOCKED(&an->an_rtlist) == rt &&
760 0 : SRPL_NEXT_LOCKED(rt, rt_next) == NULL) {
761 : /*
762 : * If there's only one entry on the list do not go
763 : * through an insert/remove cycle. This is done to
764 : * guarantee that ``an->an_rtlist'' is never empty
765 : * when a node is in the tree.
766 : */
767 0 : rt->rt_priority = prio;
768 0 : } else {
769 0 : rtref(rt); /* keep rt alive in between remove and insert */
770 0 : SRPL_REMOVE_LOCKED(&rt_rc, &an->an_rtlist,
771 : rt, rtentry, rt_next);
772 0 : rt->rt_priority = prio;
773 0 : rtable_mpath_insert(an, rt);
774 0 : rtfree(rt);
775 : error = EAGAIN;
776 : }
777 0 : rw_exit_write(&ar->ar_lock);
778 :
779 0 : return (error);
780 0 : }
781 :
782 : void
783 0 : rtable_mpath_insert(struct art_node *an, struct rtentry *rt)
784 : {
785 : struct rtentry *mrt, *prt = NULL;
786 0 : uint8_t prio = rt->rt_priority;
787 :
788 0 : if ((mrt = SRPL_FIRST_LOCKED(&an->an_rtlist)) == NULL) {
789 0 : SRPL_INSERT_HEAD_LOCKED(&rt_rc, &an->an_rtlist, rt, rt_next);
790 0 : return;
791 : }
792 :
793 : /* Iterate until we find the route to be placed after ``rt''. */
794 0 : while (mrt->rt_priority <= prio && SRPL_NEXT_LOCKED(mrt, rt_next)) {
795 : prt = mrt;
796 0 : mrt = SRPL_NEXT_LOCKED(mrt, rt_next);
797 : }
798 :
799 0 : if (mrt->rt_priority <= prio) {
800 0 : SRPL_INSERT_AFTER_LOCKED(&rt_rc, mrt, rt, rt_next);
801 0 : } else if (prt != NULL) {
802 0 : SRPL_INSERT_AFTER_LOCKED(&rt_rc, prt, rt, rt_next);
803 0 : } else {
804 0 : SRPL_INSERT_HEAD_LOCKED(&rt_rc, &an->an_rtlist, rt, rt_next);
805 : }
806 0 : }
807 :
808 : /*
809 : * Returns 1 if ``an'' perfectly matches (``dst'', ``plen''), 0 otherwise.
810 : */
811 : int
812 0 : an_match(struct art_node *an, struct sockaddr *dst, int plen)
813 : {
814 : struct rtentry *rt;
815 0 : struct srp_ref sr;
816 : int match;
817 :
818 0 : if (an == NULL || an->an_plen != plen)
819 0 : return (0);
820 :
821 0 : rt = SRPL_FIRST(&sr, &an->an_rtlist);
822 0 : match = (memcmp(rt->rt_dest, dst, dst->sa_len) == 0);
823 0 : SRPL_LEAVE(&sr);
824 :
825 0 : return (match);
826 0 : }
827 :
828 : void
829 0 : rtentry_ref(void *null, void *xrt)
830 : {
831 0 : struct rtentry *rt = xrt;
832 :
833 0 : rtref(rt);
834 0 : }
835 :
836 : void
837 0 : rtentry_unref(void *null, void *xrt)
838 : {
839 0 : struct rtentry *rt = xrt;
840 :
841 0 : rtfree(rt);
842 0 : }
843 :
844 : /*
845 : * Return a pointer to the address (key). This is an heritage from the
846 : * BSD radix tree needed to skip the non-address fields from the flavor
847 : * of "struct sockaddr" used by this routing table.
848 : */
849 : static inline uint8_t *
850 0 : satoaddr(struct art_root *at, struct sockaddr *sa)
851 : {
852 0 : return (((uint8_t *)sa) + at->ar_off);
853 : }
854 :
855 : /*
856 : * Return the prefix length of a mask.
857 : */
858 : int
859 0 : rtable_satoplen(sa_family_t af, struct sockaddr *mask)
860 : {
861 : struct domain *dp;
862 : uint8_t *ap, *ep;
863 : int mlen, plen = 0;
864 : int i;
865 :
866 0 : for (i = 0; (dp = domains[i]) != NULL; i++) {
867 0 : if (dp->dom_rtoffset == 0)
868 : continue;
869 :
870 0 : if (af == dp->dom_family)
871 : break;
872 : }
873 0 : if (dp == NULL)
874 0 : return (-1);
875 :
876 : /* Host route */
877 0 : if (mask == NULL)
878 0 : return (dp->dom_maxplen);
879 :
880 0 : mlen = mask->sa_len;
881 :
882 : /* Default route */
883 0 : if (mlen == 0)
884 0 : return (0);
885 :
886 0 : ap = (uint8_t *)((uint8_t *)mask) + dp->dom_rtoffset;
887 0 : ep = (uint8_t *)((uint8_t *)mask) + mlen;
888 0 : if (ap > ep)
889 0 : return (-1);
890 :
891 0 : if (ap == ep)
892 0 : return (0);
893 :
894 : /* "Beauty" adapted from sbin/route/show.c ... */
895 0 : while (ap < ep) {
896 0 : switch (*ap) {
897 : case 0xff:
898 0 : plen += 8;
899 0 : ap++;
900 : break;
901 : case 0xfe:
902 0 : plen += 7;
903 0 : ap++;
904 0 : goto out;
905 : case 0xfc:
906 0 : plen += 6;
907 0 : ap++;
908 0 : goto out;
909 : case 0xf8:
910 0 : plen += 5;
911 0 : ap++;
912 0 : goto out;
913 : case 0xf0:
914 0 : plen += 4;
915 0 : ap++;
916 0 : goto out;
917 : case 0xe0:
918 0 : plen += 3;
919 0 : ap++;
920 0 : goto out;
921 : case 0xc0:
922 0 : plen += 2;
923 0 : ap++;
924 0 : goto out;
925 : case 0x80:
926 0 : plen += 1;
927 0 : ap++;
928 0 : goto out;
929 : case 0x00:
930 : goto out;
931 : default:
932 : /* Non contiguous mask. */
933 0 : return (-1);
934 : }
935 :
936 : }
937 :
938 : out:
939 : #ifdef DIAGNOSTIC
940 0 : for (; ap < ep; ap++) {
941 0 : if (*ap != 0x00)
942 0 : return (-1);
943 : }
944 : #endif /* DIAGNOSTIC */
945 :
946 0 : return (plen);
947 0 : }
|
