[dpdk-dev] [PATCH] parray: introduce internal API for dynamic arrays

[Thomas Monjalon <thomas@monjalon.net>]

Performance of access in a fixed-size array is very good
because of cache locality
and because there is a single pointer to dereference.
The only drawback is the lack of flexibility:
the size of such an array cannot be increase at runtime.

An approach to this problem is to allocate the array at runtime,
being as efficient as static arrays, but still limited to a maximum.

That's why the API rte_parray is introduced,
allowing to declare an array of pointer which can be resized dynamically
and automatically at runtime while keeping a good read performance.

After resize, the previous array is kept until the next resize
to avoid crashs during a read without any lock.

Each element is a pointer to a memory chunk dynamically allocated.
This is not good for cache locality but it allows to keep the same
memory per element, no matter how the array is resized.
Cache locality could be improved with mempools.
The other drawback is having to dereference one more pointer
to read an element.

There is not much locks, so the API is for internal use only.
This API may be used to completely remove some compilation-time maximums.

Signed-off-by: Thomas Monjalon <thomas@monjalon.net>
---
 MAINTAINERS                  |   1 +
 app/test/meson.build         |   2 +
 app/test/test_parray.c       | 120 ++++++++++++++++++++++++++
 lib/eal/common/meson.build   |   1 +
 lib/eal/common/rte_parray.c  | 161 +++++++++++++++++++++++++++++++++++
 lib/eal/include/meson.build  |   1 +
 lib/eal/include/rte_parray.h | 138 ++++++++++++++++++++++++++++++
 lib/eal/version.map          |   4 +
 8 files changed, 428 insertions(+)
 create mode 100644 app/test/test_parray.c
 create mode 100644 lib/eal/common/rte_parray.c
 create mode 100644 lib/eal/include/rte_parray.h

diff --git a/MAINTAINERS b/MAINTAINERS
index 5877a16971..bdeae96e57 100644
--- a/MAINTAINERS
+++ b/MAINTAINERS
@@ -167,6 +167,7 @@ F: app/test/test_errno.c
 F: app/test/test_lcores.c
 F: app/test/test_logs.c
 F: app/test/test_memcpy*
+F: app/test/test_parray.c
 F: app/test/test_per_lcore.c
 F: app/test/test_pflock.c
 F: app/test/test_prefetch.c
diff --git a/app/test/meson.build b/app/test/meson.build
index 08c82d3d23..23dc672c0f 100644
--- a/app/test/meson.build
+++ b/app/test/meson.build
@@ -90,6 +90,7 @@ test_sources = files(
         'test_metrics.c',
         'test_mcslock.c',
         'test_mp_secondary.c',
+        'test_parray.c',
         'test_per_lcore.c',
         'test_pflock.c',
         'test_pmd_perf.c',
@@ -230,6 +231,7 @@ fast_tests = [
         ['memzone_autotest', false],
         ['meter_autotest', true],
         ['multiprocess_autotest', false],
+        ['parray_autotest', true],
         ['per_lcore_autotest', true],
         ['pflock_autotest', true],
         ['prefetch_autotest', true],
diff --git a/app/test/test_parray.c b/app/test/test_parray.c
new file mode 100644
index 0000000000..f92783d9e8
--- /dev/null
+++ b/app/test/test_parray.c
@@ -0,0 +1,120 @@
+/* SPDX-License-Identifier: BSD-3-Clause
+ * Copyright (c) 2021 NVIDIA Corporation & Affiliates
+ */
+
+#include <stdbool.h>
+#include <sys/resource.h>
+
+#include <rte_parray.h>
+#include <rte_lcore.h>
+#include <rte_errno.h>
+#include <rte_log.h>
+
+#include "test.h"
+
+RTE_LOG_REGISTER(test_parray_log, test.parray, INFO);
+#define LOG(level, ...) \
+	rte_log(RTE_LOG_ ## level, test_parray_log, RTE_FMT("parray test: " \
+		RTE_FMT_HEAD(__VA_ARGS__,) "\n", RTE_FMT_TAIL(__VA_ARGS__,)))
+
+static bool stop;
+
+static struct rte_parray array = RTE_PARRAY_INITIALIZER;
+typedef int elem_t; /* array of int pointers */
+
+static elem_t trash;
+
+static long
+get_context_switches(void)
+{
+	struct rusage thread_info;
+	long context_switches;
+
+	getrusage(RUSAGE_THREAD, &thread_info);
+	context_switches = thread_info.ru_nivcsw;
+	LOG(DEBUG, "%ld involuntary context switches on lcore %u",
+			context_switches, rte_lcore_id());
+
+	return context_switches;
+}
+
+static int
+reader(void *userdata __rte_unused)
+{
+	LOG(DEBUG, "%s on lcore %u", __func__, rte_lcore_id());
+	while (!stop) {
+		int32_t index;
+
+		RTE_PARRAY_FOREACH(&array, index)
+			trash = *RTE_PARRAY_P(elem_t, &array, index);
+	}
+	return 0;
+}
+
+static int
+test_parray(void)
+{
+	int iter;
+	int32_t index;
+	long context_switches;
+
+	stop = false;
+	rte_eal_mp_remote_launch(reader, NULL, SKIP_MAIN);
+	LOG(DEBUG, "writer on lcore %u", rte_lcore_id());
+
+	rte_parray_find_next(NULL, 0);
+	TEST_ASSERT_FAIL(rte_errno, "find from NULL did not fail");
+	rte_parray_find_next(&array, -1);
+	TEST_ASSERT_FAIL(rte_errno, "find from -1 did not fail");
+	rte_parray_find_next(&array, 0);
+	TEST_ASSERT_SUCCESS(rte_errno, "find from empty failed");
+
+	rte_parray_free(NULL, 0);
+	TEST_ASSERT_FAIL(rte_errno, "free in NULL did not fail");
+	rte_parray_free(&array, 0);
+	TEST_ASSERT_FAIL(rte_errno, "free out of range did not fail");
+
+	rte_parray_alloc(NULL, 0);
+	TEST_ASSERT_FAIL(rte_errno, "alloc in NULL did not fail");
+	for (iter = 0; iter < 127; iter++) {
+		index = rte_parray_alloc(&array, sizeof(elem_t));
+		TEST_ASSERT_SUCCESS(rte_errno, "alloc returned an error");
+		TEST_ASSERT(index >= 0, "alloc returned a negative index");
+		TEST_ASSERT_EQUAL(index, iter, "alloc returned wrong index");
+	}
+
+	rte_parray_free(&array, 0);
+	TEST_ASSERT_SUCCESS(rte_errno, "free returned an error");
+	rte_parray_free(&array, 0);
+	TEST_ASSERT_SUCCESS(rte_errno, "double free returned an error");
+
+	/* alloc should increase index if possible */
+	index = rte_parray_alloc(&array, sizeof(elem_t));
+	TEST_ASSERT_SUCCESS(rte_errno, "alloc after free returned an error");
+	TEST_ASSERT_EQUAL(index, 127, "alloc after free returned wrong index");
+	/* size should be 128, almost full, forcing next element to be 0 */
+	index = rte_parray_alloc(&array, sizeof(elem_t));
+	TEST_ASSERT_SUCCESS(rte_errno, "alloc freed 0 returned an error");
+	TEST_ASSERT_EQUAL(index, 0, "alloc freed 0 returned wrong index");
+
+	/* try more race with readers */
+	context_switches = get_context_switches();
+	for (iter = 0; iter < 99; iter++) {
+		for (index = 0; index < 9999; index++) {
+			rte_parray_alloc(&array, sizeof(elem_t));
+			TEST_ASSERT_SUCCESS(rte_errno, "alloc returned an error");
+		}
+		if (get_context_switches() > context_switches + 9)
+			break;
+	}
+
+	stop = true;
+	rte_eal_mp_wait_lcore();
+
+	rte_parray_free_all(&array);
+	TEST_ASSERT_SUCCESS(rte_errno, "free all returned an error");
+
+	return TEST_SUCCESS;
+}
+
+REGISTER_TEST_COMMAND(parray_autotest, test_parray);
diff --git a/lib/eal/common/meson.build b/lib/eal/common/meson.build
index edfca77779..d44f325ad5 100644
--- a/lib/eal/common/meson.build
+++ b/lib/eal/common/meson.build
@@ -77,6 +77,7 @@ sources += files(
         'malloc_mp.c',
         'rte_keepalive.c',
         'rte_malloc.c',
+        'rte_parray.c',
         'rte_random.c',
         'rte_reciprocal.c',
         'rte_service.c',
diff --git a/lib/eal/common/rte_parray.c b/lib/eal/common/rte_parray.c
new file mode 100644
index 0000000000..5fac341773
--- /dev/null
+++ b/lib/eal/common/rte_parray.c
@@ -0,0 +1,161 @@
+/* SPDX-License-Identifier: BSD-3-Clause
+ * Copyright (c) 2021 NVIDIA Corporation & Affiliates
+ */
+
+#include <stdlib.h>
+#include <string.h>
+#include <errno.h>
+
+#include <rte_branch_prediction.h>
+#include <rte_common.h>
+#include <rte_atomic.h>
+#include <rte_errno.h>
+
+#include "rte_parray.h"
+
+#define PARRAY_DEFAULT_SIZE 32
+
+int32_t
+rte_parray_find_next(struct rte_parray *obj, int32_t index)
+{
+	if (obj == NULL || index < 0) {
+		rte_errno = EINVAL;
+		return -1;
+	}
+
+	pthread_mutex_lock(&obj->mutex);
+
+	while (index < obj->size && obj->array[index] == NULL)
+		index++;
+	if (index >= obj->size)
+		index = -1;
+
+	pthread_mutex_unlock(&obj->mutex);
+
+	rte_errno = 0;
+	return index;
+}
+
+static int32_t
+parray_find_next_free(const struct rte_parray *obj, int32_t index)
+{
+	while (index < obj->size && obj->array[index] != NULL)
+		index++;
+	if (index >= obj->size)
+		return -1;
+	return index;
+}
+
+static int
+parray_resize(struct rte_parray *obj)
+{
+	void **new_array;
+	int32_t new_size;
+	int32_t index;
+
+	if (unlikely(obj->size > INT32_MAX / 2))
+		return -1;
+
+	/* allocate a new array with bigger size */
+	new_size = RTE_MAX(PARRAY_DEFAULT_SIZE, obj->size * 2);
+	new_array = malloc(sizeof(void *) * new_size);
+	if (new_array == NULL)
+		return -1;
+
+	/* free array of a previous resize */
+	free(obj->old_array);
+	/* save current array for freeing on next resize */
+	obj->old_array = obj->array;
+
+	/* copy current array in the new one */
+	for (index = 0; index < obj->size; index++)
+		new_array[index] = obj->old_array[index];
+	/* initialize expanded part */
+	memset(new_array + index, 0, sizeof(void *) * (new_size - index));
+
+	/*
+	 * Array readers have no guard/barrier/lock synchronization protection,
+	 * that's why the ordering for array replacement is critical.
+	 */
+	/* new array must be initialized before replacing old array */
+	rte_atomic_thread_fence(__ATOMIC_RELEASE);
+	obj->array = new_array;
+	/* array must be replaced before updating the size */
+	rte_atomic_thread_fence(__ATOMIC_RELEASE);
+	obj->size = new_size;
+
+	return 0;
+}
+
+int32_t
+rte_parray_alloc(struct rte_parray *obj, size_t elem_size)
+{
+	int32_t index;
+	void *elem;
+
+	if (obj == NULL) {
+		rte_errno = EINVAL;
+		return -rte_errno;
+	}
+
+	pthread_mutex_lock(&obj->mutex);
+
+	if (obj->count == obj->size && parray_resize(obj) != 0) {
+		rte_errno = ENOMEM;
+		return -rte_errno;
+	}
+
+	elem = malloc(elem_size);
+	if (elem == NULL) {
+		rte_errno = ENOMEM;
+		return -rte_errno;
+	}
+
+	index = parray_find_next_free(obj, obj->last + 1);
+	if (index < 0)
+		index = parray_find_next_free(obj, 0);
+
+	obj->array[index] = elem;
+	obj->count++;
+	obj->last = index;
+
+	pthread_mutex_unlock(&obj->mutex);
+
+	rte_errno = 0;
+	return index;
+}
+
+void
+rte_parray_free(struct rte_parray *obj, int32_t index)
+{
+	if (obj == NULL || index < 0 || index > obj->last) {
+		rte_errno = EINVAL;
+		return;
+	}
+
+	pthread_mutex_lock(&obj->mutex);
+
+	if (obj->array[index] != NULL) {
+		free(obj->array[index]);
+		obj->array[index] = NULL;
+		obj->count--;
+	}
+
+	pthread_mutex_unlock(&obj->mutex);
+
+	rte_errno = 0;
+}
+
+void
+rte_parray_free_all(struct rte_parray *obj)
+{
+	int32_t index;
+	int first_errno = 0;
+
+	RTE_PARRAY_FOREACH(obj, index) {
+		rte_parray_free(obj, index);
+		if (rte_errno != 0 && first_errno == 0)
+			first_errno = rte_errno;
+	}
+	rte_errno = first_errno;
+}
diff --git a/lib/eal/include/meson.build b/lib/eal/include/meson.build
index 88a9eba12f..7e563b004d 100644
--- a/lib/eal/include/meson.build
+++ b/lib/eal/include/meson.build
@@ -30,6 +30,7 @@ headers += files(
         'rte_malloc.h',
         'rte_memory.h',
         'rte_memzone.h',
+        'rte_parray.h',
         'rte_pci_dev_feature_defs.h',
         'rte_pci_dev_features.h',
         'rte_per_lcore.h',
diff --git a/lib/eal/include/rte_parray.h b/lib/eal/include/rte_parray.h
new file mode 100644
index 0000000000..b7637d03ef
--- /dev/null
+++ b/lib/eal/include/rte_parray.h
@@ -0,0 +1,138 @@
+/* SPDX-License-Identifier: BSD-3-Clause
+ * Copyright (c) 2021 NVIDIA Corporation & Affiliates
+ */
+
+#ifndef RTE_PARRAY_H
+#define RTE_PARRAY_H
+
+#include <stddef.h>
+#include <stdint.h>
+#include <pthread.h>
+
+#include <rte_compat.h>
+
+/**
+ * @file
+ * Object containing a resizable array of pointers.
+ *
+ * The write operations (alloc/free) are protected by mutex.
+ * The read operation (dereference) is considered as fast path
+ * and is not directly protected.
+ *
+ * On resize, the array n-1 is kept to allow pending reads.
+ * After 2 resizes, the array n-2 is freed.
+ *
+ * Iterating (rte_parray_find_next) is safe during alloc/free.
+ *
+ * Freeing must be synchronized with readers:
+ * an element must not be accessed if it is being freed.
+ *
+ * @warning
+ * Because of above limitations, this API is for internal use.
+ */
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+/** Main object representing a dynamic array of pointers. */
+struct rte_parray {
+	/** Array of pointer to dynamically allocated struct. */
+	void **array;
+	/** Old array before resize, freed on next resize. */
+	void **old_array;
+	/* Lock for alloc/free operations. */
+	pthread_mutex_t mutex;
+	/** Current size of the full array. */
+	int32_t size;
+	/** Number of allocated elements. */
+	int32_t count;
+	/** Last allocated element. */
+	int32_t last;
+};
+
+/** Static initializer to assign. */
+#define RTE_PARRAY_INITIALIZER {NULL, NULL, PTHREAD_MUTEX_INITIALIZER, 0, 0, -1}
+
+/** Helper for access to the typed pointer of the element at index. */
+#define RTE_PARRAY_P(type, obj, index) ((type *)(obj)->array[index])
+
+/** Loop helper to iterate all elements. */
+#define RTE_PARRAY_FOREACH(obj, index) for ( \
+	index = rte_parray_find_next(obj, 0); \
+	index > 0; \
+	index = rte_parray_find_next(obj, index + 1))
+
+/**
+ * @warning
+ * This internal API may change without prior notice.
+ *
+ * Get the next pointer in the array.
+ *
+ * @param obj
+ *   Pointer to the main object.
+ * @param index
+ *   The initial index to start the research.
+ *
+ * @return
+ *   Index of the next allocated element,
+ *   -1 if there is none.
+ *   rte_errno is set to EINVAL if parameters are NULL or negative.
+ */
+__rte_internal
+int32_t rte_parray_find_next(struct rte_parray *obj, int32_t index);
+
+/**
+ * @warning
+ * This internal API may change without prior notice.
+ *
+ * Allocate an element and insert it into the array.
+ *
+ * @param obj
+ *   Pointer to the main object.
+ * @param elem_size
+ *   Number of bytes to allocate for the element.
+ *   Do nothing if requesting 0.
+ *
+ * @return
+ *   An index in the array, otherwise the negative rte_errno:
+ *   - EINVAL if array is NULL
+ *   - ENOMEM if out of space
+ */
+__rte_internal
+int32_t rte_parray_alloc(struct rte_parray *obj, size_t elem_size);
+
+/**
+ * @warning
+ * This internal API may change without prior notice.
+ *
+ * Free an element and remove it from the array.
+ *
+ * @param obj
+ *   Pointer to the main object.
+ * @param index
+ *   Index of the element to be freed.
+ *   Do nothing if not a valid element.
+ *
+ * rte_errno is set to EINVAL if a parameter is out of range.
+ */
+__rte_internal
+void rte_parray_free(struct rte_parray *obj, int32_t index);
+
+/**
+ * @warning
+ * This internal API may change without prior notice.
+ *
+ * Free all elements of an array.
+ *
+ * @param obj
+ *   Pointer to the main object.
+ */
+__rte_internal
+void rte_parray_free_all(struct rte_parray *obj);
+
+#ifdef __cplusplus
+}
+#endif
+
+#endif /* RTE_PARRAY_H */
diff --git a/lib/eal/version.map b/lib/eal/version.map
index fe5c3dac98..5fd13884b1 100644
--- a/lib/eal/version.map
+++ b/lib/eal/version.map
@@ -432,4 +432,8 @@ INTERNAL {
 	rte_mem_map;
 	rte_mem_page_size;
 	rte_mem_unmap;
+	rte_parray_alloc;
+	rte_parray_find_next;
+	rte_parray_free;
+	rte_parray_free_all;
 };
-- 
2.31.1