blob: 1c32f8fce30fdfa5c3a352e2ebea19fb73dbf4b8 [file] [log] [blame]
/*
* IS-IS Rout(e)ing protocol - isis_spf.c
* The SPT algorithm
*
* Copyright (C) 2001,2002 Sampo Saaristo
* Tampere University of Technology
* Institute of Communications Engineering
*
* This program is free software; you can redistribute it and/or modify it
* under the terms of the GNU General Public Licenseas published by the Free
* Software Foundation; either version 2 of the License, or (at your option)
* any later version.
*
* This program is distributed in the hope that it will be useful,but WITHOUT
* ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
* FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for
* more details.
* You should have received a copy of the GNU General Public License along
* with this program; if not, write to the Free Software Foundation, Inc.,
* 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
*/
#include <stdlib.h>
#include <stdio.h>
#include <zebra.h>
#include "thread.h"
#include "linklist.h"
#include "vty.h"
#include "log.h"
#include "command.h"
#include "memory.h"
#include "prefix.h"
#include "hash.h"
#include "if.h"
#include "table.h"
#include "isis_constants.h"
#include "isis_common.h"
#include "dict.h"
#include "isisd.h"
#include "isis_misc.h"
#include "isis_adjacency.h"
#include "isis_circuit.h"
#include "isis_tlv.h"
#include "isis_pdu.h"
#include "isis_lsp.h"
#include "isis_dynhn.h"
#include "isis_spf.h"
#include "isis_route.h"
#include "isis_csm.h"
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);
/* performace issue ???? */
void
union_adjlist (struct list *target, struct list *source)
{
struct isis_adjacency *adj, *adj2;
struct listnode *node, *node2;
zlog_info ("Union adjlist!");
for (node = listhead (source); node; nextnode (node))
{
adj = getdata (node);
/* lookup adjacency in the source list */
for (node2 = listhead (target); node2; nextnode (node2))
{
adj2 = getdata (node2);
if (adj == adj2)
break;
}
if (!node2)
listnode_add (target, adj);
}
}
/* 7.2.7 */
void
remove_excess_adjs (struct list *adjs)
{
struct listnode *node, *excess = NULL;
struct isis_adjacency *adj, *candidate = NULL;
int comp;
for (node = listhead (adjs); node; nextnode (node))
{
if (excess == NULL)
excess = node;
candidate = getdata (excess);
adj = getdata (node);
if (candidate->sys_type < adj->sys_type)
{
excess = node;
candidate = adj;
continue;
}
if (candidate->sys_type > adj->sys_type)
continue;
comp = memcmp (candidate->sysid, adj->sysid, ISIS_SYS_ID_LEN);
if (comp > 0)
{
excess = node;
candidate = adj;
continue;
}
if (comp < 0)
continue;
if (candidate->circuit->circuit_id > adj->circuit->circuit_id)
{
excess = node;
candidate = adj;
continue;
}
if (candidate->circuit->circuit_id < adj->circuit->circuit_id)
continue;
comp = memcmp (candidate->snpa, adj->snpa, ETH_ALEN);
if (comp > 0)
{
excess = node;
candidate = adj;
continue;
}
}
list_delete_node (adjs, excess);
return;
}
const char *
vtype2string (enum vertextype vtype)
{
switch (vtype)
{
case VTYPE_PSEUDO_IS:
return "pseudo_IS";
break;
case VTYPE_NONPSEUDO_IS:
return "IS";
break;
case VTYPE_ES:
return "ES";
break;
case VTYPE_IPREACH_INTERNAL:
return "IP internal";
break;
case VTYPE_IPREACH_EXTERNAL:
return "IP external";
break;
#ifdef HAVE_IPV6
case VTYPE_IP6REACH_INTERNAL:
return "IP6 internal";
break;
case VTYPE_IP6REACH_EXTERNAL:
return "IP6 external";
break;
#endif /* HAVE_IPV6 */
default:
return "UNKNOWN";
}
return NULL; /* Not reached */
}
char *
vid2string (struct isis_vertex *vertex, u_char * buff)
{
switch (vertex->type)
{
case VTYPE_PSEUDO_IS:
return rawlspid_print (vertex->N.id);
break;
case VTYPE_NONPSEUDO_IS:
case VTYPE_ES:
return sysid_print (vertex->N.id);
break;
case VTYPE_IPREACH_INTERNAL:
case VTYPE_IPREACH_EXTERNAL:
#ifdef HAVE_IPV6
case VTYPE_IP6REACH_INTERNAL:
case VTYPE_IP6REACH_EXTERNAL:
#endif /* HAVE_IPV6 */
prefix2str ((struct prefix *) &vertex->N.prefix, (char *) buff, BUFSIZ);
break;
default:
return "UNKNOWN";
}
return (char *) buff;
}
struct isis_spftree *
isis_spftree_new ()
{
struct isis_spftree *tree;
tree = XMALLOC (MTYPE_ISIS_SPFTREE, sizeof (struct isis_spftree));
if (tree == NULL)
{
zlog_err ("ISIS-Spf: isis_spftree_new Out of memory!");
return NULL;
}
memset (tree, 0, sizeof (struct isis_spftree));
tree->tents = list_new ();
tree->paths = list_new ();
return tree;
}
void
isis_vertex_del (struct isis_vertex *vertex)
{
list_delete (vertex->Adj_N);
XFREE (MTYPE_ISIS_VERTEX, vertex);
return;
}
void
isis_spftree_del (struct isis_spftree *spftree)
{
spftree->tents->del = (void (*)(void *)) isis_vertex_del;
list_delete (spftree->tents);
spftree->paths->del = (void (*)(void *)) isis_vertex_del;
list_delete (spftree->paths);
XFREE (MTYPE_ISIS_SPFTREE, spftree);
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 ();
#ifdef HAVE_IPV6
area->spftree6[0] = isis_spftree_new ();
#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 ();
#ifdef HAVE_IPV6
area->spftree6[1] = isis_spftree_new ();
#endif
/* thread_add_timer (master, isis_run_spf_l2, area,
isis_jitter (PERIODIC_SPF_INTERVAL, 10)); */
}
return;
}
struct isis_vertex *
isis_vertex_new (void *id, enum vertextype vtype)
{
struct isis_vertex *vertex;
vertex = XMALLOC (MTYPE_ISIS_VERTEX, sizeof (struct isis_vertex));
if (vertex == NULL)
{
zlog_err ("isis_vertex_new Out of memory!");
return NULL;
}
memset (vertex, 0, sizeof (struct isis_vertex));
vertex->type = vtype;
switch (vtype)
{
case VTYPE_ES:
case VTYPE_NONPSEUDO_IS:
memcpy (vertex->N.id, (u_char *) id, ISIS_SYS_ID_LEN);
break;
case VTYPE_PSEUDO_IS:
memcpy (vertex->N.id, (u_char *) id, ISIS_SYS_ID_LEN + 1);
break;
case VTYPE_IPREACH_INTERNAL:
case VTYPE_IPREACH_EXTERNAL:
#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 ();
return vertex;
}
/*
* Add this IS to the root of SPT
*/
void
isis_spf_add_self (struct isis_spftree *spftree, struct isis_area *area,
int level)
{
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]);
if (lsp == NULL)
zlog_warn ("ISIS-Spf: could not find own l%d LSP!", level);
vertex = isis_vertex_new (isis->sysid, VTYPE_NONPSEUDO_IS);
vertex->lsp = lsp;
listnode_add (spftree->paths, vertex);
#ifdef EXTREME_DEBUG
zlog_info ("ISIS-Spf: added this IS %s %s depth %d dist %d to PATHS",
vtype2string (vertex->type), vid2string (vertex, buff),
vertex->depth, vertex->d_N);
#endif /* EXTREME_DEBUG */
return;
}
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 (node = listhead (list); node; nextnode (node))
{
vertex = getdata (node);
if (vertex->type != vtype)
continue;
switch (vtype)
{
case VTYPE_ES:
case VTYPE_NONPSEUDO_IS:
if (memcmp ((u_char *) id, vertex->N.id, ISIS_SYS_ID_LEN) == 0)
return vertex;
break;
case VTYPE_PSEUDO_IS:
if (memcmp ((u_char *) id, vertex->N.id, ISIS_SYS_ID_LEN + 1) == 0)
return vertex;
break;
case VTYPE_IPREACH_INTERNAL:
case VTYPE_IPREACH_EXTERNAL:
#ifdef HAVE_IPV6
case VTYPE_IP6REACH_INTERNAL:
case VTYPE_IP6REACH_EXTERNAL:
#endif /* HAVE_IPV6 */
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)) == 0)
return vertex;
break;
}
}
return NULL;
}
/*
* Add a vertex to TENT sorted by cost and by vertextype on tie break situation
*/
struct isis_vertex *
isis_spf_add2tent (struct isis_spftree *spftree, enum vertextype vtype,
void *id, struct isis_adjacency *adj, u_int16_t cost,
int depth, int family)
{
struct isis_vertex *vertex, *v;
struct listnode *node;
#ifdef EXTREME_DEBUG
u_char buff[BUFSIZ];
#endif
vertex = isis_vertex_new (id, vtype);
vertex->d_N = cost;
vertex->depth = depth;
if (adj)
listnode_add (vertex->Adj_N, adj);
#ifdef EXTREME_DEBUG
zlog_info ("ISIS-Spf: add to TENT %s %s depth %d dist %d",
vtype2string (vertex->type), vid2string (vertex, buff),
vertex->depth, vertex->d_N);
#endif /* EXTREME_DEBUG */
listnode_add (spftree->tents, vertex);
if (list_isempty (spftree->tents))
{
listnode_add (spftree->tents, vertex);
return vertex;
}
for (node = listhead (spftree->tents); node; nextnode (node))
{
v = getdata (node);
if (v->d_N > vertex->d_N)
{
list_add_node_prev (spftree->tents, node, vertex);
break;
}
else if (v->d_N == vertex->d_N)
{
/* Tie break, add according to type */
while (v && v->d_N == vertex->d_N && v->type > vertex->type)
{
if (v->type > vertex->type)
{
break;
}
nextnode (node);
(node) ? (v = getdata (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);
break;
}
}
return vertex;
}
struct isis_vertex *
isis_spf_add_local (struct isis_spftree *spftree, enum vertextype vtype,
void *id, struct isis_adjacency *adj, u_int16_t cost,
int family)
{
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);
}
/* f) */
else if (vertex->d_N > cost)
{
listnode_delete (spftree->tents, vertex);
goto add2tent;
}
/* e) do nothing */
return vertex;
}
add2tent:
return isis_spf_add2tent (spftree, vtype, id, adj, cost, 1, family);
}
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)
{
struct isis_vertex *vertex;
#ifdef EXTREME_DEBUG
u_char buff[255];
#endif
/* C.2.6 b) */
if (dist > MAX_PATH_METRIC)
return;
/* c) */
vertex = isis_find_vertex (spftree->paths, id, vtype);
if (vertex)
{
#ifdef EXTREME_DEBUG
zlog_info ("ISIS-Spf: process_N %s %s dist %d already found from PATH",
vtype2string (vtype), vid2string (vertex, buff), dist);
#endif /* EXTREME_DEBUG */
assert (dist >= vertex->d_N);
return;
}
vertex = isis_find_vertex (spftree->tents, id, vtype);
/* d) */
if (vertex)
{
/* 1) */
#ifdef EXTREME_DEBUG
zlog_info ("ISIS-Spf: process_N %s %s dist %d",
vtype2string (vtype), vid2string (vertex, buff), dist);
#endif /* EXTREME_DEBUG */
if (vertex->d_N == dist)
{
if (adj)
listnode_add (vertex->Adj_N, adj);
/* 2) */
if (listcount (vertex->Adj_N) > ISIS_MAX_PATH_SPLITS)
remove_excess_adjs (vertex->Adj_N);
/* 3) */
return;
}
else if (vertex->d_N < dist)
{
return;
/* 4) */
}
else
{
listnode_delete (spftree->tents, vertex);
}
}
isis_spf_add2tent (spftree, vtype, id, adj, dist, depth, family);
return;
}
/*
* C.2.6 Step 1
*/
int
isis_spf_process_lsp (struct isis_spftree *spftree, struct isis_lsp *lsp,
uint16_t cost, uint16_t depth, int family)
{
struct listnode *node, *fragnode = NULL;
u_int16_t dist;
struct is_neigh *is_neigh;
struct ipv4_reachability *ipreach;
enum vertextype vtype;
struct prefix prefix;
#ifdef HAVE_IPV6
struct ipv6_reachability *ip6reach;
#endif /* HAVE_IPV6 */
if (!lsp->adj)
return ISIS_WARNING;
if (lsp->tlv_data.nlpids == NULL || !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");
return ISIS_WARNING;
}
if (!ISIS_MASK_LSP_OL_BIT (lsp->lsp_header->lsp_bits))
{
if (lsp->tlv_data.is_neighs)
{
for (node = listhead (lsp->tlv_data.is_neighs); node;
nextnode (node))
{
is_neigh = getdata (node);
/* 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, lsp->adj, family);
}
}
if (family == AF_INET && lsp->tlv_data.ipv4_int_reachs)
{
prefix.family = AF_INET;
for (node = listhead (lsp->tlv_data.ipv4_int_reachs); node;
nextnode (node))
{
ipreach = getdata (node);
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,
lsp->adj, family);
}
}
if (family == AF_INET && lsp->tlv_data.ipv4_ext_reachs)
{
prefix.family = AF_INET;
for (node = listhead (lsp->tlv_data.ipv4_ext_reachs); node;
nextnode (node))
{
ipreach = getdata (node);
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,
lsp->adj, family);
}
}
#ifdef HAVE_IPV6
if (family == AF_INET6 && lsp->tlv_data.ipv6_reachs)
{
prefix.family = AF_INET6;
for (node = listhead (lsp->tlv_data.ipv6_reachs); node;
nextnode (node))
{
ip6reach = getdata (node);
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,
lsp->adj, family);
}
}
#endif /* HAVE_IPV6 */
}
if (fragnode == NULL)
fragnode = listhead (lsp->lspu.frags);
else
fragnode = nextnode (fragnode);
if (fragnode)
{
lsp = getdata (fragnode);
goto lspfragloop;
}
return ISIS_OK;
}
int
isis_spf_process_pseudo_lsp (struct isis_spftree *spftree,
struct isis_lsp *lsp, uint16_t cost,
uint16_t depth, int family)
{
struct listnode *node, *fragnode = NULL;
struct is_neigh *is_neigh;
enum vertextype vtype;
pseudofragloop:
if (lsp->lsp_header->seq_num == 0)
{
zlog_warn ("isis_spf_process_pseudo_lsp(): lsp with 0 seq_num"
" - do not process");
return ISIS_WARNING;
}
for (node = (lsp->tlv_data.is_neighs ?
listhead (lsp->tlv_data.is_neighs) : NULL);
node; nextnode (node))
{
is_neigh = getdata (node);
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))
continue;
if (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, lsp->adj,
cost, depth, family);
}
}
if (fragnode == NULL)
fragnode = listhead (lsp->lspu.frags);
else
fragnode = nextnode (fragnode);
if (fragnode)
{
lsp = getdata (fragnode);
goto pseudofragloop;
}
return ISIS_OK;
}
int
isis_spf_preload_tent (struct isis_spftree *spftree,
struct isis_area *area, int level, int family)
{
struct isis_vertex *vertex;
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];
#ifdef HAVE_IPV6
struct prefix_ipv6 *ipv6;
#endif /* HAVE_IPV6 */
for (cnode = listhead (area->circuit_list); cnode; nextnode (cnode))
{
circuit = getdata (cnode);
if (circuit->state != C_STATE_UP)
continue;
if (!(circuit->circuit_is_type & level))
continue;
if (family == AF_INET && !circuit->ip_router)
continue;
#ifdef HAVE_IPV6
if (family == AF_INET6 && !circuit->ipv6_router)
continue;
#endif /* HAVE_IPV6 */
/*
* Add IP(v6) addresses of this circuit
*/
if (family == AF_INET)
{
prefix.family = AF_INET;
for (ipnode =
(circuit->ip_addrs ? listhead (circuit->ip_addrs) : NULL);
ipnode; nextnode (ipnode))
{
ipv4 = getdata (ipnode);
prefix.u.prefix4 = ipv4->prefix;
prefix.prefixlen = ipv4->prefixlen;
isis_spf_add_local (spftree, VTYPE_IPREACH_INTERNAL, &prefix,
NULL, 0, family);
}
}
#ifdef HAVE_IPV6
if (family == AF_INET6)
{
prefix.family = AF_INET6;
for (ipnode = (circuit->ipv6_non_link ? listhead
(circuit->ipv6_non_link) : NULL); ipnode;
nextnode (ipnode))
{
ipv6 = getdata (ipnode);
prefix.prefixlen = ipv6->prefixlen;
prefix.u.prefix6 = ipv6->prefix;
isis_spf_add_local (spftree, VTYPE_IP6REACH_INTERNAL,
&prefix, NULL, 0, family);
}
}
#endif /* HAVE_IPV6 */
if (circuit->circ_type == CIRCUIT_T_BROADCAST)
{
/*
* Add the adjacencies
*/
adj_list = list_new ();
adjdb = circuit->u.bc.adjdb[level - 1];
isis_adj_build_up_list (adjdb, adj_list);
if (listcount (adj_list) == 0)
{
list_delete (adj_list);
zlog_warn ("ISIS-Spf: no L%d adjacencies on circuit %s",
level, circuit->interface->name);
continue;
}
anode = listhead (adj_list);
while (anode)
{
adj = getdata (anode);
if (!speaks (&adj->nlpids, family))
{
anode = nextnode (anode);
continue;
}
switch (adj->sys_type)
{
case ISIS_SYSTYPE_ES:
isis_spf_add_local (spftree, VTYPE_ES, adj->sysid, adj,
circuit->metrics[level -
1].metric_default,
family);
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->metrics[level -
1].metric_default,
family);
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");
/* else {
isis_spf_process_lsp (spftree, lsp, vertex->d_N, 1, family);
} */
break;
case ISIS_SYSTYPE_UNKNOWN:
default:
zlog_warn ("isis_spf_preload_tent unknow adj type");
}
anode = nextnode (anode);
}
list_delete (adj_list);
/*
* Add the pseudonode
*/
if (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);
lsp = lsp_search (lsp_id, area->lspdb[level - 1]);
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");
}
if (lsp == NULL || lsp->lsp_header->rem_lifetime == 0)
{
zlog_warn ("ISIS-Spf: No lsp found for DR");
}
else
{
isis_spf_process_pseudo_lsp
(spftree, lsp, circuit->metrics[level - 1].metric_default, 0,
family);
}
}
else if (circuit->circ_type == CIRCUIT_T_P2P)
{
adj = circuit->u.p2p.neighbor;
if (!adj)
continue;
switch (adj->sys_type)
{
case ISIS_SYSTYPE_ES:
isis_spf_add_local (spftree, VTYPE_ES, adj->sysid, adj,
circuit->metrics[level - 1].metric_default,
family);
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,
adj,
circuit->metrics[level -
1].metric_default,
family);
break;
case ISIS_SYSTYPE_UNKNOWN:
default:
zlog_warn ("isis_spf_preload_tent unknow adj type");
break;
}
}
else
{
zlog_warn ("isis_spf_preload_tent unsupported media");
retval = ISIS_WARNING;
}
}
return retval;
}
/*
* The parent(s) for vertex is set when added to TENT list
* now we just put the child pointer(s) in place
*/
void
add_to_paths (struct isis_spftree *spftree, struct isis_vertex *vertex,
struct isis_area *area)
{
#ifdef EXTREME_DEBUG
u_char buff[BUFSIZ];
#endif /* EXTREME_DEBUG */
listnode_add (spftree->paths, vertex);
#ifdef EXTREME_DEBUG
zlog_info ("ISIS-Spf: added %s %s depth %d dist %d to PATHS",
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);
else if (isis->debugs & DEBUG_SPF_EVENTS)
zlog_info ("ISIS-Spf: no adjacencies do not install route");
}
return;
}
void
init_spt (struct isis_spftree *spftree)
{
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;
return;
}
int
isis_run_spf (struct isis_area *area, int level, int family)
{
int retval = ISIS_OK;
struct listnode *node;
struct isis_vertex *vertex;
struct isis_spftree *spftree = NULL;
u_char lsp_id[ISIS_SYS_ID_LEN + 2];
struct isis_lsp *lsp;
if (family == AF_INET)
spftree = area->spftree[level - 1];
#ifdef HAVE_IPV6
else if (family == AF_INET6)
spftree = area->spftree6[level - 1];
#endif
assert (spftree);
/*
* C.2.5 Step 0
*/
init_spt (spftree);
/* a) */
isis_spf_add_self (spftree, area, level);
/* b) */
retval = isis_spf_preload_tent (spftree, area, level, family);
/*
* C.2.7 Step 2
*/
if (listcount (spftree->tents) == 0)
{
zlog_warn ("ISIS-Spf: TENT is empty");
spftree->lastrun = time (NULL);
return retval;
}
while (listcount (spftree->tents) > 0)
{
node = listhead (spftree->tents);
vertex = getdata (node);
/* Remove from tent list */
list_delete_node (spftree->tents, node);
if (isis_find_vertex (spftree->paths, vertex->N.id, vertex->type))
continue;
add_to_paths (spftree, vertex, area);
if (vertex->type == VTYPE_PSEUDO_IS ||
vertex->type == VTYPE_NONPSEUDO_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_PSEUDO_ID (lsp_id))
{
isis_spf_process_pseudo_lsp (spftree, lsp, vertex->d_N,
vertex->depth, family);
}
else
{
isis_spf_process_lsp (spftree, lsp, vertex->d_N,
vertex->depth, family);
}
}
else
{
zlog_warn ("ISIS-Spf: No LSP found for %s",
rawlspid_print (lsp_id));
}
}
}
thread_add_event (master, isis_route_validate, area, 0);
spftree->lastrun = time (NULL);
spftree->pending = 0;
return retval;
}
int
isis_run_spf_l1 (struct thread *thread)
{
struct isis_area *area;
int retval = ISIS_OK;
area = THREAD_ARG (thread);
assert (area);
area->spftree[0]->t_spf = NULL;
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);
return ISIS_WARNING;
}
if (isis->debugs & DEBUG_SPF_EVENTS)
zlog_info ("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));
return retval;
}
int
isis_run_spf_l2 (struct thread *thread)
{
struct isis_area *area;
int retval = ISIS_OK;
area = THREAD_ARG (thread);
assert (area);
area->spftree[1]->t_spf = NULL;
if (!(area->is_type & IS_LEVEL_2))
{
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_info ("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));
return retval;
}
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);
if (spftree->pending)
return retval;
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);
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_spf_l1, area,
MINIMUM_SPF_INTERVAL - diff);
else
THREAD_TIMER_ON (master, spftree->t_spf, isis_run_spf_l2, area,
MINIMUM_SPF_INTERVAL - diff);
spftree->pending = 1;
}
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));
}
return retval;
}
#ifdef HAVE_IPV6
int
isis_run_spf6_l1 (struct thread *thread)
{
struct isis_area *area;
int retval = ISIS_OK;
area = THREAD_ARG (thread);
assert (area);
area->spftree6[0]->t_spf = NULL;
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);
return ISIS_WARNING;
}
if (isis->debugs & DEBUG_SPF_EVENTS)
zlog_info ("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));
return retval;
}
int
isis_run_spf6_l2 (struct thread *thread)
{
struct isis_area *area;
int retval = ISIS_OK;
area = THREAD_ARG (thread);
assert (area);
area->spftree6[1]->t_spf = NULL;
if (!(area->is_type & IS_LEVEL_2))
{
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_info ("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));
return retval;
}
int
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);
if (spftree->pending)
return retval;
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_spf6_l1, area, 60);
else
THREAD_TIMER_ON (master, spftree->t_spf, isis_run_spf6_l2, area, 60);
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);
spftree->pending = 1;
}
else
{
spftree->pending = 0;
retval = isis_run_spf (area, level, AF_INET6);
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));
}
return retval;
}
#endif
void
isis_print_paths (struct vty *vty, struct list *paths)
{
struct listnode *node, *anode;
struct isis_vertex *vertex;
struct isis_dynhn *dyn, *nh_dyn = NULL;
struct isis_adjacency *adj;
#ifdef EXTREME_DEBUG
u_char buff[255];
#endif
vty_out (vty, "System Id Metric Next-Hop"
" Interface SNPA%s", VTY_NEWLINE);
for (node = listhead (paths); node; nextnode (node))
{
vertex = getdata (node);
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, VTY_NEWLINE);
}
else
{
dyn = dynhn_find_by_id ((u_char *) vertex->N.id);
anode = listhead (vertex->Adj_N);
adj = getdata (anode);
if (adj)
{
nh_dyn = dynhn_find_by_id (adj->sysid);
vty_out (vty, "%-20s %-10u %-20s %-11s %-5s%s",
(dyn != NULL) ? dyn->name.name :
(u_char *) rawlspid_print ((u_char *) vertex->N.id),
vertex->d_N, (nh_dyn != NULL) ? nh_dyn->name.name :
(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 :
(u_char *) rawlspid_print (vertex->N.id),
vertex->d_N, VTY_NEWLINE);
}
}
#if 0
vty_out (vty, "%s %s %u %s", vtype2string (vertex->type),
vid2string (vertex, buff), vertex->d_N, VTY_NEWLINE);
#endif
}
}
DEFUN (show_isis_topology,
show_isis_topology_cmd,
"show isis topology",
SHOW_STR
"IS-IS information\n"
"IS-IS paths to Intermediate Systems\n")
{
struct listnode *node;
struct isis_area *area;
int level;
if (!isis->area_list || isis->area_list->count == 0)
return CMD_SUCCESS;
for (node = listhead (isis->area_list); node; nextnode (node))
{
area = getdata (node);
vty_out (vty, "Area %s:%s", area->area_tag ? area->area_tag : "null",
VTY_NEWLINE);
for (level = 0; level < ISIS_LEVELS; level++)
{
if (area->ip_circuits > 0 && area->spftree[level]
&& area->spftree[level]->paths->count > 0)
{
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);
}
#ifdef HAVE_IPV6
if (area->ipv6_circuits > 0 && area->spftree6[level]
&& area->spftree6[level]->paths->count > 0)
{
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);
}
#endif /* HAVE_IPV6 */
}
}
return CMD_SUCCESS;
}
DEFUN (show_isis_topology_l1,
show_isis_topology_l1_cmd,
"show isis topology level-1",
SHOW_STR
"IS-IS information\n"
"IS-IS paths to Intermediate Systems\n"
"Paths to all level-1 routers in the area\n")
{
struct listnode *node;
struct isis_area *area;
if (!isis->area_list || isis->area_list->count == 0)
return CMD_SUCCESS;
for (node = listhead (isis->area_list); node; nextnode (node))
{
area = getdata (node);
vty_out (vty, "Area %s:%s", area->area_tag ? area->area_tag : "null",
VTY_NEWLINE);
if (area->ip_circuits > 0 && area->spftree[0]
&& area->spftree[0]->paths->count > 0)
{
vty_out (vty, "IS-IS paths to level-1 routers that speak IP%s",
VTY_NEWLINE);
isis_print_paths (vty, area->spftree[0]->paths);
}
#ifdef HAVE_IPV6
if (area->ipv6_circuits > 0 && area->spftree6[0]
&& area->spftree6[0]->paths->count > 0)
{
vty_out (vty, "IS-IS paths to level-1 routers that speak IPv6%s",
VTY_NEWLINE);
isis_print_paths (vty, area->spftree6[0]->paths);
}
#endif /* HAVE_IPV6 */
}
return CMD_SUCCESS;
}
DEFUN (show_isis_topology_l2,
show_isis_topology_l2_cmd,
"show isis topology level-2",
SHOW_STR
"IS-IS information\n"
"IS-IS paths to Intermediate Systems\n"
"Paths to all level-2 routers in the domain\n")
{
struct listnode *node;
struct isis_area *area;
if (!isis->area_list || isis->area_list->count == 0)
return CMD_SUCCESS;
for (node = listhead (isis->area_list); node; nextnode (node))
{
area = getdata (node);
vty_out (vty, "Area %s:%s", area->area_tag ? area->area_tag : "null",
VTY_NEWLINE);
if (area->ip_circuits > 0 && area->spftree[1]
&& area->spftree[1]->paths->count > 0)
{
vty_out (vty, "IS-IS paths to level-2 routers that speak IP%s",
VTY_NEWLINE);
isis_print_paths (vty, area->spftree[1]->paths);
}
#ifdef HAVE_IPV6
if (area->ipv6_circuits > 0 && area->spftree6[1]
&& area->spftree6[1]->paths->count > 0)
{
vty_out (vty, "IS-IS paths to level-2 routers that speak IPv6%s",
VTY_NEWLINE);
isis_print_paths (vty, area->spftree6[1]->paths);
}
#endif /* HAVE_IPV6 */
}
return CMD_SUCCESS;
}
void
isis_spf_cmds_init ()
{
install_element (VIEW_NODE, &show_isis_topology_cmd);
install_element (VIEW_NODE, &show_isis_topology_l1_cmd);
install_element (VIEW_NODE, &show_isis_topology_l2_cmd);
install_element (ENABLE_NODE, &show_isis_topology_cmd);
install_element (ENABLE_NODE, &show_isis_topology_l1_cmd);
install_element (ENABLE_NODE, &show_isis_topology_l2_cmd);
}