Various bug fixes to get basic label distribution working again
[mpls-ldp-portable.git] / ldp / ldp_fec.c
blob1d6e4c51b03314ad212d694aed9b8771c9d771b1
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 case MPLS_FEC_L2CC:
72 if (ldp_global_find_fec(g, fec, &f) == MPLS_SUCCESS) {
73 return f;
75 return NULL;
76 default:
77 MPLS_ASSERT(0);
80 if (mpls_tree_get(g->fec_tree, key, len, (void **)&f) != MPLS_SUCCESS) {
81 return NULL;
83 return f;
86 mpls_return_enum ldp_fec_insert2(ldp_global *g, ldp_fec * fec)
88 uint32_t key;
89 uint8_t len;
91 MPLS_ASSERT(MPLS_LIST_EMPTY(&fec->nh_root));
93 switch(fec->info.type) {
94 case MPLS_FEC_PREFIX:
95 key = fec->info.u.prefix.network.u.ipv4;
96 len = fec->info.u.prefix.length;
97 break;
98 case MPLS_FEC_HOST:
99 key = fec->info.u.host.u.ipv4;
100 len = 32;
101 case MPLS_FEC_L2CC:
102 /* they had better insert it into the global list */
103 return MPLS_SUCCESS;
104 default:
105 MPLS_ASSERT(0);
108 /* hold it since it is going in the tree */
109 MPLS_REFCNT_HOLD(fec);
111 if (mpls_tree_insert(g->fec_tree, key, len, (void *)fec) != MPLS_SUCCESS) {
112 LDP_PRINT(g->user_data, "ldp_fec_insert: error adding addr\n");
114 /* delete the refcnt we just took */
115 MPLS_REFCNT_RELEASE(fec, ldp_fec_delete);
116 goto ldp_fec_insert2_error;
118 return MPLS_SUCCESS;
120 ldp_fec_insert2_error:
121 return MPLS_FATAL;
124 ldp_fec *ldp_fec_insert(ldp_global *g, mpls_fec * fec)
126 ldp_fec *f = NULL;
128 if ((f = ldp_fec_create()) == NULL) {
129 LDP_PRINT(g->user_data, "ldp_fec_insert: error creating address\n");
130 return NULL;
133 mpls_fec2ldp_fec(fec,f);
135 MPLS_REFCNT_HOLD(f);
137 if (ldp_fec_insert2(g,f) != MPLS_SUCCESS) {
138 MPLS_REFCNT_RELEASE(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 switch(fec->type) {
161 case MPLS_FEC_PREFIX:
162 key = fec->u.prefix.network.u.ipv4;
163 len = fec->u.prefix.length;
164 break;
165 case MPLS_FEC_HOST:
166 key = fec->u.host.u.ipv4;
167 len = 32;
168 case MPLS_FEC_L2CC:
169 /* they had better remove it from the global list */
170 return;
171 default:
172 MPLS_ASSERT(0);
175 mpls_tree_remove(g->fec_tree, key, len, (void **)&f);
176 if (!f) {
177 return;
180 MPLS_ASSERT(MPLS_LIST_EMPTY(&f->nh_root));
182 MPLS_REFCNT_RELEASE(f, ldp_fec_delete);
185 mpls_bool ldp_fec_empty(ldp_fec *fec)
187 if (MPLS_LIST_EMPTY(&fec->fs_root_us) &&
188 MPLS_LIST_EMPTY(&fec->fs_root_ds)) {
189 return MPLS_BOOL_TRUE;
191 return MPLS_BOOL_FALSE;
194 mpls_return_enum ldp_fec_find_nexthop_index(ldp_fec *f, int index,
195 ldp_nexthop **n)
197 ldp_nexthop *nh = NULL;
199 MPLS_ASSERT(f);
201 if (index > 0) {
203 /* because we sort our inserts by index, this lets us know
204 if we've "walked" past the end of the list */
206 nh = MPLS_LIST_TAIL(&f->nh_root);
207 if (!nh || nh->index < index) {
208 *n = NULL;
209 return MPLS_END_OF_LIST;
212 nh = MPLS_LIST_HEAD(&f->nh_root);
213 do {
214 if (nh->index == index) {
215 *n = nh;
216 return MPLS_SUCCESS;
218 } while((nh = MPLS_LIST_NEXT(&f->nh_root, nh, _fec)));
220 *n = NULL;
221 return MPLS_FAILURE;
224 mpls_return_enum ldp_fec_add_nexthop(ldp_global *g, ldp_fec * f,
225 ldp_nexthop * nh)
227 MPLS_ASSERT(f && nh);
229 MPLS_REFCNT_HOLD(nh);
230 MPLS_LIST_ADD_HEAD(&f->nh_root, nh, _fec, ldp_nexthop);
232 ldp_nexthop_add_fec(nh, f);
234 if (nh->type & MPLS_NH_IP) {
235 ldp_addr *addr = NULL;
236 if (!(addr = ldp_addr_find(g, &nh->info.ip))) {
237 if (!(addr = ldp_addr_insert(g, &nh->info.ip))) {
238 goto ldp_fec_add_nexthop_error;
242 ldp_addr_add_nexthop(addr, nh);
245 if (nh->type & MPLS_NH_IF) {
246 ldp_if *iff = NULL;
247 if ((iff = ldp_global_find_if_handle(g, nh->info.if_handle))) {
248 ldp_if_add_nexthop(iff, nh);
252 if (nh->type & MPLS_NH_OUTSEGMENT) {
253 ldp_outlabel *out = NULL;
254 MPLS_ASSERT((out = ldp_global_find_outlabel_handle(g,
255 nh->info.outsegment_handle)));
257 ldp_outlabel_add_nexthop(out, nh);
259 return MPLS_SUCCESS;
261 ldp_fec_add_nexthop_error:
263 ldp_fec_del_nexthop(g, f, nh);
264 return MPLS_FATAL;
267 void ldp_fec_del_nexthop(ldp_global *g, ldp_fec * f, ldp_nexthop *nh)
269 MPLS_ASSERT(f && nh);
271 if (nh->addr) {
272 ldp_addr_del_nexthop(g, nh->addr, nh);
274 if (nh->iff) {
275 ldp_if_del_nexthop(g, nh->iff, nh);
277 if (nh->outlabel) {
278 ldp_outlabel_del_nexthop(nh->outlabel, nh);
281 MPLS_LIST_REMOVE(&f->nh_root, nh, _fec);
282 ldp_nexthop_del_fec(nh);
284 MPLS_REFCNT_RELEASE(nh, ldp_nexthop_delete);
287 mpls_return_enum ldp_fec_process_add(ldp_global * g, ldp_fec * f,
288 ldp_nexthop *nh)
290 ldp_session *nh_session = NULL;
291 ldp_session *peer = NULL;
292 ldp_attr *ds_attr = NULL;
293 ldp_attr *us_attr = NULL;
294 mpls_bool egress = MPLS_BOOL_FALSE;
295 ldp_outlabel *out;
297 LDP_ENTER(g->user_data, "ldp_fec_process_add");
300 * find the info about the next hop for this FEC
302 nh_session = ldp_session_for_nexthop(nh);
304 if (nh_session) {
305 ds_attr = ldp_attr_find_downstream_state2(g, nh_session, f,
306 LDP_LSP_STATE_MAP_RECV);
307 if (ds_attr && !ds_attr->outlabel) {
308 out = ldp_outlabel_create_complete(g, nh_session, ds_attr, nh);
309 if (!out) {
310 return MPLS_FAILURE;
312 ds_attr->outlabel = out;
317 * for every peer except the nh hop peer, check to see if we need to
318 * send a mapping
320 peer = MPLS_LIST_HEAD(&g->session);
321 while (peer != NULL) { /* FEC.1 */
322 if ((peer->state != LDP_STATE_OPERATIONAL) ||
323 (nh_session && peer->index == nh_session->index)) {
324 goto next_peer;
326 /* have I already sent a mapping for FEC to peer */
327 if ((us_attr = ldp_attr_find_upstream_state2(g, peer, f,
328 LDP_LSP_STATE_MAP_SENT))) {
329 /* yep, don't send another */
330 if (ds_attr) {
331 if (ldp_inlabel_add_outlabel(g, us_attr->inlabel,
332 ds_attr->outlabel) != MPLS_SUCCESS) {
333 return MPLS_FAILURE;
336 goto next_peer;
339 if (peer->oper_distribution_mode == LDP_DISTRIBUTION_UNSOLICITED) {
340 if (g->lsp_control_mode == LDP_CONTROL_INDEPENDENT) {
341 us_attr =
342 ldp_attr_find_upstream_state2(g, peer, f, LDP_LSP_STATE_REQ_RECV);
344 /* FEC.1.DUI3,4 */
345 if (ldp_label_mapping_with_xc(g, peer, f, &us_attr, ds_attr) !=
346 MPLS_SUCCESS) {
347 if (!us_attr->in_tree) {
348 ldp_attr_remove_complete(g, us_attr, MPLS_BOOL_FALSE);
350 goto next_peer;
352 } else {
354 *LDP_CONTROL_ORDERED
357 if (ds_attr || egress == MPLS_BOOL_TRUE) { /* FEC.1.DUO2 */
358 if (!(us_attr = ldp_attr_create(&f->info))) {
359 return MPLS_FAILURE;
361 /* FEC.1.DUO3-4 */
362 if ((egress == MPLS_BOOL_TRUE) && (mpls_policy_egress_check(
363 g->user_data, &f->info, &nh->info) == MPLS_BOOL_TRUE)) {
364 goto next_peer;
367 if (ldp_label_mapping_with_xc(g, peer, f, &us_attr, ds_attr) !=
368 MPLS_SUCCESS) {
369 return MPLS_FAILURE;
374 next_peer:
375 peer = MPLS_LIST_NEXT(&g->session, peer, _global);
378 if (ds_attr) { /* FEC.2 */
379 if (ldp_label_mapping_process(g, nh_session, NULL, NULL, ds_attr, f) ==
380 MPLS_FAILURE) { /* FEC.5 */
381 return MPLS_FAILURE;
383 return MPLS_SUCCESS;
387 * LDP_DISTRIBUTION_ONDEMAND
389 /* FEC.3 */
390 if (nh_session &&
391 nh_session->oper_distribution_mode == LDP_DISTRIBUTION_ONDEMAND) {
392 /* assume we're always "request when needed" */
393 ds_attr = NULL;
394 if (ldp_label_request_for_xc(g, nh_session, &f->info, NULL, &ds_attr) ==
395 MPLS_FAILURE) { /* FEC.4 */
396 return MPLS_FAILURE;
400 LDP_EXIT(g->user_data, "ldp_fec_process_add");
402 return MPLS_SUCCESS; /* FEC.6 */
405 mpls_return_enum ldp_fec_process_change(ldp_global * g, ldp_fec * f,
406 ldp_nexthop *nh, ldp_session *nh_session_old) {
407 ldp_session *peer = NULL;
408 ldp_attr *us_attr = NULL;
409 ldp_attr *ds_attr = NULL;
410 ldp_session *nh_session_new = NULL;
412 LDP_ENTER(g->user_data, "ldp_fec_process_change");
415 * NH 1-5 decide if we need to release an existing mapping
417 ds_attr = ldp_attr_find_downstream_state2(g, nh_session_old, f,
418 LDP_LSP_STATE_MAP_RECV);
419 if (!ds_attr) { /* NH.1 */
420 goto Detect_Change_Fec_Next_Hop_6;
423 if (ds_attr->ingress == MPLS_BOOL_TRUE) {
425 #if MPLS_USE_LSR
426 lsr_ftn ftn;
427 ftn.outsegment_index = ds_attr->outlabel->info.handle;
428 memcpy(&ftn.fec, &f->info, sizeof(mpls_fec));
429 lsr_cfg_ftn_set2(g->lsr_handle, &ftn, LSR_CFG_DEL);
430 #else
431 mpls_mpls_fec2out_del(g->mpls_handle, &f->info, &ds_attr->outlabel->info);
432 #endif
433 ds_attr->ingress = MPLS_BOOL_FALSE;
434 ds_attr->outlabel->merge_count--;
437 if (g->label_retention_mode == LDP_RETENTION_LIBERAL) { /* NH.3 */
438 ldp_attr *us_temp;
439 us_attr = MPLS_LIST_HEAD(&ds_attr->us_attr_root);
440 while (us_attr) {
441 /* need to walk the list in such a way as not to
442 * "pull the rug out from under me self"
444 us_temp = MPLS_LIST_NEXT(&ds_attr->us_attr_root, us_attr, _ds_attr);
445 if (us_attr->state == LDP_LSP_STATE_MAP_SENT) {
446 ldp_inlabel_del_outlabel(g, us_attr->inlabel); /* NH.2 */
447 ldp_attr_del_us2ds(us_attr, ds_attr);
449 us_attr = us_temp;
451 goto Detect_Change_Fec_Next_Hop_6;
454 ldp_label_release_send(g, nh_session_old, ds_attr, LDP_NOTIF_NONE); /* NH.4 */
455 ldp_attr_remove_complete(g, ds_attr, MPLS_BOOL_FALSE); /* NH.2,5 */
457 Detect_Change_Fec_Next_Hop_6:
460 * NH 6-9 decides is we need to send a label request abort
462 ds_attr = ldp_attr_find_downstream_state2(g, nh_session_old, f,
463 LDP_LSP_STATE_REQ_SENT);
464 if (ds_attr) { /* NH.6 */
465 if (g->label_retention_mode != LDP_RETENTION_CONSERVATIVE) { /* NH.7 */
466 /* NH.8,9 */
467 if (ldp_label_abort_send(g, nh_session_old, ds_attr) != MPLS_SUCCESS) {
468 return MPLS_FAILURE;
474 * NH 10-12 decides if we can use a mapping from our database
476 if (!(nh_session_new = ldp_get_next_hop_session_for_fec2(f,nh))) {
477 goto Detect_Change_Fec_Next_Hop_16;
480 ds_attr = ldp_attr_find_downstream_state2(g, nh_session_new, f,
481 LDP_LSP_STATE_MAP_RECV);
482 if (!ds_attr) { /* NH.11 */
483 goto Detect_Change_Fec_Next_Hop_13;
486 if (ldp_label_mapping_process(g, nh_session_new, NULL, NULL, ds_attr, f) !=
487 MPLS_SUCCESS) { /* NH.12 */
488 return MPLS_FAILURE;
490 goto Detect_Change_Fec_Next_Hop_20;
492 Detect_Change_Fec_Next_Hop_13:
495 * NH 13-15 decides if we need to make a label request
497 if (nh_session_new->oper_distribution_mode == LDP_DISTRIBUTION_ONDEMAND &&
498 g->label_retention_mode == LDP_RETENTION_CONSERVATIVE) {
499 /* NH.14-15 */
500 if (ldp_label_request_for_xc(g, nh_session_new, &f->info, NULL, &ds_attr) !=
501 MPLS_SUCCESS) {
502 return MPLS_FAILURE;
505 goto Detect_Change_Fec_Next_Hop_20;
507 Detect_Change_Fec_Next_Hop_16:
509 peer = MPLS_LIST_HEAD(&g->session);
510 while (peer) {
511 if (peer->state == LDP_STATE_OPERATIONAL) {
512 us_attr = ldp_attr_find_upstream_state2(g, peer, f,
513 LDP_LSP_STATE_MAP_SENT);
514 if (us_attr) { /* NH.17 */
515 if (ldp_label_withdraw_send(g, peer, us_attr, LDP_NOTIF_NONE) !=
516 MPLS_SUCCESS) { /* NH.18 */
517 ldp_attr_remove_complete(g, us_attr, MPLS_BOOL_FALSE);
518 return MPLS_FAILURE;
522 peer = MPLS_LIST_NEXT(&g->session, peer, _global);
525 Detect_Change_Fec_Next_Hop_20:
527 LDP_EXIT(g->user_data, "ldp_fec_process_change");
529 return MPLS_SUCCESS;
532 ldp_fec *ldp_fec_create()
534 ldp_fec *fec = (ldp_fec *) mpls_malloc(sizeof(ldp_fec));
536 if (fec != NULL) {
537 memset(fec, 0, sizeof(ldp_fec));
538 MPLS_REFCNT_INIT(fec, 0);
539 MPLS_LIST_ELEM_INIT(fec, _global);
540 MPLS_LIST_ELEM_INIT(fec, _inlabel);
541 MPLS_LIST_ELEM_INIT(fec, _outlabel);
542 MPLS_LIST_ELEM_INIT(fec, _fec);
543 MPLS_LIST_INIT(&fec->nh_root, ldp_nexthop);
544 MPLS_LIST_INIT(&fec->fs_root_us, ldp_fs);
545 MPLS_LIST_INIT(&fec->fs_root_ds, ldp_fs);
546 fec->info.type = MPLS_FEC_NONE;
547 fec->index = _ldp_fec_get_next_index();
549 return fec;
552 void mpls_fec2ldp_fec(mpls_fec * a, ldp_fec * b)
554 memcpy(&b->info, a, sizeof(mpls_fec));
557 ldp_fec *ldp_fec_create_host(mpls_inet_addr * host)
559 ldp_fec *fec = ldp_fec_create();
561 if (fec != NULL) {
562 fec->info.type = MPLS_FEC_HOST;
563 memcpy(&fec->info.u.host, host, sizeof(mpls_inet_addr));
565 return fec;
568 ldp_fec *ldp_fec_create_prefix(mpls_inet_addr * prefix, int prefix_len)
570 ldp_fec *fec = ldp_fec_create();
572 if (fec != NULL) {
573 fec->info.type = MPLS_FEC_PREFIX;
574 memcpy(&fec->info.u.prefix.network, prefix, sizeof(mpls_inet_addr));
575 fec->info.u.prefix.length = prefix_len;
577 return fec;
580 void ldp_fec_delete(ldp_fec * fec)
582 mpls_free(fec);
585 void mpls_fec2fec_tlv(mpls_fec * lf, mplsLdpFecTlv_t * tlv, int i)
587 tlv->fecElArray[i].addressEl.addressFam = 1;
589 switch (lf->type) {
590 case MPLS_FEC_PREFIX:
591 tlv->fecElArray[i].addressEl.type = MPLS_PREFIX_FEC;
592 tlv->fecElArray[i].addressEl.preLen = lf->u.prefix.length;
593 tlv->fecElArray[i].addressEl.address = lf->u.prefix.network.u.ipv4;
594 tlv->fecElemTypes[i] = MPLS_PREFIX_FEC;
595 break;
596 case MPLS_FEC_HOST:
597 tlv->fecElArray[i].addressEl.type = MPLS_HOSTADR_FEC;
598 tlv->fecElArray[i].addressEl.preLen = MPLS_IPv4LEN;
599 tlv->fecElArray[i].addressEl.address = lf->u.host.u.ipv4;
600 tlv->fecElemTypes[i] = MPLS_HOSTADR_FEC;
601 break;
602 default:
603 MPLS_ASSERT(0);
607 void fec_tlv2mpls_fec(mplsLdpFecTlv_t * tlv, int i, mpls_fec * lf) {
608 switch (tlv->fecElemTypes[i]) {
609 case MPLS_PREFIX_FEC:
610 lf->type = MPLS_FEC_PREFIX;
611 lf->u.prefix.length = tlv->fecElArray[i].addressEl.preLen;
612 lf->u.prefix.network.u.ipv4 = tlv->fecElArray[i].addressEl.address;
613 lf->u.prefix.network.type = MPLS_FAMILY_IPV4;
614 break;
615 case MPLS_HOSTADR_FEC:
616 lf->type = MPLS_FEC_HOST;
617 lf->u.host.u.ipv4 = tlv->fecElArray[i].addressEl.address;
618 lf->u.host.type = MPLS_FAMILY_IPV4;
619 break;
620 default:
621 MPLS_ASSERT(0);
625 static uint32_t _ldp_fec_get_next_index()
627 uint32_t retval = _ldp_fec_next_index;
629 _ldp_fec_next_index++;
630 if (retval > _ldp_fec_next_index) {
631 _ldp_fec_next_index = 1;
633 return retval;