File: | src/usr.sbin/ldpd/lde_lib.c |
Warning: | line 244, column 3 Use of memory after it is freed |
Press '?' to see keyboard shortcuts
Keyboard shortcuts:
1 | /* $OpenBSD: lde_lib.c,v 1.69 2017/03/04 00:15:35 renato Exp $ */ | |||
2 | ||||
3 | /* | |||
4 | * Copyright (c) 2013, 2016 Renato Westphal <renato@openbsd.org> | |||
5 | * Copyright (c) 2009 Michele Marchetto <michele@openbsd.org> | |||
6 | * | |||
7 | * Permission to use, copy, modify, and distribute this software for any | |||
8 | * purpose with or without fee is hereby granted, provided that the above | |||
9 | * copyright notice and this permission notice appear in all copies. | |||
10 | * | |||
11 | * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES | |||
12 | * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF | |||
13 | * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR | |||
14 | * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES | |||
15 | * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN | |||
16 | * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF | |||
17 | * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. | |||
18 | */ | |||
19 | ||||
20 | #include <sys/types.h> | |||
21 | #include <sys/socket.h> | |||
22 | #include <netmpls/mpls.h> | |||
23 | #include <stdlib.h> | |||
24 | #include <string.h> | |||
25 | #include <limits.h> | |||
26 | ||||
27 | #include "ldpd.h" | |||
28 | #include "lde.h" | |||
29 | #include "ldpe.h" | |||
30 | #include "log.h" | |||
31 | ||||
32 | static __inline int fec_compare(struct fec *, struct fec *); | |||
33 | static int lde_nbr_is_nexthop(struct fec_node *, | |||
34 | struct lde_nbr *); | |||
35 | static void fec_free(void *); | |||
36 | static struct fec_node *fec_add(struct fec *fec); | |||
37 | static struct fec_nh *fec_nh_add(struct fec_node *, int, union ldpd_addr *, | |||
38 | uint8_t priority); | |||
39 | static void fec_nh_del(struct fec_nh *); | |||
40 | ||||
41 | RB_GENERATE(fec_tree, fec, entry, fec_compare)void fec_tree_RB_INSERT_COLOR(struct fec_tree *head, struct fec *elm) { struct fec *parent, *gparent, *tmp; while ((parent = (elm)->entry.rbe_parent) && (parent)->entry.rbe_color == 1) { gparent = (parent)->entry.rbe_parent; if (parent == (gparent)->entry.rbe_left) { tmp = (gparent)->entry.rbe_right ; if (tmp && (tmp)->entry.rbe_color == 1) { (tmp)-> entry.rbe_color = 0; do { (parent)->entry.rbe_color = 0; ( gparent)->entry.rbe_color = 1; } while (0); elm = gparent; continue; } if ((parent)->entry.rbe_right == elm) { do { ( tmp) = (parent)->entry.rbe_right; if (((parent)->entry. rbe_right = (tmp)->entry.rbe_left)) { ((tmp)->entry.rbe_left )->entry.rbe_parent = (parent); } do {} while (0); if (((tmp )->entry.rbe_parent = (parent)->entry.rbe_parent)) { if ((parent) == ((parent)->entry.rbe_parent)->entry.rbe_left ) ((parent)->entry.rbe_parent)->entry.rbe_left = (tmp); else ((parent)->entry.rbe_parent)->entry.rbe_right = ( tmp); } else (head)->rbh_root = (tmp); (tmp)->entry.rbe_left = (parent); (parent)->entry.rbe_parent = (tmp); do {} while (0); if (((tmp)->entry.rbe_parent)) do {} while (0); } while (0); tmp = parent; parent = elm; elm = tmp; } do { (parent)-> entry.rbe_color = 0; (gparent)->entry.rbe_color = 1; } while (0); do { (tmp) = (gparent)->entry.rbe_left; if (((gparent )->entry.rbe_left = (tmp)->entry.rbe_right)) { ((tmp)-> entry.rbe_right)->entry.rbe_parent = (gparent); } do {} while (0); if (((tmp)->entry.rbe_parent = (gparent)->entry.rbe_parent )) { if ((gparent) == ((gparent)->entry.rbe_parent)->entry .rbe_left) ((gparent)->entry.rbe_parent)->entry.rbe_left = (tmp); else ((gparent)->entry.rbe_parent)->entry.rbe_right = (tmp); } else (head)->rbh_root = (tmp); (tmp)->entry .rbe_right = (gparent); (gparent)->entry.rbe_parent = (tmp ); do {} while (0); if (((tmp)->entry.rbe_parent)) do {} while (0); } while (0); } else { tmp = (gparent)->entry.rbe_left ; if (tmp && (tmp)->entry.rbe_color == 1) { (tmp)-> entry.rbe_color = 0; do { (parent)->entry.rbe_color = 0; ( gparent)->entry.rbe_color = 1; } while (0); elm = gparent; continue; } if ((parent)->entry.rbe_left == elm) { do { ( tmp) = (parent)->entry.rbe_left; if (((parent)->entry.rbe_left = (tmp)->entry.rbe_right)) { ((tmp)->entry.rbe_right)-> entry.rbe_parent = (parent); } do {} while (0); if (((tmp)-> entry.rbe_parent = (parent)->entry.rbe_parent)) { if ((parent ) == ((parent)->entry.rbe_parent)->entry.rbe_left) ((parent )->entry.rbe_parent)->entry.rbe_left = (tmp); else ((parent )->entry.rbe_parent)->entry.rbe_right = (tmp); } else ( head)->rbh_root = (tmp); (tmp)->entry.rbe_right = (parent ); (parent)->entry.rbe_parent = (tmp); do {} while (0); if (((tmp)->entry.rbe_parent)) do {} while (0); } while (0); tmp = parent; parent = elm; elm = tmp; } do { (parent)->entry .rbe_color = 0; (gparent)->entry.rbe_color = 1; } while (0 ); do { (tmp) = (gparent)->entry.rbe_right; if (((gparent) ->entry.rbe_right = (tmp)->entry.rbe_left)) { ((tmp)-> entry.rbe_left)->entry.rbe_parent = (gparent); } do {} while (0); if (((tmp)->entry.rbe_parent = (gparent)->entry.rbe_parent )) { if ((gparent) == ((gparent)->entry.rbe_parent)->entry .rbe_left) ((gparent)->entry.rbe_parent)->entry.rbe_left = (tmp); else ((gparent)->entry.rbe_parent)->entry.rbe_right = (tmp); } else (head)->rbh_root = (tmp); (tmp)->entry .rbe_left = (gparent); (gparent)->entry.rbe_parent = (tmp) ; do {} while (0); if (((tmp)->entry.rbe_parent)) do {} while (0); } while (0); } } (head->rbh_root)->entry.rbe_color = 0; } void fec_tree_RB_REMOVE_COLOR(struct fec_tree *head, struct fec *parent, struct fec *elm) { struct fec *tmp; while ((elm == ((void *)0) || (elm)->entry.rbe_color == 0) && elm != (head)->rbh_root) { if ((parent)->entry.rbe_left == elm) { tmp = (parent)->entry.rbe_right; if ((tmp)-> entry.rbe_color == 1) { do { (tmp)->entry.rbe_color = 0; ( parent)->entry.rbe_color = 1; } while (0); do { (tmp) = (parent )->entry.rbe_right; if (((parent)->entry.rbe_right = (tmp )->entry.rbe_left)) { ((tmp)->entry.rbe_left)->entry .rbe_parent = (parent); } do {} while (0); if (((tmp)->entry .rbe_parent = (parent)->entry.rbe_parent)) { if ((parent) == ((parent)->entry.rbe_parent)->entry.rbe_left) ((parent )->entry.rbe_parent)->entry.rbe_left = (tmp); else ((parent )->entry.rbe_parent)->entry.rbe_right = (tmp); } else ( head)->rbh_root = (tmp); (tmp)->entry.rbe_left = (parent ); (parent)->entry.rbe_parent = (tmp); do {} while (0); if (((tmp)->entry.rbe_parent)) do {} while (0); } while (0); tmp = (parent)->entry.rbe_right; } if (((tmp)->entry.rbe_left == ((void *)0) || ((tmp)->entry.rbe_left)->entry.rbe_color == 0) && ((tmp)->entry.rbe_right == ((void *)0) || ((tmp)->entry.rbe_right)->entry.rbe_color == 0)) { (tmp )->entry.rbe_color = 1; elm = parent; parent = (elm)->entry .rbe_parent; } else { if ((tmp)->entry.rbe_right == ((void *)0) || ((tmp)->entry.rbe_right)->entry.rbe_color == 0 ) { struct fec *oleft; if ((oleft = (tmp)->entry.rbe_left) ) (oleft)->entry.rbe_color = 0; (tmp)->entry.rbe_color = 1; do { (oleft) = (tmp)->entry.rbe_left; if (((tmp)->entry .rbe_left = (oleft)->entry.rbe_right)) { ((oleft)->entry .rbe_right)->entry.rbe_parent = (tmp); } do {} while (0); if (((oleft)->entry.rbe_parent = (tmp)->entry.rbe_parent) ) { if ((tmp) == ((tmp)->entry.rbe_parent)->entry.rbe_left ) ((tmp)->entry.rbe_parent)->entry.rbe_left = (oleft); else ((tmp)->entry.rbe_parent)->entry.rbe_right = (oleft); } else (head)->rbh_root = (oleft); (oleft)->entry.rbe_right = (tmp); (tmp)->entry.rbe_parent = (oleft); do {} while ( 0); if (((oleft)->entry.rbe_parent)) do {} while (0); } while (0); tmp = (parent)->entry.rbe_right; } (tmp)->entry.rbe_color = (parent)->entry.rbe_color; (parent)->entry.rbe_color = 0; if ((tmp)->entry.rbe_right) ((tmp)->entry.rbe_right )->entry.rbe_color = 0; do { (tmp) = (parent)->entry.rbe_right ; if (((parent)->entry.rbe_right = (tmp)->entry.rbe_left )) { ((tmp)->entry.rbe_left)->entry.rbe_parent = (parent ); } do {} while (0); if (((tmp)->entry.rbe_parent = (parent )->entry.rbe_parent)) { if ((parent) == ((parent)->entry .rbe_parent)->entry.rbe_left) ((parent)->entry.rbe_parent )->entry.rbe_left = (tmp); else ((parent)->entry.rbe_parent )->entry.rbe_right = (tmp); } else (head)->rbh_root = ( tmp); (tmp)->entry.rbe_left = (parent); (parent)->entry .rbe_parent = (tmp); do {} while (0); if (((tmp)->entry.rbe_parent )) do {} while (0); } while (0); elm = (head)->rbh_root; break ; } } else { tmp = (parent)->entry.rbe_left; if ((tmp)-> entry.rbe_color == 1) { do { (tmp)->entry.rbe_color = 0; ( parent)->entry.rbe_color = 1; } while (0); do { (tmp) = (parent )->entry.rbe_left; if (((parent)->entry.rbe_left = (tmp )->entry.rbe_right)) { ((tmp)->entry.rbe_right)->entry .rbe_parent = (parent); } do {} while (0); if (((tmp)->entry .rbe_parent = (parent)->entry.rbe_parent)) { if ((parent) == ((parent)->entry.rbe_parent)->entry.rbe_left) ((parent )->entry.rbe_parent)->entry.rbe_left = (tmp); else ((parent )->entry.rbe_parent)->entry.rbe_right = (tmp); } else ( head)->rbh_root = (tmp); (tmp)->entry.rbe_right = (parent ); (parent)->entry.rbe_parent = (tmp); do {} while (0); if (((tmp)->entry.rbe_parent)) do {} while (0); } while (0); tmp = (parent)->entry.rbe_left; } if (((tmp)->entry.rbe_left == ((void *)0) || ((tmp)->entry.rbe_left)->entry.rbe_color == 0) && ((tmp)->entry.rbe_right == ((void *)0) || ((tmp)->entry.rbe_right)->entry.rbe_color == 0)) { (tmp )->entry.rbe_color = 1; elm = parent; parent = (elm)->entry .rbe_parent; } else { if ((tmp)->entry.rbe_left == ((void * )0) || ((tmp)->entry.rbe_left)->entry.rbe_color == 0) { struct fec *oright; if ((oright = (tmp)->entry.rbe_right) ) (oright)->entry.rbe_color = 0; (tmp)->entry.rbe_color = 1; do { (oright) = (tmp)->entry.rbe_right; if (((tmp)-> entry.rbe_right = (oright)->entry.rbe_left)) { ((oright)-> entry.rbe_left)->entry.rbe_parent = (tmp); } do {} while ( 0); if (((oright)->entry.rbe_parent = (tmp)->entry.rbe_parent )) { if ((tmp) == ((tmp)->entry.rbe_parent)->entry.rbe_left ) ((tmp)->entry.rbe_parent)->entry.rbe_left = (oright); else ((tmp)->entry.rbe_parent)->entry.rbe_right = (oright ); } else (head)->rbh_root = (oright); (oright)->entry. rbe_left = (tmp); (tmp)->entry.rbe_parent = (oright); do { } while (0); if (((oright)->entry.rbe_parent)) do {} while (0); } while (0); tmp = (parent)->entry.rbe_left; } (tmp) ->entry.rbe_color = (parent)->entry.rbe_color; (parent) ->entry.rbe_color = 0; if ((tmp)->entry.rbe_left) ((tmp )->entry.rbe_left)->entry.rbe_color = 0; do { (tmp) = ( parent)->entry.rbe_left; if (((parent)->entry.rbe_left = (tmp)->entry.rbe_right)) { ((tmp)->entry.rbe_right)-> entry.rbe_parent = (parent); } do {} while (0); if (((tmp)-> entry.rbe_parent = (parent)->entry.rbe_parent)) { if ((parent ) == ((parent)->entry.rbe_parent)->entry.rbe_left) ((parent )->entry.rbe_parent)->entry.rbe_left = (tmp); else ((parent )->entry.rbe_parent)->entry.rbe_right = (tmp); } else ( head)->rbh_root = (tmp); (tmp)->entry.rbe_right = (parent ); (parent)->entry.rbe_parent = (tmp); do {} while (0); if (((tmp)->entry.rbe_parent)) do {} while (0); } while (0); elm = (head)->rbh_root; break; } } } if (elm) (elm)->entry .rbe_color = 0; } struct fec * fec_tree_RB_REMOVE(struct fec_tree *head, struct fec *elm) { struct fec *child, *parent, *old = elm; int color; if ((elm)->entry.rbe_left == ((void *)0)) child = (elm)->entry.rbe_right; else if ((elm)->entry. rbe_right == ((void *)0)) child = (elm)->entry.rbe_left; else { struct fec *left; elm = (elm)->entry.rbe_right; while ( (left = (elm)->entry.rbe_left)) elm = left; child = (elm)-> entry.rbe_right; parent = (elm)->entry.rbe_parent; color = (elm)->entry.rbe_color; if (child) (child)->entry.rbe_parent = parent; if (parent) { if ((parent)->entry.rbe_left == elm ) (parent)->entry.rbe_left = child; else (parent)->entry .rbe_right = child; do {} while (0); } else (head)->rbh_root = child; if ((elm)->entry.rbe_parent == old) parent = elm ; (elm)->entry = (old)->entry; if ((old)->entry.rbe_parent ) { if (((old)->entry.rbe_parent)->entry.rbe_left == old ) ((old)->entry.rbe_parent)->entry.rbe_left = elm; else ((old)->entry.rbe_parent)->entry.rbe_right = elm; do { } while (0); } else (head)->rbh_root = elm; ((old)->entry .rbe_left)->entry.rbe_parent = elm; if ((old)->entry.rbe_right ) ((old)->entry.rbe_right)->entry.rbe_parent = elm; if ( parent) { left = parent; do { do {} while (0); } while ((left = (left)->entry.rbe_parent)); } goto color; } parent = (elm )->entry.rbe_parent; color = (elm)->entry.rbe_color; if (child) (child)->entry.rbe_parent = parent; if (parent) { if ((parent)->entry.rbe_left == elm) (parent)->entry.rbe_left = child; else (parent)->entry.rbe_right = child; do {} while (0); } else (head)->rbh_root = child; color: if (color == 0) fec_tree_RB_REMOVE_COLOR(head, parent, child); return (old ); } struct fec * fec_tree_RB_INSERT(struct fec_tree *head, struct fec *elm) { struct fec *tmp; struct fec *parent = ((void *)0 ); int comp = 0; tmp = (head)->rbh_root; while (tmp) { parent = tmp; comp = (fec_compare)(elm, parent); if (comp < 0) tmp = (tmp)->entry.rbe_left; else if (comp > 0) tmp = (tmp )->entry.rbe_right; else return (tmp); } do { (elm)->entry .rbe_parent = parent; (elm)->entry.rbe_left = (elm)->entry .rbe_right = ((void *)0); (elm)->entry.rbe_color = 1; } while (0); if (parent != ((void *)0)) { if (comp < 0) (parent)-> entry.rbe_left = elm; else (parent)->entry.rbe_right = elm ; do {} while (0); } else (head)->rbh_root = elm; fec_tree_RB_INSERT_COLOR (head, elm); return (((void *)0)); } struct fec * fec_tree_RB_FIND (struct fec_tree *head, struct fec *elm) { struct fec *tmp = ( head)->rbh_root; int comp; while (tmp) { comp = fec_compare (elm, tmp); if (comp < 0) tmp = (tmp)->entry.rbe_left; else if (comp > 0) tmp = (tmp)->entry.rbe_right; else return (tmp); } return (((void *)0)); } struct fec * fec_tree_RB_NFIND (struct fec_tree *head, struct fec *elm) { struct fec *tmp = ( head)->rbh_root; struct fec *res = ((void *)0); int comp; while (tmp) { comp = fec_compare(elm, tmp); if (comp < 0) { res = tmp; tmp = (tmp)->entry.rbe_left; } else if (comp > 0 ) tmp = (tmp)->entry.rbe_right; else return (tmp); } return (res); } struct fec * fec_tree_RB_NEXT(struct fec *elm) { if ((elm)->entry.rbe_right) { elm = (elm)->entry.rbe_right ; while ((elm)->entry.rbe_left) elm = (elm)->entry.rbe_left ; } else { if ((elm)->entry.rbe_parent && (elm == ( (elm)->entry.rbe_parent)->entry.rbe_left)) elm = (elm)-> entry.rbe_parent; else { while ((elm)->entry.rbe_parent && (elm == ((elm)->entry.rbe_parent)->entry.rbe_right)) elm = (elm)->entry.rbe_parent; elm = (elm)->entry.rbe_parent ; } } return (elm); } struct fec * fec_tree_RB_PREV(struct fec *elm) { if ((elm)->entry.rbe_left) { elm = (elm)->entry .rbe_left; while ((elm)->entry.rbe_right) elm = (elm)-> entry.rbe_right; } else { if ((elm)->entry.rbe_parent && (elm == ((elm)->entry.rbe_parent)->entry.rbe_right)) elm = (elm)->entry.rbe_parent; else { while ((elm)->entry. rbe_parent && (elm == ((elm)->entry.rbe_parent)-> entry.rbe_left)) elm = (elm)->entry.rbe_parent; elm = (elm )->entry.rbe_parent; } } return (elm); } struct fec * fec_tree_RB_MINMAX (struct fec_tree *head, int val) { struct fec *tmp = (head)-> rbh_root; struct fec *parent = ((void *)0); while (tmp) { parent = tmp; if (val < 0) tmp = (tmp)->entry.rbe_left; else tmp = (tmp)->entry.rbe_right; } return (parent); } | |||
42 | ||||
43 | struct fec_tree ft = RB_INITIALIZER(&ft){ ((void *)0) }; | |||
44 | struct event gc_timer; | |||
45 | ||||
46 | /* FEC tree functions */ | |||
47 | void | |||
48 | fec_init(struct fec_tree *fh) | |||
49 | { | |||
50 | RB_INIT(fh)do { (fh)->rbh_root = ((void *)0); } while (0); | |||
51 | } | |||
52 | ||||
53 | static __inline int | |||
54 | fec_compare(struct fec *a, struct fec *b) | |||
55 | { | |||
56 | if (a->type < b->type) | |||
57 | return (-1); | |||
58 | if (a->type > b->type) | |||
59 | return (1); | |||
60 | ||||
61 | switch (a->type) { | |||
62 | case FEC_TYPE_IPV4: | |||
63 | if (ntohl(a->u.ipv4.prefix.s_addr)(__uint32_t)(__builtin_constant_p(a->u.ipv4.prefix.s_addr) ? (__uint32_t)(((__uint32_t)(a->u.ipv4.prefix.s_addr) & 0xff) << 24 | ((__uint32_t)(a->u.ipv4.prefix.s_addr ) & 0xff00) << 8 | ((__uint32_t)(a->u.ipv4.prefix .s_addr) & 0xff0000) >> 8 | ((__uint32_t)(a->u.ipv4 .prefix.s_addr) & 0xff000000) >> 24) : __swap32md(a ->u.ipv4.prefix.s_addr)) < | |||
64 | ntohl(b->u.ipv4.prefix.s_addr)(__uint32_t)(__builtin_constant_p(b->u.ipv4.prefix.s_addr) ? (__uint32_t)(((__uint32_t)(b->u.ipv4.prefix.s_addr) & 0xff) << 24 | ((__uint32_t)(b->u.ipv4.prefix.s_addr ) & 0xff00) << 8 | ((__uint32_t)(b->u.ipv4.prefix .s_addr) & 0xff0000) >> 8 | ((__uint32_t)(b->u.ipv4 .prefix.s_addr) & 0xff000000) >> 24) : __swap32md(b ->u.ipv4.prefix.s_addr))) | |||
65 | return (-1); | |||
66 | if (ntohl(a->u.ipv4.prefix.s_addr)(__uint32_t)(__builtin_constant_p(a->u.ipv4.prefix.s_addr) ? (__uint32_t)(((__uint32_t)(a->u.ipv4.prefix.s_addr) & 0xff) << 24 | ((__uint32_t)(a->u.ipv4.prefix.s_addr ) & 0xff00) << 8 | ((__uint32_t)(a->u.ipv4.prefix .s_addr) & 0xff0000) >> 8 | ((__uint32_t)(a->u.ipv4 .prefix.s_addr) & 0xff000000) >> 24) : __swap32md(a ->u.ipv4.prefix.s_addr)) > | |||
67 | ntohl(b->u.ipv4.prefix.s_addr)(__uint32_t)(__builtin_constant_p(b->u.ipv4.prefix.s_addr) ? (__uint32_t)(((__uint32_t)(b->u.ipv4.prefix.s_addr) & 0xff) << 24 | ((__uint32_t)(b->u.ipv4.prefix.s_addr ) & 0xff00) << 8 | ((__uint32_t)(b->u.ipv4.prefix .s_addr) & 0xff0000) >> 8 | ((__uint32_t)(b->u.ipv4 .prefix.s_addr) & 0xff000000) >> 24) : __swap32md(b ->u.ipv4.prefix.s_addr))) | |||
68 | return (1); | |||
69 | if (a->u.ipv4.prefixlen < b->u.ipv4.prefixlen) | |||
70 | return (-1); | |||
71 | if (a->u.ipv4.prefixlen > b->u.ipv4.prefixlen) | |||
72 | return (1); | |||
73 | return (0); | |||
74 | case FEC_TYPE_IPV6: | |||
75 | if (memcmp(&a->u.ipv6.prefix, &b->u.ipv6.prefix, | |||
76 | sizeof(struct in6_addr)) < 0) | |||
77 | return (-1); | |||
78 | if (memcmp(&a->u.ipv6.prefix, &b->u.ipv6.prefix, | |||
79 | sizeof(struct in6_addr)) > 0) | |||
80 | return (1); | |||
81 | if (a->u.ipv6.prefixlen < b->u.ipv6.prefixlen) | |||
82 | return (-1); | |||
83 | if (a->u.ipv6.prefixlen > b->u.ipv6.prefixlen) | |||
84 | return (1); | |||
85 | return (0); | |||
86 | case FEC_TYPE_PWID: | |||
87 | if (a->u.pwid.type < b->u.pwid.type) | |||
88 | return (-1); | |||
89 | if (a->u.pwid.type > b->u.pwid.type) | |||
90 | return (1); | |||
91 | if (a->u.pwid.pwid < b->u.pwid.pwid) | |||
92 | return (-1); | |||
93 | if (a->u.pwid.pwid > b->u.pwid.pwid) | |||
94 | return (1); | |||
95 | if (ntohl(a->u.pwid.lsr_id.s_addr)(__uint32_t)(__builtin_constant_p(a->u.pwid.lsr_id.s_addr) ? (__uint32_t)(((__uint32_t)(a->u.pwid.lsr_id.s_addr) & 0xff) << 24 | ((__uint32_t)(a->u.pwid.lsr_id.s_addr ) & 0xff00) << 8 | ((__uint32_t)(a->u.pwid.lsr_id .s_addr) & 0xff0000) >> 8 | ((__uint32_t)(a->u.pwid .lsr_id.s_addr) & 0xff000000) >> 24) : __swap32md(a ->u.pwid.lsr_id.s_addr)) < | |||
96 | ntohl(b->u.pwid.lsr_id.s_addr)(__uint32_t)(__builtin_constant_p(b->u.pwid.lsr_id.s_addr) ? (__uint32_t)(((__uint32_t)(b->u.pwid.lsr_id.s_addr) & 0xff) << 24 | ((__uint32_t)(b->u.pwid.lsr_id.s_addr ) & 0xff00) << 8 | ((__uint32_t)(b->u.pwid.lsr_id .s_addr) & 0xff0000) >> 8 | ((__uint32_t)(b->u.pwid .lsr_id.s_addr) & 0xff000000) >> 24) : __swap32md(b ->u.pwid.lsr_id.s_addr))) | |||
97 | return (-1); | |||
98 | if (ntohl(a->u.pwid.lsr_id.s_addr)(__uint32_t)(__builtin_constant_p(a->u.pwid.lsr_id.s_addr) ? (__uint32_t)(((__uint32_t)(a->u.pwid.lsr_id.s_addr) & 0xff) << 24 | ((__uint32_t)(a->u.pwid.lsr_id.s_addr ) & 0xff00) << 8 | ((__uint32_t)(a->u.pwid.lsr_id .s_addr) & 0xff0000) >> 8 | ((__uint32_t)(a->u.pwid .lsr_id.s_addr) & 0xff000000) >> 24) : __swap32md(a ->u.pwid.lsr_id.s_addr)) > | |||
99 | ntohl(b->u.pwid.lsr_id.s_addr)(__uint32_t)(__builtin_constant_p(b->u.pwid.lsr_id.s_addr) ? (__uint32_t)(((__uint32_t)(b->u.pwid.lsr_id.s_addr) & 0xff) << 24 | ((__uint32_t)(b->u.pwid.lsr_id.s_addr ) & 0xff00) << 8 | ((__uint32_t)(b->u.pwid.lsr_id .s_addr) & 0xff0000) >> 8 | ((__uint32_t)(b->u.pwid .lsr_id.s_addr) & 0xff000000) >> 24) : __swap32md(b ->u.pwid.lsr_id.s_addr))) | |||
100 | return (1); | |||
101 | return (0); | |||
102 | } | |||
103 | ||||
104 | return (-1); | |||
105 | } | |||
106 | ||||
107 | struct fec * | |||
108 | fec_find(struct fec_tree *fh, struct fec *f) | |||
109 | { | |||
110 | return (RB_FIND(fec_tree, fh, f)fec_tree_RB_FIND(fh, f)); | |||
111 | } | |||
112 | ||||
113 | int | |||
114 | fec_insert(struct fec_tree *fh, struct fec *f) | |||
115 | { | |||
116 | if (RB_INSERT(fec_tree, fh, f)fec_tree_RB_INSERT(fh, f) != NULL((void *)0)) | |||
117 | return (-1); | |||
118 | return (0); | |||
119 | } | |||
120 | ||||
121 | int | |||
122 | fec_remove(struct fec_tree *fh, struct fec *f) | |||
123 | { | |||
124 | if (RB_REMOVE(fec_tree, fh, f)fec_tree_RB_REMOVE(fh, f) == NULL((void *)0)) { | |||
125 | log_warnx("%s failed for %s", __func__, log_fec(f)); | |||
126 | return (-1); | |||
127 | } | |||
128 | return (0); | |||
129 | } | |||
130 | ||||
131 | void | |||
132 | fec_clear(struct fec_tree *fh, void (*free_cb)(void *)) | |||
133 | { | |||
134 | struct fec *f; | |||
135 | ||||
136 | while ((f = RB_ROOT(fh)(fh)->rbh_root) != NULL((void *)0)) { | |||
137 | fec_remove(fh, f); | |||
138 | free_cb(f); | |||
139 | } | |||
140 | } | |||
141 | ||||
142 | /* routing table functions */ | |||
143 | static int | |||
144 | lde_nbr_is_nexthop(struct fec_node *fn, struct lde_nbr *ln) | |||
145 | { | |||
146 | struct fec_nh *fnh; | |||
147 | ||||
148 | LIST_FOREACH(fnh, &fn->nexthops, entry)for((fnh) = ((&fn->nexthops)->lh_first); (fnh)!= (( void *)0); (fnh) = ((fnh)->entry.le_next)) | |||
149 | if (lde_address_find(ln, fnh->af, &fnh->nexthop)) | |||
150 | return (1); | |||
151 | ||||
152 | return (0); | |||
153 | } | |||
154 | ||||
155 | void | |||
156 | rt_dump(pid_t pid) | |||
157 | { | |||
158 | struct fec *f; | |||
159 | struct fec_node *fn; | |||
160 | struct lde_map *me; | |||
161 | static struct ctl_rt rtctl; | |||
162 | ||||
163 | RB_FOREACH(f, fec_tree, &ft)for ((f) = fec_tree_RB_MINMAX(&ft, -1); (f) != ((void *)0 ); (f) = fec_tree_RB_NEXT(f)) { | |||
164 | fn = (struct fec_node *)f; | |||
165 | if (fn->local_label == NO_LABEL0xffffffffU && | |||
166 | LIST_EMPTY(&fn->downstream)(((&fn->downstream)->lh_first) == ((void *)0))) | |||
167 | continue; | |||
168 | ||||
169 | switch (fn->fec.type) { | |||
170 | case FEC_TYPE_IPV4: | |||
171 | rtctl.af = AF_INET2; | |||
172 | rtctl.prefix.v4 = fn->fec.u.ipv4.prefix; | |||
173 | rtctl.prefixlen = fn->fec.u.ipv4.prefixlen; | |||
174 | break; | |||
175 | case FEC_TYPE_IPV6: | |||
176 | rtctl.af = AF_INET624; | |||
177 | rtctl.prefix.v6 = fn->fec.u.ipv6.prefix; | |||
178 | rtctl.prefixlen = fn->fec.u.ipv6.prefixlen; | |||
179 | break; | |||
180 | default: | |||
181 | continue; | |||
182 | } | |||
183 | ||||
184 | rtctl.local_label = fn->local_label; | |||
185 | LIST_FOREACH(me, &fn->downstream, entry)for((me) = ((&fn->downstream)->lh_first); (me)!= (( void *)0); (me) = ((me)->entry.le_next)) { | |||
186 | rtctl.in_use = lde_nbr_is_nexthop(fn, me->nexthop); | |||
187 | rtctl.nexthop = me->nexthop->id; | |||
188 | rtctl.remote_label = me->map.label; | |||
189 | ||||
190 | lde_imsg_compose_ldpe(IMSG_CTL_SHOW_LIB, 0, pid, | |||
191 | &rtctl, sizeof(rtctl)); | |||
192 | } | |||
193 | if (LIST_EMPTY(&fn->downstream)(((&fn->downstream)->lh_first) == ((void *)0))) { | |||
194 | rtctl.in_use = 0; | |||
195 | rtctl.nexthop.s_addr = INADDR_ANY((u_int32_t)(0x00000000)); | |||
196 | rtctl.remote_label = NO_LABEL0xffffffffU; | |||
197 | ||||
198 | lde_imsg_compose_ldpe(IMSG_CTL_SHOW_LIB, 0, pid, | |||
199 | &rtctl, sizeof(rtctl)); | |||
200 | } | |||
201 | } | |||
202 | } | |||
203 | ||||
204 | void | |||
205 | fec_snap(struct lde_nbr *ln) | |||
206 | { | |||
207 | struct fec *f; | |||
208 | struct fec_node *fn; | |||
209 | ||||
210 | RB_FOREACH(f, fec_tree, &ft)for ((f) = fec_tree_RB_MINMAX(&ft, -1); (f) != ((void *)0 ); (f) = fec_tree_RB_NEXT(f)) { | |||
211 | fn = (struct fec_node *)f; | |||
212 | if (fn->local_label == NO_LABEL0xffffffffU) | |||
213 | continue; | |||
214 | ||||
215 | lde_send_labelmapping(ln, fn, 0); | |||
216 | } | |||
217 | ||||
218 | lde_imsg_compose_ldpe(IMSG_MAPPING_ADD_END, ln->peerid, 0, NULL((void *)0), 0); | |||
219 | ||||
220 | /* | |||
221 | * RFC 5919 - Section 4: | |||
222 | * "An LDP speaker that conforms to this specification SHOULD signal | |||
223 | * completion of its label advertisements to a peer by means of a | |||
224 | * Notification message, if its peer has advertised the Unrecognized | |||
225 | * Notification capability during session establishment. The LDP | |||
226 | * speaker SHOULD send the Notification message (per Forwarding | |||
227 | * Equivalence Class (FEC) Type) to a peer even if the LDP speaker has | |||
228 | * zero Label bindings to advertise to that peer". | |||
229 | */ | |||
230 | if (ln->flags & F_NBR_CAP_UNOTIF0x08) { | |||
231 | lde_send_notification_eol_prefix(ln, AF_INET2); | |||
232 | lde_send_notification_eol_prefix(ln, AF_INET624); | |||
233 | lde_send_notification_eol_pwid(ln, PW_TYPE_WILDCARD0x7FFF); | |||
234 | } | |||
235 | } | |||
236 | ||||
237 | static void | |||
238 | fec_free(void *arg) | |||
239 | { | |||
240 | struct fec_node *fn = arg; | |||
241 | struct fec_nh *fnh; | |||
242 | ||||
243 | while ((fnh = LIST_FIRST(&fn->nexthops)((&fn->nexthops)->lh_first))) | |||
244 | fec_nh_del(fnh); | |||
| ||||
245 | if (!LIST_EMPTY(&fn->downstream)(((&fn->downstream)->lh_first) == ((void *)0))) | |||
246 | log_warnx("%s: fec %s downstream list not empty", __func__, | |||
247 | log_fec(&fn->fec)); | |||
248 | if (!LIST_EMPTY(&fn->upstream)(((&fn->upstream)->lh_first) == ((void *)0))) | |||
249 | log_warnx("%s: fec %s upstream list not empty", __func__, | |||
250 | log_fec(&fn->fec)); | |||
251 | ||||
252 | free(fn); | |||
253 | } | |||
254 | ||||
255 | void | |||
256 | fec_tree_clear(void) | |||
257 | { | |||
258 | fec_clear(&ft, fec_free); | |||
| ||||
259 | } | |||
260 | ||||
261 | static struct fec_node * | |||
262 | fec_add(struct fec *fec) | |||
263 | { | |||
264 | struct fec_node *fn; | |||
265 | ||||
266 | fn = calloc(1, sizeof(*fn)); | |||
267 | if (fn == NULL((void *)0)) | |||
268 | fatal(__func__); | |||
269 | ||||
270 | fn->fec = *fec; | |||
271 | fn->local_label = NO_LABEL0xffffffffU; | |||
272 | LIST_INIT(&fn->upstream)do { ((&fn->upstream)->lh_first) = ((void *)0); } while (0); | |||
273 | LIST_INIT(&fn->downstream)do { ((&fn->downstream)->lh_first) = ((void *)0); } while (0); | |||
274 | LIST_INIT(&fn->nexthops)do { ((&fn->nexthops)->lh_first) = ((void *)0); } while (0); | |||
275 | ||||
276 | if (fec_insert(&ft, &fn->fec)) | |||
277 | log_warnx("failed to add %s to ft tree", | |||
278 | log_fec(&fn->fec)); | |||
279 | ||||
280 | return (fn); | |||
281 | } | |||
282 | ||||
283 | struct fec_nh * | |||
284 | fec_nh_find(struct fec_node *fn, int af, union ldpd_addr *nexthop, | |||
285 | uint8_t priority) | |||
286 | { | |||
287 | struct fec_nh *fnh; | |||
288 | ||||
289 | LIST_FOREACH(fnh, &fn->nexthops, entry)for((fnh) = ((&fn->nexthops)->lh_first); (fnh)!= (( void *)0); (fnh) = ((fnh)->entry.le_next)) | |||
290 | if (fnh->af == af && | |||
291 | ldp_addrcmp(af, &fnh->nexthop, nexthop) == 0 && | |||
292 | fnh->priority == priority) | |||
293 | return (fnh); | |||
294 | ||||
295 | return (NULL((void *)0)); | |||
296 | } | |||
297 | ||||
298 | static struct fec_nh * | |||
299 | fec_nh_add(struct fec_node *fn, int af, union ldpd_addr *nexthop, | |||
300 | uint8_t priority) | |||
301 | { | |||
302 | struct fec_nh *fnh; | |||
303 | ||||
304 | fnh = calloc(1, sizeof(*fnh)); | |||
305 | if (fnh == NULL((void *)0)) | |||
306 | fatal(__func__); | |||
307 | ||||
308 | fnh->af = af; | |||
309 | fnh->nexthop = *nexthop; | |||
310 | fnh->remote_label = NO_LABEL0xffffffffU; | |||
311 | fnh->priority = priority; | |||
312 | LIST_INSERT_HEAD(&fn->nexthops, fnh, entry)do { if (((fnh)->entry.le_next = (&fn->nexthops)-> lh_first) != ((void *)0)) (&fn->nexthops)->lh_first ->entry.le_prev = &(fnh)->entry.le_next; (&fn-> nexthops)->lh_first = (fnh); (fnh)->entry.le_prev = & (&fn->nexthops)->lh_first; } while (0); | |||
313 | ||||
314 | return (fnh); | |||
315 | } | |||
316 | ||||
317 | static void | |||
318 | fec_nh_del(struct fec_nh *fnh) | |||
319 | { | |||
320 | LIST_REMOVE(fnh, entry)do { if ((fnh)->entry.le_next != ((void *)0)) (fnh)->entry .le_next->entry.le_prev = (fnh)->entry.le_prev; *(fnh)-> entry.le_prev = (fnh)->entry.le_next; ; ; } while (0); | |||
321 | free(fnh); | |||
322 | } | |||
323 | ||||
324 | uint32_t | |||
325 | egress_label(enum fec_type fec_type) | |||
326 | { | |||
327 | switch (fec_type) { | |||
328 | case FEC_TYPE_IPV4: | |||
329 | if (ldeconf->ipv4.flags & F_LDPD_AF_EXPNULL0x0004) | |||
330 | return (MPLS_LABEL_IPV4NULL0); | |||
331 | break; | |||
332 | case FEC_TYPE_IPV6: | |||
333 | if (ldeconf->ipv6.flags & F_LDPD_AF_EXPNULL0x0004) | |||
334 | return (MPLS_LABEL_IPV6NULL2); | |||
335 | break; | |||
336 | default: | |||
337 | fatalx("egress_label: unexpected fec type"); | |||
338 | } | |||
339 | ||||
340 | return (MPLS_LABEL_IMPLNULL3); | |||
341 | } | |||
342 | ||||
343 | void | |||
344 | lde_kernel_insert(struct fec *fec, int af, union ldpd_addr *nexthop, | |||
345 | uint8_t priority, int connected, void *data) | |||
346 | { | |||
347 | struct fec_node *fn; | |||
348 | struct fec_nh *fnh; | |||
349 | struct lde_map *me; | |||
350 | struct lde_nbr *ln; | |||
351 | ||||
352 | fn = (struct fec_node *)fec_find(&ft, fec); | |||
353 | if (fn == NULL((void *)0)) | |||
354 | fn = fec_add(fec); | |||
355 | if (fec_nh_find(fn, af, nexthop, priority) != NULL((void *)0)) | |||
356 | return; | |||
357 | ||||
358 | log_debug("lde add fec %s nexthop %s", | |||
359 | log_fec(&fn->fec), log_addr(af, nexthop)); | |||
360 | ||||
361 | if (fn->fec.type == FEC_TYPE_PWID) | |||
362 | fn->data = data; | |||
363 | ||||
364 | if (fn->local_label == NO_LABEL0xffffffffU) { | |||
365 | if (connected) | |||
366 | fn->local_label = egress_label(fn->fec.type); | |||
367 | else | |||
368 | fn->local_label = lde_assign_label(); | |||
369 | ||||
370 | /* FEC.1: perform lsr label distribution procedure */ | |||
371 | RB_FOREACH(ln, nbr_tree, &lde_nbrs)for ((ln) = nbr_tree_RB_MINMAX(&lde_nbrs, -1); (ln) != (( void *)0); (ln) = nbr_tree_RB_NEXT(ln)) | |||
372 | lde_send_labelmapping(ln, fn, 1); | |||
373 | } | |||
374 | ||||
375 | fnh = fec_nh_add(fn, af, nexthop, priority); | |||
376 | lde_send_change_klabel(fn, fnh); | |||
377 | ||||
378 | switch (fn->fec.type) { | |||
379 | case FEC_TYPE_IPV4: | |||
380 | case FEC_TYPE_IPV6: | |||
381 | ln = lde_nbr_find_by_addr(af, &fnh->nexthop); | |||
382 | break; | |||
383 | case FEC_TYPE_PWID: | |||
384 | ln = lde_nbr_find_by_lsrid(fn->fec.u.pwid.lsr_id); | |||
385 | break; | |||
386 | default: | |||
387 | ln = NULL((void *)0); | |||
388 | break; | |||
389 | } | |||
390 | ||||
391 | if (ln) { | |||
392 | /* FEC.2 */ | |||
393 | me = (struct lde_map *)fec_find(&ln->recv_map, &fn->fec); | |||
394 | if (me) | |||
395 | /* FEC.5 */ | |||
396 | lde_check_mapping(&me->map, ln); | |||
397 | } | |||
398 | } | |||
399 | ||||
400 | void | |||
401 | lde_kernel_remove(struct fec *fec, int af, union ldpd_addr *nexthop, | |||
402 | uint8_t priority) | |||
403 | { | |||
404 | struct fec_node *fn; | |||
405 | struct fec_nh *fnh; | |||
406 | struct lde_nbr *ln; | |||
407 | ||||
408 | fn = (struct fec_node *)fec_find(&ft, fec); | |||
409 | if (fn == NULL((void *)0)) | |||
410 | /* route lost */ | |||
411 | return; | |||
412 | fnh = fec_nh_find(fn, af, nexthop, priority); | |||
413 | if (fnh == NULL((void *)0)) | |||
414 | /* route lost */ | |||
415 | return; | |||
416 | ||||
417 | log_debug("lde remove fec %s nexthop %s", | |||
418 | log_fec(&fn->fec), log_addr(af, nexthop)); | |||
419 | ||||
420 | lde_send_delete_klabel(fn, fnh); | |||
421 | fec_nh_del(fnh); | |||
422 | if (LIST_EMPTY(&fn->nexthops)(((&fn->nexthops)->lh_first) == ((void *)0))) { | |||
423 | RB_FOREACH(ln, nbr_tree, &lde_nbrs)for ((ln) = nbr_tree_RB_MINMAX(&lde_nbrs, -1); (ln) != (( void *)0); (ln) = nbr_tree_RB_NEXT(ln)) | |||
424 | lde_send_labelwithdraw(ln, fn, NULL((void *)0), NULL((void *)0)); | |||
425 | fn->local_label = NO_LABEL0xffffffffU; | |||
426 | if (fn->fec.type == FEC_TYPE_PWID) | |||
427 | fn->data = NULL((void *)0); | |||
428 | } | |||
429 | } | |||
430 | ||||
431 | void | |||
432 | lde_check_mapping(struct map *map, struct lde_nbr *ln) | |||
433 | { | |||
434 | struct fec fec; | |||
435 | struct fec_node *fn; | |||
436 | struct fec_nh *fnh; | |||
437 | struct lde_req *lre; | |||
438 | struct lde_map *me; | |||
439 | struct l2vpn_pw *pw; | |||
440 | int msgsource = 0; | |||
441 | ||||
442 | lde_map2fec(map, ln->id, &fec); | |||
443 | fn = (struct fec_node *)fec_find(&ft, &fec); | |||
444 | if (fn == NULL((void *)0)) | |||
445 | fn = fec_add(&fec); | |||
446 | ||||
447 | /* LMp.1: first check if we have a pending request running */ | |||
448 | lre = (struct lde_req *)fec_find(&ln->sent_req, &fn->fec); | |||
449 | if (lre) | |||
450 | /* LMp.2: delete record of outstanding label request */ | |||
451 | lde_req_del(ln, lre, 1); | |||
452 | ||||
453 | /* RFC 4447 control word and status tlv negotiation */ | |||
454 | if (map->type == MAP_TYPE_PWID0x80 && l2vpn_pw_negotiate(ln, fn, map)) | |||
455 | return; | |||
456 | ||||
457 | /* | |||
458 | * LMp.3 - LMp.8: loop detection - unnecessary for frame-mode | |||
459 | * mpls networks. | |||
460 | */ | |||
461 | ||||
462 | /* LMp.9 */ | |||
463 | me = (struct lde_map *)fec_find(&ln->recv_map, &fn->fec); | |||
464 | if (me) { | |||
465 | /* LMp.10 */ | |||
466 | if (me->map.label != map->label && lre == NULL((void *)0)) { | |||
467 | /* LMp.10a */ | |||
468 | lde_send_labelrelease(ln, fn, NULL((void *)0), me->map.label); | |||
469 | ||||
470 | /* | |||
471 | * Can not use lde_nbr_find_by_addr() because there's | |||
472 | * the possibility of multipath. | |||
473 | */ | |||
474 | LIST_FOREACH(fnh, &fn->nexthops, entry)for((fnh) = ((&fn->nexthops)->lh_first); (fnh)!= (( void *)0); (fnh) = ((fnh)->entry.le_next)) { | |||
475 | if (lde_address_find(ln, fnh->af, | |||
476 | &fnh->nexthop) == NULL((void *)0)) | |||
477 | continue; | |||
478 | ||||
479 | lde_send_delete_klabel(fn, fnh); | |||
480 | fnh->remote_label = NO_LABEL0xffffffffU; | |||
481 | } | |||
482 | } | |||
483 | } | |||
484 | ||||
485 | /* | |||
486 | * LMp.11 - 12: consider multiple nexthops in order to | |||
487 | * support multipath | |||
488 | */ | |||
489 | LIST_FOREACH(fnh, &fn->nexthops, entry)for((fnh) = ((&fn->nexthops)->lh_first); (fnh)!= (( void *)0); (fnh) = ((fnh)->entry.le_next)) { | |||
490 | /* LMp.15: install FEC in FIB */ | |||
491 | switch (fec.type) { | |||
492 | case FEC_TYPE_IPV4: | |||
493 | case FEC_TYPE_IPV6: | |||
494 | if (!lde_address_find(ln, fnh->af, &fnh->nexthop)) | |||
495 | continue; | |||
496 | ||||
497 | fnh->remote_label = map->label; | |||
498 | lde_send_change_klabel(fn, fnh); | |||
499 | break; | |||
500 | case FEC_TYPE_PWID: | |||
501 | pw = (struct l2vpn_pw *) fn->data; | |||
502 | if (pw == NULL((void *)0)) | |||
503 | continue; | |||
504 | ||||
505 | pw->remote_group = map->fec.pwid.group_id; | |||
506 | if (map->flags & F_MAP_PW_IFMTU0x10) | |||
507 | pw->remote_mtu = map->fec.pwid.ifmtu; | |||
508 | if (map->flags & F_MAP_PW_STATUS0x20) | |||
509 | pw->remote_status = map->pw_status; | |||
510 | fnh->remote_label = map->label; | |||
511 | if (l2vpn_pw_ok(pw, fnh)) | |||
512 | lde_send_change_klabel(fn, fnh); | |||
513 | break; | |||
514 | default: | |||
515 | break; | |||
516 | } | |||
517 | ||||
518 | msgsource = 1; | |||
519 | } | |||
520 | /* LMp.13 & LMp.16: Record the mapping from this peer */ | |||
521 | if (me == NULL((void *)0)) | |||
522 | me = lde_map_add(ln, fn, 0); | |||
523 | me->map = *map; | |||
524 | ||||
525 | if (msgsource == 0) | |||
526 | /* LMp.13: just return since we use liberal lbl retention */ | |||
527 | return; | |||
528 | ||||
529 | /* | |||
530 | * LMp.17 - LMp.27 are unnecessary since we don't need to implement | |||
531 | * loop detection. LMp.28 - LMp.30 are unnecessary because we are | |||
532 | * merging capable. | |||
533 | */ | |||
534 | } | |||
535 | ||||
536 | void | |||
537 | lde_check_request(struct map *map, struct lde_nbr *ln) | |||
538 | { | |||
539 | struct fec fec; | |||
540 | struct lde_req *lre; | |||
541 | struct fec_node *fn; | |||
542 | struct fec_nh *fnh; | |||
543 | ||||
544 | /* wildcard label request */ | |||
545 | if (map->type == MAP_TYPE_TYPED_WCARD0x05) { | |||
546 | lde_check_request_wcard(map, ln); | |||
547 | return; | |||
548 | } | |||
549 | ||||
550 | /* LRq.1: skip loop detection (not necessary) */ | |||
551 | ||||
552 | /* LRq.2: is there a next hop for fec? */ | |||
553 | lde_map2fec(map, ln->id, &fec); | |||
554 | fn = (struct fec_node *)fec_find(&ft, &fec); | |||
555 | if (fn == NULL((void *)0) || LIST_EMPTY(&fn->nexthops)(((&fn->nexthops)->lh_first) == ((void *)0))) { | |||
556 | /* LRq.5: send No Route notification */ | |||
557 | lde_send_notification(ln, S_NO_ROUTE0x0000000D, map->msg_id, | |||
558 | htons(MSG_TYPE_LABELREQUEST)(__uint16_t)(__builtin_constant_p(0x0401) ? (__uint16_t)(((__uint16_t )(0x0401) & 0xffU) << 8 | ((__uint16_t)(0x0401) & 0xff00U) >> 8) : __swap16md(0x0401))); | |||
559 | return; | |||
560 | } | |||
561 | ||||
562 | /* LRq.3: is MsgSource the next hop? */ | |||
563 | LIST_FOREACH(fnh, &fn->nexthops, entry)for((fnh) = ((&fn->nexthops)->lh_first); (fnh)!= (( void *)0); (fnh) = ((fnh)->entry.le_next)) { | |||
564 | switch (fec.type) { | |||
565 | case FEC_TYPE_IPV4: | |||
566 | case FEC_TYPE_IPV6: | |||
567 | if (!lde_address_find(ln, fnh->af, &fnh->nexthop)) | |||
568 | continue; | |||
569 | ||||
570 | /* LRq.4: send Loop Detected notification */ | |||
571 | lde_send_notification(ln, S_LOOP_DETECTED0x0000000B, map->msg_id, | |||
572 | htons(MSG_TYPE_LABELREQUEST)(__uint16_t)(__builtin_constant_p(0x0401) ? (__uint16_t)(((__uint16_t )(0x0401) & 0xffU) << 8 | ((__uint16_t)(0x0401) & 0xff00U) >> 8) : __swap16md(0x0401))); | |||
573 | return; | |||
574 | default: | |||
575 | break; | |||
576 | } | |||
577 | } | |||
578 | ||||
579 | /* LRq.6: first check if we have a pending request running */ | |||
580 | lre = (struct lde_req *)fec_find(&ln->recv_req, &fn->fec); | |||
581 | if (lre != NULL((void *)0)) | |||
582 | /* LRq.7: duplicate request */ | |||
583 | return; | |||
584 | ||||
585 | /* LRq.8: record label request */ | |||
586 | lre = lde_req_add(ln, &fn->fec, 0); | |||
587 | if (lre != NULL((void *)0)) | |||
588 | lre->msg_id = ntohl(map->msg_id)(__uint32_t)(__builtin_constant_p(map->msg_id) ? (__uint32_t )(((__uint32_t)(map->msg_id) & 0xff) << 24 | ((__uint32_t )(map->msg_id) & 0xff00) << 8 | ((__uint32_t)(map ->msg_id) & 0xff0000) >> 8 | ((__uint32_t)(map-> msg_id) & 0xff000000) >> 24) : __swap32md(map->msg_id )); | |||
589 | ||||
590 | /* LRq.9: perform LSR label distribution */ | |||
591 | lde_send_labelmapping(ln, fn, 1); | |||
592 | ||||
593 | /* | |||
594 | * LRq.10: do nothing (Request Never) since we use liberal | |||
595 | * label retention. | |||
596 | * LRq.11 - 12 are unnecessary since we are merging capable. | |||
597 | */ | |||
598 | } | |||
599 | ||||
600 | void | |||
601 | lde_check_request_wcard(struct map *map, struct lde_nbr *ln) | |||
602 | { | |||
603 | struct fec *f; | |||
604 | struct fec_node *fn; | |||
605 | struct lde_req *lre; | |||
606 | ||||
607 | RB_FOREACH(f, fec_tree, &ft)for ((f) = fec_tree_RB_MINMAX(&ft, -1); (f) != ((void *)0 ); (f) = fec_tree_RB_NEXT(f)) { | |||
608 | fn = (struct fec_node *)f; | |||
609 | ||||
610 | /* only a typed wildcard is possible here */ | |||
611 | if (lde_wildcard_apply(map, &fn->fec, NULL((void *)0)) == 0) | |||
612 | continue; | |||
613 | ||||
614 | /* LRq.2: is there a next hop for fec? */ | |||
615 | if (LIST_EMPTY(&fn->nexthops)(((&fn->nexthops)->lh_first) == ((void *)0))) | |||
616 | continue; | |||
617 | ||||
618 | /* LRq.6: first check if we have a pending request running */ | |||
619 | lre = (struct lde_req *)fec_find(&ln->recv_req, &fn->fec); | |||
620 | if (lre != NULL((void *)0)) | |||
621 | /* LRq.7: duplicate request */ | |||
622 | continue; | |||
623 | ||||
624 | /* LRq.8: record label request */ | |||
625 | lre = lde_req_add(ln, &fn->fec, 0); | |||
626 | if (lre != NULL((void *)0)) | |||
627 | lre->msg_id = ntohl(map->msg_id)(__uint32_t)(__builtin_constant_p(map->msg_id) ? (__uint32_t )(((__uint32_t)(map->msg_id) & 0xff) << 24 | ((__uint32_t )(map->msg_id) & 0xff00) << 8 | ((__uint32_t)(map ->msg_id) & 0xff0000) >> 8 | ((__uint32_t)(map-> msg_id) & 0xff000000) >> 24) : __swap32md(map->msg_id )); | |||
628 | ||||
629 | /* LRq.9: perform LSR label distribution */ | |||
630 | lde_send_labelmapping(ln, fn, 1); | |||
631 | } | |||
632 | ||||
633 | /* | |||
634 | * RFC 5919 - Section 5.3: | |||
635 | * "When an LDP speaker receives a Label Request message for a Typed | |||
636 | * Wildcard FEC (e.g., a particular FEC Element Type) from a peer, the | |||
637 | * LDP speaker determines the set of bindings (as per any local | |||
638 | * filtering policy) to advertise to the peer for the FEC type specified | |||
639 | * by the request. Assuming the peer had advertised the Unrecognized | |||
640 | * Notification capability at session initialization time, the speaker | |||
641 | * should send the peer an End-of-LIB Notification for the FEC type when | |||
642 | * it completes advertisement of the permitted bindings". | |||
643 | */ | |||
644 | if (ln->flags & F_NBR_CAP_UNOTIF0x08) { | |||
645 | switch (map->fec.twcard.type) { | |||
646 | case MAP_TYPE_PREFIX0x02: | |||
647 | lde_send_notification_eol_prefix(ln, | |||
648 | map->fec.twcard.u.prefix_af); | |||
649 | break; | |||
650 | case MAP_TYPE_PWID0x80: | |||
651 | lde_send_notification_eol_pwid(ln, | |||
652 | map->fec.twcard.u.pw_type); | |||
653 | break; | |||
654 | default: | |||
655 | break; | |||
656 | } | |||
657 | } | |||
658 | } | |||
659 | ||||
660 | void | |||
661 | lde_check_release(struct map *map, struct lde_nbr *ln) | |||
662 | { | |||
663 | struct fec fec; | |||
664 | struct fec_node *fn; | |||
665 | struct lde_wdraw *lw; | |||
666 | struct lde_map *me; | |||
667 | ||||
668 | /* wildcard label release */ | |||
669 | if (map->type == MAP_TYPE_WILDCARD0x01 || | |||
670 | map->type == MAP_TYPE_TYPED_WCARD0x05 || | |||
671 | (map->type == MAP_TYPE_PWID0x80 && !(map->flags & F_MAP_PW_ID0x08))) { | |||
672 | lde_check_release_wcard(map, ln); | |||
673 | return; | |||
674 | } | |||
675 | ||||
676 | lde_map2fec(map, ln->id, &fec); | |||
677 | fn = (struct fec_node *)fec_find(&ft, &fec); | |||
678 | /* LRl.1: does FEC match a known FEC? */ | |||
679 | if (fn == NULL((void *)0)) | |||
680 | return; | |||
681 | ||||
682 | /* LRl.3: first check if we have a pending withdraw running */ | |||
683 | lw = (struct lde_wdraw *)fec_find(&ln->sent_wdraw, &fn->fec); | |||
684 | if (lw && (map->label == NO_LABEL0xffffffffU || map->label == lw->label)) { | |||
685 | /* LRl.4: delete record of outstanding label withdraw */ | |||
686 | lde_wdraw_del(ln, lw); | |||
687 | } | |||
688 | ||||
689 | /* LRl.6: check sent map list and remove it if available */ | |||
690 | me = (struct lde_map *)fec_find(&ln->sent_map, &fn->fec); | |||
691 | if (me && (map->label == NO_LABEL0xffffffffU || map->label == me->map.label)) | |||
692 | lde_map_del(ln, me, 1); | |||
693 | ||||
694 | /* | |||
695 | * LRl.11 - 13 are unnecessary since we remove the label from | |||
696 | * forwarding/switching as soon as the FEC is unreachable. | |||
697 | */ | |||
698 | } | |||
699 | ||||
700 | void | |||
701 | lde_check_release_wcard(struct map *map, struct lde_nbr *ln) | |||
702 | { | |||
703 | struct fec *f; | |||
704 | struct fec_node *fn; | |||
705 | struct lde_wdraw *lw; | |||
706 | struct lde_map *me; | |||
707 | ||||
708 | RB_FOREACH(f, fec_tree, &ft)for ((f) = fec_tree_RB_MINMAX(&ft, -1); (f) != ((void *)0 ); (f) = fec_tree_RB_NEXT(f)) { | |||
709 | fn = (struct fec_node *)f; | |||
710 | me = (struct lde_map *)fec_find(&ln->sent_map, &fn->fec); | |||
711 | ||||
712 | /* LRl.1: does FEC match a known FEC? */ | |||
713 | if (lde_wildcard_apply(map, &fn->fec, me) == 0) | |||
714 | continue; | |||
715 | ||||
716 | /* LRl.3: first check if we have a pending withdraw running */ | |||
717 | lw = (struct lde_wdraw *)fec_find(&ln->sent_wdraw, &fn->fec); | |||
718 | if (lw && (map->label == NO_LABEL0xffffffffU || map->label == lw->label)) { | |||
719 | /* LRl.4: delete record of outstanding lbl withdraw */ | |||
720 | lde_wdraw_del(ln, lw); | |||
721 | } | |||
722 | ||||
723 | /* LRl.6: check sent map list and remove it if available */ | |||
724 | if (me && | |||
725 | (map->label == NO_LABEL0xffffffffU || map->label == me->map.label)) | |||
726 | lde_map_del(ln, me, 1); | |||
727 | ||||
728 | /* | |||
729 | * LRl.11 - 13 are unnecessary since we remove the label from | |||
730 | * forwarding/switching as soon as the FEC is unreachable. | |||
731 | */ | |||
732 | } | |||
733 | } | |||
734 | ||||
735 | void | |||
736 | lde_check_withdraw(struct map *map, struct lde_nbr *ln) | |||
737 | { | |||
738 | struct fec fec; | |||
739 | struct fec_node *fn; | |||
740 | struct fec_nh *fnh; | |||
741 | struct lde_map *me; | |||
742 | struct l2vpn_pw *pw; | |||
743 | ||||
744 | /* wildcard label withdraw */ | |||
745 | if (map->type == MAP_TYPE_WILDCARD0x01 || | |||
746 | map->type == MAP_TYPE_TYPED_WCARD0x05 || | |||
747 | (map->type == MAP_TYPE_PWID0x80 && !(map->flags & F_MAP_PW_ID0x08))) { | |||
748 | lde_check_withdraw_wcard(map, ln); | |||
749 | return; | |||
750 | } | |||
751 | ||||
752 | lde_map2fec(map, ln->id, &fec); | |||
753 | fn = (struct fec_node *)fec_find(&ft, &fec); | |||
754 | if (fn == NULL((void *)0)) | |||
755 | fn = fec_add(&fec); | |||
756 | ||||
757 | /* LWd.1: remove label from forwarding/switching use */ | |||
758 | LIST_FOREACH(fnh, &fn->nexthops, entry)for((fnh) = ((&fn->nexthops)->lh_first); (fnh)!= (( void *)0); (fnh) = ((fnh)->entry.le_next)) { | |||
759 | switch (fec.type) { | |||
760 | case FEC_TYPE_IPV4: | |||
761 | case FEC_TYPE_IPV6: | |||
762 | if (!lde_address_find(ln, fnh->af, &fnh->nexthop)) | |||
763 | continue; | |||
764 | break; | |||
765 | case FEC_TYPE_PWID: | |||
766 | pw = (struct l2vpn_pw *) fn->data; | |||
767 | if (pw == NULL((void *)0)) | |||
768 | continue; | |||
769 | break; | |||
770 | default: | |||
771 | break; | |||
772 | } | |||
773 | if (map->label != NO_LABEL0xffffffffU && map->label != fnh->remote_label) | |||
774 | continue; | |||
775 | ||||
776 | lde_send_delete_klabel(fn, fnh); | |||
777 | fnh->remote_label = NO_LABEL0xffffffffU; | |||
778 | } | |||
779 | ||||
780 | /* LWd.2: send label release */ | |||
781 | lde_send_labelrelease(ln, fn, NULL((void *)0), map->label); | |||
782 | ||||
783 | /* LWd.3: check previously received label mapping */ | |||
784 | me = (struct lde_map *)fec_find(&ln->recv_map, &fn->fec); | |||
785 | if (me && (map->label == NO_LABEL0xffffffffU || map->label == me->map.label)) | |||
786 | /* LWd.4: remove record of previously received lbl mapping */ | |||
787 | lde_map_del(ln, me, 0); | |||
788 | } | |||
789 | ||||
790 | void | |||
791 | lde_check_withdraw_wcard(struct map *map, struct lde_nbr *ln) | |||
792 | { | |||
793 | struct fec *f; | |||
794 | struct fec_node *fn; | |||
795 | struct fec_nh *fnh; | |||
796 | struct lde_map *me; | |||
797 | ||||
798 | /* LWd.2: send label release */ | |||
799 | lde_send_labelrelease(ln, NULL((void *)0), map, map->label); | |||
800 | ||||
801 | RB_FOREACH(f, fec_tree, &ft)for ((f) = fec_tree_RB_MINMAX(&ft, -1); (f) != ((void *)0 ); (f) = fec_tree_RB_NEXT(f)) { | |||
802 | fn = (struct fec_node *)f; | |||
803 | me = (struct lde_map *)fec_find(&ln->recv_map, &fn->fec); | |||
804 | ||||
805 | if (lde_wildcard_apply(map, &fn->fec, me) == 0) | |||
806 | continue; | |||
807 | ||||
808 | /* LWd.1: remove label from forwarding/switching use */ | |||
809 | LIST_FOREACH(fnh, &fn->nexthops, entry)for((fnh) = ((&fn->nexthops)->lh_first); (fnh)!= (( void *)0); (fnh) = ((fnh)->entry.le_next)) { | |||
810 | switch (f->type) { | |||
811 | case FEC_TYPE_IPV4: | |||
812 | case FEC_TYPE_IPV6: | |||
813 | if (!lde_address_find(ln, fnh->af, | |||
814 | &fnh->nexthop)) | |||
815 | continue; | |||
816 | break; | |||
817 | case FEC_TYPE_PWID: | |||
818 | if (f->u.pwid.lsr_id.s_addr != ln->id.s_addr) | |||
819 | continue; | |||
820 | break; | |||
821 | default: | |||
822 | break; | |||
823 | } | |||
824 | if (map->label != NO_LABEL0xffffffffU && map->label != | |||
825 | fnh->remote_label) | |||
826 | continue; | |||
827 | ||||
828 | lde_send_delete_klabel(fn, fnh); | |||
829 | fnh->remote_label = NO_LABEL0xffffffffU; | |||
830 | } | |||
831 | ||||
832 | /* LWd.3: check previously received label mapping */ | |||
833 | if (me && (map->label == NO_LABEL0xffffffffU || | |||
834 | map->label == me->map.label)) | |||
835 | /* | |||
836 | * LWd.4: remove record of previously received | |||
837 | * label mapping | |||
838 | */ | |||
839 | lde_map_del(ln, me, 0); | |||
840 | } | |||
841 | } | |||
842 | ||||
843 | int | |||
844 | lde_wildcard_apply(struct map *wcard, struct fec *fec, struct lde_map *me) | |||
845 | { | |||
846 | switch (wcard->type) { | |||
847 | case MAP_TYPE_WILDCARD0x01: | |||
848 | /* full wildcard */ | |||
849 | return (1); | |||
850 | case MAP_TYPE_TYPED_WCARD0x05: | |||
851 | switch (wcard->fec.twcard.type) { | |||
852 | case MAP_TYPE_PREFIX0x02: | |||
853 | if (wcard->fec.twcard.u.prefix_af == AF_INET2 && | |||
854 | fec->type != FEC_TYPE_IPV4) | |||
855 | return (0); | |||
856 | if (wcard->fec.twcard.u.prefix_af == AF_INET624 && | |||
857 | fec->type != FEC_TYPE_IPV6) | |||
858 | return (0); | |||
859 | return (1); | |||
860 | case MAP_TYPE_PWID0x80: | |||
861 | if (fec->type != FEC_TYPE_PWID) | |||
862 | return (0); | |||
863 | if (wcard->fec.twcard.u.pw_type != PW_TYPE_WILDCARD0x7FFF && | |||
864 | wcard->fec.twcard.u.pw_type != fec->u.pwid.type) | |||
865 | return (0); | |||
866 | return (1); | |||
867 | default: | |||
868 | fatalx("lde_wildcard_apply: unexpected fec type"); | |||
869 | } | |||
870 | break; | |||
871 | case MAP_TYPE_PWID0x80: | |||
872 | /* RFC4447 pw-id group wildcard */ | |||
873 | if (fec->type != FEC_TYPE_PWID) | |||
874 | return (0); | |||
875 | if (fec->u.pwid.type != wcard->fec.pwid.type) | |||
876 | return (0); | |||
877 | if (me == NULL((void *)0) || (me->map.fec.pwid.group_id != | |||
878 | wcard->fec.pwid.group_id)) | |||
879 | return (0); | |||
880 | return (1); | |||
881 | default: | |||
882 | fatalx("lde_wildcard_apply: unexpected fec type"); | |||
883 | } | |||
884 | } | |||
885 | ||||
886 | /* gabage collector timer: timer to remove dead entries from the LIB */ | |||
887 | ||||
888 | /* ARGSUSED */ | |||
889 | void | |||
890 | lde_gc_timer(int fd, short event, void *arg) | |||
891 | { | |||
892 | struct fec *fec, *safe; | |||
893 | struct fec_node *fn; | |||
894 | int count = 0; | |||
895 | ||||
896 | RB_FOREACH_SAFE(fec, fec_tree, &ft, safe)for ((fec) = fec_tree_RB_MINMAX(&ft, -1); ((fec) != ((void *)0)) && ((safe) = fec_tree_RB_NEXT(fec), 1); (fec) = (safe)) { | |||
897 | fn = (struct fec_node *) fec; | |||
898 | ||||
899 | if (!LIST_EMPTY(&fn->nexthops)(((&fn->nexthops)->lh_first) == ((void *)0)) || | |||
900 | !LIST_EMPTY(&fn->downstream)(((&fn->downstream)->lh_first) == ((void *)0)) || | |||
901 | !LIST_EMPTY(&fn->upstream)(((&fn->upstream)->lh_first) == ((void *)0))) | |||
902 | continue; | |||
903 | ||||
904 | fec_remove(&ft, &fn->fec); | |||
905 | free(fn); | |||
906 | count++; | |||
907 | } | |||
908 | ||||
909 | if (count > 0) | |||
910 | log_debug("%s: %u entries removed", __func__, count); | |||
911 | ||||
912 | lde_gc_start_timer(); | |||
913 | } | |||
914 | ||||
915 | void | |||
916 | lde_gc_start_timer(void) | |||
917 | { | |||
918 | struct timeval tv; | |||
919 | ||||
920 | timerclear(&tv)(&tv)->tv_sec = (&tv)->tv_usec = 0; | |||
921 | tv.tv_sec = LDE_GC_INTERVAL300; | |||
922 | if (evtimer_add(&gc_timer, &tv)event_add(&gc_timer, &tv) == -1) | |||
923 | fatal(__func__); | |||
924 | } | |||
925 | ||||
926 | void | |||
927 | lde_gc_stop_timer(void) | |||
928 | { | |||
929 | if (evtimer_pending(&gc_timer, NULL)event_pending(&gc_timer, 0x01, ((void *)0)) && | |||
930 | evtimer_del(&gc_timer)event_del(&gc_timer) == -1) | |||
931 | fatal(__func__); | |||
932 | } |