[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"
#include "printfrr.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_g_addr_cmp(enum nexthop_types_t type, const union g_addr *addr1,
		       const union g_addr *addr2)
{
	int ret = 0;

	switch (type) {
	case NEXTHOP_TYPE_IPV4:
	case NEXTHOP_TYPE_IPV4_IFINDEX:
		ret = IPV4_ADDR_CMP(&addr1->ipv4, &addr2->ipv4);
		break;
	case NEXTHOP_TYPE_IPV6:
	case NEXTHOP_TYPE_IPV6_IFINDEX:
		ret = IPV6_ADDR_CMP(&addr1->ipv6, &addr2->ipv6);
		break;
	case NEXTHOP_TYPE_IFINDEX:
	case NEXTHOP_TYPE_BLACKHOLE:
		/* No addr here */
		break;
	}

	return ret;
}

static int _nexthop_gateway_cmp(const struct nexthop *nh1,
				const struct nexthop *nh2)
{
	return nexthop_g_addr_cmp(nh1->type, &nh1->gate, &nh2->gate);
}

static int _nexthop_source_cmp(const struct nexthop *nh1,
			       const struct nexthop *nh2)
{
	return nexthop_g_addr_cmp(nh1->type, &nh1->src, &nh2->src);
}

static int _nexthop_cmp_no_labels(const struct nexthop *next1,
				  const struct nexthop *next2)
{
	int ret = 0;

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

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

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

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

	switch (next1->type) {
	case NEXTHOP_TYPE_IPV4:
	case NEXTHOP_TYPE_IPV6:
		ret = _nexthop_gateway_cmp(next1, next2);
		if (ret != 0)
			return ret;
		break;
	case NEXTHOP_TYPE_IPV4_IFINDEX:
	case NEXTHOP_TYPE_IPV6_IFINDEX:
		ret = _nexthop_gateway_cmp(next1, next2);
		if (ret != 0)
			return ret;
		/* Intentional Fall-Through */
	case NEXTHOP_TYPE_IFINDEX:
		if (next1->ifindex < next2->ifindex)
			return -1;

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

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

	ret = _nexthop_source_cmp(next1, next2);

	return ret;
}

int nexthop_cmp(const struct nexthop *next1, const struct nexthop *next2)
{
	int ret = 0;

	ret = _nexthop_cmp_no_labels(next1, next2);
	if (ret != 0)
		return ret;

	ret = _nexthop_labels_cmp(next1, next2);

	return ret;
}

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.
 */
bool nexthop_labels_match(const struct nexthop *nh1, const struct nexthop *nh2)
{
	if (_nexthop_labels_cmp(nh1, nh2) != 0)
		return false;

	return true;
}

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 (nexthop_cmp(nh1, nh2) != 0)
		return false;

	return true;
}

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

	if (!nh1 && nh2)
		return false;

	if (nh1 == nh2)
		return true;

	if (_nexthop_cmp_no_labels(nh1, nh2) != 0)
		return false;

	return true;
}

/* 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;
}

#define GATE_SIZE 4 /* Number of uint32_t words in struct g_addr */

uint32_t nexthop_hash(const struct nexthop *nexthop)
{

	uint32_t key = 0x45afe398;
	uint32_t gate_src_rmap_raw[GATE_SIZE * 3] = {};

	key = jhash_3words(nexthop->type, nexthop->vrf_id,
			   nexthop->nh_label_type, key);

	assert(((sizeof(nexthop->gate) + sizeof(nexthop->src)
		 + sizeof(nexthop->rmap_src))
		/ 3)
	       == (GATE_SIZE * sizeof(uint32_t)));

	memcpy(gate_src_rmap_raw, &nexthop->gate, GATE_SIZE);
	memcpy(gate_src_rmap_raw + GATE_SIZE, &nexthop->src, GATE_SIZE);
	memcpy(gate_src_rmap_raw + (2 * GATE_SIZE), &nexthop->rmap_src,
	       GATE_SIZE);

	key = jhash2(gate_src_rmap_raw, (GATE_SIZE * 3), 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;
	}

	key = jhash_1word(CHECK_FLAG(nexthop->flags, NEXTHOP_FLAG_ONLINK), key);

	return key;
}

void nexthop_copy(struct nexthop *copy, const struct nexthop *nexthop,
		  struct nexthop *rparent)
{
	copy->vrf_id = nexthop->vrf_id;
	copy->ifindex = nexthop->ifindex;
	copy->type = nexthop->type;
	copy->flags = nexthop->flags;
	memcpy(&copy->gate, &nexthop->gate, sizeof(nexthop->gate));
	memcpy(&copy->src, &nexthop->src, sizeof(nexthop->src));
	memcpy(&copy->rmap_src, &nexthop->rmap_src, sizeof(nexthop->rmap_src));
	copy->rparent = rparent;
	if (nexthop->nh_label)
		nexthop_add_labels(copy, nexthop->nh_label_type,
				   nexthop->nh_label->num_labels,
				   &nexthop->nh_label->label[0]);
}

struct nexthop *nexthop_dup(const struct nexthop *nexthop,
			    struct nexthop *rparent)
{
	struct nexthop *new = nexthop_new();

	nexthop_copy(new, nexthop, rparent);
	return new;
}

/*
 * nexthop printing variants:
 *	%pNHvv
 *		via 1.2.3.4
 *		via 1.2.3.4, eth0
 *		is directly connected, eth0
 *		unreachable (blackhole)
 *	%pNHv
 *		1.2.3.4
 *		1.2.3.4, via eth0
 *		directly connected, eth0
 *		unreachable (blackhole)
 *	%pNHs
 *		nexthop2str()
 */
printfrr_ext_autoreg_p("NH", printfrr_nh)
static ssize_t printfrr_nh(char *buf, size_t bsz, const char *fmt,
			   int prec, const void *ptr)
{
	const struct nexthop *nexthop = ptr;
	struct fbuf fb = { .buf = buf, .pos = buf, .len = bsz - 1 };
	bool do_ifi = false;
	const char *s, *v_is = "", *v_via = "", *v_viaif = "via ";
	ssize_t ret = 3;

	switch (fmt[2]) {
	case 'v':
		if (fmt[3] == 'v') {
			v_is = "is ";
			v_via = "via ";
			v_viaif = "";
			ret++;
		}

		switch (nexthop->type) {
		case NEXTHOP_TYPE_IPV4:
		case NEXTHOP_TYPE_IPV4_IFINDEX:
			bprintfrr(&fb, "%s%pI4", v_via, &nexthop->gate.ipv4);
			do_ifi = true;
			break;
		case NEXTHOP_TYPE_IPV6:
		case NEXTHOP_TYPE_IPV6_IFINDEX:
			bprintfrr(&fb, "%s%pI6", v_via, &nexthop->gate.ipv6);
			do_ifi = true;
			break;
		case NEXTHOP_TYPE_IFINDEX:
			bprintfrr(&fb, "%sdirectly connected, %s", v_is,
				ifindex2ifname(nexthop->ifindex,
					       nexthop->vrf_id));
			break;
		case NEXTHOP_TYPE_BLACKHOLE:
			switch (nexthop->bh_type) {
			case BLACKHOLE_REJECT:
				s = " (ICMP unreachable)";
				break;
			case BLACKHOLE_ADMINPROHIB:
				s = " (ICMP admin-prohibited)";
				break;
			case BLACKHOLE_NULL:
				s = " (blackhole)";
				break;
			default:
				s = "";
				break;
			}
			bprintfrr(&fb, "unreachable%s", s);
			break;
		default:
			break;
		}
		if (do_ifi && nexthop->ifindex)
			bprintfrr(&fb, ", %s%s", v_viaif, ifindex2ifname(
					nexthop->ifindex,
					nexthop->vrf_id));

		*fb.pos = '\0';
		return ret;
	case 's':
		nexthop2str(nexthop, buf, bsz);
		return 3;
	}
	return 0;
}
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"
d52ec572	35	#include "printfrr.h"
fb018d25	36
d62a17ae	37	DEFINE_MTYPE_STATIC(LIB, NEXTHOP, "Nexthop")
d62a17ae	38	DEFINE_MTYPE_STATIC(LIB, NH_LABEL, "Nexthop label")
4a1ab8e4	39
a5a2d802 SW	40	static int _nexthop_labels_cmp(const struct nexthop *nh1,
a5a2d802 SW	41	const struct nexthop *nh2)
ebc403dd SW	42	{
	43	const struct mpls_label_stack *nhl1 = NULL;
	44	const struct mpls_label_stack *nhl2 = NULL;
	45
	46	nhl1 = nh1->nh_label;
	47	nhl2 = nh2->nh_label;
	48
	49	/* No labels is a match */
	50	if (!nhl1 && !nhl2)
	51	return 0;
	52
	53	if (nhl1 && !nhl2)
	54	return 1;
	55
	56	if (nhl2 && !nhl1)
	57	return -1;
	58
	59	if (nhl1->num_labels > nhl2->num_labels)
	60	return 1;
	61
	62	if (nhl1->num_labels < nhl2->num_labels)
	63	return -1;
	64
	65	return memcmp(nhl1->label, nhl2->label, nhl1->num_labels);
	66	}
	67
3c6e0bd4 SW	68	int nexthop_g_addr_cmp(enum nexthop_types_t type, const union g_addr *addr1,
3c6e0bd4 SW	69	const union g_addr *addr2)
24cfec84 SW	70	{
	71	int ret = 0;
	72
	73	switch (type) {
	74	case NEXTHOP_TYPE_IPV4:
	75	case NEXTHOP_TYPE_IPV4_IFINDEX:
	76	ret = IPV4_ADDR_CMP(&addr1->ipv4, &addr2->ipv4);
	77	break;
	78	case NEXTHOP_TYPE_IPV6:
	79	case NEXTHOP_TYPE_IPV6_IFINDEX:
	80	ret = IPV6_ADDR_CMP(&addr1->ipv6, &addr2->ipv6);
	81	break;
	82	case NEXTHOP_TYPE_IFINDEX:
	83	case NEXTHOP_TYPE_BLACKHOLE:
	84	/* No addr here */
	85	break;
	86	}
	87
	88	return ret;
	89	}
	90
a5a2d802 SW	91	static int _nexthop_gateway_cmp(const struct nexthop *nh1,
a5a2d802 SW	92	const struct nexthop *nh2)
24cfec84	93	{
3c6e0bd4	94	return nexthop_g_addr_cmp(nh1->type, &nh1->gate, &nh2->gate);
24cfec84 SW	95	}
24cfec84 SW	96
a5a2d802 SW	97	static int _nexthop_source_cmp(const struct nexthop *nh1,
a5a2d802 SW	98	const struct nexthop *nh2)
24cfec84	99	{
3c6e0bd4	100	return nexthop_g_addr_cmp(nh1->type, &nh1->src, &nh2->src);
24cfec84 SW	101	}
24cfec84 SW	102
a5a2d802 SW	103	static int _nexthop_cmp_no_labels(const struct nexthop *next1,
a5a2d802 SW	104	const struct nexthop *next2)
776c3e90	105	{
ff0e16da	106	int ret = 0;
776c3e90 DS	107
	108	if (next1->vrf_id < next2->vrf_id)
	109	return -1;
	110
	111	if (next1->vrf_id > next2->vrf_id)
	112	return 1;
	113
	114	if (next1->type < next2->type)
	115	return -1;
	116
	117	if (next1->type > next2->type)
	118	return 1;
	119
ff0e16da	120	switch (next1->type) {
776c3e90	121	case NEXTHOP_TYPE_IPV4:
776c3e90	122	case NEXTHOP_TYPE_IPV6:
a5a2d802 SW	123	ret = _nexthop_gateway_cmp(next1, next2);
a5a2d802 SW	124	if (ret != 0)
776c3e90 DS	125	return ret;
	126	break;
	127	case NEXTHOP_TYPE_IPV4_IFINDEX:
	128	case NEXTHOP_TYPE_IPV6_IFINDEX:
a5a2d802 SW	129	ret = _nexthop_gateway_cmp(next1, next2);
a5a2d802 SW	130	if (ret != 0)
776c3e90 DS	131	return ret;
	132	/* Intentional Fall-Through */
	133	case NEXTHOP_TYPE_IFINDEX:
	134	if (next1->ifindex < next2->ifindex)
	135	return -1;
	136
	137	if (next1->ifindex > next2->ifindex)
	138	return 1;
	139	break;
	140	case NEXTHOP_TYPE_BLACKHOLE:
	141	if (next1->bh_type < next2->bh_type)
	142	return -1;
	143
	144	if (next1->bh_type > next2->bh_type)
	145	return 1;
	146	break;
	147	}
	148
a5a2d802 SW	149	ret = _nexthop_source_cmp(next1, next2);
	150
	151	return ret;
	152	}
	153
	154	int nexthop_cmp(const struct nexthop next1, const struct nexthop next2)
	155	{
	156	int ret = 0;
	157
	158	ret = _nexthop_cmp_no_labels(next1, next2);
	159	if (ret != 0)
ff0e16da SW	160	return ret;
ff0e16da SW	161
a5a2d802 SW	162	ret = _nexthop_labels_cmp(next1, next2);
a5a2d802 SW	163
776c3e90 DS	164	return ret;
	165	}
	166
996c9314	167	int nexthop_same_firsthop(struct nexthop next1, struct nexthop next2)
25b9cb0c DL	168	{
	169	int type1 = NEXTHOP_FIRSTHOPTYPE(next1->type);
	170	int type2 = NEXTHOP_FIRSTHOPTYPE(next2->type);
	171
	172	if (type1 != type2)
	173	return 0;
996c9314	174	switch (type1) {
25b9cb0c	175	case NEXTHOP_TYPE_IPV4_IFINDEX:
996c9314	176	if (!IPV4_ADDR_SAME(&next1->gate.ipv4, &next2->gate.ipv4))
25b9cb0c DL	177	return 0;
	178	if (next1->ifindex != next2->ifindex)
	179	return 0;
	180	break;
	181	case NEXTHOP_TYPE_IFINDEX:
	182	if (next1->ifindex != next2->ifindex)
	183	return 0;
	184	break;
	185	case NEXTHOP_TYPE_IPV6_IFINDEX:
996c9314	186	if (!IPV6_ADDR_SAME(&next1->gate.ipv6, &next2->gate.ipv6))
25b9cb0c DL	187	return 0;
	188	if (next1->ifindex != next2->ifindex)
	189	return 0;
d62a17ae	190	break;
	191	default:
	192	/* do nothing */
	193	break;
	194	}
	195	return 1;
fb018d25 DS	196	}
	197
	198	/*
	199	* nexthop_type_to_str
	200	*/
d62a17ae	201	const char *nexthop_type_to_str(enum nexthop_types_t nh_type)
fb018d25	202	{
d62a17ae	203	static const char *desc[] = {
	204	"none", "Directly connected",
	205	"IPv4 nexthop", "IPv4 nexthop with ifindex",
	206	"IPv6 nexthop", "IPv6 nexthop with ifindex",
	207	"Null0 nexthop",
	208	};
	209
	210	return desc[nh_type];
fb018d25	211	}
a399694f	212
a64448ba DS	213	/*
	214	* Check if the labels match for the 2 nexthops specified.
	215	*/
89dc3160	216	bool nexthop_labels_match(const struct nexthop nh1, const struct nexthop nh2)
a64448ba	217	{
a5a2d802	218	if (_nexthop_labels_cmp(nh1, nh2) != 0)
89dc3160	219	return false;
a64448ba	220
89dc3160	221	return true;
a64448ba DS	222	}
a64448ba DS	223
d62a17ae	224	struct nexthop *nexthop_new(void)
a399694f	225	{
d62a17ae	226	return XCALLOC(MTYPE_NEXTHOP, sizeof(struct nexthop));
a399694f DS	227	}
a399694f DS	228
a399694f	229	/* Free nexthop. */
d62a17ae	230	void nexthop_free(struct nexthop *nexthop)
a399694f	231	{
d62a17ae	232	nexthop_del_labels(nexthop);
	233	if (nexthop->resolved)
	234	nexthops_free(nexthop->resolved);
	235	XFREE(MTYPE_NEXTHOP, nexthop);
a399694f DS	236	}
	237
	238	/* Frees a list of nexthops */
d62a17ae	239	void nexthops_free(struct nexthop *nexthop)
a399694f	240	{
d62a17ae	241	struct nexthop nh, next;
a399694f	242
d62a17ae	243	for (nh = nexthop; nh; nh = next) {
	244	next = nh->next;
	245	nexthop_free(nh);
	246	}
a399694f	247	}
80c2442a	248
31919191 DS	249	bool nexthop_same(const struct nexthop nh1, const struct nexthop nh2)
	250	{
	251	if (nh1 && !nh2)
	252	return false;
	253
	254	if (!nh1 && nh2)
	255	return false;
	256
	257	if (nh1 == nh2)
	258	return true;
	259
2ed74b93	260	if (nexthop_cmp(nh1, nh2) != 0)
31919191 DS	261	return false;
31919191 DS	262
2ed74b93	263	return true;
31919191 DS	264	}
31919191 DS	265
a5a2d802 SW	266	bool nexthop_same_no_labels(const struct nexthop *nh1,
	267	const struct nexthop *nh2)
	268	{
	269	if (nh1 && !nh2)
	270	return false;
	271
	272	if (!nh1 && nh2)
	273	return false;
	274
	275	if (nh1 == nh2)
	276	return true;
	277
	278	if (_nexthop_cmp_no_labels(nh1, nh2) != 0)
	279	return false;
	280
	281	return true;
	282	}
	283
40c7bdb0	284	/* Update nexthop with label information. */
d62a17ae	285	void nexthop_add_labels(struct nexthop *nexthop, enum lsp_types_t type,
d7c0a89a	286	uint8_t num_labels, mpls_label_t *label)
40c7bdb0	287	{
8ecdb26e	288	struct mpls_label_stack *nh_label;
d62a17ae	289	int i;
	290
	291	nexthop->nh_label_type = type;
	292	nh_label = XCALLOC(MTYPE_NH_LABEL,
8ecdb26e	293	sizeof(struct mpls_label_stack)
d62a17ae	294	+ num_labels * sizeof(mpls_label_t));
	295	nh_label->num_labels = num_labels;
	296	for (i = 0; i < num_labels; i++)
	297	nh_label->label[i] = *(label + i);
	298	nexthop->nh_label = nh_label;
40c7bdb0	299	}
	300
	301	/* Free label information of nexthop, if present. */
d62a17ae	302	void nexthop_del_labels(struct nexthop *nexthop)
40c7bdb0	303	{
d62a17ae	304	if (nexthop->nh_label) {
	305	XFREE(MTYPE_NH_LABEL, nexthop->nh_label);
	306	nexthop->nh_label_type = ZEBRA_LSP_NONE;
	307	}
40c7bdb0	308	}
40c7bdb0	309
d36d0d57	310	const char nexthop2str(const struct nexthop nexthop, char *str, int size)
80c2442a	311	{
d62a17ae	312	switch (nexthop->type) {
	313	case NEXTHOP_TYPE_IFINDEX:
	314	snprintf(str, size, "if %u", nexthop->ifindex);
	315	break;
	316	case NEXTHOP_TYPE_IPV4:
d62a17ae	317	case NEXTHOP_TYPE_IPV4_IFINDEX:
	318	snprintf(str, size, "%s if %u", inet_ntoa(nexthop->gate.ipv4),
	319	nexthop->ifindex);
	320	break;
	321	case NEXTHOP_TYPE_IPV6:
d62a17ae	322	case NEXTHOP_TYPE_IPV6_IFINDEX:
	323	snprintf(str, size, "%s if %u", inet6_ntoa(nexthop->gate.ipv6),
	324	nexthop->ifindex);
	325	break;
	326	case NEXTHOP_TYPE_BLACKHOLE:
	327	snprintf(str, size, "blackhole");
	328	break;
	329	default:
	330	snprintf(str, size, "unknown");
	331	break;
	332	}
	333
	334	return str;
80c2442a	335	}
9fb47c05 CF	336
	337	/*
	338	* Iteration step for ALL_NEXTHOPS macro:
	339	* This is the tricky part. Check if `nexthop' has
	340	* NEXTHOP_FLAG_RECURSIVE set. If yes, this implies that `nexthop' has
	341	* at least one nexthop attached to `nexthop->resolved', which will be
	342	* the next one.
	343	*
	344	* If NEXTHOP_FLAG_RECURSIVE is not set, `nexthop' will progress in its
	345	* current chain. In case its current chain end is reached, it will move
	346	* upwards in the recursion levels and progress there. Whenever a step
	347	* forward in a chain is done, recursion will be checked again.
	348	* In a nustshell, it's equivalent to a pre-traversal order assuming that
	349	* left branch is 'resolved' and right branch is 'next':
	350	* https://en.wikipedia.org/wiki/Tree_traversal#/media/File:Sorted_binary_tree_preorder.svg
	351	*/
d62a17ae	352	struct nexthop nexthop_next(struct nexthop nexthop)
9fb47c05	353	{
d62a17ae	354	if (CHECK_FLAG(nexthop->flags, NEXTHOP_FLAG_RECURSIVE))
d62a17ae	355	return nexthop->resolved;
9fb47c05	356
d62a17ae	357	if (nexthop->next)
d62a17ae	358	return nexthop->next;
9fb47c05	359
d62a17ae	360	for (struct nexthop *par = nexthop->rparent; par; par = par->rparent)
	361	if (par->next)
	362	return par->next;
9fb47c05	363
d62a17ae	364	return NULL;
9fb47c05	365	}
e3054ee9	366
d62a17ae	367	unsigned int nexthop_level(struct nexthop *nexthop)
e3054ee9	368	{
d62a17ae	369	unsigned int rv = 0;
e3054ee9	370
d62a17ae	371	for (struct nexthop *par = nexthop->rparent; par; par = par->rparent)
d62a17ae	372	rv++;
e3054ee9	373
d62a17ae	374	return rv;
e3054ee9	375	}
d36d0d57	376
a15e669c SW	377	#define GATE_SIZE 4 /* Number of uint32_t words in struct g_addr */
a15e669c SW	378
1b1fe1c4	379	uint32_t nexthop_hash(const struct nexthop *nexthop)
d36d0d57	380	{
a15e669c	381
1b1fe1c4	382	uint32_t key = 0x45afe398;
a15e669c	383	uint32_t gate_src_rmap_raw[GATE_SIZE * 3] = {};
d36d0d57	384
1b1fe1c4 SW	385	key = jhash_3words(nexthop->type, nexthop->vrf_id,
1b1fe1c4 SW	386	nexthop->nh_label_type, key);
a15e669c SW	387
	388	assert(((sizeof(nexthop->gate) + sizeof(nexthop->src)
	389	+ sizeof(nexthop->rmap_src))
	390	/ 3)
	391	== (GATE_SIZE * sizeof(uint32_t)));
	392
	393	memcpy(gate_src_rmap_raw, &nexthop->gate, GATE_SIZE);
	394	memcpy(gate_src_rmap_raw + GATE_SIZE, &nexthop->src, GATE_SIZE);
	395	memcpy(gate_src_rmap_raw + (2 * GATE_SIZE), &nexthop->rmap_src,
	396	GATE_SIZE);
	397
	398	key = jhash2(gate_src_rmap_raw, (GATE_SIZE * 3), key);
d36d0d57	399
1b1fe1c4 SW	400	if (nexthop->nh_label) {
	401	int labels = nexthop->nh_label->num_labels;
	402	int i = 0;
	403
	404	while (labels >= 3) {
	405	key = jhash_3words(nexthop->nh_label->label[i],
	406	nexthop->nh_label->label[i + 1],
	407	nexthop->nh_label->label[i + 2],
	408	key);
	409	labels -= 3;
	410	i += 3;
	411	}
	412
	413	if (labels >= 2) {
	414	key = jhash_2words(nexthop->nh_label->label[i],
	415	nexthop->nh_label->label[i + 1],
	416	key);
	417	labels -= 2;
	418	i += 2;
	419	}
	420
	421	if (labels >= 1)
	422	key = jhash_1word(nexthop->nh_label->label[i], key);
	423	}
	424
	425	switch (nexthop->type) {
	426	case NEXTHOP_TYPE_IPV4_IFINDEX:
	427	case NEXTHOP_TYPE_IPV6_IFINDEX:
	428	case NEXTHOP_TYPE_IFINDEX:
	429	key = jhash_1word(nexthop->ifindex, key);
	430	break;
	431	case NEXTHOP_TYPE_BLACKHOLE:
	432	case NEXTHOP_TYPE_IPV4:
	433	case NEXTHOP_TYPE_IPV6:
	434	break;
	435	}
a7df4ccf SW	436
	437	key = jhash_1word(CHECK_FLAG(nexthop->flags, NEXTHOP_FLAG_ONLINK), key);
	438
d36d0d57 QY	439	return key;
d36d0d57 QY	440	}
d52ec572	441
e7addf02 SW	442	void nexthop_copy(struct nexthop copy, const struct nexthop nexthop,
	443	struct nexthop *rparent)
	444	{
	445	copy->vrf_id = nexthop->vrf_id;
	446	copy->ifindex = nexthop->ifindex;
	447	copy->type = nexthop->type;
	448	copy->flags = nexthop->flags;
	449	memcpy(&copy->gate, &nexthop->gate, sizeof(nexthop->gate));
	450	memcpy(&copy->src, &nexthop->src, sizeof(nexthop->src));
	451	memcpy(&copy->rmap_src, &nexthop->rmap_src, sizeof(nexthop->rmap_src));
	452	copy->rparent = rparent;
	453	if (nexthop->nh_label)
	454	nexthop_add_labels(copy, nexthop->nh_label_type,
	455	nexthop->nh_label->num_labels,
	456	&nexthop->nh_label->label[0]);
	457	}
	458
504d0a40 SW	459	struct nexthop nexthop_dup(const struct nexthop nexthop,
	460	struct nexthop *rparent)
	461	{
	462	struct nexthop *new = nexthop_new();
	463
	464	nexthop_copy(new, nexthop, rparent);
	465	return new;
	466	}
	467
d52ec572 DL	468	/*
	469	* nexthop printing variants:
	470	* %pNHvv
	471	* via 1.2.3.4
	472	* via 1.2.3.4, eth0
	473	* is directly connected, eth0
	474	* unreachable (blackhole)
	475	* %pNHv
	476	* 1.2.3.4
	477	* 1.2.3.4, via eth0
	478	* directly connected, eth0
	479	* unreachable (blackhole)
	480	* %pNHs
	481	* nexthop2str()
	482	*/
	483	printfrr_ext_autoreg_p("NH", printfrr_nh)
	484	static ssize_t printfrr_nh(char buf, size_t bsz, const char fmt,
	485	int prec, const void *ptr)
	486	{
	487	const struct nexthop *nexthop = ptr;
	488	struct fbuf fb = { .buf = buf, .pos = buf, .len = bsz - 1 };
	489	bool do_ifi = false;
	490	const char s, v_is = "", v_via = "", v_viaif = "via ";
	491	ssize_t ret = 3;
	492
	493	switch (fmt[2]) {
	494	case 'v':
	495	if (fmt[3] == 'v') {
	496	v_is = "is ";
	497	v_via = "via ";
	498	v_viaif = "";
	499	ret++;
	500	}
	501
	502	switch (nexthop->type) {
	503	case NEXTHOP_TYPE_IPV4:
	504	case NEXTHOP_TYPE_IPV4_IFINDEX:
	505	bprintfrr(&fb, "%s%pI4", v_via, &nexthop->gate.ipv4);
	506	do_ifi = true;
	507	break;
	508	case NEXTHOP_TYPE_IPV6:
	509	case NEXTHOP_TYPE_IPV6_IFINDEX:
	510	bprintfrr(&fb, "%s%pI6", v_via, &nexthop->gate.ipv6);
	511	do_ifi = true;
	512	break;
	513	case NEXTHOP_TYPE_IFINDEX:
	514	bprintfrr(&fb, "%sdirectly connected, %s", v_is,
	515	ifindex2ifname(nexthop->ifindex,
	516	nexthop->vrf_id));
	517	break;
	518	case NEXTHOP_TYPE_BLACKHOLE:
	519	switch (nexthop->bh_type) {
	520	case BLACKHOLE_REJECT:
	521	s = " (ICMP unreachable)";
	522	break;
	523	case BLACKHOLE_ADMINPROHIB:
	524	s = " (ICMP admin-prohibited)";
	525	break;
	526	case BLACKHOLE_NULL:
	527	s = " (blackhole)";
	528	break;
	529	default:
	530	s = "";
	531	break;
532	}
533	bprintfrr(&fb, "unreachable%s", s);
534	break;
535	default:
536	break;
537	}
538	if (do_ifi && nexthop->ifindex)
539	bprintfrr(&fb, ", %s%s", v_viaif, ifindex2ifname(
540	nexthop->ifindex,
541	nexthop->vrf_id));
542
543	*fb.pos = '\0';
544	return ret;
545	case 's':
546	nexthop2str(nexthop, buf, bsz);
547	return 3;
548	}
549	return 0;
550	}