]> 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 #6071 from ton31337/feature/rfc6286
[mirror_frr.git] / ldpd / lde_lib.c
1 /* $OpenBSD$ */
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 <zebra.h>
21
22 #include "ldpd.h"
23 #include "ldpe.h"
24 #include "lde.h"
25 #include "log.h"
26
27 #include "mpls.h"
28
29 static __inline int fec_compare(const struct fec *, const struct fec *);
30 static int lde_nbr_is_nexthop(struct fec_node *,
31 struct lde_nbr *);
32 static void fec_free(void *);
33 static struct fec_node *fec_add(struct fec *fec);
34 static struct fec_nh *fec_nh_add(struct fec_node *, int, union ldpd_addr *,
35 ifindex_t, uint8_t, unsigned short);
36 static void fec_nh_del(struct fec_nh *);
37
38 RB_GENERATE(fec_tree, fec, entry, fec_compare)
39
40 struct fec_tree ft = RB_INITIALIZER(&ft);
41 struct thread *gc_timer;
42
43 /* FEC tree functions */
44 void
45 fec_init(struct fec_tree *fh)
46 {
47 RB_INIT(fec_tree, fh);
48 }
49
50 static __inline int
51 fec_compare(const struct fec *a, const struct fec *b)
52 {
53 if (a->type < b->type)
54 return (-1);
55 if (a->type > b->type)
56 return (1);
57
58 switch (a->type) {
59 case FEC_TYPE_IPV4:
60 if (ntohl(a->u.ipv4.prefix.s_addr) <
61 ntohl(b->u.ipv4.prefix.s_addr))
62 return (-1);
63 if (ntohl(a->u.ipv4.prefix.s_addr) >
64 ntohl(b->u.ipv4.prefix.s_addr))
65 return (1);
66 if (a->u.ipv4.prefixlen < b->u.ipv4.prefixlen)
67 return (-1);
68 if (a->u.ipv4.prefixlen > b->u.ipv4.prefixlen)
69 return (1);
70 return (0);
71 case FEC_TYPE_IPV6:
72 if (memcmp(&a->u.ipv6.prefix, &b->u.ipv6.prefix,
73 sizeof(struct in6_addr)) < 0)
74 return (-1);
75 if (memcmp(&a->u.ipv6.prefix, &b->u.ipv6.prefix,
76 sizeof(struct in6_addr)) > 0)
77 return (1);
78 if (a->u.ipv6.prefixlen < b->u.ipv6.prefixlen)
79 return (-1);
80 if (a->u.ipv6.prefixlen > b->u.ipv6.prefixlen)
81 return (1);
82 return (0);
83 case FEC_TYPE_PWID:
84 if (a->u.pwid.type < b->u.pwid.type)
85 return (-1);
86 if (a->u.pwid.type > b->u.pwid.type)
87 return (1);
88 if (a->u.pwid.pwid < b->u.pwid.pwid)
89 return (-1);
90 if (a->u.pwid.pwid > b->u.pwid.pwid)
91 return (1);
92 if (ntohl(a->u.pwid.lsr_id.s_addr) <
93 ntohl(b->u.pwid.lsr_id.s_addr))
94 return (-1);
95 if (ntohl(a->u.pwid.lsr_id.s_addr) >
96 ntohl(b->u.pwid.lsr_id.s_addr))
97 return (1);
98 return (0);
99 }
100
101 return (-1);
102 }
103
104 struct fec *
105 fec_find(struct fec_tree *fh, struct fec *f)
106 {
107 return (RB_FIND(fec_tree, fh, f));
108 }
109
110 int
111 fec_insert(struct fec_tree *fh, struct fec *f)
112 {
113 if (RB_INSERT(fec_tree, fh, f) != NULL)
114 return (-1);
115 return (0);
116 }
117
118 int
119 fec_remove(struct fec_tree *fh, struct fec *f)
120 {
121 if (RB_REMOVE(fec_tree, fh, f) == NULL) {
122 log_warnx("%s failed for %s", __func__, log_fec(f));
123 return (-1);
124 }
125 return (0);
126 }
127
128 void
129 fec_clear(struct fec_tree *fh, void (*free_cb)(void *))
130 {
131 struct fec *f;
132
133 while (!RB_EMPTY(fec_tree, fh)) {
134 f = RB_ROOT(fec_tree, fh);
135
136 fec_remove(fh, f);
137 free_cb(f);
138 }
139 }
140
141 /* routing table functions */
142 static int
143 lde_nbr_is_nexthop(struct fec_node *fn, struct lde_nbr *ln)
144 {
145 struct fec_nh *fnh;
146
147 LIST_FOREACH(fnh, &fn->nexthops, entry)
148 if (lde_address_find(ln, fnh->af, &fnh->nexthop))
149 return (1);
150
151 return (0);
152 }
153
154 void
155 rt_dump(pid_t pid)
156 {
157 struct fec *f;
158 struct fec_node *fn;
159 struct lde_map *me;
160 static struct ctl_rt rtctl;
161
162 RB_FOREACH(f, fec_tree, &ft) {
163 fn = (struct fec_node *)f;
164 if (fn->local_label == NO_LABEL &&
165 RB_EMPTY(lde_map_head, &fn->downstream))
166 continue;
167
168 memset(&rtctl, 0, sizeof(rtctl));
169 switch (fn->fec.type) {
170 case FEC_TYPE_IPV4:
171 rtctl.af = AF_INET;
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_INET6;
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 if (RB_EMPTY(lde_map_head, &fn->downstream)) {
186 rtctl.in_use = 0;
187 rtctl.nexthop.s_addr = INADDR_ANY;
188 rtctl.remote_label = NO_LABEL;
189 rtctl.no_downstream = 1;
190 }
191 lde_imsg_compose_ldpe(IMSG_CTL_SHOW_LIB_BEGIN, 0, pid, &rtctl,
192 sizeof(rtctl));
193
194 RB_FOREACH(me, lde_map_head, &fn->upstream) {
195 rtctl.nexthop = me->nexthop->id;
196 lde_imsg_compose_ldpe(IMSG_CTL_SHOW_LIB_SENT, 0, pid,
197 &rtctl, sizeof(rtctl));
198 }
199
200 RB_FOREACH(me, lde_map_head, &fn->downstream) {
201 rtctl.in_use = lde_nbr_is_nexthop(fn, me->nexthop);
202 rtctl.nexthop = me->nexthop->id;
203 rtctl.remote_label = me->map.label;
204 lde_imsg_compose_ldpe(IMSG_CTL_SHOW_LIB_RCVD, 0, pid,
205 &rtctl, sizeof(rtctl));
206 }
207 lde_imsg_compose_ldpe(IMSG_CTL_SHOW_LIB_END, 0, pid, &rtctl,
208 sizeof(rtctl));
209 }
210 }
211
212 void
213 fec_snap(struct lde_nbr *ln)
214 {
215 struct fec *f;
216 struct fec_node *fn;
217
218 RB_FOREACH(f, fec_tree, &ft) {
219 fn = (struct fec_node *)f;
220 if (fn->local_label == NO_LABEL)
221 continue;
222
223 lde_send_labelmapping(ln, fn, 0);
224 }
225
226 lde_imsg_compose_ldpe(IMSG_MAPPING_ADD_END, ln->peerid, 0, NULL, 0);
227 }
228
229 static void
230 fec_free(void *arg)
231 {
232 struct fec_node *fn = arg;
233 struct fec_nh *fnh;
234
235 while ((fnh = LIST_FIRST(&fn->nexthops))) {
236 fec_nh_del(fnh);
237 assert(fnh != LIST_FIRST(&fn->nexthops));
238 }
239 if (!RB_EMPTY(lde_map_head, &fn->downstream))
240 log_warnx("%s: fec %s downstream list not empty", __func__,
241 log_fec(&fn->fec));
242 if (!RB_EMPTY(lde_map_head, &fn->upstream))
243 log_warnx("%s: fec %s upstream list not empty", __func__,
244 log_fec(&fn->fec));
245
246 free(fn);
247 }
248
249 void
250 fec_tree_clear(void)
251 {
252 fec_clear(&ft, fec_free);
253 }
254
255 static struct fec_node *
256 fec_add(struct fec *fec)
257 {
258 struct fec_node *fn;
259
260 fn = calloc(1, sizeof(*fn));
261 if (fn == NULL)
262 fatal(__func__);
263
264 fn->fec = *fec;
265 fn->local_label = NO_LABEL;
266 RB_INIT(lde_map_head, &fn->upstream);
267 RB_INIT(lde_map_head, &fn->downstream);
268 LIST_INIT(&fn->nexthops);
269
270 if (fec_insert(&ft, &fn->fec))
271 log_warnx("failed to add %s to ft tree",
272 log_fec(&fn->fec));
273
274 return (fn);
275 }
276
277 struct fec_nh *
278 fec_nh_find(struct fec_node *fn, int af, union ldpd_addr *nexthop,
279 ifindex_t ifindex, uint8_t route_type, unsigned short route_instance)
280 {
281 struct fec_nh *fnh;
282
283 LIST_FOREACH(fnh, &fn->nexthops, entry)
284 if (fnh->af == af &&
285 ldp_addrcmp(af, &fnh->nexthop, nexthop) == 0 &&
286 fnh->ifindex == ifindex &&
287 fnh->route_type == route_type &&
288 fnh->route_instance == route_instance)
289 return (fnh);
290
291 return (NULL);
292 }
293
294 static struct fec_nh *
295 fec_nh_add(struct fec_node *fn, int af, union ldpd_addr *nexthop,
296 ifindex_t ifindex, uint8_t route_type, unsigned short route_instance)
297 {
298 struct fec_nh *fnh;
299
300 fnh = calloc(1, sizeof(*fnh));
301 if (fnh == NULL)
302 fatal(__func__);
303
304 fnh->af = af;
305 fnh->nexthop = *nexthop;
306 fnh->ifindex = ifindex;
307 fnh->remote_label = NO_LABEL;
308 fnh->route_type = route_type;
309 fnh->route_instance = route_instance;
310 LIST_INSERT_HEAD(&fn->nexthops, fnh, entry);
311
312 return (fnh);
313 }
314
315 static void
316 fec_nh_del(struct fec_nh *fnh)
317 {
318 LIST_REMOVE(fnh, entry);
319 free(fnh);
320 }
321
322 void
323 lde_kernel_insert(struct fec *fec, int af, union ldpd_addr *nexthop,
324 ifindex_t ifindex, uint8_t route_type, unsigned short route_instance,
325 int connected, void *data)
326 {
327 struct fec_node *fn;
328 struct fec_nh *fnh;
329 struct iface *iface;
330
331 fn = (struct fec_node *)fec_find(&ft, fec);
332 if (fn == NULL)
333 fn = fec_add(fec);
334 if (data)
335 fn->data = data;
336
337 fnh = fec_nh_find(fn, af, nexthop, ifindex, route_type, route_instance);
338 if (fnh == NULL) {
339 fnh = fec_nh_add(fn, af, nexthop, ifindex, route_type,
340 route_instance);
341 /*
342 * Ordered Control: if not a connected route and not a route
343 * learned over an interface not running LDP and not a PW
344 * then mark to wait until we receive labelmap msg before
345 * installing in kernel and sending to peer
346 */
347 iface = if_lookup(ldeconf, ifindex);
348 if ((ldeconf->flags & F_LDPD_ORDERED_CONTROL) &&
349 !connected && iface != NULL && fec->type != FEC_TYPE_PWID)
350 fnh->flags |= F_FEC_NH_DEFER;
351 }
352
353 fnh->flags |= F_FEC_NH_NEW;
354 if (connected)
355 fnh->flags |= F_FEC_NH_CONNECTED;
356 }
357
358 void
359 lde_kernel_remove(struct fec *fec, int af, union ldpd_addr *nexthop,
360 ifindex_t ifindex, uint8_t route_type, unsigned short route_instance)
361 {
362 struct fec_node *fn;
363 struct fec_nh *fnh;
364
365 fn = (struct fec_node *)fec_find(&ft, fec);
366 if (fn == NULL)
367 /* route lost */
368 return;
369 fnh = fec_nh_find(fn, af, nexthop, ifindex, route_type, route_instance);
370 if (fnh == NULL)
371 /* route lost */
372 return;
373
374 lde_send_delete_klabel(fn, fnh);
375 fec_nh_del(fnh);
376 }
377
378 /*
379 * Whenever a route is changed, zebra advertises its new version without
380 * withdrawing the old one. So, after processing a ZEBRA_REDISTRIBUTE_IPV[46]_ADD
381 * message, we need to check for nexthops that were removed and, for each of
382 * them (if any), withdraw the associated labels from zebra.
383 */
384 void
385 lde_kernel_update(struct fec *fec)
386 {
387 struct fec_node *fn;
388 struct fec_nh *fnh, *safe;
389 struct lde_nbr *ln;
390 struct lde_map *me;
391 struct iface *iface;
392
393 fn = (struct fec_node *)fec_find(&ft, fec);
394 if (fn == NULL)
395 return;
396
397 LIST_FOREACH_SAFE(fnh, &fn->nexthops, entry, safe) {
398 if (fnh->flags & F_FEC_NH_NEW) {
399 fnh->flags &= ~F_FEC_NH_NEW;
400 /*
401 * if LDP configured on interface or a static route
402 * clear flag else treat fec as a connected route
403 */
404 iface = if_lookup(ldeconf,fnh->ifindex);
405 if (iface || fnh->route_type == ZEBRA_ROUTE_STATIC)
406 fnh->flags &=~F_FEC_NH_NO_LDP;
407 else
408 fnh->flags |= F_FEC_NH_NO_LDP;
409 } else {
410 lde_send_delete_klabel(fn, fnh);
411 fec_nh_del(fnh);
412 }
413 }
414
415 if (LIST_EMPTY(&fn->nexthops)) {
416 RB_FOREACH(ln, nbr_tree, &lde_nbrs)
417 lde_send_labelwithdraw(ln, fn, NULL, NULL);
418 fn->data = NULL;
419
420 /*
421 * Do not deallocate the local label now, do that only in the
422 * LIB garbage collector. This will prevent ldpd from changing
423 * the input label of some prefixes too often when running on
424 * an unstable network. Also, restart the garbage collector
425 * timer so that labels are deallocated only when the network
426 * is stabilized.
427 */
428 lde_gc_start_timer();
429 } else {
430 fn->local_label = lde_update_label(fn);
431 if (fn->local_label != NO_LABEL)
432 /* FEC.1: perform lsr label distribution procedure */
433 RB_FOREACH(ln, nbr_tree, &lde_nbrs)
434 lde_send_labelmapping(ln, fn, 1);
435 }
436
437 LIST_FOREACH(fnh, &fn->nexthops, entry) {
438 lde_send_change_klabel(fn, fnh);
439
440 switch (fn->fec.type) {
441 case FEC_TYPE_IPV4:
442 case FEC_TYPE_IPV6:
443 ln = lde_nbr_find_by_addr(fnh->af, &fnh->nexthop);
444 break;
445 case FEC_TYPE_PWID:
446 ln = lde_nbr_find_by_lsrid(fn->fec.u.pwid.lsr_id);
447 break;
448 default:
449 ln = NULL;
450 break;
451 }
452
453 if (ln) {
454 /* FEC.2 */
455 me = (struct lde_map *)fec_find(&ln->recv_map, &fn->fec);
456 if (me)
457 /* FEC.5 */
458 lde_check_mapping(&me->map, ln);
459 }
460 }
461 }
462
463 void
464 lde_check_mapping(struct map *map, struct lde_nbr *ln)
465 {
466 struct fec fec;
467 struct fec_node *fn;
468 struct fec_nh *fnh;
469 struct lde_req *lre;
470 struct lde_map *me;
471 struct l2vpn_pw *pw;
472 bool send_map = false;
473
474 lde_map2fec(map, ln->id, &fec);
475
476 switch (fec.type) {
477 case FEC_TYPE_IPV4:
478 if (lde_acl_check(ldeconf->ipv4.acl_label_accept_from,
479 AF_INET, (union ldpd_addr *)&ln->id, 32) != FILTER_PERMIT)
480 return;
481 if (lde_acl_check(ldeconf->ipv4.acl_label_accept_for,
482 AF_INET, (union ldpd_addr *)&fec.u.ipv4.prefix,
483 fec.u.ipv4.prefixlen) != FILTER_PERMIT)
484 return;
485 break;
486 case FEC_TYPE_IPV6:
487 if (lde_acl_check(ldeconf->ipv6.acl_label_accept_from,
488 AF_INET, (union ldpd_addr *)&ln->id, 32) != FILTER_PERMIT)
489 return;
490 if (lde_acl_check(ldeconf->ipv6.acl_label_accept_for,
491 AF_INET6, (union ldpd_addr *)&fec.u.ipv6.prefix,
492 fec.u.ipv6.prefixlen) != FILTER_PERMIT)
493 return;
494 break;
495 default:
496 break;
497 }
498
499 fn = (struct fec_node *)fec_find(&ft, &fec);
500 if (fn == NULL)
501 fn = fec_add(&fec);
502
503 /* LMp.1: first check if we have a pending request running */
504 lre = (struct lde_req *)fec_find(&ln->sent_req, &fn->fec);
505 if (lre)
506 /* LMp.2: delete record of outstanding label request */
507 lde_req_del(ln, lre, 1);
508
509 /* RFC 4447 control word and status tlv negotiation */
510 if (map->type == MAP_TYPE_PWID && l2vpn_pw_negotiate(ln, fn, map))
511 return;
512
513 /*
514 * LMp.3 - LMp.8: loop detection - unnecessary for frame-mode
515 * mpls networks.
516 */
517
518 /* LMp.9 */
519 me = (struct lde_map *)fec_find(&ln->recv_map, &fn->fec);
520 if (me) {
521 /* LMp.10 */
522 if (me->map.label != map->label && lre == NULL) {
523 /* LMp.10a */
524 lde_send_labelrelease(ln, fn, NULL, me->map.label);
525
526 /*
527 * Can not use lde_nbr_find_by_addr() because there's
528 * the possibility of multipath.
529 */
530 LIST_FOREACH(fnh, &fn->nexthops, entry) {
531 if (lde_address_find(ln, fnh->af,
532 &fnh->nexthop) == NULL)
533 continue;
534
535 lde_send_delete_klabel(fn, fnh);
536 fnh->remote_label = NO_LABEL;
537 }
538 }
539 }
540
541 /*
542 * LMp.11 - 12: consider multiple nexthops in order to
543 * support multipath
544 */
545 LIST_FOREACH(fnh, &fn->nexthops, entry) {
546 /* LMp.15: install FEC in FIB */
547 switch (fec.type) {
548 case FEC_TYPE_IPV4:
549 case FEC_TYPE_IPV6:
550 if (!lde_address_find(ln, fnh->af, &fnh->nexthop))
551 continue;
552
553 /*
554 * Ordered Control: labelmap msg received from
555 * NH so clear flag and send labelmap msg to
556 * peer
557 */
558 if (ldeconf->flags & F_LDPD_ORDERED_CONTROL) {
559 send_map = true;
560 fnh->flags &= ~F_FEC_NH_DEFER;
561 }
562 fnh->remote_label = map->label;
563 lde_send_change_klabel(fn, fnh);
564 break;
565 case FEC_TYPE_PWID:
566 pw = (struct l2vpn_pw *) fn->data;
567 if (pw == NULL)
568 continue;
569
570 pw->remote_group = map->fec.pwid.group_id;
571 if (map->flags & F_MAP_PW_IFMTU)
572 pw->remote_mtu = map->fec.pwid.ifmtu;
573 if (map->flags & F_MAP_PW_STATUS)
574 pw->remote_status = map->pw_status;
575 else
576 pw->remote_status = PW_FORWARDING;
577 fnh->remote_label = map->label;
578 if (l2vpn_pw_ok(pw, fnh))
579 lde_send_change_klabel(fn, fnh);
580 break;
581 default:
582 break;
583 }
584 }
585 /* LMp.13 & LMp.16: Record the mapping from this peer */
586 if (me == NULL)
587 me = lde_map_add(ln, fn, 0);
588 me->map = *map;
589
590 /*
591 * LMp.17 - LMp.27 are unnecessary since we don't need to implement
592 * loop detection. LMp.28 - LMp.30 are unnecessary because we are
593 * merging capable.
594 */
595
596 /*
597 * Ordered Control: just received a labelmap for this fec from NH so
598 * need to send labelmap to all peers
599 * LMp.20 - LMp21 Execute procedure to send Label Mapping
600 */
601 if (send_map && fn->local_label != NO_LABEL)
602 RB_FOREACH(ln, nbr_tree, &lde_nbrs)
603 lde_send_labelmapping(ln, fn, 1);
604 }
605
606 void
607 lde_check_request(struct map *map, struct lde_nbr *ln)
608 {
609 struct fec fec;
610 struct lde_req *lre;
611 struct fec_node *fn;
612 struct fec_nh *fnh;
613
614 /* wildcard label request */
615 if (map->type == MAP_TYPE_TYPED_WCARD) {
616 lde_check_request_wcard(map, ln);
617 return;
618 }
619
620 /* LRq.1: skip loop detection (not necessary) */
621
622 /* LRq.2: is there a next hop for fec? */
623 lde_map2fec(map, ln->id, &fec);
624 fn = (struct fec_node *)fec_find(&ft, &fec);
625 if (fn == NULL || LIST_EMPTY(&fn->nexthops)) {
626 /* LRq.5: send No Route notification */
627 lde_send_notification(ln, S_NO_ROUTE, map->msg_id,
628 htons(MSG_TYPE_LABELREQUEST));
629 return;
630 }
631
632 /* LRq.3: is MsgSource the next hop? */
633 LIST_FOREACH(fnh, &fn->nexthops, entry) {
634 switch (fec.type) {
635 case FEC_TYPE_IPV4:
636 case FEC_TYPE_IPV6:
637 if (!lde_address_find(ln, fnh->af, &fnh->nexthop))
638 continue;
639
640 /* LRq.4: send Loop Detected notification */
641 lde_send_notification(ln, S_LOOP_DETECTED, map->msg_id,
642 htons(MSG_TYPE_LABELREQUEST));
643 return;
644 default:
645 break;
646 }
647 }
648
649 /* LRq.6: first check if we have a pending request running */
650 lre = (struct lde_req *)fec_find(&ln->recv_req, &fn->fec);
651 if (lre != NULL)
652 /* LRq.7: duplicate request */
653 return;
654
655 /* LRq.8: record label request */
656 lre = lde_req_add(ln, &fn->fec, 0);
657 if (lre != NULL)
658 lre->msg_id = ntohl(map->msg_id);
659
660 /* LRq.9: perform LSR label distribution */
661 lde_send_labelmapping(ln, fn, 1);
662
663 /*
664 * LRq.10: do nothing (Request Never) since we use liberal
665 * label retention.
666 * LRq.11 - 12 are unnecessary since we are merging capable.
667 */
668 }
669
670 void
671 lde_check_request_wcard(struct map *map, struct lde_nbr *ln)
672 {
673 struct fec *f;
674 struct fec_node *fn;
675 struct lde_req *lre;
676
677 RB_FOREACH(f, fec_tree, &ft) {
678 fn = (struct fec_node *)f;
679
680 /* only a typed wildcard is possible here */
681 if (lde_wildcard_apply(map, &fn->fec, NULL) == 0)
682 continue;
683
684 /* LRq.2: is there a next hop for fec? */
685 if (LIST_EMPTY(&fn->nexthops))
686 continue;
687
688 /* LRq.6: first check if we have a pending request running */
689 lre = (struct lde_req *)fec_find(&ln->recv_req, &fn->fec);
690 if (lre != NULL)
691 /* LRq.7: duplicate request */
692 continue;
693
694 /* LRq.8: record label request */
695 lre = lde_req_add(ln, &fn->fec, 0);
696 if (lre != NULL)
697 lre->msg_id = ntohl(map->msg_id);
698
699 /* LRq.9: perform LSR label distribution */
700 lde_send_labelmapping(ln, fn, 1);
701 }
702 }
703
704 void
705 lde_check_release(struct map *map, struct lde_nbr *ln)
706 {
707 struct fec fec;
708 struct fec_node *fn;
709 struct lde_wdraw *lw;
710 struct lde_map *me;
711 struct fec *pending_map;
712
713 /* wildcard label release */
714 if (map->type == MAP_TYPE_WILDCARD ||
715 map->type == MAP_TYPE_TYPED_WCARD ||
716 (map->type == MAP_TYPE_PWID && !(map->flags & F_MAP_PW_ID))) {
717 lde_check_release_wcard(map, ln);
718 return;
719 }
720
721 lde_map2fec(map, ln->id, &fec);
722 fn = (struct fec_node *)fec_find(&ft, &fec);
723 /* LRl.1: does FEC match a known FEC? */
724 if (fn == NULL)
725 return;
726
727 /* LRl.6: check sent map list and remove it if available */
728 me = (struct lde_map *)fec_find(&ln->sent_map, &fn->fec);
729 if (me && (map->label == NO_LABEL || map->label == me->map.label))
730 lde_map_del(ln, me, 1);
731
732 /* LRl.3: first check if we have a pending withdraw running */
733 lw = (struct lde_wdraw *)fec_find(&ln->sent_wdraw, &fn->fec);
734 if (lw && (map->label == NO_LABEL || map->label == lw->label)) {
735 /* LRl.4: delete record of outstanding label withdraw */
736 lde_wdraw_del(ln, lw);
737
738 /* send pending label mapping if any */
739 pending_map = fec_find(&ln->sent_map_pending, &fn->fec);
740 if (pending_map) {
741 lde_send_labelmapping(ln, fn, 1);
742 lde_map_pending_del(ln, pending_map);
743 }
744 }
745
746 /*
747 * LRl.11 - 13 are unnecessary since we remove the label from
748 * forwarding/switching as soon as the FEC is unreachable.
749 */
750 }
751
752 void
753 lde_check_release_wcard(struct map *map, struct lde_nbr *ln)
754 {
755 struct fec *f;
756 struct fec_node *fn;
757 struct lde_wdraw *lw;
758 struct lde_map *me;
759 struct fec *pending_map;
760
761 RB_FOREACH(f, fec_tree, &ft) {
762 fn = (struct fec_node *)f;
763 me = (struct lde_map *)fec_find(&ln->sent_map, &fn->fec);
764
765 /* LRl.1: does FEC match a known FEC? */
766 if (lde_wildcard_apply(map, &fn->fec, me) == 0)
767 continue;
768
769 /* LRl.6: check sent map list and remove it if available */
770 if (me &&
771 (map->label == NO_LABEL || map->label == me->map.label))
772 lde_map_del(ln, me, 1);
773
774 /* LRl.3: first check if we have a pending withdraw running */
775 lw = (struct lde_wdraw *)fec_find(&ln->sent_wdraw, &fn->fec);
776 if (lw && (map->label == NO_LABEL || map->label == lw->label)) {
777 /* LRl.4: delete record of outstanding lbl withdraw */
778 lde_wdraw_del(ln, lw);
779
780 /* send pending label mapping if any */
781 pending_map = fec_find(&ln->sent_map_pending, &fn->fec);
782 if (pending_map) {
783 lde_send_labelmapping(ln, fn, 1);
784 lde_map_pending_del(ln, pending_map);
785 }
786 }
787
788 /*
789 * LRl.11 - 13 are unnecessary since we remove the label from
790 * forwarding/switching as soon as the FEC is unreachable.
791 */
792 }
793 }
794
795 void
796 lde_check_withdraw(struct map *map, struct lde_nbr *ln)
797 {
798 struct fec fec;
799 struct fec_node *fn;
800 struct fec_nh *fnh;
801 struct lde_map *me;
802 struct l2vpn_pw *pw;
803 struct lde_nbr *lnbr;
804
805 /* wildcard label withdraw */
806 if (map->type == MAP_TYPE_WILDCARD ||
807 map->type == MAP_TYPE_TYPED_WCARD ||
808 (map->type == MAP_TYPE_PWID && !(map->flags & F_MAP_PW_ID))) {
809 lde_check_withdraw_wcard(map, ln);
810 return;
811 }
812
813 lde_map2fec(map, ln->id, &fec);
814 fn = (struct fec_node *)fec_find(&ft, &fec);
815 if (fn == NULL)
816 fn = fec_add(&fec);
817
818 /* LWd.1: remove label from forwarding/switching use */
819 LIST_FOREACH(fnh, &fn->nexthops, entry) {
820 switch (fec.type) {
821 case FEC_TYPE_IPV4:
822 case FEC_TYPE_IPV6:
823 if (!lde_address_find(ln, fnh->af, &fnh->nexthop))
824 continue;
825 break;
826 case FEC_TYPE_PWID:
827 pw = (struct l2vpn_pw *) fn->data;
828 if (pw == NULL)
829 continue;
830 pw->remote_status = PW_NOT_FORWARDING;
831 break;
832 default:
833 break;
834 }
835 if (map->label != NO_LABEL && map->label != fnh->remote_label)
836 continue;
837
838 lde_send_delete_klabel(fn, fnh);
839 fnh->remote_label = NO_LABEL;
840 }
841
842 /* LWd.2: send label release */
843 lde_send_labelrelease(ln, fn, NULL, map->label);
844
845 /* LWd.3: check previously received label mapping */
846 me = (struct lde_map *)fec_find(&ln->recv_map, &fn->fec);
847 if (me && (map->label == NO_LABEL || map->label == me->map.label))
848 /* LWd.4: remove record of previously received lbl mapping */
849 lde_map_del(ln, me, 0);
850
851 /* Ordered Control: additional withdraw steps */
852 if (ldeconf->flags & F_LDPD_ORDERED_CONTROL) {
853 /* LWd.8: for each neighbor other that src of withdraw msg */
854 RB_FOREACH(lnbr, nbr_tree, &lde_nbrs) {
855 if (ln->peerid == lnbr->peerid)
856 continue;
857
858 /* LWd.9: check if previously sent a label mapping */
859 me = (struct lde_map *)fec_find(&lnbr->sent_map,
860 &fn->fec);
861 /*
862 * LWd.10: does label sent to peer "map" to withdraw
863 * label
864 */
865 if (me)
866 /* LWd.11: send label withdraw */
867 lde_send_labelwithdraw(lnbr, fn, NULL, NULL);
868 }
869 }
870 }
871
872 void
873 lde_check_withdraw_wcard(struct map *map, struct lde_nbr *ln)
874 {
875 struct fec *f;
876 struct fec_node *fn;
877 struct fec_nh *fnh;
878 struct lde_map *me;
879 struct l2vpn_pw *pw;
880 struct lde_nbr *lnbr;
881
882 /* LWd.2: send label release */
883 lde_send_labelrelease(ln, NULL, map, map->label);
884
885 RB_FOREACH(f, fec_tree, &ft) {
886 fn = (struct fec_node *)f;
887 me = (struct lde_map *)fec_find(&ln->recv_map, &fn->fec);
888
889 if (lde_wildcard_apply(map, &fn->fec, me) == 0)
890 continue;
891
892 /* LWd.1: remove label from forwarding/switching use */
893 LIST_FOREACH(fnh, &fn->nexthops, entry) {
894 switch (f->type) {
895 case FEC_TYPE_IPV4:
896 case FEC_TYPE_IPV6:
897 if (!lde_address_find(ln, fnh->af,
898 &fnh->nexthop))
899 continue;
900 break;
901 case FEC_TYPE_PWID:
902 if (f->u.pwid.lsr_id.s_addr != ln->id.s_addr)
903 continue;
904 pw = (struct l2vpn_pw *) fn->data;
905 if (pw)
906 pw->remote_status = PW_NOT_FORWARDING;
907 break;
908 default:
909 break;
910 }
911 if (map->label != NO_LABEL && map->label !=
912 fnh->remote_label)
913 continue;
914
915 lde_send_delete_klabel(fn, fnh);
916 fnh->remote_label = NO_LABEL;
917 }
918
919 /* LWd.3: check previously received label mapping */
920 if (me && (map->label == NO_LABEL ||
921 map->label == me->map.label))
922 /*
923 * LWd.4: remove record of previously received
924 * label mapping
925 */
926 lde_map_del(ln, me, 0);
927
928 /* Ordered Control: additional withdraw steps */
929 if (ldeconf->flags & F_LDPD_ORDERED_CONTROL) {
930 /* LWd.8: for each neighbor other that src of withdraw msg */
931 RB_FOREACH(lnbr, nbr_tree, &lde_nbrs) {
932 if (ln->peerid == lnbr->peerid)
933 continue;
934
935 /* LWd.9: check if previously sent a label mapping */
936 me = (struct lde_map *)fec_find(&lnbr->sent_map,
937 &fn->fec);
938 /*
939 * LWd.10: does label sent to peer "map" to withdraw
940 * label
941 */
942 if (me)
943 /* LWd.11: send label withdraw */
944 lde_send_labelwithdraw(lnbr, fn, NULL, NULL);
945 }
946 }
947 }
948 }
949
950 int
951 lde_wildcard_apply(struct map *wcard, struct fec *fec, struct lde_map *me)
952 {
953 switch (wcard->type) {
954 case MAP_TYPE_WILDCARD:
955 /* full wildcard */
956 return (1);
957 case MAP_TYPE_TYPED_WCARD:
958 switch (wcard->fec.twcard.type) {
959 case MAP_TYPE_PREFIX:
960 if (wcard->fec.twcard.u.prefix_af == AF_INET &&
961 fec->type != FEC_TYPE_IPV4)
962 return (0);
963 if (wcard->fec.twcard.u.prefix_af == AF_INET6 &&
964 fec->type != FEC_TYPE_IPV6)
965 return (0);
966 return (1);
967 case MAP_TYPE_PWID:
968 if (fec->type != FEC_TYPE_PWID)
969 return (0);
970 if (wcard->fec.twcard.u.pw_type != PW_TYPE_WILDCARD &&
971 wcard->fec.twcard.u.pw_type != fec->u.pwid.type)
972 return (0);
973 return (1);
974 default:
975 fatalx("lde_wildcard_apply: unexpected fec type");
976 }
977 break;
978 case MAP_TYPE_PWID:
979 /* RFC4447 pw-id group wildcard */
980 if (fec->type != FEC_TYPE_PWID)
981 return (0);
982 if (fec->u.pwid.type != wcard->fec.pwid.type)
983 return (0);
984 if (me == NULL || (me->map.fec.pwid.group_id !=
985 wcard->fec.pwid.group_id))
986 return (0);
987 return (1);
988 default:
989 fatalx("lde_wildcard_apply: unexpected fec type");
990 }
991 }
992
993 /* gabage collector timer: timer to remove dead entries from the LIB */
994
995 /* ARGSUSED */
996 int
997 lde_gc_timer(struct thread *thread)
998 {
999 struct fec *fec, *safe;
1000 struct fec_node *fn;
1001 int count = 0;
1002
1003 RB_FOREACH_SAFE(fec, fec_tree, &ft, safe) {
1004 fn = (struct fec_node *) fec;
1005
1006 if (!LIST_EMPTY(&fn->nexthops) ||
1007 !RB_EMPTY(lde_map_head, &fn->downstream) ||
1008 !RB_EMPTY(lde_map_head, &fn->upstream))
1009 continue;
1010
1011 if (fn->local_label != NO_LABEL)
1012 lde_free_label(fn->local_label);
1013
1014 fec_remove(&ft, &fn->fec);
1015 free(fn);
1016 count++;
1017 }
1018
1019 if (count > 0)
1020 log_debug("%s: %u entries removed", __func__, count);
1021
1022 lde_gc_start_timer();
1023
1024 return (0);
1025 }
1026
1027 void
1028 lde_gc_start_timer(void)
1029 {
1030 THREAD_TIMER_OFF(gc_timer);
1031 gc_timer = NULL;
1032 thread_add_timer(master, lde_gc_timer, NULL, LDE_GC_INTERVAL,
1033 &gc_timer);
1034 }
1035
1036 void
1037 lde_gc_stop_timer(void)
1038 {
1039 THREAD_TIMER_OFF(gc_timer);
1040 }
FRRouting mirror