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