diff options
Diffstat (limited to 'isisd/isis_spf.c')
| -rw-r--r-- | isisd/isis_spf.c | 2375 |
1 files changed, 1184 insertions, 1191 deletions
diff --git a/isisd/isis_spf.c b/isisd/isis_spf.c index 4b5592c159..615c2eeaa2 100644 --- a/isisd/isis_spf.c +++ b/isisd/isis_spf.c @@ -3,18 +3,18 @@ * The SPT algorithm * * Copyright (C) 2001,2002 Sampo Saaristo - * Tampere University of Technology + * Tampere University of Technology * Institute of Communications Engineering * Copyright (C) 2017 Christian Franke <chris@opensourcerouting.org> * - * This program is free software; you can redistribute it and/or modify it - * under the terms of the GNU General Public Licenseas published by the Free - * Software Foundation; either version 2 of the License, or (at your option) + * This program is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public Licenseas published by the Free + * Software Foundation; either version 2 of the License, or (at your option) * any later version. * - * This program is distributed in the hope that it will be useful,but WITHOUT - * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or - * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for + * This program is distributed in the hope that it will be useful,but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for * more details. * * You should have received a copy of the GNU General Public License along @@ -56,1319 +56,1311 @@ DEFINE_MTYPE_STATIC(ISISD, ISIS_SPF_RUN, "ISIS SPF Run Info"); struct isis_spf_run { - struct isis_area *area; - int level; + struct isis_area *area; + int level; }; /* 7.2.7 */ -static void -remove_excess_adjs (struct list *adjs) +static void remove_excess_adjs(struct list *adjs) { - struct listnode *node, *excess = NULL; - struct isis_adjacency *adj, *candidate = NULL; - int comp; - - for (ALL_LIST_ELEMENTS_RO (adjs, node, adj)) - { - if (excess == NULL) - excess = node; - candidate = listgetdata (excess); - - if (candidate->sys_type < adj->sys_type) - { - excess = node; - continue; - } - if (candidate->sys_type > adj->sys_type) - continue; + struct listnode *node, *excess = NULL; + struct isis_adjacency *adj, *candidate = NULL; + int comp; + + for (ALL_LIST_ELEMENTS_RO(adjs, node, adj)) { + if (excess == NULL) + excess = node; + candidate = listgetdata(excess); + + if (candidate->sys_type < adj->sys_type) { + excess = node; + continue; + } + if (candidate->sys_type > adj->sys_type) + continue; - comp = memcmp (candidate->sysid, adj->sysid, ISIS_SYS_ID_LEN); - if (comp > 0) - { - excess = node; - continue; - } - if (comp < 0) - continue; + comp = memcmp(candidate->sysid, adj->sysid, ISIS_SYS_ID_LEN); + if (comp > 0) { + excess = node; + continue; + } + if (comp < 0) + continue; - if (candidate->circuit->circuit_id > adj->circuit->circuit_id) - { - excess = node; - continue; - } + if (candidate->circuit->circuit_id > adj->circuit->circuit_id) { + excess = node; + continue; + } - if (candidate->circuit->circuit_id < adj->circuit->circuit_id) - continue; + if (candidate->circuit->circuit_id < adj->circuit->circuit_id) + continue; - comp = memcmp (candidate->snpa, adj->snpa, ETH_ALEN); - if (comp > 0) - { - excess = node; - continue; + comp = memcmp(candidate->snpa, adj->snpa, ETH_ALEN); + if (comp > 0) { + excess = node; + continue; + } } - } - list_delete_node (adjs, excess); + list_delete_node(adjs, excess); - return; + return; } -static const char * -vtype2string (enum vertextype vtype) +static const char *vtype2string(enum vertextype vtype) { - switch (vtype) - { - case VTYPE_PSEUDO_IS: - return "pseudo_IS"; - break; - case VTYPE_PSEUDO_TE_IS: - return "pseudo_TE-IS"; - break; - case VTYPE_NONPSEUDO_IS: - return "IS"; - break; - case VTYPE_NONPSEUDO_TE_IS: - return "TE-IS"; - break; - case VTYPE_ES: - return "ES"; - break; - case VTYPE_IPREACH_INTERNAL: - return "IP internal"; - break; - case VTYPE_IPREACH_EXTERNAL: - return "IP external"; - break; - case VTYPE_IPREACH_TE: - return "IP TE"; - break; - case VTYPE_IP6REACH_INTERNAL: - return "IP6 internal"; - break; - case VTYPE_IP6REACH_EXTERNAL: - return "IP6 external"; - break; - default: - return "UNKNOWN"; - } - return NULL; /* Not reached */ + switch (vtype) { + case VTYPE_PSEUDO_IS: + return "pseudo_IS"; + break; + case VTYPE_PSEUDO_TE_IS: + return "pseudo_TE-IS"; + break; + case VTYPE_NONPSEUDO_IS: + return "IS"; + break; + case VTYPE_NONPSEUDO_TE_IS: + return "TE-IS"; + break; + case VTYPE_ES: + return "ES"; + break; + case VTYPE_IPREACH_INTERNAL: + return "IP internal"; + break; + case VTYPE_IPREACH_EXTERNAL: + return "IP external"; + break; + case VTYPE_IPREACH_TE: + return "IP TE"; + break; + case VTYPE_IP6REACH_INTERNAL: + return "IP6 internal"; + break; + case VTYPE_IP6REACH_EXTERNAL: + return "IP6 external"; + break; + default: + return "UNKNOWN"; + } + return NULL; /* Not reached */ } -static const char * -vid2string (struct isis_vertex *vertex, char * buff, int size) +static const char *vid2string(struct isis_vertex *vertex, char *buff, int size) { - if (VTYPE_IS(vertex->type) || VTYPE_ES(vertex->type)) - { - return print_sys_hostname (vertex->N.id); - } - - if (VTYPE_IP(vertex->type)) - { - prefix2str ((struct prefix *) &vertex->N.prefix, buff, size); - return buff; - } - - return "UNKNOWN"; + if (VTYPE_IS(vertex->type) || VTYPE_ES(vertex->type)) { + return print_sys_hostname(vertex->N.id); + } + + if (VTYPE_IP(vertex->type)) { + prefix2str((struct prefix *)&vertex->N.prefix, buff, size); + return buff; + } + + return "UNKNOWN"; } -static struct isis_vertex * -isis_vertex_new (void *id, enum vertextype vtype) +static struct isis_vertex *isis_vertex_new(void *id, enum vertextype vtype) { - struct isis_vertex *vertex; - - vertex = XCALLOC (MTYPE_ISIS_VERTEX, sizeof (struct isis_vertex)); - - vertex->type = vtype; - - if (VTYPE_IS(vtype) || VTYPE_ES(vtype)) - { - memcpy (vertex->N.id, (u_char *) id, ISIS_SYS_ID_LEN + 1); - } - else if (VTYPE_IP(vtype)) - { - memcpy (&vertex->N.prefix, (struct prefix *) id, sizeof (struct prefix)); - } - else - { - zlog_err ("WTF!"); - } - - vertex->Adj_N = list_new (); - vertex->parents = list_new (); - vertex->children = list_new (); - - return vertex; + struct isis_vertex *vertex; + + vertex = XCALLOC(MTYPE_ISIS_VERTEX, sizeof(struct isis_vertex)); + + vertex->type = vtype; + + if (VTYPE_IS(vtype) || VTYPE_ES(vtype)) { + memcpy(vertex->N.id, (u_char *)id, ISIS_SYS_ID_LEN + 1); + } else if (VTYPE_IP(vtype)) { + memcpy(&vertex->N.prefix, (struct prefix *)id, + sizeof(struct prefix)); + } else { + 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) +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; + 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); + memset(vertex, 0, sizeof(struct isis_vertex)); + XFREE(MTYPE_ISIS_VERTEX, vertex); - return; + return; } -static void -isis_vertex_adj_del (struct isis_vertex *vertex, struct isis_adjacency *adj) +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 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 *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; - return tree; + 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; + return tree; } -void -isis_spftree_del (struct isis_spftree *spftree) +void isis_spftree_del(struct isis_spftree *spftree) { - spftree->tents->del = (void (*)(void *)) isis_vertex_del; - list_delete (spftree->tents); - spftree->tents = NULL; + 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; + spftree->paths->del = (void (*)(void *))isis_vertex_del; + list_delete(spftree->paths); + spftree->paths = NULL; - XFREE (MTYPE_ISIS_SPFTREE, spftree); + XFREE(MTYPE_ISIS_SPFTREE, spftree); - return; + return; } -static void -isis_spftree_adj_del (struct isis_spftree *spftree, struct isis_adjacency *adj) +static 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; + 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) +void spftree_area_init(struct isis_area *area) { - if (area->is_type & IS_LEVEL_1) - { - if (area->spftree[0] == NULL) - area->spftree[0] = isis_spftree_new (area); - if (area->spftree6[0] == NULL) - area->spftree6[0] = isis_spftree_new (area); - } - - if (area->is_type & IS_LEVEL_2) - { - if (area->spftree[1] == NULL) - area->spftree[1] = isis_spftree_new (area); - if (area->spftree6[1] == NULL) - area->spftree6[1] = isis_spftree_new (area); - } - - return; + if (area->is_type & IS_LEVEL_1) { + if (area->spftree[0] == NULL) + area->spftree[0] = isis_spftree_new(area); + if (area->spftree6[0] == NULL) + area->spftree6[0] = isis_spftree_new(area); + } + + if (area->is_type & IS_LEVEL_2) { + if (area->spftree[1] == NULL) + area->spftree[1] = isis_spftree_new(area); + if (area->spftree6[1] == NULL) + area->spftree6[1] = isis_spftree_new(area); + } + + return; } -void -spftree_area_del (struct isis_area *area) +void spftree_area_del(struct isis_area *area) { - if (area->is_type & IS_LEVEL_1) - { - if (area->spftree[0] != NULL) - { - isis_spftree_del (area->spftree[0]); - area->spftree[0] = NULL; - } - if (area->spftree6[0]) - { - isis_spftree_del (area->spftree6[0]); - area->spftree6[0] = NULL; - } - } - - if (area->is_type & IS_LEVEL_2) - { - if (area->spftree[1] != NULL) - { - isis_spftree_del (area->spftree[1]); - area->spftree[1] = NULL; - } - if (area->spftree6[1] != NULL) - { - isis_spftree_del (area->spftree6[1]); - area->spftree6[1] = NULL; - } - } - - return; + if (area->is_type & IS_LEVEL_1) { + if (area->spftree[0] != NULL) { + isis_spftree_del(area->spftree[0]); + area->spftree[0] = NULL; + } + if (area->spftree6[0]) { + isis_spftree_del(area->spftree6[0]); + area->spftree6[0] = NULL; + } + } + + if (area->is_type & IS_LEVEL_2) { + if (area->spftree[1] != NULL) { + isis_spftree_del(area->spftree[1]); + area->spftree[1] = NULL; + } + if (area->spftree6[1] != NULL) { + isis_spftree_del(area->spftree6[1]); + area->spftree6[1] = NULL; + } + } + + return; } -void -spftree_area_adj_del (struct isis_area *area, struct isis_adjacency *adj) +void spftree_area_adj_del(struct isis_area *area, struct isis_adjacency *adj) { - if (area->is_type & IS_LEVEL_1) - { - if (area->spftree[0] != NULL) - isis_spftree_adj_del (area->spftree[0], adj); - if (area->spftree6[0] != NULL) - isis_spftree_adj_del (area->spftree6[0], adj); - } - - if (area->is_type & IS_LEVEL_2) - { - if (area->spftree[1] != NULL) - isis_spftree_adj_del (area->spftree[1], adj); - if (area->spftree6[1] != NULL) - isis_spftree_adj_del (area->spftree6[1], adj); - } - - return; + if (area->is_type & IS_LEVEL_1) { + if (area->spftree[0] != NULL) + isis_spftree_adj_del(area->spftree[0], adj); + if (area->spftree6[0] != NULL) + isis_spftree_adj_del(area->spftree6[0], adj); + } + + if (area->is_type & IS_LEVEL_2) { + if (area->spftree[1] != NULL) + isis_spftree_adj_del(area->spftree[1], adj); + if (area->spftree6[1] != NULL) + isis_spftree_adj_del(area->spftree6[1], adj); + } + + return; } -/* - * Find the system LSP: returns the LSP in our LSP database +/* + * 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) +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; + 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 struct isis_vertex * -isis_spf_add_root (struct isis_spftree *spftree, u_char *sysid) +static struct isis_vertex *isis_spf_add_root(struct isis_spftree *spftree, + u_char *sysid) { - struct isis_vertex *vertex; - struct isis_lsp *lsp; + struct isis_vertex *vertex; + struct isis_lsp *lsp; #ifdef EXTREME_DEBUG - char buff[PREFIX2STR_BUFFER]; + char buff[PREFIX2STR_BUFFER]; #endif /* EXTREME_DEBUG */ - u_char id[ISIS_SYS_ID_LEN + 1]; + u_char id[ISIS_SYS_ID_LEN + 1]; - memcpy(id, sysid, ISIS_SYS_ID_LEN); - LSP_PSEUDO_ID(id) = 0; + memcpy(id, sysid, ISIS_SYS_ID_LEN); + LSP_PSEUDO_ID(id) = 0; - lsp = isis_root_system_lsp (spftree->area, spftree->level, sysid); - if (lsp == NULL) - zlog_warn ("ISIS-Spf: could not find own l%d LSP!", spftree->level); + lsp = isis_root_system_lsp(spftree->area, spftree->level, sysid); + if (lsp == NULL) + zlog_warn("ISIS-Spf: could not find own l%d LSP!", + spftree->level); - vertex = isis_vertex_new (id, spftree->area->oldmetric ? VTYPE_NONPSEUDO_IS - : VTYPE_NONPSEUDO_TE_IS); - listnode_add (spftree->paths, vertex); + vertex = isis_vertex_new(id, + spftree->area->oldmetric + ? VTYPE_NONPSEUDO_IS + : VTYPE_NONPSEUDO_TE_IS); + listnode_add(spftree->paths, vertex); #ifdef EXTREME_DEBUG - zlog_debug ("ISIS-Spf: added this IS %s %s depth %d dist %d to PATHS", - vtype2string (vertex->type), vid2string (vertex, buff, sizeof (buff)), - vertex->depth, vertex->d_N); + zlog_debug("ISIS-Spf: added this IS %s %s depth %d dist %d to PATHS", + vtype2string(vertex->type), + vid2string(vertex, buff, sizeof(buff)), vertex->depth, + vertex->d_N); #endif /* EXTREME_DEBUG */ - return vertex; + return vertex; } -static struct isis_vertex * -isis_find_vertex (struct list *list, void *id, enum vertextype vtype) +static struct isis_vertex *isis_find_vertex(struct list *list, void *id, + enum vertextype vtype) { - struct listnode *node; - struct isis_vertex *vertex; - struct prefix *p1, *p2; - - for (ALL_LIST_ELEMENTS_RO (list, node, vertex)) - { - if (vertex->type != vtype) - continue; - if (VTYPE_IS(vertex->type) || VTYPE_ES(vertex->type)) - { - if (memcmp ((u_char *) id, vertex->N.id, ISIS_SYS_ID_LEN + 1) == 0) - return vertex; - } - if (VTYPE_IP(vertex->type)) - { - p1 = (struct prefix *) id; - p2 = (struct prefix *) &vertex->N.id; - if (p1->family == p2->family - && p1->prefixlen == p2->prefixlen - && !memcmp(&p1->u.prefix, &p2->u.prefix, PSIZE (p1->prefixlen))) - { - return vertex; - } - } - } - - return NULL; + struct listnode *node; + struct isis_vertex *vertex; + struct prefix *p1, *p2; + + for (ALL_LIST_ELEMENTS_RO(list, node, vertex)) { + if (vertex->type != vtype) + continue; + if (VTYPE_IS(vertex->type) || VTYPE_ES(vertex->type)) { + if (memcmp((u_char *)id, vertex->N.id, + ISIS_SYS_ID_LEN + 1) + == 0) + return vertex; + } + if (VTYPE_IP(vertex->type)) { + p1 = (struct prefix *)id; + p2 = (struct prefix *)&vertex->N.id; + if (p1->family == p2->family + && p1->prefixlen == p2->prefixlen + && !memcmp(&p1->u.prefix, &p2->u.prefix, + PSIZE(p1->prefixlen))) { + return vertex; + } + } + } + + return NULL; } /* * Compares vertizes for sorting in the TENT list. Returns true * if candidate should be considered before current, false otherwise. */ -static bool -tent_cmp (struct isis_vertex *current, struct isis_vertex *candidate) +static bool tent_cmp(struct isis_vertex *current, struct isis_vertex *candidate) { - if (current->d_N > candidate->d_N) - return true; + if (current->d_N > candidate->d_N) + return true; - if (current->d_N == candidate->d_N - && current->type > candidate->type) - return true; + if (current->d_N == candidate->d_N && current->type > candidate->type) + return true; - return false; + return false; } /* * Add a vertex to TENT sorted by cost and by vertextype on tie break situation */ -static struct isis_vertex * -isis_spf_add2tent (struct isis_spftree *spftree, enum vertextype vtype, - void *id, uint32_t cost, int depth, - struct isis_adjacency *adj, struct isis_vertex *parent) +static struct isis_vertex *isis_spf_add2tent(struct isis_spftree *spftree, + enum vertextype vtype, void *id, + uint32_t cost, int depth, + struct isis_adjacency *adj, + struct isis_vertex *parent) { - struct isis_vertex *vertex, *v; - struct listnode *node; - struct isis_adjacency *parent_adj; + struct isis_vertex *vertex, *v; + struct listnode *node; + struct isis_adjacency *parent_adj; #ifdef EXTREME_DEBUG - char buff[PREFIX2STR_BUFFER]; + char buff[PREFIX2STR_BUFFER]; #endif - assert (isis_find_vertex (spftree->paths, id, vtype) == NULL); - assert (isis_find_vertex (spftree->tents, id, vtype) == NULL); - vertex = isis_vertex_new (id, vtype); - vertex->d_N = cost; - vertex->depth = depth; - - 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); - } + 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 (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 %s depth %d dist %d adjcount %d", - print_sys_hostname (vertex->N.id), - vtype2string (vertex->type), vid2string (vertex, buff, sizeof (buff)), - vertex->depth, vertex->d_N, listcount(vertex->Adj_N)); + zlog_debug( + "ISIS-Spf: add to TENT %s %s %s depth %d dist %d adjcount %d", + print_sys_hostname(vertex->N.id), vtype2string(vertex->type), + vid2string(vertex, buff, sizeof(buff)), vertex->depth, + vertex->d_N, listcount(vertex->Adj_N)); #endif /* EXTREME_DEBUG */ - if (list_isempty (spftree->tents)) - { - listnode_add (spftree->tents, vertex); - return vertex; - } - - /* XXX: This cant use the standard ALL_LIST_ELEMENTS macro */ - for (node = listhead (spftree->tents); node; node = listnextnode (node)) - { - v = listgetdata (node); - if (tent_cmp(v, vertex)) - { - listnode_add_before (spftree->tents, node, vertex); - break; - } - } - - if (node == NULL) - listnode_add (spftree->tents, vertex); - - return vertex; -} + if (list_isempty(spftree->tents)) { + listnode_add(spftree->tents, vertex); + return vertex; + } -static void -isis_spf_add_local (struct isis_spftree *spftree, enum vertextype vtype, - void *id, struct isis_adjacency *adj, uint32_t cost, - struct isis_vertex *parent) -{ - struct isis_vertex *vertex; + /* XXX: This cant use the standard ALL_LIST_ELEMENTS macro */ + for (node = listhead(spftree->tents); node; node = listnextnode(node)) { + v = listgetdata(node); + if (tent_cmp(v, vertex)) { + listnode_add_before(spftree->tents, node, vertex); + break; + } + } - vertex = isis_find_vertex (spftree->tents, id, vtype); + if (node == NULL) + listnode_add(spftree->tents, vertex); - if (vertex) - { - /* C.2.5 c) */ - if (vertex->d_N == cost) - { - if (adj) - listnode_add (vertex->Adj_N, adj); - /* 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; - } - else if (vertex->d_N < cost) - { - /* e) do nothing */ - return; + return vertex; +} + +static void isis_spf_add_local(struct isis_spftree *spftree, + enum vertextype vtype, void *id, + struct isis_adjacency *adj, uint32_t cost, + struct isis_vertex *parent) +{ + struct isis_vertex *vertex; + + vertex = isis_find_vertex(spftree->tents, id, vtype); + + if (vertex) { + /* C.2.5 c) */ + if (vertex->d_N == cost) { + if (adj) + listnode_add(vertex->Adj_N, adj); + /* 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; + } else if (vertex->d_N < cost) { + /* e) do nothing */ + return; + } 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); + } } - 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); - } - } - - isis_spf_add2tent (spftree, vtype, id, cost, 1, adj, parent); - return; + + isis_spf_add2tent(spftree, vtype, id, cost, 1, adj, parent); + return; } -static void -process_N (struct isis_spftree *spftree, enum vertextype vtype, void *id, - uint32_t dist, uint16_t depth, - struct isis_vertex *parent) +static void process_N(struct isis_spftree *spftree, enum vertextype vtype, + void *id, uint32_t dist, uint16_t depth, + struct isis_vertex *parent) { - struct isis_vertex *vertex; + struct isis_vertex *vertex; #ifdef EXTREME_DEBUG - char buff[PREFIX2STR_BUFFER]; + char buff[PREFIX2STR_BUFFER]; #endif - assert (spftree && parent); - - /* RFC3787 section 5.1 */ - if (spftree->area->newmetric == 1) - { - if (dist > MAX_WIDE_PATH_METRIC) - return; - } - /* C.2.6 b) */ - else if (spftree->area->oldmetric == 1) - { - if (dist > MAX_NARROW_PATH_METRIC) - return; - } - - /* c) */ - vertex = isis_find_vertex (spftree->paths, id, vtype); - if (vertex) - { + assert(spftree && parent); + + /* RFC3787 section 5.1 */ + if (spftree->area->newmetric == 1) { + if (dist > MAX_WIDE_PATH_METRIC) + return; + } + /* C.2.6 b) */ + else if (spftree->area->oldmetric == 1) { + if (dist > MAX_NARROW_PATH_METRIC) + return; + } + + /* c) */ + vertex = isis_find_vertex(spftree->paths, id, vtype); + if (vertex) { #ifdef EXTREME_DEBUG - zlog_debug ("ISIS-Spf: process_N %s %s %s dist %d already found from PATH", - print_sys_hostname (vertex->N.id), - vtype2string (vtype), vid2string (vertex, buff, sizeof (buff)), dist); + zlog_debug( + "ISIS-Spf: process_N %s %s %s dist %d already found from PATH", + print_sys_hostname(vertex->N.id), vtype2string(vtype), + vid2string(vertex, buff, sizeof(buff)), dist); #endif /* EXTREME_DEBUG */ - assert (dist >= vertex->d_N); - return; - } - - vertex = isis_find_vertex (spftree->tents, id, vtype); - /* d) */ - if (vertex) - { - /* 1) */ + assert(dist >= vertex->d_N); + return; + } + + vertex = isis_find_vertex(spftree->tents, id, vtype); + /* d) */ + if (vertex) { +/* 1) */ #ifdef EXTREME_DEBUG - zlog_debug ("ISIS-Spf: process_N %s %s %s dist %d parent %s adjcount %d", - print_sys_hostname (vertex->N.id), - vtype2string (vtype), vid2string (vertex, buff, sizeof (buff)), dist, - (parent ? print_sys_hostname (parent->N.id) : "null"), - (parent ? listcount (parent->Adj_N) : 0)); + zlog_debug( + "ISIS-Spf: process_N %s %s %s dist %d parent %s adjcount %d", + print_sys_hostname(vertex->N.id), vtype2string(vtype), + vid2string(vertex, buff, sizeof(buff)), dist, + (parent ? print_sys_hostname(parent->N.id) : "null"), + (parent ? listcount(parent->Adj_N) : 0)); #endif /* EXTREME_DEBUG */ - if (vertex->d_N == dist) - { - struct listnode *node; - struct isis_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; - } - else if (vertex->d_N < dist) - { - return; - /* 4) */ - } - 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); + if (vertex->d_N == dist) { + 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; + } else if (vertex->d_N < dist) { + return; + /* 4) */ + } 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); + } } - } #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")); + zlog_debug("ISIS-Spf: process_N add2tent %s %s dist %d parent %s", + print_sys_hostname(id), vtype2string(vtype), dist, + (parent ? print_sys_hostname(parent->N.id) : "null")); #endif /* EXTREME_DEBUG */ - isis_spf_add2tent (spftree, vtype, id, dist, depth, NULL, parent); - return; + isis_spf_add2tent(spftree, vtype, id, dist, depth, NULL, parent); + return; } /* * C.2.6 Step 1 */ -static int -isis_spf_process_lsp (struct isis_spftree *spftree, struct isis_lsp *lsp, - uint32_t cost, uint16_t depth, - u_char *root_sysid, struct isis_vertex *parent) +static int isis_spf_process_lsp(struct isis_spftree *spftree, + struct isis_lsp *lsp, uint32_t cost, + uint16_t depth, u_char *root_sysid, + struct isis_vertex *parent) { - bool pseudo_lsp = LSP_PSEUDO_ID(lsp->lsp_header->lsp_id); - struct listnode *node, *fragnode = NULL; - uint32_t dist; - struct is_neigh *is_neigh; - struct te_is_neigh *te_is_neigh; - struct ipv4_reachability *ipreach; - struct te_ipv4_reachability *te_ipv4_reach; - enum vertextype vtype; - struct prefix prefix; - struct ipv6_reachability *ip6reach; - static const u_char null_sysid[ISIS_SYS_ID_LEN]; - struct mt_router_info *mt_router_info = NULL; - - if (spftree->mtid != ISIS_MT_IPV4_UNICAST) - mt_router_info = tlvs_lookup_mt_router_info(&lsp->tlv_data, spftree->mtid); - - if (!pseudo_lsp - && (spftree->mtid == ISIS_MT_IPV4_UNICAST && !speaks(lsp->tlv_data.nlpids, spftree->family)) - && !mt_router_info) - return ISIS_OK; + bool pseudo_lsp = LSP_PSEUDO_ID(lsp->lsp_header->lsp_id); + struct listnode *node, *fragnode = NULL; + uint32_t dist; + struct is_neigh *is_neigh; + struct te_is_neigh *te_is_neigh; + struct ipv4_reachability *ipreach; + struct te_ipv4_reachability *te_ipv4_reach; + enum vertextype vtype; + struct prefix prefix; + struct ipv6_reachability *ip6reach; + static const u_char null_sysid[ISIS_SYS_ID_LEN]; + struct mt_router_info *mt_router_info = NULL; + + if (spftree->mtid != ISIS_MT_IPV4_UNICAST) + mt_router_info = tlvs_lookup_mt_router_info(&lsp->tlv_data, + spftree->mtid); + + if (!pseudo_lsp && (spftree->mtid == ISIS_MT_IPV4_UNICAST + && !speaks(lsp->tlv_data.nlpids, spftree->family)) + && !mt_router_info) + return ISIS_OK; lspfragloop: - if (lsp->lsp_header->seq_num == 0) - { - zlog_warn ("isis_spf_process_lsp(): lsp with 0 seq_num - ignore"); - return ISIS_WARNING; - } + if (lsp->lsp_header->seq_num == 0) { + 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)); + zlog_debug("ISIS-Spf: process_lsp %s", + print_sys_hostname(lsp->lsp_header->lsp_id)); #endif /* EXTREME_DEBUG */ - /* RFC3787 section 4 SHOULD ignore overload bit in pseudo LSPs */ - if (pseudo_lsp - || (spftree->mtid == ISIS_MT_IPV4_UNICAST && !ISIS_MASK_LSP_OL_BIT (lsp->lsp_header->lsp_bits)) - || (mt_router_info && !mt_router_info->overload)) - - { - if (pseudo_lsp || spftree->mtid == ISIS_MT_IPV4_UNICAST) - { - 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 (!pseudo_lsp && !memcmp (is_neigh->neigh_id, null_sysid, ISIS_SYS_ID_LEN)) - continue; - dist = cost + is_neigh->metrics.metric_default; - process_N (spftree, LSP_PSEUDO_ID(is_neigh->neigh_id) ? VTYPE_PSEUDO_IS - : VTYPE_NONPSEUDO_IS, - (void *) is_neigh->neigh_id, dist, depth + 1, parent); - } - } - - struct list *te_is_neighs = NULL; - if (pseudo_lsp || spftree->mtid == ISIS_MT_IPV4_UNICAST) - { - te_is_neighs = lsp->tlv_data.te_is_neighs; - } - else - { - struct tlv_mt_neighbors *mt_neighbors; - mt_neighbors = tlvs_lookup_mt_neighbors(&lsp->tlv_data, spftree->mtid); - if (mt_neighbors) - te_is_neighs = mt_neighbors->list; - } - for (ALL_LIST_ELEMENTS_RO (te_is_neighs, node, te_is_neigh)) - { - if (!memcmp (te_is_neigh->neigh_id, root_sysid, ISIS_SYS_ID_LEN)) - continue; - if (!pseudo_lsp && !memcmp (te_is_neigh->neigh_id, null_sysid, ISIS_SYS_ID_LEN)) - continue; - dist = cost + GET_TE_METRIC(te_is_neigh); - process_N (spftree, LSP_PSEUDO_ID(te_is_neigh->neigh_id) ? VTYPE_PSEUDO_TE_IS - : VTYPE_NONPSEUDO_TE_IS, - (void *) te_is_neigh->neigh_id, dist, depth + 1, parent); - } - } - - if (!pseudo_lsp - && spftree->family == AF_INET - && spftree->mtid == ISIS_MT_IPV4_UNICAST) - { - struct list *reachs[] = {lsp->tlv_data.ipv4_int_reachs, - lsp->tlv_data.ipv4_ext_reachs}; - - prefix.family = AF_INET; - for (unsigned int i = 0; i < array_size(reachs); i++) - { - vtype = (reachs[i] == lsp->tlv_data.ipv4_int_reachs) ? VTYPE_IPREACH_INTERNAL - : VTYPE_IPREACH_EXTERNAL; - for (ALL_LIST_ELEMENTS_RO (reachs[i], node, ipreach)) - { - dist = cost + ipreach->metrics.metric_default; - prefix.u.prefix4 = ipreach->prefix; - prefix.prefixlen = ip_masklen (ipreach->mask); - apply_mask (&prefix); - process_N (spftree, vtype, (void *) &prefix, dist, depth + 1, - parent); - } - } - } - - if (!pseudo_lsp && spftree->family == AF_INET) - { - struct list *ipv4reachs = NULL; - - if (spftree->mtid == ISIS_MT_IPV4_UNICAST) - { - ipv4reachs = lsp->tlv_data.te_ipv4_reachs; - } - else - { - struct tlv_mt_ipv4_reachs *mt_reachs; - mt_reachs = tlvs_lookup_mt_ipv4_reachs(&lsp->tlv_data, spftree->mtid); - if (mt_reachs) - ipv4reachs = mt_reachs->list; - } - - prefix.family = AF_INET; - for (ALL_LIST_ELEMENTS_RO (ipv4reachs, node, te_ipv4_reach)) - { - assert ((te_ipv4_reach->control & 0x3F) <= IPV4_MAX_BITLEN); - - dist = cost + ntohl (te_ipv4_reach->te_metric); - 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_IPREACH_TE, (void *) &prefix, dist, depth + 1, - parent); - } - } - - if (!pseudo_lsp - && spftree->family == AF_INET6) - { - struct list *ipv6reachs = NULL; - - if (spftree->mtid == ISIS_MT_IPV4_UNICAST) - { - ipv6reachs = lsp->tlv_data.ipv6_reachs; - } - else - { - struct tlv_mt_ipv6_reachs *mt_reachs; - mt_reachs = tlvs_lookup_mt_ipv6_reachs(&lsp->tlv_data, spftree->mtid); - if (mt_reachs) - ipv6reachs = mt_reachs->list; - } - - prefix.family = AF_INET6; - for (ALL_LIST_ELEMENTS_RO (ipv6reachs, node, ip6reach)) - { - assert (ip6reach->prefix_len <= IPV6_MAX_BITLEN); - - dist = cost + ntohl(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, - parent); - } - } - - if (fragnode == NULL) - fragnode = listhead (lsp->lspu.frags); - else - fragnode = listnextnode (fragnode); - - if (fragnode) - { - lsp = listgetdata (fragnode); - goto lspfragloop; - } - - return ISIS_OK; -} + /* RFC3787 section 4 SHOULD ignore overload bit in pseudo LSPs */ + if (pseudo_lsp || (spftree->mtid == ISIS_MT_IPV4_UNICAST + && !ISIS_MASK_LSP_OL_BIT(lsp->lsp_header->lsp_bits)) + || (mt_router_info && !mt_router_info->overload)) -static int -isis_spf_preload_tent (struct isis_spftree *spftree, - u_char *root_sysid, - struct isis_vertex *parent) -{ - struct isis_circuit *circuit; - struct listnode *cnode, *anode, *ipnode; - struct isis_adjacency *adj; - struct isis_lsp *lsp; - struct list *adj_list; - struct list *adjdb; - struct prefix_ipv4 *ipv4; - 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]; - struct prefix_ipv6 *ipv6; - struct isis_circuit_mt_setting *circuit_mt; - - for (ALL_LIST_ELEMENTS_RO (spftree->area->circuit_list, cnode, circuit)) - { - circuit_mt = circuit_lookup_mt_setting(circuit, spftree->mtid); - if (circuit_mt && !circuit_mt->enabled) - continue; - if (circuit->state != C_STATE_UP) - continue; - if (!(circuit->is_type & spftree->level)) - continue; - if (spftree->family == AF_INET && !circuit->ip_router) - continue; - if (spftree->family == AF_INET6 && !circuit->ipv6_router) - continue; - /* - * Add IP(v6) addresses of this circuit - */ - if (spftree->family == AF_INET) { - prefix.family = AF_INET; - for (ALL_LIST_ELEMENTS_RO (circuit->ip_addrs, ipnode, ipv4)) - { - prefix.u.prefix4 = ipv4->prefix; - prefix.prefixlen = ipv4->prefixlen; - apply_mask (&prefix); - isis_spf_add_local (spftree, VTYPE_IPREACH_INTERNAL, &prefix, - NULL, 0, parent); - } + if (pseudo_lsp || spftree->mtid == ISIS_MT_IPV4_UNICAST) { + 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 (!pseudo_lsp + && !memcmp(is_neigh->neigh_id, null_sysid, + ISIS_SYS_ID_LEN)) + continue; + dist = cost + is_neigh->metrics.metric_default; + process_N(spftree, + LSP_PSEUDO_ID(is_neigh->neigh_id) + ? VTYPE_PSEUDO_IS + : VTYPE_NONPSEUDO_IS, + (void *)is_neigh->neigh_id, dist, + depth + 1, parent); + } + } + + struct list *te_is_neighs = NULL; + if (pseudo_lsp || spftree->mtid == ISIS_MT_IPV4_UNICAST) { + te_is_neighs = lsp->tlv_data.te_is_neighs; + } else { + struct tlv_mt_neighbors *mt_neighbors; + mt_neighbors = tlvs_lookup_mt_neighbors(&lsp->tlv_data, + spftree->mtid); + if (mt_neighbors) + te_is_neighs = mt_neighbors->list; + } + for (ALL_LIST_ELEMENTS_RO(te_is_neighs, node, te_is_neigh)) { + if (!memcmp(te_is_neigh->neigh_id, root_sysid, + ISIS_SYS_ID_LEN)) + continue; + if (!pseudo_lsp + && !memcmp(te_is_neigh->neigh_id, null_sysid, + ISIS_SYS_ID_LEN)) + continue; + dist = cost + GET_TE_METRIC(te_is_neigh); + process_N(spftree, + LSP_PSEUDO_ID(te_is_neigh->neigh_id) + ? VTYPE_PSEUDO_TE_IS + : VTYPE_NONPSEUDO_TE_IS, + (void *)te_is_neigh->neigh_id, dist, + depth + 1, parent); + } } - if (spftree->family == AF_INET6) - { - prefix.family = AF_INET6; - for (ALL_LIST_ELEMENTS_RO (circuit->ipv6_non_link, ipnode, ipv6)) - { - prefix.prefixlen = ipv6->prefixlen; - prefix.u.prefix6 = ipv6->prefix; - apply_mask (&prefix); - isis_spf_add_local (spftree, VTYPE_IP6REACH_INTERNAL, - &prefix, NULL, 0, parent); - } + + if (!pseudo_lsp && spftree->family == AF_INET + && spftree->mtid == ISIS_MT_IPV4_UNICAST) { + struct list *reachs[] = {lsp->tlv_data.ipv4_int_reachs, + lsp->tlv_data.ipv4_ext_reachs}; + + prefix.family = AF_INET; + for (unsigned int i = 0; i < array_size(reachs); i++) { + vtype = (reachs[i] == lsp->tlv_data.ipv4_int_reachs) + ? VTYPE_IPREACH_INTERNAL + : VTYPE_IPREACH_EXTERNAL; + for (ALL_LIST_ELEMENTS_RO(reachs[i], node, ipreach)) { + dist = cost + ipreach->metrics.metric_default; + prefix.u.prefix4 = ipreach->prefix; + prefix.prefixlen = ip_masklen(ipreach->mask); + apply_mask(&prefix); + process_N(spftree, vtype, (void *)&prefix, dist, + depth + 1, parent); + } + } } - if (circuit->circ_type == CIRCUIT_T_BROADCAST) - { - /* - * Add the adjacencies - */ - adj_list = list_new (); - adjdb = circuit->u.bc.adjdb[spftree->level - 1]; - isis_adj_build_up_list (adjdb, adj_list); - if (listcount (adj_list) == 0) - { - list_delete (adj_list); - if (isis->debugs & DEBUG_SPF_EVENTS) - zlog_debug ("ISIS-Spf: no L%d adjacencies on circuit %s", - spftree->level, circuit->interface->name); - continue; - } - for (ALL_LIST_ELEMENTS_RO (adj_list, anode, adj)) - { - if (!adj_has_mt(adj, spftree->mtid)) - continue; - if (spftree->mtid == ISIS_MT_IPV4_UNICAST && !speaks (&adj->nlpids, spftree->family)) - continue; - switch (adj->sys_type) - { - case ISIS_SYSTYPE_ES: - memcpy(lsp_id, adj->sysid, ISIS_SYS_ID_LEN); - LSP_PSEUDO_ID (lsp_id) = 0; - isis_spf_add_local (spftree, VTYPE_ES, lsp_id, adj, - circuit->te_metric[spftree->level - 1], - parent); - break; - case ISIS_SYSTYPE_IS: - case ISIS_SYSTYPE_L1_IS: - case ISIS_SYSTYPE_L2_IS: - memcpy (lsp_id, adj->sysid, ISIS_SYS_ID_LEN); - LSP_PSEUDO_ID (lsp_id) = 0; - LSP_FRAGMENT (lsp_id) = 0; - isis_spf_add_local (spftree, - spftree->area->oldmetric ? VTYPE_NONPSEUDO_IS - : VTYPE_NONPSEUDO_TE_IS, - lsp_id, adj, - circuit->te_metric[spftree->level - 1], - parent); - lsp = lsp_search (lsp_id, spftree->area->lspdb[spftree->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), spftree->level, - circuit->interface->name, circuit->circuit_id); - break; - case ISIS_SYSTYPE_UNKNOWN: - default: - zlog_warn ("isis_spf_preload_tent unknow adj type"); + + if (!pseudo_lsp && spftree->family == AF_INET) { + struct list *ipv4reachs = NULL; + + if (spftree->mtid == ISIS_MT_IPV4_UNICAST) { + ipv4reachs = lsp->tlv_data.te_ipv4_reachs; + } else { + struct tlv_mt_ipv4_reachs *mt_reachs; + mt_reachs = tlvs_lookup_mt_ipv4_reachs(&lsp->tlv_data, + spftree->mtid); + if (mt_reachs) + ipv4reachs = mt_reachs->list; + } + + prefix.family = AF_INET; + for (ALL_LIST_ELEMENTS_RO(ipv4reachs, node, te_ipv4_reach)) { + assert((te_ipv4_reach->control & 0x3F) + <= IPV4_MAX_BITLEN); + + dist = cost + ntohl(te_ipv4_reach->te_metric); + 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_IPREACH_TE, (void *)&prefix, + dist, depth + 1, parent); } - } - list_delete (adj_list); - /* - * Add the pseudonode - */ - if (spftree->level == 1) - 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); - /* 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)", - spftree->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[spftree->level - 1]) - { - zlog_warn ("ISIS-Spf: No adjacency found from root " - "to L%d DR %s on %s (ID %d)", - spftree->level, rawlspid_print (lsp_id), - circuit->interface->name, circuit->circuit_id); - continue; - } - lsp = lsp_search (lsp_id, spftree->area->lspdb[spftree->level - 1]); - if (lsp == NULL || lsp->lsp_header->rem_lifetime == 0) - { - zlog_warn ("ISIS-Spf: No lsp (%p) found from root " - "to L%d DR %s on %s (ID %d)", - (void *)lsp, spftree->level, rawlspid_print (lsp_id), - circuit->interface->name, circuit->circuit_id); - continue; - } - isis_spf_process_lsp (spftree, lsp, - circuit->te_metric[spftree->level - 1], 0, - root_sysid, parent); } - else if (circuit->circ_type == CIRCUIT_T_P2P) - { - adj = circuit->u.p2p.neighbor; - if (!adj) - continue; - if (!adj_has_mt(adj, spftree->mtid)) - continue; - switch (adj->sys_type) - { - case ISIS_SYSTYPE_ES: - memcpy (lsp_id, adj->sysid, ISIS_SYS_ID_LEN); - LSP_PSEUDO_ID (lsp_id) = 0; - isis_spf_add_local (spftree, VTYPE_ES, lsp_id, adj, - circuit->te_metric[spftree->level - 1], - parent); - break; - case ISIS_SYSTYPE_IS: - case ISIS_SYSTYPE_L1_IS: - case ISIS_SYSTYPE_L2_IS: - memcpy (lsp_id, adj->sysid, ISIS_SYS_ID_LEN); - LSP_PSEUDO_ID (lsp_id) = 0; - LSP_FRAGMENT (lsp_id) = 0; - if (spftree->mtid != ISIS_MT_IPV4_UNICAST || speaks (&adj->nlpids, spftree->family)) - isis_spf_add_local (spftree, - spftree->area->oldmetric ? VTYPE_NONPSEUDO_IS - : VTYPE_NONPSEUDO_TE_IS, - lsp_id, - adj, circuit->te_metric[spftree->level - 1], - parent); - break; - case ISIS_SYSTYPE_UNKNOWN: - default: - zlog_warn ("isis_spf_preload_tent unknown adj type"); - break; - } + + if (!pseudo_lsp && spftree->family == AF_INET6) { + struct list *ipv6reachs = NULL; + + if (spftree->mtid == ISIS_MT_IPV4_UNICAST) { + ipv6reachs = lsp->tlv_data.ipv6_reachs; + } else { + struct tlv_mt_ipv6_reachs *mt_reachs; + mt_reachs = tlvs_lookup_mt_ipv6_reachs(&lsp->tlv_data, + spftree->mtid); + if (mt_reachs) + ipv6reachs = mt_reachs->list; + } + + prefix.family = AF_INET6; + for (ALL_LIST_ELEMENTS_RO(ipv6reachs, node, ip6reach)) { + assert(ip6reach->prefix_len <= IPV6_MAX_BITLEN); + + dist = cost + ntohl(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, parent); + } } - else if (circuit->circ_type == CIRCUIT_T_LOOPBACK) - { - continue; - } - else - { - zlog_warn ("isis_spf_preload_tent unsupported media"); - retval = ISIS_WARNING; + + if (fragnode == NULL) + fragnode = listhead(lsp->lspu.frags); + else + fragnode = listnextnode(fragnode); + + if (fragnode) { + lsp = listgetdata(fragnode); + goto lspfragloop; + } + + return ISIS_OK; +} + +static int isis_spf_preload_tent(struct isis_spftree *spftree, + u_char *root_sysid, struct isis_vertex *parent) +{ + struct isis_circuit *circuit; + struct listnode *cnode, *anode, *ipnode; + struct isis_adjacency *adj; + struct isis_lsp *lsp; + struct list *adj_list; + struct list *adjdb; + struct prefix_ipv4 *ipv4; + 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]; + struct prefix_ipv6 *ipv6; + struct isis_circuit_mt_setting *circuit_mt; + + for (ALL_LIST_ELEMENTS_RO(spftree->area->circuit_list, cnode, + circuit)) { + circuit_mt = circuit_lookup_mt_setting(circuit, spftree->mtid); + if (circuit_mt && !circuit_mt->enabled) + continue; + if (circuit->state != C_STATE_UP) + continue; + if (!(circuit->is_type & spftree->level)) + continue; + if (spftree->family == AF_INET && !circuit->ip_router) + continue; + if (spftree->family == AF_INET6 && !circuit->ipv6_router) + continue; + /* + * Add IP(v6) addresses of this circuit + */ + if (spftree->family == AF_INET) { + prefix.family = AF_INET; + for (ALL_LIST_ELEMENTS_RO(circuit->ip_addrs, ipnode, + ipv4)) { + prefix.u.prefix4 = ipv4->prefix; + prefix.prefixlen = ipv4->prefixlen; + apply_mask(&prefix); + isis_spf_add_local(spftree, + VTYPE_IPREACH_INTERNAL, + &prefix, NULL, 0, parent); + } + } + if (spftree->family == AF_INET6) { + prefix.family = AF_INET6; + for (ALL_LIST_ELEMENTS_RO(circuit->ipv6_non_link, + ipnode, ipv6)) { + prefix.prefixlen = ipv6->prefixlen; + prefix.u.prefix6 = ipv6->prefix; + apply_mask(&prefix); + isis_spf_add_local(spftree, + VTYPE_IP6REACH_INTERNAL, + &prefix, NULL, 0, parent); + } + } + if (circuit->circ_type == CIRCUIT_T_BROADCAST) { + /* + * Add the adjacencies + */ + adj_list = list_new(); + adjdb = circuit->u.bc.adjdb[spftree->level - 1]; + isis_adj_build_up_list(adjdb, adj_list); + if (listcount(adj_list) == 0) { + list_delete(adj_list); + if (isis->debugs & DEBUG_SPF_EVENTS) + zlog_debug( + "ISIS-Spf: no L%d adjacencies on circuit %s", + spftree->level, + circuit->interface->name); + continue; + } + for (ALL_LIST_ELEMENTS_RO(adj_list, anode, adj)) { + if (!adj_has_mt(adj, spftree->mtid)) + continue; + if (spftree->mtid == ISIS_MT_IPV4_UNICAST + && !speaks(&adj->nlpids, spftree->family)) + continue; + switch (adj->sys_type) { + case ISIS_SYSTYPE_ES: + memcpy(lsp_id, adj->sysid, + ISIS_SYS_ID_LEN); + LSP_PSEUDO_ID(lsp_id) = 0; + isis_spf_add_local( + spftree, VTYPE_ES, lsp_id, adj, + circuit->te_metric + [spftree->level - 1], + parent); + break; + case ISIS_SYSTYPE_IS: + case ISIS_SYSTYPE_L1_IS: + case ISIS_SYSTYPE_L2_IS: + memcpy(lsp_id, adj->sysid, + ISIS_SYS_ID_LEN); + LSP_PSEUDO_ID(lsp_id) = 0; + LSP_FRAGMENT(lsp_id) = 0; + isis_spf_add_local( + spftree, + spftree->area->oldmetric + ? VTYPE_NONPSEUDO_IS + : VTYPE_NONPSEUDO_TE_IS, + lsp_id, adj, + circuit->te_metric + [spftree->level - 1], + parent); + lsp = lsp_search( + lsp_id, + spftree->area + ->lspdb[spftree->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), + spftree->level, + circuit->interface->name, + circuit->circuit_id); + break; + case ISIS_SYSTYPE_UNKNOWN: + default: + zlog_warn( + "isis_spf_preload_tent unknow adj type"); + } + } + list_delete(adj_list); + /* + * Add the pseudonode + */ + if (spftree->level == 1) + 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); + /* 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)", + spftree->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[spftree->level - 1]) { + zlog_warn( + "ISIS-Spf: No adjacency found from root " + "to L%d DR %s on %s (ID %d)", + spftree->level, rawlspid_print(lsp_id), + circuit->interface->name, + circuit->circuit_id); + continue; + } + lsp = lsp_search( + lsp_id, + spftree->area->lspdb[spftree->level - 1]); + if (lsp == NULL || lsp->lsp_header->rem_lifetime == 0) { + zlog_warn( + "ISIS-Spf: No lsp (%p) found from root " + "to L%d DR %s on %s (ID %d)", + (void *)lsp, spftree->level, + rawlspid_print(lsp_id), + circuit->interface->name, + circuit->circuit_id); + continue; + } + isis_spf_process_lsp( + spftree, lsp, + circuit->te_metric[spftree->level - 1], 0, + root_sysid, parent); + } else if (circuit->circ_type == CIRCUIT_T_P2P) { + adj = circuit->u.p2p.neighbor; + if (!adj) + continue; + if (!adj_has_mt(adj, spftree->mtid)) + continue; + switch (adj->sys_type) { + case ISIS_SYSTYPE_ES: + memcpy(lsp_id, adj->sysid, ISIS_SYS_ID_LEN); + LSP_PSEUDO_ID(lsp_id) = 0; + isis_spf_add_local( + spftree, VTYPE_ES, lsp_id, adj, + circuit->te_metric[spftree->level - 1], + parent); + break; + case ISIS_SYSTYPE_IS: + case ISIS_SYSTYPE_L1_IS: + case ISIS_SYSTYPE_L2_IS: + memcpy(lsp_id, adj->sysid, ISIS_SYS_ID_LEN); + LSP_PSEUDO_ID(lsp_id) = 0; + LSP_FRAGMENT(lsp_id) = 0; + if (spftree->mtid != ISIS_MT_IPV4_UNICAST + || speaks(&adj->nlpids, spftree->family)) + isis_spf_add_local( + spftree, + spftree->area->oldmetric + ? VTYPE_NONPSEUDO_IS + : VTYPE_NONPSEUDO_TE_IS, + lsp_id, adj, + circuit->te_metric + [spftree->level - 1], + parent); + break; + case ISIS_SYSTYPE_UNKNOWN: + default: + 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; + return retval; } /* * The parent(s) for vertex is set when added to TENT list * now we just put the child pointer(s) in place */ -static void -add_to_paths (struct isis_spftree *spftree, struct isis_vertex *vertex) +static void add_to_paths(struct isis_spftree *spftree, + struct isis_vertex *vertex) { - char buff[PREFIX2STR_BUFFER]; + char buff[PREFIX2STR_BUFFER]; - if (isis_find_vertex (spftree->paths, vertex->N.id, vertex->type)) - return; - listnode_add (spftree->paths, vertex); + 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 %s depth %d dist %d to PATHS", - print_sys_hostname (vertex->N.id), - vtype2string (vertex->type), vid2string (vertex, buff, sizeof (buff)), - vertex->depth, vertex->d_N); + zlog_debug("ISIS-Spf: added %s %s %s depth %d dist %d to PATHS", + print_sys_hostname(vertex->N.id), vtype2string(vertex->type), + vid2string(vertex, buff, sizeof(buff)), vertex->depth, + vertex->d_N); #endif /* EXTREME_DEBUG */ - if (VTYPE_IP(vertex->type)) - { - if (listcount (vertex->Adj_N) > 0) - isis_route_create ((struct prefix *) &vertex->N.prefix, vertex->d_N, - vertex->depth, vertex->Adj_N, spftree->area, spftree->level); - else if (isis->debugs & DEBUG_SPF_EVENTS) - zlog_debug ("ISIS-Spf: no adjacencies do not install route for " - "%s depth %d dist %d", vid2string (vertex, buff, sizeof (buff)), - vertex->depth, vertex->d_N); - } - - return; + if (VTYPE_IP(vertex->type)) { + if (listcount(vertex->Adj_N) > 0) + isis_route_create((struct prefix *)&vertex->N.prefix, + vertex->d_N, vertex->depth, + vertex->Adj_N, spftree->area, + spftree->level); + else if (isis->debugs & DEBUG_SPF_EVENTS) + zlog_debug( + "ISIS-Spf: no adjacencies do not install route for " + "%s depth %d dist %d", + vid2string(vertex, buff, sizeof(buff)), + vertex->depth, vertex->d_N); + } + + return; } -static void -init_spt (struct isis_spftree *spftree, int mtid, int level, int family) +static void init_spt(struct isis_spftree *spftree, int mtid, int level, + int family) { - spftree->tents->del = spftree->paths->del = (void (*)(void *)) isis_vertex_del; - list_delete_all_node (spftree->tents); - list_delete_all_node (spftree->paths); - spftree->tents->del = spftree->paths->del = NULL; - - spftree->mtid = mtid; - spftree->level = level; - spftree->family = family; - return; + spftree->tents->del = spftree->paths->del = + (void (*)(void *))isis_vertex_del; + list_delete_all_node(spftree->tents); + list_delete_all_node(spftree->paths); + spftree->tents->del = spftree->paths->del = NULL; + + spftree->mtid = mtid; + spftree->level = level; + spftree->family = family; + return; } -static int -isis_run_spf (struct isis_area *area, int level, int family, u_char *sysid) +static int 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 route_table *table = NULL; - struct timeval time_now; - unsigned long long start_time, end_time; - uint16_t mtid; - - /* Get time that can't roll backwards. */ - monotime(&time_now); - start_time = time_now.tv_sec; - start_time = (start_time * 1000000) + time_now.tv_usec; - - if (family == AF_INET) - spftree = area->spftree[level - 1]; - else if (family == AF_INET6) - spftree = area->spftree6[level - 1]; - assert (spftree); - assert (sysid); - - /* Make all routes in current route table inactive. */ - if (family == AF_INET) - table = area->route_table[level - 1]; - else if (family == AF_INET6) - table = area->route_table6[level - 1]; - - isis_route_invalidate_table (area, table); - - /* We only support ipv4-unicast and ipv6-unicast as topologies for now */ - if (family == AF_INET6) - mtid = isis_area_ipv6_topology(area); - else - mtid = ISIS_MT_IPV4_UNICAST; - - /* - * C.2.5 Step 0 - */ - init_spt (spftree, mtid, level, family); - /* a) */ - root_vertex = isis_spf_add_root (spftree, sysid); - /* b) */ - retval = isis_spf_preload_tent (spftree, 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 SPF-root:%s", print_sys_hostname(sysid)); - goto out; - } - - while (listcount (spftree->tents) > 0) - { - node = listhead (spftree->tents); - vertex = listgetdata (node); + 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 route_table *table = NULL; + struct timeval time_now; + unsigned long long start_time, end_time; + uint16_t mtid; + + /* Get time that can't roll backwards. */ + monotime(&time_now); + start_time = time_now.tv_sec; + start_time = (start_time * 1000000) + time_now.tv_usec; + + if (family == AF_INET) + spftree = area->spftree[level - 1]; + else if (family == AF_INET6) + spftree = area->spftree6[level - 1]; + assert(spftree); + assert(sysid); + + /* Make all routes in current route table inactive. */ + if (family == AF_INET) + table = area->route_table[level - 1]; + else if (family == AF_INET6) + table = area->route_table6[level - 1]; + + isis_route_invalidate_table(area, table); + + /* We only support ipv4-unicast and ipv6-unicast as topologies for now + */ + if (family == AF_INET6) + mtid = isis_area_ipv6_topology(area); + else + mtid = ISIS_MT_IPV4_UNICAST; + + /* + * C.2.5 Step 0 + */ + init_spt(spftree, mtid, level, family); + /* a) */ + root_vertex = isis_spf_add_root(spftree, sysid); + /* b) */ + retval = isis_spf_preload_tent(spftree, 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 SPF-root:%s", + print_sys_hostname(sysid)); + goto out; + } + + while (listcount(spftree->tents) > 0) { + node = listhead(spftree->tents); + vertex = listgetdata(node); #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); + 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); - if (VTYPE_IS(vertex->type)) - { - memcpy (lsp_id, vertex->N.id, ISIS_SYS_ID_LEN + 1); - LSP_FRAGMENT (lsp_id) = 0; - lsp = lsp_search (lsp_id, area->lspdb[level - 1]); - if (lsp && lsp->lsp_header->rem_lifetime != 0) - { - isis_spf_process_lsp (spftree, lsp, vertex->d_N, - vertex->depth, sysid, vertex); - } - else - { - zlog_warn ("ISIS-Spf: No LSP found for %s", - rawlspid_print (lsp_id)); - } + /* Remove from tent list and add to paths list */ + list_delete_node(spftree->tents, node); + add_to_paths(spftree, vertex); + if (VTYPE_IS(vertex->type)) { + memcpy(lsp_id, vertex->N.id, ISIS_SYS_ID_LEN + 1); + LSP_FRAGMENT(lsp_id) = 0; + lsp = lsp_search(lsp_id, area->lspdb[level - 1]); + if (lsp && lsp->lsp_header->rem_lifetime != 0) { + isis_spf_process_lsp(spftree, lsp, vertex->d_N, + vertex->depth, sysid, + vertex); + } else { + zlog_warn("ISIS-Spf: No LSP found for %s", + rawlspid_print(lsp_id)); + } + } } - } out: - isis_route_validate (area); - spftree->runcount++; - spftree->last_run_timestamp = time (NULL); - monotime(&time_now); - end_time = time_now.tv_sec; - end_time = (end_time * 1000000) + time_now.tv_usec; - spftree->last_run_duration = end_time - start_time; - - return retval; + isis_route_validate(area); + spftree->runcount++; + spftree->last_run_timestamp = time(NULL); + monotime(&time_now); + end_time = time_now.tv_sec; + end_time = (end_time * 1000000) + time_now.tv_usec; + spftree->last_run_duration = end_time - start_time; + + return retval; } -static int -isis_run_spf_cb (struct thread *thread) +static int isis_run_spf_cb(struct thread *thread) { - struct isis_spf_run *run = THREAD_ARG (thread); - struct isis_area *area = run->area; - int level = run->level; - int retval = ISIS_OK; - - XFREE(MTYPE_ISIS_SPF_RUN, run); - area->spf_timer[level - 1] = NULL; - - if (!(area->is_type & level)) - { - if (isis->debugs & DEBUG_SPF_EVENTS) - zlog_warn ("ISIS-SPF (%s) area does not share level", - area->area_tag); - return ISIS_WARNING; - } - - if (isis->debugs & DEBUG_SPF_EVENTS) - zlog_debug ("ISIS-Spf (%s) L%d SPF needed, periodic SPF", - area->area_tag, level); - - if (area->ip_circuits) - retval = isis_run_spf (area, level, AF_INET, isis->sysid); - if (area->ipv6_circuits) - retval = isis_run_spf (area, level, AF_INET6, isis->sysid); - - return retval; -} + struct isis_spf_run *run = THREAD_ARG(thread); + struct isis_area *area = run->area; + int level = run->level; + int retval = ISIS_OK; + + XFREE(MTYPE_ISIS_SPF_RUN, run); + area->spf_timer[level - 1] = NULL; + + if (!(area->is_type & level)) { + if (isis->debugs & DEBUG_SPF_EVENTS) + zlog_warn("ISIS-SPF (%s) area does not share level", + area->area_tag); + return ISIS_WARNING; + } -static struct isis_spf_run* -isis_run_spf_arg(struct isis_area *area, int level) -{ - struct isis_spf_run *run = XMALLOC(MTYPE_ISIS_SPF_RUN, sizeof(*run)); + if (isis->debugs & DEBUG_SPF_EVENTS) + zlog_debug("ISIS-Spf (%s) L%d SPF needed, periodic SPF", + area->area_tag, level); - run->area = area; - run->level = level; + if (area->ip_circuits) + retval = isis_run_spf(area, level, AF_INET, isis->sysid); + if (area->ipv6_circuits) + retval = isis_run_spf(area, level, AF_INET6, isis->sysid); - return run; + return retval; } -int -isis_spf_schedule (struct isis_area *area, int level) +static struct isis_spf_run *isis_run_spf_arg(struct isis_area *area, int level) { - struct isis_spftree *spftree = area->spftree[level - 1]; - time_t now = time (NULL); - int diff = now - spftree->last_run_timestamp; - - assert (diff >= 0); - assert (area->is_type & level); - - 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); - - if (area->spf_delay_ietf[level - 1]) - { - /* Need to call schedule function also if spf delay is running to - * restart holdoff timer - compare draft-ietf-rtgwg-backoff-algo-04 */ - long delay = spf_backoff_schedule(area->spf_delay_ietf[level -1]); - if (area->spf_timer[level - 1]) - return ISIS_OK; - - thread_add_timer_msec (master, isis_run_spf_cb, - isis_run_spf_arg(area, level), - delay, &area->spf_timer[level-1]); - return ISIS_OK; - } - - if (area->spf_timer[level -1]) - return ISIS_OK; - - /* wait configured min_spf_interval before doing the SPF */ - if (diff >= area->min_spf_interval[level-1]) - { - int retval = ISIS_OK; - - if (area->ip_circuits) - retval = isis_run_spf (area, level, AF_INET, isis->sysid); - if (area->ipv6_circuits) - retval = isis_run_spf (area, level, AF_INET6, isis->sysid); - - return retval; - } - - thread_add_timer (master, isis_run_spf_cb, isis_run_spf_arg(area, level), - area->min_spf_interval[level-1] - diff, - &area->spf_timer[level-1]); - - 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); - - return ISIS_OK; + struct isis_spf_run *run = XMALLOC(MTYPE_ISIS_SPF_RUN, sizeof(*run)); + + run->area = area; + run->level = level; + + return run; } -static void -isis_print_paths (struct vty *vty, struct list *paths, u_char *root_sysid) +int isis_spf_schedule(struct isis_area *area, int level) { - struct listnode *node; - struct listnode *anode; - struct isis_vertex *vertex; - struct isis_adjacency *adj; - char buff[PREFIX2STR_BUFFER]; - - vty_out (vty, - "Vertex Type Metric Next-Hop Interface Parent\n"); - - 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, sizeof (buff)), - vtype2string (vertex->type), vertex->d_N); - for (ALL_LIST_ELEMENTS_RO (vertex->Adj_N, anode, adj)) { - if (adj) { - if (rows) { - vty_out (vty, "\n"); - vty_out (vty, "%-20s %-12s %-6s ", "", "", ""); - } - vty_out (vty, "%-20s %-9s ", - print_sys_hostname (adj->sysid), - adj->circuit->interface->name); - ++rows; - } + struct isis_spftree *spftree = area->spftree[level - 1]; + time_t now = time(NULL); + int diff = now - spftree->last_run_timestamp; + + assert(diff >= 0); + assert(area->is_type & level); + + 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); + + if (area->spf_delay_ietf[level - 1]) { + /* Need to call schedule function also if spf delay is running + * to + * restart holdoff timer - compare + * draft-ietf-rtgwg-backoff-algo-04 */ + long delay = + spf_backoff_schedule(area->spf_delay_ietf[level - 1]); + if (area->spf_timer[level - 1]) + return ISIS_OK; + + thread_add_timer_msec(master, isis_run_spf_cb, + isis_run_spf_arg(area, level), delay, + &area->spf_timer[level - 1]); + return ISIS_OK; } - if (rows == 0) - vty_out (vty, "%-30s ", ""); - } - - /* 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, "\n"); - vty_out (vty, "%-72s", ""); - } - vty_out (vty, "%s(%d)", - vid2string (pvertex, buff, sizeof (buff)), pvertex->type); - ++rows; + + if (area->spf_timer[level - 1]) + return ISIS_OK; + + /* wait configured min_spf_interval before doing the SPF */ + if (diff >= area->min_spf_interval[level - 1]) { + int retval = ISIS_OK; + + if (area->ip_circuits) + retval = + isis_run_spf(area, level, AF_INET, isis->sysid); + if (area->ipv6_circuits) + retval = isis_run_spf(area, level, AF_INET6, + isis->sysid); + + return retval; } - } else { - vty_out (vty, " NULL "); - } - vty_out (vty, "\n"); - } + thread_add_timer(master, isis_run_spf_cb, isis_run_spf_arg(area, level), + area->min_spf_interval[level - 1] - diff, + &area->spf_timer[level - 1]); + + 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); + + return ISIS_OK; +} + +static void 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_adjacency *adj; + char buff[PREFIX2STR_BUFFER]; + + vty_out(vty, + "Vertex Type Metric Next-Hop Interface Parent\n"); + + 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, sizeof(buff)), + vtype2string(vertex->type), vertex->d_N); + for (ALL_LIST_ELEMENTS_RO(vertex->Adj_N, anode, adj)) { + if (adj) { + if (rows) { + vty_out(vty, "\n"); + 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 ", ""); + } + + /* 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, "\n"); + vty_out(vty, "%-72s", ""); + } + vty_out(vty, "%s(%d)", + vid2string(pvertex, buff, sizeof(buff)), + pvertex->type); + ++rows; + } + } else { + vty_out(vty, " NULL "); + } + + vty_out(vty, "\n"); + } } DEFUN (show_isis_topology, @@ -1380,56 +1372,57 @@ DEFUN (show_isis_topology, "Paths to all level-1 routers in the area\n" "Paths to all level-2 routers in the domain\n") { - int levels; - struct listnode *node; - struct isis_area *area; - - if (argc < 4) - levels = ISIS_LEVEL1|ISIS_LEVEL2; - else if (strmatch(argv[3]->text, "level-1")) - levels = ISIS_LEVEL1; - else - levels = ISIS_LEVEL2; - - if (!isis->area_list || isis->area_list->count == 0) - return CMD_SUCCESS; - - for (ALL_LIST_ELEMENTS_RO (isis->area_list, node, area)) - { - vty_out (vty, "Area %s:\n",area->area_tag ? area->area_tag : "null"); + int levels; + struct listnode *node; + struct isis_area *area; + + if (argc < 4) + levels = ISIS_LEVEL1 | ISIS_LEVEL2; + else if (strmatch(argv[3]->text, "level-1")) + levels = ISIS_LEVEL1; + else + levels = ISIS_LEVEL2; + + if (!isis->area_list || isis->area_list->count == 0) + return CMD_SUCCESS; + + for (ALL_LIST_ELEMENTS_RO(isis->area_list, node, area)) { + vty_out(vty, "Area %s:\n", + area->area_tag ? area->area_tag : "null"); + + for (int level = ISIS_LEVEL1; level <= ISIS_LEVELS; level++) { + if ((level & levels) == 0) + continue; + + if (area->ip_circuits > 0 && area->spftree[level - 1] + && area->spftree[level - 1]->paths->count > 0) { + vty_out(vty, + "IS-IS paths to level-%d routers that speak IP\n", + level); + isis_print_paths( + vty, area->spftree[level - 1]->paths, + isis->sysid); + vty_out(vty, "\n"); + } + if (area->ipv6_circuits > 0 && area->spftree6[level - 1] + && area->spftree6[level - 1]->paths->count > 0) { + vty_out(vty, + "IS-IS paths to level-%d routers that speak IPv6\n", + level); + isis_print_paths( + vty, area->spftree6[level - 1]->paths, + isis->sysid); + vty_out(vty, "\n"); + } + } - for (int level = ISIS_LEVEL1; level <= ISIS_LEVELS; level++) - { - if ((level & levels) == 0) - continue; - - if (area->ip_circuits > 0 && area->spftree[level-1] - && area->spftree[level-1]->paths->count > 0) - { - vty_out (vty, "IS-IS paths to level-%d routers that speak IP\n", - level); - isis_print_paths (vty, area->spftree[level-1]->paths, isis->sysid); - vty_out (vty, "\n"); - } - if (area->ipv6_circuits > 0 && area->spftree6[level-1] - && area->spftree6[level-1]->paths->count > 0) - { - vty_out (vty, - "IS-IS paths to level-%d routers that speak IPv6\n", - level); - isis_print_paths (vty, area->spftree6[level-1]->paths, isis->sysid); - vty_out (vty, "\n"); - } + vty_out(vty, "\n"); } - vty_out (vty, "\n"); - } - - return CMD_SUCCESS; + return CMD_SUCCESS; } -void -isis_spf_cmds_init () +void isis_spf_cmds_init() { - install_element (VIEW_NODE, &show_isis_topology_cmd); + install_element(VIEW_NODE, &show_isis_topology_cmd); } |