[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")

/* 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(struct nexthop *nh1, struct nexthop *nh2)
{
	struct mpls_label_stack *nhl1, *nhl2;

	nhl1 = nh1->nh_label;
	nhl2 = nh2->nh_label;
	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;
	}

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

uint32_t nexthop_hash(struct nexthop *nexthop)
{
	uint32_t key;

	key = jhash_1word(nexthop->vrf_id, 0x45afe398);
	key = jhash_1word(nexthop->ifindex, key);
	key = jhash_1word(nexthop->type, key);
	key = jhash(&nexthop->gate, sizeof(union g_addr), key);

	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
fb018d25	39	/* check if nexthops are same, non-recursive */
fd36be7e DL	40	int nexthop_same_no_recurse(const struct nexthop *next1,
fd36be7e DL	41	const struct nexthop *next2)
fb018d25	42	{
d62a17ae	43	if (next1->type != next2->type)
	44	return 0;
	45
	46	switch (next1->type) {
	47	case NEXTHOP_TYPE_IPV4:
	48	case NEXTHOP_TYPE_IPV4_IFINDEX:
	49	if (!IPV4_ADDR_SAME(&next1->gate.ipv4, &next2->gate.ipv4))
	50	return 0;
	51	if (next1->ifindex && (next1->ifindex != next2->ifindex))
	52	return 0;
	53	break;
	54	case NEXTHOP_TYPE_IFINDEX:
	55	if (next1->ifindex != next2->ifindex)
	56	return 0;
	57	break;
	58	case NEXTHOP_TYPE_IPV6:
	59	if (!IPV6_ADDR_SAME(&next1->gate.ipv6, &next2->gate.ipv6))
	60	return 0;
	61	break;
	62	case NEXTHOP_TYPE_IPV6_IFINDEX:
	63	if (!IPV6_ADDR_SAME(&next1->gate.ipv6, &next2->gate.ipv6))
	64	return 0;
	65	if (next1->ifindex != next2->ifindex)
	66	return 0;
25b9cb0c DL	67	break;
	68	default:
	69	/* do nothing */
	70	break;
	71	}
	72	return 1;
	73	}
	74
996c9314	75	int nexthop_same_firsthop(struct nexthop next1, struct nexthop next2)
25b9cb0c DL	76	{
	77	int type1 = NEXTHOP_FIRSTHOPTYPE(next1->type);
	78	int type2 = NEXTHOP_FIRSTHOPTYPE(next2->type);
	79
	80	if (type1 != type2)
	81	return 0;
996c9314	82	switch (type1) {
25b9cb0c	83	case NEXTHOP_TYPE_IPV4_IFINDEX:
996c9314	84	if (!IPV4_ADDR_SAME(&next1->gate.ipv4, &next2->gate.ipv4))
25b9cb0c DL	85	return 0;
	86	if (next1->ifindex != next2->ifindex)
	87	return 0;
	88	break;
	89	case NEXTHOP_TYPE_IFINDEX:
	90	if (next1->ifindex != next2->ifindex)
	91	return 0;
	92	break;
	93	case NEXTHOP_TYPE_IPV6_IFINDEX:
996c9314	94	if (!IPV6_ADDR_SAME(&next1->gate.ipv6, &next2->gate.ipv6))
25b9cb0c DL	95	return 0;
	96	if (next1->ifindex != next2->ifindex)
	97	return 0;
d62a17ae	98	break;
	99	default:
	100	/* do nothing */
	101	break;
	102	}
	103	return 1;
fb018d25 DS	104	}
	105
	106	/*
	107	* nexthop_type_to_str
	108	*/
d62a17ae	109	const char *nexthop_type_to_str(enum nexthop_types_t nh_type)
fb018d25	110	{
d62a17ae	111	static const char *desc[] = {
	112	"none", "Directly connected",
	113	"IPv4 nexthop", "IPv4 nexthop with ifindex",
	114	"IPv6 nexthop", "IPv6 nexthop with ifindex",
	115	"Null0 nexthop",
	116	};
	117
	118	return desc[nh_type];
fb018d25	119	}
a399694f	120
a64448ba DS	121	/*
	122	* Check if the labels match for the 2 nexthops specified.
	123	*/
d62a17ae	124	int nexthop_labels_match(struct nexthop nh1, struct nexthop nh2)
a64448ba	125	{
8ecdb26e	126	struct mpls_label_stack nhl1, nhl2;
a64448ba	127
d62a17ae	128	nhl1 = nh1->nh_label;
d62a17ae	129	nhl2 = nh2->nh_label;
3f58e1b3	130	if (!nhl1 \|\| !nhl2)
d62a17ae	131	return 0;
a64448ba	132
d62a17ae	133	if (nhl1->num_labels != nhl2->num_labels)
d62a17ae	134	return 0;
a64448ba	135
d62a17ae	136	if (memcmp(nhl1->label, nhl2->label, nhl1->num_labels))
d62a17ae	137	return 0;
a64448ba	138
d62a17ae	139	return 1;
a64448ba DS	140	}
a64448ba DS	141
d62a17ae	142	struct nexthop *nexthop_new(void)
a399694f	143	{
d62a17ae	144	return XCALLOC(MTYPE_NEXTHOP, sizeof(struct nexthop));
a399694f DS	145	}
a399694f DS	146
a399694f	147	/* Free nexthop. */
d62a17ae	148	void nexthop_free(struct nexthop *nexthop)
a399694f	149	{
d62a17ae	150	nexthop_del_labels(nexthop);
	151	if (nexthop->resolved)
	152	nexthops_free(nexthop->resolved);
	153	XFREE(MTYPE_NEXTHOP, nexthop);
a399694f DS	154	}
	155
	156	/* Frees a list of nexthops */
d62a17ae	157	void nexthops_free(struct nexthop *nexthop)
a399694f	158	{
d62a17ae	159	struct nexthop nh, next;
a399694f	160
d62a17ae	161	for (nh = nexthop; nh; nh = next) {
	162	next = nh->next;
	163	nexthop_free(nh);
	164	}
a399694f	165	}
80c2442a	166
31919191 DS	167	bool nexthop_same(const struct nexthop nh1, const struct nexthop nh2)
	168	{
	169	if (nh1 && !nh2)
	170	return false;
	171
	172	if (!nh1 && nh2)
	173	return false;
	174
	175	if (nh1 == nh2)
	176	return true;
	177
	178	if (nh1->vrf_id != nh2->vrf_id)
	179	return false;
	180
	181	if (nh1->type != nh2->type)
	182	return false;
	183
	184	switch (nh1->type) {
	185	case NEXTHOP_TYPE_IFINDEX:
	186	if (nh1->ifindex != nh2->ifindex)
	187	return false;
	188	break;
	189	case NEXTHOP_TYPE_IPV4:
	190	if (nh1->gate.ipv4.s_addr != nh2->gate.ipv4.s_addr)
	191	return false;
	192	break;
	193	case NEXTHOP_TYPE_IPV4_IFINDEX:
	194	if (nh1->gate.ipv4.s_addr != nh2->gate.ipv4.s_addr)
	195	return false;
	196	if (nh1->ifindex != nh2->ifindex)
	197	return false;
	198	break;
	199	case NEXTHOP_TYPE_IPV6:
	200	if (memcmp(&nh1->gate.ipv6, &nh2->gate.ipv6, 16))
	201	return false;
	202	break;
	203	case NEXTHOP_TYPE_IPV6_IFINDEX:
	204	if (memcmp(&nh1->gate.ipv6, &nh2->gate.ipv6, 16))
	205	return false;
	206	if (nh1->ifindex != nh2->ifindex)
	207	return false;
	208	break;
	209	case NEXTHOP_TYPE_BLACKHOLE:
	210	if (nh1->bh_type != nh2->bh_type)
	211	return false;
	212	break;
	213	}
	214
	215	return true;
	216	}
	217
40c7bdb0	218	/* Update nexthop with label information. */
d62a17ae	219	void nexthop_add_labels(struct nexthop *nexthop, enum lsp_types_t type,
d7c0a89a	220	uint8_t num_labels, mpls_label_t *label)
40c7bdb0	221	{
8ecdb26e	222	struct mpls_label_stack *nh_label;
d62a17ae	223	int i;
	224
	225	nexthop->nh_label_type = type;
	226	nh_label = XCALLOC(MTYPE_NH_LABEL,
8ecdb26e	227	sizeof(struct mpls_label_stack)
d62a17ae	228	+ num_labels * sizeof(mpls_label_t));
	229	nh_label->num_labels = num_labels;
	230	for (i = 0; i < num_labels; i++)
	231	nh_label->label[i] = *(label + i);
	232	nexthop->nh_label = nh_label;
40c7bdb0	233	}
	234
	235	/* Free label information of nexthop, if present. */
d62a17ae	236	void nexthop_del_labels(struct nexthop *nexthop)
40c7bdb0	237	{
d62a17ae	238	if (nexthop->nh_label) {
	239	XFREE(MTYPE_NH_LABEL, nexthop->nh_label);
	240	nexthop->nh_label_type = ZEBRA_LSP_NONE;
	241	}
40c7bdb0	242	}
40c7bdb0	243
d36d0d57	244	const char nexthop2str(const struct nexthop nexthop, char *str, int size)
80c2442a	245	{
d62a17ae	246	switch (nexthop->type) {
	247	case NEXTHOP_TYPE_IFINDEX:
	248	snprintf(str, size, "if %u", nexthop->ifindex);
	249	break;
	250	case NEXTHOP_TYPE_IPV4:
d62a17ae	251	case NEXTHOP_TYPE_IPV4_IFINDEX:
	252	snprintf(str, size, "%s if %u", inet_ntoa(nexthop->gate.ipv4),
	253	nexthop->ifindex);
	254	break;
	255	case NEXTHOP_TYPE_IPV6:
d62a17ae	256	case NEXTHOP_TYPE_IPV6_IFINDEX:
	257	snprintf(str, size, "%s if %u", inet6_ntoa(nexthop->gate.ipv6),
	258	nexthop->ifindex);
	259	break;
	260	case NEXTHOP_TYPE_BLACKHOLE:
	261	snprintf(str, size, "blackhole");
	262	break;
	263	default:
	264	snprintf(str, size, "unknown");
	265	break;
	266	}
	267
	268	return str;
80c2442a	269	}
9fb47c05 CF	270
	271	/*
	272	* Iteration step for ALL_NEXTHOPS macro:
	273	* This is the tricky part. Check if `nexthop' has
	274	* NEXTHOP_FLAG_RECURSIVE set. If yes, this implies that `nexthop' has
	275	* at least one nexthop attached to `nexthop->resolved', which will be
	276	* the next one.
	277	*
	278	* If NEXTHOP_FLAG_RECURSIVE is not set, `nexthop' will progress in its
	279	* current chain. In case its current chain end is reached, it will move
	280	* upwards in the recursion levels and progress there. Whenever a step
	281	* forward in a chain is done, recursion will be checked again.
	282	* In a nustshell, it's equivalent to a pre-traversal order assuming that
	283	* left branch is 'resolved' and right branch is 'next':
	284	* https://en.wikipedia.org/wiki/Tree_traversal#/media/File:Sorted_binary_tree_preorder.svg
	285	*/
d62a17ae	286	struct nexthop nexthop_next(struct nexthop nexthop)
9fb47c05	287	{
d62a17ae	288	if (CHECK_FLAG(nexthop->flags, NEXTHOP_FLAG_RECURSIVE))
d62a17ae	289	return nexthop->resolved;
9fb47c05	290
d62a17ae	291	if (nexthop->next)
d62a17ae	292	return nexthop->next;
9fb47c05	293
d62a17ae	294	for (struct nexthop *par = nexthop->rparent; par; par = par->rparent)
	295	if (par->next)
	296	return par->next;
9fb47c05	297
d62a17ae	298	return NULL;
9fb47c05	299	}
e3054ee9	300
d62a17ae	301	unsigned int nexthop_level(struct nexthop *nexthop)
e3054ee9	302	{
d62a17ae	303	unsigned int rv = 0;
e3054ee9	304
d62a17ae	305	for (struct nexthop *par = nexthop->rparent; par; par = par->rparent)
d62a17ae	306	rv++;
e3054ee9	307
d62a17ae	308	return rv;
e3054ee9	309	}
d36d0d57 QY	310
	311	uint32_t nexthop_hash(struct nexthop *nexthop)
	312	{
	313	uint32_t key;
	314
	315	key = jhash_1word(nexthop->vrf_id, 0x45afe398);
	316	key = jhash_1word(nexthop->ifindex, key);
	317	key = jhash_1word(nexthop->type, key);
	318	key = jhash(&nexthop->gate, sizeof(union g_addr), key);
	319
	320	return key;
	321	}