/* * 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 * * 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 #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 ] topology" #ifndef FABRICD " []" #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 ] route" #ifndef FABRICD " []" #endif " []", 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 ] fast-reroute summary" #ifndef FABRICD " []" #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); }