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