[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"
#include "vrf.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;

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

	if (next1->weight > next2->weight)
		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 *const 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)
{
	struct nexthop *nh;

	nh = XCALLOC(MTYPE_NEXTHOP, sizeof(struct nexthop));

	/*
	 * Default the weight to 1 here for all nexthops.
	 * The linux kernel does some weird stuff with adding +1 to
	 * all nexthop weights it gets over netlink.
	 * To handle this, just default everything to 1 right from
	 * from the beggining so we don't have to special case
	 * default weights in the linux netlink code.
	 *
	 * 1 should be a valid on all platforms anyway.
	 */
	nh->weight = 1;

	return nh;
}

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

/*
 * Allocate a new nexthop object and initialize it from various args.
 */
struct nexthop *nexthop_from_ifindex(ifindex_t ifindex, vrf_id_t vrf_id)
{
	struct nexthop *nexthop;

	nexthop = nexthop_new();
	nexthop->type = NEXTHOP_TYPE_IFINDEX;
	nexthop->ifindex = ifindex;
	nexthop->vrf_id = vrf_id;

	return nexthop;
}

struct nexthop *nexthop_from_ipv4(const struct in_addr *ipv4,
				  const struct in_addr *src,
				  vrf_id_t vrf_id)
{
	struct nexthop *nexthop;

	nexthop = nexthop_new();
	nexthop->type = NEXTHOP_TYPE_IPV4;
	nexthop->vrf_id = vrf_id;
	nexthop->gate.ipv4 = *ipv4;
	if (src)
		nexthop->src.ipv4 = *src;

	return nexthop;
}

struct nexthop *nexthop_from_ipv4_ifindex(const struct in_addr *ipv4,
					  const struct in_addr *src,
					  ifindex_t ifindex, vrf_id_t vrf_id)
{
	struct nexthop *nexthop;

	nexthop = nexthop_new();
	nexthop->type = NEXTHOP_TYPE_IPV4_IFINDEX;
	nexthop->vrf_id = vrf_id;
	nexthop->gate.ipv4 = *ipv4;
	if (src)
		nexthop->src.ipv4 = *src;
	nexthop->ifindex = ifindex;

	return nexthop;
}

struct nexthop *nexthop_from_ipv6(const struct in6_addr *ipv6,
				  vrf_id_t vrf_id)
{
	struct nexthop *nexthop;

	nexthop = nexthop_new();
	nexthop->vrf_id = vrf_id;
	nexthop->type = NEXTHOP_TYPE_IPV6;
	nexthop->gate.ipv6 = *ipv6;

	return nexthop;
}

struct nexthop *nexthop_from_ipv6_ifindex(const struct in6_addr *ipv6,
					  ifindex_t ifindex, vrf_id_t vrf_id)
{
	struct nexthop *nexthop;

	nexthop = nexthop_new();
	nexthop->vrf_id = vrf_id;
	nexthop->type = NEXTHOP_TYPE_IPV6_IFINDEX;
	nexthop->gate.ipv6 = *ipv6;
	nexthop->ifindex = ifindex;

	return nexthop;
}

struct nexthop *nexthop_from_blackhole(enum blackhole_type bh_type)
{
	struct nexthop *nexthop;

	nexthop = nexthop_new();
	nexthop->vrf_id = VRF_DEFAULT;
	nexthop->type = NEXTHOP_TYPE_BLACKHOLE;
	nexthop->bh_type = bh_type;

	return nexthop;
}

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

	if (num_labels == 0)
		return;

	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(const 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;
}

/* Return the next nexthop in the tree that is resolved and active */
struct nexthop *nexthop_next_active_resolved(const struct nexthop *nexthop)
{
	struct nexthop *next = nexthop_next(nexthop);

	while (next
	       && (CHECK_FLAG(next->flags, NEXTHOP_FLAG_RECURSIVE)
		   || !CHECK_FLAG(next->flags, NEXTHOP_FLAG_ACTIVE)))
		next = nexthop_next(next);

	return next;
}

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

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

	return rv;
}

/* Only hash word-sized things, let cmp do the rest. */
uint32_t nexthop_hash_quick(const struct nexthop *nexthop)
{
	uint32_t key = 0x45afe398;

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

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

		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);
	}

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

	return key;
}


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

/* For a more granular hash */
uint32_t nexthop_hash(const struct nexthop *nexthop)
{
	uint32_t gate_src_rmap_raw[GATE_SIZE * 3] = {};
	/* Get all the quick stuff */
	uint32_t key = nexthop_hash_quick(nexthop);

	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);

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