#include "command.h"
#include "memory.h"
#include "prefix.h"
-#include "hash.h"
#include "if.h"
#include "table.h"
#include "spf_backoff.h"
-#include "jhash.h"
-#include "skiplist.h"
+#include "srcdest_table.h"
#include "isis_constants.h"
#include "isis_common.h"
#include "isis_csm.h"
#include "isis_mt.h"
#include "isis_tlvs.h"
+#include "fabricd.h"
+#include "isis_spf_private.h"
DEFINE_MTYPE_STATIC(ISISD, ISIS_SPF_RUN, "ISIS SPF Run Info");
-enum vertextype {
- VTYPE_PSEUDO_IS = 1,
- VTYPE_PSEUDO_TE_IS,
- VTYPE_NONPSEUDO_IS,
- VTYPE_NONPSEUDO_TE_IS,
- VTYPE_ES,
- VTYPE_IPREACH_INTERNAL,
- VTYPE_IPREACH_EXTERNAL,
- VTYPE_IPREACH_TE,
- VTYPE_IP6REACH_INTERNAL,
- VTYPE_IP6REACH_EXTERNAL
-};
-
-#define VTYPE_IS(t) ((t) >= VTYPE_PSEUDO_IS && (t) <= VTYPE_NONPSEUDO_TE_IS)
-#define VTYPE_ES(t) ((t) == VTYPE_ES)
-#define VTYPE_IP(t) ((t) >= VTYPE_IPREACH_INTERNAL && (t) <= VTYPE_IP6REACH_EXTERNAL)
-
-/*
- * Triple <N, d(N), {Adj(N)}>
- */
-union isis_N {
- uint8_t id[ISIS_SYS_ID_LEN + 1];
- struct prefix prefix;
-};
-struct isis_vertex {
- enum vertextype type;
- union isis_N N;
- uint32_t d_N; /* d(N) Distance from this IS */
- uint16_t depth; /* The depth in the imaginary tree */
- struct list *Adj_N; /* {Adj(N)} next hop or neighbor list */
- struct list *parents; /* list of parents for ECMP */
- uint64_t insert_counter;
-};
-
-/* Vertex Queue and associated functions */
-
-struct isis_vertex_queue {
- union {
- struct skiplist *slist;
- struct list *list;
- } l;
- struct hash *hash;
- uint64_t insert_counter;
-};
-
-static unsigned isis_vertex_queue_hash_key(void *vp)
-{
- struct isis_vertex *vertex = vp;
-
- if (VTYPE_IP(vertex->type))
- return prefix_hash_key(&vertex->N.prefix);
-
- return jhash(vertex->N.id, ISIS_SYS_ID_LEN + 1, 0x55aa5a5a);
-}
-
-static int isis_vertex_queue_hash_cmp(const void *a, const void *b)
-{
- const struct isis_vertex *va = a, *vb = b;
-
- if (va->type != vb->type)
- return 0;
-
- if (VTYPE_IP(va->type))
- return prefix_cmp(&va->N.prefix, &vb->N.prefix) == 0;
-
- return memcmp(va->N.id, vb->N.id, ISIS_SYS_ID_LEN + 1) == 0;
-}
-
-/*
- * Compares vertizes for sorting in the TENT list. Returns true
- * if candidate should be considered before current, false otherwise.
- */
-static int isis_vertex_queue_tent_cmp(void *a, void *b)
-{
- struct isis_vertex *va = a;
- struct isis_vertex *vb = b;
-
- if (va->d_N < vb->d_N)
- return -1;
-
- if (va->d_N > vb->d_N)
- return 1;
-
- if (va->type < vb->type)
- return -1;
-
- if (va->type > vb->type)
- return 1;
-
- if (va->insert_counter < vb->insert_counter)
- return -1;
-
- if (va->insert_counter > vb->insert_counter)
- return 1;
-
- return 0;
-}
-
-static struct skiplist *isis_vertex_queue_skiplist(void)
-{
- return skiplist_new(0, isis_vertex_queue_tent_cmp, NULL);
-}
-
-static void isis_vertex_queue_init(struct isis_vertex_queue *queue,
- const char *name, bool ordered)
-{
- if (ordered) {
- queue->insert_counter = 1;
- queue->l.slist = isis_vertex_queue_skiplist();
- } else {
- queue->insert_counter = 0;
- queue->l.list = list_new();
- }
- queue->hash = hash_create(isis_vertex_queue_hash_key,
- isis_vertex_queue_hash_cmp, name);
-}
-
-static void isis_vertex_del(struct isis_vertex *vertex);
-
-static void isis_vertex_queue_clear(struct isis_vertex_queue *queue)
-{
- hash_clean(queue->hash, NULL);
-
- if (queue->insert_counter) {
- struct isis_vertex *vertex;
- while (0 == skiplist_first(queue->l.slist, NULL,
- (void **)&vertex)) {
- isis_vertex_del(vertex);
- skiplist_delete_first(queue->l.slist);
- }
- queue->insert_counter = 1;
- } else {
- queue->l.list->del = (void (*)(void *))isis_vertex_del;
- list_delete_all_node(queue->l.list);
- queue->l.list->del = NULL;
- }
-}
-
-static void isis_vertex_queue_free(struct isis_vertex_queue *queue)
-{
- isis_vertex_queue_clear(queue);
-
- hash_free(queue->hash);
- queue->hash = NULL;
-
- if (queue->insert_counter) {
- skiplist_free(queue->l.slist);
- queue->l.slist = NULL;
- } else
- list_delete_and_null(&queue->l.list);
-}
-
-static unsigned int isis_vertex_queue_count(struct isis_vertex_queue *queue)
-{
- return hashcount(queue->hash);
-}
-
-static void isis_vertex_queue_append(struct isis_vertex_queue *queue,
- struct isis_vertex *vertex)
-{
- assert(!queue->insert_counter);
-
- listnode_add(queue->l.list, vertex);
-
- struct isis_vertex *inserted;
-
- inserted = hash_get(queue->hash, vertex, hash_alloc_intern);
- assert(inserted == vertex);
-}
-
-static void isis_vertex_queue_insert(struct isis_vertex_queue *queue,
- struct isis_vertex *vertex)
-{
- assert(queue->insert_counter);
- vertex->insert_counter = queue->insert_counter++;
- assert(queue->insert_counter != (uint64_t)-1);
-
- skiplist_insert(queue->l.slist, vertex, vertex);
-
- struct isis_vertex *inserted;
- inserted = hash_get(queue->hash, vertex, hash_alloc_intern);
- assert(inserted == vertex);
-}
-
-static struct isis_vertex *
-isis_vertex_queue_pop(struct isis_vertex_queue *queue)
-{
- assert(queue->insert_counter);
-
- struct isis_vertex *rv;
-
- if (skiplist_first(queue->l.slist, NULL, (void **)&rv))
- return NULL;
-
- skiplist_delete_first(queue->l.slist);
- hash_release(queue->hash, rv);
-
- return rv;
-}
-
-static void isis_vertex_queue_delete(struct isis_vertex_queue *queue,
- struct isis_vertex *vertex)
-{
- assert(queue->insert_counter);
-
- skiplist_delete(queue->l.slist, vertex, vertex);
- hash_release(queue->hash, vertex);
-}
-
-#define ALL_QUEUE_ELEMENTS_RO(queue, node, data) \
- ALL_LIST_ELEMENTS_RO((queue)->l.list, node, data)
-
-
-/* End of vertex queue definitions */
-
-struct isis_spftree {
- struct isis_vertex_queue paths; /* the SPT */
- struct isis_vertex_queue tents; /* TENT */
- struct isis_area *area; /* back pointer to area */
- unsigned int runcount; /* number of runs since uptime */
- time_t last_run_timestamp; /* last run timestamp as wall time for display */
- time_t last_run_monotime; /* last run as monotime for scheduling */
- time_t last_run_duration; /* last run duration in msec */
-
- uint16_t mtid;
- int family;
- int level;
-};
-
-
/*
* supports the given af ?
*/
return NULL; /* Not reached */
}
-static const char *vid2string(struct isis_vertex *vertex, char *buff, int size)
+const char *vid2string(struct isis_vertex *vertex, char *buff, int size)
{
if (VTYPE_IS(vertex->type) || VTYPE_ES(vertex->type)) {
return print_sys_hostname(vertex->N.id);
}
if (VTYPE_IP(vertex->type)) {
- prefix2str((struct prefix *)&vertex->N.prefix, buff, size);
+ srcdest2str(&vertex->N.ip.dest,
+ &vertex->N.ip.src,
+ buff, size);
return buff;
}
return "UNKNOWN";
}
-static void isis_vertex_id_init(struct isis_vertex *vertex, union isis_N *n,
- enum vertextype vtype)
-{
- vertex->type = vtype;
-
- if (VTYPE_IS(vtype) || VTYPE_ES(vtype)) {
- memcpy(vertex->N.id, n->id, ISIS_SYS_ID_LEN + 1);
- } else if (VTYPE_IP(vtype)) {
- memcpy(&vertex->N.prefix, &n->prefix, sizeof(struct prefix));
- } else {
- zlog_err("WTF!");
- }
-}
-
-static struct isis_vertex *isis_vertex_new(union isis_N *n,
+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, n, vtype);
+ isis_vertex_id_init(vertex, id, vtype);
vertex->Adj_N = list_new();
vertex->parents = list_new();
- return vertex;
-}
-
-static void isis_vertex_del(struct isis_vertex *vertex)
-{
- list_delete_and_null(&vertex->Adj_N);
- list_delete_and_null(&vertex->parents);
-
- memset(vertex, 0, sizeof(struct isis_vertex));
- XFREE(MTYPE_ISIS_VERTEX, vertex);
+ if (spftree->hopcount_metric) {
+ vertex->firsthops = hash_create(isis_vertex_queue_hash_key,
+ isis_vertex_queue_hash_cmp,
+ NULL);
+ }
- return;
+ return vertex;
}
static void isis_vertex_adj_del(struct isis_vertex *vertex,
struct isis_spftree *tree;
tree = XCALLOC(MTYPE_ISIS_SPFTREE, sizeof(struct isis_spftree));
- if (tree == NULL) {
- zlog_err("ISIS-Spf: isis_spftree_new Out of memory!");
- return NULL;
- }
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->area = area;
tree->last_run_timestamp = 0;
tree->last_run_monotime = 0;
{
isis_vertex_queue_free(&spftree->tents);
isis_vertex_queue_free(&spftree->paths);
- XFREE(MTYPE_ISIS_SPFTREE, spftree);
+ route_table_finish(spftree->route_table);
+ spftree->route_table = NULL;
+ XFREE(MTYPE_ISIS_SPFTREE, spftree);
return;
}
void spftree_area_init(struct isis_area *area)
{
- if (area->is_type & IS_LEVEL_1) {
- if (area->spftree[0] == NULL)
- area->spftree[0] = isis_spftree_new(area);
- if (area->spftree6[0] == NULL)
- area->spftree6[0] = isis_spftree_new(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;
- if (area->is_type & IS_LEVEL_2) {
- if (area->spftree[1] == NULL)
- area->spftree[1] = isis_spftree_new(area);
- if (area->spftree6[1] == NULL)
- area->spftree6[1] = isis_spftree_new(area);
+ area->spftree[tree][level - 1] = isis_spftree_new(area);
+ }
}
-
- return;
}
void spftree_area_del(struct isis_area *area)
{
- if (area->is_type & IS_LEVEL_1) {
- if (area->spftree[0] != NULL) {
- isis_spftree_del(area->spftree[0]);
- area->spftree[0] = NULL;
- }
- if (area->spftree6[0]) {
- isis_spftree_del(area->spftree6[0]);
- area->spftree6[0] = NULL;
- }
- }
+ 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;
- if (area->is_type & IS_LEVEL_2) {
- if (area->spftree[1] != NULL) {
- isis_spftree_del(area->spftree[1]);
- area->spftree[1] = NULL;
- }
- if (area->spftree6[1] != NULL) {
- isis_spftree_del(area->spftree6[1]);
- area->spftree6[1] = NULL;
+ isis_spftree_del(area->spftree[tree][level - 1]);
}
}
-
- return;
}
void spftree_area_adj_del(struct isis_area *area, struct isis_adjacency *adj)
{
- if (area->is_type & IS_LEVEL_1) {
- if (area->spftree[0] != NULL)
- isis_spftree_adj_del(area->spftree[0], adj);
- if (area->spftree6[0] != NULL)
- isis_spftree_adj_del(area->spftree6[0], adj);
- }
-
- if (area->is_type & IS_LEVEL_2) {
- if (area->spftree[1] != NULL)
- isis_spftree_adj_del(area->spftree[1], adj);
- if (area->spftree6[1] != NULL)
- isis_spftree_adj_del(area->spftree6[1], adj);
+ 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);
+ }
}
- return;
+ if (fabricd_spftree(area) != NULL)
+ isis_spftree_adj_del(fabricd_spftree(area), adj);
}
/*
struct isis_vertex *vertex;
struct isis_lsp *lsp;
#ifdef EXTREME_DEBUG
- char buff[PREFIX2STR_BUFFER];
+ char buff[VID2STR_BUFFER];
#endif /* EXTREME_DEBUG */
- union isis_N n;
-
- memcpy(n.id, sysid, ISIS_SYS_ID_LEN);
- LSP_PSEUDO_ID(n.id) = 0;
lsp = isis_root_system_lsp(spftree->area, spftree->level, sysid);
if (lsp == NULL)
zlog_warn("ISIS-Spf: could not find own l%d LSP!",
spftree->level);
- vertex = isis_vertex_new(&n,
+ vertex = isis_vertex_new(spftree, sysid,
spftree->area->oldmetric
? VTYPE_NONPSEUDO_IS
: VTYPE_NONPSEUDO_TE_IS);
return vertex;
}
-static struct isis_vertex *isis_find_vertex(struct isis_vertex_queue *queue,
- union isis_N *n,
- enum vertextype vtype)
+static void vertex_add_parent_firsthop(struct hash_backet *backet, void *arg)
+{
+ struct isis_vertex *vertex = arg;
+ struct isis_vertex *hop = backet->data;
+
+ hash_get(vertex->firsthops, hop, hash_alloc_intern);
+}
+
+static void vertex_update_firsthops(struct isis_vertex *vertex,
+ struct isis_vertex *parent)
{
- struct isis_vertex querier;
+ if (vertex->d_N <= 2)
+ hash_get(vertex->firsthops, vertex, hash_alloc_intern);
- isis_vertex_id_init(&querier, n, vtype);
- return hash_lookup(queue->hash, &querier);
+ if (vertex->d_N < 2 || !parent)
+ return;
+
+ hash_iterate(parent->firsthops, vertex_add_parent_firsthop, vertex);
}
/*
struct listnode *node;
struct isis_adjacency *parent_adj;
#ifdef EXTREME_DEBUG
- char buff[PREFIX2STR_BUFFER];
+ char buff[VID2STR_BUFFER];
#endif
assert(isis_find_vertex(&spftree->paths, id, vtype) == NULL);
assert(isis_find_vertex(&spftree->tents, id, vtype) == NULL);
- vertex = isis_vertex_new(id, vtype);
+ vertex = isis_vertex_new(spftree, id, vtype);
vertex->d_N = cost;
vertex->depth = depth;
listnode_add(vertex->parents, parent);
}
+ if (spftree->hopcount_metric)
+ vertex_update_firsthops(vertex, parent);
+
if (parent && parent->Adj_N && listcount(parent->Adj_N) > 0) {
for (ALL_LIST_ELEMENTS_RO(parent->Adj_N, node, parent_adj))
listnode_add(vertex->Adj_N, parent_adj);
{
struct isis_vertex *vertex;
#ifdef EXTREME_DEBUG
- char buff[PREFIX2STR_BUFFER];
+ char buff[VID2STR_BUFFER];
#endif
assert(spftree && parent);
- struct prefix p;
+ if (spftree->hopcount_metric
+ && !VTYPE_IS(vtype))
+ return;
+
+ struct prefix_pair p;
if (vtype >= VTYPE_IPREACH_INTERNAL) {
- prefix_copy(&p, id);
- apply_mask(&p);
+ memcpy(&p, id, sizeof(p));
+ apply_mask(&p.dest);
+ apply_mask((struct prefix *)&p.src);
id = &p;
}
if (listnode_lookup(vertex->Adj_N, parent_adj)
== NULL)
listnode_add(vertex->Adj_N, parent_adj);
+ if (spftree->hopcount_metric)
+ vertex_update_firsthops(vertex, parent);
/* 2) */
if (listcount(vertex->Adj_N) > ISIS_MAX_PATH_SPLITS)
remove_excess_adjs(vertex->Adj_N);
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;
if (!lsp->tlvs)
return ISIS_OK;
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 (!memcmp(r->id, root_sysid, ISIS_SYS_ID_LEN))
if (!pseudo_lsp
&& !memcmp(er->id, null_sysid, ISIS_SYS_ID_LEN))
continue;
- dist = cost + er->metric;
+ dist = cost + (spftree->hopcount_metric ? 1 : er->metric);
process_N(spftree,
LSP_PSEUDO_ID(er->id) ? VTYPE_PSEUDO_TE_IS
: VTYPE_NONPSEUDO_TE_IS,
}
}
- if (!pseudo_lsp && spftree->family == AF_INET
+ if (!fabricd && !pseudo_lsp && spftree->family == AF_INET
&& spftree->mtid == ISIS_MT_IPV4_UNICAST) {
struct isis_item_list *reachs[] = {
&lsp->tlvs->oldstyle_ip_reach,
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;
- process_N(spftree, vtype, (void *)&r->prefix,
+ ip_info.dest.u.prefix4 = r->prefix.prefix;
+ ip_info.dest.prefixlen = r->prefix.prefixlen;
+ process_N(spftree, vtype, &ip_info,
dist, depth + 1, parent);
}
}
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 *)
: NULL;
r; r = r->next) {
dist = cost + r->metric;
- process_N(spftree, VTYPE_IPREACH_TE, (void *)&r->prefix,
+ ip_info.dest.u.prefix4 = r->prefix.prefix;
+ ip_info.dest.prefixlen = r->prefix.prefixlen;
+ process_N(spftree, VTYPE_IPREACH_TE, &ip_info,
dist, depth + 1, parent);
}
}
dist = cost + r->metric;
vtype = r->external ? VTYPE_IP6REACH_EXTERNAL
: VTYPE_IP6REACH_INTERNAL;
- process_N(spftree, vtype, (void *)&r->prefix, dist,
+ 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 (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;
+ }
+ process_N(spftree, vtype, &ip_info, dist,
depth + 1, parent);
}
}
struct list *adj_list;
struct list *adjdb;
struct prefix_ipv4 *ipv4;
- struct prefix prefix;
+ struct prefix_pair ip_info;
int retval = ISIS_OK;
uint8_t lsp_id[ISIS_SYS_ID_LEN + 2];
static uint8_t null_lsp_id[ISIS_SYS_ID_LEN + 2];
/*
* Add IP(v6) addresses of this circuit
*/
- if (spftree->family == AF_INET) {
- prefix.family = AF_INET;
+ if (spftree->family == AF_INET && !spftree->hopcount_metric) {
+ memset(&ip_info, 0, sizeof(ip_info));
+ ip_info.dest.family = AF_INET;
for (ALL_LIST_ELEMENTS_RO(circuit->ip_addrs, ipnode,
ipv4)) {
- prefix.u.prefix4 = ipv4->prefix;
- prefix.prefixlen = ipv4->prefixlen;
- apply_mask(&prefix);
+ ip_info.dest.u.prefix4 = ipv4->prefix;
+ ip_info.dest.prefixlen = ipv4->prefixlen;
+ apply_mask(&ip_info.dest);
isis_spf_add_local(spftree,
VTYPE_IPREACH_INTERNAL,
- &prefix, NULL, 0, parent);
+ &ip_info, NULL, 0, parent);
}
}
- if (spftree->family == AF_INET6) {
- prefix.family = AF_INET6;
+ if (spftree->family == AF_INET6 && !spftree->hopcount_metric) {
+ memset(&ip_info, 0, sizeof(ip_info));
+ ip_info.dest.family = AF_INET6;
for (ALL_LIST_ELEMENTS_RO(circuit->ipv6_non_link,
ipnode, ipv6)) {
- prefix.prefixlen = ipv6->prefixlen;
- prefix.u.prefix6 = ipv6->prefix;
- apply_mask(&prefix);
+ ip_info.dest.u.prefix6 = ipv6->prefix;
+ ip_info.dest.prefixlen = ipv6->prefixlen;
+ apply_mask(&ip_info.dest);
isis_spf_add_local(spftree,
VTYPE_IP6REACH_INTERNAL,
- &prefix, NULL, 0, parent);
+ &ip_info, NULL, 0, parent);
}
}
if (circuit->circ_type == CIRCUIT_T_BROADCAST) {
adjdb = circuit->u.bc.adjdb[spftree->level - 1];
isis_adj_build_up_list(adjdb, adj_list);
if (listcount(adj_list) == 0) {
- list_delete_and_null(&adj_list);
+ list_delete(&adj_list);
if (isis->debugs & DEBUG_SPF_EVENTS)
zlog_debug(
"ISIS-Spf: no L%d adjacencies on circuit %s",
LSP_PSEUDO_ID(lsp_id) = 0;
isis_spf_add_local(
spftree, VTYPE_ES, lsp_id, adj,
+ spftree->hopcount_metric ? 1 :
circuit->te_metric
[spftree->level - 1],
parent);
? VTYPE_NONPSEUDO_IS
: VTYPE_NONPSEUDO_TE_IS,
lsp_id, adj,
+ spftree->hopcount_metric ? 1 :
circuit->te_metric
[spftree->level - 1],
parent);
case ISIS_SYSTYPE_UNKNOWN:
default:
zlog_warn(
- "isis_spf_preload_tent unknow adj type");
+ "isis_spf_preload_tent unknown adj type");
}
}
- list_delete_and_null(&adj_list);
+ list_delete(&adj_list);
/*
* Add the pseudonode
*/
circuit->circuit_id);
continue;
}
- isis_spf_process_lsp(
- spftree, lsp,
- circuit->te_metric[spftree->level - 1], 0,
- root_sysid, parent);
+ isis_spf_process_lsp(spftree, lsp,
+ spftree->hopcount_metric ?
+ 1 : circuit->te_metric[spftree->level - 1],
+ 0, root_sysid, parent);
} else if (circuit->circ_type == CIRCUIT_T_P2P) {
adj = circuit->u.p2p.neighbor;
if (!adj || adj->adj_state != ISIS_ADJ_UP)
LSP_PSEUDO_ID(lsp_id) = 0;
isis_spf_add_local(
spftree, VTYPE_ES, lsp_id, adj,
+ spftree->hopcount_metric ? 1 :
circuit->te_metric[spftree->level - 1],
parent);
break;
? VTYPE_NONPSEUDO_IS
: VTYPE_NONPSEUDO_TE_IS,
lsp_id, adj,
+ spftree->hopcount_metric ? 1 :
circuit->te_metric
[spftree->level - 1],
parent);
static void add_to_paths(struct isis_spftree *spftree,
struct isis_vertex *vertex)
{
- char buff[PREFIX2STR_BUFFER];
+ char buff[VID2STR_BUFFER];
if (isis_find_vertex(&spftree->paths, &vertex->N, vertex->type))
return;
if (VTYPE_IP(vertex->type)) {
if (listcount(vertex->Adj_N) > 0)
- isis_route_create((struct prefix *)&vertex->N.prefix,
+ isis_route_create(&vertex->N.ip.dest,
+ &vertex->N.ip.src,
vertex->d_N, vertex->depth,
vertex->Adj_N, spftree->area,
- spftree->level);
+ spftree->route_table);
else if (isis->debugs & DEBUG_SPF_EVENTS)
zlog_debug(
"ISIS-Spf: no adjacencies do not install route for "
}
static void init_spt(struct isis_spftree *spftree, int mtid, int level,
- int family)
+ int family, enum spf_tree_id tree_id,
+ bool hopcount_metric)
{
isis_vertex_queue_clear(&spftree->tents);
isis_vertex_queue_clear(&spftree->paths);
spftree->mtid = mtid;
spftree->level = level;
spftree->family = family;
- return;
+ spftree->tree_id = tree_id;
+ spftree->hopcount_metric = hopcount_metric;
}
-static int isis_run_spf(struct isis_area *area, int level, int family,
+static void isis_spf_loop(struct isis_spftree *spftree,
+ uint8_t *root_sysid)
+{
+ struct isis_vertex *vertex;
+ struct isis_lsp *lsp;
+
+ while (isis_vertex_queue_count(&spftree->tents)) {
+ vertex = isis_vertex_queue_pop(&spftree->tents);
+
+#ifdef EXTREME_DEBUG
+ 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);
+ }
+}
+
+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);
+
+ init_spt(spftree, ISIS_MT_IPV4_UNICAST, ISIS_LEVEL2,
+ AF_INET, SPFTREE_IPV4, true);
+ if (!memcmp(sysid, isis->sysid, ISIS_SYS_ID_LEN)) {
+ /* If we are running locally, initialize with information from adjacencies */
+ struct isis_vertex *root = isis_spf_add_root(spftree, sysid);
+ isis_spf_preload_tent(spftree, sysid, root);
+ } else {
+ isis_vertex_queue_insert(&spftree->tents, isis_vertex_new(
+ spftree, sysid,
+ VTYPE_NONPSEUDO_TE_IS));
+ }
+
+ isis_spf_loop(spftree, sysid);
+
+ return spftree;
+}
+
+static int isis_run_spf(struct isis_area *area, int level,
+ enum spf_tree_id tree_id,
uint8_t *sysid, struct timeval *nowtv)
{
int retval = ISIS_OK;
- struct isis_vertex *vertex;
struct isis_vertex *root_vertex;
- struct isis_spftree *spftree = NULL;
- uint8_t lsp_id[ISIS_SYS_ID_LEN + 2];
- struct isis_lsp *lsp;
- struct route_table *table = NULL;
+ struct isis_spftree *spftree = area->spftree[tree_id][level - 1];
struct timeval time_now;
unsigned long long start_time, end_time;
- uint16_t mtid;
+ uint16_t mtid = 0;
/* Get time that can't roll backwards. */
start_time = nowtv->tv_sec;
start_time = (start_time * 1000000) + nowtv->tv_usec;
- if (family == AF_INET)
- spftree = area->spftree[level - 1];
- else if (family == AF_INET6)
- spftree = area->spftree6[level - 1];
+ int family = -1;
+ switch (tree_id) {
+ case SPFTREE_IPV4:
+ family = AF_INET;
+ mtid = ISIS_MT_IPV4_UNICAST;
+ break;
+ case SPFTREE_IPV6:
+ family = AF_INET6;
+ mtid = isis_area_ipv6_topology(area);
+ break;
+ case SPFTREE_DSTSRC:
+ family = AF_INET6;
+ mtid = ISIS_MT_IPV6_DSTSRC;
+ break;
+ case SPFTREE_COUNT:
+ assert(!"isis_run_spf should never be called with SPFTREE_COUNT as argument!");
+ return ISIS_WARNING;
+ }
+
assert(spftree);
assert(sysid);
- /* Make all routes in current route table inactive. */
- if (family == AF_INET)
- table = area->route_table[level - 1];
- else if (family == AF_INET6)
- table = area->route_table6[level - 1];
-
- isis_route_invalidate_table(area, table);
-
- /* We only support ipv4-unicast and ipv6-unicast as topologies for now
- */
- if (family == AF_INET6)
- mtid = isis_area_ipv6_topology(area);
- else
- mtid = ISIS_MT_IPV4_UNICAST;
-
/*
* C.2.5 Step 0
*/
- init_spt(spftree, mtid, level, family);
+ init_spt(spftree, mtid, level, family, tree_id, false);
/* a) */
root_vertex = isis_spf_add_root(spftree, sysid);
/* b) */
print_sys_hostname(sysid));
}
- while (isis_vertex_queue_count(&spftree->tents)) {
- vertex = isis_vertex_queue_pop(&spftree->tents);
-
-#ifdef EXTREME_DEBUG
- 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)) {
- memcpy(lsp_id, vertex->N.id, ISIS_SYS_ID_LEN + 1);
- LSP_FRAGMENT(lsp_id) = 0;
- lsp = lsp_search(lsp_id, area->lspdb[level - 1]);
- if (lsp && lsp->hdr.rem_lifetime != 0) {
- isis_spf_process_lsp(spftree, lsp, vertex->d_N,
- vertex->depth, sysid,
- vertex);
- } else {
- zlog_warn("ISIS-Spf: No LSP found for %s",
- rawlspid_print(lsp_id));
- }
- }
- }
-
+ isis_spf_loop(spftree, sysid);
out:
- isis_route_validate(area);
spftree->runcount++;
spftree->last_run_timestamp = time(NULL);
spftree->last_run_monotime = monotime(&time_now);
return retval;
}
+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);
+ } else if (area->is_type == IS_LEVEL_2) {
+ isis_route_verify_table(area, trees[1]->route_table);
+ } else {
+ isis_route_verify_merge(area, trees[0]->route_table,
+ trees[1]->route_table);
+ }
+}
+
+void isis_spf_invalidate_routes(struct isis_spftree *tree)
+{
+ isis_route_invalidate_table(tree->area, tree->route_table);
+}
+
static int isis_run_spf_cb(struct thread *thread)
{
struct isis_spf_run *run = THREAD_ARG(thread);
return ISIS_WARNING;
}
+ isis_area_invalidate_routes(area, level);
+
if (isis->debugs & DEBUG_SPF_EVENTS)
zlog_debug("ISIS-Spf (%s) L%d SPF needed, periodic SPF",
area->area_tag, level);
if (area->ip_circuits)
- retval = isis_run_spf(area, level, AF_INET, isis->sysid,
+ retval = isis_run_spf(area, level, SPFTREE_IPV4, isis->sysid,
&thread->real);
if (area->ipv6_circuits)
- retval = isis_run_spf(area, level, AF_INET6, isis->sysid,
+ retval = isis_run_spf(area, level, SPFTREE_IPV6, isis->sysid,
&thread->real);
+ if (area->ipv6_circuits
+ && isis_area_ipv6_dstsrc_enabled(area))
+ retval = isis_run_spf(area, level, SPFTREE_DSTSRC, isis->sysid,
+ &thread->real);
+
+ 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);
return retval;
}
return run;
}
-int isis_spf_schedule(struct isis_area *area, int level)
+int _isis_spf_schedule(struct isis_area *area, int level,
+ const char *func, const char *file, int line)
{
- struct isis_spftree *spftree = area->spftree[level - 1];
+ struct isis_spftree *spftree = area->spftree[SPFTREE_IPV4][level - 1];
time_t now = monotime(NULL);
int diff = now - spftree->last_run_monotime;
assert(diff >= 0);
assert(area->is_type & level);
- if (isis->debugs & DEBUG_SPF_EVENTS)
+ if (isis->debugs & DEBUG_SPF_EVENTS) {
zlog_debug(
- "ISIS-Spf (%s) L%d SPF schedule called, lastrun %d sec ago",
- area->area_tag, level, diff);
+ "ISIS-Spf (%s) L%d SPF schedule called, lastrun %d sec ago"
+ " Caller: %s %s:%d",
+ area->area_tag, level, diff, func, file, line);
+ }
if (area->spf_delay_ietf[level - 1]) {
/* Need to call schedule function also if spf delay is running
{
struct listnode *node;
struct isis_vertex *vertex;
- char buff[PREFIX2STR_BUFFER];
+ char buff[VID2STR_BUFFER];
vty_out(vty,
"Vertex Type Metric Next-Hop Interface Parent\n");
}
}
+static void isis_print_spftree(struct vty *vty, int level,
+ struct isis_area *area,
+ enum spf_tree_id tree_id)
+{
+ const char *tree_id_text = NULL;
+
+ switch (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;
+ }
+
+ if (!area->spftree[tree_id][level - 1]
+ || !isis_vertex_queue_count(
+ &area->spftree[tree_id][level - 1]->paths))
+ return;
+
+ vty_out(vty, "IS-IS paths to level-%d routers %s\n",
+ level, tree_id_text);
+ isis_print_paths(vty, &area->spftree[tree_id][level - 1]->paths,
+ isis->sysid);
+ vty_out(vty, "\n");
+}
+
DEFUN (show_isis_topology,
show_isis_topology_cmd,
- "show isis topology [<level-1|level-2>]",
- SHOW_STR
- "IS-IS information\n"
+ "show " PROTO_NAME " topology"
+#ifndef FABRICD
+ " [<level-1|level-2>]"
+#endif
+ , SHOW_STR
+ PROTO_HELP
"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")
+ "Paths to all level-2 routers in the domain\n"
+#endif
+ )
{
int levels;
struct listnode *node;
if ((level & levels) == 0)
continue;
- if (area->ip_circuits > 0 && area->spftree[level - 1]
- && isis_vertex_queue_count(&area->spftree[level - 1]->paths) > 0) {
- vty_out(vty,
- "IS-IS paths to level-%d routers that speak IP\n",
- level);
- isis_print_paths(
- vty, &area->spftree[level - 1]->paths,
- isis->sysid);
- vty_out(vty, "\n");
+ if (area->ip_circuits > 0) {
+ isis_print_spftree(vty, level, area,
+ SPFTREE_IPV4);
}
- if (area->ipv6_circuits > 0 && area->spftree6[level - 1]
- && isis_vertex_queue_count(&area->spftree6[level - 1]->paths) > 0) {
- vty_out(vty,
- "IS-IS paths to level-%d routers that speak IPv6\n",
- level);
- isis_print_paths(
- vty, &area->spftree6[level - 1]->paths,
- isis->sysid);
- vty_out(vty, "\n");
+ if (area->ipv6_circuits > 0) {
+ isis_print_spftree(vty, level, area,
+ SPFTREE_IPV6);
}
+ if (isis_area_ipv6_dstsrc_enabled(area)) {
+ isis_print_spftree(vty, level, area,
+ SPFTREE_DSTSRC);
+ }
+ }
+
+ 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");
projects / mirror_frr.git / blobdiff