1 files changed, 286 insertions, 201 deletions

diff --git a/zebra/zebra_rib.c b/zebra/zebra_rib.c
index c2fa33f57d..e0bf1a58f2 100644
--- a/zebra/zebra_rib.c
+++ b/zebra/zebra_rib.c
@@ -56,7 +56,6 @@
 #include "zebra/zebra_vxlan.h"
 #include "zebra/zapi_msg.h"
 #include "zebra/zebra_dplane.h"
-#include "zebra/zebra_nhg.h"
 
 DEFINE_MTYPE_STATIC(ZEBRA, RIB_UPDATE_CTX, "Rib update context object");
 
@@ -79,34 +78,35 @@ static const struct {
 	uint8_t distance;
 	uint8_t meta_q_map;
 } route_info[ZEBRA_ROUTE_MAX] = {
-	[ZEBRA_ROUTE_SYSTEM] = {ZEBRA_ROUTE_SYSTEM, 0, 4},
-	[ZEBRA_ROUTE_KERNEL] = {ZEBRA_ROUTE_KERNEL, 0, 0},
-	[ZEBRA_ROUTE_CONNECT] = {ZEBRA_ROUTE_CONNECT, 0, 0},
-	[ZEBRA_ROUTE_STATIC] = {ZEBRA_ROUTE_STATIC, 1, 1},
-	[ZEBRA_ROUTE_RIP] = {ZEBRA_ROUTE_RIP, 120, 2},
-	[ZEBRA_ROUTE_RIPNG] = {ZEBRA_ROUTE_RIPNG, 120, 2},
-	[ZEBRA_ROUTE_OSPF] = {ZEBRA_ROUTE_OSPF, 110, 2},
-	[ZEBRA_ROUTE_OSPF6] = {ZEBRA_ROUTE_OSPF6, 110, 2},
-	[ZEBRA_ROUTE_ISIS] = {ZEBRA_ROUTE_ISIS, 115, 2},
-	[ZEBRA_ROUTE_BGP] = {ZEBRA_ROUTE_BGP, 20 /* IBGP is 200. */, 3},
-	[ZEBRA_ROUTE_PIM] = {ZEBRA_ROUTE_PIM, 255, 4},
-	[ZEBRA_ROUTE_EIGRP] = {ZEBRA_ROUTE_EIGRP, 90, 2},
-	[ZEBRA_ROUTE_NHRP] = {ZEBRA_ROUTE_NHRP, 10, 2},
-	[ZEBRA_ROUTE_HSLS] = {ZEBRA_ROUTE_HSLS, 255, 4},
-	[ZEBRA_ROUTE_OLSR] = {ZEBRA_ROUTE_OLSR, 255, 4},
-	[ZEBRA_ROUTE_TABLE] = {ZEBRA_ROUTE_TABLE, 150, 1},
-	[ZEBRA_ROUTE_LDP] = {ZEBRA_ROUTE_LDP, 150, 4},
-	[ZEBRA_ROUTE_VNC] = {ZEBRA_ROUTE_VNC, 20, 3},
-	[ZEBRA_ROUTE_VNC_DIRECT] = {ZEBRA_ROUTE_VNC_DIRECT, 20, 3},
-	[ZEBRA_ROUTE_VNC_DIRECT_RH] = {ZEBRA_ROUTE_VNC_DIRECT_RH, 20, 3},
-	[ZEBRA_ROUTE_BGP_DIRECT] = {ZEBRA_ROUTE_BGP_DIRECT, 20, 3},
-	[ZEBRA_ROUTE_BGP_DIRECT_EXT] = {ZEBRA_ROUTE_BGP_DIRECT_EXT, 20, 3},
-	[ZEBRA_ROUTE_BABEL] = {ZEBRA_ROUTE_BABEL, 100, 2},
-	[ZEBRA_ROUTE_SHARP] = {ZEBRA_ROUTE_SHARP, 150, 4},
-	[ZEBRA_ROUTE_PBR] = {ZEBRA_ROUTE_PBR, 200, 4},
-	[ZEBRA_ROUTE_BFD] = {ZEBRA_ROUTE_BFD, 255, 4},
-	[ZEBRA_ROUTE_OPENFABRIC] = {ZEBRA_ROUTE_OPENFABRIC, 115, 2},
-	[ZEBRA_ROUTE_VRRP] = {ZEBRA_ROUTE_VRRP, 255, 4}
+	[ZEBRA_ROUTE_NHG] = {ZEBRA_ROUTE_NHG, 255 /* Uneeded for nhg's */, 0},
+	[ZEBRA_ROUTE_SYSTEM] = {ZEBRA_ROUTE_SYSTEM, 0, 5},
+	[ZEBRA_ROUTE_KERNEL] = {ZEBRA_ROUTE_KERNEL, 0, 1},
+	[ZEBRA_ROUTE_CONNECT] = {ZEBRA_ROUTE_CONNECT, 0, 1},
+	[ZEBRA_ROUTE_STATIC] = {ZEBRA_ROUTE_STATIC, 1, 2},
+	[ZEBRA_ROUTE_RIP] = {ZEBRA_ROUTE_RIP, 120, 3},
+	[ZEBRA_ROUTE_RIPNG] = {ZEBRA_ROUTE_RIPNG, 120, 3},
+	[ZEBRA_ROUTE_OSPF] = {ZEBRA_ROUTE_OSPF, 110, 3},
+	[ZEBRA_ROUTE_OSPF6] = {ZEBRA_ROUTE_OSPF6, 110, 3},
+	[ZEBRA_ROUTE_ISIS] = {ZEBRA_ROUTE_ISIS, 115, 3},
+	[ZEBRA_ROUTE_BGP] = {ZEBRA_ROUTE_BGP, 20 /* IBGP is 200. */, 4},
+	[ZEBRA_ROUTE_PIM] = {ZEBRA_ROUTE_PIM, 255, 5},
+	[ZEBRA_ROUTE_EIGRP] = {ZEBRA_ROUTE_EIGRP, 90, 3},
+	[ZEBRA_ROUTE_NHRP] = {ZEBRA_ROUTE_NHRP, 10, 3},
+	[ZEBRA_ROUTE_HSLS] = {ZEBRA_ROUTE_HSLS, 255, 5},
+	[ZEBRA_ROUTE_OLSR] = {ZEBRA_ROUTE_OLSR, 255, 5},
+	[ZEBRA_ROUTE_TABLE] = {ZEBRA_ROUTE_TABLE, 150, 2},
+	[ZEBRA_ROUTE_LDP] = {ZEBRA_ROUTE_LDP, 150, 5},
+	[ZEBRA_ROUTE_VNC] = {ZEBRA_ROUTE_VNC, 20, 4},
+	[ZEBRA_ROUTE_VNC_DIRECT] = {ZEBRA_ROUTE_VNC_DIRECT, 20, 4},
+	[ZEBRA_ROUTE_VNC_DIRECT_RH] = {ZEBRA_ROUTE_VNC_DIRECT_RH, 20, 4},
+	[ZEBRA_ROUTE_BGP_DIRECT] = {ZEBRA_ROUTE_BGP_DIRECT, 20, 4},
+	[ZEBRA_ROUTE_BGP_DIRECT_EXT] = {ZEBRA_ROUTE_BGP_DIRECT_EXT, 20, 4},
+	[ZEBRA_ROUTE_BABEL] = {ZEBRA_ROUTE_BABEL, 100, 3},
+	[ZEBRA_ROUTE_SHARP] = {ZEBRA_ROUTE_SHARP, 150, 5},
+	[ZEBRA_ROUTE_PBR] = {ZEBRA_ROUTE_PBR, 200, 5},
+	[ZEBRA_ROUTE_BFD] = {ZEBRA_ROUTE_BFD, 255, 5},
+	[ZEBRA_ROUTE_OPENFABRIC] = {ZEBRA_ROUTE_OPENFABRIC, 115, 3},
+	[ZEBRA_ROUTE_VRRP] = {ZEBRA_ROUTE_VRRP, 255, 5}
 	/* Any new route type added to zebra, should be mirrored here */
 
 	/* no entry/default: 150 */
@@ -196,8 +196,7 @@ int zebra_check_addr(const struct prefix *p)
 /* Add nexthop to the end of a rib node's nexthop list */
 void route_entry_nexthop_add(struct route_entry *re, struct nexthop *nexthop)
 {
-	_nexthop_group_add_sorted(&re->ng, nexthop);
-	re->nexthop_num++;
+	_nexthop_group_add_sorted(re->ng, nexthop);
 }
 
 
@@ -206,10 +205,8 @@ void route_entry_nexthop_add(struct route_entry *re, struct nexthop *nexthop)
  */
 void route_entry_copy_nexthops(struct route_entry *re, struct nexthop *nh)
 {
-	assert(!re->ng.nexthop);
-	copy_nexthops(&re->ng.nexthop, nh, NULL);
-	for (struct nexthop *nexthop = nh; nexthop; nexthop = nexthop->next)
-		re->nexthop_num++;
+	assert(!re->ng->nexthop);
+	copy_nexthops(&re->ng->nexthop, nh, NULL);
 }
 
 /* Delete specified nexthop from the list. */
@@ -220,8 +217,7 @@ void route_entry_nexthop_delete(struct route_entry *re, struct nexthop *nexthop)
 	if (nexthop->prev)
 		nexthop->prev->next = nexthop->next;
 	else
-		re->ng.nexthop = nexthop->next;
-	re->nexthop_num--;
+		re->ng->nexthop = nexthop->next;
 }
 
 
@@ -505,7 +501,7 @@ int zebra_rib_labeled_unicast(struct route_entry *re)
 	if (re->type != ZEBRA_ROUTE_BGP)
 		return 0;
 
-	for (ALL_NEXTHOPS(re->ng, nexthop))
+	for (ALL_NEXTHOPS_PTR(re->ng, nexthop))
 		if (!nexthop->nh_label || !nexthop->nh_label->num_labels)
 			return 0;
 
@@ -529,26 +525,17 @@ void rib_install_kernel(struct route_node *rn, struct route_entry *re,
 	srcdest_rnode_prefixes(rn, &p, &src_p);
 
 	if (info->safi != SAFI_UNICAST) {
-		for (ALL_NEXTHOPS(re->ng, nexthop))
+		for (ALL_NEXTHOPS_PTR(re->ng, nexthop))
 			SET_FLAG(nexthop->flags, NEXTHOP_FLAG_FIB);
 		return;
-	} else {
-		struct nexthop *prev;
-
-		for (ALL_NEXTHOPS(re->ng, nexthop)) {
-			UNSET_FLAG (nexthop->flags, NEXTHOP_FLAG_DUPLICATE);
-			for (ALL_NEXTHOPS(re->ng, prev)) {
-				if (prev == nexthop)
-					break;
-				if (nexthop_same_firsthop(nexthop, prev)) {
-					SET_FLAG(nexthop->flags,
-						 NEXTHOP_FLAG_DUPLICATE);
-					break;
-				}
-			}
-		}
 	}
 
+
+	/*
+	 * Install the resolved nexthop object first.
+	 */
+	zebra_nhg_install_kernel(zebra_nhg_lookup_id(re->nhe_id));
+
 	/*
 	 * If this is a replace to a new RE let the originator of the RE
 	 * know that they've lost
@@ -586,7 +573,7 @@ void rib_install_kernel(struct route_node *rn, struct route_entry *re,
 
 			if (!RIB_SYSTEM_ROUTE(old)) {
 				/* Clear old route's FIB flags */
-				for (ALL_NEXTHOPS(old->ng, nexthop)) {
+				for (ALL_NEXTHOPS_PTR(old->ng, nexthop)) {
 					UNSET_FLAG(nexthop->flags,
 						   NEXTHOP_FLAG_FIB);
 				}
@@ -624,7 +611,7 @@ void rib_uninstall_kernel(struct route_node *rn, struct route_entry *re)
 
 	if (info->safi != SAFI_UNICAST) {
 		UNSET_FLAG(re->status, ROUTE_ENTRY_INSTALLED);
-		for (ALL_NEXTHOPS(re->ng, nexthop))
+		for (ALL_NEXTHOPS_PTR(re->ng, nexthop))
 			UNSET_FLAG(nexthop->flags, NEXTHOP_FLAG_FIB);
 		return;
 	}
@@ -684,7 +671,7 @@ static void rib_uninstall(struct route_node *rn, struct route_entry *re)
 			re->fib_ng.nexthop = NULL;
 		}
 
-		for (ALL_NEXTHOPS(re->ng, nexthop))
+		for (ALL_NEXTHOPS_PTR(re->ng, nexthop))
 			UNSET_FLAG(nexthop->flags, NEXTHOP_FLAG_FIB);
 	}
 
@@ -860,7 +847,7 @@ static void rib_process_add_fib(struct zebra_vrf *zvrf, struct route_node *rn,
 
 	/* Update real nexthop. This may actually determine if nexthop is active
 	 * or not. */
-	if (!nexthop_group_active_nexthop_num(&new->ng)) {
+	if (!nexthop_group_active_nexthop_num(new->ng)) {
 		UNSET_FLAG(new->status, ROUTE_ENTRY_CHANGED);
 		return;
 	}
@@ -929,7 +916,7 @@ static void rib_process_update_fib(struct zebra_vrf *zvrf,
 
 		/* Update the nexthop; we could determine here that nexthop is
 		 * inactive. */
-		if (nexthop_group_active_nexthop_num(&new->ng))
+		if (nexthop_group_active_nexthop_num(new->ng))
 			nh_active = 1;
 
 		/* If nexthop is active, install the selected route, if
@@ -1047,7 +1034,7 @@ static struct route_entry *rib_choose_best(struct route_entry *current,
 		/* both are connected.  are either loop or vrf? */
 		struct nexthop *nexthop = NULL;
 
-		for (ALL_NEXTHOPS(alternate->ng, nexthop)) {
+		for (ALL_NEXTHOPS_PTR(alternate->ng, nexthop)) {
 			struct interface *ifp = if_lookup_by_index(
 				nexthop->ifindex, alternate->vrf_id);
 
@@ -1055,7 +1042,7 @@ static struct route_entry *rib_choose_best(struct route_entry *current,
 				return alternate;
 		}
 
-		for (ALL_NEXTHOPS(current->ng, nexthop)) {
+		for (ALL_NEXTHOPS_PTR(current->ng, nexthop)) {
 			struct interface *ifp = if_lookup_by_index(
 				nexthop->ifindex, current->vrf_id);
 
@@ -1086,6 +1073,12 @@ static struct route_entry *rib_choose_best(struct route_entry *current,
 	return current;
 }
 
+/* Core function for processing nexthop group contexts's off metaq */
+static void rib_nhg_process(struct nhg_ctx *ctx)
+{
+	nhg_ctx_process(ctx);
+}
+
 /* Core function for processing routing information base. */
 static void rib_process(struct route_node *rn)
 {
@@ -1380,7 +1373,7 @@ static void zebra_rib_fixup_system(struct route_node *rn)
 		SET_FLAG(re->status, ROUTE_ENTRY_INSTALLED);
 		UNSET_FLAG(re->status, ROUTE_ENTRY_QUEUED);
 
-		for (ALL_NEXTHOPS(re->ng, nhop)) {
+		for (ALL_NEXTHOPS_PTR(re->ng, nhop)) {
 			if (CHECK_FLAG(nhop->flags, NEXTHOP_FLAG_RECURSIVE))
 				continue;
 
@@ -1428,76 +1421,20 @@ static bool rib_update_re_from_ctx(struct route_entry *re,
 	 * status.
 	 */
 
-	/*
-	 * First check the fib nexthop-group, if it's present. The comparison
-	 * here is quite strict: we require that the fib sets match exactly.
+	/* Check both fib group and notif group for equivalence.
+	 *
+	 * Let's assume the nexthops are ordered here to save time.
 	 */
-	matched = false;
-	do {
-		if (re->fib_ng.nexthop == NULL)
-			break;
-
-		matched = true;
-
-		/* First check the route's fib nexthops */
-		for (ALL_NEXTHOPS(re->fib_ng, nexthop)) {
-
-			if (CHECK_FLAG(nexthop->flags, NEXTHOP_FLAG_RECURSIVE))
-				continue;
-
-			ctx_nexthop = NULL;
-			for (ALL_NEXTHOPS_PTR(dplane_ctx_get_ng(ctx),
-					      ctx_nexthop)) {
-				if (nexthop_same(ctx_nexthop, nexthop))
-					break;
-			}
-
-			if (ctx_nexthop == NULL) {
-				/* Nexthop not in the new installed set */
-				if (IS_ZEBRA_DEBUG_RIB_DETAILED) {
-					nexthop2str(nexthop, nh_str,
-						    sizeof(nh_str));
-					zlog_debug("update_from_ctx: no match for fib nh %s",
-						   nh_str);
-				}
-
-				matched = false;
-				break;
-			}
-		}
-
-		if (!matched)
-			break;
-
-		/* Check the new installed set */
-		ctx_nexthop = NULL;
-		for (ALL_NEXTHOPS_PTR(dplane_ctx_get_ng(ctx), ctx_nexthop)) {
-
-			if (CHECK_FLAG(ctx_nexthop->flags,
-				       NEXTHOP_FLAG_RECURSIVE))
-				continue;
-
-			/* Compare with the current group's nexthops */
-			nexthop = NULL;
-			for (ALL_NEXTHOPS(re->fib_ng, nexthop)) {
-				if (nexthop_same(nexthop, ctx_nexthop))
-					break;
-			}
-
-			if (nexthop == NULL) {
-				/* Nexthop not in the old installed set */
-				if (IS_ZEBRA_DEBUG_RIB_DETAILED) {
-					nexthop2str(ctx_nexthop, nh_str,
-						    sizeof(nh_str));
-					zlog_debug("update_from_ctx: no fib match for notif nh %s",
-						   nh_str);
-				}
-				matched = false;
-				break;
-			}
+	if (nexthop_group_equal(&re->fib_ng, dplane_ctx_get_ng(ctx)) == false) {
+		if (IS_ZEBRA_DEBUG_RIB_DETAILED) {
+			zlog_debug(
+				"%u:%s update_from_ctx: notif nh and fib nh mismatch",
+				re->vrf_id, dest_str);
 		}
 
-	} while (0);
+		matched = false;
+	} else
+		matched = true;
 
 	/* If the new FIB set matches the existing FIB set, we're done. */
 	if (matched) {
@@ -1530,9 +1467,22 @@ static bool rib_update_re_from_ctx(struct route_entry *re,
 	 * walk the RIB group, looking for the 'installable' candidate
 	 * nexthops, and then check those against the set
 	 * that is actually installed.
+	 *
+	 * Assume nexthops are ordered here as well.
 	 */
 	matched = true;
-	for (ALL_NEXTHOPS(re->ng, nexthop)) {
+
+	ctx_nexthop = dplane_ctx_get_ng(ctx)->nexthop;
+
+	/* Get the first `installed` one to check against.
+	 * If the dataplane doesn't set these to be what was actually installed,
+	 * it will just be whatever was in re->ng?
+	 */
+	if (CHECK_FLAG(ctx_nexthop->flags, NEXTHOP_FLAG_RECURSIVE)
+	    || !CHECK_FLAG(ctx_nexthop->flags, NEXTHOP_FLAG_ACTIVE))
+		ctx_nexthop = nexthop_next_active_resolved(ctx_nexthop);
+
+	for (ALL_NEXTHOPS_PTR(re->ng, nexthop)) {
 
 		if (CHECK_FLAG(nexthop->flags, NEXTHOP_FLAG_RECURSIVE))
 			continue;
@@ -1541,20 +1491,15 @@ static bool rib_update_re_from_ctx(struct route_entry *re,
 			continue;
 
 		/* Check for a FIB nexthop corresponding to the RIB nexthop */
-		ctx_nexthop = NULL;
-		for (ALL_NEXTHOPS_PTR(dplane_ctx_get_ng(ctx), ctx_nexthop)) {
-			if (nexthop_same(ctx_nexthop, nexthop))
-				break;
-		}
-
-		/* If the FIB doesn't know about the nexthop,
-		 * it's not installed
-		 */
-		if (ctx_nexthop == NULL) {
+		if (nexthop_same(ctx_nexthop, nexthop) == false) {
+			/* If the FIB doesn't know about the nexthop,
+			 * it's not installed
+			 */
 			if (IS_ZEBRA_DEBUG_RIB_DETAILED) {
 				nexthop2str(nexthop, nh_str, sizeof(nh_str));
-				zlog_debug("update_from_ctx: no notif match for rib nh %s",
-					   nh_str);
+				zlog_debug(
+					"update_from_ctx: no notif match for rib nh %s",
+					nh_str);
 			}
 			matched = false;
 
@@ -1578,6 +1523,8 @@ static bool rib_update_re_from_ctx(struct route_entry *re,
 
 			UNSET_FLAG(nexthop->flags, NEXTHOP_FLAG_FIB);
 		}
+
+		ctx_nexthop = nexthop_next_active_resolved(ctx_nexthop);
 	}
 
 	/* If all nexthops were processed, we're done */
@@ -2062,19 +2009,28 @@ done:
 	dplane_ctx_fini(&ctx);
 }
 
-/* Take a list of route_node structs and return 1, if there was a record
- * picked from it and processed by rib_process(). Don't process more,
- * than one RN record; operate only in the specified sub-queue.
- */
-static unsigned int process_subq(struct list *subq, uint8_t qindex)
+static void process_subq_nhg(struct listnode *lnode)
 {
-	struct listnode *lnode = listhead(subq);
-	struct route_node *rnode;
-	rib_dest_t *dest;
-	struct zebra_vrf *zvrf = NULL;
+	struct nhg_ctx *ctx = NULL;
+	uint8_t qindex = route_info[ZEBRA_ROUTE_NHG].meta_q_map;
 
-	if (!lnode)
-		return 0;
+	ctx = listgetdata(lnode);
+
+	if (!ctx)
+		return;
+
+	if (IS_ZEBRA_DEBUG_RIB_DETAILED)
+		zlog_debug("NHG Context id=%u dequeued from sub-queue %u",
+			   ctx->id, qindex);
+
+	rib_nhg_process(ctx);
+}
+
+static void process_subq_route(struct listnode *lnode, uint8_t qindex)
+{
+	struct route_node *rnode = NULL;
+	rib_dest_t *dest = NULL;
+	struct zebra_vrf *zvrf = NULL;
 
 	rnode = listgetdata(lnode);
 	dest = rib_dest_from_rnode(rnode);
@@ -2104,7 +2060,26 @@ static unsigned int process_subq(struct list *subq, uint8_t qindex)
     }
 #endif
 	route_unlock_node(rnode);
+}
+
+/* Take a list of route_node structs and return 1, if there was a record
+ * picked from it and processed by rib_process(). Don't process more,
+ * than one RN record; operate only in the specified sub-queue.
+ */
+static unsigned int process_subq(struct list *subq, uint8_t qindex)
+{
+	struct listnode *lnode = listhead(subq);
+
+	if (!lnode)
+		return 0;
+
+	if (qindex == route_info[ZEBRA_ROUTE_NHG].meta_q_map)
+		process_subq_nhg(lnode);
+	else
+		process_subq_route(lnode, qindex);
+
 	list_delete_node(subq, lnode);
+
 	return 1;
 }
 
@@ -2162,11 +2137,14 @@ static wq_item_status meta_queue_process(struct work_queue *dummy, void *data)
  * original metaqueue index value will win and we'll end up with
  * the route node enqueued once.
  */
-static void rib_meta_queue_add(struct meta_queue *mq, struct route_node *rn)
+static int rib_meta_queue_add(struct meta_queue *mq, void *data)
 {
+	struct route_node *rn = NULL;
 	struct route_entry *re = NULL, *curr_re = NULL;
 	uint8_t qindex = MQ_SIZE, curr_qindex = MQ_SIZE;
 
+	rn = (struct route_node *)data;
+
 	RNODE_FOREACH_RE (rn, curr_re) {
 		curr_qindex = route_info[curr_re->type].meta_q_map;
 
@@ -2177,7 +2155,7 @@ static void rib_meta_queue_add(struct meta_queue *mq, struct route_node *rn)
 	}
 
 	if (!re)
-		return;
+		return -1;
 
 	/* Invariant: at this point we always have rn->info set. */
 	if (CHECK_FLAG(rib_dest_from_rnode(rn)->flags,
@@ -2186,7 +2164,7 @@ static void rib_meta_queue_add(struct meta_queue *mq, struct route_node *rn)
 			rnode_debug(rn, re->vrf_id,
 				    "rn %p is already queued in sub-queue %u",
 				    (void *)rn, qindex);
-		return;
+		return -1;
 	}
 
 	SET_FLAG(rib_dest_from_rnode(rn)->flags, RIB_ROUTE_QUEUED(qindex));
@@ -2197,26 +2175,37 @@ static void rib_meta_queue_add(struct meta_queue *mq, struct route_node *rn)
 	if (IS_ZEBRA_DEBUG_RIB_DETAILED)
 		rnode_debug(rn, re->vrf_id, "queued rn %p into sub-queue %u",
 			    (void *)rn, qindex);
+
+	return 0;
 }
 
-/* Add route_node to work queue and schedule processing */
-void rib_queue_add(struct route_node *rn)
+static int rib_meta_queue_nhg_add(struct meta_queue *mq, void *data)
 {
-	assert(rn);
+	struct nhg_ctx *ctx = NULL;
+	uint8_t qindex = route_info[ZEBRA_ROUTE_NHG].meta_q_map;
 
-	/* Pointless to queue a route_node with no RIB entries to add or remove
-	 */
-	if (!rnode_to_ribs(rn)) {
-		zlog_debug("%s: called for route_node (%p, %d) with no ribs",
-			   __func__, (void *)rn, rn->lock);
-		zlog_backtrace(LOG_DEBUG);
-		return;
-	}
+	ctx = (struct nhg_ctx *)data;
+
+	if (!ctx)
+		return -1;
 
+	listnode_add(mq->subq[qindex], ctx);
+	mq->size++;
+
+	if (IS_ZEBRA_DEBUG_RIB_DETAILED)
+		zlog_debug("NHG Context id=%u queued into sub-queue %u",
+			   ctx->id, qindex);
+
+	return 0;
+}
+
+static int mq_add_handler(void *data,
+			  int (*mq_add_func)(struct meta_queue *mq, void *data))
+{
 	if (zrouter.ribq == NULL) {
 		flog_err(EC_ZEBRA_WQ_NONEXISTENT,
 			 "%s: work_queue does not exist!", __func__);
-		return;
+		return -1;
 	}
 
 	/*
@@ -2230,9 +2219,31 @@ void rib_queue_add(struct route_node *rn)
 	if (work_queue_empty(zrouter.ribq))
 		work_queue_add(zrouter.ribq, zrouter.mq);
 
-	rib_meta_queue_add(zrouter.mq, rn);
+	return mq_add_func(zrouter.mq, data);
+}
 
-	return;
+/* Add route_node to work queue and schedule processing */
+int rib_queue_add(struct route_node *rn)
+{
+	assert(rn);
+
+	/* Pointless to queue a route_node with no RIB entries to add or remove
+	 */
+	if (!rnode_to_ribs(rn)) {
+		zlog_debug("%s: called for route_node (%p, %d) with no ribs",
+			   __func__, (void *)rn, rn->lock);
+		zlog_backtrace(LOG_DEBUG);
+		return -1;
+	}
+
+	return mq_add_handler(rn, &rib_meta_queue_add);
+}
+
+int rib_queue_nhg_add(struct nhg_ctx *ctx)
+{
+	assert(ctx);
+
+	return mq_add_handler(ctx, &rib_meta_queue_nhg_add);
 }
 
 /* Create new meta queue.
@@ -2400,6 +2411,7 @@ static void rib_addnode(struct route_node *rn,
 void rib_unlink(struct route_node *rn, struct route_entry *re)
 {
 	rib_dest_t *dest;
+	struct nhg_hash_entry *nhe = NULL;
 
 	assert(rn && re);
 
@@ -2414,7 +2426,13 @@ void rib_unlink(struct route_node *rn, struct route_entry *re)
 	if (dest->selected_fib == re)
 		dest->selected_fib = NULL;
 
-	nexthops_free(re->ng.nexthop);
+	if (re->nhe_id) {
+		nhe = zebra_nhg_lookup_id(re->nhe_id);
+		if (nhe)
+			zebra_nhg_decrement_ref(nhe);
+	} else if (re->ng)
+		nexthop_group_delete(&re->ng);
+
 	nexthops_free(re->fib_ng.nexthop);
 
 	XFREE(MTYPE_RE, re);
@@ -2480,9 +2498,10 @@ void _route_entry_dump(const char *func, union prefixconstptr pp,
 		"%s: metric == %u, mtu == %u, distance == %u, flags == %u, status == %u",
 		straddr, re->metric, re->mtu, re->distance, re->flags, re->status);
 	zlog_debug("%s: nexthop_num == %u, nexthop_active_num == %u", straddr,
-		   re->nexthop_num, re->nexthop_active_num);
+		   nexthop_group_nexthop_num(re->ng),
+		   nexthop_group_active_nexthop_num(re->ng));
 
-	for (ALL_NEXTHOPS(re->ng, nexthop)) {
+	for (ALL_NEXTHOPS_PTR(re->ng, nexthop)) {
 		struct interface *ifp;
 		struct vrf *vrf = vrf_lookup_by_id(nexthop->vrf_id);
 
@@ -2633,6 +2652,7 @@ void rib_lookup_and_pushup(struct prefix_ipv4 *p, vrf_id_t vrf_id)
 int rib_add_multipath(afi_t afi, safi_t safi, struct prefix *p,
 		      struct prefix_ipv6 *src_p, struct route_entry *re)
 {
+	struct nhg_hash_entry *nhe = NULL;
 	struct route_table *table;
 	struct route_node *rn;
 	struct route_entry *same = NULL;
@@ -2646,10 +2666,58 @@ int rib_add_multipath(afi_t afi, safi_t safi, struct prefix *p,
 	/* Lookup table.  */
 	table = zebra_vrf_table_with_table_id(afi, safi, re->vrf_id, re->table);
 	if (!table) {
+		if (re->ng)
+			nexthop_group_delete(&re->ng);
 		XFREE(MTYPE_RE, re);
 		return 0;
 	}
 
+	if (re->nhe_id) {
+		nhe = zebra_nhg_lookup_id(re->nhe_id);
+
+		if (!nhe) {
+			flog_err(
+				EC_ZEBRA_TABLE_LOOKUP_FAILED,
+				"Zebra failed to find the nexthop hash entry for id=%u in a route entry",
+				re->nhe_id);
+			XFREE(MTYPE_RE, re);
+			return -1;
+		}
+	} else {
+		nhe = zebra_nhg_rib_find(0, re->ng, afi);
+
+		/*
+		 * The nexthops got copied over into an nhe,
+		 * so free them now.
+		 */
+		nexthop_group_delete(&re->ng);
+
+		if (!nhe) {
+			char buf[PREFIX_STRLEN] = "";
+			char buf2[PREFIX_STRLEN] = "";
+
+			flog_err(
+				EC_ZEBRA_TABLE_LOOKUP_FAILED,
+				"Zebra failed to find or create a nexthop hash entry for %s%s%s",
+				prefix2str(p, buf, sizeof(buf)),
+				src_p ? " from " : "",
+				src_p ? prefix2str(src_p, buf2, sizeof(buf2))
+				      : "");
+
+			XFREE(MTYPE_RE, re);
+			return -1;
+		}
+	}
+
+	/*
+	 * Attach the re to the nhe's nexthop group.
+	 *
+	 * TODO: This will need to change when we start getting IDs from upper
+	 * level protocols, as the refcnt might be wrong, since it checks
+	 * if old_id != new_id.
+	 */
+	zebra_nhg_re_update_ref(re, nhe);
+
 	/* Make it sure prefixlen is applied to the prefix. */
 	apply_mask(p);
 	if (src_p)
@@ -2726,8 +2794,8 @@ int rib_add_multipath(afi_t afi, safi_t safi, struct prefix *p,
 void rib_delete(afi_t afi, safi_t safi, vrf_id_t vrf_id, int type,
 		unsigned short instance, int flags, struct prefix *p,
 		struct prefix_ipv6 *src_p, const struct nexthop *nh,
-		uint32_t table_id, uint32_t metric, uint8_t distance,
-		bool fromkernel)
+		uint32_t nhe_id, uint32_t table_id, uint32_t metric,
+		uint8_t distance, bool fromkernel)
 {
 	struct route_table *table;
 	struct route_node *rn;
@@ -2790,31 +2858,37 @@ void rib_delete(afi_t afi, safi_t safi, vrf_id_t vrf_id, int type,
 
 		if (re->type == ZEBRA_ROUTE_KERNEL && re->metric != metric)
 			continue;
-		if (re->type == ZEBRA_ROUTE_CONNECT && (rtnh = re->ng.nexthop)
+		if (re->type == ZEBRA_ROUTE_CONNECT && (rtnh = re->ng->nexthop)
 		    && rtnh->type == NEXTHOP_TYPE_IFINDEX && nh) {
 			if (rtnh->ifindex != nh->ifindex)
 				continue;
 			same = re;
 			break;
 		}
+
 		/* Make sure that the route found has the same gateway. */
-		else {
-			if (nh == NULL) {
+		if (nhe_id && re->nhe_id == nhe_id) {
+			same = re;
+			break;
+		}
+
+		if (nh == NULL) {
+			same = re;
+			break;
+		}
+		for (ALL_NEXTHOPS_PTR(re->ng, rtnh)) {
+			/*
+			 * No guarantee all kernel send nh with labels
+			 * on delete.
+			 */
+			if (nexthop_same_no_labels(rtnh, nh)) {
 				same = re;
 				break;
 			}
-			for (ALL_NEXTHOPS(re->ng, rtnh))
-				/*
-				 * No guarantee all kernel send nh with labels
-				 * on delete.
-				 */
-				if (nexthop_same_no_labels(rtnh, nh)) {
-					same = re;
-					break;
-				}
-			if (same)
-				break;
 		}
+
+		if (same)
+			break;
 	}
 	/* If same type of route can't be found and this message is from
 	   kernel. */
@@ -2844,7 +2918,7 @@ void rib_delete(afi_t afi, safi_t safi, vrf_id_t vrf_id, int type,
 			if (allow_delete) {
 				UNSET_FLAG(fib->status, ROUTE_ENTRY_INSTALLED);
 				/* Unset flags. */
-				for (rtnh = fib->ng.nexthop; rtnh;
+				for (rtnh = fib->ng->nexthop; rtnh;
 				     rtnh = rtnh->next)
 					UNSET_FLAG(rtnh->flags,
 						   NEXTHOP_FLAG_FIB);
@@ -2900,7 +2974,7 @@ void rib_delete(afi_t afi, safi_t safi, vrf_id_t vrf_id, int type,
 		if (CHECK_FLAG(flags, ZEBRA_FLAG_EVPN_ROUTE)) {
 			struct nexthop *tmp_nh;
 
-			for (ALL_NEXTHOPS(re->ng, tmp_nh)) {
+			for (ALL_NEXTHOPS_PTR(re->ng, tmp_nh)) {
 				struct ipaddr vtep_ip;
 
 				memset(&vtep_ip, 0, sizeof(struct ipaddr));
@@ -2935,11 +3009,11 @@ void rib_delete(afi_t afi, safi_t safi, vrf_id_t vrf_id, int type,
 int rib_add(afi_t afi, safi_t safi, vrf_id_t vrf_id, int type,
 	    unsigned short instance, int flags, struct prefix *p,
 	    struct prefix_ipv6 *src_p, const struct nexthop *nh,
-	    uint32_t table_id, uint32_t metric, uint32_t mtu, uint8_t distance,
-	    route_tag_t tag)
+	    uint32_t nhe_id, uint32_t table_id, uint32_t metric, uint32_t mtu,
+	    uint8_t distance, route_tag_t tag)
 {
-	struct route_entry *re;
-	struct nexthop *nexthop;
+	struct route_entry *re = NULL;
+	struct nexthop *nexthop = NULL;
 
 	/* Allocate new route_entry structure. */
 	re = XCALLOC(MTYPE_RE, sizeof(struct route_entry));
@@ -2951,14 +3025,18 @@ int rib_add(afi_t afi, safi_t safi, vrf_id_t vrf_id, int type,
 	re->mtu = mtu;
 	re->table = table_id;
 	re->vrf_id = vrf_id;
-	re->nexthop_num = 0;
 	re->uptime = monotime(NULL);
 	re->tag = tag;
+	re->nhe_id = nhe_id;
 
-	/* Add nexthop. */
-	nexthop = nexthop_new();
-	*nexthop = *nh;
-	route_entry_nexthop_add(re, nexthop);
+	if (!nhe_id) {
+		re->ng = nexthop_group_new();
+
+		/* Add nexthop. */
+		nexthop = nexthop_new();
+		*nexthop = *nh;
+		route_entry_nexthop_add(re, nexthop);
+	}
 
 	return rib_add_multipath(afi, safi, p, src_p, re);
 }
@@ -3218,7 +3296,7 @@ void rib_sweep_table(struct route_table *table)
 			 * this decision needs to be revisited
 			 */
 			SET_FLAG(re->status, ROUTE_ENTRY_INSTALLED);
-			for (ALL_NEXTHOPS(re->ng, nexthop))
+			for (ALL_NEXTHOPS_PTR(re->ng, nexthop))
 				SET_FLAG(nexthop->flags, NEXTHOP_FLAG_FIB);
 
 			rib_uninstall_kernel(rn, re);
@@ -3242,6 +3320,7 @@ int rib_sweep_route(struct thread *t)
 	}
 
 	zebra_router_sweep_route();
+	zebra_router_sweep_nhgs();
 
 	return 0;
 }
@@ -3412,6 +3491,12 @@ static int rib_process_dplane_results(struct thread *thread)
 				rib_process_dplane_notify(ctx);
 				break;
 
+			case DPLANE_OP_NH_INSTALL:
+			case DPLANE_OP_NH_UPDATE:
+			case DPLANE_OP_NH_DELETE:
+				zebra_nhg_dplane_result(ctx);
+				break;
+
 			case DPLANE_OP_LSP_INSTALL:
 			case DPLANE_OP_LSP_UPDATE:
 			case DPLANE_OP_LSP_DELETE: