ospf6d: Fix inter area prefix

Inter Area Prefix LSA ECMP is not working properly.
Two ABRs advertising IAP routes to backbone, not installed
with correct cost or if ABR restarted the route is removed
from backbone.
The current implementation ABR was not suppressing IAP update
for prefix cost is not better or route is not installed.
The better cost or path route was overwritten with non optimal
cost. This caused a loop with nexthops pointing each other
at backbone and non-backbone routers.

Consider to only send BEST/installed route's IAP notification
at ABRs.
When receiving IAP update from multiple ABRs, preserve multiple
advertising routers under the prefix route node.
Upon LSA maxage only remove the advertising route's which is
impacted and update route's nexthops and update FIB.

Testing Done:
Top to Bottom is part of area 0 on the Right, and
from Left side in area 1.
Top and Bottom act as ABRs.
H1 route is sent as Inter-Area Prefix to Right.
Trigger multiple triggers for ABR routes.
1) Shutting down link between, top to right to eliminate nhs
2) Restart frr at Top.
3) Restart frr at Right.

                                     +-----------+
                                     .           |
                                   ,'|   Top     |`.
                                  /  .           |  \
                                ,' ,'+.----------+`. `.
                               /  /  `          `.  \  ',
                             ,' ,' ,'             \  `.  .
                            -  /  `                `.  ', `,
                          ,` ,` ,'                   \   \  \
                         '  -  `                      `.  `, `,
       +--------+    +--`--`--`--+                  +---'---'--'+    +--------+
       |        |    |           |                  |           |    |        |
       |    H1  ------  Left     |                  |   Right   ------   H2   |
       |        |    |           |                  |           |    |        |
       +--------+    +-----------+                  +----.--,-,-+    +--------+
                        `.  `   \                       -  / /
                          \  `.  `                    ,' .` `
                           '   .  \                  /  /  '
                            `.  \  `.               `  / ,'
                              \  `   .            ,`  / /
                               `. `.  .          /   / /
                                 \  .  \       ,'   ' /
                                  '  '--'--------+,'.`
                                   `.|           - /
                                     '  mid1     |/
                                     |           -
                                     +-----------+

Signed-off-by: Chirag Shah <chirag@cumulusnetworks.com>

3 files changed, 270 insertions, 32 deletions

diff --git a/ospf6d/ospf6_abr.c b/ospf6d/ospf6_abr.c
index bc1ce621a..b3aa3b21d 100644
--- a/ospf6d/ospf6_abr.c
+++ b/ospf6d/ospf6_abr.c
@@ -216,11 +216,31 @@ int ospf6_abr_originate_summary_to_area(struct ospf6_route *route,
 		summary_table = area->summary_router;
 	} else {
 		if (IS_OSPF6_DEBUG_ABR
-		    || IS_OSPF6_DEBUG_ORIGINATE(INTER_PREFIX)) {
+		    || IS_OSPF6_DEBUG_ORIGINATE(INTER_PREFIX))
 			is_debug++;
+
+		if (route->type == OSPF6_DEST_TYPE_NETWORK &&
+		    route->path.origin.type ==
+		    htons(OSPF6_LSTYPE_INTER_PREFIX)) {
+			if (!CHECK_FLAG(route->flag, OSPF6_ROUTE_BEST)) {
+				if (is_debug) {
+					inet_ntop(AF_INET,
+						  &(ADV_ROUTER_IN_PREFIX(
+							&route->prefix)), buf,
+						  sizeof(buf));
+					zlog_debug(
+						"%s: route %s with cost %u is not best, ignore."
+						, __PRETTY_FUNCTION__, buf,
+						route->path.cost);
+				}
+				return 0;
+			}
+		}
+
+		if (is_debug) {
 			prefix2str(&route->prefix, buf, sizeof(buf));
-			zlog_debug("Originating summary in area %s for %s",
-				   area->name, buf);
+			zlog_debug("Originating summary in area %s for %s cost %u",
+				   area->name, buf, route->path.cost);
 		}
 		summary_table = area->summary_prefix;
 	}
@@ -679,6 +699,136 @@ void ospf6_abr_defaults_to_stub(struct ospf6 *o)
 	ospf6_route_delete(def);
 }
 
+void ospf6_abr_old_path_update(struct ospf6_route *old_route,
+			       struct ospf6_route *route,
+			       struct ospf6_route_table *table)
+{
+	struct ospf6_path *o_path = NULL;
+	struct listnode *anode, *anext;
+	struct listnode *nnode, *rnode, *rnext;
+	struct ospf6_nexthop *nh, *rnh;
+
+	for (ALL_LIST_ELEMENTS(old_route->paths, anode, anext, o_path)) {
+		if (o_path->area_id != route->path.area_id ||
+		    (memcmp(&(o_path)->origin, &(route)->path.origin,
+			    sizeof(struct ospf6_ls_origin)) != 0))
+			continue;
+
+		if ((o_path->cost == route->path.cost) &&
+		    (o_path->u.cost_e2 == route->path.u.cost_e2))
+			continue;
+
+		for (ALL_LIST_ELEMENTS_RO(o_path->nh_list, nnode, nh)) {
+			for (ALL_LIST_ELEMENTS(old_route->nh_list, rnode,
+					       rnext, rnh)) {
+				if (!ospf6_nexthop_is_same(rnh, nh))
+					continue;
+				listnode_delete(old_route->nh_list, rnh);
+				ospf6_nexthop_delete(rnh);
+			}
+
+		}
+
+		listnode_delete(old_route->paths, o_path);
+		ospf6_path_free(o_path);
+
+		for (ALL_LIST_ELEMENTS(old_route->paths, anode,
+				       anext, o_path)) {
+			ospf6_merge_nexthops(old_route->nh_list,
+					     o_path->nh_list);
+		}
+
+		if (IS_OSPF6_DEBUG_ABR || IS_OSPF6_DEBUG_EXAMIN(INTER_PREFIX))
+			zlog_debug("%s: paths %u nh %u", __PRETTY_FUNCTION__,
+				   old_route->paths ?
+				   listcount(old_route->paths) : 0,
+				   old_route->nh_list ?
+				   listcount(old_route->nh_list) : 0);
+
+		if (table->hook_add)
+			(*table->hook_add)(old_route);
+
+		if (old_route->path.origin.id == route->path.origin.id &&
+		    old_route->path.origin.adv_router ==
+		    route->path.origin.adv_router) {
+			struct ospf6_path *h_path;
+
+			h_path = (struct ospf6_path *)
+			listgetdata(listhead(old_route->paths));
+			old_route->path.origin.type = h_path->origin.type;
+			old_route->path.origin.id = h_path->origin.id;
+			old_route->path.origin.adv_router =
+				h_path->origin.adv_router;
+		}
+	}
+}
+
+void ospf6_abr_old_route_remove(struct ospf6_lsa *lsa,
+				struct ospf6_route *old,
+				struct ospf6_route_table *table)
+{
+	if (listcount(old->paths) > 1) {
+		struct listnode *anode, *anext, *nnode, *rnode, *rnext;
+		struct ospf6_path *o_path;
+		struct ospf6_nexthop *nh, *rnh;
+		bool nh_updated = false;
+		char buf[PREFIX2STR_BUFFER];
+
+		for (ALL_LIST_ELEMENTS(old->paths, anode, anext, o_path)) {
+			if (o_path->origin.adv_router != lsa->header->adv_router
+			    && o_path->origin.id != lsa->header->id)
+				continue;
+			for (ALL_LIST_ELEMENTS_RO(o_path->nh_list, nnode, nh)) {
+				for (ALL_LIST_ELEMENTS(old->nh_list,
+							rnode, rnext, rnh)) {
+					if (!ospf6_nexthop_is_same(rnh, nh))
+						continue;
+					listnode_delete(old->nh_list, rnh);
+					ospf6_nexthop_delete(rnh);
+				}
+			}
+			listnode_delete(old->paths, o_path);
+			ospf6_path_free(o_path);
+			nh_updated = true;
+		}
+
+		if (nh_updated) {
+			if (listcount(old->paths)) {
+				if (IS_OSPF6_DEBUG_ABR ||
+				    IS_OSPF6_DEBUG_EXAMIN(INTER_PREFIX)) {
+					prefix2str(&old->prefix, buf,
+						   sizeof(buf));
+					zlog_debug("%s: old %s updated nh %u",
+						   __PRETTY_FUNCTION__, buf,
+						   old->nh_list ?
+						   listcount(old->nh_list) : 0);
+				}
+
+				if (table->hook_add)
+					(*table->hook_add)(old);
+
+				if ((old->path.origin.id == lsa->header->id) &&
+				    (old->path.origin.adv_router
+						 == lsa->header->adv_router)) {
+					struct ospf6_path *h_path;
+
+					h_path = (struct ospf6_path *)
+						listgetdata(
+							listhead(old->paths));
+					old->path.origin.type =
+						h_path->origin.type;
+					old->path.origin.id = h_path->origin.id;
+					old->path.origin.adv_router =
+						h_path->origin.adv_router;
+				}
+			} else
+				ospf6_route_remove(old, table);
+		}
+	} else
+		ospf6_route_remove(old, table);
+
+}
+
 /* RFC 2328 16.2. Calculating the inter-area routes */
 void ospf6_abr_examin_summary(struct ospf6_lsa *lsa, struct ospf6_area *oa)
 {
@@ -696,6 +846,9 @@ void ospf6_abr_examin_summary(struct ospf6_lsa *lsa, struct ospf6_area *oa)
 	struct ospf6_inter_prefix_lsa *prefix_lsa = NULL;
 	struct ospf6_inter_router_lsa *router_lsa = NULL;
 	bool old_entry_updated = false;
+	struct ospf6_path *path, *o_path, *ecmp_path;
+	struct listnode *anode;
+	char adv_router[16];
 
 	memset(&prefix, 0, sizeof(prefix));
 
@@ -751,10 +904,39 @@ void ospf6_abr_examin_summary(struct ospf6_lsa *lsa, struct ospf6_area *oa)
 	while (route && ospf6_route_is_prefix(&prefix, route)) {
 		if (route->path.area_id == oa->area_id
 		    && route->path.origin.type == lsa->header->type
-		    && route->path.origin.id == lsa->header->id
-		    && route->path.origin.adv_router == lsa->header->adv_router
-		    && !CHECK_FLAG(route->flag, OSPF6_ROUTE_WAS_REMOVED))
-			old = route;
+		    && !CHECK_FLAG(route->flag, OSPF6_ROUTE_WAS_REMOVED)) {
+			/* LSA adv. router could be part of route's
+			 * paths list. Find the existing path and set
+			 * old as the route.
+			 */
+			if (listcount(route->paths) > 1) {
+				struct listnode *anode;
+				struct ospf6_path *o_path;
+
+				for (ALL_LIST_ELEMENTS_RO(route->paths, anode,
+							  o_path)) {
+					inet_ntop(AF_INET,
+						  &o_path->origin.adv_router,
+						  adv_router,
+						  sizeof(adv_router));
+					if (o_path->origin.id == lsa->header->id
+					    && o_path->origin.adv_router ==
+					    lsa->header->adv_router) {
+						old = route;
+
+						if (is_debug)
+							zlog_debug("%s: old entry found in paths, adv_router %s",
+							__PRETTY_FUNCTION__,
+							adv_router);
+
+						break;
+					}
+				}
+			} else if (route->path.origin.id == lsa->header->id &&
+				   route->path.origin.adv_router ==
+				   lsa->header->adv_router)
+				old = route;
+		}
 		route = ospf6_route_next(route);
 	}
 	if (route)
@@ -765,7 +947,7 @@ void ospf6_abr_examin_summary(struct ospf6_lsa *lsa, struct ospf6_area *oa)
 		if (is_debug)
 			zlog_debug("cost is LS_INFINITY, ignore");
 		if (old)
-			ospf6_route_remove(old, table);
+			ospf6_abr_old_route_remove(lsa, old, table);
 		return;
 	}
 	if (OSPF6_LSA_IS_MAXAGE(lsa)) {
@@ -773,14 +955,15 @@ void ospf6_abr_examin_summary(struct ospf6_lsa *lsa, struct ospf6_area *oa)
 			zlog_debug("%s: LSA %s is MaxAge, ignore",
 				   __PRETTY_FUNCTION__, lsa->name);
 		if (old)
-			ospf6_route_remove(old, table);
+			ospf6_abr_old_route_remove(lsa, old, table);
 		return;
 	}
 
 	/* (2) if the LSA is self-originated, ignore */
 	if (lsa->header->adv_router == oa->ospf6->router_id) {
 		if (is_debug)
-			zlog_debug("LSA is self-originated, ignore");
+			zlog_debug("LSA %s is self-originated, ignore",
+				   lsa->name);
 		if (old)
 			ospf6_route_remove(old, table);
 		return;
@@ -888,7 +1071,7 @@ void ospf6_abr_examin_summary(struct ospf6_lsa *lsa, struct ospf6_area *oa)
 	}
 
 	/* Check input prefix-list */
-	if (PREFIX_LIST_IN(oa))
+	if (PREFIX_LIST_IN(oa)) {
 		if (prefix_list_apply(PREFIX_LIST_IN(oa), &prefix)
 		    != PREFIX_PERMIT) {
 			if (is_debug)
@@ -897,14 +1080,12 @@ void ospf6_abr_examin_summary(struct ospf6_lsa *lsa, struct ospf6_area *oa)
 				ospf6_route_remove(old, table);
 			return;
 		}
+	}
 
 	/* (5),(6): the path preference is handled by the sorting
 	   in the routing table. Always install the path by substituting
 	   old route (if any). */
-	if (old)
-		route = ospf6_route_copy(old);
-	else
-		route = ospf6_route_create();
+	route = ospf6_route_create();
 
 	route->type = type;
 	route->prefix = prefix;
@@ -920,11 +1101,8 @@ void ospf6_abr_examin_summary(struct ospf6_lsa *lsa, struct ospf6_area *oa)
 	route->path.type = OSPF6_PATH_TYPE_INTER;
 	route->path.cost = abr_entry->path.cost + cost;
 
-	/* Inter abr_entry is same as brouter.
-	 * Avoid duplicate nexthops to brouter and its
-	 * learnt route. i.e. use merge nexthops.
-	 */
-	ospf6_route_merge_nexthops(route, abr_entry);
+	/* copy brouter rechable nexthops into the route. */
+	ospf6_route_copy_nexthops(route, abr_entry);
 
 	/* (7) If the routes are identical, copy the next hops over to existing
 	   route. ospf6's route table implementation will otherwise string both
@@ -948,20 +1126,69 @@ void ospf6_abr_examin_summary(struct ospf6_lsa *lsa, struct ospf6_area *oa)
 					   old_route->path.cost,
 					   route->path.cost);
 			}
+
+			/* Check new route's adv. router is same in one of
+			 * the paths with differed cost, if so remove the
+			 * old path as later new route will be added.
+			 */
+			if (listcount(old_route->paths) > 1)
+				ospf6_abr_old_path_update(old_route, route,
+							  table);
 			continue;
 		}
 
+		ospf6_route_merge_nexthops(old_route, route);
 		old_entry_updated = true;
-		ospf6_route_merge_nexthops(old, route);
+
+		for (ALL_LIST_ELEMENTS_RO(old_route->paths, anode,
+						  o_path)) {
+			if (o_path->area_id == route->path.area_id &&
+			    (memcmp(&(o_path)->origin, &(route)->path.origin,
+				    sizeof(struct ospf6_ls_origin)) == 0))
+				break;
+		}
+
+		/* New adv. router for a existing path add to paths list */
+		if (o_path == NULL) {
+			ecmp_path = ospf6_path_dup(&route->path);
+
+			/* Add a nh_list to new ecmp path */
+			ospf6_copy_nexthops(ecmp_path->nh_list, route->nh_list);
+
+			/* Add the new path to route's path list */
+			listnode_add_sort(old_route->paths, ecmp_path);
+
+			if (is_debug) {
+				prefix2str(&route->prefix, buf, sizeof(buf));
+				inet_ntop(AF_INET,
+					  &ecmp_path->origin.adv_router,
+					  adv_router, sizeof(adv_router));
+				zlog_debug("%s: route %s cost %u another path %s added with nh %u, effective paths %u nh %u",
+						__PRETTY_FUNCTION__, buf,
+						old_route->path.cost,
+						adv_router,
+						listcount(ecmp_path->nh_list),
+						old_route->paths ?
+						listcount(old_route->paths) : 0,
+						listcount(old_route->nh_list));
+			}
+		} else {
+			/* adv. router exists in the list, update the nhs */
+			list_delete_all_node(o_path->nh_list);
+			ospf6_copy_nexthops(o_path->nh_list, route->nh_list);
+		}
+
 		if (is_debug)
-			zlog_debug("%s: Update route: %s old cost %u new cost %u nh %u",
-				   __PRETTY_FUNCTION__,
-				   buf, old->path.cost, route->path.cost,
+			zlog_debug("%s: Update route: %s %p old cost %u new cost %u nh %u",
+				   __PRETTY_FUNCTION__, buf, (void *)old_route,
+				   old_route->path.cost, route->path.cost,
 				   listcount(route->nh_list));
 
-		/* Update RIB/FIB */
+		/* For Inter-Prefix route: Update RIB/FIB,
+		 * For Inter-Router trigger summary update
+		 */
 		if (table->hook_add)
-			(*table->hook_add)(old);
+			(*table->hook_add)(old_route);
 
 		/* Delete new route */
 		ospf6_route_delete(route);
@@ -969,10 +1196,18 @@ void ospf6_abr_examin_summary(struct ospf6_lsa *lsa, struct ospf6_area *oa)
 	}
 
 	if (old_entry_updated == false) {
-		if (is_debug)
-			zlog_debug("%s: Install route: %s cost %u nh %u",
+		if (is_debug) {
+			inet_ntop(AF_INET, &route->path.origin.adv_router,
+				  adv_router, sizeof(adv_router));
+			zlog_debug("%s: Install route: %s cost %u nh %u adv_router %s ",
 				   __PRETTY_FUNCTION__, buf, route->path.cost,
-				   listcount(route->nh_list));
+				   listcount(route->nh_list), adv_router);
+		}
+
+		path = ospf6_path_dup(&route->path);
+		ospf6_copy_nexthops(path->nh_list, abr_entry->nh_list);
+		listnode_add_sort(route->paths, path);
+
 		/* ospf6_ia_add_nw_route (table, &prefix, route); */
 		ospf6_route_add(route, table);
 	}
diff --git a/ospf6d/ospf6_abr.h b/ospf6d/ospf6_abr.h
index abc383463..e40d15503 100644
--- a/ospf6d/ospf6_abr.h
+++ b/ospf6d/ospf6_abr.h
@@ -76,7 +76,12 @@ extern void ospf6_abr_prefix_resummarize(struct ospf6 *ospf6);
 extern int config_write_ospf6_debug_abr(struct vty *vty);
 extern void install_element_ospf6_debug_abr(void);
 extern int ospf6_abr_config_write(struct vty *vty);
-
+extern void ospf6_abr_old_route_remove(struct ospf6_lsa *lsa,
+				       struct ospf6_route *old,
+				       struct ospf6_route_table *table);
+extern void ospf6_abr_old_path_update(struct ospf6_route *old_route,
+				      struct ospf6_route *route,
+				      struct ospf6_route_table *table);
 extern void ospf6_abr_init(void);
 
 #endif /*OSPF6_ABR_H*/
diff --git a/ospf6d/ospf6_asbr.c b/ospf6d/ospf6_asbr.c
index 8bd0683f1..7f575ee50 100644
--- a/ospf6d/ospf6_asbr.c
+++ b/ospf6d/ospf6_asbr.c
@@ -303,7 +303,6 @@ void ospf6_asbr_update_route_ecmp_path(struct ospf6_route *old,
 					old_route->path.origin.adv_router =
 						h_path->origin.adv_router;
 				}
-				break;
 			} else {
 				if (IS_OSPF6_DEBUG_EXAMIN(AS_EXTERNAL)) {
 					prefix2str(&old_route->prefix, buf,
@@ -316,7 +315,6 @@ void ospf6_asbr_update_route_ecmp_path(struct ospf6_route *old,
 				}
 				ospf6_route_remove(old_route,
 						   ospf6->route_table);
-				break;
 			}
 		}
 		if (route_updated)