]> 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
ospfd: Minor memory fixes
[mirror_frr.git] / ospfd / ospf_ti_lfa.c
1 /*
2 * OSPF TI-LFA
3 * Copyright (C) 2020 NetDEF, Inc.
4 * Sascha Kattelmann
5 *
6 * This file is part of FRR.
7 *
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
11 * later version.
12 *
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.
17 *
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
21 */
22
23 #include <zebra.h>
24
25 #include "prefix.h"
26 #include "table.h"
27 #include "printfrr.h"
28
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"
37
38
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)
43
44 static void
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);
48
49 void ospf_print_protected_resource(
50 struct protected_resource *protected_resource, char *buf)
51 {
52 struct router_lsa_link *link;
53
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,
59 &link->link_data);
60 break;
61 case OSPF_TI_LFA_NODE_PROTECTION:
62 snprintfrr(buf, PROTECTED_RESOURCE_STRLEN,
63 "protected node: %pI4",
64 &protected_resource->router_id);
65 break;
66 case OSPF_TI_LFA_UNDEFINED_PROTECTION:
67 snprintfrr(buf, PROTECTED_RESOURCE_STRLEN,
68 "undefined protected resource");
69 break;
70 }
71 }
72
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)
76 {
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;
80
81 curr_node = listnode_lookup(q_space->pc_path, pc_node);
82 pc_node_parent = listgetdata(curr_node->next);
83
84 q_space->p_node_info->type = OSPF_TI_LFA_UNDEFINED_NODE;
85
86 p_node = ospf_spf_vertex_find(pc_node_parent->id, p_space->vertex_list);
87
88 if (p_node) {
89 q_space->p_node_info->node = p_node;
90 q_space->p_node_info->type = OSPF_TI_LFA_P_NODE;
91
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;
98 } else {
99 /*
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.
103 */
104 q_space->p_node_info->nexthop.s_addr = INADDR_ANY;
105 }
106
107 return OSPF_TI_LFA_P_Q_SPACE_ADJACENT;
108 }
109
110 ospf_ti_lfa_find_p_node(pc_node_parent, p_space, q_space);
111 return OSPF_TI_LFA_P_Q_SPACE_NON_ADJACENT;
112 }
113
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)
117 {
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;
121
122 curr_node = listnode_lookup(q_space->pc_path, pc_node);
123 next_node = curr_node->next;
124 pc_node_parent = listgetdata(next_node);
125 pc_vertex_parent =
126 ospf_spf_vertex_parent_find(pc_node_parent->id, pc_node);
127
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);
130
131 /* The Q node is always present. */
132 assert(q_node);
133
134 q_space->q_node_info->type = OSPF_TI_LFA_UNDEFINED_NODE;
135
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;
141 return;
142 }
143
144 /*
145 * Note that the Q space has the 'reverse' direction of the PC
146 * SPF. Hence compare PC SPF parent to Q space children.
147 */
148 q_space_parent =
149 ospf_spf_vertex_find(pc_node_parent->id, q_node->children);
150
151 /*
152 * If the Q space parent doesn't exist we 'hit' the border to the P
153 * space and hence got our Q node.
154 */
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;
160 return;
161 }
162
163 return ospf_ti_lfa_find_q_node(pc_node_parent, p_space, q_space);
164 }
165
166 static void ospf_ti_lfa_append_label_stack(struct mpls_label_stack *label_stack,
167 mpls_label_t labels[],
168 uint32_t num_labels)
169 {
170 int i, offset, limit;
171
172 limit = label_stack->num_labels + num_labels;
173 offset = label_stack->num_labels;
174
175 for (i = label_stack->num_labels; i < limit; i++) {
176 label_stack->label[i] = labels[i - offset];
177 label_stack->num_labels++;
178 }
179 }
180
181
182 static struct mpls_label_stack *
183 ospf_ti_lfa_create_label_stack(mpls_label_t labels[], uint32_t num_labels)
184 {
185 struct mpls_label_stack *label_stack;
186 uint32_t i;
187
188 /* Sanity check */
189 for (i = 0; i < num_labels; i++) {
190 if (labels[i] == MPLS_INVALID_LABEL)
191 return NULL;
192 }
193
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;
198
199 for (i = 0; i < num_labels; i++)
200 label_stack->label[i] = labels[i];
201
202 return label_stack;
203 }
204
205 static struct list *
206 ospf_ti_lfa_map_path_to_pc_vertices(struct list *path,
207 struct list *pc_vertex_list)
208 {
209 struct listnode *node;
210 struct vertex *vertex, *pc_vertex;
211 struct list *pc_path;
212
213 pc_path = list_new();
214
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);
218 }
219
220 return pc_path;
221 }
222
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)
227 {
228 struct list *inner_pc_path;
229 struct vertex *current_vertex;
230 struct listnode *current_listnode;
231
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);
235
236 /* Note that the post-convergence paths are reversed. */
237 for (;;) {
238 current_vertex = listgetdata(current_listnode);
239 listnode_add(inner_pc_path, current_vertex);
240
241 if (current_vertex->id.s_addr == p_node->id.s_addr)
242 break;
243
244 current_listnode = current_listnode->next;
245 }
246
247 return inner_pc_path;
248 }
249
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)
254 {
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;
269
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;
273
274 start_vertex = p_node_info->node;
275 end_vertex = q_node_info->node;
276
277 /*
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.
281 */
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,
288 &start_vertex->id);
289 }
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);
296 }
297
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,
307 end_vertex);
308 inner_backup_path_info->p_node_info.nexthop =
309 vertex_parent->nexthop->router;
310 return;
311 }
312
313 inner_pc_path = ospf_ti_lfa_cut_out_pc_path(p_space->pc_vertex_list,
314 q_space->pc_path,
315 start_vertex, end_vertex);
316
317 new_table = route_table_init();
318 new_rtrs = route_table_init();
319
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;
324
325 area->p_spaces =
326 XCALLOC(MTYPE_OSPF_P_SPACE, sizeof(struct p_spaces_head));
327
328 /* dry run true, root node false */
329 ospf_spf_calculate(area, start_vertex->lsa_p, new_table, new_rtrs, true,
330 false);
331
332 q_node = ospf_spf_vertex_find(end_vertex->id, area->spf_vertex_list);
333
334 ospf_ti_lfa_generate_p_space(area, q_node, protected_resource, false,
335 inner_pc_path);
336
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);
340
341 /* Copy over inner backup path information from the inner q_space */
342
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,
354 start_vertex);
355 inner_backup_path_info->p_node_info.nexthop =
356 vertex_parent->nexthop->router;
357 } else {
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
363 ->num_labels);
364 memcpy(&inner_backup_path_info->p_node_info,
365 inner_q_space->p_node_info,
366 sizeof(struct ospf_ti_lfa_node_info));
367 }
368
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;
373 } else {
374 memcpy(&inner_backup_path_info->q_node_info,
375 inner_q_space->q_node_info,
376 sizeof(struct ospf_ti_lfa_node_info));
377 }
378
379 /* Cleanup */
380 ospf_ti_lfa_free_p_spaces(area);
381 ospf_spf_cleanup(area->spf, area->spf_vertex_list);
382
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;
387 }
388
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)
392 {
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;
397
398 if (IS_DEBUG_OSPF_TI_LFA)
399 zlog_debug(
400 "%s: Generating Label stack for src %pI4 and dest %pI4.",
401 __func__, &p_space->root->id, &q_space->root->id);
402
403 pc_node = listnode_head(q_space->pc_path);
404
405 if (!pc_node) {
406 if (IS_DEBUG_OSPF_TI_LFA)
407 zlog_debug(
408 "%s: There seems to be no post convergence path (yet).",
409 __func__);
410 return;
411 }
412
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__);
417 return;
418 }
419
420 /* Found a PQ node? Then we are done here. */
421 if (q_space->q_node_info->type == OSPF_TI_LFA_PQ_NODE) {
422 /*
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.
425 */
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(
429 &p_space->root->id,
430 &q_space->q_node_info->node->id);
431 else
432 labels[0] = ospf_sr_get_prefix_sid_by_id(
433 &q_space->q_node_info->node->id);
434
435 q_space->label_stack =
436 ospf_ti_lfa_create_label_stack(labels, 1);
437 q_space->nexthop = q_space->q_node_info->nexthop;
438
439 return;
440 }
441
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);
446
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__);
450 return;
451 }
452
453 /*
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
456 * symmetric weights.
457 */
458 if (adjacency_result == OSPF_TI_LFA_P_Q_SPACE_ADJACENT) {
459 /*
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
462 * the Q node.
463 */
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(
467 &p_space->root->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;
472 return;
473 }
474
475 /*
476 * Otherwise we have a P and also a Q node (which are adjacent).
477 *
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
481 * adjacency SID.
482 */
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(
486 &p_space->root->id,
487 &q_space->p_node_info->node->id);
488 else
489 labels[0] = ospf_sr_get_prefix_sid_by_id(
490 &q_space->p_node_info->node->id);
491
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);
495
496 q_space->label_stack =
497 ospf_ti_lfa_create_label_stack(labels, 2);
498 q_space->nexthop = q_space->p_node_info->nexthop;
499
500 } else {
501 /*
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!
506 *
507 * After having found the inner label stack it is stitched
508 * together with the outer labels.
509 */
510 inner_backup_path_info.label_stack = XCALLOC(
511 MTYPE_OSPF_PATH,
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);
516
517 /*
518 * First stitch together the outer P node label with the inner
519 * label stack.
520 */
521 if (q_space->p_node_info->node->id.s_addr
522 == p_space->root->id.s_addr) {
523 /*
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.
527 */
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);
531
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;
537 else
538 q_space->nexthop = inner_backup_path_info
539 .q_node_info.nexthop;
540
541 } else if (ospf_spf_vertex_parent_find(
542 p_space->root->id,
543 q_space->p_node_info->node)) {
544 /*
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.
549 */
550 labels[0] = ospf_sr_get_adj_sid_by_id(
551 &p_space->root->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;
560 } else {
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;
571 }
572
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)) {
577 /*
578 * The outer Q node can be a child of the inner Q node,
579 * hence just add an Adjacency-SID.
580 */
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,
585 labels, 1);
586 } else {
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,
591 labels, 1);
592 }
593 /*
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!
596 */
597 }
598 }
599
600 static struct list *
601 ospf_ti_lfa_generate_post_convergence_path(struct list *pc_vertex_list,
602 struct vertex *dest)
603 {
604 struct list *pc_path;
605 struct vertex *current_vertex;
606 struct vertex_parent *parent;
607
608 current_vertex = ospf_spf_vertex_find(dest->id, pc_vertex_list);
609 if (!current_vertex) {
610 if (IS_DEBUG_OSPF_TI_LFA)
611 zlog_debug(
612 "%s: There seems to be no post convergence path (yet).",
613 __func__);
614 return NULL;
615 }
616
617 pc_path = list_new();
618 listnode_add(pc_path, current_vertex);
619
620 /* Generate a backup path in reverse order */
621 for (;;) {
622 parent = listnode_head(current_vertex->parents);
623 if (!parent)
624 break;
625
626 listnode_add(pc_path, parent->parent);
627 current_vertex = parent->parent;
628 }
629
630 return pc_path;
631 }
632
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)
637 {
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];
644 bool node_protected;
645
646 ospf_print_protected_resource(p_space->protected_resource, res_buf);
647 node_protected =
648 p_space->protected_resource->type == OSPF_TI_LFA_NODE_PROTECTION
649 && dest->id.s_addr
650 == p_space->protected_resource->router_id.s_addr;
651
652 /*
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.
655 */
656 if (node_protected) {
657 if (recursive) {
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,
661 child, recursive,
662 pc_path);
663 }
664 return;
665 }
666
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))
670 return;
671
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));
677
678 new_table = route_table_init();
679 new_rtrs = route_table_init();
680
681 /*
682 * Generate a new (reversed!) SPF tree for this vertex,
683 * dry run true, root node false
684 */
685 area->spf_reversed = true;
686 ospf_spf_calculate(area, dest->lsa_p, new_table, new_rtrs, true, false);
687
688 /* Reset the flag for reverse SPF */
689 area->spf_reversed = false;
690
691 q_space->root = area->spf;
692 q_space->vertex_list = area->spf_vertex_list;
693 q_space->label_stack = NULL;
694
695 if (pc_path)
696 q_space->pc_path = ospf_ti_lfa_map_path_to_pc_vertices(
697 pc_path, p_space->pc_vertex_list);
698 else
699 q_space->pc_path = ospf_ti_lfa_generate_post_convergence_path(
700 p_space->pc_vertex_list, q_space->root);
701
702 /* If there's no backup path available then we are done here. */
703 if (!q_space->pc_path) {
704 zlog_info(
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,
707 res_buf);
708 return;
709 }
710
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);
714
715 /*
716 * Generate the smallest possible label stack from the root of the P
717 * space to the root of the Q space.
718 */
719 ospf_ti_lfa_generate_label_stack(area, p_space, q_space);
720
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);
725 zlog_info(
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);
729 } else {
730 zlog_info(
731 "%s: NO label stack generated for root %pI4 and destination %pI4 for %s",
732 __func__, &p_space->root->id, &q_space->root->id,
733 res_buf);
734 }
735
736 /* We are finished, store the new Q space in the P space struct */
737 q_spaces_add(p_space->q_spaces, q_space);
738
739 /* Recursively generate Q spaces for all children */
740 if (recursive) {
741 for (ALL_LIST_ELEMENTS_RO(dest->children, node, child))
742 ospf_ti_lfa_generate_q_spaces(area, p_space, child,
743 recursive, pc_path);
744 }
745 }
746
747 static void ospf_ti_lfa_generate_post_convergence_spf(struct ospf_area *area,
748 struct p_space *p_space)
749 {
750 struct route_table *new_table, *new_rtrs;
751
752 new_table = route_table_init();
753 new_rtrs = route_table_init();
754
755 area->spf_protected_resource = p_space->protected_resource;
756
757 /*
758 * The 'post convergence' SPF tree is generated here
759 * dry run true, root node false
760 *
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
763 * ignores it.
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.
771 */
772 ospf_spf_calculate(area, area->router_lsa_self, new_table, new_rtrs,
773 true, false);
774
775 p_space->pc_spf = area->spf;
776 p_space->pc_vertex_list = area->spf_vertex_list;
777
778 area->spf_protected_resource = NULL;
779 }
780
781 static void
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)
785 {
786 struct vertex *spf_orig;
787 struct list *vertex_list, *vertex_list_orig;
788 struct p_space *p_space;
789
790 p_space = XCALLOC(MTYPE_OSPF_P_SPACE, sizeof(struct p_space));
791 vertex_list = list_new();
792
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;
798
799 /* Initialize the Q spaces for this P space and protected resource */
800 p_space->q_spaces =
801 XCALLOC(MTYPE_OSPF_Q_SPACE, sizeof(struct q_spaces_head));
802 q_spaces_init(p_space->q_spaces);
803
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);
807
808 /*
809 * Since we are going to calculate more SPF trees for Q spaces, keep the
810 * 'original' one here temporarily
811 */
812 spf_orig = area->spf;
813 vertex_list_orig = area->spf_vertex_list;
814
815 /* Generate the post convergence SPF as a blueprint for backup paths */
816 ospf_ti_lfa_generate_post_convergence_spf(area, p_space);
817
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);
820
821 /* Put the 'original' SPF tree back in place */
822 area->spf = spf_orig;
823 area->spf_vertex_list = vertex_list_orig;
824
825 /* We are finished, store the new P space */
826 p_spaces_add(area->p_spaces, p_space);
827 }
828
829 void ospf_ti_lfa_generate_p_spaces(struct ospf_area *area,
830 enum protection_type protection_type)
831 {
832 struct listnode *node, *inner_node;
833 struct vertex *root, *child;
834 struct vertex_parent *vertex_parent;
835 uint8_t *p, *lim;
836 struct router_lsa_link *l = NULL;
837 struct prefix stub_prefix, child_prefix;
838 struct protected_resource *protected_resource;
839
840 area->p_spaces =
841 XCALLOC(MTYPE_OSPF_P_SPACE, sizeof(struct p_spaces_head));
842 p_spaces_init(area->p_spaces);
843
844 root = area->spf;
845
846 /* Root or its router LSA was not created yet? */
847 if (!root || !root->lsa)
848 return;
849
850 stub_prefix.family = AF_INET;
851 child_prefix.family = AF_INET;
852 child_prefix.prefixlen = IPV4_MAX_PREFIXLEN;
853
854 p = ((uint8_t *)root->lsa) + OSPF_LSA_HEADER_SIZE + 4;
855 lim = ((uint8_t *)root->lsa) + ntohs(root->lsa->length);
856
857 zlog_info("%s: Generating P spaces for area %pI4", __func__,
858 &area->area_id);
859
860 /*
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.
863 */
864 while (p < lim) {
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));
868
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(
873 MTYPE_OSPF_P_SPACE,
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,
879 root->children);
880 if (child)
881 ospf_ti_lfa_generate_p_space(
882 area, child, protected_resource,
883 true, NULL);
884 }
885
886 continue;
887 }
888
889 /* The rest is about link protection */
890 if (protection_type != OSPF_TI_LFA_LINK_PROTECTION)
891 continue;
892
893 if (l->m[0].type != LSA_LINK_TYPE_STUB)
894 continue;
895
896 stub_prefix.prefixlen = ip_masklen(l->link_data);
897 stub_prefix.u.prefix4 = l->link_id;
898
899 for (ALL_LIST_ELEMENTS_RO(root->children, node, child)) {
900
901 if (child->type != OSPF_VERTEX_ROUTER)
902 continue;
903
904 for (ALL_LIST_ELEMENTS_RO(child->parents, inner_node,
905 vertex_parent)) {
906
907 child_prefix.u.prefix4 =
908 vertex_parent->nexthop->router;
909
910 /*
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.
916 */
917 if (prefix_match(&stub_prefix, &child_prefix)) {
918 zlog_info(
919 "%s: Generating P space for %pI4",
920 __func__, &l->link_id);
921
922 protected_resource = XCALLOC(
923 MTYPE_OSPF_P_SPACE,
924 sizeof(struct
925 protected_resource));
926 protected_resource->type =
927 protection_type;
928 protected_resource->link = l;
929
930 ospf_ti_lfa_generate_p_space(
931 area, child, protected_resource,
932 true, NULL);
933 }
934 }
935 }
936 }
937 }
938
939 static struct p_space *ospf_ti_lfa_get_p_space_by_path(struct ospf_area *area,
940 struct ospf_path *path)
941 {
942 struct p_space *p_space;
943 struct router_lsa_link *link;
944 struct vertex *child;
945 int type;
946
947 frr_each(p_spaces, area->p_spaces, p_space) {
948 type = p_space->protected_resource->type;
949
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))
954 return p_space;
955 }
956
957 if (type == OSPF_TI_LFA_NODE_PROTECTION) {
958 child = ospf_spf_vertex_by_nexthop(area->spf,
959 &path->nexthop);
960 if (child
961 && p_space->protected_resource->router_id.s_addr
962 == child->id.s_addr)
963 return p_space;
964 }
965 }
966
967 return NULL;
968 }
969
970 void ospf_ti_lfa_insert_backup_paths(struct ospf_area *area,
971 struct route_table *new_table)
972 {
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];
981
982 for (rn = route_top(new_table); rn; rn = route_next(rn)) {
983 or = rn->info;
984 if (or == NULL)
985 continue;
986
987 /* Insert a backup path for all OSPF paths */
988 for (ALL_LIST_ELEMENTS_RO(or->paths, node, path)) {
989
990 if (path->adv_router.s_addr == INADDR_ANY
991 || path->nexthop.s_addr == INADDR_ANY)
992 continue;
993
994 if (IS_DEBUG_OSPF_TI_LFA)
995 zlog_debug(
996 "%s: attempting to insert backup path for prefix %pFX, router id %pI4 and nexthop %pI4.",
997 __func__, &rn->p, &path->adv_router,
998 &path->nexthop);
999
1000 p_space = ospf_ti_lfa_get_p_space_by_path(area, path);
1001 if (!p_space) {
1002 if (IS_DEBUG_OSPF_TI_LFA)
1003 zlog_debug(
1004 "%s: P space not found for router id %pI4 and nexthop %pI4.",
1005 __func__, &path->adv_router,
1006 &path->nexthop);
1007 continue;
1008 }
1009
1010 root_search.id = path->adv_router;
1011 q_space_search.root = &root_search;
1012 q_space = q_spaces_find(p_space->q_spaces,
1013 &q_space_search);
1014 if (!q_space) {
1015 if (IS_DEBUG_OSPF_TI_LFA)
1016 zlog_debug(
1017 "%s: Q space not found for advertising router %pI4.",
1018 __func__, &path->adv_router);
1019 continue;
1020 }
1021
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(
1026 MTYPE_OSPF_PATH,
1027 sizeof(struct mpls_label_stack)
1028 + sizeof(mpls_label_t)
1029 * q_space->label_stack
1030 ->num_labels);
1031
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
1039 ->num_labels);
1040
1041 /* Set the backup nexthop too */
1042 path->srni.backup_nexthop = q_space->nexthop;
1043 }
1044
1045 if (path->srni.backup_label_stack) {
1046 mpls_label2str(
1047 path->srni.backup_label_stack
1048 ->num_labels,
1049 path->srni.backup_label_stack->label,
1050 label_buf, MPLS_LABEL_STRLEN, true);
1051 if (IS_DEBUG_OSPF_TI_LFA)
1052 zlog_debug(
1053 "%s: inserted backup path %s for prefix %pFX, router id %pI4 and nexthop %pI4.",
1054 __func__, label_buf, &rn->p,
1055 &path->adv_router,
1056 &path->nexthop);
1057 } else {
1058 if (IS_DEBUG_OSPF_TI_LFA)
1059 zlog_debug(
1060 "%s: inserted NO backup path for prefix %pFX, router id %pI4 and nexthop %pI4.",
1061 __func__, &rn->p,
1062 &path->adv_router,
1063 &path->nexthop);
1064 }
1065 }
1066 }
1067 }
1068
1069 void ospf_ti_lfa_free_p_spaces(struct ospf_area *area)
1070 {
1071 struct p_space *p_space;
1072 struct q_space *q_space;
1073
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);
1077
1078 if (q_space->pc_path)
1079 list_delete(&q_space->pc_path);
1080
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);
1085 }
1086
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);
1090
1091 q_spaces_fini(p_space->q_spaces);
1092 XFREE(MTYPE_OSPF_Q_SPACE, p_space->q_spaces);
1093 }
1094
1095 p_spaces_fini(area->p_spaces);
1096 XFREE(MTYPE_OSPF_P_SPACE, area->p_spaces);
1097 }
1098
1099 void ospf_ti_lfa_compute(struct ospf_area *area, struct route_table *new_table,
1100 enum protection_type protection_type)
1101 {
1102 /*
1103 * Generate P spaces per protected link/node and their respective Q
1104 * spaces, generate backup paths (MPLS label stacks) by finding P/Q
1105 * nodes.
1106 */
1107 ospf_ti_lfa_generate_p_spaces(area, protection_type);
1108
1109 /* Insert the generated backup paths into the routing table. */
1110 ospf_ti_lfa_insert_backup_paths(area, new_table);
1111
1112 /* Cleanup P spaces and related datastructures including Q spaces. */
1113 ospf_ti_lfa_free_p_spaces(area);
1114 }
FRRouting mirror