]>
Commit | Line | Data |
---|---|---|
c951ee6e RW |
1 | /* |
2 | * Copyright (C) 2020 NetDEF, Inc. | |
3 | * Renato Westphal | |
4 | * | |
5 | * This program is free software; you can redistribute it and/or modify it | |
6 | * under the terms of the GNU General Public License as published by the Free | |
7 | * Software Foundation; either version 2 of the License, or (at your option) | |
8 | * any later version. | |
9 | * | |
10 | * This program is distributed in the hope that it will be useful, but WITHOUT | |
11 | * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or | |
12 | * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for | |
13 | * more details. | |
14 | * | |
15 | * You should have received a copy of the GNU General Public License along | |
16 | * with this program; see the file COPYING; if not, write to the Free Software | |
17 | * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA | |
18 | */ | |
19 | ||
20 | #include <zebra.h> | |
21 | ||
22 | #include "linklist.h" | |
23 | #include "log.h" | |
24 | #include "memory.h" | |
25 | #include "vrf.h" | |
26 | #include "table.h" | |
27 | #include "srcdest_table.h" | |
28 | ||
29 | #include "isis_common.h" | |
30 | #include "isisd.h" | |
31 | #include "isis_misc.h" | |
32 | #include "isis_adjacency.h" | |
33 | #include "isis_circuit.h" | |
34 | #include "isis_lsp.h" | |
35 | #include "isis_spf.h" | |
36 | #include "isis_route.h" | |
37 | #include "isis_mt.h" | |
38 | #include "isis_tlvs.h" | |
39 | #include "isis_spf_private.h" | |
40 | #include "isisd/isis_errors.h" | |
41 | ||
42 | DEFINE_MTYPE_STATIC(ISISD, ISIS_SPF_NODE, "ISIS SPF Node"); | |
43 | ||
44 | static inline int isis_spf_node_compare(const struct isis_spf_node *a, | |
45 | const struct isis_spf_node *b) | |
46 | { | |
47 | return memcmp(a->sysid, b->sysid, sizeof(a->sysid)); | |
48 | } | |
49 | RB_GENERATE(isis_spf_nodes, isis_spf_node, entry, isis_spf_node_compare) | |
50 | ||
51 | /** | |
52 | * Initialize list of SPF nodes. | |
53 | * | |
54 | * @param nodes List of SPF nodes | |
55 | */ | |
56 | void isis_spf_node_list_init(struct isis_spf_nodes *nodes) | |
57 | { | |
58 | RB_INIT(isis_spf_nodes, nodes); | |
59 | } | |
60 | ||
61 | /** | |
62 | * Clear list of SPF nodes, releasing all allocated memory. | |
63 | * | |
64 | * @param nodes List of SPF nodes | |
65 | */ | |
66 | void isis_spf_node_list_clear(struct isis_spf_nodes *nodes) | |
67 | { | |
68 | while (!RB_EMPTY(isis_spf_nodes, nodes)) { | |
69 | struct isis_spf_node *node = RB_ROOT(isis_spf_nodes, nodes); | |
70 | ||
71 | if (node->adjacencies) | |
72 | list_delete(&node->adjacencies); | |
73 | if (node->lfa.spftree) | |
74 | isis_spftree_del(node->lfa.spftree); | |
75 | if (node->lfa.spftree_reverse) | |
76 | isis_spftree_del(node->lfa.spftree_reverse); | |
77 | isis_spf_node_list_clear(&node->lfa.p_space); | |
78 | RB_REMOVE(isis_spf_nodes, nodes, node); | |
79 | XFREE(MTYPE_ISIS_SPF_NODE, node); | |
80 | } | |
81 | } | |
82 | ||
83 | /** | |
84 | * Add new node to list of SPF nodes. | |
85 | * | |
86 | * @param nodes List of SPF nodes | |
87 | * @param sysid Node System ID | |
88 | * | |
89 | * @return Pointer to new IS-IS SPF node structure. | |
90 | */ | |
91 | struct isis_spf_node *isis_spf_node_new(struct isis_spf_nodes *nodes, | |
92 | const uint8_t *sysid) | |
93 | { | |
94 | struct isis_spf_node *node; | |
95 | ||
96 | node = XCALLOC(MTYPE_ISIS_SPF_NODE, sizeof(*node)); | |
97 | memcpy(node->sysid, sysid, sizeof(node->sysid)); | |
98 | node->adjacencies = list_new(); | |
99 | isis_spf_node_list_init(&node->lfa.p_space); | |
100 | RB_INSERT(isis_spf_nodes, nodes, node); | |
101 | ||
102 | return node; | |
103 | } | |
104 | ||
105 | /** | |
106 | * Lookup SPF node by its System ID on the given list. | |
107 | * | |
108 | * @param nodes List of SPF nodes | |
109 | * @param sysid Node System ID | |
110 | * | |
111 | * @return Pointer to SPF node if found, NULL otherwise | |
112 | */ | |
113 | struct isis_spf_node *isis_spf_node_find(const struct isis_spf_nodes *nodes, | |
114 | const uint8_t *sysid) | |
115 | { | |
116 | struct isis_spf_node node = {}; | |
117 | ||
118 | memcpy(node.sysid, sysid, sizeof(node.sysid)); | |
119 | return RB_FIND(isis_spf_nodes, nodes, &node); | |
120 | } | |
121 | ||
122 | /** | |
123 | * Check if a given IS-IS adjacency needs to be excised when computing the SPF | |
124 | * post-convergence tree. | |
125 | * | |
126 | * @param spftree IS-IS SPF tree | |
127 | * @param id Adjacency System ID (or LAN ID of the designated router | |
128 | * for broadcast interfaces) | |
129 | * | |
130 | * @return true if the adjacency needs to be excised, false | |
131 | * otherwise | |
132 | */ | |
133 | bool isis_lfa_excise_adj_check(const struct isis_spftree *spftree, | |
134 | const uint8_t *id) | |
135 | { | |
136 | const struct lfa_protected_resource *resource; | |
137 | ||
138 | if (spftree->type != SPF_TYPE_TI_LFA) | |
139 | return false; | |
140 | ||
141 | /* | |
142 | * Adjacencies formed over the failed interface should be excised both | |
143 | * when using link and node protection. | |
144 | */ | |
145 | resource = &spftree->lfa.protected_resource; | |
146 | if (!memcmp(resource->adjacency, id, ISIS_SYS_ID_LEN + 1)) | |
147 | return true; | |
148 | ||
149 | return false; | |
150 | } | |
151 | ||
152 | /** | |
153 | * Check if a given IS-IS node needs to be excised when computing the SPF | |
154 | * post-convergence tree. | |
155 | * | |
156 | * @param spftree IS-IS SPF tree | |
157 | * @param id Node System ID | |
158 | * | |
159 | * @return true if the node needs to be excised, false otherwise | |
160 | */ | |
161 | bool isis_lfa_excise_node_check(const struct isis_spftree *spftree, | |
162 | const uint8_t *id) | |
163 | { | |
164 | const struct lfa_protected_resource *resource; | |
165 | ||
166 | if (spftree->type != SPF_TYPE_TI_LFA) | |
167 | return false; | |
168 | ||
169 | /* | |
170 | * When using node protection, nodes reachable over the failed interface | |
171 | * must be excised. | |
172 | */ | |
173 | resource = &spftree->lfa.protected_resource; | |
174 | if (resource->type == LFA_LINK_PROTECTION) | |
175 | return false; | |
176 | ||
177 | if (isis_spf_node_find(&resource->nodes, id)) | |
178 | return true; | |
179 | ||
180 | return false; | |
181 | } | |
182 | ||
c951ee6e RW |
183 | struct tilfa_find_pnode_prefix_sid_args { |
184 | uint32_t sid_index; | |
185 | }; | |
186 | ||
187 | static int tilfa_find_pnode_prefix_sid_cb(const struct prefix *prefix, | |
188 | uint32_t metric, bool external, | |
189 | struct isis_subtlvs *subtlvs, | |
190 | void *arg) | |
191 | { | |
192 | struct tilfa_find_pnode_prefix_sid_args *args = arg; | |
193 | struct isis_prefix_sid *psid; | |
194 | ||
195 | if (!subtlvs || subtlvs->prefix_sids.count == 0) | |
196 | return LSP_ITER_CONTINUE; | |
197 | ||
198 | psid = (struct isis_prefix_sid *)subtlvs->prefix_sids.head; | |
199 | ||
200 | /* Require the node flag to be set. */ | |
201 | if (!CHECK_FLAG(psid->flags, ISIS_PREFIX_SID_NODE)) | |
202 | return LSP_ITER_CONTINUE; | |
203 | ||
204 | args->sid_index = psid->value; | |
205 | ||
206 | return LSP_ITER_STOP; | |
207 | } | |
208 | ||
209 | /* Find Prefix-SID associated to a System ID. */ | |
210 | static uint32_t tilfa_find_pnode_prefix_sid(struct isis_spftree *spftree, | |
211 | const uint8_t *sysid) | |
212 | { | |
213 | struct isis_lsp *lsp; | |
214 | struct tilfa_find_pnode_prefix_sid_args args; | |
215 | ||
216 | lsp = isis_root_system_lsp(spftree->lspdb, sysid); | |
217 | if (!lsp) | |
218 | return UINT32_MAX; | |
219 | ||
220 | args.sid_index = UINT32_MAX; | |
221 | isis_lsp_iterate_ip_reach(lsp, spftree->family, spftree->mtid, | |
222 | tilfa_find_pnode_prefix_sid_cb, &args); | |
223 | ||
224 | return args.sid_index; | |
225 | } | |
226 | ||
227 | struct tilfa_find_qnode_adj_sid_args { | |
228 | const uint8_t *qnode_sysid; | |
229 | mpls_label_t label; | |
230 | }; | |
231 | ||
232 | static int tilfa_find_qnode_adj_sid_cb(const uint8_t *id, uint32_t metric, | |
233 | bool oldmetric, | |
234 | struct isis_ext_subtlvs *subtlvs, | |
235 | void *arg) | |
236 | { | |
237 | struct tilfa_find_qnode_adj_sid_args *args = arg; | |
238 | struct isis_adj_sid *adj_sid; | |
239 | ||
240 | if (memcmp(id, args->qnode_sysid, ISIS_SYS_ID_LEN)) | |
241 | return LSP_ITER_CONTINUE; | |
242 | if (!subtlvs || subtlvs->adj_sid.count == 0) | |
243 | return LSP_ITER_CONTINUE; | |
244 | ||
245 | adj_sid = (struct isis_adj_sid *)subtlvs->adj_sid.head; | |
246 | args->label = adj_sid->sid; | |
247 | ||
248 | return LSP_ITER_STOP; | |
249 | } | |
250 | ||
251 | /* Find Adj-SID associated to a pair of System IDs. */ | |
252 | static mpls_label_t tilfa_find_qnode_adj_sid(struct isis_spftree *spftree, | |
253 | const uint8_t *source_sysid, | |
254 | const uint8_t *qnode_sysid) | |
255 | { | |
256 | struct isis_lsp *lsp; | |
257 | struct tilfa_find_qnode_adj_sid_args args; | |
258 | ||
259 | lsp = isis_root_system_lsp(spftree->lspdb, source_sysid); | |
260 | if (!lsp) | |
261 | return MPLS_INVALID_LABEL; | |
262 | ||
263 | args.qnode_sysid = qnode_sysid; | |
264 | args.label = MPLS_INVALID_LABEL; | |
265 | isis_lsp_iterate_is_reach(lsp, spftree->mtid, | |
266 | tilfa_find_qnode_adj_sid_cb, &args); | |
267 | ||
268 | return args.label; | |
269 | } | |
270 | ||
271 | /* | |
272 | * Compute the MPLS label stack associated to a TI-LFA repair list. This | |
273 | * needs to be computed separately for each adjacency since different | |
274 | * neighbors can have different SRGBs. | |
275 | */ | |
276 | static struct mpls_label_stack * | |
277 | tilfa_compute_label_stack(struct lspdb_head *lspdb, | |
278 | const struct isis_spf_adj *sadj, | |
279 | const struct list *repair_list) | |
280 | { | |
281 | struct mpls_label_stack *label_stack; | |
282 | struct isis_tilfa_sid *sid; | |
283 | struct listnode *node; | |
284 | size_t i = 0; | |
285 | ||
286 | /* Allocate label stack. */ | |
287 | label_stack = XCALLOC(MTYPE_ISIS_NEXTHOP_LABELS, | |
288 | sizeof(struct mpls_label_stack) | |
289 | + listcount(repair_list) | |
290 | * sizeof(mpls_label_t)); | |
291 | label_stack->num_labels = listcount(repair_list); | |
292 | ||
293 | for (ALL_LIST_ELEMENTS_RO(repair_list, node, sid)) { | |
4c75f7c7 | 294 | const uint8_t *target_node; |
c951ee6e RW |
295 | struct isis_sr_block *srgb; |
296 | mpls_label_t label; | |
297 | ||
298 | switch (sid->type) { | |
299 | case TILFA_SID_PREFIX: | |
4c75f7c7 RW |
300 | if (sid->value.index.remote) |
301 | target_node = sid->value.index.remote_sysid; | |
302 | else | |
303 | target_node = sadj->id; | |
304 | srgb = isis_sr_find_srgb(lspdb, target_node); | |
c951ee6e RW |
305 | if (!srgb) { |
306 | zlog_warn("%s: SRGB not found for node %s", | |
307 | __func__, | |
4c75f7c7 | 308 | print_sys_hostname(target_node)); |
c951ee6e RW |
309 | goto error; |
310 | } | |
311 | ||
312 | /* Check if the SID index falls inside the SRGB. */ | |
4c75f7c7 | 313 | if (sid->value.index.value >= srgb->range_size) { |
c951ee6e RW |
314 | flog_warn( |
315 | EC_ISIS_SID_OVERFLOW, | |
316 | "%s: SID index %u falls outside remote SRGB range", | |
4c75f7c7 | 317 | __func__, sid->value.index.value); |
c951ee6e RW |
318 | goto error; |
319 | } | |
320 | ||
321 | /* | |
322 | * Prefix-SID: map SID index to label value within the | |
323 | * SRGB. | |
324 | */ | |
4c75f7c7 | 325 | label = srgb->lower_bound + sid->value.index.value; |
c951ee6e RW |
326 | break; |
327 | case TILFA_SID_ADJ: | |
328 | /* Adj-SID: absolute label value can be used directly */ | |
329 | label = sid->value.label; | |
330 | break; | |
331 | default: | |
332 | flog_err(EC_LIB_DEVELOPMENT, | |
333 | "%s: unknown TI-LFA SID type [%u]", __func__, | |
334 | sid->type); | |
335 | exit(1); | |
336 | } | |
337 | label_stack->label[i++] = label; | |
338 | } | |
339 | ||
340 | return label_stack; | |
341 | ||
342 | error: | |
343 | XFREE(MTYPE_ISIS_NEXTHOP_LABELS, label_stack); | |
344 | return NULL; | |
345 | } | |
346 | ||
347 | static int tilfa_repair_list_apply(struct isis_spftree *spftree, | |
348 | struct isis_vertex *vertex_dest, | |
349 | const struct isis_vertex *vertex_pnode, | |
350 | const struct list *repair_list) | |
351 | { | |
352 | struct isis_vertex_adj *vadj; | |
353 | struct listnode *node; | |
354 | ||
355 | for (ALL_LIST_ELEMENTS_RO(vertex_dest->Adj_N, node, vadj)) { | |
356 | struct isis_spf_adj *sadj = vadj->sadj; | |
357 | struct mpls_label_stack *label_stack; | |
358 | ||
359 | if (!isis_vertex_adj_exists(spftree, vertex_pnode, sadj)) | |
360 | continue; | |
361 | ||
362 | assert(!vadj->label_stack); | |
363 | label_stack = tilfa_compute_label_stack(spftree->lspdb, sadj, | |
364 | repair_list); | |
365 | if (!label_stack) { | |
366 | char buf[VID2STR_BUFFER]; | |
367 | ||
368 | vid2string(vertex_dest, buf, sizeof(buf)); | |
369 | zlog_warn( | |
370 | "%s: %s %s adjacency %s: failed to compute label stack", | |
371 | __func__, vtype2string(vertex_dest->type), buf, | |
372 | print_sys_hostname(sadj->id)); | |
373 | return -1; | |
374 | } | |
375 | ||
376 | vadj->label_stack = label_stack; | |
377 | } | |
378 | ||
379 | return 0; | |
380 | } | |
381 | ||
382 | /* | |
383 | * Check if a node belongs to the extended P-space corresponding to a given | |
384 | * destination. | |
385 | */ | |
386 | static bool lfa_ext_p_space_check(const struct isis_spftree *spftree_pc, | |
387 | const struct isis_vertex *vertex_dest, | |
388 | const struct isis_vertex *vertex) | |
389 | { | |
390 | struct isis_spftree *spftree_old = spftree_pc->lfa.old.spftree; | |
391 | struct isis_vertex_adj *vadj; | |
392 | struct listnode *node; | |
393 | ||
394 | /* Check the local P-space first. */ | |
395 | if (isis_spf_node_find(&spftree_pc->lfa.p_space, vertex->N.id)) | |
396 | return true; | |
397 | ||
398 | /* | |
399 | * Check the P-space of the adjacent routers used to reach the | |
400 | * destination. | |
401 | */ | |
402 | for (ALL_LIST_ELEMENTS_RO(vertex_dest->Adj_N, node, vadj)) { | |
403 | struct isis_spf_adj *sadj = vadj->sadj; | |
404 | struct isis_spf_node *adj_node; | |
405 | ||
406 | adj_node = | |
407 | isis_spf_node_find(&spftree_old->adj_nodes, sadj->id); | |
408 | if (!adj_node) | |
409 | continue; | |
410 | ||
411 | if (isis_spf_node_find(&adj_node->lfa.p_space, vertex->N.id)) | |
412 | return true; | |
413 | } | |
414 | ||
415 | return false; | |
416 | } | |
417 | ||
418 | /* Check if a node belongs to the Q-space. */ | |
419 | static bool lfa_q_space_check(const struct isis_spftree *spftree_pc, | |
420 | const struct isis_vertex *vertex) | |
421 | { | |
422 | return isis_spf_node_find(&spftree_pc->lfa.q_space, vertex->N.id); | |
423 | } | |
424 | ||
425 | /* This is a recursive function. */ | |
426 | static int tilfa_build_repair_list(struct isis_spftree *spftree_pc, | |
427 | struct isis_vertex *vertex_dest, | |
428 | const struct isis_vertex *vertex, | |
429 | const struct isis_vertex *vertex_child, | |
430 | struct isis_spf_nodes *used_pnodes, | |
431 | struct list *repair_list) | |
432 | { | |
433 | struct isis_vertex *pvertex; | |
434 | struct listnode *node; | |
435 | bool is_pnode, is_qnode; | |
436 | char buf[VID2STR_BUFFER]; | |
4c75f7c7 RW |
437 | struct isis_tilfa_sid sid_dest = {}, sid_qnode = {}, sid_pnode = {}; |
438 | uint32_t sid_index; | |
c951ee6e RW |
439 | mpls_label_t label_qnode; |
440 | ||
441 | if (IS_DEBUG_TILFA) { | |
442 | vid2string(vertex, buf, sizeof(buf)); | |
443 | zlog_debug("ISIS-TI-LFA: vertex %s %s", | |
444 | vtype2string(vertex->type), buf); | |
445 | } | |
446 | ||
4c75f7c7 RW |
447 | /* Push original Prefix-SID label when necessary. */ |
448 | if (VTYPE_IP(vertex->type) && vertex->N.ip.sr.present) { | |
449 | pvertex = listnode_head(vertex->parents); | |
450 | assert(pvertex); | |
451 | ||
452 | sid_index = vertex->N.ip.sr.sid.value; | |
453 | if (IS_DEBUG_TILFA) | |
454 | zlog_debug( | |
455 | "ISIS-TI-LFA: pushing Prefix-SID to %pFX (index %u)", | |
456 | &vertex->N.ip.p.dest, sid_index); | |
457 | sid_dest.type = TILFA_SID_PREFIX; | |
458 | sid_dest.value.index.value = sid_index; | |
459 | sid_dest.value.index.remote = true; | |
460 | memcpy(sid_dest.value.index.remote_sysid, pvertex->N.id, | |
461 | sizeof(sid_dest.value.index.remote_sysid)); | |
462 | listnode_add_head(repair_list, &sid_dest); | |
463 | } | |
464 | ||
c951ee6e RW |
465 | if (!vertex_child) |
466 | goto parents; | |
467 | if (vertex->type != VTYPE_NONPSEUDO_IS | |
468 | && vertex->type != VTYPE_NONPSEUDO_TE_IS) | |
469 | goto parents; | |
470 | if (!VTYPE_IS(vertex_child->type)) | |
471 | vertex_child = NULL; | |
472 | ||
473 | /* Check if node is part of the extended P-space and/or Q-space. */ | |
474 | is_pnode = lfa_ext_p_space_check(spftree_pc, vertex_dest, vertex); | |
475 | is_qnode = lfa_q_space_check(spftree_pc, vertex); | |
476 | ||
477 | /* Push Adj-SID label when necessary. */ | |
478 | if ((!is_qnode | |
479 | || spftree_pc->lfa.protected_resource.type == LFA_NODE_PROTECTION) | |
480 | && vertex_child) { | |
481 | label_qnode = tilfa_find_qnode_adj_sid(spftree_pc, vertex->N.id, | |
482 | vertex_child->N.id); | |
483 | if (label_qnode == MPLS_INVALID_LABEL) { | |
484 | zlog_warn("ISIS-TI-LFA: failed to find %s->%s Adj-SID", | |
485 | print_sys_hostname(vertex->N.id), | |
486 | print_sys_hostname(vertex_child->N.id)); | |
487 | return -1; | |
488 | } | |
489 | if (IS_DEBUG_TILFA) | |
490 | zlog_debug( | |
491 | "ISIS-TI-LFA: pushing %s->%s Adj-SID (label %u)", | |
492 | print_sys_hostname(vertex->N.id), | |
493 | print_sys_hostname(vertex_child->N.id), | |
494 | label_qnode); | |
495 | sid_qnode.type = TILFA_SID_ADJ; | |
496 | sid_qnode.value.label = label_qnode; | |
497 | listnode_add_head(repair_list, &sid_qnode); | |
498 | } | |
499 | ||
500 | /* Push Prefix-SID label when necessary. */ | |
501 | if (is_pnode) { | |
c951ee6e RW |
502 | /* The same P-node can't be used more than once. */ |
503 | if (isis_spf_node_find(used_pnodes, vertex->N.id)) { | |
504 | if (IS_DEBUG_TILFA) | |
505 | zlog_debug( | |
506 | "ISIS-TI-LFA: skipping already used P-node"); | |
507 | return 0; | |
508 | } | |
509 | isis_spf_node_new(used_pnodes, vertex->N.id); | |
510 | ||
511 | if (!vertex_child) { | |
512 | if (IS_DEBUG_TILFA) | |
513 | zlog_debug( | |
514 | "ISIS-TI-LFA: destination is within Ext-P-Space"); | |
515 | return 0; | |
516 | } | |
517 | ||
518 | sid_index = | |
519 | tilfa_find_pnode_prefix_sid(spftree_pc, vertex->N.id); | |
520 | if (sid_index == UINT32_MAX) { | |
521 | zlog_warn( | |
522 | "ISIS-TI-LFA: failed to find Prefix-SID corresponding to PQ-node %s", | |
523 | print_sys_hostname(vertex->N.id)); | |
524 | return -1; | |
525 | } | |
526 | ||
527 | if (IS_DEBUG_TILFA) | |
528 | zlog_debug( | |
4c75f7c7 | 529 | "ISIS-TI-LFA: pushing Node-SID to %s (index %u)", |
c951ee6e RW |
530 | print_sys_hostname(vertex->N.id), sid_index); |
531 | sid_pnode.type = TILFA_SID_PREFIX; | |
4c75f7c7 | 532 | sid_pnode.value.index.value = sid_index; |
c951ee6e RW |
533 | listnode_add_head(repair_list, &sid_pnode); |
534 | ||
535 | /* Apply repair list. */ | |
536 | if (tilfa_repair_list_apply(spftree_pc, vertex_dest, vertex, | |
537 | repair_list) | |
538 | != 0) | |
539 | return -1; | |
540 | return 0; | |
541 | } | |
542 | ||
543 | parents: | |
544 | for (ALL_LIST_ELEMENTS_RO(vertex->parents, node, pvertex)) { | |
545 | struct list *repair_list_parent; | |
546 | bool ecmp; | |
547 | int ret; | |
548 | ||
549 | ecmp = (listcount(vertex->parents) > 1) ? true : false; | |
550 | repair_list_parent = ecmp ? list_dup(repair_list) : repair_list; | |
551 | ret = tilfa_build_repair_list(spftree_pc, vertex_dest, pvertex, | |
552 | vertex, used_pnodes, | |
553 | repair_list_parent); | |
554 | if (ecmp) | |
555 | list_delete(&repair_list_parent); | |
556 | if (ret != 0) | |
557 | return ret; | |
558 | } | |
559 | ||
560 | return 0; | |
561 | } | |
562 | ||
563 | static const char *lfa_protection_type2str(enum lfa_protection_type type) | |
564 | { | |
565 | switch (type) { | |
566 | case LFA_LINK_PROTECTION: | |
567 | return "link protection"; | |
568 | case LFA_NODE_PROTECTION: | |
569 | return "node protection"; | |
570 | default: | |
571 | return "unknown protection type"; | |
572 | } | |
573 | } | |
574 | ||
575 | static const char * | |
576 | lfa_protected_resource2str(const struct lfa_protected_resource *resource) | |
577 | { | |
578 | const uint8_t *fail_id; | |
579 | static char buffer[128]; | |
580 | ||
581 | fail_id = resource->adjacency; | |
582 | snprintf(buffer, sizeof(buffer), "%s.%u's failure (%s)", | |
583 | print_sys_hostname(fail_id), LSP_PSEUDO_ID(fail_id), | |
584 | lfa_protection_type2str(resource->type)); | |
585 | ||
586 | return buffer; | |
587 | } | |
588 | ||
589 | static bool | |
590 | spf_adj_check_is_affected(const struct isis_spf_adj *sadj, | |
591 | const struct lfa_protected_resource *resource, | |
592 | const uint8_t *root_sysid, bool reverse) | |
593 | { | |
594 | if (!!CHECK_FLAG(sadj->flags, F_ISIS_SPF_ADJ_BROADCAST) | |
595 | != !!LSP_PSEUDO_ID(resource->adjacency)) | |
596 | return false; | |
597 | ||
598 | if (CHECK_FLAG(sadj->flags, F_ISIS_SPF_ADJ_BROADCAST)) { | |
599 | if (!memcmp(sadj->lan.desig_is_id, resource->adjacency, | |
600 | ISIS_SYS_ID_LEN + 1)) | |
601 | return true; | |
602 | } else { | |
603 | if (!reverse | |
604 | && !memcmp(sadj->id, resource->adjacency, ISIS_SYS_ID_LEN)) | |
605 | return true; | |
606 | if (reverse && !memcmp(sadj->id, root_sysid, ISIS_SYS_ID_LEN)) | |
607 | return true; | |
608 | } | |
609 | ||
610 | return false; | |
611 | } | |
612 | ||
613 | /* Check if the given SPF vertex needs LFA protection. */ | |
614 | static bool lfa_check_needs_protection(const struct isis_spftree *spftree_pc, | |
615 | const struct isis_vertex *vertex) | |
616 | { | |
617 | struct isis_vertex *vertex_old; | |
618 | struct listnode *node; | |
619 | size_t affected_nhs = 0; | |
620 | struct isis_vertex_adj *vadj; | |
621 | ||
d4fcd8bd RW |
622 | /* Local routes don't need protection. */ |
623 | if (VTYPE_IP(vertex->type) && vertex->depth == 1) | |
624 | return false; | |
625 | ||
c951ee6e RW |
626 | /* Only local adjacencies need Adj-SID protection. */ |
627 | if (VTYPE_IS(vertex->type) | |
628 | && !isis_adj_find(spftree_pc->area, spftree_pc->level, | |
629 | vertex->N.id)) | |
630 | return false; | |
631 | ||
632 | vertex_old = isis_find_vertex(&spftree_pc->lfa.old.spftree->paths, | |
633 | &vertex->N, vertex->type); | |
634 | if (!vertex_old) | |
635 | return false; | |
636 | ||
637 | for (ALL_LIST_ELEMENTS_RO(vertex_old->Adj_N, node, vadj)) { | |
638 | struct isis_spf_adj *sadj = vadj->sadj; | |
639 | ||
640 | if (spf_adj_check_is_affected( | |
641 | sadj, &spftree_pc->lfa.protected_resource, | |
642 | spftree_pc->sysid, false)) | |
643 | affected_nhs++; | |
644 | } | |
645 | ||
646 | /* | |
647 | * No need to compute backup paths for ECMP routes, except if all | |
648 | * primary nexthops share the same broadcast interface. | |
649 | */ | |
650 | if (listcount(vertex_old->Adj_N) == affected_nhs) | |
651 | return true; | |
652 | ||
653 | return false; | |
654 | } | |
655 | ||
656 | /** | |
657 | * Check if the given SPF vertex needs protection and, if so, compute and | |
658 | * install the corresponding repair paths. | |
659 | * | |
660 | * @param spftree_pc The post-convergence SPF tree | |
661 | * @param vertex IS-IS SPF vertex to check | |
662 | * | |
663 | * @return 0 if the vertex needs to be protected, -1 otherwise | |
664 | */ | |
665 | int isis_lfa_check(struct isis_spftree *spftree_pc, struct isis_vertex *vertex) | |
666 | { | |
667 | struct isis_spf_nodes used_pnodes; | |
668 | char buf[VID2STR_BUFFER]; | |
669 | struct list *repair_list; | |
670 | int ret; | |
671 | ||
672 | if (!spftree_pc->area->srdb.enabled) | |
673 | return -1; | |
674 | ||
675 | if (IS_DEBUG_TILFA) | |
676 | vid2string(vertex, buf, sizeof(buf)); | |
677 | ||
678 | if (!lfa_check_needs_protection(spftree_pc, vertex)) { | |
679 | if (IS_DEBUG_TILFA) | |
680 | zlog_debug( | |
681 | "ISIS-TI-LFA: %s %s unaffected by %s", | |
682 | vtype2string(vertex->type), buf, | |
683 | lfa_protected_resource2str( | |
684 | &spftree_pc->lfa.protected_resource)); | |
685 | ||
686 | return -1; | |
687 | } | |
688 | ||
689 | /* | |
054fda12 | 690 | * Check if the route/adjacency was already covered by node protection. |
c951ee6e | 691 | */ |
054fda12 RW |
692 | if (VTYPE_IS(vertex->type)) { |
693 | struct isis_adjacency *adj; | |
694 | ||
695 | adj = isis_adj_find(spftree_pc->area, spftree_pc->level, | |
696 | vertex->N.id); | |
697 | if (adj | |
698 | && isis_sr_adj_sid_find(adj, spftree_pc->family, | |
699 | ISIS_SR_LAN_BACKUP)) { | |
700 | if (IS_DEBUG_TILFA) | |
701 | zlog_debug( | |
702 | "ISIS-TI-LFA: %s %s already covered by node protection", | |
703 | vtype2string(vertex->type), buf); | |
704 | ||
705 | return -1; | |
706 | } | |
707 | } | |
c951ee6e RW |
708 | if (VTYPE_IP(vertex->type)) { |
709 | struct route_table *route_table; | |
710 | ||
711 | route_table = spftree_pc->lfa.old.spftree->route_table_backup; | |
d47d6089 | 712 | if (route_node_lookup(route_table, &vertex->N.ip.p.dest)) { |
c951ee6e RW |
713 | if (IS_DEBUG_TILFA) |
714 | zlog_debug( | |
715 | "ISIS-TI-LFA: %s %s already covered by node protection", | |
716 | vtype2string(vertex->type), buf); | |
717 | ||
718 | return -1; | |
719 | } | |
720 | } | |
721 | ||
722 | if (IS_DEBUG_TILFA) | |
723 | zlog_debug( | |
724 | "ISIS-TI-LFA: computing repair path(s) of %s %s w.r.t %s", | |
725 | vtype2string(vertex->type), buf, | |
726 | lfa_protected_resource2str( | |
727 | &spftree_pc->lfa.protected_resource)); | |
728 | ||
729 | /* Create base repair list. */ | |
730 | repair_list = list_new(); | |
731 | ||
732 | isis_spf_node_list_init(&used_pnodes); | |
733 | ret = tilfa_build_repair_list(spftree_pc, vertex, vertex, NULL, | |
734 | &used_pnodes, repair_list); | |
735 | isis_spf_node_list_clear(&used_pnodes); | |
736 | list_delete(&repair_list); | |
737 | if (ret != 0) | |
738 | zlog_warn("ISIS-TI-LFA: failed to compute repair path(s)"); | |
739 | ||
740 | return ret; | |
741 | } | |
742 | ||
743 | static bool | |
744 | spf_adj_node_is_affected(struct isis_spf_node *adj_node, | |
745 | const struct lfa_protected_resource *resource, | |
746 | const uint8_t *root_sysid) | |
747 | { | |
748 | struct isis_spf_adj *sadj; | |
749 | struct listnode *node; | |
750 | ||
751 | for (ALL_LIST_ELEMENTS_RO(adj_node->adjacencies, node, sadj)) { | |
752 | if (sadj->metric != adj_node->best_metric) | |
753 | continue; | |
754 | if (spf_adj_check_is_affected(sadj, resource, root_sysid, | |
755 | false)) | |
756 | return true; | |
757 | } | |
758 | ||
759 | return false; | |
760 | } | |
761 | ||
762 | static bool vertex_is_affected(struct isis_spftree *spftree_root, | |
763 | const struct isis_spf_nodes *adj_nodes, | |
764 | bool p_space, const struct isis_vertex *vertex, | |
765 | const struct lfa_protected_resource *resource) | |
766 | { | |
767 | struct isis_vertex *pvertex; | |
768 | struct listnode *node, *vnode; | |
769 | ||
770 | for (ALL_LIST_ELEMENTS_RO(vertex->parents, node, pvertex)) { | |
771 | struct isis_spftree *spftree_parent; | |
772 | struct isis_vertex *vertex_child; | |
773 | struct isis_vertex_adj *vadj; | |
774 | bool reverse = false; | |
775 | char buf1[VID2STR_BUFFER]; | |
776 | char buf2[VID2STR_BUFFER]; | |
777 | ||
778 | if (IS_DEBUG_TILFA) | |
779 | zlog_debug("ISIS-TI-LFA: vertex %s parent %s", | |
780 | vid2string(vertex, buf1, sizeof(buf1)), | |
781 | vid2string(pvertex, buf2, sizeof(buf2))); | |
782 | ||
783 | if (p_space && resource->type == LFA_NODE_PROTECTION) { | |
784 | if (isis_spf_node_find(&resource->nodes, vertex->N.id)) | |
785 | return true; | |
786 | goto parents; | |
787 | } | |
788 | ||
789 | /* Check if either the vertex or its parent is the root node. */ | |
790 | if (memcmp(vertex->N.id, spftree_root->sysid, ISIS_SYS_ID_LEN) | |
791 | && memcmp(pvertex->N.id, spftree_root->sysid, | |
792 | ISIS_SYS_ID_LEN)) | |
793 | goto parents; | |
794 | ||
795 | /* Get SPT of the parent vertex. */ | |
796 | if (!memcmp(pvertex->N.id, spftree_root->sysid, | |
797 | ISIS_SYS_ID_LEN)) | |
798 | spftree_parent = spftree_root; | |
799 | else { | |
800 | struct isis_spf_node *adj_node; | |
801 | ||
802 | adj_node = isis_spf_node_find(adj_nodes, pvertex->N.id); | |
803 | assert(adj_node); | |
804 | spftree_parent = adj_node->lfa.spftree; | |
805 | assert(spftree_parent); | |
806 | reverse = true; | |
807 | } | |
808 | ||
809 | /* Get paths pvertex uses to reach vertex. */ | |
810 | vertex_child = isis_find_vertex(&spftree_parent->paths, | |
811 | &vertex->N, vertex->type); | |
812 | if (!vertex_child) | |
813 | goto parents; | |
814 | ||
815 | /* Check if any of these paths use the protected resource. */ | |
816 | for (ALL_LIST_ELEMENTS_RO(vertex_child->Adj_N, vnode, vadj)) | |
817 | if (spf_adj_check_is_affected(vadj->sadj, resource, | |
818 | spftree_root->sysid, | |
819 | reverse)) | |
820 | return true; | |
821 | ||
822 | parents: | |
823 | if (vertex_is_affected(spftree_root, adj_nodes, p_space, | |
824 | pvertex, resource)) | |
825 | return true; | |
826 | } | |
827 | ||
828 | return false; | |
829 | } | |
830 | ||
831 | /* Calculate set of nodes reachable without using the protected interface. */ | |
832 | static void lfa_calc_reach_nodes(struct isis_spftree *spftree, | |
833 | struct isis_spftree *spftree_root, | |
834 | const struct isis_spf_nodes *adj_nodes, | |
835 | bool p_space, | |
836 | const struct lfa_protected_resource *resource, | |
837 | struct isis_spf_nodes *nodes) | |
838 | { | |
839 | struct isis_vertex *vertex; | |
840 | struct listnode *node; | |
841 | ||
842 | for (ALL_QUEUE_ELEMENTS_RO(&spftree->paths, node, vertex)) { | |
843 | char buf[VID2STR_BUFFER]; | |
844 | ||
845 | if (!VTYPE_IS(vertex->type)) | |
846 | continue; | |
847 | ||
848 | /* Skip root node. */ | |
849 | if (!memcmp(vertex->N.id, spftree_root->sysid, ISIS_SYS_ID_LEN)) | |
850 | continue; | |
851 | ||
852 | /* Don't add the same node twice. */ | |
853 | if (isis_spf_node_find(nodes, vertex->N.id)) | |
854 | continue; | |
855 | ||
856 | if (IS_DEBUG_TILFA) | |
857 | zlog_debug("ISIS-TI-LFA: checking %s", | |
858 | vid2string(vertex, buf, sizeof(buf))); | |
859 | ||
860 | if (!vertex_is_affected(spftree_root, adj_nodes, p_space, | |
861 | vertex, resource)) { | |
862 | if (IS_DEBUG_TILFA) | |
863 | zlog_debug( | |
864 | "ISIS-TI-LFA: adding %s", | |
865 | vid2string(vertex, buf, sizeof(buf))); | |
866 | ||
867 | isis_spf_node_new(nodes, vertex->N.id); | |
868 | } | |
869 | } | |
870 | } | |
871 | ||
872 | /** | |
873 | * Helper function used to create an SPF tree structure and run reverse SPF on | |
874 | * it. | |
875 | * | |
876 | * @param spftree IS-IS SPF tree | |
877 | * | |
878 | * @return Pointer to new SPF tree structure. | |
879 | */ | |
880 | struct isis_spftree *isis_spf_reverse_run(const struct isis_spftree *spftree) | |
881 | { | |
882 | struct isis_spftree *spftree_reverse; | |
883 | ||
884 | spftree_reverse = isis_spftree_new( | |
885 | spftree->area, spftree->lspdb, spftree->sysid, spftree->level, | |
886 | spftree->tree_id, SPF_TYPE_REVERSE, | |
887 | F_SPFTREE_NO_ADJACENCIES | F_SPFTREE_NO_ROUTES); | |
888 | isis_run_spf(spftree_reverse); | |
889 | ||
890 | return spftree_reverse; | |
891 | } | |
892 | ||
893 | /* | |
894 | * Calculate the Extended P-space and Q-space associated to a given link | |
895 | * failure. | |
896 | */ | |
897 | static void lfa_calc_pq_spaces(struct isis_spftree *spftree_pc, | |
898 | const struct lfa_protected_resource *resource) | |
899 | { | |
900 | struct isis_spftree *spftree; | |
901 | struct isis_spftree *spftree_reverse; | |
902 | struct isis_spf_nodes *adj_nodes; | |
903 | struct isis_spf_node *adj_node; | |
904 | ||
905 | /* Obtain pre-failure SPTs and list of adjacent nodes. */ | |
906 | spftree = spftree_pc->lfa.old.spftree; | |
907 | spftree_reverse = spftree_pc->lfa.old.spftree_reverse; | |
908 | adj_nodes = &spftree->adj_nodes; | |
909 | ||
910 | if (IS_DEBUG_TILFA) | |
911 | zlog_debug("ISIS-TI-LFA: computing P-space (self)"); | |
912 | lfa_calc_reach_nodes(spftree, spftree, adj_nodes, true, resource, | |
913 | &spftree_pc->lfa.p_space); | |
914 | ||
915 | RB_FOREACH (adj_node, isis_spf_nodes, adj_nodes) { | |
916 | if (spf_adj_node_is_affected(adj_node, resource, | |
917 | spftree->sysid)) { | |
918 | if (IS_DEBUG_TILFA) | |
919 | zlog_debug( | |
920 | "ISIS-TI-LFA: computing Q-space (%s)", | |
921 | print_sys_hostname(adj_node->sysid)); | |
922 | ||
923 | /* | |
924 | * Compute the reverse SPF in the behalf of the node | |
925 | * adjacent to the failure. | |
926 | */ | |
927 | adj_node->lfa.spftree_reverse = | |
928 | isis_spf_reverse_run(adj_node->lfa.spftree); | |
929 | ||
930 | lfa_calc_reach_nodes(adj_node->lfa.spftree_reverse, | |
931 | spftree_reverse, adj_nodes, false, | |
932 | resource, | |
933 | &spftree_pc->lfa.q_space); | |
934 | } else { | |
935 | if (IS_DEBUG_TILFA) | |
936 | zlog_debug( | |
937 | "ISIS-TI-LFA: computing P-space (%s)", | |
938 | print_sys_hostname(adj_node->sysid)); | |
939 | lfa_calc_reach_nodes(adj_node->lfa.spftree, spftree, | |
940 | adj_nodes, true, resource, | |
941 | &adj_node->lfa.p_space); | |
942 | } | |
943 | } | |
944 | } | |
945 | ||
946 | /** | |
947 | * Compute the TI-LFA backup paths for a given protected interface. | |
948 | * | |
949 | * @param area IS-IS area | |
950 | * @param spftree IS-IS SPF tree | |
951 | * @param spftree_reverse IS-IS Reverse SPF tree | |
952 | * @param resource Protected resource | |
953 | * | |
954 | * @return Pointer to the post-convergence SPF tree | |
955 | */ | |
956 | struct isis_spftree *isis_tilfa_compute(struct isis_area *area, | |
957 | struct isis_spftree *spftree, | |
958 | struct isis_spftree *spftree_reverse, | |
959 | struct lfa_protected_resource *resource) | |
960 | { | |
961 | struct isis_spftree *spftree_pc; | |
962 | struct isis_spf_node *adj_node; | |
963 | ||
964 | if (IS_DEBUG_TILFA) | |
965 | zlog_debug("ISIS-TI-LFA: computing the P/Q spaces w.r.t. %s", | |
966 | lfa_protected_resource2str(resource)); | |
967 | ||
968 | /* Populate list of nodes affected by link failure. */ | |
969 | if (resource->type == LFA_NODE_PROTECTION) { | |
970 | isis_spf_node_list_init(&resource->nodes); | |
971 | RB_FOREACH (adj_node, isis_spf_nodes, &spftree->adj_nodes) { | |
972 | if (spf_adj_node_is_affected(adj_node, resource, | |
973 | spftree->sysid)) | |
974 | isis_spf_node_new(&resource->nodes, | |
975 | adj_node->sysid); | |
976 | } | |
977 | } | |
978 | ||
979 | /* Create post-convergence SPF tree. */ | |
980 | spftree_pc = isis_spftree_new(area, spftree->lspdb, spftree->sysid, | |
981 | spftree->level, spftree->tree_id, | |
982 | SPF_TYPE_TI_LFA, spftree->flags); | |
983 | spftree_pc->lfa.old.spftree = spftree; | |
984 | spftree_pc->lfa.old.spftree_reverse = spftree_reverse; | |
985 | spftree_pc->lfa.protected_resource = *resource; | |
986 | ||
987 | /* Compute the extended P-space and Q-space. */ | |
988 | lfa_calc_pq_spaces(spftree_pc, resource); | |
989 | ||
990 | if (IS_DEBUG_TILFA) | |
991 | zlog_debug( | |
992 | "ISIS-TI-LFA: computing the post convergence SPT w.r.t. %s", | |
993 | lfa_protected_resource2str(resource)); | |
994 | ||
995 | /* Re-run SPF in the local node to find the post-convergence paths. */ | |
996 | isis_run_spf(spftree_pc); | |
997 | ||
998 | /* Clear list of nodes affeted by link failure. */ | |
999 | if (resource->type == LFA_NODE_PROTECTION) | |
1000 | isis_spf_node_list_clear(&resource->nodes); | |
1001 | ||
1002 | return spftree_pc; | |
1003 | } | |
1004 | ||
1005 | /** | |
1006 | * Run forward SPF on all adjacent routers. | |
1007 | * | |
1008 | * @param spftree IS-IS SPF tree | |
1009 | * | |
1010 | * @return 0 on success, -1 otherwise | |
1011 | */ | |
1012 | int isis_spf_run_neighbors(struct isis_spftree *spftree) | |
1013 | { | |
1014 | struct isis_lsp *lsp; | |
1015 | struct isis_spf_node *adj_node; | |
1016 | ||
1017 | lsp = isis_root_system_lsp(spftree->lspdb, spftree->sysid); | |
1018 | if (!lsp) | |
1019 | return -1; | |
1020 | ||
1021 | RB_FOREACH (adj_node, isis_spf_nodes, &spftree->adj_nodes) { | |
1022 | if (IS_DEBUG_TILFA) | |
1023 | zlog_debug("ISIS-TI-LFA: running SPF on neighbor %s", | |
1024 | print_sys_hostname(adj_node->sysid)); | |
1025 | ||
1026 | /* Compute the SPT on behalf of the neighbor. */ | |
1027 | adj_node->lfa.spftree = isis_spftree_new( | |
1028 | spftree->area, spftree->lspdb, adj_node->sysid, | |
1029 | spftree->level, spftree->tree_id, SPF_TYPE_FORWARD, | |
1030 | F_SPFTREE_NO_ADJACENCIES | F_SPFTREE_NO_ROUTES); | |
1031 | isis_run_spf(adj_node->lfa.spftree); | |
1032 | } | |
1033 | ||
1034 | return 0; | |
1035 | } | |
1036 | ||
1037 | /** | |
1038 | * Run the TI-LFA algorithm for all proctected interfaces. | |
1039 | * | |
1040 | * @param area IS-IS area | |
1041 | * @param spftree IS-IS SPF tree | |
1042 | */ | |
1043 | void isis_spf_run_lfa(struct isis_area *area, struct isis_spftree *spftree) | |
1044 | { | |
1045 | struct isis_spftree *spftree_reverse; | |
1046 | struct isis_circuit *circuit; | |
1047 | struct listnode *node; | |
1048 | ||
1049 | /* Run reverse SPF locally. */ | |
1050 | spftree_reverse = isis_spf_reverse_run(spftree); | |
1051 | ||
1052 | /* Run forward SPF on all adjacent routers. */ | |
1053 | isis_spf_run_neighbors(spftree); | |
1054 | ||
1055 | /* Check which interfaces are protected. */ | |
1056 | for (ALL_LIST_ELEMENTS_RO(area->circuit_list, node, circuit)) { | |
1057 | struct lfa_protected_resource resource = {}; | |
1058 | struct isis_adjacency *adj; | |
1059 | struct isis_spftree *spftree_pc_link; | |
1060 | struct isis_spftree *spftree_pc_node; | |
1061 | static uint8_t null_sysid[ISIS_SYS_ID_LEN + 1]; | |
1062 | ||
1063 | if (!(circuit->is_type & spftree->level)) | |
1064 | continue; | |
1065 | ||
1066 | if (!circuit->tilfa_protection[spftree->level - 1]) | |
1067 | continue; | |
1068 | ||
1069 | /* Fill in the protected resource. */ | |
1070 | switch (circuit->circ_type) { | |
1071 | case CIRCUIT_T_BROADCAST: | |
1072 | if (spftree->level == 1) | |
1073 | memcpy(resource.adjacency, | |
1074 | circuit->u.bc.l1_desig_is, | |
1075 | ISIS_SYS_ID_LEN + 1); | |
1076 | else | |
1077 | memcpy(resource.adjacency, | |
1078 | circuit->u.bc.l2_desig_is, | |
1079 | ISIS_SYS_ID_LEN + 1); | |
1080 | /* Do nothing if no DR was elected yet. */ | |
1081 | if (!memcmp(resource.adjacency, null_sysid, | |
1082 | ISIS_SYS_ID_LEN + 1)) | |
1083 | continue; | |
1084 | break; | |
1085 | case CIRCUIT_T_P2P: | |
1086 | adj = circuit->u.p2p.neighbor; | |
1087 | if (!adj) | |
1088 | continue; | |
1089 | memcpy(resource.adjacency, adj->sysid, ISIS_SYS_ID_LEN); | |
1090 | LSP_PSEUDO_ID(resource.adjacency) = 0; | |
1091 | break; | |
1092 | default: | |
1093 | continue; | |
1094 | } | |
1095 | ||
1096 | /* Compute node protecting repair paths first (if necessary). */ | |
1097 | if (circuit->tilfa_node_protection[spftree->level - 1]) { | |
1098 | resource.type = LFA_NODE_PROTECTION; | |
1099 | spftree_pc_node = isis_tilfa_compute( | |
1100 | area, spftree, spftree_reverse, &resource); | |
1101 | isis_spftree_del(spftree_pc_node); | |
1102 | } | |
1103 | ||
1104 | /* Compute link protecting repair paths. */ | |
1105 | resource.type = LFA_LINK_PROTECTION; | |
1106 | spftree_pc_link = isis_tilfa_compute( | |
1107 | area, spftree, spftree_reverse, &resource); | |
1108 | isis_spftree_del(spftree_pc_link); | |
1109 | } | |
1110 | ||
1111 | isis_spftree_del(spftree_reverse); | |
1112 | } |