Ability to walk global addr list
[mpls-ldp-portable.git] / ldp / ldp_fec.c
blobc8149f3b86ea06d249faedd7c2eba017dcbc6a13
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 void ldp_fec_remove(ldp_global *g, mpls_fec *fec)
146 ldp_fec *f = NULL;
147 uint32_t key;
148 uint8_t len;
150 switch(fec->type) {
151 case MPLS_FEC_PREFIX:
152 key = fec->u.prefix.network.u.ipv4;
153 len = fec->u.prefix.length;
154 break;
155 case MPLS_FEC_HOST:
156 key = fec->u.host.u.ipv4;
157 len = 32;
158 case MPLS_FEC_L2CC:
159 /* they had better remove it from the global list */
160 return;
161 default:
162 MPLS_ASSERT(0);
165 mpls_tree_remove(g->fec_tree, key, len, (void **)&f);
166 if (!f) {
167 return;
170 MPLS_ASSERT(MPLS_LIST_EMPTY(&f->nh_root));
172 MPLS_REFCNT_RELEASE(f, ldp_fec_delete);
175 mpls_bool ldp_fec_empty(ldp_fec *fec)
177 if (MPLS_LIST_EMPTY(&fec->fs_root_us) &&
178 MPLS_LIST_EMPTY(&fec->fs_root_ds)) {
179 return MPLS_BOOL_TRUE;
181 return MPLS_BOOL_FALSE;
184 mpls_return_enum ldp_fec_find_nexthop_index(ldp_fec *f, int index,
185 ldp_nexthop **n)
187 ldp_nexthop *nh = NULL;
189 MPLS_ASSERT(f);
191 if (index > 0) {
193 /* because we sort our inserts by index, this lets us know
194 if we've "walked" past the end of the list */
196 nh = MPLS_LIST_TAIL(&f->nh_root);
197 if (!nh || nh->index < index) {
198 *n = NULL;
199 return MPLS_END_OF_LIST;
202 nh = MPLS_LIST_HEAD(&f->nh_root);
203 do {
204 if (nh->index == index) {
205 *n = nh;
206 return MPLS_SUCCESS;
208 } while((nh = MPLS_LIST_NEXT(&f->nh_root, nh, _fec)));
210 *n = NULL;
211 return MPLS_FAILURE;
214 mpls_return_enum ldp_fec_add_nexthop(ldp_global *g, ldp_fec * f,
215 ldp_nexthop * nh)
217 MPLS_ASSERT(f && nh);
219 MPLS_REFCNT_HOLD(nh);
220 MPLS_LIST_ADD_HEAD(&f->nh_root, nh, _fec, ldp_nexthop);
222 ldp_nexthop_add_fec(nh, f);
224 if (nh->type & MPLS_NH_IP) {
225 ldp_addr *addr = NULL;
226 if (!(addr = ldp_addr_find(g, &nh->info.ip))) {
227 if (!(addr = ldp_addr_insert(g, &nh->info.ip))) {
228 goto ldp_fec_add_nexthop_error;
232 ldp_addr_add_nexthop(addr, nh);
235 if (nh->type & MPLS_NH_IF) {
236 ldp_if *iff = NULL;
237 if ((iff = ldp_global_find_if_handle(g, nh->info.if_handle))) {
238 ldp_if_add_nexthop(iff, nh);
242 if (nh->type & MPLS_NH_OUTSEGMENT) {
243 ldp_outlabel *out = NULL;
244 MPLS_ASSERT((out = ldp_global_find_outlabel_handle(g,
245 nh->info.outsegment_handle)));
247 ldp_outlabel_add_nexthop(out, nh);
249 return MPLS_SUCCESS;
251 ldp_fec_add_nexthop_error:
253 ldp_fec_del_nexthop(g, f, nh);
254 return MPLS_FATAL;
257 void ldp_fec_del_nexthop(ldp_global *g, ldp_fec * f, ldp_nexthop *nh)
259 MPLS_ASSERT(f && nh);
261 if (nh->addr) {
262 ldp_addr_del_nexthop(g, nh->addr, nh);
264 if (nh->iff) {
265 ldp_if_del_nexthop(g, nh->iff, nh);
267 if (nh->outlabel) {
268 ldp_outlabel_del_nexthop(nh->outlabel, nh);
271 MPLS_LIST_REMOVE(&f->nh_root, nh, _fec);
272 ldp_nexthop_del_fec(nh);
274 MPLS_REFCNT_RELEASE(nh, ldp_nexthop_delete);
277 mpls_return_enum ldp_fec_process_add(ldp_global * g, ldp_fec * f,
278 ldp_nexthop *nh)
280 ldp_session *nh_session = NULL;
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;
287 LDP_ENTER(g->user_data, "ldp_fec_process_add");
290 * find the info about the next hop for this FEC
292 nh_session = ldp_session_for_nexthop(nh);
294 if (nh_session) {
295 ds_attr = ldp_attr_find_downstream_state2(g, nh_session, f,
296 LDP_LSP_STATE_MAP_RECV);
297 if (ds_attr && !ds_attr->outlabel) {
298 out = ldp_outlabel_create_complete(g, nh_session, ds_attr, nh);
299 if (!out) {
300 return MPLS_FAILURE;
302 ds_attr->outlabel = out;
307 * for every peer except the nh hop peer, check to see if we need to
308 * send a mapping
310 peer = MPLS_LIST_HEAD(&g->session);
311 while (peer != NULL) { /* FEC.1 */
312 if ((peer->state != LDP_STATE_OPERATIONAL) ||
313 (nh_session && peer->index == nh_session->index)) {
314 goto next_peer;
316 /* have I already sent a mapping for FEC to peer */
317 if ((us_attr = ldp_attr_find_upstream_state2(g, peer, f,
318 LDP_LSP_STATE_MAP_SENT))) {
319 /* yep, don't send another */
320 if (ds_attr) {
321 if (ldp_inlabel_add_outlabel(g, us_attr->inlabel,
322 ds_attr->outlabel) != MPLS_SUCCESS) {
323 return MPLS_FAILURE;
326 goto next_peer;
329 if (peer->oper_distribution_mode == LDP_DISTRIBUTION_UNSOLICITED) {
330 if (g->lsp_control_mode == LDP_CONTROL_INDEPENDENT) {
331 us_attr =
332 ldp_attr_find_upstream_state2(g, peer, f, LDP_LSP_STATE_REQ_RECV);
334 /* FEC.1.DUI3,4 */
335 if (ldp_label_mapping_with_xc(g, peer, f, &us_attr, ds_attr) !=
336 MPLS_SUCCESS) {
337 if (!us_attr->in_tree) {
338 ldp_attr_remove_complete(g, us_attr, MPLS_BOOL_FALSE);
340 goto next_peer;
342 } else {
344 *LDP_CONTROL_ORDERED
347 if (ds_attr || egress == MPLS_BOOL_TRUE) { /* FEC.1.DUO2 */
348 if (!(us_attr = ldp_attr_create(&f->info))) {
349 return MPLS_FAILURE;
351 /* FEC.1.DUO3-4 */
352 if ((egress == MPLS_BOOL_TRUE) && (mpls_policy_egress_check(
353 g->user_data, &f->info, &nh->info) == MPLS_BOOL_TRUE)) {
354 goto next_peer;
357 if (ldp_label_mapping_with_xc(g, peer, f, &us_attr, ds_attr) !=
358 MPLS_SUCCESS) {
359 return MPLS_FAILURE;
364 next_peer:
365 peer = MPLS_LIST_NEXT(&g->session, peer, _global);
368 if (ds_attr) { /* FEC.2 */
369 if (ldp_label_mapping_process(g, nh_session, NULL, NULL, ds_attr, f) ==
370 MPLS_FAILURE) { /* FEC.5 */
371 return MPLS_FAILURE;
373 return MPLS_SUCCESS;
377 * LDP_DISTRIBUTION_ONDEMAND
379 /* FEC.3 */
380 if (nh_session &&
381 nh_session->oper_distribution_mode == LDP_DISTRIBUTION_ONDEMAND) {
382 /* assume we're always "request when needed" */
383 ds_attr = NULL;
384 if (ldp_label_request_for_xc(g, nh_session, &f->info, NULL, &ds_attr) ==
385 MPLS_FAILURE) { /* FEC.4 */
386 return MPLS_FAILURE;
390 LDP_EXIT(g->user_data, "ldp_fec_process_add");
392 return MPLS_SUCCESS; /* FEC.6 */
395 mpls_return_enum ldp_fec_process_change(ldp_global * g, ldp_fec * f,
396 ldp_nexthop *nh, ldp_session *nh_session_old) {
397 ldp_session *peer = NULL;
398 ldp_attr *us_attr = NULL;
399 ldp_attr *ds_attr = NULL;
400 ldp_session *nh_session_new = NULL;
402 LDP_ENTER(g->user_data, "ldp_fec_process_change");
405 * NH 1-5 decide if we need to release an existing mapping
407 ds_attr = ldp_attr_find_downstream_state2(g, nh_session_old, f,
408 LDP_LSP_STATE_MAP_RECV);
409 if (!ds_attr) { /* NH.1 */
410 goto Detect_Change_Fec_Next_Hop_6;
413 if (ds_attr->ingress == MPLS_BOOL_TRUE) {
415 #if MPLS_USE_LSR
416 lsr_ftn ftn;
417 ftn.outsegment_index = ds_attr->outlabel->info.handle;
418 memcpy(&ftn.fec, &f->info, sizeof(mpls_fec));
419 lsr_cfg_ftn_set2(g->lsr_handle, &ftn, LSR_CFG_DEL);
420 #else
421 mpls_mpls_fec2out_del(g->mpls_handle, &f->info, &ds_attr->outlabel->info);
422 #endif
423 ds_attr->ingress = MPLS_BOOL_FALSE;
424 ds_attr->outlabel->merge_count--;
427 if (g->label_retention_mode == LDP_RETENTION_LIBERAL) { /* NH.3 */
428 ldp_attr *us_temp;
429 us_attr = MPLS_LIST_HEAD(&ds_attr->us_attr_root);
430 while (us_attr) {
431 /* need to walk the list in such a way as not to
432 * "pull the rug out from under me self"
434 us_temp = MPLS_LIST_NEXT(&ds_attr->us_attr_root, us_attr, _ds_attr);
435 if (us_attr->state == LDP_LSP_STATE_MAP_SENT) {
436 ldp_inlabel_del_outlabel(g, us_attr->inlabel); /* NH.2 */
437 ldp_attr_del_us2ds(us_attr, ds_attr);
439 us_attr = us_temp;
441 goto Detect_Change_Fec_Next_Hop_6;
444 ldp_label_release_send(g, nh_session_old, ds_attr, LDP_NOTIF_NONE); /* NH.4 */
445 ldp_attr_remove_complete(g, ds_attr, MPLS_BOOL_FALSE); /* NH.2,5 */
447 Detect_Change_Fec_Next_Hop_6:
450 * NH 6-9 decides is we need to send a label request abort
452 ds_attr = ldp_attr_find_downstream_state2(g, nh_session_old, f,
453 LDP_LSP_STATE_REQ_SENT);
454 if (ds_attr) { /* NH.6 */
455 if (g->label_retention_mode != LDP_RETENTION_CONSERVATIVE) { /* NH.7 */
456 /* NH.8,9 */
457 if (ldp_label_abort_send(g, nh_session_old, ds_attr) != MPLS_SUCCESS) {
458 return MPLS_FAILURE;
464 * NH 10-12 decides if we can use a mapping from our database
466 if (!(nh_session_new = ldp_get_next_hop_session_for_fec2(f,nh))) {
467 goto Detect_Change_Fec_Next_Hop_16;
470 ds_attr = ldp_attr_find_downstream_state2(g, nh_session_new, f,
471 LDP_LSP_STATE_MAP_RECV);
472 if (!ds_attr) { /* NH.11 */
473 goto Detect_Change_Fec_Next_Hop_13;
476 if (ldp_label_mapping_process(g, nh_session_new, NULL, NULL, ds_attr, f) !=
477 MPLS_SUCCESS) { /* NH.12 */
478 return MPLS_FAILURE;
480 goto Detect_Change_Fec_Next_Hop_20;
482 Detect_Change_Fec_Next_Hop_13:
485 * NH 13-15 decides if we need to make a label request
487 if (nh_session_new->oper_distribution_mode == LDP_DISTRIBUTION_ONDEMAND &&
488 g->label_retention_mode == LDP_RETENTION_CONSERVATIVE) {
489 /* NH.14-15 */
490 if (ldp_label_request_for_xc(g, nh_session_new, &f->info, NULL, &ds_attr) !=
491 MPLS_SUCCESS) {
492 return MPLS_FAILURE;
495 goto Detect_Change_Fec_Next_Hop_20;
497 Detect_Change_Fec_Next_Hop_16:
499 peer = MPLS_LIST_HEAD(&g->session);
500 while (peer) {
501 if (peer->state == LDP_STATE_OPERATIONAL) {
502 us_attr = ldp_attr_find_upstream_state2(g, peer, f,
503 LDP_LSP_STATE_MAP_SENT);
504 if (us_attr) { /* NH.17 */
505 if (ldp_label_withdraw_send(g, peer, us_attr, LDP_NOTIF_NONE) !=
506 MPLS_SUCCESS) { /* NH.18 */
507 ldp_attr_remove_complete(g, us_attr, MPLS_BOOL_FALSE);
508 return MPLS_FAILURE;
512 peer = MPLS_LIST_NEXT(&g->session, peer, _global);
515 Detect_Change_Fec_Next_Hop_20:
517 LDP_EXIT(g->user_data, "ldp_fec_process_change");
519 return MPLS_SUCCESS;
522 ldp_fec *ldp_fec_create()
524 ldp_fec *fec = (ldp_fec *) mpls_malloc(sizeof(ldp_fec));
526 if (fec != NULL) {
527 memset(fec, 0, sizeof(ldp_fec));
528 MPLS_REFCNT_INIT(fec, 0);
529 MPLS_LIST_ELEM_INIT(fec, _global);
530 MPLS_LIST_ELEM_INIT(fec, _inlabel);
531 MPLS_LIST_ELEM_INIT(fec, _outlabel);
532 MPLS_LIST_ELEM_INIT(fec, _fec);
533 MPLS_LIST_INIT(&fec->nh_root, ldp_nexthop);
534 MPLS_LIST_INIT(&fec->fs_root_us, ldp_fs);
535 MPLS_LIST_INIT(&fec->fs_root_ds, ldp_fs);
536 fec->info.type = MPLS_FEC_NONE;
537 fec->index = _ldp_fec_get_next_index();
539 return fec;
542 void mpls_fec2ldp_fec(mpls_fec * a, ldp_fec * b)
544 memcpy(&b->info, a, sizeof(mpls_fec));
547 ldp_fec *ldp_fec_create_host(mpls_inet_addr * host)
549 ldp_fec *fec = ldp_fec_create();
551 if (fec != NULL) {
552 fec->info.type = MPLS_FEC_HOST;
553 memcpy(&fec->info.u.host, host, sizeof(mpls_inet_addr));
555 return fec;
558 ldp_fec *ldp_fec_create_prefix(mpls_inet_addr * prefix, int prefix_len)
560 ldp_fec *fec = ldp_fec_create();
562 if (fec != NULL) {
563 fec->info.type = MPLS_FEC_PREFIX;
564 memcpy(&fec->info.u.prefix.network, prefix, sizeof(mpls_inet_addr));
565 fec->info.u.prefix.length = prefix_len;
567 return fec;
570 void ldp_fec_delete(ldp_fec * fec)
572 mpls_free(fec);
575 void mpls_fec2fec_tlv(mpls_fec * lf, mplsLdpFecTlv_t * tlv, int i)
577 tlv->fecElArray[i].addressEl.addressFam = 1;
579 switch (lf->type) {
580 case MPLS_FEC_PREFIX:
581 tlv->fecElArray[i].addressEl.type = MPLS_PREFIX_FEC;
582 tlv->fecElArray[i].addressEl.preLen = lf->u.prefix.length;
583 tlv->fecElArray[i].addressEl.address = lf->u.prefix.network.u.ipv4;
584 tlv->fecElemTypes[i] = MPLS_PREFIX_FEC;
585 break;
586 case MPLS_FEC_HOST:
587 tlv->fecElArray[i].addressEl.type = MPLS_HOSTADR_FEC;
588 tlv->fecElArray[i].addressEl.preLen = MPLS_IPv4LEN;
589 tlv->fecElArray[i].addressEl.address = lf->u.host.u.ipv4;
590 tlv->fecElemTypes[i] = MPLS_HOSTADR_FEC;
591 break;
592 default:
593 MPLS_ASSERT(0);
597 void fec_tlv2mpls_fec(mplsLdpFecTlv_t * tlv, int i, mpls_fec * lf) {
598 switch (tlv->fecElemTypes[i]) {
599 case MPLS_PREFIX_FEC:
600 lf->type = MPLS_FEC_PREFIX;
601 lf->u.prefix.length = tlv->fecElArray[i].addressEl.preLen;
602 lf->u.prefix.network.u.ipv4 = tlv->fecElArray[i].addressEl.address;
603 lf->u.prefix.network.type = MPLS_FAMILY_IPV4;
604 break;
605 case MPLS_HOSTADR_FEC:
606 lf->type = MPLS_FEC_HOST;
607 lf->u.host.u.ipv4 = tlv->fecElArray[i].addressEl.address;
608 lf->u.host.type = MPLS_FAMILY_IPV4;
609 break;
610 default:
611 MPLS_ASSERT(0);
615 static uint32_t _ldp_fec_get_next_index()
617 uint32_t retval = _ldp_fec_next_index;
619 _ldp_fec_next_index++;
620 if (retval > _ldp_fec_next_index) {
621 _ldp_fec_next_index = 1;
623 return retval;