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