From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mails.dpdk.org (mails.dpdk.org [217.70.189.124]) by inbox.dpdk.org (Postfix) with ESMTP id C9973A0C44; Mon, 14 Jun 2021 12:59:08 +0200 (CEST) Received: from [217.70.189.124] (localhost [127.0.0.1]) by mails.dpdk.org (Postfix) with ESMTP id 463BB4067A; Mon, 14 Jun 2021 12:59:08 +0200 (CEST) Received: from out5-smtp.messagingengine.com (out5-smtp.messagingengine.com [66.111.4.29]) by mails.dpdk.org (Postfix) with ESMTP id 53DD64003F for ; Mon, 14 Jun 2021 12:59:07 +0200 (CEST) Received: from compute5.internal (compute5.nyi.internal [10.202.2.45]) by mailout.nyi.internal (Postfix) with ESMTP id DA34A5C01A3; Mon, 14 Jun 2021 06:59:04 -0400 (EDT) Received: from mailfrontend2 ([10.202.2.163]) by compute5.internal (MEProxy); Mon, 14 Jun 2021 06:59:04 -0400 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=monjalon.net; h= from:to:cc:subject:date:message-id:mime-version :content-transfer-encoding; s=fm1; bh=534zrP6tnDXvV+AzZtoD8//uu4 mAsTk4wcBZ6URmOH4=; b=A5kUQDODX1KtHMas4TSDigQn1JTvzMVlri5GDrckcf 1aai4lIv9hl1ApWq81DE3YCeJEWKvEyf1RZusHb0wgtR6N4wC4AsE6AUZMqWse6Q 3ndRjINNyxhPEXr4qy6hg6mq9lOhVWi41tamZTzkeXkYXUAkWkniA872nrGJ33Zd BR93ZNX5aNnUN8RahWuJPCScymjhjOuoJLfO5Eij1IkWaotNnzJoGLjK59ruoQ84 dpiTVf6qnYHv21LoSv+QSNmdXZG8qaJasD9boV5Jhv5rvWlL3rQHEWgWq2N3XuwD NsHofdC+q5C4ALULm/gYhOlhJokZfUsMFtMGn/5quoxQ== DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d= messagingengine.com; h=cc:content-transfer-encoding:date:from :message-id:mime-version:subject:to:x-me-proxy:x-me-proxy :x-me-sender:x-me-sender:x-sasl-enc; s=fm3; bh=534zrP6tnDXvV+AzZ toD8//uu4mAsTk4wcBZ6URmOH4=; b=n1AM/CnoVUQPwMwzPKEiwgVYxYsvYDND7 jlcz0nHXNKFE9ZnD2ACo7HlGKya3YLkpPRrYytRAqkhQb4+1BKbMES/9NlZuocfJ rb2k9h8NRIuk1l3Ra7yrOR428IbZKRYnHZ7iPeqen4MAnE9e3gVBe2nS81DMuY7g 8v3zX51Pa54oyGftRY8RBcsWDmhrzDGVSQzVi5OYOlQOreicn31BN/qbGHcvhkud N2buRCdtfNTZVlhI96qB1TxPQpW+3dMkQ6/4GquPohl1lNch4ePlop5yZr7Rm5IM EUtTDl6nIY+jrY1K4E0WZ7u18r9s11n6HImEDb/3JwF07leG+/OHw== X-ME-Sender: X-ME-Received: X-ME-Proxy-Cause: gggruggvucftvghtrhhoucdtuddrgeduledrfedvhedgfedtucetufdoteggodetrfdotf fvucfrrhhofhhilhgvmecuhfgrshhtofgrihhlpdfqfgfvpdfurfetoffkrfgpnffqhgen uceurghilhhouhhtmecufedttdenucenucfjughrpefhvffufffkofgggfestdekredtre dttdenucfhrhhomhepvfhhohhmrghsucfoohhnjhgrlhhonhcuoehthhhomhgrshesmhho nhhjrghlohhnrdhnvghtqeenucggtffrrghtthgvrhhnpedvledvudehvdduudevuedvve ehgeduleegiefgjeehudehtddtgeduffejiefhgfenucevlhhushhtvghrufhiiigvpedt necurfgrrhgrmhepmhgrihhlfhhrohhmpehthhhomhgrshesmhhonhhjrghlohhnrdhnvg ht X-ME-Proxy: Received: by mail.messagingengine.com (Postfix) with ESMTPA; Mon, 14 Jun 2021 06:59:03 -0400 (EDT) From: Thomas Monjalon To: dev@dpdk.org Cc: olivier.matz@6wind.com, andrew.rybchenko@oktetlabs.ru, honnappa.nagarahalli@arm.com, konstantin.ananyev@intel.com, bruce.richardson@intel.com, ferruh.yigit@intel.com, jerinj@marvell.com, gakhil@marvell.com Date: Mon, 14 Jun 2021 12:58:39 +0200 Message-Id: <20210614105839.3379790-1-thomas@monjalon.net> X-Mailer: git-send-email 2.31.1 MIME-Version: 1.0 Content-Transfer-Encoding: 8bit Subject: [dpdk-dev] [PATCH] parray: introduce internal API for dynamic arrays X-BeenThere: dev@dpdk.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: DPDK patches and discussions List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: dev-bounces@dpdk.org Sender: "dev" 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 --- 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 +#include + +#include +#include +#include +#include + +#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 +#include +#include + +#include +#include +#include +#include + +#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 +#include +#include + +#include + +/** + * @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