| /* |
| * 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, buff, BUFSIZ); |
| break; |
| default: |
| return "UNKNOWN"; |
| } |
| |
| return 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 *)isis_vertex_del; |
| list_delete (spftree->tents); |
| |
| spftree->paths->del = (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 *)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; |
| |
| if (level == 1) |
| THREAD_TIMER_ON(master, spftree->t_spf_periodic, isis_run_spf_l1, area, |
| isis_jitter(PERIODIC_SPF_INTERVAL, 10)); |
| else |
| THREAD_TIMER_ON(master, spftree->t_spf_periodic, isis_run_spf_l2, area, |
| isis_jitter(PERIODIC_SPF_INTERVAL, 10)); |
| |
| return retval; |
| } |
| |
| int |
| isis_run_spf_l1 (struct thread *thread) |
| { |
| struct isis_area *area; |
| int retval = ISIS_OK; |
| |
| area = THREAD_ARG(thread); |
| assert (area); |
| |
| 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); |
| #ifdef HAVE_IPV6 |
| if (area->ipv6_circuits) |
| retval = isis_run_spf (area, 1, AF_INET6); |
| #endif |
| return retval; |
| } |
| |
| int |
| isis_run_spf_l2 (struct thread *thread) |
| { |
| struct isis_area *area; |
| int retval = ISIS_OK; |
| |
| area = THREAD_ARG(thread); |
| assert (area); |
| |
| 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); |
| #ifdef HAVE_IPV6 |
| if (area->ipv6_circuits) |
| retval = isis_run_spf (area, 2, AF_INET6); |
| #endif |
| |
| 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_add_timer (master, isis_run_spf_l1, area, |
| 60); |
| else |
| thread_add_timer (master, isis_run_spf_l2, area, |
| 60); |
| |
| spftree->pending = 1; |
| return retval; |
| } |
| /* FIXME: This stuff is just mess. All spf thread add/cancel |
| logic should be reviewed. */ |
| /* THREAD_TIMER_OFF(spftree->t_spf_periodic); */ |
| |
| if (diff < MINIMUM_SPF_INTERVAL) { |
| if (level == 1) |
| thread_add_timer (master, isis_run_spf_l1, area, |
| MINIMUM_SPF_INTERVAL - diff); |
| else |
| thread_add_timer (master, isis_run_spf_l2, area, |
| MINIMUM_SPF_INTERVAL - diff); |
| |
| spftree->pending = 1; |
| } else { |
| spftree->pending = 0; |
| retval = isis_run_spf (area, level, AF_INET); |
| } |
| |
| return retval; |
| } |
| |
| #ifdef HAVE_IPV6 |
| 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; |
| |
| THREAD_TIMER_OFF(spftree->t_spf_periodic); |
| |
| /* FIXME: let's wait a minute before doing the SPF */ |
| if (now - isis->uptime < 60 || isis->uptime == 0) { |
| if (level == 1) |
| thread_add_timer (master, isis_run_spf_l1, area, |
| 60); |
| else |
| thread_add_timer (master, isis_run_spf_l2, area, |
| 60); |
| |
| spftree->pending = 1; |
| return retval; |
| } |
| |
| |
| if (diff < MINIMUM_SPF_INTERVAL) { |
| if (level == 1) |
| thread_add_timer (master, isis_run_spf_l1, area, |
| MINIMUM_SPF_INTERVAL - diff); |
| else |
| thread_add_timer (master, isis_run_spf_l2, area, |
| MINIMUM_SPF_INTERVAL - diff); |
| |
| spftree->pending = 1; |
| } else { |
| spftree->pending = 0; |
| retval = isis_run_spf (area, level, AF_INET6); |
| } |
| |
| 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); |
| } |