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