Subject: [PATCH ...] Add stack library and new mempool handler
Subsystems (2)
PATCH v9 1/8 stack: introduce rte stack library
In reply to Gage EadsThe rte_stack library provides an API for configuration and use of a bounded stack of pointers. Push and pop operations are MT-safe, allowing concurrent access, and the interface supports pushing and popping multiple pointers at a time.
The library's interface is modeled after another DPDK data structure, rte_ring, and its lock-based implementation is derived from the stack mempool handler. An upcoming commit will migrate the stack mempool handler to rte_stack.
--- MAINTAINERS | 6 + config/common_base | 5 + doc/api/doxy-api-index.md | 1 + doc/api/doxy-api.conf.in | 1 + doc/guides/prog_guide/index.rst | 1 + doc/guides/prog_guide/stack_lib.rst | 28 +++++ doc/guides/rel_notes/release_19_05.rst | 5 + lib/Makefile | 2 + lib/librte_stack/Makefile | 25 ++++ lib/librte_stack/meson.build | 8 ++ lib/librte_stack/rte_stack.c | 182 ++++++++++++++++++++++++++++ lib/librte_stack/rte_stack.h | 209 +++++++++++++++++++++++++++++++++ lib/librte_stack/rte_stack_pvt.h | 34 ++++++ lib/librte_stack/rte_stack_std.c | 26 ++++ lib/librte_stack/rte_stack_std.h | 121 +++++++++++++++++++ lib/librte_stack/rte_stack_version.map | 9 ++ lib/meson.build | 2 +- mk/rte.app.mk | 1 + 18 files changed, 665 insertions(+), 1 deletion(-) create mode 100644 doc/guides/prog_guide/stack_lib.rst create mode 100644 lib/librte_stack/Makefile create mode 100644 lib/librte_stack/meson.build create mode 100644 lib/librte_stack/rte_stack.c create mode 100644 lib/librte_stack/rte_stack.h create mode 100644 lib/librte_stack/rte_stack_pvt.h create mode 100644 lib/librte_stack/rte_stack_std.c create mode 100644 lib/librte_stack/rte_stack_std.h create mode 100644 lib/librte_stack/rte_stack_version.map
MAINTAINERS +6 -0
@@ -426,6 +426,12 @@ F: drivers/raw/skeleton_rawdev/ F: app/test/test_rawdev.c F: doc/guides/prog_guide/rawdev.rst +Stack API - EXPERIMENTAL +M: Gage Eads <[email protected]> +M: Olivier Matz <[email protected]> +F: lib/librte_stack/ +F: doc/guides/prog_guide/stack_lib.rst + Memory Pool Drivers -------------------
config/common_base +5 -0
@@ -994,3 +994,8 @@ CONFIG_RTE_APP_CRYPTO_PERF=y # Compile the eventdev application # CONFIG_RTE_APP_EVENTDEV=y + +# +# Compile librte_stack +# +CONFIG_RTE_LIBRTE_STACK=y
doc/api/doxy-api-index.md +1 -0
@@ -125,6 +125,7 @@ The public API headers are grouped by topics: [mbuf] (@ref rte_mbuf.h), [mbuf pool ops] (@ref rte_mbuf_pool_ops.h), [ring] (@ref rte_ring.h), + [stack] (@ref rte_stack.h), [tailq] (@ref rte_tailq.h), [bitmap] (@ref rte_bitmap.h)
doc/api/doxy-api.conf.in +1 -0
@@ -55,6 +55,7 @@ INPUT = @TOPDIR@/doc/api/doxy-api-index.md \ @TOPDIR@/lib/librte_ring \ @TOPDIR@/lib/librte_sched \ @TOPDIR@/lib/librte_security \ + @TOPDIR@/lib/librte_stack \ @TOPDIR@/lib/librte_table \ @TOPDIR@/lib/librte_telemetry \ @TOPDIR@/lib/librte_timer \
doc/guides/prog_guide/index.rst +1 -0
@@ -55,6 +55,7 @@ Programmer's Guide metrics_lib bpf_lib ipsec_lib + stack_lib source_org dev_kit_build_system dev_kit_root_make_help
doc/guides/prog_guide/stack_lib.rst new file +28 -0
@@ -0,0 +1,28 @@ +.. SPDX-License-Identifier: BSD-3-Clause + Copyright(c) 2019 Intel Corporation. + +Stack Library +============= + +DPDK's stack library provides an API for configuration and use of a bounded +stack of pointers. + +The stack library provides the following basic operations: + +* Create a uniquely named stack of a user-specified size and using a + user-specified socket. + +* Push and pop a burst of one or more stack objects (pointers). These function + are multi-threading safe. + +* Free a previously created stack. + +* Lookup a pointer to a stack by its name. + +* Query a stack's current depth and number of free entries. + +Implementation +~~~~~~~~~~~~~~ + +The stack consists of a contiguous array of pointers, a current index, and a +spinlock. Accesses to the stack are made multi-thread safe by the spinlock.
doc/guides/rel_notes/release_19_05.rst +5 -0
@@ -121,6 +121,11 @@ New Features Improved testpmd application performance on ARM platform. For ``macswap`` forwarding mode, NEON intrinsics were used to do swap to save CPU cycles. +* **Added Stack API.** + + Added a new stack API for configuration and use of a bounded stack of + pointers. The API provides MT-safe push and pop operations that can operate + on one or more pointers per operation. Removed Items -------------
lib/Makefile +2 -0
@@ -109,6 +109,8 @@ DIRS-$(CONFIG_RTE_LIBRTE_IPSEC) += librte_ipsec DEPDIRS-librte_ipsec := librte_eal librte_mbuf librte_cryptodev librte_security DIRS-$(CONFIG_RTE_LIBRTE_TELEMETRY) += librte_telemetry DEPDIRS-librte_telemetry := librte_eal librte_metrics librte_ethdev +DIRS-$(CONFIG_RTE_LIBRTE_STACK) += librte_stack +DEPDIRS-librte_stack := librte_eal ifeq ($(CONFIG_RTE_EXEC_ENV_LINUX),y) DIRS-$(CONFIG_RTE_LIBRTE_KNI) += librte_kni
lib/librte_stack/Makefile new file +25 -0
@@ -0,0 +1,25 @@ +# SPDX-License-Identifier: BSD-3-Clause +# Copyright(c) 2019 Intel Corporation + +include $(RTE_SDK)/mk/rte.vars.mk + +# library name +LIB = librte_stack.a + +CFLAGS += $(WERROR_FLAGS) -I$(SRCDIR) -O3 +CFLAGS += -DALLOW_EXPERIMENTAL_API +LDLIBS += -lrte_eal + +EXPORT_MAP := rte_stack_version.map + +LIBABIVER := 1 + +# all source are stored in SRCS-y +SRCS-$(CONFIG_RTE_LIBRTE_STACK) := rte_stack.c \ + rte_stack_std.c + +# install includes +SYMLINK-$(CONFIG_RTE_LIBRTE_STACK)-include := rte_stack.h \ + rte_stack_std.h + +include $(RTE_SDK)/mk/rte.lib.mk
lib/librte_stack/meson.build new file +8 -0
@@ -0,0 +1,8 @@ +# SPDX-License-Identifier: BSD-3-Clause +# Copyright(c) 2019 Intel Corporation + +allow_experimental_apis = true + +version = 1 +sources = files('rte_stack.c', 'rte_stack_std.c') +headers = files('rte_stack.h', 'rte_stack_std.h')
lib/librte_stack/rte_stack.c new file +182 -0
182 lines not on this page · raw message
lib/librte_stack/rte_stack.h new file +209 -0
209 lines not on this page · raw message
lib/librte_stack/rte_stack_pvt.h new file +34 -0
@@ -0,0 +1,34 @@ +/* SPDX-License-Identifier: BSD-3-Clause +* Copyright(c) 2019 Intel Corporation +*/ + +#ifndef _RTE_STACK_PVT_H_ +#define _RTE_STACK_PVT_H_ + +#ifdef __cplusplus +extern "C" { +#endif + +#include <rte_log.h> + +extern int stack_logtype; + +#define STACK_LOG(level, fmt, args...) \ + rte_log(RTE_LOG_ ##level, stack_logtype, "%s(): "fmt "\n", \ + __func__, ##args) + +#define STACK_LOG_ERR(fmt, args...) \ + STACK_LOG(ERR, fmt, ## args) + +#define STACK_LOG_WARN(fmt, args...) \ + STACK_LOG(WARNING, fmt, ## args) + +#define STACK_LOG_INFO(fmt, args...) \ + STACK_LOG(INFO, fmt, ## args) + + +#ifdef __cplusplus +} +#endif + +#endif /* _RTE_STACK_PVT_H_ */
lib/librte_stack/rte_stack_std.c new file +26 -0
@@ -0,0 +1,26 @@ +/* SPDX-License-Identifier: BSD-3-Clause +* Copyright(c) 2019 Intel Corporation +*/ + +#include "rte_stack.h" + +void +rte_stack_std_init (struct rte_stack *s) +{ +rte_spinlock_init (&s->stack_std.lock); +} + +ssize_t +rte_stack_std_get_memsize (unsigned int count) +{ +ssize_t sz =sizeof (struct rte_stack ); + + sz +=RTE_CACHE_LINE_ROUNDUP (count *sizeof (void *)); + +/* Add padding to avoid false sharing conflicts caused by +* next-line hardware prefetchers. +*/ + sz +=2 *RTE_CACHE_LINE_SIZE ; + +return sz; +}
lib/librte_stack/rte_stack_std.h new file +121 -0
121 lines not on this page · raw message
lib/librte_stack/rte_stack_version.map new file +9 -0
@@ -0,0 +1,9 @@ +EXPERIMENTAL { + global: + + rte_stack_create; + rte_stack_free; + rte_stack_lookup; + + local: *; +};
lib/meson.build +1 -1
@@ -22,7 +22,7 @@ libraries = [ 'gro', 'gso', 'ip_frag', 'jobstats', 'kni', 'latencystats', 'lpm', 'member', 'power', 'pdump', 'rawdev', - 'reorder', 'sched', 'security', 'vhost', + 'reorder', 'sched', 'security', 'stack', 'vhost', #ipsec lib depends on crypto and security 'ipsec', # add pkt framework libs which use other libs from above
mk/rte.app.mk +1 -0
@@ -87,6 +87,7 @@ _LDLIBS-$(CONFIG_RTE_LIBRTE_SECURITY) += -lrte_security _LDLIBS-$(CONFIG_RTE_LIBRTE_COMPRESSDEV) += -lrte_compressdev _LDLIBS-$(CONFIG_RTE_LIBRTE_EVENTDEV) += -lrte_eventdev _LDLIBS-$(CONFIG_RTE_LIBRTE_RAWDEV) += -lrte_rawdev +_LDLIBS-$(CONFIG_RTE_LIBRTE_STACK) += -lrte_stack _LDLIBS-$(CONFIG_RTE_LIBRTE_TIMER) += -lrte_timer _LDLIBS-$(CONFIG_RTE_LIBRTE_MEMPOOL) += -lrte_mempool _LDLIBS-$(CONFIG_RTE_DRIVER_MEMPOOL_RING) += -lrte_mempool_ring
Signature · 1 line
2.13.6
Re: [PATCH v9 1/8] stack: introduce rte stack library
04/04/2019 01:20, Gage Eads:
mk/rte.app.mk _LDLIBS-$(CONFIG_RTE_LIBRTE_SECURITY) += -lrte_security · line 93
Quoted 10 lines
mk/rte.app.mk +1
-0@@ -87,6 +87,7 @@ _LDLIBS-$(CONFIG_RTE_LIBRTE_SECURITY) += -lrte_security _LDLIBS-$(CONFIG_RTE_LIBRTE_COMPRESSDEV) += -lrte_compressdev _LDLIBS-$(CONFIG_RTE_LIBRTE_EVENTDEV) += -lrte_eventdev _LDLIBS-$(CONFIG_RTE_LIBRTE_RAWDEV) += -lrte_rawdev +_LDLIBS-$(CONFIG_RTE_LIBRTE_STACK) += -lrte_stack _LDLIBS-$(CONFIG_RTE_LIBRTE_TIMER) += -lrte_timer _LDLIBS-$(CONFIG_RTE_LIBRTE_MEMPOOL) += -lrte_mempool _LDLIBS-$(CONFIG_RTE_DRIVER_MEMPOOL_RING) += -lrte_mempool_ring
Stack library is used by mempool, so it should appear after mempool in the library list.
It is the same as ring lib being after mempool_ring.
If you agree, please just tell me without sending a new version, because I'm doing other minor changes (sorting stack near ring in many files).
Re: [PATCH v9 1/8] stack: introduce rte stack library
Quoted 24 lines
-----Original Message-----
From: Thomas Monjalon [mailto:[email protected]]
Sent: Thursday, April 4, 2019 8:30 AM
To: Eads, Gage <[email protected]>
Cc: [email protected]; [email protected]; [email protected]; Richardson, Bruce <[email protected]>; Ananyev, Konstantin <[email protected]>; [email protected]; [email protected]; [email protected]
Subject: Re: [dpdk-dev] [PATCH v9 1/8] stack: introduce rte stack library04/04/2019 01:20, Gage Eads:
mk/rte.app.mk _LDLIBS-$(CONFIG_RTE_LIBRTE_SECURITY) += -
Quoted 3 lines
mk/rte.app.mk +0
-0@@ -87,6 +87,7 @@ _LDLIBS-$(CONFIG_RTE_LIBRTE_SECURITY) += -
lrte_securitymk/rte.app.mk _LDLIBS-$(CONFIG_RTE_LIBRTE_SECURITY) += -lrte_security
Quoted 7 lines
mk/rte.app.mk +1
-0_LDLIBS-$(CONFIG_RTE_LIBRTE_COMPRESSDEV) += -lrte_compressdev _LDLIBS-$(CONFIG_RTE_LIBRTE_EVENTDEV) += -lrte_eventdev _LDLIBS-$(CONFIG_RTE_LIBRTE_RAWDEV) += -lrte_rawdev +_LDLIBS-$(CONFIG_RTE_LIBRTE_STACK) += -lrte_stack _LDLIBS-$(CONFIG_RTE_LIBRTE_TIMER) += -lrte_timer _LDLIBS-$(CONFIG_RTE_LIBRTE_MEMPOOL) += -lrte_mempool _LDLIBS-$(CONFIG_RTE_DRIVER_MEMPOOL_RING) += -
Quoted 9 lines
lrte_mempool_ringStack library is used by mempool, so it should appear after mempool in the library list.
It is the same as ring lib being aftermempool_ring.If you agree, please just tell me without sending a new version, because I'm doing other minor changes (sorting stack near ring in many files).
Agreed. I suspect we haven't seen any linker problems because it's in a --whole-archive section (line 72), but better to put these in the correct dependency order.
PATCH v9 2/8 mempool/stack: convert mempool to use rte stack
In reply to Gage EadsThe new rte_stack library is derived from the mempool handler, so this commit removes duplicated code and simplifies the handler by migrating it to this new API.
--- MAINTAINERS | 2 +- drivers/mempool/stack/Makefile | 3 +- drivers/mempool/stack/meson.build | 6 +- drivers/mempool/stack/rte_mempool_stack.c | 93 +++++++++---------------------- 4 files changed, 33 insertions(+), 71 deletions(-)
MAINTAINERS +1 -1
@@ -303,7 +303,6 @@ M: Andrew Rybchenko <[email protected]> F: lib/librte_mempool/ F: drivers/mempool/Makefile F: drivers/mempool/ring/ -F: drivers/mempool/stack/ F: doc/guides/prog_guide/mempool_lib.rst F: app/test/test_mempool* F: app/test/test_func_reentrancy.c
@@ -431,6 +430,7 @@ M: Gage Eads <[email protected]> M: Olivier Matz <[email protected]> F: lib/librte_stack/ F: doc/guides/prog_guide/stack_lib.rst +F: drivers/mempool/stack/ Memory Pool Drivers
drivers/mempool/stack/Makefile +2 -1
@@ -10,10 +10,11 @@ LIB = librte_mempool_stack.a CFLAGS += -O3 CFLAGS += $(WERROR_FLAGS) +CFLAGS += -DALLOW_EXPERIMENTAL_API # Headers CFLAGS += -I$(RTE_SDK)/lib/librte_mempool -LDLIBS += -lrte_eal -lrte_mempool -lrte_ring +LDLIBS += -lrte_eal -lrte_mempool -lrte_stack EXPORT_MAP := rte_mempool_stack_version.map
drivers/mempool/stack/meson.build +5 -1
@@ -1,4 +1,8 @@ # SPDX-License-Identifier: BSD-3-Clause -# Copyright(c) 2017 Intel Corporation +# Copyright(c) 2017-2019 Intel Corporation + +allow_experimental_apis = true sources = files('rte_mempool_stack.c') + +deps += ['stack']
drivers/mempool/stack/rte_mempool_stack.c +25 -68
133 lines not on this page · raw message
Signature · 1 line
2.13.6
PATCH v9 3/8 test/stack: add stack test
In reply to Gage Eadsstack_autotest performs positive and negative testing of the stack API, and exercises the push and pop datapath functions with all available lcores.
--- MAINTAINERS | 1 + app/test/Makefile | 2 + app/test/meson.build | 3 + app/test/test_stack.c | 411 ++++++++++++++++++++++++++++++++++++++++++++++++++ 4 files changed, 417 insertions(+) create mode 100644 app/test/test_stack.c
MAINTAINERS +1 -0
@@ -431,6 +431,7 @@ M: Olivier Matz <[email protected]> F: lib/librte_stack/ F: doc/guides/prog_guide/stack_lib.rst F: drivers/mempool/stack/ +F: test/test/*stack* Memory Pool Drivers
app/test/Makefile +2 -0
@@ -90,6 +90,8 @@ endif SRCS-y += test_rwlock.c +SRCS-$(CONFIG_RTE_LIBRTE_STACK) += test_stack.c + SRCS-$(CONFIG_RTE_LIBRTE_TIMER) += test_timer.c SRCS-$(CONFIG_RTE_LIBRTE_TIMER) += test_timer_perf.c SRCS-$(CONFIG_RTE_LIBRTE_TIMER) += test_timer_racecond.c
app/test/meson.build +3 -0
@@ -95,6 +95,7 @@ test_sources = files('commands.c', 'test_sched.c', 'test_service_cores.c', 'test_spinlock.c', + 'test_stack.c', 'test_string_fns.c', 'test_table.c', 'test_table_acl.c',
@@ -133,6 +134,7 @@ test_deps = ['acl', 'port', 'reorder', 'ring', + 'stack', 'timer' ]
@@ -174,6 +176,7 @@ fast_parallel_test_names = [ 'rwlock_autotest', 'sched_autotest', 'spinlock_autotest', + 'stack_autotest', 'string_autotest', 'table_autotest', 'tailq_autotest',
app/test/test_stack.c new file +411 -0
411 lines not on this page · raw message
Signature · 1 line
2.13.6
Re: [PATCH v9 3/8] test/stack: add stack test
04/04/2019 01:20, Gage Eads:
MAINTAINERS M: Olivier Matz <[email protected]> · line 434
Quoted 7 lines
MAINTAINERS +1
-0@@ -431,6 +431,7 @@ M: Olivier Matz <[email protected]> F: lib/librte_stack/ F: doc/guides/prog_guide/stack_lib.rst F: drivers/mempool/stack/ +F: test/test/*stack*
Should be app/test/test_stack*
PATCH v9 4/8 test/stack: add stack perf test
In reply to Gage Eadsstack_perf_autotest tests the following with one lcore:
- Cycles to attempt to pop an empty stack
- Cycles to push then pop a single object
- Cycles to push then pop a burst of 32 objects
It also tests the cycles to push then pop a burst of 8 and 32 objects with the following lcore combinations (if possible):
- Two hyperthreads
- Two physical cores
- Two physical cores on separate NUMA nodes
- All available lcores
--- app/test/Makefile | 1 + app/test/meson.build | 2 + app/test/test_stack_perf.c | 345 +++++++++++++++++++++++++++++++++++++++++++++ 3 files changed, 348 insertions(+) create mode 100644 app/test/test_stack_perf.c
app/test/Makefile +1 -0
@@ -91,6 +91,7 @@ endif SRCS-y += test_rwlock.c SRCS-$(CONFIG_RTE_LIBRTE_STACK) += test_stack.c +SRCS-$(CONFIG_RTE_LIBRTE_STACK) += test_stack_perf.c SRCS-$(CONFIG_RTE_LIBRTE_TIMER) += test_timer.c SRCS-$(CONFIG_RTE_LIBRTE_TIMER) += test_timer_perf.c
app/test/meson.build +2 -0
@@ -96,6 +96,7 @@ test_sources = files('commands.c', 'test_service_cores.c', 'test_spinlock.c', 'test_stack.c', + 'test_stack_perf.c', 'test_string_fns.c', 'test_table.c', 'test_table_acl.c',
@@ -241,6 +242,7 @@ perf_test_names = [ 'distributor_perf_autotest', 'ring_pmd_perf_autotest', 'pmd_perf_autotest', + 'stack_perf_autotest', ] # All test cases in driver_test_names list are non-parallel
app/test/test_stack_perf.c new file +345 -0
345 lines not on this page · raw message
Signature · 1 line
2.13.6
PATCH v9 5/8 stack: add lock-free stack implementation
In reply to Gage EadsThis commit adds support for a lock-free (linked list based) stack to the stack API. This behavior is selected through a new rte_stack_create() flag, RTE_STACK_F_LF.
The stack consists of a linked list of elements, each containing a data pointer and a next pointer, and an atomic stack depth counter.
The lock-free push operation enqueues a linked list of pointers by pointing the tail of the list to the current stack head, and using a CAS to swing the stack head pointer to the head of the list. The operation retries if it is unsuccessful (i.e. the list changed between reading the head and modifying it), else it adjusts the stack length and returns.
The lock-free pop operation first reserves num elements by adjusting the stack length, to ensure the dequeue operation will succeed without blocking. It then dequeues pointers by walking the list -- starting from the head -- then swinging the head pointer (using a CAS as well). While walking the list, the data pointers are recorded in an object table.
This algorithm stack uses a 128-bit compare-and-swap instruction, which atomically updates the stack top pointer and a modification counter, to protect against the ABA problem.
The linked list elements themselves are maintained in a lock-free LIFO list, and are allocated before stack pushes and freed after stack pops. Since the stack has a fixed maximum depth, these elements do not need to be dynamically created.
--- doc/guides/prog_guide/stack_lib.rst | 61 +++++++++++- doc/guides/rel_notes/release_19_05.rst | 3 + lib/librte_stack/Makefile | 7 +- lib/librte_stack/meson.build | 7 +- lib/librte_stack/rte_stack.c | 28 ++++-- lib/librte_stack/rte_stack.h | 63 +++++++++++- lib/librte_stack/rte_stack_lf.c | 31 ++++++ lib/librte_stack/rte_stack_lf.h | 102 ++++++++++++++++++++ lib/librte_stack/rte_stack_lf_generic.h | 164 ++++++++++++++++++++++++++++++++ 9 files changed, 447 insertions(+), 19 deletions(-) create mode 100644 lib/librte_stack/rte_stack_lf.c create mode 100644 lib/librte_stack/rte_stack_lf.h create mode 100644 lib/librte_stack/rte_stack_lf_generic.h
doc/guides/prog_guide/stack_lib.rst +58 -3
@@ -10,7 +10,8 @@ stack of pointers. The stack library provides the following basic operations: * Create a uniquely named stack of a user-specified size and using a - user-specified socket. + user-specified socket, with either standard (lock-based) or lock-free + behavior. * Push and pop a burst of one or more stack objects (pointers). These function are multi-threading safe.
@@ -24,5 +25,59 @@ The stack library provides the following basic operations: Implementation ~~~~~~~~~~~~~~ -The stack consists of a contiguous array of pointers, a current index, and a -spinlock. Accesses to the stack are made multi-thread safe by the spinlock. +The library supports two types of stacks: standard (lock-based) and lock-free. +Both types use the same set of interfaces, but their implementations differ. + +Lock-based Stack +---------------- + +The lock-based stack consists of a contiguous array of pointers, a current +index, and a spinlock. Accesses to the stack are made multi-thread safe by the +spinlock. + +Lock-free Stack +------------------ + +The lock-free stack consists of a linked list of elements, each containing a +data pointer and a next pointer, and an atomic stack depth counter. The +lock-free property means that multiple threads can push and pop simultaneously, +and one thread being preempted/delayed in a push or pop operation will not +impede the forward progress of any other thread. + +The lock-free push operation enqueues a linked list of pointers by pointing the +list's tail to the current stack head, and using a CAS to swing the stack head +pointer to the head of the list. The operation retries if it is unsuccessful +(i.e. the list changed between reading the head and modifying it), else it +adjusts the stack length and returns. + +The lock-free pop operation first reserves one or more list elements by +adjusting the stack length, to ensure the dequeue operation will succeed +without blocking. It then dequeues pointers by walking the list -- starting +from the head -- then swinging the head pointer (using a CAS as well). While +walking the list, the data pointers are recorded in an object table. + +The linked list elements themselves are maintained in a lock-free LIFO, and are +allocated before stack pushes and freed after stack pops. Since the stack has a +fixed maximum depth, these elements do not need to be dynamically created. + +The lock-free behavior is selected by passing the *RTE_STACK_F_LF* flag to +rte_stack_create(). + +Preventing the ABA Problem +^^^^^^^^^^^^^^^^^^^^^^^^^^ + +To prevent the ABA problem, this algorithm stack uses a 128-bit +compare-and-swap instruction to atomically update both the stack top pointer +and a modification counter. The ABA problem can occur without a modification +counter if, for example: + +1. Thread A reads head pointer X and stores the pointed-to list element. +2. Other threads modify the list such that the head pointer is once again X, + but its pointed-to data is different than what thread A read. +3. Thread A changes the head pointer with a compare-and-swap and succeeds. + +In this case thread A would not detect that the list had changed, and would +both pop stale data and incorrect change the head pointer. By adding a +modification counter that is updated on every push and pop as part of the +compare-and-swap, the algorithm can detect when the list changes even if the +head pointer remains the same.
doc/guides/rel_notes/release_19_05.rst +3 -0
@@ -127,6 +127,9 @@ New Features pointers. The API provides MT-safe push and pop operations that can operate on one or more pointers per operation. + The library supports two stack implementations: standard (lock-based) and lock-free. + The lock-free implementation is currently limited to x86-64 platforms. + Removed Items -------------
lib/librte_stack/Makefile +5 -2
@@ -16,10 +16,13 @@ LIBABIVER := 1 # all source are stored in SRCS-y SRCS-$(CONFIG_RTE_LIBRTE_STACK) := rte_stack.c \ - rte_stack_std.c + rte_stack_std.c \ + rte_stack_lf.c # install includes SYMLINK-$(CONFIG_RTE_LIBRTE_STACK)-include := rte_stack.h \ - rte_stack_std.h + rte_stack_std.h \ + rte_stack_lf.h \ + rte_stack_lf_generic.h include $(RTE_SDK)/mk/rte.lib.mk
lib/librte_stack/meson.build +5 -2
@@ -4,5 +4,8 @@ allow_experimental_apis = true version = 1 -sources = files('rte_stack.c', 'rte_stack_std.c') -headers = files('rte_stack.h', 'rte_stack_std.h') +sources = files('rte_stack.c', 'rte_stack_std.c', 'rte_stack_lf.c') +headers = files('rte_stack.h', + 'rte_stack_std.h', + 'rte_stack_lf.h', + 'rte_stack_lf_generic.h')
lib/librte_stack/rte_stack.c +21 -7
@@ -25,18 +25,25 @@ static struct rte_tailq_elem rte_stack_tailq = { };EAL_REGISTER_TAILQ (rte_stack_tailq) + static void -rte_stack_init (struct rte_stack *s) +rte_stack_init (struct rte_stack *s,unsigned int count,uint32_t flags) {memset (s,0 ,sizeof (*s)); -rte_stack_std_init (s); +if (flags &RTE_STACK_F_LF ) +rte_stack_lf_init (s, count); +else +rte_stack_std_init (s); }static ssize_t -rte_stack_get_memsize (unsigned int count) +rte_stack_get_memsize (unsigned int count,uint32_t flags) { -return rte_stack_std_get_memsize (count); +if (flags &RTE_STACK_F_LF ) +return rte_stack_lf_get_memsize (count); +else +return rte_stack_std_get_memsize (count); } struct rte_stack *
@@ -51,9 +58,16 @@ rte_stack_create(const char *name, unsigned int count, int socket_id,unsigned int sz;int ret; -RTE_SET_USED (flags); +#ifdef RTE_ARCH_64 +RTE_BUILD_BUG_ON (sizeof (struct rte_stack_lf_head ) !=16 ); +#else +if (flags &RTE_STACK_F_LF ) { +STACK_LOG_ERR ("Lock-free stack is not supported on your platform\n" ); +return NULL ; + } +#endif - sz =rte_stack_get_memsize (count); + sz =rte_stack_get_memsize (count, flags); ret =snprintf (mz_name,sizeof (mz_name),"%s%s" ,RTE_STACK_MZ_PREFIX , name);
@@ -82,7 +96,7 @@ rte_stack_create(const char *name, unsigned int count, int socket_id, s = mz->addr; -rte_stack_init (s); +rte_stack_init (s, count, flags);/* Store the name for later lookups */ ret =snprintf (s->name,sizeof (s->name),"%s" , name);
lib/librte_stack/rte_stack.h +58 -5
108 lines not on this page · raw message
lib/librte_stack/rte_stack_lf.c new file +31 -0
@@ -0,0 +1,31 @@ +/* SPDX-License-Identifier: BSD-3-Clause +* Copyright(c) 2019 Intel Corporation +*/ + +#include "rte_stack.h" + +void +rte_stack_lf_init (struct rte_stack *s,unsigned int count) +{ +struct rte_stack_lf_elem *elems = s->stack_lf.elems; +unsigned int i; + +for (i =0 ; i < count; i++) +__rte_stack_lf_push_elems (&s->stack_lf.free, + &elems[i], &elems[i],1 ); +} + +ssize_t +rte_stack_lf_get_memsize (unsigned int count) +{ +ssize_t sz =sizeof (struct rte_stack ); + + sz +=RTE_CACHE_LINE_ROUNDUP (count *sizeof (struct rte_stack_lf_elem )); + +/* Add padding to avoid false sharing conflicts caused by +* next-line hardware prefetchers. +*/ + sz +=2 *RTE_CACHE_LINE_SIZE ; + +return sz; +}
lib/librte_stack/rte_stack_lf.h new file +102 -0
102 lines not on this page · raw message
lib/librte_stack/rte_stack_lf_generic.h new file +164 -0
164 lines not on this page · raw message
Signature · 1 line
2.13.6
PATCH v9 6/8 stack: add C11 atomic implementation
In reply to Gage EadsThis commit adds an implementation of the lock-free stack push, pop, and length functions that use __atomic builtins, for systems that benefit from the finer-grained memory ordering control.
--- lib/librte_stack/Makefile | 3 +- lib/librte_stack/meson.build | 3 +- lib/librte_stack/rte_stack_lf.h | 4 + lib/librte_stack/rte_stack_lf_c11.h | 175 ++++++++++++++++++++++++++++++++++++ 4 files changed, 183 insertions(+), 2 deletions(-) create mode 100644 lib/librte_stack/rte_stack_lf_c11.h
lib/librte_stack/Makefile +2 -1
@@ -23,6 +23,7 @@ SRCS-$(CONFIG_RTE_LIBRTE_STACK) := rte_stack.c \ SYMLINK-$(CONFIG_RTE_LIBRTE_STACK)-include := rte_stack.h \ rte_stack_std.h \ rte_stack_lf.h \ - rte_stack_lf_generic.h + rte_stack_lf_generic.h \ + rte_stack_lf_c11.h include $(RTE_SDK)/mk/rte.lib.mk
lib/librte_stack/meson.build +2 -1
@@ -8,4 +8,5 @@ sources = files('rte_stack.c', 'rte_stack_std.c', 'rte_stack_lf.c') headers = files('rte_stack.h', 'rte_stack_std.h', 'rte_stack_lf.h', - 'rte_stack_lf_generic.h') + 'rte_stack_lf_generic.h', + 'rte_stack_lf_c11.h')
lib/librte_stack/rte_stack_lf.h +4 -0
@@ -5,7 +5,11 @@#ifndef _RTE_STACK_LF_H_#define _RTE_STACK_LF_H_ +#ifdef RTE_USE_C11_MEM_MODEL +#include "rte_stack_lf_c11.h" +#else #include "rte_stack_lf_generic.h" +#endif /** * @internal Push several objects on the lock-free stack (MT-safe).
lib/librte_stack/rte_stack_lf_c11.h new file +175 -0
175 lines not on this page · raw message
Signature · 1 line
2.13.6
PATCH v9 7/8 test/stack: add lock-free stack tests
In reply to Gage EadsThis commit adds lock-free stack variants of stack_autotest (stack_lf_autotest) and stack_perf_autotest (stack_lf_perf_autotest), which differ only in that the lock-free versions pass the RTE_STACK_F_LF flag to all rte_stack_create() calls.
--- app/test/meson.build | 2 ++ app/test/test_stack.c | 41 +++++++++++++++++++++++++++-------------- app/test/test_stack_perf.c | 17 +++++++++++++++-- 3 files changed, 44 insertions(+), 16 deletions(-)
app/test/meson.build +2 -0
@@ -178,6 +178,7 @@ fast_parallel_test_names = [ 'sched_autotest', 'spinlock_autotest', 'stack_autotest', + 'stack_nb_autotest', 'string_autotest', 'table_autotest', 'tailq_autotest',
@@ -243,6 +244,7 @@ perf_test_names = [ 'ring_pmd_perf_autotest', 'pmd_perf_autotest', 'stack_perf_autotest', + 'stack_nb_perf_autotest', ] # All test cases in driver_test_names list are non-parallel
app/test/test_stack.c +27 -14
112 lines not on this page · raw message
app/test/test_stack_perf.c +15 -2
@@ -299,14 +299,14 @@ test_bulk_push_pop(struct rte_stack *s) }static int -test_stack_perf (void ) +__test_stack_perf (uint32_t flags) {struct lcore_pair cores;struct rte_stack *s;rte_atomic32_init (&lcore_barrier); - s =rte_stack_create (STACK_NAME ,STACK_SIZE ,rte_socket_id (),0 ); + s =rte_stack_create (STACK_NAME ,STACK_SIZE ,rte_socket_id (), flags);if (s ==NULL ) {printf ("[%s():%u] failed to create a stack\n" , __func__, __LINE__);
@@ -342,4 +342,17 @@ test_stack_perf(void)return 0 ; } +static int +test_stack_perf (void ) +{ +return __test_stack_perf (0 ); +} + +static int +test_lf_stack_perf (void ) +{ +return __test_stack_perf (RTE_STACK_F_LF ); +} +REGISTER_TEST_COMMAND (stack_perf_autotest, test_stack_perf); +REGISTER_TEST_COMMAND (stack_lf_perf_autotest, test_lf_stack_perf);
Signature · 1 line
2.13.6
PATCH v9 8/8 mempool/stack: add lock-free stack mempool handler
In reply to Gage EadsThis commit adds support for lock-free (linked list based) stack mempool handler.
In mempool_perf_autotest the lock-based stack outperforms the lock-free handler for certain lcore/alloc count/free count combinations*, however:
- For applications with preemptible pthreads, a standard (lock-based) stack's worst-case performance (i.e. one thread being preempted while holding the spinlock) is much worse than the lock-free stack's.
- Using per-thread mempool caches will largely mitigate the performance difference.
*Test setup: x86_64 build with default config, dual-socket Xeon E5-2699 v4, running on isolcpus cores with a tickless scheduler. The lock-based stack's rate_persec was 0.6x-3.5x the lock-free stack's.
--- doc/guides/prog_guide/env_abstraction_layer.rst | 10 ++++++++++ doc/guides/rel_notes/release_19_05.rst | 5 +++++ drivers/mempool/stack/rte_mempool_stack.c | 26 +++++++++++++++++++++++-- 3 files changed, 39 insertions(+), 2 deletions(-)
doc/guides/prog_guide/env_abstraction_layer.rst +10 -0
@@ -581,6 +581,16 @@ Known Issues 5. It MUST not be used by multi-producer/consumer pthreads, whose scheduling policies are SCHED_FIFO or SCHED_RR. + Alternatively, applications can use the lock-free stack mempool handler. When + considering this handler, note that: + + - It is currently limited to the x86_64 platform, because it uses an + instruction (16-byte compare-and-swap) that is not yet available on other + platforms. + - It has worse average-case performance than the non-preemptive rte_ring, but + software caching (e.g. the mempool cache) can mitigate this by reducing the + number of stack accesses. + + rte_timer Running ``rte_timer_manage()`` on a non-EAL pthread is not allowed. However, resetting/stopping the timer from a non-EAL pthread is allowed.
doc/guides/rel_notes/release_19_05.rst +5 -0
@@ -130,6 +130,11 @@ New Features The library supports two stack implementations: standard (lock-based) and lock-free. The lock-free implementation is currently limited to x86-64 platforms. +* **Added Lock-Free Stack Mempool Handler.** + + Added a new lock-free stack handler, which uses the newly added stack + library. + Removed Items -------------
drivers/mempool/stack/rte_mempool_stack.c +24 -2
@@ -7,7 +7,7 @@#include <rte_stack.h> static int -stack_alloc (struct rte_mempool *mp) +__stack_alloc (struct rte_mempool *mp,uint32_t flags) {char name[RTE_STACK_NAMESIZE ];struct rte_stack *s;
@@ -20,7 +20,7 @@ stack_alloc(struct rte_mempool *mp)return -rte_errno; } - s =rte_stack_create (name, mp->size, mp->socket_id,0 ); + s =rte_stack_create (name, mp->size, mp->socket_id, flags);if (s ==NULL )return -rte_errno;
@@ -30,6 +30,18 @@ stack_alloc(struct rte_mempool *mp) }static int +stack_alloc (struct rte_mempool *mp) +{ +return __stack_alloc (mp,0 ); +} + +static int +lf_stack_alloc (struct rte_mempool *mp) +{ +return __stack_alloc (mp,RTE_STACK_F_LF ); +} + +static int stack_enqueue (struct rte_mempool *mp,void *const *obj_table,unsigned int n) {
@@ -72,4 +84,14 @@ static struct rte_mempool_ops ops_stack = { .get_count = stack_get_count }; +static struct rte_mempool_ops ops_lf_stack = { + .name ="lf_stack" , + .alloc = lf_stack_alloc, + .free = stack_free, + .enqueue = stack_enqueue, + .dequeue = stack_dequeue, + .get_count = stack_get_count +}; +MEMPOOL_REGISTER_OPS (ops_stack); +MEMPOOL_REGISTER_OPS (ops_lf_stack);
Signature · 1 line
2.13.6
v10 cover Add stack library and new mempool handler
In reply to Gage EadsThis patchset introduces a stack library, supporting both lock-based and lock-free stacks, and a lock-free stack mempool handler.
The lock-based stack code is derived from the existing stack mempool handler, and that handler is refactored to use the stack library.
The lock-free stack mempool handler is intended for usages where the rte ring's "non-preemptive" constraint is not acceptable; for example, if the application uses a mixture of pinned high-priority threads and multiplexed low-priority threads that share a mempool.
Note that the lock-free algorithm relies on a 128-bit compare-and-swap[1], so it is currently limited to the x86_64 platform.
This patchset is the successor to a patchset containing only the new mempool handler[2].
[1] http://mails.dpdk.org/archives/dev/2019-April/129014.html
[2] http://mails.dpdk.org/archives/dev/2019-January/123555.html
---
v10:
- Correct test/test/ -> app/test/ in MAINTAINERS
v9:
- Add rte_atomic.h includes to rte_stack.h, test_stack.c, and test_stack_perf.c to fix ARM builds
v8:
- Add rte_debug.h include to rte_stack.h for RTE_ASSERT()
v7:
- Add rte_branch_prediction.h include to rte_stack_std.h for unlikely()
- Add rte_compat.h include to rte_stack.h for __rte_experimental
v6:
- Add load-acquire fence to the lock-free push function
- Correct generic implementation's pop_elems 128b CAS success and failure memorder to match those in the C11 implementation.
v5:
- Add comment to explain padding in *_get_memsize() functions
- Prefix internal functions with '__'
- Use RTE_ASSERT for performance critical run-time checks
- Don't use __atomic_load in the C11 pop_elems function, and put an acquire thread fence at the start of the 2nd do-while loop
- Change pop_elems 128b CAS success memorder to RELEASE and failure memorder to RELAXED
- Change compile-time assertion to run for all 64-bit architectures
- Reorganize the code with standard and lock-free .c and .h files
v4:
- Fix 32-bit build error in test_stack.c by using %zu format specifier for size_t
- Rebase onto master
v3:
- Rebase patchset onto master (test/test/ -> app/test/)
- Fix rte_stack_std_push() segfault introduced in v2
v2:
- Reworked structure and function naming to use rte_stack_{std, lf}_...
- Updated to the latest rte_atomic128_cmp_exchange() interface.
- Rename STACK_F_NB -> RTE_STACK_F_LF.
- Remove rte_rmb() and rte_wmb() from the generic push and pop implementations. These are obviated by rte_atomic128_cmp_exchange()'s two memorder arguments.
- Edit stack_lib.rst text to 80 chars/line.
- Fix rte_stack.h doxygen formatting.
- Allocate popped_objs array from the heap
- Fix stack_thread_push_pop bug ("&t->sz" -> "t->sz")
- Remove unnecessary NULL check from test_stack_basic
- Properly terminate the name string in test_stack_name_length
- Add an empty array of struct rte_nb_lifo_elem elements
- In rte_nb_lifo_push(), retrieve the last element from __nb_lifo_pop()
- Split C11 implementation into a separate patchset
Gage Eads (8):
stack: introduce rte stack library mempool/stack: convert mempool to use rte stack test/stack: add stack test
test/stack: add stack perf test
stack: add lock-free stack implementation
stack: add C11 atomic implementation test/stack: add lock-free stack tests mempool/stack: add lock-free stack mempool handler
MAINTAINERS | 9 +- app/test/Makefile | 3 + app/test/meson.build | 7 + app/test/test_stack.c | 424 ++++++++++++++++++++++++ app/test/test_stack_perf.c | 358 ++++++++++++++++++++ config/common_base | 5 + doc/api/doxy-api-index.md | 1 + doc/api/doxy-api.conf.in | 1 + doc/guides/prog_guide/env_abstraction_layer.rst | 10 + doc/guides/prog_guide/index.rst | 1 + doc/guides/prog_guide/stack_lib.rst | 83 +++++ doc/guides/rel_notes/release_19_05.rst | 13 + drivers/mempool/stack/Makefile | 3 +- drivers/mempool/stack/meson.build | 6 +- drivers/mempool/stack/rte_mempool_stack.c | 115 +++---- lib/Makefile | 2 + lib/librte_stack/Makefile | 29 ++ lib/librte_stack/meson.build | 12 + lib/librte_stack/rte_stack.c | 196 +++++++++++ lib/librte_stack/rte_stack.h | 262 +++++++++++++++ lib/librte_stack/rte_stack_lf.c | 31 ++ lib/librte_stack/rte_stack_lf.h | 106 ++++++ lib/librte_stack/rte_stack_lf_c11.h | 175 ++++++++++ lib/librte_stack/rte_stack_lf_generic.h | 164 +++++++++ lib/librte_stack/rte_stack_pvt.h | 34 ++ lib/librte_stack/rte_stack_std.c | 26 ++ lib/librte_stack/rte_stack_std.h | 121 +++++++ lib/librte_stack/rte_stack_version.map | 9 + lib/meson.build | 2 +- mk/rte.app.mk | 1 + 30 files changed, 2137 insertions(+), 72 deletions(-) create mode 100644 app/test/test_stack.c create mode 100644 app/test/test_stack_perf.c create mode 100644 doc/guides/prog_guide/stack_lib.rst create mode 100644 lib/librte_stack/Makefile create mode 100644 lib/librte_stack/meson.build create mode 100644 lib/librte_stack/rte_stack.c create mode 100644 lib/librte_stack/rte_stack.h create mode 100644 lib/librte_stack/rte_stack_lf.c create mode 100644 lib/librte_stack/rte_stack_lf.h create mode 100644 lib/librte_stack/rte_stack_lf_c11.h create mode 100644 lib/librte_stack/rte_stack_lf_generic.h create mode 100644 lib/librte_stack/rte_stack_pvt.h create mode 100644 lib/librte_stack/rte_stack_std.c create mode 100644 lib/librte_stack/rte_stack_std.h create mode 100644 lib/librte_stack/rte_stack_version.map
Signature · 1 line
2.13.6
PATCH v10 1/8 stack: introduce rte stack library
The rte_stack library provides an API for configuration and use of a bounded stack of pointers. Push and pop operations are MT-safe, allowing concurrent access, and the interface supports pushing and popping multiple pointers at a time.
The library's interface is modeled after another DPDK data structure, rte_ring, and its lock-based implementation is derived from the stack mempool handler. An upcoming commit will migrate the stack mempool handler to rte_stack.
--- MAINTAINERS | 6 + config/common_base | 5 + doc/api/doxy-api-index.md | 1 + doc/api/doxy-api.conf.in | 1 + doc/guides/prog_guide/index.rst | 1 + doc/guides/prog_guide/stack_lib.rst | 28 +++++ doc/guides/rel_notes/release_19_05.rst | 5 + lib/Makefile | 2 + lib/librte_stack/Makefile | 25 ++++ lib/librte_stack/meson.build | 8 ++ lib/librte_stack/rte_stack.c | 182 ++++++++++++++++++++++++++++ lib/librte_stack/rte_stack.h | 209 +++++++++++++++++++++++++++++++++ lib/librte_stack/rte_stack_pvt.h | 34 ++++++ lib/librte_stack/rte_stack_std.c | 26 ++++ lib/librte_stack/rte_stack_std.h | 121 +++++++++++++++++++ lib/librte_stack/rte_stack_version.map | 9 ++ lib/meson.build | 2 +- mk/rte.app.mk | 1 + 18 files changed, 665 insertions(+), 1 deletion(-) create mode 100644 doc/guides/prog_guide/stack_lib.rst create mode 100644 lib/librte_stack/Makefile create mode 100644 lib/librte_stack/meson.build create mode 100644 lib/librte_stack/rte_stack.c create mode 100644 lib/librte_stack/rte_stack.h create mode 100644 lib/librte_stack/rte_stack_pvt.h create mode 100644 lib/librte_stack/rte_stack_std.c create mode 100644 lib/librte_stack/rte_stack_std.h create mode 100644 lib/librte_stack/rte_stack_version.map
MAINTAINERS +6 -0
@@ -426,6 +426,12 @@ F: drivers/raw/skeleton_rawdev/ F: app/test/test_rawdev.c F: doc/guides/prog_guide/rawdev.rst +Stack API - EXPERIMENTAL +M: Gage Eads <[email protected]> +M: Olivier Matz <[email protected]> +F: lib/librte_stack/ +F: doc/guides/prog_guide/stack_lib.rst + Memory Pool Drivers -------------------
config/common_base +5 -0
@@ -994,3 +994,8 @@ CONFIG_RTE_APP_CRYPTO_PERF=y # Compile the eventdev application # CONFIG_RTE_APP_EVENTDEV=y + +# +# Compile librte_stack +# +CONFIG_RTE_LIBRTE_STACK=y
doc/api/doxy-api-index.md +1 -0
@@ -125,6 +125,7 @@ The public API headers are grouped by topics: [mbuf] (@ref rte_mbuf.h), [mbuf pool ops] (@ref rte_mbuf_pool_ops.h), [ring] (@ref rte_ring.h), + [stack] (@ref rte_stack.h), [tailq] (@ref rte_tailq.h), [bitmap] (@ref rte_bitmap.h)
doc/api/doxy-api.conf.in +1 -0
@@ -55,6 +55,7 @@ INPUT = @TOPDIR@/doc/api/doxy-api-index.md \ @TOPDIR@/lib/librte_ring \ @TOPDIR@/lib/librte_sched \ @TOPDIR@/lib/librte_security \ + @TOPDIR@/lib/librte_stack \ @TOPDIR@/lib/librte_table \ @TOPDIR@/lib/librte_telemetry \ @TOPDIR@/lib/librte_timer \
doc/guides/prog_guide/index.rst +1 -0
@@ -55,6 +55,7 @@ Programmer's Guide metrics_lib bpf_lib ipsec_lib + stack_lib source_org dev_kit_build_system dev_kit_root_make_help
doc/guides/prog_guide/stack_lib.rst new file +28 -0
@@ -0,0 +1,28 @@ +.. SPDX-License-Identifier: BSD-3-Clause + Copyright(c) 2019 Intel Corporation. + +Stack Library +============= + +DPDK's stack library provides an API for configuration and use of a bounded +stack of pointers. + +The stack library provides the following basic operations: + +* Create a uniquely named stack of a user-specified size and using a + user-specified socket. + +* Push and pop a burst of one or more stack objects (pointers). These function + are multi-threading safe. + +* Free a previously created stack. + +* Lookup a pointer to a stack by its name. + +* Query a stack's current depth and number of free entries. + +Implementation +~~~~~~~~~~~~~~ + +The stack consists of a contiguous array of pointers, a current index, and a +spinlock. Accesses to the stack are made multi-thread safe by the spinlock.
doc/guides/rel_notes/release_19_05.rst +5 -0
@@ -121,6 +121,11 @@ New Features Improved testpmd application performance on ARM platform. For ``macswap`` forwarding mode, NEON intrinsics were used to do swap to save CPU cycles. +* **Added Stack API.** + + Added a new stack API for configuration and use of a bounded stack of + pointers. The API provides MT-safe push and pop operations that can operate + on one or more pointers per operation. Removed Items -------------
lib/Makefile +2 -0
@@ -109,6 +109,8 @@ DIRS-$(CONFIG_RTE_LIBRTE_IPSEC) += librte_ipsec DEPDIRS-librte_ipsec := librte_eal librte_mbuf librte_cryptodev librte_security DIRS-$(CONFIG_RTE_LIBRTE_TELEMETRY) += librte_telemetry DEPDIRS-librte_telemetry := librte_eal librte_metrics librte_ethdev +DIRS-$(CONFIG_RTE_LIBRTE_STACK) += librte_stack +DEPDIRS-librte_stack := librte_eal ifeq ($(CONFIG_RTE_EXEC_ENV_LINUX),y) DIRS-$(CONFIG_RTE_LIBRTE_KNI) += librte_kni
lib/librte_stack/Makefile new file +25 -0
@@ -0,0 +1,25 @@ +# SPDX-License-Identifier: BSD-3-Clause +# Copyright(c) 2019 Intel Corporation + +include $(RTE_SDK)/mk/rte.vars.mk + +# library name +LIB = librte_stack.a + +CFLAGS += $(WERROR_FLAGS) -I$(SRCDIR) -O3 +CFLAGS += -DALLOW_EXPERIMENTAL_API +LDLIBS += -lrte_eal + +EXPORT_MAP := rte_stack_version.map + +LIBABIVER := 1 + +# all source are stored in SRCS-y +SRCS-$(CONFIG_RTE_LIBRTE_STACK) := rte_stack.c \ + rte_stack_std.c + +# install includes +SYMLINK-$(CONFIG_RTE_LIBRTE_STACK)-include := rte_stack.h \ + rte_stack_std.h + +include $(RTE_SDK)/mk/rte.lib.mk
lib/librte_stack/meson.build new file +8 -0
@@ -0,0 +1,8 @@ +# SPDX-License-Identifier: BSD-3-Clause +# Copyright(c) 2019 Intel Corporation + +allow_experimental_apis = true + +version = 1 +sources = files('rte_stack.c', 'rte_stack_std.c') +headers = files('rte_stack.h', 'rte_stack_std.h')
lib/librte_stack/rte_stack.c new file +182 -0
182 lines not on this page · raw message
lib/librte_stack/rte_stack.h new file +209 -0
209 lines not on this page · raw message
lib/librte_stack/rte_stack_pvt.h new file +34 -0
@@ -0,0 +1,34 @@ +/* SPDX-License-Identifier: BSD-3-Clause +* Copyright(c) 2019 Intel Corporation +*/ + +#ifndef _RTE_STACK_PVT_H_ +#define _RTE_STACK_PVT_H_ + +#ifdef __cplusplus +extern "C" { +#endif + +#include <rte_log.h> + +extern int stack_logtype; + +#define STACK_LOG(level, fmt, args...) \ + rte_log(RTE_LOG_ ##level, stack_logtype, "%s(): "fmt "\n", \ + __func__, ##args) + +#define STACK_LOG_ERR(fmt, args...) \ + STACK_LOG(ERR, fmt, ## args) + +#define STACK_LOG_WARN(fmt, args...) \ + STACK_LOG(WARNING, fmt, ## args) + +#define STACK_LOG_INFO(fmt, args...) \ + STACK_LOG(INFO, fmt, ## args) + + +#ifdef __cplusplus +} +#endif + +#endif /* _RTE_STACK_PVT_H_ */
lib/librte_stack/rte_stack_std.c new file +26 -0
@@ -0,0 +1,26 @@ +/* SPDX-License-Identifier: BSD-3-Clause +* Copyright(c) 2019 Intel Corporation +*/ + +#include "rte_stack.h" + +void +rte_stack_std_init (struct rte_stack *s) +{ +rte_spinlock_init (&s->stack_std.lock); +} + +ssize_t +rte_stack_std_get_memsize (unsigned int count) +{ +ssize_t sz =sizeof (struct rte_stack ); + + sz +=RTE_CACHE_LINE_ROUNDUP (count *sizeof (void *)); + +/* Add padding to avoid false sharing conflicts caused by +* next-line hardware prefetchers. +*/ + sz +=2 *RTE_CACHE_LINE_SIZE ; + +return sz; +}
lib/librte_stack/rte_stack_std.h new file +121 -0
121 lines not on this page · raw message
lib/librte_stack/rte_stack_version.map new file +9 -0
@@ -0,0 +1,9 @@ +EXPERIMENTAL { + global: + + rte_stack_create; + rte_stack_free; + rte_stack_lookup; + + local: *; +};
lib/meson.build +1 -1
@@ -22,7 +22,7 @@ libraries = [ 'gro', 'gso', 'ip_frag', 'jobstats', 'kni', 'latencystats', 'lpm', 'member', 'power', 'pdump', 'rawdev', - 'reorder', 'sched', 'security', 'vhost', + 'reorder', 'sched', 'security', 'stack', 'vhost', #ipsec lib depends on crypto and security 'ipsec', # add pkt framework libs which use other libs from above
mk/rte.app.mk +1 -0
@@ -87,6 +87,7 @@ _LDLIBS-$(CONFIG_RTE_LIBRTE_SECURITY) += -lrte_security _LDLIBS-$(CONFIG_RTE_LIBRTE_COMPRESSDEV) += -lrte_compressdev _LDLIBS-$(CONFIG_RTE_LIBRTE_EVENTDEV) += -lrte_eventdev _LDLIBS-$(CONFIG_RTE_LIBRTE_RAWDEV) += -lrte_rawdev +_LDLIBS-$(CONFIG_RTE_LIBRTE_STACK) += -lrte_stack _LDLIBS-$(CONFIG_RTE_LIBRTE_TIMER) += -lrte_timer _LDLIBS-$(CONFIG_RTE_LIBRTE_MEMPOOL) += -lrte_mempool _LDLIBS-$(CONFIG_RTE_DRIVER_MEMPOOL_RING) += -lrte_mempool_ring
Signature · 1 line
2.13.6
PATCH v10 2/8 mempool/stack: convert mempool to use rte stack
In reply to Gage EadsThe new rte_stack library is derived from the mempool handler, so this commit removes duplicated code and simplifies the handler by migrating it to this new API.
--- MAINTAINERS | 2 +- drivers/mempool/stack/Makefile | 3 +- drivers/mempool/stack/meson.build | 6 +- drivers/mempool/stack/rte_mempool_stack.c | 93 +++++++++---------------------- 4 files changed, 33 insertions(+), 71 deletions(-)
MAINTAINERS +1 -1
@@ -303,7 +303,6 @@ M: Andrew Rybchenko <[email protected]> F: lib/librte_mempool/ F: drivers/mempool/Makefile F: drivers/mempool/ring/ -F: drivers/mempool/stack/ F: doc/guides/prog_guide/mempool_lib.rst F: app/test/test_mempool* F: app/test/test_func_reentrancy.c
@@ -431,6 +430,7 @@ M: Gage Eads <[email protected]> M: Olivier Matz <[email protected]> F: lib/librte_stack/ F: doc/guides/prog_guide/stack_lib.rst +F: drivers/mempool/stack/ Memory Pool Drivers
drivers/mempool/stack/Makefile +2 -1
@@ -10,10 +10,11 @@ LIB = librte_mempool_stack.a CFLAGS += -O3 CFLAGS += $(WERROR_FLAGS) +CFLAGS += -DALLOW_EXPERIMENTAL_API # Headers CFLAGS += -I$(RTE_SDK)/lib/librte_mempool -LDLIBS += -lrte_eal -lrte_mempool -lrte_ring +LDLIBS += -lrte_eal -lrte_mempool -lrte_stack EXPORT_MAP := rte_mempool_stack_version.map
drivers/mempool/stack/meson.build +5 -1
@@ -1,4 +1,8 @@ # SPDX-License-Identifier: BSD-3-Clause -# Copyright(c) 2017 Intel Corporation +# Copyright(c) 2017-2019 Intel Corporation + +allow_experimental_apis = true sources = files('rte_mempool_stack.c') + +deps += ['stack']
drivers/mempool/stack/rte_mempool_stack.c +25 -68
133 lines not on this page · raw message
Signature · 1 line
2.13.6
PATCH v10 3/8 test/stack: add stack test
In reply to Gage Eadsstack_autotest performs positive and negative testing of the stack API, and exercises the push and pop datapath functions with all available lcores.
--- MAINTAINERS | 1 + app/test/Makefile | 2 + app/test/meson.build | 3 + app/test/test_stack.c | 411 ++++++++++++++++++++++++++++++++++++++++++++++++++ 4 files changed, 417 insertions(+) create mode 100644 app/test/test_stack.c
MAINTAINERS +1 -0
@@ -431,6 +431,7 @@ M: Olivier Matz <[email protected]> F: lib/librte_stack/ F: doc/guides/prog_guide/stack_lib.rst F: drivers/mempool/stack/ +F: app/test/test_stack* Memory Pool Drivers
app/test/Makefile +2 -0
@@ -90,6 +90,8 @@ endif SRCS-y += test_rwlock.c +SRCS-$(CONFIG_RTE_LIBRTE_STACK) += test_stack.c + SRCS-$(CONFIG_RTE_LIBRTE_TIMER) += test_timer.c SRCS-$(CONFIG_RTE_LIBRTE_TIMER) += test_timer_perf.c SRCS-$(CONFIG_RTE_LIBRTE_TIMER) += test_timer_racecond.c
app/test/meson.build +3 -0
@@ -95,6 +95,7 @@ test_sources = files('commands.c', 'test_sched.c', 'test_service_cores.c', 'test_spinlock.c', + 'test_stack.c', 'test_string_fns.c', 'test_table.c', 'test_table_acl.c',
@@ -133,6 +134,7 @@ test_deps = ['acl', 'port', 'reorder', 'ring', + 'stack', 'timer' ]
@@ -174,6 +176,7 @@ fast_parallel_test_names = [ 'rwlock_autotest', 'sched_autotest', 'spinlock_autotest', + 'stack_autotest', 'string_autotest', 'table_autotest', 'tailq_autotest',
app/test/test_stack.c new file +411 -0
411 lines not on this page · raw message
Signature · 1 line
2.13.6
PATCH v10 4/8 test/stack: add stack perf test
In reply to Gage Eadsstack_perf_autotest tests the following with one lcore:
- Cycles to attempt to pop an empty stack
- Cycles to push then pop a single object
- Cycles to push then pop a burst of 32 objects
It also tests the cycles to push then pop a burst of 8 and 32 objects with the following lcore combinations (if possible):
- Two hyperthreads
- Two physical cores
- Two physical cores on separate NUMA nodes
- All available lcores
--- app/test/Makefile | 1 + app/test/meson.build | 2 + app/test/test_stack_perf.c | 345 +++++++++++++++++++++++++++++++++++++++++++++ 3 files changed, 348 insertions(+) create mode 100644 app/test/test_stack_perf.c
app/test/Makefile +1 -0
@@ -91,6 +91,7 @@ endif SRCS-y += test_rwlock.c SRCS-$(CONFIG_RTE_LIBRTE_STACK) += test_stack.c +SRCS-$(CONFIG_RTE_LIBRTE_STACK) += test_stack_perf.c SRCS-$(CONFIG_RTE_LIBRTE_TIMER) += test_timer.c SRCS-$(CONFIG_RTE_LIBRTE_TIMER) += test_timer_perf.c
app/test/meson.build +2 -0
@@ -96,6 +96,7 @@ test_sources = files('commands.c', 'test_service_cores.c', 'test_spinlock.c', 'test_stack.c', + 'test_stack_perf.c', 'test_string_fns.c', 'test_table.c', 'test_table_acl.c',
@@ -241,6 +242,7 @@ perf_test_names = [ 'distributor_perf_autotest', 'ring_pmd_perf_autotest', 'pmd_perf_autotest', + 'stack_perf_autotest', ] # All test cases in driver_test_names list are non-parallel
app/test/test_stack_perf.c new file +345 -0
345 lines not on this page · raw message
Signature · 1 line
2.13.6
PATCH v10 5/8 stack: add lock-free stack implementation
In reply to Gage EadsThis commit adds support for a lock-free (linked list based) stack to the stack API. This behavior is selected through a new rte_stack_create() flag, RTE_STACK_F_LF.
The stack consists of a linked list of elements, each containing a data pointer and a next pointer, and an atomic stack depth counter.
The lock-free push operation enqueues a linked list of pointers by pointing the tail of the list to the current stack head, and using a CAS to swing the stack head pointer to the head of the list. The operation retries if it is unsuccessful (i.e. the list changed between reading the head and modifying it), else it adjusts the stack length and returns.
The lock-free pop operation first reserves num elements by adjusting the stack length, to ensure the dequeue operation will succeed without blocking. It then dequeues pointers by walking the list -- starting from the head -- then swinging the head pointer (using a CAS as well). While walking the list, the data pointers are recorded in an object table.
This algorithm stack uses a 128-bit compare-and-swap instruction, which atomically updates the stack top pointer and a modification counter, to protect against the ABA problem.
The linked list elements themselves are maintained in a lock-free LIFO list, and are allocated before stack pushes and freed after stack pops. Since the stack has a fixed maximum depth, these elements do not need to be dynamically created.
--- doc/guides/prog_guide/stack_lib.rst | 61 +++++++++++- doc/guides/rel_notes/release_19_05.rst | 3 + lib/librte_stack/Makefile | 7 +- lib/librte_stack/meson.build | 7 +- lib/librte_stack/rte_stack.c | 28 ++++-- lib/librte_stack/rte_stack.h | 63 +++++++++++- lib/librte_stack/rte_stack_lf.c | 31 ++++++ lib/librte_stack/rte_stack_lf.h | 102 ++++++++++++++++++++ lib/librte_stack/rte_stack_lf_generic.h | 164 ++++++++++++++++++++++++++++++++ 9 files changed, 447 insertions(+), 19 deletions(-) create mode 100644 lib/librte_stack/rte_stack_lf.c create mode 100644 lib/librte_stack/rte_stack_lf.h create mode 100644 lib/librte_stack/rte_stack_lf_generic.h
doc/guides/prog_guide/stack_lib.rst +58 -3
@@ -10,7 +10,8 @@ stack of pointers. The stack library provides the following basic operations: * Create a uniquely named stack of a user-specified size and using a - user-specified socket. + user-specified socket, with either standard (lock-based) or lock-free + behavior. * Push and pop a burst of one or more stack objects (pointers). These function are multi-threading safe.
@@ -24,5 +25,59 @@ The stack library provides the following basic operations: Implementation ~~~~~~~~~~~~~~ -The stack consists of a contiguous array of pointers, a current index, and a -spinlock. Accesses to the stack are made multi-thread safe by the spinlock. +The library supports two types of stacks: standard (lock-based) and lock-free. +Both types use the same set of interfaces, but their implementations differ. + +Lock-based Stack +---------------- + +The lock-based stack consists of a contiguous array of pointers, a current +index, and a spinlock. Accesses to the stack are made multi-thread safe by the +spinlock. + +Lock-free Stack +------------------ + +The lock-free stack consists of a linked list of elements, each containing a +data pointer and a next pointer, and an atomic stack depth counter. The +lock-free property means that multiple threads can push and pop simultaneously, +and one thread being preempted/delayed in a push or pop operation will not +impede the forward progress of any other thread. + +The lock-free push operation enqueues a linked list of pointers by pointing the +list's tail to the current stack head, and using a CAS to swing the stack head +pointer to the head of the list. The operation retries if it is unsuccessful +(i.e. the list changed between reading the head and modifying it), else it +adjusts the stack length and returns. + +The lock-free pop operation first reserves one or more list elements by +adjusting the stack length, to ensure the dequeue operation will succeed +without blocking. It then dequeues pointers by walking the list -- starting +from the head -- then swinging the head pointer (using a CAS as well). While +walking the list, the data pointers are recorded in an object table. + +The linked list elements themselves are maintained in a lock-free LIFO, and are +allocated before stack pushes and freed after stack pops. Since the stack has a +fixed maximum depth, these elements do not need to be dynamically created. + +The lock-free behavior is selected by passing the *RTE_STACK_F_LF* flag to +rte_stack_create(). + +Preventing the ABA Problem +^^^^^^^^^^^^^^^^^^^^^^^^^^ + +To prevent the ABA problem, this algorithm stack uses a 128-bit +compare-and-swap instruction to atomically update both the stack top pointer +and a modification counter. The ABA problem can occur without a modification +counter if, for example: + +1. Thread A reads head pointer X and stores the pointed-to list element. +2. Other threads modify the list such that the head pointer is once again X, + but its pointed-to data is different than what thread A read. +3. Thread A changes the head pointer with a compare-and-swap and succeeds. + +In this case thread A would not detect that the list had changed, and would +both pop stale data and incorrect change the head pointer. By adding a +modification counter that is updated on every push and pop as part of the +compare-and-swap, the algorithm can detect when the list changes even if the +head pointer remains the same.
doc/guides/rel_notes/release_19_05.rst +3 -0
@@ -127,6 +127,9 @@ New Features pointers. The API provides MT-safe push and pop operations that can operate on one or more pointers per operation. + The library supports two stack implementations: standard (lock-based) and lock-free. + The lock-free implementation is currently limited to x86-64 platforms. + Removed Items -------------
lib/librte_stack/Makefile +5 -2
@@ -16,10 +16,13 @@ LIBABIVER := 1 # all source are stored in SRCS-y SRCS-$(CONFIG_RTE_LIBRTE_STACK) := rte_stack.c \ - rte_stack_std.c + rte_stack_std.c \ + rte_stack_lf.c # install includes SYMLINK-$(CONFIG_RTE_LIBRTE_STACK)-include := rte_stack.h \ - rte_stack_std.h + rte_stack_std.h \ + rte_stack_lf.h \ + rte_stack_lf_generic.h include $(RTE_SDK)/mk/rte.lib.mk
lib/librte_stack/meson.build +5 -2
@@ -4,5 +4,8 @@ allow_experimental_apis = true version = 1 -sources = files('rte_stack.c', 'rte_stack_std.c') -headers = files('rte_stack.h', 'rte_stack_std.h') +sources = files('rte_stack.c', 'rte_stack_std.c', 'rte_stack_lf.c') +headers = files('rte_stack.h', + 'rte_stack_std.h', + 'rte_stack_lf.h', + 'rte_stack_lf_generic.h')
lib/librte_stack/rte_stack.c +21 -7
@@ -25,18 +25,25 @@ static struct rte_tailq_elem rte_stack_tailq = { };EAL_REGISTER_TAILQ (rte_stack_tailq) + static void -rte_stack_init (struct rte_stack *s) +rte_stack_init (struct rte_stack *s,unsigned int count,uint32_t flags) {memset (s,0 ,sizeof (*s)); -rte_stack_std_init (s); +if (flags &RTE_STACK_F_LF ) +rte_stack_lf_init (s, count); +else +rte_stack_std_init (s); }static ssize_t -rte_stack_get_memsize (unsigned int count) +rte_stack_get_memsize (unsigned int count,uint32_t flags) { -return rte_stack_std_get_memsize (count); +if (flags &RTE_STACK_F_LF ) +return rte_stack_lf_get_memsize (count); +else +return rte_stack_std_get_memsize (count); } struct rte_stack *
@@ -51,9 +58,16 @@ rte_stack_create(const char *name, unsigned int count, int socket_id,unsigned int sz;int ret; -RTE_SET_USED (flags); +#ifdef RTE_ARCH_64 +RTE_BUILD_BUG_ON (sizeof (struct rte_stack_lf_head ) !=16 ); +#else +if (flags &RTE_STACK_F_LF ) { +STACK_LOG_ERR ("Lock-free stack is not supported on your platform\n" ); +return NULL ; + } +#endif - sz =rte_stack_get_memsize (count); + sz =rte_stack_get_memsize (count, flags); ret =snprintf (mz_name,sizeof (mz_name),"%s%s" ,RTE_STACK_MZ_PREFIX , name);
@@ -82,7 +96,7 @@ rte_stack_create(const char *name, unsigned int count, int socket_id, s = mz->addr; -rte_stack_init (s); +rte_stack_init (s, count, flags);/* Store the name for later lookups */ ret =snprintf (s->name,sizeof (s->name),"%s" , name);
lib/librte_stack/rte_stack.h +58 -5
108 lines not on this page · raw message
lib/librte_stack/rte_stack_lf.c new file +31 -0
@@ -0,0 +1,31 @@ +/* SPDX-License-Identifier: BSD-3-Clause +* Copyright(c) 2019 Intel Corporation +*/ + +#include "rte_stack.h" + +void +rte_stack_lf_init (struct rte_stack *s,unsigned int count) +{ +struct rte_stack_lf_elem *elems = s->stack_lf.elems; +unsigned int i; + +for (i =0 ; i < count; i++) +__rte_stack_lf_push_elems (&s->stack_lf.free, + &elems[i], &elems[i],1 ); +} + +ssize_t +rte_stack_lf_get_memsize (unsigned int count) +{ +ssize_t sz =sizeof (struct rte_stack ); + + sz +=RTE_CACHE_LINE_ROUNDUP (count *sizeof (struct rte_stack_lf_elem )); + +/* Add padding to avoid false sharing conflicts caused by +* next-line hardware prefetchers. +*/ + sz +=2 *RTE_CACHE_LINE_SIZE ; + +return sz; +}
lib/librte_stack/rte_stack_lf.h new file +102 -0
102 lines not on this page · raw message
lib/librte_stack/rte_stack_lf_generic.h new file +164 -0
164 lines not on this page · raw message
Signature · 1 line
2.13.6
PATCH v10 6/8 stack: add C11 atomic implementation
In reply to Gage EadsThis commit adds an implementation of the lock-free stack push, pop, and length functions that use __atomic builtins, for systems that benefit from the finer-grained memory ordering control.
--- lib/librte_stack/Makefile | 3 +- lib/librte_stack/meson.build | 3 +- lib/librte_stack/rte_stack_lf.h | 4 + lib/librte_stack/rte_stack_lf_c11.h | 175 ++++++++++++++++++++++++++++++++++++ 4 files changed, 183 insertions(+), 2 deletions(-) create mode 100644 lib/librte_stack/rte_stack_lf_c11.h
lib/librte_stack/Makefile +2 -1
@@ -23,6 +23,7 @@ SRCS-$(CONFIG_RTE_LIBRTE_STACK) := rte_stack.c \ SYMLINK-$(CONFIG_RTE_LIBRTE_STACK)-include := rte_stack.h \ rte_stack_std.h \ rte_stack_lf.h \ - rte_stack_lf_generic.h + rte_stack_lf_generic.h \ + rte_stack_lf_c11.h include $(RTE_SDK)/mk/rte.lib.mk
lib/librte_stack/meson.build +2 -1
@@ -8,4 +8,5 @@ sources = files('rte_stack.c', 'rte_stack_std.c', 'rte_stack_lf.c') headers = files('rte_stack.h', 'rte_stack_std.h', 'rte_stack_lf.h', - 'rte_stack_lf_generic.h') + 'rte_stack_lf_generic.h', + 'rte_stack_lf_c11.h')
lib/librte_stack/rte_stack_lf.h +4 -0
@@ -5,7 +5,11 @@#ifndef _RTE_STACK_LF_H_#define _RTE_STACK_LF_H_ +#ifdef RTE_USE_C11_MEM_MODEL +#include "rte_stack_lf_c11.h" +#else #include "rte_stack_lf_generic.h" +#endif /** * @internal Push several objects on the lock-free stack (MT-safe).
lib/librte_stack/rte_stack_lf_c11.h new file +175 -0
175 lines not on this page · raw message
Signature · 1 line
2.13.6
PATCH v10 7/8 test/stack: add lock-free stack tests
In reply to Gage EadsThis commit adds lock-free stack variants of stack_autotest (stack_lf_autotest) and stack_perf_autotest (stack_lf_perf_autotest), which differ only in that the lock-free versions pass the RTE_STACK_F_LF flag to all rte_stack_create() calls.
--- app/test/meson.build | 2 ++ app/test/test_stack.c | 41 +++++++++++++++++++++++++++-------------- app/test/test_stack_perf.c | 17 +++++++++++++++-- 3 files changed, 44 insertions(+), 16 deletions(-)
app/test/meson.build +2 -0
@@ -178,6 +178,7 @@ fast_parallel_test_names = [ 'sched_autotest', 'spinlock_autotest', 'stack_autotest', + 'stack_nb_autotest', 'string_autotest', 'table_autotest', 'tailq_autotest',
@@ -243,6 +244,7 @@ perf_test_names = [ 'ring_pmd_perf_autotest', 'pmd_perf_autotest', 'stack_perf_autotest', + 'stack_nb_perf_autotest', ] # All test cases in driver_test_names list are non-parallel
app/test/test_stack.c +27 -14
112 lines not on this page · raw message
app/test/test_stack_perf.c +15 -2
@@ -299,14 +299,14 @@ test_bulk_push_pop(struct rte_stack *s) }static int -test_stack_perf (void ) +__test_stack_perf (uint32_t flags) {struct lcore_pair cores;struct rte_stack *s;rte_atomic32_init (&lcore_barrier); - s =rte_stack_create (STACK_NAME ,STACK_SIZE ,rte_socket_id (),0 ); + s =rte_stack_create (STACK_NAME ,STACK_SIZE ,rte_socket_id (), flags);if (s ==NULL ) {printf ("[%s():%u] failed to create a stack\n" , __func__, __LINE__);
@@ -342,4 +342,17 @@ test_stack_perf(void)return 0 ; } +static int +test_stack_perf (void ) +{ +return __test_stack_perf (0 ); +} + +static int +test_lf_stack_perf (void ) +{ +return __test_stack_perf (RTE_STACK_F_LF ); +} +REGISTER_TEST_COMMAND (stack_perf_autotest, test_stack_perf); +REGISTER_TEST_COMMAND (stack_lf_perf_autotest, test_lf_stack_perf);
Signature · 1 line
2.13.6
PATCH v10 8/8 mempool/stack: add lock-free stack mempool handler
In reply to Gage EadsThis commit adds support for lock-free (linked list based) stack mempool handler.
In mempool_perf_autotest the lock-based stack outperforms the lock-free handler for certain lcore/alloc count/free count combinations*, however:
- For applications with preemptible pthreads, a standard (lock-based) stack's worst-case performance (i.e. one thread being preempted while holding the spinlock) is much worse than the lock-free stack's.
- Using per-thread mempool caches will largely mitigate the performance difference.
*Test setup: x86_64 build with default config, dual-socket Xeon E5-2699 v4, running on isolcpus cores with a tickless scheduler. The lock-based stack's rate_persec was 0.6x-3.5x the lock-free stack's.
--- doc/guides/prog_guide/env_abstraction_layer.rst | 10 ++++++++++ doc/guides/rel_notes/release_19_05.rst | 5 +++++ drivers/mempool/stack/rte_mempool_stack.c | 26 +++++++++++++++++++++++-- 3 files changed, 39 insertions(+), 2 deletions(-)
doc/guides/prog_guide/env_abstraction_layer.rst +10 -0
@@ -581,6 +581,16 @@ Known Issues 5. It MUST not be used by multi-producer/consumer pthreads, whose scheduling policies are SCHED_FIFO or SCHED_RR. + Alternatively, applications can use the lock-free stack mempool handler. When + considering this handler, note that: + + - It is currently limited to the x86_64 platform, because it uses an + instruction (16-byte compare-and-swap) that is not yet available on other + platforms. + - It has worse average-case performance than the non-preemptive rte_ring, but + software caching (e.g. the mempool cache) can mitigate this by reducing the + number of stack accesses. + + rte_timer Running ``rte_timer_manage()`` on a non-EAL pthread is not allowed. However, resetting/stopping the timer from a non-EAL pthread is allowed.
doc/guides/rel_notes/release_19_05.rst +5 -0
@@ -130,6 +130,11 @@ New Features The library supports two stack implementations: standard (lock-based) and lock-free. The lock-free implementation is currently limited to x86-64 platforms. +* **Added Lock-Free Stack Mempool Handler.** + + Added a new lock-free stack handler, which uses the newly added stack + library. + Removed Items -------------
drivers/mempool/stack/rte_mempool_stack.c +24 -2
@@ -7,7 +7,7 @@#include <rte_stack.h> static int -stack_alloc (struct rte_mempool *mp) +__stack_alloc (struct rte_mempool *mp,uint32_t flags) {char name[RTE_STACK_NAMESIZE ];struct rte_stack *s;
@@ -20,7 +20,7 @@ stack_alloc(struct rte_mempool *mp)return -rte_errno; } - s =rte_stack_create (name, mp->size, mp->socket_id,0 ); + s =rte_stack_create (name, mp->size, mp->socket_id, flags);if (s ==NULL )return -rte_errno;
@@ -30,6 +30,18 @@ stack_alloc(struct rte_mempool *mp) }static int +stack_alloc (struct rte_mempool *mp) +{ +return __stack_alloc (mp,0 ); +} + +static int +lf_stack_alloc (struct rte_mempool *mp) +{ +return __stack_alloc (mp,RTE_STACK_F_LF ); +} + +static int stack_enqueue (struct rte_mempool *mp,void *const *obj_table,unsigned int n) {
@@ -72,4 +84,14 @@ static struct rte_mempool_ops ops_stack = { .get_count = stack_get_count }; +static struct rte_mempool_ops ops_lf_stack = { + .name ="lf_stack" , + .alloc = lf_stack_alloc, + .free = stack_free, + .enqueue = stack_enqueue, + .dequeue = stack_dequeue, + .get_count = stack_get_count +}; +MEMPOOL_REGISTER_OPS (ops_stack); +MEMPOOL_REGISTER_OPS (ops_lf_stack);
Signature · 1 line
2.13.6
Re: [PATCH v10 0/8] Add stack library and new mempool handler
In reply to Gage Eads04/04/2019 12:01, Gage Eads:
Quoted 13 lines
This patchset introduces a stack library, supporting both lock-based and lock-free stacks, and a lock-free stack mempool handler.
The lock-based stack code is derived from the existing stack mempool handler, and that handler is refactored to use the stack library.
The lock-free stack mempool handler is intended for usages where the rte ring's "non-preemptive" constraint is not acceptable; for example, if the application uses a mixture of pinned high-priority threads and multiplexed low-priority threads that share a mempool.
Note that the lock-free algorithm relies on a 128-bit compare-and-swap[1], so it is currently limited to the
x86_64platform.
[...]
Quoted 9 lines
Gage Eads (8):
stack: introduce rte stack library mempool/stack: convert mempool to use rte stack test/stack: add stack test
test/stack: add stack perf test
stack: add lock-free stack implementation
stack: add C11 atomic implementation test/stack: add lock-free stack tests mempool/stack: add lock-free stack mempool handler
Applied (with a few minor changes), thanks for bringing this new library.