[mirror_frr.git] / lib / nexthop.c

/* A generic nexthop structure
 * Copyright (C) 2013 Cumulus Networks, Inc.
 *
 * This file is part of Quagga.
 *
 * Quagga 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.
 *
 * Quagga 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 this program; see the file COPYING; if not, write to the Free Software
 * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
 */
#include <zebra.h>

#include "prefix.h"
#include "table.h"
#include "memory.h"
#include "command.h"
#include "if.h"
#include "log.h"
#include "sockunion.h"
#include "linklist.h"
#include "thread.h"
#include "prefix.h"
#include "nexthop.h"
#include "mpls.h"
#include "jhash.h"

DEFINE_MTYPE_STATIC(LIB, NEXTHOP, "Nexthop")
DEFINE_MTYPE_STATIC(LIB, NH_LABEL, "Nexthop label")

static int nexthop_labels_cmp(const struct nexthop *nh1,
			      const struct nexthop *nh2)
{
	const struct mpls_label_stack *nhl1 = NULL;
	const struct mpls_label_stack *nhl2 = NULL;

	nhl1 = nh1->nh_label;
	nhl2 = nh2->nh_label;

	/* No labels is a match */
	if (!nhl1 && !nhl2)
		return 0;

	if (nhl1 && !nhl2)
		return 1;

	if (nhl2 && !nhl1)
		return -1;

	if (nhl1->num_labels > nhl2->num_labels)
		return 1;

	if (nhl1->num_labels < nhl2->num_labels)
		return -1;

	return memcmp(nhl1->label, nhl2->label, nhl1->num_labels);
}

int nexthop_cmp(const struct nexthop *next1, const struct nexthop *next2)
{
	int ret;
	uint32_t n1, n2;

	if (next1->vrf_id < next2->vrf_id)
		return -1;

	if (next1->vrf_id > next2->vrf_id)
		return 1;

	if (next1->type < next2->type)
		return -1;

	if (next1->type > next2->type)
		return 1;

	switch(next1->type) {
	case NEXTHOP_TYPE_IPV4:
		n1 = ntohl(next1->gate.ipv4.s_addr);
		n2 = ntohl(next2->gate.ipv4.s_addr);
		if (n1 < n2)
			return -1;
		if (n1 > n2)
			return 1;
		break;
	case NEXTHOP_TYPE_IPV6:
		ret = memcmp(&next1->gate, &next2->gate, sizeof(union g_addr));
		if (!ret)
			return ret;
		break;
	case NEXTHOP_TYPE_IPV4_IFINDEX:
	case NEXTHOP_TYPE_IPV6_IFINDEX:
		ret = memcmp(&next1->gate, &next2->gate, sizeof(union g_addr));
		if (!ret)
			return ret;
		/* Intentional Fall-Through */
	case NEXTHOP_TYPE_IFINDEX:
		if (next1->ifindex < next2->ifindex)
			return -1;

		if (next1->ifindex > next2->ifindex)
			return 1;
		break;
	case NEXTHOP_TYPE_BLACKHOLE:
		if (next1->bh_type < next2->bh_type)
			return -1;

		if (next1->bh_type > next2->bh_type)
			return 1;
		break;
	}

	ret = memcmp(&next1->src, &next2->src, sizeof(union g_addr));
	return ret;
}

/* check if nexthops are same, non-recursive */
int nexthop_same_no_recurse(const struct nexthop *next1,
			    const struct nexthop *next2)
{
	if (next1->type != next2->type)
		return 0;

	switch (next1->type) {
	case NEXTHOP_TYPE_IPV4:
	case NEXTHOP_TYPE_IPV4_IFINDEX:
		if (!IPV4_ADDR_SAME(&next1->gate.ipv4, &next2->gate.ipv4))
			return 0;
		if (next1->ifindex && (next1->ifindex != next2->ifindex))
			return 0;
		break;
	case NEXTHOP_TYPE_IFINDEX:
		if (next1->ifindex != next2->ifindex)
			return 0;
		break;
	case NEXTHOP_TYPE_IPV6:
		if (!IPV6_ADDR_SAME(&next1->gate.ipv6, &next2->gate.ipv6))
			return 0;
		break;
	case NEXTHOP_TYPE_IPV6_IFINDEX:
		if (!IPV6_ADDR_SAME(&next1->gate.ipv6, &next2->gate.ipv6))
			return 0;
		if (next1->ifindex != next2->ifindex)
			return 0;
		break;
	default:
		/* do nothing */
		break;
	}
	return 1;
}

int nexthop_same_firsthop(struct nexthop *next1, struct nexthop *next2)
{
	int type1 = NEXTHOP_FIRSTHOPTYPE(next1->type);
	int type2 = NEXTHOP_FIRSTHOPTYPE(next2->type);

	if (type1 != type2)
		return 0;
	switch (type1) {
	case NEXTHOP_TYPE_IPV4_IFINDEX:
		if (!IPV4_ADDR_SAME(&next1->gate.ipv4, &next2->gate.ipv4))
			return 0;
		if (next1->ifindex != next2->ifindex)
			return 0;
		break;
	case NEXTHOP_TYPE_IFINDEX:
		if (next1->ifindex != next2->ifindex)
			return 0;
		break;
	case NEXTHOP_TYPE_IPV6_IFINDEX:
		if (!IPV6_ADDR_SAME(&next1->gate.ipv6, &next2->gate.ipv6))
			return 0;
		if (next1->ifindex != next2->ifindex)
			return 0;
		break;
	default:
		/* do nothing */
		break;
	}
	return 1;
}

/*
 * nexthop_type_to_str
 */
const char *nexthop_type_to_str(enum nexthop_types_t nh_type)
{
	static const char *desc[] = {
		"none",		 "Directly connected",
		"IPv4 nexthop",  "IPv4 nexthop with ifindex",
		"IPv6 nexthop",  "IPv6 nexthop with ifindex",
		"Null0 nexthop",
	};

	return desc[nh_type];
}

/*
 * Check if the labels match for the 2 nexthops specified.
 */
int nexthop_labels_match(const struct nexthop *nh1, const struct nexthop *nh2)
{
	const struct mpls_label_stack *nhl1, *nhl2;

	nhl1 = nh1->nh_label;
	nhl2 = nh2->nh_label;

	/* No labels is a match */
	if (!nhl1 && !nhl2)
		return 1;

	if (!nhl1 || !nhl2)
		return 0;

	if (nhl1->num_labels != nhl2->num_labels)
		return 0;

	if (memcmp(nhl1->label, nhl2->label, nhl1->num_labels))
		return 0;

	return 1;
}

struct nexthop *nexthop_new(void)
{
	return XCALLOC(MTYPE_NEXTHOP, sizeof(struct nexthop));
}

/* Free nexthop. */
void nexthop_free(struct nexthop *nexthop)
{
	nexthop_del_labels(nexthop);
	if (nexthop->resolved)
		nexthops_free(nexthop->resolved);
	XFREE(MTYPE_NEXTHOP, nexthop);
}

/* Frees a list of nexthops */
void nexthops_free(struct nexthop *nexthop)
{
	struct nexthop *nh, *next;

	for (nh = nexthop; nh; nh = next) {
		next = nh->next;
		nexthop_free(nh);
	}
}

bool nexthop_same(const struct nexthop *nh1, const struct nexthop *nh2)
{
	if (nh1 && !nh2)
		return false;

	if (!nh1 && nh2)
		return false;

	if (nh1 == nh2)
		return true;

	if (nh1->vrf_id != nh2->vrf_id)
		return false;

	if (nh1->type != nh2->type)
		return false;

	switch (nh1->type) {
	case NEXTHOP_TYPE_IFINDEX:
		if (nh1->ifindex != nh2->ifindex)
			return false;
		break;
	case NEXTHOP_TYPE_IPV4:
		if (nh1->gate.ipv4.s_addr != nh2->gate.ipv4.s_addr)
			return false;
		break;
	case NEXTHOP_TYPE_IPV4_IFINDEX:
		if (nh1->gate.ipv4.s_addr != nh2->gate.ipv4.s_addr)
			return false;
		if (nh1->ifindex != nh2->ifindex)
			return false;
		break;
	case NEXTHOP_TYPE_IPV6:
		if (memcmp(&nh1->gate.ipv6, &nh2->gate.ipv6, 16))
			return false;
		break;
	case NEXTHOP_TYPE_IPV6_IFINDEX:
		if (memcmp(&nh1->gate.ipv6, &nh2->gate.ipv6, 16))
			return false;
		if (nh1->ifindex != nh2->ifindex)
			return false;
		break;
	case NEXTHOP_TYPE_BLACKHOLE:
		if (nh1->bh_type != nh2->bh_type)
			return false;
		break;
	}

	/* Compare labels too (if present) */
	return (!!nexthop_labels_match(nh1, nh2));
}

/* Update nexthop with label information. */
void nexthop_add_labels(struct nexthop *nexthop, enum lsp_types_t type,
			uint8_t num_labels, mpls_label_t *label)
{
	struct mpls_label_stack *nh_label;
	int i;

	nexthop->nh_label_type = type;
	nh_label = XCALLOC(MTYPE_NH_LABEL,
			   sizeof(struct mpls_label_stack)
				   + num_labels * sizeof(mpls_label_t));
	nh_label->num_labels = num_labels;
	for (i = 0; i < num_labels; i++)
		nh_label->label[i] = *(label + i);
	nexthop->nh_label = nh_label;
}

/* Free label information of nexthop, if present. */
void nexthop_del_labels(struct nexthop *nexthop)
{
	if (nexthop->nh_label) {
		XFREE(MTYPE_NH_LABEL, nexthop->nh_label);
		nexthop->nh_label_type = ZEBRA_LSP_NONE;
	}
}

const char *nexthop2str(const struct nexthop *nexthop, char *str, int size)
{
	switch (nexthop->type) {
	case NEXTHOP_TYPE_IFINDEX:
		snprintf(str, size, "if %u", nexthop->ifindex);
		break;
	case NEXTHOP_TYPE_IPV4:
	case NEXTHOP_TYPE_IPV4_IFINDEX:
		snprintf(str, size, "%s if %u", inet_ntoa(nexthop->gate.ipv4),
			 nexthop->ifindex);
		break;
	case NEXTHOP_TYPE_IPV6:
	case NEXTHOP_TYPE_IPV6_IFINDEX:
		snprintf(str, size, "%s if %u", inet6_ntoa(nexthop->gate.ipv6),
			 nexthop->ifindex);
		break;
	case NEXTHOP_TYPE_BLACKHOLE:
		snprintf(str, size, "blackhole");
		break;
	default:
		snprintf(str, size, "unknown");
		break;
	}

	return str;
}

/*
 * Iteration step for ALL_NEXTHOPS macro:
 * This is the tricky part. Check if `nexthop' has
 * NEXTHOP_FLAG_RECURSIVE set. If yes, this implies that `nexthop' has
 * at least one nexthop attached to `nexthop->resolved', which will be
 * the next one.
 *
 * If NEXTHOP_FLAG_RECURSIVE is not set, `nexthop' will progress in its
 * current chain. In case its current chain end is reached, it will move
 * upwards in the recursion levels and progress there. Whenever a step
 * forward in a chain is done, recursion will be checked again.
 * In a nustshell, it's equivalent to a pre-traversal order assuming that
 * left branch is 'resolved' and right branch is 'next':
 * https://en.wikipedia.org/wiki/Tree_traversal#/media/File:Sorted_binary_tree_preorder.svg
 */
struct nexthop *nexthop_next(struct nexthop *nexthop)
{
	if (CHECK_FLAG(nexthop->flags, NEXTHOP_FLAG_RECURSIVE))
		return nexthop->resolved;

	if (nexthop->next)
		return nexthop->next;

	for (struct nexthop *par = nexthop->rparent; par; par = par->rparent)
		if (par->next)
			return par->next;

	return NULL;
}

unsigned int nexthop_level(struct nexthop *nexthop)
{
	unsigned int rv = 0;

	for (struct nexthop *par = nexthop->rparent; par; par = par->rparent)
		rv++;

	return rv;
}

uint32_t nexthop_hash(const struct nexthop *nexthop)
{
	uint32_t key = 0x45afe398;

	key = jhash_3words(nexthop->type, nexthop->vrf_id,
			   nexthop->nh_label_type, key);
	/* gate and blackhole are together in a union */
	key = jhash(&nexthop->gate, sizeof(nexthop->gate), key);
	key = jhash(&nexthop->src, sizeof(nexthop->src), key);
	key = jhash(&nexthop->rmap_src, sizeof(nexthop->rmap_src), key);

	if (nexthop->nh_label) {
		int labels = nexthop->nh_label->num_labels;
		int i = 0;

		while (labels >= 3) {
			key = jhash_3words(nexthop->nh_label->label[i],
					   nexthop->nh_label->label[i + 1],
					   nexthop->nh_label->label[i + 2],
					   key);
			labels -= 3;
			i += 3;
		}

		if (labels >= 2) {
			key = jhash_2words(nexthop->nh_label->label[i],
					   nexthop->nh_label->label[i + 1],
					   key);
			labels -= 2;
			i += 2;
		}

		if (labels >= 1)
			key = jhash_1word(nexthop->nh_label->label[i], key);
	}

	switch (nexthop->type) {
	case NEXTHOP_TYPE_IPV4_IFINDEX:
	case NEXTHOP_TYPE_IPV6_IFINDEX:
	case NEXTHOP_TYPE_IFINDEX:
		key = jhash_1word(nexthop->ifindex, key);
		break;
	case NEXTHOP_TYPE_BLACKHOLE:
	case NEXTHOP_TYPE_IPV4:
	case NEXTHOP_TYPE_IPV6:
		break;
	}
	return key;
}
Commit	Line	Data
fb018d25 DS	1	/* A generic nexthop structure
	2	* Copyright (C) 2013 Cumulus Networks, Inc.
	3	*
a399694f	4	* This file is part of Quagga.
fb018d25	5	*
a399694f	6	* Quagga is free software; you can redistribute it and/or modify it
fb018d25 DS	7	* under the terms of the GNU General Public License as published by the
	8	* Free Software Foundation; either version 2, or (at your option) any
	9	* later version.
	10	*
a399694f	11	* Quagga is distributed in the hope that it will be useful, but
fb018d25 DS	12	* WITHOUT ANY WARRANTY; without even the implied warranty of
	13	* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
	14	* General Public License for more details.
	15	*
896014f4 DL	16	* You should have received a copy of the GNU General Public License along
	17	* with this program; see the file COPYING; if not, write to the Free Software
	18	* Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
fb018d25 DS	19	*/
	20	#include <zebra.h>
	21
	22	#include "prefix.h"
	23	#include "table.h"
	24	#include "memory.h"
fb018d25 DS	25	#include "command.h"
	26	#include "if.h"
	27	#include "log.h"
	28	#include "sockunion.h"
	29	#include "linklist.h"
	30	#include "thread.h"
	31	#include "prefix.h"
	32	#include "nexthop.h"
40c7bdb0	33	#include "mpls.h"
d36d0d57	34	#include "jhash.h"
fb018d25	35
d62a17ae	36	DEFINE_MTYPE_STATIC(LIB, NEXTHOP, "Nexthop")
d62a17ae	37	DEFINE_MTYPE_STATIC(LIB, NH_LABEL, "Nexthop label")
4a1ab8e4	38
ebc403dd SW	39	static int nexthop_labels_cmp(const struct nexthop *nh1,
	40	const struct nexthop *nh2)
	41	{
	42	const struct mpls_label_stack *nhl1 = NULL;
	43	const struct mpls_label_stack *nhl2 = NULL;
	44
	45	nhl1 = nh1->nh_label;
	46	nhl2 = nh2->nh_label;
	47
	48	/* No labels is a match */
	49	if (!nhl1 && !nhl2)
	50	return 0;
	51
	52	if (nhl1 && !nhl2)
	53	return 1;
	54
	55	if (nhl2 && !nhl1)
	56	return -1;
	57
	58	if (nhl1->num_labels > nhl2->num_labels)
	59	return 1;
	60
	61	if (nhl1->num_labels < nhl2->num_labels)
	62	return -1;
	63
	64	return memcmp(nhl1->label, nhl2->label, nhl1->num_labels);
	65	}
	66
776c3e90 DS	67	int nexthop_cmp(const struct nexthop next1, const struct nexthop next2)
	68	{
	69	int ret;
	70	uint32_t n1, n2;
	71
	72	if (next1->vrf_id < next2->vrf_id)
	73	return -1;
	74
	75	if (next1->vrf_id > next2->vrf_id)
	76	return 1;
	77
	78	if (next1->type < next2->type)
	79	return -1;
	80
	81	if (next1->type > next2->type)
	82	return 1;
	83
	84	switch(next1->type) {
	85	case NEXTHOP_TYPE_IPV4:
	86	n1 = ntohl(next1->gate.ipv4.s_addr);
	87	n2 = ntohl(next2->gate.ipv4.s_addr);
	88	if (n1 < n2)
	89	return -1;
	90	if (n1 > n2)
	91	return 1;
	92	break;
	93	case NEXTHOP_TYPE_IPV6:
	94	ret = memcmp(&next1->gate, &next2->gate, sizeof(union g_addr));
	95	if (!ret)
	96	return ret;
	97	break;
	98	case NEXTHOP_TYPE_IPV4_IFINDEX:
	99	case NEXTHOP_TYPE_IPV6_IFINDEX:
	100	ret = memcmp(&next1->gate, &next2->gate, sizeof(union g_addr));
	101	if (!ret)
	102	return ret;
	103	/* Intentional Fall-Through */
	104	case NEXTHOP_TYPE_IFINDEX:
	105	if (next1->ifindex < next2->ifindex)
	106	return -1;
	107
	108	if (next1->ifindex > next2->ifindex)
	109	return 1;
	110	break;
	111	case NEXTHOP_TYPE_BLACKHOLE:
	112	if (next1->bh_type < next2->bh_type)
	113	return -1;
	114
	115	if (next1->bh_type > next2->bh_type)
	116	return 1;
	117	break;
	118	}
	119
	120	ret = memcmp(&next1->src, &next2->src, sizeof(union g_addr));
	121	return ret;
	122	}
	123
fb018d25	124	/* check if nexthops are same, non-recursive */
fd36be7e DL	125	int nexthop_same_no_recurse(const struct nexthop *next1,
fd36be7e DL	126	const struct nexthop *next2)
fb018d25	127	{
d62a17ae	128	if (next1->type != next2->type)
	129	return 0;
	130
	131	switch (next1->type) {
	132	case NEXTHOP_TYPE_IPV4:
	133	case NEXTHOP_TYPE_IPV4_IFINDEX:
	134	if (!IPV4_ADDR_SAME(&next1->gate.ipv4, &next2->gate.ipv4))
	135	return 0;
	136	if (next1->ifindex && (next1->ifindex != next2->ifindex))
	137	return 0;
	138	break;
	139	case NEXTHOP_TYPE_IFINDEX:
	140	if (next1->ifindex != next2->ifindex)
	141	return 0;
	142	break;
	143	case NEXTHOP_TYPE_IPV6:
	144	if (!IPV6_ADDR_SAME(&next1->gate.ipv6, &next2->gate.ipv6))
	145	return 0;
	146	break;
	147	case NEXTHOP_TYPE_IPV6_IFINDEX:
	148	if (!IPV6_ADDR_SAME(&next1->gate.ipv6, &next2->gate.ipv6))
	149	return 0;
	150	if (next1->ifindex != next2->ifindex)
	151	return 0;
25b9cb0c DL	152	break;
	153	default:
	154	/* do nothing */
	155	break;
	156	}
	157	return 1;
	158	}
	159
996c9314	160	int nexthop_same_firsthop(struct nexthop next1, struct nexthop next2)
25b9cb0c DL	161	{
	162	int type1 = NEXTHOP_FIRSTHOPTYPE(next1->type);
	163	int type2 = NEXTHOP_FIRSTHOPTYPE(next2->type);
	164
	165	if (type1 != type2)
	166	return 0;
996c9314	167	switch (type1) {
25b9cb0c	168	case NEXTHOP_TYPE_IPV4_IFINDEX:
996c9314	169	if (!IPV4_ADDR_SAME(&next1->gate.ipv4, &next2->gate.ipv4))
25b9cb0c DL	170	return 0;
	171	if (next1->ifindex != next2->ifindex)
	172	return 0;
	173	break;
	174	case NEXTHOP_TYPE_IFINDEX:
	175	if (next1->ifindex != next2->ifindex)
	176	return 0;
	177	break;
	178	case NEXTHOP_TYPE_IPV6_IFINDEX:
996c9314	179	if (!IPV6_ADDR_SAME(&next1->gate.ipv6, &next2->gate.ipv6))
25b9cb0c DL	180	return 0;
	181	if (next1->ifindex != next2->ifindex)
	182	return 0;
d62a17ae	183	break;
	184	default:
	185	/* do nothing */
	186	break;
	187	}
	188	return 1;
fb018d25 DS	189	}
	190
	191	/*
	192	* nexthop_type_to_str
	193	*/
d62a17ae	194	const char *nexthop_type_to_str(enum nexthop_types_t nh_type)
fb018d25	195	{
d62a17ae	196	static const char *desc[] = {
	197	"none", "Directly connected",
	198	"IPv4 nexthop", "IPv4 nexthop with ifindex",
	199	"IPv6 nexthop", "IPv6 nexthop with ifindex",
	200	"Null0 nexthop",
	201	};
	202
	203	return desc[nh_type];
fb018d25	204	}
a399694f	205
a64448ba DS	206	/*
	207	* Check if the labels match for the 2 nexthops specified.
	208	*/
55f93d4b	209	int nexthop_labels_match(const struct nexthop nh1, const struct nexthop nh2)
a64448ba	210	{
55f93d4b	211	const struct mpls_label_stack nhl1, nhl2;
a64448ba	212
d62a17ae	213	nhl1 = nh1->nh_label;
d62a17ae	214	nhl2 = nh2->nh_label;
55f93d4b MS	215
	216	/* No labels is a match */
	217	if (!nhl1 && !nhl2)
	218	return 1;
	219
3f58e1b3	220	if (!nhl1 \|\| !nhl2)
d62a17ae	221	return 0;
a64448ba	222
d62a17ae	223	if (nhl1->num_labels != nhl2->num_labels)
d62a17ae	224	return 0;
a64448ba	225
d62a17ae	226	if (memcmp(nhl1->label, nhl2->label, nhl1->num_labels))
d62a17ae	227	return 0;
a64448ba	228
d62a17ae	229	return 1;
a64448ba DS	230	}
a64448ba DS	231
d62a17ae	232	struct nexthop *nexthop_new(void)
a399694f	233	{
d62a17ae	234	return XCALLOC(MTYPE_NEXTHOP, sizeof(struct nexthop));
a399694f DS	235	}
a399694f DS	236
a399694f	237	/* Free nexthop. */
d62a17ae	238	void nexthop_free(struct nexthop *nexthop)
a399694f	239	{
d62a17ae	240	nexthop_del_labels(nexthop);
	241	if (nexthop->resolved)
	242	nexthops_free(nexthop->resolved);
	243	XFREE(MTYPE_NEXTHOP, nexthop);
a399694f DS	244	}
	245
	246	/* Frees a list of nexthops */
d62a17ae	247	void nexthops_free(struct nexthop *nexthop)
a399694f	248	{
d62a17ae	249	struct nexthop nh, next;
a399694f	250
d62a17ae	251	for (nh = nexthop; nh; nh = next) {
	252	next = nh->next;
	253	nexthop_free(nh);
	254	}
a399694f	255	}
80c2442a	256
31919191 DS	257	bool nexthop_same(const struct nexthop nh1, const struct nexthop nh2)
	258	{
	259	if (nh1 && !nh2)
	260	return false;
	261
	262	if (!nh1 && nh2)
	263	return false;
	264
	265	if (nh1 == nh2)
	266	return true;
	267
	268	if (nh1->vrf_id != nh2->vrf_id)
	269	return false;
	270
	271	if (nh1->type != nh2->type)
	272	return false;
	273
	274	switch (nh1->type) {
	275	case NEXTHOP_TYPE_IFINDEX:
	276	if (nh1->ifindex != nh2->ifindex)
	277	return false;
	278	break;
	279	case NEXTHOP_TYPE_IPV4:
	280	if (nh1->gate.ipv4.s_addr != nh2->gate.ipv4.s_addr)
	281	return false;
	282	break;
	283	case NEXTHOP_TYPE_IPV4_IFINDEX:
	284	if (nh1->gate.ipv4.s_addr != nh2->gate.ipv4.s_addr)
	285	return false;
	286	if (nh1->ifindex != nh2->ifindex)
	287	return false;
	288	break;
	289	case NEXTHOP_TYPE_IPV6:
	290	if (memcmp(&nh1->gate.ipv6, &nh2->gate.ipv6, 16))
	291	return false;
	292	break;
	293	case NEXTHOP_TYPE_IPV6_IFINDEX:
	294	if (memcmp(&nh1->gate.ipv6, &nh2->gate.ipv6, 16))
	295	return false;
	296	if (nh1->ifindex != nh2->ifindex)
	297	return false;
	298	break;
	299	case NEXTHOP_TYPE_BLACKHOLE:
	300	if (nh1->bh_type != nh2->bh_type)
	301	return false;
	302	break;
	303	}
	304
55f93d4b MS	305	/* Compare labels too (if present) */
55f93d4b MS	306	return (!!nexthop_labels_match(nh1, nh2));
31919191 DS	307	}
31919191 DS	308
40c7bdb0	309	/* Update nexthop with label information. */
d62a17ae	310	void nexthop_add_labels(struct nexthop *nexthop, enum lsp_types_t type,
d7c0a89a	311	uint8_t num_labels, mpls_label_t *label)
40c7bdb0	312	{
8ecdb26e	313	struct mpls_label_stack *nh_label;
d62a17ae	314	int i;
	315
	316	nexthop->nh_label_type = type;
	317	nh_label = XCALLOC(MTYPE_NH_LABEL,
8ecdb26e	318	sizeof(struct mpls_label_stack)
d62a17ae	319	+ num_labels * sizeof(mpls_label_t));
	320	nh_label->num_labels = num_labels;
	321	for (i = 0; i < num_labels; i++)
	322	nh_label->label[i] = *(label + i);
	323	nexthop->nh_label = nh_label;
40c7bdb0	324	}
	325
	326	/* Free label information of nexthop, if present. */
d62a17ae	327	void nexthop_del_labels(struct nexthop *nexthop)
40c7bdb0	328	{
d62a17ae	329	if (nexthop->nh_label) {
	330	XFREE(MTYPE_NH_LABEL, nexthop->nh_label);
	331	nexthop->nh_label_type = ZEBRA_LSP_NONE;
	332	}
40c7bdb0	333	}
40c7bdb0	334
d36d0d57	335	const char nexthop2str(const struct nexthop nexthop, char *str, int size)
80c2442a	336	{
d62a17ae	337	switch (nexthop->type) {
	338	case NEXTHOP_TYPE_IFINDEX:
	339	snprintf(str, size, "if %u", nexthop->ifindex);
	340	break;
	341	case NEXTHOP_TYPE_IPV4:
d62a17ae	342	case NEXTHOP_TYPE_IPV4_IFINDEX:
	343	snprintf(str, size, "%s if %u", inet_ntoa(nexthop->gate.ipv4),
	344	nexthop->ifindex);
	345	break;
	346	case NEXTHOP_TYPE_IPV6:
d62a17ae	347	case NEXTHOP_TYPE_IPV6_IFINDEX:
	348	snprintf(str, size, "%s if %u", inet6_ntoa(nexthop->gate.ipv6),
	349	nexthop->ifindex);
	350	break;
	351	case NEXTHOP_TYPE_BLACKHOLE:
	352	snprintf(str, size, "blackhole");
	353	break;
	354	default:
	355	snprintf(str, size, "unknown");
	356	break;
	357	}
	358
	359	return str;
80c2442a	360	}
9fb47c05 CF	361
	362	/*
	363	* Iteration step for ALL_NEXTHOPS macro:
	364	* This is the tricky part. Check if `nexthop' has
	365	* NEXTHOP_FLAG_RECURSIVE set. If yes, this implies that `nexthop' has
	366	* at least one nexthop attached to `nexthop->resolved', which will be
	367	* the next one.
	368	*
	369	* If NEXTHOP_FLAG_RECURSIVE is not set, `nexthop' will progress in its
	370	* current chain. In case its current chain end is reached, it will move
	371	* upwards in the recursion levels and progress there. Whenever a step
	372	* forward in a chain is done, recursion will be checked again.
	373	* In a nustshell, it's equivalent to a pre-traversal order assuming that
	374	* left branch is 'resolved' and right branch is 'next':
	375	* https://en.wikipedia.org/wiki/Tree_traversal#/media/File:Sorted_binary_tree_preorder.svg
	376	*/
d62a17ae	377	struct nexthop nexthop_next(struct nexthop nexthop)
9fb47c05	378	{
d62a17ae	379	if (CHECK_FLAG(nexthop->flags, NEXTHOP_FLAG_RECURSIVE))
d62a17ae	380	return nexthop->resolved;
9fb47c05	381
d62a17ae	382	if (nexthop->next)
d62a17ae	383	return nexthop->next;
9fb47c05	384
d62a17ae	385	for (struct nexthop *par = nexthop->rparent; par; par = par->rparent)
	386	if (par->next)
	387	return par->next;
9fb47c05	388
d62a17ae	389	return NULL;
9fb47c05	390	}
e3054ee9	391
d62a17ae	392	unsigned int nexthop_level(struct nexthop *nexthop)
e3054ee9	393	{
d62a17ae	394	unsigned int rv = 0;
e3054ee9	395
d62a17ae	396	for (struct nexthop *par = nexthop->rparent; par; par = par->rparent)
d62a17ae	397	rv++;
e3054ee9	398
d62a17ae	399	return rv;
e3054ee9	400	}
d36d0d57	401
1b1fe1c4	402	uint32_t nexthop_hash(const struct nexthop *nexthop)
d36d0d57	403	{
1b1fe1c4	404	uint32_t key = 0x45afe398;
d36d0d57	405
1b1fe1c4 SW	406	key = jhash_3words(nexthop->type, nexthop->vrf_id,
	407	nexthop->nh_label_type, key);
	408	/* gate and blackhole are together in a union */
	409	key = jhash(&nexthop->gate, sizeof(nexthop->gate), key);
	410	key = jhash(&nexthop->src, sizeof(nexthop->src), key);
	411	key = jhash(&nexthop->rmap_src, sizeof(nexthop->rmap_src), key);
d36d0d57	412
1b1fe1c4 SW	413	if (nexthop->nh_label) {
	414	int labels = nexthop->nh_label->num_labels;
	415	int i = 0;
	416
	417	while (labels >= 3) {
	418	key = jhash_3words(nexthop->nh_label->label[i],
	419	nexthop->nh_label->label[i + 1],
	420	nexthop->nh_label->label[i + 2],
	421	key);
	422	labels -= 3;
	423	i += 3;
	424	}
	425
	426	if (labels >= 2) {
	427	key = jhash_2words(nexthop->nh_label->label[i],
	428	nexthop->nh_label->label[i + 1],
	429	key);
	430	labels -= 2;
	431	i += 2;
	432	}
	433
	434	if (labels >= 1)
	435	key = jhash_1word(nexthop->nh_label->label[i], key);
	436	}
	437
	438	switch (nexthop->type) {
	439	case NEXTHOP_TYPE_IPV4_IFINDEX:
	440	case NEXTHOP_TYPE_IPV6_IFINDEX:
	441	case NEXTHOP_TYPE_IFINDEX:
	442	key = jhash_1word(nexthop->ifindex, key);
	443	break;
	444	case NEXTHOP_TYPE_BLACKHOLE:
	445	case NEXTHOP_TYPE_IPV4:
	446	case NEXTHOP_TYPE_IPV6:
	447	break;
	448	}
d36d0d57 QY	449	return key;
d36d0d57 QY	450	}