ldp/ldp_fec.c

   1
   2 /*
   3  *  Copyright (C) James R. Leu 2000
   4  *  jleu@mindspring.com
   5  *
   6  *  This software is covered under the LGPL, for more
   7  *  info check out http://www.gnu.org/copyleft/lgpl.html
   8  */
   9
  10 #include "ldp_struct.h"
  11 #include "ldp_fec.h"
  12 #include "ldp_if.h"
  13 #include "ldp_attr.h"
  14 #include "ldp_addr.h"
  15 #include "ldp_nexthop.h"
  16 #include "ldp_session.h"
  17 #include "ldp_inlabel.h"
  18 #include "ldp_outlabel.h"
  19 #include "ldp_global.h"
  20 #include "ldp_label_mapping.h"
  21 #include "ldp_label_request.h"
  22 #include "ldp_label_abort.h"
  23 #include "ldp_label_rel_with.h"
  24 #include "mpls_assert.h"
  25 #include "mpls_compare.h"
  26 #include "mpls_mm_impl.h"
  27 #include "mpls_tree_impl.h"
  28 #include "mpls_policy_impl.h"
  29 #include "mpls_trace_impl.h"
  30
  31 #if MPLS_USE_LSR
  32 #include "lsr_cfg.h"
  33 #else
  34 #include "mpls_mpls_impl.h"
  35 #endif
  36
  37 static uint32_t _ldp_fec_next_index = 1;
  38
  39 static mpls_return_enum ldp_fec_insert(ldp_global *g, ldp_fec * fec)
  40 {
  41   mpls_return_enum retval = MPLS_SUCCESS;
  42   uint32_t key;
  43   uint8_t len;
  44
  45   MPLS_ASSERT(g && fec);
  46   LDP_ENTER(g->user_data, "ldp_fec_insert");
  47
  48   switch(fec->info.type) {
  49     case MPLS_FEC_PREFIX:
  50       key = fec->info.u.prefix.network.u.ipv4;
  51       len = fec->info.u.prefix.length;
  52       break;
  53     case MPLS_FEC_HOST:
  54       key = fec->info.u.host.u.ipv4;
  55       len = 32;
  56       break;
  57     case MPLS_FEC_L2CC:
  58       /* they had better insert it into the global list */
  59       LDP_EXIT(g->user_data, "ldp_fec_insert: l2cc");
  60       return MPLS_SUCCESS;
  61     default:
  62       MPLS_ASSERT(0);
  63   }
  64
  65   LDP_PRINT(g->user_data, "ldp_fec_insert: 0x%08x/%d\n", key, len);
  66
  67   if (mpls_tree_insert(g->fec_tree, key, len, (void *)fec) != MPLS_SUCCESS) {
  68     LDP_PRINT(g->user_data, "ldp_fec_insert: error adding fec\n");
  69     retval = MPLS_FATAL;
  70   }
  71
  72   LDP_EXIT(g->user_data, "ldp_fec_insert");
  73   return retval;
  74 }
  75
  76 static void ldp_fec_remove(ldp_global *g, mpls_fec *fec)
  77 {
  78   ldp_fec *f = NULL;
  79   uint32_t key;
  80   uint8_t len;
  81
  82   MPLS_ASSERT(g && fec);
  83   LDP_ENTER(g->user_data, "ldp_fec_remove");
  84
  85   switch(fec->type) {
  86     case MPLS_FEC_PREFIX:
  87       key = fec->u.prefix.network.u.ipv4;
  88       len = fec->u.prefix.length;
  89       break;
  90     case MPLS_FEC_HOST:
  91       key = fec->u.host.u.ipv4;
  92       len = 32;
  93       break;
  94     case MPLS_FEC_L2CC:
  95       /* they had better remove it from the global list */
  96       LDP_EXIT(g->user_data, "ldp_fec_remove");
  97       return;
  98     default:
  99       MPLS_ASSERT(0);
 100   }
 101
 102   LDP_PRINT(g->user_data, "ldp_fec_remove: 0x%08x/%d\n", key, len);
 103   mpls_tree_remove(g->fec_tree, key, len, (void **)&f);
 104
 105   MPLS_ASSERT(f);
 106
 107   LDP_EXIT(g->user_data, "ldp_fec_remove");
 108 }
 109
 110 static uint32_t _ldp_fec_get_next_index()
 111 {
 112   uint32_t retval = _ldp_fec_next_index;
 113
 114   _ldp_fec_next_index++;
 115   if (retval > _ldp_fec_next_index) {
 116     _ldp_fec_next_index = 1;
 117   }
 118   return retval;
 119 }
 120
 121 ldp_fec *ldp_fec_create(ldp_global *g, mpls_fec *f)
 122 {
 123   ldp_fec *fec = (ldp_fec *) mpls_malloc(sizeof(ldp_fec));
 124
 125   if (fec != NULL) {
 126     memset(fec, 0, sizeof(ldp_fec));
 127     /*
 128      * note: this is init to 1 for a reason!
 129      * We're placing it in the global list, so this is our refcnt
 130      * when this refcnt gets to zero, it will be removed from the
 131      * global list and deleted
 132      */
 133     /*
 134      * TESTING: jleu 6/7/2004, since I want the FEC to be cleaned up
 135      * when it no longer has a nexthop, addr, or label, the only things that
 136      * should increment the ref are those (nh, addr, label etc), not global
 137      * nor inserting into the tree.  I also added this comment in
 138      * _ldp_global_add_fec()
 139     MPLS_REFCNT_INIT(fec, 1);
 140      */
 141     MPLS_REFCNT_INIT(fec, 0);
 142     MPLS_LIST_ELEM_INIT(fec, _global);
 143     MPLS_LIST_ELEM_INIT(fec, _inlabel);
 144     MPLS_LIST_ELEM_INIT(fec, _outlabel);
 145     MPLS_LIST_ELEM_INIT(fec, _fec);
 146     MPLS_LIST_INIT(&fec->nh_root, ldp_nexthop);
 147     MPLS_LIST_INIT(&fec->fs_root_us, ldp_fs);
 148     MPLS_LIST_INIT(&fec->fs_root_ds, ldp_fs);
 149     fec->index = _ldp_fec_get_next_index();
 150     mpls_fec2ldp_fec(f,fec);
 151
 152     _ldp_global_add_fec(g, fec);
 153     ldp_fec_insert(g, fec);
 154   }
 155   return fec;
 156 }
 157
 158 void ldp_fec_delete(ldp_global *g, ldp_fec * fec)
 159 {
 160   fprintf(stderr, "fec delete: %08x/%d\n", fec->info.u.prefix.network.u.ipv4,
 161     fec->info.u.prefix.length);
 162   ldp_fec_remove(g, &fec->info);
 163   _ldp_global_del_fec(g, fec);
 164   mpls_free(fec);
 165 }
 166
 167 ldp_fec *ldp_fec_find(ldp_global *g, mpls_fec *fec)
 168 {
 169   ldp_fec *f = NULL;
 170   uint32_t key;
 171   uint8_t len;
 172
 173   switch(fec->type) {
 174     case MPLS_FEC_PREFIX:
 175       key = fec->u.prefix.network.u.ipv4;
 176       len = fec->u.prefix.length;
 177       break;
 178     case MPLS_FEC_HOST:
 179       key = fec->u.host.u.ipv4;
 180       len = 32;
 181       break;
 182     case MPLS_FEC_L2CC:
 183       if (ldp_global_find_fec(g, fec, &f) == MPLS_SUCCESS) {
 184         return f;
 185       }
 186       return NULL;
 187     default:
 188       MPLS_ASSERT(0);
 189   }
 190
 191   LDP_PRINT(g->user_data, "ldp_fec_find: 0x%08x/%d\n", key, len);
 192   if (mpls_tree_get(g->fec_tree, key, len, (void **)&f) != MPLS_SUCCESS) {
 193     return NULL;
 194   }
 195   return f;
 196 }
 197
 198 ldp_fec *ldp_fec_find2(ldp_global *g, mpls_fec *fec)
 199 {
 200   ldp_fec *f = NULL;
 201   f = ldp_fec_find(g, fec);
 202   if (!f) {
 203     f = ldp_fec_create(g, fec);
 204   }
 205   return f;
 206 }
 207
 208 ldp_nexthop *ldp_fec_nexthop_find(ldp_fec *f, mpls_nexthop *n)
 209 {
 210   ldp_nexthop *nh = NULL;
 211
 212   MPLS_ASSERT(f && n);
 213
 214   nh = MPLS_LIST_HEAD(&f->nh_root);
 215   while (nh) {
 216     if (!mpls_nexthop_compare(&nh->info, n)) {
 217       return nh;
 218     }
 219     nh = MPLS_LIST_NEXT(&f->nh_root, nh, _fec);
 220   }
 221
 222   return NULL;
 223 }
 224
 225 mpls_return_enum ldp_fec_find_nexthop_index(ldp_fec *f, int index,
 226   ldp_nexthop **n)
 227 {
 228   ldp_nexthop *nh = NULL;
 229
 230   MPLS_ASSERT(f);
 231
 232   if (index > 0) {
 233
 234     /* because we sort our inserts by index, this lets us know
 235        if we've "walked" past the end of the list */
 236
 237     nh = MPLS_LIST_TAIL(&f->nh_root);
 238     if (!nh || nh->index < index) {
 239       *n = NULL;
 240       return MPLS_END_OF_LIST;
 241     }
 242
 243     nh = MPLS_LIST_HEAD(&f->nh_root);
 244     do {
 245       if (nh->index == index) {
 246         *n = nh;
 247         return MPLS_SUCCESS;
 248       }
 249     } while((nh = MPLS_LIST_NEXT(&f->nh_root, nh, _fec)));
 250   }
 251   *n = NULL;
 252   return MPLS_FAILURE;
 253 }
 254
 255 mpls_return_enum ldp_fec_add_nexthop(ldp_global *g, ldp_fec * f,
 256   ldp_nexthop * nh)
 257 {
 258   MPLS_ASSERT(f && nh);
 259
 260   LDP_ENTER(g->user_data, "ldp_fec_add_nexthop");
 261
 262   MPLS_REFCNT_HOLD(nh);
 263   MPLS_LIST_ADD_HEAD(&f->nh_root, nh, _fec, ldp_nexthop);
 264
 265   ldp_nexthop_add_fec(nh, f);
 266
 267   LDP_EXIT(g->user_data, "ldp_fec_add_nexthop: success");
 268   return MPLS_SUCCESS;
 269
 270 ldp_fec_add_nexthop_error:
 271
 272   ldp_fec_del_nexthop(g, f, nh);
 273   LDP_EXIT(g->user_data, "ldp_fec_add_nexthop: fail");
 274   return MPLS_FATAL;
 275 }
 276
 277 void ldp_fec_del_nexthop(ldp_global *g, ldp_fec * f, ldp_nexthop *nh)
 278 {
 279   MPLS_ASSERT(f && nh);
 280
 281   MPLS_LIST_REMOVE(&f->nh_root, nh, _fec);
 282   ldp_nexthop_del_fec(g, nh);
 283
 284   MPLS_REFCNT_RELEASE2(g, nh, ldp_nexthop_delete);
 285 }
 286
 287 mpls_return_enum ldp_fec_process_add(ldp_global * g, ldp_fec * f,
 288   ldp_nexthop *nh, ldp_session *nh_session)
 289 {
 290   ldp_session *peer = NULL;
 291   ldp_attr *ds_attr = NULL;
 292   ldp_attr *us_attr = NULL;
 293   mpls_bool egress;
 294   ldp_outlabel *out;
 295
 296   LDP_ENTER(g->user_data, "ldp_fec_process_add");
 297
 298   egress = mpls_policy_egress_check(g, &f->info, &nh->info);
 299
 300   /*
 301    * find the info about the next hop for this FEC
 302    */
 303   if (!nh_session) {
 304     nh_session = ldp_session_for_nexthop(nh);
 305   }
 306
 307   if (nh_session) {
 308     ds_attr = ldp_attr_find_downstream_state2(g, nh_session, f,
 309       LDP_LSP_STATE_MAP_RECV);
 310     if (ds_attr && !ds_attr->outlabel) {
 311       out = ldp_outlabel_create_complete(g, nh_session, ds_attr, nh);
 312       if (!out) {
 313         return MPLS_FAILURE;
 314       }
 315       ds_attr->outlabel = out;
 316     }
 317   }
 318
 319   /*
 320    * for every peer except the nh hop peer, check to see if we need to
 321    * send a mapping
 322    */
 323   peer = MPLS_LIST_HEAD(&g->session);
 324   while (peer != NULL) {        /* FEC.1 */
 325     if ((peer->state != LDP_STATE_OPERATIONAL) ||
 326       (nh_session && peer->index == nh_session->index)) {
 327       goto next_peer;
 328     }
 329     /* have I already sent a mapping for FEC to peer */
 330     if ((us_attr = ldp_attr_find_upstream_state2(g, peer, f,
 331       LDP_LSP_STATE_MAP_SENT))) {
 332       /* yep, don't send another */
 333       if (ds_attr) {
 334         if (ldp_inlabel_add_outlabel(g, us_attr->inlabel,
 335           ds_attr->outlabel) != MPLS_SUCCESS) {
 336           return MPLS_FAILURE;
 337         }
 338       }
 339       goto next_peer;
 340     }
 341
 342     if (peer->oper_distribution_mode == LDP_DISTRIBUTION_UNSOLICITED) {
 343       if (g->lsp_control_mode == LDP_CONTROL_INDEPENDENT) {
 344         us_attr =
 345           ldp_attr_find_upstream_state2(g, peer, f, LDP_LSP_STATE_REQ_RECV);
 346
 347         /* FEC.1.DUI3,4 */
 348         if (ldp_label_mapping_with_xc(g, peer, f, &us_attr, ds_attr) !=
 349           MPLS_SUCCESS) {
 350           if (!us_attr->in_tree) {
 351             ldp_attr_remove_complete(g, us_attr, MPLS_BOOL_FALSE);
 352           }
 353           goto next_peer;
 354         }
 355       } else {
 356         /*
 357          *LDP_CONTROL_ORDERED
 358          */
 359
 360         if (ds_attr || egress == MPLS_BOOL_TRUE) { /* FEC.1.DUO2 */
 361           if (!(us_attr = ldp_attr_create(&f->info))) {
 362             return MPLS_FAILURE;
 363           }
 364           /* FEC.1.DUO3-4 */
 365           if (ldp_label_mapping_with_xc(g, peer, f, &us_attr, ds_attr) !=
 366             MPLS_SUCCESS) {
 367             return MPLS_FAILURE;
 368           }
 369         }
 370       }
 371     }
 372   next_peer:
 373     peer = MPLS_LIST_NEXT(&g->session, peer, _global);
 374   }
 375
 376   if (ds_attr) {                /* FEC.2 */
 377     if (ldp_label_mapping_process(g, nh_session, NULL, NULL, ds_attr, f) ==
 378       MPLS_FAILURE) { /* FEC.5 */
 379       return MPLS_FAILURE;
 380     }
 381     return MPLS_SUCCESS;
 382   }
 383
 384   /*
 385    * LDP_DISTRIBUTION_ONDEMAND
 386    */
 387   /* FEC.3 */
 388   if (nh_session &&
 389       nh_session->oper_distribution_mode == LDP_DISTRIBUTION_ONDEMAND) {
 390     /* assume we're always "request when needed" */
 391     ds_attr = NULL;
 392     if (ldp_label_request_for_xc(g, nh_session, &f->info, NULL, &ds_attr) ==
 393       MPLS_FAILURE) { /* FEC.4 */
 394       return MPLS_FAILURE;
 395     }
 396   }
 397
 398   LDP_EXIT(g->user_data, "ldp_fec_process_add");
 399
 400   return MPLS_SUCCESS;           /* FEC.6 */
 401 }
 402
 403 mpls_return_enum ldp_fec_process_change(ldp_global * g, ldp_fec * f,
 404   ldp_nexthop *nh, ldp_nexthop *nh_old, ldp_session *nh_session_old) {
 405   ldp_session *peer = NULL;
 406   ldp_attr *us_attr = NULL;
 407   ldp_attr *ds_attr = NULL;
 408   ldp_session *nh_session = NULL;
 409
 410   LDP_ENTER(g->user_data,
 411     "ldp_fec_process_change: fec %p nh %p nh_old %p nh_session_old %p",
 412     f, nh, nh_old, nh_session_old);
 413
 414   if (!nh_session_old) {
 415     nh_session_old = ldp_session_for_nexthop(nh_old);
 416   }
 417
 418   /*
 419    * NH 1-5 decide if we need to release an existing mapping
 420    */
 421   ds_attr = ldp_attr_find_downstream_state2(g, nh_session_old, f,
 422       LDP_LSP_STATE_MAP_RECV);
 423   if (!ds_attr) {               /* NH.1 */
 424     goto Detect_Change_Fec_Next_Hop_6;
 425   }
 426
 427   if (ds_attr->ingress == MPLS_BOOL_TRUE) {
 428
 429 #if MPLS_USE_LSR
 430     lsr_ftn ftn;
 431     ftn.outsegment_index = ds_attr->outlabel->info.handle;
 432     memcpy(&ftn.fec, &f->info, sizeof(mpls_fec));
 433     lsr_cfg_ftn_set2(g->lsr_handle, &ftn, LSR_CFG_DEL);
 434 #else
 435     mpls_mpls_fec2out_del(g->mpls_handle, &f->info, &ds_attr->outlabel->info);
 436 #endif
 437     ds_attr->ingress = MPLS_BOOL_FALSE;
 438     ds_attr->outlabel->merge_count--;
 439   }
 440
 441   if (g->label_retention_mode == LDP_RETENTION_LIBERAL) { /* NH.3 */
 442     ldp_attr *us_temp;
 443     us_attr = MPLS_LIST_HEAD(&ds_attr->us_attr_root);
 444     while (us_attr) {
 445       /* need to walk the list in such a way as not to
 446        * "pull the rug out from under me self"
 447        */
 448       us_temp = MPLS_LIST_NEXT(&ds_attr->us_attr_root, us_attr, _ds_attr);
 449       if (us_attr->state == LDP_LSP_STATE_MAP_SENT) {
 450         ldp_inlabel_del_outlabel(g, us_attr->inlabel);  /* NH.2 */
 451         ldp_attr_del_us2ds(us_attr, ds_attr);
 452       }
 453       us_attr = us_temp;
 454     }
 455     goto Detect_Change_Fec_Next_Hop_6;
 456   }
 457
 458   ldp_label_release_send(g, nh_session_old, ds_attr, LDP_NOTIF_NONE); /* NH.4 */
 459   ldp_attr_remove_complete(g, ds_attr, MPLS_BOOL_FALSE); /* NH.2,5 */
 460
 461 Detect_Change_Fec_Next_Hop_6:
 462
 463   /*
 464    * NH 6-9 decides is we need to send a label request abort
 465    */
 466   ds_attr = ldp_attr_find_downstream_state2(g, nh_session_old, f,
 467     LDP_LSP_STATE_REQ_SENT);
 468   if (ds_attr) {               /* NH.6 */
 469     if (g->label_retention_mode != LDP_RETENTION_CONSERVATIVE) { /* NH.7 */
 470       /* NH.8,9 */
 471       if (ldp_label_abort_send(g, nh_session_old, ds_attr) != MPLS_SUCCESS) {
 472         return MPLS_FAILURE;
 473       }
 474     }
 475   }
 476
 477   /*
 478    * NH 10-12 decides if we can use a mapping from our database
 479    */
 480   if ((!nh) || (!(nh_session = ldp_get_next_hop_session_for_fec2(f,nh)))) {
 481     goto Detect_Change_Fec_Next_Hop_16;
 482   }
 483
 484   ds_attr = ldp_attr_find_downstream_state2(g, nh_session, f,
 485     LDP_LSP_STATE_MAP_RECV);
 486   if (!ds_attr) {               /* NH.11 */
 487     goto Detect_Change_Fec_Next_Hop_13;
 488   }
 489
 490   if (ldp_label_mapping_process(g, nh_session, NULL, NULL, ds_attr, f) !=
 491     MPLS_SUCCESS) { /* NH.12 */
 492     return MPLS_FAILURE;
 493   }
 494   goto Detect_Change_Fec_Next_Hop_20;
 495
 496 Detect_Change_Fec_Next_Hop_13:
 497
 498   /*
 499    * NH 13-15 decides if we need to make a label request
 500    */
 501   if (nh_session->oper_distribution_mode == LDP_DISTRIBUTION_ONDEMAND &&
 502     g->label_retention_mode == LDP_RETENTION_CONSERVATIVE) {
 503     /* NH.14-15 */
 504     if (ldp_label_request_for_xc(g, nh_session, &f->info, NULL, &ds_attr) !=
 505         MPLS_SUCCESS) {
 506       return MPLS_FAILURE;
 507     }
 508   }
 509   goto Detect_Change_Fec_Next_Hop_20;
 510
 511 Detect_Change_Fec_Next_Hop_16:
 512
 513   peer = MPLS_LIST_HEAD(&g->session);
 514   while (peer) {
 515     if (peer->state == LDP_STATE_OPERATIONAL) {
 516       us_attr = ldp_attr_find_upstream_state2(g, peer, f,
 517         LDP_LSP_STATE_MAP_SENT);
 518       if (us_attr) {    /* NH.17 */
 519         if (ldp_label_withdraw_send(g, peer, us_attr, LDP_NOTIF_NONE) !=
 520           MPLS_SUCCESS) { /* NH.18 */
 521           ldp_attr_remove_complete(g, us_attr, MPLS_BOOL_FALSE);
 522           return MPLS_FAILURE;
 523         }
 524       }
 525     }
 526     peer = MPLS_LIST_NEXT(&g->session, peer, _global);
 527   }
 528
 529 Detect_Change_Fec_Next_Hop_20:
 530
 531   LDP_EXIT(g->user_data, "ldp_fec_process_change");
 532
 533   return MPLS_SUCCESS;
 534 }
 535
 536 void mpls_fec2ldp_fec(mpls_fec * a, ldp_fec * b)
 537 {
 538   memcpy(&b->info, a, sizeof(mpls_fec));
 539 }
 540
 541 void mpls_fec2fec_tlv(mpls_fec * lf, mplsLdpFecTlv_t * tlv, int i)
 542 {
 543   tlv->fecElArray[i].addressEl.addressFam = 1;
 544
 545   switch (lf->type) {
 546     case MPLS_FEC_PREFIX:
 547       tlv->fecElArray[i].addressEl.type = MPLS_PREFIX_FEC;
 548       tlv->fecElArray[i].addressEl.preLen = lf->u.prefix.length;
 549       tlv->fecElArray[i].addressEl.address = lf->u.prefix.network.u.ipv4;
 550       tlv->fecElemTypes[i] = MPLS_PREFIX_FEC;
 551       break;
 552     case MPLS_FEC_HOST:
 553       tlv->fecElArray[i].addressEl.type = MPLS_HOSTADR_FEC;
 554       tlv->fecElArray[i].addressEl.preLen = MPLS_IPv4LEN;
 555       tlv->fecElArray[i].addressEl.address = lf->u.host.u.ipv4;
 556       tlv->fecElemTypes[i] = MPLS_HOSTADR_FEC;
 557       break;
 558     default:
 559       MPLS_ASSERT(0);
 560   }
 561 }
 562
 563 void fec_tlv2mpls_fec(mplsLdpFecTlv_t * tlv, int i, mpls_fec * lf) {
 564   switch (tlv->fecElemTypes[i]) {
 565     case MPLS_PREFIX_FEC:
 566       lf->type = MPLS_FEC_PREFIX;
 567       lf->u.prefix.length = tlv->fecElArray[i].addressEl.preLen;
 568       lf->u.prefix.network.u.ipv4 = tlv->fecElArray[i].addressEl.address;
 569       lf->u.prefix.network.type = MPLS_FAMILY_IPV4;
 570       break;
 571     case MPLS_HOSTADR_FEC:
 572       lf->type = MPLS_FEC_HOST;
 573       lf->u.host.u.ipv4 = tlv->fecElArray[i].addressEl.address;
 574       lf->u.host.type = MPLS_FAMILY_IPV4;
 575       break;
 576     default:
 577       MPLS_ASSERT(0);
 578   }
 579 }
 580
 581 mpls_bool ldp_fec_empty(ldp_fec *fec)
 582 {
 583   if (MPLS_LIST_EMPTY(&fec->fs_root_us) &&
 584       MPLS_LIST_EMPTY(&fec->nh_root) &&
 585       MPLS_LIST_EMPTY(&fec->fs_root_ds)) {
 586     return MPLS_BOOL_TRUE;
 587   }
 588   return MPLS_BOOL_FALSE;
 589 }
 590