diff options
Diffstat (limited to 'isisd/isis_spf.c')
| -rw-r--r-- | isisd/isis_spf.c | 2718 |
1 files changed, 2718 insertions, 0 deletions
diff --git a/isisd/isis_spf.c b/isisd/isis_spf.c new file mode 100644 index 0000000..1980f99 --- /dev/null +++ b/isisd/isis_spf.c @@ -0,0 +1,2718 @@ +/* + * IS-IS Rout(e)ing protocol - isis_spf.c + * The SPT algorithm + * + * Copyright (C) 2001,2002 Sampo Saaristo + * Tampere University of Technology + * Institute of Communications Engineering + * Copyright (C) 2017 Christian Franke <chris@opensourcerouting.org> + * + * This program is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public Licenseas 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 "thread.h" +#include "linklist.h" +#include "vty.h" +#include "log.h" +#include "command.h" +#include "termtable.h" +#include "memory.h" +#include "prefix.h" +#include "filter.h" +#include "if.h" +#include "hash.h" +#include "table.h" +#include "spf_backoff.h" +#include "srcdest_table.h" +#include "vrf.h" + +#include "isis_errors.h" +#include "isis_constants.h" +#include "isis_common.h" +#include "isis_flags.h" +#include "isisd.h" +#include "isis_misc.h" +#include "isis_adjacency.h" +#include "isis_circuit.h" +#include "isis_pdu.h" +#include "isis_lsp.h" +#include "isis_dynhn.h" +#include "isis_spf.h" +#include "isis_route.h" +#include "isis_csm.h" +#include "isis_mt.h" +#include "isis_tlvs.h" +#include "isis_zebra.h" +#include "fabricd.h" +#include "isis_spf_private.h" + +DEFINE_MTYPE_STATIC(ISISD, ISIS_SPFTREE, "ISIS SPFtree"); +DEFINE_MTYPE_STATIC(ISISD, ISIS_SPF_RUN, "ISIS SPF Run Info"); +DEFINE_MTYPE_STATIC(ISISD, ISIS_SPF_ADJ, "ISIS SPF Adjacency"); +DEFINE_MTYPE_STATIC(ISISD, ISIS_VERTEX, "ISIS vertex"); +DEFINE_MTYPE_STATIC(ISISD, ISIS_VERTEX_ADJ, "ISIS SPF Vertex Adjacency"); + +static void spf_adj_list_parse_lsp(struct isis_spftree *spftree, + struct list *adj_list, struct isis_lsp *lsp, + const uint8_t *pseudo_nodeid, + uint32_t pseudo_metric); + +/* + * supports the given af ? + */ +static bool speaks(uint8_t *protocols, uint8_t count, int family) +{ + for (uint8_t i = 0; i < count; i++) { + if (family == AF_INET && protocols[i] == NLPID_IP) + return true; + if (family == AF_INET6 && protocols[i] == NLPID_IPV6) + return true; + } + return false; +} + +struct isis_spf_run { + struct isis_area *area; + int level; +}; + +/* 7.2.7 */ +static void remove_excess_adjs(struct list *adjs) +{ + struct listnode *node, *excess = NULL; + struct isis_vertex_adj *vadj, *candidate = NULL; + int comp; + + for (ALL_LIST_ELEMENTS_RO(adjs, node, vadj)) { + struct isis_adjacency *adj, *candidate_adj; + + adj = vadj->sadj->adj; + assert(adj); + + if (excess == NULL) + excess = node; + candidate = listgetdata(excess); + candidate_adj = candidate->sadj->adj; + + if (candidate_adj->sys_type < adj->sys_type) { + excess = node; + continue; + } + if (candidate_adj->sys_type > adj->sys_type) + continue; + + comp = memcmp(candidate_adj->sysid, adj->sysid, + ISIS_SYS_ID_LEN); + if (comp > 0) { + excess = node; + continue; + } + if (comp < 0) + continue; + + if (candidate_adj->circuit->idx > adj->circuit->idx) { + excess = node; + continue; + } + + if (candidate_adj->circuit->idx < adj->circuit->idx) + continue; + + comp = memcmp(candidate_adj->snpa, adj->snpa, ETH_ALEN); + if (comp > 0) { + excess = node; + continue; + } + } + + list_delete_node(adjs, excess); + + return; +} + +const char *vtype2string(enum vertextype vtype) +{ + switch (vtype) { + case VTYPE_PSEUDO_IS: + return "pseudo_IS"; + case VTYPE_PSEUDO_TE_IS: + return "pseudo_TE-IS"; + case VTYPE_NONPSEUDO_IS: + return "IS"; + case VTYPE_NONPSEUDO_TE_IS: + return "TE-IS"; + case VTYPE_ES: + return "ES"; + case VTYPE_IPREACH_INTERNAL: + return "IP internal"; + case VTYPE_IPREACH_EXTERNAL: + return "IP external"; + case VTYPE_IPREACH_TE: + return "IP TE"; + case VTYPE_IP6REACH_INTERNAL: + return "IP6 internal"; + case VTYPE_IP6REACH_EXTERNAL: + return "IP6 external"; + default: + return "UNKNOWN"; + } + return NULL; /* Not reached */ +} + +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); + strlcpy(buff, hostname, size); + return buff; + } + + if (VTYPE_IP(vertex->type)) { + srcdest2str(&vertex->N.ip.p.dest, &vertex->N.ip.p.src, buff, + size); + return buff; + } + + return "UNKNOWN"; +} + +static bool prefix_sid_cmp(const void *value1, const void *value2) +{ + const struct isis_vertex *c1 = value1; + const struct isis_vertex *c2 = value2; + + if (CHECK_FLAG(c1->N.ip.sr.sid.flags, + ISIS_PREFIX_SID_VALUE | ISIS_PREFIX_SID_LOCAL) + != CHECK_FLAG(c2->N.ip.sr.sid.flags, + ISIS_PREFIX_SID_VALUE | ISIS_PREFIX_SID_LOCAL)) + return false; + + return c1->N.ip.sr.sid.value == c2->N.ip.sr.sid.value; +} + +static unsigned int prefix_sid_key_make(const void *value) +{ + const struct isis_vertex *vertex = value; + + return jhash_1word(vertex->N.ip.sr.sid.value, 0); +} + +struct isis_vertex *isis_spf_prefix_sid_lookup(struct isis_spftree *spftree, + struct isis_prefix_sid *psid) +{ + struct isis_vertex lookup = {}; + + lookup.N.ip.sr.sid = *psid; + return hash_lookup(spftree->prefix_sids, &lookup); +} + +void isis_vertex_adj_free(void *arg) +{ + struct isis_vertex_adj *vadj = arg; + + XFREE(MTYPE_ISIS_VERTEX_ADJ, vadj); +} + +static struct isis_vertex *isis_vertex_new(struct isis_spftree *spftree, + void *id, + enum vertextype vtype) +{ + struct isis_vertex *vertex; + + vertex = XCALLOC(MTYPE_ISIS_VERTEX, sizeof(struct isis_vertex)); + + isis_vertex_id_init(vertex, id, vtype); + + vertex->Adj_N = list_new(); + vertex->Adj_N->del = isis_vertex_adj_free; + vertex->parents = list_new(); + + if (CHECK_FLAG(spftree->flags, F_SPFTREE_HOPCOUNT_METRIC)) { + vertex->firsthops = hash_create(isis_vertex_queue_hash_key, + isis_vertex_queue_hash_cmp, + NULL); + } + + return vertex; +} + +void isis_vertex_del(struct isis_vertex *vertex) +{ + list_delete(&vertex->Adj_N); + list_delete(&vertex->parents); + if (vertex->firsthops) { + hash_clean(vertex->firsthops, NULL); + hash_free(vertex->firsthops); + vertex->firsthops = NULL; + } + + memset(vertex, 0, sizeof(struct isis_vertex)); + XFREE(MTYPE_ISIS_VERTEX, vertex); +} + +struct isis_vertex_adj * +isis_vertex_adj_add(struct isis_spftree *spftree, struct isis_vertex *vertex, + struct list *vadj_list, struct isis_spf_adj *sadj, + struct isis_prefix_sid *psid, bool last_hop) +{ + struct isis_vertex_adj *vadj; + + vadj = XCALLOC(MTYPE_ISIS_VERTEX_ADJ, sizeof(*vadj)); + vadj->sadj = sadj; + if (spftree->area->srdb.enabled && psid) { + if (vertex->N.ip.sr.present + && vertex->N.ip.sr.sid.value != psid->value) + zlog_warn( + "ISIS-SPF: ignoring different Prefix-SID for route %pFX", + &vertex->N.ip.p.dest); + else { + vadj->sr.sid = *psid; + vadj->sr.label = sr_prefix_out_label( + spftree->lspdb, vertex->N.ip.p.dest.family, + psid, sadj->id, last_hop); + if (vadj->sr.label != MPLS_INVALID_LABEL) + vadj->sr.present = true; + } + } + listnode_add(vadj_list, vadj); + + return vadj; +} + +static void isis_vertex_adj_del(struct isis_vertex *vertex, + struct isis_adjacency *adj) +{ + struct isis_vertex_adj *vadj; + struct listnode *node, *nextnode; + + if (!vertex) + return; + + for (ALL_LIST_ELEMENTS(vertex->Adj_N, node, nextnode, vadj)) { + if (vadj->sadj->adj == adj) { + listnode_delete(vertex->Adj_N, vadj); + isis_vertex_adj_free(vadj); + } + } + return; +} + +bool isis_vertex_adj_exists(const struct isis_spftree *spftree, + const struct isis_vertex *vertex, + const struct isis_spf_adj *sadj) +{ + struct isis_vertex_adj *tmp; + struct listnode *node; + + for (ALL_LIST_ELEMENTS_RO(vertex->Adj_N, node, tmp)) { + if (CHECK_FLAG(spftree->flags, F_SPFTREE_NO_ADJACENCIES)) { + if (memcmp(sadj->id, tmp->sadj->id, sizeof(sadj->id)) + == 0) + return true; + } else { + if (sadj->adj == tmp->sadj->adj) + return true; + } + } + + return false; +} + +static void isis_spf_adj_free(void *arg) +{ + struct isis_spf_adj *sadj = arg; + + XFREE(MTYPE_ISIS_SPF_ADJ, sadj); +} + +struct isis_spftree *isis_spftree_new(struct isis_area *area, + struct lspdb_head *lspdb, + const uint8_t *sysid, int level, + enum spf_tree_id tree_id, + enum spf_type type, uint8_t flags) +{ + struct isis_spftree *tree; + + tree = XCALLOC(MTYPE_ISIS_SPFTREE, sizeof(struct isis_spftree)); + + 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->prefix_sids = hash_create(prefix_sid_key_make, prefix_sid_cmp, + "SR Prefix-SID Entries"); + tree->sadj_list = list_new(); + tree->sadj_list->del = isis_spf_adj_free; + tree->last_run_timestamp = 0; + tree->last_run_monotime = 0; + tree->last_run_duration = 0; + tree->runcount = 0; + tree->type = type; + memcpy(tree->sysid, sysid, ISIS_SYS_ID_LEN); + tree->level = level; + tree->tree_id = tree_id; + tree->family = (tree->tree_id == SPFTREE_IPV4) ? AF_INET : AF_INET6; + tree->flags = flags; + isis_rlfa_list_init(tree); + tree->lfa.remote.pc_spftrees = list_new(); + tree->lfa.remote.pc_spftrees->del = (void (*)(void *))isis_spftree_del; + if (tree->type == SPF_TYPE_RLFA || 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) +{ + hash_clean(spftree->prefix_sids, NULL); + hash_free(spftree->prefix_sids); + isis_zebra_rlfa_unregister_all(spftree); + isis_rlfa_list_clear(spftree); + list_delete(&spftree->lfa.remote.pc_spftrees); + if (spftree->type == SPF_TYPE_RLFA + || 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); + return; +} + +static void isis_spftree_adj_del(struct isis_spftree *spftree, + struct isis_adjacency *adj) +{ + struct listnode *node; + struct isis_vertex *v; + if (!adj) + return; + assert(!isis_vertex_queue_count(&spftree->tents)); + for (ALL_QUEUE_ELEMENTS_RO(&spftree->paths, node, v)) + isis_vertex_adj_del(v, adj); + return; +} + +void spftree_area_init(struct isis_area *area) +{ + for (int tree = SPFTREE_IPV4; tree < SPFTREE_COUNT; tree++) { + for (int level = ISIS_LEVEL1; level <= ISIS_LEVEL2; level++) { + if (!(area->is_type & level)) + continue; + if (area->spftree[tree][level - 1]) + continue; + + area->spftree[tree][level - 1] = + isis_spftree_new(area, &area->lspdb[level - 1], + area->isis->sysid, level, tree, + SPF_TYPE_FORWARD, 0); + } + } +} + +void spftree_area_del(struct isis_area *area) +{ + for (int tree = SPFTREE_IPV4; tree < SPFTREE_COUNT; tree++) { + for (int level = ISIS_LEVEL1; level <= ISIS_LEVEL2; level++) { + if (!(area->is_type & level)) + continue; + if (!area->spftree[tree][level - 1]) + continue; + + isis_spftree_del(area->spftree[tree][level - 1]); + } + } +} + +static int spf_adj_state_change(struct isis_adjacency *adj) +{ + struct isis_area *area = adj->circuit->area; + + if (adj->adj_state == ISIS_ADJ_UP) + return 0; + + /* Remove adjacency from all SPF trees. */ + for (int tree = SPFTREE_IPV4; tree < SPFTREE_COUNT; tree++) { + for (int level = ISIS_LEVEL1; level <= ISIS_LEVEL2; level++) { + if (!(area->is_type & level)) + continue; + if (!area->spftree[tree][level - 1]) + continue; + isis_spftree_adj_del(area->spftree[tree][level - 1], + adj); + } + } + + if (fabricd_spftree(area) != NULL) + isis_spftree_adj_del(fabricd_spftree(area), adj); + + return 0; +} + +/* + * Find the system LSP: returns the LSP in our LSP database + * associated with the given system ID. + */ +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]; + + memcpy(lspid, sysid, ISIS_SYS_ID_LEN); + LSP_PSEUDO_ID(lspid) = 0; + LSP_FRAGMENT(lspid) = 0; + lsp = lsp_search(lspdb, lspid); + if (lsp && lsp->hdr.rem_lifetime != 0) + return lsp; + return NULL; +} + +/* + * Add this IS to the root of SPT + */ +static struct isis_vertex *isis_spf_add_root(struct isis_spftree *spftree) +{ + struct isis_vertex *vertex; +#ifdef EXTREME_DEBUG + char buff[VID2STR_BUFFER]; +#endif /* EXTREME_DEBUG */ + + vertex = isis_vertex_new(spftree, spftree->sysid, + spftree->area->oldmetric + ? VTYPE_NONPSEUDO_IS + : VTYPE_NONPSEUDO_TE_IS); + isis_vertex_queue_append(&spftree->paths, vertex); + +#ifdef EXTREME_DEBUG + if (IS_DEBUG_SPF_EVENTS) + zlog_debug( + "ISIS-SPF: added this IS %s %s depth %d dist %d to PATHS", + vtype2string(vertex->type), + vid2string(vertex, buff, sizeof(buff)), vertex->depth, + vertex->d_N); +#endif /* EXTREME_DEBUG */ + + return vertex; +} + +static void vertex_add_parent_firsthop(struct hash_bucket *bucket, void *arg) +{ + struct isis_vertex *vertex = arg; + struct isis_vertex *hop = bucket->data; + + (void)hash_get(vertex->firsthops, hop, hash_alloc_intern); +} + +static void vertex_update_firsthops(struct isis_vertex *vertex, + struct isis_vertex *parent) +{ + if (vertex->d_N <= 2) + (void)hash_get(vertex->firsthops, vertex, hash_alloc_intern); + + if (vertex->d_N < 2 || !parent) + return; + + hash_iterate(parent->firsthops, vertex_add_parent_firsthop, vertex); +} + +/* + * Add a vertex to TENT sorted by cost and by vertextype on tie break situation + */ +static struct isis_vertex * +isis_spf_add2tent(struct isis_spftree *spftree, enum vertextype vtype, void *id, + uint32_t cost, int depth, struct isis_spf_adj *sadj, + struct isis_prefix_sid *psid, struct isis_vertex *parent) +{ + struct isis_vertex *vertex; + struct listnode *node; + bool last_hop; + char buff[VID2STR_BUFFER]; + + vertex = isis_find_vertex(&spftree->paths, id, vtype); + if (vertex != NULL) { + zlog_err( + "%s: vertex %s of type %s already in PATH; check for sysId collisions with established neighbors", + __func__, vid2string(vertex, buff, sizeof(buff)), + vtype2string(vertex->type)); + return NULL; + } + vertex = isis_find_vertex(&spftree->tents, id, vtype); + if (vertex != NULL) { + zlog_err( + "%s: vertex %s of type %s already in TENT; check for sysId collisions with established neighbors", + __func__, vid2string(vertex, buff, sizeof(buff)), + vtype2string(vertex->type)); + return NULL; + } + + vertex = isis_vertex_new(spftree, id, vtype); + vertex->d_N = cost; + vertex->depth = depth; + if (VTYPE_IP(vtype) && spftree->area->srdb.enabled && psid) { + struct isis_area *area = spftree->area; + struct isis_vertex *vertex_psid; + + /* + * Check if the Prefix-SID is already in use by another prefix. + */ + vertex_psid = isis_spf_prefix_sid_lookup(spftree, psid); + if (vertex_psid + && !prefix_same(&vertex_psid->N.ip.p.dest, + &vertex->N.ip.p.dest)) { + flog_warn( + EC_ISIS_SID_COLLISION, + "ISIS-Sr (%s): collision detected, prefixes %pFX and %pFX share the same SID %s (%u)", + area->area_tag, &vertex->N.ip.p.dest, + &vertex_psid->N.ip.p.dest, + CHECK_FLAG(psid->flags, ISIS_PREFIX_SID_VALUE) + ? "label" + : "index", + psid->value); + psid = NULL; + } else { + bool local; + + local = (vertex->depth == 1); + vertex->N.ip.sr.sid = *psid; + vertex->N.ip.sr.label = + sr_prefix_in_label(area, psid, local); + if (vertex->N.ip.sr.label != MPLS_INVALID_LABEL) + vertex->N.ip.sr.present = true; + + (void)hash_get(spftree->prefix_sids, vertex, + hash_alloc_intern); + } + } + + if (parent) { + listnode_add(vertex->parents, parent); + } + + if (CHECK_FLAG(spftree->flags, F_SPFTREE_HOPCOUNT_METRIC)) + vertex_update_firsthops(vertex, parent); + + last_hop = (vertex->depth == 2); + if (parent && parent->Adj_N && listcount(parent->Adj_N) > 0) { + struct isis_vertex_adj *parent_vadj; + + for (ALL_LIST_ELEMENTS_RO(parent->Adj_N, node, parent_vadj)) + isis_vertex_adj_add(spftree, vertex, vertex->Adj_N, + parent_vadj->sadj, psid, last_hop); + } else if (sadj) { + isis_vertex_adj_add(spftree, vertex, vertex->Adj_N, sadj, psid, + last_hop); + } + +#ifdef EXTREME_DEBUG + if (IS_DEBUG_SPF_EVENTS) + zlog_debug( + "ISIS-SPF: add to TENT %s %s %s depth %d dist %d adjcount %d", + print_sys_hostname(vertex->N.id), + vtype2string(vertex->type), + vid2string(vertex, buff, sizeof(buff)), vertex->depth, + vertex->d_N, listcount(vertex->Adj_N)); +#endif /* EXTREME_DEBUG */ + + isis_vertex_queue_insert(&spftree->tents, vertex); + return vertex; +} + +static void isis_spf_add_local(struct isis_spftree *spftree, + enum vertextype vtype, void *id, + struct isis_spf_adj *sadj, uint32_t cost, + struct isis_prefix_sid *psid, + struct isis_vertex *parent) +{ + struct isis_vertex *vertex; + + vertex = isis_find_vertex(&spftree->tents, id, vtype); + + if (vertex) { + /* C.2.5 c) */ + if (vertex->d_N == cost) { + if (sadj) { + bool last_hop = (vertex->depth == 2); + + isis_vertex_adj_add(spftree, vertex, + vertex->Adj_N, sadj, psid, + last_hop); + } + /* d) */ + if (!CHECK_FLAG(spftree->flags, + F_SPFTREE_NO_ADJACENCIES) + && listcount(vertex->Adj_N) > ISIS_MAX_PATH_SPLITS) + remove_excess_adjs(vertex->Adj_N); + if (parent && (listnode_lookup(vertex->parents, parent) + == NULL)) + listnode_add(vertex->parents, parent); + return; + } else if (vertex->d_N < cost) { + /* e) do nothing */ + return; + } else { /* vertex->d_N > cost */ + /* f) */ + isis_vertex_queue_delete(&spftree->tents, vertex); + isis_vertex_del(vertex); + } + } + + isis_spf_add2tent(spftree, vtype, id, cost, 1, sadj, psid, parent); + return; +} + +static void process_N(struct isis_spftree *spftree, enum vertextype vtype, + void *id, uint32_t dist, uint16_t depth, + struct isis_prefix_sid *psid, struct isis_vertex *parent) +{ + struct isis_vertex *vertex; +#ifdef EXTREME_DEBUG + char buff[VID2STR_BUFFER]; +#endif + + assert(spftree && parent); + + if (CHECK_FLAG(spftree->flags, F_SPFTREE_HOPCOUNT_METRIC) + && !VTYPE_IS(vtype)) + return; + + struct prefix_pair p; + if (vtype >= VTYPE_IPREACH_INTERNAL) { + memcpy(&p, id, sizeof(p)); + apply_mask(&p.dest); + apply_mask(&p.src); + id = &p; + } + + /* RFC3787 section 5.1 */ + if (spftree->area->newmetric == 1) { + if (dist > MAX_WIDE_PATH_METRIC) + return; + } + /* C.2.6 b) */ + else if (spftree->area->oldmetric == 1) { + if (dist > MAX_NARROW_PATH_METRIC) + return; + } + + /* c) */ + vertex = isis_find_vertex(&spftree->paths, id, vtype); + if (vertex) { +#ifdef EXTREME_DEBUG + if (IS_DEBUG_SPF_EVENTS) + zlog_debug( + "ISIS-SPF: process_N %s %s %s dist %d already found from PATH", + print_sys_hostname(vertex->N.id), + vtype2string(vtype), + vid2string(vertex, buff, sizeof(buff)), dist); +#endif /* EXTREME_DEBUG */ + assert(dist >= vertex->d_N); + return; + } + + vertex = isis_find_vertex(&spftree->tents, id, vtype); + /* d) */ + if (vertex) { +/* 1) */ +#ifdef EXTREME_DEBUG + if (IS_DEBUG_SPF_EVENTS) + zlog_debug( + "ISIS-SPF: process_N %s %s %s dist %d parent %s adjcount %d", + print_sys_hostname(vertex->N.id), + vtype2string(vtype), + vid2string(vertex, buff, sizeof(buff)), dist, + (parent ? print_sys_hostname(parent->N.id) + : "null"), + (parent ? listcount(parent->Adj_N) : 0)); +#endif /* EXTREME_DEBUG */ + if (vertex->d_N == dist) { + struct listnode *node; + struct isis_vertex_adj *parent_vadj; + for (ALL_LIST_ELEMENTS_RO(parent->Adj_N, node, + parent_vadj)) + if (!isis_vertex_adj_exists( + spftree, vertex, + parent_vadj->sadj)) { + bool last_hop = (vertex->depth == 2); + + isis_vertex_adj_add(spftree, vertex, + vertex->Adj_N, + parent_vadj->sadj, + psid, last_hop); + } + if (CHECK_FLAG(spftree->flags, + F_SPFTREE_HOPCOUNT_METRIC)) + vertex_update_firsthops(vertex, parent); + /* 2) */ + if (!CHECK_FLAG(spftree->flags, + F_SPFTREE_NO_ADJACENCIES) + && listcount(vertex->Adj_N) > ISIS_MAX_PATH_SPLITS) + remove_excess_adjs(vertex->Adj_N); + if (listnode_lookup(vertex->parents, parent) == NULL) + listnode_add(vertex->parents, parent); + return; + } else if (vertex->d_N < dist) { + return; + /* 4) */ + } else { + isis_vertex_queue_delete(&spftree->tents, vertex); + isis_vertex_del(vertex); + } + } + +#ifdef EXTREME_DEBUG + if (IS_DEBUG_SPF_EVENTS) + zlog_debug( + "ISIS-SPF: process_N add2tent %s %s dist %d parent %s", + print_sys_hostname(id), vtype2string(vtype), dist, + (parent ? print_sys_hostname(parent->N.id) : "null")); +#endif /* EXTREME_DEBUG */ + + isis_spf_add2tent(spftree, vtype, id, dist, depth, NULL, psid, parent); + return; +} + +/* + * C.2.6 Step 1 + */ +static int isis_spf_process_lsp(struct isis_spftree *spftree, + struct isis_lsp *lsp, uint32_t cost, + uint16_t depth, uint8_t *root_sysid, + struct isis_vertex *parent) +{ + bool pseudo_lsp = LSP_PSEUDO_ID(lsp->hdr.lsp_id); + struct listnode *fragnode = NULL; + uint32_t dist; + enum vertextype vtype; + static const uint8_t null_sysid[ISIS_SYS_ID_LEN]; + struct isis_mt_router_info *mt_router_info = NULL; + struct prefix_pair ip_info; + bool has_valid_psid; + + if (isis_lfa_excise_node_check(spftree, lsp->hdr.lsp_id)) { + if (IS_DEBUG_LFA) + zlog_debug("ISIS-LFA: excising node %s", + print_sys_hostname(lsp->hdr.lsp_id)); + return ISIS_OK; + } + + if (!lsp->tlvs) + return ISIS_OK; + + if (spftree->mtid != ISIS_MT_IPV4_UNICAST) + mt_router_info = isis_tlvs_lookup_mt_router_info(lsp->tlvs, + spftree->mtid); + + if (!pseudo_lsp && (spftree->mtid == ISIS_MT_IPV4_UNICAST + && !speaks(lsp->tlvs->protocols_supported.protocols, + lsp->tlvs->protocols_supported.count, + spftree->family)) + && !mt_router_info) + return ISIS_OK; + + /* RFC3787 section 4 SHOULD ignore overload bit in pseudo LSPs */ + bool no_overload = (pseudo_lsp + || (spftree->mtid == ISIS_MT_IPV4_UNICAST + && !ISIS_MASK_LSP_OL_BIT(lsp->hdr.lsp_bits)) + || (mt_router_info && !mt_router_info->overload)); + +lspfragloop: + if (lsp->hdr.seqno == 0) { + zlog_warn("%s: lsp with 0 seq_num - ignore", __func__); + return ISIS_WARNING; + } + +#ifdef EXTREME_DEBUG + if (IS_DEBUG_SPF_EVENTS) + zlog_debug("ISIS-SPF: process_lsp %s", + print_sys_hostname(lsp->hdr.lsp_id)); +#endif /* EXTREME_DEBUG */ + + if (no_overload) { + if ((pseudo_lsp || spftree->mtid == ISIS_MT_IPV4_UNICAST) + && spftree->area->oldmetric) { + struct isis_oldstyle_reach *r; + for (r = (struct isis_oldstyle_reach *) + lsp->tlvs->oldstyle_reach.head; + r; r = r->next) { + if (fabricd) + continue; + + /* C.2.6 a) */ + /* Two way connectivity */ + if (!LSP_PSEUDO_ID(r->id) + && !memcmp(r->id, root_sysid, + ISIS_SYS_ID_LEN)) + continue; + if (!pseudo_lsp + && !memcmp(r->id, null_sysid, + ISIS_SYS_ID_LEN)) + continue; + dist = cost + r->metric; + process_N(spftree, + LSP_PSEUDO_ID(r->id) + ? VTYPE_PSEUDO_IS + : VTYPE_NONPSEUDO_IS, + (void *)r->id, dist, depth + 1, NULL, + parent); + } + } + + if (spftree->area->newmetric) { + struct isis_item_list *te_neighs = NULL; + if (pseudo_lsp || spftree->mtid == ISIS_MT_IPV4_UNICAST) + te_neighs = &lsp->tlvs->extended_reach; + else + te_neighs = isis_lookup_mt_items( + &lsp->tlvs->mt_reach, spftree->mtid); + + struct isis_extended_reach *er; + for (er = te_neighs ? (struct isis_extended_reach *) + te_neighs->head + : NULL; + er; er = er->next) { + /* C.2.6 a) */ + /* Two way connectivity */ + if (!LSP_PSEUDO_ID(er->id) + && !memcmp(er->id, root_sysid, + ISIS_SYS_ID_LEN)) + continue; + if (!pseudo_lsp + && !memcmp(er->id, null_sysid, + ISIS_SYS_ID_LEN)) + continue; + dist = cost + + (CHECK_FLAG(spftree->flags, + F_SPFTREE_HOPCOUNT_METRIC) + ? 1 + : er->metric); + process_N(spftree, + LSP_PSEUDO_ID(er->id) + ? VTYPE_PSEUDO_TE_IS + : VTYPE_NONPSEUDO_TE_IS, + (void *)er->id, dist, depth + 1, NULL, + parent); + } + } + } + + if (!fabricd && !pseudo_lsp && spftree->family == AF_INET + && spftree->mtid == ISIS_MT_IPV4_UNICAST + && spftree->area->oldmetric) { + struct isis_item_list *reachs[] = { + &lsp->tlvs->oldstyle_ip_reach, + &lsp->tlvs->oldstyle_ip_reach_ext}; + + for (unsigned int i = 0; i < array_size(reachs); i++) { + vtype = i ? VTYPE_IPREACH_EXTERNAL + : VTYPE_IPREACH_INTERNAL; + + memset(&ip_info, 0, sizeof(ip_info)); + ip_info.dest.family = AF_INET; + + struct isis_oldstyle_ip_reach *r; + for (r = (struct isis_oldstyle_ip_reach *)reachs[i] + ->head; + r; r = r->next) { + dist = cost + r->metric; + ip_info.dest.u.prefix4 = r->prefix.prefix; + ip_info.dest.prefixlen = r->prefix.prefixlen; + process_N(spftree, vtype, &ip_info, + dist, depth + 1, NULL, parent); + } + } + } + + /* we can skip all the rest if we're using metric style narrow */ + if (!spftree->area->newmetric) + goto end; + + if (!pseudo_lsp && spftree->family == AF_INET) { + struct isis_item_list *ipv4_reachs; + if (spftree->mtid == ISIS_MT_IPV4_UNICAST) + ipv4_reachs = &lsp->tlvs->extended_ip_reach; + else + ipv4_reachs = isis_lookup_mt_items( + &lsp->tlvs->mt_ip_reach, spftree->mtid); + + memset(&ip_info, 0, sizeof(ip_info)); + ip_info.dest.family = AF_INET; + + struct isis_extended_ip_reach *r; + for (r = ipv4_reachs + ? (struct isis_extended_ip_reach *) + ipv4_reachs->head + : NULL; + r; r = r->next) { + dist = cost + r->metric; + ip_info.dest.u.prefix4 = r->prefix.prefix; + ip_info.dest.prefixlen = r->prefix.prefixlen; + + /* Parse list of Prefix-SID subTLVs if SR is enabled */ + has_valid_psid = false; + if (spftree->area->srdb.enabled && r->subtlvs) { + for (struct isis_item *i = + r->subtlvs->prefix_sids.head; + i; i = i->next) { + struct isis_prefix_sid *psid = + (struct isis_prefix_sid *)i; + + if (psid->algorithm != SR_ALGORITHM_SPF) + continue; + + has_valid_psid = true; + process_N(spftree, VTYPE_IPREACH_TE, + &ip_info, dist, depth + 1, + psid, parent); + /* + * Stop the Prefix-SID iteration since + * we only support the SPF algorithm for + * now. + */ + break; + } + } + if (!has_valid_psid) + process_N(spftree, VTYPE_IPREACH_TE, &ip_info, + dist, depth + 1, NULL, parent); + } + } + + if (!pseudo_lsp && spftree->family == AF_INET6) { + struct isis_item_list *ipv6_reachs; + if (spftree->mtid == ISIS_MT_IPV4_UNICAST) + ipv6_reachs = &lsp->tlvs->ipv6_reach; + else + ipv6_reachs = isis_lookup_mt_items( + &lsp->tlvs->mt_ipv6_reach, spftree->mtid); + + struct isis_ipv6_reach *r; + for (r = ipv6_reachs + ? (struct isis_ipv6_reach *)ipv6_reachs->head + : NULL; + r; r = r->next) { + dist = cost + r->metric; + vtype = r->external ? VTYPE_IP6REACH_EXTERNAL + : VTYPE_IP6REACH_INTERNAL; + memset(&ip_info, 0, sizeof(ip_info)); + ip_info.dest.family = AF_INET6; + ip_info.dest.u.prefix6 = r->prefix.prefix; + ip_info.dest.prefixlen = r->prefix.prefixlen; + + if (spftree->area->srdb.enabled && r->subtlvs && + r->subtlvs->source_prefix && + r->subtlvs->source_prefix->prefixlen) { + if (spftree->tree_id != SPFTREE_DSTSRC) { + char buff[VID2STR_BUFFER]; + zlog_warn("Ignoring dest-src route %s in non dest-src topology", + srcdest2str( + &ip_info.dest, + r->subtlvs->source_prefix, + buff, sizeof(buff) + ) + ); + continue; + } + ip_info.src = *r->subtlvs->source_prefix; + } + + /* Parse list of Prefix-SID subTLVs */ + has_valid_psid = false; + if (r->subtlvs) { + for (struct isis_item *i = + r->subtlvs->prefix_sids.head; + i; i = i->next) { + struct isis_prefix_sid *psid = + (struct isis_prefix_sid *)i; + + if (psid->algorithm != SR_ALGORITHM_SPF) + continue; + + has_valid_psid = true; + process_N(spftree, vtype, &ip_info, + dist, depth + 1, psid, + parent); + /* + * Stop the Prefix-SID iteration since + * we only support the SPF algorithm for + * now. + */ + break; + } + } + if (!has_valid_psid) + process_N(spftree, vtype, &ip_info, dist, + depth + 1, NULL, parent); + } + } + +end: + + /* if attach bit set in LSP, attached-bit receive ignore is + * not configured, we are a level-1 area and we have no other + * level-2 | level1-2 areas then add a default route toward + * this neighbor + */ + if ((lsp->hdr.lsp_bits & LSPBIT_ATT) == LSPBIT_ATT + && !spftree->area->attached_bit_rcv_ignore + && (spftree->area->is_type & IS_LEVEL_1) + && !isis_level2_adj_up(spftree->area)) { + struct prefix_pair ip_info = { {0} }; + if (IS_DEBUG_RTE_EVENTS) + zlog_debug("ISIS-Spf (%s): add default %s route", + rawlspid_print(lsp->hdr.lsp_id), + spftree->family == AF_INET ? "ipv4" + : "ipv6"); + + if (spftree->family == AF_INET) { + ip_info.dest.family = AF_INET; + vtype = VTYPE_IPREACH_INTERNAL; + } else { + ip_info.dest.family = AF_INET6; + vtype = VTYPE_IP6REACH_INTERNAL; + } + process_N(spftree, vtype, &ip_info, cost, depth + 1, NULL, + parent); + } + + if (fragnode == NULL) + fragnode = listhead(lsp->lspu.frags); + else + fragnode = listnextnode(fragnode); + + if (fragnode) { + lsp = listgetdata(fragnode); + goto lspfragloop; + } + + return ISIS_OK; +} + +static struct isis_adjacency *adj_find(struct list *adj_list, const uint8_t *id, + int level, uint16_t mtid, int family) +{ + struct isis_adjacency *adj; + struct listnode *node; + + for (ALL_LIST_ELEMENTS_RO(adj_list, node, adj)) { + if (!(adj->level & level)) + continue; + if (memcmp(adj->sysid, id, ISIS_SYS_ID_LEN) != 0) + continue; + if (adj->adj_state != ISIS_ADJ_UP) + continue; + if (!adj_has_mt(adj, mtid)) + continue; + if (mtid == ISIS_MT_IPV4_UNICAST + && !speaks(adj->nlpids.nlpids, adj->nlpids.count, family)) + continue; + return adj; + } + + return NULL; +} + +struct spf_preload_tent_ip_reach_args { + struct isis_spftree *spftree; + struct isis_vertex *parent; +}; + +static int isis_spf_preload_tent_ip_reach_cb(const struct prefix *prefix, + uint32_t metric, bool external, + struct isis_subtlvs *subtlvs, + void *arg) +{ + struct spf_preload_tent_ip_reach_args *args = arg; + struct isis_spftree *spftree = args->spftree; + struct isis_vertex *parent = args->parent; + struct prefix_pair ip_info; + enum vertextype vtype; + bool has_valid_psid = false; + + if (external) + return LSP_ITER_CONTINUE; + + assert(spftree->family == prefix->family); + memset(&ip_info, 0, sizeof(ip_info)); + prefix_copy(&ip_info.dest, prefix); + apply_mask(&ip_info.dest); + + if (prefix->family == AF_INET) + vtype = VTYPE_IPREACH_INTERNAL; + else + vtype = VTYPE_IP6REACH_INTERNAL; + + /* Parse list of Prefix-SID subTLVs if SR is enabled */ + if (spftree->area->srdb.enabled && subtlvs) { + for (struct isis_item *i = subtlvs->prefix_sids.head; i; + i = i->next) { + struct isis_prefix_sid *psid = + (struct isis_prefix_sid *)i; + + if (psid->algorithm != SR_ALGORITHM_SPF) + continue; + + has_valid_psid = true; + isis_spf_add_local(spftree, vtype, &ip_info, NULL, 0, + psid, parent); + + /* + * Stop the Prefix-SID iteration since we only support + * the SPF algorithm for now. + */ + break; + } + } + if (!has_valid_psid) + isis_spf_add_local(spftree, vtype, &ip_info, NULL, 0, NULL, + parent); + + return LSP_ITER_CONTINUE; +} + +static void isis_spf_preload_tent(struct isis_spftree *spftree, + uint8_t *root_sysid, + struct isis_lsp *root_lsp, + struct isis_vertex *parent) +{ + struct spf_preload_tent_ip_reach_args ip_reach_args; + struct isis_spf_adj *sadj; + struct listnode *node; + + if (!CHECK_FLAG(spftree->flags, F_SPFTREE_HOPCOUNT_METRIC)) { + ip_reach_args.spftree = spftree; + ip_reach_args.parent = parent; + isis_lsp_iterate_ip_reach( + root_lsp, spftree->family, spftree->mtid, + isis_spf_preload_tent_ip_reach_cb, &ip_reach_args); + } + + /* 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_LFA) + 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; + if (!LSP_PSEUDO_ID(sadj->id)) { + isis_spf_add_local(spftree, + CHECK_FLAG(sadj->flags, + F_ISIS_SPF_ADJ_OLDMETRIC) + ? VTYPE_NONPSEUDO_IS + : VTYPE_NONPSEUDO_TE_IS, + sadj->id, sadj, metric, NULL, + parent); + } else if (sadj->lsp) { + isis_spf_process_lsp(spftree, sadj->lsp, metric, 0, + spftree->sysid, parent); + } + } +} + +struct spf_adj_find_reverse_metric_args { + const uint8_t *id_self; + uint32_t reverse_metric; +}; + +static int spf_adj_find_reverse_metric_cb(const uint8_t *id, uint32_t metric, + bool oldmetric, + struct isis_ext_subtlvs *subtlvs, + void *arg) +{ + struct spf_adj_find_reverse_metric_args *args = arg; + + if (memcmp(id, args->id_self, ISIS_SYS_ID_LEN)) + return LSP_ITER_CONTINUE; + + args->reverse_metric = metric; + + return LSP_ITER_STOP; +} + +/* + * Change all SPF adjacencies to use the link cost in the direction from the + * next hop back towards root in place of the link cost in the direction away + * from root towards the next hop. + */ +static void spf_adj_get_reverse_metrics(struct isis_spftree *spftree) +{ + struct isis_spf_adj *sadj; + struct listnode *node, *nnode; + + for (ALL_LIST_ELEMENTS(spftree->sadj_list, node, nnode, sadj)) { + uint8_t lspid[ISIS_SYS_ID_LEN + 2]; + struct isis_lsp *lsp_adj; + const uint8_t *id_self; + struct spf_adj_find_reverse_metric_args args; + + /* Skip pseudonodes. */ + if (LSP_PSEUDO_ID(sadj->id)) + continue; + + /* Find LSP of the corresponding adjacency. */ + memcpy(lspid, sadj->id, ISIS_SYS_ID_LEN); + LSP_PSEUDO_ID(lspid) = 0; + LSP_FRAGMENT(lspid) = 0; + lsp_adj = lsp_search(spftree->lspdb, lspid); + if (lsp_adj == NULL || lsp_adj->hdr.rem_lifetime == 0) { + /* Delete one-way adjacency. */ + listnode_delete(spftree->sadj_list, sadj); + isis_spf_adj_free(sadj); + continue; + } + + /* Find root node in the LSP of the adjacent router. */ + if (CHECK_FLAG(sadj->flags, F_ISIS_SPF_ADJ_BROADCAST)) + id_self = sadj->lan.desig_is_id; + else + id_self = spftree->sysid; + args.id_self = id_self; + args.reverse_metric = UINT32_MAX; + isis_lsp_iterate_is_reach(lsp_adj, spftree->mtid, + spf_adj_find_reverse_metric_cb, + &args); + if (args.reverse_metric == UINT32_MAX) { + /* Delete one-way adjacency. */ + listnode_delete(spftree->sadj_list, sadj); + isis_spf_adj_free(sadj); + continue; + } + sadj->metric = args.reverse_metric; + } +} + +static void spf_adj_list_parse_tlv(struct isis_spftree *spftree, + struct list *adj_list, const uint8_t *id, + const uint8_t *desig_is_id, + uint32_t pseudo_metric, uint32_t metric, + bool oldmetric, + struct isis_ext_subtlvs *subtlvs) +{ + struct isis_spf_adj *sadj; + uint8_t lspid[ISIS_SYS_ID_LEN + 2]; + struct isis_lsp *lsp; + uint8_t flags = 0; + + /* Skip self in the pseudonode. */ + if (desig_is_id && !memcmp(id, spftree->sysid, ISIS_SYS_ID_LEN)) + return; + + /* Find LSP from the adjacency. */ + memcpy(lspid, id, ISIS_SYS_ID_LEN + 1); + LSP_FRAGMENT(lspid) = 0; + lsp = lsp_search(spftree->lspdb, lspid); + if (lsp == NULL || lsp->hdr.rem_lifetime == 0) { + zlog_warn("ISIS-SPF: No LSP found from root to L%d %s", + spftree->level, rawlspid_print(lspid)); + return; + } + + sadj = XCALLOC(MTYPE_ISIS_SPF_ADJ, sizeof(*sadj)); + memcpy(sadj->id, id, sizeof(sadj->id)); + if (desig_is_id) { + memcpy(sadj->lan.desig_is_id, desig_is_id, + sizeof(sadj->lan.desig_is_id)); + SET_FLAG(flags, F_ISIS_SPF_ADJ_BROADCAST); + sadj->metric = pseudo_metric; + } else + sadj->metric = metric; + if (oldmetric) + SET_FLAG(flags, F_ISIS_SPF_ADJ_OLDMETRIC); + sadj->lsp = lsp; + sadj->subtlvs = subtlvs; + sadj->flags = flags; + + if ((oldmetric && metric == ISIS_NARROW_METRIC_INFINITY) + || (!oldmetric && metric == ISIS_WIDE_METRIC_INFINITY)) + SET_FLAG(flags, F_ISIS_SPF_ADJ_METRIC_INFINITY); + + /* Set real adjacency. */ + if (!CHECK_FLAG(spftree->flags, F_SPFTREE_NO_ADJACENCIES) + && !LSP_PSEUDO_ID(id)) { + struct isis_adjacency *adj; + + adj = adj_find(adj_list, id, spftree->level, spftree->mtid, + spftree->family); + if (!adj) { + XFREE(MTYPE_ISIS_SPF_ADJ, sadj); + return; + } + + listnode_delete(adj_list, adj); + sadj->adj = adj; + } + + /* 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)) + spf_adj_list_parse_lsp(spftree, adj_list, lsp, id, metric); +} + +static void spf_adj_list_parse_lsp(struct isis_spftree *spftree, + struct list *adj_list, struct isis_lsp *lsp, + const uint8_t *pseudo_nodeid, + uint32_t pseudo_metric) +{ + bool pseudo_lsp = LSP_PSEUDO_ID(lsp->hdr.lsp_id); + struct isis_lsp *frag; + struct listnode *node; + struct isis_item *head; + struct isis_item_list *te_neighs; + + if (lsp->hdr.seqno == 0 || lsp->hdr.rem_lifetime == 0) + return; + + /* Parse LSP. */ + if (lsp->tlvs) { + if (pseudo_lsp || spftree->mtid == ISIS_MT_IPV4_UNICAST) { + head = lsp->tlvs->oldstyle_reach.head; + for (struct isis_oldstyle_reach *reach = + (struct isis_oldstyle_reach *)head; + reach; reach = reach->next) { + spf_adj_list_parse_tlv( + spftree, adj_list, reach->id, + pseudo_nodeid, pseudo_metric, + reach->metric, true, NULL); + } + } + + if (pseudo_lsp || spftree->mtid == ISIS_MT_IPV4_UNICAST) + te_neighs = &lsp->tlvs->extended_reach; + else + te_neighs = isis_get_mt_items(&lsp->tlvs->mt_reach, + spftree->mtid); + if (te_neighs) { + head = te_neighs->head; + for (struct isis_extended_reach *reach = + (struct isis_extended_reach *)head; + reach; reach = reach->next) { + spf_adj_list_parse_tlv( + spftree, adj_list, reach->id, + pseudo_nodeid, pseudo_metric, + reach->metric, false, reach->subtlvs); + } + } + } + + if (LSP_FRAGMENT(lsp->hdr.lsp_id)) + return; + + /* Parse LSP fragments. */ + for (ALL_LIST_ELEMENTS_RO(lsp->lspu.frags, node, frag)) { + if (!frag->tlvs) + continue; + + spf_adj_list_parse_lsp(spftree, adj_list, frag, pseudo_nodeid, + pseudo_metric); + } +} + +static void isis_spf_build_adj_list(struct isis_spftree *spftree, + struct isis_lsp *lsp) +{ + struct list *adj_list = NULL; + + if (!CHECK_FLAG(spftree->flags, F_SPFTREE_NO_ADJACENCIES)) + adj_list = list_dup(spftree->area->adjacency_list); + + spf_adj_list_parse_lsp(spftree, adj_list, lsp, NULL, 0); + + if (!CHECK_FLAG(spftree->flags, F_SPFTREE_NO_ADJACENCIES)) + list_delete(&adj_list); + + if (spftree->type == SPF_TYPE_REVERSE) + spf_adj_get_reverse_metrics(spftree); +} + +/* + * The parent(s) for vertex is set when added to TENT list + * now we just put the child pointer(s) in place + */ +static void add_to_paths(struct isis_spftree *spftree, + struct isis_vertex *vertex) +{ +#ifdef EXTREME_DEBUG + char buff[VID2STR_BUFFER]; +#endif /* EXTREME_DEBUG */ + + if (isis_find_vertex(&spftree->paths, &vertex->N, vertex->type)) + return; + isis_vertex_queue_append(&spftree->paths, vertex); + +#ifdef EXTREME_DEBUG + if (IS_DEBUG_SPF_EVENTS) + zlog_debug("ISIS-SPF: added %s %s %s depth %d dist %d to PATHS", + print_sys_hostname(vertex->N.id), + vtype2string(vertex->type), + vid2string(vertex, buff, sizeof(buff)), + vertex->depth, vertex->d_N); +#endif /* EXTREME_DEBUG */ +} + +static void init_spt(struct isis_spftree *spftree, int mtid) +{ + /* Clear data from previous run. */ + hash_clean(spftree->prefix_sids, NULL); + 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); + isis_zebra_rlfa_unregister_all(spftree); + isis_rlfa_list_clear(spftree); + list_delete_all_node(spftree->lfa.remote.pc_spftrees); + memset(&spftree->lfa.protection_counters, 0, + sizeof(spftree->lfa.protection_counters)); + + spftree->mtid = mtid; +} + +static enum spf_prefix_priority +spf_prefix_priority(struct isis_spftree *spftree, struct isis_vertex *vertex) +{ + struct isis_area *area = spftree->area; + struct prefix *prefix = &vertex->N.ip.p.dest; + + for (int priority = SPF_PREFIX_PRIO_CRITICAL; + priority <= SPF_PREFIX_PRIO_MEDIUM; priority++) { + struct spf_prefix_priority_acl *ppa; + enum filter_type ret = FILTER_PERMIT; + + ppa = &area->spf_prefix_priorities[priority]; + switch (spftree->family) { + case AF_INET: + ret = access_list_apply(ppa->list_v4, prefix); + break; + case AF_INET6: + ret = access_list_apply(ppa->list_v6, prefix); + break; + default: + break; + } + + if (ret == FILTER_PERMIT) + return priority; + } + + /* Assign medium priority to loopback prefixes by default. */ + if (is_host_route(prefix)) + return SPF_PREFIX_PRIO_MEDIUM; + + return SPF_PREFIX_PRIO_LOW; +} + +static void spf_path_process(struct isis_spftree *spftree, + struct isis_vertex *vertex) +{ + struct isis_area *area = spftree->area; + int level = spftree->level; + char buff[VID2STR_BUFFER]; + + if (spftree->type == SPF_TYPE_TI_LFA && VTYPE_IS(vertex->type) + && !CHECK_FLAG(spftree->flags, F_SPFTREE_NO_ADJACENCIES)) { + if (listcount(vertex->Adj_N) > 0) { + struct isis_adjacency *adj; + + if (isis_tilfa_check(spftree, vertex) != 0) + return; + + adj = isis_adj_find(area, level, vertex->N.id); + if (adj) + sr_adj_sid_add_single(adj, spftree->family, + true, vertex->Adj_N); + } else if (IS_DEBUG_SPF_EVENTS) + zlog_debug( + "ISIS-SPF: no adjacencies, do not install backup Adj-SID for %s depth %d dist %d", + vid2string(vertex, buff, sizeof(buff)), + vertex->depth, vertex->d_N); + } + + if (VTYPE_IP(vertex->type) + && !CHECK_FLAG(spftree->flags, F_SPFTREE_NO_ROUTES)) { + enum spf_prefix_priority priority; + + priority = spf_prefix_priority(spftree, vertex); + vertex->N.ip.priority = priority; + if (vertex->depth == 1 || listcount(vertex->Adj_N) > 0) { + struct isis_spftree *pre_spftree; + struct route_table *route_table; + bool allow_ecmp; + + switch (spftree->type) { + case SPF_TYPE_RLFA: + case SPF_TYPE_TI_LFA: + if (priority + > area->lfa_priority_limit[level - 1]) { + if (IS_DEBUG_LFA) + zlog_debug( + "ISIS-LFA: skipping %s %s (low prefix priority)", + vtype2string( + vertex->type), + vid2string( + vertex, buff, + sizeof(buff))); + return; + } + break; + default: + break; + } + + switch (spftree->type) { + case SPF_TYPE_RLFA: + isis_rlfa_check(spftree, vertex); + return; + case SPF_TYPE_TI_LFA: + if (isis_tilfa_check(spftree, vertex) != 0) + return; + + pre_spftree = spftree->lfa.old.spftree; + route_table = pre_spftree->route_table_backup; + allow_ecmp = area->lfa_load_sharing[level - 1]; + pre_spftree->lfa.protection_counters + .tilfa[vertex->N.ip.priority] += 1; + break; + default: + route_table = spftree->route_table; + allow_ecmp = true; + + /* + * Update LFA protection counters (ignore local + * routes). + */ + if (vertex->depth > 1) { + spftree->lfa.protection_counters + .total[priority] += 1; + if (listcount(vertex->Adj_N) > 1) + spftree->lfa.protection_counters + .ecmp[priority] += 1; + } + break; + } + + 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, allow_ecmp, 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", + vid2string(vertex, buff, sizeof(buff)), + vertex->depth, vertex->d_N); + } +} + +static void isis_spf_loop(struct isis_spftree *spftree, + uint8_t *root_sysid) +{ + struct isis_vertex *vertex; + struct isis_lsp *lsp; + struct listnode *node; + + while (isis_vertex_queue_count(&spftree->tents)) { + vertex = isis_vertex_queue_pop(&spftree->tents); + +#ifdef EXTREME_DEBUG + if (IS_DEBUG_SPF_EVENTS) + zlog_debug( + "ISIS-SPF: get TENT node %s %s depth %d dist %d to PATHS", + print_sys_hostname(vertex->N.id), + vtype2string(vertex->type), vertex->depth, + vertex->d_N); +#endif /* EXTREME_DEBUG */ + + add_to_paths(spftree, vertex); + if (!VTYPE_IS(vertex->type)) + continue; + + lsp = lsp_for_vertex(spftree, vertex); + if (!lsp) { + zlog_warn("ISIS-SPF: No LSP found for %s", + isis_format_id(vertex->N.id, + sizeof(vertex->N.id))); + continue; + } + + isis_spf_process_lsp(spftree, lsp, vertex->d_N, vertex->depth, + root_sysid, vertex); + } + + /* Generate routes once the SPT is formed. */ + for (ALL_QUEUE_ELEMENTS_RO(&spftree->paths, node, vertex)) { + /* New-style TLVs take precedence over the old-style TLVs. */ + switch (vertex->type) { + case VTYPE_IPREACH_INTERNAL: + case VTYPE_IPREACH_EXTERNAL: + if (isis_find_vertex(&spftree->paths, &vertex->N, + VTYPE_IPREACH_TE)) + continue; + break; + default: + break; + } + + spf_path_process(spftree, vertex); + } +} + +struct isis_spftree *isis_run_hopcount_spf(struct isis_area *area, + uint8_t *sysid, + struct isis_spftree *spftree) +{ + if (!spftree) + spftree = isis_spftree_new(area, &area->lspdb[IS_LEVEL_2 - 1], + sysid, ISIS_LEVEL2, SPFTREE_IPV4, + SPF_TYPE_FORWARD, + F_SPFTREE_HOPCOUNT_METRIC); + + init_spt(spftree, ISIS_MT_IPV4_UNICAST); + if (!memcmp(sysid, area->isis->sysid, ISIS_SYS_ID_LEN)) { + struct isis_lsp *root_lsp; + struct isis_vertex *root_vertex; + + root_lsp = isis_root_system_lsp(spftree->lspdb, spftree->sysid); + if (root_lsp) { + /* + * If we are running locally, initialize with + * information from adjacencies + */ + root_vertex = isis_spf_add_root(spftree); + + isis_spf_preload_tent(spftree, sysid, root_lsp, + root_vertex); + } + } else { + isis_vertex_queue_insert( + &spftree->tents, + isis_vertex_new(spftree, sysid, VTYPE_NONPSEUDO_TE_IS)); + } + + isis_spf_loop(spftree, sysid); + + return spftree; +} + +void isis_run_spf(struct isis_spftree *spftree) +{ + struct isis_lsp *root_lsp; + struct isis_vertex *root_vertex; + struct timeval time_start; + struct timeval time_end; + struct isis_mt_router_info *mt_router_info; + uint16_t mtid = 0; + + /* Get time that can't roll backwards. */ + monotime(&time_start); + + root_lsp = isis_root_system_lsp(spftree->lspdb, spftree->sysid); + if (root_lsp == NULL) { + zlog_err("ISIS-SPF: could not find own l%d LSP!", + spftree->level); + return; + } + + /* Get Multi-Topology ID. */ + switch (spftree->tree_id) { + case SPFTREE_IPV4: + mtid = ISIS_MT_IPV4_UNICAST; + break; + case SPFTREE_IPV6: + mt_router_info = isis_tlvs_lookup_mt_router_info( + root_lsp->tlvs, ISIS_MT_IPV6_UNICAST); + if (mt_router_info) + mtid = ISIS_MT_IPV6_UNICAST; + else + mtid = ISIS_MT_IPV4_UNICAST; + break; + case SPFTREE_DSTSRC: + mtid = ISIS_MT_IPV6_DSTSRC; + break; + case SPFTREE_COUNT: + zlog_err( + "%s should never be called with SPFTREE_COUNT as argument!", + __func__); + exit(1); + } + + /* + * C.2.5 Step 0 + */ + init_spt(spftree, mtid); + /* a) */ + root_vertex = isis_spf_add_root(spftree); + /* b) */ + isis_spf_build_adj_list(spftree, root_lsp); + isis_spf_preload_tent(spftree, spftree->sysid, root_lsp, root_vertex); + + /* + * C.2.7 Step 2 + */ + if (!isis_vertex_queue_count(&spftree->tents) + && (IS_DEBUG_SPF_EVENTS)) { + zlog_warn("ISIS-SPF: TENT is empty SPF-root:%s", + print_sys_hostname(spftree->sysid)); + } + + isis_spf_loop(spftree, spftree->sysid); + spftree->runcount++; + spftree->last_run_timestamp = time(NULL); + spftree->last_run_monotime = monotime(&time_end); + spftree->last_run_duration = + ((time_end.tv_sec - time_start.tv_sec) * 1000000) + + (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 + || area->tilfa_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, + trees[0]->route_table_backup); + } else if (area->is_type == IS_LEVEL_2) { + 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[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 void isis_run_spf_cb(struct thread *thread) +{ + struct isis_spf_run *run = THREAD_ARG(thread); + struct isis_area *area = run->area; + int level = run->level; + int have_run = 0; + + XFREE(MTYPE_ISIS_SPF_RUN, run); + + if (!(area->is_type & level)) { + if (IS_DEBUG_SPF_EVENTS) + zlog_warn("ISIS-SPF (%s) area does not share level", + area->area_tag); + return; + } + + isis_area_delete_backup_adj_sids(area, level); + isis_area_invalidate_routes(area, level); + + if (IS_DEBUG_SPF_EVENTS) + zlog_debug("ISIS-SPF (%s) L%d SPF needed, periodic SPF", + area->area_tag, level); + + if (area->ip_circuits) { + isis_run_spf_with_protection( + area, area->spftree[SPFTREE_IPV4][level - 1]); + have_run = 1; + } + if (area->ipv6_circuits) { + isis_run_spf_with_protection( + area, area->spftree[SPFTREE_IPV6][level - 1]); + have_run = 1; + } + if (area->ipv6_circuits && isis_area_ipv6_dstsrc_enabled(area)) { + isis_run_spf_with_protection( + area, area->spftree[SPFTREE_DSTSRC][level - 1]); + have_run = 1; + } + + if (have_run) + area->spf_run_count[level]++; + + isis_area_verify_routes(area); + + /* walk all circuits and reset any spf specific flags */ + struct listnode *node; + struct isis_circuit *circuit; + for (ALL_LIST_ELEMENTS_RO(area->circuit_list, node, circuit)) + UNSET_FLAG(circuit->flags, ISIS_CIRCUIT_FLAPPED_AFTER_SPF); + + fabricd_run_spf(area); +} + +static struct isis_spf_run *isis_run_spf_arg(struct isis_area *area, int level) +{ + struct isis_spf_run *run = XMALLOC(MTYPE_ISIS_SPF_RUN, sizeof(*run)); + + run->area = area; + run->level = level; + + return run; +} + +void isis_spf_timer_free(void *run) +{ + XFREE(MTYPE_ISIS_SPF_RUN, run); +} + +int _isis_spf_schedule(struct isis_area *area, int level, + const char *func, const char *file, int line) +{ + struct isis_spftree *spftree = area->spftree[SPFTREE_IPV4][level - 1]; + time_t now = monotime(NULL); + int diff = now - spftree->last_run_monotime; + + if (CHECK_FLAG(im->options, F_ISIS_UNIT_TEST)) + return 0; + + assert(diff >= 0); + assert(area->is_type & level); + + if (IS_DEBUG_SPF_EVENTS) { + zlog_debug( + "ISIS-SPF (%s) L%d SPF schedule called, lastrun %d sec ago Caller: %s %s:%d", + area->area_tag, level, diff, func, file, line); + } + + THREAD_OFF(area->t_rlfa_rib_update); + if (area->spf_delay_ietf[level - 1]) { + /* Need to call schedule function also if spf delay is running + * to + * restart holdoff timer - compare + * draft-ietf-rtgwg-backoff-algo-04 */ + long delay = + spf_backoff_schedule(area->spf_delay_ietf[level - 1]); + if (area->spf_timer[level - 1]) + return ISIS_OK; + + thread_add_timer_msec(master, isis_run_spf_cb, + isis_run_spf_arg(area, level), delay, + &area->spf_timer[level - 1]); + return ISIS_OK; + } + + if (area->spf_timer[level - 1]) + return ISIS_OK; + + /* wait configured min_spf_interval before doing the SPF */ + long timer; + if (diff >= area->min_spf_interval[level - 1] + || area->bfd_force_spf_refresh) { + /* + * Last run is more than min interval ago or BFD signalled a + * 'down' message, schedule immediate run + */ + timer = 0; + + if (area->bfd_force_spf_refresh) { + zlog_debug( + "ISIS-SPF (%s) L%d SPF scheduled immediately due to BFD 'down' message", + area->area_tag, level); + area->bfd_force_spf_refresh = false; + } + } else { + timer = area->min_spf_interval[level - 1] - diff; + } + + thread_add_timer(master, isis_run_spf_cb, isis_run_spf_arg(area, level), + timer, &area->spf_timer[level - 1]); + + if (IS_DEBUG_SPF_EVENTS) + zlog_debug("ISIS-SPF (%s) L%d SPF scheduled %ld sec from now", + area->area_tag, level, timer); + + return ISIS_OK; +} + +static void isis_print_paths(struct vty *vty, struct isis_vertex_queue *queue, + uint8_t *root_sysid) +{ + struct listnode *node; + struct isis_vertex *vertex; + char buff[VID2STR_BUFFER]; + + vty_out(vty, + "Vertex Type Metric Next-Hop Interface Parent\n"); + + for (ALL_QUEUE_ELEMENTS_RO(queue, node, vertex)) { + if (VTYPE_IS(vertex->type) + && memcmp(vertex->N.id, root_sysid, ISIS_SYS_ID_LEN) == 0) { + vty_out(vty, "%-20s %-12s %-6s", + print_sys_hostname(root_sysid), "", ""); + vty_out(vty, "%-30s\n", ""); + continue; + } + + int rows = 0; + struct listnode *anode = listhead(vertex->Adj_N); + struct listnode *pnode = listhead(vertex->parents); + struct isis_vertex_adj *vadj; + struct isis_vertex *pvertex; + + vty_out(vty, "%-20s %-12s %-6u ", + vid2string(vertex, buff, sizeof(buff)), + vtype2string(vertex->type), vertex->d_N); + for (unsigned int i = 0; + i < MAX(vertex->Adj_N ? listcount(vertex->Adj_N) : 0, + vertex->parents ? listcount(vertex->parents) : 0); + i++) { + if (anode) { + vadj = listgetdata(anode); + anode = anode->next; + } else { + vadj = NULL; + } + + if (pnode) { + pvertex = listgetdata(pnode); + pnode = pnode->next; + } else { + pvertex = NULL; + } + + if (rows) { + vty_out(vty, "\n"); + vty_out(vty, "%-20s %-12s %-6s ", "", "", ""); + } + + if (vadj) { + struct isis_spf_adj *sadj = vadj->sadj; + + vty_out(vty, "%-20s %-9s ", + print_sys_hostname(sadj->id), + sadj->adj ? sadj->adj->circuit + ->interface->name + : "-"); + } + + if (pvertex) { + if (!vadj) + vty_out(vty, "%-20s %-9s ", "", ""); + + vty_out(vty, "%s(%d)", + vid2string(pvertex, buff, sizeof(buff)), + pvertex->type); + } + + ++rows; + } + vty_out(vty, "\n"); + } +} + +void isis_print_spftree(struct vty *vty, struct isis_spftree *spftree) +{ + const char *tree_id_text = NULL; + + if (!spftree || !isis_vertex_queue_count(&spftree->paths)) + return; + + switch (spftree->tree_id) { + case SPFTREE_IPV4: + tree_id_text = "that speak IP"; + break; + case SPFTREE_IPV6: + tree_id_text = "that speak IPv6"; + break; + case SPFTREE_DSTSRC: + tree_id_text = "that support IPv6 dst-src routing"; + break; + case SPFTREE_COUNT: + assert(!"isis_print_spftree shouldn't be called with SPFTREE_COUNT as type"); + return; + } + + vty_out(vty, "IS-IS paths to level-%d routers %s\n", spftree->level, + tree_id_text); + isis_print_paths(vty, &spftree->paths, spftree->sysid); + vty_out(vty, "\n"); +} + +static void show_isis_topology_common(struct vty *vty, int levels, + struct isis *isis) +{ + struct listnode *node; + struct isis_area *area; + + if (!isis->area_list || isis->area_list->count == 0) + return; + + for (ALL_LIST_ELEMENTS_RO(isis->area_list, node, area)) { + vty_out(vty, "Area %s:\n", + area->area_tag ? area->area_tag : "null"); + + for (int level = ISIS_LEVEL1; level <= ISIS_LEVELS; level++) { + if ((level & levels) == 0) + continue; + + if (area->ip_circuits > 0) { + isis_print_spftree( + vty, + area->spftree[SPFTREE_IPV4][level - 1]); + } + if (area->ipv6_circuits > 0) { + isis_print_spftree( + vty, + area->spftree[SPFTREE_IPV6][level - 1]); + } + if (isis_area_ipv6_dstsrc_enabled(area)) { + isis_print_spftree(vty, + area->spftree[SPFTREE_DSTSRC] + [level - 1]); + } + } + + if (fabricd_spftree(area)) { + vty_out(vty, + "IS-IS paths to level-2 routers with hop-by-hop metric\n"); + isis_print_paths(vty, &fabricd_spftree(area)->paths, isis->sysid); + vty_out(vty, "\n"); + } + + vty_out(vty, "\n"); + } +} + +DEFUN(show_isis_topology, show_isis_topology_cmd, + "show " PROTO_NAME + " [vrf <NAME|all>] topology" +#ifndef FABRICD + " [<level-1|level-2>]" +#endif + , + SHOW_STR PROTO_HELP VRF_CMD_HELP_STR + "All VRFs\n" + "IS-IS paths to Intermediate Systems\n" +#ifndef FABRICD + "Paths to all level-1 routers in the area\n" + "Paths to all level-2 routers in the domain\n" +#endif +) +{ + int levels = ISIS_LEVELS; + struct listnode *node; + struct isis *isis = NULL; + int idx = 0; + const char *vrf_name = VRF_DEFAULT_NAME; + bool all_vrf = false; + int idx_vrf = 0; + + if (argv_find(argv, argc, "topology", &idx)) { + if (argc < idx + 2) + levels = ISIS_LEVEL1 | ISIS_LEVEL2; + else if (strmatch(argv[idx + 1]->arg, "level-1")) + levels = ISIS_LEVEL1; + else + levels = ISIS_LEVEL2; + } + + if (!im) { + vty_out(vty, "IS-IS Routing Process not enabled\n"); + return CMD_SUCCESS; + } + 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, node, isis)) + show_isis_topology_common(vty, levels, isis); + return CMD_SUCCESS; + } + isis = isis_lookup_by_vrfname(vrf_name); + if (isis != NULL) + show_isis_topology_common(vty, levels, isis); + } + + return CMD_SUCCESS; +} + +static void isis_print_route(struct ttable *tt, const struct prefix *prefix, + struct isis_route_info *rinfo, bool prefix_sid, + bool no_adjacencies) +{ + struct isis_nexthop *nexthop; + struct listnode *node; + bool first = true; + char buf_prefix[BUFSIZ]; + + (void)prefix2str(prefix, buf_prefix, sizeof(buf_prefix)); + for (ALL_LIST_ELEMENTS_RO(rinfo->nexthops, node, nexthop)) { + struct interface *ifp; + char buf_iface[BUFSIZ]; + char buf_nhop[BUFSIZ]; + + if (!no_adjacencies) { + inet_ntop(nexthop->family, &nexthop->ip, buf_nhop, + sizeof(buf_nhop)); + ifp = if_lookup_by_index(nexthop->ifindex, VRF_DEFAULT); + if (ifp) + strlcpy(buf_iface, ifp->name, + sizeof(buf_iface)); + else + snprintf(buf_iface, sizeof(buf_iface), + "ifindex %u", nexthop->ifindex); + } else { + strlcpy(buf_nhop, print_sys_hostname(nexthop->sysid), + sizeof(buf_nhop)); + strlcpy(buf_iface, "-", sizeof(buf_iface)); + } + + if (prefix_sid) { + char buf_sid[BUFSIZ] = {}; + char buf_lblop[BUFSIZ] = {}; + + if (nexthop->sr.present) { + snprintf(buf_sid, sizeof(buf_sid), "%u", + nexthop->sr.sid.value); + sr_op2str(buf_lblop, sizeof(buf_lblop), + rinfo->sr.label, nexthop->sr.label); + } else { + strlcpy(buf_sid, "-", sizeof(buf_sid)); + strlcpy(buf_lblop, "-", sizeof(buf_lblop)); + } + + if (first) { + ttable_add_row(tt, "%s|%u|%s|%s|%s|%s", + buf_prefix, rinfo->cost, + buf_iface, buf_nhop, buf_sid, + buf_lblop); + first = false; + } else + ttable_add_row(tt, "||%s|%s|%s|%s", buf_iface, + buf_nhop, buf_sid, buf_lblop); + } else { + char buf_labels[BUFSIZ] = {}; + + 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.present) + label2str(nexthop->sr.label, buf_labels, + sizeof(buf_labels)); + else + strlcpy(buf_labels, "-", sizeof(buf_labels)); + + if (first) { + ttable_add_row(tt, "%s|%u|%s|%s|%s", buf_prefix, + rinfo->cost, buf_iface, buf_nhop, + buf_labels); + first = false; + } else + ttable_add_row(tt, "||%s|%s|%s", buf_iface, + buf_nhop, buf_labels); + } + } + if (list_isempty(rinfo->nexthops)) { + if (prefix_sid) { + char buf_sid[BUFSIZ] = {}; + char buf_lblop[BUFSIZ] = {}; + + if (rinfo->sr.present) { + snprintf(buf_sid, sizeof(buf_sid), "%u", + rinfo->sr.sid.value); + sr_op2str(buf_lblop, sizeof(buf_lblop), + rinfo->sr.label, + MPLS_LABEL_IMPLICIT_NULL); + } else { + strlcpy(buf_sid, "-", sizeof(buf_sid)); + strlcpy(buf_lblop, "-", sizeof(buf_lblop)); + } + + ttable_add_row(tt, "%s|%u|%s|%s|%s|%s", buf_prefix, + rinfo->cost, "-", "-", buf_sid, + buf_lblop); + } else + ttable_add_row(tt, "%s|%u|%s|%s|%s", buf_prefix, + rinfo->cost, "-", "-", "-"); + } +} + +void isis_print_routes(struct vty *vty, struct isis_spftree *spftree, + bool prefix_sid, bool backup) +{ + struct route_table *route_table; + struct ttable *tt; + struct route_node *rn; + bool no_adjacencies = false; + const char *tree_id_text = NULL; + + if (!spftree) + return; + + switch (spftree->tree_id) { + case SPFTREE_IPV4: + tree_id_text = "IPv4"; + break; + case SPFTREE_IPV6: + tree_id_text = "IPv6"; + break; + case SPFTREE_DSTSRC: + tree_id_text = "IPv6 (dst-src routing)"; + break; + case SPFTREE_COUNT: + assert(!"isis_print_routes shouldn't be called with SPFTREE_COUNT as type"); + return; + } + + vty_out(vty, "IS-IS %s %s routing table:\n\n", + circuit_t2string(spftree->level), tree_id_text); + + /* Prepare table. */ + tt = ttable_new(&ttable_styles[TTSTYLE_BLANK]); + if (prefix_sid) + ttable_add_row(tt, "Prefix|Metric|Interface|Nexthop|SID|Label Op."); + else + ttable_add_row(tt, "Prefix|Metric|Interface|Nexthop|Label(s)"); + tt->style.cell.rpad = 2; + tt->style.corner = '+'; + ttable_restyle(tt); + ttable_rowseps(tt, 0, BOTTOM, true, '-'); + + if (CHECK_FLAG(spftree->flags, F_SPFTREE_NO_ADJACENCIES)) + no_adjacencies = true; + + 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; + + rinfo = rn->info; + if (!rinfo) + continue; + + isis_print_route(tt, &rn->p, rinfo, prefix_sid, no_adjacencies); + } + + /* Dump the generated table. */ + if (tt->nrows > 1) { + char *table; + + table = ttable_dump(tt, "\n"); + vty_out(vty, "%s\n", table); + XFREE(MTYPE_TMP, table); + } + ttable_del(tt); +} + +static void show_isis_route_common(struct vty *vty, int levels, + struct isis *isis, bool prefix_sid, + bool backup) +{ + struct listnode *node; + struct isis_area *area; + + if (!isis->area_list || isis->area_list->count == 0) + return; + + for (ALL_LIST_ELEMENTS_RO(isis->area_list, node, area)) { + vty_out(vty, "Area %s:\n", + area->area_tag ? area->area_tag : "null"); + + for (int level = ISIS_LEVEL1; level <= ISIS_LEVELS; level++) { + if ((level & levels) == 0) + continue; + + if (area->ip_circuits > 0) { + isis_print_routes( + vty, + area->spftree[SPFTREE_IPV4][level - 1], + prefix_sid, backup); + } + if (area->ipv6_circuits > 0) { + isis_print_routes( + vty, + area->spftree[SPFTREE_IPV6][level - 1], + prefix_sid, backup); + } + if (isis_area_ipv6_dstsrc_enabled(area)) { + isis_print_routes(vty, + area->spftree[SPFTREE_DSTSRC] + [level - 1], + prefix_sid, backup); + } + } + } +} + +DEFUN(show_isis_route, show_isis_route_cmd, + "show " PROTO_NAME + " [vrf <NAME|all>] route" +#ifndef FABRICD + " [<level-1|level-2>]" +#endif + " [<prefix-sid|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 Prefix-SID information\n" + "Show backup routes\n") +{ + int levels; + struct isis *isis; + struct listnode *node; + const char *vrf_name = VRF_DEFAULT_NAME; + bool all_vrf = false; + bool prefix_sid = false; + bool backup = false; + int idx = 0; + + if (argv_find(argv, argc, "level-1", &idx)) + levels = ISIS_LEVEL1; + else if (argv_find(argv, argc, "level-2", &idx)) + levels = ISIS_LEVEL2; + else + levels = ISIS_LEVEL1 | ISIS_LEVEL2; + + if (!im) { + vty_out(vty, "IS-IS Routing Process not enabled\n"); + return CMD_SUCCESS; + } + ISIS_FIND_VRF_ARGS(argv, argc, idx, vrf_name, all_vrf); + + if (argv_find(argv, argc, "prefix-sid", &idx)) + prefix_sid = true; + 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, + prefix_sid, backup); + return CMD_SUCCESS; + } + isis = isis_lookup_by_vrfname(vrf_name); + if (isis != NULL) + show_isis_route_common(vty, levels, isis, prefix_sid, + backup); + } + + return CMD_SUCCESS; +} + +static void isis_print_frr_summary_line(struct ttable *tt, + const char *protection, + uint32_t counters[SPF_PREFIX_PRIO_MAX]) +{ + uint32_t critical, high, medium, low, total; + + critical = counters[SPF_PREFIX_PRIO_CRITICAL]; + high = counters[SPF_PREFIX_PRIO_HIGH]; + medium = counters[SPF_PREFIX_PRIO_MEDIUM]; + low = counters[SPF_PREFIX_PRIO_LOW]; + total = critical + high + medium + low; + + ttable_add_row(tt, "%s|%u|%u|%u|%u|%u", protection, critical, high, + medium, low, total); +} + +static void +isis_print_frr_summary_line_coverage(struct ttable *tt, const char *protection, + double counters[SPF_PREFIX_PRIO_MAX], + double total) +{ + double critical, high, medium, low; + + critical = counters[SPF_PREFIX_PRIO_CRITICAL] * 100; + high = counters[SPF_PREFIX_PRIO_HIGH] * 100; + medium = counters[SPF_PREFIX_PRIO_MEDIUM] * 100; + low = counters[SPF_PREFIX_PRIO_LOW] * 100; + total *= 100; + + ttable_add_row(tt, "%s|%.2f%%|%.2f%%|%.2f%%|%.2f%%|%.2f%%", protection, + critical, high, medium, low, total); +} + +static void isis_print_frr_summary(struct vty *vty, + struct isis_spftree *spftree) +{ + struct ttable *tt; + char *table; + const char *tree_id_text = NULL; + uint32_t protectd[SPF_PREFIX_PRIO_MAX] = {0}; + uint32_t unprotected[SPF_PREFIX_PRIO_MAX] = {0}; + double coverage[SPF_PREFIX_PRIO_MAX] = {0}; + uint32_t protected_total = 0, grand_total = 0; + double coverage_total; + + if (!spftree) + return; + + switch (spftree->tree_id) { + case SPFTREE_IPV4: + tree_id_text = "IPv4"; + break; + case SPFTREE_IPV6: + tree_id_text = "IPv6"; + break; + case SPFTREE_DSTSRC: + tree_id_text = "IPv6 (dst-src routing)"; + break; + case SPFTREE_COUNT: + assert(!"isis_print_frr_summary shouldn't be called with SPFTREE_COUNT as type"); + return; + } + + vty_out(vty, " IS-IS %s %s Fast ReRoute summary:\n\n", + circuit_t2string(spftree->level), tree_id_text); + + /* Prepare table. */ + tt = ttable_new(&ttable_styles[TTSTYLE_BLANK]); + ttable_add_row( + tt, + "Protection \\ Priority|Critical|High |Medium |Low |Total"); + tt->style.cell.rpad = 2; + tt->style.corner = '+'; + ttable_restyle(tt); + ttable_rowseps(tt, 0, BOTTOM, true, '-'); + + /* Compute unprotected and coverage totals. */ + for (int priority = SPF_PREFIX_PRIO_CRITICAL; + priority < SPF_PREFIX_PRIO_MAX; priority++) { + uint32_t *lfa = spftree->lfa.protection_counters.lfa; + uint32_t *rlfa = spftree->lfa.protection_counters.rlfa; + uint32_t *tilfa = spftree->lfa.protection_counters.tilfa; + uint32_t *ecmp = spftree->lfa.protection_counters.ecmp; + uint32_t *total = spftree->lfa.protection_counters.total; + + protectd[priority] = lfa[priority] + rlfa[priority] + + tilfa[priority] + ecmp[priority]; + /* Safeguard to protect against possible inconsistencies. */ + if (protectd[priority] > total[priority]) + protectd[priority] = total[priority]; + unprotected[priority] = total[priority] - protectd[priority]; + protected_total += protectd[priority]; + grand_total += total[priority]; + + if (!total[priority]) + coverage[priority] = 0; + else + coverage[priority] = + protectd[priority] / (double)total[priority]; + } + + if (!grand_total) + coverage_total = 0; + else + coverage_total = protected_total / (double)grand_total; + + /* Add rows. */ + isis_print_frr_summary_line(tt, "Classic LFA", + spftree->lfa.protection_counters.lfa); + isis_print_frr_summary_line(tt, "Remote LFA", + spftree->lfa.protection_counters.rlfa); + isis_print_frr_summary_line(tt, "Topology Independent LFA", + spftree->lfa.protection_counters.tilfa); + isis_print_frr_summary_line(tt, "ECMP", + spftree->lfa.protection_counters.ecmp); + isis_print_frr_summary_line(tt, "Unprotected", unprotected); + isis_print_frr_summary_line_coverage(tt, "Protection coverage", + coverage, coverage_total); + + /* Dump the generated table. */ + table = ttable_dump(tt, "\n"); + vty_out(vty, "%s\n", table); + XFREE(MTYPE_TMP, table); + ttable_del(tt); +} + +static void show_isis_frr_summary_common(struct vty *vty, int levels, + struct isis *isis) +{ + struct listnode *node; + struct isis_area *area; + + if (!isis->area_list || isis->area_list->count == 0) + return; + + for (ALL_LIST_ELEMENTS_RO(isis->area_list, node, area)) { + vty_out(vty, "Area %s:\n", + area->area_tag ? area->area_tag : "null"); + + for (int level = ISIS_LEVEL1; level <= ISIS_LEVELS; level++) { + if ((level & levels) == 0) + continue; + + if (area->ip_circuits > 0) { + isis_print_frr_summary( + vty, + area->spftree[SPFTREE_IPV4][level - 1]); + } + if (area->ipv6_circuits > 0) { + isis_print_frr_summary( + vty, + area->spftree[SPFTREE_IPV6][level - 1]); + } + if (isis_area_ipv6_dstsrc_enabled(area)) { + isis_print_frr_summary( + vty, area->spftree[SPFTREE_DSTSRC] + [level - 1]); + } + } + } +} + +DEFUN(show_isis_frr_summary, show_isis_frr_summary_cmd, + "show " PROTO_NAME + " [vrf <NAME|all>] fast-reroute summary" +#ifndef FABRICD + " [<level-1|level-2>]" +#endif + , + SHOW_STR PROTO_HELP VRF_FULL_CMD_HELP_STR + "IS-IS FRR information\n" + "FRR summary\n" +#ifndef FABRICD + "level-1 routes\n" + "level-2 routes\n" +#endif +) +{ + int levels; + struct isis *isis; + struct listnode *node; + const char *vrf_name = VRF_DEFAULT_NAME; + bool all_vrf = false; + int idx = 0; + + if (argv_find(argv, argc, "level-1", &idx)) + levels = ISIS_LEVEL1; + else if (argv_find(argv, argc, "level-2", &idx)) + levels = ISIS_LEVEL2; + else + levels = ISIS_LEVEL1 | ISIS_LEVEL2; + + if (!im) { + vty_out(vty, "IS-IS Routing Process not enabled\n"); + return CMD_SUCCESS; + } + ISIS_FIND_VRF_ARGS(argv, argc, idx, vrf_name, all_vrf); + + if (vrf_name) { + if (all_vrf) { + for (ALL_LIST_ELEMENTS_RO(im->isis, node, isis)) + show_isis_frr_summary_common(vty, levels, isis); + return CMD_SUCCESS; + } + isis = isis_lookup_by_vrfname(vrf_name); + if (isis != NULL) + show_isis_frr_summary_common(vty, levels, isis); + } + + return CMD_SUCCESS; +} + +void isis_spf_init(void) +{ + install_element(VIEW_NODE, &show_isis_topology_cmd); + install_element(VIEW_NODE, &show_isis_route_cmd); + install_element(VIEW_NODE, &show_isis_frr_summary_cmd); + + /* Register hook(s). */ + hook_register(isis_adj_state_change_hook, spf_adj_state_change); +} + +void isis_spf_print(struct isis_spftree *spftree, struct vty *vty) +{ + vty_out(vty, " last run elapsed : "); + vty_out_timestr(vty, spftree->last_run_timestamp); + vty_out(vty, "\n"); + + vty_out(vty, " last run duration : %u usec\n", + (uint32_t)spftree->last_run_duration); + + vty_out(vty, " run count : %u\n", spftree->runcount); +} +void isis_spf_print_json(struct isis_spftree *spftree, struct json_object *json) +{ + char uptime[MONOTIME_STRLEN]; + time_t cur; + cur = time(NULL); + cur -= spftree->last_run_timestamp; + frrtime_to_interval(cur, uptime, sizeof(uptime)); + json_object_string_add(json, "last-run-elapsed", uptime); + json_object_int_add(json, "last-run-duration-usec", + spftree->last_run_duration); + json_object_int_add(json, "last-run-count", spftree->runcount); +} |