summaryrefslogtreecommitdiffstats
path: root/ospf6d
diff options
context:
space:
mode:
Diffstat (limited to 'ospf6d')
-rw-r--r--ospf6d/ospf6_area.c4
-rw-r--r--ospf6d/ospf6_intra.c6
-rw-r--r--ospf6d/ospf6_spf.c244
-rw-r--r--ospf6d/ospf6_spf.h1
4 files changed, 181 insertions, 74 deletions
diff --git a/ospf6d/ospf6_area.c b/ospf6d/ospf6_area.c
index 6bbab46ad..bd5e2bd1d 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 b5a0a9209..b1d940952 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 4276f46c3..340d90159 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 2246e2dfc..dbb88d12b 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
generated by cgit v1.2.3 (git 2.39.1) at 2024-12-01 08:45:35 +0100