3 * Copyright (C) James R. Leu 2000
6 * This software is covered under the LGPL, for more
7 * info check out http://www.gnu.org/copyleft/lgpl.html
10 #include "ldp_struct.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"
34 #include "mpls_mpls_impl.h"
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
;
46 nh
= MPLS_LIST_HEAD(&f
->nh_root
);
48 if (!mpls_nexthop_compare(&nh
->info
, n
)) {
51 nh
= MPLS_LIST_NEXT(&f
->nh_root
, nh
, _fec
);
52 } while((nh
= MPLS_LIST_NEXT(&f
->nh_root
, nh
, _fec
)));
57 ldp_fec
*ldp_fec_find(ldp_global
*g
, mpls_fec
*fec
)
65 key
= fec
->u
.prefix
.network
.u
.ipv4
;
66 len
= fec
->u
.prefix
.length
;
69 key
= fec
->u
.host
.u
.ipv4
;
72 if (ldp_global_find_fec(g
, fec
, &f
) == MPLS_SUCCESS
) {
80 if (mpls_tree_get(g
->fec_tree
, key
, len
, (void **)&f
) != MPLS_SUCCESS
) {
86 mpls_return_enum
ldp_fec_insert2(ldp_global
*g
, ldp_fec
* fec
)
91 MPLS_ASSERT(MPLS_LIST_EMPTY(&fec
->nh_root
));
93 switch(fec
->info
.type
) {
95 key
= fec
->info
.u
.prefix
.network
.u
.ipv4
;
96 len
= fec
->info
.u
.prefix
.length
;
99 key
= fec
->info
.u
.host
.u
.ipv4
;
102 /* they had better insert it into the global tree */
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
;
120 ldp_fec_insert2_error
:
124 ldp_fec
*ldp_fec_insert(ldp_global
*g
, mpls_fec
* fec
)
128 if ((f
= ldp_fec_create()) == NULL
) {
129 LDP_PRINT(g
->user_data
, "ldp_fec_insert: error creating address\n");
133 mpls_fec2ldp_fec(fec
,f
);
137 if (ldp_fec_insert2(g
,f
) != MPLS_SUCCESS
) {
138 MPLS_REFCNT_RELEASE(f
, ldp_fec_delete
);
144 void ldp_fec_remove(ldp_global
*g
, mpls_fec
*fec
)
151 case MPLS_FEC_PREFIX
:
152 key
= fec
->u
.prefix
.network
.u
.ipv4
;
153 len
= fec
->u
.prefix
.length
;
156 key
= fec
->u
.host
.u
.ipv4
;
159 /* they had better remove it from the global tree */
165 mpls_tree_remove(g
->fec_tree
, key
, len
, (void **)&f
);
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
,
187 ldp_nexthop
*nh
= NULL
;
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
) {
199 return MPLS_END_OF_LIST
;
202 nh
= MPLS_LIST_HEAD(&f
->nh_root
);
204 if (nh
->index
== index
) {
208 } while((nh
= MPLS_LIST_NEXT(&f
->nh_root
, nh
, _fec
)));
214 mpls_return_enum
ldp_fec_add_nexthop(ldp_global
*g
, ldp_fec
* f
,
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
) {
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
);
255 ldp_fec_add_nexthop_error
:
257 ldp_fec_del_nexthop(f
, nh
);
261 void ldp_fec_del_nexthop(ldp_fec
* f
, ldp_nexthop
*nh
)
263 MPLS_ASSERT(f
&& nh
);
266 ldp_addr_del_nexthop(nh
->addr
, nh
);
269 ldp_if_del_nexthop(nh
->iff
, nh
);
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
,
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
;
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
);
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
);
306 ds_attr
->outlabel
= out
;
311 * for every peer except the nh hop peer, check to see if we need to
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
)) {
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 */
325 if (ldp_inlabel_add_outlabel(g
, us_attr
->inlabel
,
326 ds_attr
->outlabel
) != MPLS_SUCCESS
) {
333 if (peer
->oper_distribution_mode
== LDP_DISTRIBUTION_UNSOLICITED
) {
334 if (g
->lsp_control_mode
== LDP_CONTROL_INDEPENDENT
) {
336 ldp_attr_find_upstream_state2(g
, peer
, f
, LDP_LSP_STATE_REQ_RECV
);
339 if (ldp_label_mapping_with_xc(g
, peer
, f
, &us_attr
, ds_attr
) !=
341 if (!us_attr
->in_tree
) {
342 ldp_attr_remove_complete(g
, us_attr
, MPLS_BOOL_FALSE
);
351 if (ds_attr
|| egress
== MPLS_BOOL_TRUE
) { /* FEC.1.DUO2 */
352 if (!(us_attr
= ldp_attr_create(&f
->info
))) {
356 if ((egress
== MPLS_BOOL_TRUE
) && (mpls_policy_egress_check(
357 g
->user_data
, &f
->info
, &nh
->info
) == MPLS_BOOL_TRUE
)) {
361 if (ldp_label_mapping_with_xc(g
, peer
, f
, &us_attr
, ds_attr
) !=
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 */
381 * LDP_DISTRIBUTION_ONDEMAND
385 nh_session
->oper_distribution_mode
== LDP_DISTRIBUTION_ONDEMAND
) {
386 /* assume we're always "request when needed" */
388 if (ldp_label_request_for_xc(g
, nh_session
, &f
->info
, NULL
, &ds_attr
) ==
389 MPLS_FAILURE
) { /* FEC.4 */
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
) {
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
);
425 mpls_mpls_fec2out_del(g
->mpls_handle
, &f
->info
, &ds_attr
->outlabel
->info
);
427 ds_attr
->ingress
= MPLS_BOOL_FALSE
;
428 ds_attr
->outlabel
->merge_count
--;
431 if (g
->label_retention_mode
== LDP_RETENTION_LIBERAL
) { /* NH.3 */
433 us_attr
= MPLS_LIST_HEAD(&ds_attr
->us_attr_root
);
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
);
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 */
461 if (ldp_label_abort_send(g
, nh_session_old
, ds_attr
) != MPLS_SUCCESS
) {
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 */
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
) {
494 if (ldp_label_request_for_xc(g
, nh_session_new
, &f
->info
, NULL
, &ds_attr
) !=
499 goto Detect_Change_Fec_Next_Hop_20
;
501 Detect_Change_Fec_Next_Hop_16
:
503 peer
= MPLS_LIST_HEAD(&g
->session
);
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
);
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");
526 ldp_fec
*ldp_fec_create()
528 ldp_fec
*fec
= (ldp_fec
*) mpls_malloc(sizeof(ldp_fec
));
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();
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();
556 fec
->info
.type
= MPLS_FEC_HOST
;
557 memcpy(&fec
->info
.u
.host
, host
, sizeof(mpls_inet_addr
));
562 ldp_fec
*ldp_fec_create_prefix(mpls_inet_addr
* prefix
, int prefix_len
)
564 ldp_fec
*fec
= ldp_fec_create();
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
;
574 void ldp_fec_delete(ldp_fec
* fec
)
579 void mpls_fec2fec_tlv(mpls_fec
* lf
, mplsLdpFecTlv_t
* tlv
, int i
)
581 tlv
->fecElArray
[i
].addressEl
.addressFam
= 1;
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
;
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
;
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
;
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
;
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;