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