]> git.proxmox.com Git - mirror_frr.git/blame - isisd/isis_lfa.c
projects / mirror_frr.git / blame
? search:
summary | shortlog | log | commit | commitdiff | tree
blob | blame (incremental) | history | HEAD
Merge pull request #8666 from idryzhov/bgp-replace-as
[mirror_frr.git] / isisd / isis_lfa.c
CommitLineData
c951ee6e
RW		 1/*
2 * Copyright (C) 2020 NetDEF, Inc.
3 * Renato Westphal
4 *
5 * This program is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License as published by the Free
7 * Software Foundation; either version 2 of the License, or (at your option)
8 * any later version.
9 *
10 * This program is distributed in the hope that it will be useful, but WITHOUT
11 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
12 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for
13 * more details.
14 *
15 * You should have received a copy of the GNU General Public License along
16 * with this program; see the file COPYING; if not, write to the Free Software
17 * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
18 */
19
20#include <zebra.h>
21
22#include "linklist.h"
23#include "log.h"
24#include "memory.h"
25#include "vrf.h"
26#include "table.h"
27#include "srcdest_table.h"
16fe8cff
RW		 28#include "plist.h"
29#include "zclient.h"
c951ee6e
RW		 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"
16fe8cff
RW		 42#include "isis_zebra.h"
43#include "isis_errors.h"
c951ee6e
RW		 44
45DEFINE_MTYPE_STATIC(ISISD, ISIS_SPF_NODE, "ISIS SPF Node");
e886416f
RW		 46DEFINE_MTYPE_STATIC(ISISD, ISIS_LFA_TIEBREAKER, "ISIS LFA Tiebreaker");
47DEFINE_MTYPE_STATIC(ISISD, ISIS_LFA_EXCL_IFACE, "ISIS LFA Excluded Interface");
16fe8cff 48DEFINE_MTYPE_STATIC(ISISD, ISIS_RLFA, "ISIS Remote LFA");
66b9a381 49DEFINE_MTYPE(ISISD, ISIS_NEXTHOP_LABELS, "ISIS nexthop MPLS labels");
c951ee6e
RW		 50
51static 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}
56RB_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 */
63void 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 */
73void 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 */
98struct 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 */
120struct 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
e886416f
RW		 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 */
137int 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 */
154void 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 */
165void 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 */
187struct 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 */
209void 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
216static bool lfa_excl_interface_hash_cmp(const void *value1, const void *value2)
217{
218 return strmatch(value1, value2);
219}
220
221static unsigned int lfa_excl_interface_hash_make(const void *value)
222{
223 return string_hash_make(value);
224}
225
226static void *lfa_excl_interface_hash_alloc(void *p)
227{
228 return XSTRDUP(MTYPE_ISIS_LFA_EXCL_IFACE, p);
229}
230
231static 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 */
242void 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 */
254void 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 */
267void 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 */
281void 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 */
301bool 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
c951ee6e
RW		 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 */
319bool isis_lfa_excise_adj_check(const struct isis_spftree *spftree,
320 const uint8_t *id)
321{
322 const struct lfa_protected_resource *resource;
323
16fe8cff 324 if (spftree->type != SPF_TYPE_RLFA && spftree->type != SPF_TYPE_TI_LFA)
c951ee6e
RW		 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 */
347bool 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
c951ee6e
RW		 369struct tilfa_find_pnode_prefix_sid_args {
370 uint32_t sid_index;
371};
372
373static 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. */
396static 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
413struct tilfa_find_qnode_adj_sid_args {
414 const uint8_t *qnode_sysid;
415 mpls_label_t label;
416};
417
418static 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. */
438static 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 */
462static struct mpls_label_stack *
463tilfa_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)) {
4c75f7c7 480 const uint8_t *target_node;
c951ee6e
RW		 481 struct isis_sr_block *srgb;
482 mpls_label_t label;
483
484 switch (sid->type) {
485 case TILFA_SID_PREFIX:
4c75f7c7
RW		 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);
c951ee6e
RW		 491 if (!srgb) {
492 zlog_warn("%s: SRGB not found for node %s",
493 __func__,
4c75f7c7 494 print_sys_hostname(target_node));
c951ee6e
RW		 495 goto error;
496 }
497
498 /* Check if the SID index falls inside the SRGB. */
4c75f7c7 499 if (sid->value.index.value >= srgb->range_size) {
c951ee6e
RW		 500 flog_warn(
501 EC_ISIS_SID_OVERFLOW,
502 "%s: SID index %u falls outside remote SRGB range",
4c75f7c7 503 __func__, sid->value.index.value);
c951ee6e
RW		 504 goto error;
505 }
506
507 /*
508 * Prefix-SID: map SID index to label value within the
509 * SRGB.
510 */
4c75f7c7 511 label = srgb->lower_bound + sid->value.index.value;
c951ee6e
RW		 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
528error:
529 XFREE(MTYPE_ISIS_NEXTHOP_LABELS, label_stack);
530 return NULL;
531}
532
533static 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
5dd20c56
RW		 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
c951ee6e
RW		 552 if (!isis_vertex_adj_exists(spftree, vertex_pnode, sadj))
553 continue;
554
c951ee6e
RW		 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 */
578static 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. */
611static 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. */
618static 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];
4c75f7c7
RW		 629 struct isis_tilfa_sid sid_dest = {}, sid_qnode = {}, sid_pnode = {};
630 uint32_t sid_index;
c951ee6e
RW		 631 mpls_label_t label_qnode;
632
2866b119 633 if (IS_DEBUG_LFA) {
c951ee6e 634 vid2string(vertex, buf, sizeof(buf));
2866b119
RW		 635 zlog_debug("ISIS-LFA: vertex %s %s", vtype2string(vertex->type),
636 buf);
c951ee6e
RW		 637 }
638
4c75f7c7
RW		 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;
2866b119 645 if (IS_DEBUG_LFA)
4c75f7c7 646 zlog_debug(
2866b119 647 "ISIS-LFA: pushing Prefix-SID to %pFX (index %u)",
4c75f7c7
RW		 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
c951ee6e
RW		 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) {
784f92f0
RW		 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
c951ee6e
RW		 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) {
2866b119 691 zlog_warn("ISIS-LFA: failed to find %s->%s Adj-SID",
c951ee6e
RW		 692 print_sys_hostname(vertex->N.id),
693 print_sys_hostname(vertex_child->N.id));
694 return -1;
695 }
2866b119 696 if (IS_DEBUG_LFA)
c951ee6e 697 zlog_debug(
2866b119 698 "ISIS-LFA: pushing %s->%s Adj-SID (label %u)",
c951ee6e
RW		 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) {
c951ee6e
RW		 709 /* The same P-node can't be used more than once. */
710 if (isis_spf_node_find(used_pnodes, vertex->N.id)) {
2866b119 711 if (IS_DEBUG_LFA)
c951ee6e 712 zlog_debug(
2866b119 713 "ISIS-LFA: skipping already used P-node");
c951ee6e
RW		 714 return 0;
715 }
716 isis_spf_node_new(used_pnodes, vertex->N.id);
717
718 if (!vertex_child) {
2866b119 719 if (IS_DEBUG_LFA)
c951ee6e 720 zlog_debug(
2866b119 721 "ISIS-LFA: destination is within Ext-P-Space");
c951ee6e
RW		 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(
2866b119 729 "ISIS-LFA: failed to find Prefix-SID corresponding to PQ-node %s",
c951ee6e
RW		 730 print_sys_hostname(vertex->N.id));
731 return -1;
732 }
733
2866b119 734 if (IS_DEBUG_LFA)
c951ee6e 735 zlog_debug(
2866b119 736 "ISIS-LFA: pushing Node-SID to %s (index %u)",
c951ee6e
RW		 737 print_sys_hostname(vertex->N.id), sid_index);
738 sid_pnode.type = TILFA_SID_PREFIX;
4c75f7c7 739 sid_pnode.value.index.value = sid_index;
c951ee6e
RW		 740 listnode_add_head(repair_list, &sid_pnode);
741
742 /* Apply repair list. */
e886416f
RW		 743 if (spftree_pc->area->srdb.config.msd
744 && listcount(repair_list)
745 > spftree_pc->area->srdb.config.msd) {
6dfb7f59 746 zlog_warn(
2866b119 747 "ISIS-LFA: list of repair segments exceeds locally configured MSD (%u > %u)",
6dfb7f59
RW		 748 listcount(repair_list),
749 spftree_pc->area->srdb.config.msd);
750 return -1;
751 }
c951ee6e
RW		 752 if (tilfa_repair_list_apply(spftree_pc, vertex_dest, vertex,
753 repair_list)
754 != 0)
755 return -1;
756 return 0;
757 }
758
759parents:
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
779static 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
791static const char *
792lfa_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
805static bool
806spf_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
e886416f
RW		 829/* Check if the given vertex is affected by a given local failure. */
830static bool
831spf_vertex_check_is_affected(const struct isis_vertex *vertex,
832 const uint8_t *root_sysid,
833 const struct lfa_protected_resource *resource)
c951ee6e 834{
e886416f 835 struct isis_vertex_adj *vadj;
c951ee6e
RW		 836 struct listnode *node;
837 size_t affected_nhs = 0;
c951ee6e 838
d4fcd8bd
RW		 839 /* Local routes don't need protection. */
840 if (VTYPE_IP(vertex->type) && vertex->depth == 1)
841 return false;
842
e886416f 843 for (ALL_LIST_ELEMENTS_RO(vertex->Adj_N, node, vadj)) {
c951ee6e
RW		 844 struct isis_spf_adj *sadj = vadj->sadj;
845
e886416f
RW		 846 if (spf_adj_check_is_affected(sadj, resource, root_sysid,
847 false))
c951ee6e
RW		 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 */
e886416f 855 if (listcount(vertex->Adj_N) == affected_nhs)
c951ee6e
RW		 856 return true;
857
858 return false;
859}
860
16fe8cff
RW		 861/* Check if a given RLFA/TI-LFA post-convergence SPF vertex needs protection. */
862static bool lfa_check_needs_protection(const struct isis_spftree *spftree_pc,
863 const struct isis_vertex *vertex)
e886416f
RW		 864{
865 struct isis_vertex *vertex_old;
866
16fe8cff
RW		 867 /* Only local adjacencies need TI-LFA Adj-SID protection. */
868 if (spftree_pc->type == SPF_TYPE_TI_LFA && VTYPE_IS(vertex->type)
e886416f
RW		 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
16fe8cff
RW		 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
e886416f
RW		 882 return spf_vertex_check_is_affected(
883 vertex_old, spftree_pc->sysid,
884 &spftree_pc->lfa.protected_resource);
885}
886
c951ee6e
RW		 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 */
e886416f
RW		 896int isis_tilfa_check(struct isis_spftree *spftree_pc,
897 struct isis_vertex *vertex)
c951ee6e
RW		 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
16fe8cff 907 if (!lfa_check_needs_protection(spftree_pc, vertex)) {
2866b119 908 if (IS_DEBUG_LFA)
c951ee6e 909 zlog_debug(
2866b119 910 "ISIS-LFA: %s %s unaffected by %s",
816c583f
RW		 911 vtype2string(vertex->type),
912 vid2string(vertex, buf, sizeof(buf)),
c951ee6e
RW		 913 lfa_protected_resource2str(
914 &spftree_pc->lfa.protected_resource));
915
916 return -1;
917 }
918
919 /*
054fda12 920 * Check if the route/adjacency was already covered by node protection.
c951ee6e 921 */
054fda12
RW		 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)) {
2866b119 930 if (IS_DEBUG_LFA)
054fda12 931 zlog_debug(
2866b119 932 "ISIS-LFA: %s %s already covered by node protection",
816c583f
RW		 933 vtype2string(vertex->type),
934 vid2string(vertex, buf, sizeof(buf)));
054fda12
RW		 935
936 return -1;
937 }
938 }
c951ee6e
RW		 939 if (VTYPE_IP(vertex->type)) {
940 struct route_table *route_table;
941
942 route_table = spftree_pc->lfa.old.spftree->route_table_backup;
d47d6089 943 if (route_node_lookup(route_table, &vertex->N.ip.p.dest)) {
2866b119 944 if (IS_DEBUG_LFA)
c951ee6e 945 zlog_debug(
2866b119 946 "ISIS-LFA: %s %s already covered by node protection",
816c583f
RW		 947 vtype2string(vertex->type),
948 vid2string(vertex, buf, sizeof(buf)));
c951ee6e
RW		 949
950 return -1;
951 }
952 }
953
2866b119 954 if (IS_DEBUG_LFA)
c951ee6e 955 zlog_debug(
2866b119 956 "ISIS-LFA: computing repair path(s) of %s %s w.r.t %s",
816c583f
RW		 957 vtype2string(vertex->type),
958 vid2string(vertex, buf, sizeof(buf)),
c951ee6e
RW		 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)
6dfb7f59 971 zlog_warn(
2866b119 972 "ISIS-LFA: failed to compute repair path(s) of %s %s w.r.t %s",
816c583f
RW		 973 vtype2string(vertex->type),
974 vid2string(vertex, buf, sizeof(buf)),
6dfb7f59
RW		 975 lfa_protected_resource2str(
976 &spftree_pc->lfa.protected_resource));
c951ee6e
RW		 977
978 return ret;
979}
980
981static bool
982spf_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
1000static 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;
c951ee6e
RW		 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. */
1063static 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
c951ee6e
RW		 1087 if (!vertex_is_affected(spftree_root, adj_nodes, p_space,
1088 vertex, resource)) {
2866b119 1089 if (IS_DEBUG_LFA)
c951ee6e 1090 zlog_debug(
2866b119 1091 "ISIS-LFA: adding %s",
c951ee6e
RW		 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 *
2866b119 1105 * @return Pointer to new SPF tree structure.
c951ee6e
RW		 1106 */
1107struct 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 */
1124static 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
2866b119
RW		 1137 if (IS_DEBUG_LFA)
1138 zlog_debug("ISIS-LFA: computing P-space (self)");
c951ee6e
RW		 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)) {
2866b119
RW		 1145 if (IS_DEBUG_LFA)
1146 zlog_debug("ISIS-LFA: computing Q-space (%s)",
1147 print_sys_hostname(adj_node->sysid));
c951ee6e
RW		 1148
1149 /*
1150 * Compute the reverse SPF in the behalf of the node
7c3be15f
FR		 1151 * adjacent to the failure, if we haven't done that
1152 * before
c951ee6e 1153 */
7c3be15f
FR		 1154 if (!adj_node->lfa.spftree_reverse)
1155 adj_node->lfa.spftree_reverse =
1156 isis_spf_reverse_run(
1157 adj_node->lfa.spftree);
c951ee6e
RW		 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 {
2866b119
RW		 1164 if (IS_DEBUG_LFA)
1165 zlog_debug("ISIS-LFA: computing P-space (%s)",
1166 print_sys_hostname(adj_node->sysid));
c951ee6e
RW		 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 */
1184struct 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
2866b119 1192 if (IS_DEBUG_LFA)
16fe8cff 1193 zlog_debug("ISIS-LFA: computing TI-LFAs for %s",
c951ee6e
RW		 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
2866b119 1218 if (IS_DEBUG_LFA)
c951ee6e 1219 zlog_debug(
2866b119 1220 "ISIS-LFA: computing the post convergence SPT w.r.t. %s",
c951ee6e
RW		 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 */
1240int 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) {
2866b119
RW		 1250 if (IS_DEBUG_LFA)
1251 zlog_debug("ISIS-LFA: running SPF on neighbor %s",
c951ee6e
RW		 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
16fe8cff
RW		 1265/* Find Router ID of PQ node. */
1266static 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. */
1282static const struct in_addr *
1283rlfa_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
1355parents:
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
1368int rlfa_cmp(const struct rlfa *a, const struct rlfa *b)
1369{
1370 return prefix_cmp(&a->prefix, &b->prefix);
1371}
1372
1373static 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
1389static 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
1395static 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
1404static 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
1416static 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
1467int 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
1532void 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
1549void isis_rlfa_list_init(struct isis_spftree *spftree)
1550{
1551 rlfa_tree_init(&spftree->lfa.remote.rlfas);
1552}
1553
1554void 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
1565void 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
1630void 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 */
1666void 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 */
1721struct 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
e886416f
RW		 1756/* Calculate the distance from the root node to the given IP destination. */
1757static 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. */
1805static 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 */
1833static 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 */
1894static 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 */
1929static 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
1968static struct list *
16fe8cff 1969isis_lfa_tiebreakers(struct isis_area *area, struct isis_spftree *spftree,
e886416f
RW		 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
2079void 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
16fe8cff
RW		 2089 if (IS_DEBUG_LFA)
2090 zlog_debug("ISIS-LFA: computing local LFAs for %s",
2091 lfa_protected_resource2str(resource));
2092
e886416f
RW		 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(
16fe8cff
RW		 2112 "ISIS-LFA: %s %s unaffected by %s",
2113 vtype2string(vertex->type), buf,
e886416f
RW		 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)
16fe8cff
RW		 2219 zlog_debug(
2220 "ISIS-LFA: no valid local LFAs found");
e886416f
RW		 2221 list_delete(&lfa_list);
2222 continue;
2223 }
2224
16fe8cff
RW		 2225 SET_FLAG(vertex->flags, F_ISIS_VERTEX_LFA_PROTECTED);
2226
e886416f
RW		 2227 /* Check tie-breakers. */
2228 filtered_lfa_list =
16fe8cff
RW		 2229 isis_lfa_tiebreakers(area, spftree, resource, vertex,
2230 sadj_primary, lfa_list);
e886416f
RW		 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);
fc156c28
RW		 2238 spftree->lfa.protection_counters.lfa[vertex->N.ip.priority] +=
2239 1;
e886416f
RW		 2240
2241 list_delete(&filtered_lfa_list);
2242 list_delete(&lfa_list);
2243 }
2244}
2245
2246static 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);
ce4eccfa
FR		 2261
2262 /* don't do link protection unless link-fallback is configured
2263 */
2264 if (!circuit->tilfa_link_fallback[spftree->level - 1])
2265 return;
e886416f
RW		 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
c951ee6e 2275/**
16fe8cff 2276 * Run the LFA/RLFA/TI-LFA algorithms for all protected interfaces.
c951ee6e
RW		 2277 *
2278 * @param area IS-IS area
2279 * @param spftree IS-IS SPF tree
2280 */
2281void isis_spf_run_lfa(struct isis_area *area, struct isis_spftree *spftree)
2282{
e886416f 2283 struct isis_spftree *spftree_reverse = NULL;
c951ee6e
RW		 2284 struct isis_circuit *circuit;
2285 struct listnode *node;
e886416f
RW		 2286 int level = spftree->level;
2287
c951ee6e 2288 /* Run reverse SPF locally. */
16fe8cff
RW		 2289 if (area->rlfa_protected_links[level - 1] > 0
2290 || area->tilfa_protected_links[level - 1] > 0)
e886416f 2291 spftree_reverse = isis_spf_reverse_run(spftree);
c951ee6e
RW		 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;
c951ee6e
RW		 2300 static uint8_t null_sysid[ISIS_SYS_ID_LEN + 1];
2301
e886416f 2302 if (!(circuit->is_type & level))
c951ee6e
RW		 2303 continue;
2304
e886416f
RW		 2305 if (!circuit->lfa_protection[level - 1]
2306 && !circuit->tilfa_protection[level - 1])
c951ee6e
RW		 2307 continue;
2308
2309 /* Fill in the protected resource. */
2310 switch (circuit->circ_type) {
2311 case CIRCUIT_T_BROADCAST:
e886416f 2312 if (level == ISIS_LEVEL1)
c951ee6e
RW		 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
16fe8cff
RW		 2336 if (circuit->lfa_protection[level - 1]) {
2337 /* Run local LFA. */
e886416f 2338 isis_lfa_compute(area, circuit, spftree, &resource);
16fe8cff
RW		 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. */
e886416f
RW		 2356 assert(spftree_reverse);
2357 isis_spf_run_tilfa(area, circuit, spftree,
2358 spftree_reverse, &resource);
c951ee6e 2359 }
c951ee6e
RW		 2360 }
2361
16fe8cff 2362 if (spftree_reverse)
e886416f 2363 isis_spftree_del(spftree_reverse);
c951ee6e 2364}
FRRouting mirror