Patch Detail
get:
Show a patch.
patch:
Update a patch.
put:
Update a patch.
GET /api/patches/52231/?format=api
{ "id": 52231, "url": "http://patches.dpdk.org/api/patches/52231/?format=api", "web_url": "http://patches.dpdk.org/project/dpdk/patch/20190403200916.16349-6-gage.eads@intel.com/", "project": { "id": 1, "url": "http://patches.dpdk.org/api/projects/1/?format=api", "name": "DPDK", "link_name": "dpdk", "list_id": "dev.dpdk.org", "list_email": "dev@dpdk.org", "web_url": "http://core.dpdk.org", "scm_url": "git://dpdk.org/dpdk", "webscm_url": "http://git.dpdk.org/dpdk", "list_archive_url": "https://inbox.dpdk.org/dev", "list_archive_url_format": "https://inbox.dpdk.org/dev/{}", "commit_url_format": "" }, "msgid": "<20190403200916.16349-6-gage.eads@intel.com>", "list_archive_url": "https://inbox.dpdk.org/dev/20190403200916.16349-6-gage.eads@intel.com", "date": "2019-04-03T20:09:13", "name": "[v7,5/8] stack: add lock-free stack implementation", "commit_ref": null, "pull_url": null, "state": "superseded", "archived": true, "hash": "9d390651291c2d930cdde349ec5235623cbd926c", "submitter": { "id": 586, "url": "http://patches.dpdk.org/api/people/586/?format=api", "name": "Eads, Gage", "email": "gage.eads@intel.com" }, "delegate": null, "mbox": "http://patches.dpdk.org/project/dpdk/patch/20190403200916.16349-6-gage.eads@intel.com/mbox/", "series": [ { "id": 4101, "url": "http://patches.dpdk.org/api/series/4101/?format=api", "web_url": "http://patches.dpdk.org/project/dpdk/list/?series=4101", "date": "2019-04-03T20:09:08", "name": "Add stack library and new mempool handler", "version": 7, "mbox": "http://patches.dpdk.org/series/4101/mbox/" } ], "comments": "http://patches.dpdk.org/api/patches/52231/comments/", "check": "success", "checks": "http://patches.dpdk.org/api/patches/52231/checks/", "tags": {}, "related": [], "headers": { "Return-Path": "<dev-bounces@dpdk.org>", "X-Original-To": "patchwork@dpdk.org", "Delivered-To": "patchwork@dpdk.org", "Received": [ "from [92.243.14.124] (localhost [127.0.0.1])\n\tby dpdk.org (Postfix) with ESMTP id 488A11B44E;\n\tWed, 3 Apr 2019 22:10:23 +0200 (CEST)", "from mga01.intel.com (mga01.intel.com [192.55.52.88])\n\tby dpdk.org (Postfix) with ESMTP id 2A6606CC1\n\tfor <dev@dpdk.org>; Wed, 3 Apr 2019 22:10:04 +0200 (CEST)", "from orsmga007.jf.intel.com ([10.7.209.58])\n\tby fmsmga101.fm.intel.com with ESMTP/TLS/DHE-RSA-AES256-GCM-SHA384;\n\t03 Apr 2019 13:10:03 -0700", "from txasoft-yocto.an.intel.com ([10.123.72.192])\n\tby orsmga007.jf.intel.com with ESMTP; 03 Apr 2019 13:10:02 -0700" ], "X-Amp-Result": "SKIPPED(no attachment in message)", "X-Amp-File-Uploaded": "False", "X-ExtLoop1": "1", "X-IronPort-AV": "E=Sophos;i=\"5.60,306,1549958400\"; d=\"scan'208\";a=\"128403728\"", "From": "Gage Eads <gage.eads@intel.com>", "To": "dev@dpdk.org", "Cc": "olivier.matz@6wind.com, arybchenko@solarflare.com,\n\tbruce.richardson@intel.com, konstantin.ananyev@intel.com,\n\tgavin.hu@arm.com, \n\tHonnappa.Nagarahalli@arm.com, nd@arm.com, thomas@monjalon.net", "Date": "Wed, 3 Apr 2019 15:09:13 -0500", "Message-Id": "<20190403200916.16349-6-gage.eads@intel.com>", "X-Mailer": "git-send-email 2.13.6", "In-Reply-To": "<20190403200916.16349-1-gage.eads@intel.com>", "References": "<20190401211429.20282-1-gage.eads@intel.com>\n\t<20190403200916.16349-1-gage.eads@intel.com>", "Subject": "[dpdk-dev] [PATCH v7 5/8] stack: add lock-free stack implementation", "X-BeenThere": "dev@dpdk.org", "X-Mailman-Version": "2.1.15", "Precedence": "list", "List-Id": "DPDK patches and discussions <dev.dpdk.org>", "List-Unsubscribe": "<https://mails.dpdk.org/options/dev>,\n\t<mailto:dev-request@dpdk.org?subject=unsubscribe>", "List-Archive": "<http://mails.dpdk.org/archives/dev/>", "List-Post": "<mailto:dev@dpdk.org>", "List-Help": "<mailto:dev-request@dpdk.org?subject=help>", "List-Subscribe": "<https://mails.dpdk.org/listinfo/dev>,\n\t<mailto:dev-request@dpdk.org?subject=subscribe>", "Errors-To": "dev-bounces@dpdk.org", "Sender": "\"dev\" <dev-bounces@dpdk.org>" }, "content": "This commit adds support for a lock-free (linked list based) stack to the\nstack API. This behavior is selected through a new rte_stack_create() flag,\nRTE_STACK_F_LF.\n\nThe stack consists of a linked list of elements, each containing a data\npointer and a next pointer, and an atomic stack depth counter.\n\nThe lock-free push operation enqueues a linked list of pointers by pointing\nthe tail of the list to the current stack head, and using a CAS to swing\nthe stack head pointer to the head of the list. The operation retries if it\nis unsuccessful (i.e. the list changed between reading the head and\nmodifying it), else it adjusts the stack length and returns.\n\nThe lock-free pop operation first reserves num elements by adjusting the\nstack length, to ensure the dequeue operation will succeed without\nblocking. It then dequeues pointers by walking the list -- starting from\nthe head -- then swinging the head pointer (using a CAS as well). While\nwalking the list, the data pointers are recorded in an object table.\n\nThis algorithm stack uses a 128-bit compare-and-swap instruction, which\natomically updates the stack top pointer and a modification counter, to\nprotect against the ABA problem.\n\nThe linked list elements themselves are maintained in a lock-free LIFO\nlist, and are allocated before stack pushes and freed after stack pops.\nSince the stack has a fixed maximum depth, these elements do not need to be\ndynamically created.\n\nSigned-off-by: Gage Eads <gage.eads@intel.com>\nReviewed-by: Olivier Matz <olivier.matz@6wind.com>\nReviewed-by: Honnappa Nagarahalli <honnappa.nagarahalli@arm.com>\n---\n doc/guides/prog_guide/stack_lib.rst | 61 +++++++++++-\n doc/guides/rel_notes/release_19_05.rst | 3 +\n lib/librte_stack/Makefile | 7 +-\n lib/librte_stack/meson.build | 7 +-\n lib/librte_stack/rte_stack.c | 28 ++++--\n lib/librte_stack/rte_stack.h | 62 +++++++++++-\n lib/librte_stack/rte_stack_lf.c | 31 ++++++\n lib/librte_stack/rte_stack_lf.h | 102 ++++++++++++++++++++\n lib/librte_stack/rte_stack_lf_generic.h | 164 ++++++++++++++++++++++++++++++++\n 9 files changed, 446 insertions(+), 19 deletions(-)\n create mode 100644 lib/librte_stack/rte_stack_lf.c\n create mode 100644 lib/librte_stack/rte_stack_lf.h\n create mode 100644 lib/librte_stack/rte_stack_lf_generic.h", "diff": "diff --git a/doc/guides/prog_guide/stack_lib.rst b/doc/guides/prog_guide/stack_lib.rst\nindex 25a8cc38a..8fe8804e3 100644\n--- a/doc/guides/prog_guide/stack_lib.rst\n+++ b/doc/guides/prog_guide/stack_lib.rst\n@@ -10,7 +10,8 @@ stack of pointers.\n The stack library provides the following basic operations:\n \n * Create a uniquely named stack of a user-specified size and using a\n- user-specified socket.\n+ user-specified socket, with either standard (lock-based) or lock-free\n+ behavior.\n \n * Push and pop a burst of one or more stack objects (pointers). These function\n are multi-threading safe.\n@@ -24,5 +25,59 @@ The stack library provides the following basic operations:\n Implementation\n ~~~~~~~~~~~~~~\n \n-The stack consists of a contiguous array of pointers, a current index, and a\n-spinlock. Accesses to the stack are made multi-thread safe by the spinlock.\n+The library supports two types of stacks: standard (lock-based) and lock-free.\n+Both types use the same set of interfaces, but their implementations differ.\n+\n+Lock-based Stack\n+----------------\n+\n+The lock-based stack consists of a contiguous array of pointers, a current\n+index, and a spinlock. Accesses to the stack are made multi-thread safe by the\n+spinlock.\n+\n+Lock-free Stack\n+------------------\n+\n+The lock-free stack consists of a linked list of elements, each containing a\n+data pointer and a next pointer, and an atomic stack depth counter. The\n+lock-free property means that multiple threads can push and pop simultaneously,\n+and one thread being preempted/delayed in a push or pop operation will not\n+impede the forward progress of any other thread.\n+\n+The lock-free push operation enqueues a linked list of pointers by pointing the\n+list's tail to the current stack head, and using a CAS to swing the stack head\n+pointer to the head of the list. The operation retries if it is unsuccessful\n+(i.e. the list changed between reading the head and modifying it), else it\n+adjusts the stack length and returns.\n+\n+The lock-free pop operation first reserves one or more list elements by\n+adjusting the stack length, to ensure the dequeue operation will succeed\n+without blocking. It then dequeues pointers by walking the list -- starting\n+from the head -- then swinging the head pointer (using a CAS as well). While\n+walking the list, the data pointers are recorded in an object table.\n+\n+The linked list elements themselves are maintained in a lock-free LIFO, and are\n+allocated before stack pushes and freed after stack pops. Since the stack has a\n+fixed maximum depth, these elements do not need to be dynamically created.\n+\n+The lock-free behavior is selected by passing the *RTE_STACK_F_LF* flag to\n+rte_stack_create().\n+\n+Preventing the ABA Problem\n+^^^^^^^^^^^^^^^^^^^^^^^^^^\n+\n+To prevent the ABA problem, this algorithm stack uses a 128-bit\n+compare-and-swap instruction to atomically update both the stack top pointer\n+and a modification counter. The ABA problem can occur without a modification\n+counter if, for example:\n+\n+1. Thread A reads head pointer X and stores the pointed-to list element.\n+2. Other threads modify the list such that the head pointer is once again X,\n+ but its pointed-to data is different than what thread A read.\n+3. Thread A changes the head pointer with a compare-and-swap and succeeds.\n+\n+In this case thread A would not detect that the list had changed, and would\n+both pop stale data and incorrect change the head pointer. By adding a\n+modification counter that is updated on every push and pop as part of the\n+compare-and-swap, the algorithm can detect when the list changes even if the\n+head pointer remains the same.\ndiff --git a/doc/guides/rel_notes/release_19_05.rst b/doc/guides/rel_notes/release_19_05.rst\nindex ebfbe36e5..3b115b5f6 100644\n--- a/doc/guides/rel_notes/release_19_05.rst\n+++ b/doc/guides/rel_notes/release_19_05.rst\n@@ -127,6 +127,9 @@ New Features\n pointers. The API provides MT-safe push and pop operations that can operate\n on one or more pointers per operation.\n \n+ The library supports two stack implementations: standard (lock-based) and lock-free.\n+ The lock-free implementation is currently limited to x86-64 platforms.\n+\n Removed Items\n -------------\n \ndiff --git a/lib/librte_stack/Makefile b/lib/librte_stack/Makefile\nindex 6db540073..311edd997 100644\n--- a/lib/librte_stack/Makefile\n+++ b/lib/librte_stack/Makefile\n@@ -16,10 +16,13 @@ LIBABIVER := 1\n \n # all source are stored in SRCS-y\n SRCS-$(CONFIG_RTE_LIBRTE_STACK) := rte_stack.c \\\n-\t\t\t\t rte_stack_std.c\n+\t\t\t\t rte_stack_std.c \\\n+\t\t\t\t rte_stack_lf.c\n \n # install includes\n SYMLINK-$(CONFIG_RTE_LIBRTE_STACK)-include := rte_stack.h \\\n-\t\t\t\t\t rte_stack_std.h\n+\t\t\t\t\t rte_stack_std.h \\\n+\t\t\t\t\t rte_stack_lf.h \\\n+\t\t\t\t\t rte_stack_lf_generic.h\n \n include $(RTE_SDK)/mk/rte.lib.mk\ndiff --git a/lib/librte_stack/meson.build b/lib/librte_stack/meson.build\nindex d2e60ce9b..7a09a5d66 100644\n--- a/lib/librte_stack/meson.build\n+++ b/lib/librte_stack/meson.build\n@@ -4,5 +4,8 @@\n allow_experimental_apis = true\n \n version = 1\n-sources = files('rte_stack.c', 'rte_stack_std.c')\n-headers = files('rte_stack.h', 'rte_stack_std.h')\n+sources = files('rte_stack.c', 'rte_stack_std.c', 'rte_stack_lf.c')\n+headers = files('rte_stack.h',\n+\t\t'rte_stack_std.h',\n+\t\t'rte_stack_lf.h',\n+\t\t'rte_stack_lf_generic.h')\ndiff --git a/lib/librte_stack/rte_stack.c b/lib/librte_stack/rte_stack.c\nindex 610014b6c..1a4d9bd1e 100644\n--- a/lib/librte_stack/rte_stack.c\n+++ b/lib/librte_stack/rte_stack.c\n@@ -25,18 +25,25 @@ static struct rte_tailq_elem rte_stack_tailq = {\n };\n EAL_REGISTER_TAILQ(rte_stack_tailq)\n \n+\n static void\n-rte_stack_init(struct rte_stack *s)\n+rte_stack_init(struct rte_stack *s, unsigned int count, uint32_t flags)\n {\n \tmemset(s, 0, sizeof(*s));\n \n-\trte_stack_std_init(s);\n+\tif (flags & RTE_STACK_F_LF)\n+\t\trte_stack_lf_init(s, count);\n+\telse\n+\t\trte_stack_std_init(s);\n }\n \n static ssize_t\n-rte_stack_get_memsize(unsigned int count)\n+rte_stack_get_memsize(unsigned int count, uint32_t flags)\n {\n-\treturn rte_stack_std_get_memsize(count);\n+\tif (flags & RTE_STACK_F_LF)\n+\t\treturn rte_stack_lf_get_memsize(count);\n+\telse\n+\t\treturn rte_stack_std_get_memsize(count);\n }\n \n struct rte_stack *\n@@ -51,9 +58,16 @@ rte_stack_create(const char *name, unsigned int count, int socket_id,\n \tunsigned int sz;\n \tint ret;\n \n-\tRTE_SET_USED(flags);\n+#ifdef RTE_ARCH_64\n+\tRTE_BUILD_BUG_ON(sizeof(struct rte_stack_lf_head) != 16);\n+#else\n+\tif (flags & RTE_STACK_F_LF) {\n+\t\tSTACK_LOG_ERR(\"Lock-free stack is not supported on your platform\\n\");\n+\t\treturn NULL;\n+\t}\n+#endif\n \n-\tsz = rte_stack_get_memsize(count);\n+\tsz = rte_stack_get_memsize(count, flags);\n \n \tret = snprintf(mz_name, sizeof(mz_name), \"%s%s\",\n \t\t RTE_STACK_MZ_PREFIX, name);\n@@ -82,7 +96,7 @@ rte_stack_create(const char *name, unsigned int count, int socket_id,\n \n \ts = mz->addr;\n \n-\trte_stack_init(s);\n+\trte_stack_init(s, count, flags);\n \n \t/* Store the name for later lookups */\n \tret = snprintf(s->name, sizeof(s->name), \"%s\", name);\ndiff --git a/lib/librte_stack/rte_stack.h b/lib/librte_stack/rte_stack.h\nindex cebb5be13..54e795682 100644\n--- a/lib/librte_stack/rte_stack.h\n+++ b/lib/librte_stack/rte_stack.h\n@@ -31,6 +31,35 @@ extern \"C\" {\n #define RTE_STACK_NAMESIZE (RTE_MEMZONE_NAMESIZE - \\\n \t\t\t sizeof(RTE_STACK_MZ_PREFIX) + 1)\n \n+struct rte_stack_lf_elem {\n+\tvoid *data;\t\t\t/**< Data pointer */\n+\tstruct rte_stack_lf_elem *next;\t/**< Next pointer */\n+};\n+\n+struct rte_stack_lf_head {\n+\tstruct rte_stack_lf_elem *top; /**< Stack top */\n+\tuint64_t cnt; /**< Modification counter for avoiding ABA problem */\n+};\n+\n+struct rte_stack_lf_list {\n+\t/** List head */\n+\tstruct rte_stack_lf_head head __rte_aligned(16);\n+\t/** List len */\n+\trte_atomic64_t len;\n+};\n+\n+/* Structure containing two lock-free LIFO lists: the stack itself and a list\n+ * of free linked-list elements.\n+ */\n+struct rte_stack_lf {\n+\t/** LIFO list of elements */\n+\tstruct rte_stack_lf_list used __rte_cache_aligned;\n+\t/** LIFO list of free elements */\n+\tstruct rte_stack_lf_list free __rte_cache_aligned;\n+\t/** LIFO elements */\n+\tstruct rte_stack_lf_elem elems[] __rte_cache_aligned;\n+};\n+\n /* Structure containing the LIFO, its current length, and a lock for mutual\n * exclusion.\n */\n@@ -50,10 +79,21 @@ struct rte_stack {\n \tconst struct rte_memzone *memzone;\n \tuint32_t capacity; /**< Usable size of the stack. */\n \tuint32_t flags; /**< Flags supplied at creation. */\n-\tstruct rte_stack_std stack_std; /**< LIFO structure. */\n+\tRTE_STD_C11\n+\tunion {\n+\t\tstruct rte_stack_lf stack_lf; /**< Lock-free LIFO structure. */\n+\t\tstruct rte_stack_std stack_std;\t/**< LIFO structure. */\n+\t};\n } __rte_cache_aligned;\n \n+/**\n+ * The stack uses lock-free push and pop functions. This flag is only\n+ * supported on x86_64 platforms, currently.\n+ */\n+#define RTE_STACK_F_LF 0x0001\n+\n #include \"rte_stack_std.h\"\n+#include \"rte_stack_lf.h\"\n \n /**\n * @warning\n@@ -76,7 +116,10 @@ rte_stack_push(struct rte_stack *s, void * const *obj_table, unsigned int n)\n \tRTE_ASSERT(s != NULL);\n \tRTE_ASSERT(obj_table != NULL);\n \n-\treturn __rte_stack_std_push(s, obj_table, n);\n+\tif (s->flags & RTE_STACK_F_LF)\n+\t\treturn __rte_stack_lf_push(s, obj_table, n);\n+\telse\n+\t\treturn __rte_stack_std_push(s, obj_table, n);\n }\n \n /**\n@@ -100,7 +143,10 @@ rte_stack_pop(struct rte_stack *s, void **obj_table, unsigned int n)\n \tRTE_ASSERT(s != NULL);\n \tRTE_ASSERT(obj_table != NULL);\n \n-\treturn __rte_stack_std_pop(s, obj_table, n);\n+\tif (s->flags & RTE_STACK_F_LF)\n+\t\treturn __rte_stack_lf_pop(s, obj_table, n);\n+\telse\n+\t\treturn __rte_stack_std_pop(s, obj_table, n);\n }\n \n /**\n@@ -119,7 +165,10 @@ rte_stack_count(struct rte_stack *s)\n {\n \tRTE_ASSERT(s != NULL);\n \n-\treturn __rte_stack_std_count(s);\n+\tif (s->flags & RTE_STACK_F_LF)\n+\t\treturn __rte_stack_lf_count(s);\n+\telse\n+\t\treturn __rte_stack_std_count(s);\n }\n \n /**\n@@ -159,7 +208,10 @@ rte_stack_free_count(struct rte_stack *s)\n * NUMA. The value can be *SOCKET_ID_ANY* if there is no NUMA\n * constraint for the reserved zone.\n * @param flags\n- * Reserved for future use.\n+ * An OR of the following:\n+ * - RTE_STACK_F_LF: If this flag is set, the stack uses lock-free\n+ * variants of the push and pop functions. Otherwise, it achieves\n+ * thread-safety using a lock.\n * @return\n * On success, the pointer to the new allocated stack. NULL on error with\n * rte_errno set appropriately. Possible errno values include:\ndiff --git a/lib/librte_stack/rte_stack_lf.c b/lib/librte_stack/rte_stack_lf.c\nnew file mode 100644\nindex 000000000..0adcc263e\n--- /dev/null\n+++ b/lib/librte_stack/rte_stack_lf.c\n@@ -0,0 +1,31 @@\n+/* SPDX-License-Identifier: BSD-3-Clause\n+ * Copyright(c) 2019 Intel Corporation\n+ */\n+\n+#include \"rte_stack.h\"\n+\n+void\n+rte_stack_lf_init(struct rte_stack *s, unsigned int count)\n+{\n+\tstruct rte_stack_lf_elem *elems = s->stack_lf.elems;\n+\tunsigned int i;\n+\n+\tfor (i = 0; i < count; i++)\n+\t\t__rte_stack_lf_push_elems(&s->stack_lf.free,\n+\t\t\t\t\t &elems[i], &elems[i], 1);\n+}\n+\n+ssize_t\n+rte_stack_lf_get_memsize(unsigned int count)\n+{\n+\tssize_t sz = sizeof(struct rte_stack);\n+\n+\tsz += RTE_CACHE_LINE_ROUNDUP(count * sizeof(struct rte_stack_lf_elem));\n+\n+\t/* Add padding to avoid false sharing conflicts caused by\n+\t * next-line hardware prefetchers.\n+\t */\n+\tsz += 2 * RTE_CACHE_LINE_SIZE;\n+\n+\treturn sz;\n+}\ndiff --git a/lib/librte_stack/rte_stack_lf.h b/lib/librte_stack/rte_stack_lf.h\nnew file mode 100644\nindex 000000000..bfd680133\n--- /dev/null\n+++ b/lib/librte_stack/rte_stack_lf.h\n@@ -0,0 +1,102 @@\n+/* SPDX-License-Identifier: BSD-3-Clause\n+ * Copyright(c) 2019 Intel Corporation\n+ */\n+\n+#ifndef _RTE_STACK_LF_H_\n+#define _RTE_STACK_LF_H_\n+\n+#include \"rte_stack_lf_generic.h\"\n+\n+/**\n+ * @internal Push several objects on the lock-free stack (MT-safe).\n+ *\n+ * @param s\n+ * A pointer to the stack structure.\n+ * @param obj_table\n+ * A pointer to a table of void * pointers (objects).\n+ * @param n\n+ * The number of objects to push on the stack from the obj_table.\n+ * @return\n+ * Actual number of objects enqueued.\n+ */\n+static __rte_always_inline unsigned int __rte_experimental\n+__rte_stack_lf_push(struct rte_stack *s,\n+\t\t void * const *obj_table,\n+\t\t unsigned int n)\n+{\n+\tstruct rte_stack_lf_elem *tmp, *first, *last = NULL;\n+\tunsigned int i;\n+\n+\tif (unlikely(n == 0))\n+\t\treturn 0;\n+\n+\t/* Pop n free elements */\n+\tfirst = __rte_stack_lf_pop_elems(&s->stack_lf.free, n, NULL, &last);\n+\tif (unlikely(first == NULL))\n+\t\treturn 0;\n+\n+\t/* Construct the list elements */\n+\tfor (tmp = first, i = 0; i < n; i++, tmp = tmp->next)\n+\t\ttmp->data = obj_table[n - i - 1];\n+\n+\t/* Push them to the used list */\n+\t__rte_stack_lf_push_elems(&s->stack_lf.used, first, last, n);\n+\n+\treturn n;\n+}\n+\n+/**\n+ * @internal Pop several objects from the lock-free stack (MT-safe).\n+ *\n+ * @param s\n+ * A pointer to the stack structure.\n+ * @param obj_table\n+ * A pointer to a table of void * pointers (objects).\n+ * @param n\n+ * The number of objects to pull from the stack.\n+ * @return\n+ * - Actual number of objects popped.\n+ */\n+static __rte_always_inline unsigned int __rte_experimental\n+__rte_stack_lf_pop(struct rte_stack *s, void **obj_table, unsigned int n)\n+{\n+\tstruct rte_stack_lf_elem *first, *last = NULL;\n+\n+\tif (unlikely(n == 0))\n+\t\treturn 0;\n+\n+\t/* Pop n used elements */\n+\tfirst = __rte_stack_lf_pop_elems(&s->stack_lf.used,\n+\t\t\t\t\t n, obj_table, &last);\n+\tif (unlikely(first == NULL))\n+\t\treturn 0;\n+\n+\t/* Push the list elements to the free list */\n+\t__rte_stack_lf_push_elems(&s->stack_lf.free, first, last, n);\n+\n+\treturn n;\n+}\n+\n+/**\n+ * @internal Initialize a lock-free stack.\n+ *\n+ * @param s\n+ * A pointer to the stack structure.\n+ * @param count\n+ * The size of the stack.\n+ */\n+void\n+rte_stack_lf_init(struct rte_stack *s, unsigned int count);\n+\n+/**\n+ * @internal Return the memory required for a lock-free stack.\n+ *\n+ * @param count\n+ * The size of the stack.\n+ * @return\n+ * The bytes to allocate for a lock-free stack.\n+ */\n+ssize_t\n+rte_stack_lf_get_memsize(unsigned int count);\n+\n+#endif /* _RTE_STACK_LF_H_ */\ndiff --git a/lib/librte_stack/rte_stack_lf_generic.h b/lib/librte_stack/rte_stack_lf_generic.h\nnew file mode 100644\nindex 000000000..1191406d3\n--- /dev/null\n+++ b/lib/librte_stack/rte_stack_lf_generic.h\n@@ -0,0 +1,164 @@\n+/* SPDX-License-Identifier: BSD-3-Clause\n+ * Copyright(c) 2019 Intel Corporation\n+ */\n+\n+#ifndef _RTE_STACK_LF_GENERIC_H_\n+#define _RTE_STACK_LF_GENERIC_H_\n+\n+#include <rte_branch_prediction.h>\n+#include <rte_prefetch.h>\n+\n+static __rte_always_inline unsigned int\n+__rte_stack_lf_count(struct rte_stack *s)\n+{\n+\t/* stack_lf_push() and stack_lf_pop() do not update the list's contents\n+\t * and stack_lf->len atomically, which can cause the list to appear\n+\t * shorter than it actually is if this function is called while other\n+\t * threads are modifying the list.\n+\t *\n+\t * However, given the inherently approximate nature of the get_count\n+\t * callback -- even if the list and its size were updated atomically,\n+\t * the size could change between when get_count executes and when the\n+\t * value is returned to the caller -- this is acceptable.\n+\t *\n+\t * The stack_lf->len updates are placed such that the list may appear to\n+\t * have fewer elements than it does, but will never appear to have more\n+\t * elements. If the mempool is near-empty to the point that this is a\n+\t * concern, the user should consider increasing the mempool size.\n+\t */\n+\treturn (unsigned int)rte_atomic64_read(&s->stack_lf.used.len);\n+}\n+\n+static __rte_always_inline void\n+__rte_stack_lf_push_elems(struct rte_stack_lf_list *list,\n+\t\t\t struct rte_stack_lf_elem *first,\n+\t\t\t struct rte_stack_lf_elem *last,\n+\t\t\t unsigned int num)\n+{\n+#ifndef RTE_ARCH_X86_64\n+\tRTE_SET_USED(first);\n+\tRTE_SET_USED(last);\n+\tRTE_SET_USED(list);\n+\tRTE_SET_USED(num);\n+#else\n+\tstruct rte_stack_lf_head old_head;\n+\tint success;\n+\n+\told_head = list->head;\n+\n+\tdo {\n+\t\tstruct rte_stack_lf_head new_head;\n+\n+\t\t/* An acquire fence (or stronger) is needed for weak memory\n+\t\t * models to establish a synchronized-with relationship between\n+\t\t * the list->head load and store-release operations (as part of\n+\t\t * the rte_atomic128_cmp_exchange()).\n+\t\t */\n+\t\trte_smp_mb();\n+\n+\t\t/* Swing the top pointer to the first element in the list and\n+\t\t * make the last element point to the old top.\n+\t\t */\n+\t\tnew_head.top = first;\n+\t\tnew_head.cnt = old_head.cnt + 1;\n+\n+\t\tlast->next = old_head.top;\n+\n+\t\t/* old_head is updated on failure */\n+\t\tsuccess = rte_atomic128_cmp_exchange(\n+\t\t\t\t(rte_int128_t *)&list->head,\n+\t\t\t\t(rte_int128_t *)&old_head,\n+\t\t\t\t(rte_int128_t *)&new_head,\n+\t\t\t\t1, __ATOMIC_RELEASE,\n+\t\t\t\t__ATOMIC_RELAXED);\n+\t} while (success == 0);\n+\n+\trte_atomic64_add(&list->len, num);\n+#endif\n+}\n+\n+static __rte_always_inline struct rte_stack_lf_elem *\n+__rte_stack_lf_pop_elems(struct rte_stack_lf_list *list,\n+\t\t\t unsigned int num,\n+\t\t\t void **obj_table,\n+\t\t\t struct rte_stack_lf_elem **last)\n+{\n+#ifndef RTE_ARCH_X86_64\n+\tRTE_SET_USED(obj_table);\n+\tRTE_SET_USED(last);\n+\tRTE_SET_USED(list);\n+\tRTE_SET_USED(num);\n+\n+\treturn NULL;\n+#else\n+\tstruct rte_stack_lf_head old_head;\n+\tint success;\n+\n+\t/* Reserve num elements, if available */\n+\twhile (1) {\n+\t\tuint64_t len = rte_atomic64_read(&list->len);\n+\n+\t\t/* Does the list contain enough elements? */\n+\t\tif (unlikely(len < num))\n+\t\t\treturn NULL;\n+\n+\t\tif (rte_atomic64_cmpset((volatile uint64_t *)&list->len,\n+\t\t\t\t\tlen, len - num))\n+\t\t\tbreak;\n+\t}\n+\n+\told_head = list->head;\n+\n+\t/* Pop num elements */\n+\tdo {\n+\t\tstruct rte_stack_lf_head new_head;\n+\t\tstruct rte_stack_lf_elem *tmp;\n+\t\tunsigned int i;\n+\n+\t\t/* An acquire fence (or stronger) is needed for weak memory\n+\t\t * models to ensure the LF LIFO element reads are properly\n+\t\t * ordered with respect to the head pointer read.\n+\t\t */\n+\t\trte_smp_mb();\n+\n+\t\trte_prefetch0(old_head.top);\n+\n+\t\ttmp = old_head.top;\n+\n+\t\t/* Traverse the list to find the new head. A next pointer will\n+\t\t * either point to another element or NULL; if a thread\n+\t\t * encounters a pointer that has already been popped, the CAS\n+\t\t * will fail.\n+\t\t */\n+\t\tfor (i = 0; i < num && tmp != NULL; i++) {\n+\t\t\trte_prefetch0(tmp->next);\n+\t\t\tif (obj_table)\n+\t\t\t\tobj_table[i] = tmp->data;\n+\t\t\tif (last)\n+\t\t\t\t*last = tmp;\n+\t\t\ttmp = tmp->next;\n+\t\t}\n+\n+\t\t/* If NULL was encountered, the list was modified while\n+\t\t * traversing it. Retry.\n+\t\t */\n+\t\tif (i != num)\n+\t\t\tcontinue;\n+\n+\t\tnew_head.top = tmp;\n+\t\tnew_head.cnt = old_head.cnt + 1;\n+\n+\t\t/* old_head is updated on failure */\n+\t\tsuccess = rte_atomic128_cmp_exchange(\n+\t\t\t\t(rte_int128_t *)&list->head,\n+\t\t\t\t(rte_int128_t *)&old_head,\n+\t\t\t\t(rte_int128_t *)&new_head,\n+\t\t\t\t1, __ATOMIC_RELEASE,\n+\t\t\t\t__ATOMIC_RELAXED);\n+\t} while (success == 0);\n+\n+\treturn old_head.top;\n+#endif\n+}\n+\n+#endif /* _RTE_STACK_LF_GENERIC_H_ */\n", "prefixes": [ "v7", "5/8" ] }