lib,sharpd,zebra: initial support for multiple backup nexthops

Initial changes to support a nexthop with multiple backups. Lib
changes to hold a small array in each primary, zapi message
changes to support sending multiple backups, and daemon
changes to show commands to support multiple backups. The config
input for multiple backup indices is not present here.

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

5 files changed, 93 insertions, 29 deletions

diff --git a/lib/nexthop.c b/lib/nexthop.c
index 3496081d4..3f5308bc2 100644
--- a/lib/nexthop.c
+++ b/lib/nexthop.c
@@ -157,6 +157,10 @@ static int _nexthop_cmp_no_labels(const struct nexthop *next1,
 		goto done;
 
 	if (!CHECK_FLAG(next1->flags, NEXTHOP_FLAG_HAS_BACKUP) &&
+	    !CHECK_FLAG(next2->flags, NEXTHOP_FLAG_HAS_BACKUP))
+		return 0;
+
+	if (!CHECK_FLAG(next1->flags, NEXTHOP_FLAG_HAS_BACKUP) &&
 	    CHECK_FLAG(next2->flags, NEXTHOP_FLAG_HAS_BACKUP))
 		return -1;
 
@@ -164,12 +168,18 @@ static int _nexthop_cmp_no_labels(const struct nexthop *next1,
 	    !CHECK_FLAG(next2->flags, NEXTHOP_FLAG_HAS_BACKUP))
 		return 1;
 
-	if (next1->backup_idx < next2->backup_idx)
+	if (next1->backup_num == 0 && next2->backup_num == 0)
+		goto done;
+
+	if (next1->backup_num < next2->backup_num)
 		return -1;
 
-	if (next1->backup_idx > next2->backup_idx)
+	if (next1->backup_num > next2->backup_num)
 		return 1;
 
+	ret = memcmp(next1->backup_idx,
+		     next2->backup_idx, next1->backup_num);
+
 done:
 	return ret;
 }
@@ -529,14 +539,15 @@ unsigned int nexthop_level(struct nexthop *nexthop)
 uint32_t nexthop_hash_quick(const struct nexthop *nexthop)
 {
 	uint32_t key = 0x45afe398;
-	uint32_t val;
+	int i;
 
 	key = jhash_3words(nexthop->type, nexthop->vrf_id,
 			   nexthop->nh_label_type, key);
 
 	if (nexthop->nh_label) {
 		int labels = nexthop->nh_label->num_labels;
-		int i = 0;
+
+		i = 0;
 
 		while (labels >= 3) {
 			key = jhash_3words(nexthop->nh_label->label[i],
@@ -559,14 +570,35 @@ uint32_t nexthop_hash_quick(const struct nexthop *nexthop)
 			key = jhash_1word(nexthop->nh_label->label[i], key);
 	}
 
-	val = 0;
-	if (CHECK_FLAG(nexthop->flags, NEXTHOP_FLAG_HAS_BACKUP))
-		val = (uint32_t)nexthop->backup_idx;
-
-	key = jhash_3words(nexthop->ifindex,
-			   CHECK_FLAG(nexthop->flags, NEXTHOP_FLAG_ONLINK), val,
+	key = jhash_2words(nexthop->ifindex,
+			   CHECK_FLAG(nexthop->flags, NEXTHOP_FLAG_ONLINK),
 			   key);
 
+	/* Include backup nexthops, if present */
+	if (CHECK_FLAG(nexthop->flags, NEXTHOP_FLAG_HAS_BACKUP)) {
+		int backups = nexthop->backup_num;
+
+		i = 0;
+
+		while (backups >= 3) {
+			key = jhash_3words(nexthop->backup_idx[i],
+					   nexthop->backup_idx[i + 1],
+					   nexthop->backup_idx[i + 2], key);
+			backups -= 3;
+			i += 3;
+		}
+
+		while (backups >= 2) {
+			key = jhash_2words(nexthop->backup_idx[i],
+					   nexthop->backup_idx[i + 1], key);
+			backups -= 2;
+			i += 2;
+		}
+
+		if (backups >= 1)
+			key = jhash_1word(nexthop->backup_idx[i], key);
+	}
+
 	return key;
 }
 
@@ -604,7 +636,12 @@ void nexthop_copy_no_recurse(struct nexthop *copy,
 	copy->type = nexthop->type;
 	copy->flags = nexthop->flags;
 	copy->weight = nexthop->weight;
-	copy->backup_idx = nexthop->backup_idx;
+
+	assert(nexthop->backup_num < NEXTHOP_MAX_BACKUPS);
+	copy->backup_num = nexthop->backup_num;
+	if (copy->backup_num > 0)
+		memcpy(copy->backup_idx, nexthop->backup_idx, copy->backup_num);
+
 	memcpy(&copy->gate, &nexthop->gate, sizeof(nexthop->gate));
 	memcpy(&copy->src, &nexthop->src, sizeof(nexthop->src));
 	memcpy(&copy->rmap_src, &nexthop->rmap_src, sizeof(nexthop->rmap_src));
diff --git a/lib/nexthop.h b/lib/nexthop.h
index eda88efc0..e40c27d87 100644
--- a/lib/nexthop.h
+++ b/lib/nexthop.h
@@ -65,6 +65,12 @@ enum nh_encap_type {
 	NET_VXLAN = 100, /* value copied from FPM_NH_ENCAP_VXLAN. */
 };
 
+/* Fixed limit on the number of backup nexthops per primary nexthop */
+#define NEXTHOP_MAX_BACKUPS  8
+
+/* Backup index value is limited */
+#define NEXTHOP_BACKUP_IDX_MAX 255
+
 /* Nexthop structure. */
 struct nexthop {
 	struct nexthop *next;
@@ -124,10 +130,11 @@ struct nexthop {
 	/* Weight of the nexthop ( for unequal cost ECMP ) */
 	uint8_t weight;
 
-	/* Index of a corresponding backup nexthop in a backup list;
+	/* Count and index of corresponding backup nexthop(s) in a backup list;
 	 * only meaningful if the HAS_BACKUP flag is set.
 	 */
-	uint8_t backup_idx;
+	uint8_t backup_num;
+	uint8_t backup_idx[NEXTHOP_MAX_BACKUPS];
 
 	/* Encapsulation information. */
 	enum nh_encap_type nh_encap_type;
@@ -136,9 +143,6 @@ struct nexthop {
 	} nh_encap;
 };
 
-/* Backup index value is limited */
-#define NEXTHOP_BACKUP_IDX_MAX 255
-
 /* Utility to append one nexthop to another. */
 #define NEXTHOP_APPEND(to, new)           \
 	do {                              \
diff --git a/lib/nexthop_group.c b/lib/nexthop_group.c
index 4f0c72af2..318f9f616 100644
--- a/lib/nexthop_group.c
+++ b/lib/nexthop_group.c
@@ -806,7 +806,8 @@ static bool nexthop_group_parse_nexthop(struct nexthop *nhop,
 			return false;
 
 		SET_FLAG(nhop->flags, NEXTHOP_FLAG_HAS_BACKUP);
-		nhop->backup_idx = backup_idx;
+		nhop->backup_num = 1;
+		nhop->backup_idx[0] = backup_idx;
 	}
 
 	return true;
@@ -992,7 +993,7 @@ void nexthop_group_write_nexthop(struct vty *vty, struct nexthop *nh)
 		vty_out(vty, " weight %u", nh->weight);
 
 	if (CHECK_FLAG(nh->flags, NEXTHOP_FLAG_HAS_BACKUP))
-		vty_out(vty, " backup-idx %d", nh->backup_idx);
+		vty_out(vty, " backup-idx %d", nh->backup_idx[0]);
 
 	vty_out(vty, "\n");
 }
@@ -1048,7 +1049,7 @@ void nexthop_group_json_nexthop(json_object *j, struct nexthop *nh)
 		json_object_int_add(j, "weight", nh->weight);
 
 	if (CHECK_FLAG(nh->flags, NEXTHOP_FLAG_HAS_BACKUP))
-		json_object_int_add(j, "backupIdx", nh->backup_idx);
+		json_object_int_add(j, "backupIdx", nh->backup_idx[0]);
 }
 
 static void nexthop_group_write_nexthop_internal(struct vty *vty,
diff --git a/lib/zclient.c b/lib/zclient.c
index 793864243..6a511ccab 100644
--- a/lib/zclient.c
+++ b/lib/zclient.c
@@ -888,7 +888,7 @@ static void zapi_nexthop_group_sort(struct zapi_nexthop *nh_grp,
 int zapi_nexthop_encode(struct stream *s, const struct zapi_nexthop *api_nh,
 			uint32_t api_flags)
 {
-	int ret = 0;
+	int i, ret = 0;
 	int nh_flags = api_nh->flags;
 
 	stream_putl(s, api_nh->vrf_id);
@@ -951,8 +951,17 @@ int zapi_nexthop_encode(struct stream *s, const struct zapi_nexthop *api_nh,
 			   sizeof(struct ethaddr));
 
 	/* Index of backup nexthop */
-	if (CHECK_FLAG(nh_flags, ZAPI_NEXTHOP_FLAG_HAS_BACKUP))
-		stream_putc(s, api_nh->backup_idx);
+	if (CHECK_FLAG(nh_flags, ZAPI_NEXTHOP_FLAG_HAS_BACKUP)) {
+		/* Validate backup count */
+		if (api_nh->backup_num > NEXTHOP_MAX_BACKUPS) {
+			ret = -1;
+			goto done;
+		}
+
+		stream_putc(s, api_nh->backup_num);
+		for (i = 0; i < api_nh->backup_num; i++)
+			stream_putc(s, api_nh->backup_idx[i]);
+	}
 
 done:
 	return ret;
@@ -1111,7 +1120,7 @@ int zapi_route_encode(uint8_t cmd, struct stream *s, struct zapi_route *api)
 static int zapi_nexthop_decode(struct stream *s, struct zapi_nexthop *api_nh,
 			       uint32_t api_flags)
 {
-	int ret = -1;
+	int i, ret = -1;
 
 	STREAM_GETL(s, api_nh->vrf_id);
 	STREAM_GETC(s, api_nh->type);
@@ -1163,8 +1172,15 @@ static int zapi_nexthop_decode(struct stream *s, struct zapi_nexthop *api_nh,
 			   sizeof(struct ethaddr));
 
 	/* Backup nexthop index */
-	if (CHECK_FLAG(api_nh->flags, ZAPI_NEXTHOP_FLAG_HAS_BACKUP))
-		STREAM_GETC(s, api_nh->backup_idx);
+	if (CHECK_FLAG(api_nh->flags, ZAPI_NEXTHOP_FLAG_HAS_BACKUP)) {
+		STREAM_GETC(s, api_nh->backup_num);
+
+		if (api_nh->backup_num > NEXTHOP_MAX_BACKUPS)
+			return -1;
+
+		for (i = 0; i < api_nh->backup_num; i++)
+			STREAM_GETC(s, api_nh->backup_idx[i]);
+	}
 
 	/* Success */
 	ret = 0;
@@ -1483,7 +1499,8 @@ struct nexthop *nexthop_from_zapi_nexthop(const struct zapi_nexthop *znh)
 
 	if (CHECK_FLAG(znh->flags, ZAPI_NEXTHOP_FLAG_HAS_BACKUP)) {
 		SET_FLAG(n->flags, NEXTHOP_FLAG_HAS_BACKUP);
-		n->backup_idx = znh->backup_idx;
+		n->backup_num = znh->backup_num;
+		memcpy(n->backup_idx, znh->backup_idx, n->backup_num);
 	}
 
 	return n;
@@ -1519,8 +1536,12 @@ int zapi_nexthop_from_nexthop(struct zapi_nexthop *znh,
 	}
 
 	if (CHECK_FLAG(nh->flags, NEXTHOP_FLAG_HAS_BACKUP)) {
+		if (nh->backup_num > NEXTHOP_MAX_BACKUPS)
+			return -1;
+
 		SET_FLAG(znh->flags, ZAPI_NEXTHOP_FLAG_HAS_BACKUP);
-		znh->backup_idx = nh->backup_idx;
+		znh->backup_num = nh->backup_num;
+		memcpy(znh->backup_idx, nh->backup_idx, znh->backup_num);
 	}
 
 	return 0;
diff --git a/lib/zclient.h b/lib/zclient.h
index 3ded2f55d..250824e61 100644
--- a/lib/zclient.h
+++ b/lib/zclient.h
@@ -394,8 +394,9 @@ struct zapi_nexthop {
 
 	uint32_t weight;
 
-	/* Index of backup nexthop */
-	uint8_t backup_idx;
+	/* Backup nexthops, for IP-FRR, TI-LFA, etc */
+	uint8_t backup_num;
+	uint8_t backup_idx[NEXTHOP_MAX_BACKUPS];
 };
 
 /*