[mirror_frr.git] / zebra / zebra_nhg.c

/* Zebra Nexthop Group Code.
 * Copyright (C) 2019 Cumulus Networks, Inc.
 *                    Donald Sharp
 *                    Stephen Worley
 *
 * This file is part of FRR.
 *
 * FRR is free software; you can redistribute it and/or modify it
 * under the terms of the GNU General Public License as published by the
 * Free Software Foundation; either version 2, or (at your option) any
 * later version.
 *
 * FRR is distributed in the hope that it will be useful, but
 * WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with FRR; see the file COPYING.  If not, write to the Free
 * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
 * 02111-1307, USA.
 */
#include <zebra.h>

#include "lib/nexthop.h"
#include "lib/nexthop_group_private.h"
#include "lib/routemap.h"
#include "lib/mpls.h"
#include "lib/jhash.h"
#include "lib/debug.h"

#include "zebra/connected.h"
#include "zebra/debug.h"
#include "zebra/zebra_router.h"
#include "zebra/zebra_nhg_private.h"
#include "zebra/zebra_rnh.h"
#include "zebra/zebra_routemap.h"
#include "zebra/zebra_memory.h"
#include "zebra/zserv.h"
#include "zebra/rt.h"
#include "zebra_errors.h"
#include "zebra_dplane.h"
#include "zebra/interface.h"

DEFINE_MTYPE_STATIC(ZEBRA, NHG, "Nexthop Group Entry");
DEFINE_MTYPE_STATIC(ZEBRA, NHG_CONNECTED, "Nexthop Group Connected");
DEFINE_MTYPE_STATIC(ZEBRA, NHG_CTX, "Nexthop Group Context");

/* id counter to keep in sync with kernel */
uint32_t id_counter;

/*  */
static bool g_nexthops_enabled = true;

static struct nhg_hash_entry *depends_find(const struct nexthop *nh,
					   afi_t afi);
static void depends_add(struct nhg_connected_tree_head *head,
			struct nhg_hash_entry *depend);
static struct nhg_hash_entry *
depends_find_add(struct nhg_connected_tree_head *head, struct nexthop *nh,
		 afi_t afi);
static struct nhg_hash_entry *
depends_find_id_add(struct nhg_connected_tree_head *head, uint32_t id);
static void depends_decrement_free(struct nhg_connected_tree_head *head);

static struct nhg_backup_info *
nhg_backup_copy(const struct nhg_backup_info *orig);


static void nhg_connected_free(struct nhg_connected *dep)
{
	XFREE(MTYPE_NHG_CONNECTED, dep);
}

static struct nhg_connected *nhg_connected_new(struct nhg_hash_entry *nhe)
{
	struct nhg_connected *new = NULL;

	new = XCALLOC(MTYPE_NHG_CONNECTED, sizeof(struct nhg_connected));
	new->nhe = nhe;

	return new;
}

void nhg_connected_tree_free(struct nhg_connected_tree_head *head)
{
	struct nhg_connected *rb_node_dep = NULL;

	if (!nhg_connected_tree_is_empty(head)) {
		frr_each_safe(nhg_connected_tree, head, rb_node_dep) {
			nhg_connected_tree_del(head, rb_node_dep);
			nhg_connected_free(rb_node_dep);
		}
	}
}

bool nhg_connected_tree_is_empty(const struct nhg_connected_tree_head *head)
{
	return nhg_connected_tree_count(head) ? false : true;
}

struct nhg_connected *
nhg_connected_tree_root(struct nhg_connected_tree_head *head)
{
	return nhg_connected_tree_first(head);
}

struct nhg_hash_entry *
nhg_connected_tree_del_nhe(struct nhg_connected_tree_head *head,
			   struct nhg_hash_entry *depend)
{
	struct nhg_connected lookup = {};
	struct nhg_connected *remove = NULL;
	struct nhg_hash_entry *removed_nhe;

	lookup.nhe = depend;

	/* Lookup to find the element, then remove it */
	remove = nhg_connected_tree_find(head, &lookup);
	if (remove)
		/* Re-returning here just in case this API changes..
		 * the _del list api's are a bit undefined at the moment.
		 *
		 * So hopefully returning here will make it fail if the api
		 * changes to something different than currently expected.
		 */
		remove = nhg_connected_tree_del(head, remove);

	/* If the entry was sucessfully removed, free the 'connected` struct */
	if (remove) {
		removed_nhe = remove->nhe;
		nhg_connected_free(remove);
		return removed_nhe;
	}

	return NULL;
}

/* Assuming UNIQUE RB tree. If this changes, assumptions here about
 * insertion need to change.
 */
struct nhg_hash_entry *
nhg_connected_tree_add_nhe(struct nhg_connected_tree_head *head,
			   struct nhg_hash_entry *depend)
{
	struct nhg_connected *new = NULL;

	new = nhg_connected_new(depend);

	/* On success, NULL will be returned from the
	 * RB code.
	 */
	if (new && (nhg_connected_tree_add(head, new) == NULL))
		return NULL;

	/* If it wasn't successful, it must be a duplicate. We enforce the
	 * unique property for the `nhg_connected` tree.
	 */
	nhg_connected_free(new);

	return depend;
}

static void
nhg_connected_tree_decrement_ref(struct nhg_connected_tree_head *head)
{
	struct nhg_connected *rb_node_dep = NULL;

	frr_each_safe(nhg_connected_tree, head, rb_node_dep) {
		zebra_nhg_decrement_ref(rb_node_dep->nhe);
	}
}

static void
nhg_connected_tree_increment_ref(struct nhg_connected_tree_head *head)
{
	struct nhg_connected *rb_node_dep = NULL;

	frr_each(nhg_connected_tree, head, rb_node_dep) {
		zebra_nhg_increment_ref(rb_node_dep->nhe);
	}
}

struct nhg_hash_entry *zebra_nhg_resolve(struct nhg_hash_entry *nhe)
{
	if (CHECK_FLAG(nhe->flags, NEXTHOP_GROUP_RECURSIVE)
	    && !zebra_nhg_depends_is_empty(nhe)) {
		nhe = nhg_connected_tree_root(&nhe->nhg_depends)->nhe;
		return zebra_nhg_resolve(nhe);
	}

	return nhe;
}

unsigned int zebra_nhg_depends_count(const struct nhg_hash_entry *nhe)
{
	return nhg_connected_tree_count(&nhe->nhg_depends);
}

bool zebra_nhg_depends_is_empty(const struct nhg_hash_entry *nhe)
{
	return nhg_connected_tree_is_empty(&nhe->nhg_depends);
}

static void zebra_nhg_depends_del(struct nhg_hash_entry *from,
				  struct nhg_hash_entry *depend)
{
	nhg_connected_tree_del_nhe(&from->nhg_depends, depend);
}

static void zebra_nhg_depends_init(struct nhg_hash_entry *nhe)
{
	nhg_connected_tree_init(&nhe->nhg_depends);
}

unsigned int zebra_nhg_dependents_count(const struct nhg_hash_entry *nhe)
{
	return nhg_connected_tree_count(&nhe->nhg_dependents);
}


bool zebra_nhg_dependents_is_empty(const struct nhg_hash_entry *nhe)
{
	return nhg_connected_tree_is_empty(&nhe->nhg_dependents);
}

static void zebra_nhg_dependents_del(struct nhg_hash_entry *from,
				     struct nhg_hash_entry *dependent)
{
	nhg_connected_tree_del_nhe(&from->nhg_dependents, dependent);
}

static void zebra_nhg_dependents_add(struct nhg_hash_entry *to,
				     struct nhg_hash_entry *dependent)
{
	nhg_connected_tree_add_nhe(&to->nhg_dependents, dependent);
}

static void zebra_nhg_dependents_init(struct nhg_hash_entry *nhe)
{
	nhg_connected_tree_init(&nhe->nhg_dependents);
}

/* Release this nhe from anything depending on it */
static void zebra_nhg_dependents_release(struct nhg_hash_entry *nhe)
{
	struct nhg_connected *rb_node_dep = NULL;

	frr_each_safe(nhg_connected_tree, &nhe->nhg_dependents, rb_node_dep) {
		zebra_nhg_depends_del(rb_node_dep->nhe, nhe);
		/* recheck validity of the dependent */
		zebra_nhg_check_valid(rb_node_dep->nhe);
	}
}

/* Release this nhe from anything that it depends on */
static void zebra_nhg_depends_release(struct nhg_hash_entry *nhe)
{
	if (!zebra_nhg_depends_is_empty(nhe)) {
		struct nhg_connected *rb_node_dep = NULL;

		frr_each_safe(nhg_connected_tree, &nhe->nhg_depends,
			       rb_node_dep) {
			zebra_nhg_dependents_del(rb_node_dep->nhe, nhe);
		}
	}
}


struct nhg_hash_entry *zebra_nhg_lookup_id(uint32_t id)
{
	struct nhg_hash_entry lookup = {};

	lookup.id = id;
	return hash_lookup(zrouter.nhgs_id, &lookup);
}

static int zebra_nhg_insert_id(struct nhg_hash_entry *nhe)
{
	if (hash_lookup(zrouter.nhgs_id, nhe)) {
		flog_err(
			EC_ZEBRA_NHG_TABLE_INSERT_FAILED,
			"Failed inserting NHG id=%u into the ID hash table, entry already exists",
			nhe->id);
		return -1;
	}

	hash_get(zrouter.nhgs_id, nhe, hash_alloc_intern);

	return 0;
}

static void zebra_nhg_set_if(struct nhg_hash_entry *nhe, struct interface *ifp)
{
	nhe->ifp = ifp;
	if_nhg_dependents_add(ifp, nhe);
}

static void
zebra_nhg_connect_depends(struct nhg_hash_entry *nhe,
			  struct nhg_connected_tree_head *nhg_depends)
{
	struct nhg_connected *rb_node_dep = NULL;

	/* This has been allocated higher above in the stack. Could probably
	 * re-allocate and free the old stuff but just using the same memory
	 * for now. Otherwise, their might be a time trade-off for repeated
	 * alloc/frees as startup.
	 */
	nhe->nhg_depends = *nhg_depends;

	/* Attach backpointer to anything that it depends on */
	zebra_nhg_dependents_init(nhe);
	if (!zebra_nhg_depends_is_empty(nhe)) {
		frr_each(nhg_connected_tree, &nhe->nhg_depends, rb_node_dep) {
			if (IS_ZEBRA_DEBUG_NHG_DETAIL)
				zlog_debug("%s: nhe %p (%u), dep %p (%u)",
					   __func__, nhe, nhe->id,
					   rb_node_dep->nhe,
					   rb_node_dep->nhe->id);

			zebra_nhg_dependents_add(rb_node_dep->nhe, nhe);
		}
	}
}

/* Init an nhe, for use in a hash lookup for example */
void zebra_nhe_init(struct nhg_hash_entry *nhe, afi_t afi,
		    const struct nexthop *nh)
{
	memset(nhe, 0, sizeof(struct nhg_hash_entry));
	nhe->vrf_id = VRF_DEFAULT;
	nhe->type = ZEBRA_ROUTE_NHG;
	nhe->afi = AFI_UNSPEC;

	/* There are some special rules that apply to groups representing
	 * a single nexthop.
	 */
	if (nh && (nh->next == NULL)) {
		switch (nh->type) {
		case (NEXTHOP_TYPE_IFINDEX):
		case (NEXTHOP_TYPE_BLACKHOLE):
			/*
			 * This switch case handles setting the afi different
			 * for ipv4/v6 routes. Ifindex/blackhole nexthop
			 * objects cannot be ambiguous, they must be Address
			 * Family specific. If we get here, we will either use
			 * the AF of the route, or the one we got passed from
			 * here from the kernel.
			 */
			nhe->afi = afi;
			break;
		case (NEXTHOP_TYPE_IPV4_IFINDEX):
		case (NEXTHOP_TYPE_IPV4):
			nhe->afi = AFI_IP;
			break;
		case (NEXTHOP_TYPE_IPV6_IFINDEX):
		case (NEXTHOP_TYPE_IPV6):
			nhe->afi = AFI_IP6;
			break;
		}
	}
}

struct nhg_hash_entry *zebra_nhg_alloc(void)
{
	struct nhg_hash_entry *nhe;

	nhe = XCALLOC(MTYPE_NHG, sizeof(struct nhg_hash_entry));

	return nhe;
}

/*
 * Allocate new nhe and make shallow copy of 'orig'; no
 * recursive info is copied.
 */
struct nhg_hash_entry *zebra_nhe_copy(const struct nhg_hash_entry *orig,
				      uint32_t id)
{
	struct nhg_hash_entry *nhe;

	nhe = zebra_nhg_alloc();

	nhe->id = id;

	nexthop_group_copy(&(nhe->nhg), &(orig->nhg));

	nhe->vrf_id = orig->vrf_id;
	nhe->afi = orig->afi;
	nhe->type = orig->type ? orig->type : ZEBRA_ROUTE_NHG;
	nhe->refcnt = 0;
	nhe->dplane_ref = zebra_router_get_next_sequence();

	/* Copy backup info also, if present */
	if (orig->backup_info)
		nhe->backup_info = nhg_backup_copy(orig->backup_info);

	return nhe;
}

/* Allocation via hash handler */
static void *zebra_nhg_hash_alloc(void *arg)
{
	struct nhg_hash_entry *nhe = NULL;
	struct nhg_hash_entry *copy = arg;

	nhe = zebra_nhe_copy(copy, copy->id);

	/* Mark duplicate nexthops in a group at creation time. */
	nexthop_group_mark_duplicates(&(nhe->nhg));

	zebra_nhg_connect_depends(nhe, &(copy->nhg_depends));

	/* Add the ifp now if it's not a group or recursive and has ifindex */
	if (zebra_nhg_depends_is_empty(nhe) && nhe->nhg.nexthop
	    && nhe->nhg.nexthop->ifindex) {
		struct interface *ifp = NULL;

		ifp = if_lookup_by_index(nhe->nhg.nexthop->ifindex,
					 nhe->nhg.nexthop->vrf_id);
		if (ifp)
			zebra_nhg_set_if(nhe, ifp);
		else
			flog_err(
				EC_ZEBRA_IF_LOOKUP_FAILED,
				"Zebra failed to lookup an interface with ifindex=%d in vrf=%u for NHE id=%u",
				nhe->nhg.nexthop->ifindex,
				nhe->nhg.nexthop->vrf_id, nhe->id);
	}

	zebra_nhg_insert_id(nhe);

	return nhe;
}

uint32_t zebra_nhg_hash_key(const void *arg)
{
	const struct nhg_hash_entry *nhe = arg;
	uint32_t val, key = 0x5a351234;

	val = nexthop_group_hash(&(nhe->nhg));
	if (nhe->backup_info) {
		val = jhash_2words(val,
				   nexthop_group_hash(
					   &(nhe->backup_info->nhe->nhg)),
				   key);
	}

	key = jhash_3words(nhe->vrf_id, nhe->afi, val, key);

	return key;
}

uint32_t zebra_nhg_id_key(const void *arg)
{
	const struct nhg_hash_entry *nhe = arg;

	return nhe->id;
}

/* Helper with common nhg/nhe nexthop comparison logic */
static bool nhg_compare_nexthops(const struct nexthop *nh1,
				 const struct nexthop *nh2)
{
	assert(nh1 != NULL && nh2 != NULL);

	/*
	 * We have to check the active flag of each individual one,
	 * not just the overall active_num. This solves the special case
	 * issue of a route with a nexthop group with one nexthop
	 * resolving to itself and thus marking it inactive. If we
	 * have two different routes each wanting to mark a different
	 * nexthop inactive, they need to hash to two different groups.
	 *
	 * If we just hashed on num_active, they would hash the same
	 * which is incorrect.
	 *
	 * ex)
	 *      1.1.1.0/24
	 *           -> 1.1.1.1 dummy1 (inactive)
	 *           -> 1.1.2.1 dummy2
	 *
	 *      1.1.2.0/24
	 *           -> 1.1.1.1 dummy1
	 *           -> 1.1.2.1 dummy2 (inactive)
	 *
	 * Without checking each individual one, they would hash to
	 * the same group and both have 1.1.1.1 dummy1 marked inactive.
	 *
	 */
	if (CHECK_FLAG(nh1->flags, NEXTHOP_FLAG_ACTIVE)
	    != CHECK_FLAG(nh2->flags, NEXTHOP_FLAG_ACTIVE))
		return false;

	if (!nexthop_same(nh1, nh2))
		return false;

	return true;
}

bool zebra_nhg_hash_equal(const void *arg1, const void *arg2)
{
	const struct nhg_hash_entry *nhe1 = arg1;
	const struct nhg_hash_entry *nhe2 = arg2;
	struct nexthop *nexthop1;
	struct nexthop *nexthop2;

	/* No matter what if they equal IDs, assume equal */
	if (nhe1->id && nhe2->id && (nhe1->id == nhe2->id))
		return true;

	if (nhe1->vrf_id != nhe2->vrf_id)
		return false;

	if (nhe1->afi != nhe2->afi)
		return false;

	/* Nexthops should be in-order, so we simply compare them in-place */
	for (nexthop1 = nhe1->nhg.nexthop, nexthop2 = nhe2->nhg.nexthop;
	     nexthop1 && nexthop2;
	     nexthop1 = nexthop1->next, nexthop2 = nexthop2->next) {

		if (!nhg_compare_nexthops(nexthop1, nexthop2))
			return false;
	}

	/* Check for unequal list lengths */
	if (nexthop1 || nexthop2)
		return false;

	/* If there's no backup info, comparison is done. */
	if ((nhe1->backup_info == NULL) && (nhe2->backup_info == NULL))
		return true;

	/* Compare backup info also - test the easy things first */
	if (nhe1->backup_info && (nhe2->backup_info == NULL))
		return false;
	if (nhe2->backup_info && (nhe1->backup_info == NULL))
		return false;

	/* Compare number of backups before actually comparing any */
	for (nexthop1 = nhe1->backup_info->nhe->nhg.nexthop,
	     nexthop2 = nhe2->backup_info->nhe->nhg.nexthop;
	     nexthop1 && nexthop2;
	     nexthop1 = nexthop1->next, nexthop2 = nexthop2->next) {
		;
	}

	/* Did we find the end of one list before the other? */
	if (nexthop1 || nexthop2)
		return false;

	/* Have to compare the backup nexthops */
	for (nexthop1 = nhe1->backup_info->nhe->nhg.nexthop,
	     nexthop2 = nhe2->backup_info->nhe->nhg.nexthop;
	     nexthop1 && nexthop2;
	     nexthop1 = nexthop1->next, nexthop2 = nexthop2->next) {

		if (!nhg_compare_nexthops(nexthop1, nexthop2))
			return false;
	}

	return true;
}

bool zebra_nhg_hash_id_equal(const void *arg1, const void *arg2)
{
	const struct nhg_hash_entry *nhe1 = arg1;
	const struct nhg_hash_entry *nhe2 = arg2;

	return nhe1->id == nhe2->id;
}

static int zebra_nhg_process_grp(struct nexthop_group *nhg,
				 struct nhg_connected_tree_head *depends,
				 struct nh_grp *grp, uint8_t count)
{
	nhg_connected_tree_init(depends);

	for (int i = 0; i < count; i++) {
		struct nhg_hash_entry *depend = NULL;
		/* We do not care about nexthop_grp.weight at
		 * this time. But we should figure out
		 * how to adapt this to our code in
		 * the future.
		 */
		depend = depends_find_id_add(depends, grp[i].id);

		if (!depend) {
			flog_err(
				EC_ZEBRA_NHG_SYNC,
				"Received Nexthop Group from the kernel with a dependent Nexthop ID (%u) which we do not have in our table",
				grp[i].id);
			return -1;
		}

		/*
		 * If this is a nexthop with its own group
		 * dependencies, add them as well. Not sure its
		 * even possible to have a group within a group
		 * in the kernel.
		 */

		copy_nexthops(&nhg->nexthop, depend->nhg.nexthop, NULL);
	}

	return 0;
}

static void handle_recursive_depend(struct nhg_connected_tree_head *nhg_depends,
				    struct nexthop *nh, afi_t afi)
{
	struct nhg_hash_entry *depend = NULL;
	struct nexthop_group resolved_ng = {};

	resolved_ng.nexthop = nh;

	if (IS_ZEBRA_DEBUG_NHG_DETAIL)
		zlog_debug("%s: head %p, nh %pNHv",
			   __func__, nhg_depends, nh);

	depend = zebra_nhg_rib_find(0, &resolved_ng, afi);

	if (IS_ZEBRA_DEBUG_NHG_DETAIL)
		zlog_debug("%s: nh %pNHv => %p (%u)",
			   __func__, nh, depend,
			   depend ? depend->id : 0);

	if (depend)
		depends_add(nhg_depends, depend);
}

/*
 * Lookup an nhe in the global hash, using data from another nhe. If 'lookup'
 * has an id value, that's used. Create a new global/shared nhe if not found.
 */
static bool zebra_nhe_find(struct nhg_hash_entry **nhe, /* return value */
			   struct nhg_hash_entry *lookup,
			   struct nhg_connected_tree_head *nhg_depends,
			   afi_t afi)
{
	bool created = false;
	bool recursive = false;
	struct nhg_hash_entry *newnhe, *backup_nhe;
	struct nexthop *nh = NULL;

	if (IS_ZEBRA_DEBUG_NHG_DETAIL)
		zlog_debug("%s: id %u, lookup %p, vrf %d, type %d, depends %p",
			   __func__, lookup->id, lookup,
			   lookup->vrf_id, lookup->type,
			   nhg_depends);

	if (lookup->id)
		(*nhe) = zebra_nhg_lookup_id(lookup->id);
	else
		(*nhe) = hash_lookup(zrouter.nhgs, lookup);

	if (IS_ZEBRA_DEBUG_NHG_DETAIL)
		zlog_debug("%s: lookup => %p (%u)",
			   __func__, (*nhe),
			   (*nhe) ? (*nhe)->id : 0);

	/* If we found an existing object, we're done */
	if (*nhe)
		goto done;

	/* We're going to create/insert a new nhe:
	 * assign the next global id value if necessary.
	 */
	if (lookup->id == 0)
		lookup->id = ++id_counter;
	newnhe = hash_get(zrouter.nhgs, lookup, zebra_nhg_hash_alloc);
	created = true;

	/* Mail back the new object */
	*nhe = newnhe;

	if (IS_ZEBRA_DEBUG_NHG_DETAIL)
		zlog_debug("%s: => created %p (%u)", __func__, newnhe,
			   newnhe->id);

	/* Only hash/lookup the depends if the first lookup
	 * fails to find something. This should hopefully save a
	 * lot of cycles for larger ecmp sizes.
	 */
	if (nhg_depends) {
		/* If you don't want to hash on each nexthop in the
		 * nexthop group struct you can pass the depends
		 * directly. Kernel-side we do this since it just looks
		 * them up via IDs.
		 */
		zebra_nhg_connect_depends(newnhe, nhg_depends);
		goto done;
	}

	/* Prepare dependency relationships if this is not a
	 * singleton nexthop. There are two cases: a single
	 * recursive nexthop, where we need a relationship to the
	 * resolving nexthop; or a group of nexthops, where we need
	 * relationships with the corresponding singletons.
	 */
	zebra_nhg_depends_init(lookup);

	nh = newnhe->nhg.nexthop;

	if (CHECK_FLAG(nh->flags, NEXTHOP_FLAG_ACTIVE))
		SET_FLAG(newnhe->flags, NEXTHOP_GROUP_VALID);

	if (nh->next == NULL) {
		if (CHECK_FLAG(nh->flags, NEXTHOP_FLAG_RECURSIVE)) {
			/* Single recursive nexthop */
			handle_recursive_depend(&newnhe->nhg_depends,
						nh->resolved, afi);
			recursive = true;
		}
	} else {
		/* List of nexthops */
		for (nh = newnhe->nhg.nexthop; nh; nh = nh->next) {
			if (IS_ZEBRA_DEBUG_NHG_DETAIL)
				zlog_debug("%s: depends NH %pNHv %s",
					   __func__, nh,
					   CHECK_FLAG(nh->flags,
						      NEXTHOP_FLAG_RECURSIVE) ?
					   "(R)" : "");

			depends_find_add(&newnhe->nhg_depends, nh, afi);
		}
	}

	if (recursive)
		SET_FLAG((*nhe)->flags, NEXTHOP_GROUP_RECURSIVE);

	if (zebra_nhg_get_backup_nhg(newnhe) == NULL ||
	    zebra_nhg_get_backup_nhg(newnhe)->nexthop == NULL)
		goto done;

	/* If there are backup nexthops, add them to the backup
	 * depends tree. The rules here are a little different.
	 */
	recursive = false;
	backup_nhe = newnhe->backup_info->nhe;

	nh = backup_nhe->nhg.nexthop;

	/* Singleton recursive NH */
	if (nh->next == NULL &&
	    CHECK_FLAG(nh->flags, NEXTHOP_FLAG_RECURSIVE)) {
		if (IS_ZEBRA_DEBUG_NHG_DETAIL)
			zlog_debug("%s: backup depend NH %pNHv (R)",
				   __func__, nh);

		/* Single recursive nexthop */
		handle_recursive_depend(&backup_nhe->nhg_depends,
					nh->resolved, afi);
		recursive = true;
	} else {
		/* One or more backup NHs */
		for (; nh; nh = nh->next) {
			if (IS_ZEBRA_DEBUG_NHG_DETAIL)
				zlog_debug("%s: backup depend NH %pNHv %s",
					   __func__, nh,
					   CHECK_FLAG(nh->flags,
						      NEXTHOP_FLAG_RECURSIVE) ?
					   "(R)" : "");

			depends_find_add(&backup_nhe->nhg_depends,
					 nh, afi);
		}
	}

	if (recursive)
		SET_FLAG(backup_nhe->flags, NEXTHOP_GROUP_RECURSIVE);

done:

	return created;
}

/*
 * Lookup or create an nhe, based on an nhg or an nhe id.
 */
static bool zebra_nhg_find(struct nhg_hash_entry **nhe, uint32_t id,
			   struct nexthop_group *nhg,
			   struct nhg_connected_tree_head *nhg_depends,
			   vrf_id_t vrf_id, afi_t afi, int type)
{
	struct nhg_hash_entry lookup = {};
	bool created = false;

	if (IS_ZEBRA_DEBUG_NHG_DETAIL)
		zlog_debug("%s: id %u, nhg %p, vrf %d, type %d, depends %p",
			   __func__, id, nhg, vrf_id, type,
			   nhg_depends);

	/* Use a temporary nhe and call into the superset/common code */
	lookup.id = id;
	lookup.type = type ? type : ZEBRA_ROUTE_NHG;
	lookup.nhg = *nhg;

	lookup.vrf_id = vrf_id;
	if (lookup.nhg.nexthop->next) {
		/* Groups can have all vrfs and AF's in them */
		lookup.afi = AFI_UNSPEC;
	} else {
		switch (lookup.nhg.nexthop->type) {
		case (NEXTHOP_TYPE_IFINDEX):
		case (NEXTHOP_TYPE_BLACKHOLE):
			/*
			 * This switch case handles setting the afi different
			 * for ipv4/v6 routes. Ifindex/blackhole nexthop
			 * objects cannot be ambiguous, they must be Address
			 * Family specific. If we get here, we will either use
			 * the AF of the route, or the one we got passed from
			 * here from the kernel.
			 */
			lookup.afi = afi;
			break;
		case (NEXTHOP_TYPE_IPV4_IFINDEX):
		case (NEXTHOP_TYPE_IPV4):
			lookup.afi = AFI_IP;
			break;
		case (NEXTHOP_TYPE_IPV6_IFINDEX):
		case (NEXTHOP_TYPE_IPV6):
			lookup.afi = AFI_IP6;
			break;
		}
	}

	created = zebra_nhe_find(nhe, &lookup, nhg_depends, afi);

	return created;
}

/* Find/create a single nexthop */
static struct nhg_hash_entry *
zebra_nhg_find_nexthop(uint32_t id, struct nexthop *nh, afi_t afi, int type)
{
	struct nhg_hash_entry *nhe = NULL;
	struct nexthop_group nhg = {};
	vrf_id_t vrf_id = !vrf_is_backend_netns() ? VRF_DEFAULT : nh->vrf_id;

	nexthop_group_add_sorted(&nhg, nh);

	zebra_nhg_find(&nhe, id, &nhg, NULL, vrf_id, afi, type);

	if (IS_ZEBRA_DEBUG_NHG_DETAIL)
		zlog_debug("%s: nh %pNHv => %p (%u)",
			   __func__, nh, nhe, nhe ? nhe->id : 0);

	return nhe;
}

static uint32_t nhg_ctx_get_id(const struct nhg_ctx *ctx)
{
	return ctx->id;
}

static void nhg_ctx_set_status(struct nhg_ctx *ctx, enum nhg_ctx_status status)
{
	ctx->status = status;
}

static enum nhg_ctx_status nhg_ctx_get_status(const struct nhg_ctx *ctx)
{
	return ctx->status;
}

static void nhg_ctx_set_op(struct nhg_ctx *ctx, enum nhg_ctx_op_e op)
{
	ctx->op = op;
}

static enum nhg_ctx_op_e nhg_ctx_get_op(const struct nhg_ctx *ctx)
{
	return ctx->op;
}

static vrf_id_t nhg_ctx_get_vrf_id(const struct nhg_ctx *ctx)
{
	return ctx->vrf_id;
}

static int nhg_ctx_get_type(const struct nhg_ctx *ctx)
{
	return ctx->type;
}

static int nhg_ctx_get_afi(const struct nhg_ctx *ctx)
{
	return ctx->afi;
}

static struct nexthop *nhg_ctx_get_nh(struct nhg_ctx *ctx)
{
	return &ctx->u.nh;
}

static uint8_t nhg_ctx_get_count(const struct nhg_ctx *ctx)
{
	return ctx->count;
}

static struct nh_grp *nhg_ctx_get_grp(struct nhg_ctx *ctx)
{
	return ctx->u.grp;
}

static struct nhg_ctx *nhg_ctx_new(void)
{
	struct nhg_ctx *new;

	new = XCALLOC(MTYPE_NHG_CTX, sizeof(struct nhg_ctx));

	return new;
}

static void nhg_ctx_free(struct nhg_ctx **ctx)
{
	struct nexthop *nh;

	if (ctx == NULL)
		return;

	assert((*ctx) != NULL);

	if (nhg_ctx_get_count(*ctx))
		goto done;

	nh = nhg_ctx_get_nh(*ctx);

	nexthop_del_labels(nh);

done:
	XFREE(MTYPE_NHG_CTX, *ctx);
}

static struct nhg_ctx *nhg_ctx_init(uint32_t id, struct nexthop *nh,
				    struct nh_grp *grp, vrf_id_t vrf_id,
				    afi_t afi, int type, uint8_t count)
{
	struct nhg_ctx *ctx = NULL;

	ctx = nhg_ctx_new();

	ctx->id = id;
	ctx->vrf_id = vrf_id;
	ctx->afi = afi;
	ctx->type = type;
	ctx->count = count;

	if (count)
		/* Copy over the array */
		memcpy(&ctx->u.grp, grp, count * sizeof(struct nh_grp));
	else if (nh)
		ctx->u.nh = *nh;

	return ctx;
}

static bool zebra_nhg_contains_unhashable(struct nhg_hash_entry *nhe)
{
	struct nhg_connected *rb_node_dep = NULL;

	frr_each(nhg_connected_tree, &nhe->nhg_depends, rb_node_dep) {
		if (CHECK_FLAG(rb_node_dep->nhe->flags,
			       NEXTHOP_GROUP_UNHASHABLE))
			return true;
	}

	return false;
}

static void zebra_nhg_set_unhashable(struct nhg_hash_entry *nhe)
{
	SET_FLAG(nhe->flags, NEXTHOP_GROUP_UNHASHABLE);
	SET_FLAG(nhe->flags, NEXTHOP_GROUP_INSTALLED);

	flog(LOG_INFO,
	     EC_ZEBRA_DUPLICATE_NHG_MESSAGE,
	     "Nexthop Group with ID (%d) is a duplicate, therefore unhashable, ignoring",
	     nhe->id);
}

static void zebra_nhg_set_valid(struct nhg_hash_entry *nhe)
{
	struct nhg_connected *rb_node_dep;

	SET_FLAG(nhe->flags, NEXTHOP_GROUP_VALID);

	frr_each(nhg_connected_tree, &nhe->nhg_dependents, rb_node_dep)
		zebra_nhg_set_valid(rb_node_dep->nhe);
}

static void zebra_nhg_set_invalid(struct nhg_hash_entry *nhe)
{
	struct nhg_connected *rb_node_dep;

	UNSET_FLAG(nhe->flags, NEXTHOP_GROUP_VALID);

	/* Update validity of nexthops depending on it */
	frr_each(nhg_connected_tree, &nhe->nhg_dependents, rb_node_dep)
		zebra_nhg_check_valid(rb_node_dep->nhe);
}

void zebra_nhg_check_valid(struct nhg_hash_entry *nhe)
{
	struct nhg_connected *rb_node_dep = NULL;
	bool valid = false;

	/* If anthing else in the group is valid, the group is valid */
	frr_each(nhg_connected_tree, &nhe->nhg_depends, rb_node_dep) {
		if (CHECK_FLAG(rb_node_dep->nhe->flags, NEXTHOP_GROUP_VALID)) {
			valid = true;
			goto done;
		}
	}

done:
	if (valid)
		zebra_nhg_set_valid(nhe);
	else
		zebra_nhg_set_invalid(nhe);
}


static void zebra_nhg_release(struct nhg_hash_entry *nhe)
{
	if (IS_ZEBRA_DEBUG_NHG_DETAIL)
		zlog_debug("%s: nhe %p (%u)", __func__, nhe, nhe->id);

	/* Remove it from any lists it may be on */
	zebra_nhg_depends_release(nhe);
	zebra_nhg_dependents_release(nhe);
	if (nhe->ifp)
		if_nhg_dependents_del(nhe->ifp, nhe);

	/*
	 * If its unhashable, we didn't store it here and have to be
	 * sure we don't clear one thats actually being used.
	 */
	if (!CHECK_FLAG(nhe->flags, NEXTHOP_GROUP_UNHASHABLE))
		hash_release(zrouter.nhgs, nhe);

	hash_release(zrouter.nhgs_id, nhe);
}

static void zebra_nhg_handle_uninstall(struct nhg_hash_entry *nhe)
{
	zebra_nhg_release(nhe);
	zebra_nhg_free(nhe);
}

static void zebra_nhg_handle_install(struct nhg_hash_entry *nhe)
{
	/* Update validity of groups depending on it */
	struct nhg_connected *rb_node_dep;

	frr_each_safe(nhg_connected_tree, &nhe->nhg_dependents, rb_node_dep)
		zebra_nhg_set_valid(rb_node_dep->nhe);
}

/*
 * The kernel/other program has changed the state of a nexthop object we are
 * using.
 */
static void zebra_nhg_handle_kernel_state_change(struct nhg_hash_entry *nhe,
						 bool is_delete)
{
	if (nhe->refcnt) {
		flog_err(
			EC_ZEBRA_NHG_SYNC,
			"Kernel %s a nexthop group with ID (%u) that we are still using for a route, sending it back down",
			(is_delete ? "deleted" : "updated"), nhe->id);

		UNSET_FLAG(nhe->flags, NEXTHOP_GROUP_INSTALLED);
		zebra_nhg_install_kernel(nhe);
	} else
		zebra_nhg_handle_uninstall(nhe);
}

static int nhg_ctx_process_new(struct nhg_ctx *ctx)
{
	struct nexthop_group *nhg = NULL;
	struct nhg_connected_tree_head nhg_depends = {};
	struct nhg_hash_entry *lookup = NULL;
	struct nhg_hash_entry *nhe = NULL;

	uint32_t id = nhg_ctx_get_id(ctx);
	uint8_t count = nhg_ctx_get_count(ctx);
	vrf_id_t vrf_id = nhg_ctx_get_vrf_id(ctx);
	int type = nhg_ctx_get_type(ctx);
	afi_t afi = nhg_ctx_get_afi(ctx);

	lookup = zebra_nhg_lookup_id(id);

	if (IS_ZEBRA_DEBUG_NHG_DETAIL)
		zlog_debug("%s: id %u, count %d, lookup => %p",
			   __func__, id, count, lookup);

	if (lookup) {
		/* This is already present in our table, hence an update
		 * that we did not initate.
		 */
		zebra_nhg_handle_kernel_state_change(lookup, false);
		return 0;
	}

	if (nhg_ctx_get_count(ctx)) {
		nhg = nexthop_group_new();
		if (zebra_nhg_process_grp(nhg, &nhg_depends,
					  nhg_ctx_get_grp(ctx), count)) {
			depends_decrement_free(&nhg_depends);
			nexthop_group_delete(&nhg);
			return -ENOENT;
		}

		if (!zebra_nhg_find(&nhe, id, nhg, &nhg_depends, vrf_id, type,
				    afi))
			depends_decrement_free(&nhg_depends);

		/* These got copied over in zebra_nhg_alloc() */
		nexthop_group_delete(&nhg);
	} else
		nhe = zebra_nhg_find_nexthop(id, nhg_ctx_get_nh(ctx), afi,
					     type);

	if (nhe) {
		if (id != nhe->id) {
			struct nhg_hash_entry *kernel_nhe = NULL;

			/* Duplicate but with different ID from
			 * the kernel
			 */

			/* The kernel allows duplicate nexthops
			 * as long as they have different IDs.
			 * We are ignoring those to prevent
			 * syncing problems with the kernel
			 * changes.
			 *
			 * We maintain them *ONLY* in the ID hash table to
			 * track them and set the flag to indicated
			 * their attributes are unhashable.
			 */

			kernel_nhe = zebra_nhe_copy(nhe, id);

			if (IS_ZEBRA_DEBUG_NHG_DETAIL)
				zlog_debug("%s: copying kernel nhe (%u), dup of %u",
					   __func__, id, nhe->id);

			zebra_nhg_insert_id(kernel_nhe);
			zebra_nhg_set_unhashable(kernel_nhe);
		} else if (zebra_nhg_contains_unhashable(nhe)) {
			/* The group we got contains an unhashable/duplicated
			 * depend, so lets mark this group as unhashable as well
			 * and release it from the non-ID hash.
			 */
			if (IS_ZEBRA_DEBUG_NHG_DETAIL)
				zlog_debug("%s: nhe %p (%u) unhashable",
					   __func__, nhe, nhe->id);

			hash_release(zrouter.nhgs, nhe);
			zebra_nhg_set_unhashable(nhe);
		} else {
			/* It actually created a new nhe */
			if (IS_ZEBRA_DEBUG_NHG_DETAIL)
				zlog_debug("%s: nhe %p (%u) is new",
					   __func__, nhe, nhe->id);

			SET_FLAG(nhe->flags, NEXTHOP_GROUP_VALID);
			SET_FLAG(nhe->flags, NEXTHOP_GROUP_INSTALLED);
		}
	} else {
		flog_err(
			EC_ZEBRA_TABLE_LOOKUP_FAILED,
			"Zebra failed to find or create a nexthop hash entry for ID (%u)",
			id);
		return -1;
	}

	return 0;
}

static int nhg_ctx_process_del(struct nhg_ctx *ctx)
{
	struct nhg_hash_entry *nhe = NULL;
	uint32_t id = nhg_ctx_get_id(ctx);

	nhe = zebra_nhg_lookup_id(id);

	if (!nhe) {
		flog_warn(
			EC_ZEBRA_BAD_NHG_MESSAGE,
			"Kernel delete message received for nexthop group ID (%u) that we do not have in our ID table",
			id);
		return -1;
	}

	zebra_nhg_handle_kernel_state_change(nhe, true);

	return 0;
}

static void nhg_ctx_fini(struct nhg_ctx **ctx)
{
	/*
	 * Just freeing for now, maybe do something more in the future
	 * based on flag.
	 */

	nhg_ctx_free(ctx);
}

static int queue_add(struct nhg_ctx *ctx)
{
	/* If its queued or already processed do nothing */
	if (nhg_ctx_get_status(ctx) == NHG_CTX_QUEUED)
		return 0;

	if (rib_queue_nhg_add(ctx)) {
		nhg_ctx_set_status(ctx, NHG_CTX_FAILURE);
		return -1;
	}

	nhg_ctx_set_status(ctx, NHG_CTX_QUEUED);

	return 0;
}

int nhg_ctx_process(struct nhg_ctx *ctx)
{
	int ret = 0;

	switch (nhg_ctx_get_op(ctx)) {
	case NHG_CTX_OP_NEW:
		ret = nhg_ctx_process_new(ctx);
		if (nhg_ctx_get_count(ctx) && ret == -ENOENT
		    && nhg_ctx_get_status(ctx) != NHG_CTX_REQUEUED) {
			/**
			 * We have entered a situation where we are
			 * processing a group from the kernel
			 * that has a contained nexthop which
			 * we have not yet processed.
			 *
			 * Re-enqueue this ctx to be handled exactly one
			 * more time (indicated by the flag).
			 *
			 * By the time we get back to it, we
			 * should have processed its depends.
			 */
			nhg_ctx_set_status(ctx, NHG_CTX_NONE);
			if (queue_add(ctx) == 0) {
				nhg_ctx_set_status(ctx, NHG_CTX_REQUEUED);
				return 0;
			}
		}
		break;
	case NHG_CTX_OP_DEL:
		ret = nhg_ctx_process_del(ctx);
	case NHG_CTX_OP_NONE:
		break;
	}

	nhg_ctx_set_status(ctx, (ret ? NHG_CTX_FAILURE : NHG_CTX_SUCCESS));

	nhg_ctx_fini(&ctx);

	return ret;
}

/* Kernel-side, you either get a single new nexthop or a array of ID's */
int zebra_nhg_kernel_find(uint32_t id, struct nexthop *nh, struct nh_grp *grp,
			  uint8_t count, vrf_id_t vrf_id, afi_t afi, int type,
			  int startup)
{
	struct nhg_ctx *ctx = NULL;

	if (IS_ZEBRA_DEBUG_NHG_DETAIL)
		zlog_debug("%s: nh %pNHv, id %u, count %d",
			   __func__, nh, id, (int)count);

	if (id > id_counter)
		/* Increase our counter so we don't try to create
		 * an ID that already exists
		 */
		id_counter = id;

	ctx = nhg_ctx_init(id, nh, grp, vrf_id, afi, type, count);
	nhg_ctx_set_op(ctx, NHG_CTX_OP_NEW);

	/* Under statup conditions, we need to handle them immediately
	 * like we do for routes. Otherwise, we are going to get a route
	 * with a nhe_id that we have not handled.
	 */
	if (startup)
		return nhg_ctx_process(ctx);

	if (queue_add(ctx)) {
		nhg_ctx_fini(&ctx);
		return -1;
	}

	return 0;
}

/* Kernel-side, received delete message */
int zebra_nhg_kernel_del(uint32_t id, vrf_id_t vrf_id)
{
	struct nhg_ctx *ctx = NULL;

	ctx = nhg_ctx_init(id, NULL, NULL, vrf_id, 0, 0, 0);

	nhg_ctx_set_op(ctx, NHG_CTX_OP_DEL);

	if (queue_add(ctx)) {
		nhg_ctx_fini(&ctx);
		return -1;
	}

	return 0;
}

/* Some dependency helper functions */
static struct nhg_hash_entry *depends_find_recursive(const struct nexthop *nh,
						     afi_t afi)
{
	struct nhg_hash_entry *nhe;
	struct nexthop *lookup = NULL;

	lookup = nexthop_dup(nh, NULL);

	nhe = zebra_nhg_find_nexthop(0, lookup, afi, 0);

	nexthops_free(lookup);

	return nhe;
}

static struct nhg_hash_entry *depends_find_singleton(const struct nexthop *nh,
						     afi_t afi)
{
	struct nhg_hash_entry *nhe;
	struct nexthop lookup = {};

	/* Capture a snapshot of this single nh; it might be part of a list,
	 * so we need to make a standalone copy.
	 */
	nexthop_copy_no_recurse(&lookup, nh, NULL);

	nhe = zebra_nhg_find_nexthop(0, &lookup, afi, 0);

	/* The copy may have allocated labels; free them if necessary. */
	nexthop_del_labels(&lookup);

	if (IS_ZEBRA_DEBUG_NHG_DETAIL)
		zlog_debug("%s: nh %pNHv => %p (%u)",
			   __func__, nh, nhe, nhe ? nhe->id : 0);

	return nhe;
}

static struct nhg_hash_entry *depends_find(const struct nexthop *nh, afi_t afi)
{
	struct nhg_hash_entry *nhe = NULL;
	char rbuf[10];

	if (!nh)
		goto done;

	/* We are separating these functions out to increase handling speed
	 * in the non-recursive case (by not alloc/freeing)
	 */
	if (CHECK_FLAG(nh->flags, NEXTHOP_FLAG_RECURSIVE)) {
		nhe = depends_find_recursive(nh, afi);
		strlcpy(rbuf, "(R)", sizeof(rbuf));
	} else {
		nhe = depends_find_singleton(nh, afi);
		rbuf[0] = '\0';
	}

	if (IS_ZEBRA_DEBUG_NHG_DETAIL)
		zlog_debug("%s: nh %pNHv %s => %p (%u)",
			   __func__, nh, rbuf,
			   nhe, nhe ? nhe->id : 0);

done:
	return nhe;
}

static void depends_add(struct nhg_connected_tree_head *head,
			struct nhg_hash_entry *depend)
{
	if (IS_ZEBRA_DEBUG_NHG_DETAIL)
		zlog_debug("%s: head %p nh %pNHv",
			   __func__, head, depend->nhg.nexthop);

	/* If NULL is returned, it was successfully added and
	 * needs to have its refcnt incremented.
	 *
	 * Else the NHE is already present in the tree and doesn't
	 * need to increment the refcnt.
	 */
	if (nhg_connected_tree_add_nhe(head, depend) == NULL)
		zebra_nhg_increment_ref(depend);
}

static struct nhg_hash_entry *
depends_find_add(struct nhg_connected_tree_head *head, struct nexthop *nh,
		 afi_t afi)
{
	struct nhg_hash_entry *depend = NULL;

	depend = depends_find(nh, afi);

	if (IS_ZEBRA_DEBUG_NHG_DETAIL)
		zlog_debug("%s: nh %pNHv => %p",
			   __func__, nh, depend);

	if (depend)
		depends_add(head, depend);

	return depend;
}

static struct nhg_hash_entry *
depends_find_id_add(struct nhg_connected_tree_head *head, uint32_t id)
{
	struct nhg_hash_entry *depend = NULL;

	depend = zebra_nhg_lookup_id(id);

	if (depend)
		depends_add(head, depend);

	return depend;
}

static void depends_decrement_free(struct nhg_connected_tree_head *head)
{
	nhg_connected_tree_decrement_ref(head);
	nhg_connected_tree_free(head);
}

/* Find an nhe based on a list of nexthops */
struct nhg_hash_entry *
zebra_nhg_rib_find(uint32_t id, struct nexthop_group *nhg, afi_t rt_afi)
{
	struct nhg_hash_entry *nhe = NULL;
	vrf_id_t vrf_id;

	/*
	 * CLANG SA is complaining that nexthop may be NULL
	 * Make it happy but this is ridonc
	 */
	assert(nhg->nexthop);
	vrf_id = !vrf_is_backend_netns() ? VRF_DEFAULT : nhg->nexthop->vrf_id;

	zebra_nhg_find(&nhe, id, nhg, NULL, vrf_id, rt_afi, 0);

	if (IS_ZEBRA_DEBUG_NHG_DETAIL)
		zlog_debug("%s: => nhe %p (%u)",
			   __func__, nhe, nhe ? nhe->id : 0);

	return nhe;
}

/* Find an nhe based on a route's nhe */
struct nhg_hash_entry *
zebra_nhg_rib_find_nhe(struct nhg_hash_entry *rt_nhe, afi_t rt_afi)
{
	struct nhg_hash_entry *nhe = NULL;

	if (!(rt_nhe && rt_nhe->nhg.nexthop)) {
		flog_err(EC_ZEBRA_TABLE_LOOKUP_FAILED,
			 "No nexthop passed to %s", __func__);
		return NULL;
	}

	if (IS_ZEBRA_DEBUG_NHG_DETAIL)
		zlog_debug("%s: rt_nhe %p (%u)", __func__, rt_nhe, rt_nhe->id);

	zebra_nhe_find(&nhe, rt_nhe, NULL, rt_afi);

	if (IS_ZEBRA_DEBUG_NHG_DETAIL)
		zlog_debug("%s: => nhe %p (%u)",
			   __func__, nhe, nhe ? nhe->id : 0);

	return nhe;
}

/*
 * Allocate backup nexthop info object. Typically these are embedded in
 * nhg_hash_entry objects.
 */
struct nhg_backup_info *zebra_nhg_backup_alloc(void)
{
	struct nhg_backup_info *p;

	p = XCALLOC(MTYPE_NHG, sizeof(struct nhg_backup_info));

	p->nhe = zebra_nhg_alloc();

	/* Identify the embedded group used to hold the list of backups */
	SET_FLAG(p->nhe->flags, NEXTHOP_GROUP_BACKUP);

	return p;
}

/*
 * Free backup nexthop info object, deal with any embedded allocations
 */
void zebra_nhg_backup_free(struct nhg_backup_info **p)
{
	if (p && *p) {
		if ((*p)->nhe)
			zebra_nhg_free((*p)->nhe);

		XFREE(MTYPE_NHG, (*p));
	}
}

/* Accessor for backup nexthop group */
struct nexthop_group *zebra_nhg_get_backup_nhg(struct nhg_hash_entry *nhe)
{
	struct nexthop_group *p = NULL;

	if (nhe) {
		if (nhe->backup_info && nhe->backup_info->nhe)
			p = &(nhe->backup_info->nhe->nhg);
	}

	return p;
}

/*
 * Helper to return a copy of a backup_info - note that this is a shallow
 * copy, meant to be used when creating a new nhe from info passed in with
 * a route e.g.
 */
static struct nhg_backup_info *
nhg_backup_copy(const struct nhg_backup_info *orig)
{
	struct nhg_backup_info *b;

	b = zebra_nhg_backup_alloc();

	/* Copy list of nexthops */
	nexthop_group_copy(&(b->nhe->nhg), &(orig->nhe->nhg));

	return b;
}

static void zebra_nhg_free_members(struct nhg_hash_entry *nhe)
{
	nexthops_free(nhe->nhg.nexthop);

	zebra_nhg_backup_free(&nhe->backup_info);

	/* Decrement to remove connection ref */
	nhg_connected_tree_decrement_ref(&nhe->nhg_depends);
	nhg_connected_tree_free(&nhe->nhg_depends);
	nhg_connected_tree_free(&nhe->nhg_dependents);
}

void zebra_nhg_free(struct nhg_hash_entry *nhe)
{
	if (IS_ZEBRA_DEBUG_NHG_DETAIL) {
		/* Group or singleton? */
		if (nhe->nhg.nexthop && nhe->nhg.nexthop->next)
			zlog_debug("%s: nhe %p (%u), refcnt %d",
				   __func__, nhe, nhe->id, nhe->refcnt);
		else
			zlog_debug("%s: nhe %p (%u), refcnt %d, NH %pNHv",
				   __func__, nhe, nhe->id, nhe->refcnt,
				   nhe->nhg.nexthop);
	}

	if (nhe->refcnt)
		zlog_debug("nhe_id=%u hash refcnt=%d", nhe->id, nhe->refcnt);

	zebra_nhg_free_members(nhe);

	XFREE(MTYPE_NHG, nhe);
}

void zebra_nhg_hash_free(void *p)
{
	zebra_nhg_free((struct nhg_hash_entry *)p);
}

void zebra_nhg_decrement_ref(struct nhg_hash_entry *nhe)
{
	if (IS_ZEBRA_DEBUG_NHG_DETAIL)
		zlog_debug("%s: nhe %p (%u) %d => %d",
			   __func__, nhe, nhe->id, nhe->refcnt,
			   nhe->refcnt - 1);

	nhe->refcnt--;

	if (!zebra_nhg_depends_is_empty(nhe))
		nhg_connected_tree_decrement_ref(&nhe->nhg_depends);

	if (ZEBRA_NHG_CREATED(nhe) && nhe->refcnt <= 0)
		zebra_nhg_uninstall_kernel(nhe);
}

void zebra_nhg_increment_ref(struct nhg_hash_entry *nhe)
{
	if (IS_ZEBRA_DEBUG_NHG_DETAIL)
		zlog_debug("%s: nhe %p (%u) %d => %d",
			   __func__, nhe, nhe->id, nhe->refcnt,
			   nhe->refcnt + 1);

	nhe->refcnt++;

	if (!zebra_nhg_depends_is_empty(nhe))
		nhg_connected_tree_increment_ref(&nhe->nhg_depends);
}

static void nexthop_set_resolved(afi_t afi, const struct nexthop *newhop,
				 struct nexthop *nexthop)
{
	struct nexthop *resolved_hop;
	uint8_t num_labels = 0;
	mpls_label_t labels[MPLS_MAX_LABELS];
	enum lsp_types_t label_type = ZEBRA_LSP_NONE;
	int i = 0;

	resolved_hop = nexthop_new();
	SET_FLAG(resolved_hop->flags, NEXTHOP_FLAG_ACTIVE);

	resolved_hop->vrf_id = nexthop->vrf_id;
	switch (newhop->type) {
	case NEXTHOP_TYPE_IPV4:
	case NEXTHOP_TYPE_IPV4_IFINDEX:
		/* If the resolving route specifies a gateway, use it */
		resolved_hop->type = newhop->type;
		resolved_hop->gate.ipv4 = newhop->gate.ipv4;

		if (newhop->ifindex) {
			resolved_hop->type = NEXTHOP_TYPE_IPV4_IFINDEX;
			resolved_hop->ifindex = newhop->ifindex;
		}
		break;
	case NEXTHOP_TYPE_IPV6:
	case NEXTHOP_TYPE_IPV6_IFINDEX:
		resolved_hop->type = newhop->type;
		resolved_hop->gate.ipv6 = newhop->gate.ipv6;

		if (newhop->ifindex) {
			resolved_hop->type = NEXTHOP_TYPE_IPV6_IFINDEX;
			resolved_hop->ifindex = newhop->ifindex;
		}
		break;
	case NEXTHOP_TYPE_IFINDEX:
		/* If the resolving route is an interface route,
		 * it means the gateway we are looking up is connected
		 * to that interface. (The actual network is _not_ onlink).
		 * Therefore, the resolved route should have the original
		 * gateway as nexthop as it is directly connected.
		 *
		 * On Linux, we have to set the onlink netlink flag because
		 * otherwise, the kernel won't accept the route.
		 */
		resolved_hop->flags |= NEXTHOP_FLAG_ONLINK;
		if (afi == AFI_IP) {
			resolved_hop->type = NEXTHOP_TYPE_IPV4_IFINDEX;
			resolved_hop->gate.ipv4 = nexthop->gate.ipv4;
		} else if (afi == AFI_IP6) {
			resolved_hop->type = NEXTHOP_TYPE_IPV6_IFINDEX;
			resolved_hop->gate.ipv6 = nexthop->gate.ipv6;
		}
		resolved_hop->ifindex = newhop->ifindex;
		break;
	case NEXTHOP_TYPE_BLACKHOLE:
		resolved_hop->type = NEXTHOP_TYPE_BLACKHOLE;
		resolved_hop->bh_type = newhop->bh_type;
		break;
	}

	if (newhop->flags & NEXTHOP_FLAG_ONLINK)
		resolved_hop->flags |= NEXTHOP_FLAG_ONLINK;

	/* Copy labels of the resolved route and the parent resolving to it */
	if (newhop->nh_label) {
		for (i = 0; i < newhop->nh_label->num_labels; i++) {
			/* Be a bit picky about overrunning the local array */
			if (num_labels >= MPLS_MAX_LABELS) {
				if (IS_ZEBRA_DEBUG_NHG || IS_ZEBRA_DEBUG_RIB)
					zlog_debug("%s: too many labels in newhop %pNHv",
						   __func__, newhop);
				break;
			}
			labels[num_labels++] = newhop->nh_label->label[i];
		}
		/* Use the "outer" type */
		label_type = newhop->nh_label_type;
	}

	if (nexthop->nh_label) {
		for (i = 0; i < nexthop->nh_label->num_labels; i++) {
			/* Be a bit picky about overrunning the local array */
			if (num_labels >= MPLS_MAX_LABELS) {
				if (IS_ZEBRA_DEBUG_NHG || IS_ZEBRA_DEBUG_RIB)
					zlog_debug("%s: too many labels in nexthop %pNHv",
						   __func__, nexthop);
				break;
			}
			labels[num_labels++] = nexthop->nh_label->label[i];
		}

		/* If the parent has labels, use its type if
		 * we don't already have one.
		 */
		if (label_type == ZEBRA_LSP_NONE)
			label_type = nexthop->nh_label_type;
	}

	if (num_labels)
		nexthop_add_labels(resolved_hop, label_type, num_labels,
				   labels);

	resolved_hop->rparent = nexthop;
	_nexthop_add(&nexthop->resolved, resolved_hop);
}

/* Checks if nexthop we are trying to resolve to is valid */
static bool nexthop_valid_resolve(const struct nexthop *nexthop,
				  const struct nexthop *resolved)
{
	/* Can't resolve to a recursive nexthop */
	if (CHECK_FLAG(resolved->flags, NEXTHOP_FLAG_RECURSIVE))
		return false;

	/* Must be ACTIVE */
	if (!CHECK_FLAG(resolved->flags, NEXTHOP_FLAG_ACTIVE))
		return false;

	switch (nexthop->type) {
	case NEXTHOP_TYPE_IPV4_IFINDEX:
	case NEXTHOP_TYPE_IPV6_IFINDEX:
		/* If the nexthop we are resolving to does not match the
		 * ifindex for the nexthop the route wanted, its not valid.
		 */
		if (nexthop->ifindex != resolved->ifindex)
			return false;
		break;
	case NEXTHOP_TYPE_IPV4:
	case NEXTHOP_TYPE_IPV6:
	case NEXTHOP_TYPE_IFINDEX:
	case NEXTHOP_TYPE_BLACKHOLE:
		break;
	}

	return true;
}

/*
 * Given a nexthop we need to properly recursively resolve
 * the route.  As such, do a table lookup to find and match
 * if at all possible.  Set the nexthop->ifindex and resolved_id
 * as appropriate
 */
static int nexthop_active(afi_t afi, struct route_entry *re,
			  struct nexthop *nexthop, struct route_node *top)
{
	struct prefix p;
	struct route_table *table;
	struct route_node *rn;
	struct route_entry *match = NULL;
	int resolved;
	struct nexthop *newhop;
	struct interface *ifp;
	rib_dest_t *dest;
	struct zebra_vrf *zvrf;

	if ((nexthop->type == NEXTHOP_TYPE_IPV4)
	    || nexthop->type == NEXTHOP_TYPE_IPV6)
		nexthop->ifindex = 0;


	UNSET_FLAG(nexthop->flags, NEXTHOP_FLAG_RECURSIVE);
	nexthops_free(nexthop->resolved);
	nexthop->resolved = NULL;
	re->nexthop_mtu = 0;

	if (IS_ZEBRA_DEBUG_NHG_DETAIL)
		zlog_debug("%s: re %p, nexthop %pNHv",
			   __func__, re, nexthop);

	/*
	 * If the kernel has sent us a NEW route, then
	 * by golly gee whiz it's a good route.
	 *
	 * If its an already INSTALLED route we have already handled, then the
	 * kernel route's nexthop might have became unreachable
	 * and we have to handle that.
	 */
	if (!CHECK_FLAG(re->status, ROUTE_ENTRY_INSTALLED)
	    && (re->type == ZEBRA_ROUTE_KERNEL
		|| re->type == ZEBRA_ROUTE_SYSTEM))
		return 1;

	/*
	 * If the nexthop has been marked as 'onlink' we just need to make
	 * sure the nexthop's interface is known and is operational.
	 */
	if (CHECK_FLAG(nexthop->flags, NEXTHOP_FLAG_ONLINK)) {
		ifp = if_lookup_by_index(nexthop->ifindex, nexthop->vrf_id);
		if (!ifp) {
			if (IS_ZEBRA_DEBUG_NHG_DETAIL)
				zlog_debug("nexthop %pNHv marked onlink but nhif %u doesn't exist",
					   nexthop, nexthop->ifindex);
			return 0;
		}
		if (!if_is_operative(ifp)) {
			if (IS_ZEBRA_DEBUG_NHG_DETAIL)
				zlog_debug("nexthop %pNHv marked onlink but nhif %s is not operational",
					   nexthop, ifp->name);
			return 0;
		}
		return 1;
	}

	if ((top->p.family == AF_INET && top->p.prefixlen == 32
	     && nexthop->gate.ipv4.s_addr == top->p.u.prefix4.s_addr)
	    || (top->p.family == AF_INET6 && top->p.prefixlen == 128
		&& memcmp(&nexthop->gate.ipv6, &top->p.u.prefix6, 16) == 0)) {
		if (IS_ZEBRA_DEBUG_RIB_DETAILED)
			zlog_debug(
				"        :%s: Attempting to install a max prefixlength route through itself",
				__func__);
		return 0;
	}

	/* Make lookup prefix. */
	memset(&p, 0, sizeof(struct prefix));
	switch (afi) {
	case AFI_IP:
		p.family = AF_INET;
		p.prefixlen = IPV4_MAX_PREFIXLEN;
		p.u.prefix4 = nexthop->gate.ipv4;
		break;
	case AFI_IP6:
		p.family = AF_INET6;
		p.prefixlen = IPV6_MAX_PREFIXLEN;
		p.u.prefix6 = nexthop->gate.ipv6;
		break;
	default:
		assert(afi != AFI_IP && afi != AFI_IP6);
		break;
	}
	/* Lookup table.  */
	table = zebra_vrf_table(afi, SAFI_UNICAST, nexthop->vrf_id);
	/* get zvrf */
	zvrf = zebra_vrf_lookup_by_id(nexthop->vrf_id);
	if (!table || !zvrf) {
		if (IS_ZEBRA_DEBUG_RIB_DETAILED)
			zlog_debug("        %s: Table not found", __func__);
		return 0;
	}

	rn = route_node_match(table, (struct prefix *)&p);
	while (rn) {
		route_unlock_node(rn);

		/* Lookup should halt if we've matched against ourselves ('top',
		 * if specified) - i.e., we cannot have a nexthop NH1 is
		 * resolved by a route NH1. The exception is if the route is a
		 * host route.
		 */
		if (rn == top)
			if (((afi == AFI_IP) && (rn->p.prefixlen != 32))
			    || ((afi == AFI_IP6) && (rn->p.prefixlen != 128))) {
				if (IS_ZEBRA_DEBUG_RIB_DETAILED)
					zlog_debug(
						"        %s: Matched against ourself and prefix length is not max bit length",
						__func__);
				return 0;
			}

		/* Pick up selected route. */
		/* However, do not resolve over default route unless explicitly
		 * allowed.
		 */
		if (is_default_prefix(&rn->p)
		    && !rnh_resolve_via_default(zvrf, p.family)) {
			if (IS_ZEBRA_DEBUG_RIB_DETAILED)
				zlog_debug(
					"        :%s: Resolved against default route",
					__func__);
			return 0;
		}

		dest = rib_dest_from_rnode(rn);
		if (dest && dest->selected_fib
		    && !CHECK_FLAG(dest->selected_fib->status,
				   ROUTE_ENTRY_REMOVED)
		    && dest->selected_fib->type != ZEBRA_ROUTE_TABLE)
			match = dest->selected_fib;

		/* If there is no selected route or matched route is EGP, go up
		 * tree.
		 */
		if (!match) {
			do {
				rn = rn->parent;
			} while (rn && rn->info == NULL);
			if (rn)
				route_lock_node(rn);

			continue;
		}

		if (match->type == ZEBRA_ROUTE_CONNECT) {
			/* Directly point connected route. */
			newhop = match->nhe->nhg.nexthop;
			if (newhop) {
				if (nexthop->type == NEXTHOP_TYPE_IPV4
				    || nexthop->type == NEXTHOP_TYPE_IPV6)
					nexthop->ifindex = newhop->ifindex;
			}

			if (IS_ZEBRA_DEBUG_NHG_DETAIL)
				zlog_debug("%s: CONNECT match %p (%u), newhop %pNHv",
					   __func__, match,
					   match->nhe->id, newhop);

			return 1;
		} else if (CHECK_FLAG(re->flags, ZEBRA_FLAG_ALLOW_RECURSION)) {
			struct nexthop_group *nhg;

			resolved = 0;

			/* Examine installed nexthops */
			nhg = &match->nhe->nhg;
			for (ALL_NEXTHOPS_PTR(nhg, newhop)) {
				if (!CHECK_FLAG(match->status,
						ROUTE_ENTRY_INSTALLED))
					continue;
				if (!nexthop_valid_resolve(nexthop, newhop))
					continue;

				if (IS_ZEBRA_DEBUG_NHG_DETAIL)
					zlog_debug("%s: RECURSIVE match %p (%u), newhop %pNHv",
						   __func__, match,
						   match->nhe->id, newhop);

				SET_FLAG(nexthop->flags,
					 NEXTHOP_FLAG_RECURSIVE);
				nexthop_set_resolved(afi, newhop, nexthop);
				resolved = 1;
			}

			/* Examine installed backup nexthops, if any */
			nhg = zebra_nhg_get_backup_nhg(match->nhe);
			if (nhg == NULL)
				goto done_with_match;

			for (ALL_NEXTHOPS_PTR(nhg, newhop)) {
				if (!CHECK_FLAG(match->status,
						ROUTE_ENTRY_INSTALLED))
					continue;
				if (!nexthop_valid_resolve(nexthop, newhop))
					continue;

				if (IS_ZEBRA_DEBUG_NHG_DETAIL)
					zlog_debug("%s: RECURSIVE match backup %p (%u), newhop %pNHv",
						   __func__, match,
						   match->nhe->id, newhop);

				SET_FLAG(nexthop->flags,
					 NEXTHOP_FLAG_RECURSIVE);
				nexthop_set_resolved(afi, newhop, nexthop);
				resolved = 1;
			}
done_with_match:
			if (resolved)
				re->nexthop_mtu = match->mtu;
			else if (IS_ZEBRA_DEBUG_RIB_DETAILED)
				zlog_debug(
					"        %s: Recursion failed to find",
					__func__);

			return resolved;
		} else {
			if (IS_ZEBRA_DEBUG_RIB_DETAILED) {
				zlog_debug(
					"        %s: Route Type %s has not turned on recursion",
					__func__, zebra_route_string(re->type));
				if (re->type == ZEBRA_ROUTE_BGP
				    && !CHECK_FLAG(re->flags, ZEBRA_FLAG_IBGP))
					zlog_debug(
						"        EBGP: see \"disable-ebgp-connected-route-check\" or \"disable-connected-check\"");
			}
			return 0;
		}
	}
	if (IS_ZEBRA_DEBUG_RIB_DETAILED)
		zlog_debug("        %s: Nexthop did not lookup in table",
			   __func__);
	return 0;
}

/* This function verifies reachability of one given nexthop, which can be
 * numbered or unnumbered, IPv4 or IPv6. The result is unconditionally stored
 * in nexthop->flags field. The nexthop->ifindex will be updated
 * appropriately as well.  An existing route map can turn
 * (otherwise active) nexthop into inactive, but not vice versa.
 *
 * If it finds a nexthop recursivedly, set the resolved_id
 * to match that nexthop's nhg_hash_entry ID;
 *
 * The return value is the final value of 'ACTIVE' flag.
 */
static unsigned nexthop_active_check(struct route_node *rn,
				     struct route_entry *re,
				     struct nexthop *nexthop)
{
	struct interface *ifp;
	route_map_result_t ret = RMAP_PERMITMATCH;
	int family;
	char buf[SRCDEST2STR_BUFFER];
	const struct prefix *p, *src_p;
	struct zebra_vrf *zvrf;

	srcdest_rnode_prefixes(rn, &p, &src_p);

	if (rn->p.family == AF_INET)
		family = AFI_IP;
	else if (rn->p.family == AF_INET6)
		family = AFI_IP6;
	else
		family = 0;
	switch (nexthop->type) {
	case NEXTHOP_TYPE_IFINDEX:
		ifp = if_lookup_by_index(nexthop->ifindex, nexthop->vrf_id);
		/*
		 * If the interface exists and its operative or its a kernel
		 * route and interface is up, its active. We trust kernel routes
		 * to be good.
		 */
		if (ifp
		    && (if_is_operative(ifp)
			|| (if_is_up(ifp)
			    && (re->type == ZEBRA_ROUTE_KERNEL
				|| re->type == ZEBRA_ROUTE_SYSTEM))))
			SET_FLAG(nexthop->flags, NEXTHOP_FLAG_ACTIVE);
		else
			UNSET_FLAG(nexthop->flags, NEXTHOP_FLAG_ACTIVE);
		break;
	case NEXTHOP_TYPE_IPV4:
	case NEXTHOP_TYPE_IPV4_IFINDEX:
		family = AFI_IP;
		if (nexthop_active(AFI_IP, re, nexthop, rn))
			SET_FLAG(nexthop->flags, NEXTHOP_FLAG_ACTIVE);
		else
			UNSET_FLAG(nexthop->flags, NEXTHOP_FLAG_ACTIVE);
		break;
	case NEXTHOP_TYPE_IPV6:
		family = AFI_IP6;
		if (nexthop_active(AFI_IP6, re, nexthop, rn))
			SET_FLAG(nexthop->flags, NEXTHOP_FLAG_ACTIVE);
		else
			UNSET_FLAG(nexthop->flags, NEXTHOP_FLAG_ACTIVE);
		break;
	case NEXTHOP_TYPE_IPV6_IFINDEX:
		/* RFC 5549, v4 prefix with v6 NH */
		if (rn->p.family != AF_INET)
			family = AFI_IP6;
		if (IN6_IS_ADDR_LINKLOCAL(&nexthop->gate.ipv6)) {
			ifp = if_lookup_by_index(nexthop->ifindex,
						 nexthop->vrf_id);
			if (ifp && if_is_operative(ifp))
				SET_FLAG(nexthop->flags, NEXTHOP_FLAG_ACTIVE);
			else
				UNSET_FLAG(nexthop->flags, NEXTHOP_FLAG_ACTIVE);
		} else {
			if (nexthop_active(AFI_IP6, re, nexthop, rn))
				SET_FLAG(nexthop->flags, NEXTHOP_FLAG_ACTIVE);
			else
				UNSET_FLAG(nexthop->flags, NEXTHOP_FLAG_ACTIVE);
		}
		break;
	case NEXTHOP_TYPE_BLACKHOLE:
		SET_FLAG(nexthop->flags, NEXTHOP_FLAG_ACTIVE);
		break;
	default:
		break;
	}

	if (!CHECK_FLAG(nexthop->flags, NEXTHOP_FLAG_ACTIVE)) {
		if (IS_ZEBRA_DEBUG_RIB_DETAILED)
			zlog_debug("        %s: Unable to find active nexthop",
				   __func__);
		return 0;
	}

	/* XXX: What exactly do those checks do? Do we support
	 * e.g. IPv4 routes with IPv6 nexthops or vice versa?
	 */
	if (RIB_SYSTEM_ROUTE(re) || (family == AFI_IP && p->family != AF_INET)
	    || (family == AFI_IP6 && p->family != AF_INET6))
		return CHECK_FLAG(nexthop->flags, NEXTHOP_FLAG_ACTIVE);

	/* The original code didn't determine the family correctly
	 * e.g. for NEXTHOP_TYPE_IFINDEX. Retrieve the correct afi
	 * from the rib_table_info in those cases.
	 * Possibly it may be better to use only the rib_table_info
	 * in every case.
	 */
	if (!family) {
		struct rib_table_info *info;

		info = srcdest_rnode_table_info(rn);
		family = info->afi;
	}

	memset(&nexthop->rmap_src.ipv6, 0, sizeof(union g_addr));

	zvrf = zebra_vrf_lookup_by_id(nexthop->vrf_id);
	if (!zvrf) {
		if (IS_ZEBRA_DEBUG_RIB_DETAILED)
			zlog_debug("        %s: zvrf is NULL", __func__);
		return CHECK_FLAG(nexthop->flags, NEXTHOP_FLAG_ACTIVE);
	}

	/* It'll get set if required inside */
	ret = zebra_route_map_check(family, re->type, re->instance, p, nexthop,
				    zvrf, re->tag);
	if (ret == RMAP_DENYMATCH) {
		if (IS_ZEBRA_DEBUG_RIB) {
			srcdest_rnode2str(rn, buf, sizeof(buf));
			zlog_debug(
				"%u:%s: Filtering out with NH out %s due to route map",
				re->vrf_id, buf,
				ifindex2ifname(nexthop->ifindex,
					       nexthop->vrf_id));
		}
		UNSET_FLAG(nexthop->flags, NEXTHOP_FLAG_ACTIVE);
	}
	return CHECK_FLAG(nexthop->flags, NEXTHOP_FLAG_ACTIVE);
}

/* Helper function called after resolution to walk nhg rb trees
 * and toggle the NEXTHOP_GROUP_VALID flag if the nexthop
 * is active on singleton NHEs.
 */
static bool zebra_nhg_set_valid_if_active(struct nhg_hash_entry *nhe)
{
	struct nhg_connected *rb_node_dep = NULL;
	bool valid = false;

	if (!zebra_nhg_depends_is_empty(nhe)) {
		/* Is at least one depend valid? */
		frr_each(nhg_connected_tree, &nhe->nhg_depends, rb_node_dep) {
			if (zebra_nhg_set_valid_if_active(rb_node_dep->nhe))
				valid = true;
		}

		goto done;
	}

	/* should be fully resolved singleton at this point */
	if (CHECK_FLAG(nhe->nhg.nexthop->flags, NEXTHOP_FLAG_ACTIVE))
		valid = true;

done:
	if (valid)
		SET_FLAG(nhe->flags, NEXTHOP_GROUP_VALID);

	return valid;
}

/*
 * Process a list of nexthops, given an nhg, determining
 * whether each one is ACTIVE/installable at this time.
 */
static uint32_t nexthop_list_active_update(struct route_node *rn,
					   struct route_entry *re,
					   struct nexthop_group *nhg)
{
	union g_addr prev_src;
	unsigned int prev_active, new_active;
	ifindex_t prev_index;
	uint32_t counter = 0;
	struct nexthop *nexthop;

	nexthop = nhg->nexthop;

	/* Process nexthops one-by-one */
	for ( ; nexthop; nexthop = nexthop->next) {

		/* No protocol daemon provides src and so we're skipping
		 * tracking it
		 */
		prev_src = nexthop->rmap_src;
		prev_active = CHECK_FLAG(nexthop->flags, NEXTHOP_FLAG_ACTIVE);
		prev_index = nexthop->ifindex;
		/*
		 * We need to respect the multipath_num here
		 * as that what we should be able to install from
		 * a multipath perspective should not be a data plane
		 * decision point.
		 */
		new_active =
			nexthop_active_check(rn, re, nexthop);

		if (new_active && counter >= zrouter.multipath_num) {
			struct nexthop *nh;

			/* Set it and its resolved nexthop as inactive. */
			for (nh = nexthop; nh; nh = nh->resolved)
				UNSET_FLAG(nh->flags, NEXTHOP_FLAG_ACTIVE);

			new_active = 0;
		}

		if (new_active)
			counter++;

		/* Don't allow src setting on IPv6 addr for now */
		if (prev_active != new_active || prev_index != nexthop->ifindex
		    || ((nexthop->type >= NEXTHOP_TYPE_IFINDEX
			 && nexthop->type < NEXTHOP_TYPE_IPV6)
			&& prev_src.ipv4.s_addr
				   != nexthop->rmap_src.ipv4.s_addr)
		    || ((nexthop->type >= NEXTHOP_TYPE_IPV6
			 && nexthop->type < NEXTHOP_TYPE_BLACKHOLE)
			&& !(IPV6_ADDR_SAME(&prev_src.ipv6,
					    &nexthop->rmap_src.ipv6)))
		    || CHECK_FLAG(re->status, ROUTE_ENTRY_LABELS_CHANGED))
			SET_FLAG(re->status, ROUTE_ENTRY_CHANGED);
	}

	return counter;
}

/*
 * Iterate over all nexthops of the given RIB entry and refresh their
 * ACTIVE flag.  If any nexthop is found to toggle the ACTIVE flag,
 * the whole re structure is flagged with ROUTE_ENTRY_CHANGED.
 *
 * Return value is the new number of active nexthops.
 */
int nexthop_active_update(struct route_node *rn, struct route_entry *re)
{
	struct nhg_hash_entry *curr_nhe;
	uint32_t curr_active = 0, backup_active = 0;

	afi_t rt_afi = family2afi(rn->p.family);

	UNSET_FLAG(re->status, ROUTE_ENTRY_CHANGED);

	/* Make a local copy of the existing nhe, so we don't work on/modify
	 * the shared nhe.
	 */
	curr_nhe = zebra_nhe_copy(re->nhe, re->nhe->id);

	if (IS_ZEBRA_DEBUG_NHG_DETAIL)
		zlog_debug("%s: re %p nhe %p (%u), curr_nhe %p",
			   __func__, re, re->nhe, re->nhe->id,
			   curr_nhe);

	/* Clear the existing id, if any: this will avoid any confusion
	 * if the id exists, and will also force the creation
	 * of a new nhe reflecting the changes we may make in this local copy.
	 */
	curr_nhe->id = 0;

	/* Process nexthops */
	curr_active = nexthop_list_active_update(rn, re, &curr_nhe->nhg);

	if (IS_ZEBRA_DEBUG_NHG_DETAIL)
		zlog_debug("%s: re %p curr_active %u", __func__, re,
			   curr_active);

	/* If there are no backup nexthops, we are done */
	if (zebra_nhg_get_backup_nhg(curr_nhe) == NULL)
		goto backups_done;

	backup_active = nexthop_list_active_update(
		rn, re, zebra_nhg_get_backup_nhg(curr_nhe));

	if (IS_ZEBRA_DEBUG_NHG_DETAIL)
		zlog_debug("%s: re %p backup_active %u", __func__, re,
			   backup_active);

backups_done:

	/*
	 * Ref or create an nhe that matches the current state of the
	 * nexthop(s).
	 */
	if (CHECK_FLAG(re->status, ROUTE_ENTRY_CHANGED)) {
		struct nhg_hash_entry *new_nhe = NULL;

		new_nhe = zebra_nhg_rib_find_nhe(curr_nhe, rt_afi);

		if (IS_ZEBRA_DEBUG_NHG_DETAIL)
			zlog_debug("%s: re %p CHANGED: nhe %p (%u) => new_nhe %p (%u)",
				   __func__, re, re->nhe,
				   re->nhe->id, new_nhe, new_nhe->id);

		route_entry_update_nhe(re, new_nhe);
	}


	/* Walk the NHE depends tree and toggle NEXTHOP_GROUP_VALID
	 * flag where appropriate.
	 */
	if (curr_active)
		zebra_nhg_set_valid_if_active(re->nhe);

	/*
	 * Do not need the old / copied nhe anymore since it
	 * was either copied over into a new nhe or not
	 * used at all.
	 */
	zebra_nhg_free(curr_nhe);
	return curr_active;
}

/* Recursively construct a grp array of fully resolved IDs.
 *
 * This function allows us to account for groups within groups,
 * by converting them into a flat array of IDs.
 *
 * nh_grp is modified at every level of recursion to append
 * to it the next unique, fully resolved ID from the entire tree.
 *
 *
 * Note:
 * I'm pretty sure we only allow ONE level of group within group currently.
 * But making this recursive just in case that ever changes.
 */
static uint8_t zebra_nhg_nhe2grp_internal(struct nh_grp *grp,
					  uint8_t curr_index,
					  struct nhg_hash_entry *nhe,
					  int max_num)
{
	struct nhg_connected *rb_node_dep = NULL;
	struct nhg_hash_entry *depend = NULL;
	uint8_t i = curr_index;

	frr_each(nhg_connected_tree, &nhe->nhg_depends, rb_node_dep) {
		bool duplicate = false;

		if (i >= max_num)
			goto done;

		depend = rb_node_dep->nhe;

		/*
		 * If its recursive, use its resolved nhe in the group
		 */
		if (CHECK_FLAG(depend->flags, NEXTHOP_GROUP_RECURSIVE)) {
			depend = zebra_nhg_resolve(depend);
			if (!depend) {
				flog_err(
					EC_ZEBRA_NHG_FIB_UPDATE,
					"Failed to recursively resolve Nexthop Hash Entry in the group id=%u",
					nhe->id);
				continue;
			}
		}

		if (!zebra_nhg_depends_is_empty(depend)) {
			/* This is a group within a group */
			i = zebra_nhg_nhe2grp_internal(grp, i, depend, max_num);
		} else {
			if (!CHECK_FLAG(depend->flags, NEXTHOP_GROUP_VALID)) {
				if (IS_ZEBRA_DEBUG_RIB_DETAILED
				    || IS_ZEBRA_DEBUG_NHG)
					zlog_debug(
						"%s: Nexthop ID (%u) not valid, not appending to dataplane install group",
						__func__, depend->id);
				continue;
			}

			/* If the nexthop not installed/queued for install don't
			 * put in the ID array.
			 */
			if (!(CHECK_FLAG(depend->flags, NEXTHOP_GROUP_INSTALLED)
			      || CHECK_FLAG(depend->flags,
					    NEXTHOP_GROUP_QUEUED))) {
				if (IS_ZEBRA_DEBUG_RIB_DETAILED
				    || IS_ZEBRA_DEBUG_NHG)
					zlog_debug(
						"%s: Nexthop ID (%u) not installed or queued for install, not appending to dataplane install group",
						__func__, depend->id);
				continue;
			}

			/* Check for duplicate IDs, ignore if found. */
			for (int j = 0; j < i; j++) {
				if (depend->id == grp[j].id) {
					duplicate = true;
					break;
				}
			}

			if (duplicate) {
				if (IS_ZEBRA_DEBUG_RIB_DETAILED
				    || IS_ZEBRA_DEBUG_NHG)
					zlog_debug(
						"%s: Nexthop ID (%u) is duplicate, not appending to dataplane install group",
						__func__, depend->id);
				continue;
			}

			grp[i].id = depend->id;
			grp[i].weight = depend->nhg.nexthop->weight;
			i++;
		}
	}

	if (nhe->backup_info == NULL || nhe->backup_info->nhe == NULL)
		goto done;

	/* TODO -- For now, we are not trying to use or install any
	 * backup info in this nexthop-id path: we aren't prepared
	 * to use the backups here yet. We're just debugging what we find.
	 */
	if (IS_ZEBRA_DEBUG_NHG_DETAIL)
		zlog_debug("%s: skipping backup nhe",  __func__);

done:
	return i;
}

/* Convert a nhe into a group array */
uint8_t zebra_nhg_nhe2grp(struct nh_grp *grp, struct nhg_hash_entry *nhe,
			  int max_num)
{
	/* Call into the recursive function */
	return zebra_nhg_nhe2grp_internal(grp, 0, nhe, max_num);
}

void zebra_nhg_install_kernel(struct nhg_hash_entry *nhe)
{
	struct nhg_connected *rb_node_dep = NULL;

	/* Resolve it first */
	nhe = zebra_nhg_resolve(nhe);

	/* Make sure all depends are installed/queued */
	frr_each(nhg_connected_tree, &nhe->nhg_depends, rb_node_dep) {
		zebra_nhg_install_kernel(rb_node_dep->nhe);
	}

	if (CHECK_FLAG(nhe->flags, NEXTHOP_GROUP_VALID)
	    && !CHECK_FLAG(nhe->flags, NEXTHOP_GROUP_INSTALLED)
	    && !CHECK_FLAG(nhe->flags, NEXTHOP_GROUP_QUEUED)) {
		/* Change its type to us since we are installing it */
		nhe->type = ZEBRA_ROUTE_NHG;

		int ret = dplane_nexthop_add(nhe);

		switch (ret) {
		case ZEBRA_DPLANE_REQUEST_QUEUED:
			SET_FLAG(nhe->flags, NEXTHOP_GROUP_QUEUED);
			break;
		case ZEBRA_DPLANE_REQUEST_FAILURE:
			flog_err(
				EC_ZEBRA_DP_INSTALL_FAIL,
				"Failed to install Nexthop ID (%u) into the kernel",
				nhe->id);
			break;
		case ZEBRA_DPLANE_REQUEST_SUCCESS:
			SET_FLAG(nhe->flags, NEXTHOP_GROUP_INSTALLED);
			zebra_nhg_handle_install(nhe);
			break;
		}
	}
}

void zebra_nhg_uninstall_kernel(struct nhg_hash_entry *nhe)
{
	if (CHECK_FLAG(nhe->flags, NEXTHOP_GROUP_INSTALLED)) {
		int ret = dplane_nexthop_delete(nhe);

		switch (ret) {
		case ZEBRA_DPLANE_REQUEST_QUEUED:
			SET_FLAG(nhe->flags, NEXTHOP_GROUP_QUEUED);
			break;
		case ZEBRA_DPLANE_REQUEST_FAILURE:
			flog_err(
				EC_ZEBRA_DP_DELETE_FAIL,
				"Failed to uninstall Nexthop ID (%u) from the kernel",
				nhe->id);
			break;
		case ZEBRA_DPLANE_REQUEST_SUCCESS:
			UNSET_FLAG(nhe->flags, NEXTHOP_GROUP_INSTALLED);
			break;
		}
	}

	zebra_nhg_handle_uninstall(nhe);
}

void zebra_nhg_dplane_result(struct zebra_dplane_ctx *ctx)
{
	enum dplane_op_e op;
	enum zebra_dplane_result status;
	uint32_t id = 0;
	struct nhg_hash_entry *nhe = NULL;

	op = dplane_ctx_get_op(ctx);
	status = dplane_ctx_get_status(ctx);

	id = dplane_ctx_get_nhe_id(ctx);

	if (IS_ZEBRA_DEBUG_DPLANE_DETAIL || IS_ZEBRA_DEBUG_NHG_DETAIL)
		zlog_debug(
			"Nexthop dplane ctx %p, op %s, nexthop ID (%u), result %s",
			ctx, dplane_op2str(op), id, dplane_res2str(status));

	switch (op) {
	case DPLANE_OP_NH_DELETE:
		if (status != ZEBRA_DPLANE_REQUEST_SUCCESS)
			flog_err(
				EC_ZEBRA_DP_DELETE_FAIL,
				"Failed to uninstall Nexthop ID (%u) from the kernel",
				id);
		/* We already free'd the data, nothing to do */
		break;
	case DPLANE_OP_NH_INSTALL:
	case DPLANE_OP_NH_UPDATE:
		nhe = zebra_nhg_lookup_id(id);

		if (!nhe) {
			flog_err(
				EC_ZEBRA_NHG_SYNC,
				"%s operation preformed on Nexthop ID (%u) in the kernel, that we no longer have in our table",
				dplane_op2str(op), id);
			break;
		}

		UNSET_FLAG(nhe->flags, NEXTHOP_GROUP_QUEUED);
		if (status == ZEBRA_DPLANE_REQUEST_SUCCESS) {
			SET_FLAG(nhe->flags, NEXTHOP_GROUP_VALID);
			SET_FLAG(nhe->flags, NEXTHOP_GROUP_INSTALLED);
			zebra_nhg_handle_install(nhe);
		} else
			flog_err(
				EC_ZEBRA_DP_INSTALL_FAIL,
				"Failed to install Nexthop ID (%u) into the kernel",
				nhe->id);
		break;
	case DPLANE_OP_ROUTE_INSTALL:
	case DPLANE_OP_ROUTE_UPDATE:
	case DPLANE_OP_ROUTE_DELETE:
	case DPLANE_OP_ROUTE_NOTIFY:
	case DPLANE_OP_LSP_INSTALL:
	case DPLANE_OP_LSP_UPDATE:
	case DPLANE_OP_LSP_DELETE:
	case DPLANE_OP_LSP_NOTIFY:
	case DPLANE_OP_PW_INSTALL:
	case DPLANE_OP_PW_UNINSTALL:
	case DPLANE_OP_SYS_ROUTE_ADD:
	case DPLANE_OP_SYS_ROUTE_DELETE:
	case DPLANE_OP_ADDR_INSTALL:
	case DPLANE_OP_ADDR_UNINSTALL:
	case DPLANE_OP_MAC_INSTALL:
	case DPLANE_OP_MAC_DELETE:
	case DPLANE_OP_NEIGH_INSTALL:
	case DPLANE_OP_NEIGH_UPDATE:
	case DPLANE_OP_NEIGH_DELETE:
	case DPLANE_OP_VTEP_ADD:
	case DPLANE_OP_VTEP_DELETE:
	case DPLANE_OP_RULE_ADD:
	case DPLANE_OP_RULE_DELETE:
	case DPLANE_OP_RULE_UPDATE:
	case DPLANE_OP_NONE:
		break;
	}

	dplane_ctx_fini(&ctx);
}

static void zebra_nhg_sweep_entry(struct hash_bucket *bucket, void *arg)
{
	struct nhg_hash_entry *nhe = NULL;

	nhe = (struct nhg_hash_entry *)bucket->data;

	/* If its being ref'd, just let it be uninstalled via a route removal */
	if (ZEBRA_NHG_CREATED(nhe) && nhe->refcnt <= 0)
		zebra_nhg_uninstall_kernel(nhe);
}

void zebra_nhg_sweep_table(struct hash *hash)
{
	hash_iterate(hash, zebra_nhg_sweep_entry, NULL);
}

/* Global control to disable use of kernel nexthops, if available. We can't
 * force the kernel to support nexthop ids, of course, but we can disable
 * zebra's use of them, for testing e.g. By default, if the kernel supports
 * nexthop ids, zebra uses them.
 */
void zebra_nhg_enable_kernel_nexthops(bool set)
{
	g_nexthops_enabled = set;
}

bool zebra_nhg_kernel_nexthops_enabled(void)
{
	return g_nexthops_enabled;
}