]> git.proxmox.com Git - mirror_frr.git/blob - ldpd/lde_lib.c
projects / mirror_frr.git / blob
? search:
summary | shortlog | log | commit | commitdiff | tree
blame | history | raw | HEAD
Merge pull request #12798 from donaldsharp/rib_match_multicast
[mirror_frr.git] / ldpd / lde_lib.c
1 // SPDX-License-Identifier: ISC
2 /* $OpenBSD$ */
3
4 /*
5 * Copyright (c) 2013, 2016 Renato Westphal <renato@openbsd.org>
6 * Copyright (c) 2009 Michele Marchetto <michele@openbsd.org>
7 */
8
9 #include <zebra.h>
10
11 #include "ldpd.h"
12 #include "ldpe.h"
13 #include "lde.h"
14 #include "log.h"
15 #include "rlfa.h"
16
17 #include "mpls.h"
18
19 static __inline int fec_compare(const struct fec *, const struct fec *);
20 static int lde_nbr_is_nexthop(struct fec_node *,
21 struct lde_nbr *);
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 *);
27
28 RB_GENERATE(fec_tree, fec, entry, fec_compare)
29
30 struct fec_tree ft = RB_INITIALIZER(&ft);
31 struct thread *gc_timer;
32
33 /* FEC tree functions */
34 void
35 fec_init(struct fec_tree *fh)
36 {
37 RB_INIT(fec_tree, fh);
38 }
39
40 static __inline int
41 fec_compare(const struct fec *a, const struct fec *b)
42 {
43 if (a->type < b->type)
44 return (-1);
45 if (a->type > b->type)
46 return (1);
47
48 switch (a->type) {
49 case FEC_TYPE_IPV4:
50 if (ntohl(a->u.ipv4.prefix.s_addr) <
51 ntohl(b->u.ipv4.prefix.s_addr))
52 return (-1);
53 if (ntohl(a->u.ipv4.prefix.s_addr) >
54 ntohl(b->u.ipv4.prefix.s_addr))
55 return (1);
56 if (a->u.ipv4.prefixlen < b->u.ipv4.prefixlen)
57 return (-1);
58 if (a->u.ipv4.prefixlen > b->u.ipv4.prefixlen)
59 return (1);
60 return (0);
61 case FEC_TYPE_IPV6:
62 if (memcmp(&a->u.ipv6.prefix, &b->u.ipv6.prefix,
63 sizeof(struct in6_addr)) < 0)
64 return (-1);
65 if (memcmp(&a->u.ipv6.prefix, &b->u.ipv6.prefix,
66 sizeof(struct in6_addr)) > 0)
67 return (1);
68 if (a->u.ipv6.prefixlen < b->u.ipv6.prefixlen)
69 return (-1);
70 if (a->u.ipv6.prefixlen > b->u.ipv6.prefixlen)
71 return (1);
72 return (0);
73 case FEC_TYPE_PWID:
74 if (a->u.pwid.type < b->u.pwid.type)
75 return (-1);
76 if (a->u.pwid.type > b->u.pwid.type)
77 return (1);
78 if (a->u.pwid.pwid < b->u.pwid.pwid)
79 return (-1);
80 if (a->u.pwid.pwid > b->u.pwid.pwid)
81 return (1);
82 if (ntohl(a->u.pwid.lsr_id.s_addr) <
83 ntohl(b->u.pwid.lsr_id.s_addr))
84 return (-1);
85 if (ntohl(a->u.pwid.lsr_id.s_addr) >
86 ntohl(b->u.pwid.lsr_id.s_addr))
87 return (1);
88 return (0);
89 }
90
91 return (-1);
92 }
93
94 struct fec *
95 fec_find(struct fec_tree *fh, struct fec *f)
96 {
97 return (RB_FIND(fec_tree, fh, f));
98 }
99
100 int
101 fec_insert(struct fec_tree *fh, struct fec *f)
102 {
103 if (RB_INSERT(fec_tree, fh, f) != NULL)
104 return (-1);
105 return (0);
106 }
107
108 int
109 fec_remove(struct fec_tree *fh, struct fec *f)
110 {
111 if (RB_REMOVE(fec_tree, fh, f) == NULL) {
112 log_warnx("%s failed for %s", __func__, log_fec(f));
113 return (-1);
114 }
115 return (0);
116 }
117
118 void
119 fec_clear(struct fec_tree *fh, void (*free_cb)(void *))
120 {
121 struct fec *f;
122
123 while (!RB_EMPTY(fec_tree, fh)) {
124 f = RB_ROOT(fec_tree, fh);
125
126 fec_remove(fh, f);
127 free_cb(f);
128 }
129 }
130
131 /* routing table functions */
132 static int
133 lde_nbr_is_nexthop(struct fec_node *fn, struct lde_nbr *ln)
134 {
135 struct fec_nh *fnh;
136
137 LIST_FOREACH(fnh, &fn->nexthops, entry)
138 if (lde_address_find(ln, fnh->af, &fnh->nexthop))
139 return (1);
140
141 return (0);
142 }
143
144 void
145 rt_dump(pid_t pid)
146 {
147 struct fec *f;
148 struct fec_node *fn;
149 struct lde_map *me;
150 static struct ctl_rt rtctl;
151
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))
156 continue;
157
158 memset(&rtctl, 0, sizeof(rtctl));
159 switch (fn->fec.type) {
160 case FEC_TYPE_IPV4:
161 rtctl.af = AF_INET;
162 rtctl.prefix.v4 = fn->fec.u.ipv4.prefix;
163 rtctl.prefixlen = fn->fec.u.ipv4.prefixlen;
164 break;
165 case FEC_TYPE_IPV6:
166 rtctl.af = AF_INET6;
167 rtctl.prefix.v6 = fn->fec.u.ipv6.prefix;
168 rtctl.prefixlen = fn->fec.u.ipv6.prefixlen;
169 break;
170 case FEC_TYPE_PWID:
171 continue;
172 }
173
174 rtctl.local_label = fn->local_label;
175 if (RB_EMPTY(lde_map_head, &fn->downstream)) {
176 rtctl.in_use = 0;
177 rtctl.nexthop.s_addr = INADDR_ANY;
178 rtctl.remote_label = NO_LABEL;
179 rtctl.no_downstream = 1;
180 }
181 lde_imsg_compose_ldpe(IMSG_CTL_SHOW_LIB_BEGIN, 0, pid, &rtctl,
182 sizeof(rtctl));
183
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));
188 }
189
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));
196 }
197 lde_imsg_compose_ldpe(IMSG_CTL_SHOW_LIB_END, 0, pid, &rtctl,
198 sizeof(rtctl));
199 }
200 }
201
202 void
203 fec_snap(struct lde_nbr *ln)
204 {
205 struct fec *f;
206 struct fec_node *fn;
207
208 RB_FOREACH(f, fec_tree, &ft) {
209 fn = (struct fec_node *)f;
210 if (fn->local_label == NO_LABEL)
211 continue;
212
213 lde_send_labelmapping(ln, fn, 0);
214 }
215
216 lde_imsg_compose_ldpe(IMSG_MAPPING_ADD_END, ln->peerid, 0, NULL, 0);
217 }
218
219 static void
220 fec_free(void *arg)
221 {
222 struct fec_node *fn = arg;
223 struct fec_nh *fnh;
224
225 while ((fnh = LIST_FIRST(&fn->nexthops))) {
226 fec_nh_del(fnh);
227 assert(fnh != LIST_FIRST(&fn->nexthops));
228 }
229 if (!RB_EMPTY(lde_map_head, &fn->downstream))
230 log_warnx("%s: fec %s downstream list not empty", __func__,
231 log_fec(&fn->fec));
232 if (!RB_EMPTY(lde_map_head, &fn->upstream))
233 log_warnx("%s: fec %s upstream list not empty", __func__,
234 log_fec(&fn->fec));
235
236 free(fn);
237 }
238
239 void
240 fec_tree_clear(void)
241 {
242 fec_clear(&ft, fec_free);
243 }
244
245 static struct fec_node *
246 fec_add(struct fec *fec)
247 {
248 struct fec_node *fn;
249
250 fn = calloc(1, sizeof(*fn));
251 if (fn == NULL)
252 fatal(__func__);
253
254 fn->fec = *fec;
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);
259
260 if (fec->type == FEC_TYPE_PWID)
261 fn->pw_remote_status = PW_FORWARDING;
262
263 if (fec_insert(&ft, &fn->fec))
264 log_warnx("failed to add %s to ft tree",
265 log_fec(&fn->fec));
266
267 return (fn);
268 }
269
270 struct fec_nh *
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)
273 {
274 struct fec_nh *fnh;
275
276 LIST_FOREACH(fnh, &fn->nexthops, entry)
277 if (fnh->af == af &&
278 ldp_addrcmp(af, &fnh->nexthop, nexthop) == 0 &&
279 fnh->ifindex == ifindex &&
280 fnh->route_type == route_type &&
281 fnh->route_instance == route_instance)
282 return (fnh);
283
284 return (NULL);
285 }
286
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)
290 {
291 struct fec_nh *fnh;
292
293 fnh = calloc(1, sizeof(*fnh));
294 if (fnh == NULL)
295 fatal(__func__);
296
297 fnh->af = af;
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);
304
305 return (fnh);
306 }
307
308 static void
309 fec_nh_del(struct fec_nh *fnh)
310 {
311 LIST_REMOVE(fnh, entry);
312 free(fnh);
313 }
314
315 void
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)
319 {
320 struct fec_node *fn;
321 struct fec_nh *fnh;
322 struct iface *iface;
323
324 fn = (struct fec_node *)fec_find(&ft, fec);
325 if (fn == NULL)
326 fn = fec_add(fec);
327 if (data)
328 fn->data = data;
329
330 fnh = fec_nh_find(fn, af, nexthop, ifindex, route_type, route_instance);
331 if (fnh == NULL) {
332 fnh = fec_nh_add(fn, af, nexthop, ifindex, route_type,
333 route_instance);
334 /*
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
339 */
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;
344 }
345
346 fnh->flags |= F_FEC_NH_NEW;
347 if (connected)
348 fnh->flags |= F_FEC_NH_CONNECTED;
349 }
350
351 void
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)
354 {
355 struct fec_node *fn;
356 struct fec_nh *fnh;
357
358 fn = (struct fec_node *)fec_find(&ft, fec);
359 if (fn == NULL)
360 /* route lost */
361 return;
362 fnh = fec_nh_find(fn, af, nexthop, ifindex, route_type, route_instance);
363 if (fnh == NULL)
364 /* route lost */
365 return;
366
367 lde_send_delete_klabel(fn, fnh);
368 fec_nh_del(fnh);
369 }
370
371 /*
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.
376 */
377 void
378 lde_kernel_update(struct fec *fec)
379 {
380 struct fec_node *fn;
381 struct fec_nh *fnh, *safe;
382 struct lde_nbr *ln;
383 struct lde_map *me;
384 struct iface *iface;
385
386 fn = (struct fec_node *)fec_find(&ft, fec);
387 if (fn == NULL)
388 return;
389
390 LIST_FOREACH_SAFE(fnh, &fn->nexthops, entry, safe) {
391 if (fnh->flags & F_FEC_NH_NEW) {
392 fnh->flags &= ~F_FEC_NH_NEW;
393 /*
394 * if LDP configured on interface or a static route
395 * clear flag else treat fec as a connected route
396 */
397 if (ldeconf->flags & F_LDPD_ENABLED) {
398 iface = if_lookup(ldeconf,fnh->ifindex);
399 if (fnh->flags & F_FEC_NH_CONNECTED ||
400 iface ||
401 fnh->route_type == ZEBRA_ROUTE_STATIC)
402 fnh->flags &=~F_FEC_NH_NO_LDP;
403 else
404 fnh->flags |= F_FEC_NH_NO_LDP;
405 } else
406 fnh->flags |= F_FEC_NH_NO_LDP;
407 } else {
408 lde_send_delete_klabel(fn, fnh);
409 fec_nh_del(fnh);
410 }
411 }
412
413 if (LIST_EMPTY(&fn->nexthops)) {
414 RB_FOREACH(ln, nbr_tree, &lde_nbrs)
415 lde_send_labelwithdraw(ln, fn, NULL, NULL);
416 fn->data = NULL;
417
418 /*
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
424 * is stabilized.
425 */
426 lde_gc_start_timer();
427 } else {
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);
433 }
434
435 /* if no label created yet then don't try to program labeled route */
436 if (fn->local_label == NO_LABEL)
437 return;
438
439 LIST_FOREACH(fnh, &fn->nexthops, entry) {
440 lde_send_change_klabel(fn, fnh);
441
442 switch (fn->fec.type) {
443 case FEC_TYPE_IPV4:
444 case FEC_TYPE_IPV6:
445 ln = lde_nbr_find_by_addr(fnh->af, &fnh->nexthop);
446 break;
447 case FEC_TYPE_PWID:
448 ln = lde_nbr_find_by_lsrid(fn->fec.u.pwid.lsr_id);
449 break;
450 default:
451 ln = NULL;
452 break;
453 }
454
455 if (ln) {
456 /* FEC.2 */
457 me = (struct lde_map *)fec_find(&ln->recv_map, &fn->fec);
458 if (me)
459 /* FEC.5 */
460 lde_check_mapping(&me->map, ln, 0);
461 }
462 }
463 }
464
465 void
466 lde_check_mapping(struct map *map, struct lde_nbr *ln, int rcvd_label_mapping)
467 {
468 struct fec fec;
469 struct fec_node *fn;
470 struct fec_nh *fnh;
471 struct lde_req *lre;
472 struct lde_map *me;
473 struct l2vpn_pw *pw;
474 bool send_map = false;
475
476 lde_map2fec(map, ln->id, &fec);
477
478 switch (fec.type) {
479 case FEC_TYPE_IPV4:
480 if (lde_acl_check(ldeconf->ipv4.acl_label_accept_from,
481 AF_INET, (union ldpd_addr *)&ln->id, 32) != FILTER_PERMIT)
482 return;
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)
486 return;
487 break;
488 case FEC_TYPE_IPV6:
489 if (lde_acl_check(ldeconf->ipv6.acl_label_accept_from,
490 AF_INET, (union ldpd_addr *)&ln->id, 32) != FILTER_PERMIT)
491 return;
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)
495 return;
496 break;
497 case FEC_TYPE_PWID:
498 break;
499 }
500
501 fn = (struct fec_node *)fec_find(&ft, &fec);
502 if (fn == NULL)
503 fn = fec_add(&fec);
504
505 /* LMp.1: first check if we have a pending request running */
506 lre = (struct lde_req *)fec_find(&ln->sent_req, &fn->fec);
507 if (lre)
508 /* LMp.2: delete record of outstanding label request */
509 lde_req_del(ln, lre, 1);
510
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;
515
516 return;
517 }
518
519 /*
520 * LMp.3 - LMp.8: loop detection - unnecessary for frame-mode
521 * mpls networks.
522 */
523
524 /* LMp.9 */
525 me = (struct lde_map *)fec_find(&ln->recv_map, &fn->fec);
526 if (me) {
527 /* LMp.10 */
528 if (me->map.label != map->label && lre == NULL) {
529 /* LMp.10a */
530 lde_send_labelrelease(ln, fn, NULL, me->map.label);
531
532 /*
533 * Can not use lde_nbr_find_by_addr() because there's
534 * the possibility of multipath.
535 */
536 LIST_FOREACH(fnh, &fn->nexthops, entry) {
537 if (lde_address_find(ln, fnh->af,
538 &fnh->nexthop) == NULL)
539 continue;
540
541 lde_send_delete_klabel(fn, fnh);
542 fnh->remote_label = NO_LABEL;
543 }
544 }
545 }
546
547 /*
548 * LMp.11 - 12: consider multiple nexthops in order to
549 * support multipath
550 */
551 LIST_FOREACH(fnh, &fn->nexthops, entry) {
552 /* LMp.15: install FEC in FIB */
553 switch (fec.type) {
554 case FEC_TYPE_IPV4:
555 case FEC_TYPE_IPV6:
556 if (!lde_address_find(ln, fnh->af, &fnh->nexthop))
557 continue;
558
559 /*
560 * Ordered Control: labelmap msg received from
561 * NH so clear flag and send labelmap msg to
562 * peer
563 */
564 if (ldeconf->flags & F_LDPD_ORDERED_CONTROL) {
565 send_map = true;
566 fnh->flags &= ~F_FEC_NH_DEFER;
567 }
568 fnh->remote_label = map->label;
569 if (fn->local_label != NO_LABEL)
570 lde_send_change_klabel(fn, fnh);
571 break;
572 case FEC_TYPE_PWID:
573 pw = (struct l2vpn_pw *) fn->data;
574 if (pw == NULL)
575 continue;
576
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;
583 }
584 else
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);
589 break;
590 default:
591 break;
592 }
593 }
594
595 /* Update RLFA clients. */
596 lde_rlfa_update_clients(&fec, ln, map->label);
597
598 /* LMp.13 & LMp.16: Record the mapping from this peer */
599 if (me == NULL)
600 me = lde_map_add(ln, fn, 0);
601 me->map = *map;
602
603 /*
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
606 * merging capable.
607 */
608
609 /*
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
613 */
614 if (send_map && fn->local_label != NO_LABEL)
615 RB_FOREACH(ln, nbr_tree, &lde_nbrs)
616 lde_send_labelmapping(ln, fn, 1);
617 }
618
619 void
620 lde_check_request(struct map *map, struct lde_nbr *ln)
621 {
622 struct fec fec;
623 struct lde_req *lre;
624 struct fec_node *fn;
625 struct fec_nh *fnh;
626
627 /* wildcard label request */
628 if (map->type == MAP_TYPE_TYPED_WCARD) {
629 lde_check_request_wcard(map, ln);
630 return;
631 }
632
633 /* LRq.1: skip loop detection (not necessary) */
634
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));
642 return;
643 }
644
645 /* LRq.3: is MsgSource the next hop? */
646 LIST_FOREACH(fnh, &fn->nexthops, entry) {
647 switch (fec.type) {
648 case FEC_TYPE_IPV4:
649 case FEC_TYPE_IPV6:
650 if (!lde_address_find(ln, fnh->af, &fnh->nexthop))
651 continue;
652
653 /* LRq.4: send Loop Detected notification */
654 lde_send_notification(ln, S_LOOP_DETECTED, map->msg_id,
655 htons(MSG_TYPE_LABELREQUEST));
656 return;
657 case FEC_TYPE_PWID:
658 break;
659 }
660 }
661
662 /* LRq.6: first check if we have a pending request running */
663 lre = (struct lde_req *)fec_find(&ln->recv_req, &fn->fec);
664 if (lre != NULL)
665 /* LRq.7: duplicate request */
666 return;
667
668 /* LRq.8: record label request */
669 lre = lde_req_add(ln, &fn->fec, 0);
670 if (lre != NULL)
671 lre->msg_id = ntohl(map->msg_id);
672
673 /* LRq.9: perform LSR label distribution */
674 lde_send_labelmapping(ln, fn, 1);
675
676 /*
677 * LRq.10: do nothing (Request Never) since we use liberal
678 * label retention.
679 * LRq.11 - 12 are unnecessary since we are merging capable.
680 */
681 }
682
683 void
684 lde_check_request_wcard(struct map *map, struct lde_nbr *ln)
685 {
686 struct fec *f;
687 struct fec_node *fn;
688 struct lde_req *lre;
689
690 RB_FOREACH(f, fec_tree, &ft) {
691 fn = (struct fec_node *)f;
692
693 /* only a typed wildcard is possible here */
694 if (lde_wildcard_apply(map, &fn->fec, NULL) == 0)
695 continue;
696
697 /* LRq.2: is there a next hop for fec? */
698 if (LIST_EMPTY(&fn->nexthops))
699 continue;
700
701 /* LRq.6: first check if we have a pending request running */
702 lre = (struct lde_req *)fec_find(&ln->recv_req, &fn->fec);
703 if (lre != NULL)
704 /* LRq.7: duplicate request */
705 continue;
706
707 /* LRq.8: record label request */
708 lre = lde_req_add(ln, &fn->fec, 0);
709 if (lre != NULL)
710 lre->msg_id = ntohl(map->msg_id);
711
712 /* LRq.9: perform LSR label distribution */
713 lde_send_labelmapping(ln, fn, 1);
714 }
715 }
716
717 void
718 lde_check_release(struct map *map, struct lde_nbr *ln)
719 {
720 struct fec fec;
721 struct fec_node *fn;
722 struct lde_wdraw *lw;
723 struct lde_map *me;
724 struct fec *pending_map;
725
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);
731 return;
732 }
733
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? */
737 if (fn == NULL)
738 return;
739
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);
744
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);
750
751 /* send pending label mapping if any */
752 pending_map = fec_find(&ln->sent_map_pending, &fn->fec);
753 if (pending_map) {
754 lde_send_labelmapping(ln, fn, 1);
755 lde_map_pending_del(ln, pending_map);
756 }
757 }
758
759 /*
760 * LRl.11 - 13 are unnecessary since we remove the label from
761 * forwarding/switching as soon as the FEC is unreachable.
762 */
763 }
764
765 void
766 lde_check_release_wcard(struct map *map, struct lde_nbr *ln)
767 {
768 struct fec *f;
769 struct fec_node *fn;
770 struct lde_wdraw *lw;
771 struct lde_map *me;
772 struct fec *pending_map;
773
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);
777
778 /* LRl.1: does FEC match a known FEC? */
779 if (lde_wildcard_apply(map, &fn->fec, me) == 0)
780 continue;
781
782 /* LRl.6: check sent map list and remove it if available */
783 if (me &&
784 (map->label == NO_LABEL || map->label == me->map.label))
785 lde_map_del(ln, me, 1);
786
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);
792
793 /* send pending label mapping if any */
794 pending_map = fec_find(&ln->sent_map_pending, &fn->fec);
795 if (pending_map) {
796 lde_send_labelmapping(ln, fn, 1);
797 lde_map_pending_del(ln, pending_map);
798 }
799 }
800
801 /*
802 * LRl.11 - 13 are unnecessary since we remove the label from
803 * forwarding/switching as soon as the FEC is unreachable.
804 */
805 }
806 }
807
808 void
809 lde_check_withdraw(struct map *map, struct lde_nbr *ln)
810 {
811 struct fec fec;
812 struct fec_node *fn;
813 struct fec_nh *fnh;
814 struct lde_map *me;
815 struct l2vpn_pw *pw;
816 struct lde_nbr *lnbr;
817
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);
823 return;
824 }
825
826 lde_map2fec(map, ln->id, &fec);
827 fn = (struct fec_node *)fec_find(&ft, &fec);
828 if (fn == NULL)
829 fn = fec_add(&fec);
830
831 /* LWd.1: remove label from forwarding/switching use */
832 LIST_FOREACH(fnh, &fn->nexthops, entry) {
833 switch (fec.type) {
834 case FEC_TYPE_IPV4:
835 case FEC_TYPE_IPV6:
836 if (!lde_address_find(ln, fnh->af, &fnh->nexthop))
837 continue;
838 break;
839 case FEC_TYPE_PWID:
840 pw = (struct l2vpn_pw *) fn->data;
841 if (pw == NULL)
842 continue;
843 pw->remote_status = PW_NOT_FORWARDING;
844 break;
845 default:
846 break;
847 }
848 if (map->label != NO_LABEL && map->label != fnh->remote_label)
849 continue;
850
851 lde_send_delete_klabel(fn, fnh);
852 fnh->remote_label = NO_LABEL;
853 }
854
855 /* Update RLFA clients. */
856 lde_rlfa_update_clients(&fec, ln, MPLS_INVALID_LABEL);
857
858 /* LWd.2: send label release */
859 lde_send_labelrelease(ln, fn, NULL, map->label);
860
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);
866 else
867 /* LWd.13 done */
868 return;
869
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)
875 continue;
876
877 /* LWd.9: check if previously sent a label mapping */
878 me = (struct lde_map *)fec_find(&lnbr->sent_map,
879 &fn->fec);
880
881 /*
882 * LWd.10: does label sent to peer "map" to withdraw
883 * label
884 */
885 if (me && lde_nbr_is_nexthop(fn, lnbr))
886 /* LWd.11: send label withdraw */
887 lde_send_labelwithdraw(lnbr, fn, NULL, NULL);
888 }
889 }
890
891 }
892
893 void
894 lde_check_withdraw_wcard(struct map *map, struct lde_nbr *ln)
895 {
896 struct fec *f;
897 struct fec_node *fn;
898 struct fec_nh *fnh;
899 struct lde_map *me;
900 struct l2vpn_pw *pw;
901 struct lde_nbr *lnbr;
902
903 /* LWd.2: send label release */
904 lde_send_labelrelease(ln, NULL, map, map->label);
905
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);
909
910 if (lde_wildcard_apply(map, &fn->fec, me) == 0)
911 continue;
912
913 /* LWd.1: remove label from forwarding/switching use */
914 LIST_FOREACH(fnh, &fn->nexthops, entry) {
915 switch (f->type) {
916 case FEC_TYPE_IPV4:
917 case FEC_TYPE_IPV6:
918 if (!lde_address_find(ln, fnh->af,
919 &fnh->nexthop))
920 continue;
921 break;
922 case FEC_TYPE_PWID:
923 if (f->u.pwid.lsr_id.s_addr != ln->id.s_addr)
924 continue;
925 pw = (struct l2vpn_pw *) fn->data;
926 if (pw)
927 pw->remote_status = PW_NOT_FORWARDING;
928 break;
929 default:
930 break;
931 }
932 if (map->label != NO_LABEL && map->label !=
933 fnh->remote_label)
934 continue;
935
936 lde_send_delete_klabel(fn, fnh);
937 fnh->remote_label = NO_LABEL;
938 }
939
940 /* Update RLFA clients. */
941 lde_rlfa_update_clients(f, ln, MPLS_INVALID_LABEL);
942
943 /* LWd.3: check previously received label mapping */
944 if (me && (map->label == NO_LABEL ||
945 map->label == me->map.label))
946 /*
947 * LWd.4: remove record of previously received
948 * label mapping
949 */
950 lde_map_del(ln, me, 0);
951 else
952 /* LWd.13 done */
953 continue;
954
955 /* Ordered Control: additional withdraw steps */
956 if (ldeconf->flags & F_LDPD_ORDERED_CONTROL) {
957 /*
958 * LWd.8: for each neighbor other that src of
959 * withdraw msg
960 */
961 RB_FOREACH(lnbr, nbr_tree, &lde_nbrs) {
962 if (ln->peerid == lnbr->peerid)
963 continue;
964
965 /* LWd.9: check if previously sent a label
966 * mapping
967 */
968 me = (struct lde_map *)fec_find(
969 &lnbr->sent_map, &fn->fec);
970 /*
971 * LWd.10: does label sent to peer "map" to
972 * withdraw label
973 */
974 if (me && lde_nbr_is_nexthop(fn, lnbr))
975 /* LWd.11: send label withdraw */
976 lde_send_labelwithdraw(lnbr, fn, NULL,
977 NULL);
978 }
979 }
980 }
981 }
982
983 int
984 lde_wildcard_apply(struct map *wcard, struct fec *fec, struct lde_map *me)
985 {
986 switch (wcard->type) {
987 case MAP_TYPE_WILDCARD:
988 /* full wildcard */
989 return (1);
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)
995 return (0);
996 if (wcard->fec.twcard.u.prefix_af == AF_INET6 &&
997 fec->type != FEC_TYPE_IPV6)
998 return (0);
999 return (1);
1000 case MAP_TYPE_PWID:
1001 if (fec->type != FEC_TYPE_PWID)
1002 return (0);
1003 if (wcard->fec.twcard.u.pw_type != PW_TYPE_WILDCARD &&
1004 wcard->fec.twcard.u.pw_type != fec->u.pwid.type)
1005 return (0);
1006 return (1);
1007 default:
1008 fatalx("lde_wildcard_apply: unexpected fec type");
1009 }
1010 break;
1011 case MAP_TYPE_PWID:
1012 /* RFC4447 pw-id group wildcard */
1013 if (fec->type != FEC_TYPE_PWID)
1014 return (0);
1015 if (fec->u.pwid.type != wcard->fec.pwid.type)
1016 return (0);
1017 if (me == NULL || (me->map.fec.pwid.group_id !=
1018 wcard->fec.pwid.group_id))
1019 return (0);
1020 return (1);
1021 default:
1022 fatalx("lde_wildcard_apply: unexpected fec type");
1023 }
1024 }
1025
1026 /* gabage collector timer: timer to remove dead entries from the LIB */
1027
1028 /* ARGSUSED */
1029 void lde_gc_timer(struct thread *thread)
1030 {
1031 struct fec *fec, *safe;
1032 struct fec_node *fn;
1033 int count = 0;
1034
1035 RB_FOREACH_SAFE(fec, fec_tree, &ft, safe) {
1036 fn = (struct fec_node *) fec;
1037
1038 if (!LIST_EMPTY(&fn->nexthops) ||
1039 !RB_EMPTY(lde_map_head, &fn->downstream) ||
1040 !RB_EMPTY(lde_map_head, &fn->upstream))
1041 continue;
1042
1043 if (fn->local_label != NO_LABEL)
1044 lde_free_label(fn->local_label);
1045
1046 fec_remove(&ft, &fn->fec);
1047 free(fn);
1048 count++;
1049 }
1050
1051 if (count > 0)
1052 log_debug("%s: %u entries removed", __func__, count);
1053
1054 lde_gc_start_timer();
1055 }
1056
1057 void
1058 lde_gc_start_timer(void)
1059 {
1060 THREAD_OFF(gc_timer);
1061 thread_add_timer(master, lde_gc_timer, NULL, LDE_GC_INTERVAL,
1062 &gc_timer);
1063 }
1064
1065 void
1066 lde_gc_stop_timer(void)
1067 {
1068 THREAD_OFF(gc_timer);
1069 }
FRRouting mirror