3 * Copyright (C) 2020 NetDEF, Inc.
6 * This file is part of FRR.
8 * FRR is free software; you can redistribute it and/or modify it
9 * under the terms of the GNU General Public License as published by the
10 * Free Software Foundation; either version 2, or (at your option) any
13 * FRR is distributed in the hope that it will be useful, but
14 * WITHOUT ANY WARRANTY; without even the implied warranty of
15 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
16 * General Public License for more details.
18 * You should have received a copy of the GNU General Public License along
19 * with this program; see the file COPYING; if not, write to the Free Software
20 * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
29 #include "ospfd/ospfd.h"
30 #include "ospfd/ospf_asbr.h"
31 #include "ospfd/ospf_lsa.h"
32 #include "ospfd/ospf_spf.h"
33 #include "ospfd/ospf_sr.h"
34 #include "ospfd/ospf_route.h"
35 #include "ospfd/ospf_ti_lfa.h"
36 #include "ospfd/ospf_dump.h"
39 DECLARE_RBTREE_UNIQ(p_spaces
, struct p_space
, p_spaces_item
,
40 p_spaces_compare_func
);
41 DECLARE_RBTREE_UNIQ(q_spaces
, struct q_space
, q_spaces_item
,
42 q_spaces_compare_func
);
45 ospf_ti_lfa_generate_p_space(struct ospf_area
*area
, struct vertex
*child
,
46 struct protected_resource
*protected_resource
,
47 bool recursive
, struct list
*pc_path
);
49 void ospf_print_protected_resource(
50 struct protected_resource
*protected_resource
, char *buf
)
52 struct router_lsa_link
*link
;
54 switch (protected_resource
->type
) {
55 case OSPF_TI_LFA_LINK_PROTECTION
:
56 link
= protected_resource
->link
;
57 snprintfrr(buf
, PROTECTED_RESOURCE_STRLEN
,
58 "protected link: %pI4 %pI4", &link
->link_id
,
61 case OSPF_TI_LFA_NODE_PROTECTION
:
62 snprintfrr(buf
, PROTECTED_RESOURCE_STRLEN
,
63 "protected node: %pI4",
64 &protected_resource
->router_id
);
66 case OSPF_TI_LFA_UNDEFINED_PROTECTION
:
67 snprintfrr(buf
, PROTECTED_RESOURCE_STRLEN
,
68 "undefined protected resource");
73 static enum ospf_ti_lfa_p_q_space_adjacency
74 ospf_ti_lfa_find_p_node(struct vertex
*pc_node
, struct p_space
*p_space
,
75 struct q_space
*q_space
)
77 struct listnode
*curr_node
;
78 struct vertex
*p_node
= NULL
, *pc_node_parent
, *p_node_pc_parent
;
79 struct vertex_parent
*pc_vertex_parent
;
81 curr_node
= listnode_lookup(q_space
->pc_path
, pc_node
);
82 pc_node_parent
= listgetdata(curr_node
->next
);
84 q_space
->p_node_info
->type
= OSPF_TI_LFA_UNDEFINED_NODE
;
86 p_node
= ospf_spf_vertex_find(pc_node_parent
->id
, p_space
->vertex_list
);
89 q_space
->p_node_info
->node
= p_node
;
90 q_space
->p_node_info
->type
= OSPF_TI_LFA_P_NODE
;
92 if (curr_node
->next
->next
) {
93 p_node_pc_parent
= listgetdata(curr_node
->next
->next
);
94 pc_vertex_parent
= ospf_spf_vertex_parent_find(
95 p_node_pc_parent
->id
, pc_node_parent
);
96 q_space
->p_node_info
->nexthop
=
97 pc_vertex_parent
->nexthop
->router
;
100 * It can happen that the P node is the root node itself
101 * (hence there can be no parents). In this case we
102 * don't need to set a nexthop.
104 q_space
->p_node_info
->nexthop
.s_addr
= INADDR_ANY
;
107 return OSPF_TI_LFA_P_Q_SPACE_ADJACENT
;
110 ospf_ti_lfa_find_p_node(pc_node_parent
, p_space
, q_space
);
111 return OSPF_TI_LFA_P_Q_SPACE_NON_ADJACENT
;
114 static void ospf_ti_lfa_find_q_node(struct vertex
*pc_node
,
115 struct p_space
*p_space
,
116 struct q_space
*q_space
)
118 struct listnode
*curr_node
, *next_node
;
119 struct vertex
*p_node
, *q_node
, *q_space_parent
= NULL
, *pc_node_parent
;
120 struct vertex_parent
*pc_vertex_parent
;
122 curr_node
= listnode_lookup(q_space
->pc_path
, pc_node
);
123 next_node
= curr_node
->next
;
124 pc_node_parent
= listgetdata(next_node
);
126 ospf_spf_vertex_parent_find(pc_node_parent
->id
, pc_node
);
128 p_node
= ospf_spf_vertex_find(pc_node
->id
, p_space
->vertex_list
);
129 q_node
= ospf_spf_vertex_find(pc_node
->id
, q_space
->vertex_list
);
131 /* The Q node is always present. */
134 q_space
->q_node_info
->type
= OSPF_TI_LFA_UNDEFINED_NODE
;
136 if (p_node
&& q_node
) {
137 q_space
->q_node_info
->node
= pc_node
;
138 q_space
->q_node_info
->type
= OSPF_TI_LFA_PQ_NODE
;
139 q_space
->q_node_info
->nexthop
=
140 pc_vertex_parent
->nexthop
->router
;
145 * Note that the Q space has the 'reverse' direction of the PC
146 * SPF. Hence compare PC SPF parent to Q space children.
149 ospf_spf_vertex_find(pc_node_parent
->id
, q_node
->children
);
152 * If the Q space parent doesn't exist we 'hit' the border to the P
153 * space and hence got our Q node.
155 if (!q_space_parent
) {
156 q_space
->q_node_info
->node
= pc_node
;
157 q_space
->q_node_info
->type
= OSPF_TI_LFA_Q_NODE
;
158 q_space
->q_node_info
->nexthop
=
159 pc_vertex_parent
->nexthop
->router
;
163 return ospf_ti_lfa_find_q_node(pc_node_parent
, p_space
, q_space
);
166 static void ospf_ti_lfa_append_label_stack(struct mpls_label_stack
*label_stack
,
167 mpls_label_t labels
[],
170 int i
, offset
, limit
;
172 limit
= label_stack
->num_labels
+ num_labels
;
173 offset
= label_stack
->num_labels
;
175 for (i
= label_stack
->num_labels
; i
< limit
; i
++) {
176 label_stack
->label
[i
] = labels
[i
- offset
];
177 label_stack
->num_labels
++;
182 static struct mpls_label_stack
*
183 ospf_ti_lfa_create_label_stack(mpls_label_t labels
[], uint32_t num_labels
)
185 struct mpls_label_stack
*label_stack
;
189 for (i
= 0; i
< num_labels
; i
++) {
190 if (labels
[i
] == MPLS_INVALID_LABEL
)
194 label_stack
= XCALLOC(MTYPE_OSPF_Q_SPACE
,
195 sizeof(struct mpls_label_stack
)
196 + MPLS_MAX_LABELS
* sizeof(mpls_label_t
));
197 label_stack
->num_labels
= num_labels
;
199 for (i
= 0; i
< num_labels
; i
++)
200 label_stack
->label
[i
] = labels
[i
];
206 ospf_ti_lfa_map_path_to_pc_vertices(struct list
*path
,
207 struct list
*pc_vertex_list
)
209 struct listnode
*node
;
210 struct vertex
*vertex
, *pc_vertex
;
211 struct list
*pc_path
;
213 pc_path
= list_new();
215 for (ALL_LIST_ELEMENTS_RO(path
, node
, vertex
)) {
216 pc_vertex
= ospf_spf_vertex_find(vertex
->id
, pc_vertex_list
);
217 listnode_add(pc_path
, pc_vertex
);
223 static struct list
*ospf_ti_lfa_cut_out_pc_path(struct list
*pc_vertex_list
,
224 struct list
*pc_path
,
225 struct vertex
*p_node
,
226 struct vertex
*q_node
)
228 struct list
*inner_pc_path
;
229 struct vertex
*current_vertex
;
230 struct listnode
*current_listnode
;
232 inner_pc_path
= list_new();
233 current_vertex
= ospf_spf_vertex_find(q_node
->id
, pc_vertex_list
);
234 current_listnode
= listnode_lookup(pc_path
, current_vertex
);
236 /* Note that the post-convergence paths are reversed. */
238 current_vertex
= listgetdata(current_listnode
);
239 listnode_add(inner_pc_path
, current_vertex
);
241 if (current_vertex
->id
.s_addr
== p_node
->id
.s_addr
)
244 current_listnode
= current_listnode
->next
;
247 return inner_pc_path
;
250 static void ospf_ti_lfa_generate_inner_label_stack(
251 struct ospf_area
*area
, struct p_space
*p_space
,
252 struct q_space
*q_space
,
253 struct ospf_ti_lfa_inner_backup_path_info
*inner_backup_path_info
)
255 struct route_table
*new_table
, *new_rtrs
;
256 struct vertex
*q_node
;
257 struct vertex
*start_vertex
, *end_vertex
;
258 struct vertex_parent
*vertex_parent
;
259 struct listnode
*pc_p_node
, *pc_q_node
;
260 struct vertex
*spf_orig
;
261 struct list
*vertex_list_orig
;
262 struct p_spaces_head
*p_spaces_orig
;
263 struct p_space
*inner_p_space
;
264 struct q_space
*inner_q_space
;
265 struct ospf_ti_lfa_node_info
*p_node_info
, *q_node_info
;
266 struct protected_resource
*protected_resource
;
267 struct list
*inner_pc_path
;
268 mpls_label_t start_label
, end_label
;
270 p_node_info
= q_space
->p_node_info
;
271 q_node_info
= q_space
->q_node_info
;
272 protected_resource
= p_space
->protected_resource
;
274 start_vertex
= p_node_info
->node
;
275 end_vertex
= q_node_info
->node
;
278 * It can happen that the P node and/or the Q node are the root or
279 * the destination, therefore we need to force one step forward (resp.
280 * backward) using an Adjacency-SID.
282 start_label
= MPLS_INVALID_LABEL
;
283 end_label
= MPLS_INVALID_LABEL
;
284 if (p_node_info
->node
->id
.s_addr
== p_space
->root
->id
.s_addr
) {
285 pc_p_node
= listnode_lookup(q_space
->pc_path
, p_space
->pc_spf
);
286 start_vertex
= listgetdata(pc_p_node
->prev
);
287 start_label
= ospf_sr_get_adj_sid_by_id(&p_node_info
->node
->id
,
290 if (q_node_info
->node
->id
.s_addr
== q_space
->root
->id
.s_addr
) {
291 pc_q_node
= listnode_lookup(q_space
->pc_path
,
292 listnode_head(q_space
->pc_path
));
293 end_vertex
= listgetdata(pc_q_node
->next
);
294 end_label
= ospf_sr_get_adj_sid_by_id(&end_vertex
->id
,
295 &q_node_info
->node
->id
);
298 /* Corner case: inner path is just one node */
299 if (start_vertex
->id
.s_addr
== end_vertex
->id
.s_addr
) {
300 inner_backup_path_info
->label_stack
=
301 ospf_ti_lfa_create_label_stack(&start_label
, 1);
302 inner_backup_path_info
->q_node_info
.node
= end_vertex
;
303 inner_backup_path_info
->q_node_info
.type
= OSPF_TI_LFA_PQ_NODE
;
304 inner_backup_path_info
->p_node_info
.type
=
305 OSPF_TI_LFA_UNDEFINED_NODE
;
306 vertex_parent
= ospf_spf_vertex_parent_find(p_space
->root
->id
,
308 inner_backup_path_info
->p_node_info
.nexthop
=
309 vertex_parent
->nexthop
->router
;
313 inner_pc_path
= ospf_ti_lfa_cut_out_pc_path(p_space
->pc_vertex_list
,
315 start_vertex
, end_vertex
);
317 new_table
= route_table_init();
318 new_rtrs
= route_table_init();
320 /* Copy the current state ... */
321 spf_orig
= area
->spf
;
322 vertex_list_orig
= area
->spf_vertex_list
;
323 p_spaces_orig
= area
->p_spaces
;
326 XCALLOC(MTYPE_OSPF_P_SPACE
, sizeof(struct p_spaces_head
));
328 /* dry run true, root node false */
329 ospf_spf_calculate(area
, start_vertex
->lsa_p
, new_table
, new_rtrs
, true,
332 q_node
= ospf_spf_vertex_find(end_vertex
->id
, area
->spf_vertex_list
);
334 ospf_ti_lfa_generate_p_space(area
, q_node
, protected_resource
, false,
337 /* There's just one P and Q space */
338 inner_p_space
= p_spaces_pop(area
->p_spaces
);
339 inner_q_space
= q_spaces_pop(inner_p_space
->q_spaces
);
341 /* Copy over inner backup path information from the inner q_space */
343 /* In case the outer P node is also the root of the P space */
344 if (start_label
!= MPLS_INVALID_LABEL
) {
345 inner_backup_path_info
->label_stack
=
346 ospf_ti_lfa_create_label_stack(&start_label
, 1);
347 ospf_ti_lfa_append_label_stack(
348 inner_backup_path_info
->label_stack
,
349 inner_q_space
->label_stack
->label
,
350 inner_q_space
->label_stack
->num_labels
);
351 inner_backup_path_info
->p_node_info
.node
= start_vertex
;
352 inner_backup_path_info
->p_node_info
.type
= OSPF_TI_LFA_P_NODE
;
353 vertex_parent
= ospf_spf_vertex_parent_find(p_space
->root
->id
,
355 inner_backup_path_info
->p_node_info
.nexthop
=
356 vertex_parent
->nexthop
->router
;
358 memcpy(inner_backup_path_info
->label_stack
,
359 inner_q_space
->label_stack
,
360 sizeof(struct mpls_label_stack
)
361 + sizeof(mpls_label_t
)
362 * inner_q_space
->label_stack
364 memcpy(&inner_backup_path_info
->p_node_info
,
365 inner_q_space
->p_node_info
,
366 sizeof(struct ospf_ti_lfa_node_info
));
369 /* In case the outer Q node is also the root of the Q space */
370 if (end_label
!= MPLS_INVALID_LABEL
) {
371 inner_backup_path_info
->q_node_info
.node
= end_vertex
;
372 inner_backup_path_info
->q_node_info
.type
= OSPF_TI_LFA_Q_NODE
;
374 memcpy(&inner_backup_path_info
->q_node_info
,
375 inner_q_space
->q_node_info
,
376 sizeof(struct ospf_ti_lfa_node_info
));
380 ospf_ti_lfa_free_p_spaces(area
);
381 ospf_spf_cleanup(area
->spf
, area
->spf_vertex_list
);
383 /* ... and copy the current state back. */
384 area
->spf
= spf_orig
;
385 area
->spf_vertex_list
= vertex_list_orig
;
386 area
->p_spaces
= p_spaces_orig
;
389 static void ospf_ti_lfa_generate_label_stack(struct ospf_area
*area
,
390 struct p_space
*p_space
,
391 struct q_space
*q_space
)
393 enum ospf_ti_lfa_p_q_space_adjacency adjacency_result
;
394 mpls_label_t labels
[MPLS_MAX_LABELS
];
395 struct vertex
*pc_node
;
396 struct ospf_ti_lfa_inner_backup_path_info inner_backup_path_info
;
398 if (IS_DEBUG_OSPF_TI_LFA
)
400 "%s: Generating Label stack for src %pI4 and dest %pI4.",
401 __func__
, &p_space
->root
->id
, &q_space
->root
->id
);
403 pc_node
= listnode_head(q_space
->pc_path
);
406 if (IS_DEBUG_OSPF_TI_LFA
)
408 "%s: There seems to be no post convergence path (yet).",
413 ospf_ti_lfa_find_q_node(pc_node
, p_space
, q_space
);
414 if (q_space
->q_node_info
->type
== OSPF_TI_LFA_UNDEFINED_NODE
) {
415 if (IS_DEBUG_OSPF_TI_LFA
)
416 zlog_debug("%s: Q node not found!", __func__
);
420 /* Found a PQ node? Then we are done here. */
421 if (q_space
->q_node_info
->type
== OSPF_TI_LFA_PQ_NODE
) {
423 * If the PQ node is a child of the root, then we can use an
424 * adjacency SID instead of a prefix SID for the backup path.
426 if (ospf_spf_vertex_parent_find(p_space
->root
->id
,
427 q_space
->q_node_info
->node
))
428 labels
[0] = ospf_sr_get_adj_sid_by_id(
430 &q_space
->q_node_info
->node
->id
);
432 labels
[0] = ospf_sr_get_prefix_sid_by_id(
433 &q_space
->q_node_info
->node
->id
);
435 q_space
->label_stack
=
436 ospf_ti_lfa_create_label_stack(labels
, 1);
437 q_space
->nexthop
= q_space
->q_node_info
->nexthop
;
442 /* Otherwise find a (hopefully adjacent) P node. */
443 pc_node
= ospf_spf_vertex_find(q_space
->q_node_info
->node
->id
,
444 p_space
->pc_vertex_list
);
445 adjacency_result
= ospf_ti_lfa_find_p_node(pc_node
, p_space
, q_space
);
447 if (q_space
->p_node_info
->type
== OSPF_TI_LFA_UNDEFINED_NODE
) {
448 if (IS_DEBUG_OSPF_TI_LFA
)
449 zlog_debug("%s: P node not found!", __func__
);
454 * This should be the regular case: P and Q space are adjacent or even
455 * overlapping. This is guaranteed for link protection when used with
458 if (adjacency_result
== OSPF_TI_LFA_P_Q_SPACE_ADJACENT
) {
460 * It can happen that the P node is the root itself, therefore
461 * we don't need a label for it. So just one adjacency SID for
464 if (q_space
->p_node_info
->node
->id
.s_addr
465 == p_space
->root
->id
.s_addr
) {
466 labels
[0] = ospf_sr_get_adj_sid_by_id(
468 &q_space
->q_node_info
->node
->id
);
469 q_space
->label_stack
=
470 ospf_ti_lfa_create_label_stack(labels
, 1);
471 q_space
->nexthop
= q_space
->q_node_info
->nexthop
;
476 * Otherwise we have a P and also a Q node (which are adjacent).
478 * It can happen that the P node is a child of the root,
479 * therefore we might just need the adjacency SID for the P node
480 * instead of the prefix SID. For the Q node always take the
483 if (ospf_spf_vertex_parent_find(p_space
->root
->id
,
484 q_space
->p_node_info
->node
))
485 labels
[0] = ospf_sr_get_adj_sid_by_id(
487 &q_space
->p_node_info
->node
->id
);
489 labels
[0] = ospf_sr_get_prefix_sid_by_id(
490 &q_space
->p_node_info
->node
->id
);
492 labels
[1] = ospf_sr_get_adj_sid_by_id(
493 &q_space
->p_node_info
->node
->id
,
494 &q_space
->q_node_info
->node
->id
);
496 q_space
->label_stack
=
497 ospf_ti_lfa_create_label_stack(labels
, 2);
498 q_space
->nexthop
= q_space
->p_node_info
->nexthop
;
502 * It can happen that the P and Q space are not adjacent when
503 * e.g. node protection or asymmetric weights are used. In this
504 * case the found P and Q nodes are used as a reference for
505 * another run of the algorithm!
507 * After having found the inner label stack it is stitched
508 * together with the outer labels.
510 inner_backup_path_info
.label_stack
= XCALLOC(
512 sizeof(struct mpls_label_stack
)
513 + sizeof(mpls_label_t
) * MPLS_MAX_LABELS
);
514 ospf_ti_lfa_generate_inner_label_stack(area
, p_space
, q_space
,
515 &inner_backup_path_info
);
518 * First stitch together the outer P node label with the inner
521 if (q_space
->p_node_info
->node
->id
.s_addr
522 == p_space
->root
->id
.s_addr
) {
524 * It can happen that the P node is the root itself,
525 * therefore we don't need a label for it. Just take
526 * the inner label stack first.
528 q_space
->label_stack
= ospf_ti_lfa_create_label_stack(
529 inner_backup_path_info
.label_stack
->label
,
530 inner_backup_path_info
.label_stack
->num_labels
);
532 /* Use the inner P or Q node for the nexthop */
533 if (inner_backup_path_info
.p_node_info
.type
534 != OSPF_TI_LFA_UNDEFINED_NODE
)
535 q_space
->nexthop
= inner_backup_path_info
536 .p_node_info
.nexthop
;
538 q_space
->nexthop
= inner_backup_path_info
539 .q_node_info
.nexthop
;
541 } else if (ospf_spf_vertex_parent_find(
543 q_space
->p_node_info
->node
)) {
545 * It can happen that the outer P node is a child of
546 * the root, therefore we might just need the
547 * adjacency SID for the outer P node instead of the
548 * prefix SID. Then just append the inner label stack.
550 labels
[0] = ospf_sr_get_adj_sid_by_id(
552 &q_space
->p_node_info
->node
->id
);
553 q_space
->label_stack
=
554 ospf_ti_lfa_create_label_stack(labels
, 1);
555 ospf_ti_lfa_append_label_stack(
556 q_space
->label_stack
,
557 inner_backup_path_info
.label_stack
->label
,
558 inner_backup_path_info
.label_stack
->num_labels
);
559 q_space
->nexthop
= q_space
->p_node_info
->nexthop
;
561 /* The outer P node needs a Prefix-SID here */
562 labels
[0] = ospf_sr_get_prefix_sid_by_id(
563 &q_space
->p_node_info
->node
->id
);
564 q_space
->label_stack
=
565 ospf_ti_lfa_create_label_stack(labels
, 1);
566 ospf_ti_lfa_append_label_stack(
567 q_space
->label_stack
,
568 inner_backup_path_info
.label_stack
->label
,
569 inner_backup_path_info
.label_stack
->num_labels
);
570 q_space
->nexthop
= q_space
->p_node_info
->nexthop
;
573 /* Now the outer Q node needs to be considered */
574 if (ospf_spf_vertex_parent_find(
575 inner_backup_path_info
.q_node_info
.node
->id
,
576 q_space
->q_node_info
->node
)) {
578 * The outer Q node can be a child of the inner Q node,
579 * hence just add an Adjacency-SID.
581 labels
[0] = ospf_sr_get_adj_sid_by_id(
582 &inner_backup_path_info
.q_node_info
.node
->id
,
583 &q_space
->q_node_info
->node
->id
);
584 ospf_ti_lfa_append_label_stack(q_space
->label_stack
,
587 /* Otherwise a Prefix-SID is needed */
588 labels
[0] = ospf_sr_get_prefix_sid_by_id(
589 &q_space
->q_node_info
->node
->id
);
590 ospf_ti_lfa_append_label_stack(q_space
->label_stack
,
594 * Note that there's also the case where the inner and outer Q
595 * node are the same, but then there's nothing to do!
601 ospf_ti_lfa_generate_post_convergence_path(struct list
*pc_vertex_list
,
604 struct list
*pc_path
;
605 struct vertex
*current_vertex
;
606 struct vertex_parent
*parent
;
608 current_vertex
= ospf_spf_vertex_find(dest
->id
, pc_vertex_list
);
609 if (!current_vertex
) {
610 if (IS_DEBUG_OSPF_TI_LFA
)
612 "%s: There seems to be no post convergence path (yet).",
617 pc_path
= list_new();
618 listnode_add(pc_path
, current_vertex
);
620 /* Generate a backup path in reverse order */
622 parent
= listnode_head(current_vertex
->parents
);
626 listnode_add(pc_path
, parent
->parent
);
627 current_vertex
= parent
->parent
;
633 static void ospf_ti_lfa_generate_q_spaces(struct ospf_area
*area
,
634 struct p_space
*p_space
,
635 struct vertex
*dest
, bool recursive
,
636 struct list
*pc_path
)
638 struct listnode
*node
;
639 struct vertex
*child
;
640 struct route_table
*new_table
, *new_rtrs
;
641 struct q_space
*q_space
, q_space_search
;
642 char label_buf
[MPLS_LABEL_STRLEN
];
643 char res_buf
[PROTECTED_RESOURCE_STRLEN
];
646 ospf_print_protected_resource(p_space
->protected_resource
, res_buf
);
648 p_space
->protected_resource
->type
== OSPF_TI_LFA_NODE_PROTECTION
650 == p_space
->protected_resource
->router_id
.s_addr
;
653 * If node protection is used, don't build a Q space for the protected
654 * node of that particular P space. Move on with children instead.
656 if (node_protected
) {
658 /* Recursively generate Q spaces for all children */
659 for (ALL_LIST_ELEMENTS_RO(dest
->children
, node
, child
))
660 ospf_ti_lfa_generate_q_spaces(area
, p_space
,
667 /* Check if we already have a Q space for this destination */
668 q_space_search
.root
= dest
;
669 if (q_spaces_find(p_space
->q_spaces
, &q_space_search
))
672 q_space
= XCALLOC(MTYPE_OSPF_Q_SPACE
, sizeof(struct q_space
));
673 q_space
->p_node_info
= XCALLOC(MTYPE_OSPF_Q_SPACE
,
674 sizeof(struct ospf_ti_lfa_node_info
));
675 q_space
->q_node_info
= XCALLOC(MTYPE_OSPF_Q_SPACE
,
676 sizeof(struct ospf_ti_lfa_node_info
));
678 new_table
= route_table_init();
679 new_rtrs
= route_table_init();
682 * Generate a new (reversed!) SPF tree for this vertex,
683 * dry run true, root node false
685 area
->spf_reversed
= true;
686 ospf_spf_calculate(area
, dest
->lsa_p
, new_table
, new_rtrs
, true, false);
688 /* Reset the flag for reverse SPF */
689 area
->spf_reversed
= false;
691 q_space
->root
= area
->spf
;
692 q_space
->vertex_list
= area
->spf_vertex_list
;
693 q_space
->label_stack
= NULL
;
696 q_space
->pc_path
= ospf_ti_lfa_map_path_to_pc_vertices(
697 pc_path
, p_space
->pc_vertex_list
);
699 q_space
->pc_path
= ospf_ti_lfa_generate_post_convergence_path(
700 p_space
->pc_vertex_list
, q_space
->root
);
702 /* If there's no backup path available then we are done here. */
703 if (!q_space
->pc_path
) {
705 "%s: NO backup path found for root %pI4 and destination %pI4 for %s, aborting ...",
706 __func__
, &p_space
->root
->id
, &q_space
->root
->id
,
711 /* 'Cut' the protected resource out of the new SPF tree */
712 ospf_spf_remove_resource(q_space
->root
, q_space
->vertex_list
,
713 p_space
->protected_resource
);
716 * Generate the smallest possible label stack from the root of the P
717 * space to the root of the Q space.
719 ospf_ti_lfa_generate_label_stack(area
, p_space
, q_space
);
721 if (q_space
->label_stack
) {
722 mpls_label2str(q_space
->label_stack
->num_labels
,
723 q_space
->label_stack
->label
, label_buf
,
724 MPLS_LABEL_STRLEN
, true);
726 "%s: Generated label stack %s for root %pI4 and destination %pI4 for %s",
727 __func__
, label_buf
, &p_space
->root
->id
,
728 &q_space
->root
->id
, res_buf
);
731 "%s: NO label stack generated for root %pI4 and destination %pI4 for %s",
732 __func__
, &p_space
->root
->id
, &q_space
->root
->id
,
736 /* We are finished, store the new Q space in the P space struct */
737 q_spaces_add(p_space
->q_spaces
, q_space
);
739 /* Recursively generate Q spaces for all children */
741 for (ALL_LIST_ELEMENTS_RO(dest
->children
, node
, child
))
742 ospf_ti_lfa_generate_q_spaces(area
, p_space
, child
,
747 static void ospf_ti_lfa_generate_post_convergence_spf(struct ospf_area
*area
,
748 struct p_space
*p_space
)
750 struct route_table
*new_table
, *new_rtrs
;
752 new_table
= route_table_init();
753 new_rtrs
= route_table_init();
755 area
->spf_protected_resource
= p_space
->protected_resource
;
758 * The 'post convergence' SPF tree is generated here
759 * dry run true, root node false
761 * So how does this work? During the SPF calculation the algorithm
762 * checks if a link belongs to a protected resource and then just
764 * This is actually _NOT_ a good way to calculate the post
765 * convergence SPF tree. The preferred way would be to delete the
766 * relevant links (and nodes) from a copy of the LSDB and then just run
767 * the SPF algorithm on that as usual.
768 * However, removing links from router LSAs appears to be its own
769 * endeavour (because LSAs are stored as a 'raw' stream), so we go with
770 * this rather hacky way for now.
772 ospf_spf_calculate(area
, area
->router_lsa_self
, new_table
, new_rtrs
,
775 p_space
->pc_spf
= area
->spf
;
776 p_space
->pc_vertex_list
= area
->spf_vertex_list
;
778 area
->spf_protected_resource
= NULL
;
782 ospf_ti_lfa_generate_p_space(struct ospf_area
*area
, struct vertex
*child
,
783 struct protected_resource
*protected_resource
,
784 bool recursive
, struct list
*pc_path
)
786 struct vertex
*spf_orig
;
787 struct list
*vertex_list
, *vertex_list_orig
;
788 struct p_space
*p_space
;
790 p_space
= XCALLOC(MTYPE_OSPF_P_SPACE
, sizeof(struct p_space
));
791 vertex_list
= list_new();
793 /* The P-space will get its own SPF tree, so copy the old one */
794 ospf_spf_copy(area
->spf
, vertex_list
);
795 p_space
->root
= listnode_head(vertex_list
);
796 p_space
->vertex_list
= vertex_list
;
797 p_space
->protected_resource
= protected_resource
;
799 /* Initialize the Q spaces for this P space and protected resource */
801 XCALLOC(MTYPE_OSPF_Q_SPACE
, sizeof(struct q_spaces_head
));
802 q_spaces_init(p_space
->q_spaces
);
804 /* 'Cut' the protected resource out of the new SPF tree */
805 ospf_spf_remove_resource(p_space
->root
, p_space
->vertex_list
,
806 p_space
->protected_resource
);
809 * Since we are going to calculate more SPF trees for Q spaces, keep the
810 * 'original' one here temporarily
812 spf_orig
= area
->spf
;
813 vertex_list_orig
= area
->spf_vertex_list
;
815 /* Generate the post convergence SPF as a blueprint for backup paths */
816 ospf_ti_lfa_generate_post_convergence_spf(area
, p_space
);
818 /* Generate the relevant Q spaces for this particular P space */
819 ospf_ti_lfa_generate_q_spaces(area
, p_space
, child
, recursive
, pc_path
);
821 /* Put the 'original' SPF tree back in place */
822 area
->spf
= spf_orig
;
823 area
->spf_vertex_list
= vertex_list_orig
;
825 /* We are finished, store the new P space */
826 p_spaces_add(area
->p_spaces
, p_space
);
829 void ospf_ti_lfa_generate_p_spaces(struct ospf_area
*area
,
830 enum protection_type protection_type
)
832 struct listnode
*node
, *inner_node
;
833 struct vertex
*root
, *child
;
834 struct vertex_parent
*vertex_parent
;
836 struct router_lsa_link
*l
= NULL
;
837 struct prefix stub_prefix
, child_prefix
;
838 struct protected_resource
*protected_resource
;
841 XCALLOC(MTYPE_OSPF_P_SPACE
, sizeof(struct p_spaces_head
));
842 p_spaces_init(area
->p_spaces
);
846 /* Root or its router LSA was not created yet? */
847 if (!root
|| !root
->lsa
)
850 stub_prefix
.family
= AF_INET
;
851 child_prefix
.family
= AF_INET
;
852 child_prefix
.prefixlen
= IPV4_MAX_BITLEN
;
854 p
= ((uint8_t *)root
->lsa
) + OSPF_LSA_HEADER_SIZE
+ 4;
855 lim
= ((uint8_t *)root
->lsa
) + ntohs(root
->lsa
->length
);
857 zlog_info("%s: Generating P spaces for area %pI4", __func__
,
861 * Iterate over all stub networks which target other OSPF neighbors.
862 * Check the nexthop of the child vertex if a stub network is relevant.
865 l
= (struct router_lsa_link
*)p
;
866 p
+= (OSPF_ROUTER_LSA_LINK_SIZE
867 + (l
->m
[0].tos_count
* OSPF_ROUTER_LSA_TOS_SIZE
));
869 /* First comes node protection */
870 if (protection_type
== OSPF_TI_LFA_NODE_PROTECTION
) {
871 if (l
->m
[0].type
== LSA_LINK_TYPE_POINTOPOINT
) {
872 protected_resource
= XCALLOC(
874 sizeof(struct protected_resource
));
875 protected_resource
->type
= protection_type
;
876 protected_resource
->router_id
= l
->link_id
;
877 child
= ospf_spf_vertex_find(
878 protected_resource
->router_id
,
881 ospf_ti_lfa_generate_p_space(
882 area
, child
, protected_resource
,
889 /* The rest is about link protection */
890 if (protection_type
!= OSPF_TI_LFA_LINK_PROTECTION
)
893 if (l
->m
[0].type
!= LSA_LINK_TYPE_STUB
)
896 stub_prefix
.prefixlen
= ip_masklen(l
->link_data
);
897 stub_prefix
.u
.prefix4
= l
->link_id
;
899 for (ALL_LIST_ELEMENTS_RO(root
->children
, node
, child
)) {
901 if (child
->type
!= OSPF_VERTEX_ROUTER
)
904 for (ALL_LIST_ELEMENTS_RO(child
->parents
, inner_node
,
907 child_prefix
.u
.prefix4
=
908 vertex_parent
->nexthop
->router
;
911 * If there's a link for that stub network then
912 * we will protect it. Hence generate a P space
913 * for that particular link including the
914 * Q spaces so we can later on generate a
915 * backup path for the link.
917 if (prefix_match(&stub_prefix
, &child_prefix
)) {
919 "%s: Generating P space for %pI4",
920 __func__
, &l
->link_id
);
922 protected_resource
= XCALLOC(
925 protected_resource
));
926 protected_resource
->type
=
928 protected_resource
->link
= l
;
930 ospf_ti_lfa_generate_p_space(
931 area
, child
, protected_resource
,
939 static struct p_space
*ospf_ti_lfa_get_p_space_by_path(struct ospf_area
*area
,
940 struct ospf_path
*path
)
942 struct p_space
*p_space
;
943 struct router_lsa_link
*link
;
944 struct vertex
*child
;
947 frr_each(p_spaces
, area
->p_spaces
, p_space
) {
948 type
= p_space
->protected_resource
->type
;
950 if (type
== OSPF_TI_LFA_LINK_PROTECTION
) {
951 link
= p_space
->protected_resource
->link
;
952 if ((path
->nexthop
.s_addr
& link
->link_data
.s_addr
)
953 == (link
->link_id
.s_addr
& link
->link_data
.s_addr
))
957 if (type
== OSPF_TI_LFA_NODE_PROTECTION
) {
958 child
= ospf_spf_vertex_by_nexthop(area
->spf
,
961 && p_space
->protected_resource
->router_id
.s_addr
970 void ospf_ti_lfa_insert_backup_paths(struct ospf_area
*area
,
971 struct route_table
*new_table
)
973 struct route_node
*rn
;
974 struct ospf_route
*or;
975 struct ospf_path
*path
;
976 struct listnode
*node
;
977 struct p_space
*p_space
;
978 struct q_space
*q_space
, q_space_search
;
979 struct vertex root_search
;
980 char label_buf
[MPLS_LABEL_STRLEN
];
982 for (rn
= route_top(new_table
); rn
; rn
= route_next(rn
)) {
987 /* Insert a backup path for all OSPF paths */
988 for (ALL_LIST_ELEMENTS_RO(or->paths
, node
, path
)) {
990 if (path
->adv_router
.s_addr
== INADDR_ANY
991 || path
->nexthop
.s_addr
== INADDR_ANY
)
994 if (IS_DEBUG_OSPF_TI_LFA
)
996 "%s: attempting to insert backup path for prefix %pFX, router id %pI4 and nexthop %pI4.",
997 __func__
, &rn
->p
, &path
->adv_router
,
1000 p_space
= ospf_ti_lfa_get_p_space_by_path(area
, path
);
1002 if (IS_DEBUG_OSPF_TI_LFA
)
1004 "%s: P space not found for router id %pI4 and nexthop %pI4.",
1005 __func__
, &path
->adv_router
,
1010 root_search
.id
= path
->adv_router
;
1011 q_space_search
.root
= &root_search
;
1012 q_space
= q_spaces_find(p_space
->q_spaces
,
1015 if (IS_DEBUG_OSPF_TI_LFA
)
1017 "%s: Q space not found for advertising router %pI4.",
1018 __func__
, &path
->adv_router
);
1022 /* If there's a backup label stack, insert it*/
1023 if (q_space
->label_stack
) {
1024 /* Init the backup path data in path */
1025 path
->srni
.backup_label_stack
= XCALLOC(
1027 sizeof(struct mpls_label_stack
)
1028 + sizeof(mpls_label_t
)
1029 * q_space
->label_stack
1032 /* Copy over the label stack */
1033 path
->srni
.backup_label_stack
->num_labels
=
1034 q_space
->label_stack
->num_labels
;
1035 memcpy(path
->srni
.backup_label_stack
->label
,
1036 q_space
->label_stack
->label
,
1037 sizeof(mpls_label_t
)
1038 * q_space
->label_stack
1041 /* Set the backup nexthop too */
1042 path
->srni
.backup_nexthop
= q_space
->nexthop
;
1045 if (path
->srni
.backup_label_stack
) {
1047 path
->srni
.backup_label_stack
1049 path
->srni
.backup_label_stack
->label
,
1050 label_buf
, MPLS_LABEL_STRLEN
, true);
1051 if (IS_DEBUG_OSPF_TI_LFA
)
1053 "%s: inserted backup path %s for prefix %pFX, router id %pI4 and nexthop %pI4.",
1054 __func__
, label_buf
, &rn
->p
,
1058 if (IS_DEBUG_OSPF_TI_LFA
)
1060 "%s: inserted NO backup path for prefix %pFX, router id %pI4 and nexthop %pI4.",
1069 void ospf_ti_lfa_free_p_spaces(struct ospf_area
*area
)
1071 struct p_space
*p_space
;
1072 struct q_space
*q_space
;
1074 while ((p_space
= p_spaces_pop(area
->p_spaces
))) {
1075 while ((q_space
= q_spaces_pop(p_space
->q_spaces
))) {
1076 ospf_spf_cleanup(q_space
->root
, q_space
->vertex_list
);
1078 if (q_space
->pc_path
)
1079 list_delete(&q_space
->pc_path
);
1081 XFREE(MTYPE_OSPF_Q_SPACE
, q_space
->p_node_info
);
1082 XFREE(MTYPE_OSPF_Q_SPACE
, q_space
->q_node_info
);
1083 XFREE(MTYPE_OSPF_Q_SPACE
, q_space
->label_stack
);
1084 XFREE(MTYPE_OSPF_Q_SPACE
, q_space
);
1087 ospf_spf_cleanup(p_space
->root
, p_space
->vertex_list
);
1088 ospf_spf_cleanup(p_space
->pc_spf
, p_space
->pc_vertex_list
);
1089 XFREE(MTYPE_OSPF_P_SPACE
, p_space
->protected_resource
);
1091 q_spaces_fini(p_space
->q_spaces
);
1092 XFREE(MTYPE_OSPF_Q_SPACE
, p_space
->q_spaces
);
1095 p_spaces_fini(area
->p_spaces
);
1096 XFREE(MTYPE_OSPF_P_SPACE
, area
->p_spaces
);
1099 void ospf_ti_lfa_compute(struct ospf_area
*area
, struct route_table
*new_table
,
1100 enum protection_type protection_type
)
1103 * Generate P spaces per protected link/node and their respective Q
1104 * spaces, generate backup paths (MPLS label stacks) by finding P/Q
1107 ospf_ti_lfa_generate_p_spaces(area
, protection_type
);
1109 /* Insert the generated backup paths into the routing table. */
1110 ospf_ti_lfa_insert_backup_paths(area
, new_table
);
1112 /* Cleanup P spaces and related datastructures including Q spaces. */
1113 ospf_ti_lfa_free_p_spaces(area
);