Skip to contentSkip to conversation

Subject: [PATCH ...] Add stack library and new mempool handler

PATCH Superseded Gage Eads 4 participants 133 messages Feb 22, 2019 – Apr 4, 2019 1 message not in the archive Page 2 of 2

Subsystems (2)
lore
Share & tools
lore
author
#113 lore raw

PATCH v9 1/8 stack: introduce rte stack library

In reply to Gage Eads

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
index 71ac8cd4b..f30fc4aa6 100644
@@ -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
index 6292bc4af..fc8dba69d 100644
@@ -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
index aacc66bd8..de1e215dd 100644
@@ -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
index a365e669b..7722fc3e9 100644
@@ -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
index 6726b1e8d..f4f60862f 100644
@@ -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
new file mode 100644
index 000000000..25a8cc38a
@@ -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
index bdad1ddbe..ebfbe36e5 100644
@@ -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
index a358f1c19..9f90e80ad 100644
@@ -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
new file mode 100644
index 000000000..6db540073
@@ -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
new file mode 100644
index 000000000..d2e60ce9b
@@ -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
new file mode 100644
index 000000000..4a6a7bdb3
@@ -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
new file mode 100644
index 000000000..0a310d7c6
@@ -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
new file mode 100644
index 000000000..6662679c3
@@ -0,0 +1,9 @@
+EXPERIMENTAL {
+	global:
+
+	rte_stack_create;
+	rte_stack_free;
+	rte_stack_lookup;
+
+	local: *;
+};
lib/meson.build +1 -1
index c3289f885..595314d7d 100644
@@ -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
index 262132fc6..7e033e78c 100644
@@ -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
#114 lore raw

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).

author
#115 lore raw

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 library

04/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_security

mk/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_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).

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.

author
#116 lore raw

PATCH v9 2/8 mempool/stack: convert mempool to use rte stack

In reply to Gage Eads

The 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
index f30fc4aa6..e09e7d93f 100644
@@ -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
index 0444aedad..1681a62bc 100644
@@ -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
index b75a3bb56..03e369a41 100644
@@ -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
author
#117 lore raw

PATCH v9 3/8 test/stack: add stack test

In reply to Gage Eads

stack_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
index e09e7d93f..e4e6d1b15 100644
@@ -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
index d6aa28bad..e5bde81af 100644
@@ -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
index c5e65fe66..56ea13f53 100644
@@ -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
#118 lore raw

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*

author
#119 lore raw

PATCH v9 4/8 test/stack: add stack perf test

In reply to Gage Eads

stack_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
index e5bde81af..b28bed2d4 100644
@@ -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
index 56ea13f53..02eb788a4 100644
@@ -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
author
#120 lore raw

PATCH v9 5/8 stack: add lock-free stack implementation

In reply to Gage Eads

This 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
index 25a8cc38a..8fe8804e3 100644
@@ -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
index ebfbe36e5..3b115b5f6 100644
@@ -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
index 6db540073..311edd997 100644
@@ -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
index d2e60ce9b..7a09a5d66 100644
@@ -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
index 610014b6c..1a4d9bd1e 100644
@@ -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
new file mode 100644
index 000000000..0adcc263e
@@ -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
author
#121 lore raw

PATCH v9 6/8 stack: add C11 atomic implementation

In reply to Gage Eads

This 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
index 311edd997..8d18ce520 100644
@@ -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
index 7a09a5d66..46fce0c20 100644
@@ -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
index bfd680133..518889a05 100644
@@ -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
author
#122 lore raw

PATCH v9 7/8 test/stack: add lock-free stack tests

In reply to Gage Eads

This 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
index 02eb788a4..867cc5863 100644
@@ -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
index a44fbb73e..ba27fbf70 100644
@@ -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
author
#123 lore raw

PATCH v9 8/8 mempool/stack: add lock-free stack mempool handler

In reply to Gage Eads

This 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
index 6a04c3c33..fa8afdb3a 100644
@@ -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
index 3b115b5f6..f873984ad 100644
@@ -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
index 25ccdb9af..7e85c8d6b 100644
@@ -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
author
#124 lore raw

v10 cover Add stack library and new mempool handler

In reply to Gage Eads

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_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
author
#125 lore raw

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
index 71ac8cd4b..f30fc4aa6 100644
@@ -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
index 6292bc4af..fc8dba69d 100644
@@ -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
index aacc66bd8..de1e215dd 100644
@@ -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
index a365e669b..7722fc3e9 100644
@@ -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
index 6726b1e8d..f4f60862f 100644
@@ -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
new file mode 100644
index 000000000..25a8cc38a
@@ -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
index bdad1ddbe..ebfbe36e5 100644
@@ -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
index a358f1c19..9f90e80ad 100644
@@ -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
new file mode 100644
index 000000000..6db540073
@@ -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
new file mode 100644
index 000000000..d2e60ce9b
@@ -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
new file mode 100644
index 000000000..4a6a7bdb3
@@ -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
new file mode 100644
index 000000000..0a310d7c6
@@ -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
new file mode 100644
index 000000000..6662679c3
@@ -0,0 +1,9 @@
+EXPERIMENTAL {
+	global:
+
+	rte_stack_create;
+	rte_stack_free;
+	rte_stack_lookup;
+
+	local: *;
+};
lib/meson.build +1 -1
index c3289f885..595314d7d 100644
@@ -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
index 262132fc6..7e033e78c 100644
@@ -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
author
#126 lore raw

PATCH v10 2/8 mempool/stack: convert mempool to use rte stack

In reply to Gage Eads

The 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
index f30fc4aa6..e09e7d93f 100644
@@ -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
index 0444aedad..1681a62bc 100644
@@ -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
index b75a3bb56..03e369a41 100644
@@ -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
author
#127 lore raw

PATCH v10 3/8 test/stack: add stack test

In reply to Gage Eads

stack_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
index e09e7d93f..332ae98d7 100644
@@ -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
index d6aa28bad..e5bde81af 100644
@@ -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
index c5e65fe66..56ea13f53 100644
@@ -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
author
#128 lore raw

PATCH v10 4/8 test/stack: add stack perf test

In reply to Gage Eads

stack_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
index e5bde81af..b28bed2d4 100644
@@ -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
index 56ea13f53..02eb788a4 100644
@@ -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
author
#129 lore raw

PATCH v10 5/8 stack: add lock-free stack implementation

In reply to Gage Eads

This 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
index 25a8cc38a..8fe8804e3 100644
@@ -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
index ebfbe36e5..3b115b5f6 100644
@@ -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
index 6db540073..311edd997 100644
@@ -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
index d2e60ce9b..7a09a5d66 100644
@@ -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
index 610014b6c..1a4d9bd1e 100644
@@ -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
new file mode 100644
index 000000000..0adcc263e
@@ -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
author
#130 lore raw

PATCH v10 6/8 stack: add C11 atomic implementation

In reply to Gage Eads

This 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
index 311edd997..8d18ce520 100644
@@ -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
index 7a09a5d66..46fce0c20 100644
@@ -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
index bfd680133..518889a05 100644
@@ -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
author
#131 lore raw

PATCH v10 7/8 test/stack: add lock-free stack tests

In reply to Gage Eads

This 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
index 02eb788a4..867cc5863 100644
@@ -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
index a44fbb73e..ba27fbf70 100644
@@ -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
author
#132 lore raw

PATCH v10 8/8 mempool/stack: add lock-free stack mempool handler

In reply to Gage Eads

This 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
index 6a04c3c33..fa8afdb3a 100644
@@ -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
index 3b115b5f6..f873984ad 100644
@@ -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
index 25ccdb9af..7e85c8d6b 100644
@@ -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
#133 lore raw

Re: [PATCH v10 0/8] Add stack library and new mempool handler

In reply to Gage Eads

04/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_64 platform.

[...]

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.