]>
Commit | Line | Data |
---|---|---|
7fd0729f G |
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" | |
385a1e07 | 27 | #include "printfrr.h" |
7fd0729f G |
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" | |
a4553b5b | 36 | #include "ospfd/ospf_dump.h" |
7fd0729f G |
37 | |
38 | ||
39 | DECLARE_RBTREE_UNIQ(p_spaces, struct p_space, p_spaces_item, | |
960b9a53 | 40 | p_spaces_compare_func); |
7fd0729f | 41 | DECLARE_RBTREE_UNIQ(q_spaces, struct q_space, q_spaces_item, |
960b9a53 | 42 | q_spaces_compare_func); |
7fd0729f | 43 | |
bdcfd34a G |
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 | ||
385a1e07 G |
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 | } | |
7fd0729f | 72 | |
bdcfd34a G |
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) | |
7fd0729f | 76 | { |
9d3444f8 G |
77 | struct listnode *curr_node; |
78 | struct vertex *p_node = NULL, *pc_node_parent, *p_node_pc_parent; | |
7fd0729f G |
79 | struct vertex_parent *pc_vertex_parent; |
80 | ||
9d3444f8 G |
81 | curr_node = listnode_lookup(q_space->pc_path, pc_node); |
82 | pc_node_parent = listgetdata(curr_node->next); | |
7fd0729f | 83 | |
bdcfd34a | 84 | q_space->p_node_info->type = OSPF_TI_LFA_UNDEFINED_NODE; |
7fd0729f | 85 | |
9d3444f8 G |
86 | p_node = ospf_spf_vertex_find(pc_node_parent->id, p_space->vertex_list); |
87 | ||
88 | if (p_node) { | |
bdcfd34a G |
89 | q_space->p_node_info->node = p_node; |
90 | q_space->p_node_info->type = OSPF_TI_LFA_P_NODE; | |
9d3444f8 G |
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); | |
bdcfd34a G |
96 | q_space->p_node_info->nexthop = |
97 | pc_vertex_parent->nexthop->router; | |
9d3444f8 G |
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 | */ | |
bdcfd34a | 104 | q_space->p_node_info->nexthop.s_addr = INADDR_ANY; |
9d3444f8 | 105 | } |
bdcfd34a G |
106 | |
107 | return OSPF_TI_LFA_P_Q_SPACE_ADJACENT; | |
7fd0729f | 108 | } |
bdcfd34a G |
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; | |
7fd0729f G |
112 | } |
113 | ||
114 | static void ospf_ti_lfa_find_q_node(struct vertex *pc_node, | |
115 | struct p_space *p_space, | |
bdcfd34a | 116 | struct q_space *q_space) |
7fd0729f | 117 | { |
9d3444f8 G |
118 | struct listnode *curr_node, *next_node; |
119 | struct vertex *p_node, *q_node, *q_space_parent = NULL, *pc_node_parent; | |
7fd0729f G |
120 | struct vertex_parent *pc_vertex_parent; |
121 | ||
9d3444f8 G |
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 | ||
7fd0729f G |
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 | ||
7815c834 G |
131 | /* The Q node is always present. */ |
132 | assert(q_node); | |
133 | ||
bdcfd34a | 134 | q_space->q_node_info->type = OSPF_TI_LFA_UNDEFINED_NODE; |
7fd0729f G |
135 | |
136 | if (p_node && q_node) { | |
bdcfd34a G |
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; | |
7fd0729f G |
141 | return; |
142 | } | |
143 | ||
9d3444f8 G |
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); | |
7fd0729f G |
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) { | |
bdcfd34a G |
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; | |
7fd0729f G |
160 | return; |
161 | } | |
162 | ||
bdcfd34a | 163 | return ospf_ti_lfa_find_q_node(pc_node_parent, p_space, q_space); |
7fd0729f G |
164 | } |
165 | ||
bdcfd34a G |
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 | ||
7fd0729f G |
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) | |
bdcfd34a | 196 | + MPLS_MAX_LABELS * sizeof(mpls_label_t)); |
7fd0729f G |
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 | ||
bdcfd34a G |
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, | |
7fd0729f G |
391 | struct q_space *q_space) |
392 | { | |
bdcfd34a G |
393 | enum ospf_ti_lfa_p_q_space_adjacency adjacency_result; |
394 | mpls_label_t labels[MPLS_MAX_LABELS]; | |
7fd0729f | 395 | struct vertex *pc_node; |
bdcfd34a | 396 | struct ospf_ti_lfa_inner_backup_path_info inner_backup_path_info; |
7fd0729f | 397 | |
a4553b5b G |
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); | |
7fd0729f | 402 | |
9d3444f8 | 403 | pc_node = listnode_head(q_space->pc_path); |
cc1725bd | 404 | |
7fd0729f | 405 | if (!pc_node) { |
a4553b5b G |
406 | if (IS_DEBUG_OSPF_TI_LFA) |
407 | zlog_debug( | |
408 | "%s: There seems to be no post convergence path (yet).", | |
409 | __func__); | |
7fd0729f G |
410 | return; |
411 | } | |
412 | ||
bdcfd34a G |
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) { | |
a4553b5b G |
415 | if (IS_DEBUG_OSPF_TI_LFA) |
416 | zlog_debug("%s: Q node not found!", __func__); | |
7fd0729f G |
417 | return; |
418 | } | |
419 | ||
420 | /* Found a PQ node? Then we are done here. */ | |
bdcfd34a | 421 | if (q_space->q_node_info->type == OSPF_TI_LFA_PQ_NODE) { |
cc1725bd G |
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, | |
bdcfd34a | 427 | q_space->q_node_info->node)) |
cc1725bd | 428 | labels[0] = ospf_sr_get_adj_sid_by_id( |
bdcfd34a G |
429 | &p_space->root->id, |
430 | &q_space->q_node_info->node->id); | |
cc1725bd G |
431 | else |
432 | labels[0] = ospf_sr_get_prefix_sid_by_id( | |
bdcfd34a | 433 | &q_space->q_node_info->node->id); |
cc1725bd | 434 | |
7fd0729f G |
435 | q_space->label_stack = |
436 | ospf_ti_lfa_create_label_stack(labels, 1); | |
bdcfd34a | 437 | q_space->nexthop = q_space->q_node_info->nexthop; |
cc1725bd | 438 | |
7fd0729f G |
439 | return; |
440 | } | |
441 | ||
bdcfd34a G |
442 | /* Otherwise find a (hopefully adjacent) P node. */ |
443 | pc_node = ospf_spf_vertex_find(q_space->q_node_info->node->id, | |
7fd0729f | 444 | p_space->pc_vertex_list); |
bdcfd34a G |
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) { | |
a4553b5b G |
448 | if (IS_DEBUG_OSPF_TI_LFA) |
449 | zlog_debug("%s: P node not found!", __func__); | |
7fd0729f G |
450 | return; |
451 | } | |
452 | ||
453 | /* | |
bdcfd34a G |
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. | |
7fd0729f | 457 | */ |
bdcfd34a G |
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 | ||
7fd0729f | 496 | q_space->label_stack = |
bdcfd34a G |
497 | ospf_ti_lfa_create_label_stack(labels, 2); |
498 | q_space->nexthop = q_space->p_node_info->nexthop; | |
7fd0729f | 499 | |
bdcfd34a G |
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); | |
cc1725bd | 516 | |
bdcfd34a G |
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 | } | |
cc1725bd | 572 | |
bdcfd34a G |
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 | } | |
7fd0729f G |
598 | } |
599 | ||
9d3444f8 G |
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 | ||
9d3444f8 G |
608 | current_vertex = ospf_spf_vertex_find(dest->id, pc_vertex_list); |
609 | if (!current_vertex) { | |
a4553b5b G |
610 | if (IS_DEBUG_OSPF_TI_LFA) |
611 | zlog_debug( | |
612 | "%s: There seems to be no post convergence path (yet).", | |
613 | __func__); | |
bdcfd34a | 614 | return NULL; |
9d3444f8 G |
615 | } |
616 | ||
bdcfd34a | 617 | pc_path = list_new(); |
9d3444f8 G |
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 | ||
7fd0729f G |
633 | static void ospf_ti_lfa_generate_q_spaces(struct ospf_area *area, |
634 | struct p_space *p_space, | |
bdcfd34a G |
635 | struct vertex *dest, bool recursive, |
636 | struct list *pc_path) | |
7fd0729f G |
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; | |
385a1e07 G |
642 | char label_buf[MPLS_LABEL_STRLEN]; |
643 | char res_buf[PROTECTED_RESOURCE_STRLEN]; | |
bdcfd34a | 644 | bool node_protected; |
385a1e07 G |
645 | |
646 | ospf_print_protected_resource(p_space->protected_resource, res_buf); | |
bdcfd34a G |
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; | |
385a1e07 G |
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 | */ | |
bdcfd34a G |
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 | } | |
385a1e07 G |
664 | return; |
665 | } | |
7fd0729f G |
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)); | |
bdcfd34a G |
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)); | |
7fd0729f G |
677 | |
678 | new_table = route_table_init(); | |
679 | new_rtrs = route_table_init(); | |
680 | ||
681 | /* | |
133e59cf | 682 | * Generate a new (reversed!) SPF tree for this vertex, |
7fd0729f G |
683 | * dry run true, root node false |
684 | */ | |
133e59cf | 685 | area->spf_reversed = true; |
7fd0729f G |
686 | ospf_spf_calculate(area, dest->lsa_p, new_table, new_rtrs, true, false); |
687 | ||
133e59cf G |
688 | /* Reset the flag for reverse SPF */ |
689 | area->spf_reversed = false; | |
690 | ||
7fd0729f G |
691 | q_space->root = area->spf; |
692 | q_space->vertex_list = area->spf_vertex_list; | |
693 | q_space->label_stack = NULL; | |
bdcfd34a G |
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 | } | |
7fd0729f | 710 | |
385a1e07 G |
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); | |
7fd0729f G |
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 | */ | |
bdcfd34a | 719 | ospf_ti_lfa_generate_label_stack(area, p_space, q_space); |
385a1e07 | 720 | |
7fd0729f G |
721 | if (q_space->label_stack) { |
722 | mpls_label2str(q_space->label_stack->num_labels, | |
385a1e07 | 723 | q_space->label_stack->label, label_buf, |
7fd0729f G |
724 | MPLS_LABEL_STRLEN, true); |
725 | zlog_info( | |
385a1e07 G |
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); | |
7fd0729f G |
729 | } else { |
730 | zlog_info( | |
385a1e07 | 731 | "%s: NO label stack generated for root %pI4 and destination %pI4 for %s", |
7fd0729f | 732 | __func__, &p_space->root->id, &q_space->root->id, |
385a1e07 | 733 | res_buf); |
7fd0729f G |
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 */ | |
bdcfd34a G |
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 | } | |
7fd0729f G |
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 | ||
385a1e07 | 755 | area->spf_protected_resource = p_space->protected_resource; |
7fd0729f G |
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 | |
385a1e07 G |
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 | |
7fd0729f | 765 | * convergence SPF tree. The preferred way would be to delete the |
385a1e07 G |
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. | |
7fd0729f G |
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 | ||
385a1e07 | 778 | area->spf_protected_resource = NULL; |
7fd0729f G |
779 | } |
780 | ||
385a1e07 G |
781 | static void |
782 | ospf_ti_lfa_generate_p_space(struct ospf_area *area, struct vertex *child, | |
bdcfd34a G |
783 | struct protected_resource *protected_resource, |
784 | bool recursive, struct list *pc_path) | |
7fd0729f G |
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; | |
385a1e07 | 797 | p_space->protected_resource = protected_resource; |
7fd0729f | 798 | |
385a1e07 | 799 | /* Initialize the Q spaces for this P space and protected resource */ |
7fd0729f G |
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 | ||
385a1e07 G |
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); | |
7fd0729f G |
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 */ | |
bdcfd34a | 819 | ospf_ti_lfa_generate_q_spaces(area, p_space, child, recursive, pc_path); |
7fd0729f G |
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 | ||
385a1e07 G |
829 | void ospf_ti_lfa_generate_p_spaces(struct ospf_area *area, |
830 | enum protection_type protection_type) | |
7fd0729f G |
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; | |
385a1e07 | 838 | struct protected_resource *protected_resource; |
7fd0729f G |
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; | |
936fbaef | 852 | child_prefix.prefixlen = IPV4_MAX_BITLEN; |
7fd0729f G |
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 | ||
385a1e07 G |
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( | |
bdcfd34a G |
882 | area, child, protected_resource, |
883 | true, NULL); | |
385a1e07 G |
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 | ||
7fd0729f G |
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); | |
385a1e07 G |
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( | |
bdcfd34a G |
931 | area, child, protected_resource, |
932 | true, NULL); | |
7fd0729f G |
933 | } |
934 | } | |
935 | } | |
936 | } | |
937 | } | |
938 | ||
385a1e07 G |
939 | static struct p_space *ospf_ti_lfa_get_p_space_by_path(struct ospf_area *area, |
940 | struct ospf_path *path) | |
7fd0729f G |
941 | { |
942 | struct p_space *p_space; | |
943 | struct router_lsa_link *link; | |
385a1e07 G |
944 | struct vertex *child; |
945 | int type; | |
7fd0729f G |
946 | |
947 | frr_each(p_spaces, area->p_spaces, p_space) { | |
385a1e07 G |
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 | } | |
7fd0729f G |
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; | |
385a1e07 | 980 | char label_buf[MPLS_LABEL_STRLEN]; |
7fd0729f G |
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)) { | |
385a1e07 G |
989 | |
990 | if (path->adv_router.s_addr == INADDR_ANY | |
991 | || path->nexthop.s_addr == INADDR_ANY) | |
992 | continue; | |
993 | ||
a4553b5b G |
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); | |
385a1e07 G |
999 | |
1000 | p_space = ospf_ti_lfa_get_p_space_by_path(area, path); | |
7fd0729f | 1001 | if (!p_space) { |
a4553b5b G |
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); | |
7fd0729f G |
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) { | |
a4553b5b G |
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); | |
7fd0729f G |
1019 | continue; |
1020 | } | |
1021 | ||
669247b8 G |
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 | } | |
385a1e07 G |
1044 | |
1045 | if (path->srni.backup_label_stack) { | |
7815c834 G |
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); | |
a4553b5b G |
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); | |
385a1e07 | 1057 | } else { |
a4553b5b G |
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); | |
385a1e07 | 1064 | } |
7fd0729f G |
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 | ||
bdcfd34a G |
1078 | if (q_space->pc_path) |
1079 | list_delete(&q_space->pc_path); | |
9d3444f8 | 1080 | |
bdcfd34a G |
1081 | XFREE(MTYPE_OSPF_Q_SPACE, q_space->p_node_info); |
1082 | XFREE(MTYPE_OSPF_Q_SPACE, q_space->q_node_info); | |
669247b8 | 1083 | XFREE(MTYPE_OSPF_Q_SPACE, q_space->label_stack); |
7fd0729f G |
1084 | XFREE(MTYPE_OSPF_Q_SPACE, q_space); |
1085 | } | |
669247b8 | 1086 | |
7fd0729f G |
1087 | ospf_spf_cleanup(p_space->root, p_space->vertex_list); |
1088 | ospf_spf_cleanup(p_space->pc_spf, p_space->pc_vertex_list); | |
385a1e07 | 1089 | XFREE(MTYPE_OSPF_P_SPACE, p_space->protected_resource); |
7fd0729f G |
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 | ||
385a1e07 G |
1099 | void ospf_ti_lfa_compute(struct ospf_area *area, struct route_table *new_table, |
1100 | enum protection_type protection_type) | |
7fd0729f G |
1101 | { |
1102 | /* | |
385a1e07 G |
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. | |
7fd0729f | 1106 | */ |
385a1e07 | 1107 | ospf_ti_lfa_generate_p_spaces(area, protection_type); |
7fd0729f G |
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 | } |