From c951ee6eeeace451f89bfafbbf2ce9e9d554c22f Mon Sep 17 00:00:00 2001 From: Renato Westphal Date: Thu, 20 Aug 2020 19:55:42 -0300 Subject: [PATCH] isisd: add support for Topology Independent LFA (TI-LFA) TI-LFA is a modern fast-reroute (FRR) solution that leverages Segment Routing to pre-compute backup nexthops for all destinations in the network, helping to reduce traffic restoration times whenever a failure occurs. The backup nexthops are expected to be installed in the FIB so that they can be activated as soon as a failure is detected, making sub-50ms recovery possible (assuming an hierarchical FIB). TI-LFA is a huge step forward compared to prior IP-FRR solutions, like classic LFA and Remote LFA, as it guarantees 100% coverage for all destinations. This is possible thanks to the source routing capabilities of SR, which allows the backup nexthops to steer traffic around the failures (using as many SIDs as necessary). In addition to that, the repair paths always follow the post-convergence SPF tree, which prevents transient congestions and suboptimal routing from happening. Deploying TI-LFA is very simple as it only requires a single configuration command for each interface that needs to be protected (both link protection and node protection are available). In addition to IPv4 and IPv6 routes, SR Prefix-SIDs and Adj-SIDs are also protected by the backup nexthops computed by the TI-LFA algorithms. Signed-off-by: Renato Westphal --- isisd/isis_circuit.h | 2 + isisd/isis_lfa.c | 1087 ++++++++++++++++++++++++++++++++++++++ isisd/isis_lfa.h | 101 ++++ isisd/isis_memory.c | 1 + isisd/isis_memory.h | 1 + isisd/isis_nb_config.c | 87 +-- isisd/isis_route.c | 76 ++- isisd/isis_route.h | 18 +- isisd/isis_spf.c | 175 ++++-- isisd/isis_spf.h | 9 +- isisd/isis_spf_private.h | 20 +- isisd/isis_sr.c | 62 ++- isisd/isis_zebra.c | 173 ++++-- isisd/isisd.c | 38 ++ isisd/isisd.h | 7 +- isisd/subdir.am | 2 + 16 files changed, 1705 insertions(+), 154 deletions(-) create mode 100644 isisd/isis_lfa.c create mode 100644 isisd/isis_lfa.h diff --git a/isisd/isis_circuit.h b/isisd/isis_circuit.h index 48afd24b6d..b4b03bf6b9 100644 --- a/isisd/isis_circuit.h +++ b/isisd/isis_circuit.h @@ -141,6 +141,8 @@ struct isis_circuit { bool disable_threeway_adj; struct bfd_info *bfd_info; struct ldp_sync_info *ldp_sync_info; + bool tilfa_protection[ISIS_LEVELS]; + bool tilfa_node_protection[ISIS_LEVELS]; /* * Counters as in 10589--11.2.5.9 */ diff --git a/isisd/isis_lfa.c b/isisd/isis_lfa.c new file mode 100644 index 0000000000..e0a58c8f6e --- /dev/null +++ b/isisd/isis_lfa.c @@ -0,0 +1,1087 @@ +/* + * 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 + +#include "linklist.h" +#include "log.h" +#include "memory.h" +#include "vrf.h" +#include "table.h" +#include "srcdest_table.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 "isisd/isis_errors.h" + +DEFINE_MTYPE_STATIC(ISISD, ISIS_SPF_NODE, "ISIS SPF Node"); + +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); +} + +/** + * 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_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; +} + +/* Find SRGB associated to a System ID. */ +static struct isis_sr_block *tilfa_find_srgb(struct lspdb_head *lspdb, + const uint8_t *sysid) +{ + struct isis_lsp *lsp; + + lsp = isis_root_system_lsp(lspdb, sysid); + if (!lsp) + return NULL; + + if (!lsp->tlvs->router_cap + || lsp->tlvs->router_cap->srgb.range_size == 0) + return NULL; + + return &lsp->tlvs->router_cap->srgb; +} + +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)) { + struct isis_sr_block *srgb; + mpls_label_t label; + + switch (sid->type) { + case TILFA_SID_PREFIX: + srgb = tilfa_find_srgb(lspdb, sadj->id); + if (!srgb) { + zlog_warn("%s: SRGB not found for node %s", + __func__, + print_sys_hostname(sadj->id)); + goto error; + } + + /* Check if the SID index falls inside the SRGB. */ + if (sid->value.index >= srgb->range_size) { + flog_warn( + EC_ISIS_SID_OVERFLOW, + "%s: SID index %u falls outside remote SRGB range", + __func__, sid->value.index); + goto error; + } + + /* + * Prefix-SID: map SID index to label value within the + * SRGB. + */ + label = srgb->lower_bound + sid->value.index; + 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; + + if (!isis_vertex_adj_exists(spftree, vertex_pnode, sadj)) + continue; + + assert(!vadj->label_stack); + 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_qnode, sid_pnode; + mpls_label_t label_qnode; + + if (IS_DEBUG_TILFA) { + vid2string(vertex, buf, sizeof(buf)); + zlog_debug("ISIS-TI-LFA: vertex %s %s", + vtype2string(vertex->type), buf); + } + + 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) { + 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-TI-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_TILFA) + zlog_debug( + "ISIS-TI-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) { + uint32_t sid_index; + + /* The same P-node can't be used more than once. */ + if (isis_spf_node_find(used_pnodes, vertex->N.id)) { + if (IS_DEBUG_TILFA) + zlog_debug( + "ISIS-TI-LFA: skipping already used P-node"); + return 0; + } + isis_spf_node_new(used_pnodes, vertex->N.id); + + if (!vertex_child) { + if (IS_DEBUG_TILFA) + zlog_debug( + "ISIS-TI-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-TI-LFA: failed to find Prefix-SID corresponding to PQ-node %s", + print_sys_hostname(vertex->N.id)); + return -1; + } + + if (IS_DEBUG_TILFA) + zlog_debug( + "ISIS-TI-LFA: pushing Prefix-SID to %s (index %u)", + print_sys_hostname(vertex->N.id), sid_index); + sid_pnode.type = TILFA_SID_PREFIX; + sid_pnode.value.index = sid_index; + listnode_add_head(repair_list, &sid_pnode); + + /* Apply repair list. */ + 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 SPF vertex needs LFA protection. */ +static bool lfa_check_needs_protection(const struct isis_spftree *spftree_pc, + const struct isis_vertex *vertex) +{ + struct isis_vertex *vertex_old; + struct listnode *node; + size_t affected_nhs = 0; + struct isis_vertex_adj *vadj; + + /* Only local adjacencies need Adj-SID protection. */ + if (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; + + for (ALL_LIST_ELEMENTS_RO(vertex_old->Adj_N, node, vadj)) { + struct isis_spf_adj *sadj = vadj->sadj; + + if (spf_adj_check_is_affected( + sadj, &spftree_pc->lfa.protected_resource, + spftree_pc->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_old->Adj_N) == affected_nhs) + return true; + + return false; +} + +/** + * 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_lfa_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 (IS_DEBUG_TILFA) + vid2string(vertex, buf, sizeof(buf)); + + if (!lfa_check_needs_protection(spftree_pc, vertex)) { + if (IS_DEBUG_TILFA) + zlog_debug( + "ISIS-TI-LFA: %s %s unaffected by %s", + vtype2string(vertex->type), buf, + lfa_protected_resource2str( + &spftree_pc->lfa.protected_resource)); + + return -1; + } + + /* + * Check if the adjacency was already covered by node protection. + */ + 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.dest)) { + if (IS_DEBUG_TILFA) + zlog_debug( + "ISIS-TI-LFA: %s %s already covered by node protection", + vtype2string(vertex->type), buf); + + return -1; + } + } + + if (IS_DEBUG_TILFA) + zlog_debug( + "ISIS-TI-LFA: computing repair path(s) of %s %s w.r.t %s", + vtype2string(vertex->type), 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-TI-LFA: failed to compute repair path(s)"); + + 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; + char buf1[VID2STR_BUFFER]; + char buf2[VID2STR_BUFFER]; + + if (IS_DEBUG_TILFA) + zlog_debug("ISIS-TI-LFA: vertex %s parent %s", + vid2string(vertex, buf1, sizeof(buf1)), + vid2string(pvertex, buf2, sizeof(buf2))); + + 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 (IS_DEBUG_TILFA) + zlog_debug("ISIS-TI-LFA: checking %s", + vid2string(vertex, buf, sizeof(buf))); + + if (!vertex_is_affected(spftree_root, adj_nodes, p_space, + vertex, resource)) { + if (IS_DEBUG_TILFA) + zlog_debug( + "ISIS-TI-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_TILFA) + zlog_debug("ISIS-TI-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_TILFA) + zlog_debug( + "ISIS-TI-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. + */ + 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_TILFA) + zlog_debug( + "ISIS-TI-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_TILFA) + zlog_debug("ISIS-TI-LFA: computing the P/Q spaces w.r.t. %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_TILFA) + zlog_debug( + "ISIS-TI-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_TILFA) + zlog_debug("ISIS-TI-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; +} + +/** + * Run the TI-LFA algorithm for all proctected 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; + struct isis_circuit *circuit; + struct listnode *node; + + /* Run reverse SPF locally. */ + 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; + struct isis_spftree *spftree_pc_link; + struct isis_spftree *spftree_pc_node; + static uint8_t null_sysid[ISIS_SYS_ID_LEN + 1]; + + if (!(circuit->is_type & spftree->level)) + continue; + + if (!circuit->tilfa_protection[spftree->level - 1]) + continue; + + /* Fill in the protected resource. */ + switch (circuit->circ_type) { + case CIRCUIT_T_BROADCAST: + if (spftree->level == 1) + 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; + } + + /* 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); + } + + /* 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); + } + + isis_spftree_del(spftree_reverse); +} diff --git a/isisd/isis_lfa.h b/isisd/isis_lfa.h new file mode 100644 index 0000000000..62a7666f9c --- /dev/null +++ b/isisd/isis_lfa.h @@ -0,0 +1,101 @@ +/* + * 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 + */ + +#ifndef _FRR_ISIS_LFA_H +#define _FRR_ISIS_LFA_H + +enum isis_tilfa_sid_type { + TILFA_SID_PREFIX = 1, + TILFA_SID_ADJ, +}; + +struct isis_tilfa_sid { + enum isis_tilfa_sid_type type; + union { + uint32_t index; + mpls_label_t label; + } value; +}; + +RB_HEAD(isis_spf_nodes, isis_spf_node); +RB_PROTOTYPE(isis_spf_nodes, isis_spf_node, entry, isis_spf_node_compare) +struct isis_spf_node { + RB_ENTRY(isis_spf_node) entry; + + /* Node's System ID. */ + uint8_t sysid[ISIS_SYS_ID_LEN]; + + /* Local adjacencies over which this node is reachable. */ + struct list *adjacencies; + + /* Best metric of all adjacencies used to reach this node. */ + uint32_t best_metric; + + struct { + /* Node's forward SPT. */ + struct isis_spftree *spftree; + + /* Node's reverse SPT. */ + struct isis_spftree *spftree_reverse; + + /* Node's P-space. */ + struct isis_spf_nodes p_space; + } lfa; +}; + +enum lfa_protection_type { + LFA_LINK_PROTECTION = 1, + LFA_NODE_PROTECTION, +}; + +struct lfa_protected_resource { + /* The protection type. */ + enum lfa_protection_type type; + + /* The protected adjacency (might be a pseudonode). */ + uint8_t adjacency[ISIS_SYS_ID_LEN + 1]; + + /* List of nodes reachable over the protected interface. */ + struct isis_spf_nodes nodes; +}; + +/* Forward declaration(s). */ +struct isis_vertex; + +/* Prototypes. */ +void isis_spf_node_list_init(struct isis_spf_nodes *nodes); +void isis_spf_node_list_clear(struct isis_spf_nodes *nodes); +struct isis_spf_node *isis_spf_node_new(struct isis_spf_nodes *nodes, + const uint8_t *sysid); +struct isis_spf_node *isis_spf_node_find(const struct isis_spf_nodes *nodes, + const uint8_t *sysid); +bool isis_lfa_excise_adj_check(const struct isis_spftree *spftree, + const uint8_t *id); +bool isis_lfa_excise_node_check(const struct isis_spftree *spftree, + const uint8_t *id); +struct isis_spftree *isis_spf_reverse_run(const struct isis_spftree *spftree); +int isis_spf_run_neighbors(struct isis_spftree *spftree); +void isis_spf_run_lfa(struct isis_area *area, struct isis_spftree *spftree); +int isis_lfa_check(struct isis_spftree *spftree, struct isis_vertex *vertex); +struct isis_spftree * +isis_tilfa_compute(struct isis_area *area, struct isis_spftree *spftree, + struct isis_spftree *spftree_reverse, + struct lfa_protected_resource *protected_resource); + +#endif /* _FRR_ISIS_LFA_H */ diff --git a/isisd/isis_memory.c b/isisd/isis_memory.c index 2725459767..a64decc14f 100644 --- a/isisd/isis_memory.c +++ b/isisd/isis_memory.c @@ -39,6 +39,7 @@ DEFINE_MTYPE(ISISD, ISIS_SPFTREE, "ISIS SPFtree") DEFINE_MTYPE(ISISD, ISIS_VERTEX, "ISIS vertex") DEFINE_MTYPE(ISISD, ISIS_ROUTE_INFO, "ISIS route info") DEFINE_MTYPE(ISISD, ISIS_NEXTHOP, "ISIS nexthop") +DEFINE_MTYPE(ISISD, ISIS_NEXTHOP_LABELS, "ISIS nexthop MPLS labels") DEFINE_MTYPE(ISISD, ISIS_DICT, "ISIS dictionary") DEFINE_MTYPE(ISISD, ISIS_DICT_NODE, "ISIS dictionary node") DEFINE_MTYPE(ISISD, ISIS_EXT_ROUTE, "ISIS redistributed route") diff --git a/isisd/isis_memory.h b/isisd/isis_memory.h index e672340e84..6b63b3ccb8 100644 --- a/isisd/isis_memory.h +++ b/isisd/isis_memory.h @@ -38,6 +38,7 @@ DECLARE_MTYPE(ISIS_SPFTREE) DECLARE_MTYPE(ISIS_VERTEX) DECLARE_MTYPE(ISIS_ROUTE_INFO) DECLARE_MTYPE(ISIS_NEXTHOP) +DECLARE_MTYPE(ISIS_NEXTHOP_LABELS) DECLARE_MTYPE(ISIS_DICT) DECLARE_MTYPE(ISIS_DICT_NODE) DECLARE_MTYPE(ISIS_EXT_ROUTE) diff --git a/isisd/isis_nb_config.c b/isisd/isis_nb_config.c index 50c409ecb0..dc344cb5fe 100644 --- a/isisd/isis_nb_config.c +++ b/isisd/isis_nb_config.c @@ -43,6 +43,7 @@ #include "isisd/isis_csm.h" #include "isisd/isis_adjacency.h" #include "isisd/isis_spf.h" +#include "isisd/isis_spf_private.h" #include "isisd/isis_te.h" #include "isisd/isis_memory.h" #include "isisd/isis_mt.h" @@ -2945,15 +2946,24 @@ int lib_interface_isis_mpls_holddown_destroy(struct nb_cb_destroy_args *args) int lib_interface_isis_fast_reroute_level_1_ti_lfa_enable_modify( struct nb_cb_modify_args *args) { - switch (args->event) { - case NB_EV_VALIDATE: - case NB_EV_PREPARE: - case NB_EV_ABORT: - case NB_EV_APPLY: - /* TODO: implement me. */ - break; + struct isis_area *area; + struct isis_circuit *circuit; + + if (args->event != NB_EV_APPLY) + return NB_OK; + + circuit = nb_running_get_entry(args->dnode, NULL, true); + circuit->tilfa_protection[0] = yang_dnode_get_bool(args->dnode, NULL); + if (circuit->tilfa_protection[0]) + circuit->area->lfa_protected_links[0]++; + else { + assert(circuit->area->lfa_protected_links[0] > 0); + circuit->area->lfa_protected_links[0]--; } + area = circuit->area; + lsp_regenerate_schedule(area, area->is_type, 0); + return NB_OK; } @@ -2964,14 +2974,18 @@ int lib_interface_isis_fast_reroute_level_1_ti_lfa_enable_modify( int lib_interface_isis_fast_reroute_level_1_ti_lfa_node_protection_modify( struct nb_cb_modify_args *args) { - switch (args->event) { - case NB_EV_VALIDATE: - case NB_EV_PREPARE: - case NB_EV_ABORT: - case NB_EV_APPLY: - /* TODO: implement me. */ - break; - } + struct isis_area *area; + struct isis_circuit *circuit; + + if (args->event != NB_EV_APPLY) + return NB_OK; + + circuit = nb_running_get_entry(args->dnode, NULL, true); + circuit->tilfa_node_protection[0] = + yang_dnode_get_bool(args->dnode, NULL); + + area = circuit->area; + lsp_regenerate_schedule(area, area->is_type, 0); return NB_OK; } @@ -2983,15 +2997,24 @@ int lib_interface_isis_fast_reroute_level_1_ti_lfa_node_protection_modify( int lib_interface_isis_fast_reroute_level_2_ti_lfa_enable_modify( struct nb_cb_modify_args *args) { - switch (args->event) { - case NB_EV_VALIDATE: - case NB_EV_PREPARE: - case NB_EV_ABORT: - case NB_EV_APPLY: - /* TODO: implement me. */ - break; + struct isis_area *area; + struct isis_circuit *circuit; + + if (args->event != NB_EV_APPLY) + return NB_OK; + + circuit = nb_running_get_entry(args->dnode, NULL, true); + circuit->tilfa_protection[1] = yang_dnode_get_bool(args->dnode, NULL); + if (circuit->tilfa_protection[1]) + circuit->area->lfa_protected_links[1]++; + else { + assert(circuit->area->lfa_protected_links[1] > 0); + circuit->area->lfa_protected_links[1]--; } + area = circuit->area; + lsp_regenerate_schedule(area, area->is_type, 0); + return NB_OK; } @@ -3002,14 +3025,18 @@ int lib_interface_isis_fast_reroute_level_2_ti_lfa_enable_modify( int lib_interface_isis_fast_reroute_level_2_ti_lfa_node_protection_modify( struct nb_cb_modify_args *args) { - switch (args->event) { - case NB_EV_VALIDATE: - case NB_EV_PREPARE: - case NB_EV_ABORT: - case NB_EV_APPLY: - /* TODO: implement me. */ - break; - } + struct isis_area *area; + struct isis_circuit *circuit; + + if (args->event != NB_EV_APPLY) + return NB_OK; + + circuit = nb_running_get_entry(args->dnode, NULL, true); + circuit->tilfa_node_protection[1] = + yang_dnode_get_bool(args->dnode, NULL); + + area = circuit->area; + lsp_regenerate_schedule(area, area->is_type, 0); return NB_OK; } diff --git a/isisd/isis_route.c b/isisd/isis_route.c index fa06572555..0868ab487c 100644 --- a/isisd/isis_route.c +++ b/isisd/isis_route.c @@ -76,8 +76,9 @@ static struct isis_nexthop *isis_nexthop_create(int family, union g_addr *ip, return nexthop; } -static void isis_nexthop_delete(struct isis_nexthop *nexthop) +void isis_nexthop_delete(struct isis_nexthop *nexthop) { + XFREE(MTYPE_ISIS_NEXTHOP_LABELS, nexthop->label_stack); XFREE(MTYPE_ISIS_NEXTHOP, nexthop); } @@ -115,8 +116,9 @@ static struct isis_nexthop *nexthoplookup(struct list *nexthops, int family, return NULL; } -static void adjinfo2nexthop(int family, struct list *nexthops, - struct isis_adjacency *adj) +void adjinfo2nexthop(int family, struct list *nexthops, + struct isis_adjacency *adj, + struct mpls_label_stack *label_stack) { struct isis_nexthop *nh; union g_addr ip = {}; @@ -132,6 +134,7 @@ static void adjinfo2nexthop(int family, struct list *nexthops, AF_INET, &ip, adj->circuit->interface->ifindex); memcpy(nh->sysid, adj->sysid, sizeof(nh->sysid)); + nh->label_stack = label_stack; listnode_add(nexthops, nh); break; } @@ -147,6 +150,7 @@ static void adjinfo2nexthop(int family, struct list *nexthops, AF_INET6, &ip, adj->circuit->interface->ifindex); memcpy(nh->sysid, adj->sysid, sizeof(nh->sysid)); + nh->label_stack = label_stack; listnode_add(nexthops, nh); break; } @@ -160,13 +164,15 @@ static void adjinfo2nexthop(int family, struct list *nexthops, } static void isis_route_add_dummy_nexthops(struct isis_route_info *rinfo, - const uint8_t *sysid) + const uint8_t *sysid, + struct mpls_label_stack *label_stack) { struct isis_nexthop *nh; nh = XCALLOC(MTYPE_ISIS_NEXTHOP, sizeof(struct isis_nexthop)); memcpy(nh->sysid, sysid, sizeof(nh->sysid)); isis_sr_nexthop_reset(&nh->sr); + nh->label_stack = label_stack; listnode_add(rinfo->nexthops, nh); } @@ -186,13 +192,15 @@ static struct isis_route_info *isis_route_info_new(struct prefix *prefix, for (ALL_LIST_ELEMENTS_RO(adjacencies, node, vadj)) { struct isis_spf_adj *sadj = vadj->sadj; struct isis_adjacency *adj = sadj->adj; + struct mpls_label_stack *label_stack = vadj->label_stack; /* * Create dummy nexthops when running SPF on a testing * environment. */ if (CHECK_FLAG(im->options, F_ISIS_UNIT_TEST)) { - isis_route_add_dummy_nexthops(rinfo, sadj->id); + isis_route_add_dummy_nexthops(rinfo, sadj->id, + label_stack); continue; } @@ -219,7 +227,8 @@ static struct isis_route_info *isis_route_info_new(struct prefix *prefix, prefix->family); exit(1); } - adjinfo2nexthop(prefix->family, rinfo->nexthops, adj); + adjinfo2nexthop(prefix->family, rinfo->nexthops, adj, + label_stack); } rinfo->cost = cost; @@ -239,6 +248,12 @@ static void isis_route_info_delete(struct isis_route_info *route_info) XFREE(MTYPE_ISIS_ROUTE_INFO, route_info); } +void isis_route_node_cleanup(struct route_table *table, struct route_node *node) +{ + if (node->info) + isis_route_info_delete(node->info); +} + static int isis_route_info_same(struct isis_route_info *new, struct isis_route_info *old, char *buf, size_t buf_size) @@ -412,6 +427,7 @@ static void isis_route_update(struct isis_area *area, struct prefix *prefix, static void _isis_route_verify_table(struct isis_area *area, struct route_table *table, + struct route_table *table_backup, struct route_table **tables) { struct route_node *rnode, *drnode; @@ -433,6 +449,19 @@ static void _isis_route_verify_table(struct isis_area *area, (const struct prefix **)&dst_p, (const struct prefix **)&src_p); + /* Link primary route to backup route. */ + if (table_backup) { + struct route_node *rnode_bck; + + rnode_bck = srcdest_rnode_lookup(table_backup, dst_p, + src_p); + if (rnode_bck) { + rinfo->backup = rnode_bck->info; + UNSET_FLAG(rinfo->flag, + ISIS_ROUTE_FLAG_ZEBRA_SYNCED); + } + } + #ifdef EXTREME_DEBUG if (IS_DEBUG_RTE_EVENTS) { srcdest2str(dst_p, src_p, buff, sizeof(buff)); @@ -490,9 +519,10 @@ static void _isis_route_verify_table(struct isis_area *area, } } -void isis_route_verify_table(struct isis_area *area, struct route_table *table) +void isis_route_verify_table(struct isis_area *area, struct route_table *table, + struct route_table *table_backup) { - _isis_route_verify_table(area, table, NULL); + _isis_route_verify_table(area, table, table_backup, NULL); } /* Function to validate route tables for L1L2 areas. In this case we can't use @@ -507,9 +537,13 @@ void isis_route_verify_table(struct isis_area *area, struct route_table *table) * to the RIB with different zebra route types and let RIB handle this? */ void isis_route_verify_merge(struct isis_area *area, struct route_table *level1_table, - struct route_table *level2_table) + struct route_table *level1_table_backup, + struct route_table *level2_table, + struct route_table *level2_table_backup) { - struct route_table *tables[] = { level1_table, level2_table }; + struct route_table *tables[] = {level1_table, level2_table}; + struct route_table *tables_backup[] = {level1_table_backup, + level2_table_backup}; struct route_table *merge; struct route_node *rnode, *mrnode; @@ -519,6 +553,8 @@ void isis_route_verify_merge(struct isis_area *area, for (rnode = route_top(tables[level - 1]); rnode; rnode = srcdest_route_next(rnode)) { struct isis_route_info *rinfo = rnode->info; + struct route_node *rnode_bck; + if (!rinfo) continue; @@ -528,6 +564,16 @@ void isis_route_verify_merge(struct isis_area *area, srcdest_rnode_prefixes(rnode, (const struct prefix **)&prefix, (const struct prefix **)&src_p); + + /* Link primary route to backup route. */ + rnode_bck = srcdest_rnode_lookup( + tables_backup[level - 1], prefix, src_p); + if (rnode_bck) { + rinfo->backup = rnode_bck->info; + UNSET_FLAG(rinfo->flag, + ISIS_ROUTE_FLAG_ZEBRA_SYNCED); + } + mrnode = srcdest_rnode_get(merge, prefix, src_p); struct isis_route_info *mrinfo = mrnode->info; if (mrinfo) { @@ -566,7 +612,7 @@ void isis_route_verify_merge(struct isis_area *area, } } - _isis_route_verify_table(area, merge, tables); + _isis_route_verify_table(area, merge, NULL, tables); route_table_finish(merge); } @@ -580,6 +626,14 @@ void isis_route_invalidate_table(struct isis_area *area, continue; rinfo = rode->info; + if (rinfo->backup) { + rinfo->backup = NULL; + /* + * For now, always force routes that have backup + * nexthops to be reinstalled. + */ + UNSET_FLAG(rinfo->flag, ISIS_ROUTE_FLAG_ZEBRA_SYNCED); + } UNSET_FLAG(rinfo->flag, ISIS_ROUTE_FLAG_ACTIVE); } } diff --git a/isisd/isis_route.h b/isisd/isis_route.h index 0356668d7e..fbb548a79e 100644 --- a/isisd/isis_route.h +++ b/isisd/isis_route.h @@ -33,6 +33,7 @@ struct isis_nexthop { union g_addr ip; uint8_t sysid[ISIS_SYS_ID_LEN]; struct sr_nexthop_info sr; + struct mpls_label_stack *label_stack; }; struct isis_route_info { @@ -43,6 +44,7 @@ struct isis_route_info { uint32_t cost; uint32_t depth; struct list *nexthops; + struct isis_route_info *backup; }; DECLARE_HOOK(isis_route_update_hook, @@ -50,6 +52,10 @@ DECLARE_HOOK(isis_route_update_hook, struct isis_route_info *route_info), (area, prefix, route_info)) +void isis_nexthop_delete(struct isis_nexthop *nexthop); +void adjinfo2nexthop(int family, struct list *nexthops, + struct isis_adjacency *adj, + struct mpls_label_stack *label_stack); struct isis_route_info *isis_route_create(struct prefix *prefix, struct prefix_ipv6 *src_p, uint32_t cost, @@ -60,16 +66,22 @@ struct isis_route_info *isis_route_create(struct prefix *prefix, /* Walk the given table and install new routes to zebra and remove old ones. * route status is tracked using ISIS_ROUTE_FLAG_ACTIVE */ -void isis_route_verify_table(struct isis_area *area, - struct route_table *table); +void isis_route_verify_table(struct isis_area *area, struct route_table *table, + struct route_table *table_backup); /* Same as isis_route_verify_table, but merge L1 and L2 routes before */ void isis_route_verify_merge(struct isis_area *area, struct route_table *level1_table, - struct route_table *level2_table); + struct route_table *level1_table_backup, + struct route_table *level2_table, + struct route_table *level2_table_backup); /* Unset ISIS_ROUTE_FLAG_ACTIVE on all routes. Used before running spf. */ void isis_route_invalidate_table(struct isis_area *area, struct route_table *table); +/* Cleanup route node when freeing routing table. */ +void isis_route_node_cleanup(struct route_table *table, + struct route_node *node); + #endif /* _ZEBRA_ISIS_ROUTE_H */ diff --git a/isisd/isis_spf.c b/isisd/isis_spf.c index dd0a6ec824..e18f09b66b 100644 --- a/isisd/isis_spf.c +++ b/isisd/isis_spf.c @@ -138,7 +138,7 @@ static void remove_excess_adjs(struct list *adjs) return; } -static const char *vtype2string(enum vertextype vtype) +const char *vtype2string(enum vertextype vtype) { switch (vtype) { case VTYPE_PSEUDO_IS: @@ -167,7 +167,7 @@ static const char *vtype2string(enum vertextype vtype) return NULL; /* Not reached */ } -const char *vid2string(struct isis_vertex *vertex, char *buff, int size) +const char *vid2string(const struct isis_vertex *vertex, char *buff, int size) { if (VTYPE_IS(vertex->type) || VTYPE_ES(vertex->type)) { const char *hostname = print_sys_hostname(vertex->N.id); @@ -286,6 +286,9 @@ struct isis_spftree *isis_spftree_new(struct isis_area *area, isis_vertex_queue_init(&tree->tents, "IS-IS SPF tents", true); isis_vertex_queue_init(&tree->paths, "IS-IS SPF paths", false); tree->route_table = srcdest_table_init(); + tree->route_table->cleanup = isis_route_node_cleanup; + tree->route_table_backup = srcdest_table_init(); + tree->route_table_backup->cleanup = isis_route_node_cleanup; tree->area = area; tree->lspdb = lspdb; tree->sadj_list = list_new(); @@ -300,16 +303,26 @@ struct isis_spftree *isis_spftree_new(struct isis_area *area, tree->tree_id = tree_id; tree->family = (tree->tree_id == SPFTREE_IPV4) ? AF_INET : AF_INET6; tree->flags = flags; + if (tree->type == SPF_TYPE_TI_LFA) { + isis_spf_node_list_init(&tree->lfa.p_space); + isis_spf_node_list_init(&tree->lfa.q_space); + } return tree; } void isis_spftree_del(struct isis_spftree *spftree) { + if (spftree->type == SPF_TYPE_TI_LFA) { + isis_spf_node_list_clear(&spftree->lfa.q_space); + isis_spf_node_list_clear(&spftree->lfa.p_space); + } + isis_spf_node_list_clear(&spftree->adj_nodes); list_delete(&spftree->sadj_list); isis_vertex_queue_free(&spftree->tents); isis_vertex_queue_free(&spftree->paths); route_table_finish(spftree->route_table); + route_table_finish(spftree->route_table_backup); spftree->route_table = NULL; XFREE(MTYPE_ISIS_SPFTREE, spftree); @@ -389,8 +402,8 @@ static int spf_adj_state_change(struct isis_adjacency *adj) * Find the system LSP: returns the LSP in our LSP database * associated with the given system ID. */ -static struct isis_lsp *isis_root_system_lsp(struct lspdb_head *lspdb, - uint8_t *sysid) +struct isis_lsp *isis_root_system_lsp(struct lspdb_head *lspdb, + const uint8_t *sysid) { struct isis_lsp *lsp; uint8_t lspid[ISIS_SYS_ID_LEN + 2]; @@ -663,6 +676,13 @@ static int isis_spf_process_lsp(struct isis_spftree *spftree, struct isis_mt_router_info *mt_router_info = NULL; struct prefix_pair ip_info; + if (isis_lfa_excise_node_check(spftree, lsp->hdr.lsp_id)) { + if (IS_DEBUG_TILFA) + zlog_debug("ISIS-LFA: excising node %s", + print_sys_hostname(lsp->hdr.lsp_id)); + return ISIS_OK; + } + if (!lsp->tlvs) return ISIS_OK; @@ -940,8 +960,22 @@ static void isis_spf_preload_tent(struct isis_spftree *spftree, /* Iterate over adjacencies. */ for (ALL_LIST_ELEMENTS_RO(spftree->sadj_list, node, sadj)) { + const uint8_t *adj_id; uint32_t metric; + if (CHECK_FLAG(sadj->flags, F_ISIS_SPF_ADJ_BROADCAST)) + adj_id = sadj->lan.desig_is_id; + else + adj_id = sadj->id; + + if (isis_lfa_excise_adj_check(spftree, adj_id)) { + if (IS_DEBUG_TILFA) + zlog_debug("ISIS-Spf: excising adjacency %s", + isis_format_id(sadj->id, + ISIS_SYS_ID_LEN + 1)); + continue; + } + metric = CHECK_FLAG(spftree->flags, F_SPFTREE_HOPCOUNT_METRIC) ? 1 : sadj->metric; @@ -1076,6 +1110,17 @@ static void spf_adj_list_parse_tlv(struct isis_spftree *spftree, /* Add adjacency to the list. */ listnode_add(spftree->sadj_list, sadj); + if (!LSP_PSEUDO_ID(id)) { + struct isis_spf_node *node; + + node = isis_spf_node_find(&spftree->adj_nodes, id); + if (!node) + node = isis_spf_node_new(&spftree->adj_nodes, id); + if (node->best_metric == 0 || sadj->metric < node->best_metric) + node->best_metric = sadj->metric; + listnode_add(node->adjacencies, sadj); + } + /* Parse pseudonode LSP too. */ if (LSP_PSEUDO_ID(id)) { uint8_t lspid[ISIS_SYS_ID_LEN + 2]; @@ -1177,6 +1222,7 @@ static void isis_spf_build_adj_list(struct isis_spftree *spftree, static void add_to_paths(struct isis_spftree *spftree, struct isis_vertex *vertex) { + struct isis_area *area = spftree->area; char buff[VID2STR_BUFFER]; if (isis_find_vertex(&spftree->paths, &vertex->N, vertex->type)) @@ -1192,14 +1238,23 @@ static void add_to_paths(struct isis_spftree *spftree, if (VTYPE_IP(vertex->type) && !CHECK_FLAG(spftree->flags, F_SPFTREE_NO_ROUTES)) { - if (listcount(vertex->Adj_N) > 0) + if (listcount(vertex->Adj_N) > 0) { + struct route_table *route_table; + + if (spftree->type == SPF_TYPE_TI_LFA) { + if (isis_lfa_check(spftree, vertex) != 0) + return; + route_table = spftree->lfa.old.spftree + ->route_table_backup; + } else + route_table = spftree->route_table; + isis_route_create(&vertex->N.ip.dest, &vertex->N.ip.src, vertex->d_N, vertex->depth, - vertex->Adj_N, spftree->area, - spftree->route_table); - else if (IS_DEBUG_SPF_EVENTS) + vertex->Adj_N, area, route_table); + } else if (IS_DEBUG_SPF_EVENTS) zlog_debug( - "ISIS-Spf: no adjacencies do not install route for %s depth %d dist %d", + "ISIS-Spf: no adjacencies, do not install route for %s depth %d dist %d", vid2string(vertex, buff, sizeof(buff)), vertex->depth, vertex->d_N); } @@ -1210,6 +1265,7 @@ static void add_to_paths(struct isis_spftree *spftree, static void init_spt(struct isis_spftree *spftree, int mtid) { /* Clear data from previous run. */ + isis_spf_node_list_clear(&spftree->adj_nodes); list_delete_all_node(spftree->sadj_list); isis_vertex_queue_clear(&spftree->tents); isis_vertex_queue_clear(&spftree->paths); @@ -1356,28 +1412,48 @@ void isis_run_spf(struct isis_spftree *spftree) + (time_end.tv_usec - time_start.tv_usec); } +static void isis_run_spf_with_protection(struct isis_area *area, + struct isis_spftree *spftree) +{ + /* Run forward SPF locally. */ + memcpy(spftree->sysid, area->isis->sysid, ISIS_SYS_ID_LEN); + isis_run_spf(spftree); + + /* Run LFA protection if configured. */ + if (area->lfa_protected_links[spftree->level - 1] > 0) + isis_spf_run_lfa(area, spftree); +} + void isis_spf_verify_routes(struct isis_area *area, struct isis_spftree **trees) { if (area->is_type == IS_LEVEL_1) { - isis_route_verify_table(area, trees[0]->route_table); + isis_route_verify_table(area, trees[0]->route_table, + trees[0]->route_table_backup); } else if (area->is_type == IS_LEVEL_2) { - isis_route_verify_table(area, trees[1]->route_table); + isis_route_verify_table(area, trees[1]->route_table, + trees[1]->route_table_backup); } else { isis_route_verify_merge(area, trees[0]->route_table, - trees[1]->route_table); + trees[0]->route_table_backup, + trees[1]->route_table, + trees[1]->route_table_backup); } } void isis_spf_invalidate_routes(struct isis_spftree *tree) { isis_route_invalidate_table(tree->area, tree->route_table); + + /* Delete backup routes. */ + route_table_finish(tree->route_table_backup); + tree->route_table_backup = srcdest_table_init(); + tree->route_table_backup->cleanup = isis_route_node_cleanup; } static int isis_run_spf_cb(struct thread *thread) { struct isis_spf_run *run = THREAD_ARG(thread); struct isis_area *area = run->area; - struct isis_spftree *spftree; int level = run->level; XFREE(MTYPE_ISIS_SPF_RUN, run); @@ -1396,21 +1472,15 @@ static int isis_run_spf_cb(struct thread *thread) zlog_debug("ISIS-Spf (%s) L%d SPF needed, periodic SPF", area->area_tag, level); - if (area->ip_circuits) { - spftree = area->spftree[SPFTREE_IPV4][level - 1]; - memcpy(spftree->sysid, area->isis->sysid, ISIS_SYS_ID_LEN); - isis_run_spf(spftree); - } - if (area->ipv6_circuits) { - spftree = area->spftree[SPFTREE_IPV6][level - 1]; - memcpy(spftree->sysid, area->isis->sysid, ISIS_SYS_ID_LEN); - isis_run_spf(spftree); - } - if (area->ipv6_circuits && isis_area_ipv6_dstsrc_enabled(area)) { - spftree = area->spftree[SPFTREE_DSTSRC][level - 1]; - memcpy(spftree->sysid, area->isis->sysid, ISIS_SYS_ID_LEN); - isis_run_spf(spftree); - } + if (area->ip_circuits) + isis_run_spf_with_protection( + area, area->spftree[SPFTREE_IPV4][level - 1]); + if (area->ipv6_circuits) + isis_run_spf_with_protection( + area, area->spftree[SPFTREE_IPV6][level - 1]); + if (area->ipv6_circuits && isis_area_ipv6_dstsrc_enabled(area)) + isis_run_spf_with_protection( + area, area->spftree[SPFTREE_DSTSRC][level - 1]); isis_area_verify_routes(area); @@ -1706,8 +1776,10 @@ DEFUN(show_isis_topology, show_isis_topology_cmd, return CMD_SUCCESS; } -void isis_print_routes(struct vty *vty, struct isis_spftree *spftree) +void isis_print_routes(struct vty *vty, struct isis_spftree *spftree, + bool backup) { + struct route_table *route_table; struct ttable *tt; struct route_node *rn; const char *tree_id_text = NULL; @@ -1741,7 +1813,9 @@ void isis_print_routes(struct vty *vty, struct isis_spftree *spftree) ttable_restyle(tt); ttable_rowseps(tt, 0, BOTTOM, true, '-'); - for (rn = route_top(spftree->route_table); rn; rn = route_next(rn)) { + route_table = + (backup) ? spftree->route_table_backup : spftree->route_table; + for (rn = route_top(route_table); rn; rn = route_next(rn)) { struct isis_route_info *rinfo; struct isis_nexthop *nexthop; struct listnode *node; @@ -1779,7 +1853,22 @@ void isis_print_routes(struct vty *vty, struct isis_spftree *spftree) strlcpy(buf_iface, "-", sizeof(buf_iface)); } - if (nexthop->sr.label != MPLS_INVALID_LABEL) + if (nexthop->label_stack) { + for (int i = 0; + i < nexthop->label_stack->num_labels; + i++) { + char buf_label[BUFSIZ]; + + label2str( + nexthop->label_stack->label[i], + buf_label, sizeof(buf_label)); + if (i != 0) + strlcat(buf_labels, "/", + sizeof(buf_labels)); + strlcat(buf_labels, buf_label, + sizeof(buf_labels)); + } + } else if (nexthop->sr.label != MPLS_INVALID_LABEL) label2str(nexthop->sr.label, buf_labels, sizeof(buf_labels)); else @@ -1808,7 +1897,7 @@ void isis_print_routes(struct vty *vty, struct isis_spftree *spftree) } static void show_isis_route_common(struct vty *vty, int levels, - struct isis *isis) + struct isis *isis, bool backup) { struct listnode *node; struct isis_area *area; @@ -1827,17 +1916,20 @@ static void show_isis_route_common(struct vty *vty, int levels, if (area->ip_circuits > 0) { isis_print_routes( vty, - area->spftree[SPFTREE_IPV4][level - 1]); + area->spftree[SPFTREE_IPV4][level - 1], + backup); } if (area->ipv6_circuits > 0) { isis_print_routes( vty, - area->spftree[SPFTREE_IPV6][level - 1]); + area->spftree[SPFTREE_IPV6][level - 1], + backup); } if (isis_area_ipv6_dstsrc_enabled(area)) { isis_print_routes(vty, area->spftree[SPFTREE_DSTSRC] - [level - 1]); + [level - 1], + backup); } } } @@ -1849,20 +1941,21 @@ DEFUN(show_isis_route, show_isis_route_cmd, #ifndef FABRICD " []" #endif - , + " [backup]", SHOW_STR PROTO_HELP VRF_FULL_CMD_HELP_STR "IS-IS routing table\n" #ifndef FABRICD "level-1 routes\n" "level-2 routes\n" #endif -) + "Show backup routes\n") { int levels; struct isis *isis; struct listnode *node; const char *vrf_name = VRF_DEFAULT_NAME; bool all_vrf = false; + bool backup = false; int idx = 0; if (argv_find(argv, argc, "level-1", &idx)) @@ -1878,15 +1971,19 @@ DEFUN(show_isis_route, show_isis_route_cmd, } ISIS_FIND_VRF_ARGS(argv, argc, idx, vrf_name, all_vrf); + if (argv_find(argv, argc, "backup", &idx)) + backup = true; + if (vrf_name) { if (all_vrf) { for (ALL_LIST_ELEMENTS_RO(im->isis, node, isis)) - show_isis_route_common(vty, levels, isis); + show_isis_route_common(vty, levels, isis, + backup); return CMD_SUCCESS; } isis = isis_lookup_by_vrfname(vrf_name); if (isis != NULL) - show_isis_route_common(vty, levels, isis); + show_isis_route_common(vty, levels, isis, backup); } return CMD_SUCCESS; diff --git a/isisd/isis_spf.h b/isisd/isis_spf.h index b2dc23496f..5d07c80d20 100644 --- a/isisd/isis_spf.h +++ b/isisd/isis_spf.h @@ -24,11 +24,14 @@ #ifndef _ZEBRA_ISIS_SPF_H #define _ZEBRA_ISIS_SPF_H +#include "isisd/isis_lfa.h" + struct isis_spftree; enum spf_type { SPF_TYPE_FORWARD = 1, SPF_TYPE_REVERSE, + SPF_TYPE_TI_LFA, }; struct isis_spf_adj { @@ -56,17 +59,21 @@ void isis_spf_verify_routes(struct isis_area *area, void isis_spftree_del(struct isis_spftree *spftree); void spftree_area_init(struct isis_area *area); void spftree_area_del(struct isis_area *area); +struct isis_lsp *isis_root_system_lsp(struct lspdb_head *lspdb, + const uint8_t *sysid); #define isis_spf_schedule(area, level) \ _isis_spf_schedule((area), (level), __func__, \ __FILE__, __LINE__) int _isis_spf_schedule(struct isis_area *area, int level, const char *func, const char *file, int line); void isis_print_spftree(struct vty *vty, struct isis_spftree *spftree); -void isis_print_routes(struct vty *vty, struct isis_spftree *spftree); +void isis_print_routes(struct vty *vty, struct isis_spftree *spftree, + bool backup); void isis_spf_init(void); void isis_spf_print(struct isis_spftree *spftree, struct vty *vty); void isis_run_spf(struct isis_spftree *spftree); struct isis_spftree *isis_run_hopcount_spf(struct isis_area *area, uint8_t *sysid, struct isis_spftree *spftree); + #endif /* _ZEBRA_ISIS_SPF_H */ diff --git a/isisd/isis_spf_private.h b/isisd/isis_spf_private.h index 1e61bf0f48..1a2e969bd9 100644 --- a/isisd/isis_spf_private.h +++ b/isisd/isis_spf_private.h @@ -306,8 +306,10 @@ struct isis_spftree { struct isis_vertex_queue paths; /* the SPT */ struct isis_vertex_queue tents; /* TENT */ struct route_table *route_table; + struct route_table *route_table_backup; struct lspdb_head *lspdb; /* link-state db */ struct list *sadj_list; + struct isis_spf_nodes adj_nodes; struct isis_area *area; /* back pointer to area */ unsigned int runcount; /* number of runs since uptime */ time_t last_run_timestamp; /* last run timestamp as wall time for display */ @@ -320,7 +322,20 @@ struct isis_spftree { int family; int level; enum spf_tree_id tree_id; - bool hopcount_metric; + struct { + /* Original pre-failure local SPTs. */ + struct { + struct isis_spftree *spftree; + struct isis_spftree *spftree_reverse; + } old; + + /* Protected resource. */ + struct lfa_protected_resource protected_resource; + + /* P-space and Q-space. */ + struct isis_spf_nodes p_space; + struct isis_spf_nodes q_space; + } lfa; uint8_t flags; }; #define F_SPFTREE_HOPCOUNT_METRIC 0x01 @@ -373,6 +388,7 @@ static struct isis_lsp *lsp_for_vertex(struct isis_spftree *spftree, } #define VID2STR_BUFFER SRCDEST2STR_BUFFER -const char *vid2string(struct isis_vertex *vertex, char *buff, int size); +const char *vtype2string(enum vertextype vtype); +const char *vid2string(const struct isis_vertex *vertex, char *buff, int size); #endif diff --git a/isisd/isis_sr.c b/isisd/isis_sr.c index d05afaa630..c2c34c24f3 100644 --- a/isisd/isis_sr.c +++ b/isisd/isis_sr.c @@ -1792,15 +1792,17 @@ static int sr_if_new_hook(struct interface *ifp) /** * Show LFIB operation in human readable format. * - * @param buf Buffer to store string output. Must be pre-allocate - * @param size Size of the buffer - * @param label_in Input Label - * @param label_out Output Label + * @param buf Buffer to store string output. Must be pre-allocate + * @param size Size of the buffer + * @param label_in Input Label + * @param label_out Output Label + * @param label_stack Output Label Stack (TI-LFA) * * @return String containing LFIB operation in human readable format */ static char *sr_op2str(char *buf, size_t size, mpls_label_t label_in, - mpls_label_t label_out) + mpls_label_t label_out, + const struct mpls_label_stack *label_stack) { if (size < 24) return NULL; @@ -1810,6 +1812,16 @@ static char *sr_op2str(char *buf, size_t size, mpls_label_t label_in, return buf; } + if (label_stack) { + char buf_labels[256]; + + mpls_label2str(label_stack->num_labels, &label_stack->label[0], + buf_labels, sizeof(buf_labels), 1); + + snprintf(buf, size, "Swap(%u, %s)", label_in, buf_labels); + return buf; + } + switch (label_out) { case MPLS_LABEL_IMPLICIT_NULL: snprintf(buf, size, "Pop(%u)", label_in); @@ -1859,7 +1871,7 @@ static void show_prefix_sid_local(struct vty *vty, struct ttable *tt, snprintf(buf_uptime, sizeof(buf_uptime), "-"); } sr_op2str(buf_oper, sizeof(buf_oper), srp->input_label, - MPLS_LABEL_IMPLICIT_NULL); + MPLS_LABEL_IMPLICIT_NULL, NULL); ttable_add_row(tt, "%s|%u|%s|-|%s|%s", prefix2str(&srp->prefix, buf_prefix, sizeof(buf_prefix)), @@ -1876,7 +1888,7 @@ static void show_prefix_sid_local(struct vty *vty, struct ttable *tt, */ static void show_prefix_sid_remote(struct vty *vty, struct ttable *tt, const struct isis_area *area, - const struct sr_prefix *srp) + const struct sr_prefix *srp, bool backup) { struct isis_nexthop *nexthop; struct listnode *node; @@ -1886,19 +1898,22 @@ static void show_prefix_sid_remote(struct vty *vty, struct ttable *tt, char buf_iface[BUFSIZ]; char buf_uptime[BUFSIZ]; bool first = true; + struct isis_route_info *rinfo; (void)prefix2str(&srp->prefix, buf_prefix, sizeof(buf_prefix)); - if (!srp->u.remote.rinfo) { + rinfo = srp->u.remote.rinfo; + if (rinfo && backup) + rinfo = rinfo->backup; + if (!rinfo) { ttable_add_row(tt, "%s|%u|%s|-|-|-", buf_prefix, srp->sid.value, sr_op2str(buf_oper, sizeof(buf_oper), srp->input_label, - MPLS_LABEL_IMPLICIT_NULL)); + MPLS_LABEL_IMPLICIT_NULL, NULL)); return; } - for (ALL_LIST_ELEMENTS_RO(srp->u.remote.rinfo->nexthops, node, - nexthop)) { + for (ALL_LIST_ELEMENTS_RO(rinfo->nexthops, node, nexthop)) { struct interface *ifp; inet_ntop(nexthop->family, &nexthop->ip, buf_nhop, @@ -1915,7 +1930,7 @@ static void show_prefix_sid_remote(struct vty *vty, struct ttable *tt, log_uptime(nexthop->sr.uptime, buf_uptime, sizeof(buf_uptime)); sr_op2str(buf_oper, sizeof(buf_oper), srp->input_label, - nexthop->sr.label); + nexthop->sr.label, nexthop->label_stack); if (first) ttable_add_row(tt, "%s|%u|%s|%s|%s|%s", buf_prefix, @@ -1935,7 +1950,8 @@ static void show_prefix_sid_remote(struct vty *vty, struct ttable *tt, * @param area IS-IS area * @param level IS-IS level */ -static void show_prefix_sids(struct vty *vty, struct isis_area *area, int level) +static void show_prefix_sids(struct vty *vty, struct isis_area *area, int level, + bool backup) { struct sr_prefix *srp; struct ttable *tt; @@ -1960,7 +1976,7 @@ static void show_prefix_sids(struct vty *vty, struct isis_area *area, int level) show_prefix_sid_local(vty, tt, area, srp); break; case ISIS_SR_PREFIX_REMOTE: - show_prefix_sid_remote(vty, tt, area, srp); + show_prefix_sid_remote(vty, tt, area, srp, backup); break; } } @@ -1980,20 +1996,25 @@ static void show_prefix_sids(struct vty *vty, struct isis_area *area, int level) * Declaration of new show commands. */ DEFUN(show_sr_prefix_sids, show_sr_prefix_sids_cmd, - "show isis [vrf ] segment-routing prefix-sids", + "show isis [vrf ] segment-routing prefix-sids [backup]", SHOW_STR PROTO_HELP VRF_CMD_HELP_STR "All VRFs\n" "Segment-Routing\n" - "Segment-Routing Prefix-SIDs\n") + "Segment-Routing Prefix-SIDs\n" + "Show backup Prefix-SIDs\n") { struct listnode *node, *inode; struct isis_area *area; struct isis *isis = NULL; const char *vrf_name = VRF_DEFAULT_NAME; bool all_vrf = false; - int idx_vrf = 0; + bool backup = false; + int idx = 0; + + ISIS_FIND_VRF_ARGS(argv, argc, idx, vrf_name, all_vrf); + if (argv_find(argv, argc, "backup", &idx)) + backup = true; - ISIS_FIND_VRF_ARGS(argv, argc, idx_vrf, vrf_name, all_vrf); if (vrf_name) { if (all_vrf) { for (ALL_LIST_ELEMENTS_RO(im->isis, inode, isis)) { @@ -2005,7 +2026,7 @@ DEFUN(show_sr_prefix_sids, show_sr_prefix_sids_cmd, for (int level = ISIS_LEVEL1; level <= ISIS_LEVELS; level++) show_prefix_sids(vty, area, - level); + level, backup); } } return 0; @@ -2019,7 +2040,8 @@ DEFUN(show_sr_prefix_sids, show_sr_prefix_sids_cmd, : "null"); for (int level = ISIS_LEVEL1; level <= ISIS_LEVELS; level++) - show_prefix_sids(vty, area, level); + show_prefix_sids(vty, area, level, + backup); } } } diff --git a/isisd/isis_zebra.c b/isisd/isis_zebra.c index 9ed868e795..26cc175a52 100644 --- a/isisd/isis_zebra.c +++ b/isisd/isis_zebra.c @@ -168,42 +168,29 @@ static int isis_zebra_link_params(ZAPI_CALLBACK_ARGS) return 0; } -void isis_zebra_route_add_route(struct isis *isis, - struct prefix *prefix, - struct prefix_ipv6 *src_p, - struct isis_route_info *route_info) +enum isis_zebra_nexthop_type { + ISIS_ROUTE_NEXTHOP_MAIN = 0, + ISIS_ROUTE_NEXTHOP_BACKUP, + ISIS_MPLS_NEXTHOP_MAIN, + ISIS_MPLS_NEXTHOP_BACKUP, +}; + +static int isis_zebra_add_nexthops(struct isis *isis, struct list *nexthops, + struct zapi_nexthop zapi_nexthops[], + enum isis_zebra_nexthop_type type, + uint8_t backup_nhs) { - struct zapi_route api; - struct zapi_nexthop *api_nh; struct isis_nexthop *nexthop; struct listnode *node; int count = 0; - if (zclient->sock < 0) - return; - - memset(&api, 0, sizeof(api)); - api.vrf_id = isis->vrf_id; - api.type = PROTO_TYPE; - api.safi = SAFI_UNICAST; - api.prefix = *prefix; - if (src_p && src_p->prefixlen) { - api.src_prefix = *src_p; - SET_FLAG(api.message, ZAPI_MESSAGE_SRCPFX); - } - SET_FLAG(api.message, ZAPI_MESSAGE_NEXTHOP); - SET_FLAG(api.message, ZAPI_MESSAGE_METRIC); - api.metric = route_info->cost; -#if 0 - SET_FLAG(api.message, ZAPI_MESSAGE_DISTANCE); - api.distance = route_info->depth; -#endif - /* Nexthops */ - for (ALL_LIST_ELEMENTS_RO(route_info->nexthops, node, nexthop)) { + for (ALL_LIST_ELEMENTS_RO(nexthops, node, nexthop)) { + struct zapi_nexthop *api_nh; + if (count >= MULTIPATH_NUM) break; - api_nh = &api.nexthops[count]; + api_nh = &zapi_nexthops[count]; if (fabricd) SET_FLAG(api_nh->flags, ZAPI_NEXTHOP_FLAG_ONLINK); api_nh->vrf_id = isis->vrf_id; @@ -234,11 +221,98 @@ void isis_zebra_route_add_route(struct isis *isis, } api_nh->ifindex = nexthop->ifindex; + + /* Add MPLS label(s). */ + switch (type) { + case ISIS_ROUTE_NEXTHOP_MAIN: + case ISIS_ROUTE_NEXTHOP_BACKUP: + /* + * SR/TI-LFA labels are installed using separate + * messages. + */ + break; + case ISIS_MPLS_NEXTHOP_MAIN: + if (nexthop->sr.label != MPLS_INVALID_LABEL) { + api_nh->label_num = 1; + api_nh->labels[0] = nexthop->sr.label; + } else { + api_nh->label_num = 1; + api_nh->labels[0] = MPLS_LABEL_IMPLICIT_NULL; + } + break; + case ISIS_MPLS_NEXTHOP_BACKUP: + if (nexthop->label_stack) { + api_nh->label_num = + nexthop->label_stack->num_labels; + memcpy(api_nh->labels, + nexthop->label_stack->label, + sizeof(mpls_label_t) + * api_nh->label_num); + } else { + api_nh->label_num = 1; + api_nh->labels[0] = MPLS_LABEL_IMPLICIT_NULL; + } + break; + } + + /* Backup nexthop handling. */ + if (backup_nhs) { + SET_FLAG(api_nh->flags, ZAPI_NEXTHOP_FLAG_HAS_BACKUP); + /* + * If the backup has multiple nexthops, all of them + * protect the same primary nexthop since ECMP routes + * have no backups. + */ + api_nh->backup_num = backup_nhs; + for (int i = 0; i < backup_nhs; i++) + api_nh->backup_idx[i] = i; + } count++; } - if (!count) + + return count; +} + +void isis_zebra_route_add_route(struct isis *isis, struct prefix *prefix, + struct prefix_ipv6 *src_p, + struct isis_route_info *route_info) +{ + struct zapi_route api; + int count = 0; + + if (zclient->sock < 0) return; + memset(&api, 0, sizeof(api)); + api.vrf_id = isis->vrf_id; + api.type = PROTO_TYPE; + api.safi = SAFI_UNICAST; + api.prefix = *prefix; + if (src_p && src_p->prefixlen) { + api.src_prefix = *src_p; + SET_FLAG(api.message, ZAPI_MESSAGE_SRCPFX); + } + SET_FLAG(api.message, ZAPI_MESSAGE_NEXTHOP); + SET_FLAG(api.message, ZAPI_MESSAGE_METRIC); + api.metric = route_info->cost; + + /* Add backup nexthops first. */ + if (route_info->backup) { + count = isis_zebra_add_nexthops( + isis, route_info->backup->nexthops, api.backup_nexthops, + ISIS_ROUTE_NEXTHOP_BACKUP, 0); + if (count > 0) { + SET_FLAG(api.message, ZAPI_MESSAGE_BACKUP_NEXTHOPS); + api.backup_nexthop_num = count; + } + } + + /* Add primary nexthops. */ + count = isis_zebra_add_nexthops(isis, route_info->nexthops, + api.nexthops, ISIS_ROUTE_NEXTHOP_MAIN, + count); + if (!count) + return; api.nexthop_num = count; zclient_route_send(ZEBRA_ROUTE_ADD, zclient, &api); @@ -274,11 +348,12 @@ void isis_zebra_route_del_route(struct isis *isis, */ static void isis_zebra_prefix_install_prefix_sid(const struct sr_prefix *srp) { + struct isis *isis = srp->srn->area->isis; struct zapi_labels zl; struct zapi_nexthop *znh; - struct listnode *node; - struct isis_nexthop *nexthop; struct interface *ifp; + struct isis_route_info *rinfo; + int count = 0; /* Prepare message. */ memset(&zl, 0, sizeof(zl)); @@ -308,23 +383,27 @@ static void isis_zebra_prefix_install_prefix_sid(const struct sr_prefix *srp) zl.route.type = ZEBRA_ROUTE_ISIS; zl.route.instance = 0; - for (ALL_LIST_ELEMENTS_RO(srp->u.remote.rinfo->nexthops, node, - nexthop)) { - if (nexthop->sr.label == MPLS_INVALID_LABEL) - continue; - - if (zl.nexthop_num >= MULTIPATH_NUM) - break; - - znh = &zl.nexthops[zl.nexthop_num++]; - znh->type = (srp->prefix.family == AF_INET) - ? NEXTHOP_TYPE_IPV4_IFINDEX - : NEXTHOP_TYPE_IPV6_IFINDEX; - znh->gate = nexthop->ip; - znh->ifindex = nexthop->ifindex; - znh->label_num = 1; - znh->labels[0] = nexthop->sr.label; + rinfo = srp->u.remote.rinfo; + + /* Add backup nexthops first. */ + if (rinfo->backup) { + count = isis_zebra_add_nexthops( + isis, rinfo->backup->nexthops, + zl.backup_nexthops, ISIS_MPLS_NEXTHOP_BACKUP, + 0); + if (count > 0) { + SET_FLAG(zl.message, ZAPI_LABELS_HAS_BACKUPS); + zl.backup_nexthop_num = count; + } } + + /* Add primary nexthops. */ + count = isis_zebra_add_nexthops(isis, rinfo->nexthops, + zl.nexthops, + ISIS_MPLS_NEXTHOP_MAIN, count); + if (!count) + return; + zl.nexthop_num = count; break; } diff --git a/isisd/isisd.c b/isisd/isisd.c index 8d73c0571d..57d3e9c7c0 100644 --- a/isisd/isisd.c +++ b/isisd/isisd.c @@ -77,6 +77,7 @@ unsigned long debug_bfd; unsigned long debug_tx_queue; unsigned long debug_sr; unsigned long debug_ldp_sync; +unsigned long debug_tilfa; DEFINE_QOBJ_TYPE(isis_area) @@ -1191,6 +1192,8 @@ void print_debug(struct vty *vty, int flags, int onoff) if (flags & DEBUG_SR) vty_out(vty, "IS-IS Segment Routing events debugging is %s\n", onoffs); + if (flags & DEBUG_TILFA) + vty_out(vty, "IS-IS TI-LFA events debugging is %s\n", onoffs); if (flags & DEBUG_UPDATE_PACKETS) vty_out(vty, "IS-IS Update related packet debugging is %s\n", onoffs); @@ -1285,6 +1288,10 @@ static int config_write_debug(struct vty *vty) vty_out(vty, "debug " PROTO_NAME " sr-events\n"); write++; } + if (IS_DEBUG_TILFA) { + vty_out(vty, "debug " PROTO_NAME " ti-lfa\n"); + write++; + } if (IS_DEBUG_UPDATE_PACKETS) { vty_out(vty, "debug " PROTO_NAME " update-packets\n"); write++; @@ -1515,6 +1522,33 @@ DEFUN (no_debug_isis_srevents, return CMD_SUCCESS; } +DEFUN (debug_isis_tilfa, + debug_isis_tilfa_cmd, + "debug " PROTO_NAME " ti-lfa", + DEBUG_STR + PROTO_HELP + "IS-IS TI-LFA Events\n") +{ + debug_tilfa |= DEBUG_TILFA; + print_debug(vty, DEBUG_TILFA, 1); + + return CMD_SUCCESS; +} + +DEFUN (no_debug_isis_tilfa, + no_debug_isis_tilfa_cmd, + "no debug " PROTO_NAME " ti-lfa", + NO_STR + UNDEBUG_STR + PROTO_HELP + "IS-IS TI-LFA Events\n") +{ + debug_tilfa &= ~DEBUG_TILFA; + print_debug(vty, DEBUG_TILFA, 0); + + return CMD_SUCCESS; +} + DEFUN (debug_isis_rtevents, debug_isis_rtevents_cmd, "debug " PROTO_NAME " route-events", @@ -2848,6 +2882,8 @@ void isis_init(void) install_element(ENABLE_NODE, &no_debug_isis_spfevents_cmd); install_element(ENABLE_NODE, &debug_isis_srevents_cmd); install_element(ENABLE_NODE, &no_debug_isis_srevents_cmd); + install_element(ENABLE_NODE, &debug_isis_tilfa_cmd); + install_element(ENABLE_NODE, &no_debug_isis_tilfa_cmd); install_element(ENABLE_NODE, &debug_isis_rtevents_cmd); install_element(ENABLE_NODE, &no_debug_isis_rtevents_cmd); install_element(ENABLE_NODE, &debug_isis_events_cmd); @@ -2877,6 +2913,8 @@ void isis_init(void) install_element(CONFIG_NODE, &no_debug_isis_spfevents_cmd); install_element(CONFIG_NODE, &debug_isis_srevents_cmd); install_element(CONFIG_NODE, &no_debug_isis_srevents_cmd); + install_element(CONFIG_NODE, &debug_isis_tilfa_cmd); + install_element(CONFIG_NODE, &no_debug_isis_tilfa_cmd); install_element(CONFIG_NODE, &debug_isis_rtevents_cmd); install_element(CONFIG_NODE, &no_debug_isis_rtevents_cmd); install_element(CONFIG_NODE, &debug_isis_events_cmd); diff --git a/isisd/isisd.h b/isisd/isisd.h index d8df6eead9..921df4d7ef 100644 --- a/isisd/isisd.h +++ b/isisd/isisd.h @@ -188,6 +188,8 @@ struct isis_area { struct isis_sr_db srdb; int ipv6_circuits; bool purge_originator; + /* Fast Re-Route information. */ + size_t lfa_protected_links[ISIS_LEVELS]; /* Counters */ uint32_t circuit_state_changes; struct isis_redist redist_settings[REDIST_PROTOCOL_COUNT] @@ -278,6 +280,7 @@ extern unsigned long debug_bfd; extern unsigned long debug_tx_queue; extern unsigned long debug_sr; extern unsigned long debug_ldp_sync; +extern unsigned long debug_tilfa; #define DEBUG_ADJ_PACKETS (1<<0) #define DEBUG_SNP_PACKETS (1<<1) @@ -292,7 +295,8 @@ extern unsigned long debug_ldp_sync; #define DEBUG_BFD (1<<10) #define DEBUG_TX_QUEUE (1<<11) #define DEBUG_SR (1<<12) -#define DEBUG_LDP_SYNC (1 << 13) +#define DEBUG_LDP_SYNC (1<<13) +#define DEBUG_TILFA (1<<14) /* Debug related macro. */ #define IS_DEBUG_ADJ_PACKETS (debug_adj_pkt & DEBUG_ADJ_PACKETS) @@ -309,6 +313,7 @@ extern unsigned long debug_ldp_sync; #define IS_DEBUG_TX_QUEUE (debug_tx_queue & DEBUG_TX_QUEUE) #define IS_DEBUG_SR (debug_sr & DEBUG_SR) #define IS_DEBUG_LDP_SYNC (debug_ldp_sync & DEBUG_LDP_SYNC) +#define IS_DEBUG_TILFA (debug_tilfa & DEBUG_TILFA) #define lsp_debug(...) \ do { \ diff --git a/isisd/subdir.am b/isisd/subdir.am index 1d59592626..4be4efc118 100644 --- a/isisd/subdir.am +++ b/isisd/subdir.am @@ -52,6 +52,7 @@ noinst_HEADERS += \ isisd/isis_events.h \ isisd/isis_flags.h \ isisd/isis_ldp_sync.h \ + isisd/isis_lfa.h \ isisd/isis_lsp.h \ isisd/isis_memory.h \ isisd/isis_misc.h \ @@ -86,6 +87,7 @@ LIBISIS_SOURCES = \ isisd/isis_events.c \ isisd/isis_flags.c \ isisd/isis_ldp_sync.c \ + isisd/isis_lfa.c \ isisd/isis_lsp.c \ isisd/isis_memory.c \ isisd/isis_misc.c \ -- 2.39.5