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