Add additional comments
[mpls-ldp-portable.git] / ldp / ldp_fec.c
blob0996d6039a6798766b5acf618d3d795b22df6038
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;
39 static mpls_return_enum ldp_fec_insert(ldp_global *g, ldp_fec * fec)
41 mpls_return_enum retval = MPLS_SUCCESS;
42 uint32_t key;
43 uint8_t len;
45 MPLS_ASSERT(g && fec);
46 LDP_ENTER(g->user_data, "ldp_fec_insert");
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);
65 LDP_PRINT(g->user_data, "ldp_fec_insert: 0x%08x/%d\n", key, len);
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;
72 LDP_EXIT(g->user_data, "ldp_fec_insert");
73 return retval;
76 static void ldp_fec_remove(ldp_global *g, mpls_fec *fec)
78 ldp_fec *f = NULL;
79 uint32_t key;
80 uint8_t len;
82 MPLS_ASSERT(g && fec);
83 LDP_ENTER(g->user_data, "ldp_fec_remove");
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);
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);
105 MPLS_ASSERT(f);
107 LDP_EXIT(g->user_data, "ldp_fec_remove");
110 static uint32_t _ldp_fec_get_next_index()
112 uint32_t retval = _ldp_fec_next_index;
114 _ldp_fec_next_index++;
115 if (retval > _ldp_fec_next_index) {
116 _ldp_fec_next_index = 1;
118 return retval;
121 ldp_fec *ldp_fec_create(ldp_global *g, mpls_fec *f)
123 ldp_fec *fec = (ldp_fec *) mpls_malloc(sizeof(ldp_fec));
125 if (fec != NULL) {
126 memset(fec, 0, sizeof(ldp_fec));
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
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);
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);
152 _ldp_global_add_fec(g, fec);
153 ldp_fec_insert(g, fec);
155 return fec;
158 void ldp_fec_delete(ldp_global *g, ldp_fec * fec)
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);
167 ldp_fec *ldp_fec_find(ldp_global *g, mpls_fec *fec)
169 ldp_fec *f = NULL;
170 uint32_t key;
171 uint8_t len;
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;
186 return NULL;
187 default:
188 MPLS_ASSERT(0);
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;
195 return f;
198 ldp_fec *ldp_fec_find2(ldp_global *g, mpls_fec *fec)
200 ldp_fec *f = NULL;
201 f = ldp_fec_find(g, fec);
202 if (!f) {
203 f = ldp_fec_create(g, fec);
205 return f;
208 ldp_nexthop *ldp_fec_nexthop_find(ldp_fec *f, mpls_nexthop *n)
210 ldp_nexthop *nh = NULL;
212 MPLS_ASSERT(f && n);
214 nh = MPLS_LIST_HEAD(&f->nh_root);
215 while (nh) {
216 if (!mpls_nexthop_compare(&nh->info, n)) {
217 return nh;
219 nh = MPLS_LIST_NEXT(&f->nh_root, nh, _fec);
222 return NULL;
225 mpls_return_enum ldp_fec_find_nexthop_index(ldp_fec *f, int index,
226 ldp_nexthop **n)
228 ldp_nexthop *nh = NULL;
230 MPLS_ASSERT(f);
232 if (index > 0) {
234 /* because we sort our inserts by index, this lets us know
235 if we've "walked" past the end of the list */
237 nh = MPLS_LIST_TAIL(&f->nh_root);
238 if (!nh || nh->index < index) {
239 *n = NULL;
240 return MPLS_END_OF_LIST;
243 nh = MPLS_LIST_HEAD(&f->nh_root);
244 do {
245 if (nh->index == index) {
246 *n = nh;
247 return MPLS_SUCCESS;
249 } while((nh = MPLS_LIST_NEXT(&f->nh_root, nh, _fec)));
251 *n = NULL;
252 return MPLS_FAILURE;
255 mpls_return_enum ldp_fec_add_nexthop(ldp_global *g, ldp_fec * f,
256 ldp_nexthop * nh)
258 MPLS_ASSERT(f && nh);
260 LDP_ENTER(g->user_data, "ldp_fec_add_nexthop");
262 MPLS_REFCNT_HOLD(nh);
263 MPLS_LIST_ADD_HEAD(&f->nh_root, nh, _fec, ldp_nexthop);
265 ldp_nexthop_add_fec(nh, f);
267 LDP_EXIT(g->user_data, "ldp_fec_add_nexthop: success");
268 return MPLS_SUCCESS;
270 ldp_fec_add_nexthop_error:
272 ldp_fec_del_nexthop(g, f, nh);
273 LDP_EXIT(g->user_data, "ldp_fec_add_nexthop: fail");
274 return MPLS_FATAL;
277 void ldp_fec_del_nexthop(ldp_global *g, ldp_fec * f, ldp_nexthop *nh)
279 MPLS_ASSERT(f && nh);
281 MPLS_LIST_REMOVE(&f->nh_root, nh, _fec);
282 ldp_nexthop_del_fec(g, nh);
284 MPLS_REFCNT_RELEASE2(g, nh, ldp_nexthop_delete);
287 mpls_return_enum ldp_fec_process_add(ldp_global * g, ldp_fec * f,
288 ldp_nexthop *nh, ldp_session *nh_session)
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;
296 LDP_ENTER(g->user_data, "ldp_fec_process_add");
299 * find the info about the next hop for this FEC
301 if (!nh_session) {
302 nh_session = ldp_get_next_hop_session_for_fec2(f, nh);
305 if (nh_session) {
306 /* check if we've received and retainted a label from nh_session for f */
307 ds_attr = ldp_attr_find_downstream_state2(g, nh_session, f,
308 LDP_LSP_STATE_MAP_RECV);
309 if (ds_attr && !ds_attr->outlabel) {
310 /* if so, and we have not installed that label, install it now */
311 out = ldp_outlabel_create_complete(g, nh_session, ds_attr, nh);
312 if (!out) {
313 return MPLS_FAILURE;
315 ds_attr->outlabel = out;
319 /* are we willing to egress for this FEC */
320 egress = mpls_policy_egress_check(g->user_data, &f->info, &nh->info);
323 * for every peer except the nh hop peer, check to see if we need to
324 * send a mapping
326 peer = MPLS_LIST_HEAD(&g->session);
327 while (peer != NULL) { /* FEC.1 */
328 if ((peer->state != LDP_STATE_OPERATIONAL) ||
329 (nh_session && peer->index == nh_session->index)) {
330 goto next_peer;
332 /* have I already sent a mapping for FEC to peer */
333 if ((us_attr = ldp_attr_find_upstream_state2(g, peer, f,
334 LDP_LSP_STATE_MAP_SENT))) {
335 /* yep, don't send another */
336 if (ds_attr) {
337 /* we need to XC the label we sent with the one we already have */
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 /* we need to send a label */
347 if (peer->oper_distribution_mode == LDP_DISTRIBUTION_UNSOLICITED) {
348 if (g->lsp_control_mode == LDP_CONTROL_INDEPENDENT) {
349 /* if we have received a pending request, give that as input to
350 * ldp_label_mapping_with_xc */
351 us_attr =
352 ldp_attr_find_upstream_state2(g, peer, f, LDP_LSP_STATE_REQ_RECV);
354 /* FEC.1.DUI3,4 */
355 if (ldp_label_mapping_with_xc(g, peer, f, &us_attr, ds_attr) !=
356 MPLS_SUCCESS) {
357 if (!us_attr->in_tree) {
358 ldp_attr_remove_complete(g, us_attr, MPLS_BOOL_FALSE);
360 goto next_peer;
362 } else {
364 *LDP_CONTROL_ORDERED
367 if (ds_attr || (egress == MPLS_BOOL_TRUE)) { /* FEC.1.DUO2 */
368 if (!(us_attr = ldp_attr_create(&f->info))) {
369 return MPLS_FAILURE;
371 /* FEC.1.DUO3-4 */
372 if (ldp_label_mapping_with_xc(g, peer, f, &us_attr, ds_attr) !=
373 MPLS_SUCCESS) {
374 return MPLS_FAILURE;
379 next_peer:
380 peer = MPLS_LIST_NEXT(&g->session, peer, _global);
383 if (ds_attr) { /* FEC.2 */
384 /* does this send an updated mapping? */
385 if (ldp_label_mapping_process(g, nh_session, NULL, NULL, ds_attr, f) ==
386 MPLS_FAILURE) { /* FEC.5 */
387 return MPLS_FAILURE;
389 return MPLS_SUCCESS;
393 * LDP_DISTRIBUTION_ONDEMAND
395 /* FEC.3 */
396 if (nh_session &&
397 nh_session->oper_distribution_mode == LDP_DISTRIBUTION_ONDEMAND) {
398 /* assume we're always "request when needed" */
399 ds_attr = NULL;
400 if (ldp_label_request_for_xc(g, nh_session, &f->info, NULL, &ds_attr) ==
401 MPLS_FAILURE) { /* FEC.4 */
402 return MPLS_FAILURE;
406 LDP_EXIT(g->user_data, "ldp_fec_process_add");
408 return MPLS_SUCCESS; /* FEC.6 */
411 mpls_return_enum ldp_fec_process_change(ldp_global * g, ldp_fec * f,
412 ldp_nexthop *nh, ldp_nexthop *nh_old, ldp_session *nh_session_old) {
413 ldp_session *peer = NULL;
414 ldp_attr *us_attr = NULL;
415 ldp_attr *ds_attr = NULL;
416 ldp_session *nh_session = NULL;
418 LDP_ENTER(g->user_data,
419 "ldp_fec_process_change: fec %p nh %p nh_old %p nh_session_old %p",
420 f, nh, nh_old, nh_session_old);
422 if (!nh_session_old) {
423 nh_session_old = ldp_session_for_nexthop(nh_old);
427 * NH 1-5 decide if we need to release an existing mapping
429 ds_attr = ldp_attr_find_downstream_state2(g, nh_session_old, f,
430 LDP_LSP_STATE_MAP_RECV);
431 if (!ds_attr) { /* NH.1 */
432 goto Detect_Change_Fec_Next_Hop_6;
435 if (ds_attr->ingress == MPLS_BOOL_TRUE) {
437 #if MPLS_USE_LSR
438 lsr_ftn ftn;
439 ftn.outsegment_index = ds_attr->outlabel->info.handle;
440 memcpy(&ftn.fec, &f->info, sizeof(mpls_fec));
441 lsr_cfg_ftn_set2(g->lsr_handle, &ftn, LSR_CFG_DEL);
442 #else
443 mpls_mpls_fec2out_del(g->mpls_handle, &f->info, &ds_attr->outlabel->info);
444 #endif
445 ds_attr->ingress = MPLS_BOOL_FALSE;
446 ds_attr->outlabel->merge_count--;
449 if (g->label_retention_mode == LDP_RETENTION_LIBERAL) { /* NH.3 */
450 ldp_attr *us_temp;
451 us_attr = MPLS_LIST_HEAD(&ds_attr->us_attr_root);
452 while (us_attr) {
453 /* need to walk the list in such a way as not to
454 * "pull the rug out from under me self"
456 us_temp = MPLS_LIST_NEXT(&ds_attr->us_attr_root, us_attr, _ds_attr);
457 if (us_attr->state == LDP_LSP_STATE_MAP_SENT) {
458 ldp_inlabel_del_outlabel(g, us_attr->inlabel); /* NH.2 */
459 ldp_attr_del_us2ds(us_attr, ds_attr);
461 us_attr = us_temp;
463 goto Detect_Change_Fec_Next_Hop_6;
466 ldp_label_release_send(g, nh_session_old, ds_attr, LDP_NOTIF_NONE); /* NH.4 */
467 ldp_attr_remove_complete(g, ds_attr, MPLS_BOOL_FALSE); /* NH.2,5 */
469 Detect_Change_Fec_Next_Hop_6:
472 * NH 6-9 decides is we need to send a label request abort
474 ds_attr = ldp_attr_find_downstream_state2(g, nh_session_old, f,
475 LDP_LSP_STATE_REQ_SENT);
476 if (ds_attr) { /* NH.6 */
477 if (g->label_retention_mode != LDP_RETENTION_CONSERVATIVE) { /* NH.7 */
478 /* NH.8,9 */
479 if (ldp_label_abort_send(g, nh_session_old, ds_attr) != MPLS_SUCCESS) {
480 return MPLS_FAILURE;
486 * NH 10-12 decides if we can use a mapping from our database
488 if ((!nh) || (!(nh_session = ldp_get_next_hop_session_for_fec2(f,nh)))) {
489 goto Detect_Change_Fec_Next_Hop_16;
492 ds_attr = ldp_attr_find_downstream_state2(g, nh_session, f,
493 LDP_LSP_STATE_MAP_RECV);
494 if (!ds_attr) { /* NH.11 */
495 goto Detect_Change_Fec_Next_Hop_13;
498 if (ldp_label_mapping_process(g, nh_session, NULL, NULL, ds_attr, f) !=
499 MPLS_SUCCESS) { /* NH.12 */
500 return MPLS_FAILURE;
502 goto Detect_Change_Fec_Next_Hop_20;
504 Detect_Change_Fec_Next_Hop_13:
507 * NH 13-15 decides if we need to make a label request
509 if (nh_session->oper_distribution_mode == LDP_DISTRIBUTION_ONDEMAND &&
510 g->label_retention_mode == LDP_RETENTION_CONSERVATIVE) {
511 /* NH.14-15 */
512 if (ldp_label_request_for_xc(g, nh_session, &f->info, NULL, &ds_attr) !=
513 MPLS_SUCCESS) {
514 return MPLS_FAILURE;
517 goto Detect_Change_Fec_Next_Hop_20;
519 Detect_Change_Fec_Next_Hop_16:
521 peer = MPLS_LIST_HEAD(&g->session);
522 while (peer) {
523 if (peer->state == LDP_STATE_OPERATIONAL) {
524 us_attr = ldp_attr_find_upstream_state2(g, peer, f,
525 LDP_LSP_STATE_MAP_SENT);
526 if (us_attr) { /* NH.17 */
527 if (ldp_label_withdraw_send(g, peer, us_attr, LDP_NOTIF_NONE) !=
528 MPLS_SUCCESS) { /* NH.18 */
529 ldp_attr_remove_complete(g, us_attr, MPLS_BOOL_FALSE);
530 return MPLS_FAILURE;
534 peer = MPLS_LIST_NEXT(&g->session, peer, _global);
537 Detect_Change_Fec_Next_Hop_20:
539 LDP_EXIT(g->user_data, "ldp_fec_process_change");
541 return MPLS_SUCCESS;
544 void mpls_fec2ldp_fec(mpls_fec * a, ldp_fec * b)
546 memcpy(&b->info, a, sizeof(mpls_fec));
549 void mpls_fec2fec_tlv(mpls_fec * lf, mplsLdpFecTlv_t * tlv, int i)
551 tlv->fecElArray[i].addressEl.addressFam = 1;
553 switch (lf->type) {
554 case MPLS_FEC_PREFIX:
555 tlv->fecElArray[i].addressEl.type = MPLS_PREFIX_FEC;
556 tlv->fecElArray[i].addressEl.preLen = lf->u.prefix.length;
557 tlv->fecElArray[i].addressEl.address = lf->u.prefix.network.u.ipv4;
558 tlv->fecElemTypes[i] = MPLS_PREFIX_FEC;
559 break;
560 case MPLS_FEC_HOST:
561 tlv->fecElArray[i].addressEl.type = MPLS_HOSTADR_FEC;
562 tlv->fecElArray[i].addressEl.preLen = MPLS_IPv4LEN;
563 tlv->fecElArray[i].addressEl.address = lf->u.host.u.ipv4;
564 tlv->fecElemTypes[i] = MPLS_HOSTADR_FEC;
565 break;
566 default:
567 MPLS_ASSERT(0);
571 void fec_tlv2mpls_fec(mplsLdpFecTlv_t * tlv, int i, mpls_fec * lf) {
572 switch (tlv->fecElemTypes[i]) {
573 case MPLS_PREFIX_FEC:
574 lf->type = MPLS_FEC_PREFIX;
575 lf->u.prefix.length = tlv->fecElArray[i].addressEl.preLen;
576 lf->u.prefix.network.u.ipv4 = tlv->fecElArray[i].addressEl.address;
577 lf->u.prefix.network.type = MPLS_FAMILY_IPV4;
578 break;
579 case MPLS_HOSTADR_FEC:
580 lf->type = MPLS_FEC_HOST;
581 lf->u.host.u.ipv4 = tlv->fecElArray[i].addressEl.address;
582 lf->u.host.type = MPLS_FAMILY_IPV4;
583 break;
584 default:
585 MPLS_ASSERT(0);
589 mpls_bool ldp_fec_empty(ldp_fec *fec)
591 if (MPLS_LIST_EMPTY(&fec->fs_root_us) &&
592 MPLS_LIST_EMPTY(&fec->nh_root) &&
593 MPLS_LIST_EMPTY(&fec->fs_root_ds)) {
594 return MPLS_BOOL_TRUE;
596 return MPLS_BOOL_FALSE;