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