1 /* $OpenBSD: lde_lib.c,v 1.69 2017/03/04 00:15:35 renato Exp $ */ 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 <sys/types.h> 21 #include <sys/socket.h> 22 #include <netmpls/mpls.h> 23 #include <stdlib.h> 24 #include <string.h> 25 #include <limits.h> 26 27 #include "ldpd.h" 28 #include "lde.h" 29 #include "ldpe.h" 30 #include "log.h" 31 32 static __inline int fec_compare(struct fec *, struct fec *); 33 static int lde_nbr_is_nexthop(struct fec_node *, 34 struct lde_nbr *); 35 static void fec_free(void *); 36 static struct fec_node *fec_add(struct fec *fec); 37 static struct fec_nh *fec_nh_add(struct fec_node *, int, union ldpd_addr *, 38 uint8_t priority); 39 static void fec_nh_del(struct fec_nh *); 40 41 RB_GENERATE(fec_tree, fec, entry, fec_compare) 42 43 struct fec_tree ft = RB_INITIALIZER(&ft); 44 struct event gc_timer; 45 46 /* FEC tree functions */ 47 void 48 fec_init(struct fec_tree *fh) 49 { 50 RB_INIT(fh); 51 } 52 53 static __inline int 54 fec_compare(struct fec *a, struct fec *b) 55 { 56 if (a->type < b->type) 57 return (-1); 58 if (a->type > b->type) 59 return (1); 60 61 switch (a->type) { 62 case FEC_TYPE_IPV4: 63 if (ntohl(a->u.ipv4.prefix.s_addr) < 64 ntohl(b->u.ipv4.prefix.s_addr)) 65 return (-1); 66 if (ntohl(a->u.ipv4.prefix.s_addr) > 67 ntohl(b->u.ipv4.prefix.s_addr)) 68 return (1); 69 if (a->u.ipv4.prefixlen < b->u.ipv4.prefixlen) 70 return (-1); 71 if (a->u.ipv4.prefixlen > b->u.ipv4.prefixlen) 72 return (1); 73 return (0); 74 case FEC_TYPE_IPV6: 75 if (memcmp(&a->u.ipv6.prefix, &b->u.ipv6.prefix, 76 sizeof(struct in6_addr)) < 0) 77 return (-1); 78 if (memcmp(&a->u.ipv6.prefix, &b->u.ipv6.prefix, 79 sizeof(struct in6_addr)) > 0) 80 return (1); 81 if (a->u.ipv6.prefixlen < b->u.ipv6.prefixlen) 82 return (-1); 83 if (a->u.ipv6.prefixlen > b->u.ipv6.prefixlen) 84 return (1); 85 return (0); 86 case FEC_TYPE_PWID: 87 if (a->u.pwid.type < b->u.pwid.type) 88 return (-1); 89 if (a->u.pwid.type > b->u.pwid.type) 90 return (1); 91 if (a->u.pwid.pwid < b->u.pwid.pwid) 92 return (-1); 93 if (a->u.pwid.pwid > b->u.pwid.pwid) 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 if (ntohl(a->u.pwid.lsr_id.s_addr) > 99 ntohl(b->u.pwid.lsr_id.s_addr)) 100 return (1); 101 return (0); 102 } 103 104 return (-1); 105 } 106 107 struct fec * 108 fec_find(struct fec_tree *fh, struct fec *f) 109 { 110 return (RB_FIND(fec_tree, fh, f)); 111 } 112 113 int 114 fec_insert(struct fec_tree *fh, struct fec *f) 115 { 116 if (RB_INSERT(fec_tree, fh, f) != NULL) 117 return (-1); 118 return (0); 119 } 120 121 int 122 fec_remove(struct fec_tree *fh, struct fec *f) 123 { 124 if (RB_REMOVE(fec_tree, fh, f) == NULL) { 125 log_warnx("%s failed for %s", __func__, log_fec(f)); 126 return (-1); 127 } 128 return (0); 129 } 130 131 void 132 fec_clear(struct fec_tree *fh, void (*free_cb)(void *)) 133 { 134 struct fec *f; 135 136 while ((f = RB_ROOT(fh)) != NULL) { 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 LIST_EMPTY(&fn->downstream)) 167 continue; 168 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 LIST_FOREACH(me, &fn->downstream, entry) { 186 rtctl.in_use = lde_nbr_is_nexthop(fn, me->nexthop); 187 rtctl.nexthop = me->nexthop->id; 188 rtctl.remote_label = me->map.label; 189 190 lde_imsg_compose_ldpe(IMSG_CTL_SHOW_LIB, 0, pid, 191 &rtctl, sizeof(rtctl)); 192 } 193 if (LIST_EMPTY(&fn->downstream)) { 194 rtctl.in_use = 0; 195 rtctl.nexthop.s_addr = INADDR_ANY; 196 rtctl.remote_label = NO_LABEL; 197 198 lde_imsg_compose_ldpe(IMSG_CTL_SHOW_LIB, 0, pid, 199 &rtctl, sizeof(rtctl)); 200 } 201 } 202 } 203 204 void 205 fec_snap(struct lde_nbr *ln) 206 { 207 struct fec *f; 208 struct fec_node *fn; 209 210 RB_FOREACH(f, fec_tree, &ft) { 211 fn = (struct fec_node *)f; 212 if (fn->local_label == NO_LABEL) 213 continue; 214 215 lde_send_labelmapping(ln, fn, 0); 216 } 217 218 lde_imsg_compose_ldpe(IMSG_MAPPING_ADD_END, ln->peerid, 0, NULL, 0); 219 220 /* 221 * RFC 5919 - Section 4: 222 * "An LDP speaker that conforms to this specification SHOULD signal 223 * completion of its label advertisements to a peer by means of a 224 * Notification message, if its peer has advertised the Unrecognized 225 * Notification capability during session establishment. The LDP 226 * speaker SHOULD send the Notification message (per Forwarding 227 * Equivalence Class (FEC) Type) to a peer even if the LDP speaker has 228 * zero Label bindings to advertise to that peer". 229 */ 230 if (ln->flags & F_NBR_CAP_UNOTIF) { 231 lde_send_notification_eol_prefix(ln, AF_INET); 232 lde_send_notification_eol_prefix(ln, AF_INET6); 233 lde_send_notification_eol_pwid(ln, PW_TYPE_WILDCARD); 234 } 235 } 236 237 static void 238 fec_free(void *arg) 239 { 240 struct fec_node *fn = arg; 241 struct fec_nh *fnh; 242 243 while ((fnh = LIST_FIRST(&fn->nexthops))) 244 fec_nh_del(fnh); 245 if (!LIST_EMPTY(&fn->downstream)) 246 log_warnx("%s: fec %s downstream list not empty", __func__, 247 log_fec(&fn->fec)); 248 if (!LIST_EMPTY(&fn->upstream)) 249 log_warnx("%s: fec %s upstream list not empty", __func__, 250 log_fec(&fn->fec)); 251 252 free(fn); 253 } 254 255 void 256 fec_tree_clear(void) 257 { 258 fec_clear(&ft, fec_free); 259 } 260 261 static struct fec_node * 262 fec_add(struct fec *fec) 263 { 264 struct fec_node *fn; 265 266 fn = calloc(1, sizeof(*fn)); 267 if (fn == NULL) 268 fatal(__func__); 269 270 fn->fec = *fec; 271 fn->local_label = NO_LABEL; 272 LIST_INIT(&fn->upstream); 273 LIST_INIT(&fn->downstream); 274 LIST_INIT(&fn->nexthops); 275 276 if (fec_insert(&ft, &fn->fec)) 277 log_warnx("failed to add %s to ft tree", 278 log_fec(&fn->fec)); 279 280 return (fn); 281 } 282 283 struct fec_nh * 284 fec_nh_find(struct fec_node *fn, int af, union ldpd_addr *nexthop, 285 uint8_t priority) 286 { 287 struct fec_nh *fnh; 288 289 LIST_FOREACH(fnh, &fn->nexthops, entry) 290 if (fnh->af == af && 291 ldp_addrcmp(af, &fnh->nexthop, nexthop) == 0 && 292 fnh->priority == priority) 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 uint8_t priority) 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->remote_label = NO_LABEL; 311 fnh->priority = priority; 312 LIST_INSERT_HEAD(&fn->nexthops, fnh, entry); 313 314 return (fnh); 315 } 316 317 static void 318 fec_nh_del(struct fec_nh *fnh) 319 { 320 LIST_REMOVE(fnh, entry); 321 free(fnh); 322 } 323 324 uint32_t 325 egress_label(enum fec_type fec_type) 326 { 327 switch (fec_type) { 328 case FEC_TYPE_IPV4: 329 if (ldeconf->ipv4.flags & F_LDPD_AF_EXPNULL) 330 return (MPLS_LABEL_IPV4NULL); 331 break; 332 case FEC_TYPE_IPV6: 333 if (ldeconf->ipv6.flags & F_LDPD_AF_EXPNULL) 334 return (MPLS_LABEL_IPV6NULL); 335 break; 336 default: 337 fatalx("egress_label: unexpected fec type"); 338 } 339 340 return (MPLS_LABEL_IMPLNULL); 341 } 342 343 void 344 lde_kernel_insert(struct fec *fec, int af, union ldpd_addr *nexthop, 345 uint8_t priority, int connected, void *data) 346 { 347 struct fec_node *fn; 348 struct fec_nh *fnh; 349 struct lde_map *me; 350 struct lde_nbr *ln; 351 352 fn = (struct fec_node *)fec_find(&ft, fec); 353 if (fn == NULL) 354 fn = fec_add(fec); 355 if (fec_nh_find(fn, af, nexthop, priority) != NULL) 356 return; 357 358 log_debug("lde add fec %s nexthop %s", 359 log_fec(&fn->fec), log_addr(af, nexthop)); 360 361 if (fn->fec.type == FEC_TYPE_PWID) 362 fn->data = data; 363 364 if (fn->local_label == NO_LABEL) { 365 if (connected) 366 fn->local_label = egress_label(fn->fec.type); 367 else 368 fn->local_label = lde_assign_label(); 369 370 /* FEC.1: perform lsr label distribution procedure */ 371 RB_FOREACH(ln, nbr_tree, &lde_nbrs) 372 lde_send_labelmapping(ln, fn, 1); 373 } 374 375 fnh = fec_nh_add(fn, af, nexthop, priority); 376 lde_send_change_klabel(fn, fnh); 377 378 switch (fn->fec.type) { 379 case FEC_TYPE_IPV4: 380 case FEC_TYPE_IPV6: 381 ln = lde_nbr_find_by_addr(af, &fnh->nexthop); 382 break; 383 case FEC_TYPE_PWID: 384 ln = lde_nbr_find_by_lsrid(fn->fec.u.pwid.lsr_id); 385 break; 386 default: 387 ln = NULL; 388 break; 389 } 390 391 if (ln) { 392 /* FEC.2 */ 393 me = (struct lde_map *)fec_find(&ln->recv_map, &fn->fec); 394 if (me) 395 /* FEC.5 */ 396 lde_check_mapping(&me->map, ln); 397 } 398 } 399 400 void 401 lde_kernel_remove(struct fec *fec, int af, union ldpd_addr *nexthop, 402 uint8_t priority) 403 { 404 struct fec_node *fn; 405 struct fec_nh *fnh; 406 struct lde_nbr *ln; 407 408 fn = (struct fec_node *)fec_find(&ft, fec); 409 if (fn == NULL) 410 /* route lost */ 411 return; 412 fnh = fec_nh_find(fn, af, nexthop, priority); 413 if (fnh == NULL) 414 /* route lost */ 415 return; 416 417 log_debug("lde remove fec %s nexthop %s", 418 log_fec(&fn->fec), log_addr(af, nexthop)); 419 420 lde_send_delete_klabel(fn, fnh); 421 fec_nh_del(fnh); 422 if (LIST_EMPTY(&fn->nexthops)) { 423 RB_FOREACH(ln, nbr_tree, &lde_nbrs) 424 lde_send_labelwithdraw(ln, fn, NULL, NULL); 425 fn->local_label = NO_LABEL; 426 if (fn->fec.type == FEC_TYPE_PWID) 427 fn->data = NULL; 428 } 429 } 430 431 void 432 lde_check_mapping(struct map *map, struct lde_nbr *ln) 433 { 434 struct fec fec; 435 struct fec_node *fn; 436 struct fec_nh *fnh; 437 struct lde_req *lre; 438 struct lde_map *me; 439 struct l2vpn_pw *pw; 440 int msgsource = 0; 441 442 lde_map2fec(map, ln->id, &fec); 443 fn = (struct fec_node *)fec_find(&ft, &fec); 444 if (fn == NULL) 445 fn = fec_add(&fec); 446 447 /* LMp.1: first check if we have a pending request running */ 448 lre = (struct lde_req *)fec_find(&ln->sent_req, &fn->fec); 449 if (lre) 450 /* LMp.2: delete record of outstanding label request */ 451 lde_req_del(ln, lre, 1); 452 453 /* RFC 4447 control word and status tlv negotiation */ 454 if (map->type == MAP_TYPE_PWID && l2vpn_pw_negotiate(ln, fn, map)) 455 return; 456 457 /* 458 * LMp.3 - LMp.8: loop detection - unnecessary for frame-mode 459 * mpls networks. 460 */ 461 462 /* LMp.9 */ 463 me = (struct lde_map *)fec_find(&ln->recv_map, &fn->fec); 464 if (me) { 465 /* LMp.10 */ 466 if (me->map.label != map->label && lre == NULL) { 467 /* LMp.10a */ 468 lde_send_labelrelease(ln, fn, NULL, me->map.label); 469 470 /* 471 * Can not use lde_nbr_find_by_addr() because there's 472 * the possibility of multipath. 473 */ 474 LIST_FOREACH(fnh, &fn->nexthops, entry) { 475 if (lde_address_find(ln, fnh->af, 476 &fnh->nexthop) == NULL) 477 continue; 478 479 lde_send_delete_klabel(fn, fnh); 480 fnh->remote_label = NO_LABEL; 481 } 482 } 483 } 484 485 /* 486 * LMp.11 - 12: consider multiple nexthops in order to 487 * support multipath 488 */ 489 LIST_FOREACH(fnh, &fn->nexthops, entry) { 490 /* LMp.15: install FEC in FIB */ 491 switch (fec.type) { 492 case FEC_TYPE_IPV4: 493 case FEC_TYPE_IPV6: 494 if (!lde_address_find(ln, fnh->af, &fnh->nexthop)) 495 continue; 496 497 fnh->remote_label = map->label; 498 lde_send_change_klabel(fn, fnh); 499 break; 500 case FEC_TYPE_PWID: 501 pw = (struct l2vpn_pw *) fn->data; 502 if (pw == NULL) 503 continue; 504 505 pw->remote_group = map->fec.pwid.group_id; 506 if (map->flags & F_MAP_PW_IFMTU) 507 pw->remote_mtu = map->fec.pwid.ifmtu; 508 if (map->flags & F_MAP_PW_STATUS) 509 pw->remote_status = map->pw_status; 510 fnh->remote_label = map->label; 511 if (l2vpn_pw_ok(pw, fnh)) 512 lde_send_change_klabel(fn, fnh); 513 break; 514 default: 515 break; 516 } 517 518 msgsource = 1; 519 } 520 /* LMp.13 & LMp.16: Record the mapping from this peer */ 521 if (me == NULL) 522 me = lde_map_add(ln, fn, 0); 523 me->map = *map; 524 525 if (msgsource == 0) 526 /* LMp.13: just return since we use liberal lbl retention */ 527 return; 528 529 /* 530 * LMp.17 - LMp.27 are unnecessary since we don't need to implement 531 * loop detection. LMp.28 - LMp.30 are unnecessary because we are 532 * merging capable. 533 */ 534 } 535 536 void 537 lde_check_request(struct map *map, struct lde_nbr *ln) 538 { 539 struct fec fec; 540 struct lde_req *lre; 541 struct fec_node *fn; 542 struct fec_nh *fnh; 543 544 /* wildcard label request */ 545 if (map->type == MAP_TYPE_TYPED_WCARD) { 546 lde_check_request_wcard(map, ln); 547 return; 548 } 549 550 /* LRq.1: skip loop detection (not necessary) */ 551 552 /* LRq.2: is there a next hop for fec? */ 553 lde_map2fec(map, ln->id, &fec); 554 fn = (struct fec_node *)fec_find(&ft, &fec); 555 if (fn == NULL || LIST_EMPTY(&fn->nexthops)) { 556 /* LRq.5: send No Route notification */ 557 lde_send_notification(ln, S_NO_ROUTE, map->msg_id, 558 htons(MSG_TYPE_LABELREQUEST)); 559 return; 560 } 561 562 /* LRq.3: is MsgSource the next hop? */ 563 LIST_FOREACH(fnh, &fn->nexthops, entry) { 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 /* LRq.4: send Loop Detected notification */ 571 lde_send_notification(ln, S_LOOP_DETECTED, map->msg_id, 572 htons(MSG_TYPE_LABELREQUEST)); 573 return; 574 default: 575 break; 576 } 577 } 578 579 /* LRq.6: first check if we have a pending request running */ 580 lre = (struct lde_req *)fec_find(&ln->recv_req, &fn->fec); 581 if (lre != NULL) 582 /* LRq.7: duplicate request */ 583 return; 584 585 /* LRq.8: record label request */ 586 lre = lde_req_add(ln, &fn->fec, 0); 587 if (lre != NULL) 588 lre->msg_id = ntohl(map->msg_id); 589 590 /* LRq.9: perform LSR label distribution */ 591 lde_send_labelmapping(ln, fn, 1); 592 593 /* 594 * LRq.10: do nothing (Request Never) since we use liberal 595 * label retention. 596 * LRq.11 - 12 are unnecessary since we are merging capable. 597 */ 598 } 599 600 void 601 lde_check_request_wcard(struct map *map, struct lde_nbr *ln) 602 { 603 struct fec *f; 604 struct fec_node *fn; 605 struct lde_req *lre; 606 607 RB_FOREACH(f, fec_tree, &ft) { 608 fn = (struct fec_node *)f; 609 610 /* only a typed wildcard is possible here */ 611 if (lde_wildcard_apply(map, &fn->fec, NULL) == 0) 612 continue; 613 614 /* LRq.2: is there a next hop for fec? */ 615 if (LIST_EMPTY(&fn->nexthops)) 616 continue; 617 618 /* LRq.6: first check if we have a pending request running */ 619 lre = (struct lde_req *)fec_find(&ln->recv_req, &fn->fec); 620 if (lre != NULL) 621 /* LRq.7: duplicate request */ 622 continue; 623 624 /* LRq.8: record label request */ 625 lre = lde_req_add(ln, &fn->fec, 0); 626 if (lre != NULL) 627 lre->msg_id = ntohl(map->msg_id); 628 629 /* LRq.9: perform LSR label distribution */ 630 lde_send_labelmapping(ln, fn, 1); 631 } 632 633 /* 634 * RFC 5919 - Section 5.3: 635 * "When an LDP speaker receives a Label Request message for a Typed 636 * Wildcard FEC (e.g., a particular FEC Element Type) from a peer, the 637 * LDP speaker determines the set of bindings (as per any local 638 * filtering policy) to advertise to the peer for the FEC type specified 639 * by the request. Assuming the peer had advertised the Unrecognized 640 * Notification capability at session initialization time, the speaker 641 * should send the peer an End-of-LIB Notification for the FEC type when 642 * it completes advertisement of the permitted bindings". 643 */ 644 if (ln->flags & F_NBR_CAP_UNOTIF) { 645 switch (map->fec.twcard.type) { 646 case MAP_TYPE_PREFIX: 647 lde_send_notification_eol_prefix(ln, 648 map->fec.twcard.u.prefix_af); 649 break; 650 case MAP_TYPE_PWID: 651 lde_send_notification_eol_pwid(ln, 652 map->fec.twcard.u.pw_type); 653 break; 654 default: 655 break; 656 } 657 } 658 } 659 660 void 661 lde_check_release(struct map *map, struct lde_nbr *ln) 662 { 663 struct fec fec; 664 struct fec_node *fn; 665 struct lde_wdraw *lw; 666 struct lde_map *me; 667 668 /* wildcard label release */ 669 if (map->type == MAP_TYPE_WILDCARD || 670 map->type == MAP_TYPE_TYPED_WCARD || 671 (map->type == MAP_TYPE_PWID && !(map->flags & F_MAP_PW_ID))) { 672 lde_check_release_wcard(map, ln); 673 return; 674 } 675 676 lde_map2fec(map, ln->id, &fec); 677 fn = (struct fec_node *)fec_find(&ft, &fec); 678 /* LRl.1: does FEC match a known FEC? */ 679 if (fn == NULL) 680 return; 681 682 /* LRl.3: first check if we have a pending withdraw running */ 683 lw = (struct lde_wdraw *)fec_find(&ln->sent_wdraw, &fn->fec); 684 if (lw && (map->label == NO_LABEL || map->label == lw->label)) { 685 /* LRl.4: delete record of outstanding label withdraw */ 686 lde_wdraw_del(ln, lw); 687 } 688 689 /* LRl.6: check sent map list and remove it if available */ 690 me = (struct lde_map *)fec_find(&ln->sent_map, &fn->fec); 691 if (me && (map->label == NO_LABEL || map->label == me->map.label)) 692 lde_map_del(ln, me, 1); 693 694 /* 695 * LRl.11 - 13 are unnecessary since we remove the label from 696 * forwarding/switching as soon as the FEC is unreachable. 697 */ 698 } 699 700 void 701 lde_check_release_wcard(struct map *map, struct lde_nbr *ln) 702 { 703 struct fec *f; 704 struct fec_node *fn; 705 struct lde_wdraw *lw; 706 struct lde_map *me; 707 708 RB_FOREACH(f, fec_tree, &ft) { 709 fn = (struct fec_node *)f; 710 me = (struct lde_map *)fec_find(&ln->sent_map, &fn->fec); 711 712 /* LRl.1: does FEC match a known FEC? */ 713 if (lde_wildcard_apply(map, &fn->fec, me) == 0) 714 continue; 715 716 /* LRl.3: first check if we have a pending withdraw running */ 717 lw = (struct lde_wdraw *)fec_find(&ln->sent_wdraw, &fn->fec); 718 if (lw && (map->label == NO_LABEL || map->label == lw->label)) { 719 /* LRl.4: delete record of outstanding lbl withdraw */ 720 lde_wdraw_del(ln, lw); 721 } 722 723 /* LRl.6: check sent map list and remove it if available */ 724 if (me && 725 (map->label == NO_LABEL || map->label == me->map.label)) 726 lde_map_del(ln, me, 1); 727 728 /* 729 * LRl.11 - 13 are unnecessary since we remove the label from 730 * forwarding/switching as soon as the FEC is unreachable. 731 */ 732 } 733 } 734 735 void 736 lde_check_withdraw(struct map *map, struct lde_nbr *ln) 737 { 738 struct fec fec; 739 struct fec_node *fn; 740 struct fec_nh *fnh; 741 struct lde_map *me; 742 struct l2vpn_pw *pw; 743 744 /* wildcard label withdraw */ 745 if (map->type == MAP_TYPE_WILDCARD || 746 map->type == MAP_TYPE_TYPED_WCARD || 747 (map->type == MAP_TYPE_PWID && !(map->flags & F_MAP_PW_ID))) { 748 lde_check_withdraw_wcard(map, ln); 749 return; 750 } 751 752 lde_map2fec(map, ln->id, &fec); 753 fn = (struct fec_node *)fec_find(&ft, &fec); 754 if (fn == NULL) 755 fn = fec_add(&fec); 756 757 /* LWd.1: remove label from forwarding/switching use */ 758 LIST_FOREACH(fnh, &fn->nexthops, entry) { 759 switch (fec.type) { 760 case FEC_TYPE_IPV4: 761 case FEC_TYPE_IPV6: 762 if (!lde_address_find(ln, fnh->af, &fnh->nexthop)) 763 continue; 764 break; 765 case FEC_TYPE_PWID: 766 pw = (struct l2vpn_pw *) fn->data; 767 if (pw == NULL) 768 continue; 769 break; 770 default: 771 break; 772 } 773 if (map->label != NO_LABEL && map->label != fnh->remote_label) 774 continue; 775 776 lde_send_delete_klabel(fn, fnh); 777 fnh->remote_label = NO_LABEL; 778 } 779 780 /* LWd.2: send label release */ 781 lde_send_labelrelease(ln, fn, NULL, map->label); 782 783 /* LWd.3: check previously received label mapping */ 784 me = (struct lde_map *)fec_find(&ln->recv_map, &fn->fec); 785 if (me && (map->label == NO_LABEL || map->label == me->map.label)) 786 /* LWd.4: remove record of previously received lbl mapping */ 787 lde_map_del(ln, me, 0); 788 } 789 790 void 791 lde_check_withdraw_wcard(struct map *map, struct lde_nbr *ln) 792 { 793 struct fec *f; 794 struct fec_node *fn; 795 struct fec_nh *fnh; 796 struct lde_map *me; 797 798 /* LWd.2: send label release */ 799 lde_send_labelrelease(ln, NULL, map, map->label); 800 801 RB_FOREACH(f, fec_tree, &ft) { 802 fn = (struct fec_node *)f; 803 me = (struct lde_map *)fec_find(&ln->recv_map, &fn->fec); 804 805 if (lde_wildcard_apply(map, &fn->fec, me) == 0) 806 continue; 807 808 /* LWd.1: remove label from forwarding/switching use */ 809 LIST_FOREACH(fnh, &fn->nexthops, entry) { 810 switch (f->type) { 811 case FEC_TYPE_IPV4: 812 case FEC_TYPE_IPV6: 813 if (!lde_address_find(ln, fnh->af, 814 &fnh->nexthop)) 815 continue; 816 break; 817 case FEC_TYPE_PWID: 818 if (f->u.pwid.lsr_id.s_addr != ln->id.s_addr) 819 continue; 820 break; 821 default: 822 break; 823 } 824 if (map->label != NO_LABEL && map->label != 825 fnh->remote_label) 826 continue; 827 828 lde_send_delete_klabel(fn, fnh); 829 fnh->remote_label = NO_LABEL; 830 } 831 832 /* LWd.3: check previously received label mapping */ 833 if (me && (map->label == NO_LABEL || 834 map->label == me->map.label)) 835 /* 836 * LWd.4: remove record of previously received 837 * label mapping 838 */ 839 lde_map_del(ln, me, 0); 840 } 841 } 842 843 int 844 lde_wildcard_apply(struct map *wcard, struct fec *fec, struct lde_map *me) 845 { 846 switch (wcard->type) { 847 case MAP_TYPE_WILDCARD: 848 /* full wildcard */ 849 return (1); 850 case MAP_TYPE_TYPED_WCARD: 851 switch (wcard->fec.twcard.type) { 852 case MAP_TYPE_PREFIX: 853 if (wcard->fec.twcard.u.prefix_af == AF_INET && 854 fec->type != FEC_TYPE_IPV4) 855 return (0); 856 if (wcard->fec.twcard.u.prefix_af == AF_INET6 && 857 fec->type != FEC_TYPE_IPV6) 858 return (0); 859 return (1); 860 case MAP_TYPE_PWID: 861 if (fec->type != FEC_TYPE_PWID) 862 return (0); 863 if (wcard->fec.twcard.u.pw_type != PW_TYPE_WILDCARD && 864 wcard->fec.twcard.u.pw_type != fec->u.pwid.type) 865 return (0); 866 return (1); 867 default: 868 fatalx("lde_wildcard_apply: unexpected fec type"); 869 } 870 break; 871 case MAP_TYPE_PWID: 872 /* RFC4447 pw-id group wildcard */ 873 if (fec->type != FEC_TYPE_PWID) 874 return (0); 875 if (fec->u.pwid.type != wcard->fec.pwid.type) 876 return (0); 877 if (me == NULL || (me->map.fec.pwid.group_id != 878 wcard->fec.pwid.group_id)) 879 return (0); 880 return (1); 881 default: 882 fatalx("lde_wildcard_apply: unexpected fec type"); 883 } 884 } 885 886 /* gabage collector timer: timer to remove dead entries from the LIB */ 887 888 /* ARGSUSED */ 889 void 890 lde_gc_timer(int fd, short event, void *arg) 891 { 892 struct fec *fec, *safe; 893 struct fec_node *fn; 894 int count = 0; 895 896 RB_FOREACH_SAFE(fec, fec_tree, &ft, safe) { 897 fn = (struct fec_node *) fec; 898 899 if (!LIST_EMPTY(&fn->nexthops) || 900 !LIST_EMPTY(&fn->downstream) || 901 !LIST_EMPTY(&fn->upstream)) 902 continue; 903 904 fec_remove(&ft, &fn->fec); 905 free(fn); 906 count++; 907 } 908 909 if (count > 0) 910 log_debug("%s: %u entries removed", __func__, count); 911 912 lde_gc_start_timer(); 913 } 914 915 void 916 lde_gc_start_timer(void) 917 { 918 struct timeval tv; 919 920 timerclear(&tv); 921 tv.tv_sec = LDE_GC_INTERVAL; 922 if (evtimer_add(&gc_timer, &tv) == -1) 923 fatal(__func__); 924 } 925 926 void 927 lde_gc_stop_timer(void) 928 { 929 if (evtimer_pending(&gc_timer, NULL) && 930 evtimer_del(&gc_timer) == -1) 931 fatal(__func__); 932 } 933