]> 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 #6376 from opensourcerouting/bump-libyang-req-version-1.x
[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 if (ldeconf->flags & F_LDPD_ENABLED) {
408 iface = if_lookup(ldeconf,fnh->ifindex);
409 if (fnh->flags & F_FEC_NH_CONNECTED ||
410 iface ||
411 fnh->route_type == ZEBRA_ROUTE_STATIC)
412 fnh->flags &=~F_FEC_NH_NO_LDP;
413 else
414 fnh->flags |= F_FEC_NH_NO_LDP;
415 } else
416 fnh->flags |= F_FEC_NH_NO_LDP;
417 } else {
418 lde_send_delete_klabel(fn, fnh);
419 fec_nh_del(fnh);
420 }
421 }
422
423 if (LIST_EMPTY(&fn->nexthops)) {
424 RB_FOREACH(ln, nbr_tree, &lde_nbrs)
425 lde_send_labelwithdraw(ln, fn, NULL, NULL);
426 fn->data = NULL;
427
428 /*
429 * Do not deallocate the local label now, do that only in the
430 * LIB garbage collector. This will prevent ldpd from changing
431 * the input label of some prefixes too often when running on
432 * an unstable network. Also, restart the garbage collector
433 * timer so that labels are deallocated only when the network
434 * is stabilized.
435 */
436 lde_gc_start_timer();
437 } else {
438 fn->local_label = lde_update_label(fn);
439 if (fn->local_label != NO_LABEL)
440 /* FEC.1: perform lsr label distribution procedure */
441 RB_FOREACH(ln, nbr_tree, &lde_nbrs)
442 lde_send_labelmapping(ln, fn, 1);
443 }
444
445 /* if no label created yet then don't try to program labeled route */
446 if (fn->local_label == NO_LABEL)
447 return;
448
449 LIST_FOREACH(fnh, &fn->nexthops, entry) {
450 lde_send_change_klabel(fn, fnh);
451
452 switch (fn->fec.type) {
453 case FEC_TYPE_IPV4:
454 case FEC_TYPE_IPV6:
455 ln = lde_nbr_find_by_addr(fnh->af, &fnh->nexthop);
456 break;
457 case FEC_TYPE_PWID:
458 ln = lde_nbr_find_by_lsrid(fn->fec.u.pwid.lsr_id);
459 break;
460 default:
461 ln = NULL;
462 break;
463 }
464
465 if (ln) {
466 /* FEC.2 */
467 me = (struct lde_map *)fec_find(&ln->recv_map, &fn->fec);
468 if (me)
469 /* FEC.5 */
470 lde_check_mapping(&me->map, ln, 0);
471 }
472 }
473 }
474
475 void
476 lde_check_mapping(struct map *map, struct lde_nbr *ln, int rcvd_label_mapping)
477 {
478 struct fec fec;
479 struct fec_node *fn;
480 struct fec_nh *fnh;
481 struct lde_req *lre;
482 struct lde_map *me;
483 struct l2vpn_pw *pw;
484 bool send_map = false;
485
486 lde_map2fec(map, ln->id, &fec);
487
488 switch (fec.type) {
489 case FEC_TYPE_IPV4:
490 if (lde_acl_check(ldeconf->ipv4.acl_label_accept_from,
491 AF_INET, (union ldpd_addr *)&ln->id, 32) != FILTER_PERMIT)
492 return;
493 if (lde_acl_check(ldeconf->ipv4.acl_label_accept_for,
494 AF_INET, (union ldpd_addr *)&fec.u.ipv4.prefix,
495 fec.u.ipv4.prefixlen) != FILTER_PERMIT)
496 return;
497 break;
498 case FEC_TYPE_IPV6:
499 if (lde_acl_check(ldeconf->ipv6.acl_label_accept_from,
500 AF_INET, (union ldpd_addr *)&ln->id, 32) != FILTER_PERMIT)
501 return;
502 if (lde_acl_check(ldeconf->ipv6.acl_label_accept_for,
503 AF_INET6, (union ldpd_addr *)&fec.u.ipv6.prefix,
504 fec.u.ipv6.prefixlen) != FILTER_PERMIT)
505 return;
506 break;
507 default:
508 break;
509 }
510
511 fn = (struct fec_node *)fec_find(&ft, &fec);
512 if (fn == NULL)
513 fn = fec_add(&fec);
514
515 /* LMp.1: first check if we have a pending request running */
516 lre = (struct lde_req *)fec_find(&ln->sent_req, &fn->fec);
517 if (lre)
518 /* LMp.2: delete record of outstanding label request */
519 lde_req_del(ln, lre, 1);
520
521 /* RFC 4447 control word and status tlv negotiation */
522 if (map->type == MAP_TYPE_PWID && l2vpn_pw_negotiate(ln, fn, map)) {
523 if (rcvd_label_mapping && map->flags & F_MAP_PW_STATUS)
524 fn->pw_remote_status = map->pw_status;
525
526 return;
527 }
528
529 /*
530 * LMp.3 - LMp.8: loop detection - unnecessary for frame-mode
531 * mpls networks.
532 */
533
534 /* LMp.9 */
535 me = (struct lde_map *)fec_find(&ln->recv_map, &fn->fec);
536 if (me) {
537 /* LMp.10 */
538 if (me->map.label != map->label && lre == NULL) {
539 /* LMp.10a */
540 lde_send_labelrelease(ln, fn, NULL, me->map.label);
541
542 /*
543 * Can not use lde_nbr_find_by_addr() because there's
544 * the possibility of multipath.
545 */
546 LIST_FOREACH(fnh, &fn->nexthops, entry) {
547 if (lde_address_find(ln, fnh->af,
548 &fnh->nexthop) == NULL)
549 continue;
550
551 lde_send_delete_klabel(fn, fnh);
552 fnh->remote_label = NO_LABEL;
553 }
554 }
555 }
556
557 /*
558 * LMp.11 - 12: consider multiple nexthops in order to
559 * support multipath
560 */
561 LIST_FOREACH(fnh, &fn->nexthops, entry) {
562 /* LMp.15: install FEC in FIB */
563 switch (fec.type) {
564 case FEC_TYPE_IPV4:
565 case FEC_TYPE_IPV6:
566 if (!lde_address_find(ln, fnh->af, &fnh->nexthop))
567 continue;
568
569 /*
570 * Ordered Control: labelmap msg received from
571 * NH so clear flag and send labelmap msg to
572 * peer
573 */
574 if (ldeconf->flags & F_LDPD_ORDERED_CONTROL) {
575 send_map = true;
576 fnh->flags &= ~F_FEC_NH_DEFER;
577 }
578 fnh->remote_label = map->label;
579 if (fn->local_label != NO_LABEL)
580 lde_send_change_klabel(fn, fnh);
581 break;
582 case FEC_TYPE_PWID:
583 pw = (struct l2vpn_pw *) fn->data;
584 if (pw == NULL)
585 continue;
586
587 pw->remote_group = map->fec.pwid.group_id;
588 if (map->flags & F_MAP_PW_IFMTU)
589 pw->remote_mtu = map->fec.pwid.ifmtu;
590 if (rcvd_label_mapping && map->flags & F_MAP_PW_STATUS) {
591 pw->remote_status = map->pw_status;
592 fn->pw_remote_status = map->pw_status;
593 }
594 else
595 pw->remote_status = PW_FORWARDING;
596 fnh->remote_label = map->label;
597 if (l2vpn_pw_ok(pw, fnh))
598 lde_send_change_klabel(fn, fnh);
599 break;
600 default:
601 break;
602 }
603 }
604 /* LMp.13 & LMp.16: Record the mapping from this peer */
605 if (me == NULL)
606 me = lde_map_add(ln, fn, 0);
607 me->map = *map;
608
609 /*
610 * LMp.17 - LMp.27 are unnecessary since we don't need to implement
611 * loop detection. LMp.28 - LMp.30 are unnecessary because we are
612 * merging capable.
613 */
614
615 /*
616 * Ordered Control: just received a labelmap for this fec from NH so
617 * need to send labelmap to all peers
618 * LMp.20 - LMp21 Execute procedure to send Label Mapping
619 */
620 if (send_map && fn->local_label != NO_LABEL)
621 RB_FOREACH(ln, nbr_tree, &lde_nbrs)
622 lde_send_labelmapping(ln, fn, 1);
623 }
624
625 void
626 lde_check_request(struct map *map, struct lde_nbr *ln)
627 {
628 struct fec fec;
629 struct lde_req *lre;
630 struct fec_node *fn;
631 struct fec_nh *fnh;
632
633 /* wildcard label request */
634 if (map->type == MAP_TYPE_TYPED_WCARD) {
635 lde_check_request_wcard(map, ln);
636 return;
637 }
638
639 /* LRq.1: skip loop detection (not necessary) */
640
641 /* LRq.2: is there a next hop for fec? */
642 lde_map2fec(map, ln->id, &fec);
643 fn = (struct fec_node *)fec_find(&ft, &fec);
644 if (fn == NULL || LIST_EMPTY(&fn->nexthops)) {
645 /* LRq.5: send No Route notification */
646 lde_send_notification(ln, S_NO_ROUTE, map->msg_id,
647 htons(MSG_TYPE_LABELREQUEST));
648 return;
649 }
650
651 /* LRq.3: is MsgSource the next hop? */
652 LIST_FOREACH(fnh, &fn->nexthops, entry) {
653 switch (fec.type) {
654 case FEC_TYPE_IPV4:
655 case FEC_TYPE_IPV6:
656 if (!lde_address_find(ln, fnh->af, &fnh->nexthop))
657 continue;
658
659 /* LRq.4: send Loop Detected notification */
660 lde_send_notification(ln, S_LOOP_DETECTED, map->msg_id,
661 htons(MSG_TYPE_LABELREQUEST));
662 return;
663 default:
664 break;
665 }
666 }
667
668 /* LRq.6: first check if we have a pending request running */
669 lre = (struct lde_req *)fec_find(&ln->recv_req, &fn->fec);
670 if (lre != NULL)
671 /* LRq.7: duplicate request */
672 return;
673
674 /* LRq.8: record label request */
675 lre = lde_req_add(ln, &fn->fec, 0);
676 if (lre != NULL)
677 lre->msg_id = ntohl(map->msg_id);
678
679 /* LRq.9: perform LSR label distribution */
680 lde_send_labelmapping(ln, fn, 1);
681
682 /*
683 * LRq.10: do nothing (Request Never) since we use liberal
684 * label retention.
685 * LRq.11 - 12 are unnecessary since we are merging capable.
686 */
687 }
688
689 void
690 lde_check_request_wcard(struct map *map, struct lde_nbr *ln)
691 {
692 struct fec *f;
693 struct fec_node *fn;
694 struct lde_req *lre;
695
696 RB_FOREACH(f, fec_tree, &ft) {
697 fn = (struct fec_node *)f;
698
699 /* only a typed wildcard is possible here */
700 if (lde_wildcard_apply(map, &fn->fec, NULL) == 0)
701 continue;
702
703 /* LRq.2: is there a next hop for fec? */
704 if (LIST_EMPTY(&fn->nexthops))
705 continue;
706
707 /* LRq.6: first check if we have a pending request running */
708 lre = (struct lde_req *)fec_find(&ln->recv_req, &fn->fec);
709 if (lre != NULL)
710 /* LRq.7: duplicate request */
711 continue;
712
713 /* LRq.8: record label request */
714 lre = lde_req_add(ln, &fn->fec, 0);
715 if (lre != NULL)
716 lre->msg_id = ntohl(map->msg_id);
717
718 /* LRq.9: perform LSR label distribution */
719 lde_send_labelmapping(ln, fn, 1);
720 }
721 }
722
723 void
724 lde_check_release(struct map *map, struct lde_nbr *ln)
725 {
726 struct fec fec;
727 struct fec_node *fn;
728 struct lde_wdraw *lw;
729 struct lde_map *me;
730 struct fec *pending_map;
731
732 /* wildcard label release */
733 if (map->type == MAP_TYPE_WILDCARD ||
734 map->type == MAP_TYPE_TYPED_WCARD ||
735 (map->type == MAP_TYPE_PWID && !(map->flags & F_MAP_PW_ID))) {
736 lde_check_release_wcard(map, ln);
737 return;
738 }
739
740 lde_map2fec(map, ln->id, &fec);
741 fn = (struct fec_node *)fec_find(&ft, &fec);
742 /* LRl.1: does FEC match a known FEC? */
743 if (fn == NULL)
744 return;
745
746 /* LRl.6: check sent map list and remove it if available */
747 me = (struct lde_map *)fec_find(&ln->sent_map, &fn->fec);
748 if (me && (map->label == NO_LABEL || map->label == me->map.label))
749 lde_map_del(ln, me, 1);
750
751 /* LRl.3: first check if we have a pending withdraw running */
752 lw = (struct lde_wdraw *)fec_find(&ln->sent_wdraw, &fn->fec);
753 if (lw && (map->label == NO_LABEL || map->label == lw->label)) {
754 /* LRl.4: delete record of outstanding label withdraw */
755 lde_wdraw_del(ln, lw);
756
757 /* send pending label mapping if any */
758 pending_map = fec_find(&ln->sent_map_pending, &fn->fec);
759 if (pending_map) {
760 lde_send_labelmapping(ln, fn, 1);
761 lde_map_pending_del(ln, pending_map);
762 }
763 }
764
765 /*
766 * LRl.11 - 13 are unnecessary since we remove the label from
767 * forwarding/switching as soon as the FEC is unreachable.
768 */
769 }
770
771 void
772 lde_check_release_wcard(struct map *map, struct lde_nbr *ln)
773 {
774 struct fec *f;
775 struct fec_node *fn;
776 struct lde_wdraw *lw;
777 struct lde_map *me;
778 struct fec *pending_map;
779
780 RB_FOREACH(f, fec_tree, &ft) {
781 fn = (struct fec_node *)f;
782 me = (struct lde_map *)fec_find(&ln->sent_map, &fn->fec);
783
784 /* LRl.1: does FEC match a known FEC? */
785 if (lde_wildcard_apply(map, &fn->fec, me) == 0)
786 continue;
787
788 /* LRl.6: check sent map list and remove it if available */
789 if (me &&
790 (map->label == NO_LABEL || map->label == me->map.label))
791 lde_map_del(ln, me, 1);
792
793 /* LRl.3: first check if we have a pending withdraw running */
794 lw = (struct lde_wdraw *)fec_find(&ln->sent_wdraw, &fn->fec);
795 if (lw && (map->label == NO_LABEL || map->label == lw->label)) {
796 /* LRl.4: delete record of outstanding lbl withdraw */
797 lde_wdraw_del(ln, lw);
798
799 /* send pending label mapping if any */
800 pending_map = fec_find(&ln->sent_map_pending, &fn->fec);
801 if (pending_map) {
802 lde_send_labelmapping(ln, fn, 1);
803 lde_map_pending_del(ln, pending_map);
804 }
805 }
806
807 /*
808 * LRl.11 - 13 are unnecessary since we remove the label from
809 * forwarding/switching as soon as the FEC is unreachable.
810 */
811 }
812 }
813
814 void
815 lde_check_withdraw(struct map *map, struct lde_nbr *ln)
816 {
817 struct fec fec;
818 struct fec_node *fn;
819 struct fec_nh *fnh;
820 struct lde_map *me;
821 struct l2vpn_pw *pw;
822 struct lde_nbr *lnbr;
823
824 /* wildcard label withdraw */
825 if (map->type == MAP_TYPE_WILDCARD ||
826 map->type == MAP_TYPE_TYPED_WCARD ||
827 (map->type == MAP_TYPE_PWID && !(map->flags & F_MAP_PW_ID))) {
828 lde_check_withdraw_wcard(map, ln);
829 return;
830 }
831
832 lde_map2fec(map, ln->id, &fec);
833 fn = (struct fec_node *)fec_find(&ft, &fec);
834 if (fn == NULL)
835 fn = fec_add(&fec);
836
837 /* LWd.1: remove label from forwarding/switching use */
838 LIST_FOREACH(fnh, &fn->nexthops, entry) {
839 switch (fec.type) {
840 case FEC_TYPE_IPV4:
841 case FEC_TYPE_IPV6:
842 if (!lde_address_find(ln, fnh->af, &fnh->nexthop))
843 continue;
844 break;
845 case FEC_TYPE_PWID:
846 pw = (struct l2vpn_pw *) fn->data;
847 if (pw == NULL)
848 continue;
849 pw->remote_status = PW_NOT_FORWARDING;
850 break;
851 default:
852 break;
853 }
854 if (map->label != NO_LABEL && map->label != fnh->remote_label)
855 continue;
856
857 lde_send_delete_klabel(fn, fnh);
858 fnh->remote_label = NO_LABEL;
859 }
860
861 /* LWd.2: send label release */
862 lde_send_labelrelease(ln, fn, NULL, map->label);
863
864 /* LWd.3: check previously received label mapping */
865 me = (struct lde_map *)fec_find(&ln->recv_map, &fn->fec);
866 if (me && (map->label == NO_LABEL || map->label == me->map.label))
867 /* LWd.4: remove record of previously received lbl mapping */
868 lde_map_del(ln, me, 0);
869 else
870 /* LWd.13 done */
871 return;
872
873 /* Ordered Control: additional withdraw steps */
874 if (ldeconf->flags & F_LDPD_ORDERED_CONTROL) {
875 /* LWd.8: for each neighbor other that src of withdraw msg */
876 RB_FOREACH(lnbr, nbr_tree, &lde_nbrs) {
877 if (ln->peerid == lnbr->peerid)
878 continue;
879
880 /* LWd.9: check if previously sent a label mapping */
881 me = (struct lde_map *)fec_find(&lnbr->sent_map,
882 &fn->fec);
883
884 /*
885 * LWd.10: does label sent to peer "map" to withdraw
886 * label
887 */
888 if (me && lde_nbr_is_nexthop(fn, lnbr))
889 /* LWd.11: send label withdraw */
890 lde_send_labelwithdraw(lnbr, fn, NULL, NULL);
891 }
892 }
893
894 }
895
896 void
897 lde_check_withdraw_wcard(struct map *map, struct lde_nbr *ln)
898 {
899 struct fec *f;
900 struct fec_node *fn;
901 struct fec_nh *fnh;
902 struct lde_map *me;
903 struct l2vpn_pw *pw;
904 struct lde_nbr *lnbr;
905
906 /* LWd.2: send label release */
907 lde_send_labelrelease(ln, NULL, map, map->label);
908
909 RB_FOREACH(f, fec_tree, &ft) {
910 fn = (struct fec_node *)f;
911 me = (struct lde_map *)fec_find(&ln->recv_map, &fn->fec);
912
913 if (lde_wildcard_apply(map, &fn->fec, me) == 0)
914 continue;
915
916 /* LWd.1: remove label from forwarding/switching use */
917 LIST_FOREACH(fnh, &fn->nexthops, entry) {
918 switch (f->type) {
919 case FEC_TYPE_IPV4:
920 case FEC_TYPE_IPV6:
921 if (!lde_address_find(ln, fnh->af,
922 &fnh->nexthop))
923 continue;
924 break;
925 case FEC_TYPE_PWID:
926 if (f->u.pwid.lsr_id.s_addr != ln->id.s_addr)
927 continue;
928 pw = (struct l2vpn_pw *) fn->data;
929 if (pw)
930 pw->remote_status = PW_NOT_FORWARDING;
931 break;
932 default:
933 break;
934 }
935 if (map->label != NO_LABEL && map->label !=
936 fnh->remote_label)
937 continue;
938
939 lde_send_delete_klabel(fn, fnh);
940 fnh->remote_label = NO_LABEL;
941 }
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 int
1030 lde_gc_timer(struct thread *thread)
1031 {
1032 struct fec *fec, *safe;
1033 struct fec_node *fn;
1034 int count = 0;
1035
1036 RB_FOREACH_SAFE(fec, fec_tree, &ft, safe) {
1037 fn = (struct fec_node *) fec;
1038
1039 if (!LIST_EMPTY(&fn->nexthops) ||
1040 !RB_EMPTY(lde_map_head, &fn->downstream) ||
1041 !RB_EMPTY(lde_map_head, &fn->upstream))
1042 continue;
1043
1044 if (fn->local_label != NO_LABEL)
1045 lde_free_label(fn->local_label);
1046
1047 fec_remove(&ft, &fn->fec);
1048 free(fn);
1049 count++;
1050 }
1051
1052 if (count > 0)
1053 log_debug("%s: %u entries removed", __func__, count);
1054
1055 lde_gc_start_timer();
1056
1057 return (0);
1058 }
1059
1060 void
1061 lde_gc_start_timer(void)
1062 {
1063 THREAD_TIMER_OFF(gc_timer);
1064 gc_timer = NULL;
1065 thread_add_timer(master, lde_gc_timer, NULL, LDE_GC_INTERVAL,
1066 &gc_timer);
1067 }
1068
1069 void
1070 lde_gc_stop_timer(void)
1071 {
1072 THREAD_TIMER_OFF(gc_timer);
1073 }
FRRouting mirror