lib,zebra: add api to enforce nexthop sort order when copying

Add an api that creates a copy of a list of nexthops and
enforces the canonical sort ordering; consolidate some nhg
code to avoid copy-and-paste. The zebra dplane uses
that api when a plugin sets up a list of nexthops, ensuring
that the plugin's list is ordered when it's processed in
zebra.

Signed-off-by: Mark Stapp <mjs@voltanet.io>

3 files changed, 76 insertions, 19 deletions

diff --git a/lib/nexthop_group.c b/lib/nexthop_group.c
index b810d13a5..e1c1b1ca8 100644
--- a/lib/nexthop_group.c
+++ b/lib/nexthop_group.c
@@ -243,25 +243,16 @@ void _nexthop_add(struct nexthop **target, struct nexthop *nexthop)
 	nexthop->prev = last;
 }
 
-void nexthop_group_add_sorted(struct nexthop_group *nhg,
-			      struct nexthop *nexthop)
+/* Add nexthop to sorted list of nexthops */
+static void _nexthop_add_sorted(struct nexthop **head,
+				struct nexthop *nexthop)
 {
-	struct nexthop *position, *prev, *tail;
-
-	/* Try to just append to the end first
-	 * This trust it is already sorted
-	 */
-
-	tail = nexthop_group_tail(nhg);
+	struct nexthop *position, *prev;
 
-	if (tail && (nexthop_cmp(tail, nexthop) < 0)) {
-		tail->next = nexthop;
-		nexthop->prev = tail;
-
-		return;
-	}
+	/* Ensure this gets set */
+	nexthop->next = NULL;
 
-	for (position = nhg->nexthop, prev = NULL; position;
+	for (position = *head, prev = NULL; position;
 	     prev = position, position = position->next) {
 		if (nexthop_cmp(position, nexthop) > 0) {
 			nexthop->next = position;
@@ -270,7 +261,7 @@ void nexthop_group_add_sorted(struct nexthop_group *nhg,
 			if (nexthop->prev)
 				nexthop->prev->next = nexthop;
 			else
-				nhg->nexthop = nexthop;
+				*head = nexthop;
 
 			position->prev = nexthop;
 			return;
@@ -281,7 +272,27 @@ void nexthop_group_add_sorted(struct nexthop_group *nhg,
 	if (prev)
 		prev->next = nexthop;
 	else
-		nhg->nexthop = nexthop;
+		*head = nexthop;
+}
+
+void nexthop_group_add_sorted(struct nexthop_group *nhg,
+			      struct nexthop *nexthop)
+{
+	struct nexthop *tail;
+
+	/* Try to just append to the end first;
+	 * trust the list is already sorted
+	 */
+	tail = nexthop_group_tail(nhg);
+
+	if (tail && (nexthop_cmp(tail, nexthop) < 0)) {
+		tail->next = nexthop;
+		nexthop->prev = tail;
+
+		return;
+	}
+
+	_nexthop_add_sorted(&nhg->nexthop, nexthop);
 }
 
 /* Delete nexthop from a nexthop list.  */
@@ -308,6 +319,40 @@ void _nexthop_del(struct nexthop_group *nhg, struct nexthop *nh)
 	nh->next = NULL;
 }
 
+/*
+ * Copy a list of nexthops in 'nh' to an nhg, enforcing canonical sort order
+ */
+void nexthop_group_copy_nh_sorted(struct nexthop_group *nhg,
+				  const struct nexthop *nh)
+{
+	struct nexthop *nexthop, *tail;
+	const struct nexthop *nh1;
+
+	/* We'll try to append to the end of the new list;
+	 * if the original list in nh is already sorted, this eliminates
+	 * lots of comparison operations.
+	 */
+	tail = nexthop_group_tail(nhg);
+
+	for (nh1 = nh; nh1; nh1 = nh1->next) {
+		nexthop = nexthop_dup(nh1, NULL);
+
+		if (tail && (nexthop_cmp(tail, nexthop) < 0)) {
+			tail->next = nexthop;
+			nexthop->prev = tail;
+
+			tail = nexthop;
+			continue;
+		}
+
+		_nexthop_add_sorted(&nhg->nexthop, nexthop);
+
+		if (tail == NULL)
+			tail = nexthop;
+	}
+}
+
+/* Copy a list of nexthops, no effort made to sort or order them. */
 void copy_nexthops(struct nexthop **tnh, const struct nexthop *nh,
 		   struct nexthop *rparent)
 {
diff --git a/lib/nexthop_group.h b/lib/nexthop_group.h
index c90b21737..73b020283 100644
--- a/lib/nexthop_group.h
+++ b/lib/nexthop_group.h
@@ -44,6 +44,13 @@ void nexthop_group_delete(struct nexthop_group **nhg);
 
 void nexthop_group_copy(struct nexthop_group *to,
 			struct nexthop_group *from);
+
+/*
+ * Copy a list of nexthops in 'nh' to an nhg, enforcing canonical sort order
+ */
+void nexthop_group_copy_nh_sorted(struct nexthop_group *nhg,
+				  const struct nexthop *nh);
+
 void copy_nexthops(struct nexthop **tnh, const struct nexthop *nh,
 		   struct nexthop *rparent);
 
diff --git a/zebra/zebra_dplane.c b/zebra/zebra_dplane.c
index ca72ea522..ef942151b 100644
--- a/zebra/zebra_dplane.c
+++ b/zebra/zebra_dplane.c
@@ -1023,6 +1023,11 @@ uint8_t dplane_ctx_get_old_distance(const struct zebra_dplane_ctx *ctx)
 	return ctx->u.rinfo.zd_old_distance;
 }
 
+/*
+ * Set the nexthops associated with a context: note that processing code
+ * may well expect that nexthops are in canonical (sorted) order, so we
+ * will enforce that here.
+ */
 void dplane_ctx_set_nexthops(struct zebra_dplane_ctx *ctx, struct nexthop *nh)
 {
 	DPLANE_CTX_VALID(ctx);
@@ -1031,7 +1036,7 @@ void dplane_ctx_set_nexthops(struct zebra_dplane_ctx *ctx, struct nexthop *nh)
 		nexthops_free(ctx->u.rinfo.zd_ng.nexthop);
 		ctx->u.rinfo.zd_ng.nexthop = NULL;
 	}
-	copy_nexthops(&(ctx->u.rinfo.zd_ng.nexthop), nh, NULL);
+	nexthop_group_copy_nh_sorted(&(ctx->u.rinfo.zd_ng), nh);
 }
 
 const struct nexthop_group *dplane_ctx_get_ng(