]>
Commit | Line | Data |
---|---|---|
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 | #include "plist.h" | |
29 | #include "zclient.h" | |
30 | ||
31 | #include "isis_common.h" | |
32 | #include "isisd.h" | |
33 | #include "isis_misc.h" | |
34 | #include "isis_adjacency.h" | |
35 | #include "isis_circuit.h" | |
36 | #include "isis_lsp.h" | |
37 | #include "isis_spf.h" | |
38 | #include "isis_route.h" | |
39 | #include "isis_mt.h" | |
40 | #include "isis_tlvs.h" | |
41 | #include "isis_spf_private.h" | |
42 | #include "isis_zebra.h" | |
43 | #include "isis_errors.h" | |
44 | ||
45 | DEFINE_MTYPE_STATIC(ISISD, ISIS_SPF_NODE, "ISIS SPF Node"); | |
46 | DEFINE_MTYPE_STATIC(ISISD, ISIS_LFA_TIEBREAKER, "ISIS LFA Tiebreaker"); | |
47 | DEFINE_MTYPE_STATIC(ISISD, ISIS_LFA_EXCL_IFACE, "ISIS LFA Excluded Interface"); | |
48 | DEFINE_MTYPE_STATIC(ISISD, ISIS_RLFA, "ISIS Remote LFA"); | |
49 | DEFINE_MTYPE(ISISD, ISIS_NEXTHOP_LABELS, "ISIS nexthop MPLS labels"); | |
50 | ||
51 | static inline int isis_spf_node_compare(const struct isis_spf_node *a, | |
52 | const struct isis_spf_node *b) | |
53 | { | |
54 | return memcmp(a->sysid, b->sysid, sizeof(a->sysid)); | |
55 | } | |
56 | RB_GENERATE(isis_spf_nodes, isis_spf_node, entry, isis_spf_node_compare) | |
57 | ||
58 | /** | |
59 | * Initialize list of SPF nodes. | |
60 | * | |
61 | * @param nodes List of SPF nodes | |
62 | */ | |
63 | void isis_spf_node_list_init(struct isis_spf_nodes *nodes) | |
64 | { | |
65 | RB_INIT(isis_spf_nodes, nodes); | |
66 | } | |
67 | ||
68 | /** | |
69 | * Clear list of SPF nodes, releasing all allocated memory. | |
70 | * | |
71 | * @param nodes List of SPF nodes | |
72 | */ | |
73 | void isis_spf_node_list_clear(struct isis_spf_nodes *nodes) | |
74 | { | |
75 | while (!RB_EMPTY(isis_spf_nodes, nodes)) { | |
76 | struct isis_spf_node *node = RB_ROOT(isis_spf_nodes, nodes); | |
77 | ||
78 | if (node->adjacencies) | |
79 | list_delete(&node->adjacencies); | |
80 | if (node->lfa.spftree) | |
81 | isis_spftree_del(node->lfa.spftree); | |
82 | if (node->lfa.spftree_reverse) | |
83 | isis_spftree_del(node->lfa.spftree_reverse); | |
84 | isis_spf_node_list_clear(&node->lfa.p_space); | |
85 | RB_REMOVE(isis_spf_nodes, nodes, node); | |
86 | XFREE(MTYPE_ISIS_SPF_NODE, node); | |
87 | } | |
88 | } | |
89 | ||
90 | /** | |
91 | * Add new node to list of SPF nodes. | |
92 | * | |
93 | * @param nodes List of SPF nodes | |
94 | * @param sysid Node System ID | |
95 | * | |
96 | * @return Pointer to new IS-IS SPF node structure. | |
97 | */ | |
98 | struct isis_spf_node *isis_spf_node_new(struct isis_spf_nodes *nodes, | |
99 | const uint8_t *sysid) | |
100 | { | |
101 | struct isis_spf_node *node; | |
102 | ||
103 | node = XCALLOC(MTYPE_ISIS_SPF_NODE, sizeof(*node)); | |
104 | memcpy(node->sysid, sysid, sizeof(node->sysid)); | |
105 | node->adjacencies = list_new(); | |
106 | isis_spf_node_list_init(&node->lfa.p_space); | |
107 | RB_INSERT(isis_spf_nodes, nodes, node); | |
108 | ||
109 | return node; | |
110 | } | |
111 | ||
112 | /** | |
113 | * Lookup SPF node by its System ID on the given list. | |
114 | * | |
115 | * @param nodes List of SPF nodes | |
116 | * @param sysid Node System ID | |
117 | * | |
118 | * @return Pointer to SPF node if found, NULL otherwise | |
119 | */ | |
120 | struct isis_spf_node *isis_spf_node_find(const struct isis_spf_nodes *nodes, | |
121 | const uint8_t *sysid) | |
122 | { | |
123 | struct isis_spf_node node = {}; | |
124 | ||
125 | memcpy(node.sysid, sysid, sizeof(node.sysid)); | |
126 | return RB_FIND(isis_spf_nodes, nodes, &node); | |
127 | } | |
128 | ||
129 | /** | |
130 | * LFA tiebreaker RB-tree comparison function. | |
131 | * | |
132 | * @param a First LFA tiebreaker | |
133 | * @param b Second LFA tiebreaker | |
134 | * | |
135 | * @return -1 (a < b), 0 (a == b) or +1 (a > b) | |
136 | */ | |
137 | int lfa_tiebreaker_cmp(const struct lfa_tiebreaker *a, | |
138 | const struct lfa_tiebreaker *b) | |
139 | { | |
140 | if (a->index < b->index) | |
141 | return -1; | |
142 | if (a->index > b->index) | |
143 | return 1; | |
144 | ||
145 | return a->type - b->type; | |
146 | } | |
147 | ||
148 | /** | |
149 | * Initialize list of LFA tie-breakers. | |
150 | * | |
151 | * @param area IS-IS area | |
152 | * @param level IS-IS level | |
153 | */ | |
154 | void isis_lfa_tiebreakers_init(struct isis_area *area, int level) | |
155 | { | |
156 | lfa_tiebreaker_tree_init(&area->lfa_tiebreakers[level - 1]); | |
157 | } | |
158 | ||
159 | /** | |
160 | * Clear list of LFA tie-breakers, releasing all allocated memory. | |
161 | * | |
162 | * @param area IS-IS area | |
163 | * @param level IS-IS level | |
164 | */ | |
165 | void isis_lfa_tiebreakers_clear(struct isis_area *area, int level) | |
166 | { | |
167 | while (lfa_tiebreaker_tree_count(&area->lfa_tiebreakers[level - 1]) | |
168 | > 0) { | |
169 | struct lfa_tiebreaker *tie_b; | |
170 | ||
171 | tie_b = lfa_tiebreaker_tree_first( | |
172 | &area->lfa_tiebreakers[level - 1]); | |
173 | isis_lfa_tiebreaker_delete(area, level, tie_b); | |
174 | } | |
175 | } | |
176 | ||
177 | /** | |
178 | * Add new LFA tie-breaker to list of LFA tie-breakers. | |
179 | * | |
180 | * @param area IS-IS area | |
181 | * @param level IS-IS level | |
182 | * @param index LFA tie-breaker index | |
183 | * @param type LFA tie-breaker type | |
184 | * | |
185 | * @return Pointer to new LFA tie-breaker structure. | |
186 | */ | |
187 | struct lfa_tiebreaker *isis_lfa_tiebreaker_add(struct isis_area *area, | |
188 | int level, uint8_t index, | |
189 | enum lfa_tiebreaker_type type) | |
190 | { | |
191 | struct lfa_tiebreaker *tie_b; | |
192 | ||
193 | tie_b = XCALLOC(MTYPE_ISIS_LFA_TIEBREAKER, sizeof(*tie_b)); | |
194 | tie_b->index = index; | |
195 | tie_b->type = type; | |
196 | tie_b->area = area; | |
197 | lfa_tiebreaker_tree_add(&area->lfa_tiebreakers[level - 1], tie_b); | |
198 | ||
199 | return tie_b; | |
200 | } | |
201 | ||
202 | /** | |
203 | * Remove LFA tie-breaker from list of LFA tie-breakers. | |
204 | * | |
205 | * @param area IS-IS area | |
206 | * @param level IS-IS level | |
207 | * @param tie_b Pointer to LFA tie-breaker structure | |
208 | */ | |
209 | void isis_lfa_tiebreaker_delete(struct isis_area *area, int level, | |
210 | struct lfa_tiebreaker *tie_b) | |
211 | { | |
212 | lfa_tiebreaker_tree_del(&area->lfa_tiebreakers[level - 1], tie_b); | |
213 | XFREE(MTYPE_ISIS_LFA_TIEBREAKER, tie_b); | |
214 | } | |
215 | ||
216 | static bool lfa_excl_interface_hash_cmp(const void *value1, const void *value2) | |
217 | { | |
218 | return strmatch(value1, value2); | |
219 | } | |
220 | ||
221 | static unsigned int lfa_excl_interface_hash_make(const void *value) | |
222 | { | |
223 | return string_hash_make(value); | |
224 | } | |
225 | ||
226 | static void *lfa_excl_interface_hash_alloc(void *p) | |
227 | { | |
228 | return XSTRDUP(MTYPE_ISIS_LFA_EXCL_IFACE, p); | |
229 | } | |
230 | ||
231 | static void lfa_excl_interface_hash_free(void *arg) | |
232 | { | |
233 | XFREE(MTYPE_ISIS_LFA_EXCL_IFACE, arg); | |
234 | } | |
235 | ||
236 | /** | |
237 | * Initialize hash table of LFA excluded interfaces. | |
238 | * | |
239 | * @param circuit IS-IS interface | |
240 | * @param level IS-IS level | |
241 | */ | |
242 | void isis_lfa_excluded_ifaces_init(struct isis_circuit *circuit, int level) | |
243 | { | |
244 | circuit->lfa_excluded_ifaces[level - 1] = hash_create( | |
245 | lfa_excl_interface_hash_make, lfa_excl_interface_hash_cmp, | |
246 | "LFA Excluded Interfaces"); | |
247 | } | |
248 | ||
249 | /** | |
250 | * Clear hash table of LFA excluded interfaces, releasing all allocated memory. | |
251 | * | |
252 | * @param nodes List of SPF nodes | |
253 | */ | |
254 | void isis_lfa_excluded_ifaces_clear(struct isis_circuit *circuit, int level) | |
255 | { | |
256 | hash_clean(circuit->lfa_excluded_ifaces[level - 1], | |
257 | lfa_excl_interface_hash_free); | |
258 | } | |
259 | ||
260 | /** | |
261 | * Add new interface to hash table of excluded interfaces. | |
262 | * | |
263 | * @param circuit IS-IS interface | |
264 | * @param level IS-IS level | |
265 | * @param ifname Excluded interface name | |
266 | */ | |
267 | void isis_lfa_excluded_iface_add(struct isis_circuit *circuit, int level, | |
268 | const char *ifname) | |
269 | { | |
270 | hash_get(circuit->lfa_excluded_ifaces[level - 1], (char *)ifname, | |
271 | lfa_excl_interface_hash_alloc); | |
272 | } | |
273 | ||
274 | /** | |
275 | * Remove interface from hash table of excluded interfaces. | |
276 | * | |
277 | * @param circuit IS-IS interface | |
278 | * @param level IS-IS level | |
279 | * @param ifname Excluded interface name | |
280 | */ | |
281 | void isis_lfa_excluded_iface_delete(struct isis_circuit *circuit, int level, | |
282 | const char *ifname) | |
283 | { | |
284 | char *found; | |
285 | ||
286 | found = hash_lookup(circuit->lfa_excluded_ifaces[level - 1], | |
287 | (char *)ifname); | |
288 | if (found) { | |
289 | hash_release(circuit->lfa_excluded_ifaces[level - 1], found); | |
290 | lfa_excl_interface_hash_free(found); | |
291 | } | |
292 | } | |
293 | ||
294 | /** | |
295 | * Lookup excluded interface. | |
296 | * | |
297 | * @param circuit IS-IS interface | |
298 | * @param level IS-IS level | |
299 | * @param ifname Excluded interface name | |
300 | */ | |
301 | bool isis_lfa_excluded_iface_check(struct isis_circuit *circuit, int level, | |
302 | const char *ifname) | |
303 | { | |
304 | return hash_lookup(circuit->lfa_excluded_ifaces[level - 1], | |
305 | (char *)ifname); | |
306 | } | |
307 | ||
308 | /** | |
309 | * Check if a given IS-IS adjacency needs to be excised when computing the SPF | |
310 | * post-convergence tree. | |
311 | * | |
312 | * @param spftree IS-IS SPF tree | |
313 | * @param id Adjacency System ID (or LAN ID of the designated router | |
314 | * for broadcast interfaces) | |
315 | * | |
316 | * @return true if the adjacency needs to be excised, false | |
317 | * otherwise | |
318 | */ | |
319 | bool isis_lfa_excise_adj_check(const struct isis_spftree *spftree, | |
320 | const uint8_t *id) | |
321 | { | |
322 | const struct lfa_protected_resource *resource; | |
323 | ||
324 | if (spftree->type != SPF_TYPE_RLFA && spftree->type != SPF_TYPE_TI_LFA) | |
325 | return false; | |
326 | ||
327 | /* | |
328 | * Adjacencies formed over the failed interface should be excised both | |
329 | * when using link and node protection. | |
330 | */ | |
331 | resource = &spftree->lfa.protected_resource; | |
332 | if (!memcmp(resource->adjacency, id, ISIS_SYS_ID_LEN + 1)) | |
333 | return true; | |
334 | ||
335 | return false; | |
336 | } | |
337 | ||
338 | /** | |
339 | * Check if a given IS-IS node needs to be excised when computing the SPF | |
340 | * post-convergence tree. | |
341 | * | |
342 | * @param spftree IS-IS SPF tree | |
343 | * @param id Node System ID | |
344 | * | |
345 | * @return true if the node needs to be excised, false otherwise | |
346 | */ | |
347 | bool isis_lfa_excise_node_check(const struct isis_spftree *spftree, | |
348 | const uint8_t *id) | |
349 | { | |
350 | const struct lfa_protected_resource *resource; | |
351 | ||
352 | if (spftree->type != SPF_TYPE_TI_LFA) | |
353 | return false; | |
354 | ||
355 | /* | |
356 | * When using node protection, nodes reachable over the failed interface | |
357 | * must be excised. | |
358 | */ | |
359 | resource = &spftree->lfa.protected_resource; | |
360 | if (resource->type == LFA_LINK_PROTECTION) | |
361 | return false; | |
362 | ||
363 | if (isis_spf_node_find(&resource->nodes, id)) | |
364 | return true; | |
365 | ||
366 | return false; | |
367 | } | |
368 | ||
369 | struct tilfa_find_pnode_prefix_sid_args { | |
370 | uint32_t sid_index; | |
371 | }; | |
372 | ||
373 | static int tilfa_find_pnode_prefix_sid_cb(const struct prefix *prefix, | |
374 | uint32_t metric, bool external, | |
375 | struct isis_subtlvs *subtlvs, | |
376 | void *arg) | |
377 | { | |
378 | struct tilfa_find_pnode_prefix_sid_args *args = arg; | |
379 | struct isis_prefix_sid *psid; | |
380 | ||
381 | if (!subtlvs || subtlvs->prefix_sids.count == 0) | |
382 | return LSP_ITER_CONTINUE; | |
383 | ||
384 | psid = (struct isis_prefix_sid *)subtlvs->prefix_sids.head; | |
385 | ||
386 | /* Require the node flag to be set. */ | |
387 | if (!CHECK_FLAG(psid->flags, ISIS_PREFIX_SID_NODE)) | |
388 | return LSP_ITER_CONTINUE; | |
389 | ||
390 | args->sid_index = psid->value; | |
391 | ||
392 | return LSP_ITER_STOP; | |
393 | } | |
394 | ||
395 | /* Find Prefix-SID associated to a System ID. */ | |
396 | static uint32_t tilfa_find_pnode_prefix_sid(struct isis_spftree *spftree, | |
397 | const uint8_t *sysid) | |
398 | { | |
399 | struct isis_lsp *lsp; | |
400 | struct tilfa_find_pnode_prefix_sid_args args; | |
401 | ||
402 | lsp = isis_root_system_lsp(spftree->lspdb, sysid); | |
403 | if (!lsp) | |
404 | return UINT32_MAX; | |
405 | ||
406 | args.sid_index = UINT32_MAX; | |
407 | isis_lsp_iterate_ip_reach(lsp, spftree->family, spftree->mtid, | |
408 | tilfa_find_pnode_prefix_sid_cb, &args); | |
409 | ||
410 | return args.sid_index; | |
411 | } | |
412 | ||
413 | struct tilfa_find_qnode_adj_sid_args { | |
414 | const uint8_t *qnode_sysid; | |
415 | mpls_label_t label; | |
416 | }; | |
417 | ||
418 | static int tilfa_find_qnode_adj_sid_cb(const uint8_t *id, uint32_t metric, | |
419 | bool oldmetric, | |
420 | struct isis_ext_subtlvs *subtlvs, | |
421 | void *arg) | |
422 | { | |
423 | struct tilfa_find_qnode_adj_sid_args *args = arg; | |
424 | struct isis_adj_sid *adj_sid; | |
425 | ||
426 | if (memcmp(id, args->qnode_sysid, ISIS_SYS_ID_LEN)) | |
427 | return LSP_ITER_CONTINUE; | |
428 | if (!subtlvs || subtlvs->adj_sid.count == 0) | |
429 | return LSP_ITER_CONTINUE; | |
430 | ||
431 | adj_sid = (struct isis_adj_sid *)subtlvs->adj_sid.head; | |
432 | args->label = adj_sid->sid; | |
433 | ||
434 | return LSP_ITER_STOP; | |
435 | } | |
436 | ||
437 | /* Find Adj-SID associated to a pair of System IDs. */ | |
438 | static mpls_label_t tilfa_find_qnode_adj_sid(struct isis_spftree *spftree, | |
439 | const uint8_t *source_sysid, | |
440 | const uint8_t *qnode_sysid) | |
441 | { | |
442 | struct isis_lsp *lsp; | |
443 | struct tilfa_find_qnode_adj_sid_args args; | |
444 | ||
445 | lsp = isis_root_system_lsp(spftree->lspdb, source_sysid); | |
446 | if (!lsp) | |
447 | return MPLS_INVALID_LABEL; | |
448 | ||
449 | args.qnode_sysid = qnode_sysid; | |
450 | args.label = MPLS_INVALID_LABEL; | |
451 | isis_lsp_iterate_is_reach(lsp, spftree->mtid, | |
452 | tilfa_find_qnode_adj_sid_cb, &args); | |
453 | ||
454 | return args.label; | |
455 | } | |
456 | ||
457 | /* | |
458 | * Compute the MPLS label stack associated to a TI-LFA repair list. This | |
459 | * needs to be computed separately for each adjacency since different | |
460 | * neighbors can have different SRGBs. | |
461 | */ | |
462 | static struct mpls_label_stack * | |
463 | tilfa_compute_label_stack(struct lspdb_head *lspdb, | |
464 | const struct isis_spf_adj *sadj, | |
465 | const struct list *repair_list) | |
466 | { | |
467 | struct mpls_label_stack *label_stack; | |
468 | struct isis_tilfa_sid *sid; | |
469 | struct listnode *node; | |
470 | size_t i = 0; | |
471 | ||
472 | /* Allocate label stack. */ | |
473 | label_stack = XCALLOC(MTYPE_ISIS_NEXTHOP_LABELS, | |
474 | sizeof(struct mpls_label_stack) | |
475 | + listcount(repair_list) | |
476 | * sizeof(mpls_label_t)); | |
477 | label_stack->num_labels = listcount(repair_list); | |
478 | ||
479 | for (ALL_LIST_ELEMENTS_RO(repair_list, node, sid)) { | |
480 | const uint8_t *target_node; | |
481 | struct isis_sr_block *srgb; | |
482 | mpls_label_t label; | |
483 | ||
484 | switch (sid->type) { | |
485 | case TILFA_SID_PREFIX: | |
486 | if (sid->value.index.remote) | |
487 | target_node = sid->value.index.remote_sysid; | |
488 | else | |
489 | target_node = sadj->id; | |
490 | srgb = isis_sr_find_srgb(lspdb, target_node); | |
491 | if (!srgb) { | |
492 | zlog_warn("%s: SRGB not found for node %s", | |
493 | __func__, | |
494 | print_sys_hostname(target_node)); | |
495 | goto error; | |
496 | } | |
497 | ||
498 | /* Check if the SID index falls inside the SRGB. */ | |
499 | if (sid->value.index.value >= srgb->range_size) { | |
500 | flog_warn( | |
501 | EC_ISIS_SID_OVERFLOW, | |
502 | "%s: SID index %u falls outside remote SRGB range", | |
503 | __func__, sid->value.index.value); | |
504 | goto error; | |
505 | } | |
506 | ||
507 | /* | |
508 | * Prefix-SID: map SID index to label value within the | |
509 | * SRGB. | |
510 | */ | |
511 | label = srgb->lower_bound + sid->value.index.value; | |
512 | break; | |
513 | case TILFA_SID_ADJ: | |
514 | /* Adj-SID: absolute label value can be used directly */ | |
515 | label = sid->value.label; | |
516 | break; | |
517 | default: | |
518 | flog_err(EC_LIB_DEVELOPMENT, | |
519 | "%s: unknown TI-LFA SID type [%u]", __func__, | |
520 | sid->type); | |
521 | exit(1); | |
522 | } | |
523 | label_stack->label[i++] = label; | |
524 | } | |
525 | ||
526 | return label_stack; | |
527 | ||
528 | error: | |
529 | XFREE(MTYPE_ISIS_NEXTHOP_LABELS, label_stack); | |
530 | return NULL; | |
531 | } | |
532 | ||
533 | static int tilfa_repair_list_apply(struct isis_spftree *spftree, | |
534 | struct isis_vertex *vertex_dest, | |
535 | const struct isis_vertex *vertex_pnode, | |
536 | const struct list *repair_list) | |
537 | { | |
538 | struct isis_vertex_adj *vadj; | |
539 | struct listnode *node; | |
540 | ||
541 | for (ALL_LIST_ELEMENTS_RO(vertex_dest->Adj_N, node, vadj)) { | |
542 | struct isis_spf_adj *sadj = vadj->sadj; | |
543 | struct mpls_label_stack *label_stack; | |
544 | ||
545 | /* | |
546 | * Don't try to apply the repair list if one was already applied | |
547 | * before (can't have ECMP past the P-node). | |
548 | */ | |
549 | if (vadj->label_stack) | |
550 | continue; | |
551 | ||
552 | if (!isis_vertex_adj_exists(spftree, vertex_pnode, sadj)) | |
553 | continue; | |
554 | ||
555 | label_stack = tilfa_compute_label_stack(spftree->lspdb, sadj, | |
556 | repair_list); | |
557 | if (!label_stack) { | |
558 | char buf[VID2STR_BUFFER]; | |
559 | ||
560 | vid2string(vertex_dest, buf, sizeof(buf)); | |
561 | zlog_warn( | |
562 | "%s: %s %s adjacency %s: failed to compute label stack", | |
563 | __func__, vtype2string(vertex_dest->type), buf, | |
564 | print_sys_hostname(sadj->id)); | |
565 | return -1; | |
566 | } | |
567 | ||
568 | vadj->label_stack = label_stack; | |
569 | } | |
570 | ||
571 | return 0; | |
572 | } | |
573 | ||
574 | /* | |
575 | * Check if a node belongs to the extended P-space corresponding to a given | |
576 | * destination. | |
577 | */ | |
578 | static bool lfa_ext_p_space_check(const struct isis_spftree *spftree_pc, | |
579 | const struct isis_vertex *vertex_dest, | |
580 | const struct isis_vertex *vertex) | |
581 | { | |
582 | struct isis_spftree *spftree_old = spftree_pc->lfa.old.spftree; | |
583 | struct isis_vertex_adj *vadj; | |
584 | struct listnode *node; | |
585 | ||
586 | /* Check the local P-space first. */ | |
587 | if (isis_spf_node_find(&spftree_pc->lfa.p_space, vertex->N.id)) | |
588 | return true; | |
589 | ||
590 | /* | |
591 | * Check the P-space of the adjacent routers used to reach the | |
592 | * destination. | |
593 | */ | |
594 | for (ALL_LIST_ELEMENTS_RO(vertex_dest->Adj_N, node, vadj)) { | |
595 | struct isis_spf_adj *sadj = vadj->sadj; | |
596 | struct isis_spf_node *adj_node; | |
597 | ||
598 | adj_node = | |
599 | isis_spf_node_find(&spftree_old->adj_nodes, sadj->id); | |
600 | if (!adj_node) | |
601 | continue; | |
602 | ||
603 | if (isis_spf_node_find(&adj_node->lfa.p_space, vertex->N.id)) | |
604 | return true; | |
605 | } | |
606 | ||
607 | return false; | |
608 | } | |
609 | ||
610 | /* Check if a node belongs to the Q-space. */ | |
611 | static bool lfa_q_space_check(const struct isis_spftree *spftree_pc, | |
612 | const struct isis_vertex *vertex) | |
613 | { | |
614 | return isis_spf_node_find(&spftree_pc->lfa.q_space, vertex->N.id); | |
615 | } | |
616 | ||
617 | /* This is a recursive function. */ | |
618 | static int tilfa_build_repair_list(struct isis_spftree *spftree_pc, | |
619 | struct isis_vertex *vertex_dest, | |
620 | const struct isis_vertex *vertex, | |
621 | const struct isis_vertex *vertex_child, | |
622 | struct isis_spf_nodes *used_pnodes, | |
623 | struct list *repair_list) | |
624 | { | |
625 | struct isis_vertex *pvertex; | |
626 | struct listnode *node; | |
627 | bool is_pnode, is_qnode; | |
628 | char buf[VID2STR_BUFFER]; | |
629 | struct isis_tilfa_sid sid_dest = {}, sid_qnode = {}, sid_pnode = {}; | |
630 | uint32_t sid_index; | |
631 | mpls_label_t label_qnode; | |
632 | ||
633 | if (IS_DEBUG_LFA) { | |
634 | vid2string(vertex, buf, sizeof(buf)); | |
635 | zlog_debug("ISIS-LFA: vertex %s %s", vtype2string(vertex->type), | |
636 | buf); | |
637 | } | |
638 | ||
639 | /* Push original Prefix-SID label when necessary. */ | |
640 | if (VTYPE_IP(vertex->type) && vertex->N.ip.sr.present) { | |
641 | pvertex = listnode_head(vertex->parents); | |
642 | assert(pvertex); | |
643 | ||
644 | sid_index = vertex->N.ip.sr.sid.value; | |
645 | if (IS_DEBUG_LFA) | |
646 | zlog_debug( | |
647 | "ISIS-LFA: pushing Prefix-SID to %pFX (index %u)", | |
648 | &vertex->N.ip.p.dest, sid_index); | |
649 | sid_dest.type = TILFA_SID_PREFIX; | |
650 | sid_dest.value.index.value = sid_index; | |
651 | sid_dest.value.index.remote = true; | |
652 | memcpy(sid_dest.value.index.remote_sysid, pvertex->N.id, | |
653 | sizeof(sid_dest.value.index.remote_sysid)); | |
654 | listnode_add_head(repair_list, &sid_dest); | |
655 | } | |
656 | ||
657 | if (!vertex_child) | |
658 | goto parents; | |
659 | if (vertex->type != VTYPE_NONPSEUDO_IS | |
660 | && vertex->type != VTYPE_NONPSEUDO_TE_IS) | |
661 | goto parents; | |
662 | if (!VTYPE_IS(vertex_child->type)) | |
663 | vertex_child = NULL; | |
664 | ||
665 | /* Check if node is part of the extended P-space and/or Q-space. */ | |
666 | is_pnode = lfa_ext_p_space_check(spftree_pc, vertex_dest, vertex); | |
667 | is_qnode = lfa_q_space_check(spftree_pc, vertex); | |
668 | ||
669 | /* Push Adj-SID label when necessary. */ | |
670 | if ((!is_qnode | |
671 | || spftree_pc->lfa.protected_resource.type == LFA_NODE_PROTECTION) | |
672 | && vertex_child) { | |
673 | /* | |
674 | * If vertex is the penultimate hop router, then pushing an | |
675 | * Adj-SID towards the final hop means that the No-PHP flag of | |
676 | * the original Prefix-SID must be honored. We do that by | |
677 | * removing the previously added Prefix-SID from the repair list | |
678 | * when those conditions are met. | |
679 | */ | |
680 | if (vertex->depth == (vertex_dest->depth - 2) | |
681 | && VTYPE_IP(vertex_dest->type) | |
682 | && vertex_dest->N.ip.sr.present | |
683 | && !CHECK_FLAG(vertex_dest->N.ip.sr.sid.flags, | |
684 | ISIS_PREFIX_SID_NO_PHP)) { | |
685 | list_delete_all_node(repair_list); | |
686 | } | |
687 | ||
688 | label_qnode = tilfa_find_qnode_adj_sid(spftree_pc, vertex->N.id, | |
689 | vertex_child->N.id); | |
690 | if (label_qnode == MPLS_INVALID_LABEL) { | |
691 | zlog_warn("ISIS-LFA: failed to find %s->%s Adj-SID", | |
692 | print_sys_hostname(vertex->N.id), | |
693 | print_sys_hostname(vertex_child->N.id)); | |
694 | return -1; | |
695 | } | |
696 | if (IS_DEBUG_LFA) | |
697 | zlog_debug( | |
698 | "ISIS-LFA: pushing %s->%s Adj-SID (label %u)", | |
699 | print_sys_hostname(vertex->N.id), | |
700 | print_sys_hostname(vertex_child->N.id), | |
701 | label_qnode); | |
702 | sid_qnode.type = TILFA_SID_ADJ; | |
703 | sid_qnode.value.label = label_qnode; | |
704 | listnode_add_head(repair_list, &sid_qnode); | |
705 | } | |
706 | ||
707 | /* Push Prefix-SID label when necessary. */ | |
708 | if (is_pnode) { | |
709 | /* The same P-node can't be used more than once. */ | |
710 | if (isis_spf_node_find(used_pnodes, vertex->N.id)) { | |
711 | if (IS_DEBUG_LFA) | |
712 | zlog_debug( | |
713 | "ISIS-LFA: skipping already used P-node"); | |
714 | return 0; | |
715 | } | |
716 | isis_spf_node_new(used_pnodes, vertex->N.id); | |
717 | ||
718 | if (!vertex_child) { | |
719 | if (IS_DEBUG_LFA) | |
720 | zlog_debug( | |
721 | "ISIS-LFA: destination is within Ext-P-Space"); | |
722 | return 0; | |
723 | } | |
724 | ||
725 | sid_index = | |
726 | tilfa_find_pnode_prefix_sid(spftree_pc, vertex->N.id); | |
727 | if (sid_index == UINT32_MAX) { | |
728 | zlog_warn( | |
729 | "ISIS-LFA: failed to find Prefix-SID corresponding to PQ-node %s", | |
730 | print_sys_hostname(vertex->N.id)); | |
731 | return -1; | |
732 | } | |
733 | ||
734 | if (IS_DEBUG_LFA) | |
735 | zlog_debug( | |
736 | "ISIS-LFA: pushing Node-SID to %s (index %u)", | |
737 | print_sys_hostname(vertex->N.id), sid_index); | |
738 | sid_pnode.type = TILFA_SID_PREFIX; | |
739 | sid_pnode.value.index.value = sid_index; | |
740 | listnode_add_head(repair_list, &sid_pnode); | |
741 | ||
742 | /* Apply repair list. */ | |
743 | if (spftree_pc->area->srdb.config.msd | |
744 | && listcount(repair_list) | |
745 | > spftree_pc->area->srdb.config.msd) { | |
746 | zlog_warn( | |
747 | "ISIS-LFA: list of repair segments exceeds locally configured MSD (%u > %u)", | |
748 | listcount(repair_list), | |
749 | spftree_pc->area->srdb.config.msd); | |
750 | return -1; | |
751 | } | |
752 | if (tilfa_repair_list_apply(spftree_pc, vertex_dest, vertex, | |
753 | repair_list) | |
754 | != 0) | |
755 | return -1; | |
756 | return 0; | |
757 | } | |
758 | ||
759 | parents: | |
760 | for (ALL_LIST_ELEMENTS_RO(vertex->parents, node, pvertex)) { | |
761 | struct list *repair_list_parent; | |
762 | bool ecmp; | |
763 | int ret; | |
764 | ||
765 | ecmp = (listcount(vertex->parents) > 1) ? true : false; | |
766 | repair_list_parent = ecmp ? list_dup(repair_list) : repair_list; | |
767 | ret = tilfa_build_repair_list(spftree_pc, vertex_dest, pvertex, | |
768 | vertex, used_pnodes, | |
769 | repair_list_parent); | |
770 | if (ecmp) | |
771 | list_delete(&repair_list_parent); | |
772 | if (ret != 0) | |
773 | return ret; | |
774 | } | |
775 | ||
776 | return 0; | |
777 | } | |
778 | ||
779 | static const char *lfa_protection_type2str(enum lfa_protection_type type) | |
780 | { | |
781 | switch (type) { | |
782 | case LFA_LINK_PROTECTION: | |
783 | return "link protection"; | |
784 | case LFA_NODE_PROTECTION: | |
785 | return "node protection"; | |
786 | default: | |
787 | return "unknown protection type"; | |
788 | } | |
789 | } | |
790 | ||
791 | static const char * | |
792 | lfa_protected_resource2str(const struct lfa_protected_resource *resource) | |
793 | { | |
794 | const uint8_t *fail_id; | |
795 | static char buffer[128]; | |
796 | ||
797 | fail_id = resource->adjacency; | |
798 | snprintf(buffer, sizeof(buffer), "%s.%u's failure (%s)", | |
799 | print_sys_hostname(fail_id), LSP_PSEUDO_ID(fail_id), | |
800 | lfa_protection_type2str(resource->type)); | |
801 | ||
802 | return buffer; | |
803 | } | |
804 | ||
805 | static bool | |
806 | spf_adj_check_is_affected(const struct isis_spf_adj *sadj, | |
807 | const struct lfa_protected_resource *resource, | |
808 | const uint8_t *root_sysid, bool reverse) | |
809 | { | |
810 | if (!!CHECK_FLAG(sadj->flags, F_ISIS_SPF_ADJ_BROADCAST) | |
811 | != !!LSP_PSEUDO_ID(resource->adjacency)) | |
812 | return false; | |
813 | ||
814 | if (CHECK_FLAG(sadj->flags, F_ISIS_SPF_ADJ_BROADCAST)) { | |
815 | if (!memcmp(sadj->lan.desig_is_id, resource->adjacency, | |
816 | ISIS_SYS_ID_LEN + 1)) | |
817 | return true; | |
818 | } else { | |
819 | if (!reverse | |
820 | && !memcmp(sadj->id, resource->adjacency, ISIS_SYS_ID_LEN)) | |
821 | return true; | |
822 | if (reverse && !memcmp(sadj->id, root_sysid, ISIS_SYS_ID_LEN)) | |
823 | return true; | |
824 | } | |
825 | ||
826 | return false; | |
827 | } | |
828 | ||
829 | /* Check if the given vertex is affected by a given local failure. */ | |
830 | static bool | |
831 | spf_vertex_check_is_affected(const struct isis_vertex *vertex, | |
832 | const uint8_t *root_sysid, | |
833 | const struct lfa_protected_resource *resource) | |
834 | { | |
835 | struct isis_vertex_adj *vadj; | |
836 | struct listnode *node; | |
837 | size_t affected_nhs = 0; | |
838 | ||
839 | /* Local routes don't need protection. */ | |
840 | if (VTYPE_IP(vertex->type) && vertex->depth == 1) | |
841 | return false; | |
842 | ||
843 | for (ALL_LIST_ELEMENTS_RO(vertex->Adj_N, node, vadj)) { | |
844 | struct isis_spf_adj *sadj = vadj->sadj; | |
845 | ||
846 | if (spf_adj_check_is_affected(sadj, resource, root_sysid, | |
847 | false)) | |
848 | affected_nhs++; | |
849 | } | |
850 | ||
851 | /* | |
852 | * No need to compute backup paths for ECMP routes, except if all | |
853 | * primary nexthops share the same broadcast interface. | |
854 | */ | |
855 | if (listcount(vertex->Adj_N) == affected_nhs) | |
856 | return true; | |
857 | ||
858 | return false; | |
859 | } | |
860 | ||
861 | /* Check if a given RLFA/TI-LFA post-convergence SPF vertex needs protection. */ | |
862 | static bool lfa_check_needs_protection(const struct isis_spftree *spftree_pc, | |
863 | const struct isis_vertex *vertex) | |
864 | { | |
865 | struct isis_vertex *vertex_old; | |
866 | ||
867 | /* Only local adjacencies need TI-LFA Adj-SID protection. */ | |
868 | if (spftree_pc->type == SPF_TYPE_TI_LFA && VTYPE_IS(vertex->type) | |
869 | && !isis_adj_find(spftree_pc->area, spftree_pc->level, | |
870 | vertex->N.id)) | |
871 | return false; | |
872 | ||
873 | vertex_old = isis_find_vertex(&spftree_pc->lfa.old.spftree->paths, | |
874 | &vertex->N, vertex->type); | |
875 | if (!vertex_old) | |
876 | return false; | |
877 | ||
878 | /* Skip vertex if it's already protected by local LFA. */ | |
879 | if (CHECK_FLAG(vertex_old->flags, F_ISIS_VERTEX_LFA_PROTECTED)) | |
880 | return false; | |
881 | ||
882 | return spf_vertex_check_is_affected( | |
883 | vertex_old, spftree_pc->sysid, | |
884 | &spftree_pc->lfa.protected_resource); | |
885 | } | |
886 | ||
887 | /** | |
888 | * Check if the given SPF vertex needs protection and, if so, compute and | |
889 | * install the corresponding repair paths. | |
890 | * | |
891 | * @param spftree_pc The post-convergence SPF tree | |
892 | * @param vertex IS-IS SPF vertex to check | |
893 | * | |
894 | * @return 0 if the vertex needs to be protected, -1 otherwise | |
895 | */ | |
896 | int isis_tilfa_check(struct isis_spftree *spftree_pc, | |
897 | struct isis_vertex *vertex) | |
898 | { | |
899 | struct isis_spf_nodes used_pnodes; | |
900 | char buf[VID2STR_BUFFER]; | |
901 | struct list *repair_list; | |
902 | int ret; | |
903 | ||
904 | if (!spftree_pc->area->srdb.enabled) | |
905 | return -1; | |
906 | ||
907 | if (!lfa_check_needs_protection(spftree_pc, vertex)) { | |
908 | if (IS_DEBUG_LFA) | |
909 | zlog_debug( | |
910 | "ISIS-LFA: %s %s unaffected by %s", | |
911 | vtype2string(vertex->type), | |
912 | vid2string(vertex, buf, sizeof(buf)), | |
913 | lfa_protected_resource2str( | |
914 | &spftree_pc->lfa.protected_resource)); | |
915 | ||
916 | return -1; | |
917 | } | |
918 | ||
919 | /* | |
920 | * Check if the route/adjacency was already covered by node protection. | |
921 | */ | |
922 | if (VTYPE_IS(vertex->type)) { | |
923 | struct isis_adjacency *adj; | |
924 | ||
925 | adj = isis_adj_find(spftree_pc->area, spftree_pc->level, | |
926 | vertex->N.id); | |
927 | if (adj | |
928 | && isis_sr_adj_sid_find(adj, spftree_pc->family, | |
929 | ISIS_SR_LAN_BACKUP)) { | |
930 | if (IS_DEBUG_LFA) | |
931 | zlog_debug( | |
932 | "ISIS-LFA: %s %s already covered by node protection", | |
933 | vtype2string(vertex->type), | |
934 | vid2string(vertex, buf, sizeof(buf))); | |
935 | ||
936 | return -1; | |
937 | } | |
938 | } | |
939 | if (VTYPE_IP(vertex->type)) { | |
940 | struct route_table *route_table; | |
941 | ||
942 | route_table = spftree_pc->lfa.old.spftree->route_table_backup; | |
943 | if (route_node_lookup(route_table, &vertex->N.ip.p.dest)) { | |
944 | if (IS_DEBUG_LFA) | |
945 | zlog_debug( | |
946 | "ISIS-LFA: %s %s already covered by node protection", | |
947 | vtype2string(vertex->type), | |
948 | vid2string(vertex, buf, sizeof(buf))); | |
949 | ||
950 | return -1; | |
951 | } | |
952 | } | |
953 | ||
954 | if (IS_DEBUG_LFA) | |
955 | zlog_debug( | |
956 | "ISIS-LFA: computing repair path(s) of %s %s w.r.t %s", | |
957 | vtype2string(vertex->type), | |
958 | vid2string(vertex, buf, sizeof(buf)), | |
959 | lfa_protected_resource2str( | |
960 | &spftree_pc->lfa.protected_resource)); | |
961 | ||
962 | /* Create base repair list. */ | |
963 | repair_list = list_new(); | |
964 | ||
965 | isis_spf_node_list_init(&used_pnodes); | |
966 | ret = tilfa_build_repair_list(spftree_pc, vertex, vertex, NULL, | |
967 | &used_pnodes, repair_list); | |
968 | isis_spf_node_list_clear(&used_pnodes); | |
969 | list_delete(&repair_list); | |
970 | if (ret != 0) | |
971 | zlog_warn( | |
972 | "ISIS-LFA: failed to compute repair path(s) of %s %s w.r.t %s", | |
973 | vtype2string(vertex->type), | |
974 | vid2string(vertex, buf, sizeof(buf)), | |
975 | lfa_protected_resource2str( | |
976 | &spftree_pc->lfa.protected_resource)); | |
977 | ||
978 | return ret; | |
979 | } | |
980 | ||
981 | static bool | |
982 | spf_adj_node_is_affected(struct isis_spf_node *adj_node, | |
983 | const struct lfa_protected_resource *resource, | |
984 | const uint8_t *root_sysid) | |
985 | { | |
986 | struct isis_spf_adj *sadj; | |
987 | struct listnode *node; | |
988 | ||
989 | for (ALL_LIST_ELEMENTS_RO(adj_node->adjacencies, node, sadj)) { | |
990 | if (sadj->metric != adj_node->best_metric) | |
991 | continue; | |
992 | if (spf_adj_check_is_affected(sadj, resource, root_sysid, | |
993 | false)) | |
994 | return true; | |
995 | } | |
996 | ||
997 | return false; | |
998 | } | |
999 | ||
1000 | static bool vertex_is_affected(struct isis_spftree *spftree_root, | |
1001 | const struct isis_spf_nodes *adj_nodes, | |
1002 | bool p_space, const struct isis_vertex *vertex, | |
1003 | const struct lfa_protected_resource *resource) | |
1004 | { | |
1005 | struct isis_vertex *pvertex; | |
1006 | struct listnode *node, *vnode; | |
1007 | ||
1008 | for (ALL_LIST_ELEMENTS_RO(vertex->parents, node, pvertex)) { | |
1009 | struct isis_spftree *spftree_parent; | |
1010 | struct isis_vertex *vertex_child; | |
1011 | struct isis_vertex_adj *vadj; | |
1012 | bool reverse = false; | |
1013 | ||
1014 | if (p_space && resource->type == LFA_NODE_PROTECTION) { | |
1015 | if (isis_spf_node_find(&resource->nodes, vertex->N.id)) | |
1016 | return true; | |
1017 | goto parents; | |
1018 | } | |
1019 | ||
1020 | /* Check if either the vertex or its parent is the root node. */ | |
1021 | if (memcmp(vertex->N.id, spftree_root->sysid, ISIS_SYS_ID_LEN) | |
1022 | && memcmp(pvertex->N.id, spftree_root->sysid, | |
1023 | ISIS_SYS_ID_LEN)) | |
1024 | goto parents; | |
1025 | ||
1026 | /* Get SPT of the parent vertex. */ | |
1027 | if (!memcmp(pvertex->N.id, spftree_root->sysid, | |
1028 | ISIS_SYS_ID_LEN)) | |
1029 | spftree_parent = spftree_root; | |
1030 | else { | |
1031 | struct isis_spf_node *adj_node; | |
1032 | ||
1033 | adj_node = isis_spf_node_find(adj_nodes, pvertex->N.id); | |
1034 | assert(adj_node); | |
1035 | spftree_parent = adj_node->lfa.spftree; | |
1036 | assert(spftree_parent); | |
1037 | reverse = true; | |
1038 | } | |
1039 | ||
1040 | /* Get paths pvertex uses to reach vertex. */ | |
1041 | vertex_child = isis_find_vertex(&spftree_parent->paths, | |
1042 | &vertex->N, vertex->type); | |
1043 | if (!vertex_child) | |
1044 | goto parents; | |
1045 | ||
1046 | /* Check if any of these paths use the protected resource. */ | |
1047 | for (ALL_LIST_ELEMENTS_RO(vertex_child->Adj_N, vnode, vadj)) | |
1048 | if (spf_adj_check_is_affected(vadj->sadj, resource, | |
1049 | spftree_root->sysid, | |
1050 | reverse)) | |
1051 | return true; | |
1052 | ||
1053 | parents: | |
1054 | if (vertex_is_affected(spftree_root, adj_nodes, p_space, | |
1055 | pvertex, resource)) | |
1056 | return true; | |
1057 | } | |
1058 | ||
1059 | return false; | |
1060 | } | |
1061 | ||
1062 | /* Calculate set of nodes reachable without using the protected interface. */ | |
1063 | static void lfa_calc_reach_nodes(struct isis_spftree *spftree, | |
1064 | struct isis_spftree *spftree_root, | |
1065 | const struct isis_spf_nodes *adj_nodes, | |
1066 | bool p_space, | |
1067 | const struct lfa_protected_resource *resource, | |
1068 | struct isis_spf_nodes *nodes) | |
1069 | { | |
1070 | struct isis_vertex *vertex; | |
1071 | struct listnode *node; | |
1072 | ||
1073 | for (ALL_QUEUE_ELEMENTS_RO(&spftree->paths, node, vertex)) { | |
1074 | char buf[VID2STR_BUFFER]; | |
1075 | ||
1076 | if (!VTYPE_IS(vertex->type)) | |
1077 | continue; | |
1078 | ||
1079 | /* Skip root node. */ | |
1080 | if (!memcmp(vertex->N.id, spftree_root->sysid, ISIS_SYS_ID_LEN)) | |
1081 | continue; | |
1082 | ||
1083 | /* Don't add the same node twice. */ | |
1084 | if (isis_spf_node_find(nodes, vertex->N.id)) | |
1085 | continue; | |
1086 | ||
1087 | if (!vertex_is_affected(spftree_root, adj_nodes, p_space, | |
1088 | vertex, resource)) { | |
1089 | if (IS_DEBUG_LFA) | |
1090 | zlog_debug( | |
1091 | "ISIS-LFA: adding %s", | |
1092 | vid2string(vertex, buf, sizeof(buf))); | |
1093 | ||
1094 | isis_spf_node_new(nodes, vertex->N.id); | |
1095 | } | |
1096 | } | |
1097 | } | |
1098 | ||
1099 | /** | |
1100 | * Helper function used to create an SPF tree structure and run reverse SPF on | |
1101 | * it. | |
1102 | * | |
1103 | * @param spftree IS-IS SPF tree | |
1104 | * | |
1105 | * @return Pointer to new SPF tree structure. | |
1106 | */ | |
1107 | struct isis_spftree *isis_spf_reverse_run(const struct isis_spftree *spftree) | |
1108 | { | |
1109 | struct isis_spftree *spftree_reverse; | |
1110 | ||
1111 | spftree_reverse = isis_spftree_new( | |
1112 | spftree->area, spftree->lspdb, spftree->sysid, spftree->level, | |
1113 | spftree->tree_id, SPF_TYPE_REVERSE, | |
1114 | F_SPFTREE_NO_ADJACENCIES | F_SPFTREE_NO_ROUTES); | |
1115 | isis_run_spf(spftree_reverse); | |
1116 | ||
1117 | return spftree_reverse; | |
1118 | } | |
1119 | ||
1120 | /* | |
1121 | * Calculate the Extended P-space and Q-space associated to a given link | |
1122 | * failure. | |
1123 | */ | |
1124 | static void lfa_calc_pq_spaces(struct isis_spftree *spftree_pc, | |
1125 | const struct lfa_protected_resource *resource) | |
1126 | { | |
1127 | struct isis_spftree *spftree; | |
1128 | struct isis_spftree *spftree_reverse; | |
1129 | struct isis_spf_nodes *adj_nodes; | |
1130 | struct isis_spf_node *adj_node; | |
1131 | ||
1132 | /* Obtain pre-failure SPTs and list of adjacent nodes. */ | |
1133 | spftree = spftree_pc->lfa.old.spftree; | |
1134 | spftree_reverse = spftree_pc->lfa.old.spftree_reverse; | |
1135 | adj_nodes = &spftree->adj_nodes; | |
1136 | ||
1137 | if (IS_DEBUG_LFA) | |
1138 | zlog_debug("ISIS-LFA: computing P-space (self)"); | |
1139 | lfa_calc_reach_nodes(spftree, spftree, adj_nodes, true, resource, | |
1140 | &spftree_pc->lfa.p_space); | |
1141 | ||
1142 | RB_FOREACH (adj_node, isis_spf_nodes, adj_nodes) { | |
1143 | if (spf_adj_node_is_affected(adj_node, resource, | |
1144 | spftree->sysid)) { | |
1145 | if (IS_DEBUG_LFA) | |
1146 | zlog_debug("ISIS-LFA: computing Q-space (%s)", | |
1147 | print_sys_hostname(adj_node->sysid)); | |
1148 | ||
1149 | /* | |
1150 | * Compute the reverse SPF in the behalf of the node | |
1151 | * adjacent to the failure, if we haven't done that | |
1152 | * before | |
1153 | */ | |
1154 | if (!adj_node->lfa.spftree_reverse) | |
1155 | adj_node->lfa.spftree_reverse = | |
1156 | isis_spf_reverse_run( | |
1157 | adj_node->lfa.spftree); | |
1158 | ||
1159 | lfa_calc_reach_nodes(adj_node->lfa.spftree_reverse, | |
1160 | spftree_reverse, adj_nodes, false, | |
1161 | resource, | |
1162 | &spftree_pc->lfa.q_space); | |
1163 | } else { | |
1164 | if (IS_DEBUG_LFA) | |
1165 | zlog_debug("ISIS-LFA: computing P-space (%s)", | |
1166 | print_sys_hostname(adj_node->sysid)); | |
1167 | lfa_calc_reach_nodes(adj_node->lfa.spftree, spftree, | |
1168 | adj_nodes, true, resource, | |
1169 | &adj_node->lfa.p_space); | |
1170 | } | |
1171 | } | |
1172 | } | |
1173 | ||
1174 | /** | |
1175 | * Compute the TI-LFA backup paths for a given protected interface. | |
1176 | * | |
1177 | * @param area IS-IS area | |
1178 | * @param spftree IS-IS SPF tree | |
1179 | * @param spftree_reverse IS-IS Reverse SPF tree | |
1180 | * @param resource Protected resource | |
1181 | * | |
1182 | * @return Pointer to the post-convergence SPF tree | |
1183 | */ | |
1184 | struct isis_spftree *isis_tilfa_compute(struct isis_area *area, | |
1185 | struct isis_spftree *spftree, | |
1186 | struct isis_spftree *spftree_reverse, | |
1187 | struct lfa_protected_resource *resource) | |
1188 | { | |
1189 | struct isis_spftree *spftree_pc; | |
1190 | struct isis_spf_node *adj_node; | |
1191 | ||
1192 | if (IS_DEBUG_LFA) | |
1193 | zlog_debug("ISIS-LFA: computing TI-LFAs for %s", | |
1194 | lfa_protected_resource2str(resource)); | |
1195 | ||
1196 | /* Populate list of nodes affected by link failure. */ | |
1197 | if (resource->type == LFA_NODE_PROTECTION) { | |
1198 | isis_spf_node_list_init(&resource->nodes); | |
1199 | RB_FOREACH (adj_node, isis_spf_nodes, &spftree->adj_nodes) { | |
1200 | if (spf_adj_node_is_affected(adj_node, resource, | |
1201 | spftree->sysid)) | |
1202 | isis_spf_node_new(&resource->nodes, | |
1203 | adj_node->sysid); | |
1204 | } | |
1205 | } | |
1206 | ||
1207 | /* Create post-convergence SPF tree. */ | |
1208 | spftree_pc = isis_spftree_new(area, spftree->lspdb, spftree->sysid, | |
1209 | spftree->level, spftree->tree_id, | |
1210 | SPF_TYPE_TI_LFA, spftree->flags); | |
1211 | spftree_pc->lfa.old.spftree = spftree; | |
1212 | spftree_pc->lfa.old.spftree_reverse = spftree_reverse; | |
1213 | spftree_pc->lfa.protected_resource = *resource; | |
1214 | ||
1215 | /* Compute the extended P-space and Q-space. */ | |
1216 | lfa_calc_pq_spaces(spftree_pc, resource); | |
1217 | ||
1218 | if (IS_DEBUG_LFA) | |
1219 | zlog_debug( | |
1220 | "ISIS-LFA: computing the post convergence SPT w.r.t. %s", | |
1221 | lfa_protected_resource2str(resource)); | |
1222 | ||
1223 | /* Re-run SPF in the local node to find the post-convergence paths. */ | |
1224 | isis_run_spf(spftree_pc); | |
1225 | ||
1226 | /* Clear list of nodes affeted by link failure. */ | |
1227 | if (resource->type == LFA_NODE_PROTECTION) | |
1228 | isis_spf_node_list_clear(&resource->nodes); | |
1229 | ||
1230 | return spftree_pc; | |
1231 | } | |
1232 | ||
1233 | /** | |
1234 | * Run forward SPF on all adjacent routers. | |
1235 | * | |
1236 | * @param spftree IS-IS SPF tree | |
1237 | * | |
1238 | * @return 0 on success, -1 otherwise | |
1239 | */ | |
1240 | int isis_spf_run_neighbors(struct isis_spftree *spftree) | |
1241 | { | |
1242 | struct isis_lsp *lsp; | |
1243 | struct isis_spf_node *adj_node; | |
1244 | ||
1245 | lsp = isis_root_system_lsp(spftree->lspdb, spftree->sysid); | |
1246 | if (!lsp) | |
1247 | return -1; | |
1248 | ||
1249 | RB_FOREACH (adj_node, isis_spf_nodes, &spftree->adj_nodes) { | |
1250 | if (IS_DEBUG_LFA) | |
1251 | zlog_debug("ISIS-LFA: running SPF on neighbor %s", | |
1252 | print_sys_hostname(adj_node->sysid)); | |
1253 | ||
1254 | /* Compute the SPT on behalf of the neighbor. */ | |
1255 | adj_node->lfa.spftree = isis_spftree_new( | |
1256 | spftree->area, spftree->lspdb, adj_node->sysid, | |
1257 | spftree->level, spftree->tree_id, SPF_TYPE_FORWARD, | |
1258 | F_SPFTREE_NO_ADJACENCIES | F_SPFTREE_NO_ROUTES); | |
1259 | isis_run_spf(adj_node->lfa.spftree); | |
1260 | } | |
1261 | ||
1262 | return 0; | |
1263 | } | |
1264 | ||
1265 | /* Find Router ID of PQ node. */ | |
1266 | static struct in_addr *rlfa_pq_node_rtr_id(struct isis_spftree *spftree, | |
1267 | const struct isis_vertex *vertex_pq) | |
1268 | { | |
1269 | struct isis_lsp *lsp; | |
1270 | ||
1271 | lsp = isis_root_system_lsp(spftree->lspdb, vertex_pq->N.id); | |
1272 | if (!lsp) | |
1273 | return NULL; | |
1274 | ||
1275 | if (lsp->tlvs->router_cap->router_id.s_addr == INADDR_ANY) | |
1276 | return NULL; | |
1277 | ||
1278 | return &lsp->tlvs->router_cap->router_id; | |
1279 | } | |
1280 | ||
1281 | /* Find PQ node by intersecting the P/Q spaces. This is a recursive function. */ | |
1282 | static const struct in_addr * | |
1283 | rlfa_find_pq_node(struct isis_spftree *spftree_pc, | |
1284 | struct isis_vertex *vertex_dest, | |
1285 | const struct isis_vertex *vertex, | |
1286 | const struct isis_vertex *vertex_child) | |
1287 | { | |
1288 | struct isis_area *area = spftree_pc->area; | |
1289 | int level = spftree_pc->level; | |
1290 | struct isis_vertex *pvertex; | |
1291 | struct listnode *node; | |
1292 | bool is_pnode, is_qnode; | |
1293 | ||
1294 | if (!vertex_child) | |
1295 | goto parents; | |
1296 | if (vertex->type != VTYPE_NONPSEUDO_IS | |
1297 | && vertex->type != VTYPE_NONPSEUDO_TE_IS) | |
1298 | goto parents; | |
1299 | if (!VTYPE_IS(vertex_child->type)) | |
1300 | vertex_child = NULL; | |
1301 | ||
1302 | /* Check if node is part of the extended P-space and/or Q-space. */ | |
1303 | is_pnode = lfa_ext_p_space_check(spftree_pc, vertex_dest, vertex); | |
1304 | is_qnode = lfa_q_space_check(spftree_pc, vertex); | |
1305 | ||
1306 | if (is_pnode && is_qnode) { | |
1307 | const struct in_addr *rtr_id_pq; | |
1308 | uint32_t max_metric; | |
1309 | struct prefix_list *plist = NULL; | |
1310 | ||
1311 | rtr_id_pq = rlfa_pq_node_rtr_id(spftree_pc, vertex); | |
1312 | if (!rtr_id_pq) { | |
1313 | if (IS_DEBUG_LFA) { | |
1314 | char buf[VID2STR_BUFFER]; | |
1315 | ||
1316 | vid2string(vertex, buf, sizeof(buf)); | |
1317 | zlog_debug( | |
1318 | "ISIS-LFA: tentative PQ node (%s %s) doesn't have a router-ID", | |
1319 | vtype2string(vertex->type), buf); | |
1320 | } | |
1321 | goto parents; | |
1322 | } | |
1323 | ||
1324 | max_metric = spftree_pc->lfa.remote.max_metric; | |
1325 | if (max_metric && vertex->d_N > max_metric) { | |
1326 | if (IS_DEBUG_LFA) | |
1327 | zlog_debug( | |
1328 | "ISIS-LFA: skipping PQ node %pI4 (maximum metric)", | |
1329 | rtr_id_pq); | |
1330 | goto parents; | |
1331 | } | |
1332 | ||
1333 | plist = area->rlfa_plist[level - 1]; | |
1334 | if (plist) { | |
1335 | struct prefix p; | |
1336 | ||
1337 | p.family = AF_INET; | |
1338 | p.prefixlen = IPV4_MAX_BITLEN; | |
1339 | p.u.prefix4 = *rtr_id_pq; | |
1340 | if (prefix_list_apply(plist, &p) == PREFIX_DENY) { | |
1341 | if (IS_DEBUG_LFA) | |
1342 | zlog_debug( | |
1343 | "ISIS-LFA: PQ node %pI4 filtered by prefix-list", | |
1344 | rtr_id_pq); | |
1345 | goto parents; | |
1346 | } | |
1347 | } | |
1348 | ||
1349 | if (IS_DEBUG_LFA) | |
1350 | zlog_debug("ISIS-LFA: found PQ node: %pI4", rtr_id_pq); | |
1351 | ||
1352 | return rtr_id_pq; | |
1353 | } | |
1354 | ||
1355 | parents: | |
1356 | for (ALL_LIST_ELEMENTS_RO(vertex->parents, node, pvertex)) { | |
1357 | const struct in_addr *rtr_id_pq; | |
1358 | ||
1359 | rtr_id_pq = rlfa_find_pq_node(spftree_pc, vertex_dest, pvertex, | |
1360 | vertex); | |
1361 | if (rtr_id_pq) | |
1362 | return rtr_id_pq; | |
1363 | } | |
1364 | ||
1365 | return NULL; | |
1366 | } | |
1367 | ||
1368 | int rlfa_cmp(const struct rlfa *a, const struct rlfa *b) | |
1369 | { | |
1370 | return prefix_cmp(&a->prefix, &b->prefix); | |
1371 | } | |
1372 | ||
1373 | static struct rlfa *rlfa_add(struct isis_spftree *spftree, | |
1374 | struct isis_vertex *vertex, | |
1375 | struct in_addr pq_address) | |
1376 | { | |
1377 | struct rlfa *rlfa; | |
1378 | ||
1379 | assert(VTYPE_IP(vertex->type)); | |
1380 | rlfa = XCALLOC(MTYPE_ISIS_RLFA, sizeof(*rlfa)); | |
1381 | rlfa->prefix = vertex->N.ip.p.dest; | |
1382 | rlfa->vertex = vertex; | |
1383 | rlfa->pq_address = pq_address; | |
1384 | rlfa_tree_add(&spftree->lfa.remote.rlfas, rlfa); | |
1385 | ||
1386 | return rlfa; | |
1387 | } | |
1388 | ||
1389 | static void rlfa_delete(struct isis_spftree *spftree, struct rlfa *rlfa) | |
1390 | { | |
1391 | rlfa_tree_del(&spftree->lfa.remote.rlfas, rlfa); | |
1392 | XFREE(MTYPE_ISIS_RLFA, rlfa); | |
1393 | } | |
1394 | ||
1395 | static struct rlfa *rlfa_lookup(struct isis_spftree *spftree, | |
1396 | union prefixconstptr pu) | |
1397 | { | |
1398 | struct rlfa s = {}; | |
1399 | ||
1400 | s.prefix = *pu.p; | |
1401 | return rlfa_tree_find(&spftree->lfa.remote.rlfas, &s); | |
1402 | } | |
1403 | ||
1404 | static int isis_area_verify_routes_cb(struct thread *thread) | |
1405 | { | |
1406 | struct isis_area *area = THREAD_ARG(thread); | |
1407 | ||
1408 | if (IS_DEBUG_LFA) | |
1409 | zlog_debug("ISIS-LFA: updating RLFAs in the RIB"); | |
1410 | ||
1411 | isis_area_verify_routes(area); | |
1412 | ||
1413 | return 0; | |
1414 | } | |
1415 | ||
1416 | static mpls_label_t rlfa_nexthop_label(struct isis_spftree *spftree, | |
1417 | struct isis_vertex_adj *vadj, | |
1418 | struct zapi_rlfa_response *response) | |
1419 | { | |
1420 | struct isis_spf_adj *sadj = vadj->sadj; | |
1421 | struct isis_adjacency *adj = sadj->adj; | |
1422 | ||
1423 | /* | |
1424 | * Special case to make unit tests work (use implicit-null labels | |
1425 | * instead of artifical ones). | |
1426 | */ | |
1427 | if (CHECK_FLAG(spftree->flags, F_SPFTREE_NO_ADJACENCIES)) | |
1428 | return MPLS_LABEL_IMPLICIT_NULL; | |
1429 | ||
1430 | for (unsigned int i = 0; i < response->nexthop_num; i++) { | |
1431 | switch (response->nexthops[i].family) { | |
1432 | case AF_INET: | |
1433 | for (unsigned int j = 0; j < adj->ipv4_address_count; | |
1434 | j++) { | |
1435 | struct in_addr addr = adj->ipv4_addresses[j]; | |
1436 | ||
1437 | if (!IPV4_ADDR_SAME( | |
1438 | &addr, | |
1439 | &response->nexthops[i].gate.ipv4)) | |
1440 | continue; | |
1441 | ||
1442 | return response->nexthops[i].label; | |
1443 | } | |
1444 | break; | |
1445 | case AF_INET6: | |
1446 | for (unsigned int j = 0; j < adj->ipv6_address_count; | |
1447 | j++) { | |
1448 | struct in6_addr addr = adj->ipv6_addresses[j]; | |
1449 | ||
1450 | if (!IPV6_ADDR_SAME( | |
1451 | &addr, | |
1452 | &response->nexthops[i].gate.ipv6)) | |
1453 | continue; | |
1454 | ||
1455 | return response->nexthops[i].label; | |
1456 | } | |
1457 | break; | |
1458 | ||
1459 | default: | |
1460 | break; | |
1461 | } | |
1462 | } | |
1463 | ||
1464 | return MPLS_INVALID_LABEL; | |
1465 | } | |
1466 | ||
1467 | int isis_rlfa_activate(struct isis_spftree *spftree, struct rlfa *rlfa, | |
1468 | struct zapi_rlfa_response *response) | |
1469 | { | |
1470 | struct isis_area *area = spftree->area; | |
1471 | struct isis_vertex *vertex = rlfa->vertex; | |
1472 | struct isis_vertex_adj *vadj; | |
1473 | struct listnode *node; | |
1474 | ||
1475 | for (ALL_LIST_ELEMENTS_RO(vertex->Adj_N, node, vadj)) { | |
1476 | mpls_label_t ldp_label; | |
1477 | struct mpls_label_stack *label_stack; | |
1478 | size_t num_labels = 0; | |
1479 | size_t i = 0; | |
1480 | ||
1481 | ldp_label = rlfa_nexthop_label(spftree, vadj, response); | |
1482 | if (ldp_label == MPLS_INVALID_LABEL) { | |
1483 | if (IS_DEBUG_LFA) | |
1484 | zlog_debug( | |
1485 | "ISIS-LFA: failed to activate RLFA: missing LDP label to reach PQ node through %s", | |
1486 | sysid_print(vadj->sadj->id)); | |
1487 | return -1; | |
1488 | } | |
1489 | ||
1490 | if (ldp_label != MPLS_LABEL_IMPLICIT_NULL) | |
1491 | num_labels++; | |
1492 | if (response->pq_label != MPLS_LABEL_IMPLICIT_NULL) | |
1493 | num_labels++; | |
1494 | if (vadj->sr.present | |
1495 | && vadj->sr.label != MPLS_LABEL_IMPLICIT_NULL) | |
1496 | num_labels++; | |
1497 | ||
1498 | /* Allocate label stack. */ | |
1499 | label_stack = | |
1500 | XCALLOC(MTYPE_ISIS_NEXTHOP_LABELS, | |
1501 | sizeof(struct mpls_label_stack) | |
1502 | + num_labels * sizeof(mpls_label_t)); | |
1503 | label_stack->num_labels = num_labels; | |
1504 | ||
1505 | /* Push label allocated by the nexthop (outer label). */ | |
1506 | if (ldp_label != MPLS_LABEL_IMPLICIT_NULL) | |
1507 | label_stack->label[i++] = ldp_label; | |
1508 | /* Push label allocated by the PQ node (inner label). */ | |
1509 | if (response->pq_label != MPLS_LABEL_IMPLICIT_NULL) | |
1510 | label_stack->label[i++] = response->pq_label; | |
1511 | /* Preserve the original Prefix-SID label when it's present. */ | |
1512 | if (vadj->sr.present | |
1513 | && vadj->sr.label != MPLS_LABEL_IMPLICIT_NULL) | |
1514 | label_stack->label[i++] = vadj->sr.label; | |
1515 | ||
1516 | vadj->label_stack = label_stack; | |
1517 | } | |
1518 | ||
1519 | isis_route_create(&vertex->N.ip.p.dest, &vertex->N.ip.p.src, | |
1520 | vertex->d_N, vertex->depth, &vertex->N.ip.sr, | |
1521 | vertex->Adj_N, true, area, | |
1522 | spftree->route_table_backup); | |
1523 | spftree->lfa.protection_counters.rlfa[vertex->N.ip.priority] += 1; | |
1524 | ||
1525 | thread_cancel(&area->t_rlfa_rib_update); | |
1526 | thread_add_timer(master, isis_area_verify_routes_cb, area, 2, | |
1527 | &area->t_rlfa_rib_update); | |
1528 | ||
1529 | return 0; | |
1530 | } | |
1531 | ||
1532 | void isis_rlfa_deactivate(struct isis_spftree *spftree, struct rlfa *rlfa) | |
1533 | { | |
1534 | struct isis_area *area = spftree->area; | |
1535 | struct isis_vertex *vertex = rlfa->vertex; | |
1536 | struct route_node *rn; | |
1537 | ||
1538 | rn = route_node_lookup(spftree->route_table_backup, &rlfa->prefix); | |
1539 | if (!rn) | |
1540 | return; | |
1541 | isis_route_delete(area, rn, spftree->route_table_backup); | |
1542 | spftree->lfa.protection_counters.rlfa[vertex->N.ip.priority] -= 1; | |
1543 | ||
1544 | thread_cancel(&area->t_rlfa_rib_update); | |
1545 | thread_add_timer(master, isis_area_verify_routes_cb, area, 2, | |
1546 | &area->t_rlfa_rib_update); | |
1547 | } | |
1548 | ||
1549 | void isis_rlfa_list_init(struct isis_spftree *spftree) | |
1550 | { | |
1551 | rlfa_tree_init(&spftree->lfa.remote.rlfas); | |
1552 | } | |
1553 | ||
1554 | void isis_rlfa_list_clear(struct isis_spftree *spftree) | |
1555 | { | |
1556 | while (rlfa_tree_count(&spftree->lfa.remote.rlfas) > 0) { | |
1557 | struct rlfa *rlfa; | |
1558 | ||
1559 | rlfa = rlfa_tree_first(&spftree->lfa.remote.rlfas); | |
1560 | isis_rlfa_deactivate(spftree, rlfa); | |
1561 | rlfa_delete(spftree, rlfa); | |
1562 | } | |
1563 | } | |
1564 | ||
1565 | void isis_rlfa_process_ldp_response(struct zapi_rlfa_response *response) | |
1566 | { | |
1567 | struct isis *isis; | |
1568 | struct isis_area *area; | |
1569 | struct isis_spftree *spftree; | |
1570 | struct rlfa *rlfa; | |
1571 | enum spf_tree_id tree_id; | |
1572 | uint32_t spf_run_id; | |
1573 | int level; | |
1574 | ||
1575 | if (response->igp.protocol != ZEBRA_ROUTE_ISIS) | |
1576 | return; | |
1577 | ||
1578 | isis = isis_lookup_by_vrfid(response->igp.vrf_id); | |
1579 | if (!isis) | |
1580 | return; | |
1581 | ||
1582 | area = isis_area_lookup(response->igp.isis.area_tag, | |
1583 | response->igp.vrf_id); | |
1584 | if (!area) | |
1585 | return; | |
1586 | ||
1587 | tree_id = response->igp.isis.spf.tree_id; | |
1588 | if (tree_id != SPFTREE_IPV4 && tree_id != SPFTREE_IPV6) { | |
1589 | zlog_warn("ISIS-LFA: invalid SPF tree ID received from LDP"); | |
1590 | return; | |
1591 | } | |
1592 | ||
1593 | level = response->igp.isis.spf.level; | |
1594 | if (level != ISIS_LEVEL1 && level != ISIS_LEVEL2) { | |
1595 | zlog_warn("ISIS-LFA: invalid IS-IS level received from LDP"); | |
1596 | return; | |
1597 | } | |
1598 | ||
1599 | spf_run_id = response->igp.isis.spf.run_id; | |
1600 | spftree = area->spftree[tree_id][level - 1]; | |
1601 | if (spftree->runcount != spf_run_id) | |
1602 | /* Outdated RLFA, ignore... */ | |
1603 | return; | |
1604 | ||
1605 | rlfa = rlfa_lookup(spftree, &response->destination); | |
1606 | if (!rlfa) { | |
1607 | zlog_warn( | |
1608 | "ISIS-LFA: couldn't find Remote-LFA %pFX received from LDP", | |
1609 | &response->destination); | |
1610 | return; | |
1611 | } | |
1612 | ||
1613 | if (response->pq_label != MPLS_INVALID_LABEL) { | |
1614 | if (IS_DEBUG_LFA) | |
1615 | zlog_debug( | |
1616 | "ISIS-LFA: activating/updating RLFA for %pFX", | |
1617 | &rlfa->prefix); | |
1618 | ||
1619 | if (isis_rlfa_activate(spftree, rlfa, response) != 0) | |
1620 | isis_rlfa_deactivate(spftree, rlfa); | |
1621 | } else { | |
1622 | if (IS_DEBUG_LFA) | |
1623 | zlog_debug("ISIS-LFA: deactivating RLFA for %pFX", | |
1624 | &rlfa->prefix); | |
1625 | ||
1626 | isis_rlfa_deactivate(spftree, rlfa); | |
1627 | } | |
1628 | } | |
1629 | ||
1630 | void isis_ldp_rlfa_handle_client_close(struct zapi_client_close_info *info) | |
1631 | { | |
1632 | struct isis *isis = isis_lookup_by_vrfid(VRF_DEFAULT); | |
1633 | struct isis_area *area; | |
1634 | struct listnode *node; | |
1635 | ||
1636 | if (!isis) | |
1637 | return; | |
1638 | ||
1639 | /* Check if the LDP main client session closed */ | |
1640 | if (info->proto != ZEBRA_ROUTE_LDP || info->session_id == 0) | |
1641 | return; | |
1642 | ||
1643 | if (IS_DEBUG_LFA) | |
1644 | zlog_debug("ISIS-LFA: LDP is down, deactivating all RLFAs"); | |
1645 | ||
1646 | for (ALL_LIST_ELEMENTS_RO(isis->area_list, node, area)) { | |
1647 | for (int tree = SPFTREE_IPV4; tree < SPFTREE_COUNT; tree++) { | |
1648 | for (int level = ISIS_LEVEL1; level <= ISIS_LEVELS; | |
1649 | level++) { | |
1650 | struct isis_spftree *spftree; | |
1651 | ||
1652 | spftree = area->spftree[tree][level - 1]; | |
1653 | isis_rlfa_list_clear(spftree); | |
1654 | } | |
1655 | } | |
1656 | } | |
1657 | } | |
1658 | ||
1659 | /** | |
1660 | * Check if the given SPF vertex needs protection and, if so, attempt to | |
1661 | * compute a Remote LFA for it. | |
1662 | * | |
1663 | * @param spftree_pc The post-convergence SPF tree | |
1664 | * @param vertex IS-IS SPF vertex to check | |
1665 | */ | |
1666 | void isis_rlfa_check(struct isis_spftree *spftree_pc, | |
1667 | struct isis_vertex *vertex) | |
1668 | { | |
1669 | struct isis_spftree *spftree_old = spftree_pc->lfa.old.spftree; | |
1670 | struct rlfa *rlfa; | |
1671 | const struct in_addr *rtr_id_pq; | |
1672 | char buf[VID2STR_BUFFER]; | |
1673 | ||
1674 | if (!lfa_check_needs_protection(spftree_pc, vertex)) { | |
1675 | if (IS_DEBUG_LFA) | |
1676 | zlog_debug( | |
1677 | "ISIS-LFA: %s %s unaffected by %s", | |
1678 | vtype2string(vertex->type), | |
1679 | vid2string(vertex, buf, sizeof(buf)), | |
1680 | lfa_protected_resource2str( | |
1681 | &spftree_pc->lfa.protected_resource)); | |
1682 | ||
1683 | return; | |
1684 | } | |
1685 | ||
1686 | if (IS_DEBUG_LFA) | |
1687 | zlog_debug( | |
1688 | "ISIS-LFA: computing repair path(s) of %s %s w.r.t %s", | |
1689 | vtype2string(vertex->type), | |
1690 | vid2string(vertex, buf, sizeof(buf)), | |
1691 | lfa_protected_resource2str( | |
1692 | &spftree_pc->lfa.protected_resource)); | |
1693 | ||
1694 | /* Find PQ node. */ | |
1695 | rtr_id_pq = rlfa_find_pq_node(spftree_pc, vertex, vertex, NULL); | |
1696 | if (!rtr_id_pq) { | |
1697 | if (IS_DEBUG_LFA) | |
1698 | zlog_debug("ISIS-LFA: no acceptable PQ node found"); | |
1699 | return; | |
1700 | } | |
1701 | ||
1702 | /* Store valid RLFA and store LDP label for the PQ node. */ | |
1703 | rlfa = rlfa_add(spftree_old, vertex, *rtr_id_pq); | |
1704 | ||
1705 | /* Register RLFA with LDP. */ | |
1706 | if (isis_zebra_rlfa_register(spftree_old, rlfa) != 0) | |
1707 | rlfa_delete(spftree_old, rlfa); | |
1708 | } | |
1709 | ||
1710 | /** | |
1711 | * Compute the Remote LFA backup paths for a given protected interface. | |
1712 | * | |
1713 | * @param area IS-IS area | |
1714 | * @param spftree IS-IS SPF tree | |
1715 | * @param spftree_reverse IS-IS Reverse SPF tree | |
1716 | * @param max_metric Remote LFA maximum metric | |
1717 | * @param resource Protected resource | |
1718 | * | |
1719 | * @return Pointer to the post-convergence SPF tree | |
1720 | */ | |
1721 | struct isis_spftree *isis_rlfa_compute(struct isis_area *area, | |
1722 | struct isis_spftree *spftree, | |
1723 | struct isis_spftree *spftree_reverse, | |
1724 | uint32_t max_metric, | |
1725 | struct lfa_protected_resource *resource) | |
1726 | { | |
1727 | struct isis_spftree *spftree_pc; | |
1728 | ||
1729 | if (IS_DEBUG_LFA) | |
1730 | zlog_debug("ISIS-LFA: computing remote LFAs for %s", | |
1731 | lfa_protected_resource2str(resource)); | |
1732 | ||
1733 | /* Create post-convergence SPF tree. */ | |
1734 | spftree_pc = isis_spftree_new(area, spftree->lspdb, spftree->sysid, | |
1735 | spftree->level, spftree->tree_id, | |
1736 | SPF_TYPE_RLFA, spftree->flags); | |
1737 | spftree_pc->lfa.old.spftree = spftree; | |
1738 | spftree_pc->lfa.old.spftree_reverse = spftree_reverse; | |
1739 | spftree_pc->lfa.remote.max_metric = max_metric; | |
1740 | spftree_pc->lfa.protected_resource = *resource; | |
1741 | ||
1742 | /* Compute the extended P-space and Q-space. */ | |
1743 | lfa_calc_pq_spaces(spftree_pc, resource); | |
1744 | ||
1745 | if (IS_DEBUG_LFA) | |
1746 | zlog_debug( | |
1747 | "ISIS-LFA: computing the post convergence SPT w.r.t. %s", | |
1748 | lfa_protected_resource2str(resource)); | |
1749 | ||
1750 | /* Re-run SPF in the local node to find the post-convergence paths. */ | |
1751 | isis_run_spf(spftree_pc); | |
1752 | ||
1753 | return spftree_pc; | |
1754 | } | |
1755 | ||
1756 | /* Calculate the distance from the root node to the given IP destination. */ | |
1757 | static int lfa_calc_dist_destination(struct isis_spftree *spftree, | |
1758 | const struct isis_vertex *vertex_N, | |
1759 | uint32_t *distance) | |
1760 | { | |
1761 | struct isis_vertex *vertex, *vertex_best = NULL; | |
1762 | ||
1763 | switch (spftree->family) { | |
1764 | case AF_INET: | |
1765 | for (int vtype = VTYPE_IPREACH_INTERNAL; | |
1766 | vtype <= VTYPE_IPREACH_TE; vtype++) { | |
1767 | vertex = isis_find_vertex( | |
1768 | &spftree->paths, &vertex_N->N.ip.p.dest, vtype); | |
1769 | if (!vertex) | |
1770 | continue; | |
1771 | ||
1772 | /* Pick vertex with the best metric. */ | |
1773 | if (!vertex_best || vertex_best->d_N > vertex->d_N) | |
1774 | vertex_best = vertex; | |
1775 | } | |
1776 | break; | |
1777 | case AF_INET6: | |
1778 | for (int vtype = VTYPE_IP6REACH_INTERNAL; | |
1779 | vtype <= VTYPE_IP6REACH_EXTERNAL; vtype++) { | |
1780 | vertex = isis_find_vertex( | |
1781 | &spftree->paths, &vertex_N->N.ip.p.dest, vtype); | |
1782 | if (!vertex) | |
1783 | continue; | |
1784 | ||
1785 | /* Pick vertex with the best metric. */ | |
1786 | if (!vertex_best || vertex_best->d_N > vertex->d_N) | |
1787 | vertex_best = vertex; | |
1788 | } | |
1789 | break; | |
1790 | default: | |
1791 | break; | |
1792 | } | |
1793 | ||
1794 | if (!vertex_best) | |
1795 | return -1; | |
1796 | ||
1797 | assert(VTYPE_IP(vertex_best->type)); | |
1798 | vertex_best = listnode_head(vertex_best->parents); | |
1799 | *distance = vertex_best->d_N; | |
1800 | ||
1801 | return 0; | |
1802 | } | |
1803 | ||
1804 | /* Calculate the distance from the root node to the given node. */ | |
1805 | static int lfa_calc_dist_node(struct isis_spftree *spftree, | |
1806 | const uint8_t *sysid, uint32_t *distance) | |
1807 | { | |
1808 | struct isis_vertex *vertex, *vertex_best = NULL; | |
1809 | ||
1810 | for (int vtype = VTYPE_PSEUDO_IS; vtype <= VTYPE_NONPSEUDO_TE_IS; | |
1811 | vtype++) { | |
1812 | vertex = isis_find_vertex(&spftree->paths, sysid, vtype); | |
1813 | if (!vertex) | |
1814 | continue; | |
1815 | ||
1816 | /* Pick vertex with the best metric. */ | |
1817 | if (!vertex_best || vertex_best->d_N > vertex->d_N) | |
1818 | vertex_best = vertex; | |
1819 | } | |
1820 | ||
1821 | if (!vertex_best) | |
1822 | return -1; | |
1823 | ||
1824 | *distance = vertex_best->d_N; | |
1825 | ||
1826 | return 0; | |
1827 | } | |
1828 | ||
1829 | /* | |
1830 | * Check loop-free criterion (RFC 5286's inequality 1): | |
1831 | * - Dist_opt(N, D) < Dist_opt(N, S) + Dist_opt(S, D) | |
1832 | */ | |
1833 | static bool clfa_loop_free_check(struct isis_spftree *spftree, | |
1834 | struct isis_vertex *vertex_S_D, | |
1835 | struct isis_spf_adj *sadj_primary, | |
1836 | struct isis_spf_adj *sadj_N, | |
1837 | uint32_t *lfa_metric) | |
1838 | { | |
1839 | struct isis_spf_node *node_N; | |
1840 | uint32_t dist_N_D; | |
1841 | uint32_t dist_N_S; | |
1842 | uint32_t dist_S_D; | |
1843 | ||
1844 | node_N = isis_spf_node_find(&spftree->adj_nodes, sadj_N->id); | |
1845 | assert(node_N); | |
1846 | ||
1847 | /* Distance from N to D. */ | |
1848 | if (lfa_calc_dist_destination(node_N->lfa.spftree, vertex_S_D, | |
1849 | &dist_N_D) | |
1850 | != 0) | |
1851 | return false; | |
1852 | ||
1853 | /* Distance from N to S (or PN). */ | |
1854 | if (CHECK_FLAG(sadj_primary->flags, F_ISIS_SPF_ADJ_BROADCAST)) { | |
1855 | static uint8_t pn_sysid[ISIS_SYS_ID_LEN + 1]; | |
1856 | ||
1857 | memcpy(pn_sysid, sadj_primary->id, ISIS_SYS_ID_LEN + 1); | |
1858 | if (lfa_calc_dist_node(node_N->lfa.spftree, pn_sysid, &dist_N_S) | |
1859 | != 0) | |
1860 | return false; | |
1861 | } else { | |
1862 | static uint8_t root_sysid[ISIS_SYS_ID_LEN + 1]; | |
1863 | ||
1864 | memcpy(root_sysid, spftree->sysid, ISIS_SYS_ID_LEN); | |
1865 | LSP_PSEUDO_ID(root_sysid) = 0; | |
1866 | if (lfa_calc_dist_node(node_N->lfa.spftree, root_sysid, | |
1867 | &dist_N_S) | |
1868 | != 0) | |
1869 | return false; | |
1870 | } | |
1871 | ||
1872 | /* Distance from S (or PN) to D. */ | |
1873 | vertex_S_D = listnode_head(vertex_S_D->parents); | |
1874 | dist_S_D = vertex_S_D->d_N; | |
1875 | if (CHECK_FLAG(sadj_primary->flags, F_ISIS_SPF_ADJ_BROADCAST)) | |
1876 | dist_S_D -= sadj_primary->metric; | |
1877 | ||
1878 | if (IS_DEBUG_LFA) | |
1879 | zlog_debug("ISIS-LFA: loop-free check: %u < %u + %u", dist_N_D, | |
1880 | dist_N_S, dist_S_D); | |
1881 | ||
1882 | if (dist_N_D < (dist_N_S + dist_S_D)) { | |
1883 | *lfa_metric = sadj_N->metric + dist_N_D; | |
1884 | return true; | |
1885 | } | |
1886 | ||
1887 | return false; | |
1888 | } | |
1889 | ||
1890 | /* | |
1891 | * Check loop-free criterion (RFC 5286's inequality 2): | |
1892 | * - Distance_opt(N, D) < Distance_opt(S, D) | |
1893 | */ | |
1894 | static bool clfa_downstream_check(struct isis_spftree *spftree, | |
1895 | struct isis_vertex *vertex_S_D, | |
1896 | struct isis_spf_adj *sadj_N) | |
1897 | { | |
1898 | struct isis_spf_node *node_N; | |
1899 | uint32_t dist_N_D; | |
1900 | uint32_t dist_S_D; | |
1901 | ||
1902 | node_N = isis_spf_node_find(&spftree->adj_nodes, sadj_N->id); | |
1903 | assert(node_N); | |
1904 | ||
1905 | /* Distance from N to D. */ | |
1906 | if (lfa_calc_dist_destination(node_N->lfa.spftree, vertex_S_D, | |
1907 | &dist_N_D) | |
1908 | != 0) | |
1909 | return false; | |
1910 | ||
1911 | /* Distance from S (or PN) to D. */ | |
1912 | vertex_S_D = listnode_head(vertex_S_D->parents); | |
1913 | dist_S_D = vertex_S_D->d_N; | |
1914 | ||
1915 | if (IS_DEBUG_LFA) | |
1916 | zlog_debug("ISIS-LFA: downstream check: %u < %u", dist_N_D, | |
1917 | dist_S_D); | |
1918 | ||
1919 | if (dist_N_D < dist_S_D) | |
1920 | return true; | |
1921 | ||
1922 | return false; | |
1923 | } | |
1924 | ||
1925 | /* | |
1926 | * Check loop-free criterion (RFC 5286's inequality 3): | |
1927 | * - Dist_opt(N, D) < Dist_opt(N, E) + Dist_opt(E, D) | |
1928 | */ | |
1929 | static bool clfa_node_protecting_check(struct isis_spftree *spftree, | |
1930 | struct isis_vertex *vertex_S_D, | |
1931 | struct isis_spf_adj *sadj_N, | |
1932 | struct isis_spf_adj *sadj_E) | |
1933 | { | |
1934 | struct isis_spf_node *node_N, *node_E; | |
1935 | uint32_t dist_N_D; | |
1936 | uint32_t dist_N_E; | |
1937 | uint32_t dist_E_D; | |
1938 | ||
1939 | node_N = isis_spf_node_find(&spftree->adj_nodes, sadj_N->id); | |
1940 | assert(node_N); | |
1941 | node_E = isis_spf_node_find(&spftree->adj_nodes, sadj_E->id); | |
1942 | assert(node_E); | |
1943 | ||
1944 | /* Distance from N to D. */ | |
1945 | if (lfa_calc_dist_destination(node_N->lfa.spftree, vertex_S_D, | |
1946 | &dist_N_D) | |
1947 | != 0) | |
1948 | return false; | |
1949 | ||
1950 | /* Distance from N to E. */ | |
1951 | if (lfa_calc_dist_node(node_N->lfa.spftree, node_E->sysid, &dist_N_E) | |
1952 | != 0) | |
1953 | return false; | |
1954 | ||
1955 | /* Distance from E to D. */ | |
1956 | if (lfa_calc_dist_destination(node_E->lfa.spftree, vertex_S_D, | |
1957 | &dist_E_D) | |
1958 | != 0) | |
1959 | return false; | |
1960 | ||
1961 | if (IS_DEBUG_LFA) | |
1962 | zlog_debug("ISIS-LFA: node protecting check: %u < %u + %u", | |
1963 | dist_N_D, dist_N_E, dist_E_D); | |
1964 | ||
1965 | return (dist_N_D < (dist_N_E + dist_E_D)); | |
1966 | } | |
1967 | ||
1968 | static struct list * | |
1969 | isis_lfa_tiebreakers(struct isis_area *area, struct isis_spftree *spftree, | |
1970 | struct lfa_protected_resource *resource, | |
1971 | struct isis_vertex *vertex, | |
1972 | struct isis_spf_adj *sadj_primary, struct list *lfa_list) | |
1973 | { | |
1974 | struct lfa_tiebreaker *tie_b; | |
1975 | int level = spftree->level; | |
1976 | struct list *filtered_lfa_list; | |
1977 | struct list *tent_lfa_list; | |
1978 | ||
1979 | filtered_lfa_list = list_dup(lfa_list); | |
1980 | filtered_lfa_list->del = NULL; | |
1981 | ||
1982 | if (listcount(filtered_lfa_list) == 1) | |
1983 | return filtered_lfa_list; | |
1984 | ||
1985 | /* Check tiebreakers in ascending order by index. */ | |
1986 | frr_each (lfa_tiebreaker_tree, &area->lfa_tiebreakers[level - 1], | |
1987 | tie_b) { | |
1988 | struct isis_vertex_adj *lfa; | |
1989 | struct listnode *node, *nnode; | |
1990 | uint32_t best_metric = UINT32_MAX; | |
1991 | ||
1992 | tent_lfa_list = list_dup(filtered_lfa_list); | |
1993 | ||
1994 | switch (tie_b->type) { | |
1995 | case LFA_TIEBREAKER_DOWNSTREAM: | |
1996 | for (ALL_LIST_ELEMENTS(tent_lfa_list, node, nnode, | |
1997 | lfa)) { | |
1998 | if (clfa_downstream_check(spftree, vertex, | |
1999 | lfa->sadj)) | |
2000 | continue; | |
2001 | ||
2002 | if (IS_DEBUG_LFA) | |
2003 | zlog_debug( | |
2004 | "ISIS-LFA: LFA %s doesn't satisfy the downstream condition", | |
2005 | print_sys_hostname( | |
2006 | lfa->sadj->id)); | |
2007 | listnode_delete(tent_lfa_list, lfa); | |
2008 | } | |
2009 | break; | |
2010 | case LFA_TIEBREAKER_LOWEST_METRIC: | |
2011 | /* Find the best metric first. */ | |
2012 | for (ALL_LIST_ELEMENTS_RO(tent_lfa_list, node, lfa)) { | |
2013 | if (lfa->lfa_metric < best_metric) | |
2014 | best_metric = lfa->lfa_metric; | |
2015 | } | |
2016 | ||
2017 | /* Remove LFAs that don't have the best metric. */ | |
2018 | for (ALL_LIST_ELEMENTS(tent_lfa_list, node, nnode, | |
2019 | lfa)) { | |
2020 | if (lfa->lfa_metric == best_metric) | |
2021 | continue; | |
2022 | ||
2023 | if (IS_DEBUG_LFA) | |
2024 | zlog_debug( | |
2025 | "ISIS-LFA: LFA %s doesn't have the lowest cost metric", | |
2026 | print_sys_hostname( | |
2027 | lfa->sadj->id)); | |
2028 | listnode_delete(tent_lfa_list, lfa); | |
2029 | } | |
2030 | break; | |
2031 | case LFA_TIEBREAKER_NODE_PROTECTING: | |
2032 | for (ALL_LIST_ELEMENTS(tent_lfa_list, node, nnode, | |
2033 | lfa)) { | |
2034 | if (clfa_node_protecting_check(spftree, vertex, | |
2035 | lfa->sadj, | |
2036 | sadj_primary)) | |
2037 | continue; | |
2038 | ||
2039 | if (IS_DEBUG_LFA) | |
2040 | zlog_debug( | |
2041 | "ISIS-LFA: LFA %s doesn't provide node protection", | |
2042 | print_sys_hostname( | |
2043 | lfa->sadj->id)); | |
2044 | listnode_delete(tent_lfa_list, lfa); | |
2045 | } | |
2046 | break; | |
2047 | } | |
2048 | ||
2049 | /* | |
2050 | * Decide what to do next based on the number of remaining LFAs. | |
2051 | */ | |
2052 | switch (listcount(tent_lfa_list)) { | |
2053 | case 0: | |
2054 | /* | |
2055 | * Ignore this tie-breaker since it excluded all LFAs. | |
2056 | * Move on to the next one (if any). | |
2057 | */ | |
2058 | list_delete(&tent_lfa_list); | |
2059 | break; | |
2060 | case 1: | |
2061 | /* Finish tie-breaking once we get a single LFA. */ | |
2062 | list_delete(&filtered_lfa_list); | |
2063 | filtered_lfa_list = tent_lfa_list; | |
2064 | return filtered_lfa_list; | |
2065 | default: | |
2066 | /* | |
2067 | * We still have two or more LFAs. Move on to the next | |
2068 | * tie-breaker (if any). | |
2069 | */ | |
2070 | list_delete(&filtered_lfa_list); | |
2071 | filtered_lfa_list = tent_lfa_list; | |
2072 | break; | |
2073 | } | |
2074 | } | |
2075 | ||
2076 | return filtered_lfa_list; | |
2077 | } | |
2078 | ||
2079 | void isis_lfa_compute(struct isis_area *area, struct isis_circuit *circuit, | |
2080 | struct isis_spftree *spftree, | |
2081 | struct lfa_protected_resource *resource) | |
2082 | { | |
2083 | struct isis_vertex *vertex; | |
2084 | struct listnode *vnode, *snode; | |
2085 | int level = spftree->level; | |
2086 | ||
2087 | resource->type = LFA_LINK_PROTECTION; | |
2088 | ||
2089 | if (IS_DEBUG_LFA) | |
2090 | zlog_debug("ISIS-LFA: computing local LFAs for %s", | |
2091 | lfa_protected_resource2str(resource)); | |
2092 | ||
2093 | for (ALL_QUEUE_ELEMENTS_RO(&spftree->paths, vnode, vertex)) { | |
2094 | struct list *lfa_list; | |
2095 | struct list *filtered_lfa_list; | |
2096 | struct isis_spf_adj *sadj_N; | |
2097 | struct isis_vertex_adj *vadj_primary; | |
2098 | struct isis_spf_adj *sadj_primary; | |
2099 | bool allow_ecmp; | |
2100 | uint32_t best_metric = UINT32_MAX; | |
2101 | char buf[VID2STR_BUFFER]; | |
2102 | ||
2103 | if (!VTYPE_IP(vertex->type)) | |
2104 | continue; | |
2105 | ||
2106 | vid2string(vertex, buf, sizeof(buf)); | |
2107 | ||
2108 | if (!spf_vertex_check_is_affected(vertex, spftree->sysid, | |
2109 | resource)) { | |
2110 | if (IS_DEBUG_LFA) | |
2111 | zlog_debug( | |
2112 | "ISIS-LFA: %s %s unaffected by %s", | |
2113 | vtype2string(vertex->type), buf, | |
2114 | lfa_protected_resource2str(resource)); | |
2115 | continue; | |
2116 | } | |
2117 | ||
2118 | if (IS_DEBUG_LFA) | |
2119 | zlog_debug("ISIS-LFA: checking %s %s w.r.t %s", | |
2120 | vtype2string(vertex->type), buf, | |
2121 | lfa_protected_resource2str(resource)); | |
2122 | ||
2123 | if (vertex->N.ip.priority | |
2124 | > area->lfa_priority_limit[level - 1]) { | |
2125 | if (IS_DEBUG_LFA) | |
2126 | zlog_debug( | |
2127 | "ISIS-LFA: skipping computing LFAs due to low prefix priority"); | |
2128 | continue; | |
2129 | } | |
2130 | ||
2131 | vadj_primary = listnode_head(vertex->Adj_N); | |
2132 | sadj_primary = vadj_primary->sadj; | |
2133 | ||
2134 | /* | |
2135 | * Loop over list of SPF adjacencies and compute a list of | |
2136 | * preliminary LFAs. | |
2137 | */ | |
2138 | lfa_list = list_new(); | |
2139 | lfa_list->del = isis_vertex_adj_free; | |
2140 | for (ALL_LIST_ELEMENTS_RO(spftree->sadj_list, snode, sadj_N)) { | |
2141 | uint32_t lfa_metric; | |
2142 | struct isis_vertex_adj *lfa; | |
2143 | struct isis_prefix_sid *psid = NULL; | |
2144 | bool last_hop = false; | |
2145 | ||
2146 | /* Skip pseudonodes. */ | |
2147 | if (LSP_PSEUDO_ID(sadj_N->id)) | |
2148 | continue; | |
2149 | ||
2150 | /* | |
2151 | * Skip nexthops that are along a link whose cost is | |
2152 | * infinite. | |
2153 | */ | |
2154 | if (CHECK_FLAG(sadj_N->flags, | |
2155 | F_ISIS_SPF_ADJ_METRIC_INFINITY)) | |
2156 | continue; | |
2157 | ||
2158 | /* Skip nexthops that have the overload bit set. */ | |
2159 | if (spftree->mtid != ISIS_MT_IPV4_UNICAST) { | |
2160 | struct isis_mt_router_info *mt_router_info; | |
2161 | ||
2162 | mt_router_info = | |
2163 | isis_tlvs_lookup_mt_router_info( | |
2164 | sadj_N->lsp->tlvs, | |
2165 | spftree->mtid); | |
2166 | if (mt_router_info && mt_router_info->overload) | |
2167 | continue; | |
2168 | } else if (ISIS_MASK_LSP_OL_BIT( | |
2169 | sadj_N->lsp->hdr.lsp_bits)) | |
2170 | continue; | |
2171 | ||
2172 | /* Skip primary nexthop. */ | |
2173 | if (spf_adj_check_is_affected(sadj_N, resource, NULL, | |
2174 | false)) | |
2175 | continue; | |
2176 | ||
2177 | /* Skip excluded interfaces as per the configuration. */ | |
2178 | if (circuit | |
2179 | && isis_lfa_excluded_iface_check( | |
2180 | circuit, level, | |
2181 | sadj_N->adj->circuit->interface->name)) | |
2182 | continue; | |
2183 | ||
2184 | if (IS_DEBUG_LFA) | |
2185 | zlog_debug( | |
2186 | "ISIS-LFA: checking candidate LFA %s", | |
2187 | print_sys_hostname(sadj_N->id)); | |
2188 | ||
2189 | /* Check loop-free criterion. */ | |
2190 | if (!clfa_loop_free_check(spftree, vertex, sadj_primary, | |
2191 | sadj_N, &lfa_metric)) { | |
2192 | if (IS_DEBUG_LFA) | |
2193 | zlog_debug( | |
2194 | "ISIS-LFA: LFA condition not met for %s", | |
2195 | print_sys_hostname(sadj_N->id)); | |
2196 | continue; | |
2197 | } | |
2198 | ||
2199 | if (lfa_metric < best_metric) | |
2200 | best_metric = lfa_metric; | |
2201 | ||
2202 | if (IS_DEBUG_LFA) | |
2203 | zlog_debug( | |
2204 | "ISIS-LFA: %s is a valid loop-free alternate", | |
2205 | print_sys_hostname(sadj_N->id)); | |
2206 | ||
2207 | if (vertex->N.ip.sr.present) { | |
2208 | psid = &vertex->N.ip.sr.sid; | |
2209 | if (lfa_metric == sadj_N->metric) | |
2210 | last_hop = true; | |
2211 | } | |
2212 | lfa = isis_vertex_adj_add(spftree, vertex, lfa_list, | |
2213 | sadj_N, psid, last_hop); | |
2214 | lfa->lfa_metric = lfa_metric; | |
2215 | } | |
2216 | ||
2217 | if (list_isempty(lfa_list)) { | |
2218 | if (IS_DEBUG_LFA) | |
2219 | zlog_debug( | |
2220 | "ISIS-LFA: no valid local LFAs found"); | |
2221 | list_delete(&lfa_list); | |
2222 | continue; | |
2223 | } | |
2224 | ||
2225 | SET_FLAG(vertex->flags, F_ISIS_VERTEX_LFA_PROTECTED); | |
2226 | ||
2227 | /* Check tie-breakers. */ | |
2228 | filtered_lfa_list = | |
2229 | isis_lfa_tiebreakers(area, spftree, resource, vertex, | |
2230 | sadj_primary, lfa_list); | |
2231 | ||
2232 | /* Create backup route using the best LFAs. */ | |
2233 | allow_ecmp = area->lfa_load_sharing[level - 1]; | |
2234 | isis_route_create(&vertex->N.ip.p.dest, &vertex->N.ip.p.src, | |
2235 | best_metric, vertex->depth, &vertex->N.ip.sr, | |
2236 | filtered_lfa_list, allow_ecmp, area, | |
2237 | spftree->route_table_backup); | |
2238 | spftree->lfa.protection_counters.lfa[vertex->N.ip.priority] += | |
2239 | 1; | |
2240 | ||
2241 | list_delete(&filtered_lfa_list); | |
2242 | list_delete(&lfa_list); | |
2243 | } | |
2244 | } | |
2245 | ||
2246 | static void isis_spf_run_tilfa(struct isis_area *area, | |
2247 | struct isis_circuit *circuit, | |
2248 | struct isis_spftree *spftree, | |
2249 | struct isis_spftree *spftree_reverse, | |
2250 | struct lfa_protected_resource *resource) | |
2251 | { | |
2252 | struct isis_spftree *spftree_pc_link; | |
2253 | struct isis_spftree *spftree_pc_node; | |
2254 | ||
2255 | /* Compute node protecting repair paths first (if necessary). */ | |
2256 | if (circuit->tilfa_node_protection[spftree->level - 1]) { | |
2257 | resource->type = LFA_NODE_PROTECTION; | |
2258 | spftree_pc_node = isis_tilfa_compute(area, spftree, | |
2259 | spftree_reverse, resource); | |
2260 | isis_spftree_del(spftree_pc_node); | |
2261 | ||
2262 | /* don't do link protection unless link-fallback is configured | |
2263 | */ | |
2264 | if (!circuit->tilfa_link_fallback[spftree->level - 1]) | |
2265 | return; | |
2266 | } | |
2267 | ||
2268 | /* Compute link protecting repair paths. */ | |
2269 | resource->type = LFA_LINK_PROTECTION; | |
2270 | spftree_pc_link = | |
2271 | isis_tilfa_compute(area, spftree, spftree_reverse, resource); | |
2272 | isis_spftree_del(spftree_pc_link); | |
2273 | } | |
2274 | ||
2275 | /** | |
2276 | * Run the LFA/RLFA/TI-LFA algorithms for all protected interfaces. | |
2277 | * | |
2278 | * @param area IS-IS area | |
2279 | * @param spftree IS-IS SPF tree | |
2280 | */ | |
2281 | void isis_spf_run_lfa(struct isis_area *area, struct isis_spftree *spftree) | |
2282 | { | |
2283 | struct isis_spftree *spftree_reverse = NULL; | |
2284 | struct isis_circuit *circuit; | |
2285 | struct listnode *node; | |
2286 | int level = spftree->level; | |
2287 | ||
2288 | /* Run reverse SPF locally. */ | |
2289 | if (area->rlfa_protected_links[level - 1] > 0 | |
2290 | || area->tilfa_protected_links[level - 1] > 0) | |
2291 | spftree_reverse = isis_spf_reverse_run(spftree); | |
2292 | ||
2293 | /* Run forward SPF on all adjacent routers. */ | |
2294 | isis_spf_run_neighbors(spftree); | |
2295 | ||
2296 | /* Check which interfaces are protected. */ | |
2297 | for (ALL_LIST_ELEMENTS_RO(area->circuit_list, node, circuit)) { | |
2298 | struct lfa_protected_resource resource = {}; | |
2299 | struct isis_adjacency *adj; | |
2300 | static uint8_t null_sysid[ISIS_SYS_ID_LEN + 1]; | |
2301 | ||
2302 | if (!(circuit->is_type & level)) | |
2303 | continue; | |
2304 | ||
2305 | if (!circuit->lfa_protection[level - 1] | |
2306 | && !circuit->tilfa_protection[level - 1]) | |
2307 | continue; | |
2308 | ||
2309 | /* Fill in the protected resource. */ | |
2310 | switch (circuit->circ_type) { | |
2311 | case CIRCUIT_T_BROADCAST: | |
2312 | if (level == ISIS_LEVEL1) | |
2313 | memcpy(resource.adjacency, | |
2314 | circuit->u.bc.l1_desig_is, | |
2315 | ISIS_SYS_ID_LEN + 1); | |
2316 | else | |
2317 | memcpy(resource.adjacency, | |
2318 | circuit->u.bc.l2_desig_is, | |
2319 | ISIS_SYS_ID_LEN + 1); | |
2320 | /* Do nothing if no DR was elected yet. */ | |
2321 | if (!memcmp(resource.adjacency, null_sysid, | |
2322 | ISIS_SYS_ID_LEN + 1)) | |
2323 | continue; | |
2324 | break; | |
2325 | case CIRCUIT_T_P2P: | |
2326 | adj = circuit->u.p2p.neighbor; | |
2327 | if (!adj) | |
2328 | continue; | |
2329 | memcpy(resource.adjacency, adj->sysid, ISIS_SYS_ID_LEN); | |
2330 | LSP_PSEUDO_ID(resource.adjacency) = 0; | |
2331 | break; | |
2332 | default: | |
2333 | continue; | |
2334 | } | |
2335 | ||
2336 | if (circuit->lfa_protection[level - 1]) { | |
2337 | /* Run local LFA. */ | |
2338 | isis_lfa_compute(area, circuit, spftree, &resource); | |
2339 | ||
2340 | if (circuit->rlfa_protection[level - 1]) { | |
2341 | struct isis_spftree *spftree_pc; | |
2342 | uint32_t max_metric; | |
2343 | ||
2344 | /* Run remote LFA. */ | |
2345 | assert(spftree_reverse); | |
2346 | max_metric = | |
2347 | circuit->rlfa_max_metric[level - 1]; | |
2348 | spftree_pc = isis_rlfa_compute( | |
2349 | area, spftree, spftree_reverse, | |
2350 | max_metric, &resource); | |
2351 | listnode_add(spftree->lfa.remote.pc_spftrees, | |
2352 | spftree_pc); | |
2353 | } | |
2354 | } else if (circuit->tilfa_protection[level - 1]) { | |
2355 | /* Run TI-LFA. */ | |
2356 | assert(spftree_reverse); | |
2357 | isis_spf_run_tilfa(area, circuit, spftree, | |
2358 | spftree_reverse, &resource); | |
2359 | } | |
2360 | } | |
2361 | ||
2362 | if (spftree_reverse) | |
2363 | isis_spftree_del(spftree_reverse); | |
2364 | } |