From 26e1461672844ec1d0dd065714f740723349dd53 Mon Sep 17 00:00:00 2001 From: Chirag Shah Date: Mon, 13 Nov 2017 15:24:06 +0000 Subject: [PATCH] ospf6d: SPF consider all Router LSAs Based on RFC-5340, there could be multiple Router LSAs associated with Same Advertising Router. During SPF calculation ensure first Root Vertex accommodates all Link state IDs for its originated Router LSAs push them into priority queue. Similarly follow for other Vertexes, considering Router LSAs with multiple Link State IDs. Ticket: CM-18069 Testing Done: Topology: R1 === R2 -- R3 Validated with more than 100 Subinterfaces between R1 === R2 with broadcast links, Validated show ipv6 ospf6 spf tree containing all graph nodes. Validated ip -6 route at R3 and all intra prefix LSAs route installed with ospf6 as protocol. 2) Run R1 === R2 with Point-to-Point links. 3) Perform few other abr and ospf6 test cases of LSA ageout, route install and delete cases. Signed-off-by: Chirag Shah --- ospf6d/ospf6_area.c | 4 +- ospf6d/ospf6_intra.c | 6 +- ospf6d/ospf6_spf.c | 244 +++++++++++++++++++++++++++++++------------ ospf6d/ospf6_spf.h | 1 + 4 files changed, 181 insertions(+), 74 deletions(-) diff --git a/ospf6d/ospf6_area.c b/ospf6d/ospf6_area.c index 6bbab46ad8..bd5e2bd1d3 100644 --- a/ospf6d/ospf6_area.c +++ b/ospf6d/ospf6_area.c @@ -61,8 +61,8 @@ static void ospf6_area_lsdb_hook_add(struct ospf6_lsa *lsa) case OSPF6_LSTYPE_ROUTER: case OSPF6_LSTYPE_NETWORK: if (IS_OSPF6_DEBUG_EXAMIN_TYPE(lsa->header->type)) { - zlog_debug("Examin %s", lsa->name); - zlog_debug("Schedule SPF Calculation for %s", + zlog_debug("%s Examin LSA %s", __PRETTY_FUNCTION__, lsa->name); + zlog_debug(" Schedule SPF Calculation for %s", OSPF6_AREA(lsa->lsdb->data)->name); } ospf6_spf_schedule( diff --git a/ospf6d/ospf6_intra.c b/ospf6d/ospf6_intra.c index b5a0a9209b..b1d940952c 100644 --- a/ospf6d/ospf6_intra.c +++ b/ospf6d/ospf6_intra.c @@ -1316,7 +1316,7 @@ void ospf6_intra_prefix_lsa_add(struct ospf6_lsa *lsa) return; if (IS_OSPF6_DEBUG_EXAMIN(INTRA_PREFIX)) - zlog_debug("%s found", lsa->name); + zlog_debug("%s: LSA %s found", __PRETTY_FUNCTION__, lsa->name); oa = OSPF6_AREA(lsa->lsdb->data); @@ -1325,7 +1325,7 @@ void ospf6_intra_prefix_lsa_add(struct ospf6_lsa *lsa) lsa->header); if (intra_prefix_lsa->ref_type == htons(OSPF6_LSTYPE_ROUTER)) ospf6_linkstate_prefix(intra_prefix_lsa->ref_adv_router, - htonl(0), &ls_prefix); + intra_prefix_lsa->ref_id, &ls_prefix); else if (intra_prefix_lsa->ref_type == htons(OSPF6_LSTYPE_NETWORK)) ospf6_linkstate_prefix(intra_prefix_lsa->ref_adv_router, intra_prefix_lsa->ref_id, &ls_prefix); @@ -1404,7 +1404,7 @@ void ospf6_intra_prefix_lsa_add(struct ospf6_lsa *lsa) if (IS_OSPF6_DEBUG_EXAMIN(INTRA_PREFIX)) { prefix2str(&route->prefix, buf, sizeof(buf)); - zlog_debug(" add %s", buf); + zlog_debug(" route %s add", buf); } ospf6_route_add(route, oa->route_table); diff --git a/ospf6d/ospf6_spf.c b/ospf6d/ospf6_spf.c index 4276f46c38..340d90159f 100644 --- a/ospf6d/ospf6_spf.c +++ b/ospf6d/ospf6_spf.c @@ -110,26 +110,30 @@ static struct ospf6_vertex *ospf6_vertex_create(struct ospf6_lsa *lsa) sizeof(struct ospf6_vertex)); /* type */ - if (ntohs(lsa->header->type) == OSPF6_LSTYPE_ROUTER) + if (ntohs(lsa->header->type) == OSPF6_LSTYPE_ROUTER) { v->type = OSPF6_VERTEX_TYPE_ROUTER; - else if (ntohs(lsa->header->type) == OSPF6_LSTYPE_NETWORK) + /* Router LSA use Link ID 0 as base in vertex_id */ + ospf6_linkstate_prefix(lsa->header->adv_router, htonl(0), + &v->vertex_id); + } else if (ntohs(lsa->header->type) == OSPF6_LSTYPE_NETWORK) { v->type = OSPF6_VERTEX_TYPE_NETWORK; - else - assert(0); - - /* vertex_id */ - ospf6_linkstate_prefix(lsa->header->adv_router, lsa->header->id, + /* vertex_id */ + ospf6_linkstate_prefix(lsa->header->adv_router, lsa->header->id, &v->vertex_id); + } else + assert(0); /* name */ ospf6_linkstate_prefix2str(&v->vertex_id, v->name, sizeof(v->name)); if (IS_OSPF6_DEBUG_SPF(PROCESS)) - zlog_debug("%s: Creating vertex %s of type %s", __func__, - v->name, + zlog_debug("%s: Creating vertex %s of type %s (0x%04hx) lsa %s", + __func__, v->name, ((ntohs(lsa->header->type) == OSPF6_LSTYPE_ROUTER) ? "Router" - : "N/W")); + : "N/W"), ntohs(lsa->header->type), + lsa->name); + /* Associated LSA */ v->lsa = lsa; @@ -158,7 +162,8 @@ static void ospf6_vertex_delete(struct ospf6_vertex *v) } static struct ospf6_lsa *ospf6_lsdesc_lsa(caddr_t lsdesc, - struct ospf6_vertex *v) + struct ospf6_vertex *v, + uint32_t link_id) { struct ospf6_lsa *lsa; u_int16_t type = 0; @@ -166,12 +171,12 @@ static struct ospf6_lsa *ospf6_lsdesc_lsa(caddr_t lsdesc, if (VERTEX_IS_TYPE(NETWORK, v)) { type = htons(OSPF6_LSTYPE_ROUTER); - id = htonl(0); + id = link_id; adv_router = NETWORK_LSDESC_GET_NBR_ROUTERID(lsdesc); } else { if (ROUTER_LSDESC_IS_TYPE(POINTTOPOINT, lsdesc)) { type = htons(OSPF6_LSTYPE_ROUTER); - id = htonl(0); + id = link_id; adv_router = ROUTER_LSDESC_GET_NBR_ROUTERID(lsdesc); } else if (ROUTER_LSDESC_IS_TYPE(TRANSIT_NETWORK, lsdesc)) { type = htons(OSPF6_LSTYPE_NETWORK); @@ -187,10 +192,12 @@ static struct ospf6_lsa *ospf6_lsdesc_lsa(caddr_t lsdesc, inet_ntop(AF_INET, &id, ibuf, sizeof(ibuf)); inet_ntop(AF_INET, &adv_router, abuf, sizeof(abuf)); if (lsa) - zlog_debug(" Link to: %s", lsa->name); + zlog_debug(" Link to: %s , V %s id %u", lsa->name, + v->name, link_id); else - zlog_debug(" Link to: [%s Id:%s Adv:%s] No LSA", - ospf6_lstype_name(type), ibuf, abuf); + zlog_debug(" Link to: [%s Id:%s Adv:%s] No LSA , V %s id %u", + ospf6_lstype_name(type), ibuf, abuf, + v->name, link_id); } return lsa; @@ -308,10 +315,11 @@ static int ospf6_spf_install(struct ospf6_vertex *v, { struct ospf6_route *route, *parent_route; struct ospf6_vertex *prev; + char pbuf[PREFIX2STR_BUFFER]; if (IS_OSPF6_DEBUG_SPF(PROCESS)) - zlog_debug("SPF install %s hops %d cost %d", v->name, v->hops, - v->cost); + zlog_debug("SPF install %s (lsa %s) hops %d cost %d", v->name, + v->lsa->name, v->hops, v->cost); route = ospf6_route_lookup(&v->vertex_id, result_table); if (route && route->path.cost < v->cost) { @@ -322,16 +330,30 @@ static int ospf6_spf_install(struct ospf6_vertex *v, ospf6_vertex_delete(v); return -1; } else if (route && route->path.cost == v->cost) { - if (IS_OSPF6_DEBUG_SPF(PROCESS)) - zlog_debug(" another path found, merge"); - + if (IS_OSPF6_DEBUG_SPF(PROCESS)) { + prefix2str(&route->prefix, pbuf, sizeof(pbuf)); + zlog_debug(" another path found to route %s lsa %s, merge", + pbuf, v->lsa->name); + } ospf6_spf_merge_nexthops_to_route(route, v); prev = (struct ospf6_vertex *)route->route_option; assert(prev->hops <= v->hops); - ospf6_vertex_delete(v); + if ((VERTEX_IS_TYPE(ROUTER, v) && + route->path.origin.id != v->lsa->header->id)) { + if (IS_OSPF6_DEBUG_SPF(PROCESS)) { + zlog_debug("%s: V lsa %s id %u, route id %u are different", + __PRETTY_FUNCTION__, v->lsa->name, + ntohl(v->lsa->header->id), + ntohl(route->path.origin.id)); + } + return 0; + } + + ospf6_vertex_delete(v); return -1; + } /* There should be no case where candidate being installed (variable @@ -438,8 +460,10 @@ void ospf6_spf_calculation(u_int32_t router_id, struct ospf6_vertex *root, *v, *w; int size; caddr_t lsdesc; - struct ospf6_lsa *lsa; + struct ospf6_lsa *lsa, *self_rtr_lsa = NULL, *rtr_lsa = NULL; + const struct route_node *end = NULL; struct in6_addr address; + struct ospf6_lsdb *lsdb = NULL; ospf6_spf_table_finish(result_table); @@ -454,6 +478,8 @@ void ospf6_spf_calculation(u_int32_t router_id, return; } + self_rtr_lsa = lsa; + /* initialize */ candidate_list = pqueue_create(); candidate_list->cmp = ospf6_vertex_cmp; @@ -462,6 +488,7 @@ void ospf6_spf_calculation(u_int32_t router_id, root->area = oa; root->cost = 0; root->hops = 0; + root->link_id = lsa->header->id; inet_pton(AF_INET6, "::1", &address); /* Actually insert root to the candidate-list as the only candidate */ @@ -482,55 +509,134 @@ void ospf6_spf_calculation(u_int32_t router_id, && ospf6_router_is_stub_router(v->lsa))) continue; - /* For each LS description in the just-added vertex V's LSA */ - size = (VERTEX_IS_TYPE(ROUTER, v) - ? sizeof(struct ospf6_router_lsdesc) - : sizeof(struct ospf6_network_lsdesc)); - for (lsdesc = OSPF6_LSA_HEADER_END(v->lsa->header) + 4; - lsdesc + size <= OSPF6_LSA_END(v->lsa->header); - lsdesc += size) { - lsa = ospf6_lsdesc_lsa(lsdesc, v); - if (lsa == NULL) - continue; - - if (OSPF6_LSA_IS_MAXAGE(lsa)) - continue; - - if (!ospf6_lsdesc_backlink(lsa, lsdesc, v)) - continue; - - w = ospf6_vertex_create(lsa); - w->area = oa; - w->parent = v; - if (VERTEX_IS_TYPE(ROUTER, v)) { - w->cost = v->cost - + ROUTER_LSDESC_GET_METRIC(lsdesc); - w->hops = - v->hops - + (VERTEX_IS_TYPE(NETWORK, w) ? 0 : 1); - } else /* NETWORK */ - { - w->cost = v->cost; - w->hops = v->hops + 1; + if (VERTEX_IS_TYPE(ROUTER, v)) { + /* First fetch root Router LSAs from lsdb_self */ + if (v->lsa == self_rtr_lsa) + lsdb = oa->lsdb_self; + else + lsdb = v->area->lsdb; + + /* Iterating multiple ROUTER LSAs from same adv router + * with different Link State ID */ + end = ospf6_lsdb_head(lsdb, 2, + htons(OSPF6_LSTYPE_ROUTER), + v->lsa->header->adv_router, + &rtr_lsa); + while (rtr_lsa) { + if (IS_OSPF6_DEBUG_SPF(PROCESS)) + zlog_debug("%s: Next LSA %s to process" + ,__PRETTY_FUNCTION__, + rtr_lsa->name); + size = sizeof(struct ospf6_router_lsdesc); + /* For each LS description in the just-added vertex V's LSA */ + for (lsdesc = OSPF6_LSA_HEADER_END( + rtr_lsa->header) + 4; + lsdesc + size <= OSPF6_LSA_END( + rtr_lsa->header); + lsdesc += size) { + lsa = ospf6_lsdesc_lsa(lsdesc, v, + rtr_lsa->header->id); + if (lsa == NULL) + continue; + + if (OSPF6_LSA_IS_MAXAGE(lsa)) + continue; + + if (!ospf6_lsdesc_backlink(lsa, + lsdesc, v)) + continue; + + w = ospf6_vertex_create(lsa); + w->area = oa; + w->parent = v; + w->link_id = rtr_lsa->header->id; + + if (VERTEX_IS_TYPE(ROUTER, v)) { + w->cost = v->cost + + ROUTER_LSDESC_GET_METRIC(lsdesc); + w->hops = + v->hops + + (VERTEX_IS_TYPE(NETWORK, w) + ? 0 : 1); + } else /* NETWORK */ { + w->cost = v->cost; + w->hops = v->hops + 1; + } + + /* nexthop calculation */ + if (w->hops == 0) + ospf6_add_nexthop(w->nh_list, + ROUTER_LSDESC_GET_IFID(lsdesc) + , NULL); + else if (w->hops == 1 && v->hops == 0) + ospf6_nexthop_calc(w, v, lsdesc); + else { + ospf6_copy_nexthops(w->nh_list, + v->nh_list); + } + + /* add new candidate to the candidate_list */ + if (IS_OSPF6_DEBUG_SPF(PROCESS)) + zlog_debug( + " New candidate: %s hops %d cost %d", + w->name, w->hops, + w->cost); + pqueue_enqueue(w, candidate_list); + } + /* Fetch next Link state ID Router LSA */ + rtr_lsa = ospf6_lsdb_next(end, rtr_lsa); } - - /* nexthop calculation */ - if (w->hops == 0) - ospf6_add_nexthop( - w->nh_list, + } else { + /* For each LS description in the just-added vertex V's LSA */ + size = (VERTEX_IS_TYPE(ROUTER, v) + ? sizeof(struct ospf6_router_lsdesc) + : sizeof(struct ospf6_network_lsdesc)); + for (lsdesc = OSPF6_LSA_HEADER_END(v->lsa->header) + 4; + lsdesc + size <= OSPF6_LSA_END(v->lsa->header); + lsdesc += size) { + lsa = ospf6_lsdesc_lsa(lsdesc, v, v->link_id); + if (lsa == NULL) + continue; + + if (OSPF6_LSA_IS_MAXAGE(lsa)) + continue; + + if (!ospf6_lsdesc_backlink(lsa, lsdesc, v)) + continue; + + w = ospf6_vertex_create(lsa); + w->area = oa; + w->parent = v; + if (VERTEX_IS_TYPE(ROUTER, v)) { + w->cost = v->cost + + ROUTER_LSDESC_GET_METRIC(lsdesc); + w->hops = + v->hops + + (VERTEX_IS_TYPE(NETWORK, w) ? + 0 : 1); + } else /* NETWORK */ { + w->cost = v->cost; + w->hops = v->hops + 1; + } + + /* nexthop calculation */ + if (w->hops == 0) + ospf6_add_nexthop(w->nh_list, ROUTER_LSDESC_GET_IFID(lsdesc), NULL); - else if (w->hops == 1 && v->hops == 0) - ospf6_nexthop_calc(w, v, lsdesc); - else { - ospf6_copy_nexthops(w->nh_list, v->nh_list); - } - - /* add new candidate to the candidate_list */ - if (IS_OSPF6_DEBUG_SPF(PROCESS)) - zlog_debug( + else if (w->hops == 1 && v->hops == 0) + ospf6_nexthop_calc(w, v, lsdesc); + else { + ospf6_copy_nexthops(w->nh_list, + v->nh_list); + } + + /* add new candidate to the candidate_list */ + if (IS_OSPF6_DEBUG_SPF(PROCESS)) + zlog_debug( " New candidate: %s hops %d cost %d", - w->name, w->hops, w->cost); - pqueue_enqueue(w, candidate_list); + w->name, w->hops, w->cost); + pqueue_enqueue(w, candidate_list); + } } } diff --git a/ospf6d/ospf6_spf.h b/ospf6d/ospf6_spf.h index 2246e2dfc7..dbb88d12ba 100644 --- a/ospf6d/ospf6_spf.h +++ b/ospf6d/ospf6_spf.h @@ -68,6 +68,7 @@ struct ospf6_vertex { /* nexthops to this node */ struct list *nh_list; + uint32_t link_id; }; #define OSPF6_VERTEX_TYPE_ROUTER 0x01 -- 2.39.5