diff options
Diffstat (limited to 'isisd/isis_spf.c')
| -rw-r--r-- | isisd/isis_spf.c | 1124 |
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; |