First step towards making this work:
[mpls-ldp-portable.git] / ldp / ldp_fec.c
blobfb70abace41b0f6a008d8e2a797a7511eb6651d7
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 do {
48 if (!mpls_nexthop_compare(&nh->info, n)) {
49 return nh;
51 nh = MPLS_LIST_NEXT(&f->nh_root, nh, _fec);
52 } while((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 tree */
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 tree */
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 if (!(iff = ldp_if_insert(g, nh->info.if_handle))) {
239 goto ldp_fec_add_nexthop_error;
243 ldp_if_add_nexthop(iff, nh);
246 if (nh->type & MPLS_NH_OUTSEGMENT) {
247 ldp_outlabel *out = NULL;
248 MPLS_ASSERT((out = ldp_global_find_outlabel_handle(g,
249 nh->info.outsegment_handle)));
251 ldp_outlabel_add_nexthop(out, nh);
253 return MPLS_SUCCESS;
255 ldp_fec_add_nexthop_error:
257 ldp_fec_del_nexthop(f, nh);
258 return MPLS_FATAL;
261 void ldp_fec_del_nexthop(ldp_fec * f, ldp_nexthop *nh)
263 MPLS_ASSERT(f && nh);
265 if (nh->addr) {
266 ldp_addr_del_nexthop(nh->addr, nh);
268 if (nh->iff) {
269 ldp_if_del_nexthop(nh->iff, nh);
271 if (nh->outlabel) {
272 ldp_outlabel_del_nexthop(nh->outlabel, nh);
275 MPLS_LIST_REMOVE(&f->nh_root, nh, _fec);
276 ldp_nexthop_del_fec(nh);
278 MPLS_REFCNT_RELEASE(nh, ldp_nexthop_delete);
281 mpls_return_enum ldp_fec_process_add(ldp_global * g, ldp_fec * f,
282 ldp_nexthop *nh)
284 ldp_session *nh_session = NULL;
285 ldp_session *peer = NULL;
286 ldp_attr *ds_attr = NULL;
287 ldp_attr *us_attr = NULL;
288 mpls_bool egress = MPLS_BOOL_FALSE;
289 ldp_outlabel *out;
291 LDP_ENTER(g->user_data, "ldp_fec_process_add");
294 * find the info about the next hop for this FEC
296 nh_session = ldp_session_for_nexthop(nh);
298 if (nh_session) {
299 ds_attr = ldp_attr_find_downstream_state2(g, nh_session, f,
300 LDP_LSP_STATE_MAP_RECV);
301 if (ds_attr && !ds_attr->outlabel) {
302 out = ldp_outlabel_create_complete(g, nh_session, ds_attr, nh);
303 if (!out) {
304 return MPLS_FAILURE;
306 ds_attr->outlabel = out;
311 * for every peer except the nh hop peer, check to see if we need to
312 * send a mapping
314 peer = MPLS_LIST_HEAD(&g->session);
315 while (peer != NULL) { /* FEC.1 */
316 if ((peer->state != LDP_STATE_OPERATIONAL) ||
317 (nh_session && peer->index == nh_session->index)) {
318 goto next_peer;
320 /* have I already sent a mapping for FEC to peer */
321 if ((us_attr = ldp_attr_find_upstream_state2(g, peer, f,
322 LDP_LSP_STATE_MAP_SENT))) {
323 /* yep, don't send another */
324 if (ds_attr) {
325 if (ldp_inlabel_add_outlabel(g, us_attr->inlabel,
326 ds_attr->outlabel) != MPLS_SUCCESS) {
327 return MPLS_FAILURE;
330 goto next_peer;
333 if (peer->oper_distribution_mode == LDP_DISTRIBUTION_UNSOLICITED) {
334 if (g->lsp_control_mode == LDP_CONTROL_INDEPENDENT) {
335 us_attr =
336 ldp_attr_find_upstream_state2(g, peer, f, LDP_LSP_STATE_REQ_RECV);
338 /* FEC.1.DUI3,4 */
339 if (ldp_label_mapping_with_xc(g, peer, f, &us_attr, ds_attr) !=
340 MPLS_SUCCESS) {
341 if (!us_attr->in_tree) {
342 ldp_attr_remove_complete(g, us_attr, MPLS_BOOL_FALSE);
344 goto next_peer;
346 } else {
348 *LDP_CONTROL_ORDERED
351 if (ds_attr || egress == MPLS_BOOL_TRUE) { /* FEC.1.DUO2 */
352 if (!(us_attr = ldp_attr_create(&f->info))) {
353 return MPLS_FAILURE;
355 /* FEC.1.DUO3-4 */
356 if ((egress == MPLS_BOOL_TRUE) && (mpls_policy_egress_check(
357 g->user_data, &f->info, &nh->info) == MPLS_BOOL_TRUE)) {
358 goto next_peer;
361 if (ldp_label_mapping_with_xc(g, peer, f, &us_attr, ds_attr) !=
362 MPLS_SUCCESS) {
363 return MPLS_FAILURE;
368 next_peer:
369 peer = MPLS_LIST_NEXT(&g->session, peer, _global);
372 if (ds_attr) { /* FEC.2 */
373 if (ldp_label_mapping_process(g, nh_session, NULL, NULL, ds_attr, f) ==
374 MPLS_FAILURE) { /* FEC.5 */
375 return MPLS_FAILURE;
377 return MPLS_SUCCESS;
381 * LDP_DISTRIBUTION_ONDEMAND
383 /* FEC.3 */
384 if (nh_session &&
385 nh_session->oper_distribution_mode == LDP_DISTRIBUTION_ONDEMAND) {
386 /* assume we're always "request when needed" */
387 ds_attr = NULL;
388 if (ldp_label_request_for_xc(g, nh_session, &f->info, NULL, &ds_attr) ==
389 MPLS_FAILURE) { /* FEC.4 */
390 return MPLS_FAILURE;
394 LDP_EXIT(g->user_data, "ldp_fec_process_add");
396 return MPLS_SUCCESS; /* FEC.6 */
399 mpls_return_enum ldp_fec_process_change(ldp_global * g, ldp_fec * f,
400 ldp_nexthop *nh, ldp_session *nh_session_old) {
401 ldp_session *peer = NULL;
402 ldp_attr *us_attr = NULL;
403 ldp_attr *ds_attr = NULL;
404 ldp_session *nh_session_new = NULL;
406 LDP_ENTER(g->user_data, "ldp_fec_process_change");
409 * NH 1-5 decide if we need to release an existing mapping
411 ds_attr = ldp_attr_find_downstream_state2(g, nh_session_old, f,
412 LDP_LSP_STATE_MAP_RECV);
413 if (!ds_attr) { /* NH.1 */
414 goto Detect_Change_Fec_Next_Hop_6;
417 if (ds_attr->ingress == MPLS_BOOL_TRUE) {
419 #if MPLS_USE_LSR
420 lsr_ftn ftn;
421 ftn.outsegment_index = ds_attr->outlabel->info.handle;
422 memcpy(&ftn.fec, &f->info, sizeof(mpls_fec));
423 lsr_cfg_ftn_set2(g->lsr_handle, &ftn, LSR_CFG_DEL);
424 #else
425 mpls_mpls_fec2out_del(g->mpls_handle, &f->info, &ds_attr->outlabel->info);
426 #endif
427 ds_attr->ingress = MPLS_BOOL_FALSE;
428 ds_attr->outlabel->merge_count--;
431 if (g->label_retention_mode == LDP_RETENTION_LIBERAL) { /* NH.3 */
432 ldp_attr *us_temp;
433 us_attr = MPLS_LIST_HEAD(&ds_attr->us_attr_root);
434 while (us_attr) {
435 /* need to walk the list in such a way as not to
436 * "pull the rug out from under me self"
438 us_temp = MPLS_LIST_NEXT(&ds_attr->us_attr_root, us_attr, _ds_attr);
439 if (us_attr->state == LDP_LSP_STATE_MAP_SENT) {
440 ldp_inlabel_del_outlabel(g, us_attr->inlabel); /* NH.2 */
441 ldp_attr_del_us2ds(us_attr, ds_attr);
443 us_attr = us_temp;
445 goto Detect_Change_Fec_Next_Hop_6;
448 ldp_label_release_send(g, nh_session_old, ds_attr, LDP_NOTIF_NONE); /* NH.4 */
449 ldp_attr_remove_complete(g, ds_attr, MPLS_BOOL_FALSE); /* NH.2,5 */
451 Detect_Change_Fec_Next_Hop_6:
454 * NH 6-9 decides is we need to send a label request abort
456 ds_attr = ldp_attr_find_downstream_state2(g, nh_session_old, f,
457 LDP_LSP_STATE_REQ_SENT);
458 if (ds_attr) { /* NH.6 */
459 if (g->label_retention_mode != LDP_RETENTION_CONSERVATIVE) { /* NH.7 */
460 /* NH.8,9 */
461 if (ldp_label_abort_send(g, nh_session_old, ds_attr) != MPLS_SUCCESS) {
462 return MPLS_FAILURE;
468 * NH 10-12 decides if we can use a mapping from our database
470 if (!(nh_session_new = ldp_get_next_hop_session_for_fec2(f,nh))) {
471 goto Detect_Change_Fec_Next_Hop_16;
474 ds_attr = ldp_attr_find_downstream_state2(g, nh_session_new, f,
475 LDP_LSP_STATE_MAP_RECV);
476 if (!ds_attr) { /* NH.11 */
477 goto Detect_Change_Fec_Next_Hop_13;
480 if (ldp_label_mapping_process(g, nh_session_new, NULL, NULL, ds_attr, f) !=
481 MPLS_SUCCESS) { /* NH.12 */
482 return MPLS_FAILURE;
484 goto Detect_Change_Fec_Next_Hop_20;
486 Detect_Change_Fec_Next_Hop_13:
489 * NH 13-15 decides if we need to make a label request
491 if (nh_session_new->oper_distribution_mode == LDP_DISTRIBUTION_ONDEMAND &&
492 g->label_retention_mode == LDP_RETENTION_CONSERVATIVE) {
493 /* NH.14-15 */
494 if (ldp_label_request_for_xc(g, nh_session_new, &f->info, NULL, &ds_attr) !=
495 MPLS_SUCCESS) {
496 return MPLS_FAILURE;
499 goto Detect_Change_Fec_Next_Hop_20;
501 Detect_Change_Fec_Next_Hop_16:
503 peer = MPLS_LIST_HEAD(&g->session);
504 while (peer) {
505 if (peer->state == LDP_STATE_OPERATIONAL) {
506 us_attr = ldp_attr_find_upstream_state2(g, peer, f,
507 LDP_LSP_STATE_MAP_SENT);
508 if (us_attr) { /* NH.17 */
509 if (ldp_label_withdraw_send(g, peer, us_attr, LDP_NOTIF_NONE) !=
510 MPLS_SUCCESS) { /* NH.18 */
511 ldp_attr_remove_complete(g, us_attr, MPLS_BOOL_FALSE);
512 return MPLS_FAILURE;
516 peer = MPLS_LIST_NEXT(&g->session, peer, _global);
519 Detect_Change_Fec_Next_Hop_20:
521 LDP_EXIT(g->user_data, "ldp_fec_process_change");
523 return MPLS_SUCCESS;
526 ldp_fec *ldp_fec_create()
528 ldp_fec *fec = (ldp_fec *) mpls_malloc(sizeof(ldp_fec));
530 if (fec != NULL) {
531 memset(fec, 0, sizeof(ldp_fec));
532 MPLS_REFCNT_INIT(fec, 0);
533 MPLS_LIST_ELEM_INIT(fec, _global);
534 MPLS_LIST_ELEM_INIT(fec, _inlabel);
535 MPLS_LIST_ELEM_INIT(fec, _outlabel);
536 MPLS_LIST_ELEM_INIT(fec, _fec);
537 MPLS_LIST_INIT(&fec->nh_root, ldp_nexthop);
538 MPLS_LIST_INIT(&fec->fs_root_us, ldp_fs);
539 MPLS_LIST_INIT(&fec->fs_root_ds, ldp_fs);
540 fec->info.type = MPLS_FEC_NONE;
541 fec->index = _ldp_fec_get_next_index();
543 return fec;
546 void mpls_fec2ldp_fec(mpls_fec * a, ldp_fec * b)
548 memcpy(&b->info, a, sizeof(mpls_fec));
551 ldp_fec *ldp_fec_create_host(mpls_inet_addr * host)
553 ldp_fec *fec = ldp_fec_create();
555 if (fec != NULL) {
556 fec->info.type = MPLS_FEC_HOST;
557 memcpy(&fec->info.u.host, host, sizeof(mpls_inet_addr));
559 return fec;
562 ldp_fec *ldp_fec_create_prefix(mpls_inet_addr * prefix, int prefix_len)
564 ldp_fec *fec = ldp_fec_create();
566 if (fec != NULL) {
567 fec->info.type = MPLS_FEC_PREFIX;
568 memcpy(&fec->info.u.prefix.network, prefix, sizeof(mpls_inet_addr));
569 fec->info.u.prefix.length = prefix_len;
571 return fec;
574 void ldp_fec_delete(ldp_fec * 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;