FECs are now added to the global list as part of creation, and
[mpls-ldp-portable.git] / ldp / ldp_fec.c
blob50fe89535ef62ccf8473b9817f4262834d419f0c
2 /*
3 * Copyright (C) James R. Leu 2000
4 * jleu@mindspring.com
6 * This software is covered under the LGPL, for more
7 * info check out http://www.gnu.org/copyleft/lgpl.html
8 */
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"
31 #if MPLS_USE_LSR
32 #include "lsr_cfg.h"
33 #else
34 #include "mpls_mpls_impl.h"
35 #endif
37 static uint32_t _ldp_fec_next_index = 1;
38 static uint32_t _ldp_fec_get_next_index();
40 ldp_nexthop *ldp_fec_nexthop_find(ldp_fec *f, mpls_nexthop *n)
42 ldp_nexthop *nh = NULL;
44 MPLS_ASSERT(f && n);
46 nh = MPLS_LIST_HEAD(&f->nh_root);
47 while (nh) {
48 if (!mpls_nexthop_compare(&nh->info, n)) {
49 return nh;
51 nh = MPLS_LIST_NEXT(&f->nh_root, nh, _fec);
54 return NULL;
57 ldp_fec *ldp_fec_find(ldp_global *g, mpls_fec *fec)
59 ldp_fec *f = NULL;
60 uint32_t key;
61 uint8_t len;
63 switch(fec->type) {
64 case MPLS_FEC_PREFIX:
65 key = fec->u.prefix.network.u.ipv4;
66 len = fec->u.prefix.length;
67 break;
68 case MPLS_FEC_HOST:
69 key = fec->u.host.u.ipv4;
70 len = 32;
71 break;
72 case MPLS_FEC_L2CC:
73 if (ldp_global_find_fec(g, fec, &f) == MPLS_SUCCESS) {
74 return f;
76 return NULL;
77 default:
78 MPLS_ASSERT(0);
81 if (mpls_tree_get(g->fec_tree, key, len, (void **)&f) != MPLS_SUCCESS) {
82 return NULL;
84 return f;
87 mpls_return_enum ldp_fec_insert2(ldp_global *g, ldp_fec * fec)
89 uint32_t key;
90 uint8_t len;
92 MPLS_ASSERT(MPLS_LIST_EMPTY(&fec->nh_root));
94 switch(fec->info.type) {
95 case MPLS_FEC_PREFIX:
96 key = fec->info.u.prefix.network.u.ipv4;
97 len = fec->info.u.prefix.length;
98 break;
99 case MPLS_FEC_HOST:
100 key = fec->info.u.host.u.ipv4;
101 len = 32;
102 case MPLS_FEC_L2CC:
103 /* they had better insert it into the global list */
104 return MPLS_SUCCESS;
105 default:
106 MPLS_ASSERT(0);
109 /* hold it since it is going in the tree */
110 MPLS_REFCNT_HOLD(fec);
112 if (mpls_tree_insert(g->fec_tree, key, len, (void *)fec) != MPLS_SUCCESS) {
113 LDP_PRINT(g->user_data, "ldp_fec_insert: error adding addr\n");
115 /* delete the refcnt we just took */
116 MPLS_REFCNT_RELEASE2(g, fec, ldp_fec_delete);
117 goto ldp_fec_insert2_error;
119 return MPLS_SUCCESS;
121 ldp_fec_insert2_error:
122 return MPLS_FATAL;
125 ldp_fec *ldp_fec_insert(ldp_global *g, mpls_fec * fec)
127 ldp_fec *f = NULL;
129 if ((f = ldp_fec_create(g)) == NULL) {
130 LDP_PRINT(g->user_data, "ldp_fec_insert: error creating address\n");
131 return NULL;
134 mpls_fec2ldp_fec(fec,f);
136 if (ldp_fec_insert2(g,f) != MPLS_SUCCESS) {
137 /* this should delete it */
138 MPLS_REFCNT_RELEASE2(g, f, ldp_fec_delete);
139 return NULL;
141 return f;
144 ldp_fec *ldp_fec_find2(ldp_global *g, mpls_fec *fec)
146 ldp_fec *f = NULL;
147 f = ldp_fec_find(g, fec);
148 if (!f) {
149 f = ldp_fec_insert(g, fec);
151 return f;
154 void ldp_fec_remove(ldp_global *g, mpls_fec *fec)
156 ldp_fec *f = NULL;
157 uint32_t key;
158 uint8_t len;
160 LDP_ENTER(g->user_data, "ldp_fec_remove");
162 switch(fec->type) {
163 case MPLS_FEC_PREFIX:
164 key = fec->u.prefix.network.u.ipv4;
165 len = fec->u.prefix.length;
166 break;
167 case MPLS_FEC_HOST:
168 key = fec->u.host.u.ipv4;
169 len = 32;
170 break;
171 case MPLS_FEC_L2CC:
172 /* they had better remove it from the global list */
173 LDP_EXIT(g->user_data, "ldp_fec_remove");
174 return;
175 default:
176 MPLS_ASSERT(0);
179 mpls_tree_remove(g->fec_tree, key, len, (void **)&f);
180 if (!f) {
181 LDP_EXIT(g->user_data, "ldp_fec_remove");
182 return;
185 MPLS_ASSERT(MPLS_LIST_EMPTY(&f->nh_root));
187 MPLS_REFCNT_RELEASE2(g, f, ldp_fec_delete);
189 LDP_EXIT(g->user_data, "ldp_fec_remove");
192 mpls_bool ldp_fec_empty(ldp_fec *fec)
194 if (MPLS_LIST_EMPTY(&fec->fs_root_us) &&
195 MPLS_LIST_EMPTY(&fec->fs_root_ds)) {
196 return MPLS_BOOL_TRUE;
198 return MPLS_BOOL_FALSE;
201 mpls_return_enum ldp_fec_find_nexthop_index(ldp_fec *f, int index,
202 ldp_nexthop **n)
204 ldp_nexthop *nh = NULL;
206 MPLS_ASSERT(f);
208 if (index > 0) {
210 /* because we sort our inserts by index, this lets us know
211 if we've "walked" past the end of the list */
213 nh = MPLS_LIST_TAIL(&f->nh_root);
214 if (!nh || nh->index < index) {
215 *n = NULL;
216 return MPLS_END_OF_LIST;
219 nh = MPLS_LIST_HEAD(&f->nh_root);
220 do {
221 if (nh->index == index) {
222 *n = nh;
223 return MPLS_SUCCESS;
225 } while((nh = MPLS_LIST_NEXT(&f->nh_root, nh, _fec)));
227 *n = NULL;
228 return MPLS_FAILURE;
231 mpls_return_enum ldp_fec_add_nexthop(ldp_global *g, ldp_fec * f,
232 ldp_nexthop * nh)
234 MPLS_ASSERT(f && nh);
236 MPLS_REFCNT_HOLD(nh);
237 MPLS_LIST_ADD_HEAD(&f->nh_root, nh, _fec, ldp_nexthop);
239 ldp_nexthop_add_fec(nh, f);
241 if (nh->type & MPLS_NH_IP) {
242 ldp_addr *addr = NULL;
243 if (!(addr = ldp_addr_find(g, &nh->info.ip))) {
244 if (!(addr = ldp_addr_insert(g, &nh->info.ip))) {
245 goto ldp_fec_add_nexthop_error;
249 ldp_addr_add_nexthop(addr, nh);
252 if (nh->type & MPLS_NH_IF) {
253 ldp_if *iff = NULL;
254 if ((iff = ldp_global_find_if_handle(g, nh->info.if_handle))) {
255 ldp_if_add_nexthop(iff, nh);
259 if (nh->type & MPLS_NH_OUTSEGMENT) {
260 ldp_outlabel *out = NULL;
261 MPLS_ASSERT((out = ldp_global_find_outlabel_handle(g,
262 nh->info.outsegment_handle)));
264 ldp_outlabel_add_nexthop(out, nh);
266 return MPLS_SUCCESS;
268 ldp_fec_add_nexthop_error:
270 ldp_fec_del_nexthop(g, f, nh);
271 return MPLS_FATAL;
274 void ldp_fec_del_nexthop(ldp_global *g, ldp_fec * f, ldp_nexthop *nh)
276 MPLS_ASSERT(f && nh);
278 if (nh->addr) {
279 ldp_addr_del_nexthop(g, nh->addr, nh);
281 if (nh->iff) {
282 ldp_if_del_nexthop(g, nh->iff, nh);
284 if (nh->outlabel) {
285 ldp_outlabel_del_nexthop(nh->outlabel, nh);
288 MPLS_LIST_REMOVE(&f->nh_root, nh, _fec);
289 ldp_nexthop_del_fec(nh);
291 MPLS_REFCNT_RELEASE(nh, ldp_nexthop_delete);
294 mpls_return_enum ldp_fec_process_add(ldp_global * g, ldp_fec * f,
295 ldp_nexthop *nh)
297 ldp_session *nh_session = NULL;
298 ldp_session *peer = NULL;
299 ldp_attr *ds_attr = NULL;
300 ldp_attr *us_attr = NULL;
301 mpls_bool egress = MPLS_BOOL_FALSE;
302 ldp_outlabel *out;
304 LDP_ENTER(g->user_data, "ldp_fec_process_add");
307 * find the info about the next hop for this FEC
309 nh_session = ldp_session_for_nexthop(nh);
311 if (nh_session) {
312 ds_attr = ldp_attr_find_downstream_state2(g, nh_session, f,
313 LDP_LSP_STATE_MAP_RECV);
314 if (ds_attr && !ds_attr->outlabel) {
315 out = ldp_outlabel_create_complete(g, nh_session, ds_attr, nh);
316 if (!out) {
317 return MPLS_FAILURE;
319 ds_attr->outlabel = out;
324 * for every peer except the nh hop peer, check to see if we need to
325 * send a mapping
327 peer = MPLS_LIST_HEAD(&g->session);
328 while (peer != NULL) { /* FEC.1 */
329 if ((peer->state != LDP_STATE_OPERATIONAL) ||
330 (nh_session && peer->index == nh_session->index)) {
331 goto next_peer;
333 /* have I already sent a mapping for FEC to peer */
334 if ((us_attr = ldp_attr_find_upstream_state2(g, peer, f,
335 LDP_LSP_STATE_MAP_SENT))) {
336 /* yep, don't send another */
337 if (ds_attr) {
338 if (ldp_inlabel_add_outlabel(g, us_attr->inlabel,
339 ds_attr->outlabel) != MPLS_SUCCESS) {
340 return MPLS_FAILURE;
343 goto next_peer;
346 if (peer->oper_distribution_mode == LDP_DISTRIBUTION_UNSOLICITED) {
347 if (g->lsp_control_mode == LDP_CONTROL_INDEPENDENT) {
348 us_attr =
349 ldp_attr_find_upstream_state2(g, peer, f, LDP_LSP_STATE_REQ_RECV);
351 /* FEC.1.DUI3,4 */
352 if (ldp_label_mapping_with_xc(g, peer, f, &us_attr, ds_attr) !=
353 MPLS_SUCCESS) {
354 if (!us_attr->in_tree) {
355 ldp_attr_remove_complete(g, us_attr, MPLS_BOOL_FALSE);
357 goto next_peer;
359 } else {
361 *LDP_CONTROL_ORDERED
364 if (ds_attr || egress == MPLS_BOOL_TRUE) { /* FEC.1.DUO2 */
365 if (!(us_attr = ldp_attr_create(&f->info))) {
366 return MPLS_FAILURE;
368 /* FEC.1.DUO3-4 */
369 if ((egress == MPLS_BOOL_TRUE) && (mpls_policy_egress_check(
370 g->user_data, &f->info, &nh->info) == MPLS_BOOL_TRUE)) {
371 goto next_peer;
374 if (ldp_label_mapping_with_xc(g, peer, f, &us_attr, ds_attr) !=
375 MPLS_SUCCESS) {
376 return MPLS_FAILURE;
381 next_peer:
382 peer = MPLS_LIST_NEXT(&g->session, peer, _global);
385 if (ds_attr) { /* FEC.2 */
386 if (ldp_label_mapping_process(g, nh_session, NULL, NULL, ds_attr, f) ==
387 MPLS_FAILURE) { /* FEC.5 */
388 return MPLS_FAILURE;
390 return MPLS_SUCCESS;
394 * LDP_DISTRIBUTION_ONDEMAND
396 /* FEC.3 */
397 if (nh_session &&
398 nh_session->oper_distribution_mode == LDP_DISTRIBUTION_ONDEMAND) {
399 /* assume we're always "request when needed" */
400 ds_attr = NULL;
401 if (ldp_label_request_for_xc(g, nh_session, &f->info, NULL, &ds_attr) ==
402 MPLS_FAILURE) { /* FEC.4 */
403 return MPLS_FAILURE;
407 LDP_EXIT(g->user_data, "ldp_fec_process_add");
409 return MPLS_SUCCESS; /* FEC.6 */
412 mpls_return_enum ldp_fec_process_change(ldp_global * g, ldp_fec * f,
413 ldp_nexthop *nh, ldp_session *nh_session_old) {
414 ldp_session *peer = NULL;
415 ldp_attr *us_attr = NULL;
416 ldp_attr *ds_attr = NULL;
417 ldp_session *nh_session_new = NULL;
419 LDP_ENTER(g->user_data, "ldp_fec_process_change");
422 * NH 1-5 decide if we need to release an existing mapping
424 ds_attr = ldp_attr_find_downstream_state2(g, nh_session_old, f,
425 LDP_LSP_STATE_MAP_RECV);
426 if (!ds_attr) { /* NH.1 */
427 goto Detect_Change_Fec_Next_Hop_6;
430 if (ds_attr->ingress == MPLS_BOOL_TRUE) {
432 #if MPLS_USE_LSR
433 lsr_ftn ftn;
434 ftn.outsegment_index = ds_attr->outlabel->info.handle;
435 memcpy(&ftn.fec, &f->info, sizeof(mpls_fec));
436 lsr_cfg_ftn_set2(g->lsr_handle, &ftn, LSR_CFG_DEL);
437 #else
438 mpls_mpls_fec2out_del(g->mpls_handle, &f->info, &ds_attr->outlabel->info);
439 #endif
440 ds_attr->ingress = MPLS_BOOL_FALSE;
441 ds_attr->outlabel->merge_count--;
444 if (g->label_retention_mode == LDP_RETENTION_LIBERAL) { /* NH.3 */
445 ldp_attr *us_temp;
446 us_attr = MPLS_LIST_HEAD(&ds_attr->us_attr_root);
447 while (us_attr) {
448 /* need to walk the list in such a way as not to
449 * "pull the rug out from under me self"
451 us_temp = MPLS_LIST_NEXT(&ds_attr->us_attr_root, us_attr, _ds_attr);
452 if (us_attr->state == LDP_LSP_STATE_MAP_SENT) {
453 ldp_inlabel_del_outlabel(g, us_attr->inlabel); /* NH.2 */
454 ldp_attr_del_us2ds(us_attr, ds_attr);
456 us_attr = us_temp;
458 goto Detect_Change_Fec_Next_Hop_6;
461 ldp_label_release_send(g, nh_session_old, ds_attr, LDP_NOTIF_NONE); /* NH.4 */
462 ldp_attr_remove_complete(g, ds_attr, MPLS_BOOL_FALSE); /* NH.2,5 */
464 Detect_Change_Fec_Next_Hop_6:
467 * NH 6-9 decides is we need to send a label request abort
469 ds_attr = ldp_attr_find_downstream_state2(g, nh_session_old, f,
470 LDP_LSP_STATE_REQ_SENT);
471 if (ds_attr) { /* NH.6 */
472 if (g->label_retention_mode != LDP_RETENTION_CONSERVATIVE) { /* NH.7 */
473 /* NH.8,9 */
474 if (ldp_label_abort_send(g, nh_session_old, ds_attr) != MPLS_SUCCESS) {
475 return MPLS_FAILURE;
481 * NH 10-12 decides if we can use a mapping from our database
483 if (!(nh_session_new = ldp_get_next_hop_session_for_fec2(f,nh))) {
484 goto Detect_Change_Fec_Next_Hop_16;
487 ds_attr = ldp_attr_find_downstream_state2(g, nh_session_new, f,
488 LDP_LSP_STATE_MAP_RECV);
489 if (!ds_attr) { /* NH.11 */
490 goto Detect_Change_Fec_Next_Hop_13;
493 if (ldp_label_mapping_process(g, nh_session_new, NULL, NULL, ds_attr, f) !=
494 MPLS_SUCCESS) { /* NH.12 */
495 return MPLS_FAILURE;
497 goto Detect_Change_Fec_Next_Hop_20;
499 Detect_Change_Fec_Next_Hop_13:
502 * NH 13-15 decides if we need to make a label request
504 if (nh_session_new->oper_distribution_mode == LDP_DISTRIBUTION_ONDEMAND &&
505 g->label_retention_mode == LDP_RETENTION_CONSERVATIVE) {
506 /* NH.14-15 */
507 if (ldp_label_request_for_xc(g, nh_session_new, &f->info, NULL, &ds_attr) !=
508 MPLS_SUCCESS) {
509 return MPLS_FAILURE;
512 goto Detect_Change_Fec_Next_Hop_20;
514 Detect_Change_Fec_Next_Hop_16:
516 peer = MPLS_LIST_HEAD(&g->session);
517 while (peer) {
518 if (peer->state == LDP_STATE_OPERATIONAL) {
519 us_attr = ldp_attr_find_upstream_state2(g, peer, f,
520 LDP_LSP_STATE_MAP_SENT);
521 if (us_attr) { /* NH.17 */
522 if (ldp_label_withdraw_send(g, peer, us_attr, LDP_NOTIF_NONE) !=
523 MPLS_SUCCESS) { /* NH.18 */
524 ldp_attr_remove_complete(g, us_attr, MPLS_BOOL_FALSE);
525 return MPLS_FAILURE;
529 peer = MPLS_LIST_NEXT(&g->session, peer, _global);
532 Detect_Change_Fec_Next_Hop_20:
534 LDP_EXIT(g->user_data, "ldp_fec_process_change");
536 return MPLS_SUCCESS;
539 ldp_fec *ldp_fec_create(ldp_global *g)
541 ldp_fec *fec = (ldp_fec *) mpls_malloc(sizeof(ldp_fec));
543 if (fec != NULL) {
544 memset(fec, 0, sizeof(ldp_fec));
546 * note: this is init to 1 for a reason!
547 * We're placing it in the global list, so this is our refcnt
548 * when this refcnt gets to zero, it will be removed from the
549 * global list and deleted
551 MPLS_REFCNT_INIT(fec, 1);
552 MPLS_LIST_ELEM_INIT(fec, _global);
553 MPLS_LIST_ELEM_INIT(fec, _inlabel);
554 MPLS_LIST_ELEM_INIT(fec, _outlabel);
555 MPLS_LIST_ELEM_INIT(fec, _fec);
556 MPLS_LIST_INIT(&fec->nh_root, ldp_nexthop);
557 MPLS_LIST_INIT(&fec->fs_root_us, ldp_fs);
558 MPLS_LIST_INIT(&fec->fs_root_ds, ldp_fs);
559 fec->info.type = MPLS_FEC_NONE;
560 fec->index = _ldp_fec_get_next_index();
561 _ldp_global_add_fec(g, fec);
563 return fec;
566 void mpls_fec2ldp_fec(mpls_fec * a, ldp_fec * b)
568 memcpy(&b->info, a, sizeof(mpls_fec));
571 void ldp_fec_delete(ldp_global *g, ldp_fec * fec)
573 fprintf(stderr, "fec delete: %08x/%d\n", fec->info.u.prefix.network.u.ipv4,
574 fec->info.u.prefix.length);
575 _ldp_global_del_fec(g, fec);
576 mpls_free(fec);
579 void mpls_fec2fec_tlv(mpls_fec * lf, mplsLdpFecTlv_t * tlv, int i)
581 tlv->fecElArray[i].addressEl.addressFam = 1;
583 switch (lf->type) {
584 case MPLS_FEC_PREFIX:
585 tlv->fecElArray[i].addressEl.type = MPLS_PREFIX_FEC;
586 tlv->fecElArray[i].addressEl.preLen = lf->u.prefix.length;
587 tlv->fecElArray[i].addressEl.address = lf->u.prefix.network.u.ipv4;
588 tlv->fecElemTypes[i] = MPLS_PREFIX_FEC;
589 break;
590 case MPLS_FEC_HOST:
591 tlv->fecElArray[i].addressEl.type = MPLS_HOSTADR_FEC;
592 tlv->fecElArray[i].addressEl.preLen = MPLS_IPv4LEN;
593 tlv->fecElArray[i].addressEl.address = lf->u.host.u.ipv4;
594 tlv->fecElemTypes[i] = MPLS_HOSTADR_FEC;
595 break;
596 default:
597 MPLS_ASSERT(0);
601 void fec_tlv2mpls_fec(mplsLdpFecTlv_t * tlv, int i, mpls_fec * lf) {
602 switch (tlv->fecElemTypes[i]) {
603 case MPLS_PREFIX_FEC:
604 lf->type = MPLS_FEC_PREFIX;
605 lf->u.prefix.length = tlv->fecElArray[i].addressEl.preLen;
606 lf->u.prefix.network.u.ipv4 = tlv->fecElArray[i].addressEl.address;
607 lf->u.prefix.network.type = MPLS_FAMILY_IPV4;
608 break;
609 case MPLS_HOSTADR_FEC:
610 lf->type = MPLS_FEC_HOST;
611 lf->u.host.u.ipv4 = tlv->fecElArray[i].addressEl.address;
612 lf->u.host.type = MPLS_FAMILY_IPV4;
613 break;
614 default:
615 MPLS_ASSERT(0);
619 static uint32_t _ldp_fec_get_next_index()
621 uint32_t retval = _ldp_fec_next_index;
623 _ldp_fec_next_index++;
624 if (retval > _ldp_fec_next_index) {
625 _ldp_fec_next_index = 1;
627 return retval;