]> git.proxmox.com Git - mirror_frr.git/blob - ospfd/ospf_ti_lfa.c
projects / mirror_frr.git / blob
? search:
summary | shortlog | log | commit | commitdiff | tree
blame | history | raw | HEAD
bfdd: Fix malformed session with vrf
[mirror_frr.git] / ospfd / ospf_ti_lfa.c
1 // SPDX-License-Identifier: GPL-2.0-or-later
2 /*
3 * OSPF TI-LFA
4 * Copyright (C) 2020 NetDEF, Inc.
5 * Sascha Kattelmann
6 */
7
8 #include <zebra.h>
9
10 #include "prefix.h"
11 #include "table.h"
12 #include "printfrr.h"
13
14 #include "ospfd/ospfd.h"
15 #include "ospfd/ospf_asbr.h"
16 #include "ospfd/ospf_lsa.h"
17 #include "ospfd/ospf_spf.h"
18 #include "ospfd/ospf_sr.h"
19 #include "ospfd/ospf_route.h"
20 #include "ospfd/ospf_ti_lfa.h"
21 #include "ospfd/ospf_dump.h"
22
23
24 DECLARE_RBTREE_UNIQ(p_spaces, struct p_space, p_spaces_item,
25 p_spaces_compare_func);
26 DECLARE_RBTREE_UNIQ(q_spaces, struct q_space, q_spaces_item,
27 q_spaces_compare_func);
28
29 static void
30 ospf_ti_lfa_generate_p_space(struct ospf_area *area, struct vertex *child,
31 struct protected_resource *protected_resource,
32 bool recursive, struct list *pc_path);
33
34 void ospf_print_protected_resource(
35 struct protected_resource *protected_resource, char *buf)
36 {
37 struct router_lsa_link *link;
38
39 switch (protected_resource->type) {
40 case OSPF_TI_LFA_LINK_PROTECTION:
41 link = protected_resource->link;
42 snprintfrr(buf, PROTECTED_RESOURCE_STRLEN,
43 "protected link: %pI4 %pI4", &link->link_id,
44 &link->link_data);
45 break;
46 case OSPF_TI_LFA_NODE_PROTECTION:
47 snprintfrr(buf, PROTECTED_RESOURCE_STRLEN,
48 "protected node: %pI4",
49 &protected_resource->router_id);
50 break;
51 case OSPF_TI_LFA_UNDEFINED_PROTECTION:
52 snprintfrr(buf, PROTECTED_RESOURCE_STRLEN,
53 "undefined protected resource");
54 break;
55 }
56 }
57
58 static enum ospf_ti_lfa_p_q_space_adjacency
59 ospf_ti_lfa_find_p_node(struct vertex *pc_node, struct p_space *p_space,
60 struct q_space *q_space)
61 {
62 struct listnode *curr_node;
63 struct vertex *p_node = NULL, *pc_node_parent, *p_node_pc_parent;
64 struct vertex_parent *pc_vertex_parent;
65
66 curr_node = listnode_lookup(q_space->pc_path, pc_node);
67 pc_node_parent = listgetdata(curr_node->next);
68
69 q_space->p_node_info->type = OSPF_TI_LFA_UNDEFINED_NODE;
70
71 p_node = ospf_spf_vertex_find(pc_node_parent->id, p_space->vertex_list);
72
73 if (p_node) {
74 q_space->p_node_info->node = p_node;
75 q_space->p_node_info->type = OSPF_TI_LFA_P_NODE;
76
77 if (curr_node->next->next) {
78 p_node_pc_parent = listgetdata(curr_node->next->next);
79 pc_vertex_parent = ospf_spf_vertex_parent_find(
80 p_node_pc_parent->id, pc_node_parent);
81 q_space->p_node_info->nexthop =
82 pc_vertex_parent->nexthop->router;
83 } else {
84 /*
85 * It can happen that the P node is the root node itself
86 * (hence there can be no parents). In this case we
87 * don't need to set a nexthop.
88 */
89 q_space->p_node_info->nexthop.s_addr = INADDR_ANY;
90 }
91
92 return OSPF_TI_LFA_P_Q_SPACE_ADJACENT;
93 }
94
95 ospf_ti_lfa_find_p_node(pc_node_parent, p_space, q_space);
96 return OSPF_TI_LFA_P_Q_SPACE_NON_ADJACENT;
97 }
98
99 static void ospf_ti_lfa_find_q_node(struct vertex *pc_node,
100 struct p_space *p_space,
101 struct q_space *q_space)
102 {
103 struct listnode *curr_node, *next_node;
104 struct vertex *p_node, *q_node, *q_space_parent = NULL, *pc_node_parent;
105 struct vertex_parent *pc_vertex_parent;
106
107 curr_node = listnode_lookup(q_space->pc_path, pc_node);
108 next_node = curr_node->next;
109 pc_node_parent = listgetdata(next_node);
110 pc_vertex_parent =
111 ospf_spf_vertex_parent_find(pc_node_parent->id, pc_node);
112
113 p_node = ospf_spf_vertex_find(pc_node->id, p_space->vertex_list);
114 q_node = ospf_spf_vertex_find(pc_node->id, q_space->vertex_list);
115
116 /* The Q node is always present. */
117 assert(q_node);
118
119 q_space->q_node_info->type = OSPF_TI_LFA_UNDEFINED_NODE;
120
121 if (p_node && q_node) {
122 q_space->q_node_info->node = pc_node;
123 q_space->q_node_info->type = OSPF_TI_LFA_PQ_NODE;
124 q_space->q_node_info->nexthop =
125 pc_vertex_parent->nexthop->router;
126 return;
127 }
128
129 /*
130 * Note that the Q space has the 'reverse' direction of the PC
131 * SPF. Hence compare PC SPF parent to Q space children.
132 */
133 q_space_parent =
134 ospf_spf_vertex_find(pc_node_parent->id, q_node->children);
135
136 /*
137 * If the Q space parent doesn't exist we 'hit' the border to the P
138 * space and hence got our Q node.
139 */
140 if (!q_space_parent) {
141 q_space->q_node_info->node = pc_node;
142 q_space->q_node_info->type = OSPF_TI_LFA_Q_NODE;
143 q_space->q_node_info->nexthop =
144 pc_vertex_parent->nexthop->router;
145 return;
146 }
147
148 return ospf_ti_lfa_find_q_node(pc_node_parent, p_space, q_space);
149 }
150
151 static void ospf_ti_lfa_append_label_stack(struct mpls_label_stack *label_stack,
152 mpls_label_t labels[],
153 uint32_t num_labels)
154 {
155 int i, offset, limit;
156
157 limit = label_stack->num_labels + num_labels;
158 offset = label_stack->num_labels;
159
160 for (i = label_stack->num_labels; i < limit; i++) {
161 label_stack->label[i] = labels[i - offset];
162 label_stack->num_labels++;
163 }
164 }
165
166
167 static struct mpls_label_stack *
168 ospf_ti_lfa_create_label_stack(mpls_label_t labels[], uint32_t num_labels)
169 {
170 struct mpls_label_stack *label_stack;
171 uint32_t i;
172
173 /* Sanity check */
174 for (i = 0; i < num_labels; i++) {
175 if (labels[i] == MPLS_INVALID_LABEL)
176 return NULL;
177 }
178
179 label_stack = XCALLOC(MTYPE_OSPF_Q_SPACE,
180 sizeof(struct mpls_label_stack)
181 + MPLS_MAX_LABELS * sizeof(mpls_label_t));
182 label_stack->num_labels = num_labels;
183
184 for (i = 0; i < num_labels; i++)
185 label_stack->label[i] = labels[i];
186
187 return label_stack;
188 }
189
190 static struct list *
191 ospf_ti_lfa_map_path_to_pc_vertices(struct list *path,
192 struct list *pc_vertex_list)
193 {
194 struct listnode *node;
195 struct vertex *vertex, *pc_vertex;
196 struct list *pc_path;
197
198 pc_path = list_new();
199
200 for (ALL_LIST_ELEMENTS_RO(path, node, vertex)) {
201 pc_vertex = ospf_spf_vertex_find(vertex->id, pc_vertex_list);
202 listnode_add(pc_path, pc_vertex);
203 }
204
205 return pc_path;
206 }
207
208 static struct list *ospf_ti_lfa_cut_out_pc_path(struct list *pc_vertex_list,
209 struct list *pc_path,
210 struct vertex *p_node,
211 struct vertex *q_node)
212 {
213 struct list *inner_pc_path;
214 struct vertex *current_vertex;
215 struct listnode *current_listnode;
216
217 inner_pc_path = list_new();
218 current_vertex = ospf_spf_vertex_find(q_node->id, pc_vertex_list);
219 current_listnode = listnode_lookup(pc_path, current_vertex);
220
221 /* Note that the post-convergence paths are reversed. */
222 for (;;) {
223 current_vertex = listgetdata(current_listnode);
224 listnode_add(inner_pc_path, current_vertex);
225
226 if (current_vertex->id.s_addr == p_node->id.s_addr)
227 break;
228
229 current_listnode = current_listnode->next;
230 }
231
232 return inner_pc_path;
233 }
234
235 static void ospf_ti_lfa_generate_inner_label_stack(
236 struct ospf_area *area, struct p_space *p_space,
237 struct q_space *q_space,
238 struct ospf_ti_lfa_inner_backup_path_info *inner_backup_path_info)
239 {
240 struct route_table *new_table;
241 struct vertex *q_node;
242 struct vertex *start_vertex, *end_vertex;
243 struct vertex_parent *vertex_parent;
244 struct listnode *pc_p_node, *pc_q_node;
245 struct vertex *spf_orig;
246 struct list *vertex_list_orig;
247 struct p_spaces_head *p_spaces_orig;
248 struct p_space *inner_p_space;
249 struct q_space *inner_q_space;
250 struct ospf_ti_lfa_node_info *p_node_info, *q_node_info;
251 struct protected_resource *protected_resource;
252 struct list *inner_pc_path;
253 mpls_label_t start_label, end_label;
254
255 p_node_info = q_space->p_node_info;
256 q_node_info = q_space->q_node_info;
257 protected_resource = p_space->protected_resource;
258
259 start_vertex = p_node_info->node;
260 end_vertex = q_node_info->node;
261
262 /*
263 * It can happen that the P node and/or the Q node are the root or
264 * the destination, therefore we need to force one step forward (resp.
265 * backward) using an Adjacency-SID.
266 */
267 start_label = MPLS_INVALID_LABEL;
268 end_label = MPLS_INVALID_LABEL;
269 if (p_node_info->node->id.s_addr == p_space->root->id.s_addr) {
270 pc_p_node = listnode_lookup(q_space->pc_path, p_space->pc_spf);
271 start_vertex = listgetdata(pc_p_node->prev);
272 start_label = ospf_sr_get_adj_sid_by_id(&p_node_info->node->id,
273 &start_vertex->id);
274 }
275 if (q_node_info->node->id.s_addr == q_space->root->id.s_addr) {
276 pc_q_node = listnode_lookup(q_space->pc_path,
277 listnode_head(q_space->pc_path));
278 end_vertex = listgetdata(pc_q_node->next);
279 end_label = ospf_sr_get_adj_sid_by_id(&end_vertex->id,
280 &q_node_info->node->id);
281 }
282
283 /* Corner case: inner path is just one node */
284 if (start_vertex->id.s_addr == end_vertex->id.s_addr) {
285 inner_backup_path_info->label_stack =
286 ospf_ti_lfa_create_label_stack(&start_label, 1);
287 inner_backup_path_info->q_node_info.node = end_vertex;
288 inner_backup_path_info->q_node_info.type = OSPF_TI_LFA_PQ_NODE;
289 inner_backup_path_info->p_node_info.type =
290 OSPF_TI_LFA_UNDEFINED_NODE;
291 vertex_parent = ospf_spf_vertex_parent_find(p_space->root->id,
292 end_vertex);
293 inner_backup_path_info->p_node_info.nexthop =
294 vertex_parent->nexthop->router;
295 return;
296 }
297
298 inner_pc_path = ospf_ti_lfa_cut_out_pc_path(p_space->pc_vertex_list,
299 q_space->pc_path,
300 start_vertex, end_vertex);
301
302 new_table = route_table_init();
303
304 /* Copy the current state ... */
305 spf_orig = area->spf;
306 vertex_list_orig = area->spf_vertex_list;
307 p_spaces_orig = area->p_spaces;
308
309 area->p_spaces =
310 XCALLOC(MTYPE_OSPF_P_SPACE, sizeof(struct p_spaces_head));
311
312 /* dry run true, root node false */
313 ospf_spf_calculate(area, start_vertex->lsa_p, new_table, NULL, NULL,
314 true, false);
315
316 q_node = ospf_spf_vertex_find(end_vertex->id, area->spf_vertex_list);
317
318 ospf_ti_lfa_generate_p_space(area, q_node, protected_resource, false,
319 inner_pc_path);
320
321 /* There's just one P and Q space */
322 inner_p_space = p_spaces_pop(area->p_spaces);
323 inner_q_space = q_spaces_pop(inner_p_space->q_spaces);
324
325 /* Copy over inner backup path information from the inner q_space */
326
327 /* In case the outer P node is also the root of the P space */
328 if (start_label != MPLS_INVALID_LABEL) {
329 inner_backup_path_info->label_stack =
330 ospf_ti_lfa_create_label_stack(&start_label, 1);
331 ospf_ti_lfa_append_label_stack(
332 inner_backup_path_info->label_stack,
333 inner_q_space->label_stack->label,
334 inner_q_space->label_stack->num_labels);
335 inner_backup_path_info->p_node_info.node = start_vertex;
336 inner_backup_path_info->p_node_info.type = OSPF_TI_LFA_P_NODE;
337 vertex_parent = ospf_spf_vertex_parent_find(p_space->root->id,
338 start_vertex);
339 inner_backup_path_info->p_node_info.nexthop =
340 vertex_parent->nexthop->router;
341 } else {
342 memcpy(inner_backup_path_info->label_stack,
343 inner_q_space->label_stack,
344 sizeof(struct mpls_label_stack)
345 + sizeof(mpls_label_t)
346 * inner_q_space->label_stack
347 ->num_labels);
348 memcpy(&inner_backup_path_info->p_node_info,
349 inner_q_space->p_node_info,
350 sizeof(struct ospf_ti_lfa_node_info));
351 }
352
353 /* In case the outer Q node is also the root of the Q space */
354 if (end_label != MPLS_INVALID_LABEL) {
355 inner_backup_path_info->q_node_info.node = end_vertex;
356 inner_backup_path_info->q_node_info.type = OSPF_TI_LFA_Q_NODE;
357 } else {
358 memcpy(&inner_backup_path_info->q_node_info,
359 inner_q_space->q_node_info,
360 sizeof(struct ospf_ti_lfa_node_info));
361 }
362
363 /* Cleanup */
364 ospf_ti_lfa_free_p_spaces(area);
365 ospf_spf_cleanup(area->spf, area->spf_vertex_list);
366
367 /* ... and copy the current state back. */
368 area->spf = spf_orig;
369 area->spf_vertex_list = vertex_list_orig;
370 area->p_spaces = p_spaces_orig;
371 }
372
373 static void ospf_ti_lfa_generate_label_stack(struct ospf_area *area,
374 struct p_space *p_space,
375 struct q_space *q_space)
376 {
377 enum ospf_ti_lfa_p_q_space_adjacency adjacency_result;
378 mpls_label_t labels[MPLS_MAX_LABELS];
379 struct vertex *pc_node;
380 struct ospf_ti_lfa_inner_backup_path_info inner_backup_path_info;
381
382 if (IS_DEBUG_OSPF_TI_LFA)
383 zlog_debug(
384 "%s: Generating Label stack for src %pI4 and dest %pI4.",
385 __func__, &p_space->root->id, &q_space->root->id);
386
387 pc_node = listnode_head(q_space->pc_path);
388
389 if (!pc_node) {
390 if (IS_DEBUG_OSPF_TI_LFA)
391 zlog_debug(
392 "%s: There seems to be no post convergence path (yet).",
393 __func__);
394 return;
395 }
396
397 ospf_ti_lfa_find_q_node(pc_node, p_space, q_space);
398 if (q_space->q_node_info->type == OSPF_TI_LFA_UNDEFINED_NODE) {
399 if (IS_DEBUG_OSPF_TI_LFA)
400 zlog_debug("%s: Q node not found!", __func__);
401 return;
402 }
403
404 /* Found a PQ node? Then we are done here. */
405 if (q_space->q_node_info->type == OSPF_TI_LFA_PQ_NODE) {
406 /*
407 * If the PQ node is a child of the root, then we can use an
408 * adjacency SID instead of a prefix SID for the backup path.
409 */
410 if (ospf_spf_vertex_parent_find(p_space->root->id,
411 q_space->q_node_info->node))
412 labels[0] = ospf_sr_get_adj_sid_by_id(
413 &p_space->root->id,
414 &q_space->q_node_info->node->id);
415 else
416 labels[0] = ospf_sr_get_prefix_sid_by_id(
417 &q_space->q_node_info->node->id);
418
419 q_space->label_stack =
420 ospf_ti_lfa_create_label_stack(labels, 1);
421 q_space->nexthop = q_space->q_node_info->nexthop;
422
423 return;
424 }
425
426 /* Otherwise find a (hopefully adjacent) P node. */
427 pc_node = ospf_spf_vertex_find(q_space->q_node_info->node->id,
428 p_space->pc_vertex_list);
429 adjacency_result = ospf_ti_lfa_find_p_node(pc_node, p_space, q_space);
430
431 if (q_space->p_node_info->type == OSPF_TI_LFA_UNDEFINED_NODE) {
432 if (IS_DEBUG_OSPF_TI_LFA)
433 zlog_debug("%s: P node not found!", __func__);
434 return;
435 }
436
437 /*
438 * This should be the regular case: P and Q space are adjacent or even
439 * overlapping. This is guaranteed for link protection when used with
440 * symmetric weights.
441 */
442 if (adjacency_result == OSPF_TI_LFA_P_Q_SPACE_ADJACENT) {
443 /*
444 * It can happen that the P node is the root itself, therefore
445 * we don't need a label for it. So just one adjacency SID for
446 * the Q node.
447 */
448 if (q_space->p_node_info->node->id.s_addr
449 == p_space->root->id.s_addr) {
450 labels[0] = ospf_sr_get_adj_sid_by_id(
451 &p_space->root->id,
452 &q_space->q_node_info->node->id);
453 q_space->label_stack =
454 ospf_ti_lfa_create_label_stack(labels, 1);
455 q_space->nexthop = q_space->q_node_info->nexthop;
456 return;
457 }
458
459 /*
460 * Otherwise we have a P and also a Q node (which are adjacent).
461 *
462 * It can happen that the P node is a child of the root,
463 * therefore we might just need the adjacency SID for the P node
464 * instead of the prefix SID. For the Q node always take the
465 * adjacency SID.
466 */
467 if (ospf_spf_vertex_parent_find(p_space->root->id,
468 q_space->p_node_info->node))
469 labels[0] = ospf_sr_get_adj_sid_by_id(
470 &p_space->root->id,
471 &q_space->p_node_info->node->id);
472 else
473 labels[0] = ospf_sr_get_prefix_sid_by_id(
474 &q_space->p_node_info->node->id);
475
476 labels[1] = ospf_sr_get_adj_sid_by_id(
477 &q_space->p_node_info->node->id,
478 &q_space->q_node_info->node->id);
479
480 q_space->label_stack =
481 ospf_ti_lfa_create_label_stack(labels, 2);
482 q_space->nexthop = q_space->p_node_info->nexthop;
483
484 } else {
485 /*
486 * It can happen that the P and Q space are not adjacent when
487 * e.g. node protection or asymmetric weights are used. In this
488 * case the found P and Q nodes are used as a reference for
489 * another run of the algorithm!
490 *
491 * After having found the inner label stack it is stitched
492 * together with the outer labels.
493 */
494 inner_backup_path_info.label_stack = XCALLOC(
495 MTYPE_OSPF_PATH,
496 sizeof(struct mpls_label_stack)
497 + sizeof(mpls_label_t) * MPLS_MAX_LABELS);
498 ospf_ti_lfa_generate_inner_label_stack(area, p_space, q_space,
499 &inner_backup_path_info);
500
501 /*
502 * First stitch together the outer P node label with the inner
503 * label stack.
504 */
505 if (q_space->p_node_info->node->id.s_addr
506 == p_space->root->id.s_addr) {
507 /*
508 * It can happen that the P node is the root itself,
509 * therefore we don't need a label for it. Just take
510 * the inner label stack first.
511 */
512 q_space->label_stack = ospf_ti_lfa_create_label_stack(
513 inner_backup_path_info.label_stack->label,
514 inner_backup_path_info.label_stack->num_labels);
515
516 /* Use the inner P or Q node for the nexthop */
517 if (inner_backup_path_info.p_node_info.type
518 != OSPF_TI_LFA_UNDEFINED_NODE)
519 q_space->nexthop = inner_backup_path_info
520 .p_node_info.nexthop;
521 else
522 q_space->nexthop = inner_backup_path_info
523 .q_node_info.nexthop;
524
525 } else if (ospf_spf_vertex_parent_find(
526 p_space->root->id,
527 q_space->p_node_info->node)) {
528 /*
529 * It can happen that the outer P node is a child of
530 * the root, therefore we might just need the
531 * adjacency SID for the outer P node instead of the
532 * prefix SID. Then just append the inner label stack.
533 */
534 labels[0] = ospf_sr_get_adj_sid_by_id(
535 &p_space->root->id,
536 &q_space->p_node_info->node->id);
537 q_space->label_stack =
538 ospf_ti_lfa_create_label_stack(labels, 1);
539 ospf_ti_lfa_append_label_stack(
540 q_space->label_stack,
541 inner_backup_path_info.label_stack->label,
542 inner_backup_path_info.label_stack->num_labels);
543 q_space->nexthop = q_space->p_node_info->nexthop;
544 } else {
545 /* The outer P node needs a Prefix-SID here */
546 labels[0] = ospf_sr_get_prefix_sid_by_id(
547 &q_space->p_node_info->node->id);
548 q_space->label_stack =
549 ospf_ti_lfa_create_label_stack(labels, 1);
550 ospf_ti_lfa_append_label_stack(
551 q_space->label_stack,
552 inner_backup_path_info.label_stack->label,
553 inner_backup_path_info.label_stack->num_labels);
554 q_space->nexthop = q_space->p_node_info->nexthop;
555 }
556
557 /* Now the outer Q node needs to be considered */
558 if (ospf_spf_vertex_parent_find(
559 inner_backup_path_info.q_node_info.node->id,
560 q_space->q_node_info->node)) {
561 /*
562 * The outer Q node can be a child of the inner Q node,
563 * hence just add an Adjacency-SID.
564 */
565 labels[0] = ospf_sr_get_adj_sid_by_id(
566 &inner_backup_path_info.q_node_info.node->id,
567 &q_space->q_node_info->node->id);
568 ospf_ti_lfa_append_label_stack(q_space->label_stack,
569 labels, 1);
570 } else {
571 /* Otherwise a Prefix-SID is needed */
572 labels[0] = ospf_sr_get_prefix_sid_by_id(
573 &q_space->q_node_info->node->id);
574 ospf_ti_lfa_append_label_stack(q_space->label_stack,
575 labels, 1);
576 }
577 /*
578 * Note that there's also the case where the inner and outer Q
579 * node are the same, but then there's nothing to do!
580 */
581 }
582 }
583
584 static struct list *
585 ospf_ti_lfa_generate_post_convergence_path(struct list *pc_vertex_list,
586 struct vertex *dest)
587 {
588 struct list *pc_path;
589 struct vertex *current_vertex;
590 struct vertex_parent *parent;
591
592 current_vertex = ospf_spf_vertex_find(dest->id, pc_vertex_list);
593 if (!current_vertex) {
594 if (IS_DEBUG_OSPF_TI_LFA)
595 zlog_debug(
596 "%s: There seems to be no post convergence path (yet).",
597 __func__);
598 return NULL;
599 }
600
601 pc_path = list_new();
602 listnode_add(pc_path, current_vertex);
603
604 /* Generate a backup path in reverse order */
605 for (;;) {
606 parent = listnode_head(current_vertex->parents);
607 if (!parent)
608 break;
609
610 listnode_add(pc_path, parent->parent);
611 current_vertex = parent->parent;
612 }
613
614 return pc_path;
615 }
616
617 static void ospf_ti_lfa_generate_q_spaces(struct ospf_area *area,
618 struct p_space *p_space,
619 struct vertex *dest, bool recursive,
620 struct list *pc_path)
621 {
622 struct listnode *node;
623 struct vertex *child;
624 struct route_table *new_table;
625 struct q_space *q_space, q_space_search;
626 char label_buf[MPLS_LABEL_STRLEN];
627 char res_buf[PROTECTED_RESOURCE_STRLEN];
628 bool node_protected;
629
630 ospf_print_protected_resource(p_space->protected_resource, res_buf);
631 node_protected =
632 p_space->protected_resource->type == OSPF_TI_LFA_NODE_PROTECTION
633 && dest->id.s_addr
634 == p_space->protected_resource->router_id.s_addr;
635
636 /*
637 * If node protection is used, don't build a Q space for the protected
638 * node of that particular P space. Move on with children instead.
639 */
640 if (node_protected) {
641 if (recursive) {
642 /* Recursively generate Q spaces for all children */
643 for (ALL_LIST_ELEMENTS_RO(dest->children, node, child))
644 ospf_ti_lfa_generate_q_spaces(area, p_space,
645 child, recursive,
646 pc_path);
647 }
648 return;
649 }
650
651 /* Check if we already have a Q space for this destination */
652 q_space_search.root = dest;
653 if (q_spaces_find(p_space->q_spaces, &q_space_search))
654 return;
655
656 q_space = XCALLOC(MTYPE_OSPF_Q_SPACE, sizeof(struct q_space));
657 q_space->p_node_info = XCALLOC(MTYPE_OSPF_Q_SPACE,
658 sizeof(struct ospf_ti_lfa_node_info));
659 q_space->q_node_info = XCALLOC(MTYPE_OSPF_Q_SPACE,
660 sizeof(struct ospf_ti_lfa_node_info));
661
662 new_table = route_table_init();
663
664 /*
665 * Generate a new (reversed!) SPF tree for this vertex,
666 * dry run true, root node false
667 */
668 area->spf_reversed = true;
669 ospf_spf_calculate(area, dest->lsa_p, new_table, NULL, NULL, true,
670 false);
671
672 /* Reset the flag for reverse SPF */
673 area->spf_reversed = false;
674
675 q_space->root = area->spf;
676 q_space->vertex_list = area->spf_vertex_list;
677 q_space->label_stack = NULL;
678
679 if (pc_path)
680 q_space->pc_path = ospf_ti_lfa_map_path_to_pc_vertices(
681 pc_path, p_space->pc_vertex_list);
682 else
683 q_space->pc_path = ospf_ti_lfa_generate_post_convergence_path(
684 p_space->pc_vertex_list, q_space->root);
685
686 /* If there's no backup path available then we are done here. */
687 if (!q_space->pc_path) {
688 zlog_info(
689 "%s: NO backup path found for root %pI4 and destination %pI4 for %s, aborting ...",
690 __func__, &p_space->root->id, &q_space->root->id,
691 res_buf);
692
693 XFREE(MTYPE_OSPF_Q_SPACE, q_space->p_node_info);
694 XFREE(MTYPE_OSPF_Q_SPACE, q_space->q_node_info);
695 XFREE(MTYPE_OSPF_Q_SPACE, q_space);
696
697 return;
698 }
699
700 /* 'Cut' the protected resource out of the new SPF tree */
701 ospf_spf_remove_resource(q_space->root, q_space->vertex_list,
702 p_space->protected_resource);
703
704 /*
705 * Generate the smallest possible label stack from the root of the P
706 * space to the root of the Q space.
707 */
708 ospf_ti_lfa_generate_label_stack(area, p_space, q_space);
709
710 if (q_space->label_stack) {
711 mpls_label2str(q_space->label_stack->num_labels,
712 q_space->label_stack->label, label_buf,
713 MPLS_LABEL_STRLEN, 0, true);
714 zlog_info(
715 "%s: Generated label stack %s for root %pI4 and destination %pI4 for %s",
716 __func__, label_buf, &p_space->root->id,
717 &q_space->root->id, res_buf);
718 } else {
719 zlog_info(
720 "%s: NO label stack generated for root %pI4 and destination %pI4 for %s",
721 __func__, &p_space->root->id, &q_space->root->id,
722 res_buf);
723 }
724
725 /* We are finished, store the new Q space in the P space struct */
726 q_spaces_add(p_space->q_spaces, q_space);
727
728 /* Recursively generate Q spaces for all children */
729 if (recursive) {
730 for (ALL_LIST_ELEMENTS_RO(dest->children, node, child))
731 ospf_ti_lfa_generate_q_spaces(area, p_space, child,
732 recursive, pc_path);
733 }
734 }
735
736 static void ospf_ti_lfa_generate_post_convergence_spf(struct ospf_area *area,
737 struct p_space *p_space)
738 {
739 struct route_table *new_table;
740
741 new_table = route_table_init();
742
743 area->spf_protected_resource = p_space->protected_resource;
744
745 /*
746 * The 'post convergence' SPF tree is generated here
747 * dry run true, root node false
748 *
749 * So how does this work? During the SPF calculation the algorithm
750 * checks if a link belongs to a protected resource and then just
751 * ignores it.
752 * This is actually _NOT_ a good way to calculate the post
753 * convergence SPF tree. The preferred way would be to delete the
754 * relevant links (and nodes) from a copy of the LSDB and then just run
755 * the SPF algorithm on that as usual.
756 * However, removing links from router LSAs appears to be its own
757 * endeavour (because LSAs are stored as a 'raw' stream), so we go with
758 * this rather hacky way for now.
759 */
760 ospf_spf_calculate(area, area->router_lsa_self, new_table, NULL, NULL,
761 true, false);
762
763 p_space->pc_spf = area->spf;
764 p_space->pc_vertex_list = area->spf_vertex_list;
765
766 area->spf_protected_resource = NULL;
767 }
768
769 static void
770 ospf_ti_lfa_generate_p_space(struct ospf_area *area, struct vertex *child,
771 struct protected_resource *protected_resource,
772 bool recursive, struct list *pc_path)
773 {
774 struct vertex *spf_orig;
775 struct list *vertex_list, *vertex_list_orig;
776 struct p_space *p_space;
777
778 p_space = XCALLOC(MTYPE_OSPF_P_SPACE, sizeof(struct p_space));
779 vertex_list = list_new();
780
781 /* The P-space will get its own SPF tree, so copy the old one */
782 ospf_spf_copy(area->spf, vertex_list);
783 p_space->root = listnode_head(vertex_list);
784 p_space->vertex_list = vertex_list;
785 p_space->protected_resource = protected_resource;
786
787 /* Initialize the Q spaces for this P space and protected resource */
788 p_space->q_spaces =
789 XCALLOC(MTYPE_OSPF_Q_SPACE, sizeof(struct q_spaces_head));
790 q_spaces_init(p_space->q_spaces);
791
792 /* 'Cut' the protected resource out of the new SPF tree */
793 ospf_spf_remove_resource(p_space->root, p_space->vertex_list,
794 p_space->protected_resource);
795
796 /*
797 * Since we are going to calculate more SPF trees for Q spaces, keep the
798 * 'original' one here temporarily
799 */
800 spf_orig = area->spf;
801 vertex_list_orig = area->spf_vertex_list;
802
803 /* Generate the post convergence SPF as a blueprint for backup paths */
804 ospf_ti_lfa_generate_post_convergence_spf(area, p_space);
805
806 /* Generate the relevant Q spaces for this particular P space */
807 ospf_ti_lfa_generate_q_spaces(area, p_space, child, recursive, pc_path);
808
809 /* Put the 'original' SPF tree back in place */
810 area->spf = spf_orig;
811 area->spf_vertex_list = vertex_list_orig;
812
813 /* We are finished, store the new P space */
814 p_spaces_add(area->p_spaces, p_space);
815 }
816
817 void ospf_ti_lfa_generate_p_spaces(struct ospf_area *area,
818 enum protection_type protection_type)
819 {
820 struct listnode *node, *inner_node;
821 struct vertex *root, *child;
822 struct vertex_parent *vertex_parent;
823 uint8_t *p, *lim;
824 struct router_lsa_link *l = NULL;
825 struct prefix stub_prefix, child_prefix;
826 struct protected_resource *protected_resource;
827
828 area->p_spaces =
829 XCALLOC(MTYPE_OSPF_P_SPACE, sizeof(struct p_spaces_head));
830 p_spaces_init(area->p_spaces);
831
832 root = area->spf;
833
834 /* Root or its router LSA was not created yet? */
835 if (!root || !root->lsa)
836 return;
837
838 stub_prefix.family = AF_INET;
839 child_prefix.family = AF_INET;
840 child_prefix.prefixlen = IPV4_MAX_BITLEN;
841
842 p = ((uint8_t *)root->lsa) + OSPF_LSA_HEADER_SIZE + 4;
843 lim = ((uint8_t *)root->lsa) + ntohs(root->lsa->length);
844
845 zlog_info("%s: Generating P spaces for area %pI4", __func__,
846 &area->area_id);
847
848 /*
849 * Iterate over all stub networks which target other OSPF neighbors.
850 * Check the nexthop of the child vertex if a stub network is relevant.
851 */
852 while (p < lim) {
853 l = (struct router_lsa_link *)p;
854 p += (OSPF_ROUTER_LSA_LINK_SIZE
855 + (l->m[0].tos_count * OSPF_ROUTER_LSA_TOS_SIZE));
856
857 /* First comes node protection */
858 if (protection_type == OSPF_TI_LFA_NODE_PROTECTION) {
859 if (l->m[0].type == LSA_LINK_TYPE_POINTOPOINT) {
860 protected_resource = XCALLOC(
861 MTYPE_OSPF_P_SPACE,
862 sizeof(struct protected_resource));
863 protected_resource->type = protection_type;
864 protected_resource->router_id = l->link_id;
865 child = ospf_spf_vertex_find(
866 protected_resource->router_id,
867 root->children);
868 if (child)
869 ospf_ti_lfa_generate_p_space(
870 area, child, protected_resource,
871 true, NULL);
872 }
873
874 continue;
875 }
876
877 /* The rest is about link protection */
878 if (protection_type != OSPF_TI_LFA_LINK_PROTECTION)
879 continue;
880
881 if (l->m[0].type != LSA_LINK_TYPE_STUB)
882 continue;
883
884 stub_prefix.prefixlen = ip_masklen(l->link_data);
885 stub_prefix.u.prefix4 = l->link_id;
886
887 for (ALL_LIST_ELEMENTS_RO(root->children, node, child)) {
888
889 if (child->type != OSPF_VERTEX_ROUTER)
890 continue;
891
892 for (ALL_LIST_ELEMENTS_RO(child->parents, inner_node,
893 vertex_parent)) {
894
895 child_prefix.u.prefix4 =
896 vertex_parent->nexthop->router;
897
898 /*
899 * If there's a link for that stub network then
900 * we will protect it. Hence generate a P space
901 * for that particular link including the
902 * Q spaces so we can later on generate a
903 * backup path for the link.
904 */
905 if (prefix_match(&stub_prefix, &child_prefix)) {
906 zlog_info(
907 "%s: Generating P space for %pI4",
908 __func__, &l->link_id);
909
910 protected_resource = XCALLOC(
911 MTYPE_OSPF_P_SPACE,
912 sizeof(struct
913 protected_resource));
914 protected_resource->type =
915 protection_type;
916 protected_resource->link = l;
917
918 ospf_ti_lfa_generate_p_space(
919 area, child, protected_resource,
920 true, NULL);
921 }
922 }
923 }
924 }
925 }
926
927 static struct p_space *ospf_ti_lfa_get_p_space_by_path(struct ospf_area *area,
928 struct ospf_path *path)
929 {
930 struct p_space *p_space;
931 struct router_lsa_link *link;
932 struct vertex *child;
933 int type;
934
935 frr_each(p_spaces, area->p_spaces, p_space) {
936 type = p_space->protected_resource->type;
937
938 if (type == OSPF_TI_LFA_LINK_PROTECTION) {
939 link = p_space->protected_resource->link;
940 if ((path->nexthop.s_addr & link->link_data.s_addr)
941 == (link->link_id.s_addr & link->link_data.s_addr))
942 return p_space;
943 }
944
945 if (type == OSPF_TI_LFA_NODE_PROTECTION) {
946 child = ospf_spf_vertex_by_nexthop(area->spf,
947 &path->nexthop);
948 if (child
949 && p_space->protected_resource->router_id.s_addr
950 == child->id.s_addr)
951 return p_space;
952 }
953 }
954
955 return NULL;
956 }
957
958 void ospf_ti_lfa_insert_backup_paths(struct ospf_area *area,
959 struct route_table *new_table)
960 {
961 struct route_node *rn;
962 struct ospf_route *or;
963 struct ospf_path *path;
964 struct listnode *node;
965 struct p_space *p_space;
966 struct q_space *q_space, q_space_search;
967 struct vertex root_search;
968 char label_buf[MPLS_LABEL_STRLEN];
969
970 for (rn = route_top(new_table); rn; rn = route_next(rn)) {
971 or = rn->info;
972 if (or == NULL)
973 continue;
974
975 /* Insert a backup path for all OSPF paths */
976 for (ALL_LIST_ELEMENTS_RO(or->paths, node, path)) {
977
978 if (path->adv_router.s_addr == INADDR_ANY
979 || path->nexthop.s_addr == INADDR_ANY)
980 continue;
981
982 if (IS_DEBUG_OSPF_TI_LFA)
983 zlog_debug(
984 "%s: attempting to insert backup path for prefix %pFX, router id %pI4 and nexthop %pI4.",
985 __func__, &rn->p, &path->adv_router,
986 &path->nexthop);
987
988 p_space = ospf_ti_lfa_get_p_space_by_path(area, path);
989 if (!p_space) {
990 if (IS_DEBUG_OSPF_TI_LFA)
991 zlog_debug(
992 "%s: P space not found for router id %pI4 and nexthop %pI4.",
993 __func__, &path->adv_router,
994 &path->nexthop);
995 continue;
996 }
997
998 root_search.id = path->adv_router;
999 q_space_search.root = &root_search;
1000 q_space = q_spaces_find(p_space->q_spaces,
1001 &q_space_search);
1002 if (!q_space) {
1003 if (IS_DEBUG_OSPF_TI_LFA)
1004 zlog_debug(
1005 "%s: Q space not found for advertising router %pI4.",
1006 __func__, &path->adv_router);
1007 continue;
1008 }
1009
1010 /* If there's a backup label stack, insert it*/
1011 if (q_space->label_stack) {
1012 /* Init the backup path data in path */
1013 path->srni.backup_label_stack = XCALLOC(
1014 MTYPE_OSPF_PATH,
1015 sizeof(struct mpls_label_stack)
1016 + sizeof(mpls_label_t)
1017 * q_space->label_stack
1018 ->num_labels);
1019
1020 /* Copy over the label stack */
1021 path->srni.backup_label_stack->num_labels =
1022 q_space->label_stack->num_labels;
1023 memcpy(path->srni.backup_label_stack->label,
1024 q_space->label_stack->label,
1025 sizeof(mpls_label_t)
1026 * q_space->label_stack
1027 ->num_labels);
1028
1029 /* Set the backup nexthop too */
1030 path->srni.backup_nexthop = q_space->nexthop;
1031 }
1032
1033 if (path->srni.backup_label_stack) {
1034 mpls_label2str(
1035 path->srni.backup_label_stack
1036 ->num_labels,
1037 path->srni.backup_label_stack->label,
1038 label_buf, MPLS_LABEL_STRLEN, 0, true);
1039 if (IS_DEBUG_OSPF_TI_LFA)
1040 zlog_debug(
1041 "%s: inserted backup path %s for prefix %pFX, router id %pI4 and nexthop %pI4.",
1042 __func__, label_buf, &rn->p,
1043 &path->adv_router,
1044 &path->nexthop);
1045 } else {
1046 if (IS_DEBUG_OSPF_TI_LFA)
1047 zlog_debug(
1048 "%s: inserted NO backup path for prefix %pFX, router id %pI4 and nexthop %pI4.",
1049 __func__, &rn->p,
1050 &path->adv_router,
1051 &path->nexthop);
1052 }
1053 }
1054 }
1055 }
1056
1057 void ospf_ti_lfa_free_p_spaces(struct ospf_area *area)
1058 {
1059 struct p_space *p_space;
1060 struct q_space *q_space;
1061
1062 while ((p_space = p_spaces_pop(area->p_spaces))) {
1063 while ((q_space = q_spaces_pop(p_space->q_spaces))) {
1064 ospf_spf_cleanup(q_space->root, q_space->vertex_list);
1065
1066 if (q_space->pc_path)
1067 list_delete(&q_space->pc_path);
1068
1069 XFREE(MTYPE_OSPF_Q_SPACE, q_space->p_node_info);
1070 XFREE(MTYPE_OSPF_Q_SPACE, q_space->q_node_info);
1071 XFREE(MTYPE_OSPF_Q_SPACE, q_space->label_stack);
1072 XFREE(MTYPE_OSPF_Q_SPACE, q_space);
1073 }
1074
1075 ospf_spf_cleanup(p_space->root, p_space->vertex_list);
1076 ospf_spf_cleanup(p_space->pc_spf, p_space->pc_vertex_list);
1077 XFREE(MTYPE_OSPF_P_SPACE, p_space->protected_resource);
1078
1079 q_spaces_fini(p_space->q_spaces);
1080 XFREE(MTYPE_OSPF_Q_SPACE, p_space->q_spaces);
1081 }
1082
1083 p_spaces_fini(area->p_spaces);
1084 XFREE(MTYPE_OSPF_P_SPACE, area->p_spaces);
1085 }
1086
1087 void ospf_ti_lfa_compute(struct ospf_area *area, struct route_table *new_table,
1088 enum protection_type protection_type)
1089 {
1090 /*
1091 * Generate P spaces per protected link/node and their respective Q
1092 * spaces, generate backup paths (MPLS label stacks) by finding P/Q
1093 * nodes.
1094 */
1095 ospf_ti_lfa_generate_p_spaces(area, protection_type);
1096
1097 /* Insert the generated backup paths into the routing table. */
1098 ospf_ti_lfa_insert_backup_paths(area, new_table);
1099
1100 /* Cleanup P spaces and related datastructures including Q spaces. */
1101 ospf_ti_lfa_free_p_spaces(area);
1102 }
FRRouting mirror