]> 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 #6517 from vishaldhingra/submodule
[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->type == FEC_TYPE_PWID)
271 fn->pw_remote_status = PW_FORWARDING;
272
273 if (fec_insert(&ft, &fn->fec))
274 log_warnx("failed to add %s to ft tree",
275 log_fec(&fn->fec));
276
277 return (fn);
278 }
279
280 struct fec_nh *
281 fec_nh_find(struct fec_node *fn, int af, union ldpd_addr *nexthop,
282 ifindex_t ifindex, uint8_t route_type, unsigned short route_instance)
283 {
284 struct fec_nh *fnh;
285
286 LIST_FOREACH(fnh, &fn->nexthops, entry)
287 if (fnh->af == af &&
288 ldp_addrcmp(af, &fnh->nexthop, nexthop) == 0 &&
289 fnh->ifindex == ifindex &&
290 fnh->route_type == route_type &&
291 fnh->route_instance == route_instance)
292 return (fnh);
293
294 return (NULL);
295 }
296
297 static struct fec_nh *
298 fec_nh_add(struct fec_node *fn, int af, union ldpd_addr *nexthop,
299 ifindex_t ifindex, uint8_t route_type, unsigned short route_instance)
300 {
301 struct fec_nh *fnh;
302
303 fnh = calloc(1, sizeof(*fnh));
304 if (fnh == NULL)
305 fatal(__func__);
306
307 fnh->af = af;
308 fnh->nexthop = *nexthop;
309 fnh->ifindex = ifindex;
310 fnh->remote_label = NO_LABEL;
311 fnh->route_type = route_type;
312 fnh->route_instance = route_instance;
313 LIST_INSERT_HEAD(&fn->nexthops, fnh, entry);
314
315 return (fnh);
316 }
317
318 static void
319 fec_nh_del(struct fec_nh *fnh)
320 {
321 LIST_REMOVE(fnh, entry);
322 free(fnh);
323 }
324
325 void
326 lde_kernel_insert(struct fec *fec, int af, union ldpd_addr *nexthop,
327 ifindex_t ifindex, uint8_t route_type, unsigned short route_instance,
328 int connected, void *data)
329 {
330 struct fec_node *fn;
331 struct fec_nh *fnh;
332 struct iface *iface;
333
334 fn = (struct fec_node *)fec_find(&ft, fec);
335 if (fn == NULL)
336 fn = fec_add(fec);
337 if (data)
338 fn->data = data;
339
340 fnh = fec_nh_find(fn, af, nexthop, ifindex, route_type, route_instance);
341 if (fnh == NULL) {
342 fnh = fec_nh_add(fn, af, nexthop, ifindex, route_type,
343 route_instance);
344 /*
345 * Ordered Control: if not a connected route and not a route
346 * learned over an interface not running LDP and not a PW
347 * then mark to wait until we receive labelmap msg before
348 * installing in kernel and sending to peer
349 */
350 iface = if_lookup(ldeconf, ifindex);
351 if ((ldeconf->flags & F_LDPD_ORDERED_CONTROL) &&
352 !connected && iface != NULL && fec->type != FEC_TYPE_PWID)
353 fnh->flags |= F_FEC_NH_DEFER;
354 }
355
356 fnh->flags |= F_FEC_NH_NEW;
357 if (connected)
358 fnh->flags |= F_FEC_NH_CONNECTED;
359 }
360
361 void
362 lde_kernel_remove(struct fec *fec, int af, union ldpd_addr *nexthop,
363 ifindex_t ifindex, uint8_t route_type, unsigned short route_instance)
364 {
365 struct fec_node *fn;
366 struct fec_nh *fnh;
367
368 fn = (struct fec_node *)fec_find(&ft, fec);
369 if (fn == NULL)
370 /* route lost */
371 return;
372 fnh = fec_nh_find(fn, af, nexthop, ifindex, route_type, route_instance);
373 if (fnh == NULL)
374 /* route lost */
375 return;
376
377 lde_send_delete_klabel(fn, fnh);
378 fec_nh_del(fnh);
379 }
380
381 /*
382 * Whenever a route is changed, zebra advertises its new version without
383 * withdrawing the old one. So, after processing a ZEBRA_REDISTRIBUTE_IPV[46]_ADD
384 * message, we need to check for nexthops that were removed and, for each of
385 * them (if any), withdraw the associated labels from zebra.
386 */
387 void
388 lde_kernel_update(struct fec *fec)
389 {
390 struct fec_node *fn;
391 struct fec_nh *fnh, *safe;
392 struct lde_nbr *ln;
393 struct lde_map *me;
394 struct iface *iface;
395
396 fn = (struct fec_node *)fec_find(&ft, fec);
397 if (fn == NULL)
398 return;
399
400 LIST_FOREACH_SAFE(fnh, &fn->nexthops, entry, safe) {
401 if (fnh->flags & F_FEC_NH_NEW) {
402 fnh->flags &= ~F_FEC_NH_NEW;
403 /*
404 * if LDP configured on interface or a static route
405 * clear flag else treat fec as a connected route
406 */
407 iface = if_lookup(ldeconf,fnh->ifindex);
408 if (iface || fnh->route_type == ZEBRA_ROUTE_STATIC)
409 fnh->flags &=~F_FEC_NH_NO_LDP;
410 else
411 fnh->flags |= F_FEC_NH_NO_LDP;
412 } else {
413 lde_send_delete_klabel(fn, fnh);
414 fec_nh_del(fnh);
415 }
416 }
417
418 if (LIST_EMPTY(&fn->nexthops)) {
419 RB_FOREACH(ln, nbr_tree, &lde_nbrs)
420 lde_send_labelwithdraw(ln, fn, NULL, NULL);
421 fn->data = NULL;
422
423 /*
424 * Do not deallocate the local label now, do that only in the
425 * LIB garbage collector. This will prevent ldpd from changing
426 * the input label of some prefixes too often when running on
427 * an unstable network. Also, restart the garbage collector
428 * timer so that labels are deallocated only when the network
429 * is stabilized.
430 */
431 lde_gc_start_timer();
432 } else {
433 fn->local_label = lde_update_label(fn);
434 if (fn->local_label != NO_LABEL)
435 /* FEC.1: perform lsr label distribution procedure */
436 RB_FOREACH(ln, nbr_tree, &lde_nbrs)
437 lde_send_labelmapping(ln, fn, 1);
438 }
439
440 LIST_FOREACH(fnh, &fn->nexthops, entry) {
441 lde_send_change_klabel(fn, fnh);
442
443 switch (fn->fec.type) {
444 case FEC_TYPE_IPV4:
445 case FEC_TYPE_IPV6:
446 ln = lde_nbr_find_by_addr(fnh->af, &fnh->nexthop);
447 break;
448 case FEC_TYPE_PWID:
449 ln = lde_nbr_find_by_lsrid(fn->fec.u.pwid.lsr_id);
450 break;
451 default:
452 ln = NULL;
453 break;
454 }
455
456 if (ln) {
457 /* FEC.2 */
458 me = (struct lde_map *)fec_find(&ln->recv_map, &fn->fec);
459 if (me)
460 /* FEC.5 */
461 lde_check_mapping(&me->map, ln, 0);
462 }
463 }
464 }
465
466 void
467 lde_check_mapping(struct map *map, struct lde_nbr *ln, int rcvd_label_mapping)
468 {
469 struct fec fec;
470 struct fec_node *fn;
471 struct fec_nh *fnh;
472 struct lde_req *lre;
473 struct lde_map *me;
474 struct l2vpn_pw *pw;
475 bool send_map = false;
476
477 lde_map2fec(map, ln->id, &fec);
478
479 switch (fec.type) {
480 case FEC_TYPE_IPV4:
481 if (lde_acl_check(ldeconf->ipv4.acl_label_accept_from,
482 AF_INET, (union ldpd_addr *)&ln->id, 32) != FILTER_PERMIT)
483 return;
484 if (lde_acl_check(ldeconf->ipv4.acl_label_accept_for,
485 AF_INET, (union ldpd_addr *)&fec.u.ipv4.prefix,
486 fec.u.ipv4.prefixlen) != FILTER_PERMIT)
487 return;
488 break;
489 case FEC_TYPE_IPV6:
490 if (lde_acl_check(ldeconf->ipv6.acl_label_accept_from,
491 AF_INET, (union ldpd_addr *)&ln->id, 32) != FILTER_PERMIT)
492 return;
493 if (lde_acl_check(ldeconf->ipv6.acl_label_accept_for,
494 AF_INET6, (union ldpd_addr *)&fec.u.ipv6.prefix,
495 fec.u.ipv6.prefixlen) != FILTER_PERMIT)
496 return;
497 break;
498 default:
499 break;
500 }
501
502 fn = (struct fec_node *)fec_find(&ft, &fec);
503 if (fn == NULL)
504 fn = fec_add(&fec);
505
506 /* LMp.1: first check if we have a pending request running */
507 lre = (struct lde_req *)fec_find(&ln->sent_req, &fn->fec);
508 if (lre)
509 /* LMp.2: delete record of outstanding label request */
510 lde_req_del(ln, lre, 1);
511
512 /* RFC 4447 control word and status tlv negotiation */
513 if (map->type == MAP_TYPE_PWID && l2vpn_pw_negotiate(ln, fn, map)) {
514 if (rcvd_label_mapping && map->flags & F_MAP_PW_STATUS)
515 fn->pw_remote_status = map->pw_status;
516
517 return;
518 }
519
520 /*
521 * LMp.3 - LMp.8: loop detection - unnecessary for frame-mode
522 * mpls networks.
523 */
524
525 /* LMp.9 */
526 me = (struct lde_map *)fec_find(&ln->recv_map, &fn->fec);
527 if (me) {
528 /* LMp.10 */
529 if (me->map.label != map->label && lre == NULL) {
530 /* LMp.10a */
531 lde_send_labelrelease(ln, fn, NULL, me->map.label);
532
533 /*
534 * Can not use lde_nbr_find_by_addr() because there's
535 * the possibility of multipath.
536 */
537 LIST_FOREACH(fnh, &fn->nexthops, entry) {
538 if (lde_address_find(ln, fnh->af,
539 &fnh->nexthop) == NULL)
540 continue;
541
542 lde_send_delete_klabel(fn, fnh);
543 fnh->remote_label = NO_LABEL;
544 }
545 }
546 }
547
548 /*
549 * LMp.11 - 12: consider multiple nexthops in order to
550 * support multipath
551 */
552 LIST_FOREACH(fnh, &fn->nexthops, entry) {
553 /* LMp.15: install FEC in FIB */
554 switch (fec.type) {
555 case FEC_TYPE_IPV4:
556 case FEC_TYPE_IPV6:
557 if (!lde_address_find(ln, fnh->af, &fnh->nexthop))
558 continue;
559
560 /*
561 * Ordered Control: labelmap msg received from
562 * NH so clear flag and send labelmap msg to
563 * peer
564 */
565 if (ldeconf->flags & F_LDPD_ORDERED_CONTROL) {
566 send_map = true;
567 fnh->flags &= ~F_FEC_NH_DEFER;
568 }
569 fnh->remote_label = map->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 /* LMp.13 & LMp.16: Record the mapping from this peer */
595 if (me == NULL)
596 me = lde_map_add(ln, fn, 0);
597 me->map = *map;
598
599 /*
600 * LMp.17 - LMp.27 are unnecessary since we don't need to implement
601 * loop detection. LMp.28 - LMp.30 are unnecessary because we are
602 * merging capable.
603 */
604
605 /*
606 * Ordered Control: just received a labelmap for this fec from NH so
607 * need to send labelmap to all peers
608 * LMp.20 - LMp21 Execute procedure to send Label Mapping
609 */
610 if (send_map && fn->local_label != NO_LABEL)
611 RB_FOREACH(ln, nbr_tree, &lde_nbrs)
612 lde_send_labelmapping(ln, fn, 1);
613 }
614
615 void
616 lde_check_request(struct map *map, struct lde_nbr *ln)
617 {
618 struct fec fec;
619 struct lde_req *lre;
620 struct fec_node *fn;
621 struct fec_nh *fnh;
622
623 /* wildcard label request */
624 if (map->type == MAP_TYPE_TYPED_WCARD) {
625 lde_check_request_wcard(map, ln);
626 return;
627 }
628
629 /* LRq.1: skip loop detection (not necessary) */
630
631 /* LRq.2: is there a next hop for fec? */
632 lde_map2fec(map, ln->id, &fec);
633 fn = (struct fec_node *)fec_find(&ft, &fec);
634 if (fn == NULL || LIST_EMPTY(&fn->nexthops)) {
635 /* LRq.5: send No Route notification */
636 lde_send_notification(ln, S_NO_ROUTE, map->msg_id,
637 htons(MSG_TYPE_LABELREQUEST));
638 return;
639 }
640
641 /* LRq.3: is MsgSource the next hop? */
642 LIST_FOREACH(fnh, &fn->nexthops, entry) {
643 switch (fec.type) {
644 case FEC_TYPE_IPV4:
645 case FEC_TYPE_IPV6:
646 if (!lde_address_find(ln, fnh->af, &fnh->nexthop))
647 continue;
648
649 /* LRq.4: send Loop Detected notification */
650 lde_send_notification(ln, S_LOOP_DETECTED, map->msg_id,
651 htons(MSG_TYPE_LABELREQUEST));
652 return;
653 default:
654 break;
655 }
656 }
657
658 /* LRq.6: first check if we have a pending request running */
659 lre = (struct lde_req *)fec_find(&ln->recv_req, &fn->fec);
660 if (lre != NULL)
661 /* LRq.7: duplicate request */
662 return;
663
664 /* LRq.8: record label request */
665 lre = lde_req_add(ln, &fn->fec, 0);
666 if (lre != NULL)
667 lre->msg_id = ntohl(map->msg_id);
668
669 /* LRq.9: perform LSR label distribution */
670 lde_send_labelmapping(ln, fn, 1);
671
672 /*
673 * LRq.10: do nothing (Request Never) since we use liberal
674 * label retention.
675 * LRq.11 - 12 are unnecessary since we are merging capable.
676 */
677 }
678
679 void
680 lde_check_request_wcard(struct map *map, struct lde_nbr *ln)
681 {
682 struct fec *f;
683 struct fec_node *fn;
684 struct lde_req *lre;
685
686 RB_FOREACH(f, fec_tree, &ft) {
687 fn = (struct fec_node *)f;
688
689 /* only a typed wildcard is possible here */
690 if (lde_wildcard_apply(map, &fn->fec, NULL) == 0)
691 continue;
692
693 /* LRq.2: is there a next hop for fec? */
694 if (LIST_EMPTY(&fn->nexthops))
695 continue;
696
697 /* LRq.6: first check if we have a pending request running */
698 lre = (struct lde_req *)fec_find(&ln->recv_req, &fn->fec);
699 if (lre != NULL)
700 /* LRq.7: duplicate request */
701 continue;
702
703 /* LRq.8: record label request */
704 lre = lde_req_add(ln, &fn->fec, 0);
705 if (lre != NULL)
706 lre->msg_id = ntohl(map->msg_id);
707
708 /* LRq.9: perform LSR label distribution */
709 lde_send_labelmapping(ln, fn, 1);
710 }
711 }
712
713 void
714 lde_check_release(struct map *map, struct lde_nbr *ln)
715 {
716 struct fec fec;
717 struct fec_node *fn;
718 struct lde_wdraw *lw;
719 struct lde_map *me;
720 struct fec *pending_map;
721
722 /* wildcard label release */
723 if (map->type == MAP_TYPE_WILDCARD ||
724 map->type == MAP_TYPE_TYPED_WCARD ||
725 (map->type == MAP_TYPE_PWID && !(map->flags & F_MAP_PW_ID))) {
726 lde_check_release_wcard(map, ln);
727 return;
728 }
729
730 lde_map2fec(map, ln->id, &fec);
731 fn = (struct fec_node *)fec_find(&ft, &fec);
732 /* LRl.1: does FEC match a known FEC? */
733 if (fn == NULL)
734 return;
735
736 /* LRl.6: check sent map list and remove it if available */
737 me = (struct lde_map *)fec_find(&ln->sent_map, &fn->fec);
738 if (me && (map->label == NO_LABEL || map->label == me->map.label))
739 lde_map_del(ln, me, 1);
740
741 /* LRl.3: first check if we have a pending withdraw running */
742 lw = (struct lde_wdraw *)fec_find(&ln->sent_wdraw, &fn->fec);
743 if (lw && (map->label == NO_LABEL || map->label == lw->label)) {
744 /* LRl.4: delete record of outstanding label withdraw */
745 lde_wdraw_del(ln, lw);
746
747 /* send pending label mapping if any */
748 pending_map = fec_find(&ln->sent_map_pending, &fn->fec);
749 if (pending_map) {
750 lde_send_labelmapping(ln, fn, 1);
751 lde_map_pending_del(ln, pending_map);
752 }
753 }
754
755 /*
756 * LRl.11 - 13 are unnecessary since we remove the label from
757 * forwarding/switching as soon as the FEC is unreachable.
758 */
759 }
760
761 void
762 lde_check_release_wcard(struct map *map, struct lde_nbr *ln)
763 {
764 struct fec *f;
765 struct fec_node *fn;
766 struct lde_wdraw *lw;
767 struct lde_map *me;
768 struct fec *pending_map;
769
770 RB_FOREACH(f, fec_tree, &ft) {
771 fn = (struct fec_node *)f;
772 me = (struct lde_map *)fec_find(&ln->sent_map, &fn->fec);
773
774 /* LRl.1: does FEC match a known FEC? */
775 if (lde_wildcard_apply(map, &fn->fec, me) == 0)
776 continue;
777
778 /* LRl.6: check sent map list and remove it if available */
779 if (me &&
780 (map->label == NO_LABEL || map->label == me->map.label))
781 lde_map_del(ln, me, 1);
782
783 /* LRl.3: first check if we have a pending withdraw running */
784 lw = (struct lde_wdraw *)fec_find(&ln->sent_wdraw, &fn->fec);
785 if (lw && (map->label == NO_LABEL || map->label == lw->label)) {
786 /* LRl.4: delete record of outstanding lbl withdraw */
787 lde_wdraw_del(ln, lw);
788
789 /* send pending label mapping if any */
790 pending_map = fec_find(&ln->sent_map_pending, &fn->fec);
791 if (pending_map) {
792 lde_send_labelmapping(ln, fn, 1);
793 lde_map_pending_del(ln, pending_map);
794 }
795 }
796
797 /*
798 * LRl.11 - 13 are unnecessary since we remove the label from
799 * forwarding/switching as soon as the FEC is unreachable.
800 */
801 }
802 }
803
804 void
805 lde_check_withdraw(struct map *map, struct lde_nbr *ln)
806 {
807 struct fec fec;
808 struct fec_node *fn;
809 struct fec_nh *fnh;
810 struct lde_map *me;
811 struct l2vpn_pw *pw;
812 struct lde_nbr *lnbr;
813
814 /* wildcard label withdraw */
815 if (map->type == MAP_TYPE_WILDCARD ||
816 map->type == MAP_TYPE_TYPED_WCARD ||
817 (map->type == MAP_TYPE_PWID && !(map->flags & F_MAP_PW_ID))) {
818 lde_check_withdraw_wcard(map, ln);
819 return;
820 }
821
822 lde_map2fec(map, ln->id, &fec);
823 fn = (struct fec_node *)fec_find(&ft, &fec);
824 if (fn == NULL)
825 fn = fec_add(&fec);
826
827 /* LWd.1: remove label from forwarding/switching use */
828 LIST_FOREACH(fnh, &fn->nexthops, entry) {
829 switch (fec.type) {
830 case FEC_TYPE_IPV4:
831 case FEC_TYPE_IPV6:
832 if (!lde_address_find(ln, fnh->af, &fnh->nexthop))
833 continue;
834 break;
835 case FEC_TYPE_PWID:
836 pw = (struct l2vpn_pw *) fn->data;
837 if (pw == NULL)
838 continue;
839 pw->remote_status = PW_NOT_FORWARDING;
840 break;
841 default:
842 break;
843 }
844 if (map->label != NO_LABEL && map->label != fnh->remote_label)
845 continue;
846
847 lde_send_delete_klabel(fn, fnh);
848 fnh->remote_label = NO_LABEL;
849 }
850
851 /* LWd.2: send label release */
852 lde_send_labelrelease(ln, fn, NULL, map->label);
853
854 /* LWd.3: check previously received label mapping */
855 me = (struct lde_map *)fec_find(&ln->recv_map, &fn->fec);
856 if (me && (map->label == NO_LABEL || map->label == me->map.label))
857 /* LWd.4: remove record of previously received lbl mapping */
858 lde_map_del(ln, me, 0);
859 else
860 /* LWd.13 done */
861 return;
862
863 /* Ordered Control: additional withdraw steps */
864 if (ldeconf->flags & F_LDPD_ORDERED_CONTROL) {
865 /* LWd.8: for each neighbor other that src of withdraw msg */
866 RB_FOREACH(lnbr, nbr_tree, &lde_nbrs) {
867 if (ln->peerid == lnbr->peerid)
868 continue;
869
870 /* LWd.9: check if previously sent a label mapping */
871 me = (struct lde_map *)fec_find(&lnbr->sent_map,
872 &fn->fec);
873
874 /*
875 * LWd.10: does label sent to peer "map" to withdraw
876 * label
877 */
878 if (me && lde_nbr_is_nexthop(fn, lnbr))
879 /* LWd.11: send label withdraw */
880 lde_send_labelwithdraw(lnbr, fn, NULL, NULL);
881 }
882 }
883
884 }
885
886 void
887 lde_check_withdraw_wcard(struct map *map, struct lde_nbr *ln)
888 {
889 struct fec *f;
890 struct fec_node *fn;
891 struct fec_nh *fnh;
892 struct lde_map *me;
893 struct l2vpn_pw *pw;
894 struct lde_nbr *lnbr;
895
896 /* LWd.2: send label release */
897 lde_send_labelrelease(ln, NULL, map, map->label);
898
899 RB_FOREACH(f, fec_tree, &ft) {
900 fn = (struct fec_node *)f;
901 me = (struct lde_map *)fec_find(&ln->recv_map, &fn->fec);
902
903 if (lde_wildcard_apply(map, &fn->fec, me) == 0)
904 continue;
905
906 /* LWd.1: remove label from forwarding/switching use */
907 LIST_FOREACH(fnh, &fn->nexthops, entry) {
908 switch (f->type) {
909 case FEC_TYPE_IPV4:
910 case FEC_TYPE_IPV6:
911 if (!lde_address_find(ln, fnh->af,
912 &fnh->nexthop))
913 continue;
914 break;
915 case FEC_TYPE_PWID:
916 if (f->u.pwid.lsr_id.s_addr != ln->id.s_addr)
917 continue;
918 pw = (struct l2vpn_pw *) fn->data;
919 if (pw)
920 pw->remote_status = PW_NOT_FORWARDING;
921 break;
922 default:
923 break;
924 }
925 if (map->label != NO_LABEL && map->label !=
926 fnh->remote_label)
927 continue;
928
929 lde_send_delete_klabel(fn, fnh);
930 fnh->remote_label = NO_LABEL;
931 }
932
933 /* LWd.3: check previously received label mapping */
934 if (me && (map->label == NO_LABEL ||
935 map->label == me->map.label))
936 /*
937 * LWd.4: remove record of previously received
938 * label mapping
939 */
940 lde_map_del(ln, me, 0);
941 else
942 /* LWd.13 done */
943 continue;
944
945 /* Ordered Control: additional withdraw steps */
946 if (ldeconf->flags & F_LDPD_ORDERED_CONTROL) {
947 /*
948 * LWd.8: for each neighbor other that src of
949 * withdraw msg
950 */
951 RB_FOREACH(lnbr, nbr_tree, &lde_nbrs) {
952 if (ln->peerid == lnbr->peerid)
953 continue;
954
955 /* LWd.9: check if previously sent a label
956 * mapping
957 */
958 me = (struct lde_map *)fec_find(
959 &lnbr->sent_map, &fn->fec);
960 /*
961 * LWd.10: does label sent to peer "map" to
962 * withdraw label
963 */
964 if (me && lde_nbr_is_nexthop(fn, lnbr))
965 /* LWd.11: send label withdraw */
966 lde_send_labelwithdraw(lnbr, fn, NULL,
967 NULL);
968 }
969 }
970 }
971 }
972
973 int
974 lde_wildcard_apply(struct map *wcard, struct fec *fec, struct lde_map *me)
975 {
976 switch (wcard->type) {
977 case MAP_TYPE_WILDCARD:
978 /* full wildcard */
979 return (1);
980 case MAP_TYPE_TYPED_WCARD:
981 switch (wcard->fec.twcard.type) {
982 case MAP_TYPE_PREFIX:
983 if (wcard->fec.twcard.u.prefix_af == AF_INET &&
984 fec->type != FEC_TYPE_IPV4)
985 return (0);
986 if (wcard->fec.twcard.u.prefix_af == AF_INET6 &&
987 fec->type != FEC_TYPE_IPV6)
988 return (0);
989 return (1);
990 case MAP_TYPE_PWID:
991 if (fec->type != FEC_TYPE_PWID)
992 return (0);
993 if (wcard->fec.twcard.u.pw_type != PW_TYPE_WILDCARD &&
994 wcard->fec.twcard.u.pw_type != fec->u.pwid.type)
995 return (0);
996 return (1);
997 default:
998 fatalx("lde_wildcard_apply: unexpected fec type");
999 }
1000 break;
1001 case MAP_TYPE_PWID:
1002 /* RFC4447 pw-id group wildcard */
1003 if (fec->type != FEC_TYPE_PWID)
1004 return (0);
1005 if (fec->u.pwid.type != wcard->fec.pwid.type)
1006 return (0);
1007 if (me == NULL || (me->map.fec.pwid.group_id !=
1008 wcard->fec.pwid.group_id))
1009 return (0);
1010 return (1);
1011 default:
1012 fatalx("lde_wildcard_apply: unexpected fec type");
1013 }
1014 }
1015
1016 /* gabage collector timer: timer to remove dead entries from the LIB */
1017
1018 /* ARGSUSED */
1019 int
1020 lde_gc_timer(struct thread *thread)
1021 {
1022 struct fec *fec, *safe;
1023 struct fec_node *fn;
1024 int count = 0;
1025
1026 RB_FOREACH_SAFE(fec, fec_tree, &ft, safe) {
1027 fn = (struct fec_node *) fec;
1028
1029 if (!LIST_EMPTY(&fn->nexthops) ||
1030 !RB_EMPTY(lde_map_head, &fn->downstream) ||
1031 !RB_EMPTY(lde_map_head, &fn->upstream))
1032 continue;
1033
1034 if (fn->local_label != NO_LABEL)
1035 lde_free_label(fn->local_label);
1036
1037 fec_remove(&ft, &fn->fec);
1038 free(fn);
1039 count++;
1040 }
1041
1042 if (count > 0)
1043 log_debug("%s: %u entries removed", __func__, count);
1044
1045 lde_gc_start_timer();
1046
1047 return (0);
1048 }
1049
1050 void
1051 lde_gc_start_timer(void)
1052 {
1053 THREAD_TIMER_OFF(gc_timer);
1054 gc_timer = NULL;
1055 thread_add_timer(master, lde_gc_timer, NULL, LDE_GC_INTERVAL,
1056 &gc_timer);
1057 }
1058
1059 void
1060 lde_gc_stop_timer(void)
1061 {
1062 THREAD_TIMER_OFF(gc_timer);
1063 }
FRRouting mirror