]> git.proxmox.com Git - mirror_frr.git/blob - ospfd/ospf_ti_lfa.c
projects / mirror_frr.git / blob
? search:


28d24bcbe6b4b0af76dcc57d9f53af22205f57cf
[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, NULL, new_rtrs,
330 true, 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 /* XXX do these get freed?? */
680 new_rtrs = route_table_init();
681
682 /*
683 * Generate a new (reversed!) SPF tree for this vertex,
684 * dry run true, root node false
685 */
686 area->spf_reversed = true;
687 ospf_spf_calculate(area, dest->lsa_p, new_table, NULL, new_rtrs, true,
688 false);
689
690 /* Reset the flag for reverse SPF */
691 area->spf_reversed = false;
692
693 q_space->root = area->spf;
694 q_space->vertex_list = area->spf_vertex_list;
695 q_space->label_stack = NULL;
696
697 if (pc_path)
698 q_space->pc_path = ospf_ti_lfa_map_path_to_pc_vertices(
699 pc_path, p_space->pc_vertex_list);
700 else
701 q_space->pc_path = ospf_ti_lfa_generate_post_convergence_path(
702 p_space->pc_vertex_list, q_space->root);
703
704 /* If there's no backup path available then we are done here. */
705 if (!q_space->pc_path) {
706 zlog_info(
707 "%s: NO backup path found for root %pI4 and destination %pI4 for %s, aborting ...",
708 __func__, &p_space->root->id, &q_space->root->id,
709 res_buf);
710 return;
711 }
712
713 /* 'Cut' the protected resource out of the new SPF tree */
714 ospf_spf_remove_resource(q_space->root, q_space->vertex_list,
715 p_space->protected_resource);
716
717 /*
718 * Generate the smallest possible label stack from the root of the P
719 * space to the root of the Q space.
720 */
721 ospf_ti_lfa_generate_label_stack(area, p_space, q_space);
722
723 if (q_space->label_stack) {
724 mpls_label2str(q_space->label_stack->num_labels,
725 q_space->label_stack->label, label_buf,
726 MPLS_LABEL_STRLEN, true);
727 zlog_info(
728 "%s: Generated label stack %s for root %pI4 and destination %pI4 for %s",
729 __func__, label_buf, &p_space->root->id,
730 &q_space->root->id, res_buf);
731 } else {
732 zlog_info(
733 "%s: NO label stack generated for root %pI4 and destination %pI4 for %s",
734 __func__, &p_space->root->id, &q_space->root->id,
735 res_buf);
736 }
737
738 /* We are finished, store the new Q space in the P space struct */
739 q_spaces_add(p_space->q_spaces, q_space);
740
741 /* Recursively generate Q spaces for all children */
742 if (recursive) {
743 for (ALL_LIST_ELEMENTS_RO(dest->children, node, child))
744 ospf_ti_lfa_generate_q_spaces(area, p_space, child,
745 recursive, pc_path);
746 }
747 }
748
749 static void ospf_ti_lfa_generate_post_convergence_spf(struct ospf_area *area,
750 struct p_space *p_space)
751 {
752 struct route_table *new_table, *new_rtrs;
753
754 new_table = route_table_init();
755 /* XXX do these get freed?? */
756 new_rtrs = route_table_init();
757
758 area->spf_protected_resource = p_space->protected_resource;
759
760 /*
761 * The 'post convergence' SPF tree is generated here
762 * dry run true, root node false
763 *
764 * So how does this work? During the SPF calculation the algorithm
765 * checks if a link belongs to a protected resource and then just
766 * ignores it.
767 * This is actually _NOT_ a good way to calculate the post
768 * convergence SPF tree. The preferred way would be to delete the
769 * relevant links (and nodes) from a copy of the LSDB and then just run
770 * the SPF algorithm on that as usual.
771 * However, removing links from router LSAs appears to be its own
772 * endeavour (because LSAs are stored as a 'raw' stream), so we go with
773 * this rather hacky way for now.
774 */
775 ospf_spf_calculate(area, area->router_lsa_self, new_table, NULL,
776 new_rtrs, true, false);
777
778 p_space->pc_spf = area->spf;
779 p_space->pc_vertex_list = area->spf_vertex_list;
780
781 area->spf_protected_resource = NULL;
782 }
783
784 static void
785 ospf_ti_lfa_generate_p_space(struct ospf_area *area, struct vertex *child,
786 struct protected_resource *protected_resource,
787 bool recursive, struct list *pc_path)
788 {
789 struct vertex *spf_orig;
790 struct list *vertex_list, *vertex_list_orig;
791 struct p_space *p_space;
792
793 p_space = XCALLOC(MTYPE_OSPF_P_SPACE, sizeof(struct p_space));
794 vertex_list = list_new();
795
796 /* The P-space will get its own SPF tree, so copy the old one */
797 ospf_spf_copy(area->spf, vertex_list);
798 p_space->root = listnode_head(vertex_list);
799 p_space->vertex_list = vertex_list;
800 p_space->protected_resource = protected_resource;
801
802 /* Initialize the Q spaces for this P space and protected resource */
803 p_space->q_spaces =
804 XCALLOC(MTYPE_OSPF_Q_SPACE, sizeof(struct q_spaces_head));
805 q_spaces_init(p_space->q_spaces);
806
807 /* 'Cut' the protected resource out of the new SPF tree */
808 ospf_spf_remove_resource(p_space->root, p_space->vertex_list,
809 p_space->protected_resource);
810
811 /*
812 * Since we are going to calculate more SPF trees for Q spaces, keep the
813 * 'original' one here temporarily
814 */
815 spf_orig = area->spf;
816 vertex_list_orig = area->spf_vertex_list;
817
818 /* Generate the post convergence SPF as a blueprint for backup paths */
819 ospf_ti_lfa_generate_post_convergence_spf(area, p_space);
820
821 /* Generate the relevant Q spaces for this particular P space */
822 ospf_ti_lfa_generate_q_spaces(area, p_space, child, recursive, pc_path);
823
824 /* Put the 'original' SPF tree back in place */
825 area->spf = spf_orig;
826 area->spf_vertex_list = vertex_list_orig;
827
828 /* We are finished, store the new P space */
829 p_spaces_add(area->p_spaces, p_space);
830 }
831
832 void ospf_ti_lfa_generate_p_spaces(struct ospf_area *area,
833 enum protection_type protection_type)
834 {
835 struct listnode *node, *inner_node;
836 struct vertex *root, *child;
837 struct vertex_parent *vertex_parent;
838 uint8_t *p, *lim;
839 struct router_lsa_link *l = NULL;
840 struct prefix stub_prefix, child_prefix;
841 struct protected_resource *protected_resource;
842
843 area->p_spaces =
844 XCALLOC(MTYPE_OSPF_P_SPACE, sizeof(struct p_spaces_head));
845 p_spaces_init(area->p_spaces);
846
847 root = area->spf;
848
849 /* Root or its router LSA was not created yet? */
850 if (!root || !root->lsa)
851 return;
852
853 stub_prefix.family = AF_INET;
854 child_prefix.family = AF_INET;
855 child_prefix.prefixlen = IPV4_MAX_BITLEN;
856
857 p = ((uint8_t *)root->lsa) + OSPF_LSA_HEADER_SIZE + 4;
858 lim = ((uint8_t *)root->lsa) + ntohs(root->lsa->length);
859
860 zlog_info("%s: Generating P spaces for area %pI4", __func__,
861 &area->area_id);
862
863 /*
864 * Iterate over all stub networks which target other OSPF neighbors.
865 * Check the nexthop of the child vertex if a stub network is relevant.
866 */
867 while (p < lim) {
868 l = (struct router_lsa_link *)p;
869 p += (OSPF_ROUTER_LSA_LINK_SIZE
870 + (l->m[0].tos_count * OSPF_ROUTER_LSA_TOS_SIZE));
871
872 /* First comes node protection */
873 if (protection_type == OSPF_TI_LFA_NODE_PROTECTION) {
874 if (l->m[0].type == LSA_LINK_TYPE_POINTOPOINT) {
875 protected_resource = XCALLOC(
876 MTYPE_OSPF_P_SPACE,
877 sizeof(struct protected_resource));
878 protected_resource->type = protection_type;
879 protected_resource->router_id = l->link_id;
880 child = ospf_spf_vertex_find(
881 protected_resource->router_id,
882 root->children);
883 if (child)
884 ospf_ti_lfa_generate_p_space(
885 area, child, protected_resource,
886 true, NULL);
887 }
888
889 continue;
890 }
891
892 /* The rest is about link protection */
893 if (protection_type != OSPF_TI_LFA_LINK_PROTECTION)
894 continue;
895
896 if (l->m[0].type != LSA_LINK_TYPE_STUB)
897 continue;
898
899 stub_prefix.prefixlen = ip_masklen(l->link_data);
900 stub_prefix.u.prefix4 = l->link_id;
901
902 for (ALL_LIST_ELEMENTS_RO(root->children, node, child)) {
903
904 if (child->type != OSPF_VERTEX_ROUTER)
905 continue;
906
907 for (ALL_LIST_ELEMENTS_RO(child->parents, inner_node,
908 vertex_parent)) {
909
910 child_prefix.u.prefix4 =
911 vertex_parent->nexthop->router;
912
913 /*
914 * If there's a link for that stub network then
915 * we will protect it. Hence generate a P space
916 * for that particular link including the
917 * Q spaces so we can later on generate a
918 * backup path for the link.
919 */
920 if (prefix_match(&stub_prefix, &child_prefix)) {
921 zlog_info(
922 "%s: Generating P space for %pI4",
923 __func__, &l->link_id);
924
925 protected_resource = XCALLOC(
926 MTYPE_OSPF_P_SPACE,
927 sizeof(struct
928 protected_resource));
929 protected_resource->type =
930 protection_type;
931 protected_resource->link = l;
932
933 ospf_ti_lfa_generate_p_space(
934 area, child, protected_resource,
935 true, NULL);
936 }
937 }
938 }
939 }
940 }
941
942 static struct p_space *ospf_ti_lfa_get_p_space_by_path(struct ospf_area *area,
943 struct ospf_path *path)
944 {
945 struct p_space *p_space;
946 struct router_lsa_link *link;
947 struct vertex *child;
948 int type;
949
950 frr_each(p_spaces, area->p_spaces, p_space) {
951 type = p_space->protected_resource->type;
952
953 if (type == OSPF_TI_LFA_LINK_PROTECTION) {
954 link = p_space->protected_resource->link;
955 if ((path->nexthop.s_addr & link->link_data.s_addr)
956 == (link->link_id.s_addr & link->link_data.s_addr))
957 return p_space;
958 }
959
960 if (type == OSPF_TI_LFA_NODE_PROTECTION) {
961 child = ospf_spf_vertex_by_nexthop(area->spf,
962 &path->nexthop);
963 if (child
964 && p_space->protected_resource->router_id.s_addr
965 == child->id.s_addr)
966 return p_space;
967 }
968 }
969
970 return NULL;
971 }
972
973 void ospf_ti_lfa_insert_backup_paths(struct ospf_area *area,
974 struct route_table *new_table)
975 {
976 struct route_node *rn;
977 struct ospf_route *or;
978 struct ospf_path *path;
979 struct listnode *node;
980 struct p_space *p_space;
981 struct q_space *q_space, q_space_search;
982 struct vertex root_search;
983 char label_buf[MPLS_LABEL_STRLEN];
984
985 for (rn = route_top(new_table); rn; rn = route_next(rn)) {
986 or = rn->info;
987 if (or == NULL)
988 continue;
989
990 /* Insert a backup path for all OSPF paths */
991 for (ALL_LIST_ELEMENTS_RO(or->paths, node, path)) {
992
993 if (path->adv_router.s_addr == INADDR_ANY
994 || path->nexthop.s_addr == INADDR_ANY)
995 continue;
996
997 if (IS_DEBUG_OSPF_TI_LFA)
998 zlog_debug(
999 "%s: attempting to insert backup path for prefix %pFX, router id %pI4 and nexthop %pI4.",
1000 __func__, &rn->p, &path->adv_router,
1001 &path->nexthop);
1002
1003 p_space = ospf_ti_lfa_get_p_space_by_path(area, path);
1004 if (!p_space) {
1005 if (IS_DEBUG_OSPF_TI_LFA)
1006 zlog_debug(
1007 "%s: P space not found for router id %pI4 and nexthop %pI4.",
1008 __func__, &path->adv_router,
1009 &path->nexthop);
1010 continue;
1011 }
1012
1013 root_search.id = path->adv_router;
1014 q_space_search.root = &root_search;
1015 q_space = q_spaces_find(p_space->q_spaces,
1016 &q_space_search);
1017 if (!q_space) {
1018 if (IS_DEBUG_OSPF_TI_LFA)
1019 zlog_debug(
1020 "%s: Q space not found for advertising router %pI4.",
1021 __func__, &path->adv_router);
1022 continue;
1023 }
1024
1025 /* If there's a backup label stack, insert it*/
1026 if (q_space->label_stack) {
1027 /* Init the backup path data in path */
1028 path->srni.backup_label_stack = XCALLOC(
1029 MTYPE_OSPF_PATH,
1030 sizeof(struct mpls_label_stack)
1031 + sizeof(mpls_label_t)
1032 * q_space->label_stack
1033 ->num_labels);
1034
1035 /* Copy over the label stack */
1036 path->srni.backup_label_stack->num_labels =
1037 q_space->label_stack->num_labels;
1038 memcpy(path->srni.backup_label_stack->label,
1039 q_space->label_stack->label,
1040 sizeof(mpls_label_t)
1041 * q_space->label_stack
1042 ->num_labels);
1043
1044 /* Set the backup nexthop too */
1045 path->srni.backup_nexthop = q_space->nexthop;
1046 }
1047
1048 if (path->srni.backup_label_stack) {
1049 mpls_label2str(
1050 path->srni.backup_label_stack
1051 ->num_labels,
1052 path->srni.backup_label_stack->label,
1053 label_buf, MPLS_LABEL_STRLEN, true);
1054 if (IS_DEBUG_OSPF_TI_LFA)
1055 zlog_debug(
1056 "%s: inserted backup path %s for prefix %pFX, router id %pI4 and nexthop %pI4.",
1057 __func__, label_buf, &rn->p,
1058 &path->adv_router,
1059 &path->nexthop);
1060 } else {
1061 if (IS_DEBUG_OSPF_TI_LFA)
1062 zlog_debug(
1063 "%s: inserted NO backup path for prefix %pFX, router id %pI4 and nexthop %pI4.",
1064 __func__, &rn->p,
1065 &path->adv_router,
1066 &path->nexthop);
1067 }
1068 }
1069 }
1070 }
1071
1072 void ospf_ti_lfa_free_p_spaces(struct ospf_area *area)
1073 {
1074 struct p_space *p_space;
1075 struct q_space *q_space;
1076
1077 while ((p_space = p_spaces_pop(area->p_spaces))) {
1078 while ((q_space = q_spaces_pop(p_space->q_spaces))) {
1079 ospf_spf_cleanup(q_space->root, q_space->vertex_list);
1080
1081 if (q_space->pc_path)
1082 list_delete(&q_space->pc_path);
1083
1084 XFREE(MTYPE_OSPF_Q_SPACE, q_space->p_node_info);
1085 XFREE(MTYPE_OSPF_Q_SPACE, q_space->q_node_info);
1086 XFREE(MTYPE_OSPF_Q_SPACE, q_space->label_stack);
1087 XFREE(MTYPE_OSPF_Q_SPACE, q_space);
1088 }
1089
1090 ospf_spf_cleanup(p_space->root, p_space->vertex_list);
1091 ospf_spf_cleanup(p_space->pc_spf, p_space->pc_vertex_list);
1092 XFREE(MTYPE_OSPF_P_SPACE, p_space->protected_resource);
1093
1094 q_spaces_fini(p_space->q_spaces);
1095 XFREE(MTYPE_OSPF_Q_SPACE, p_space->q_spaces);
1096 }
1097
1098 p_spaces_fini(area->p_spaces);
1099 XFREE(MTYPE_OSPF_P_SPACE, area->p_spaces);
1100 }
1101
1102 void ospf_ti_lfa_compute(struct ospf_area *area, struct route_table *new_table,
1103 enum protection_type protection_type)
1104 {
1105 /*
1106 * Generate P spaces per protected link/node and their respective Q
1107 * spaces, generate backup paths (MPLS label stacks) by finding P/Q
1108 * nodes.
1109 */
1110 ospf_ti_lfa_generate_p_spaces(area, protection_type);
1111
1112 /* Insert the generated backup paths into the routing table. */
1113 ospf_ti_lfa_insert_backup_paths(area, new_table);
1114
1115 /* Cleanup P spaces and related datastructures including Q spaces. */
1116 ospf_ti_lfa_free_p_spaces(area);
1117 }
FRRouting mirror