diff options
Diffstat (limited to 'isisd/isis_lfa.c')
| -rw-r--r-- | isisd/isis_lfa.c | 2366 |
1 files changed, 2366 insertions, 0 deletions
diff --git a/isisd/isis_lfa.c b/isisd/isis_lfa.c new file mode 100644 index 0000000..c4fadcb --- /dev/null +++ b/isisd/isis_lfa.c @@ -0,0 +1,2366 @@ +/* + * Copyright (C) 2020 NetDEF, Inc. + * Renato Westphal + * + * This program is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License as published by the Free + * Software Foundation; either version 2 of the License, or (at your option) + * any later version. + * + * This program is distributed in the hope that it will be useful, but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for + * more details. + * + * You should have received a copy of the GNU General Public License along + * with this program; see the file COPYING; if not, write to the Free Software + * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA + */ + +#include <zebra.h> + +#include "linklist.h" +#include "log.h" +#include "memory.h" +#include "vrf.h" +#include "table.h" +#include "srcdest_table.h" +#include "plist.h" +#include "zclient.h" + +#include "isis_common.h" +#include "isisd.h" +#include "isis_misc.h" +#include "isis_adjacency.h" +#include "isis_circuit.h" +#include "isis_lsp.h" +#include "isis_spf.h" +#include "isis_route.h" +#include "isis_mt.h" +#include "isis_tlvs.h" +#include "isis_spf_private.h" +#include "isis_zebra.h" +#include "isis_errors.h" + +DEFINE_MTYPE_STATIC(ISISD, ISIS_SPF_NODE, "ISIS SPF Node"); +DEFINE_MTYPE_STATIC(ISISD, ISIS_LFA_TIEBREAKER, "ISIS LFA Tiebreaker"); +DEFINE_MTYPE_STATIC(ISISD, ISIS_LFA_EXCL_IFACE, "ISIS LFA Excluded Interface"); +DEFINE_MTYPE_STATIC(ISISD, ISIS_RLFA, "ISIS Remote LFA"); +DEFINE_MTYPE(ISISD, ISIS_NEXTHOP_LABELS, "ISIS nexthop MPLS labels"); + +static inline int isis_spf_node_compare(const struct isis_spf_node *a, + const struct isis_spf_node *b) +{ + return memcmp(a->sysid, b->sysid, sizeof(a->sysid)); +} +RB_GENERATE(isis_spf_nodes, isis_spf_node, entry, isis_spf_node_compare) + +/** + * Initialize list of SPF nodes. + * + * @param nodes List of SPF nodes + */ +void isis_spf_node_list_init(struct isis_spf_nodes *nodes) +{ + RB_INIT(isis_spf_nodes, nodes); +} + +/** + * Clear list of SPF nodes, releasing all allocated memory. + * + * @param nodes List of SPF nodes + */ +void isis_spf_node_list_clear(struct isis_spf_nodes *nodes) +{ + while (!RB_EMPTY(isis_spf_nodes, nodes)) { + struct isis_spf_node *node = RB_ROOT(isis_spf_nodes, nodes); + + if (node->adjacencies) + list_delete(&node->adjacencies); + if (node->lfa.spftree) + isis_spftree_del(node->lfa.spftree); + if (node->lfa.spftree_reverse) + isis_spftree_del(node->lfa.spftree_reverse); + isis_spf_node_list_clear(&node->lfa.p_space); + RB_REMOVE(isis_spf_nodes, nodes, node); + XFREE(MTYPE_ISIS_SPF_NODE, node); + } +} + +/** + * Add new node to list of SPF nodes. + * + * @param nodes List of SPF nodes + * @param sysid Node System ID + * + * @return Pointer to new IS-IS SPF node structure. + */ +struct isis_spf_node *isis_spf_node_new(struct isis_spf_nodes *nodes, + const uint8_t *sysid) +{ + struct isis_spf_node *node; + + node = XCALLOC(MTYPE_ISIS_SPF_NODE, sizeof(*node)); + memcpy(node->sysid, sysid, sizeof(node->sysid)); + node->adjacencies = list_new(); + isis_spf_node_list_init(&node->lfa.p_space); + RB_INSERT(isis_spf_nodes, nodes, node); + + return node; +} + +/** + * Lookup SPF node by its System ID on the given list. + * + * @param nodes List of SPF nodes + * @param sysid Node System ID + * + * @return Pointer to SPF node if found, NULL otherwise + */ +struct isis_spf_node *isis_spf_node_find(const struct isis_spf_nodes *nodes, + const uint8_t *sysid) +{ + struct isis_spf_node node = {}; + + memcpy(node.sysid, sysid, sizeof(node.sysid)); + return RB_FIND(isis_spf_nodes, nodes, &node); +} + +/** + * LFA tiebreaker RB-tree comparison function. + * + * @param a First LFA tiebreaker + * @param b Second LFA tiebreaker + * + * @return -1 (a < b), 0 (a == b) or +1 (a > b) + */ +int lfa_tiebreaker_cmp(const struct lfa_tiebreaker *a, + const struct lfa_tiebreaker *b) +{ + if (a->index < b->index) + return -1; + if (a->index > b->index) + return 1; + + return a->type - b->type; +} + +/** + * Initialize list of LFA tie-breakers. + * + * @param area IS-IS area + * @param level IS-IS level + */ +void isis_lfa_tiebreakers_init(struct isis_area *area, int level) +{ + lfa_tiebreaker_tree_init(&area->lfa_tiebreakers[level - 1]); +} + +/** + * Clear list of LFA tie-breakers, releasing all allocated memory. + * + * @param area IS-IS area + * @param level IS-IS level + */ +void isis_lfa_tiebreakers_clear(struct isis_area *area, int level) +{ + while (lfa_tiebreaker_tree_count(&area->lfa_tiebreakers[level - 1]) + > 0) { + struct lfa_tiebreaker *tie_b; + + tie_b = lfa_tiebreaker_tree_first( + &area->lfa_tiebreakers[level - 1]); + isis_lfa_tiebreaker_delete(area, level, tie_b); + } +} + +/** + * Add new LFA tie-breaker to list of LFA tie-breakers. + * + * @param area IS-IS area + * @param level IS-IS level + * @param index LFA tie-breaker index + * @param type LFA tie-breaker type + * + * @return Pointer to new LFA tie-breaker structure. + */ +struct lfa_tiebreaker *isis_lfa_tiebreaker_add(struct isis_area *area, + int level, uint8_t index, + enum lfa_tiebreaker_type type) +{ + struct lfa_tiebreaker *tie_b; + + tie_b = XCALLOC(MTYPE_ISIS_LFA_TIEBREAKER, sizeof(*tie_b)); + tie_b->index = index; + tie_b->type = type; + tie_b->area = area; + lfa_tiebreaker_tree_add(&area->lfa_tiebreakers[level - 1], tie_b); + + return tie_b; +} + +/** + * Remove LFA tie-breaker from list of LFA tie-breakers. + * + * @param area IS-IS area + * @param level IS-IS level + * @param tie_b Pointer to LFA tie-breaker structure + */ +void isis_lfa_tiebreaker_delete(struct isis_area *area, int level, + struct lfa_tiebreaker *tie_b) +{ + lfa_tiebreaker_tree_del(&area->lfa_tiebreakers[level - 1], tie_b); + XFREE(MTYPE_ISIS_LFA_TIEBREAKER, tie_b); +} + +static bool lfa_excl_interface_hash_cmp(const void *value1, const void *value2) +{ + return strmatch(value1, value2); +} + +static unsigned int lfa_excl_interface_hash_make(const void *value) +{ + return string_hash_make(value); +} + +static void *lfa_excl_interface_hash_alloc(void *p) +{ + return XSTRDUP(MTYPE_ISIS_LFA_EXCL_IFACE, p); +} + +static void lfa_excl_interface_hash_free(void *arg) +{ + XFREE(MTYPE_ISIS_LFA_EXCL_IFACE, arg); +} + +/** + * Initialize hash table of LFA excluded interfaces. + * + * @param circuit IS-IS interface + * @param level IS-IS level + */ +void isis_lfa_excluded_ifaces_init(struct isis_circuit *circuit, int level) +{ + circuit->lfa_excluded_ifaces[level - 1] = hash_create( + lfa_excl_interface_hash_make, lfa_excl_interface_hash_cmp, + "LFA Excluded Interfaces"); +} + +/** + * Clear hash table of LFA excluded interfaces, releasing all allocated memory. + * + * @param nodes List of SPF nodes + */ +void isis_lfa_excluded_ifaces_clear(struct isis_circuit *circuit, int level) +{ + hash_clean(circuit->lfa_excluded_ifaces[level - 1], + lfa_excl_interface_hash_free); +} + +/** + * Add new interface to hash table of excluded interfaces. + * + * @param circuit IS-IS interface + * @param level IS-IS level + * @param ifname Excluded interface name + */ +void isis_lfa_excluded_iface_add(struct isis_circuit *circuit, int level, + const char *ifname) +{ + (void)hash_get(circuit->lfa_excluded_ifaces[level - 1], (char *)ifname, + lfa_excl_interface_hash_alloc); +} + +/** + * Remove interface from hash table of excluded interfaces. + * + * @param circuit IS-IS interface + * @param level IS-IS level + * @param ifname Excluded interface name + */ +void isis_lfa_excluded_iface_delete(struct isis_circuit *circuit, int level, + const char *ifname) +{ + char *found; + + found = hash_lookup(circuit->lfa_excluded_ifaces[level - 1], + (char *)ifname); + if (found) { + hash_release(circuit->lfa_excluded_ifaces[level - 1], found); + lfa_excl_interface_hash_free(found); + } +} + +/** + * Lookup excluded interface. + * + * @param circuit IS-IS interface + * @param level IS-IS level + * @param ifname Excluded interface name + */ +bool isis_lfa_excluded_iface_check(struct isis_circuit *circuit, int level, + const char *ifname) +{ + return hash_lookup(circuit->lfa_excluded_ifaces[level - 1], + (char *)ifname); +} + +/** + * Check if a given IS-IS adjacency needs to be excised when computing the SPF + * post-convergence tree. + * + * @param spftree IS-IS SPF tree + * @param id Adjacency System ID (or LAN ID of the designated router + * for broadcast interfaces) + * + * @return true if the adjacency needs to be excised, false + * otherwise + */ +bool isis_lfa_excise_adj_check(const struct isis_spftree *spftree, + const uint8_t *id) +{ + const struct lfa_protected_resource *resource; + + if (spftree->type != SPF_TYPE_RLFA && spftree->type != SPF_TYPE_TI_LFA) + return false; + + /* + * Adjacencies formed over the failed interface should be excised both + * when using link and node protection. + */ + resource = &spftree->lfa.protected_resource; + if (!memcmp(resource->adjacency, id, ISIS_SYS_ID_LEN + 1)) + return true; + + return false; +} + +/** + * Check if a given IS-IS node needs to be excised when computing the SPF + * post-convergence tree. + * + * @param spftree IS-IS SPF tree + * @param id Node System ID + * + * @return true if the node needs to be excised, false otherwise + */ +bool isis_lfa_excise_node_check(const struct isis_spftree *spftree, + const uint8_t *id) +{ + const struct lfa_protected_resource *resource; + + if (spftree->type != SPF_TYPE_TI_LFA) + return false; + + /* + * When using node protection, nodes reachable over the failed interface + * must be excised. + */ + resource = &spftree->lfa.protected_resource; + if (resource->type == LFA_LINK_PROTECTION) + return false; + + if (isis_spf_node_find(&resource->nodes, id)) + return true; + + return false; +} + +struct tilfa_find_pnode_prefix_sid_args { + uint32_t sid_index; +}; + +static int tilfa_find_pnode_prefix_sid_cb(const struct prefix *prefix, + uint32_t metric, bool external, + struct isis_subtlvs *subtlvs, + void *arg) +{ + struct tilfa_find_pnode_prefix_sid_args *args = arg; + struct isis_prefix_sid *psid; + + if (!subtlvs || subtlvs->prefix_sids.count == 0) + return LSP_ITER_CONTINUE; + + psid = (struct isis_prefix_sid *)subtlvs->prefix_sids.head; + + /* Require the node flag to be set. */ + if (!CHECK_FLAG(psid->flags, ISIS_PREFIX_SID_NODE)) + return LSP_ITER_CONTINUE; + + args->sid_index = psid->value; + + return LSP_ITER_STOP; +} + +/* Find Prefix-SID associated to a System ID. */ +static uint32_t tilfa_find_pnode_prefix_sid(struct isis_spftree *spftree, + const uint8_t *sysid) +{ + struct isis_lsp *lsp; + struct tilfa_find_pnode_prefix_sid_args args; + + lsp = isis_root_system_lsp(spftree->lspdb, sysid); + if (!lsp) + return UINT32_MAX; + + args.sid_index = UINT32_MAX; + isis_lsp_iterate_ip_reach(lsp, spftree->family, spftree->mtid, + tilfa_find_pnode_prefix_sid_cb, &args); + + return args.sid_index; +} + +struct tilfa_find_qnode_adj_sid_args { + const uint8_t *qnode_sysid; + mpls_label_t label; +}; + +static int tilfa_find_qnode_adj_sid_cb(const uint8_t *id, uint32_t metric, + bool oldmetric, + struct isis_ext_subtlvs *subtlvs, + void *arg) +{ + struct tilfa_find_qnode_adj_sid_args *args = arg; + struct isis_adj_sid *adj_sid; + + if (memcmp(id, args->qnode_sysid, ISIS_SYS_ID_LEN)) + return LSP_ITER_CONTINUE; + if (!subtlvs || subtlvs->adj_sid.count == 0) + return LSP_ITER_CONTINUE; + + adj_sid = (struct isis_adj_sid *)subtlvs->adj_sid.head; + args->label = adj_sid->sid; + + return LSP_ITER_STOP; +} + +/* Find Adj-SID associated to a pair of System IDs. */ +static mpls_label_t tilfa_find_qnode_adj_sid(struct isis_spftree *spftree, + const uint8_t *source_sysid, + const uint8_t *qnode_sysid) +{ + struct isis_lsp *lsp; + struct tilfa_find_qnode_adj_sid_args args; + + lsp = isis_root_system_lsp(spftree->lspdb, source_sysid); + if (!lsp) + return MPLS_INVALID_LABEL; + + args.qnode_sysid = qnode_sysid; + args.label = MPLS_INVALID_LABEL; + isis_lsp_iterate_is_reach(lsp, spftree->mtid, + tilfa_find_qnode_adj_sid_cb, &args); + + return args.label; +} + +/* + * Compute the MPLS label stack associated to a TI-LFA repair list. This + * needs to be computed separately for each adjacency since different + * neighbors can have different SRGBs. + */ +static struct mpls_label_stack * +tilfa_compute_label_stack(struct lspdb_head *lspdb, + const struct isis_spf_adj *sadj, + const struct list *repair_list) +{ + struct mpls_label_stack *label_stack; + struct isis_tilfa_sid *sid; + struct listnode *node; + size_t i = 0; + + /* Allocate label stack. */ + label_stack = XCALLOC(MTYPE_ISIS_NEXTHOP_LABELS, + sizeof(struct mpls_label_stack) + + listcount(repair_list) + * sizeof(mpls_label_t)); + label_stack->num_labels = listcount(repair_list); + + for (ALL_LIST_ELEMENTS_RO(repair_list, node, sid)) { + const uint8_t *target_node; + struct isis_sr_block *srgb; + mpls_label_t label; + + switch (sid->type) { + case TILFA_SID_PREFIX: + if (sid->value.index.remote) + target_node = sid->value.index.remote_sysid; + else + target_node = sadj->id; + srgb = isis_sr_find_srgb(lspdb, target_node); + if (!srgb) { + zlog_warn("%s: SRGB not found for node %s", + __func__, + print_sys_hostname(target_node)); + goto error; + } + + /* Check if the SID index falls inside the SRGB. */ + if (sid->value.index.value >= srgb->range_size) { + flog_warn( + EC_ISIS_SID_OVERFLOW, + "%s: SID index %u falls outside remote SRGB range", + __func__, sid->value.index.value); + goto error; + } + + /* + * Prefix-SID: map SID index to label value within the + * SRGB. + */ + label = srgb->lower_bound + sid->value.index.value; + break; + case TILFA_SID_ADJ: + /* Adj-SID: absolute label value can be used directly */ + label = sid->value.label; + break; + default: + flog_err(EC_LIB_DEVELOPMENT, + "%s: unknown TI-LFA SID type [%u]", __func__, + sid->type); + exit(1); + } + label_stack->label[i++] = label; + } + + return label_stack; + +error: + XFREE(MTYPE_ISIS_NEXTHOP_LABELS, label_stack); + return NULL; +} + +static int tilfa_repair_list_apply(struct isis_spftree *spftree, + struct isis_vertex *vertex_dest, + const struct isis_vertex *vertex_pnode, + const struct list *repair_list) +{ + struct isis_vertex_adj *vadj; + struct listnode *node; + + for (ALL_LIST_ELEMENTS_RO(vertex_dest->Adj_N, node, vadj)) { + struct isis_spf_adj *sadj = vadj->sadj; + struct mpls_label_stack *label_stack; + + /* + * Don't try to apply the repair list if one was already applied + * before (can't have ECMP past the P-node). + */ + if (vadj->label_stack) + continue; + + if (!isis_vertex_adj_exists(spftree, vertex_pnode, sadj)) + continue; + + label_stack = tilfa_compute_label_stack(spftree->lspdb, sadj, + repair_list); + if (!label_stack) { + char buf[VID2STR_BUFFER]; + + vid2string(vertex_dest, buf, sizeof(buf)); + zlog_warn( + "%s: %s %s adjacency %s: failed to compute label stack", + __func__, vtype2string(vertex_dest->type), buf, + print_sys_hostname(sadj->id)); + return -1; + } + + vadj->label_stack = label_stack; + } + + return 0; +} + +/* + * Check if a node belongs to the extended P-space corresponding to a given + * destination. + */ +static bool lfa_ext_p_space_check(const struct isis_spftree *spftree_pc, + const struct isis_vertex *vertex_dest, + const struct isis_vertex *vertex) +{ + struct isis_spftree *spftree_old = spftree_pc->lfa.old.spftree; + struct isis_vertex_adj *vadj; + struct listnode *node; + + /* Check the local P-space first. */ + if (isis_spf_node_find(&spftree_pc->lfa.p_space, vertex->N.id)) + return true; + + /* + * Check the P-space of the adjacent routers used to reach the + * destination. + */ + for (ALL_LIST_ELEMENTS_RO(vertex_dest->Adj_N, node, vadj)) { + struct isis_spf_adj *sadj = vadj->sadj; + struct isis_spf_node *adj_node; + + adj_node = + isis_spf_node_find(&spftree_old->adj_nodes, sadj->id); + if (!adj_node) + continue; + + if (isis_spf_node_find(&adj_node->lfa.p_space, vertex->N.id)) + return true; + } + + return false; +} + +/* Check if a node belongs to the Q-space. */ +static bool lfa_q_space_check(const struct isis_spftree *spftree_pc, + const struct isis_vertex *vertex) +{ + return isis_spf_node_find(&spftree_pc->lfa.q_space, vertex->N.id); +} + +/* This is a recursive function. */ +static int tilfa_build_repair_list(struct isis_spftree *spftree_pc, + struct isis_vertex *vertex_dest, + const struct isis_vertex *vertex, + const struct isis_vertex *vertex_child, + struct isis_spf_nodes *used_pnodes, + struct list *repair_list) +{ + struct isis_vertex *pvertex; + struct listnode *node; + bool is_pnode, is_qnode; + char buf[VID2STR_BUFFER]; + struct isis_tilfa_sid sid_dest = {}, sid_qnode = {}, sid_pnode = {}; + uint32_t sid_index; + mpls_label_t label_qnode; + + if (IS_DEBUG_LFA) { + vid2string(vertex, buf, sizeof(buf)); + zlog_debug("ISIS-LFA: vertex %s %s", vtype2string(vertex->type), + buf); + } + + /* Push original Prefix-SID label when necessary. */ + if (VTYPE_IP(vertex->type) && vertex->N.ip.sr.present) { + pvertex = listnode_head(vertex->parents); + assert(pvertex); + + sid_index = vertex->N.ip.sr.sid.value; + if (IS_DEBUG_LFA) + zlog_debug( + "ISIS-LFA: pushing Prefix-SID to %pFX (index %u)", + &vertex->N.ip.p.dest, sid_index); + sid_dest.type = TILFA_SID_PREFIX; + sid_dest.value.index.value = sid_index; + sid_dest.value.index.remote = true; + memcpy(sid_dest.value.index.remote_sysid, pvertex->N.id, + sizeof(sid_dest.value.index.remote_sysid)); + listnode_add_head(repair_list, &sid_dest); + } + + if (!vertex_child) + goto parents; + if (vertex->type != VTYPE_NONPSEUDO_IS + && vertex->type != VTYPE_NONPSEUDO_TE_IS) + goto parents; + if (!VTYPE_IS(vertex_child->type)) + vertex_child = NULL; + + /* Check if node is part of the extended P-space and/or Q-space. */ + is_pnode = lfa_ext_p_space_check(spftree_pc, vertex_dest, vertex); + is_qnode = lfa_q_space_check(spftree_pc, vertex); + + /* Push Adj-SID label when necessary. */ + if ((!is_qnode + || spftree_pc->lfa.protected_resource.type == LFA_NODE_PROTECTION) + && vertex_child) { + /* + * If vertex is the penultimate hop router, then pushing an + * Adj-SID towards the final hop means that the No-PHP flag of + * the original Prefix-SID must be honored. We do that by + * removing the previously added Prefix-SID from the repair list + * when those conditions are met. + */ + if (vertex->depth == (vertex_dest->depth - 2) + && VTYPE_IP(vertex_dest->type) + && vertex_dest->N.ip.sr.present + && !CHECK_FLAG(vertex_dest->N.ip.sr.sid.flags, + ISIS_PREFIX_SID_NO_PHP)) { + list_delete_all_node(repair_list); + } + + label_qnode = tilfa_find_qnode_adj_sid(spftree_pc, vertex->N.id, + vertex_child->N.id); + if (label_qnode == MPLS_INVALID_LABEL) { + zlog_warn("ISIS-LFA: failed to find %s->%s Adj-SID", + print_sys_hostname(vertex->N.id), + print_sys_hostname(vertex_child->N.id)); + return -1; + } + if (IS_DEBUG_LFA) + zlog_debug( + "ISIS-LFA: pushing %s->%s Adj-SID (label %u)", + print_sys_hostname(vertex->N.id), + print_sys_hostname(vertex_child->N.id), + label_qnode); + sid_qnode.type = TILFA_SID_ADJ; + sid_qnode.value.label = label_qnode; + listnode_add_head(repair_list, &sid_qnode); + } + + /* Push Prefix-SID label when necessary. */ + if (is_pnode) { + /* The same P-node can't be used more than once. */ + if (isis_spf_node_find(used_pnodes, vertex->N.id)) { + if (IS_DEBUG_LFA) + zlog_debug( + "ISIS-LFA: skipping already used P-node"); + return 0; + } + isis_spf_node_new(used_pnodes, vertex->N.id); + + if (!vertex_child) { + if (IS_DEBUG_LFA) + zlog_debug( + "ISIS-LFA: destination is within Ext-P-Space"); + return 0; + } + + sid_index = + tilfa_find_pnode_prefix_sid(spftree_pc, vertex->N.id); + if (sid_index == UINT32_MAX) { + zlog_warn( + "ISIS-LFA: failed to find Prefix-SID corresponding to PQ-node %s", + print_sys_hostname(vertex->N.id)); + return -1; + } + + if (IS_DEBUG_LFA) + zlog_debug( + "ISIS-LFA: pushing Node-SID to %s (index %u)", + print_sys_hostname(vertex->N.id), sid_index); + sid_pnode.type = TILFA_SID_PREFIX; + sid_pnode.value.index.value = sid_index; + listnode_add_head(repair_list, &sid_pnode); + + /* Apply repair list. */ + if (spftree_pc->area->srdb.config.msd + && listcount(repair_list) + > spftree_pc->area->srdb.config.msd) { + zlog_warn( + "ISIS-LFA: list of repair segments exceeds locally configured MSD (%u > %u)", + listcount(repair_list), + spftree_pc->area->srdb.config.msd); + return -1; + } + if (tilfa_repair_list_apply(spftree_pc, vertex_dest, vertex, + repair_list) + != 0) + return -1; + return 0; + } + +parents: + for (ALL_LIST_ELEMENTS_RO(vertex->parents, node, pvertex)) { + struct list *repair_list_parent; + bool ecmp; + int ret; + + ecmp = (listcount(vertex->parents) > 1) ? true : false; + repair_list_parent = ecmp ? list_dup(repair_list) : repair_list; + ret = tilfa_build_repair_list(spftree_pc, vertex_dest, pvertex, + vertex, used_pnodes, + repair_list_parent); + if (ecmp) + list_delete(&repair_list_parent); + if (ret != 0) + return ret; + } + + return 0; +} + +static const char *lfa_protection_type2str(enum lfa_protection_type type) +{ + switch (type) { + case LFA_LINK_PROTECTION: + return "link protection"; + case LFA_NODE_PROTECTION: + return "node protection"; + default: + return "unknown protection type"; + } +} + +static const char * +lfa_protected_resource2str(const struct lfa_protected_resource *resource) +{ + const uint8_t *fail_id; + static char buffer[128]; + + fail_id = resource->adjacency; + snprintf(buffer, sizeof(buffer), "%s.%u's failure (%s)", + print_sys_hostname(fail_id), LSP_PSEUDO_ID(fail_id), + lfa_protection_type2str(resource->type)); + + return buffer; +} + +static bool +spf_adj_check_is_affected(const struct isis_spf_adj *sadj, + const struct lfa_protected_resource *resource, + const uint8_t *root_sysid, bool reverse) +{ + if (!!CHECK_FLAG(sadj->flags, F_ISIS_SPF_ADJ_BROADCAST) + != !!LSP_PSEUDO_ID(resource->adjacency)) + return false; + + if (CHECK_FLAG(sadj->flags, F_ISIS_SPF_ADJ_BROADCAST)) { + if (!memcmp(sadj->lan.desig_is_id, resource->adjacency, + ISIS_SYS_ID_LEN + 1)) + return true; + } else { + if (!reverse + && !memcmp(sadj->id, resource->adjacency, ISIS_SYS_ID_LEN)) + return true; + if (reverse && !memcmp(sadj->id, root_sysid, ISIS_SYS_ID_LEN)) + return true; + } + + return false; +} + +/* Check if the given vertex is affected by a given local failure. */ +static bool +spf_vertex_check_is_affected(const struct isis_vertex *vertex, + const uint8_t *root_sysid, + const struct lfa_protected_resource *resource) +{ + struct isis_vertex_adj *vadj; + struct listnode *node; + size_t affected_nhs = 0; + + /* Local routes don't need protection. */ + if (VTYPE_IP(vertex->type) && vertex->depth == 1) + return false; + + for (ALL_LIST_ELEMENTS_RO(vertex->Adj_N, node, vadj)) { + struct isis_spf_adj *sadj = vadj->sadj; + + if (spf_adj_check_is_affected(sadj, resource, root_sysid, + false)) + affected_nhs++; + } + + /* + * No need to compute backup paths for ECMP routes, except if all + * primary nexthops share the same broadcast interface. + */ + if (listcount(vertex->Adj_N) == affected_nhs) + return true; + + return false; +} + +/* Check if a given RLFA/TI-LFA post-convergence SPF vertex needs protection. */ +static bool lfa_check_needs_protection(const struct isis_spftree *spftree_pc, + const struct isis_vertex *vertex) +{ + struct isis_vertex *vertex_old; + + /* Only local adjacencies need TI-LFA Adj-SID protection. */ + if (spftree_pc->type == SPF_TYPE_TI_LFA && VTYPE_IS(vertex->type) + && !isis_adj_find(spftree_pc->area, spftree_pc->level, + vertex->N.id)) + return false; + + vertex_old = isis_find_vertex(&spftree_pc->lfa.old.spftree->paths, + &vertex->N, vertex->type); + if (!vertex_old) + return false; + + /* Skip vertex if it's already protected by local LFA. */ + if (CHECK_FLAG(vertex_old->flags, F_ISIS_VERTEX_LFA_PROTECTED)) + return false; + + return spf_vertex_check_is_affected( + vertex_old, spftree_pc->sysid, + &spftree_pc->lfa.protected_resource); +} + +/** + * Check if the given SPF vertex needs protection and, if so, compute and + * install the corresponding repair paths. + * + * @param spftree_pc The post-convergence SPF tree + * @param vertex IS-IS SPF vertex to check + * + * @return 0 if the vertex needs to be protected, -1 otherwise + */ +int isis_tilfa_check(struct isis_spftree *spftree_pc, + struct isis_vertex *vertex) +{ + struct isis_spf_nodes used_pnodes; + char buf[VID2STR_BUFFER]; + struct list *repair_list; + int ret; + + if (!spftree_pc->area->srdb.enabled) + return -1; + + if (!lfa_check_needs_protection(spftree_pc, vertex)) { + if (IS_DEBUG_LFA) + zlog_debug( + "ISIS-LFA: %s %s unaffected by %s", + vtype2string(vertex->type), + vid2string(vertex, buf, sizeof(buf)), + lfa_protected_resource2str( + &spftree_pc->lfa.protected_resource)); + + return -1; + } + + /* + * Check if the route/adjacency was already covered by node protection. + */ + if (VTYPE_IS(vertex->type)) { + struct isis_adjacency *adj; + + adj = isis_adj_find(spftree_pc->area, spftree_pc->level, + vertex->N.id); + if (adj + && isis_sr_adj_sid_find(adj, spftree_pc->family, + ISIS_SR_LAN_BACKUP)) { + if (IS_DEBUG_LFA) + zlog_debug( + "ISIS-LFA: %s %s already covered by node protection", + vtype2string(vertex->type), + vid2string(vertex, buf, sizeof(buf))); + + return -1; + } + } + if (VTYPE_IP(vertex->type)) { + struct route_table *route_table; + + route_table = spftree_pc->lfa.old.spftree->route_table_backup; + if (route_node_lookup(route_table, &vertex->N.ip.p.dest)) { + if (IS_DEBUG_LFA) + zlog_debug( + "ISIS-LFA: %s %s already covered by node protection", + vtype2string(vertex->type), + vid2string(vertex, buf, sizeof(buf))); + + return -1; + } + } + + if (IS_DEBUG_LFA) + zlog_debug( + "ISIS-LFA: computing repair path(s) of %s %s w.r.t %s", + vtype2string(vertex->type), + vid2string(vertex, buf, sizeof(buf)), + lfa_protected_resource2str( + &spftree_pc->lfa.protected_resource)); + + /* Create base repair list. */ + repair_list = list_new(); + + isis_spf_node_list_init(&used_pnodes); + ret = tilfa_build_repair_list(spftree_pc, vertex, vertex, NULL, + &used_pnodes, repair_list); + isis_spf_node_list_clear(&used_pnodes); + list_delete(&repair_list); + if (ret != 0) + zlog_warn( + "ISIS-LFA: failed to compute repair path(s) of %s %s w.r.t %s", + vtype2string(vertex->type), + vid2string(vertex, buf, sizeof(buf)), + lfa_protected_resource2str( + &spftree_pc->lfa.protected_resource)); + + return ret; +} + +static bool +spf_adj_node_is_affected(struct isis_spf_node *adj_node, + const struct lfa_protected_resource *resource, + const uint8_t *root_sysid) +{ + struct isis_spf_adj *sadj; + struct listnode *node; + + for (ALL_LIST_ELEMENTS_RO(adj_node->adjacencies, node, sadj)) { + if (sadj->metric != adj_node->best_metric) + continue; + if (spf_adj_check_is_affected(sadj, resource, root_sysid, + false)) + return true; + } + + return false; +} + +static bool vertex_is_affected(struct isis_spftree *spftree_root, + const struct isis_spf_nodes *adj_nodes, + bool p_space, const struct isis_vertex *vertex, + const struct lfa_protected_resource *resource) +{ + struct isis_vertex *pvertex; + struct listnode *node, *vnode; + + for (ALL_LIST_ELEMENTS_RO(vertex->parents, node, pvertex)) { + struct isis_spftree *spftree_parent; + struct isis_vertex *vertex_child; + struct isis_vertex_adj *vadj; + bool reverse = false; + + if (p_space && resource->type == LFA_NODE_PROTECTION) { + if (isis_spf_node_find(&resource->nodes, vertex->N.id)) + return true; + goto parents; + } + + /* Check if either the vertex or its parent is the root node. */ + if (memcmp(vertex->N.id, spftree_root->sysid, ISIS_SYS_ID_LEN) + && memcmp(pvertex->N.id, spftree_root->sysid, + ISIS_SYS_ID_LEN)) + goto parents; + + /* Get SPT of the parent vertex. */ + if (!memcmp(pvertex->N.id, spftree_root->sysid, + ISIS_SYS_ID_LEN)) + spftree_parent = spftree_root; + else { + struct isis_spf_node *adj_node; + + adj_node = isis_spf_node_find(adj_nodes, pvertex->N.id); + assert(adj_node); + spftree_parent = adj_node->lfa.spftree; + assert(spftree_parent); + reverse = true; + } + + /* Get paths pvertex uses to reach vertex. */ + vertex_child = isis_find_vertex(&spftree_parent->paths, + &vertex->N, vertex->type); + if (!vertex_child) + goto parents; + + /* Check if any of these paths use the protected resource. */ + for (ALL_LIST_ELEMENTS_RO(vertex_child->Adj_N, vnode, vadj)) + if (spf_adj_check_is_affected(vadj->sadj, resource, + spftree_root->sysid, + reverse)) + return true; + + parents: + if (vertex_is_affected(spftree_root, adj_nodes, p_space, + pvertex, resource)) + return true; + } + + return false; +} + +/* Calculate set of nodes reachable without using the protected interface. */ +static void lfa_calc_reach_nodes(struct isis_spftree *spftree, + struct isis_spftree *spftree_root, + const struct isis_spf_nodes *adj_nodes, + bool p_space, + const struct lfa_protected_resource *resource, + struct isis_spf_nodes *nodes) +{ + struct isis_vertex *vertex; + struct listnode *node; + + for (ALL_QUEUE_ELEMENTS_RO(&spftree->paths, node, vertex)) { + char buf[VID2STR_BUFFER]; + + if (!VTYPE_IS(vertex->type)) + continue; + + /* Skip root node. */ + if (!memcmp(vertex->N.id, spftree_root->sysid, ISIS_SYS_ID_LEN)) + continue; + + /* Don't add the same node twice. */ + if (isis_spf_node_find(nodes, vertex->N.id)) + continue; + + if (!vertex_is_affected(spftree_root, adj_nodes, p_space, + vertex, resource)) { + if (IS_DEBUG_LFA) + zlog_debug( + "ISIS-LFA: adding %s", + vid2string(vertex, buf, sizeof(buf))); + + isis_spf_node_new(nodes, vertex->N.id); + } + } +} + +/** + * Helper function used to create an SPF tree structure and run reverse SPF on + * it. + * + * @param spftree IS-IS SPF tree + * + * @return Pointer to new SPF tree structure. + */ +struct isis_spftree *isis_spf_reverse_run(const struct isis_spftree *spftree) +{ + struct isis_spftree *spftree_reverse; + + spftree_reverse = isis_spftree_new( + spftree->area, spftree->lspdb, spftree->sysid, spftree->level, + spftree->tree_id, SPF_TYPE_REVERSE, + F_SPFTREE_NO_ADJACENCIES | F_SPFTREE_NO_ROUTES); + isis_run_spf(spftree_reverse); + + return spftree_reverse; +} + +/* + * Calculate the Extended P-space and Q-space associated to a given link + * failure. + */ +static void lfa_calc_pq_spaces(struct isis_spftree *spftree_pc, + const struct lfa_protected_resource *resource) +{ + struct isis_spftree *spftree; + struct isis_spftree *spftree_reverse; + struct isis_spf_nodes *adj_nodes; + struct isis_spf_node *adj_node; + + /* Obtain pre-failure SPTs and list of adjacent nodes. */ + spftree = spftree_pc->lfa.old.spftree; + spftree_reverse = spftree_pc->lfa.old.spftree_reverse; + adj_nodes = &spftree->adj_nodes; + + if (IS_DEBUG_LFA) + zlog_debug("ISIS-LFA: computing P-space (self)"); + lfa_calc_reach_nodes(spftree, spftree, adj_nodes, true, resource, + &spftree_pc->lfa.p_space); + + RB_FOREACH (adj_node, isis_spf_nodes, adj_nodes) { + if (spf_adj_node_is_affected(adj_node, resource, + spftree->sysid)) { + if (IS_DEBUG_LFA) + zlog_debug("ISIS-LFA: computing Q-space (%s)", + print_sys_hostname(adj_node->sysid)); + + /* + * Compute the reverse SPF in the behalf of the node + * adjacent to the failure, if we haven't done that + * before + */ + if (!adj_node->lfa.spftree_reverse) + adj_node->lfa.spftree_reverse = + isis_spf_reverse_run( + adj_node->lfa.spftree); + + lfa_calc_reach_nodes(adj_node->lfa.spftree_reverse, + spftree_reverse, adj_nodes, false, + resource, + &spftree_pc->lfa.q_space); + } else { + if (IS_DEBUG_LFA) + zlog_debug("ISIS-LFA: computing P-space (%s)", + print_sys_hostname(adj_node->sysid)); + lfa_calc_reach_nodes(adj_node->lfa.spftree, spftree, + adj_nodes, true, resource, + &adj_node->lfa.p_space); + } + } +} + +/** + * Compute the TI-LFA backup paths for a given protected interface. + * + * @param area IS-IS area + * @param spftree IS-IS SPF tree + * @param spftree_reverse IS-IS Reverse SPF tree + * @param resource Protected resource + * + * @return Pointer to the post-convergence SPF tree + */ +struct isis_spftree *isis_tilfa_compute(struct isis_area *area, + struct isis_spftree *spftree, + struct isis_spftree *spftree_reverse, + struct lfa_protected_resource *resource) +{ + struct isis_spftree *spftree_pc; + struct isis_spf_node *adj_node; + + if (IS_DEBUG_LFA) + zlog_debug("ISIS-LFA: computing TI-LFAs for %s", + lfa_protected_resource2str(resource)); + + /* Populate list of nodes affected by link failure. */ + if (resource->type == LFA_NODE_PROTECTION) { + isis_spf_node_list_init(&resource->nodes); + RB_FOREACH (adj_node, isis_spf_nodes, &spftree->adj_nodes) { + if (spf_adj_node_is_affected(adj_node, resource, + spftree->sysid)) + isis_spf_node_new(&resource->nodes, + adj_node->sysid); + } + } + + /* Create post-convergence SPF tree. */ + spftree_pc = isis_spftree_new(area, spftree->lspdb, spftree->sysid, + spftree->level, spftree->tree_id, + SPF_TYPE_TI_LFA, spftree->flags); + spftree_pc->lfa.old.spftree = spftree; + spftree_pc->lfa.old.spftree_reverse = spftree_reverse; + spftree_pc->lfa.protected_resource = *resource; + + /* Compute the extended P-space and Q-space. */ + lfa_calc_pq_spaces(spftree_pc, resource); + + if (IS_DEBUG_LFA) + zlog_debug( + "ISIS-LFA: computing the post convergence SPT w.r.t. %s", + lfa_protected_resource2str(resource)); + + /* Re-run SPF in the local node to find the post-convergence paths. */ + isis_run_spf(spftree_pc); + + /* Clear list of nodes affeted by link failure. */ + if (resource->type == LFA_NODE_PROTECTION) + isis_spf_node_list_clear(&resource->nodes); + + return spftree_pc; +} + +/** + * Run forward SPF on all adjacent routers. + * + * @param spftree IS-IS SPF tree + * + * @return 0 on success, -1 otherwise + */ +int isis_spf_run_neighbors(struct isis_spftree *spftree) +{ + struct isis_lsp *lsp; + struct isis_spf_node *adj_node; + + lsp = isis_root_system_lsp(spftree->lspdb, spftree->sysid); + if (!lsp) + return -1; + + RB_FOREACH (adj_node, isis_spf_nodes, &spftree->adj_nodes) { + if (IS_DEBUG_LFA) + zlog_debug("ISIS-LFA: running SPF on neighbor %s", + print_sys_hostname(adj_node->sysid)); + + /* Compute the SPT on behalf of the neighbor. */ + adj_node->lfa.spftree = isis_spftree_new( + spftree->area, spftree->lspdb, adj_node->sysid, + spftree->level, spftree->tree_id, SPF_TYPE_FORWARD, + F_SPFTREE_NO_ADJACENCIES | F_SPFTREE_NO_ROUTES); + isis_run_spf(adj_node->lfa.spftree); + } + + return 0; +} + +/* Find Router ID of PQ node. */ +static struct in_addr *rlfa_pq_node_rtr_id(struct isis_spftree *spftree, + const struct isis_vertex *vertex_pq) +{ + struct isis_lsp *lsp; + + lsp = isis_root_system_lsp(spftree->lspdb, vertex_pq->N.id); + if (!lsp) + return NULL; + + if (lsp->tlvs->router_cap->router_id.s_addr == INADDR_ANY) + return NULL; + + return &lsp->tlvs->router_cap->router_id; +} + +/* Find PQ node by intersecting the P/Q spaces. This is a recursive function. */ +static const struct in_addr * +rlfa_find_pq_node(struct isis_spftree *spftree_pc, + struct isis_vertex *vertex_dest, + const struct isis_vertex *vertex, + const struct isis_vertex *vertex_child) +{ + struct isis_area *area = spftree_pc->area; + int level = spftree_pc->level; + struct isis_vertex *pvertex; + struct listnode *node; + bool is_pnode, is_qnode; + + if (!vertex_child) + goto parents; + if (vertex->type != VTYPE_NONPSEUDO_IS + && vertex->type != VTYPE_NONPSEUDO_TE_IS) + goto parents; + if (!VTYPE_IS(vertex_child->type)) + vertex_child = NULL; + + /* Check if node is part of the extended P-space and/or Q-space. */ + is_pnode = lfa_ext_p_space_check(spftree_pc, vertex_dest, vertex); + is_qnode = lfa_q_space_check(spftree_pc, vertex); + + if (is_pnode && is_qnode) { + const struct in_addr *rtr_id_pq; + uint32_t max_metric; + struct prefix_list *plist = NULL; + + rtr_id_pq = rlfa_pq_node_rtr_id(spftree_pc, vertex); + if (!rtr_id_pq) { + if (IS_DEBUG_LFA) { + char buf[VID2STR_BUFFER]; + + vid2string(vertex, buf, sizeof(buf)); + zlog_debug( + "ISIS-LFA: tentative PQ node (%s %s) doesn't have a router-ID", + vtype2string(vertex->type), buf); + } + goto parents; + } + + max_metric = spftree_pc->lfa.remote.max_metric; + if (max_metric && vertex->d_N > max_metric) { + if (IS_DEBUG_LFA) + zlog_debug( + "ISIS-LFA: skipping PQ node %pI4 (maximum metric)", + rtr_id_pq); + goto parents; + } + + plist = area->rlfa_plist[level - 1]; + if (plist) { + struct prefix p; + + p.family = AF_INET; + p.prefixlen = IPV4_MAX_BITLEN; + p.u.prefix4 = *rtr_id_pq; + if (prefix_list_apply(plist, &p) == PREFIX_DENY) { + if (IS_DEBUG_LFA) + zlog_debug( + "ISIS-LFA: PQ node %pI4 filtered by prefix-list", + rtr_id_pq); + goto parents; + } + } + + if (IS_DEBUG_LFA) + zlog_debug("ISIS-LFA: found PQ node: %pI4", rtr_id_pq); + + return rtr_id_pq; + } + +parents: + for (ALL_LIST_ELEMENTS_RO(vertex->parents, node, pvertex)) { + const struct in_addr *rtr_id_pq; + + rtr_id_pq = rlfa_find_pq_node(spftree_pc, vertex_dest, pvertex, + vertex); + if (rtr_id_pq) + return rtr_id_pq; + } + + return NULL; +} + +int rlfa_cmp(const struct rlfa *a, const struct rlfa *b) +{ + return prefix_cmp(&a->prefix, &b->prefix); +} + +static struct rlfa *rlfa_add(struct isis_spftree *spftree, + struct isis_vertex *vertex, + struct in_addr pq_address) +{ + struct rlfa *rlfa; + + assert(VTYPE_IP(vertex->type)); + rlfa = XCALLOC(MTYPE_ISIS_RLFA, sizeof(*rlfa)); + rlfa->prefix = vertex->N.ip.p.dest; + rlfa->vertex = vertex; + rlfa->pq_address = pq_address; + rlfa_tree_add(&spftree->lfa.remote.rlfas, rlfa); + + return rlfa; +} + +static void rlfa_delete(struct isis_spftree *spftree, struct rlfa *rlfa) +{ + rlfa_tree_del(&spftree->lfa.remote.rlfas, rlfa); + XFREE(MTYPE_ISIS_RLFA, rlfa); +} + +static struct rlfa *rlfa_lookup(struct isis_spftree *spftree, + union prefixconstptr pu) +{ + struct rlfa s = {}; + + s.prefix = *pu.p; + return rlfa_tree_find(&spftree->lfa.remote.rlfas, &s); +} + +static void isis_area_verify_routes_cb(struct thread *thread) +{ + struct isis_area *area = THREAD_ARG(thread); + + if (IS_DEBUG_LFA) + zlog_debug("ISIS-LFA: updating RLFAs in the RIB"); + + isis_area_verify_routes(area); +} + +static mpls_label_t rlfa_nexthop_label(struct isis_spftree *spftree, + struct isis_vertex_adj *vadj, + struct zapi_rlfa_response *response) +{ + struct isis_spf_adj *sadj = vadj->sadj; + struct isis_adjacency *adj = sadj->adj; + + /* + * Special case to make unit tests work (use implicit-null labels + * instead of artifical ones). + */ + if (CHECK_FLAG(spftree->flags, F_SPFTREE_NO_ADJACENCIES)) + return MPLS_LABEL_IMPLICIT_NULL; + + for (unsigned int i = 0; i < response->nexthop_num; i++) { + switch (response->nexthops[i].family) { + case AF_INET: + for (unsigned int j = 0; j < adj->ipv4_address_count; + j++) { + struct in_addr addr = adj->ipv4_addresses[j]; + + if (!IPV4_ADDR_SAME( + &addr, + &response->nexthops[i].gate.ipv4)) + continue; + + return response->nexthops[i].label; + } + break; + case AF_INET6: + for (unsigned int j = 0; j < adj->ll_ipv6_count; j++) { + struct in6_addr addr = adj->ll_ipv6_addrs[j]; + + if (!IPV6_ADDR_SAME( + &addr, + &response->nexthops[i].gate.ipv6)) + continue; + + return response->nexthops[i].label; + } + break; + + default: + break; + } + } + + return MPLS_INVALID_LABEL; +} + +int isis_rlfa_activate(struct isis_spftree *spftree, struct rlfa *rlfa, + struct zapi_rlfa_response *response) +{ + struct isis_area *area = spftree->area; + struct isis_vertex *vertex = rlfa->vertex; + struct isis_vertex_adj *vadj; + struct listnode *node; + + for (ALL_LIST_ELEMENTS_RO(vertex->Adj_N, node, vadj)) { + mpls_label_t ldp_label; + struct mpls_label_stack *label_stack; + size_t num_labels = 0; + size_t i = 0; + + ldp_label = rlfa_nexthop_label(spftree, vadj, response); + if (ldp_label == MPLS_INVALID_LABEL) { + if (IS_DEBUG_LFA) + zlog_debug( + "ISIS-LFA: failed to activate RLFA: missing LDP label to reach PQ node through %s", + sysid_print(vadj->sadj->id)); + return -1; + } + + if (ldp_label != MPLS_LABEL_IMPLICIT_NULL) + num_labels++; + if (response->pq_label != MPLS_LABEL_IMPLICIT_NULL) + num_labels++; + if (vadj->sr.present + && vadj->sr.label != MPLS_LABEL_IMPLICIT_NULL) + num_labels++; + + /* Allocate label stack. */ + label_stack = + XCALLOC(MTYPE_ISIS_NEXTHOP_LABELS, + sizeof(struct mpls_label_stack) + + num_labels * sizeof(mpls_label_t)); + label_stack->num_labels = num_labels; + + /* Push label allocated by the nexthop (outer label). */ + if (ldp_label != MPLS_LABEL_IMPLICIT_NULL) + label_stack->label[i++] = ldp_label; + /* Push label allocated by the PQ node (inner label). */ + if (response->pq_label != MPLS_LABEL_IMPLICIT_NULL) + label_stack->label[i++] = response->pq_label; + /* Preserve the original Prefix-SID label when it's present. */ + if (vadj->sr.present + && vadj->sr.label != MPLS_LABEL_IMPLICIT_NULL) + label_stack->label[i++] = vadj->sr.label; + + vadj->label_stack = label_stack; + } + + isis_route_create(&vertex->N.ip.p.dest, &vertex->N.ip.p.src, + vertex->d_N, vertex->depth, &vertex->N.ip.sr, + vertex->Adj_N, true, area, + spftree->route_table_backup); + spftree->lfa.protection_counters.rlfa[vertex->N.ip.priority] += 1; + + THREAD_OFF(area->t_rlfa_rib_update); + thread_add_timer(master, isis_area_verify_routes_cb, area, 2, + &area->t_rlfa_rib_update); + + return 0; +} + +void isis_rlfa_deactivate(struct isis_spftree *spftree, struct rlfa *rlfa) +{ + struct isis_area *area = spftree->area; + struct isis_vertex *vertex = rlfa->vertex; + struct route_node *rn; + + rn = route_node_lookup(spftree->route_table_backup, &rlfa->prefix); + if (!rn) + return; + isis_route_delete(area, rn, spftree->route_table_backup); + spftree->lfa.protection_counters.rlfa[vertex->N.ip.priority] -= 1; + + THREAD_OFF(area->t_rlfa_rib_update); + thread_add_timer(master, isis_area_verify_routes_cb, area, 2, + &area->t_rlfa_rib_update); +} + +void isis_rlfa_list_init(struct isis_spftree *spftree) +{ + rlfa_tree_init(&spftree->lfa.remote.rlfas); +} + +void isis_rlfa_list_clear(struct isis_spftree *spftree) +{ + while (rlfa_tree_count(&spftree->lfa.remote.rlfas) > 0) { + struct rlfa *rlfa; + + rlfa = rlfa_tree_first(&spftree->lfa.remote.rlfas); + isis_rlfa_deactivate(spftree, rlfa); + rlfa_delete(spftree, rlfa); + } +} + +void isis_rlfa_process_ldp_response(struct zapi_rlfa_response *response) +{ + struct isis *isis; + struct isis_area *area; + struct isis_spftree *spftree; + struct rlfa *rlfa; + enum spf_tree_id tree_id; + uint32_t spf_run_id; + int level; + + if (response->igp.protocol != ZEBRA_ROUTE_ISIS) + return; + + isis = isis_lookup_by_vrfid(response->igp.vrf_id); + if (!isis) + return; + + area = isis_area_lookup(response->igp.isis.area_tag, + response->igp.vrf_id); + if (!area) + return; + + tree_id = response->igp.isis.spf.tree_id; + if (tree_id != SPFTREE_IPV4 && tree_id != SPFTREE_IPV6) { + zlog_warn("ISIS-LFA: invalid SPF tree ID received from LDP"); + return; + } + + level = response->igp.isis.spf.level; + if (level != ISIS_LEVEL1 && level != ISIS_LEVEL2) { + zlog_warn("ISIS-LFA: invalid IS-IS level received from LDP"); + return; + } + + spf_run_id = response->igp.isis.spf.run_id; + spftree = area->spftree[tree_id][level - 1]; + if (spftree->runcount != spf_run_id) + /* Outdated RLFA, ignore... */ + return; + + rlfa = rlfa_lookup(spftree, &response->destination); + if (!rlfa) { + zlog_warn( + "ISIS-LFA: couldn't find Remote-LFA %pFX received from LDP", + &response->destination); + return; + } + + if (response->pq_label != MPLS_INVALID_LABEL) { + if (IS_DEBUG_LFA) + zlog_debug( + "ISIS-LFA: activating/updating RLFA for %pFX", + &rlfa->prefix); + + if (isis_rlfa_activate(spftree, rlfa, response) != 0) + isis_rlfa_deactivate(spftree, rlfa); + } else { + if (IS_DEBUG_LFA) + zlog_debug("ISIS-LFA: deactivating RLFA for %pFX", + &rlfa->prefix); + + isis_rlfa_deactivate(spftree, rlfa); + } +} + +void isis_ldp_rlfa_handle_client_close(struct zapi_client_close_info *info) +{ + struct isis *isis = isis_lookup_by_vrfid(VRF_DEFAULT); + struct isis_area *area; + struct listnode *node; + + if (!isis) + return; + + /* Check if the LDP main client session closed */ + if (info->proto != ZEBRA_ROUTE_LDP || info->session_id == 0) + return; + + if (IS_DEBUG_LFA) + zlog_debug("ISIS-LFA: LDP is down, deactivating all RLFAs"); + + for (ALL_LIST_ELEMENTS_RO(isis->area_list, node, area)) { + for (int tree = SPFTREE_IPV4; tree < SPFTREE_COUNT; tree++) { + for (int level = ISIS_LEVEL1; level <= ISIS_LEVELS; + level++) { + struct isis_spftree *spftree; + + if (!(area->is_type & level)) + continue; + if (!area->spftree[tree][level - 1]) + continue; + + spftree = area->spftree[tree][level - 1]; + isis_rlfa_list_clear(spftree); + } + } + } +} + +/** + * Check if the given SPF vertex needs protection and, if so, attempt to + * compute a Remote LFA for it. + * + * @param spftree_pc The post-convergence SPF tree + * @param vertex IS-IS SPF vertex to check + */ +void isis_rlfa_check(struct isis_spftree *spftree_pc, + struct isis_vertex *vertex) +{ + struct isis_spftree *spftree_old = spftree_pc->lfa.old.spftree; + struct rlfa *rlfa; + const struct in_addr *rtr_id_pq; + char buf[VID2STR_BUFFER]; + + if (!lfa_check_needs_protection(spftree_pc, vertex)) { + if (IS_DEBUG_LFA) + zlog_debug( + "ISIS-LFA: %s %s unaffected by %s", + vtype2string(vertex->type), + vid2string(vertex, buf, sizeof(buf)), + lfa_protected_resource2str( + &spftree_pc->lfa.protected_resource)); + + return; + } + + if (IS_DEBUG_LFA) + zlog_debug( + "ISIS-LFA: computing repair path(s) of %s %s w.r.t %s", + vtype2string(vertex->type), + vid2string(vertex, buf, sizeof(buf)), + lfa_protected_resource2str( + &spftree_pc->lfa.protected_resource)); + + /* Find PQ node. */ + rtr_id_pq = rlfa_find_pq_node(spftree_pc, vertex, vertex, NULL); + if (!rtr_id_pq) { + if (IS_DEBUG_LFA) + zlog_debug("ISIS-LFA: no acceptable PQ node found"); + return; + } + + /* Store valid RLFA and store LDP label for the PQ node. */ + rlfa = rlfa_add(spftree_old, vertex, *rtr_id_pq); + + /* Register RLFA with LDP. */ + if (isis_zebra_rlfa_register(spftree_old, rlfa) != 0) + rlfa_delete(spftree_old, rlfa); +} + +/** + * Compute the Remote LFA backup paths for a given protected interface. + * + * @param area IS-IS area + * @param spftree IS-IS SPF tree + * @param spftree_reverse IS-IS Reverse SPF tree + * @param max_metric Remote LFA maximum metric + * @param resource Protected resource + * + * @return Pointer to the post-convergence SPF tree + */ +struct isis_spftree *isis_rlfa_compute(struct isis_area *area, + struct isis_spftree *spftree, + struct isis_spftree *spftree_reverse, + uint32_t max_metric, + struct lfa_protected_resource *resource) +{ + struct isis_spftree *spftree_pc; + + if (IS_DEBUG_LFA) + zlog_debug("ISIS-LFA: computing remote LFAs for %s", + lfa_protected_resource2str(resource)); + + /* Create post-convergence SPF tree. */ + spftree_pc = isis_spftree_new(area, spftree->lspdb, spftree->sysid, + spftree->level, spftree->tree_id, + SPF_TYPE_RLFA, spftree->flags); + spftree_pc->lfa.old.spftree = spftree; + spftree_pc->lfa.old.spftree_reverse = spftree_reverse; + spftree_pc->lfa.remote.max_metric = max_metric; + spftree_pc->lfa.protected_resource = *resource; + + /* Compute the extended P-space and Q-space. */ + lfa_calc_pq_spaces(spftree_pc, resource); + + if (IS_DEBUG_LFA) + zlog_debug( + "ISIS-LFA: computing the post convergence SPT w.r.t. %s", + lfa_protected_resource2str(resource)); + + /* Re-run SPF in the local node to find the post-convergence paths. */ + isis_run_spf(spftree_pc); + + return spftree_pc; +} + +/* Calculate the distance from the root node to the given IP destination. */ +static int lfa_calc_dist_destination(struct isis_spftree *spftree, + const struct isis_vertex *vertex_N, + uint32_t *distance) +{ + struct isis_vertex *vertex, *vertex_best = NULL; + + switch (spftree->family) { + case AF_INET: + for (int vtype = VTYPE_IPREACH_INTERNAL; + vtype <= VTYPE_IPREACH_TE; vtype++) { + vertex = isis_find_vertex( + &spftree->paths, &vertex_N->N.ip.p.dest, vtype); + if (!vertex) + continue; + + /* Pick vertex with the best metric. */ + if (!vertex_best || vertex_best->d_N > vertex->d_N) + vertex_best = vertex; + } + break; + case AF_INET6: + for (int vtype = VTYPE_IP6REACH_INTERNAL; + vtype <= VTYPE_IP6REACH_EXTERNAL; vtype++) { + vertex = isis_find_vertex( + &spftree->paths, &vertex_N->N.ip.p.dest, vtype); + if (!vertex) + continue; + + /* Pick vertex with the best metric. */ + if (!vertex_best || vertex_best->d_N > vertex->d_N) + vertex_best = vertex; + } + break; + default: + break; + } + + if (!vertex_best) + return -1; + + assert(VTYPE_IP(vertex_best->type)); + vertex_best = listnode_head(vertex_best->parents); + *distance = vertex_best->d_N; + + return 0; +} + +/* Calculate the distance from the root node to the given node. */ +static int lfa_calc_dist_node(struct isis_spftree *spftree, + const uint8_t *sysid, uint32_t *distance) +{ + struct isis_vertex *vertex, *vertex_best = NULL; + + for (int vtype = VTYPE_PSEUDO_IS; vtype <= VTYPE_NONPSEUDO_TE_IS; + vtype++) { + vertex = isis_find_vertex(&spftree->paths, sysid, vtype); + if (!vertex) + continue; + + /* Pick vertex with the best metric. */ + if (!vertex_best || vertex_best->d_N > vertex->d_N) + vertex_best = vertex; + } + + if (!vertex_best) + return -1; + + *distance = vertex_best->d_N; + + return 0; +} + +/* + * Check loop-free criterion (RFC 5286's inequality 1): + * - Dist_opt(N, D) < Dist_opt(N, S) + Dist_opt(S, D) + */ +static bool clfa_loop_free_check(struct isis_spftree *spftree, + struct isis_vertex *vertex_S_D, + struct isis_spf_adj *sadj_primary, + struct isis_spf_adj *sadj_N, + uint32_t *lfa_metric) +{ + struct isis_spf_node *node_N; + uint32_t dist_N_D; + uint32_t dist_N_S; + uint32_t dist_S_D; + + node_N = isis_spf_node_find(&spftree->adj_nodes, sadj_N->id); + assert(node_N); + + /* Distance from N to D. */ + if (lfa_calc_dist_destination(node_N->lfa.spftree, vertex_S_D, + &dist_N_D) + != 0) + return false; + + /* Distance from N to S (or PN). */ + if (CHECK_FLAG(sadj_primary->flags, F_ISIS_SPF_ADJ_BROADCAST)) { + static uint8_t pn_sysid[ISIS_SYS_ID_LEN + 1]; + + memcpy(pn_sysid, sadj_primary->id, ISIS_SYS_ID_LEN + 1); + if (lfa_calc_dist_node(node_N->lfa.spftree, pn_sysid, &dist_N_S) + != 0) + return false; + } else { + static uint8_t root_sysid[ISIS_SYS_ID_LEN + 1]; + + memcpy(root_sysid, spftree->sysid, ISIS_SYS_ID_LEN); + LSP_PSEUDO_ID(root_sysid) = 0; + if (lfa_calc_dist_node(node_N->lfa.spftree, root_sysid, + &dist_N_S) + != 0) + return false; + } + + /* Distance from S (or PN) to D. */ + vertex_S_D = listnode_head(vertex_S_D->parents); + dist_S_D = vertex_S_D->d_N; + if (CHECK_FLAG(sadj_primary->flags, F_ISIS_SPF_ADJ_BROADCAST)) + dist_S_D -= sadj_primary->metric; + + if (IS_DEBUG_LFA) + zlog_debug("ISIS-LFA: loop-free check: %u < %u + %u", dist_N_D, + dist_N_S, dist_S_D); + + if (dist_N_D < (dist_N_S + dist_S_D)) { + *lfa_metric = sadj_N->metric + dist_N_D; + return true; + } + + return false; +} + +/* + * Check loop-free criterion (RFC 5286's inequality 2): + * - Distance_opt(N, D) < Distance_opt(S, D) + */ +static bool clfa_downstream_check(struct isis_spftree *spftree, + struct isis_vertex *vertex_S_D, + struct isis_spf_adj *sadj_N) +{ + struct isis_spf_node *node_N; + uint32_t dist_N_D; + uint32_t dist_S_D; + + node_N = isis_spf_node_find(&spftree->adj_nodes, sadj_N->id); + assert(node_N); + + /* Distance from N to D. */ + if (lfa_calc_dist_destination(node_N->lfa.spftree, vertex_S_D, + &dist_N_D) + != 0) + return false; + + /* Distance from S (or PN) to D. */ + vertex_S_D = listnode_head(vertex_S_D->parents); + dist_S_D = vertex_S_D->d_N; + + if (IS_DEBUG_LFA) + zlog_debug("ISIS-LFA: downstream check: %u < %u", dist_N_D, + dist_S_D); + + if (dist_N_D < dist_S_D) + return true; + + return false; +} + +/* + * Check loop-free criterion (RFC 5286's inequality 3): + * - Dist_opt(N, D) < Dist_opt(N, E) + Dist_opt(E, D) + */ +static bool clfa_node_protecting_check(struct isis_spftree *spftree, + struct isis_vertex *vertex_S_D, + struct isis_spf_adj *sadj_N, + struct isis_spf_adj *sadj_E) +{ + struct isis_spf_node *node_N, *node_E; + uint32_t dist_N_D; + uint32_t dist_N_E; + uint32_t dist_E_D; + + node_N = isis_spf_node_find(&spftree->adj_nodes, sadj_N->id); + assert(node_N); + node_E = isis_spf_node_find(&spftree->adj_nodes, sadj_E->id); + assert(node_E); + + /* Distance from N to D. */ + if (lfa_calc_dist_destination(node_N->lfa.spftree, vertex_S_D, + &dist_N_D) + != 0) + return false; + + /* Distance from N to E. */ + if (lfa_calc_dist_node(node_N->lfa.spftree, node_E->sysid, &dist_N_E) + != 0) + return false; + + /* Distance from E to D. */ + if (lfa_calc_dist_destination(node_E->lfa.spftree, vertex_S_D, + &dist_E_D) + != 0) + return false; + + if (IS_DEBUG_LFA) + zlog_debug("ISIS-LFA: node protecting check: %u < %u + %u", + dist_N_D, dist_N_E, dist_E_D); + + return (dist_N_D < (dist_N_E + dist_E_D)); +} + +static struct list * +isis_lfa_tiebreakers(struct isis_area *area, struct isis_spftree *spftree, + struct lfa_protected_resource *resource, + struct isis_vertex *vertex, + struct isis_spf_adj *sadj_primary, struct list *lfa_list) +{ + struct lfa_tiebreaker *tie_b; + int level = spftree->level; + struct list *filtered_lfa_list; + struct list *tent_lfa_list; + + filtered_lfa_list = list_dup(lfa_list); + filtered_lfa_list->del = NULL; + + if (listcount(filtered_lfa_list) == 1) + return filtered_lfa_list; + + /* Check tiebreakers in ascending order by index. */ + frr_each (lfa_tiebreaker_tree, &area->lfa_tiebreakers[level - 1], + tie_b) { + struct isis_vertex_adj *lfa; + struct listnode *node, *nnode; + uint32_t best_metric = UINT32_MAX; + + tent_lfa_list = list_dup(filtered_lfa_list); + + switch (tie_b->type) { + case LFA_TIEBREAKER_DOWNSTREAM: + for (ALL_LIST_ELEMENTS(tent_lfa_list, node, nnode, + lfa)) { + if (clfa_downstream_check(spftree, vertex, + lfa->sadj)) + continue; + + if (IS_DEBUG_LFA) + zlog_debug( + "ISIS-LFA: LFA %s doesn't satisfy the downstream condition", + print_sys_hostname( + lfa->sadj->id)); + listnode_delete(tent_lfa_list, lfa); + } + break; + case LFA_TIEBREAKER_LOWEST_METRIC: + /* Find the best metric first. */ + for (ALL_LIST_ELEMENTS_RO(tent_lfa_list, node, lfa)) { + if (lfa->lfa_metric < best_metric) + best_metric = lfa->lfa_metric; + } + + /* Remove LFAs that don't have the best metric. */ + for (ALL_LIST_ELEMENTS(tent_lfa_list, node, nnode, + lfa)) { + if (lfa->lfa_metric == best_metric) + continue; + + if (IS_DEBUG_LFA) + zlog_debug( + "ISIS-LFA: LFA %s doesn't have the lowest cost metric", + print_sys_hostname( + lfa->sadj->id)); + listnode_delete(tent_lfa_list, lfa); + } + break; + case LFA_TIEBREAKER_NODE_PROTECTING: + for (ALL_LIST_ELEMENTS(tent_lfa_list, node, nnode, + lfa)) { + if (clfa_node_protecting_check(spftree, vertex, + lfa->sadj, + sadj_primary)) + continue; + + if (IS_DEBUG_LFA) + zlog_debug( + "ISIS-LFA: LFA %s doesn't provide node protection", + print_sys_hostname( + lfa->sadj->id)); + listnode_delete(tent_lfa_list, lfa); + } + break; + } + + /* + * Decide what to do next based on the number of remaining LFAs. + */ + switch (listcount(tent_lfa_list)) { + case 0: + /* + * Ignore this tie-breaker since it excluded all LFAs. + * Move on to the next one (if any). + */ + list_delete(&tent_lfa_list); + break; + case 1: + /* Finish tie-breaking once we get a single LFA. */ + list_delete(&filtered_lfa_list); + filtered_lfa_list = tent_lfa_list; + return filtered_lfa_list; + default: + /* + * We still have two or more LFAs. Move on to the next + * tie-breaker (if any). + */ + list_delete(&filtered_lfa_list); + filtered_lfa_list = tent_lfa_list; + break; + } + } + + return filtered_lfa_list; +} + +void isis_lfa_compute(struct isis_area *area, struct isis_circuit *circuit, + struct isis_spftree *spftree, + struct lfa_protected_resource *resource) +{ + struct isis_vertex *vertex; + struct listnode *vnode, *snode; + int level = spftree->level; + + resource->type = LFA_LINK_PROTECTION; + + if (IS_DEBUG_LFA) + zlog_debug("ISIS-LFA: computing local LFAs for %s", + lfa_protected_resource2str(resource)); + + for (ALL_QUEUE_ELEMENTS_RO(&spftree->paths, vnode, vertex)) { + struct list *lfa_list; + struct list *filtered_lfa_list; + struct isis_spf_adj *sadj_N; + struct isis_vertex_adj *vadj_primary; + struct isis_spf_adj *sadj_primary; + bool allow_ecmp; + uint32_t best_metric = UINT32_MAX; + char buf[VID2STR_BUFFER]; + + if (!VTYPE_IP(vertex->type)) + continue; + + vid2string(vertex, buf, sizeof(buf)); + + if (!spf_vertex_check_is_affected(vertex, spftree->sysid, + resource)) { + if (IS_DEBUG_LFA) + zlog_debug( + "ISIS-LFA: %s %s unaffected by %s", + vtype2string(vertex->type), buf, + lfa_protected_resource2str(resource)); + continue; + } + + if (IS_DEBUG_LFA) + zlog_debug("ISIS-LFA: checking %s %s w.r.t %s", + vtype2string(vertex->type), buf, + lfa_protected_resource2str(resource)); + + if (vertex->N.ip.priority + > area->lfa_priority_limit[level - 1]) { + if (IS_DEBUG_LFA) + zlog_debug( + "ISIS-LFA: skipping computing LFAs due to low prefix priority"); + continue; + } + + vadj_primary = listnode_head(vertex->Adj_N); + sadj_primary = vadj_primary->sadj; + + /* + * Loop over list of SPF adjacencies and compute a list of + * preliminary LFAs. + */ + lfa_list = list_new(); + lfa_list->del = isis_vertex_adj_free; + for (ALL_LIST_ELEMENTS_RO(spftree->sadj_list, snode, sadj_N)) { + uint32_t lfa_metric; + struct isis_vertex_adj *lfa; + struct isis_prefix_sid *psid = NULL; + bool last_hop = false; + + /* Skip pseudonodes. */ + if (LSP_PSEUDO_ID(sadj_N->id)) + continue; + + /* + * Skip nexthops that are along a link whose cost is + * infinite. + */ + if (CHECK_FLAG(sadj_N->flags, + F_ISIS_SPF_ADJ_METRIC_INFINITY)) + continue; + + /* Skip nexthops that have the overload bit set. */ + if (spftree->mtid != ISIS_MT_IPV4_UNICAST) { + struct isis_mt_router_info *mt_router_info; + + mt_router_info = + isis_tlvs_lookup_mt_router_info( + sadj_N->lsp->tlvs, + spftree->mtid); + if (mt_router_info && mt_router_info->overload) + continue; + } else if (ISIS_MASK_LSP_OL_BIT( + sadj_N->lsp->hdr.lsp_bits)) + continue; + + /* Skip primary nexthop. */ + if (spf_adj_check_is_affected(sadj_N, resource, NULL, + false)) + continue; + + /* Skip excluded interfaces as per the configuration. */ + if (circuit + && isis_lfa_excluded_iface_check( + circuit, level, + sadj_N->adj->circuit->interface->name)) + continue; + + if (IS_DEBUG_LFA) + zlog_debug( + "ISIS-LFA: checking candidate LFA %s", + print_sys_hostname(sadj_N->id)); + + /* Check loop-free criterion. */ + if (!clfa_loop_free_check(spftree, vertex, sadj_primary, + sadj_N, &lfa_metric)) { + if (IS_DEBUG_LFA) + zlog_debug( + "ISIS-LFA: LFA condition not met for %s", + print_sys_hostname(sadj_N->id)); + continue; + } + + if (lfa_metric < best_metric) + best_metric = lfa_metric; + + if (IS_DEBUG_LFA) + zlog_debug( + "ISIS-LFA: %s is a valid loop-free alternate", + print_sys_hostname(sadj_N->id)); + + if (vertex->N.ip.sr.present) { + psid = &vertex->N.ip.sr.sid; + if (lfa_metric == sadj_N->metric) + last_hop = true; + } + lfa = isis_vertex_adj_add(spftree, vertex, lfa_list, + sadj_N, psid, last_hop); + lfa->lfa_metric = lfa_metric; + } + + if (list_isempty(lfa_list)) { + if (IS_DEBUG_LFA) + zlog_debug( + "ISIS-LFA: no valid local LFAs found"); + list_delete(&lfa_list); + continue; + } + + SET_FLAG(vertex->flags, F_ISIS_VERTEX_LFA_PROTECTED); + + /* Check tie-breakers. */ + filtered_lfa_list = + isis_lfa_tiebreakers(area, spftree, resource, vertex, + sadj_primary, lfa_list); + + /* Create backup route using the best LFAs. */ + allow_ecmp = area->lfa_load_sharing[level - 1]; + isis_route_create(&vertex->N.ip.p.dest, &vertex->N.ip.p.src, + best_metric, vertex->depth, &vertex->N.ip.sr, + filtered_lfa_list, allow_ecmp, area, + spftree->route_table_backup); + spftree->lfa.protection_counters.lfa[vertex->N.ip.priority] += + 1; + + list_delete(&filtered_lfa_list); + list_delete(&lfa_list); + } +} + +static void isis_spf_run_tilfa(struct isis_area *area, + struct isis_circuit *circuit, + struct isis_spftree *spftree, + struct isis_spftree *spftree_reverse, + struct lfa_protected_resource *resource) +{ + struct isis_spftree *spftree_pc_link; + struct isis_spftree *spftree_pc_node; + + /* Compute node protecting repair paths first (if necessary). */ + if (circuit->tilfa_node_protection[spftree->level - 1]) { + resource->type = LFA_NODE_PROTECTION; + spftree_pc_node = isis_tilfa_compute(area, spftree, + spftree_reverse, resource); + isis_spftree_del(spftree_pc_node); + + /* don't do link protection unless link-fallback is configured + */ + if (!circuit->tilfa_link_fallback[spftree->level - 1]) + return; + } + + /* Compute link protecting repair paths. */ + resource->type = LFA_LINK_PROTECTION; + spftree_pc_link = + isis_tilfa_compute(area, spftree, spftree_reverse, resource); + isis_spftree_del(spftree_pc_link); +} + +/** + * Run the LFA/RLFA/TI-LFA algorithms for all protected interfaces. + * + * @param area IS-IS area + * @param spftree IS-IS SPF tree + */ +void isis_spf_run_lfa(struct isis_area *area, struct isis_spftree *spftree) +{ + struct isis_spftree *spftree_reverse = NULL; + struct isis_circuit *circuit; + struct listnode *node; + int level = spftree->level; + + /* Run reverse SPF locally. */ + if (area->rlfa_protected_links[level - 1] > 0 + || area->tilfa_protected_links[level - 1] > 0) + spftree_reverse = isis_spf_reverse_run(spftree); + + /* Run forward SPF on all adjacent routers. */ + isis_spf_run_neighbors(spftree); + + /* Check which interfaces are protected. */ + for (ALL_LIST_ELEMENTS_RO(area->circuit_list, node, circuit)) { + struct lfa_protected_resource resource = {}; + struct isis_adjacency *adj; + static uint8_t null_sysid[ISIS_SYS_ID_LEN + 1]; + + if (!(circuit->is_type & level)) + continue; + + if (!circuit->lfa_protection[level - 1] + && !circuit->tilfa_protection[level - 1]) + continue; + + /* Fill in the protected resource. */ + switch (circuit->circ_type) { + case CIRCUIT_T_BROADCAST: + if (level == ISIS_LEVEL1) + memcpy(resource.adjacency, + circuit->u.bc.l1_desig_is, + ISIS_SYS_ID_LEN + 1); + else + memcpy(resource.adjacency, + circuit->u.bc.l2_desig_is, + ISIS_SYS_ID_LEN + 1); + /* Do nothing if no DR was elected yet. */ + if (!memcmp(resource.adjacency, null_sysid, + ISIS_SYS_ID_LEN + 1)) + continue; + break; + case CIRCUIT_T_P2P: + adj = circuit->u.p2p.neighbor; + if (!adj) + continue; + memcpy(resource.adjacency, adj->sysid, ISIS_SYS_ID_LEN); + LSP_PSEUDO_ID(resource.adjacency) = 0; + break; + default: + continue; + } + + if (circuit->lfa_protection[level - 1]) { + /* Run local LFA. */ + isis_lfa_compute(area, circuit, spftree, &resource); + + if (circuit->rlfa_protection[level - 1]) { + struct isis_spftree *spftree_pc; + uint32_t max_metric; + + /* Run remote LFA. */ + assert(spftree_reverse); + max_metric = + circuit->rlfa_max_metric[level - 1]; + spftree_pc = isis_rlfa_compute( + area, spftree, spftree_reverse, + max_metric, &resource); + listnode_add(spftree->lfa.remote.pc_spftrees, + spftree_pc); + } + } else if (circuit->tilfa_protection[level - 1]) { + /* Run TI-LFA. */ + assert(spftree_reverse); + isis_spf_run_tilfa(area, circuit, spftree, + spftree_reverse, &resource); + } + } + + if (spftree_reverse) + isis_spftree_del(spftree_reverse); +} |