Merge pull request #3051 from mitch-skiba/addpath_change_V1

Addpath - Reuse IDs

7 files changed, 220 insertions, 17 deletions

diff --git a/tests/.gitignore b/tests/.gitignore
index 49a4b6e47..a6202786b 100644
--- a/tests/.gitignore
+++ b/tests/.gitignore
@@ -20,23 +20,24 @@
 /lib/cli/test_commands_defun.c
 /lib/test_buffer
 /lib/test_checksum
+/lib/test_graph
 /lib/test_heavy
 /lib/test_heavy_thread
 /lib/test_heavy_wq
+/lib/test_idalloc
 /lib/test_memory
 /lib/test_nexthop_iter
 /lib/test_privs
 /lib/test_ringbuf
-/lib/test_srcdest_table
 /lib/test_segv
 /lib/test_sig
+/lib/test_srcdest_table
 /lib/test_stream
 /lib/test_table
 /lib/test_timer_correctness
 /lib/test_timer_performance
 /lib/test_ttable
-/lib/test_zmq
 /lib/test_zlog
-/lib/test_graph
+/lib/test_zmq
 /ospf6d/test_lsdb
 /ospf6d/test_lsdb_clippy.c
diff --git a/tests/bgpd/test_bgp_table.c b/tests/bgpd/test_bgp_table.c
index 171b1aa22..73243dcac 100644
--- a/tests/bgpd/test_bgp_table.c
+++ b/tests/bgpd/test_bgp_table.c
@@ -28,6 +28,8 @@
 #include "bgpd/bgp_table.h"
 #include "linklist.h"
 
+/* Satisfy link requirements from including bgpd.h */
+struct zebra_privs_t bgpd_privs = {0};
 /*
  * test_node_t
  *
diff --git a/tests/bgpd/test_peer_attr.c b/tests/bgpd/test_peer_attr.c
index 2f464d721..2fbc686e1 100644
--- a/tests/bgpd/test_peer_attr.c
+++ b/tests/bgpd/test_peer_attr.c
@@ -254,6 +254,8 @@ TEST_STR_ATTR_HANDLER_DECL(password, password, "FRR-Peer", "FRR-Group");
 TEST_ATTR_HANDLER_DECL(local_as, change_local_as, 1, 2);
 TEST_ATTR_HANDLER_DECL(timers_1, keepalive, 10, 20);
 TEST_ATTR_HANDLER_DECL(timers_2, holdtime, 30, 60);
+TEST_ATTR_HANDLER_DECL(addpath_types, addpath_type[pa->afi][pa->safi],
+		       BGP_ADDPATH_ALL, BGP_ADDPATH_BEST_PER_AS);
 TEST_SU_ATTR_HANDLER_DECL(update_source_su, update_source, "255.255.255.1",
 			  "255.255.255.2");
 TEST_STR_ATTR_HANDLER_DECL(update_source_if, update_if, "IF-PEER", "IF-GROUP");
@@ -414,12 +416,11 @@ static struct test_peer_attr test_peer_attrs[] = {
 
 	/* Address Family Attributes */
 	{
-		.cmd = "addpath-tx-all-paths",
-		.u.flag = PEER_FLAG_ADDPATH_TX_ALL_PATHS,
-	},
-	{
-		.cmd = "addpath-tx-bestpath-per-AS",
-		.u.flag = PEER_FLAG_ADDPATH_TX_BESTPATH_PER_AS,
+		.cmd = "addpath",
+		.peer_cmd = "addpath-tx-all-paths",
+		.group_cmd = "addpath-tx-bestpath-per-AS",
+		.type = PEER_AT_AF_CUSTOM,
+		.handlers[0] = TEST_HANDLER(addpath_types),
 	},
 	{
 		.cmd = "allowas-in",
diff --git a/tests/bgpd/test_peer_attr.py b/tests/bgpd/test_peer_attr.py
index 7a4dd2b04..bafd131b7 100644
--- a/tests/bgpd/test_peer_attr.py
+++ b/tests/bgpd/test_peer_attr.py
@@ -26,14 +26,10 @@ TestFlag.okfail('peer\\timers')
 TestFlag.okfail('peer\\timers connect')
 TestFlag.okfail('peer\\update-source')
 TestFlag.okfail('peer\\update-source')
-TestFlag.okfail('peer\\ipv4-unicast\\addpath-tx-all-paths')
-TestFlag.okfail('peer\\ipv4-multicast\\addpath-tx-all-paths')
-TestFlag.okfail('peer\\ipv6-unicast\\addpath-tx-all-paths')
-TestFlag.okfail('peer\\ipv6-multicast\\addpath-tx-all-paths')
-TestFlag.okfail('peer\\ipv4-unicast\\addpath-tx-bestpath-per-AS')
-TestFlag.okfail('peer\\ipv4-multicast\\addpath-tx-bestpath-per-AS')
-TestFlag.okfail('peer\\ipv6-unicast\\addpath-tx-bestpath-per-AS')
-TestFlag.okfail('peer\\ipv6-multicast\\addpath-tx-bestpath-per-AS')
+TestFlag.okfail('peer\\ipv4-unicast\\addpath')
+TestFlag.okfail('peer\\ipv4-multicast\\addpath')
+TestFlag.okfail('peer\\ipv6-unicast\\addpath')
+TestFlag.okfail('peer\\ipv6-multicast\\addpath')
 TestFlag.okfail('peer\\ipv4-unicast\\allowas-in')
 TestFlag.okfail('peer\\ipv4-multicast\\allowas-in')
 TestFlag.okfail('peer\\ipv6-unicast\\allowas-in')
diff --git a/tests/lib/test_idalloc.c b/tests/lib/test_idalloc.c
new file mode 100644
index 000000000..3053c1c07
--- /dev/null
+++ b/tests/lib/test_idalloc.c
@@ -0,0 +1,193 @@
+#include "id_alloc.h"
+
+#include <inttypes.h>
+#include <string.h>
+#include <assert.h>
+#include <stdio.h>
+
+#define IDS_PER_PAGE (1<<(IDALLOC_OFFSET_BITS + IDALLOC_WORD_BITS))
+char allocated_markers[IDS_PER_PAGE*3];
+
+int main(int argc, char **argv)
+{
+	int i, val;
+	uint32_t pg;
+	struct id_alloc *a;
+
+	/* 1. Rattle test, shake it a little and make sure it doesn't make any
+	 * noise :)
+	 */
+	a = idalloc_new("Rattle test");
+	for (i = 0; i < 1000000; i++)
+		assert(idalloc_allocate(a) != 0);
+
+	idalloc_destroy(a);
+
+	/* 2. Reserve a few low IDs, make sure they are skipped by normal
+	 * allocation.
+	 */
+	a = idalloc_new("Low Reservations");
+	assert(idalloc_reserve(a, 1) == 1);
+	assert(idalloc_reserve(a, 3) == 3);
+	assert(idalloc_reserve(a, 5) == 5);
+	for (i = 0; i < 100; i++) {
+		val = idalloc_allocate(a);
+		assert(val != 1 && val != 3 && val != 5);
+	}
+	idalloc_destroy(a);
+
+	/* 3. Single page testing. Check that IDs are kept unique, and all IDs
+	 * in the existing page are allocated before a new page is added.
+	 */
+	memset(allocated_markers, 0, sizeof(allocated_markers));
+	allocated_markers[IDALLOC_INVALID] = 1;
+
+	a = idalloc_new("Single Page");
+
+	/* reserve the rest of the first page */
+	for (i = 0; i < IDS_PER_PAGE - 1; i++) {
+		val = idalloc_allocate(a);
+		assert(val < IDS_PER_PAGE);
+		assert(allocated_markers[val] == 0);
+		assert(a->capacity == IDS_PER_PAGE);
+		allocated_markers[val] = 1;
+	}
+	/* Check that the count is right */
+	assert(a->allocated == IDS_PER_PAGE);
+
+	/* Free some IDs out of the middle. */
+	idalloc_free(a, 300);
+	allocated_markers[300] = 0;
+	idalloc_free(a, 400);
+	allocated_markers[400] = 0;
+	idalloc_free(a, 500);
+	allocated_markers[500] = 0;
+
+	assert(a->allocated == IDS_PER_PAGE-3);
+
+	/* Allocate the three IDs back and make sure they are pulled from the
+	 * set just freed
+	 */
+	for (i = 0; i < 3; i++) {
+		val = idalloc_allocate(a);
+		assert(val < IDS_PER_PAGE);
+		assert(allocated_markers[val] == 0);
+		assert(a->capacity == IDS_PER_PAGE);
+		allocated_markers[val] = 1;
+	}
+	idalloc_destroy(a);
+
+	/* 4. Multi-page testing. */
+	memset(allocated_markers, 0, sizeof(allocated_markers));
+	allocated_markers[IDALLOC_INVALID] = 1;
+
+	a = idalloc_new("Multi-page");
+
+	/* reserve the rest of the first page and all of the second and third */
+	for (i = 0; i < 3 * IDS_PER_PAGE - 1; i++) {
+		val = idalloc_allocate(a);
+		assert(val < 3*IDS_PER_PAGE);
+		assert(allocated_markers[val] == 0);
+		allocated_markers[val] = 1;
+	}
+	assert(a->capacity == 3*IDS_PER_PAGE);
+	assert(a->allocated == 3*IDS_PER_PAGE);
+
+	/* Free two IDs from each page. */
+	for (i = 0; i < 3; i++) {
+		idalloc_free(a, 7 + i*IDS_PER_PAGE);
+		allocated_markers[7 + i*IDS_PER_PAGE] = 0;
+
+		idalloc_free(a, 4 + i*IDS_PER_PAGE);
+		allocated_markers[4 + i*IDS_PER_PAGE] = 0;
+	}
+
+	assert(a->allocated == 3*IDS_PER_PAGE - 6);
+
+	/* Allocate the six IDs back and make sure they are pulled from the set
+	 * just freed.
+	 */
+	for (i = 0; i < 6; i++) {
+		val = idalloc_allocate(a);
+		assert(val < 3*IDS_PER_PAGE);
+		assert(allocated_markers[val] == 0);
+		assert(a->capacity == 3*IDS_PER_PAGE);
+		allocated_markers[val] = 1;
+	}
+
+	assert(a->capacity == 3*IDS_PER_PAGE);
+	assert(a->allocated == 3*IDS_PER_PAGE);
+
+	/* Walk each allocated ID. Free it, then re-allocate it back. */
+	for (i = 1; i < 3 * IDS_PER_PAGE - 1; i++) {
+		idalloc_free(a, i);
+		val = idalloc_allocate(a);
+		assert(val == i);
+		assert(a->capacity == 3*IDS_PER_PAGE);
+		assert(a->allocated == 3*IDS_PER_PAGE);
+	}
+	idalloc_destroy(a);
+
+	/* 5. Weird Reservations
+	 * idalloc_reserve exists primarily to black out low numbered IDs that
+	 * are reserved for special cases. However, we will test it for more
+	 * complex use cases to avoid unpleasant surprises.
+	 */
+
+	memset(allocated_markers, 0, sizeof(allocated_markers));
+	allocated_markers[IDALLOC_INVALID] = 1;
+
+	a = idalloc_new("Weird Reservations");
+
+	/* Start with 3 pages fully allocated. */
+	for (i = 0; i < 3 * IDS_PER_PAGE - 1; i++) {
+		val = idalloc_allocate(a);
+		assert(val < 3*IDS_PER_PAGE);
+		assert(allocated_markers[val] == 0);
+		allocated_markers[val] = 1;
+	}
+	assert(a->capacity == 3*IDS_PER_PAGE);
+	assert(a->allocated == 3*IDS_PER_PAGE);
+
+	/* Free a bit out of each of the three pages. Then reserve one of the
+	 * three freed IDs. Finally, allocate the other two freed IDs. Do this
+	 * each of three ways. (Reserve out of the first, seconds then third
+	 * page.)
+	 * The intent here is to exercise the rare cases on reserve_bit's
+	 * linked-list removal in the case that it is not removing the first
+	 * page with a free bit in its list of pages with free bits.
+	 */
+
+	for (pg = 0; pg < 3; pg++) {
+		/* free a bit out of each of the three pages */
+		for (i = 0; i < 3; i++) {
+			idalloc_free(a, i*IDS_PER_PAGE + 17);
+			allocated_markers[i*IDS_PER_PAGE + 17] = 0;
+		}
+
+		assert(a->capacity == 3*IDS_PER_PAGE);
+		assert(a->allocated == 3*IDS_PER_PAGE-3);
+
+		/* Reserve one of the freed IDs */
+		assert(idalloc_reserve(a, pg*IDS_PER_PAGE + 17) ==
+		       pg*IDS_PER_PAGE + 17);
+		allocated_markers[pg*IDS_PER_PAGE + 17] = 1;
+
+		assert(a->capacity == 3*IDS_PER_PAGE);
+		assert(a->allocated == 3*IDS_PER_PAGE-2);
+
+		/* Allocate the other two back */
+		for (i = 0; i < 2; i++) {
+			val = idalloc_allocate(a);
+			assert(val < 3*IDS_PER_PAGE);
+			assert(allocated_markers[val] == 0);
+			allocated_markers[val] = 1;
+		}
+		assert(a->capacity == 3*IDS_PER_PAGE);
+		assert(a->allocated == 3*IDS_PER_PAGE);
+	}
+	idalloc_destroy(a);
+
+	puts("ID Allocator test successful.\n");
+	return 0;
+}
diff --git a/tests/lib/test_idalloc.py b/tests/lib/test_idalloc.py
new file mode 100644
index 000000000..22de082be
--- /dev/null
+++ b/tests/lib/test_idalloc.py
@@ -0,0 +1,6 @@
+import frrtest
+
+class TestIDAlloc(frrtest.TestMultiOut):
+    program = './test_idalloc'
+
+TestIDAlloc.onesimple('ID Allocator test successful.')
diff --git a/tests/subdir.am b/tests/subdir.am
index 7a693ac0f..6b52c90bc 100644
--- a/tests/subdir.am
+++ b/tests/subdir.am
@@ -51,6 +51,7 @@ check_PROGRAMS = \
 	tests/lib/test_heavy_thread \
 	tests/lib/test_heavy_wq \
 	tests/lib/test_heavy \
+	tests/lib/test_idalloc \
 	tests/lib/test_memory \
 	tests/lib/test_nexthop_iter \
 	tests/lib/test_privs \
@@ -198,6 +199,9 @@ tests_lib_test_heavy_wq_CFLAGS = $(TESTS_CFLAGS)
 tests_lib_test_heavy_wq_CPPFLAGS = $(TESTS_CPPFLAGS)
 tests_lib_test_heavy_wq_LDADD = $(ALL_TESTS_LDADD) -lm
 tests_lib_test_heavy_wq_SOURCES = tests/lib/test_heavy_wq.c tests/helpers/c/main.c
+tests_lib_test_idalloc_CFLAGS = $(TESTS_CFLAGS)
+tests_lib_test_idalloc_LDADD = $(ALL_TESTS_LDADD)
+tests_lib_test_idalloc_SOURCES = tests/lib/test_idalloc.c
 tests_lib_test_memory_CFLAGS = $(TESTS_CFLAGS)
 tests_lib_test_memory_CPPFLAGS = $(TESTS_CPPFLAGS)
 tests_lib_test_memory_LDADD = $(ALL_TESTS_LDADD)