summaryrefslogtreecommitdiff
path: root/isisd/isis_spf.c
diff options
context:
space:
mode:
Diffstat (limited to 'isisd/isis_spf.c')
-rw-r--r--isisd/isis_spf.c1124
1 files changed, 661 insertions, 463 deletions
diff --git a/isisd/isis_spf.c b/isisd/isis_spf.c
index 5d0b161f..198104a9 100644
--- a/isisd/isis_spf.c
+++ b/isisd/isis_spf.c
@@ -36,6 +36,7 @@
#include "isis_constants.h"
#include "isis_common.h"
+#include "isis_flags.h"
#include "dict.h"
#include "isisd.h"
#include "isis_misc.h"
@@ -49,10 +50,6 @@
#include "isis_route.h"
#include "isis_csm.h"
-extern struct isis *isis;
-extern struct thread_master *master;
-extern struct host host;
-
int isis_run_spf_l1 (struct thread *thread);
int isis_run_spf_l2 (struct thread *thread);
@@ -113,7 +110,6 @@ remove_excess_adjs (struct list *adjs)
return;
}
-#ifdef EXTREME_DEBUG
static const char *
vtype2string (enum vertextype vtype)
{
@@ -164,12 +160,12 @@ vid2string (struct isis_vertex *vertex, u_char * buff)
{
case VTYPE_PSEUDO_IS:
case VTYPE_PSEUDO_TE_IS:
- return rawlspid_print (vertex->N.id);
+ return print_sys_hostname (vertex->N.id);
break;
case VTYPE_NONPSEUDO_IS:
case VTYPE_NONPSEUDO_TE_IS:
case VTYPE_ES:
- return sysid_print (vertex->N.id);
+ return print_sys_hostname (vertex->N.id);
break;
case VTYPE_IPREACH_INTERNAL:
case VTYPE_IPREACH_EXTERNAL:
@@ -186,149 +182,265 @@ vid2string (struct isis_vertex *vertex, u_char * buff)
return (char *) buff;
}
-#endif /* EXTREME_DEBUG */
-static struct isis_spftree *
-isis_spftree_new ()
+static struct isis_vertex *
+isis_vertex_new (void *id, enum vertextype vtype)
{
- struct isis_spftree *tree;
+ struct isis_vertex *vertex;
- tree = XCALLOC (MTYPE_ISIS_SPFTREE, sizeof (struct isis_spftree));
- if (tree == NULL)
+ vertex = XCALLOC (MTYPE_ISIS_VERTEX, sizeof (struct isis_vertex));
+ if (vertex == NULL)
{
- zlog_err ("ISIS-Spf: isis_spftree_new Out of memory!");
+ zlog_err ("isis_vertex_new Out of memory!");
return NULL;
}
- tree->tents = list_new ();
- tree->paths = list_new ();
- return tree;
+ vertex->type = vtype;
+ switch (vtype)
+ {
+ case VTYPE_ES:
+ case VTYPE_NONPSEUDO_IS:
+ case VTYPE_NONPSEUDO_TE_IS:
+ memcpy (vertex->N.id, (u_char *) id, ISIS_SYS_ID_LEN);
+ break;
+ case VTYPE_PSEUDO_IS:
+ case VTYPE_PSEUDO_TE_IS:
+ memcpy (vertex->N.id, (u_char *) id, ISIS_SYS_ID_LEN + 1);
+ break;
+ case VTYPE_IPREACH_INTERNAL:
+ case VTYPE_IPREACH_EXTERNAL:
+ case VTYPE_IPREACH_TE:
+#ifdef HAVE_IPV6
+ case VTYPE_IP6REACH_INTERNAL:
+ case VTYPE_IP6REACH_EXTERNAL:
+#endif /* HAVE_IPV6 */
+ memcpy (&vertex->N.prefix, (struct prefix *) id,
+ sizeof (struct prefix));
+ break;
+ default:
+ zlog_err ("WTF!");
+ }
+
+ vertex->Adj_N = list_new ();
+ vertex->parents = list_new ();
+ vertex->children = list_new ();
+
+ return vertex;
}
static void
isis_vertex_del (struct isis_vertex *vertex)
{
list_delete (vertex->Adj_N);
+ vertex->Adj_N = NULL;
+ list_delete (vertex->parents);
+ vertex->parents = NULL;
+ list_delete (vertex->children);
+ vertex->children = NULL;
+ memset(vertex, 0, sizeof(struct isis_vertex));
XFREE (MTYPE_ISIS_VERTEX, vertex);
return;
}
-#if 0 /* HT: Not used yet. */
static void
+isis_vertex_adj_del (struct isis_vertex *vertex, struct isis_adjacency *adj)
+{
+ struct listnode *node, *nextnode;
+ if (!vertex)
+ return;
+ for (node = listhead (vertex->Adj_N); node; node = nextnode)
+ {
+ nextnode = listnextnode(node);
+ if (listgetdata(node) == adj)
+ list_delete_node(vertex->Adj_N, node);
+ }
+ return;
+}
+
+struct isis_spftree *
+isis_spftree_new (struct isis_area *area)
+{
+ 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;
+ }
+
+ tree->tents = list_new ();
+ tree->paths = list_new ();
+ tree->area = area;
+ tree->last_run_timestamp = 0;
+ tree->last_run_duration = 0;
+ tree->runcount = 0;
+ tree->pending = 0;
+ return tree;
+}
+
+void
isis_spftree_del (struct isis_spftree *spftree)
{
+ THREAD_TIMER_OFF (spftree->t_spf);
+
spftree->tents->del = (void (*)(void *)) isis_vertex_del;
list_delete (spftree->tents);
+ spftree->tents = NULL;
spftree->paths->del = (void (*)(void *)) isis_vertex_del;
list_delete (spftree->paths);
+ spftree->paths = NULL;
XFREE (MTYPE_ISIS_SPFTREE, spftree);
return;
}
-#endif
+
+void
+isis_spftree_adj_del (struct isis_spftree *spftree, struct isis_adjacency *adj)
+{
+ struct listnode *node;
+ if (!adj)
+ return;
+ for (node = listhead (spftree->tents); node; node = listnextnode (node))
+ isis_vertex_adj_del (listgetdata (node), adj);
+ for (node = listhead (spftree->paths); node; node = listnextnode (node))
+ isis_vertex_adj_del (listgetdata (node), adj);
+ return;
+}
void
spftree_area_init (struct isis_area *area)
{
- if ((area->is_type & IS_LEVEL_1) && area->spftree[0] == NULL)
- {
- area->spftree[0] = isis_spftree_new ();
+ if (area->is_type & IS_LEVEL_1)
+ {
+ if (area->spftree[0] == NULL)
+ area->spftree[0] = isis_spftree_new (area);
#ifdef HAVE_IPV6
- area->spftree6[0] = isis_spftree_new ();
+ if (area->spftree6[0] == NULL)
+ area->spftree6[0] = isis_spftree_new (area);
#endif
+ }
- /* thread_add_timer (master, isis_run_spf_l1, area,
- isis_jitter (PERIODIC_SPF_INTERVAL, 10)); */
- }
-
- if ((area->is_type & IS_LEVEL_2) && area->spftree[1] == NULL)
- {
- area->spftree[1] = isis_spftree_new ();
+ if (area->is_type & IS_LEVEL_2)
+ {
+ if (area->spftree[1] == NULL)
+ area->spftree[1] = isis_spftree_new (area);
#ifdef HAVE_IPV6
- area->spftree6[1] = isis_spftree_new ();
+ if (area->spftree6[1] == NULL)
+ area->spftree6[1] = isis_spftree_new (area);
#endif
- /* thread_add_timer (master, isis_run_spf_l2, area,
- isis_jitter (PERIODIC_SPF_INTERVAL, 10)); */
- }
+ }
return;
}
-static struct isis_vertex *
-isis_vertex_new (void *id, enum vertextype vtype)
+void
+spftree_area_del (struct isis_area *area)
{
- struct isis_vertex *vertex;
-
- vertex = XCALLOC (MTYPE_ISIS_VERTEX, sizeof (struct isis_vertex));
- if (vertex == NULL)
+ if (area->is_type & IS_LEVEL_1)
+ {
+ if (area->spftree[0] != NULL)
{
- zlog_err ("isis_vertex_new Out of memory!");
- return NULL;
+ isis_spftree_del (area->spftree[0]);
+ area->spftree[0] = NULL;
+ }
+#ifdef HAVE_IPV6
+ if (area->spftree6[0])
+ {
+ isis_spftree_del (area->spftree6[0]);
+ area->spftree6[0] = NULL;
}
+#endif
+ }
- vertex->type = vtype;
- switch (vtype)
+ if (area->is_type & IS_LEVEL_2)
+ {
+ if (area->spftree[1] != NULL)
{
- case VTYPE_ES:
- case VTYPE_NONPSEUDO_IS:
- case VTYPE_NONPSEUDO_TE_IS:
- memcpy (vertex->N.id, (u_char *) id, ISIS_SYS_ID_LEN);
- break;
- case VTYPE_PSEUDO_IS:
- case VTYPE_PSEUDO_TE_IS:
- memcpy (vertex->N.id, (u_char *) id, ISIS_SYS_ID_LEN + 1);
- break;
- case VTYPE_IPREACH_INTERNAL:
- case VTYPE_IPREACH_EXTERNAL:
- case VTYPE_IPREACH_TE:
+ isis_spftree_del (area->spftree[1]);
+ area->spftree[1] = NULL;
+ }
#ifdef HAVE_IPV6
- case VTYPE_IP6REACH_INTERNAL:
- case VTYPE_IP6REACH_EXTERNAL:
-#endif /* HAVE_IPV6 */
- memcpy (&vertex->N.prefix, (struct prefix *) id,
- sizeof (struct prefix));
- break;
- default:
- zlog_err ("WTF!");
+ if (area->spftree[1] != NULL)
+ {
+ isis_spftree_del (area->spftree6[1]);
+ area->spftree6[1] = NULL;
}
+#endif
+ }
- vertex->Adj_N = list_new ();
+ return;
+}
- return vertex;
+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);
+#ifdef HAVE_IPV6
+ if (area->spftree6[0] != NULL)
+ isis_spftree_adj_del (area->spftree6[0], adj);
+#endif
+ }
+
+ if (area->is_type & IS_LEVEL_2)
+ {
+ if (area->spftree[1] != NULL)
+ isis_spftree_adj_del (area->spftree[1], adj);
+#ifdef HAVE_IPV6
+ if (area->spftree6[1] != NULL)
+ isis_spftree_adj_del (area->spftree6[1], adj);
+#endif
+ }
+
+ return;
+}
+
+/*
+ * Find the system LSP: returns the LSP in our LSP database
+ * associated with the given system ID.
+ */
+static struct isis_lsp *
+isis_root_system_lsp (struct isis_area *area, int level, u_char *sysid)
+{
+ struct isis_lsp *lsp;
+ u_char 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 (lspid, area->lspdb[level - 1]);
+ if (lsp && lsp->lsp_header->rem_lifetime != 0)
+ return lsp;
+ return NULL;
}
/*
* Add this IS to the root of SPT
*/
-static void
-isis_spf_add_self (struct isis_spftree *spftree, struct isis_area *area,
- int level)
+static struct isis_vertex *
+isis_spf_add_root (struct isis_spftree *spftree, int level, u_char *sysid)
{
struct isis_vertex *vertex;
struct isis_lsp *lsp;
- u_char lspid[ISIS_SYS_ID_LEN + 2];
#ifdef EXTREME_DEBUG
u_char buff[BUFSIZ];
#endif /* EXTREME_DEBUG */
- memcpy (lspid, isis->sysid, ISIS_SYS_ID_LEN);
- LSP_PSEUDO_ID (lspid) = 0;
- LSP_FRAGMENT (lspid) = 0;
-
- lsp = lsp_search (lspid, area->lspdb[level - 1]);
+ lsp = isis_root_system_lsp (spftree->area, level, sysid);
if (lsp == NULL)
zlog_warn ("ISIS-Spf: could not find own l%d LSP!", level);
- if (!area->oldmetric)
- vertex = isis_vertex_new (isis->sysid, VTYPE_NONPSEUDO_TE_IS);
+ if (!spftree->area->oldmetric)
+ vertex = isis_vertex_new (sysid, VTYPE_NONPSEUDO_TE_IS);
else
- vertex = isis_vertex_new (isis->sysid, VTYPE_NONPSEUDO_IS);
-
- vertex->lsp = lsp;
+ vertex = isis_vertex_new (sysid, VTYPE_NONPSEUDO_IS);
listnode_add (spftree->paths, vertex);
@@ -338,7 +450,7 @@ isis_spf_add_self (struct isis_spftree *spftree, struct isis_area *area,
vertex->depth, vertex->d_N);
#endif /* EXTREME_DEBUG */
- return;
+ return vertex;
}
static struct isis_vertex *
@@ -390,26 +502,40 @@ isis_find_vertex (struct list *list, void *id, enum vertextype vtype)
*/
static struct isis_vertex *
isis_spf_add2tent (struct isis_spftree *spftree, enum vertextype vtype,
- void *id, struct isis_adjacency *adj, u_int32_t cost,
- int depth, int family)
+ void *id, uint32_t cost, int depth, int family,
+ struct isis_adjacency *adj, struct isis_vertex *parent)
{
struct isis_vertex *vertex, *v;
struct listnode *node;
+ struct isis_adjacency *parent_adj;
#ifdef EXTREME_DEBUG
u_char buff[BUFSIZ];
#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->d_N = cost;
vertex->depth = depth;
- if (adj)
+ if (parent) {
+ listnode_add (vertex->parents, parent);
+ if (listnode_lookup (parent->children, vertex) == NULL)
+ listnode_add (parent->children, vertex);
+ }
+
+ 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);
+ } else if (adj) {
listnode_add (vertex->Adj_N, adj);
+ }
#ifdef EXTREME_DEBUG
- zlog_debug ("ISIS-Spf: add to TENT %s %s depth %d dist %d",
+ 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),
- vertex->depth, vertex->d_N);
+ vertex->depth, vertex->d_N, listcount(vertex->Adj_N));
#endif /* EXTREME_DEBUG */
if (list_isempty (spftree->tents))
@@ -417,8 +543,8 @@ isis_spf_add2tent (struct isis_spftree *spftree, enum vertextype vtype,
listnode_add (spftree->tents, vertex);
return vertex;
}
-
- /* XXX: This cant use the standard ALL_LIST_ELEMENT macro */
+
+ /* XXX: This cant use the standard ALL_LIST_ELEMENTS macro */
for (node = listhead (spftree->tents); node; node = listnextnode (node))
{
v = listgetdata (node);
@@ -427,35 +553,24 @@ isis_spf_add2tent (struct isis_spftree *spftree, enum vertextype vtype,
list_add_node_prev (spftree->tents, node, vertex);
break;
}
- else if (v->d_N == vertex->d_N)
+ else if (v->d_N == vertex->d_N && v->type > vertex->type)
{
/* Tie break, add according to type */
- while (v && v->d_N == vertex->d_N && v->type > vertex->type)
- {
- if (v->type > vertex->type)
- {
- break;
- }
- /* XXX: this seems dubious, node is the loop iterator */
- node = listnextnode (node);
- (node) ? (v = listgetdata (node)) : (v = NULL);
- }
- list_add_node_prev (spftree->tents, node, vertex);
- break;
- }
- else if (node->next == NULL)
- {
- list_add_node_next (spftree->tents, node, vertex);
+ list_add_node_prev (spftree->tents, node, vertex);
break;
}
}
+
+ if (node == NULL)
+ listnode_add (spftree->tents, vertex);
+
return vertex;
}
-static struct isis_vertex *
+static void
isis_spf_add_local (struct isis_spftree *spftree, enum vertextype vtype,
- void *id, struct isis_adjacency *adj, u_int32_t cost,
- int family)
+ void *id, struct isis_adjacency *adj, uint32_t cost,
+ int family, struct isis_vertex *parent)
{
struct isis_vertex *vertex;
@@ -471,40 +586,65 @@ isis_spf_add_local (struct isis_spftree *spftree, enum vertextype vtype,
/* d) */
if (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);
+ if (parent && (listnode_lookup (parent->children, vertex) == NULL))
+ listnode_add (parent->children, vertex);
+ return;
}
- /* f) */
- else if (vertex->d_N > cost)
+ else if (vertex->d_N < cost)
{
- listnode_delete (spftree->tents, vertex);
- goto add2tent;
+ /* e) do nothing */
+ return;
}
- /* e) do nothing */
- return vertex;
+ else { /* vertex->d_N > cost */
+ /* f) */
+ struct listnode *pnode, *pnextnode;
+ struct isis_vertex *pvertex;
+ listnode_delete (spftree->tents, vertex);
+ assert (listcount (vertex->children) == 0);
+ for (ALL_LIST_ELEMENTS (vertex->parents, pnode, pnextnode, pvertex))
+ listnode_delete(pvertex->children, vertex);
+ isis_vertex_del (vertex);
+ }
}
-add2tent:
- return isis_spf_add2tent (spftree, vtype, id, adj, cost, 1, family);
+ isis_spf_add2tent (spftree, vtype, id, cost, 1, family, adj, parent);
+ return;
}
static void
process_N (struct isis_spftree *spftree, enum vertextype vtype, void *id,
- u_int16_t dist, u_int16_t depth, struct isis_adjacency *adj,
- int family)
+ uint32_t dist, uint16_t depth, int family,
+ struct isis_vertex *parent)
{
struct isis_vertex *vertex;
#ifdef EXTREME_DEBUG
u_char buff[255];
#endif
+ assert (spftree && parent);
+
+ /* RFC3787 section 5.1 */
+ if (spftree->area->newmetric == 1)
+ {
+ if (dist > MAX_WIDE_PATH_METRIC)
+ return;
+ }
/* C.2.6 b) */
- if (dist > MAX_PATH_METRIC)
- return;
+ 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
- zlog_debug ("ISIS-Spf: process_N %s %s dist %d already found from PATH",
+ 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), dist);
#endif /* EXTREME_DEBUG */
assert (dist >= vertex->d_N);
@@ -517,16 +657,26 @@ process_N (struct isis_spftree *spftree, enum vertextype vtype, void *id,
{
/* 1) */
#ifdef EXTREME_DEBUG
- zlog_debug ("ISIS-Spf: process_N %s %s dist %d",
- vtype2string (vtype), vid2string (vertex, buff), dist);
+ 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), dist,
+ (parent ? print_sys_hostname (parent->N.id) : "null"),
+ (parent ? listcount (parent->Adj_N) : 0));
#endif /* EXTREME_DEBUG */
if (vertex->d_N == dist)
{
- if (adj)
- listnode_add (vertex->Adj_N, adj);
+ struct listnode *node;
+ struct isis_adjacency *parent_adj;
+ for (ALL_LIST_ELEMENTS_RO (parent->Adj_N, node, parent_adj))
+ if (listnode_lookup(vertex->Adj_N, parent_adj) == NULL)
+ listnode_add (vertex->Adj_N, parent_adj);
/* 2) */
if (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);
+ if (listnode_lookup (parent->children, vertex) == NULL)
+ listnode_add (parent->children, vertex);
/* 3) */
return;
}
@@ -537,11 +687,23 @@ process_N (struct isis_spftree *spftree, enum vertextype vtype, void *id,
}
else
{
+ struct listnode *pnode, *pnextnode;
+ struct isis_vertex *pvertex;
listnode_delete (spftree->tents, vertex);
+ assert (listcount (vertex->children) == 0);
+ for (ALL_LIST_ELEMENTS (vertex->parents, pnode, pnextnode, pvertex))
+ listnode_delete(pvertex->children, vertex);
+ isis_vertex_del (vertex);
}
}
- isis_spf_add2tent (spftree, vtype, id, adj, dist, depth, family);
+#ifdef EXTREME_DEBUG
+ 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, family, NULL, parent);
return;
}
@@ -551,10 +713,10 @@ process_N (struct isis_spftree *spftree, enum vertextype vtype, void *id,
static int
isis_spf_process_lsp (struct isis_spftree *spftree, struct isis_lsp *lsp,
uint32_t cost, uint16_t depth, int family,
- struct isis_adjacency *adj)
+ u_char *root_sysid, struct isis_vertex *parent)
{
struct listnode *node, *fragnode = NULL;
- u_int16_t dist;
+ uint32_t dist;
struct is_neigh *is_neigh;
struct te_is_neigh *te_is_neigh;
struct ipv4_reachability *ipreach;
@@ -564,114 +726,121 @@ isis_spf_process_lsp (struct isis_spftree *spftree, struct isis_lsp *lsp,
#ifdef HAVE_IPV6
struct ipv6_reachability *ip6reach;
#endif /* HAVE_IPV6 */
+ static const u_char null_sysid[ISIS_SYS_ID_LEN];
- if (lsp->tlv_data.nlpids == NULL || !speaks (lsp->tlv_data.nlpids, family))
+ if (!speaks (lsp->tlv_data.nlpids, family))
return ISIS_OK;
lspfragloop:
if (lsp->lsp_header->seq_num == 0)
{
- zlog_warn ("isis_spf_process_lsp(): lsp with 0 seq_num"
- " - do not process");
+ zlog_warn ("isis_spf_process_lsp(): lsp with 0 seq_num - ignore");
return ISIS_WARNING;
}
+#ifdef EXTREME_DEBUG
+ zlog_debug ("ISIS-Spf: process_lsp %s", print_sys_hostname(lsp->lsp_header->lsp_id));
+#endif /* EXTREME_DEBUG */
+
if (!ISIS_MASK_LSP_OL_BIT (lsp->lsp_header->lsp_bits))
+ {
+ if (lsp->tlv_data.is_neighs)
{
- if (lsp->tlv_data.is_neighs)
- {
- for (ALL_LIST_ELEMENTS_RO (lsp->tlv_data.is_neighs, node, is_neigh))
- {
- /* C.2.6 a) */
- /* Two way connectivity */
- if (!memcmp (is_neigh->neigh_id, isis->sysid, ISIS_SYS_ID_LEN))
- continue;
- dist = cost + is_neigh->metrics.metric_default;
- vtype = LSP_PSEUDO_ID (is_neigh->neigh_id) ? VTYPE_PSEUDO_IS
- : VTYPE_NONPSEUDO_IS;
- process_N (spftree, vtype, (void *) is_neigh->neigh_id, dist,
- depth + 1, adj, family);
- }
- }
- if (lsp->tlv_data.te_is_neighs)
- {
- for (ALL_LIST_ELEMENTS_RO (lsp->tlv_data.te_is_neighs, node,
- te_is_neigh))
- {
- uint32_t metric;
- if (!memcmp (te_is_neigh->neigh_id, isis->sysid, ISIS_SYS_ID_LEN))
- continue;
- memcpy (&metric, te_is_neigh->te_metric, 3);
- dist = cost + ntohl (metric << 8);
- vtype = LSP_PSEUDO_ID (te_is_neigh->neigh_id) ? VTYPE_PSEUDO_TE_IS
- : VTYPE_NONPSEUDO_TE_IS;
- process_N (spftree, vtype, (void *) te_is_neigh->neigh_id, dist,
- depth + 1, adj, family);
- }
- }
- if (family == AF_INET && lsp->tlv_data.ipv4_int_reachs)
- {
- prefix.family = AF_INET;
- for (ALL_LIST_ELEMENTS_RO (lsp->tlv_data.ipv4_int_reachs,
- node, ipreach))
- {
- dist = cost + ipreach->metrics.metric_default;
- vtype = VTYPE_IPREACH_INTERNAL;
- prefix.u.prefix4 = ipreach->prefix;
- prefix.prefixlen = ip_masklen (ipreach->mask);
- process_N (spftree, vtype, (void *) &prefix, dist, depth + 1,
- adj, family);
- }
- }
+ for (ALL_LIST_ELEMENTS_RO (lsp->tlv_data.is_neighs, node, is_neigh))
+ {
+ /* C.2.6 a) */
+ /* Two way connectivity */
+ if (!memcmp (is_neigh->neigh_id, root_sysid, ISIS_SYS_ID_LEN))
+ continue;
+ if (!memcmp (is_neigh->neigh_id, null_sysid, ISIS_SYS_ID_LEN))
+ continue;
+ dist = cost + is_neigh->metrics.metric_default;
+ vtype = LSP_PSEUDO_ID (is_neigh->neigh_id) ? VTYPE_PSEUDO_IS
+ : VTYPE_NONPSEUDO_IS;
+ process_N (spftree, vtype, (void *) is_neigh->neigh_id, dist,
+ depth + 1, family, parent);
+ }
+ }
+ if (lsp->tlv_data.te_is_neighs)
+ {
+ for (ALL_LIST_ELEMENTS_RO (lsp->tlv_data.te_is_neighs, node,
+ te_is_neigh))
+ {
+ if (!memcmp (te_is_neigh->neigh_id, root_sysid, ISIS_SYS_ID_LEN))
+ continue;
+ if (!memcmp (te_is_neigh->neigh_id, null_sysid, ISIS_SYS_ID_LEN))
+ continue;
+ dist = cost + GET_TE_METRIC(te_is_neigh);
+ vtype = LSP_PSEUDO_ID (te_is_neigh->neigh_id) ? VTYPE_PSEUDO_TE_IS
+ : VTYPE_NONPSEUDO_TE_IS;
+ process_N (spftree, vtype, (void *) te_is_neigh->neigh_id, dist,
+ depth + 1, family, parent);
+ }
+ }
+ }
- if (family == AF_INET && lsp->tlv_data.ipv4_ext_reachs)
- {
- prefix.family = AF_INET;
- for (ALL_LIST_ELEMENTS_RO (lsp->tlv_data.ipv4_ext_reachs,
- node, ipreach))
- {
- dist = cost + ipreach->metrics.metric_default;
- vtype = VTYPE_IPREACH_EXTERNAL;
- prefix.u.prefix4 = ipreach->prefix;
- prefix.prefixlen = ip_masklen (ipreach->mask);
- process_N (spftree, vtype, (void *) &prefix, dist, depth + 1,
- adj, family);
- }
- }
- if (family == AF_INET && lsp->tlv_data.te_ipv4_reachs)
- {
- prefix.family = AF_INET;
- for (ALL_LIST_ELEMENTS_RO (lsp->tlv_data.te_ipv4_reachs,
- node, te_ipv4_reach))
- {
- dist = cost + ntohl (te_ipv4_reach->te_metric);
- vtype = VTYPE_IPREACH_TE;
- prefix.u.prefix4 = newprefix2inaddr (&te_ipv4_reach->prefix_start,
- te_ipv4_reach->control);
- prefix.prefixlen = (te_ipv4_reach->control & 0x3F);
- process_N (spftree, vtype, (void *) &prefix, dist, depth + 1,
- adj, family);
- }
- }
+ if (family == AF_INET && lsp->tlv_data.ipv4_int_reachs)
+ {
+ prefix.family = AF_INET;
+ for (ALL_LIST_ELEMENTS_RO (lsp->tlv_data.ipv4_int_reachs, node, ipreach))
+ {
+ dist = cost + ipreach->metrics.metric_default;
+ vtype = VTYPE_IPREACH_INTERNAL;
+ prefix.u.prefix4 = ipreach->prefix;
+ prefix.prefixlen = ip_masklen (ipreach->mask);
+ apply_mask (&prefix);
+ process_N (spftree, vtype, (void *) &prefix, dist, depth + 1,
+ family, parent);
+ }
+ }
+ if (family == AF_INET && lsp->tlv_data.ipv4_ext_reachs)
+ {
+ prefix.family = AF_INET;
+ for (ALL_LIST_ELEMENTS_RO (lsp->tlv_data.ipv4_ext_reachs, node, ipreach))
+ {
+ dist = cost + ipreach->metrics.metric_default;
+ vtype = VTYPE_IPREACH_EXTERNAL;
+ prefix.u.prefix4 = ipreach->prefix;
+ prefix.prefixlen = ip_masklen (ipreach->mask);
+ apply_mask (&prefix);
+ process_N (spftree, vtype, (void *) &prefix, dist, depth + 1,
+ family, parent);
+ }
+ }
+ if (family == AF_INET && lsp->tlv_data.te_ipv4_reachs)
+ {
+ prefix.family = AF_INET;
+ for (ALL_LIST_ELEMENTS_RO (lsp->tlv_data.te_ipv4_reachs,
+ node, te_ipv4_reach))
+ {
+ dist = cost + ntohl (te_ipv4_reach->te_metric);
+ vtype = VTYPE_IPREACH_TE;
+ prefix.u.prefix4 = newprefix2inaddr (&te_ipv4_reach->prefix_start,
+ te_ipv4_reach->control);
+ prefix.prefixlen = (te_ipv4_reach->control & 0x3F);
+ apply_mask (&prefix);
+ process_N (spftree, vtype, (void *) &prefix, dist, depth + 1,
+ family, parent);
+ }
+ }
#ifdef HAVE_IPV6
- if (family == AF_INET6 && lsp->tlv_data.ipv6_reachs)
- {
- prefix.family = AF_INET6;
- for (ALL_LIST_ELEMENTS_RO (lsp->tlv_data.ipv6_reachs,
- node, ip6reach))
- {
- dist = cost + ip6reach->metric;
- vtype = (ip6reach->control_info & CTRL_INFO_DISTRIBUTION) ?
- VTYPE_IP6REACH_EXTERNAL : VTYPE_IP6REACH_INTERNAL;
- prefix.prefixlen = ip6reach->prefix_len;
- memcpy (&prefix.u.prefix6.s6_addr, ip6reach->prefix,
- PSIZE (ip6reach->prefix_len));
- process_N (spftree, vtype, (void *) &prefix, dist, depth + 1,
- adj, family);
- }
- }
-#endif /* HAVE_IPV6 */
+ if (family == AF_INET6 && lsp->tlv_data.ipv6_reachs)
+ {
+ prefix.family = AF_INET6;
+ for (ALL_LIST_ELEMENTS_RO (lsp->tlv_data.ipv6_reachs, node, ip6reach))
+ {
+ dist = cost + ip6reach->metric;
+ vtype = (ip6reach->control_info & CTRL_INFO_DISTRIBUTION) ?
+ VTYPE_IP6REACH_EXTERNAL : VTYPE_IP6REACH_INTERNAL;
+ prefix.prefixlen = ip6reach->prefix_len;
+ memcpy (&prefix.u.prefix6.s6_addr, ip6reach->prefix,
+ PSIZE (ip6reach->prefix_len));
+ apply_mask (&prefix);
+ process_N (spftree, vtype, (void *) &prefix, dist, depth + 1,
+ family, parent);
}
+ }
+#endif /* HAVE_IPV6 */
if (fragnode == NULL)
fragnode = listhead (lsp->lspu.frags);
@@ -689,14 +858,16 @@ lspfragloop:
static int
isis_spf_process_pseudo_lsp (struct isis_spftree *spftree,
- struct isis_lsp *lsp, uint16_t cost,
+ struct isis_lsp *lsp, uint32_t cost,
uint16_t depth, int family,
- struct isis_adjacency *adj)
+ u_char *root_sysid,
+ struct isis_vertex *parent)
{
struct listnode *node, *fragnode = NULL;
struct is_neigh *is_neigh;
struct te_is_neigh *te_is_neigh;
enum vertextype vtype;
+ uint32_t dist;
pseudofragloop:
@@ -707,41 +878,36 @@ pseudofragloop:
return ISIS_WARNING;
}
+#ifdef EXTREME_DEBUG
+ zlog_debug ("ISIS-Spf: process_pseudo_lsp %s",
+ print_sys_hostname(lsp->lsp_header->lsp_id));
+#endif /* EXTREME_DEBUG */
+
+ /* RFC3787 section 4 SHOULD ignore overload bit in pseudo LSPs */
+
if (lsp->tlv_data.is_neighs)
for (ALL_LIST_ELEMENTS_RO (lsp->tlv_data.is_neighs, node, is_neigh))
{
- vtype = LSP_PSEUDO_ID (is_neigh->neigh_id) ? VTYPE_PSEUDO_IS
- : VTYPE_NONPSEUDO_IS;
/* Two way connectivity */
- if (!memcmp (is_neigh->neigh_id, isis->sysid, ISIS_SYS_ID_LEN))
+ if (!memcmp (is_neigh->neigh_id, root_sysid, ISIS_SYS_ID_LEN))
continue;
- if ((depth > 0 || isis_find_vertex
- (spftree->tents, (void *) is_neigh->neigh_id, vtype) == NULL)
- && isis_find_vertex (spftree->paths, (void *) is_neigh->neigh_id,
- vtype) == NULL)
- {
- /* C.2.5 i) */
- isis_spf_add2tent (spftree, vtype, is_neigh->neigh_id, adj,
- cost, depth, family);
- }
+ dist = cost + is_neigh->metrics.metric_default;
+ vtype = LSP_PSEUDO_ID (is_neigh->neigh_id) ? VTYPE_PSEUDO_IS
+ : VTYPE_NONPSEUDO_IS;
+ process_N (spftree, vtype, (void *) is_neigh->neigh_id, dist,
+ depth + 1, family, parent);
}
if (lsp->tlv_data.te_is_neighs)
for (ALL_LIST_ELEMENTS_RO (lsp->tlv_data.te_is_neighs, node, te_is_neigh))
{
- vtype = LSP_PSEUDO_ID (te_is_neigh->neigh_id) ? VTYPE_PSEUDO_TE_IS
- : VTYPE_NONPSEUDO_TE_IS;
/* Two way connectivity */
- if (!memcmp (te_is_neigh->neigh_id, isis->sysid, ISIS_SYS_ID_LEN))
+ if (!memcmp (te_is_neigh->neigh_id, root_sysid, ISIS_SYS_ID_LEN))
continue;
- if ((depth > 0 || isis_find_vertex
- (spftree->tents, (void *) te_is_neigh->neigh_id, vtype) == NULL)
- && isis_find_vertex (spftree->paths, (void *) te_is_neigh->neigh_id,
- vtype) == NULL)
- {
- /* C.2.5 i) */
- isis_spf_add2tent (spftree, vtype, te_is_neigh->neigh_id, adj,
- cost, depth, family);
- }
+ dist = cost + GET_TE_METRIC(te_is_neigh);
+ vtype = LSP_PSEUDO_ID (te_is_neigh->neigh_id) ? VTYPE_PSEUDO_TE_IS
+ : VTYPE_NONPSEUDO_TE_IS;
+ process_N (spftree, vtype, (void *) te_is_neigh->neigh_id, dist,
+ depth + 1, family, parent);
}
if (fragnode == NULL)
@@ -759,10 +925,10 @@ pseudofragloop:
}
static int
-isis_spf_preload_tent (struct isis_spftree *spftree,
- struct isis_area *area, int level, int family)
+isis_spf_preload_tent (struct isis_spftree *spftree, int level,
+ int family, u_char *root_sysid,
+ struct isis_vertex *parent)
{
- struct isis_vertex *vertex;
struct isis_circuit *circuit;
struct listnode *cnode, *anode, *ipnode;
struct isis_adjacency *adj;
@@ -773,15 +939,16 @@ isis_spf_preload_tent (struct isis_spftree *spftree,
struct prefix prefix;
int retval = ISIS_OK;
u_char lsp_id[ISIS_SYS_ID_LEN + 2];
+ static u_char null_lsp_id[ISIS_SYS_ID_LEN + 2];
#ifdef HAVE_IPV6
struct prefix_ipv6 *ipv6;
#endif /* HAVE_IPV6 */
- for (ALL_LIST_ELEMENTS_RO (area->circuit_list, cnode, circuit))
+ for (ALL_LIST_ELEMENTS_RO (spftree->area->circuit_list, cnode, circuit))
{
if (circuit->state != C_STATE_UP)
continue;
- if (!(circuit->circuit_is_type & level))
+ if (!(circuit->is_type & level))
continue;
if (family == AF_INET && !circuit->ip_router)
continue;
@@ -799,8 +966,9 @@ isis_spf_preload_tent (struct isis_spftree *spftree,
{
prefix.u.prefix4 = ipv4->prefix;
prefix.prefixlen = ipv4->prefixlen;
+ apply_mask (&prefix);
isis_spf_add_local (spftree, VTYPE_IPREACH_INTERNAL, &prefix,
- NULL, 0, family);
+ NULL, 0, family, parent);
}
}
#ifdef HAVE_IPV6
@@ -811,8 +979,9 @@ isis_spf_preload_tent (struct isis_spftree *spftree,
{
prefix.prefixlen = ipv6->prefixlen;
prefix.u.prefix6 = ipv6->prefix;
+ apply_mask (&prefix);
isis_spf_add_local (spftree, VTYPE_IP6REACH_INTERNAL,
- &prefix, NULL, 0, family);
+ &prefix, NULL, 0, family, parent);
}
}
#endif /* HAVE_IPV6 */
@@ -832,40 +1001,41 @@ isis_spf_preload_tent (struct isis_spftree *spftree,
level, circuit->interface->name);
continue;
}
- anode = listhead (adj_list);
- while (anode)
+ for (ALL_LIST_ELEMENTS_RO (adj_list, anode, adj))
{
- adj = listgetdata (anode);
if (!speaks (&adj->nlpids, family))
- {
- anode = listnextnode (anode);
continue;
- }
switch (adj->sys_type)
{
case ISIS_SYSTYPE_ES:
isis_spf_add_local (spftree, VTYPE_ES, adj->sysid, adj,
- circuit->te_metric[level - 1], family);
+ circuit->te_metric[level - 1],
+ family, parent);
break;
case ISIS_SYSTYPE_IS:
case ISIS_SYSTYPE_L1_IS:
case ISIS_SYSTYPE_L2_IS:
- vertex =
- isis_spf_add_local (spftree, VTYPE_NONPSEUDO_IS,
- adj->sysid, adj,
- circuit->te_metric[level - 1], family);
+ isis_spf_add_local (spftree,
+ spftree->area->oldmetric ?
+ VTYPE_NONPSEUDO_IS :
+ VTYPE_NONPSEUDO_TE_IS,
+ adj->sysid, adj,
+ circuit->te_metric[level - 1],
+ family, parent);
memcpy (lsp_id, adj->sysid, ISIS_SYS_ID_LEN);
LSP_PSEUDO_ID (lsp_id) = 0;
LSP_FRAGMENT (lsp_id) = 0;
- lsp = lsp_search (lsp_id, area->lspdb[level - 1]);
- if (!lsp)
- zlog_warn ("No lsp found for IS adjacency");
+ lsp = lsp_search (lsp_id, spftree->area->lspdb[level - 1]);
+ if (lsp == NULL || lsp->lsp_header->rem_lifetime == 0)
+ zlog_warn ("ISIS-Spf: No LSP %s found for IS adjacency "
+ "L%d on %s (ID %u)",
+ rawlspid_print (lsp_id), level,
+ circuit->interface->name, circuit->circuit_id);
break;
case ISIS_SYSTYPE_UNKNOWN:
default:
zlog_warn ("isis_spf_preload_tent unknow adj type");
}
- anode = listnextnode (anode);
}
list_delete (adj_list);
/*
@@ -875,23 +1045,36 @@ isis_spf_preload_tent (struct isis_spftree *spftree,
memcpy (lsp_id, circuit->u.bc.l1_desig_is, ISIS_SYS_ID_LEN + 1);
else
memcpy (lsp_id, circuit->u.bc.l2_desig_is, ISIS_SYS_ID_LEN + 1);
- lsp = lsp_search (lsp_id, area->lspdb[level - 1]);
+ /* can happen during DR reboot */
+ if (memcmp (lsp_id, null_lsp_id, ISIS_SYS_ID_LEN + 1) == 0)
+ {
+ if (isis->debugs & DEBUG_SPF_EVENTS)
+ zlog_debug ("ISIS-Spf: No L%d DR on %s (ID %d)",
+ level, circuit->interface->name, circuit->circuit_id);
+ continue;
+ }
adj = isis_adj_lookup (lsp_id, adjdb);
/* if no adj, we are the dis or error */
if (!adj && !circuit->u.bc.is_dr[level - 1])
{
- zlog_warn ("ISIS-Spf: No adjacency found for DR");
- }
- else if (lsp == NULL || lsp->lsp_header->rem_lifetime == 0)
- {
- zlog_warn ("ISIS-Spf: No lsp found for DR");
+ zlog_warn ("ISIS-Spf: No adjacency found from root "
+ "to L%d DR %s on %s (ID %d)",
+ level, rawlspid_print (lsp_id),
+ circuit->interface->name, circuit->circuit_id);
+ continue;
}
- else
+ lsp = lsp_search (lsp_id, spftree->area->lspdb[level - 1]);
+ if (lsp == NULL || lsp->lsp_header->rem_lifetime == 0)
{
- isis_spf_process_pseudo_lsp (spftree, lsp,
- circuit->te_metric[level - 1], 0, family, adj);
-
+ zlog_warn ("ISIS-Spf: No lsp (%p) found from root "
+ "to L%d DR %s on %s (ID %d)",
+ lsp, level, rawlspid_print (lsp_id),
+ circuit->interface->name, circuit->circuit_id);
+ continue;
}
+ isis_spf_process_pseudo_lsp (spftree, lsp,
+ circuit->te_metric[level - 1], 0,
+ family, root_sysid, parent);
}
else if (circuit->circ_type == CIRCUIT_T_P2P)
{
@@ -902,28 +1085,36 @@ isis_spf_preload_tent (struct isis_spftree *spftree,
{
case ISIS_SYSTYPE_ES:
isis_spf_add_local (spftree, VTYPE_ES, adj->sysid, adj,
- circuit->te_metric[level - 1], family);
+ circuit->te_metric[level - 1], family,
+ parent);
break;
case ISIS_SYSTYPE_IS:
case ISIS_SYSTYPE_L1_IS:
case ISIS_SYSTYPE_L2_IS:
if (speaks (&adj->nlpids, family))
- isis_spf_add_local (spftree, VTYPE_NONPSEUDO_IS, adj->sysid,
+ isis_spf_add_local (spftree,
+ spftree->area->oldmetric ?
+ VTYPE_NONPSEUDO_IS :
+ VTYPE_NONPSEUDO_TE_IS,
+ adj->sysid,
adj, circuit->te_metric[level - 1],
- family);
+ family, parent);
break;
case ISIS_SYSTYPE_UNKNOWN:
default:
- zlog_warn ("isis_spf_preload_tent unknow adj type");
+ zlog_warn ("isis_spf_preload_tent unknown adj type");
break;
}
}
+ else if (circuit->circ_type == CIRCUIT_T_LOOPBACK)
+ {
+ continue;
+ }
else
{
zlog_warn ("isis_spf_preload_tent unsupported media");
retval = ISIS_WARNING;
}
-
}
return retval;
@@ -935,25 +1126,30 @@ isis_spf_preload_tent (struct isis_spftree *spftree,
*/
static void
add_to_paths (struct isis_spftree *spftree, struct isis_vertex *vertex,
- struct isis_area *area, int level)
+ int level)
{
-#ifdef EXTREME_DEBUG
u_char buff[BUFSIZ];
-#endif /* EXTREME_DEBUG */
+
+ if (isis_find_vertex (spftree->paths, vertex->N.id, vertex->type))
+ return;
listnode_add (spftree->paths, vertex);
#ifdef EXTREME_DEBUG
- zlog_debug ("ISIS-Spf: added %s %s depth %d dist %d to PATHS",
+ 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),
vertex->depth, vertex->d_N);
#endif /* EXTREME_DEBUG */
+
if (vertex->type > VTYPE_ES)
{
if (listcount (vertex->Adj_N) > 0)
isis_route_create ((struct prefix *) &vertex->N.prefix, vertex->d_N,
- vertex->depth, vertex->Adj_N, area, level);
+ vertex->depth, vertex->Adj_N, spftree->area, level);
else if (isis->debugs & DEBUG_SPF_EVENTS)
- zlog_debug ("ISIS-Spf: no adjacencies do not install route");
+ zlog_debug ("ISIS-Spf: no adjacencies do not install route for "
+ "%s depth %d dist %d", vid2string (vertex, buff),
+ vertex->depth, vertex->d_N);
}
return;
@@ -966,23 +1162,27 @@ init_spt (struct isis_spftree *spftree)
list_delete_all_node (spftree->tents);
list_delete_all_node (spftree->paths);
spftree->tents->del = spftree->paths->del = NULL;
-
return;
}
static int
-isis_run_spf (struct isis_area *area, int level, int family)
+isis_run_spf (struct isis_area *area, int level, int family, u_char *sysid)
{
int retval = ISIS_OK;
struct listnode *node;
struct isis_vertex *vertex;
+ struct isis_vertex *root_vertex;
struct isis_spftree *spftree = NULL;
u_char lsp_id[ISIS_SYS_ID_LEN + 2];
struct isis_lsp *lsp;
- struct isis_adjacency *adj = NULL;
struct route_table *table = NULL;
- struct route_node *rode;
- struct isis_route_info *rinfo;
+ struct timespec time_now;
+ unsigned long long start_time, end_time;
+
+ /* Get time that can't roll backwards. */
+ clock_gettime(CLOCK_MONOTONIC, &time_now);
+ start_time = time_now.tv_sec;
+ start_time = (start_time * 1000000) + (time_now.tv_nsec / 1000);
if (family == AF_INET)
spftree = area->spftree[level - 1];
@@ -990,8 +1190,8 @@ isis_run_spf (struct isis_area *area, int level, int family)
else if (family == AF_INET6)
spftree = area->spftree6[level - 1];
#endif
-
assert (spftree);
+ assert (sysid);
/* Make all routes in current route table inactive. */
if (family == AF_INET)
@@ -1001,71 +1201,66 @@ isis_run_spf (struct isis_area *area, int level, int family)
table = area->route_table6[level - 1];
#endif
- for (rode = route_top (table); rode; rode = route_next (rode))
- {
- if (rode->info == NULL)
- continue;
- rinfo = rode->info;
-
- UNSET_FLAG (rinfo->flag, ISIS_ROUTE_FLAG_ACTIVE);
- }
+ isis_route_invalidate_table (area, table);
/*
* C.2.5 Step 0
*/
init_spt (spftree);
/* a) */
- isis_spf_add_self (spftree, area, level);
+ root_vertex = isis_spf_add_root (spftree, level, sysid);
/* b) */
- retval = isis_spf_preload_tent (spftree, area, level, family);
+ retval = isis_spf_preload_tent (spftree, level, family, sysid, root_vertex);
+ if (retval != ISIS_OK)
+ {
+ zlog_warn ("ISIS-Spf: failed to load TENT SPF-root:%s", print_sys_hostname(sysid));
+ goto out;
+ }
/*
* C.2.7 Step 2
*/
if (listcount (spftree->tents) == 0)
{
- zlog_warn ("ISIS-Spf: TENT is empty");
+ zlog_warn ("ISIS-Spf: TENT is empty SPF-root:%s", print_sys_hostname(sysid));
goto out;
}
while (listcount (spftree->tents) > 0)
{
- /* C.2.7 a) 1) */
node = listhead (spftree->tents);
vertex = listgetdata (node);
- /* C.2.7 a) 2) */
- list_delete_node (spftree->tents, node);
-
- /* C.2.7 a) 3) */
- if (isis_find_vertex (spftree->paths, vertex->N.id, vertex->type))
- continue;
- add_to_paths (spftree, vertex, area, level);
-
- if (vertex->type == VTYPE_PSEUDO_IS ||
- vertex->type == VTYPE_NONPSEUDO_IS ||
- vertex->type == VTYPE_PSEUDO_TE_IS ||
- vertex->type == VTYPE_NONPSEUDO_TE_IS )
- {
- if (listcount(vertex->Adj_N) == 0) {
- continue;
- }
- adj = listgetdata(vertex->Adj_N->head);
+#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 */
+ /* Remove from tent list and add to paths list */
+ list_delete_node (spftree->tents, node);
+ add_to_paths (spftree, vertex, level);
+ switch (vertex->type)
+ {
+ case VTYPE_PSEUDO_IS:
+ case VTYPE_NONPSEUDO_IS:
+ case VTYPE_PSEUDO_TE_IS:
+ case VTYPE_NONPSEUDO_TE_IS:
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)
+ if (lsp && lsp->lsp_header->rem_lifetime != 0)
{
if (LSP_PSEUDO_ID (lsp_id))
{
isis_spf_process_pseudo_lsp (spftree, lsp, vertex->d_N,
- vertex->depth, family, adj);
+ vertex->depth, family, sysid,
+ vertex);
}
else
{
isis_spf_process_lsp (spftree, lsp, vertex->d_N,
- vertex->depth, family, adj);
+ vertex->depth, family, sysid, vertex);
}
}
else
@@ -1073,13 +1268,21 @@ isis_run_spf (struct isis_area *area, int level, int family)
zlog_warn ("ISIS-Spf: No LSP found for %s",
rawlspid_print (lsp_id));
}
+ break;
+ default:;
}
}
out:
- thread_add_event (master, isis_route_validate, area, 0);
- spftree->lastrun = time (NULL);
+ isis_route_validate (area);
spftree->pending = 0;
+ spftree->runcount++;
+ spftree->last_run_timestamp = time (NULL);
+ clock_gettime(CLOCK_MONOTONIC, &time_now);
+ end_time = time_now.tv_sec;
+ end_time = (end_time * 1000000) + (time_now.tv_nsec / 1000);
+ spftree->last_run_duration = end_time - start_time;
+
return retval;
}
@@ -1094,6 +1297,7 @@ isis_run_spf_l1 (struct thread *thread)
assert (area);
area->spftree[0]->t_spf = NULL;
+ area->spftree[0]->pending = 0;
if (!(area->is_type & IS_LEVEL_1))
{
@@ -1107,10 +1311,7 @@ isis_run_spf_l1 (struct thread *thread)
zlog_debug ("ISIS-Spf (%s) L1 SPF needed, periodic SPF", area->area_tag);
if (area->ip_circuits)
- retval = isis_run_spf (area, 1, AF_INET);
-
- THREAD_TIMER_ON (master, area->spftree[0]->t_spf, isis_run_spf_l1, area,
- isis_jitter (PERIODIC_SPF_INTERVAL, 10));
+ retval = isis_run_spf (area, 1, AF_INET, isis->sysid);
return retval;
}
@@ -1125,6 +1326,7 @@ isis_run_spf_l2 (struct thread *thread)
assert (area);
area->spftree[1]->t_spf = NULL;
+ area->spftree[1]->pending = 0;
if (!(area->is_type & IS_LEVEL_2))
{
@@ -1137,10 +1339,7 @@ isis_run_spf_l2 (struct thread *thread)
zlog_debug ("ISIS-Spf (%s) L2 SPF needed, periodic SPF", area->area_tag);
if (area->ip_circuits)
- retval = isis_run_spf (area, 2, AF_INET);
-
- THREAD_TIMER_ON (master, area->spftree[1]->t_spf, isis_run_spf_l2, area,
- isis_jitter (PERIODIC_SPF_INTERVAL, 10));
+ retval = isis_run_spf (area, 2, AF_INET, isis->sysid);
return retval;
}
@@ -1148,53 +1347,40 @@ isis_run_spf_l2 (struct thread *thread)
int
isis_spf_schedule (struct isis_area *area, int level)
{
- int retval = ISIS_OK;
struct isis_spftree *spftree = area->spftree[level - 1];
- time_t diff, now = time (NULL);
+ time_t now = time (NULL);
+ int diff = now - spftree->last_run_timestamp;
- if (spftree->pending)
- return retval;
+ assert (diff >= 0);
+ assert (area->is_type & level);
- diff = now - spftree->lastrun;
-
- /* FIXME: let's wait a minute before doing the SPF */
- if (now - isis->uptime < 60 || isis->uptime == 0)
- {
- if (level == 1)
- THREAD_TIMER_ON (master, spftree->t_spf, isis_run_spf_l1, area, 60);
- else
- THREAD_TIMER_ON (master, spftree->t_spf, isis_run_spf_l2, area, 60);
+ 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);
- spftree->pending = 1;
- return retval;
- }
+ if (spftree->pending)
+ return ISIS_OK;
THREAD_TIMER_OFF (spftree->t_spf);
- if (diff < MINIMUM_SPF_INTERVAL)
- {
- if (level == 1)
- THREAD_TIMER_ON (master, spftree->t_spf, isis_run_spf_l1, area,
- MINIMUM_SPF_INTERVAL - diff);
- else
- THREAD_TIMER_ON (master, spftree->t_spf, isis_run_spf_l2, area,
- MINIMUM_SPF_INTERVAL - diff);
+ /* wait configured min_spf_interval before doing the SPF */
+ if (diff >= area->min_spf_interval[level-1])
+ return isis_run_spf (area, level, AF_INET, isis->sysid);
- spftree->pending = 1;
- }
+ if (level == 1)
+ THREAD_TIMER_ON (master, spftree->t_spf, isis_run_spf_l1, area,
+ area->min_spf_interval[0] - diff);
else
- {
- spftree->pending = 0;
- retval = isis_run_spf (area, level, AF_INET);
- if (level == 1)
- THREAD_TIMER_ON (master, spftree->t_spf, isis_run_spf_l1, area,
- isis_jitter (PERIODIC_SPF_INTERVAL, 10));
- else
- THREAD_TIMER_ON (master, spftree->t_spf, isis_run_spf_l2, area,
- isis_jitter (PERIODIC_SPF_INTERVAL, 10));
- }
+ THREAD_TIMER_ON (master, spftree->t_spf, isis_run_spf_l2, area,
+ area->min_spf_interval[1] - diff);
- return retval;
+ if (isis->debugs & DEBUG_SPF_EVENTS)
+ zlog_debug ("ISIS-Spf (%s) L%d SPF scheduled %d sec from now",
+ area->area_tag, level, area->min_spf_interval[level-1] - diff);
+
+ spftree->pending = 1;
+
+ return ISIS_OK;
}
#ifdef HAVE_IPV6
@@ -1208,11 +1394,12 @@ isis_run_spf6_l1 (struct thread *thread)
assert (area);
area->spftree6[0]->t_spf = NULL;
+ area->spftree6[0]->pending = 0;
if (!(area->is_type & IS_LEVEL_1))
{
if (isis->debugs & DEBUG_SPF_EVENTS)
- zlog_warn ("ISIS-SPF (%s) area does not share level", area->area_tag);
+ zlog_warn ("ISIS-SPF (%s) area does not share level", area->area_tag);
return ISIS_WARNING;
}
@@ -1220,10 +1407,7 @@ isis_run_spf6_l1 (struct thread *thread)
zlog_debug ("ISIS-Spf (%s) L1 SPF needed, periodic SPF", area->area_tag);
if (area->ipv6_circuits)
- retval = isis_run_spf (area, 1, AF_INET6);
-
- THREAD_TIMER_ON (master, area->spftree6[0]->t_spf, isis_run_spf6_l1, area,
- isis_jitter (PERIODIC_SPF_INTERVAL, 10));
+ retval = isis_run_spf (area, 1, AF_INET6, isis->sysid);
return retval;
}
@@ -1238,6 +1422,7 @@ isis_run_spf6_l2 (struct thread *thread)
assert (area);
area->spftree6[1]->t_spf = NULL;
+ area->spftree6[1]->pending = 0;
if (!(area->is_type & IS_LEVEL_2))
{
@@ -1250,10 +1435,7 @@ isis_run_spf6_l2 (struct thread *thread)
zlog_debug ("ISIS-Spf (%s) L2 SPF needed, periodic SPF.", area->area_tag);
if (area->ipv6_circuits)
- retval = isis_run_spf (area, 2, AF_INET6);
-
- THREAD_TIMER_ON (master, area->spftree6[1]->t_spf, isis_run_spf6_l2, area,
- isis_jitter (PERIODIC_SPF_INTERVAL, 10));
+ retval = isis_run_spf (area, 2, AF_INET6, isis->sysid);
return retval;
}
@@ -1263,104 +1445,110 @@ isis_spf_schedule6 (struct isis_area *area, int level)
{
int retval = ISIS_OK;
struct isis_spftree *spftree = area->spftree6[level - 1];
- time_t diff, now = time (NULL);
+ time_t now = time (NULL);
+ time_t diff = now - spftree->last_run_timestamp;
- if (spftree->pending)
- return retval;
+ assert (diff >= 0);
+ assert (area->is_type & level);
- diff = now - spftree->lastrun;
+ 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);
- /* FIXME: let's wait a minute before doing the SPF */
- if (now - isis->uptime < 60 || isis->uptime == 0)
- {
- if (level == 1)
- THREAD_TIMER_ON (master, spftree->t_spf, isis_run_spf6_l1, area, 60);
- else
- THREAD_TIMER_ON (master, spftree->t_spf, isis_run_spf6_l2, area, 60);
+ if (spftree->pending)
+ return ISIS_OK;
- spftree->pending = 1;
- return retval;
- }
-
THREAD_TIMER_OFF (spftree->t_spf);
- if (diff < MINIMUM_SPF_INTERVAL)
- {
- if (level == 1)
- THREAD_TIMER_ON (master, spftree->t_spf, isis_run_spf6_l1, area,
- MINIMUM_SPF_INTERVAL - diff);
- else
- THREAD_TIMER_ON (master, spftree->t_spf, isis_run_spf6_l2, area,
- MINIMUM_SPF_INTERVAL - diff);
+ /* wait configured min_spf_interval before doing the SPF */
+ if (diff >= area->min_spf_interval[level-1])
+ return isis_run_spf (area, level, AF_INET6, isis->sysid);
- spftree->pending = 1;
- }
+ if (level == 1)
+ THREAD_TIMER_ON (master, spftree->t_spf, isis_run_spf6_l1, area,
+ area->min_spf_interval[0] - diff);
else
- {
- spftree->pending = 0;
- retval = isis_run_spf (area, level, AF_INET6);
+ THREAD_TIMER_ON (master, spftree->t_spf, isis_run_spf6_l2, area,
+ area->min_spf_interval[1] - diff);
- if (level == 1)
- THREAD_TIMER_ON (master, spftree->t_spf, isis_run_spf6_l1, area,
- isis_jitter (PERIODIC_SPF_INTERVAL, 10));
- else
- THREAD_TIMER_ON (master, spftree->t_spf, isis_run_spf6_l2, area,
- isis_jitter (PERIODIC_SPF_INTERVAL, 10));
- }
+ if (isis->debugs & DEBUG_SPF_EVENTS)
+ zlog_debug ("ISIS-Spf (%s) L%d SPF scheduled %d sec from now",
+ area->area_tag, level, area->min_spf_interval[level-1] - diff);
+
+ spftree->pending = 1;
return retval;
}
#endif
static void
-isis_print_paths (struct vty *vty, struct list *paths)
+isis_print_paths (struct vty *vty, struct list *paths, u_char *root_sysid)
{
struct listnode *node;
+ struct listnode *anode;
struct isis_vertex *vertex;
- struct isis_dynhn *dyn, *nh_dyn = NULL;
struct isis_adjacency *adj;
-#if 0
u_char buff[255];
-#endif /* 0 */
- vty_out (vty, "System Id Metric Next-Hop"
- " Interface SNPA%s", VTY_NEWLINE);
+ vty_out (vty, "Vertex Type Metric "
+ "Next-Hop Interface Parent%s", VTY_NEWLINE);
+
+ for (ALL_LIST_ELEMENTS_RO (paths, node, vertex)) {
+ if (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", "");
+ } else {
+ int rows = 0;
+ vty_out (vty, "%-20s %-12s %-6u ", vid2string (vertex, buff),
+ vtype2string (vertex->type), vertex->d_N);
+ for (ALL_LIST_ELEMENTS_RO (vertex->Adj_N, anode, adj)) {
+ if (adj) {
+ if (rows) {
+ vty_out (vty, "%s", VTY_NEWLINE);
+ vty_out (vty, "%-20s %-12s %-6s ", "", "", "");
+ }
+ vty_out (vty, "%-20s %-9s ",
+ print_sys_hostname (adj->sysid),
+ adj->circuit->interface->name);
+ ++rows;
+ }
+ }
+ if (rows == 0)
+ vty_out (vty, "%-30s ", "");
+ }
- for (ALL_LIST_ELEMENTS_RO (paths, node, vertex))
- {
- if (vertex->type != VTYPE_NONPSEUDO_IS)
- continue;
- if (memcmp (vertex->N.id, isis->sysid, ISIS_SYS_ID_LEN) == 0)
- {
- vty_out (vty, "%s --%s", host.name?host.name:"",
- VTY_NEWLINE);
+ /* Print list of parents for the ECMP DAG */
+ if (listcount (vertex->parents) > 0) {
+ struct listnode *pnode;
+ struct isis_vertex *pvertex;
+ int rows = 0;
+ for (ALL_LIST_ELEMENTS_RO (vertex->parents, pnode, pvertex)) {
+ if (rows) {
+ vty_out (vty, "%s", VTY_NEWLINE);
+ vty_out (vty, "%-72s", "");
+ }
+ vty_out (vty, "%s(%d)",
+ vid2string (pvertex, buff), pvertex->type);
+ ++rows;
}
- else
- {
- dyn = dynhn_find_by_id ((u_char *) vertex->N.id);
- adj = listgetdata (listhead (vertex->Adj_N));
- if (adj)
- {
- nh_dyn = dynhn_find_by_id (adj->sysid);
- vty_out (vty, "%-20s %-10u %-20s %-11s %-5s%s",
- (dyn != NULL) ? dyn->name.name :
- (const u_char *)rawlspid_print ((u_char *) vertex->N.id),
- vertex->d_N, (nh_dyn != NULL) ? nh_dyn->name.name :
- (const u_char *)rawlspid_print (adj->sysid),
- adj->circuit->interface->name,
- snpa_print (adj->snpa), VTY_NEWLINE);
- }
- else
- {
- vty_out (vty, "%s %u %s", dyn ? dyn->name.name :
- (const u_char *) rawlspid_print (vertex->N.id),
- vertex->d_N, VTY_NEWLINE);
+ } else {
+ vty_out (vty, " NULL ");
+ }
+
+#if 0
+ if (listcount (vertex->children) > 0) {
+ struct listnode *cnode;
+ struct isis_vertex *cvertex;
+ for (ALL_LIST_ELEMENTS_RO (vertex->children, cnode, cvertex)) {
+ vty_out (vty, "%s", VTY_NEWLINE);
+ vty_out (vty, "%-72s", "");
+ vty_out (vty, "%s(%d) ",
+ vid2string (cvertex, buff), cvertex->type);
}
}
-#if 0
- vty_out (vty, "%s %s %u %s", vtype2string (vertex->type),
- vid2string (vertex, buff), vertex->d_N, VTY_NEWLINE);
#endif
+ vty_out (vty, "%s", VTY_NEWLINE);
}
}
@@ -1390,7 +1578,8 @@ DEFUN (show_isis_topology,
{
vty_out (vty, "IS-IS paths to level-%d routers that speak IP%s",
level + 1, VTY_NEWLINE);
- isis_print_paths (vty, area->spftree[level]->paths);
+ isis_print_paths (vty, area->spftree[level]->paths, isis->sysid);
+ vty_out (vty, "%s", VTY_NEWLINE);
}
#ifdef HAVE_IPV6
if (area->ipv6_circuits > 0 && area->spftree6[level]
@@ -1399,10 +1588,13 @@ DEFUN (show_isis_topology,
vty_out (vty,
"IS-IS paths to level-%d routers that speak IPv6%s",
level + 1, VTY_NEWLINE);
- isis_print_paths (vty, area->spftree6[level]->paths);
+ isis_print_paths (vty, area->spftree6[level]->paths, isis->sysid);
+ vty_out (vty, "%s", VTY_NEWLINE);
}
#endif /* HAVE_IPV6 */
}
+
+ vty_out (vty, "%s", VTY_NEWLINE);
}
return CMD_SUCCESS;
@@ -1432,7 +1624,8 @@ DEFUN (show_isis_topology_l1,
{
vty_out (vty, "IS-IS paths to level-1 routers that speak IP%s",
VTY_NEWLINE);
- isis_print_paths (vty, area->spftree[0]->paths);
+ isis_print_paths (vty, area->spftree[0]->paths, isis->sysid);
+ vty_out (vty, "%s", VTY_NEWLINE);
}
#ifdef HAVE_IPV6
if (area->ipv6_circuits > 0 && area->spftree6[0]
@@ -1440,9 +1633,11 @@ DEFUN (show_isis_topology_l1,
{
vty_out (vty, "IS-IS paths to level-1 routers that speak IPv6%s",
VTY_NEWLINE);
- isis_print_paths (vty, area->spftree6[0]->paths);
+ isis_print_paths (vty, area->spftree6[0]->paths, isis->sysid);
+ vty_out (vty, "%s", VTY_NEWLINE);
}
#endif /* HAVE_IPV6 */
+ vty_out (vty, "%s", VTY_NEWLINE);
}
return CMD_SUCCESS;
@@ -1472,7 +1667,8 @@ DEFUN (show_isis_topology_l2,
{
vty_out (vty, "IS-IS paths to level-2 routers that speak IP%s",
VTY_NEWLINE);
- isis_print_paths (vty, area->spftree[1]->paths);
+ isis_print_paths (vty, area->spftree[1]->paths, isis->sysid);
+ vty_out (vty, "%s", VTY_NEWLINE);
}
#ifdef HAVE_IPV6
if (area->ipv6_circuits > 0 && area->spftree6[1]
@@ -1480,9 +1676,11 @@ DEFUN (show_isis_topology_l2,
{
vty_out (vty, "IS-IS paths to level-2 routers that speak IPv6%s",
VTY_NEWLINE);
- isis_print_paths (vty, area->spftree6[1]->paths);
+ isis_print_paths (vty, area->spftree6[1]->paths, isis->sysid);
+ vty_out (vty, "%s", VTY_NEWLINE);
}
#endif /* HAVE_IPV6 */
+ vty_out (vty, "%s", VTY_NEWLINE);
}
return CMD_SUCCESS;