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