From d034aa027ef44d0a74805c27ad2a4d8ea20395d1 Mon Sep 17 00:00:00 2001 From: Peter Szilagyi Date: Sat, 1 Oct 2011 17:22:51 +0400 Subject: isisd: fix wrong next-hops from SPF The forwarding table was filled with wrong next-hops, and which is even worse, it was done in a totally non-deterministic way. The next-hop set for an IP prefix by isisd was the neighbor IS from which the flooded LSP about the IP prefix was arrived. So, if an IS received all the LSPs through its, say, eth0 interface, all entries in the forwarding table contained the next IS reachable via eth0 as the next-hop. The solution is to propagate the correct next-hop further from node to node as the SPF algorithm traverses the graph and selects the next node to be added to the set of already covered nodes. Also, the construction of the tentative node list (the nodes where the shortest path is not known yet) was buggy: if a node was already a member of this list with a certain path cost, and an alternative path was found to it with a lower cost while processing a pseudo-node LSP, it was not added to the list. This way, the path selected by isisd for a certain prefix was the first one it encountered during the LSDB processing. Signed-off-by: Fritz Reichmann --- isisd/isis_spf.c | 53 ++++++++++++++++++++++++++++------------------------- 1 file changed, 28 insertions(+), 25 deletions(-) (limited to 'isisd/isis_spf.c') diff --git a/isisd/isis_spf.c b/isisd/isis_spf.c index 5d7e9da4..b6178e3a 100644 --- a/isisd/isis_spf.c +++ b/isisd/isis_spf.c @@ -405,12 +405,13 @@ isis_spf_add2tent (struct isis_spftree *spftree, enum vertextype vtype, if (adj) listnode_add (vertex->Adj_N, adj); + #ifdef EXTREME_DEBUG zlog_debug ("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); @@ -549,7 +550,8 @@ process_N (struct isis_spftree *spftree, enum vertextype vtype, void *id, */ static int isis_spf_process_lsp (struct isis_spftree *spftree, struct isis_lsp *lsp, - uint32_t cost, uint16_t depth, int family) + uint32_t cost, uint16_t depth, int family, + struct isis_adjacency *adj) { struct listnode *node, *fragnode = NULL; u_int16_t dist; @@ -563,9 +565,6 @@ isis_spf_process_lsp (struct isis_spftree *spftree, struct isis_lsp *lsp, 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; @@ -591,7 +590,7 @@ lspfragloop: 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); + depth + 1, adj, family); } } if (lsp->tlv_data.te_is_neighs) @@ -607,7 +606,7 @@ lspfragloop: vtype = LSP_PSEUDO_ID (te_is_neigh->neigh_id) ? VTYPE_PSEUDO_TE_IS : VTYPE_NONPSEUDO_TE_IS; process_N (spftree, vtype, (void *) te_is_neigh->neigh_id, dist, - depth + 1, lsp->adj, family); + depth + 1, adj, family); } } if (family == AF_INET && lsp->tlv_data.ipv4_int_reachs) @@ -621,7 +620,7 @@ lspfragloop: prefix.u.prefix4 = ipreach->prefix; prefix.prefixlen = ip_masklen (ipreach->mask); process_N (spftree, vtype, (void *) &prefix, dist, depth + 1, - lsp->adj, family); + adj, family); } } @@ -636,7 +635,7 @@ lspfragloop: prefix.u.prefix4 = ipreach->prefix; prefix.prefixlen = ip_masklen (ipreach->mask); process_N (spftree, vtype, (void *) &prefix, dist, depth + 1, - lsp->adj, family); + adj, family); } } if (family == AF_INET && lsp->tlv_data.te_ipv4_reachs) @@ -651,7 +650,7 @@ lspfragloop: te_ipv4_reach->control); prefix.prefixlen = (te_ipv4_reach->control & 0x3F); process_N (spftree, vtype, (void *) &prefix, dist, depth + 1, - lsp->adj, family); + adj, family); } } #ifdef HAVE_IPV6 @@ -668,7 +667,7 @@ lspfragloop: memcpy (&prefix.u.prefix6.s6_addr, ip6reach->prefix, PSIZE (ip6reach->prefix_len)); process_N (spftree, vtype, (void *) &prefix, dist, depth + 1, - lsp->adj, family); + adj, family); } } #endif /* HAVE_IPV6 */ @@ -691,7 +690,8 @@ lspfragloop: static int isis_spf_process_pseudo_lsp (struct isis_spftree *spftree, struct isis_lsp *lsp, uint16_t cost, - uint16_t depth, int family) + uint16_t depth, int family, + struct isis_adjacency *adj) { struct listnode *node, *fragnode = NULL; struct is_neigh *is_neigh; @@ -715,13 +715,13 @@ pseudofragloop: /* 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 + if ((depth > 0 || isis_find_vertex + (spftree->tents, (void *) is_neigh->neigh_id, vtype) == NULL) && isis_find_vertex (spftree->paths, (void *) is_neigh->neigh_id, vtype) == NULL) { /* C.2.5 i) */ - isis_spf_add2tent (spftree, vtype, is_neigh->neigh_id, lsp->adj, + isis_spf_add2tent (spftree, vtype, is_neigh->neigh_id, adj, cost, depth, family); } } @@ -733,13 +733,13 @@ pseudofragloop: /* Two way connectivity */ if (!memcmp (te_is_neigh->neigh_id, isis->sysid, ISIS_SYS_ID_LEN)) continue; - if (isis_find_vertex - (spftree->tents, (void *) te_is_neigh->neigh_id, vtype) == NULL + if ((depth > 0 || isis_find_vertex + (spftree->tents, (void *) te_is_neigh->neigh_id, vtype) == NULL) && isis_find_vertex (spftree->paths, (void *) te_is_neigh->neigh_id, vtype) == NULL) { /* C.2.5 i) */ - isis_spf_add2tent (spftree, vtype, te_is_neigh->neigh_id, lsp->adj, + isis_spf_add2tent (spftree, vtype, te_is_neigh->neigh_id, adj, cost, depth, family); } } @@ -860,9 +860,6 @@ isis_spf_preload_tent (struct isis_spftree *spftree, 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: @@ -885,14 +882,14 @@ isis_spf_preload_tent (struct isis_spftree *spftree, { zlog_warn ("ISIS-Spf: No adjacency found for DR"); } - if (lsp == NULL || lsp->lsp_header->rem_lifetime == 0) + else 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->te_metric[level - 1], 0, family); + circuit->te_metric[level - 1], 0, family, adj); } } @@ -982,6 +979,7 @@ isis_run_spf (struct isis_area *area, int level, int family) struct isis_spftree *spftree = NULL; u_char lsp_id[ISIS_SYS_ID_LEN + 2]; struct isis_lsp *lsp; + struct isis_adjacency *adj = NULL; struct route_table *table = NULL; struct route_node *rode; struct isis_route_info *rinfo; @@ -1042,6 +1040,11 @@ isis_run_spf (struct isis_area *area, int level, int family) if (vertex->type == VTYPE_PSEUDO_IS || vertex->type == VTYPE_NONPSEUDO_IS) { + if (listcount(vertex->Adj_N) == 0) { + continue; + } + adj = listgetdata(vertex->Adj_N->head); + 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]); @@ -1050,13 +1053,13 @@ isis_run_spf (struct isis_area *area, int level, int family) if (LSP_PSEUDO_ID (lsp_id)) { isis_spf_process_pseudo_lsp (spftree, lsp, vertex->d_N, - vertex->depth, family); + vertex->depth, family, adj); } else { isis_spf_process_lsp (spftree, lsp, vertex->d_N, - vertex->depth, family); + vertex->depth, family, adj); } } else -- cgit v1.2.1 From c25eaffdb2190149e768dc4ee4efc913c6d02992 Mon Sep 17 00:00:00 2001 From: Fritz Reichmann Date: Sat, 1 Oct 2011 17:43:12 +0400 Subject: isisd: unexpected kernel routing table (BZ#544) Fix bug 544: isisd produces an unexpected routing table for wide-metric. * isis_spf.c: Accept VTYPE_PSEUDO_TE_IS and VTYPE_NONPSEUDO_TE_IS vertex types for SPF calculation * isis_pdu.c: Change order of TLVs to match Cisco to make bitwise comparison easier for Wireshark * isis_tlv.c: EXTREME_TLV_DEBUG for TLV debugging instead of EXTREME_DEBUG --- isisd/isis_spf.c | 12 +++++++++--- 1 file changed, 9 insertions(+), 3 deletions(-) (limited to 'isisd/isis_spf.c') diff --git a/isisd/isis_spf.c b/isisd/isis_spf.c index b6178e3a..5d0b161f 100644 --- a/isisd/isis_spf.c +++ b/isisd/isis_spf.c @@ -1030,15 +1030,22 @@ isis_run_spf (struct isis_area *area, int level, int family) while (listcount (spftree->tents) > 0) { + /* C.2.7 a) 1) */ node = listhead (spftree->tents); vertex = listgetdata (node); - /* Remove from tent list */ + + /* C.2.7 a) 2) */ list_delete_node (spftree->tents, node); + + /* C.2.7 a) 3) */ if (isis_find_vertex (spftree->paths, vertex->N.id, vertex->type)) continue; add_to_paths (spftree, vertex, area, level); + if (vertex->type == VTYPE_PSEUDO_IS || - vertex->type == VTYPE_NONPSEUDO_IS) + vertex->type == VTYPE_NONPSEUDO_IS || + vertex->type == VTYPE_PSEUDO_TE_IS || + vertex->type == VTYPE_NONPSEUDO_TE_IS ) { if (listcount(vertex->Adj_N) == 0) { continue; @@ -1054,7 +1061,6 @@ isis_run_spf (struct isis_area *area, int level, int family) { isis_spf_process_pseudo_lsp (spftree, lsp, vertex->d_N, vertex->depth, family, adj); - } else { -- cgit v1.2.1