]>
git.proxmox.com Git - mirror_frr.git/blob - ldpd/lde_lib.c
1 // SPDX-License-Identifier: ISC
5 * Copyright (c) 2013, 2016 Renato Westphal <renato@openbsd.org>
6 * Copyright (c) 2009 Michele Marchetto <michele@openbsd.org>
19 static __inline
int fec_compare(const struct fec
*, const struct fec
*);
20 static int lde_nbr_is_nexthop(struct fec_node
*,
22 static void fec_free(void *);
23 static struct fec_node
*fec_add(struct fec
*fec
);
24 static struct fec_nh
*fec_nh_add(struct fec_node
*, int, union ldpd_addr
*,
25 ifindex_t
, uint8_t, unsigned short);
26 static void fec_nh_del(struct fec_nh
*);
28 RB_GENERATE(fec_tree
, fec
, entry
, fec_compare
)
30 struct fec_tree ft
= RB_INITIALIZER(&ft
);
31 struct thread
*gc_timer
;
33 /* FEC tree functions */
35 fec_init(struct fec_tree
*fh
)
37 RB_INIT(fec_tree
, fh
);
41 fec_compare(const struct fec
*a
, const struct fec
*b
)
43 if (a
->type
< b
->type
)
45 if (a
->type
> b
->type
)
50 if (ntohl(a
->u
.ipv4
.prefix
.s_addr
) <
51 ntohl(b
->u
.ipv4
.prefix
.s_addr
))
53 if (ntohl(a
->u
.ipv4
.prefix
.s_addr
) >
54 ntohl(b
->u
.ipv4
.prefix
.s_addr
))
56 if (a
->u
.ipv4
.prefixlen
< b
->u
.ipv4
.prefixlen
)
58 if (a
->u
.ipv4
.prefixlen
> b
->u
.ipv4
.prefixlen
)
62 if (memcmp(&a
->u
.ipv6
.prefix
, &b
->u
.ipv6
.prefix
,
63 sizeof(struct in6_addr
)) < 0)
65 if (memcmp(&a
->u
.ipv6
.prefix
, &b
->u
.ipv6
.prefix
,
66 sizeof(struct in6_addr
)) > 0)
68 if (a
->u
.ipv6
.prefixlen
< b
->u
.ipv6
.prefixlen
)
70 if (a
->u
.ipv6
.prefixlen
> b
->u
.ipv6
.prefixlen
)
74 if (a
->u
.pwid
.type
< b
->u
.pwid
.type
)
76 if (a
->u
.pwid
.type
> b
->u
.pwid
.type
)
78 if (a
->u
.pwid
.pwid
< b
->u
.pwid
.pwid
)
80 if (a
->u
.pwid
.pwid
> b
->u
.pwid
.pwid
)
82 if (ntohl(a
->u
.pwid
.lsr_id
.s_addr
) <
83 ntohl(b
->u
.pwid
.lsr_id
.s_addr
))
85 if (ntohl(a
->u
.pwid
.lsr_id
.s_addr
) >
86 ntohl(b
->u
.pwid
.lsr_id
.s_addr
))
95 fec_find(struct fec_tree
*fh
, struct fec
*f
)
97 return (RB_FIND(fec_tree
, fh
, f
));
101 fec_insert(struct fec_tree
*fh
, struct fec
*f
)
103 if (RB_INSERT(fec_tree
, fh
, f
) != NULL
)
109 fec_remove(struct fec_tree
*fh
, struct fec
*f
)
111 if (RB_REMOVE(fec_tree
, fh
, f
) == NULL
) {
112 log_warnx("%s failed for %s", __func__
, log_fec(f
));
119 fec_clear(struct fec_tree
*fh
, void (*free_cb
)(void *))
123 while (!RB_EMPTY(fec_tree
, fh
)) {
124 f
= RB_ROOT(fec_tree
, fh
);
131 /* routing table functions */
133 lde_nbr_is_nexthop(struct fec_node
*fn
, struct lde_nbr
*ln
)
137 LIST_FOREACH(fnh
, &fn
->nexthops
, entry
)
138 if (lde_address_find(ln
, fnh
->af
, &fnh
->nexthop
))
150 static struct ctl_rt rtctl
;
152 RB_FOREACH(f
, fec_tree
, &ft
) {
153 fn
= (struct fec_node
*)f
;
154 if (fn
->local_label
== NO_LABEL
&&
155 RB_EMPTY(lde_map_head
, &fn
->downstream
))
158 memset(&rtctl
, 0, sizeof(rtctl
));
159 switch (fn
->fec
.type
) {
162 rtctl
.prefix
.v4
= fn
->fec
.u
.ipv4
.prefix
;
163 rtctl
.prefixlen
= fn
->fec
.u
.ipv4
.prefixlen
;
167 rtctl
.prefix
.v6
= fn
->fec
.u
.ipv6
.prefix
;
168 rtctl
.prefixlen
= fn
->fec
.u
.ipv6
.prefixlen
;
174 rtctl
.local_label
= fn
->local_label
;
175 if (RB_EMPTY(lde_map_head
, &fn
->downstream
)) {
177 rtctl
.nexthop
.s_addr
= INADDR_ANY
;
178 rtctl
.remote_label
= NO_LABEL
;
179 rtctl
.no_downstream
= 1;
181 lde_imsg_compose_ldpe(IMSG_CTL_SHOW_LIB_BEGIN
, 0, pid
, &rtctl
,
184 RB_FOREACH(me
, lde_map_head
, &fn
->upstream
) {
185 rtctl
.nexthop
= me
->nexthop
->id
;
186 lde_imsg_compose_ldpe(IMSG_CTL_SHOW_LIB_SENT
, 0, pid
,
187 &rtctl
, sizeof(rtctl
));
190 RB_FOREACH(me
, lde_map_head
, &fn
->downstream
) {
191 rtctl
.in_use
= lde_nbr_is_nexthop(fn
, me
->nexthop
);
192 rtctl
.nexthop
= me
->nexthop
->id
;
193 rtctl
.remote_label
= me
->map
.label
;
194 lde_imsg_compose_ldpe(IMSG_CTL_SHOW_LIB_RCVD
, 0, pid
,
195 &rtctl
, sizeof(rtctl
));
197 lde_imsg_compose_ldpe(IMSG_CTL_SHOW_LIB_END
, 0, pid
, &rtctl
,
203 fec_snap(struct lde_nbr
*ln
)
208 RB_FOREACH(f
, fec_tree
, &ft
) {
209 fn
= (struct fec_node
*)f
;
210 if (fn
->local_label
== NO_LABEL
)
213 lde_send_labelmapping(ln
, fn
, 0);
216 lde_imsg_compose_ldpe(IMSG_MAPPING_ADD_END
, ln
->peerid
, 0, NULL
, 0);
222 struct fec_node
*fn
= arg
;
225 while ((fnh
= LIST_FIRST(&fn
->nexthops
))) {
227 assert(fnh
!= LIST_FIRST(&fn
->nexthops
));
229 if (!RB_EMPTY(lde_map_head
, &fn
->downstream
))
230 log_warnx("%s: fec %s downstream list not empty", __func__
,
232 if (!RB_EMPTY(lde_map_head
, &fn
->upstream
))
233 log_warnx("%s: fec %s upstream list not empty", __func__
,
242 fec_clear(&ft
, fec_free
);
245 static struct fec_node
*
246 fec_add(struct fec
*fec
)
250 fn
= calloc(1, sizeof(*fn
));
255 fn
->local_label
= NO_LABEL
;
256 RB_INIT(lde_map_head
, &fn
->upstream
);
257 RB_INIT(lde_map_head
, &fn
->downstream
);
258 LIST_INIT(&fn
->nexthops
);
260 if (fec
->type
== FEC_TYPE_PWID
)
261 fn
->pw_remote_status
= PW_FORWARDING
;
263 if (fec_insert(&ft
, &fn
->fec
))
264 log_warnx("failed to add %s to ft tree",
271 fec_nh_find(struct fec_node
*fn
, int af
, union ldpd_addr
*nexthop
,
272 ifindex_t ifindex
, uint8_t route_type
, unsigned short route_instance
)
276 LIST_FOREACH(fnh
, &fn
->nexthops
, entry
)
278 ldp_addrcmp(af
, &fnh
->nexthop
, nexthop
) == 0 &&
279 fnh
->ifindex
== ifindex
&&
280 fnh
->route_type
== route_type
&&
281 fnh
->route_instance
== route_instance
)
287 static struct fec_nh
*
288 fec_nh_add(struct fec_node
*fn
, int af
, union ldpd_addr
*nexthop
,
289 ifindex_t ifindex
, uint8_t route_type
, unsigned short route_instance
)
293 fnh
= calloc(1, sizeof(*fnh
));
298 fnh
->nexthop
= *nexthop
;
299 fnh
->ifindex
= ifindex
;
300 fnh
->remote_label
= NO_LABEL
;
301 fnh
->route_type
= route_type
;
302 fnh
->route_instance
= route_instance
;
303 LIST_INSERT_HEAD(&fn
->nexthops
, fnh
, entry
);
309 fec_nh_del(struct fec_nh
*fnh
)
311 LIST_REMOVE(fnh
, entry
);
316 lde_kernel_insert(struct fec
*fec
, int af
, union ldpd_addr
*nexthop
,
317 ifindex_t ifindex
, uint8_t route_type
, unsigned short route_instance
,
318 int connected
, void *data
)
324 fn
= (struct fec_node
*)fec_find(&ft
, fec
);
330 fnh
= fec_nh_find(fn
, af
, nexthop
, ifindex
, route_type
, route_instance
);
332 fnh
= fec_nh_add(fn
, af
, nexthop
, ifindex
, route_type
,
335 * Ordered Control: if not a connected route and not a route
336 * learned over an interface not running LDP and not a PW
337 * then mark to wait until we receive labelmap msg before
338 * installing in kernel and sending to peer
340 iface
= if_lookup(ldeconf
, ifindex
);
341 if ((ldeconf
->flags
& F_LDPD_ORDERED_CONTROL
) &&
342 !connected
&& iface
!= NULL
&& fec
->type
!= FEC_TYPE_PWID
)
343 fnh
->flags
|= F_FEC_NH_DEFER
;
346 fnh
->flags
|= F_FEC_NH_NEW
;
348 fnh
->flags
|= F_FEC_NH_CONNECTED
;
352 lde_kernel_remove(struct fec
*fec
, int af
, union ldpd_addr
*nexthop
,
353 ifindex_t ifindex
, uint8_t route_type
, unsigned short route_instance
)
358 fn
= (struct fec_node
*)fec_find(&ft
, fec
);
362 fnh
= fec_nh_find(fn
, af
, nexthop
, ifindex
, route_type
, route_instance
);
367 lde_send_delete_klabel(fn
, fnh
);
372 * Whenever a route is changed, zebra advertises its new version without
373 * withdrawing the old one. So, after processing a ZEBRA_REDISTRIBUTE_IPV[46]_ADD
374 * message, we need to check for nexthops that were removed and, for each of
375 * them (if any), withdraw the associated labels from zebra.
378 lde_kernel_update(struct fec
*fec
)
381 struct fec_nh
*fnh
, *safe
;
386 fn
= (struct fec_node
*)fec_find(&ft
, fec
);
390 LIST_FOREACH_SAFE(fnh
, &fn
->nexthops
, entry
, safe
) {
391 if (fnh
->flags
& F_FEC_NH_NEW
) {
392 fnh
->flags
&= ~F_FEC_NH_NEW
;
394 * if LDP configured on interface or a static route
395 * clear flag else treat fec as a connected route
397 if (ldeconf
->flags
& F_LDPD_ENABLED
) {
398 iface
= if_lookup(ldeconf
,fnh
->ifindex
);
399 if (fnh
->flags
& F_FEC_NH_CONNECTED
||
401 fnh
->route_type
== ZEBRA_ROUTE_STATIC
)
402 fnh
->flags
&=~F_FEC_NH_NO_LDP
;
404 fnh
->flags
|= F_FEC_NH_NO_LDP
;
406 fnh
->flags
|= F_FEC_NH_NO_LDP
;
408 lde_send_delete_klabel(fn
, fnh
);
413 if (LIST_EMPTY(&fn
->nexthops
)) {
414 RB_FOREACH(ln
, nbr_tree
, &lde_nbrs
)
415 lde_send_labelwithdraw(ln
, fn
, NULL
, NULL
);
419 * Do not deallocate the local label now, do that only in the
420 * LIB garbage collector. This will prevent ldpd from changing
421 * the input label of some prefixes too often when running on
422 * an unstable network. Also, restart the garbage collector
423 * timer so that labels are deallocated only when the network
426 lde_gc_start_timer();
428 fn
->local_label
= lde_update_label(fn
);
429 if (fn
->local_label
!= NO_LABEL
)
430 /* FEC.1: perform lsr label distribution procedure */
431 RB_FOREACH(ln
, nbr_tree
, &lde_nbrs
)
432 lde_send_labelmapping(ln
, fn
, 1);
435 /* if no label created yet then don't try to program labeled route */
436 if (fn
->local_label
== NO_LABEL
)
439 LIST_FOREACH(fnh
, &fn
->nexthops
, entry
) {
440 lde_send_change_klabel(fn
, fnh
);
442 switch (fn
->fec
.type
) {
445 ln
= lde_nbr_find_by_addr(fnh
->af
, &fnh
->nexthop
);
448 ln
= lde_nbr_find_by_lsrid(fn
->fec
.u
.pwid
.lsr_id
);
457 me
= (struct lde_map
*)fec_find(&ln
->recv_map
, &fn
->fec
);
460 lde_check_mapping(&me
->map
, ln
, 0);
466 lde_check_mapping(struct map
*map
, struct lde_nbr
*ln
, int rcvd_label_mapping
)
474 bool send_map
= false;
476 lde_map2fec(map
, ln
->id
, &fec
);
480 if (lde_acl_check(ldeconf
->ipv4
.acl_label_accept_from
,
481 AF_INET
, (union ldpd_addr
*)&ln
->id
, 32) != FILTER_PERMIT
)
483 if (lde_acl_check(ldeconf
->ipv4
.acl_label_accept_for
,
484 AF_INET
, (union ldpd_addr
*)&fec
.u
.ipv4
.prefix
,
485 fec
.u
.ipv4
.prefixlen
) != FILTER_PERMIT
)
489 if (lde_acl_check(ldeconf
->ipv6
.acl_label_accept_from
,
490 AF_INET
, (union ldpd_addr
*)&ln
->id
, 32) != FILTER_PERMIT
)
492 if (lde_acl_check(ldeconf
->ipv6
.acl_label_accept_for
,
493 AF_INET6
, (union ldpd_addr
*)&fec
.u
.ipv6
.prefix
,
494 fec
.u
.ipv6
.prefixlen
) != FILTER_PERMIT
)
501 fn
= (struct fec_node
*)fec_find(&ft
, &fec
);
505 /* LMp.1: first check if we have a pending request running */
506 lre
= (struct lde_req
*)fec_find(&ln
->sent_req
, &fn
->fec
);
508 /* LMp.2: delete record of outstanding label request */
509 lde_req_del(ln
, lre
, 1);
511 /* RFC 4447 control word and status tlv negotiation */
512 if (map
->type
== MAP_TYPE_PWID
&& l2vpn_pw_negotiate(ln
, fn
, map
)) {
513 if (rcvd_label_mapping
&& map
->flags
& F_MAP_PW_STATUS
)
514 fn
->pw_remote_status
= map
->pw_status
;
520 * LMp.3 - LMp.8: loop detection - unnecessary for frame-mode
525 me
= (struct lde_map
*)fec_find(&ln
->recv_map
, &fn
->fec
);
528 if (me
->map
.label
!= map
->label
&& lre
== NULL
) {
530 lde_send_labelrelease(ln
, fn
, NULL
, me
->map
.label
);
533 * Can not use lde_nbr_find_by_addr() because there's
534 * the possibility of multipath.
536 LIST_FOREACH(fnh
, &fn
->nexthops
, entry
) {
537 if (lde_address_find(ln
, fnh
->af
,
538 &fnh
->nexthop
) == NULL
)
541 lde_send_delete_klabel(fn
, fnh
);
542 fnh
->remote_label
= NO_LABEL
;
548 * LMp.11 - 12: consider multiple nexthops in order to
551 LIST_FOREACH(fnh
, &fn
->nexthops
, entry
) {
552 /* LMp.15: install FEC in FIB */
556 if (!lde_address_find(ln
, fnh
->af
, &fnh
->nexthop
))
560 * Ordered Control: labelmap msg received from
561 * NH so clear flag and send labelmap msg to
564 if (ldeconf
->flags
& F_LDPD_ORDERED_CONTROL
) {
566 fnh
->flags
&= ~F_FEC_NH_DEFER
;
568 fnh
->remote_label
= map
->label
;
569 if (fn
->local_label
!= NO_LABEL
)
570 lde_send_change_klabel(fn
, fnh
);
573 pw
= (struct l2vpn_pw
*) fn
->data
;
577 pw
->remote_group
= map
->fec
.pwid
.group_id
;
578 if (map
->flags
& F_MAP_PW_IFMTU
)
579 pw
->remote_mtu
= map
->fec
.pwid
.ifmtu
;
580 if (rcvd_label_mapping
&& map
->flags
& F_MAP_PW_STATUS
) {
581 pw
->remote_status
= map
->pw_status
;
582 fn
->pw_remote_status
= map
->pw_status
;
585 pw
->remote_status
= PW_FORWARDING
;
586 fnh
->remote_label
= map
->label
;
587 if (l2vpn_pw_ok(pw
, fnh
))
588 lde_send_change_klabel(fn
, fnh
);
595 /* Update RLFA clients. */
596 lde_rlfa_update_clients(&fec
, ln
, map
->label
);
598 /* LMp.13 & LMp.16: Record the mapping from this peer */
600 me
= lde_map_add(ln
, fn
, 0);
604 * LMp.17 - LMp.27 are unnecessary since we don't need to implement
605 * loop detection. LMp.28 - LMp.30 are unnecessary because we are
610 * Ordered Control: just received a labelmap for this fec from NH so
611 * need to send labelmap to all peers
612 * LMp.20 - LMp21 Execute procedure to send Label Mapping
614 if (send_map
&& fn
->local_label
!= NO_LABEL
)
615 RB_FOREACH(ln
, nbr_tree
, &lde_nbrs
)
616 lde_send_labelmapping(ln
, fn
, 1);
620 lde_check_request(struct map
*map
, struct lde_nbr
*ln
)
627 /* wildcard label request */
628 if (map
->type
== MAP_TYPE_TYPED_WCARD
) {
629 lde_check_request_wcard(map
, ln
);
633 /* LRq.1: skip loop detection (not necessary) */
635 /* LRq.2: is there a next hop for fec? */
636 lde_map2fec(map
, ln
->id
, &fec
);
637 fn
= (struct fec_node
*)fec_find(&ft
, &fec
);
638 if (fn
== NULL
|| LIST_EMPTY(&fn
->nexthops
)) {
639 /* LRq.5: send No Route notification */
640 lde_send_notification(ln
, S_NO_ROUTE
, map
->msg_id
,
641 htons(MSG_TYPE_LABELREQUEST
));
645 /* LRq.3: is MsgSource the next hop? */
646 LIST_FOREACH(fnh
, &fn
->nexthops
, entry
) {
650 if (!lde_address_find(ln
, fnh
->af
, &fnh
->nexthop
))
653 /* LRq.4: send Loop Detected notification */
654 lde_send_notification(ln
, S_LOOP_DETECTED
, map
->msg_id
,
655 htons(MSG_TYPE_LABELREQUEST
));
662 /* LRq.6: first check if we have a pending request running */
663 lre
= (struct lde_req
*)fec_find(&ln
->recv_req
, &fn
->fec
);
665 /* LRq.7: duplicate request */
668 /* LRq.8: record label request */
669 lre
= lde_req_add(ln
, &fn
->fec
, 0);
671 lre
->msg_id
= ntohl(map
->msg_id
);
673 /* LRq.9: perform LSR label distribution */
674 lde_send_labelmapping(ln
, fn
, 1);
677 * LRq.10: do nothing (Request Never) since we use liberal
679 * LRq.11 - 12 are unnecessary since we are merging capable.
684 lde_check_request_wcard(struct map
*map
, struct lde_nbr
*ln
)
690 RB_FOREACH(f
, fec_tree
, &ft
) {
691 fn
= (struct fec_node
*)f
;
693 /* only a typed wildcard is possible here */
694 if (lde_wildcard_apply(map
, &fn
->fec
, NULL
) == 0)
697 /* LRq.2: is there a next hop for fec? */
698 if (LIST_EMPTY(&fn
->nexthops
))
701 /* LRq.6: first check if we have a pending request running */
702 lre
= (struct lde_req
*)fec_find(&ln
->recv_req
, &fn
->fec
);
704 /* LRq.7: duplicate request */
707 /* LRq.8: record label request */
708 lre
= lde_req_add(ln
, &fn
->fec
, 0);
710 lre
->msg_id
= ntohl(map
->msg_id
);
712 /* LRq.9: perform LSR label distribution */
713 lde_send_labelmapping(ln
, fn
, 1);
718 lde_check_release(struct map
*map
, struct lde_nbr
*ln
)
722 struct lde_wdraw
*lw
;
724 struct fec
*pending_map
;
726 /* wildcard label release */
727 if (map
->type
== MAP_TYPE_WILDCARD
||
728 map
->type
== MAP_TYPE_TYPED_WCARD
||
729 (map
->type
== MAP_TYPE_PWID
&& !(map
->flags
& F_MAP_PW_ID
))) {
730 lde_check_release_wcard(map
, ln
);
734 lde_map2fec(map
, ln
->id
, &fec
);
735 fn
= (struct fec_node
*)fec_find(&ft
, &fec
);
736 /* LRl.1: does FEC match a known FEC? */
740 /* LRl.6: check sent map list and remove it if available */
741 me
= (struct lde_map
*)fec_find(&ln
->sent_map
, &fn
->fec
);
742 if (me
&& (map
->label
== NO_LABEL
|| map
->label
== me
->map
.label
))
743 lde_map_del(ln
, me
, 1);
745 /* LRl.3: first check if we have a pending withdraw running */
746 lw
= (struct lde_wdraw
*)fec_find(&ln
->sent_wdraw
, &fn
->fec
);
747 if (lw
&& (map
->label
== NO_LABEL
|| map
->label
== lw
->label
)) {
748 /* LRl.4: delete record of outstanding label withdraw */
749 lde_wdraw_del(ln
, lw
);
751 /* send pending label mapping if any */
752 pending_map
= fec_find(&ln
->sent_map_pending
, &fn
->fec
);
754 lde_send_labelmapping(ln
, fn
, 1);
755 lde_map_pending_del(ln
, pending_map
);
760 * LRl.11 - 13 are unnecessary since we remove the label from
761 * forwarding/switching as soon as the FEC is unreachable.
766 lde_check_release_wcard(struct map
*map
, struct lde_nbr
*ln
)
770 struct lde_wdraw
*lw
;
772 struct fec
*pending_map
;
774 RB_FOREACH(f
, fec_tree
, &ft
) {
775 fn
= (struct fec_node
*)f
;
776 me
= (struct lde_map
*)fec_find(&ln
->sent_map
, &fn
->fec
);
778 /* LRl.1: does FEC match a known FEC? */
779 if (lde_wildcard_apply(map
, &fn
->fec
, me
) == 0)
782 /* LRl.6: check sent map list and remove it if available */
784 (map
->label
== NO_LABEL
|| map
->label
== me
->map
.label
))
785 lde_map_del(ln
, me
, 1);
787 /* LRl.3: first check if we have a pending withdraw running */
788 lw
= (struct lde_wdraw
*)fec_find(&ln
->sent_wdraw
, &fn
->fec
);
789 if (lw
&& (map
->label
== NO_LABEL
|| map
->label
== lw
->label
)) {
790 /* LRl.4: delete record of outstanding lbl withdraw */
791 lde_wdraw_del(ln
, lw
);
793 /* send pending label mapping if any */
794 pending_map
= fec_find(&ln
->sent_map_pending
, &fn
->fec
);
796 lde_send_labelmapping(ln
, fn
, 1);
797 lde_map_pending_del(ln
, pending_map
);
802 * LRl.11 - 13 are unnecessary since we remove the label from
803 * forwarding/switching as soon as the FEC is unreachable.
809 lde_check_withdraw(struct map
*map
, struct lde_nbr
*ln
)
816 struct lde_nbr
*lnbr
;
818 /* wildcard label withdraw */
819 if (map
->type
== MAP_TYPE_WILDCARD
||
820 map
->type
== MAP_TYPE_TYPED_WCARD
||
821 (map
->type
== MAP_TYPE_PWID
&& !(map
->flags
& F_MAP_PW_ID
))) {
822 lde_check_withdraw_wcard(map
, ln
);
826 lde_map2fec(map
, ln
->id
, &fec
);
827 fn
= (struct fec_node
*)fec_find(&ft
, &fec
);
831 /* LWd.1: remove label from forwarding/switching use */
832 LIST_FOREACH(fnh
, &fn
->nexthops
, entry
) {
836 if (!lde_address_find(ln
, fnh
->af
, &fnh
->nexthop
))
840 pw
= (struct l2vpn_pw
*) fn
->data
;
843 pw
->remote_status
= PW_NOT_FORWARDING
;
848 if (map
->label
!= NO_LABEL
&& map
->label
!= fnh
->remote_label
)
851 lde_send_delete_klabel(fn
, fnh
);
852 fnh
->remote_label
= NO_LABEL
;
855 /* Update RLFA clients. */
856 lde_rlfa_update_clients(&fec
, ln
, MPLS_INVALID_LABEL
);
858 /* LWd.2: send label release */
859 lde_send_labelrelease(ln
, fn
, NULL
, map
->label
);
861 /* LWd.3: check previously received label mapping */
862 me
= (struct lde_map
*)fec_find(&ln
->recv_map
, &fn
->fec
);
863 if (me
&& (map
->label
== NO_LABEL
|| map
->label
== me
->map
.label
))
864 /* LWd.4: remove record of previously received lbl mapping */
865 lde_map_del(ln
, me
, 0);
870 /* Ordered Control: additional withdraw steps */
871 if (ldeconf
->flags
& F_LDPD_ORDERED_CONTROL
) {
872 /* LWd.8: for each neighbor other that src of withdraw msg */
873 RB_FOREACH(lnbr
, nbr_tree
, &lde_nbrs
) {
874 if (ln
->peerid
== lnbr
->peerid
)
877 /* LWd.9: check if previously sent a label mapping */
878 me
= (struct lde_map
*)fec_find(&lnbr
->sent_map
,
882 * LWd.10: does label sent to peer "map" to withdraw
885 if (me
&& lde_nbr_is_nexthop(fn
, lnbr
))
886 /* LWd.11: send label withdraw */
887 lde_send_labelwithdraw(lnbr
, fn
, NULL
, NULL
);
894 lde_check_withdraw_wcard(struct map
*map
, struct lde_nbr
*ln
)
901 struct lde_nbr
*lnbr
;
903 /* LWd.2: send label release */
904 lde_send_labelrelease(ln
, NULL
, map
, map
->label
);
906 RB_FOREACH(f
, fec_tree
, &ft
) {
907 fn
= (struct fec_node
*)f
;
908 me
= (struct lde_map
*)fec_find(&ln
->recv_map
, &fn
->fec
);
910 if (lde_wildcard_apply(map
, &fn
->fec
, me
) == 0)
913 /* LWd.1: remove label from forwarding/switching use */
914 LIST_FOREACH(fnh
, &fn
->nexthops
, entry
) {
918 if (!lde_address_find(ln
, fnh
->af
,
923 if (f
->u
.pwid
.lsr_id
.s_addr
!= ln
->id
.s_addr
)
925 pw
= (struct l2vpn_pw
*) fn
->data
;
927 pw
->remote_status
= PW_NOT_FORWARDING
;
932 if (map
->label
!= NO_LABEL
&& map
->label
!=
936 lde_send_delete_klabel(fn
, fnh
);
937 fnh
->remote_label
= NO_LABEL
;
940 /* Update RLFA clients. */
941 lde_rlfa_update_clients(f
, ln
, MPLS_INVALID_LABEL
);
943 /* LWd.3: check previously received label mapping */
944 if (me
&& (map
->label
== NO_LABEL
||
945 map
->label
== me
->map
.label
))
947 * LWd.4: remove record of previously received
950 lde_map_del(ln
, me
, 0);
955 /* Ordered Control: additional withdraw steps */
956 if (ldeconf
->flags
& F_LDPD_ORDERED_CONTROL
) {
958 * LWd.8: for each neighbor other that src of
961 RB_FOREACH(lnbr
, nbr_tree
, &lde_nbrs
) {
962 if (ln
->peerid
== lnbr
->peerid
)
965 /* LWd.9: check if previously sent a label
968 me
= (struct lde_map
*)fec_find(
969 &lnbr
->sent_map
, &fn
->fec
);
971 * LWd.10: does label sent to peer "map" to
974 if (me
&& lde_nbr_is_nexthop(fn
, lnbr
))
975 /* LWd.11: send label withdraw */
976 lde_send_labelwithdraw(lnbr
, fn
, NULL
,
984 lde_wildcard_apply(struct map
*wcard
, struct fec
*fec
, struct lde_map
*me
)
986 switch (wcard
->type
) {
987 case MAP_TYPE_WILDCARD
:
990 case MAP_TYPE_TYPED_WCARD
:
991 switch (wcard
->fec
.twcard
.type
) {
992 case MAP_TYPE_PREFIX
:
993 if (wcard
->fec
.twcard
.u
.prefix_af
== AF_INET
&&
994 fec
->type
!= FEC_TYPE_IPV4
)
996 if (wcard
->fec
.twcard
.u
.prefix_af
== AF_INET6
&&
997 fec
->type
!= FEC_TYPE_IPV6
)
1001 if (fec
->type
!= FEC_TYPE_PWID
)
1003 if (wcard
->fec
.twcard
.u
.pw_type
!= PW_TYPE_WILDCARD
&&
1004 wcard
->fec
.twcard
.u
.pw_type
!= fec
->u
.pwid
.type
)
1008 fatalx("lde_wildcard_apply: unexpected fec type");
1012 /* RFC4447 pw-id group wildcard */
1013 if (fec
->type
!= FEC_TYPE_PWID
)
1015 if (fec
->u
.pwid
.type
!= wcard
->fec
.pwid
.type
)
1017 if (me
== NULL
|| (me
->map
.fec
.pwid
.group_id
!=
1018 wcard
->fec
.pwid
.group_id
))
1022 fatalx("lde_wildcard_apply: unexpected fec type");
1026 /* gabage collector timer: timer to remove dead entries from the LIB */
1029 void lde_gc_timer(struct thread
*thread
)
1031 struct fec
*fec
, *safe
;
1032 struct fec_node
*fn
;
1035 RB_FOREACH_SAFE(fec
, fec_tree
, &ft
, safe
) {
1036 fn
= (struct fec_node
*) fec
;
1038 if (!LIST_EMPTY(&fn
->nexthops
) ||
1039 !RB_EMPTY(lde_map_head
, &fn
->downstream
) ||
1040 !RB_EMPTY(lde_map_head
, &fn
->upstream
))
1043 if (fn
->local_label
!= NO_LABEL
)
1044 lde_free_label(fn
->local_label
);
1046 fec_remove(&ft
, &fn
->fec
);
1052 log_debug("%s: %u entries removed", __func__
, count
);
1054 lde_gc_start_timer();
1058 lde_gc_start_timer(void)
1060 THREAD_OFF(gc_timer
);
1061 thread_add_timer(master
, lde_gc_timer
, NULL
, LDE_GC_INTERVAL
,
1066 lde_gc_stop_timer(void)
1068 THREAD_OFF(gc_timer
);