Line data Source code
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 0 : DECLARE_RBTREE_UNIQ(p_spaces, struct p_space, p_spaces_item,
40 : p_spaces_compare_func);
41 0 : 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 0 : void ospf_print_protected_resource(
50 : struct protected_resource *protected_resource, char *buf)
51 : {
52 0 : struct router_lsa_link *link;
53 :
54 0 : switch (protected_resource->type) {
55 0 : case OSPF_TI_LFA_LINK_PROTECTION:
56 0 : link = protected_resource->link;
57 0 : snprintfrr(buf, PROTECTED_RESOURCE_STRLEN,
58 : "protected link: %pI4 %pI4", &link->link_id,
59 : &link->link_data);
60 0 : break;
61 0 : case OSPF_TI_LFA_NODE_PROTECTION:
62 0 : snprintfrr(buf, PROTECTED_RESOURCE_STRLEN,
63 : "protected node: %pI4",
64 : &protected_resource->router_id);
65 0 : break;
66 0 : case OSPF_TI_LFA_UNDEFINED_PROTECTION:
67 0 : snprintfrr(buf, PROTECTED_RESOURCE_STRLEN,
68 : "undefined protected resource");
69 0 : break;
70 : }
71 0 : }
72 :
73 : static enum ospf_ti_lfa_p_q_space_adjacency
74 0 : ospf_ti_lfa_find_p_node(struct vertex *pc_node, struct p_space *p_space,
75 : struct q_space *q_space)
76 : {
77 0 : struct listnode *curr_node;
78 0 : struct vertex *p_node = NULL, *pc_node_parent, *p_node_pc_parent;
79 0 : struct vertex_parent *pc_vertex_parent;
80 :
81 0 : curr_node = listnode_lookup(q_space->pc_path, pc_node);
82 0 : pc_node_parent = listgetdata(curr_node->next);
83 :
84 0 : q_space->p_node_info->type = OSPF_TI_LFA_UNDEFINED_NODE;
85 :
86 0 : p_node = ospf_spf_vertex_find(pc_node_parent->id, p_space->vertex_list);
87 :
88 0 : if (p_node) {
89 0 : q_space->p_node_info->node = p_node;
90 0 : q_space->p_node_info->type = OSPF_TI_LFA_P_NODE;
91 :
92 0 : if (curr_node->next->next) {
93 0 : p_node_pc_parent = listgetdata(curr_node->next->next);
94 0 : pc_vertex_parent = ospf_spf_vertex_parent_find(
95 : p_node_pc_parent->id, pc_node_parent);
96 0 : q_space->p_node_info->nexthop =
97 0 : 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 0 : q_space->p_node_info->nexthop.s_addr = INADDR_ANY;
105 : }
106 :
107 0 : return OSPF_TI_LFA_P_Q_SPACE_ADJACENT;
108 : }
109 :
110 0 : ospf_ti_lfa_find_p_node(pc_node_parent, p_space, q_space);
111 0 : return OSPF_TI_LFA_P_Q_SPACE_NON_ADJACENT;
112 : }
113 :
114 0 : 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 0 : struct listnode *curr_node, *next_node;
119 0 : struct vertex *p_node, *q_node, *q_space_parent = NULL, *pc_node_parent;
120 0 : struct vertex_parent *pc_vertex_parent;
121 :
122 0 : curr_node = listnode_lookup(q_space->pc_path, pc_node);
123 0 : next_node = curr_node->next;
124 0 : pc_node_parent = listgetdata(next_node);
125 0 : pc_vertex_parent =
126 0 : ospf_spf_vertex_parent_find(pc_node_parent->id, pc_node);
127 :
128 0 : p_node = ospf_spf_vertex_find(pc_node->id, p_space->vertex_list);
129 0 : q_node = ospf_spf_vertex_find(pc_node->id, q_space->vertex_list);
130 :
131 : /* The Q node is always present. */
132 0 : assert(q_node);
133 :
134 0 : q_space->q_node_info->type = OSPF_TI_LFA_UNDEFINED_NODE;
135 :
136 0 : if (p_node && q_node) {
137 0 : q_space->q_node_info->node = pc_node;
138 0 : q_space->q_node_info->type = OSPF_TI_LFA_PQ_NODE;
139 0 : q_space->q_node_info->nexthop =
140 0 : pc_vertex_parent->nexthop->router;
141 0 : 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 0 : q_space_parent =
149 0 : 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 0 : if (!q_space_parent) {
156 0 : q_space->q_node_info->node = pc_node;
157 0 : q_space->q_node_info->type = OSPF_TI_LFA_Q_NODE;
158 0 : q_space->q_node_info->nexthop =
159 0 : pc_vertex_parent->nexthop->router;
160 0 : return;
161 : }
162 :
163 : return ospf_ti_lfa_find_q_node(pc_node_parent, p_space, q_space);
164 : }
165 :
166 0 : 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 0 : int i, offset, limit;
171 :
172 0 : limit = label_stack->num_labels + num_labels;
173 0 : offset = label_stack->num_labels;
174 :
175 0 : for (i = label_stack->num_labels; i < limit; i++) {
176 0 : label_stack->label[i] = labels[i - offset];
177 0 : label_stack->num_labels++;
178 : }
179 0 : }
180 :
181 :
182 : static struct mpls_label_stack *
183 0 : ospf_ti_lfa_create_label_stack(mpls_label_t labels[], uint32_t num_labels)
184 : {
185 0 : struct mpls_label_stack *label_stack;
186 0 : uint32_t i;
187 :
188 : /* Sanity check */
189 0 : for (i = 0; i < num_labels; i++) {
190 0 : if (labels[i] == MPLS_INVALID_LABEL)
191 : return NULL;
192 : }
193 :
194 0 : label_stack = XCALLOC(MTYPE_OSPF_Q_SPACE,
195 : sizeof(struct mpls_label_stack)
196 : + MPLS_MAX_LABELS * sizeof(mpls_label_t));
197 0 : label_stack->num_labels = num_labels;
198 :
199 0 : for (i = 0; i < num_labels; i++)
200 0 : label_stack->label[i] = labels[i];
201 :
202 : return label_stack;
203 : }
204 :
205 : static struct list *
206 0 : ospf_ti_lfa_map_path_to_pc_vertices(struct list *path,
207 : struct list *pc_vertex_list)
208 : {
209 0 : struct listnode *node;
210 0 : struct vertex *vertex, *pc_vertex;
211 0 : struct list *pc_path;
212 :
213 0 : pc_path = list_new();
214 :
215 0 : for (ALL_LIST_ELEMENTS_RO(path, node, vertex)) {
216 0 : pc_vertex = ospf_spf_vertex_find(vertex->id, pc_vertex_list);
217 0 : listnode_add(pc_path, pc_vertex);
218 : }
219 :
220 0 : return pc_path;
221 : }
222 :
223 0 : 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 0 : struct list *inner_pc_path;
229 0 : struct vertex *current_vertex;
230 0 : struct listnode *current_listnode;
231 :
232 0 : inner_pc_path = list_new();
233 0 : current_vertex = ospf_spf_vertex_find(q_node->id, pc_vertex_list);
234 0 : current_listnode = listnode_lookup(pc_path, current_vertex);
235 :
236 : /* Note that the post-convergence paths are reversed. */
237 0 : for (;;) {
238 0 : current_vertex = listgetdata(current_listnode);
239 0 : listnode_add(inner_pc_path, current_vertex);
240 :
241 0 : if (current_vertex->id.s_addr == p_node->id.s_addr)
242 : break;
243 :
244 0 : current_listnode = current_listnode->next;
245 : }
246 :
247 0 : return inner_pc_path;
248 : }
249 :
250 0 : 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 0 : struct route_table *new_table, *new_rtrs;
256 0 : struct vertex *q_node;
257 0 : struct vertex *start_vertex, *end_vertex;
258 0 : struct vertex_parent *vertex_parent;
259 0 : struct listnode *pc_p_node, *pc_q_node;
260 0 : struct vertex *spf_orig;
261 0 : struct list *vertex_list_orig;
262 0 : struct p_spaces_head *p_spaces_orig;
263 0 : struct p_space *inner_p_space;
264 0 : struct q_space *inner_q_space;
265 0 : struct ospf_ti_lfa_node_info *p_node_info, *q_node_info;
266 0 : struct protected_resource *protected_resource;
267 0 : struct list *inner_pc_path;
268 0 : mpls_label_t start_label, end_label;
269 :
270 0 : p_node_info = q_space->p_node_info;
271 0 : q_node_info = q_space->q_node_info;
272 0 : protected_resource = p_space->protected_resource;
273 :
274 0 : start_vertex = p_node_info->node;
275 0 : 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 0 : start_label = MPLS_INVALID_LABEL;
283 0 : end_label = MPLS_INVALID_LABEL;
284 0 : if (p_node_info->node->id.s_addr == p_space->root->id.s_addr) {
285 0 : pc_p_node = listnode_lookup(q_space->pc_path, p_space->pc_spf);
286 0 : start_vertex = listgetdata(pc_p_node->prev);
287 0 : start_label = ospf_sr_get_adj_sid_by_id(&p_node_info->node->id,
288 : &start_vertex->id);
289 : }
290 0 : if (q_node_info->node->id.s_addr == q_space->root->id.s_addr) {
291 0 : pc_q_node = listnode_lookup(q_space->pc_path,
292 0 : listnode_head(q_space->pc_path));
293 0 : end_vertex = listgetdata(pc_q_node->next);
294 0 : end_label = ospf_sr_get_adj_sid_by_id(&end_vertex->id,
295 0 : &q_node_info->node->id);
296 : }
297 :
298 : /* Corner case: inner path is just one node */
299 0 : if (start_vertex->id.s_addr == end_vertex->id.s_addr) {
300 0 : inner_backup_path_info->label_stack =
301 0 : ospf_ti_lfa_create_label_stack(&start_label, 1);
302 0 : inner_backup_path_info->q_node_info.node = end_vertex;
303 0 : inner_backup_path_info->q_node_info.type = OSPF_TI_LFA_PQ_NODE;
304 0 : inner_backup_path_info->p_node_info.type =
305 : OSPF_TI_LFA_UNDEFINED_NODE;
306 0 : vertex_parent = ospf_spf_vertex_parent_find(p_space->root->id,
307 : end_vertex);
308 0 : inner_backup_path_info->p_node_info.nexthop =
309 0 : vertex_parent->nexthop->router;
310 0 : return;
311 : }
312 :
313 0 : 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 0 : new_table = route_table_init();
318 0 : new_rtrs = route_table_init();
319 :
320 : /* Copy the current state ... */
321 0 : spf_orig = area->spf;
322 0 : vertex_list_orig = area->spf_vertex_list;
323 0 : p_spaces_orig = area->p_spaces;
324 :
325 0 : area->p_spaces =
326 0 : XCALLOC(MTYPE_OSPF_P_SPACE, sizeof(struct p_spaces_head));
327 :
328 : /* dry run true, root node false */
329 0 : ospf_spf_calculate(area, start_vertex->lsa_p, new_table, NULL, new_rtrs,
330 : true, false);
331 :
332 0 : q_node = ospf_spf_vertex_find(end_vertex->id, area->spf_vertex_list);
333 :
334 0 : 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 0 : inner_p_space = p_spaces_pop(area->p_spaces);
339 0 : 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 0 : if (start_label != MPLS_INVALID_LABEL) {
345 0 : inner_backup_path_info->label_stack =
346 0 : ospf_ti_lfa_create_label_stack(&start_label, 1);
347 0 : ospf_ti_lfa_append_label_stack(
348 : inner_backup_path_info->label_stack,
349 0 : inner_q_space->label_stack->label,
350 0 : inner_q_space->label_stack->num_labels);
351 0 : inner_backup_path_info->p_node_info.node = start_vertex;
352 0 : inner_backup_path_info->p_node_info.type = OSPF_TI_LFA_P_NODE;
353 0 : vertex_parent = ospf_spf_vertex_parent_find(p_space->root->id,
354 : start_vertex);
355 0 : inner_backup_path_info->p_node_info.nexthop =
356 0 : vertex_parent->nexthop->router;
357 : } else {
358 0 : memcpy(inner_backup_path_info->label_stack,
359 : inner_q_space->label_stack,
360 : sizeof(struct mpls_label_stack)
361 0 : + sizeof(mpls_label_t)
362 0 : * inner_q_space->label_stack
363 0 : ->num_labels);
364 0 : memcpy(&inner_backup_path_info->p_node_info,
365 0 : 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 0 : if (end_label != MPLS_INVALID_LABEL) {
371 0 : inner_backup_path_info->q_node_info.node = end_vertex;
372 0 : inner_backup_path_info->q_node_info.type = OSPF_TI_LFA_Q_NODE;
373 : } else {
374 0 : memcpy(&inner_backup_path_info->q_node_info,
375 0 : inner_q_space->q_node_info,
376 : sizeof(struct ospf_ti_lfa_node_info));
377 : }
378 :
379 : /* Cleanup */
380 0 : ospf_ti_lfa_free_p_spaces(area);
381 0 : ospf_spf_cleanup(area->spf, area->spf_vertex_list);
382 :
383 : /* ... and copy the current state back. */
384 0 : area->spf = spf_orig;
385 0 : area->spf_vertex_list = vertex_list_orig;
386 0 : area->p_spaces = p_spaces_orig;
387 : }
388 :
389 0 : 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 0 : enum ospf_ti_lfa_p_q_space_adjacency adjacency_result;
394 0 : mpls_label_t labels[MPLS_MAX_LABELS];
395 0 : struct vertex *pc_node;
396 0 : struct ospf_ti_lfa_inner_backup_path_info inner_backup_path_info;
397 :
398 0 : if (IS_DEBUG_OSPF_TI_LFA)
399 0 : 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 0 : pc_node = listnode_head(q_space->pc_path);
404 :
405 0 : if (!pc_node) {
406 0 : if (IS_DEBUG_OSPF_TI_LFA)
407 0 : zlog_debug(
408 : "%s: There seems to be no post convergence path (yet).",
409 : __func__);
410 0 : return;
411 : }
412 :
413 0 : ospf_ti_lfa_find_q_node(pc_node, p_space, q_space);
414 0 : if (q_space->q_node_info->type == OSPF_TI_LFA_UNDEFINED_NODE) {
415 0 : if (IS_DEBUG_OSPF_TI_LFA)
416 0 : zlog_debug("%s: Q node not found!", __func__);
417 0 : return;
418 : }
419 :
420 : /* Found a PQ node? Then we are done here. */
421 0 : 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 0 : if (ospf_spf_vertex_parent_find(p_space->root->id,
427 : q_space->q_node_info->node))
428 0 : labels[0] = ospf_sr_get_adj_sid_by_id(
429 0 : &p_space->root->id,
430 0 : &q_space->q_node_info->node->id);
431 : else
432 0 : labels[0] = ospf_sr_get_prefix_sid_by_id(
433 0 : &q_space->q_node_info->node->id);
434 :
435 0 : q_space->label_stack =
436 0 : ospf_ti_lfa_create_label_stack(labels, 1);
437 0 : q_space->nexthop = q_space->q_node_info->nexthop;
438 :
439 0 : return;
440 : }
441 :
442 : /* Otherwise find a (hopefully adjacent) P node. */
443 0 : pc_node = ospf_spf_vertex_find(q_space->q_node_info->node->id,
444 : p_space->pc_vertex_list);
445 0 : adjacency_result = ospf_ti_lfa_find_p_node(pc_node, p_space, q_space);
446 :
447 0 : if (q_space->p_node_info->type == OSPF_TI_LFA_UNDEFINED_NODE) {
448 0 : if (IS_DEBUG_OSPF_TI_LFA)
449 0 : zlog_debug("%s: P node not found!", __func__);
450 0 : 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 0 : 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 0 : if (q_space->p_node_info->node->id.s_addr
465 0 : == p_space->root->id.s_addr) {
466 0 : labels[0] = ospf_sr_get_adj_sid_by_id(
467 : &p_space->root->id,
468 0 : &q_space->q_node_info->node->id);
469 0 : q_space->label_stack =
470 0 : ospf_ti_lfa_create_label_stack(labels, 1);
471 0 : q_space->nexthop = q_space->q_node_info->nexthop;
472 0 : 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 0 : if (ospf_spf_vertex_parent_find(p_space->root->id,
484 : q_space->p_node_info->node))
485 0 : labels[0] = ospf_sr_get_adj_sid_by_id(
486 0 : &p_space->root->id,
487 0 : &q_space->p_node_info->node->id);
488 : else
489 0 : labels[0] = ospf_sr_get_prefix_sid_by_id(
490 0 : &q_space->p_node_info->node->id);
491 :
492 0 : labels[1] = ospf_sr_get_adj_sid_by_id(
493 0 : &q_space->p_node_info->node->id,
494 0 : &q_space->q_node_info->node->id);
495 :
496 0 : q_space->label_stack =
497 0 : ospf_ti_lfa_create_label_stack(labels, 2);
498 0 : 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 0 : 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 0 : 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 0 : if (q_space->p_node_info->node->id.s_addr
522 0 : == 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 0 : q_space->label_stack = ospf_ti_lfa_create_label_stack(
529 0 : inner_backup_path_info.label_stack->label,
530 0 : inner_backup_path_info.label_stack->num_labels);
531 :
532 : /* Use the inner P or Q node for the nexthop */
533 0 : if (inner_backup_path_info.p_node_info.type
534 : != OSPF_TI_LFA_UNDEFINED_NODE)
535 0 : q_space->nexthop = inner_backup_path_info
536 : .p_node_info.nexthop;
537 : else
538 0 : q_space->nexthop = inner_backup_path_info
539 : .q_node_info.nexthop;
540 :
541 0 : } 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 0 : labels[0] = ospf_sr_get_adj_sid_by_id(
551 0 : &p_space->root->id,
552 0 : &q_space->p_node_info->node->id);
553 0 : q_space->label_stack =
554 0 : ospf_ti_lfa_create_label_stack(labels, 1);
555 0 : ospf_ti_lfa_append_label_stack(
556 : q_space->label_stack,
557 0 : inner_backup_path_info.label_stack->label,
558 0 : inner_backup_path_info.label_stack->num_labels);
559 0 : q_space->nexthop = q_space->p_node_info->nexthop;
560 : } else {
561 : /* The outer P node needs a Prefix-SID here */
562 0 : labels[0] = ospf_sr_get_prefix_sid_by_id(
563 0 : &q_space->p_node_info->node->id);
564 0 : q_space->label_stack =
565 0 : ospf_ti_lfa_create_label_stack(labels, 1);
566 0 : ospf_ti_lfa_append_label_stack(
567 : q_space->label_stack,
568 0 : inner_backup_path_info.label_stack->label,
569 0 : inner_backup_path_info.label_stack->num_labels);
570 0 : q_space->nexthop = q_space->p_node_info->nexthop;
571 : }
572 :
573 : /* Now the outer Q node needs to be considered */
574 0 : if (ospf_spf_vertex_parent_find(
575 0 : inner_backup_path_info.q_node_info.node->id,
576 0 : 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 0 : labels[0] = ospf_sr_get_adj_sid_by_id(
582 : &inner_backup_path_info.q_node_info.node->id,
583 0 : &q_space->q_node_info->node->id);
584 0 : ospf_ti_lfa_append_label_stack(q_space->label_stack,
585 : labels, 1);
586 : } else {
587 : /* Otherwise a Prefix-SID is needed */
588 0 : labels[0] = ospf_sr_get_prefix_sid_by_id(
589 0 : &q_space->q_node_info->node->id);
590 0 : 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 0 : ospf_ti_lfa_generate_post_convergence_path(struct list *pc_vertex_list,
602 : struct vertex *dest)
603 : {
604 0 : struct list *pc_path;
605 0 : struct vertex *current_vertex;
606 0 : struct vertex_parent *parent;
607 :
608 0 : current_vertex = ospf_spf_vertex_find(dest->id, pc_vertex_list);
609 0 : if (!current_vertex) {
610 0 : if (IS_DEBUG_OSPF_TI_LFA)
611 0 : zlog_debug(
612 : "%s: There seems to be no post convergence path (yet).",
613 : __func__);
614 0 : return NULL;
615 : }
616 :
617 0 : pc_path = list_new();
618 0 : listnode_add(pc_path, current_vertex);
619 :
620 : /* Generate a backup path in reverse order */
621 0 : for (;;) {
622 0 : parent = listnode_head(current_vertex->parents);
623 0 : if (!parent)
624 : break;
625 :
626 0 : listnode_add(pc_path, parent->parent);
627 0 : current_vertex = parent->parent;
628 : }
629 :
630 : return pc_path;
631 : }
632 :
633 0 : 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 0 : struct listnode *node;
639 0 : struct vertex *child;
640 0 : struct route_table *new_table, *new_rtrs;
641 0 : struct q_space *q_space, q_space_search;
642 0 : char label_buf[MPLS_LABEL_STRLEN];
643 0 : char res_buf[PROTECTED_RESOURCE_STRLEN];
644 0 : bool node_protected;
645 :
646 0 : ospf_print_protected_resource(p_space->protected_resource, res_buf);
647 0 : node_protected =
648 0 : p_space->protected_resource->type == OSPF_TI_LFA_NODE_PROTECTION
649 0 : && dest->id.s_addr
650 0 : == 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 0 : if (node_protected) {
657 0 : if (recursive) {
658 : /* Recursively generate Q spaces for all children */
659 0 : for (ALL_LIST_ELEMENTS_RO(dest->children, node, child))
660 0 : ospf_ti_lfa_generate_q_spaces(area, p_space,
661 : child, recursive,
662 : pc_path);
663 : }
664 0 : return;
665 : }
666 :
667 : /* Check if we already have a Q space for this destination */
668 0 : q_space_search.root = dest;
669 0 : if (q_spaces_find(p_space->q_spaces, &q_space_search))
670 : return;
671 :
672 0 : q_space = XCALLOC(MTYPE_OSPF_Q_SPACE, sizeof(struct q_space));
673 0 : q_space->p_node_info = XCALLOC(MTYPE_OSPF_Q_SPACE,
674 : sizeof(struct ospf_ti_lfa_node_info));
675 0 : q_space->q_node_info = XCALLOC(MTYPE_OSPF_Q_SPACE,
676 : sizeof(struct ospf_ti_lfa_node_info));
677 :
678 0 : new_table = route_table_init();
679 : /* XXX do these get freed?? */
680 0 : 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 0 : area->spf_reversed = true;
687 0 : ospf_spf_calculate(area, dest->lsa_p, new_table, NULL, new_rtrs, true,
688 : false);
689 :
690 : /* Reset the flag for reverse SPF */
691 0 : area->spf_reversed = false;
692 :
693 0 : q_space->root = area->spf;
694 0 : q_space->vertex_list = area->spf_vertex_list;
695 0 : q_space->label_stack = NULL;
696 :
697 0 : if (pc_path)
698 0 : q_space->pc_path = ospf_ti_lfa_map_path_to_pc_vertices(
699 : pc_path, p_space->pc_vertex_list);
700 : else
701 0 : 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 0 : if (!q_space->pc_path) {
706 0 : 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 0 : return;
711 : }
712 :
713 : /* 'Cut' the protected resource out of the new SPF tree */
714 0 : 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 0 : ospf_ti_lfa_generate_label_stack(area, p_space, q_space);
722 :
723 0 : if (q_space->label_stack) {
724 0 : mpls_label2str(q_space->label_stack->num_labels,
725 0 : q_space->label_stack->label, label_buf,
726 : MPLS_LABEL_STRLEN, true);
727 0 : 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 0 : 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 0 : q_spaces_add(p_space->q_spaces, q_space);
740 :
741 : /* Recursively generate Q spaces for all children */
742 0 : if (recursive) {
743 0 : for (ALL_LIST_ELEMENTS_RO(dest->children, node, child))
744 0 : ospf_ti_lfa_generate_q_spaces(area, p_space, child,
745 : recursive, pc_path);
746 : }
747 : }
748 :
749 0 : static void ospf_ti_lfa_generate_post_convergence_spf(struct ospf_area *area,
750 : struct p_space *p_space)
751 : {
752 0 : struct route_table *new_table, *new_rtrs;
753 :
754 0 : new_table = route_table_init();
755 : /* XXX do these get freed?? */
756 0 : new_rtrs = route_table_init();
757 :
758 0 : 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 0 : ospf_spf_calculate(area, area->router_lsa_self, new_table, NULL,
776 : new_rtrs, true, false);
777 :
778 0 : p_space->pc_spf = area->spf;
779 0 : p_space->pc_vertex_list = area->spf_vertex_list;
780 :
781 0 : area->spf_protected_resource = NULL;
782 0 : }
783 :
784 : static void
785 0 : 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 0 : struct vertex *spf_orig;
790 0 : struct list *vertex_list, *vertex_list_orig;
791 0 : struct p_space *p_space;
792 :
793 0 : p_space = XCALLOC(MTYPE_OSPF_P_SPACE, sizeof(struct p_space));
794 0 : vertex_list = list_new();
795 :
796 : /* The P-space will get its own SPF tree, so copy the old one */
797 0 : ospf_spf_copy(area->spf, vertex_list);
798 0 : p_space->root = listnode_head(vertex_list);
799 0 : p_space->vertex_list = vertex_list;
800 0 : p_space->protected_resource = protected_resource;
801 :
802 : /* Initialize the Q spaces for this P space and protected resource */
803 0 : p_space->q_spaces =
804 0 : XCALLOC(MTYPE_OSPF_Q_SPACE, sizeof(struct q_spaces_head));
805 0 : q_spaces_init(p_space->q_spaces);
806 :
807 : /* 'Cut' the protected resource out of the new SPF tree */
808 0 : 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 0 : spf_orig = area->spf;
816 0 : vertex_list_orig = area->spf_vertex_list;
817 :
818 : /* Generate the post convergence SPF as a blueprint for backup paths */
819 0 : ospf_ti_lfa_generate_post_convergence_spf(area, p_space);
820 :
821 : /* Generate the relevant Q spaces for this particular P space */
822 0 : ospf_ti_lfa_generate_q_spaces(area, p_space, child, recursive, pc_path);
823 :
824 : /* Put the 'original' SPF tree back in place */
825 0 : area->spf = spf_orig;
826 0 : area->spf_vertex_list = vertex_list_orig;
827 :
828 : /* We are finished, store the new P space */
829 0 : p_spaces_add(area->p_spaces, p_space);
830 0 : }
831 :
832 0 : void ospf_ti_lfa_generate_p_spaces(struct ospf_area *area,
833 : enum protection_type protection_type)
834 : {
835 0 : struct listnode *node, *inner_node;
836 0 : struct vertex *root, *child;
837 0 : struct vertex_parent *vertex_parent;
838 0 : uint8_t *p, *lim;
839 0 : struct router_lsa_link *l = NULL;
840 0 : struct prefix stub_prefix, child_prefix;
841 0 : struct protected_resource *protected_resource;
842 :
843 0 : area->p_spaces =
844 0 : XCALLOC(MTYPE_OSPF_P_SPACE, sizeof(struct p_spaces_head));
845 0 : p_spaces_init(area->p_spaces);
846 :
847 0 : root = area->spf;
848 :
849 : /* Root or its router LSA was not created yet? */
850 0 : if (!root || !root->lsa)
851 0 : return;
852 :
853 0 : stub_prefix.family = AF_INET;
854 0 : child_prefix.family = AF_INET;
855 0 : child_prefix.prefixlen = IPV4_MAX_BITLEN;
856 :
857 0 : p = ((uint8_t *)root->lsa) + OSPF_LSA_HEADER_SIZE + 4;
858 0 : lim = ((uint8_t *)root->lsa) + ntohs(root->lsa->length);
859 :
860 0 : 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 0 : while (p < lim) {
868 0 : l = (struct router_lsa_link *)p;
869 0 : p += (OSPF_ROUTER_LSA_LINK_SIZE
870 0 : + (l->m[0].tos_count * OSPF_ROUTER_LSA_TOS_SIZE));
871 :
872 : /* First comes node protection */
873 0 : if (protection_type == OSPF_TI_LFA_NODE_PROTECTION) {
874 0 : if (l->m[0].type == LSA_LINK_TYPE_POINTOPOINT) {
875 0 : protected_resource = XCALLOC(
876 : MTYPE_OSPF_P_SPACE,
877 : sizeof(struct protected_resource));
878 0 : protected_resource->type = protection_type;
879 0 : protected_resource->router_id = l->link_id;
880 0 : child = ospf_spf_vertex_find(
881 : protected_resource->router_id,
882 : root->children);
883 0 : if (child)
884 0 : ospf_ti_lfa_generate_p_space(
885 : area, child, protected_resource,
886 : true, NULL);
887 : }
888 :
889 0 : continue;
890 : }
891 :
892 : /* The rest is about link protection */
893 0 : if (protection_type != OSPF_TI_LFA_LINK_PROTECTION)
894 0 : continue;
895 :
896 0 : if (l->m[0].type != LSA_LINK_TYPE_STUB)
897 0 : continue;
898 :
899 0 : stub_prefix.prefixlen = ip_masklen(l->link_data);
900 0 : stub_prefix.u.prefix4 = l->link_id;
901 :
902 0 : for (ALL_LIST_ELEMENTS_RO(root->children, node, child)) {
903 :
904 0 : if (child->type != OSPF_VERTEX_ROUTER)
905 0 : continue;
906 :
907 0 : for (ALL_LIST_ELEMENTS_RO(child->parents, inner_node,
908 : vertex_parent)) {
909 :
910 0 : child_prefix.u.prefix4 =
911 0 : 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 0 : if (prefix_match(&stub_prefix, &child_prefix)) {
921 0 : zlog_info(
922 : "%s: Generating P space for %pI4",
923 : __func__, &l->link_id);
924 :
925 0 : protected_resource = XCALLOC(
926 : MTYPE_OSPF_P_SPACE,
927 : sizeof(struct
928 : protected_resource));
929 0 : protected_resource->type =
930 : protection_type;
931 0 : protected_resource->link = l;
932 :
933 0 : ospf_ti_lfa_generate_p_space(
934 : area, child, protected_resource,
935 : true, NULL);
936 : }
937 : }
938 : }
939 : }
940 : }
941 :
942 0 : static struct p_space *ospf_ti_lfa_get_p_space_by_path(struct ospf_area *area,
943 : struct ospf_path *path)
944 : {
945 0 : struct p_space *p_space;
946 0 : struct router_lsa_link *link;
947 0 : struct vertex *child;
948 0 : int type;
949 :
950 0 : frr_each(p_spaces, area->p_spaces, p_space) {
951 0 : type = p_space->protected_resource->type;
952 :
953 0 : if (type == OSPF_TI_LFA_LINK_PROTECTION) {
954 0 : link = p_space->protected_resource->link;
955 0 : if ((path->nexthop.s_addr & link->link_data.s_addr)
956 0 : == (link->link_id.s_addr & link->link_data.s_addr))
957 0 : return p_space;
958 : }
959 :
960 0 : if (type == OSPF_TI_LFA_NODE_PROTECTION) {
961 0 : child = ospf_spf_vertex_by_nexthop(area->spf,
962 : &path->nexthop);
963 0 : if (child
964 0 : && p_space->protected_resource->router_id.s_addr
965 0 : == child->id.s_addr)
966 0 : return p_space;
967 : }
968 : }
969 :
970 : return NULL;
971 : }
972 :
973 0 : void ospf_ti_lfa_insert_backup_paths(struct ospf_area *area,
974 : struct route_table *new_table)
975 : {
976 0 : struct route_node *rn;
977 0 : struct ospf_route *or;
978 0 : struct ospf_path *path;
979 0 : struct listnode *node;
980 0 : struct p_space *p_space;
981 0 : struct q_space *q_space, q_space_search;
982 0 : struct vertex root_search;
983 0 : char label_buf[MPLS_LABEL_STRLEN];
984 :
985 0 : for (rn = route_top(new_table); rn; rn = route_next(rn)) {
986 0 : or = rn->info;
987 0 : if (or == NULL)
988 0 : continue;
989 :
990 : /* Insert a backup path for all OSPF paths */
991 0 : for (ALL_LIST_ELEMENTS_RO(or->paths, node, path)) {
992 :
993 0 : if (path->adv_router.s_addr == INADDR_ANY
994 0 : || path->nexthop.s_addr == INADDR_ANY)
995 0 : continue;
996 :
997 0 : if (IS_DEBUG_OSPF_TI_LFA)
998 0 : 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 0 : p_space = ospf_ti_lfa_get_p_space_by_path(area, path);
1004 0 : if (!p_space) {
1005 0 : if (IS_DEBUG_OSPF_TI_LFA)
1006 0 : zlog_debug(
1007 : "%s: P space not found for router id %pI4 and nexthop %pI4.",
1008 : __func__, &path->adv_router,
1009 : &path->nexthop);
1010 0 : continue;
1011 : }
1012 :
1013 0 : root_search.id = path->adv_router;
1014 0 : q_space_search.root = &root_search;
1015 0 : q_space = q_spaces_find(p_space->q_spaces,
1016 : &q_space_search);
1017 0 : if (!q_space) {
1018 0 : if (IS_DEBUG_OSPF_TI_LFA)
1019 0 : zlog_debug(
1020 : "%s: Q space not found for advertising router %pI4.",
1021 : __func__, &path->adv_router);
1022 0 : continue;
1023 : }
1024 :
1025 : /* If there's a backup label stack, insert it*/
1026 0 : if (q_space->label_stack) {
1027 : /* Init the backup path data in path */
1028 0 : 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 0 : path->srni.backup_label_stack->num_labels =
1037 0 : q_space->label_stack->num_labels;
1038 0 : memcpy(path->srni.backup_label_stack->label,
1039 0 : q_space->label_stack->label,
1040 : sizeof(mpls_label_t)
1041 : * q_space->label_stack
1042 0 : ->num_labels);
1043 :
1044 : /* Set the backup nexthop too */
1045 0 : path->srni.backup_nexthop = q_space->nexthop;
1046 : }
1047 :
1048 0 : if (path->srni.backup_label_stack) {
1049 0 : mpls_label2str(
1050 : path->srni.backup_label_stack
1051 0 : ->num_labels,
1052 0 : path->srni.backup_label_stack->label,
1053 : label_buf, MPLS_LABEL_STRLEN, true);
1054 0 : if (IS_DEBUG_OSPF_TI_LFA)
1055 0 : 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 0 : if (IS_DEBUG_OSPF_TI_LFA)
1062 0 : 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 0 : }
1071 :
1072 0 : void ospf_ti_lfa_free_p_spaces(struct ospf_area *area)
1073 : {
1074 0 : struct p_space *p_space;
1075 0 : struct q_space *q_space;
1076 :
1077 0 : while ((p_space = p_spaces_pop(area->p_spaces))) {
1078 0 : while ((q_space = q_spaces_pop(p_space->q_spaces))) {
1079 0 : ospf_spf_cleanup(q_space->root, q_space->vertex_list);
1080 :
1081 0 : if (q_space->pc_path)
1082 0 : list_delete(&q_space->pc_path);
1083 :
1084 0 : XFREE(MTYPE_OSPF_Q_SPACE, q_space->p_node_info);
1085 0 : XFREE(MTYPE_OSPF_Q_SPACE, q_space->q_node_info);
1086 0 : XFREE(MTYPE_OSPF_Q_SPACE, q_space->label_stack);
1087 0 : XFREE(MTYPE_OSPF_Q_SPACE, q_space);
1088 : }
1089 :
1090 0 : ospf_spf_cleanup(p_space->root, p_space->vertex_list);
1091 0 : ospf_spf_cleanup(p_space->pc_spf, p_space->pc_vertex_list);
1092 0 : XFREE(MTYPE_OSPF_P_SPACE, p_space->protected_resource);
1093 :
1094 0 : q_spaces_fini(p_space->q_spaces);
1095 0 : XFREE(MTYPE_OSPF_Q_SPACE, p_space->q_spaces);
1096 : }
1097 :
1098 0 : p_spaces_fini(area->p_spaces);
1099 0 : XFREE(MTYPE_OSPF_P_SPACE, area->p_spaces);
1100 0 : }
1101 :
1102 0 : 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 0 : ospf_ti_lfa_generate_p_spaces(area, protection_type);
1111 :
1112 : /* Insert the generated backup paths into the routing table. */
1113 0 : ospf_ti_lfa_insert_backup_paths(area, new_table);
1114 :
1115 : /* Cleanup P spaces and related datastructures including Q spaces. */
1116 0 : ospf_ti_lfa_free_p_spaces(area);
1117 0 : }
|
