lib: Sort zapi_nexthops on the encode

Sort nexthops before we push them to zebra. This offloads
the nexthop sorting zebra is doing onto the upper level protocols
so that when it gets to zebra and we construct a group, it just has
to append them to the tail for every nexthop.

Signed-off-by: Stephen Worley <sworley@cumulusnetworks.com>

3 files changed, 95 insertions, 5 deletions

diff --git a/lib/nexthop.c b/lib/nexthop.c
index 0984c1a16..cf5bed3d6 100644
--- a/lib/nexthop.c
+++ b/lib/nexthop.c
@@ -65,9 +65,8 @@ static int _nexthop_labels_cmp(const struct nexthop *nh1,
 	return memcmp(nhl1->label, nhl2->label, nhl1->num_labels);
 }
 
-static int _nexthop_g_addr_cmp(enum nexthop_types_t type,
-			       const union g_addr *addr1,
-			       const union g_addr *addr2)
+int nexthop_g_addr_cmp(enum nexthop_types_t type, const union g_addr *addr1,
+		       const union g_addr *addr2)
 {
 	int ret = 0;
 
@@ -92,13 +91,13 @@ static int _nexthop_g_addr_cmp(enum nexthop_types_t type,
 static int _nexthop_gateway_cmp(const struct nexthop *nh1,
 				const struct nexthop *nh2)
 {
-	return _nexthop_g_addr_cmp(nh1->type, &nh1->gate, &nh2->gate);
+	return nexthop_g_addr_cmp(nh1->type, &nh1->gate, &nh2->gate);
 }
 
 static int _nexthop_source_cmp(const struct nexthop *nh1,
 			       const struct nexthop *nh2)
 {
-	return _nexthop_g_addr_cmp(nh1->type, &nh1->src, &nh2->src);
+	return nexthop_g_addr_cmp(nh1->type, &nh1->src, &nh2->src);
 }
 
 static int _nexthop_cmp_no_labels(const struct nexthop *next1,
diff --git a/lib/nexthop.h b/lib/nexthop.h
index 20401cd58..9dd5fc6fd 100644
--- a/lib/nexthop.h
+++ b/lib/nexthop.h
@@ -142,6 +142,9 @@ extern bool nexthop_same(const struct nexthop *nh1, const struct nexthop *nh2);
 extern bool nexthop_same_no_labels(const struct nexthop *nh1,
 				   const struct nexthop *nh2);
 extern int nexthop_cmp(const struct nexthop *nh1, const struct nexthop *nh2);
+extern int nexthop_g_addr_cmp(enum nexthop_types_t type,
+			      const union g_addr *addr1,
+			      const union g_addr *addr2);
 
 extern const char *nexthop_type_to_str(enum nexthop_types_t nh_type);
 extern bool nexthop_labels_match(const struct nexthop *nh1,
diff --git a/lib/zclient.c b/lib/zclient.c
index 693770019..cb9f92723 100644
--- a/lib/zclient.c
+++ b/lib/zclient.c
@@ -765,6 +765,92 @@ int zclient_route_send(uint8_t cmd, struct zclient *zclient,
 	return zclient_send_message(zclient);
 }
 
+static int zapi_nexthop_labels_cmp(const struct zapi_nexthop *next1,
+				   const struct zapi_nexthop *next2)
+{
+	if (next1->label_num > next2->label_num)
+		return 1;
+
+	if (next1->label_num < next2->label_num)
+		return -1;
+
+	return memcmp(next1->labels, next2->labels, next1->label_num);
+}
+
+static int zapi_nexthop_cmp_no_labels(const struct zapi_nexthop *next1,
+				      const struct zapi_nexthop *next2)
+{
+	int ret = 0;
+
+	if (next1->vrf_id < next2->vrf_id)
+		return -1;
+
+	if (next1->vrf_id > next2->vrf_id)
+		return 1;
+
+	if (next1->type < next2->type)
+		return -1;
+
+	if (next1->type > next2->type)
+		return 1;
+
+	switch (next1->type) {
+	case NEXTHOP_TYPE_IPV4:
+	case NEXTHOP_TYPE_IPV6:
+		ret = nexthop_g_addr_cmp(next1->type, &next1->gate,
+					 &next2->gate);
+		if (ret != 0)
+			return ret;
+		break;
+	case NEXTHOP_TYPE_IPV4_IFINDEX:
+	case NEXTHOP_TYPE_IPV6_IFINDEX:
+		ret = nexthop_g_addr_cmp(next1->type, &next1->gate,
+					 &next2->gate);
+		if (ret != 0)
+			return ret;
+		/* Intentional Fall-Through */
+	case NEXTHOP_TYPE_IFINDEX:
+		if (next1->ifindex < next2->ifindex)
+			return -1;
+
+		if (next1->ifindex > next2->ifindex)
+			return 1;
+		break;
+	case NEXTHOP_TYPE_BLACKHOLE:
+		if (next1->bh_type < next2->bh_type)
+			return -1;
+
+		if (next1->bh_type > next2->bh_type)
+			return 1;
+		break;
+	}
+
+	return 0;
+}
+
+static int zapi_nexthop_cmp(const void *item1, const void *item2)
+{
+	int ret = 0;
+
+	const struct zapi_nexthop *next1 = item1;
+	const struct zapi_nexthop *next2 = item2;
+
+	ret = zapi_nexthop_cmp_no_labels(next1, next2);
+	if (ret != 0)
+		return ret;
+
+	ret = zapi_nexthop_labels_cmp(next1, next2);
+
+	return ret;
+}
+
+static void zapi_nexthop_group_sort(struct zapi_nexthop *nh_grp,
+				    uint16_t nexthop_num)
+{
+	qsort(nh_grp, nexthop_num, sizeof(struct zapi_nexthop),
+	      &zapi_nexthop_cmp);
+}
+
 int zapi_route_encode(uint8_t cmd, struct stream *s, struct zapi_route *api)
 {
 	struct zapi_nexthop *api_nh;
@@ -820,6 +906,8 @@ int zapi_route_encode(uint8_t cmd, struct stream *s, struct zapi_route *api)
 			return -1;
 		}
 
+		zapi_nexthop_group_sort(api->nexthops, api->nexthop_num);
+
 		stream_putw(s, api->nexthop_num);
 
 		for (i = 0; i < api->nexthop_num; i++) {