Merge pull request #8380 from mjstapp/nexthop_cmp_basic

5 files changed, 321 insertions, 1 deletions

diff --git a/lib/nexthop.c b/lib/nexthop.c
index 843939814..0ac6c0ae1 100644
--- a/lib/nexthop.c
+++ b/lib/nexthop.c
@@ -62,7 +62,8 @@ static int _nexthop_labels_cmp(const struct nexthop *nh1,
 	if (nhl1->num_labels < nhl2->num_labels)
 		return -1;
 
-	return memcmp(nhl1->label, nhl2->label, nhl1->num_labels);
+	return memcmp(nhl1->label, nhl2->label,
+		      (nhl1->num_labels * sizeof(mpls_label_t)));
 }
 
 int nexthop_g_addr_cmp(enum nexthop_types_t type, const union g_addr *addr1,
@@ -203,6 +204,105 @@ int nexthop_cmp(const struct nexthop *next1, const struct nexthop *next2)
 }
 
 /*
+ * More-limited comparison function used to detect duplicate
+ * nexthops. This is used in places where we don't need the full
+ * comparison of 'nexthop_cmp()'.
+ */
+int nexthop_cmp_basic(const struct nexthop *nh1,
+		      const struct nexthop *nh2)
+{
+	int ret = 0;
+	const struct mpls_label_stack *nhl1 = NULL;
+	const struct mpls_label_stack *nhl2 = NULL;
+
+	if (nh1 == NULL && nh2 == NULL)
+		return 0;
+
+	if (nh1 && !nh2)
+		return 1;
+
+	if (!nh1 && nh2)
+		return -1;
+
+	if (nh1->vrf_id < nh2->vrf_id)
+		return -1;
+
+	if (nh1->vrf_id > nh2->vrf_id)
+		return 1;
+
+	if (nh1->type < nh2->type)
+		return -1;
+
+	if (nh1->type > nh2->type)
+		return 1;
+
+	if (nh1->weight < nh2->weight)
+		return -1;
+
+	if (nh1->weight > nh2->weight)
+		return 1;
+
+	switch (nh1->type) {
+	case NEXTHOP_TYPE_IPV4:
+	case NEXTHOP_TYPE_IPV6:
+		ret = nexthop_g_addr_cmp(nh1->type, &nh1->gate, &nh2->gate);
+		if (ret != 0)
+			return ret;
+		break;
+	case NEXTHOP_TYPE_IPV4_IFINDEX:
+	case NEXTHOP_TYPE_IPV6_IFINDEX:
+		ret = nexthop_g_addr_cmp(nh1->type, &nh1->gate, &nh2->gate);
+		if (ret != 0)
+			return ret;
+		/* Intentional Fall-Through */
+	case NEXTHOP_TYPE_IFINDEX:
+		if (nh1->ifindex < nh2->ifindex)
+			return -1;
+
+		if (nh1->ifindex > nh2->ifindex)
+			return 1;
+		break;
+	case NEXTHOP_TYPE_BLACKHOLE:
+		if (nh1->bh_type < nh2->bh_type)
+			return -1;
+
+		if (nh1->bh_type > nh2->bh_type)
+			return 1;
+		break;
+	}
+
+	/* Compare source addr */
+	ret = nexthop_g_addr_cmp(nh1->type, &nh1->src, &nh2->src);
+	if (ret != 0)
+		goto done;
+
+	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;
+
+	ret = memcmp(nhl1->label, nhl2->label,
+		     (nhl1->num_labels * sizeof(mpls_label_t)));
+
+done:
+	return ret;
+}
+
+/*
  * nexthop_type_to_str
  */
 const char *nexthop_type_to_str(enum nexthop_types_t nh_type)
diff --git a/lib/nexthop.h b/lib/nexthop.h
index f1ad195cf..d6ea83cf0 100644
--- a/lib/nexthop.h
+++ b/lib/nexthop.h
@@ -207,6 +207,11 @@ extern int nexthop_g_addr_cmp(enum nexthop_types_t type,
 			      const union g_addr *addr1,
 			      const union g_addr *addr2);
 
+/* More-limited comparison function used to detect duplicate nexthops.
+ * Returns -1, 0, 1
+ */
+int nexthop_cmp_basic(const struct nexthop *nh1, const struct nexthop *nh2);
+
 extern const char *nexthop_type_to_str(enum nexthop_types_t nh_type);
 extern bool nexthop_labels_match(const struct nexthop *nh1,
 				 const struct nexthop *nh2);
diff --git a/tests/lib/test_nexthop.c b/tests/lib/test_nexthop.c
new file mode 100644
index 000000000..659d207b4
--- /dev/null
+++ b/tests/lib/test_nexthop.c
@@ -0,0 +1,201 @@
+/*
+ * Nexthop module test.
+ *
+ * Copyright (C) 2021 by Volta Networks, Inc.
+ *
+ * This file is part of FRR.
+ *
+ * FRR is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License as published by the
+ * Free Software Foundation; either version 2, or (at your option) any
+ * later version.
+ *
+ * FRR is distributed in the hope that it will be useful, but
+ * WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License along
+ * with 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 <nexthop.h>
+
+static bool verbose;
+
+static void test_run_first(void)
+{
+	int ret, i;
+	struct nexthop *nh1, *nh2;
+	struct in_addr addr;
+	struct in6_addr addr6;
+	mpls_label_t labels[MPLS_MAX_LABELS];
+
+	/* Test comparison apis */
+
+	/* ifindex comparisons */
+	nh1 = nexthop_from_ifindex(11, 0);
+	nh2 = nexthop_from_ifindex(12, 0);
+
+	ret = nexthop_cmp_basic(nh1, nh2);
+	assert(ret < 0);
+
+	nexthop_free(nh1);
+	nh1 = nexthop_from_ifindex(12, 0);
+
+	ret = nexthop_cmp_basic(nh1, nh2);
+	assert(ret == 0);
+
+	nexthop_free(nh1);
+	nexthop_free(nh2);
+
+	/* ipv4, vrf */
+	addr.s_addr = 0x04030201;
+	nh1 = nexthop_from_ipv4(&addr, NULL, 0);
+	nh2 = nexthop_from_ipv4(&addr, NULL, 111);
+
+	ret = nexthop_cmp_basic(nh1, nh2);
+	assert(ret != 0);
+
+	nexthop_free(nh2);
+
+	addr.s_addr = 0x04030202;
+	nh2 = nexthop_from_ipv4(&addr, NULL, 0);
+
+	ret = nexthop_cmp_basic(nh1, nh2);
+	assert(ret != 0);
+
+	nexthop_free(nh2);
+
+	addr.s_addr = 0x04030201;
+	nh2 = nexthop_from_ipv4(&addr, NULL, 0);
+
+	ret = nexthop_cmp_basic(nh1, nh2);
+	assert(ret == 0);
+
+	/* Weight */
+	nh2->weight = 20;
+
+	ret = nexthop_cmp_basic(nh1, nh2);
+	assert(ret != 0);
+
+	nexthop_free(nh1);
+	nexthop_free(nh2);
+
+	/* ipv6 */
+	memset(addr6.s6_addr, 0, sizeof(addr6.s6_addr));
+	nh1 = nexthop_from_ipv6(&addr6, 0);
+	nh2 = nexthop_from_ipv6(&addr6, 0);
+
+	ret = nexthop_cmp_basic(nh1, nh2);
+	assert(ret == 0);
+
+	nexthop_free(nh2);
+
+	nh2 = nexthop_from_ipv6(&addr6, 1);
+
+	ret = nexthop_cmp_basic(nh1, nh2);
+	assert(ret != 0);
+
+	nexthop_free(nh2);
+
+	addr6.s6_addr[14] = 1;
+	addr6.s6_addr[15] = 1;
+	nh2 = nexthop_from_ipv6(&addr6, 0);
+
+	ret = nexthop_cmp_basic(nh1, nh2);
+	assert(ret != 0);
+
+	nexthop_free(nh1);
+	nexthop_free(nh2);
+
+	/* Blackhole */
+	nh1 = nexthop_from_blackhole(BLACKHOLE_REJECT);
+	nh2 = nexthop_from_blackhole(BLACKHOLE_REJECT);
+
+	ret = nexthop_cmp_basic(nh1, nh2);
+	assert(ret == 0);
+
+	nexthop_free(nh2);
+
+	nh2 = nexthop_from_blackhole(BLACKHOLE_NULL);
+
+	ret = nexthop_cmp_basic(nh1, nh2);
+	assert(ret != 0);
+
+	/* Labels */
+	addr.s_addr = 0x04030201;
+	nh1 = nexthop_from_ipv4(&addr, NULL, 0);
+	nh2 = nexthop_from_ipv4(&addr, NULL, 0);
+
+	memset(labels, 0, sizeof(labels));
+	labels[0] = 111;
+	labels[1] = 222;
+
+	nexthop_add_labels(nh1, ZEBRA_LSP_STATIC, 2, labels);
+
+	ret = nexthop_cmp_basic(nh1, nh2);
+	assert(ret != 0);
+
+	nexthop_add_labels(nh2, ZEBRA_LSP_STATIC, 2, labels);
+
+	ret = nexthop_cmp_basic(nh1, nh2);
+	assert(ret == 0);
+
+	nexthop_free(nh2);
+
+	/* LSP type isn't included */
+	nh2 = nexthop_from_ipv4(&addr, NULL, 0);
+	nexthop_add_labels(nh2, ZEBRA_LSP_LDP, 2, labels);
+
+	ret = nexthop_cmp_basic(nh1, nh2);
+	assert(ret == 0);
+
+	nexthop_free(nh2);
+
+	labels[2] = 333;
+	nh2 = nexthop_from_ipv4(&addr, NULL, 0);
+	nexthop_add_labels(nh2, ZEBRA_LSP_LDP, 3, labels);
+
+	ret = nexthop_cmp_basic(nh1, nh2);
+	assert(ret != 0);
+
+	nexthop_free(nh1);
+	nexthop_free(nh2);
+
+	nh1 = nexthop_from_ipv4(&addr, NULL, 0);
+	nh2 = nexthop_from_ipv4(&addr, NULL, 0);
+
+	for (i = 0; i < MPLS_MAX_LABELS; i++)
+		labels[i] = 111 * (i + 1);
+
+	nexthop_add_labels(nh1, ZEBRA_LSP_LDP, MPLS_MAX_LABELS, labels);
+	nexthop_add_labels(nh2, ZEBRA_LSP_LDP, MPLS_MAX_LABELS, labels);
+
+	ret = nexthop_cmp_basic(nh1, nh2);
+	assert(ret == 0);
+
+	nexthop_free(nh2);
+
+	/* Test very last label in stack */
+	labels[15] = 999;
+	nh2 = nexthop_from_ipv4(&addr, NULL, 0);
+	nexthop_add_labels(nh2, ZEBRA_LSP_LDP, MPLS_MAX_LABELS, labels);
+
+	ret = nexthop_cmp_basic(nh1, nh2);
+	assert(ret != 0);
+
+	/* End */
+	nexthop_free(nh1);
+	nexthop_free(nh2);
+}
+
+int main(int argc, char **argv)
+{
+	if (argc >= 2 && !strcmp("-v", argv[1]))
+		verbose = true;
+	test_run_first();
+	printf("Simple test passed.\n");
+}
diff --git a/tests/lib/test_nexthop.py b/tests/lib/test_nexthop.py
new file mode 100644
index 000000000..81bfa43ab
--- /dev/null
+++ b/tests/lib/test_nexthop.py
@@ -0,0 +1,8 @@
+import frrtest
+
+
+class TestNexthopIter(frrtest.TestMultiOut):
+    program = "./test_nexthop"
+
+
+TestNexthopIter.onesimple("Simple test passed.")
diff --git a/tests/subdir.am b/tests/subdir.am
index 139f4878c..43fad29fa 100644
--- a/tests/subdir.am
+++ b/tests/subdir.am
@@ -76,6 +76,7 @@ check_PROGRAMS = \
 	tests/lib/test_idalloc \
 	tests/lib/test_memory \
 	tests/lib/test_nexthop_iter \
+	tests/lib/test_nexthop \
 	tests/lib/test_ntop \
 	tests/lib/test_prefix2str \
 	tests/lib/test_printfrr \
@@ -293,6 +294,10 @@ tests_lib_test_nexthop_iter_CFLAGS = $(TESTS_CFLAGS)
 tests_lib_test_nexthop_iter_CPPFLAGS = $(TESTS_CPPFLAGS)
 tests_lib_test_nexthop_iter_LDADD = $(ALL_TESTS_LDADD)
 tests_lib_test_nexthop_iter_SOURCES = tests/lib/test_nexthop_iter.c tests/helpers/c/prng.c
+tests_lib_test_nexthop_CFLAGS = $(TESTS_CFLAGS)
+tests_lib_test_nexthop_CPPFLAGS = $(TESTS_CPPFLAGS)
+tests_lib_test_nexthop_LDADD = $(ALL_TESTS_LDADD)
+tests_lib_test_nexthop_SOURCES = tests/lib/test_nexthop.c
 tests_lib_test_ntop_CFLAGS = $(TESTS_CFLAGS)
 tests_lib_test_ntop_CPPFLAGS = $(CPPFLAGS_BASE) # no assert override
 tests_lib_test_ntop_LDADD = # none
@@ -412,6 +417,7 @@ EXTRA_DIST += \
 	tests/lib/test_assert.py \
 	tests/lib/test_atomlist.py \
 	tests/lib/test_nexthop_iter.py \
+	tests/lib/test_nexthop.py \
 	tests/lib/test_ntop.py \
 	tests/lib/test_prefix2str.py \
 	tests/lib/test_printfrr.py \