Skip to contentSkip to conversation

Add non-blocking stack mempool handler

PATCH Superseded Gage Eads 7 participants 43 messages Jan 10, 2019 – Jan 25, 2019 Arm/Amlogic Meson SoC support

lore
Share & tools
lore

Gage Eads

author
#0 lore raw

cover Add non-blocking stack mempool handler

For some users, 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.

This patchset introduces a non-blocking stack mempool handler. Note that the non-blocking algorithm relies on a 128-bit compare-and-swap, so it is limited to x86_64 machines.

In mempool_perf_autotest the lock-based stack outperforms the non-blocking handler*, however:
- For applications with preemptible pthreads, a lock-based stack's worst-case performance (i.e. one thread being preempted while holding the spinlock) is much worse than the non-blocking 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 1x-3.5x the non-blocking stack's.

Gage Eads (3):
eal: add 128-bit cmpset (x86-64 only) mempool/nb_stack: add non-blocking stack mempool
doc: add NB stack comment to EAL "known issues"

 MAINTAINERS                                        |   4 +
 config/common_base                                 |   1 +
 doc/guides/prog_guide/env_abstraction_layer.rst    |   5 +
 drivers/mempool/Makefile                           |   1 +
 drivers/mempool/nb_stack/Makefile                  |  30 +++++
 drivers/mempool/nb_stack/meson.build               |   4 +
 drivers/mempool/nb_stack/nb_lifo.h                 | 132 +++++++++++++++++++++
 drivers/mempool/nb_stack/rte_mempool_nb_stack.c    | 125 +++++++++++++++++++
 .../nb_stack/rte_mempool_nb_stack_version.map      |   4 +
 .../common/include/arch/x86/rte_atomic_64.h        |  22 ++++
 mk/rte.app.mk                                      |   1 +
 11 files changed, 329 insertions(+)
 create mode 100644 drivers/mempool/nb_stack/Makefile
 create mode 100644 drivers/mempool/nb_stack/meson.build
 create mode 100644 drivers/mempool/nb_stack/nb_lifo.h
 create mode 100644 drivers/mempool/nb_stack/rte_mempool_nb_stack.c
 create mode 100644 drivers/mempool/nb_stack/rte_mempool_nb_stack_version.map
Signature · 1 line
2.13.6
author
#1 lore raw

PATCH 1/3 eal: add 128-bit cmpset (x86-64 only)

This operation can be used for non-blocking algorithms, such as a non-blocking stack or ring.

---
 .../common/include/arch/x86/rte_atomic_64.h        | 22 ++++++++++++++++++++++
 1 file changed, 22 insertions(+)
lib/librte_eal/common/include/arch/x86/rte_atomic_64.h +22 -0
index fd2ec9c53..34c2addf8 100644
@@ -34,6 +34,7 @@
 /*
  * Inspired from FreeBSD src/sys/amd64/include/atomic.h
  * Copyright (c) 1998 Doug Rabson
+ * Copyright (c) 2019 Intel Corporation
  * All rights reserved.
  */
 
@@ -208,4 +209,25 @@ static inline void rte_atomic64_clear(rte_atomic64_t *v)
 }
 #endif
 
+static inline int
+rte_atomic128_cmpset(volatile uint64_t *dst, uint64_t *exp, uint64_t *src)
+{
+	uint8_t res;
+
+	asm volatile (
+		      MPLOCKED
+		      "cmpxchg16b %[dst];"
+		      " sete %[res]"
+		      : [dst] "=m" (*dst),
+			[res] "=r" (res)
+		      : "c" (src[1]),
+			"b" (src[0]),
+			"m" (*dst),
+			"d" (exp[1]),
+			"a" (exp[0])
+		      : "memory");
+
+	return res;
+}
+
 #endif /* _RTE_ATOMIC_X86_64_H_ */
Signature · 1 line
2.13.6
#2 lore raw

Re: [PATCH 1/3] eal: add 128-bit cmpset (x86-64 only)

Quoted 36 lines · Gage Eads

This operation can be used for non-blocking algorithms, such as a non-blocking stack or ring.

---
  .../common/include/arch/x86/rte_atomic_64.h        | 22 ++++++++++++++++++++++
  1 file changed, 22 insertions(+)
lib/librte_eal/common/include/arch/x86/rte_atomic_64.h +13 -0
index fd2ec9c53..34c2addf8 100644
@@ -34,6 +34,7 @@
  /*
   * Inspired from FreeBSD src/sys/amd64/include/atomic.h
   * Copyright (c) 1998 Doug Rabson
+ * Copyright (c) 2019 Intel Corporation
   * All rights reserved.
   */
 
@@ -208,4 +209,25 @@ static inline void rte_atomic64_clear(rte_atomic64_t *v)
  }
  #endif
 
+static inline int
+rte_atomic128_cmpset(volatile uint64_t *dst, uint64_t *exp, uint64_t *src)
+{
+	uint8_t res;
+
+	asm volatile (
+		      MPLOCKED
+		      "cmpxchg16b %[dst];"
+		      " sete %[res]"
+		      : [dst] "=m" (*dst),
+			[res] "=r" (res)
+		      : "c" (src[1]),

lib/librte_eal/common/include/arch/x86/rte_atomic_64.h static inline void rte_atomic64_clear(rte_atomic64_t *v) · line 233

Quoted 10 lines
lib/librte_eal/common/include/arch/x86/rte_atomic_64.h +9 -0
+			"b" (src[0]),
+			"m" (*dst),
+			"d" (exp[1]),
+			"a" (exp[0])
+		      : "memory");
+
+	return res;
+}
+
  #endif /* _RTE_ATOMIC_X86_64_

Is it OK to add it to rte_atomic_64.h header which is for 64-bit integer ops?

Andrew.

Quoted 1 line

H_ */

#3 lore raw

Re: [PATCH 1/3] eal: add 128-bit cmpset (x86-64 only)

Hi Gage,

snipped

Quoted 14 lines

Review static inline void

Quoted 1 line
(quoted diff) +0 -0
@@ -208,4 +209,25 @@ static inline void

rte_atomic64_clear(rte_atomic64_t *v)

Quoted 12 lines
lib/librte_eal/common/include/arch/x86/rte_atomic_64.h +9 -0
  }
  #endif
 
+static inline int
+rte_atomic128_cmpset(volatile uint64_t *dst, uint64_t *exp, uint64_t
+*src) {
+	uint8_t res;
+
+	asm volatile (
+		      MPLOCKED
+		      "cmpxchg16b %[dst];"
+		      " sete %[res]"
Quoted 8 lines

lib/librte_eal/common/include/arch/x86/rte_atomic_64.h static inline void rte_atomic64_clear(rte_atomic64_t *v) · line 228

Quoted 8 lines
lib/librte_eal/common/include/arch/x86/rte_atomic_64.h +8 -0
+		      : [dst] "=m" (*dst),
+			[res] "=r" (res)
+		      : "c" (src[1]),
+			"b" (src[0]),
+			"m" (*dst),
+			"d" (exp[1]),
+			"a" (exp[0])
+		      : "memory");

Since update depends upon on the 'set|unset' value of ZF, should we first set ZF to 0?

Apologies in advance if it is internally taken care by 'sete'.

Quoted 10 lines

lib/librte_eal/common/include/arch/x86/rte_atomic_64.h static inline void rte_atomic64_clear(rte_atomic64_t *v)

Quoted 5 lines
lib/librte_eal/common/include/arch/x86/rte_atomic_64.h +4 -0
+
+	return res;
+}
+
  #endif /* _RTE_ATOMIC_X86_64_

Is it OK to add it to rte_atomic_64.h header which is for 64-bit integer ops?

Andrew.

Quoted 1 line

H_ */

author
#4 lore raw

Re: [PATCH 1/3] eal: add 128-bit cmpset (x86-64 only)

Quoted 39 lines

-----Original Message-----
From: Varghese, Vipin
Sent: Sunday, January 13, 2019 10:29 PM
To: Andrew Rybchenko <[email protected]>; Eads, Gage <[email protected]>; [email protected]
Cc: [email protected]; Richardson, Bruce <[email protected]>; Ananyev, Konstantin <[email protected]>
Subject: RE: [dpdk-dev] [PATCH 1/3] eal: add 128-bit cmpset (x86-64 only)

Hi Gage,

snipped

Quoted 14 lines

Review static inline void

Quoted 1 line
(quoted diff) +0 -0
@@ -208,4 +209,25 @@ static inline void

rte_atomic64_clear(rte_atomic64_t *v)

Quoted 12 lines
lib/librte_eal/common/include/arch/x86/rte_atomic_64.h +9 -0
  }
  #endif
 
+static inline int
+rte_atomic128_cmpset(volatile uint64_t *dst, uint64_t *exp, uint64_t
+*src) {
+	uint8_t res;
+
+	asm volatile (
+		      MPLOCKED
+		      "cmpxchg16b %[dst];"
+		      " sete %[res]"
Quoted 8 lines

lib/librte_eal/common/include/arch/x86/rte_atomic_64.h static inline void rte_atomic64_clear(rte_atomic64_t *v) · line 228

Quoted 8 lines
lib/librte_eal/common/include/arch/x86/rte_atomic_64.h +8 -0
+		      : [dst] "=m" (*dst),
+			[res] "=r" (res)
+		      : "c" (src[1]),
+			"b" (src[0]),
+			"m" (*dst),
+			"d" (exp[1]),
+			"a" (exp[0])
+		      : "memory");

Since update depends upon on the 'set|unset' value of ZF, should we first set ZF to 0?

Quoted 1 line

Apologies in advance if it is internally taken care by 'sete'.

cmpxchg16b will set the ZF if the compared values are equal, else it will clear the ZF, so there's no need to initialize the ZF.

Source: https://www.felixcloutier.com/x86/cmpxchg8b:cmpxchg16b

Thanks,
Gage

#5 lore raw

Re: [PATCH 1/3] eal: add 128-bit cmpset (x86-64 only)

Thanks Gage for clarifying and correcting. Appreciate the same.

Quoted 60 lines

-----Original Message-----
From: Eads, Gage
Sent: Monday, January 14, 2019 9:17 PM
To: Varghese, Vipin <[email protected]>; Andrew Rybchenko <[email protected]>; [email protected]
Cc: [email protected]; Richardson, Bruce <[email protected]>; Ananyev, Konstantin <[email protected]>
Subject: RE: [dpdk-dev] [PATCH 1/3] eal: add 128-bit cmpset (x86-64 only)

Quoted 40 lines

-----Original Message-----
From: Varghese, Vipin
Sent: Sunday, January 13, 2019 10:29 PM
To: Andrew Rybchenko <[email protected]>; Eads, Gage <[email protected]>; [email protected]
Cc: [email protected]; Richardson, Bruce <[email protected]>; Ananyev, Konstantin <[email protected]>
Subject: RE: [dpdk-dev] [PATCH 1/3] eal: add 128-bit cmpset (x86-64 only)

Hi Gage,

snipped

Quoted 15 lines

Review static inline void

Quoted 1 line
(quoted diff) +0 -0
@@ -208,4 +209,25 @@ static inline void

rte_atomic64_clear(rte_atomic64_t *v)

Quoted 13 lines
lib/librte_eal/common/include/arch/x86/rte_atomic_64.h +10 -0
  }
  #endif
 
+static inline int
+rte_atomic128_cmpset(volatile uint64_t *dst, uint64_t *exp,
+uint64_t
+*src) {
+	uint8_t res;
+
+	asm volatile (
+		      MPLOCKED
+		      "cmpxchg16b %[dst];"
+		      " sete %[res]"
Quoted 8 lines

lib/librte_eal/common/include/arch/x86/rte_atomic_64.h static inline void rte_atomic64_clear(rte_atomic64_t *v) · line 228

Quoted 8 lines
lib/librte_eal/common/include/arch/x86/rte_atomic_64.h +8 -0
+		      : [dst] "=m" (*dst),
+			[res] "=r" (res)
+		      : "c" (src[1]),
+			"b" (src[0]),
+			"m" (*dst),
+			"d" (exp[1]),
+			"a" (exp[0])
+		      : "memory");

Since update depends upon on the 'set|unset' value of ZF, should we first set ZF to 0?

Quoted 1 line

Apologies in advance if it is internally taken care by 'sete'.

cmpxchg16b will set the ZF if the compared values are equal, else it will clear the ZF, so there's no need to initialize the ZF.

Source: https://www.felixcloutier.com/x86/cmpxchg8b:cmpxchg16b

Thanks,
Gage

author
#6 lore raw

Re: [PATCH 1/3] eal: add 128-bit cmpset (x86-64 only)

In reply to Andrew Rybchenko

From: Andrew Rybchenko [mailto:[email protected]]
Sent: Sunday, January 13, 2019 6:19 AM
To: Eads, Gage <[email protected]>; [email protected]
Cc: [email protected]; Richardson, Bruce <[email protected]>; Ananyev, Konstantin <[email protected]>
Subject: Re: [PATCH 1/3] eal: add 128-bit cmpset (x86-64 only)

On 1/10/19 11:55 PM, Gage Eads wrote:

This operation can be used for non-blocking algorithms, such as a

non-blocking stack or ring.

---

 .../common/include/arch/x86/rte_atomic_64.h        | 22 ++++++++++++++++++++++
 1 file changed, 22 insertions(+)
lib/librte_eal/common/include/arch/x86/rte_atomic_64.h +0 -0

index fd2ec9c53..34c2addf8 100644

--- a/lib/librte_eal/common/include/arch/x86/rte_atomic_64.h

+++ b/lib/librte_eal/common/include/arch/x86/rte_atomic_64.h

@@ -34,6 +34,7 @@

/*

* Inspired from FreeBSD src/sys/amd64/include/atomic.h

* Copyright (c) 1998 Doug Rabson

+ * Copyright (c) 2019 Intel Corporation

* All rights reserved.

*/

@@ -208,4 +209,25 @@ static inline void rte_atomic64_clear(rte_atomic64_t *v)

}

#endif

+static inline int

+rte_atomic128_cmpset(volatile uint64_t *dst, uint64_t *exp, uint64_t *src)

+{

+ uint8_t res;

+

+ asm volatile (

+ MPLOCKED

+ "cmpxchg16b %[dst];"

+ " sete %[res]"

+ : [dst] "=m" (*dst),

+ [res] "=r" (res)

+ : "c" (src[1]),

+ "b" (src[0]),

+ "m" (*dst),

+ "d" (exp[1]),

+ "a" (exp[0])

+ : "memory");

+

+ return res;

+}

+

#endif /* _RTE_ATOMIC_X86_64_

Is it OK to add it to rte_atomic_64.h header which is for 64-bit integer ops?

Andrew.

I believe this file is for atomic operations specific to x86_64 builds, but not necessarily limited to 64-bit operations (note that rte_atomic_32.h contains 64-bit operations specific to 32-bit builds). At least, that’s how I interpreted it.

author
#7 lore raw

PATCH 2/3 mempool/nb_stack: add non-blocking stack mempool

In reply to Gage Eads

This commit adds support for non-blocking (linked list based) stack mempool handler. The stack uses a 128-bit compare-and-swap instruction, and thus is limited to x86_64. The 128-bit CAS atomically updates the stack top pointer and a modification counter, which protects against the ABA problem.

In mempool_perf_autotest the lock-based stack outperforms the non-blocking handler*, however:
- For applications with preemptible pthreads, a lock-based stack's worst-case performance (i.e. one thread being preempted while holding the spinlock) is much worse than the non-blocking 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 1x-3.5x the non-blocking stack's.

---
 MAINTAINERS                                        |   4 +
 config/common_base                                 |   1 +
 drivers/mempool/Makefile                           |   1 +
 drivers/mempool/nb_stack/Makefile                  |  30 +++++
 drivers/mempool/nb_stack/meson.build               |   4 +
 drivers/mempool/nb_stack/nb_lifo.h                 | 132 +++++++++++++++++++++
 drivers/mempool/nb_stack/rte_mempool_nb_stack.c    | 125 +++++++++++++++++++
 .../nb_stack/rte_mempool_nb_stack_version.map      |   4 +
 mk/rte.app.mk                                      |   1 +
 9 files changed, 302 insertions(+)
 create mode 100644 drivers/mempool/nb_stack/Makefile
 create mode 100644 drivers/mempool/nb_stack/meson.build
 create mode 100644 drivers/mempool/nb_stack/nb_lifo.h
 create mode 100644 drivers/mempool/nb_stack/rte_mempool_nb_stack.c
 create mode 100644 drivers/mempool/nb_stack/rte_mempool_nb_stack_version.map
MAINTAINERS +4 -0
index 470f36b9c..5519d3323 100644
@@ -416,6 +416,10 @@ M: Artem V. Andreev <[email protected]>
 M: Andrew Rybchenko <[email protected]>
 F: drivers/mempool/bucket/
 
+Non-blocking stack memory pool
+M: Gage Eads <[email protected]>
+F: drivers/mempool/nb_stack/
+
 
 Bus Drivers
 -----------
config/common_base +1 -0
index 964a6956e..40ce47312 100644
@@ -728,6 +728,7 @@ CONFIG_RTE_DRIVER_MEMPOOL_BUCKET=y
 CONFIG_RTE_DRIVER_MEMPOOL_BUCKET_SIZE_KB=64
 CONFIG_RTE_DRIVER_MEMPOOL_RING=y
 CONFIG_RTE_DRIVER_MEMPOOL_STACK=y
+CONFIG_RTE_DRIVER_MEMPOOL_NB_STACK=y
 
 #
 # Compile PMD for octeontx fpa mempool device
drivers/mempool/Makefile +1 -0
index 28c2e8360..aeae3ac12 100644
@@ -13,5 +13,6 @@ endif
 DIRS-$(CONFIG_RTE_DRIVER_MEMPOOL_RING) += ring
 DIRS-$(CONFIG_RTE_DRIVER_MEMPOOL_STACK) += stack
 DIRS-$(CONFIG_RTE_LIBRTE_OCTEONTX_MEMPOOL) += octeontx
+DIRS-$(CONFIG_RTE_DRIVER_MEMPOOL_NB_STACK) += nb_stack
 
 include $(RTE_SDK)/mk/rte.subdir.mk
drivers/mempool/nb_stack/Makefile new file +30 -0
new file mode 100644
index 000000000..38b45f4f5
@@ -0,0 +1,30 @@
+# SPDX-License-Identifier: BSD-3-Clause
+# Copyright(c) 2019 Intel Corporation
+
+include $(RTE_SDK)/mk/rte.vars.mk
+
+# The non-blocking stack uses a 128-bit compare-and-swap instruction, and thus
+# is limited to x86_64.
+ifeq ($(CONFIG_RTE_ARCH_X86_64),y)
+
+#
+# library name
+#
+LIB = librte_mempool_nb_stack.a
+
+CFLAGS += -O3
+CFLAGS += $(WERROR_FLAGS)
+
+# Headers
+CFLAGS += -I$(RTE_SDK)/lib/librte_mempool
+LDLIBS += -lrte_eal -lrte_mempool
+
+EXPORT_MAP := rte_mempool_nb_stack_version.map
+
+LIBABIVER := 1
+
+SRCS-$(CONFIG_RTE_DRIVER_MEMPOOL_NB_STACK) += rte_mempool_nb_stack.c
+
+endif
+
+include $(RTE_SDK)/mk/rte.lib.mk
drivers/mempool/nb_stack/meson.build new file +4 -0
new file mode 100644
index 000000000..66d64a9ba
@@ -0,0 +1,4 @@
+# SPDX-License-Identifier: BSD-3-Clause
+# Copyright(c) 2019 Intel Corporation
+
+sources = files('rte_mempool_nb_stack.c')
drivers/mempool/nb_stack/nb_lifo.h new file +132 -0

132 lines not on this page · raw message

drivers/mempool/nb_stack/rte_mempool_nb_stack.c new file +125 -0

125 lines not on this page · raw message

drivers/mempool/nb_stack/rte_mempool_nb_stack_version.map new file +4 -0
new file mode 100644
index 000000000..fc8c95e91
@@ -0,0 +1,4 @@
+DPDK_19.05 {
+
+	local: *;
+};
mk/rte.app.mk +1 -0
index 02e8b6f05..0b11d9417 100644
@@ -133,6 +133,7 @@ ifeq ($(CONFIG_RTE_BUILD_SHARED_LIB),n)
 
 _LDLIBS-$(CONFIG_RTE_DRIVER_MEMPOOL_BUCKET) += -lrte_mempool_bucket
 _LDLIBS-$(CONFIG_RTE_DRIVER_MEMPOOL_STACK)  += -lrte_mempool_stack
+_LDLIBS-$(CONFIG_RTE_DRIVER_MEMPOOL_NB_STACK)  += -lrte_mempool_nb_stack
 ifeq ($(CONFIG_RTE_LIBRTE_DPAA_BUS),y)
 _LDLIBS-$(CONFIG_RTE_LIBRTE_DPAA_MEMPOOL)   += -lrte_mempool_dpaa
 endif
Signature · 1 line
2.13.6
#8 lore raw

Re: [PATCH 2/3] mempool/nb_stack: add non-blocking stack mempool

Hi Gage,

In general looks very good.

Have you considered to make nb_lifo.h a library to be reusable outside of the mempool driver?

There are few notes below.

Thanks,
Andrew.

Quoted 55 lines · Gage Eads

This commit adds support for non-blocking (linked list based) stack mempool handler. The stack uses a 128-bit compare-and-swap instruction, and thus is limited to x86_64. The 128-bit CAS atomically updates the stack top pointer and a modification counter, which protects against the ABA problem.

In mempool_perf_autotest the lock-based stack outperforms the non-blocking handler*, however:
- For applications with preemptible pthreads, a lock-based stack's worst-case performance (i.e. one thread being preempted while holding the spinlock) is much worse than the non-blocking 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 1x-3.5x the non-blocking stack's.

---
  MAINTAINERS                                        |   4 +
  config/common_base                                 |   1 +
  drivers/mempool/Makefile                           |   1 +
  drivers/mempool/nb_stack/Makefile                  |  30 +++++
  drivers/mempool/nb_stack/meson.build               |   4 +
  drivers/mempool/nb_stack/nb_lifo.h                 | 132 +++++++++++++++++++++
  drivers/mempool/nb_stack/rte_mempool_nb_stack.c    | 125 +++++++++++++++++++
  .../nb_stack/rte_mempool_nb_stack_version.map      |   4 +
  mk/rte.app.mk                                      |   1 +
  9 files changed, 302 insertions(+)

create mode 100644 drivers/mempool/nb_stack/Makefile
create mode 100644 drivers/mempool/nb_stack/meson.build
create mode 100644 drivers/mempool/nb_stack/nb_lifo.h
create mode 100644 drivers/mempool/nb_stack/rte_mempool_nb_stack.c create mode 100644 drivers/mempool/nb_stack/rte_mempool_nb_stack_version.map

MAINTAINERS +4 -0
index 470f36b9c..5519d3323 100644
@@ -416,6 +416,10 @@ M: Artem V. Andreev <[email protected]>
  M: Andrew Rybchenko <[email protected]>
  F: drivers/mempool/bucket/
 
+Non-blocking stack memory pool
+M: Gage Eads <[email protected]>
+F: drivers/mempool/nb_stack/
+
 
  Bus Drivers
  -----------
config/common_base +0 -0
index 964a6956e..40ce47312 100644

config/common_base CONFIG_RTE_DRIVER_MEMPOOL_BUCKET=y · line 731

Quoted 4 lines
config/common_base +1 -0
@@ -728,6 +728,7 @@ CONFIG_RTE_DRIVER_MEMPOOL_BUCKET=y
  CONFIG_RTE_DRIVER_MEMPOOL_BUCKET_SIZE_KB=64
  CONFIG_RTE_DRIVER_MEMPOOL_RING=y
  CONFIG_RTE_DRIVER_MEMPOOL_STACK=y
+CONFIG_RTE_DRIVER_MEMPOOL_NB_STACK=y

Typically it is alphabetically sorted.

drivers/mempool/Makefile endif · line 16

Quoted 11 lines
config/common_base +0 -0
  #
  # Compile PMD for octeontx fpa mempool device
drivers/mempool/Makefile +1 -0
index 28c2e8360..aeae3ac12 100644
@@ -13,5 +13,6 @@ endif
  DIRS-$(CONFIG_RTE_DRIVER_MEMPOOL_RING) += ring
  DIRS-$(CONFIG_RTE_DRIVER_MEMPOOL_STACK) += stack
  DIRS-$(CONFIG_RTE_LIBRTE_OCTEONTX_MEMPOOL) += octeontx
+DIRS-$(CONFIG_RTE_DRIVER_MEMPOOL_NB_STACK) += nb_stack

Typically it is alphabetically sorted. Yes, already broken, but, please, put it before ring.

Quoted 17 lines
drivers/mempool/Makefile +0 -0
  include $(RTE_SDK)/mk/rte.subdir.mk
drivers/mempool/nb_stack/Makefile new file +9 -0
new file mode 100644
index 000000000..38b45f4f5
@@ -0,0 +1,30 @@
+# SPDX-License-Identifier: BSD-3-Clause
+# Copyright(c) 2019 Intel Corporation
+
+include $(RTE_SDK)/mk/rte.vars.mk
+
+# The non-blocking stack uses a 128-bit compare-and-swap instruction, and thus
+# is limited to x86_64.
+ifeq ($(CONFIG_RTE_ARCH_X86_64),y)
+

drivers/mempool/nb_stack/Makefile line 19

Quoted 10 lines
drivers/mempool/nb_stack/Makefile new file +10 -0
+#
+# library name
+#
+LIB = librte_mempool_nb_stack.a
+
+CFLAGS += -O3
+CFLAGS += $(WERROR_FLAGS)
+
+# Headers
+CFLAGS += -I$(RTE_SDK)/lib/librte_mempool

I guess it is derived from stack. Is it really required? There is no such line in ring, bucket, octeontx and dpaa2.

Quoted 17 lines
drivers/mempool/nb_stack/Makefile new file +11 -0
+LDLIBS += -lrte_eal -lrte_mempool
+
+EXPORT_MAP := rte_mempool_nb_stack_version.map
+
+LIBABIVER := 1
+
+SRCS-$(CONFIG_RTE_DRIVER_MEMPOOL_NB_STACK) += rte_mempool_nb_stack.c
+
+endif
+
+include $(RTE_SDK)/mk/rte.lib.mk
drivers/mempool/nb_stack/meson.build new file +0 -0
new file mode 100644
index 000000000..66d64a9ba

drivers/mempool/nb_stack/meson.build line 4

Quoted 4 lines
drivers/mempool/nb_stack/meson.build new file +4 -0
@@ -0,0 +1,4 @@
+# SPDX-License-Identifier: BSD-3-Clause
+# Copyright(c) 2019 Intel Corporation
+
+sources = files('rte_mempool_nb_stack.c')

Have no tested meson build for non-x86_64 target? I guess it should be fixed to skip it on non-x86_64 builds.

Quoted 57 lines
drivers/mempool/nb_stack/nb_lifo.h new file +51 -0
new file mode 100644
index 000000000..701d75e37
@@ -0,0 +1,132 @@
+/* SPDX-License-Identifier: BSD-3-Clause
+ * Copyright(c) 2019 Intel Corporation
+ */
+
+#ifndef _NB_LIFO_H_
+#define _NB_LIFO_H_
+
+struct nb_lifo_elem {
+	void *data;
+	struct nb_lifo_elem *next;
+};
+
+struct nb_lifo_head {
+	struct nb_lifo_elem *top; /**< Stack top */
+	uint64_t cnt; /**< Modification counter */
+};
+
+struct nb_lifo {
+	volatile struct nb_lifo_head head __rte_aligned(16);
+	rte_atomic64_t len;
+} __rte_cache_aligned;
+
+static __rte_always_inline void
+nb_lifo_init(struct nb_lifo *lifo)
+{
+	memset(lifo, 0, sizeof(*lifo));
+	rte_atomic64_set(&lifo->len, 0);
+}
+
+static __rte_always_inline unsigned int
+nb_lifo_len(struct nb_lifo *lifo)
+{
+	return (unsigned int) rte_atomic64_read(&lifo->len);
+}
+
+static __rte_always_inline void
+nb_lifo_push(struct nb_lifo *lifo,
+	     struct nb_lifo_elem *first,
+	     struct nb_lifo_elem *last,
+	     unsigned int num)
+{
+	while (1) {
+		struct nb_lifo_head old_head, new_head;
+
+		old_head = lifo->head;
+
+		/* Swing the top pointer to the first element in the list and
+		 * make the last element point to the old top.
+		 */
+		new_head.top = first;
+		new_head.cnt = old_head.cnt + 1;

drivers/mempool/nb_stack/nb_lifo.h line 61

Quoted 10 lines
drivers/mempool/nb_stack/nb_lifo.h new file +10 -0
+
+		last->next = old_head.top;
+
+		if (rte_atomic128_cmpset((volatile uint64_t *) &lifo->head,
+					 (uint64_t *)&old_head,
+					 (uint64_t *)&new_head))
+			break;
+	}
+
+	rte_atomic64_add(&lifo->len, num);

I'd like to understand why it is not a problem that change of the list and increase its length are not atomic. So, we can get wrong length of the stack in the middle. It would be good to explain it in the comment.

Quoted 39 lines
drivers/mempool/nb_stack/nb_lifo.h new file +39 -0
+}
+
+static __rte_always_inline void
+nb_lifo_push_single(struct nb_lifo *lifo, struct nb_lifo_elem *elem)
+{
+	nb_lifo_push(lifo, elem, elem, 1);
+}
+
+static __rte_always_inline struct nb_lifo_elem *
+nb_lifo_pop(struct nb_lifo *lifo,
+	    unsigned int num,
+	    void **obj_table,
+	    struct nb_lifo_elem **last)
+{
+	struct nb_lifo_head old_head;
+
+	/* Reserve num elements, if available */
+	while (1) {
+		uint64_t len = rte_atomic64_read(&lifo->len);
+
+		/* Does the list contain enough elements? */
+		if (len < num)
+			return NULL;
+
+		if (rte_atomic64_cmpset((volatile uint64_t *)&lifo->len,
+					len, len - num))
+			break;
+	}
+
+	/* Pop num elements */
+	while (1) {
+		struct nb_lifo_head new_head;
+		struct nb_lifo_elem *tmp;
+		unsigned int i;
+
+		old_head = lifo->head;
+
+		tmp = old_head.top;
+

drivers/mempool/nb_stack/nb_lifo.h line 110

Quoted 10 lines
drivers/mempool/nb_stack/nb_lifo.h new file +10 -0
+		/* Traverse the list to find the new head. A next pointer will
+		 * either point to another element or NULL; if a thread
+		 * encounters a pointer that has already been popped, the CAS
+		 * will fail.
+		 */
+		for (i = 0; i < num && tmp != NULL; i++) {
+			if (obj_table)
+				obj_table[i] = tmp->data;
+			if (last)
+				*last = tmp;

Isn't it better to do obj_table and last assignment later when we successfully reserved elements? If there is not retries, current solution is optimal, but I guess solution with the second traversal to fill in obj_table will show more stable performance results under high load when many retries are done.

Quoted 60 lines
drivers/mempool/nb_stack/nb_lifo.h new file +22 -0
+			tmp = tmp->next;
+		}
+
+		/* If NULL was encountered, the list was modified while
+		 * traversing it. Retry.
+		 */
+		if (i != num)
+			continue;
+
+		new_head.top = tmp;
+		new_head.cnt = old_head.cnt + 1;
+
+		if (rte_atomic128_cmpset((volatile uint64_t *) &lifo->head,
+					 (uint64_t *)&old_head,
+					 (uint64_t *)&new_head))
+			break;
+	}
+
+	return old_head.top;
+}
+
+#endif /* _NB_LIFO_H_ */
drivers/mempool/nb_stack/rte_mempool_nb_stack.c new file +32 -0
new file mode 100644
index 000000000..1b30775f7
@@ -0,0 +1,125 @@
+/* SPDX-License-Identifier: BSD-3-Clause
+ * Copyright(c) 2019 Intel Corporation
+ */
+
+#include <stdio.h>
+#include <rte_mempool.h>
+#include <rte_malloc.h>
+
+#include "nb_lifo.h"
+
+struct rte_mempool_nb_stack {
+	uint64_t size;
+	struct nb_lifo used_lifo; /**< LIFO containing mempool pointers  */
+	struct nb_lifo free_lifo; /**< LIFO containing unused LIFO elements */
+};
+
+static int
+nb_stack_alloc(struct rte_mempool *mp)
+{
+	struct rte_mempool_nb_stack *s;
+	struct nb_lifo_elem *elems;
+	unsigned int n = mp->size;
+	unsigned int size, i;
+
+	size = sizeof(*s) + n * sizeof(struct nb_lifo_elem);
+
+	/* Allocate our local memory structure */
+	s = rte_zmalloc_socket("mempool-nb_stack",
+			       size,
+			       RTE_CACHE_LINE_SIZE,
+			       mp->socket_id);
+	if (s == NULL) {

drivers/mempool/nb_stack/rte_mempool_nb_stack.c line 42

Quoted 10 lines
drivers/mempool/nb_stack/rte_mempool_nb_stack.c new file +10 -0
+		RTE_LOG(ERR, MEMPOOL, "Cannot allocate nb_stack!\n");
+		return -ENOMEM;
+	}
+
+	s->size = n;
+
+	nb_lifo_init(&s->used_lifo);
+	nb_lifo_init(&s->free_lifo);
+
+	elems = (struct nb_lifo_elem *) &s[1];

Does checkpatch.sh generate warning here because of space after type cast? There are few similar cases in the patch.

Quoted 12 lines
drivers/mempool/nb_stack/rte_mempool_nb_stack.c new file +12 -0
+	for (i = 0; i < n; i++)
+		nb_lifo_push_single(&s->free_lifo, &elems[i]);
+
+	mp->pool_data = s;
+
+	return 0;
+}
+
+static int
+nb_stack_enqueue(struct rte_mempool *mp, void * const *obj_table,
+		 unsigned int n)
+{

drivers/mempool/nb_stack/rte_mempool_nb_stack.c line 64

Quoted 10 lines
drivers/mempool/nb_stack/rte_mempool_nb_stack.c new file +10 -0
+	struct rte_mempool_nb_stack *s = mp->pool_data;
+	struct nb_lifo_elem *first, *last, *tmp;
+	unsigned int i;
+
+	if (unlikely(n == 0))
+		return 0;
+
+	/* Pop n free elements */
+	first = nb_lifo_pop(&s->free_lifo, n, NULL, NULL);
+	if (unlikely(!first))

Just a nit, but as far as I know comparison with NULL is typically used in DPDK. (few cases in the patch)

Quoted 39 lines
drivers/mempool/nb_stack/rte_mempool_nb_stack.c new file +39 -0
+		return -ENOBUFS;
+
+	/* Prepare the list elements */
+	tmp = first;
+	for (i = 0; i < n; i++) {
+		tmp->data = obj_table[i];
+		last = tmp;
+		tmp = tmp->next;
+	}
+
+	/* Enqueue them to the used list */
+	nb_lifo_push(&s->used_lifo, first, last, n);
+
+	return 0;
+}
+
+static int
+nb_stack_dequeue(struct rte_mempool *mp, void **obj_table,
+		 unsigned int n)
+{
+	struct rte_mempool_nb_stack *s = mp->pool_data;
+	struct nb_lifo_elem *first, *last;
+
+	if (unlikely(n == 0))
+		return 0;
+
+	/* Pop n used elements */
+	first = nb_lifo_pop(&s->used_lifo, n, obj_table, &last);
+	if (unlikely(!first))
+		return -ENOENT;
+
+	/* Enqueue the list elements to the free list */
+	nb_lifo_push(&s->free_lifo, first, last, n);
+
+	return 0;
+}
+
+static unsigned
+nb_stack_get_count(const struct rte_mempool *mp)

drivers/mempool/nb_stack/rte_mempool_nb_stack.c line 113

Quoted 10 lines
drivers/mempool/nb_stack/rte_mempool_nb_stack.c new file +10 -0
+{
+	struct rte_mempool_nb_stack *s = mp->pool_data;
+
+	return nb_lifo_len(&s->used_lifo);
+}
+
+static void
+nb_stack_free(struct rte_mempool *mp)
+{
+	rte_free((void *)(mp->pool_data));

I think type cast is not required.

Quoted 27 lines
drivers/mempool/nb_stack/rte_mempool_nb_stack.c new file +12 -0
+}
+
+static struct rte_mempool_ops ops_nb_stack = {
+	.name = "nb_stack",
+	.alloc = nb_stack_alloc,
+	.free = nb_stack_free,
+	.enqueue = nb_stack_enqueue,
+	.dequeue = nb_stack_dequeue,
+	.get_count = nb_stack_get_count
+};
+
+MEMPOOL_REGISTER_OPS(ops_nb_stack);
drivers/mempool/nb_stack/rte_mempool_nb_stack_version.map new file +4 -0
new file mode 100644
index 000000000..fc8c95e91
@@ -0,0 +1,4 @@
+DPDK_19.05 {
+
+	local: *;
+};
mk/rte.app.mk +0 -0
index 02e8b6f05..0b11d9417 100644

mk/rte.app.mk ifeq ($(CONFIG_RTE_BUILD_SHARED_LIB),n) · line 136

Quoted 4 lines
mk/rte.app.mk +1 -0
@@ -133,6 +133,7 @@ ifeq ($(CONFIG_RTE_BUILD_SHARED_LIB),n)
 
  _LDLIBS-$(CONFIG_RTE_DRIVER_MEMPOOL_BUCKET) += -lrte_mempool_bucket
  _LDLIBS-$(CONFIG_RTE_DRIVER_MEMPOOL_STACK)  += -lrte_mempool_stack
+_LDLIBS-$(CONFIG_RTE_DRIVER_MEMPOOL_NB_STACK)  += -lrte_mempool_nb_stack

It is better to sort it alphabetically.

Quoted 3 lines
mk/rte.app.mk +0 -0
  ifeq ($(CONFIG_RTE_LIBRTE_DPAA_BUS),y)
  _LDLIBS-$(CONFIG_RTE_LIBRTE_DPAA_MEMPOOL)   += -lrte_mempool_dpaa
  endif
author
#9 lore raw

Re: [PATCH 2/3] mempool/nb_stack: add non-blocking stack mempool

Quoted 10 lines

-----Original Message-----
From: Andrew Rybchenko [mailto:[email protected]]
Sent: Sunday, January 13, 2019 7:31 AM
To: Eads, Gage <[email protected]>; [email protected]
Cc: [email protected]; Richardson, Bruce <[email protected]>; Ananyev, Konstantin <[email protected]>
Subject: Re: [PATCH 2/3] mempool/nb_stack: add non-blocking stack mempool

Quoted 6 lines

Hi Gage,

In general looks very good.

Have you considered to make nb_lifo.h a library to be reusable outside of the mempool driver?

I'm certainly open to it, if the community can benefit. Due to the difficulty of adding a new lib/ directory (I believe this requires Tech Board approval), I'll defer that work to a separate patchset.

Quoted 84 lines

There are few notes below.

Thanks,
Andrew.

On 1/10/19 11:55 PM, Gage Eads wrote:

This commit adds support for non-blocking (linked list based) stack
mempool
handler. The stack uses a 128-bit compare-and-swap instruction, and
thus is
limited to x86_64. The 128-bit CAS atomically updates the stack top
pointer
and a modification counter, which protects against the ABA problem.

In mempool_perf_autotest the lock-based stack outperforms the non-
blocking
handler*, however:
- For applications with preemptible pthreads, a lock-based stack's worst-case performance (i.e. one thread being preempted while holding the spinlock) is much worse than the non-blocking 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 1x-3.5x the non-blocking stack's.

<mailto:[email protected]>
---
MAINTAINERS | 4 +
config/common_base | 1 +
drivers/mempool/Makefile | 1 +
drivers/mempool/nb_stack/Makefile | 30 +++++
drivers/mempool/nb_stack/meson.build | 4 +
drivers/mempool/nb_stack/nb_lifo.h | 132
+++++++++++++++++++++
drivers/mempool/nb_stack/rte_mempool_nb_stack.c | 125
+++++++++++++++++++

	 .../nb_stack/rte_mempool_nb_stack_version.map      |   4 +
	 mk/rte.app.mk                                      |   1 +
	 9 files changed, 302 insertions(+)

create mode 100644 drivers/mempool/nb_stack/Makefile create mode 100644 drivers/mempool/nb_stack/meson.build create mode 100644 drivers/mempool/nb_stack/nb_lifo.h create mode 100644
drivers/mempool/nb_stack/rte_mempool_nb_stack.c

	 create mode 100644

drivers/mempool/nb_stack/rte_mempool_nb_stack_version.map

	diff --git a/MAINTAINERS b/MAINTAINERS
	index 470f36b9c..5519d3323 100644
	--- a/MAINTAINERS
	+++ b/MAINTAINERS
	@@ -416,6 +416,10 @@ M: Artem V. Andreev
<[email protected]> <mailto:[email protected]>
	 M: Andrew Rybchenko <[email protected]>
<mailto:[email protected]>
	 F: drivers/mempool/bucket/

	+Non-blocking stack memory pool
	+M: Gage Eads <[email protected]> <mailto:[email protected]>
	+F: drivers/mempool/nb_stack/
	+

	 Bus Drivers
	 -----------
	diff --git a/config/common_base b/config/common_base
	index 964a6956e..40ce47312 100644
	--- a/config/common_base
	+++ b/config/common_base
	@@ -728,6 +728,7 @@ CONFIG_RTE_DRIVER_MEMPOOL_BUCKET=y
	 CONFIG_RTE_DRIVER_MEMPOOL_BUCKET_SIZE_KB=64
	 CONFIG_RTE_DRIVER_MEMPOOL_RING=y
	 CONFIG_RTE_DRIVER_MEMPOOL_STACK=y
	+CONFIG_RTE_DRIVER_MEMPOOL_NB_STACK=y
Quoted 1 line

Typically it is alphabetically sorted.

Will fix.

Quoted 16 lines


	 #
	 # Compile PMD for octeontx fpa mempool device
	diff --git a/drivers/mempool/Makefile b/drivers/mempool/Makefile
	index 28c2e8360..aeae3ac12 100644
	--- a/drivers/mempool/Makefile
	+++ b/drivers/mempool/Makefile
	@@ -13,5 +13,6 @@ endif
	 DIRS-$(CONFIG_RTE_DRIVER_MEMPOOL_RING) += ring
	 DIRS-$(CONFIG_RTE_DRIVER_MEMPOOL_STACK) += stack
	 DIRS-$(CONFIG_RTE_LIBRTE_OCTEONTX_MEMPOOL) += octeontx
	+DIRS-$(CONFIG_RTE_DRIVER_MEMPOOL_NB_STACK) += nb_stack
Quoted 3 lines

Typically it is alphabetically sorted. Yes, already broken, but, please, put it before ring.

Sure, will do.

Quoted 33 lines


	 include $(RTE_SDK)/mk/rte.subdir.mk
	diff --git a/drivers/mempool/nb_stack/Makefile
b/drivers/mempool/nb_stack/Makefile
	new file mode 100644
	index 000000000..38b45f4f5
	--- /dev/null
	+++ b/drivers/mempool/nb_stack/Makefile
	@@ -0,0 +1,30 @@
	+# SPDX-License-Identifier: BSD-3-Clause
	+# Copyright(c) 2019 Intel Corporation
	+
	+include $(RTE_SDK)/mk/rte.vars.mk
	+
	+# The non-blocking stack uses a 128-bit compare-and-swap instruction,
and thus
	+# is limited to x86_64.
	+ifeq ($(CONFIG_RTE_ARCH_X86_64),y)
	+
	+#
	+# library name
	+#
	+LIB = librte_mempool_nb_stack.a
	+
	+CFLAGS += -O3
	+CFLAGS += $(WERROR_FLAGS)
	+
	+# Headers
	+CFLAGS += -I$(RTE_SDK)/lib/librte_mempool
Quoted 4 lines

I guess it is derived from stack. Is it really required? There is no such line in ring, bucket, octeontx and dpaa2.

Good guess :). No, I don't believe so -- I'll remove this.

Quoted 26 lines
	+LDLIBS += -lrte_eal -lrte_mempool
	+
	+EXPORT_MAP := rte_mempool_nb_stack_version.map
	+
	+LIBABIVER := 1
	+
	+SRCS-$(CONFIG_RTE_DRIVER_MEMPOOL_NB_STACK) +=
rte_mempool_nb_stack.c
	+
	+endif
	+
	+include $(RTE_SDK)/mk/rte.lib.mk
	diff --git a/drivers/mempool/nb_stack/meson.build
b/drivers/mempool/nb_stack/meson.build
	new file mode 100644
	index 000000000..66d64a9ba
	--- /dev/null
	+++ b/drivers/mempool/nb_stack/meson.build
	@@ -0,0 +1,4 @@
	+# SPDX-License-Identifier: BSD-3-Clause
	+# Copyright(c) 2019 Intel Corporation
	+
	+sources = files('rte_mempool_nb_stack.c')
Quoted 3 lines

Have no tested meson build for non-x86_64 target? I guess it should be fixed to skip it on non-x86_64 builds.

I did not -- my mistake. I'll correct this.

Quoted 75 lines


	diff --git a/drivers/mempool/nb_stack/nb_lifo.h
b/drivers/mempool/nb_stack/nb_lifo.h
	new file mode 100644
	index 000000000..701d75e37
	--- /dev/null
	+++ b/drivers/mempool/nb_stack/nb_lifo.h
	@@ -0,0 +1,132 @@
	+/* SPDX-License-Identifier: BSD-3-Clause
	+ * Copyright(c) 2019 Intel Corporation
	+ */
	+
	+#ifndef _NB_LIFO_H_
	+#define _NB_LIFO_H_
	+
	+struct nb_lifo_elem {
	+	void *data;
	+	struct nb_lifo_elem *next;
	+};
	+
	+struct nb_lifo_head {
	+	struct nb_lifo_elem *top; /**< Stack top */
	+	uint64_t cnt; /**< Modification counter */
	+};
	+
	+struct nb_lifo {
	+	volatile struct nb_lifo_head head __rte_aligned(16);
	+	rte_atomic64_t len;
	+} __rte_cache_aligned;
	+
	+static __rte_always_inline void
	+nb_lifo_init(struct nb_lifo *lifo)
	+{
	+	memset(lifo, 0, sizeof(*lifo));
	+	rte_atomic64_set(&lifo->len, 0);
	+}
	+
	+static __rte_always_inline unsigned int
	+nb_lifo_len(struct nb_lifo *lifo)
	+{
	+	return (unsigned int) rte_atomic64_read(&lifo->len);
	+}
	+
	+static __rte_always_inline void
	+nb_lifo_push(struct nb_lifo *lifo,
	+	     struct nb_lifo_elem *first,
	+	     struct nb_lifo_elem *last,
	+	     unsigned int num)
	+{
	+	while (1) {
	+		struct nb_lifo_head old_head, new_head;
	+
	+		old_head = lifo->head;
	+
	+		/* Swing the top pointer to the first element in the list
and
	+		 * make the last element point to the old top.
	+		 */
	+		new_head.top = first;
	+		new_head.cnt = old_head.cnt + 1;
	+
	+		last->next = old_head.top;
	+
	+		if (rte_atomic128_cmpset((volatile uint64_t *) &lifo-
Quoted 1 line

head,

	+					 (uint64_t *)&old_head,
	+					 (uint64_t *)&new_head))
	+			break;
	+	}
	+
	+	rte_atomic64_add(&lifo->len, num);
Quoted 4 lines

I'd like to understand why it is not a problem that change of the list and increase its length are not atomic. So, we can get wrong length of the stack in the middle. It would be good to explain it in the comment.

Indeed, there is a window in which the list appears shorter than it is. I don't believe this a problem becaues the get_count callback is inherently racy/approximate (if it is called while the list being accessed). That is, even if the list and its size were updated atomically, the size could change between when get_count reads the size and when that value is returned to the calling thread.

I placed the lifo->len updates such that the list may appear to have fewer elements than it does, but will never appear to have more elements. If the mempool is near-empty to the point that this is a concern, I think the bigger problem is the mempool size.

If that seems reasonable, I'll add that as a comment in the code.

Quoted 55 lines

	+}
	+
	+static __rte_always_inline void
	+nb_lifo_push_single(struct nb_lifo *lifo, struct nb_lifo_elem *elem)
	+{
	+	nb_lifo_push(lifo, elem, elem, 1);
	+}
	+
	+static __rte_always_inline struct nb_lifo_elem *
	+nb_lifo_pop(struct nb_lifo *lifo,
	+	    unsigned int num,
	+	    void **obj_table,
	+	    struct nb_lifo_elem **last)
	+{
	+	struct nb_lifo_head old_head;
	+
	+	/* Reserve num elements, if available */
	+	while (1) {
	+		uint64_t len = rte_atomic64_read(&lifo->len);
	+
	+		/* Does the list contain enough elements? */
	+		if (len < num)
	+			return NULL;
	+
	+		if (rte_atomic64_cmpset((volatile uint64_t *)&lifo->len,
	+					len, len - num))
	+			break;
	+	}
	+
	+	/* Pop num elements */
	+	while (1) {
	+		struct nb_lifo_head new_head;
	+		struct nb_lifo_elem *tmp;
	+		unsigned int i;
	+
	+		old_head = lifo->head;
	+
	+		tmp = old_head.top;
	+
	+		/* Traverse the list to find the new head. A next pointer

will
+ * either point to another element or NULL; if a thread
+ * encounters a pointer that has already been popped,
the CAS

	+		 * will fail.
	+		 */
	+		for (i = 0; i < num && tmp != NULL; i++) {
	+			if (obj_table)
	+				obj_table[i] = tmp->data;
	+			if (last)
	+				*last = tmp;
Quoted 5 lines

Isn't it better to do obj_table and last assignment later when we successfully reserved elements? If there is not retries, current solution is optimal, but I guess solution with the second traversal to fill in obj_table will show more stable performance results under high load when many retries are done.

I suspect that the latency of the writes to obj_table and last would largely be hidden by the pointer chasing, since obj_table (aided by the next-line prefetcher) and last should be cached but chances are tmp->next won't be.

Admittedly this is just a theory, I haven't experimentally confirmed anything; if you prefer, I'll investigate this further.

Quoted 79 lines

	+			tmp = tmp->next;
	+		}
	+
	+		/* If NULL was encountered, the list was modified while
	+		 * traversing it. Retry.
	+		 */
	+		if (i != num)
	+			continue;
	+
	+		new_head.top = tmp;
	+		new_head.cnt = old_head.cnt + 1;
	+
	+		if (rte_atomic128_cmpset((volatile uint64_t *) &lifo-
Quoted 1 line

head,

	+					 (uint64_t *)&old_head,
	+					 (uint64_t *)&new_head))
	+			break;
	+	}
	+
	+	return old_head.top;
	+}
	+
	+#endif /* _NB_LIFO_H_ */
	diff --git a/drivers/mempool/nb_stack/rte_mempool_nb_stack.c
b/drivers/mempool/nb_stack/rte_mempool_nb_stack.c
	new file mode 100644
	index 000000000..1b30775f7
	--- /dev/null
	+++ b/drivers/mempool/nb_stack/rte_mempool_nb_stack.c
	@@ -0,0 +1,125 @@
	+/* SPDX-License-Identifier: BSD-3-Clause
	+ * Copyright(c) 2019 Intel Corporation
	+ */
	+
	+#include <stdio.h>
	+#include <rte_mempool.h>
	+#include <rte_malloc.h>
	+
	+#include "nb_lifo.h"
	+
	+struct rte_mempool_nb_stack {
	+	uint64_t size;
	+	struct nb_lifo used_lifo; /**< LIFO containing mempool pointers
*/
	+	struct nb_lifo free_lifo; /**< LIFO containing unused LIFO
elements */
	+};
	+
	+static int
	+nb_stack_alloc(struct rte_mempool *mp)
	+{
	+	struct rte_mempool_nb_stack *s;
	+	struct nb_lifo_elem *elems;
	+	unsigned int n = mp->size;
	+	unsigned int size, i;
	+
	+	size = sizeof(*s) + n * sizeof(struct nb_lifo_elem);
	+
	+	/* Allocate our local memory structure */
	+	s = rte_zmalloc_socket("mempool-nb_stack",
	+			       size,
	+			       RTE_CACHE_LINE_SIZE,
	+			       mp->socket_id);
	+	if (s == NULL) {
	+		RTE_LOG(ERR, MEMPOOL, "Cannot allocate
nb_stack!\n");
	+		return -ENOMEM;
	+	}
	+
	+	s->size = n;
	+
	+	nb_lifo_init(&s->used_lifo);
	+	nb_lifo_init(&s->free_lifo);
	+
	+	elems = (struct nb_lifo_elem *) &s[1];
Quoted 3 lines

Does checkpatch.sh generate warning here because of space after type cast? There are few similar cases in the patch.

No, because that's a --strict option. Regardless, I'm starting to prefer that style -- I'll fix these instances in v2.

Quoted 26 lines

	+	for (i = 0; i < n; i++)
	+		nb_lifo_push_single(&s->free_lifo, &elems[i]);
	+
	+	mp->pool_data = s;
	+
	+	return 0;
	+}
	+
	+static int
	+nb_stack_enqueue(struct rte_mempool *mp, void * const *obj_table,
	+		 unsigned int n)
	+{
	+	struct rte_mempool_nb_stack *s = mp->pool_data;
	+	struct nb_lifo_elem *first, *last, *tmp;
	+	unsigned int i;
	+
	+	if (unlikely(n == 0))
	+		return 0;
	+
	+	/* Pop n free elements */
	+	first = nb_lifo_pop(&s->free_lifo, n, NULL, NULL);
	+	if (unlikely(!first))
Quoted 3 lines

Just a nit, but as far as I know comparison with NULL is typically used in DPDK. (few cases in the patch)

Looks like this is explicitly called out in the style guide: https://doc.dpdk.org/guides/contributing/coding_style.html#null-pointers

Will fix in v2.

Quoted 53 lines

	+		return -ENOBUFS;
	+
	+	/* Prepare the list elements */
	+	tmp = first;
	+	for (i = 0; i < n; i++) {
	+		tmp->data = obj_table[i];
	+		last = tmp;
	+		tmp = tmp->next;
	+	}
	+
	+	/* Enqueue them to the used list */
	+	nb_lifo_push(&s->used_lifo, first, last, n);
	+
	+	return 0;
	+}
	+
	+static int
	+nb_stack_dequeue(struct rte_mempool *mp, void **obj_table,
	+		 unsigned int n)
	+{
	+	struct rte_mempool_nb_stack *s = mp->pool_data;
	+	struct nb_lifo_elem *first, *last;
	+
	+	if (unlikely(n == 0))
	+		return 0;
	+
	+	/* Pop n used elements */
	+	first = nb_lifo_pop(&s->used_lifo, n, obj_table, &last);
	+	if (unlikely(!first))
	+		return -ENOENT;
	+
	+	/* Enqueue the list elements to the free list */
	+	nb_lifo_push(&s->free_lifo, first, last, n);
	+
	+	return 0;
	+}
	+
	+static unsigned
	+nb_stack_get_count(const struct rte_mempool *mp)
	+{
	+	struct rte_mempool_nb_stack *s = mp->pool_data;
	+
	+	return nb_lifo_len(&s->used_lifo);
	+}
	+
	+static void
	+nb_stack_free(struct rte_mempool *mp)
	+{
	+	rte_free((void *)(mp->pool_data));
Quoted 3 lines

I think type cast is not required.

Will fix.

Quoted 37 lines

	+}
	+
	+static struct rte_mempool_ops ops_nb_stack = {
	+	.name = "nb_stack",
	+	.alloc = nb_stack_alloc,
	+	.free = nb_stack_free,
	+	.enqueue = nb_stack_enqueue,
	+	.dequeue = nb_stack_dequeue,
	+	.get_count = nb_stack_get_count
	+};
	+
	+MEMPOOL_REGISTER_OPS(ops_nb_stack);
	diff --git
a/drivers/mempool/nb_stack/rte_mempool_nb_stack_version.map
b/drivers/mempool/nb_stack/rte_mempool_nb_stack_version.map
	new file mode 100644
	index 000000000..fc8c95e91
	--- /dev/null
	+++ b/drivers/mempool/nb_stack/rte_mempool_nb_stack_version.map
	@@ -0,0 +1,4 @@
	+DPDK_19.05 {
	+
	+	local: *;
	+};
	diff --git a/mk/rte.app.mk b/mk/rte.app.mk
	index 02e8b6f05..0b11d9417 100644
	--- a/mk/rte.app.mk
	+++ b/mk/rte.app.mk
	@@ -133,6 +133,7 @@ ifeq ($(CONFIG_RTE_BUILD_SHARED_LIB),n)

	 _LDLIBS-$(CONFIG_RTE_DRIVER_MEMPOOL_BUCKET) += -
lrte_mempool_bucket
	 _LDLIBS-$(CONFIG_RTE_DRIVER_MEMPOOL_STACK)  += -
lrte_mempool_stack
	+_LDLIBS-$(CONFIG_RTE_DRIVER_MEMPOOL_NB_STACK)  += -
Quoted 5 lines

lrte_mempool_nb_stack

It is better to sort it alphabetically.

Will fix.

Appreciate the detailed review!

Thanks,
Gage

author
#10 lore raw

PATCH 3/3 doc: add NB stack comment to EAL "known issues"

In reply to Gage Eads

This comment makes users aware of the non-blocking stack option and its caveats.

---
 doc/guides/prog_guide/env_abstraction_layer.rst | 5 +++++
 1 file changed, 5 insertions(+)
doc/guides/prog_guide/env_abstraction_layer.rst +5 -0
index 929d76dba..9497b879c 100644
@@ -541,6 +541,11 @@ Known Issues
 
   5. It MUST not be used by multi-producer/consumer pthreads, whose scheduling policies are SCHED_FIFO or SCHED_RR.
 
+  Alternatively, x86_64 applications can use the non-blocking stack mempool handler. When considering this handler, note that:
+
+  - it is limited to the x86_64 platform, because it uses an instruction (16-byte compare-and-swap) that is not 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 handler operations.
+
 + 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.
Signature · 1 line
2.13.6
author
#11 lore raw

v2 cover Add non-blocking stack mempool handler

In reply to Gage Eads

For some users, 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.

This patchset introduces a non-blocking stack mempool handler. Note that the non-blocking algorithm relies on a 128-bit compare-and-swap, so it is limited to x86_64 machines.

In mempool_perf_autotest the lock-based stack outperforms the non-blocking handler*, however:
- For applications with preemptible pthreads, a lock-based stack's worst-case performance (i.e. one thread being preempted while holding the spinlock) is much worse than the non-blocking 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 1x-3.5x the non-blocking stack's.

v2:
- Merge separate docs commit into patch #2
- Fixed two space-after-typecast issues
- Fix alphabetical sorting for build files
- Remove unnecessary include path from nb_stack/Makefile
- Add a comment to nb_lifo_len() justifying its approximate behavior
- Fix comparison with NULL
- Remove unnecessary void * cast
- Fix meson builds and limit them to x86_64
- Fix missing library error for non-x86_64 builds

Gage Eads (2):
eal: add 128-bit cmpset (x86-64 only) mempool/nb_stack: add non-blocking stack mempool

 MAINTAINERS                                        |   4 +
 config/common_base                                 |   1 +
 doc/guides/prog_guide/env_abstraction_layer.rst    |   5 +
 drivers/mempool/Makefile                           |   3 +
 drivers/mempool/meson.build                        |   5 +
 drivers/mempool/nb_stack/Makefile                  |  23 ++++
 drivers/mempool/nb_stack/meson.build               |   4 +
 drivers/mempool/nb_stack/nb_lifo.h                 | 147 +++++++++++++++++++++
 drivers/mempool/nb_stack/rte_mempool_nb_stack.c    | 125 ++++++++++++++++++
 .../nb_stack/rte_mempool_nb_stack_version.map      |   4 +
 .../common/include/arch/x86/rte_atomic_64.h        |  22 +++
 mk/rte.app.mk                                      |   7 +-
 12 files changed, 348 insertions(+), 2 deletions(-)
 create mode 100644 drivers/mempool/nb_stack/Makefile
 create mode 100644 drivers/mempool/nb_stack/meson.build
 create mode 100644 drivers/mempool/nb_stack/nb_lifo.h
 create mode 100644 drivers/mempool/nb_stack/rte_mempool_nb_stack.c
 create mode 100644 drivers/mempool/nb_stack/rte_mempool_nb_stack_version.map
Signature · 1 line
2.13.6
author
#12 lore raw

PATCH v2 1/2 eal: add 128-bit cmpset (x86-64 only)

This operation can be used for non-blocking algorithms, such as a non-blocking stack or ring.

---
 .../common/include/arch/x86/rte_atomic_64.h        | 22 ++++++++++++++++++++++
 1 file changed, 22 insertions(+)
lib/librte_eal/common/include/arch/x86/rte_atomic_64.h +22 -0
index fd2ec9c53..34c2addf8 100644
@@ -34,6 +34,7 @@
 /*
  * Inspired from FreeBSD src/sys/amd64/include/atomic.h
  * Copyright (c) 1998 Doug Rabson
+ * Copyright (c) 2019 Intel Corporation
  * All rights reserved.
  */
 
@@ -208,4 +209,25 @@ static inline void rte_atomic64_clear(rte_atomic64_t *v)
 }
 #endif
 
+static inline int
+rte_atomic128_cmpset(volatile uint64_t *dst, uint64_t *exp, uint64_t *src)
+{
+	uint8_t res;
+
+	asm volatile (
+		      MPLOCKED
+		      "cmpxchg16b %[dst];"
+		      " sete %[res]"
+		      : [dst] "=m" (*dst),
+			[res] "=r" (res)
+		      : "c" (src[1]),
+			"b" (src[0]),
+			"m" (*dst),
+			"d" (exp[1]),
+			"a" (exp[0])
+		      : "memory");
+
+	return res;
+}
+
 #endif /* _RTE_ATOMIC_X86_64_H_ */
Signature · 1 line
2.13.6
#13 lore raw

Re: [PATCH v2 1/2] eal: add 128-bit cmpset (x86-64 only)

Quoted 49 lines

-----Original Message-----
From: dev <[email protected]> On Behalf Of Gage Eads
Sent: Wednesday, January 16, 2019 6:33 AM
To: [email protected]
Cc: [email protected]; [email protected]; [email protected]; [email protected]
Subject: [dpdk-dev] [PATCH v2 1/2] eal: add 128-bit cmpset (x86-64 only)

This operation can be used for non-blocking algorithms, such as a non-blocking stack or ring.

---
 .../common/include/arch/x86/rte_atomic_64.h        | 22
++++++++++++++++++++++
 1 file changed, 22 insertions(+)
lib/librte_eal/common/include/arch/x86/rte_atomic_64.h +3 -0
index fd2ec9c53..34c2addf8 100644
@@ -34,6 +34,7 @@
 /*
  * Inspired from FreeBSD src/sys/amd64/include/atomic.h
  * Copyright (c) 1998 Doug Rabson
+ * Copyright (c) 2019 Intel Corporation
  * All rights reserved.
  */
 
@@ -208,4 +209,25 @@ static inline void
 rte_atomic64_clear(rte_atomic64_t *v)
 }
 #endif
 
+static inline int
+rte_atomic128_cmpset(volatile uint64_t *dst, uint64_t *exp, uint64_t

*src)

lib/librte_eal/common/include/arch/x86/rte_atomic_64.h +9 -0
+{
+uint8_t res;
+
+asm volatile (
+      MPLOCKED
+      "cmpxchg16b %[dst];"
+      " sete %[res]"
+      : [dst] "=m" (*dst),
+[res] "=r" (res)

lib/librte_eal/common/include/arch/x86/rte_atomic_64.h static inline void rte_atomic64_clear(rte_atomic64_t *v) · line 232

Quoted 10 lines
lib/librte_eal/common/include/arch/x86/rte_atomic_64.h +10 -0
+      : "c" (src[1]),
+"b" (src[0]),
+"m" (*dst),
+"d" (exp[1]),
+"a" (exp[0])
+      : "memory");
+
+return res;
+}
+

CONFIG_RTE_DRIVER_MEMPOOL_NB_STACK=y can't coexist with RTE_FORCE_INTRINSICS=y, this should be explicitly described somewhere in the configuration and documentations.

Quoted 3 lines

#endif /* _RTE_ATOMIC_X86_64_H_ */
--
2.13.6

IMPORTANT NOTICE: The contents of this email and any attachments are confidential and may also be privileged. If you are not the intended recipient, please notify the sender immediately and do not disclose the contents to any other person, use it for any purpose, or store or copy the information in any medium. Thank you.

author
#14 lore raw

Re: [PATCH v2 1/2] eal: add 128-bit cmpset (x86-64 only)

Quoted 66 lines

-----Original Message-----
From: Gavin Hu (Arm Technology China) [mailto:[email protected]]
Sent: Thursday, January 17, 2019 2:49 AM
To: Eads, Gage <[email protected]>; [email protected]
Cc: [email protected]; [email protected]; Richardson, Bruce <[email protected]>; Ananyev, Konstantin <[email protected]>; Honnappa Nagarahalli <[email protected]>
Subject: RE: [dpdk-dev] [PATCH v2 1/2] eal: add 128-bit cmpset (x86-64 only)

Quoted 52 lines

-----Original Message-----
From: dev <[email protected]> On Behalf Of Gage Eads
Sent: Wednesday, January 16, 2019 6:33 AM
To: [email protected]
Cc: [email protected]; [email protected]; [email protected]; [email protected]
Subject: [dpdk-dev] [PATCH v2 1/2] eal: add 128-bit cmpset (x86-64 only)

This operation can be used for non-blocking algorithms, such as a non-blocking stack or ring.

---
 .../common/include/arch/x86/rte_atomic_64.h        | 22
++++++++++++++++++++++
 1 file changed, 22 insertions(+)
lib/librte_eal/common/include/arch/x86/rte_atomic_64.h +1 -0
index fd2ec9c53..34c2addf8 100644
@@ -34,6 +34,7 @@
 /*
  * Inspired from FreeBSD src/sys/amd64/include/atomic.h
  * Copyright (c) 1998 Doug Rabson
+ * Copyright (c) 2019 Intel Corporation
  * All rights reserved.
  */
 
@@ -208,4 +209,25 @@ static inline void

rte_atomic64_clear(rte_atomic64_t *v) } #endif

lib/librte_eal/common/include/arch/x86/rte_atomic_64.h +2 -0
+static inline int
+rte_atomic128_cmpset(volatile uint64_t *dst, uint64_t *exp, uint64_t

*src)

lib/librte_eal/common/include/arch/x86/rte_atomic_64.h +15 -0
+{
+uint8_t res;
+
+asm volatile (
+      MPLOCKED
+      "cmpxchg16b %[dst];"
+      " sete %[res]"
+      : [dst] "=m" (*dst),
+[res] "=r" (res)
+      : "c" (src[1]),
+"b" (src[0]),
+"m" (*dst),
+"d" (exp[1]),
+"a" (exp[0])
+      : "memory");
Quoted 9 lines

lib/librte_eal/common/include/arch/x86/rte_atomic_64.h static inline void rte_atomic64_clear(rte_atomic64_t *v) · line 232

Quoted 4 lines
lib/librte_eal/common/include/arch/x86/rte_atomic_64.h +4 -0
+
+return res;
+}
+

CONFIG_RTE_DRIVER_MEMPOOL_NB_STACK=y can't coexist with RTE_FORCE_INTRINSICS=y, this should be explicitly described somewhere in the configuration and documentations.

This patch places rte_atomic128_cmpset() outside of the RTE_FORCE_INTRINSICS ifndef, and this file is included regardless of that config flag, so it's compiled either way.

Quoted 9 lines
Quoted 3 lines

#endif /* _RTE_ATOMIC_X86_64_H_ */
--
2.13.6

IMPORTANT NOTICE: The contents of this email and any attachments are confidential and may also be privileged. If you are not the intended recipient, please notify the sender immediately and do not disclose the contents to any other person, use it for any purpose, or store or copy the information in any medium. Thank you.

#15 lore raw

Re: [PATCH v2 1/2] eal: add 128-bit cmpset (x86-64 only)

Quoted 89 lines

-----Original Message-----
From: Eads, Gage <[email protected]>
Sent: Thursday, January 17, 2019 11:14 PM
To: Gavin Hu (Arm Technology China) <[email protected]>; [email protected]
Cc: [email protected]; [email protected]; Richardson, Bruce <[email protected]>; Ananyev, Konstantin <[email protected]>; Honnappa Nagarahalli <[email protected]>
Subject: RE: [dpdk-dev] [PATCH v2 1/2] eal: add 128-bit cmpset (x86-64 only)

Quoted 5 lines

-----Original Message-----
From: Gavin Hu (Arm Technology China) [mailto:[email protected]]
Sent: Thursday, January 17, 2019 2:49 AM
To: Eads, Gage <[email protected]>; [email protected]
Cc: [email protected]; [email protected]; Richardson,

Bruce

Quoted 4 lines

<[email protected]>; Ananyev, Konstantin <[email protected]>; Honnappa Nagarahalli <[email protected]>
Subject: RE: [dpdk-dev] [PATCH v2 1/2] eal: add 128-bit cmpset (x86-64

only)

Quoted 54 lines
Quoted 54 lines

-----Original Message-----
From: dev <[email protected]> On Behalf Of Gage Eads
Sent: Wednesday, January 16, 2019 6:33 AM
To: [email protected]
Cc: [email protected]; [email protected]; [email protected]; [email protected]
Subject: [dpdk-dev] [PATCH v2 1/2] eal: add 128-bit cmpset (x86-64 only)

This operation can be used for non-blocking algorithms, such as a non-blocking stack or ring.

---
 .../common/include/arch/x86/rte_atomic_64.h        | 22
++++++++++++++++++++++
 1 file changed, 22 insertions(+)
lib/librte_eal/common/include/arch/x86/rte_atomic_64.h +1 -0
index fd2ec9c53..34c2addf8 100644
@@ -34,6 +34,7 @@
 /*
  * Inspired from FreeBSD src/sys/amd64/include/atomic.h
  * Copyright (c) 1998 Doug Rabson
+ * Copyright (c) 2019 Intel Corporation
  * All rights reserved.
  */
 
@@ -208,4 +209,25 @@ static inline void

rte_atomic64_clear(rte_atomic64_t *v) } #endif

lib/librte_eal/common/include/arch/x86/rte_atomic_64.h +2 -0
+static inline int
+rte_atomic128_cmpset(volatile uint64_t *dst, uint64_t *exp, uint64_t

*src)

lib/librte_eal/common/include/arch/x86/rte_atomic_64.h +14 -0
+{
+uint8_t res;
+
+asm volatile (
+      MPLOCKED
+      "cmpxchg16b %[dst];"
+      " sete %[res]"
+      : [dst] "=m" (*dst),
+[res] "=r" (res)
+      : "c" (src[1]),
+"b" (src[0]),
+"m" (*dst),
+"d" (exp[1]),
+"a" (exp[0])
Quoted 8 lines

lib/librte_eal/common/include/arch/x86/rte_atomic_64.h static inline void rte_atomic64_clear(rte_atomic64_t *v) · line 232

Quoted 5 lines
lib/librte_eal/common/include/arch/x86/rte_atomic_64.h +5 -0
+      : "memory");
+
+return res;
+}
+

CONFIG_RTE_DRIVER_MEMPOOL_NB_STACK=y can't coexist with RTE_FORCE_INTRINSICS=y, this should be explicitly described somewhere

Quoted 8 lines

in the

Quoted 2 lines

configuration and documentations.

This patch places rte_atomic128_cmpset() outside of the RTE_FORCE_INTRINSICS ifndef, and this file is included regardless of that config flag, so it's compiled either way.

Quoted 4 lines
Quoted 4 lines
Quoted 3 lines

#endif /* _RTE_ATOMIC_X86_64_H_ */
--
2.13.6

author
#16 lore raw

PATCH v2 2/2 mempool/nb_stack: add non-blocking stack mempool

In reply to Gage Eads

This commit adds support for non-blocking (linked list based) stack mempool handler. The stack uses a 128-bit compare-and-swap instruction, and thus is limited to x86_64. The 128-bit CAS atomically updates the stack top pointer and a modification counter, which protects against the ABA problem.

In mempool_perf_autotest the lock-based stack outperforms the non-blocking handler*, however:
- For applications with preemptible pthreads, a lock-based stack's worst-case performance (i.e. one thread being preempted while holding the spinlock) is much worse than the non-blocking 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 1x-3.5x the non-blocking stack's.

---
 MAINTAINERS                                        |   4 +
 config/common_base                                 |   1 +
 doc/guides/prog_guide/env_abstraction_layer.rst    |   5 +
 drivers/mempool/Makefile                           |   3 +
 drivers/mempool/meson.build                        |   5 +
 drivers/mempool/nb_stack/Makefile                  |  23 ++++
 drivers/mempool/nb_stack/meson.build               |   4 +
 drivers/mempool/nb_stack/nb_lifo.h                 | 147 +++++++++++++++++++++
 drivers/mempool/nb_stack/rte_mempool_nb_stack.c    | 125 ++++++++++++++++++
 .../nb_stack/rte_mempool_nb_stack_version.map      |   4 +
 mk/rte.app.mk                                      |   7 +-
 11 files changed, 326 insertions(+), 2 deletions(-)
 create mode 100644 drivers/mempool/nb_stack/Makefile
 create mode 100644 drivers/mempool/nb_stack/meson.build
 create mode 100644 drivers/mempool/nb_stack/nb_lifo.h
 create mode 100644 drivers/mempool/nb_stack/rte_mempool_nb_stack.c
 create mode 100644 drivers/mempool/nb_stack/rte_mempool_nb_stack_version.map
MAINTAINERS +4 -0
index 470f36b9c..5519d3323 100644
@@ -416,6 +416,10 @@ M: Artem V. Andreev <[email protected]>
 M: Andrew Rybchenko <[email protected]>
 F: drivers/mempool/bucket/
 
+Non-blocking stack memory pool
+M: Gage Eads <[email protected]>
+F: drivers/mempool/nb_stack/
+
 
 Bus Drivers
 -----------
config/common_base +1 -0
index 964a6956e..8a51f36b1 100644
@@ -726,6 +726,7 @@ CONFIG_RTE_LIBRTE_MEMPOOL_DEBUG=n
 #
 CONFIG_RTE_DRIVER_MEMPOOL_BUCKET=y
 CONFIG_RTE_DRIVER_MEMPOOL_BUCKET_SIZE_KB=64
+CONFIG_RTE_DRIVER_MEMPOOL_NB_STACK=y
 CONFIG_RTE_DRIVER_MEMPOOL_RING=y
 CONFIG_RTE_DRIVER_MEMPOOL_STACK=y
 
doc/guides/prog_guide/env_abstraction_layer.rst +5 -0
index 929d76dba..9497b879c 100644
@@ -541,6 +541,11 @@ Known Issues
 
   5. It MUST not be used by multi-producer/consumer pthreads, whose scheduling policies are SCHED_FIFO or SCHED_RR.
 
+  Alternatively, x86_64 applications can use the non-blocking stack mempool handler. When considering this handler, note that:
+
+  - it is limited to the x86_64 platform, because it uses an instruction (16-byte compare-and-swap) that is not 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 handler operations.
+
 + 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.
drivers/mempool/Makefile +3 -0
index 28c2e8360..895cf8a34 100644
@@ -10,6 +10,9 @@ endif
 ifeq ($(CONFIG_RTE_EAL_VFIO)$(CONFIG_RTE_LIBRTE_FSLMC_BUS),yy)
 DIRS-$(CONFIG_RTE_LIBRTE_DPAA2_MEMPOOL) += dpaa2
 endif
+ifeq ($(CONFIG_RTE_ARCH_X86_64),y)
+DIRS-$(CONFIG_RTE_DRIVER_MEMPOOL_NB_STACK) += nb_stack
+endif
 DIRS-$(CONFIG_RTE_DRIVER_MEMPOOL_RING) += ring
 DIRS-$(CONFIG_RTE_DRIVER_MEMPOOL_STACK) += stack
 DIRS-$(CONFIG_RTE_LIBRTE_OCTEONTX_MEMPOOL) += octeontx
drivers/mempool/meson.build +5 -0
index 4527d9806..01ee30fee 100644
@@ -2,6 +2,11 @@
 # Copyright(c) 2017 Intel Corporation
 
 drivers = ['bucket', 'dpaa', 'dpaa2', 'octeontx', 'ring', 'stack']
+
+if dpdk_conf.has('RTE_ARCH_X86_64')
+	drivers += 'nb_stack'
+endif
+
 std_deps = ['mempool']
 config_flag_fmt = 'RTE_LIBRTE_@0@_MEMPOOL'
 driver_name_fmt = 'rte_mempool_@0@'
drivers/mempool/nb_stack/Makefile new file +23 -0
new file mode 100644
index 000000000..318b18283
@@ -0,0 +1,23 @@
+# SPDX-License-Identifier: BSD-3-Clause
+# Copyright(c) 2019 Intel Corporation
+
+include $(RTE_SDK)/mk/rte.vars.mk
+
+#
+# library name
+#
+LIB = librte_mempool_nb_stack.a
+
+CFLAGS += -O3
+CFLAGS += $(WERROR_FLAGS)
+
+# Headers
+LDLIBS += -lrte_eal -lrte_mempool
+
+EXPORT_MAP := rte_mempool_nb_stack_version.map
+
+LIBABIVER := 1
+
+SRCS-$(CONFIG_RTE_DRIVER_MEMPOOL_NB_STACK) += rte_mempool_nb_stack.c
+
+include $(RTE_SDK)/mk/rte.lib.mk
drivers/mempool/nb_stack/meson.build new file +4 -0
new file mode 100644
index 000000000..66d64a9ba
@@ -0,0 +1,4 @@
+# SPDX-License-Identifier: BSD-3-Clause
+# Copyright(c) 2019 Intel Corporation
+
+sources = files('rte_mempool_nb_stack.c')
drivers/mempool/nb_stack/nb_lifo.h new file +147 -0

147 lines not on this page · raw message

drivers/mempool/nb_stack/rte_mempool_nb_stack.c new file +125 -0

125 lines not on this page · raw message

drivers/mempool/nb_stack/rte_mempool_nb_stack_version.map new file +4 -0
new file mode 100644
index 000000000..fc8c95e91
@@ -0,0 +1,4 @@
+DPDK_19.05 {
+
+	local: *;
+};
mk/rte.app.mk +5 -2
index 02e8b6f05..d4b4aaaf6 100644
@@ -131,8 +131,11 @@ endif
 ifeq ($(CONFIG_RTE_BUILD_SHARED_LIB),n)
 # plugins (link only if static libraries)
 
-_LDLIBS-$(CONFIG_RTE_DRIVER_MEMPOOL_BUCKET) += -lrte_mempool_bucket
-_LDLIBS-$(CONFIG_RTE_DRIVER_MEMPOOL_STACK)  += -lrte_mempool_stack
+_LDLIBS-$(CONFIG_RTE_DRIVER_MEMPOOL_BUCKET)   += -lrte_mempool_bucket
+ifeq ($(CONFIG_RTE_ARCH_X86_64),y)
+_LDLIBS-$(CONFIG_RTE_DRIVER_MEMPOOL_NB_STACK) += -lrte_mempool_nb_stack
+endif
+_LDLIBS-$(CONFIG_RTE_DRIVER_MEMPOOL_STACK)    += -lrte_mempool_stack
 ifeq ($(CONFIG_RTE_LIBRTE_DPAA_BUS),y)
 _LDLIBS-$(CONFIG_RTE_LIBRTE_DPAA_MEMPOOL)   += -lrte_mempool_dpaa
 endif
Signature · 1 line
2.13.6
Acked-by on v2 2/2
#17 lore raw

Re: [PATCH v2 2/2] mempool/nb_stack: add non-blocking stack mempool

Quoted 13 lines · Gage Eads

This commit adds support for non-blocking (linked list based) stack mempool handler. The stack uses a 128-bit compare-and-swap instruction, and thus is limited to x86_64. The 128-bit CAS atomically updates the stack top pointer and a modification counter, which protects against the ABA problem.

In mempool_perf_autotest the lock-based stack outperforms the non-blocking handler*, however:
- For applications with preemptible pthreads, a lock-based stack's worst-case performance (i.e. one thread being preempted while holding the spinlock) is much worse than the non-blocking stack's.
- Using per-thread mempool caches will largely mitigate the performance difference.

Quoted 6 lines

*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 1x-3.5x the non-blocking stack's.

---

Few minor nits below. Other than that

Don't forget about release notes when 19.05 release cycle starts.

[snip]

drivers/mempool/meson.build line 9

Quoted 13 lines
drivers/mempool/meson.build +5 -0
index 4527d9806..01ee30fee 100644
@@ -2,6 +2,11 @@
  # Copyright(c) 2017 Intel Corporation
 
  drivers = ['bucket', 'dpaa', 'dpaa2', 'octeontx', 'ring', 'stack']
+
+if dpdk_conf.has('RTE_ARCH_X86_64')
+	drivers += 'nb_stack'
+endif
+

I think it would be better to concentrate the logic inside nb_stack/meson.build. There is a 'build' variable which may be set to false disable the build. You can find an example in drivers/net/sfc/meson.build.

[snip]

Quoted 10 lines
drivers/mempool/meson.build +10 -0
+static __rte_always_inline void
+nb_lifo_push(struct nb_lifo *lifo,
+	     struct nb_lifo_elem *first,
+	     struct nb_lifo_elem *last,
+	     unsigned int num)
+{
+	while (1) {
+		struct nb_lifo_head old_head, new_head;
+
+		old_head = lifo->head;

drivers/mempool/meson.build

Quoted 10 lines
drivers/mempool/meson.build +10 -0
+
+		/* Swing the top pointer to the first element in the list and
+		 * make the last element point to the old top.
+		 */
+		new_head.top = first;
+		new_head.cnt = old_head.cnt + 1;
+
+		last->next = old_head.top;
+
+		if (rte_atomic128_cmpset((volatile uint64_t *) &lifo->head,

Unnecessary space after type cast above.

[snip]

drivers/mempool/meson.build

Quoted 4 lines
drivers/mempool/meson.build +4 -0
+		new_head.top = tmp;
+		new_head.cnt = old_head.cnt + 1;
+
+		if (rte_atomic128_cmpset((volatile uint64_t *) &lifo->head,

Unnecessary space after type cast above.

[snip]

#18 lore raw

Re: [PATCH v2 2/2] mempool/nb_stack: add non-blocking stack mempool

In reply to Gage Eads
Quoted 75 lines

-----Original Message-----
From: dev <[email protected]> On Behalf Of Gage Eads
Sent: Wednesday, January 16, 2019 6:33 AM
To: [email protected]
Cc: [email protected]; [email protected]; [email protected]; [email protected]
Subject: [dpdk-dev] [PATCH v2 2/2] mempool/nb_stack: add non-blocking stack mempool

This commit adds support for non-blocking (linked list based) stack mempool
handler. The stack uses a 128-bit compare-and-swap instruction, and thus is
limited to x86_64. The 128-bit CAS atomically updates the stack top pointer
and a modification counter, which protects against the ABA problem.

In mempool_perf_autotest the lock-based stack outperforms the non- blocking
handler*, however:
- For applications with preemptible pthreads, a lock-based stack's worst-case performance (i.e. one thread being preempted while holding the spinlock) is much worse than the non-blocking 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 1x-3.5x the non-blocking stack's.

---
 MAINTAINERS                                        |   4 +
 config/common_base                                 |   1 +
 doc/guides/prog_guide/env_abstraction_layer.rst    |   5 +
 drivers/mempool/Makefile                           |   3 +
 drivers/mempool/meson.build                        |   5 +
 drivers/mempool/nb_stack/Makefile                  |  23 ++++
 drivers/mempool/nb_stack/meson.build               |   4 +
 drivers/mempool/nb_stack/nb_lifo.h                 | 147
+++++++++++++++++++++
 drivers/mempool/nb_stack/rte_mempool_nb_stack.c    | 125
++++++++++++++++++
 .../nb_stack/rte_mempool_nb_stack_version.map      |   4 +
 mk/rte.app.mk                                      |   7 +-
 11 files changed, 326 insertions(+), 2 deletions(-)
 create mode 100644 drivers/mempool/nb_stack/Makefile
 create mode 100644 drivers/mempool/nb_stack/meson.build
 create mode 100644 drivers/mempool/nb_stack/nb_lifo.h
 create mode 100644 drivers/mempool/nb_stack/rte_mempool_nb_stack.c
 create mode 100644

drivers/mempool/nb_stack/rte_mempool_nb_stack_version.map

MAINTAINERS +0 -0
index 470f36b9c..5519d3323 100644
@@ -416,6 +416,10 @@ M: Artem V. Andreev

<[email protected]>
M: Andrew Rybchenko <[email protected]>
F: drivers/mempool/bucket/

MAINTAINERS +4 -0
+Non-blocking stack memory pool
+M: Gage Eads <[email protected]>
+F: drivers/mempool/nb_stack/
+
 
 Bus Drivers
 -----------
config/common_base +0 -0
index 964a6956e..8a51f36b1 100644

config/common_base CONFIG_RTE_LIBRTE_MEMPOOL_DEBUG=n · line 729

Quoted 4 lines
config/common_base +1 -0
@@ -726,6 +726,7 @@ CONFIG_RTE_LIBRTE_MEMPOOL_DEBUG=n
 #
 CONFIG_RTE_DRIVER_MEMPOOL_BUCKET=y
 CONFIG_RTE_DRIVER_MEMPOOL_BUCKET_SIZE_KB=64
+CONFIG_RTE_DRIVER_MEMPOOL_NB_STACK=y

NAK, as this applies to x86_64 only, it will break arm/ppc and even 32bit i386 configurations.

Quoted 424 lines
config/common_base +0 -0
 CONFIG_RTE_DRIVER_MEMPOOL_RING=y
 CONFIG_RTE_DRIVER_MEMPOOL_STACK=y
 
doc/guides/prog_guide/env_abstraction_layer.rst +0 -0
index 929d76dba..9497b879c 100644
@@ -541,6 +541,11 @@ Known Issues
 
   5. It MUST not be used by multi-producer/consumer pthreads, whose

scheduling policies are SCHED_FIFO or SCHED_RR.

+ Alternatively, x86_64 applications can use the non-blocking stack mempool handler. When considering this handler, note that:

doc/guides/prog_guide/env_abstraction_layer.rst +2 -0
+
+  - it is limited to the x86_64 platform, because it uses an instruction (16-

byte compare-and-swap) that is not 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 handler operations.
+
+ 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.

drivers/mempool/Makefile +3 -0
index 28c2e8360..895cf8a34 100644
@@ -10,6 +10,9 @@ endif
 ifeq ($(CONFIG_RTE_EAL_VFIO)$(CONFIG_RTE_LIBRTE_FSLMC_BUS),yy)
 DIRS-$(CONFIG_RTE_LIBRTE_DPAA2_MEMPOOL) += dpaa2
 endif
+ifeq ($(CONFIG_RTE_ARCH_X86_64),y)
+DIRS-$(CONFIG_RTE_DRIVER_MEMPOOL_NB_STACK) += nb_stack
+endif
 DIRS-$(CONFIG_RTE_DRIVER_MEMPOOL_RING) += ring
 DIRS-$(CONFIG_RTE_DRIVER_MEMPOOL_STACK) += stack
 DIRS-$(CONFIG_RTE_LIBRTE_OCTEONTX_MEMPOOL) += octeontx
drivers/mempool/meson.build +5 -0
index 4527d9806..01ee30fee 100644
@@ -2,6 +2,11 @@
 # Copyright(c) 2017 Intel Corporation
 
 drivers = ['bucket', 'dpaa', 'dpaa2', 'octeontx', 'ring', 'stack']
+
+if dpdk_conf.has('RTE_ARCH_X86_64')
+drivers += 'nb_stack'
+endif
+
 std_deps = ['mempool']
 config_flag_fmt = 'RTE_LIBRTE_@0@_MEMPOOL'
 driver_name_fmt = 'rte_mempool_@0@'
drivers/mempool/nb_stack/Makefile new file +21 -0
new file mode 100644
index 000000000..318b18283
@@ -0,0 +1,23 @@
+# SPDX-License-Identifier: BSD-3-Clause
+# Copyright(c) 2019 Intel Corporation
+
+include $(RTE_SDK)/mk/rte.vars.mk
+
+#
+# library name
+#
+LIB = librte_mempool_nb_stack.a
+
+CFLAGS += -O3
+CFLAGS += $(WERROR_FLAGS)
+
+# Headers
+LDLIBS += -lrte_eal -lrte_mempool
+
+EXPORT_MAP := rte_mempool_nb_stack_version.map
+
+LIBABIVER := 1
+
+SRCS-$(CONFIG_RTE_DRIVER_MEMPOOL_NB_STACK) +=

rte_mempool_nb_stack.c

drivers/mempool/nb_stack/Makefile new file +2 -0
+
+include $(RTE_SDK)/mk/rte.lib.mk
drivers/mempool/nb_stack/meson.build new file +4 -0
new file mode 100644
index 000000000..66d64a9ba
@@ -0,0 +1,4 @@
+# SPDX-License-Identifier: BSD-3-Clause
+# Copyright(c) 2019 Intel Corporation
+
+sources = files('rte_mempool_nb_stack.c')
drivers/mempool/nb_stack/nb_lifo.h new file +33 -0
new file mode 100644
index 000000000..2edae1c0f
@@ -0,0 +1,147 @@
+/* SPDX-License-Identifier: BSD-3-Clause
+ * Copyright(c) 2019 Intel Corporation
+ */
+
+#ifndef _NB_LIFO_H_
+#define _NB_LIFO_H_
+
+struct nb_lifo_elem {
+void *data;
+struct nb_lifo_elem *next;
+};
+
+struct nb_lifo_head {
+struct nb_lifo_elem *top; /**< Stack top */
+uint64_t cnt; /**< Modification counter */
+};
+
+struct nb_lifo {
+volatile struct nb_lifo_head head __rte_aligned(16);
+rte_atomic64_t len;
+} __rte_cache_aligned;
+
+static __rte_always_inline void
+nb_lifo_init(struct nb_lifo *lifo)
+{
+memset(lifo, 0, sizeof(*lifo));
+rte_atomic64_set(&lifo->len, 0);
+}
+
+static __rte_always_inline unsigned int
+nb_lifo_len(struct nb_lifo *lifo)
+{
+/* nb_lifo_push() and nb_lifo_pop() do not update the list's

contents
+ * and lifo->len atomically, which can cause the list to appear shorter
+ * than it actually is if this function is called while other threads
+ * are modifying the list.
+ *
+ * However, given the inherently approximate nature of the get_count
+ * callback -- even if the list and its size were updated atomically,
+ * the size could change between when get_count executes and when the
+ * value is returned to the caller -- this is acceptable.
+ *
+ * The lifo->len updates are placed such that the list may appear to
+ * have fewer elements than it does, but will never appear to have more
+ * elements. If the mempool is near-empty to the point that this is a
+ * concern, the user should consider increasing the mempool size.
+ */

drivers/mempool/nb_stack/nb_lifo.h new file +69 -0
+return (unsigned int)rte_atomic64_read(&lifo->len);
+}
+
+static __rte_always_inline void
+nb_lifo_push(struct nb_lifo *lifo,
+     struct nb_lifo_elem *first,
+     struct nb_lifo_elem *last,
+     unsigned int num)
+{
+while (1) {
+struct nb_lifo_head old_head, new_head;
+
+old_head = lifo->head;
+
+/* Swing the top pointer to the first element in the list and
+ * make the last element point to the old top.
+ */
+new_head.top = first;
+new_head.cnt = old_head.cnt + 1;
+
+last->next = old_head.top;
+
+if (rte_atomic128_cmpset((volatile uint64_t *) &lifo->head,
+ (uint64_t *)&old_head,
+ (uint64_t *)&new_head))
+break;
+}
+
+rte_atomic64_add(&lifo->len, num);
+}
+
+static __rte_always_inline void
+nb_lifo_push_single(struct nb_lifo *lifo, struct nb_lifo_elem *elem)
+{
+nb_lifo_push(lifo, elem, elem, 1);
+}
+
+static __rte_always_inline struct nb_lifo_elem *
+nb_lifo_pop(struct nb_lifo *lifo,
+    unsigned int num,
+    void **obj_table,
+    struct nb_lifo_elem **last)
+{
+struct nb_lifo_head old_head;
+
+/* Reserve num elements, if available */
+while (1) {
+uint64_t len = rte_atomic64_read(&lifo->len);
+
+/* Does the list contain enough elements? */
+if (len < num)
+return NULL;
+
+if (rte_atomic64_cmpset((volatile uint64_t *)&lifo->len,
+len, len - num))
+break;
+}
+
+/* Pop num elements */
+while (1) {
+struct nb_lifo_head new_head;
+struct nb_lifo_elem *tmp;
+unsigned int i;
+
+old_head = lifo->head;
+
+tmp = old_head.top;
+
+/* Traverse the list to find the new head. A next pointer

will
+ * either point to another element or NULL; if a thread
+ * encounters a pointer that has already been popped, the CAS
+ * will fail.
+ */

drivers/mempool/nb_stack/nb_lifo.h new file +27 -0
+for (i = 0; i < num && tmp != NULL; i++) {
+if (obj_table)
+obj_table[i] = tmp->data;
+if (last)
+*last = tmp;
+tmp = tmp->next;
+}
+
+/* If NULL was encountered, the list was modified while
+ * traversing it. Retry.
+ */
+if (i != num)
+continue;
+
+new_head.top = tmp;
+new_head.cnt = old_head.cnt + 1;
+
+if (rte_atomic128_cmpset((volatile uint64_t *) &lifo->head,
+ (uint64_t *)&old_head,
+ (uint64_t *)&new_head))
+break;
+}
+
+return old_head.top;
+}
+
+#endif /* _NB_LIFO_H_ */
drivers/mempool/nb_stack/rte_mempool_nb_stack.c new file +14 -0
new file mode 100644
index 000000000..1818a2cfa
@@ -0,0 +1,125 @@
+/* SPDX-License-Identifier: BSD-3-Clause
+ * Copyright(c) 2019 Intel Corporation
+ */
+
+#include <stdio.h>
+#include <rte_mempool.h>
+#include <rte_malloc.h>
+
+#include "nb_lifo.h"
+
+struct rte_mempool_nb_stack {
+uint64_t size;
+struct nb_lifo used_lifo; /**< LIFO containing mempool pointers  */
+struct nb_lifo free_lifo; /**< LIFO containing unused LIFO elements

*/

drivers/mempool/nb_stack/rte_mempool_nb_stack.c new file +111 -0
+};
+
+static int
+nb_stack_alloc(struct rte_mempool *mp)
+{
+struct rte_mempool_nb_stack *s;
+struct nb_lifo_elem *elems;
+unsigned int n = mp->size;
+unsigned int size, i;
+
+size = sizeof(*s) + n * sizeof(struct nb_lifo_elem);
+
+/* Allocate our local memory structure */
+s = rte_zmalloc_socket("mempool-nb_stack",
+       size,
+       RTE_CACHE_LINE_SIZE,
+       mp->socket_id);
+if (s == NULL) {
+RTE_LOG(ERR, MEMPOOL, "Cannot allocate nb_stack!\n");
+return -ENOMEM;
+}
+
+s->size = n;
+
+nb_lifo_init(&s->used_lifo);
+nb_lifo_init(&s->free_lifo);
+
+elems = (struct nb_lifo_elem *)&s[1];
+for (i = 0; i < n; i++)
+nb_lifo_push_single(&s->free_lifo, &elems[i]);
+
+mp->pool_data = s;
+
+return 0;
+}
+
+static int
+nb_stack_enqueue(struct rte_mempool *mp, void * const *obj_table,
+ unsigned int n)
+{
+struct rte_mempool_nb_stack *s = mp->pool_data;
+struct nb_lifo_elem *first, *last, *tmp;
+unsigned int i;
+
+if (unlikely(n == 0))
+return 0;
+
+/* Pop n free elements */
+first = nb_lifo_pop(&s->free_lifo, n, NULL, NULL);
+if (unlikely(first == NULL))
+return -ENOBUFS;
+
+/* Prepare the list elements */
+tmp = first;
+for (i = 0; i < n; i++) {
+tmp->data = obj_table[i];
+last = tmp;
+tmp = tmp->next;
+}
+
+/* Enqueue them to the used list */
+nb_lifo_push(&s->used_lifo, first, last, n);
+
+return 0;
+}
+
+static int
+nb_stack_dequeue(struct rte_mempool *mp, void **obj_table,
+ unsigned int n)
+{
+struct rte_mempool_nb_stack *s = mp->pool_data;
+struct nb_lifo_elem *first, *last;
+
+if (unlikely(n == 0))
+return 0;
+
+/* Pop n used elements */
+first = nb_lifo_pop(&s->used_lifo, n, obj_table, &last);
+if (unlikely(first == NULL))
+return -ENOENT;
+
+/* Enqueue the list elements to the free list */
+nb_lifo_push(&s->free_lifo, first, last, n);
+
+return 0;
+}
+
+static unsigned
+nb_stack_get_count(const struct rte_mempool *mp)
+{
+struct rte_mempool_nb_stack *s = mp->pool_data;
+
+return nb_lifo_len(&s->used_lifo);
+}
+
+static void
+nb_stack_free(struct rte_mempool *mp)
+{
+rte_free(mp->pool_data);
+}
+
+static struct rte_mempool_ops ops_nb_stack = {
+.name = "nb_stack",
+.alloc = nb_stack_alloc,
+.free = nb_stack_free,
+.enqueue = nb_stack_enqueue,
+.dequeue = nb_stack_dequeue,
+.get_count = nb_stack_get_count
+};
+
+MEMPOOL_REGISTER_OPS(ops_nb_stack);

diff --git a/drivers/mempool/nb_stack/rte_mempool_nb_stack_version.map b/drivers/mempool/nb_stack/rte_mempool_nb_stack_version.map new file mode 100644
index 000000000..fc8c95e91

drivers/mempool/nb_stack/rte_mempool_nb_stack_version.map new file +4 -0
@@ -0,0 +1,4 @@
+DPDK_19.05 {
+
+local: *;
+};
mk/rte.app.mk +0 -1
index 02e8b6f05..d4b4aaaf6 100644
@@ -131,8 +131,11 @@ endif
 ifeq ($(CONFIG_RTE_BUILD_SHARED_LIB),n)
 # plugins (link only if static libraries)
 
-_LDLIBS-$(CONFIG_RTE_DRIVER_MEMPOOL_BUCKET) += -

lrte_mempool_bucket
-_LDLIBS-$(CONFIG_RTE_DRIVER_MEMPOOL_STACK) += -
lrte_mempool_stack
+_LDLIBS-$(CONFIG_RTE_DRIVER_MEMPOOL_BUCKET) += -
lrte_mempool_bucket

mk/rte.app.mk +2 -0
+ifeq ($(CONFIG_RTE_ARCH_X86_64),y)
+_LDLIBS-$(CONFIG_RTE_DRIVER_MEMPOOL_NB_STACK) += -

lrte_mempool_nb_stack

mk/rte.app.mk +2 -0
+endif
+_LDLIBS-$(CONFIG_RTE_DRIVER_MEMPOOL_STACK)    += -
Quoted 7 lines

lrte_mempool_stack
ifeq ($(CONFIG_RTE_LIBRTE_DPAA_BUS),y)
_LDLIBS-$(CONFIG_RTE_LIBRTE_DPAA_MEMPOOL) += -
lrte_mempool_dpaa
endif
--
2.13.6

IMPORTANT NOTICE: The contents of this email and any attachments are confidential and may also be privileged. If you are not the intended recipient, please notify the sender immediately and do not disclose the contents to any other person, use it for any purpose, or store or copy the information in any medium. Thank you.

author
#19 lore raw

Re: [PATCH v2 2/2] mempool/nb_stack: add non-blocking stack mempool

Quoted 79 lines

-----Original Message-----
From: Gavin Hu (Arm Technology China) [mailto:[email protected]]
Sent: Thursday, January 17, 2019 2:06 AM
To: Eads, Gage <[email protected]>; [email protected]
Cc: [email protected]; [email protected]; Richardson, Bruce <[email protected]>; Ananyev, Konstantin <[email protected]>; Honnappa Nagarahalli <[email protected]>; Ruifeng Wang (Arm Technology China) <[email protected]>; Phil Yang (Arm Technology China) <[email protected]>
Subject: RE: [dpdk-dev] [PATCH v2 2/2] mempool/nb_stack: add non-blocking stack mempool

Quoted 63 lines

-----Original Message-----
From: dev <[email protected]> On Behalf Of Gage Eads
Sent: Wednesday, January 16, 2019 6:33 AM
To: [email protected]
Cc: [email protected]; [email protected]; [email protected]; [email protected]
Subject: [dpdk-dev] [PATCH v2 2/2] mempool/nb_stack: add non-blocking stack mempool

This commit adds support for non-blocking (linked list based) stack mempool handler. The stack uses a 128-bit compare-and-swap instruction, and thus is limited to x86_64. The 128-bit CAS atomically updates the stack top pointer and a modification counter, which protects against the ABA problem.

In mempool_perf_autotest the lock-based stack outperforms the non- blocking handler*, however:
- For applications with preemptible pthreads, a lock-based stack's worst-case performance (i.e. one thread being preempted while holding the spinlock) is much worse than the non-blocking 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 1x-3.5x the non-blocking stack's.

---
 MAINTAINERS                                        |   4 +
 config/common_base                                 |   1 +
 doc/guides/prog_guide/env_abstraction_layer.rst    |   5 +
 drivers/mempool/Makefile                           |   3 +
 drivers/mempool/meson.build                        |   5 +
 drivers/mempool/nb_stack/Makefile                  |  23 ++++
 drivers/mempool/nb_stack/meson.build               |   4 +
 drivers/mempool/nb_stack/nb_lifo.h                 | 147
+++++++++++++++++++++
 drivers/mempool/nb_stack/rte_mempool_nb_stack.c    | 125
++++++++++++++++++
 .../nb_stack/rte_mempool_nb_stack_version.map      |   4 +
 mk/rte.app.mk                                      |   7 +-
 11 files changed, 326 insertions(+), 2 deletions(-)  create mode
100644 drivers/mempool/nb_stack/Makefile  create mode 100644
drivers/mempool/nb_stack/meson.build
 create mode 100644 drivers/mempool/nb_stack/nb_lifo.h
 create mode 100644 drivers/mempool/nb_stack/rte_mempool_nb_stack.c
 create mode 100644

drivers/mempool/nb_stack/rte_mempool_nb_stack_version.map

MAINTAINERS index 470f36b9c..5519d3323 renamed from MAINTAINERS +0 -0

100644

MAINTAINERS +4 -0
@@ -416,6 +416,10 @@ M: Artem V. Andreev <[email protected]>
 M: Andrew Rybchenko <[email protected]>
 F: drivers/mempool/bucket/
 
+Non-blocking stack memory pool
+M: Gage Eads <[email protected]>
+F: drivers/mempool/nb_stack/
+
 
Quoted 14 lines
Quoted 10 lines
MAINTAINERS +0 -0
 Bus Drivers
 -----------
config/common_base index renamed from config/common_base +0 -0

964a6956e..8a51f36b1 100644

config/common_base +0 -0
@@ -726,6 +726,7 @@ CONFIG_RTE_LIBRTE_MEMPOOL_DEBUG=n  #

CONFIG_RTE_DRIVER_MEMPOOL_BUCKET=y
CONFIG_RTE_DRIVER_MEMPOOL_BUCKET_SIZE_KB=64
+CONFIG_RTE_DRIVER_MEMPOOL_NB_STACK=y

NAK, as this applies to x86_64 only, it will break arm/ppc and even 32bit i386 configurations.

Hi Gavin,

This patch resolves that in the make and meson build files, which ensure that the library is only built for x86-64 targets:

drivers/mempool/Makefile +3 -0
index 28c2e8360..895cf8a34 100644
@@ -10,6 +10,9 @@ endif
 ifeq ($(CONFIG_RTE_EAL_VFIO)$(CONFIG_RTE_LIBRTE_FSLMC_BUS),yy)
 DIRS-$(CONFIG_RTE_LIBRTE_DPAA2_MEMPOOL) += dpaa2
 endif
+ifeq ($(CONFIG_RTE_ARCH_X86_64),y)
+DIRS-$(CONFIG_RTE_DRIVER_MEMPOOL_NB_STACK) += nb_stack
+endif
 
drivers/mempool/nb_stack/meson.build new file +8 -0
new file mode 100644
index 000000000..4a699511d
@@ -0,0 +1,8 @@
+# SPDX-License-Identifier: BSD-3-Clause
+# Copyright(c) 2019 Intel Corporation
+
+if arch_subdir != 'x86' or cc.sizeof('void *') == 4
+	build = false
+endif
+
+sources = files('rte_mempool_nb_stack.c')

(Note: this code was pulled from the v3 patch)

You can see successful 32-bit builds at the dpdk-test-report here: http://mails.dpdk.org/archives/test-report/2019-January/073636.html

Quoted 6 lines

IMPORTANT NOTICE: The contents of this email and any attachments are confidential and may also be privileged. If you are not the intended recipient, please notify the sender immediately and do not disclose the contents to any other person, use it for any purpose, or store or copy the information in any medium. Thank you.

#20 lore raw

Re: [PATCH v2 2/2] mempool/nb_stack: add non-blocking stack mempool

Quoted 116 lines · Gage
Quoted 79 lines

-----Original Message-----
From: Gavin Hu (Arm Technology China) [mailto:[email protected]]
Sent: Thursday, January 17, 2019 2:06 AM
To: Eads, Gage <[email protected]>; [email protected]
Cc: [email protected]; [email protected]; Richardson, Bruce <[email protected]>; Ananyev, Konstantin <[email protected]>; Honnappa Nagarahalli <[email protected]>; Ruifeng Wang (Arm Technology China) <[email protected]>; Phil Yang (Arm Technology China) <[email protected]>
Subject: RE: [dpdk-dev] [PATCH v2 2/2] mempool/nb_stack: add non-blocking stack mempool

Quoted 63 lines

-----Original Message-----
From: dev <[email protected]> On Behalf Of Gage Eads
Sent: Wednesday, January 16, 2019 6:33 AM
To: [email protected]
Cc: [email protected]; [email protected]; [email protected]; [email protected]
Subject: [dpdk-dev] [PATCH v2 2/2] mempool/nb_stack: add non-blocking stack mempool

This commit adds support for non-blocking (linked list based) stack mempool handler. The stack uses a 128-bit compare-and-swap instruction, and thus is limited to x86_64. The 128-bit CAS atomically updates the stack top pointer and a modification counter, which protects against the ABA problem.

In mempool_perf_autotest the lock-based stack outperforms the non- blocking handler*, however:
- For applications with preemptible pthreads, a lock-based stack's worst-case performance (i.e. one thread being preempted while holding the spinlock) is much worse than the non-blocking 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 1x-3.5x the non-blocking stack's.

---
 MAINTAINERS                                        |   4 +
 config/common_base                                 |   1 +
 doc/guides/prog_guide/env_abstraction_layer.rst    |   5 +
 drivers/mempool/Makefile                           |   3 +
 drivers/mempool/meson.build                        |   5 +
 drivers/mempool/nb_stack/Makefile                  |  23 ++++
 drivers/mempool/nb_stack/meson.build               |   4 +
 drivers/mempool/nb_stack/nb_lifo.h                 | 147
+++++++++++++++++++++
 drivers/mempool/nb_stack/rte_mempool_nb_stack.c    | 125
++++++++++++++++++
 .../nb_stack/rte_mempool_nb_stack_version.map      |   4 +
 mk/rte.app.mk                                      |   7 +-
 11 files changed, 326 insertions(+), 2 deletions(-)  create mode
100644 drivers/mempool/nb_stack/Makefile  create mode 100644
drivers/mempool/nb_stack/meson.build
 create mode 100644 drivers/mempool/nb_stack/nb_lifo.h
 create mode 100644 drivers/mempool/nb_stack/rte_mempool_nb_stack.c
 create mode 100644

drivers/mempool/nb_stack/rte_mempool_nb_stack_version.map

MAINTAINERS index 470f36b9c..5519d3323 renamed from MAINTAINERS +0 -0

100644

MAINTAINERS +4 -0
@@ -416,6 +416,10 @@ M: Artem V. Andreev <[email protected]>
 M: Andrew Rybchenko <[email protected]>
 F: drivers/mempool/bucket/
 
+Non-blocking stack memory pool
+M: Gage Eads <[email protected]>
+F: drivers/mempool/nb_stack/
+
 
Quoted 14 lines
Quoted 10 lines
MAINTAINERS +0 -0
 Bus Drivers
 -----------
config/common_base index renamed from config/common_base +0 -0

964a6956e..8a51f36b1 100644

config/common_base +0 -0
@@ -726,6 +726,7 @@ CONFIG_RTE_LIBRTE_MEMPOOL_DEBUG=n  #

CONFIG_RTE_DRIVER_MEMPOOL_BUCKET=y
CONFIG_RTE_DRIVER_MEMPOOL_BUCKET_SIZE_KB=64
+CONFIG_RTE_DRIVER_MEMPOOL_NB_STACK=y

NAK, as this applies to x86_64 only, it will break arm/ppc and even 32bit i386 configurations.

Hi Gavin,

This patch resolves that in the make and meson build files, which ensure that the library is only built for x86-64 targets:

drivers/mempool/Makefile +3 -0
index 28c2e8360..895cf8a34 100644
@@ -10,6 +10,9 @@ endif
 ifeq ($(CONFIG_RTE_EAL_VFIO)$(CONFIG_RTE_LIBRTE_FSLMC_BUS),yy)
 DIRS-$(CONFIG_RTE_LIBRTE_DPAA2_MEMPOOL) += dpaa2
 endif
+ifeq ($(CONFIG_RTE_ARCH_X86_64),y)
+DIRS-$(CONFIG_RTE_DRIVER_MEMPOOL_NB_STACK) += nb_stack
+endif
 
drivers/mempool/nb_stack/meson.build new file +0 -0
new file mode 100644
index 000000000..4a699511d

drivers/mempool/nb_stack/meson.build line 7

Quoted 7 lines
drivers/mempool/nb_stack/meson.build new file +7 -0
@@ -0,0 +1,8 @@
+# SPDX-License-Identifier: BSD-3-Clause
+# Copyright(c) 2019 Intel Corporation
+
+if arch_subdir != 'x86' or cc.sizeof('void *') == 4
+	build = false
+endif
+

Minor suggestion:
Can be simplified to "build = dpdk_conf.has('RTE_ARCH_X86_64')", I believe.

/Bruce

author
#21 lore raw

Re: [PATCH v2 2/2] mempool/nb_stack: add non-blocking stack mempool

Quoted 145 lines

-----Original Message-----
From: Richardson, Bruce
Sent: Thursday, January 17, 2019 8:21 AM
To: Eads, Gage <[email protected]>
Cc: Gavin Hu (Arm Technology China) <[email protected]>; [email protected]; [email protected]; [email protected]; Ananyev, Konstantin <[email protected]>; Honnappa Nagarahalli <[email protected]>; Ruifeng Wang (Arm Technology China) <[email protected]>; Phil Yang (Arm Technology China) <[email protected]>
Subject: Re: [dpdk-dev] [PATCH v2 2/2] mempool/nb_stack: add non-blocking stack mempool

Quoted 96 lines · Gage
Quoted 81 lines

-----Original Message-----
From: Gavin Hu (Arm Technology China) [mailto:[email protected]]
Sent: Thursday, January 17, 2019 2:06 AM
To: Eads, Gage <[email protected]>; [email protected]
Cc: [email protected]; [email protected]; Richardson, Bruce <[email protected]>; Ananyev, Konstantin <[email protected]>; Honnappa Nagarahalli <[email protected]>; Ruifeng Wang (Arm Technology China) <[email protected]>; Phil Yang (Arm Technology China) <[email protected]>
Subject: RE: [dpdk-dev] [PATCH v2 2/2] mempool/nb_stack: add non-blocking stack mempool

Quoted 65 lines

-----Original Message-----
From: dev <[email protected]> On Behalf Of Gage Eads
Sent: Wednesday, January 16, 2019 6:33 AM
To: [email protected]
Cc: [email protected]; [email protected]; [email protected]; [email protected]
Subject: [dpdk-dev] [PATCH v2 2/2] mempool/nb_stack: add non-blocking stack mempool

This commit adds support for non-blocking (linked list based) stack mempool handler. The stack uses a 128-bit compare-and-swap instruction, and thus is limited to x86_64. The 128-bit CAS atomically updates the stack top pointer and a modification counter, which protects against the ABA problem.

In mempool_perf_autotest the lock-based stack outperforms the non- blocking handler*, however:
- For applications with preemptible pthreads, a lock-based stack's worst-case performance (i.e. one thread being preempted while holding the spinlock) is much worse than the non-blocking 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 1x-3.5x the non-blocking stack's.

---
 MAINTAINERS                                        |   4 +
 config/common_base                                 |   1 +
 doc/guides/prog_guide/env_abstraction_layer.rst    |   5 +
 drivers/mempool/Makefile                           |   3 +
 drivers/mempool/meson.build                        |   5 +
 drivers/mempool/nb_stack/Makefile                  |  23 ++++
 drivers/mempool/nb_stack/meson.build               |   4 +
 drivers/mempool/nb_stack/nb_lifo.h                 | 147
+++++++++++++++++++++
 drivers/mempool/nb_stack/rte_mempool_nb_stack.c    | 125
++++++++++++++++++
 .../nb_stack/rte_mempool_nb_stack_version.map      |   4 +
 mk/rte.app.mk                                      |   7 +-
 11 files changed, 326 insertions(+), 2 deletions(-)  create mode
100644 drivers/mempool/nb_stack/Makefile  create mode 100644
drivers/mempool/nb_stack/meson.build
 create mode 100644 drivers/mempool/nb_stack/nb_lifo.h
 create mode 100644
drivers/mempool/nb_stack/rte_mempool_nb_stack.c
 create mode 100644

drivers/mempool/nb_stack/rte_mempool_nb_stack_version.map

MAINTAINERS index 470f36b9c..5519d3323 renamed from MAINTAINERS +0 -0

100644

MAINTAINERS +0 -0
@@ -416,6 +416,10 @@ M: Artem V. Andreev

<[email protected]>
M: Andrew Rybchenko <[email protected]>
F: drivers/mempool/bucket/

MAINTAINERS +4 -0
+Non-blocking stack memory pool
+M: Gage Eads <[email protected]>
+F: drivers/mempool/nb_stack/
+
Quoted 14 lines
Quoted 10 lines

Bus Drivers
-----------

config/common_base index renamed from config/common_base +0 -0

964a6956e..8a51f36b1 100644

config/common_base +0 -0
@@ -726,6 +726,7 @@ CONFIG_RTE_LIBRTE_MEMPOOL_DEBUG=n  #

CONFIG_RTE_DRIVER_MEMPOOL_BUCKET=y
CONFIG_RTE_DRIVER_MEMPOOL_BUCKET_SIZE_KB=64
+CONFIG_RTE_DRIVER_MEMPOOL_NB_STACK=y

NAK, as this applies to x86_64 only, it will break arm/ppc and even 32bit i386 configurations.

Quoted 3 lines

Hi Gavin,

This patch resolves that in the make and meson build files, which ensure that

the library is only built for x86-64 targets:

Quoted 18 lines
drivers/mempool/Makefile index renamed from drivers/mempool/Makefile +0 -0

28c2e8360..895cf8a34 100644

drivers/mempool/Makefile +2 -0
@@ -10,6 +10,9 @@ endif
 ifeq ($(CONFIG_RTE_EAL_VFIO)$(CONFIG_RTE_LIBRTE_FSLMC_BUS),yy)
 DIRS-$(CONFIG_RTE_LIBRTE_DPAA2_MEMPOOL) += dpaa2  endif
+ifeq ($(CONFIG_RTE_ARCH_X86_64),y)
+DIRS-$(CONFIG_RTE_DRIVER_MEMPOOL_NB_STACK) += nb_stack endif
 
drivers/mempool/nb_stack/meson.build new file +0 -0
new file mode 100644
index 000000000..4a699511d

drivers/mempool/nb_stack/meson.build line 7

Quoted 7 lines
drivers/mempool/nb_stack/meson.build new file +7 -0
@@ -0,0 +1,8 @@
+# SPDX-License-Identifier: BSD-3-Clause # Copyright(c) 2019 Intel
+Corporation
+
+if arch_subdir != 'x86' or cc.sizeof('void *') == 4
+	build = false
+endif
+

Minor suggestion:
Can be simplified to "build = dpdk_conf.has('RTE_ARCH_X86_64')", I believe.

Quoted 1 line

/Bruce

Sure, I'll switch to that check in v4.

Thanks,
Gage

#22 lore raw

Re: [PATCH v2 2/2] mempool/nb_stack: add non-blocking stack mempool

Quoted 134 lines

-----Original Message-----
From: Eads, Gage <[email protected]>
Sent: Thursday, January 17, 2019 11:16 PM
To: Richardson, Bruce <[email protected]>
Cc: Gavin Hu (Arm Technology China) <[email protected]>; [email protected]; [email protected]; [email protected]; Ananyev, Konstantin <[email protected]>; Honnappa Nagarahalli <[email protected]>; Ruifeng Wang (Arm Technology China) <[email protected]>; Phil Yang (Arm Technology China) <[email protected]>
Subject: RE: [dpdk-dev] [PATCH v2 2/2] mempool/nb_stack: add non- blocking stack mempool

Quoted 5 lines

-----Original Message-----
From: Richardson, Bruce
Sent: Thursday, January 17, 2019 8:21 AM
To: Eads, Gage <[email protected]>
Cc: Gavin Hu (Arm Technology China) <[email protected]>;

[email protected];

Quoted 1 line

[email protected]; [email protected]; Ananyev,

Konstantin

Quoted 2 lines

<[email protected]>; Honnappa Nagarahalli <[email protected]>; Ruifeng Wang (Arm Technology

China)

Quoted 3 lines

<[email protected]>; Phil Yang (Arm Technology China) <[email protected]>
Subject: Re: [dpdk-dev] [PATCH v2 2/2] mempool/nb_stack: add non-

blocking

Quoted 13 lines

stack mempool

Quoted 10 lines · Gage
Quoted 10 lines

-----Original Message-----
From: Gavin Hu (Arm Technology China) [mailto:[email protected]]
Sent: Thursday, January 17, 2019 2:06 AM
To: Eads, Gage <[email protected]>; [email protected]
Cc: [email protected]; [email protected]; Richardson, Bruce <[email protected]>; Ananyev, Konstantin <[email protected]>; Honnappa Nagarahalli <[email protected]>; Ruifeng Wang (Arm Technology

China)

Quoted 15 lines
Quoted 15 lines
Quoted 15 lines

<[email protected]>; Phil Yang (Arm Technology China) <[email protected]>
Subject: RE: [dpdk-dev] [PATCH v2 2/2] mempool/nb_stack: add non-blocking stack mempool

Quoted 9 lines

-----Original Message-----
From: dev <[email protected]> On Behalf Of Gage Eads
Sent: Wednesday, January 16, 2019 6:33 AM
To: [email protected]
Cc: [email protected]; [email protected]; [email protected]; [email protected]
Subject: [dpdk-dev] [PATCH v2 2/2] mempool/nb_stack: add non-blocking stack mempool

Quoted 2 lines
Quoted 2 lines
Quoted 2 lines
Quoted 2 lines

This commit adds support for non-blocking (linked list based) stack mempool handler. The stack uses a 128-bit compare-and-

swap

Quoted 5 lines
Quoted 5 lines
Quoted 5 lines
Quoted 5 lines

instruction, and thus is limited to x86_64. The 128-bit CAS atomically updates the stack top pointer and a modification counter, which protects against the ABA problem.

In mempool_perf_autotest the lock-based stack outperforms the

non-

Quoted 5 lines
Quoted 5 lines
Quoted 5 lines
Quoted 5 lines

blocking handler*, however:
- For applications with preemptible pthreads, a lock-based stack's worst-case performance (i.e. one thread being preempted while holding the spinlock) is much worse than the non-blocking stack's.
- Using per-thread mempool caches will largely mitigate the

performance

Quoted 5 lines
Quoted 5 lines
Quoted 5 lines
Quoted 5 lines

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 1x-3.5x the non-blocking

stack's.

Quoted 25 lines
Quoted 25 lines
Quoted 25 lines
Quoted 25 lines
---
 MAINTAINERS                                        |   4 +
 config/common_base                                 |   1 +
 doc/guides/prog_guide/env_abstraction_layer.rst    |   5 +
 drivers/mempool/Makefile                           |   3 +
 drivers/mempool/meson.build                        |   5 +
 drivers/mempool/nb_stack/Makefile                  |  23 ++++
 drivers/mempool/nb_stack/meson.build               |   4 +
 drivers/mempool/nb_stack/nb_lifo.h                 | 147
+++++++++++++++++++++
 drivers/mempool/nb_stack/rte_mempool_nb_stack.c    | 125
++++++++++++++++++
 .../nb_stack/rte_mempool_nb_stack_version.map      |   4 +
 mk/rte.app.mk                                      |   7 +-
 11 files changed, 326 insertions(+), 2 deletions(-)  create mode
100644 drivers/mempool/nb_stack/Makefile  create mode 100644
drivers/mempool/nb_stack/meson.build
 create mode 100644 drivers/mempool/nb_stack/nb_lifo.h
 create mode 100644
drivers/mempool/nb_stack/rte_mempool_nb_stack.c
 create mode 100644

drivers/mempool/nb_stack/rte_mempool_nb_stack_version.map

Quoted 1 line
Quoted 1 line
Quoted 1 line

MAINTAINERS index

Quoted 1 line
MAINTAINERS index renamed from MAINTAINERS +0 -0

470f36b9c..5519d3323

Quoted 13 lines
Quoted 13 lines
Quoted 13 lines
Quoted 13 lines

100644

MAINTAINERS +0 -0
@@ -416,6 +416,10 @@ M: Artem V. Andreev

<[email protected]>
M: Andrew Rybchenko <[email protected]>
F: drivers/mempool/bucket/

MAINTAINERS +4 -0
+Non-blocking stack memory pool
+M: Gage Eads <[email protected]>
+F: drivers/mempool/nb_stack/
+
Quoted 7 lines
Quoted 7 lines
Quoted 7 lines

config/common_base CONFIG_RTE_LIBRTE_MEMPOOL_DEBUG=n

Quoted 7 lines

Bus Drivers
-----------

config/common_base index renamed from config/common_base +0 -0

964a6956e..8a51f36b1 100644

config/common_base +0 -0
@@ -726,6 +726,7 @@ CONFIG_RTE_LIBRTE_MEMPOOL_DEBUG=n

#

Quoted 4 lines
Quoted 4 lines
Quoted 4 lines
Quoted 3 lines

CONFIG_RTE_DRIVER_MEMPOOL_BUCKET=y
CONFIG_RTE_DRIVER_MEMPOOL_BUCKET_SIZE_KB=64
+CONFIG_RTE_DRIVER_MEMPOOL_NB_STACK=y

Quoted 9 lines
Quoted 7 lines
Quoted 7 lines
Quoted 3 lines

NAK, as this applies to x86_64 only, it will break arm/ppc and even 32bit i386 configurations.

Hi Gavin,

This patch resolves that in the make and meson build files, which

ensure that

Quoted 1 line

the library is only built for x86-64 targets:

Looking down to the changes with Makefile and meson.build, it will be compiled out for arm/ppc/i386. That works at least. But having this entry in the arm/ppc/i386 configurations is very strange, since they have no such implementations. Why not put it into defconfig_x86_64-native-linuxapp-icc/gcc/clang to limit the scope?

Quoted 29 lines
Quoted 2 lines

drivers/mempool/Makefile

Quoted 2 lines
drivers/mempool/Makefile +0 -0

index

Quoted 18 lines
Quoted 18 lines

28c2e8360..895cf8a34 100644

drivers/mempool/Makefile +2 -0
@@ -10,6 +10,9 @@ endif
 ifeq ($(CONFIG_RTE_EAL_VFIO)$(CONFIG_RTE_LIBRTE_FSLMC_BUS),yy)
 DIRS-$(CONFIG_RTE_LIBRTE_DPAA2_MEMPOOL) += dpaa2  endif
+ifeq ($(CONFIG_RTE_ARCH_X86_64),y)
+DIRS-$(CONFIG_RTE_DRIVER_MEMPOOL_NB_STACK) += nb_stack endif
 
drivers/mempool/nb_stack/meson.build new file +2 -0
new file mode 100644
index 000000000..4a699511d
@@ -0,0 +1,8 @@
+# SPDX-License-Identifier: BSD-3-Clause # Copyright(c) 2019 Intel
+Corporation
Quoted 8 lines

drivers/mempool/nb_stack/meson.build line 7

Quoted 5 lines
drivers/mempool/nb_stack/meson.build new file +5 -0
+
+if arch_subdir != 'x86' or cc.sizeof('void *') == 4
+build = false
+endif
+

Minor suggestion:
Can be simplified to "build = dpdk_conf.has('RTE_ARCH_X86_64')", I

Quoted 8 lines

believe.

Quoted 2 lines

/Bruce

Sure, I'll switch to that check in v4.

Thanks,
Gage

IMPORTANT NOTICE: The contents of this email and any attachments are confidential and may also be privileged. If you are not the intended recipient, please notify the sender immediately and do not disclose the contents to any other person, use it for any purpose, or store or copy the information in any medium. Thank you.

author
#23 lore raw

Re: [PATCH v2 2/2] mempool/nb_stack: add non-blocking stack mempool

Quoted 160 lines

-----Original Message-----
From: Gavin Hu (Arm Technology China) [mailto:[email protected]]
Sent: Thursday, January 17, 2019 9:42 AM
To: Eads, Gage <[email protected]>; Richardson, Bruce <[email protected]>
Cc: [email protected]; [email protected]; [email protected]; Ananyev, Konstantin <[email protected]>; Honnappa Nagarahalli <[email protected]>; Ruifeng Wang (Arm Technology China) <[email protected]>; Phil Yang (Arm Technology China) <[email protected]>
Subject: RE: [dpdk-dev] [PATCH v2 2/2] mempool/nb_stack: add non-blocking stack mempool

Quoted 143 lines

-----Original Message-----
From: Eads, Gage <[email protected]>
Sent: Thursday, January 17, 2019 11:16 PM
To: Richardson, Bruce <[email protected]>
Cc: Gavin Hu (Arm Technology China) <[email protected]>; [email protected]; [email protected]; [email protected]; Ananyev, Konstantin <[email protected]>; Honnappa Nagarahalli <[email protected]>; Ruifeng Wang (Arm Technology China) <[email protected]>; Phil Yang (Arm Technology
China) <[email protected]>
Subject: RE: [dpdk-dev] [PATCH v2 2/2] mempool/nb_stack: add non- blocking stack mempool

Quoted 5 lines

-----Original Message-----
From: Richardson, Bruce
Sent: Thursday, January 17, 2019 8:21 AM
To: Eads, Gage <[email protected]>
Cc: Gavin Hu (Arm Technology China) <[email protected]>;

[email protected];

Quoted 1 line

[email protected]; [email protected]; Ananyev,

Konstantin

Quoted 2 lines

<[email protected]>; Honnappa Nagarahalli <[email protected]>; Ruifeng Wang (Arm Technology

China)

Quoted 3 lines

<[email protected]>; Phil Yang (Arm Technology China) <[email protected]>
Subject: Re: [dpdk-dev] [PATCH v2 2/2] mempool/nb_stack: add non-

blocking

Quoted 13 lines

stack mempool

Quoted 10 lines · Gage
Quoted 10 lines

-----Original Message-----
From: Gavin Hu (Arm Technology China) [mailto:[email protected]]
Sent: Thursday, January 17, 2019 2:06 AM
To: Eads, Gage <[email protected]>; [email protected]
Cc: [email protected]; [email protected]; Richardson, Bruce <[email protected]>; Ananyev, Konstantin <[email protected]>; Honnappa Nagarahalli <[email protected]>; Ruifeng Wang (Arm Technology

China)

Quoted 15 lines
Quoted 15 lines
Quoted 15 lines

<[email protected]>; Phil Yang (Arm Technology China) <[email protected]>
Subject: RE: [dpdk-dev] [PATCH v2 2/2] mempool/nb_stack: add non-blocking stack mempool

Quoted 9 lines

-----Original Message-----
From: dev <[email protected]> On Behalf Of Gage Eads
Sent: Wednesday, January 16, 2019 6:33 AM
To: [email protected]
Cc: [email protected]; [email protected]; [email protected]; [email protected]
Subject: [dpdk-dev] [PATCH v2 2/2] mempool/nb_stack: add non-blocking stack mempool

Quoted 2 lines
Quoted 2 lines
Quoted 2 lines
Quoted 2 lines

This commit adds support for non-blocking (linked list based) stack mempool handler. The stack uses a 128-bit compare-and-

swap

Quoted 5 lines
Quoted 5 lines
Quoted 5 lines
Quoted 5 lines

instruction, and thus is limited to x86_64. The 128-bit CAS atomically updates the stack top pointer and a modification counter, which protects against the ABA problem.

In mempool_perf_autotest the lock-based stack outperforms the

non-

Quoted 5 lines
Quoted 5 lines
Quoted 5 lines
Quoted 5 lines

blocking handler*, however:
- For applications with preemptible pthreads, a lock-based stack's worst-case performance (i.e. one thread being preempted while holding the spinlock) is much worse than the non-blocking stack's.
- Using per-thread mempool caches will largely mitigate the

performance

Quoted 7 lines
Quoted 7 lines
Quoted 7 lines
Quoted 7 lines

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 1x-3.5x the non-blocking

stack's.

Quoted 26 lines
Quoted 26 lines
Quoted 26 lines
Quoted 26 lines
---
 MAINTAINERS                                        |   4 +
 config/common_base                                 |   1 +
 doc/guides/prog_guide/env_abstraction_layer.rst    |   5 +
 drivers/mempool/Makefile                           |   3 +
 drivers/mempool/meson.build                        |   5 +
 drivers/mempool/nb_stack/Makefile                  |  23 ++++
 drivers/mempool/nb_stack/meson.build               |   4 +
 drivers/mempool/nb_stack/nb_lifo.h                 | 147
+++++++++++++++++++++
 drivers/mempool/nb_stack/rte_mempool_nb_stack.c    | 125
++++++++++++++++++
 .../nb_stack/rte_mempool_nb_stack_version.map      |   4 +
 mk/rte.app.mk                                      |   7 +-
 11 files changed, 326 insertions(+), 2 deletions(-)  create
mode
100644 drivers/mempool/nb_stack/Makefile  create mode 100644
drivers/mempool/nb_stack/meson.build
 create mode 100644 drivers/mempool/nb_stack/nb_lifo.h
 create mode 100644
drivers/mempool/nb_stack/rte_mempool_nb_stack.c
 create mode 100644

drivers/mempool/nb_stack/rte_mempool_nb_stack_version.map

Quoted 1 line
Quoted 1 line
Quoted 1 line

MAINTAINERS index

Quoted 1 line
MAINTAINERS index renamed from MAINTAINERS +0 -0

470f36b9c..5519d3323

Quoted 13 lines
Quoted 13 lines
Quoted 13 lines
Quoted 13 lines

100644

MAINTAINERS +0 -0
@@ -416,6 +416,10 @@ M: Artem V. Andreev

<[email protected]>
M: Andrew Rybchenko <[email protected]>
F: drivers/mempool/bucket/

MAINTAINERS +4 -0
+Non-blocking stack memory pool
+M: Gage Eads <[email protected]>
+F: drivers/mempool/nb_stack/
+
Quoted 7 lines
Quoted 7 lines
Quoted 7 lines

config/common_base CONFIG_RTE_LIBRTE_MEMPOOL_DEBUG=n

Quoted 7 lines

Bus Drivers
-----------

config/common_base index renamed from config/common_base +0 -0

964a6956e..8a51f36b1 100644

config/common_base +0 -0
@@ -726,6 +726,7 @@ CONFIG_RTE_LIBRTE_MEMPOOL_DEBUG=n

#

Quoted 11 lines
Quoted 11 lines
Quoted 7 lines
Quoted 3 lines

CONFIG_RTE_DRIVER_MEMPOOL_BUCKET=y
CONFIG_RTE_DRIVER_MEMPOOL_BUCKET_SIZE_KB=64
+CONFIG_RTE_DRIVER_MEMPOOL_NB_STACK=y

NAK, as this applies to x86_64 only, it will break arm/ppc and even 32bit i386 configurations.

Hi Gavin,

This patch resolves that in the make and meson build files, which

ensure that

Quoted 9 lines
Quoted 1 line
Quoted 1 line

the library is only built for x86-64 targets:

Looking down to the changes with Makefile and meson.build, it will be compiled out for arm/ppc/i386. That works at least.
But having this entry in the arm/ppc/i386 configurations is very strange, since they have no such implementations.
Why not put it into defconfig_x86_64-native-linuxapp-icc/gcc/clang to limit the scope?

Certainly, that's reasonable -- it simply slipped my mind. I'll address this in the next version.

Thanks,
Gage

Quoted 5 lines

IMPORTANT NOTICE: The contents of this email and any attachments are confidential and may also be privileged. If you are not the intended recipient, please notify the sender immediately and do not disclose the contents to any other person, use it for any purpose, or store or copy the information in any medium. Thank you.

author
#24 lore raw

v3 cover Add non-blocking stack mempool handler

In reply to Gage Eads

For some users, 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.

This patchset introduces a non-blocking stack mempool handler. Note that the non-blocking algorithm relies on a 128-bit compare-and-swap, so it is limited to x86_64 machines.

In mempool_perf_autotest the lock-based stack outperforms the non-blocking handler*, however:
- For applications with preemptible pthreads, a lock-based stack's worst-case performance (i.e. one thread being preempted while holding the spinlock) is much worse than the non-blocking 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 1x-3.5x the non-blocking stack's.

v3:
- Fix two more space-after-typecast issues
- Rework nb_stack's meson.build x86_64 check, borrowing from net/sfc/

v2:
- Merge separate docs commit into patch #2
- Fix two space-after-typecast issues
- Fix alphabetical sorting for build files
- Remove unnecessary include path from nb_stack/Makefile
- Add a comment to nb_lifo_len() justifying its approximate behavior
- Fix comparison with NULL
- Remove unnecessary void * cast
- Fix meson builds and limit them to x86_64
- Fix missing library error for non-x86_64 builds

Gage Eads (2):
eal: add 128-bit cmpset (x86-64 only) mempool/nb_stack: add non-blocking stack mempool

 MAINTAINERS                                        |   4 +
 config/common_base                                 |   1 +
 doc/guides/prog_guide/env_abstraction_layer.rst    |   5 +
 drivers/mempool/Makefile                           |   3 +
 drivers/mempool/meson.build                        |   3 +-
 drivers/mempool/nb_stack/Makefile                  |  23 ++++
 drivers/mempool/nb_stack/meson.build               |   8 ++
 drivers/mempool/nb_stack/nb_lifo.h                 | 147 +++++++++++++++++++++
 drivers/mempool/nb_stack/rte_mempool_nb_stack.c    | 125 ++++++++++++++++++
 .../nb_stack/rte_mempool_nb_stack_version.map      |   4 +
 .../common/include/arch/x86/rte_atomic_64.h        |  22 +++
 mk/rte.app.mk                                      |   7 +-
 12 files changed, 349 insertions(+), 3 deletions(-)
 create mode 100644 drivers/mempool/nb_stack/Makefile
 create mode 100644 drivers/mempool/nb_stack/meson.build
 create mode 100644 drivers/mempool/nb_stack/nb_lifo.h
 create mode 100644 drivers/mempool/nb_stack/rte_mempool_nb_stack.c
 create mode 100644 drivers/mempool/nb_stack/rte_mempool_nb_stack_version.map
Signature · 1 line
2.13.6
author
#25 lore raw

PATCH v3 1/2 eal: add 128-bit cmpset (x86-64 only)

This operation can be used for non-blocking algorithms, such as a non-blocking stack or ring.

---
 .../common/include/arch/x86/rte_atomic_64.h        | 22 ++++++++++++++++++++++
 1 file changed, 22 insertions(+)
lib/librte_eal/common/include/arch/x86/rte_atomic_64.h +22 -0
index fd2ec9c53..34c2addf8 100644
@@ -34,6 +34,7 @@
 /*
  * Inspired from FreeBSD src/sys/amd64/include/atomic.h
  * Copyright (c) 1998 Doug Rabson
+ * Copyright (c) 2019 Intel Corporation
  * All rights reserved.
  */
 
@@ -208,4 +209,25 @@ static inline void rte_atomic64_clear(rte_atomic64_t *v)
 }
 #endif
 
+static inline int
+rte_atomic128_cmpset(volatile uint64_t *dst, uint64_t *exp, uint64_t *src)
+{
+	uint8_t res;
+
+	asm volatile (
+		      MPLOCKED
+		      "cmpxchg16b %[dst];"
+		      " sete %[res]"
+		      : [dst] "=m" (*dst),
+			[res] "=r" (res)
+		      : "c" (src[1]),
+			"b" (src[0]),
+			"m" (*dst),
+			"d" (exp[1]),
+			"a" (exp[0])
+		      : "memory");
+
+	return res;
+}
+
 #endif /* _RTE_ATOMIC_X86_64_H_ */
Signature · 1 line
2.13.6
#26 lore raw

Re: [PATCH v3 1/2] eal: add 128-bit cmpset (x86-64 only)

lib/librte_eal/common/include/arch/x86/rte_atomic_64.h

Quoted 16 lines

Subject: [dpdk-dev] [PATCH v3 1/2] eal: add 128-bit cmpset (x86-64 only)

This operation can be used for non-blocking algorithms, such as a non- blocking stack or ring.

---
 .../common/include/arch/x86/rte_atomic_64.h        | 22
++++++++++++++++++++++
 1 file changed, 22 insertions(+)
lib/librte_eal/common/include/arch/x86/rte_atomic_64.h +0 -0
index fd2ec9c53..34c2addf8 100644

Since this is a 128b operation should there be a new file created with the name rte_atomic_128.h?

Quoted 9 lines
lib/librte_eal/common/include/arch/x86/rte_atomic_64.h +1 -0
@@ -34,6 +34,7 @@
 /*
  * Inspired from FreeBSD src/sys/amd64/include/atomic.h
  * Copyright (c) 1998 Doug Rabson
+ * Copyright (c) 2019 Intel Corporation
  * All rights reserved.
  */
 

lib/librte_eal/common/include/arch/x86/rte_atomic_64.h static inline void rte_atomic64_clear(rte_atomic64_t · line 213

Quoted 5 lines
lib/librte_eal/common/include/arch/x86/rte_atomic_64.h +3 -0
@@ -208,4 +209,25 @@ static inline void rte_atomic64_clear(rte_atomic64_t
 *v)  }  #endif
 
+static inline int
+rte_atomic128_cmpset(volatile uint64_t *dst, uint64_t *exp, uint64_t
+*src) {

The API name suggests it is a 128b operation. 'dst', 'exp' and 'src' should be pointers to 128b (__int128)? Or we could define our own data type.
Since, it is a new API, can we define it with memory orderings which will be more conducive to relaxed memory ordering based architectures? You can refer to [1] and [2] for guidance. If this an external API, it requires 'experimental' tag.

1. https://github.com/ARM-software/progress64/blob/master/src/lockfree/aarch64.h#L63
2. https://github.com/ARM-software/progress64/blob/master/src/lockfree/x86-64.h#L34

Quoted 21 lines
lib/librte_eal/common/include/arch/x86/rte_atomic_64.h +18 -1
+	uint8_t res;
+
+	asm volatile (
+		      MPLOCKED
+		      "cmpxchg16b %[dst];"
+		      " sete %[res]"
+		      : [dst] "=m" (*dst),
+			[res] "=r" (res)
+		      : "c" (src[1]),
+			"b" (src[0]),
+			"m" (*dst),
+			"d" (exp[1]),
+			"a" (exp[0])
+		      : "memory");
+
+	return res;
+}
+
 #endif /* _RTE_ATOMIC_X86_64_H_ */
--

2.13.6

author
#27 lore raw

Re: [PATCH v3 1/2] eal: add 128-bit cmpset (x86-64 only)

Quoted 44 lines

-----Original Message-----
From: Honnappa Nagarahalli [mailto:[email protected]]
Sent: Thursday, January 17, 2019 9:45 AM
To: Eads, Gage <[email protected]>; [email protected]
Cc: [email protected]; [email protected]; Richardson, Bruce <[email protected]>; Ananyev, Konstantin <[email protected]>; nd <[email protected]>; Honnappa Nagarahalli <[email protected]>; nd <[email protected]>
Subject: RE: [dpdk-dev] [PATCH v3 1/2] eal: add 128-bit cmpset (x86-64 only)

lib/librte_eal/common/include/arch/x86/rte_atomic_64.h

Quoted 17 lines

Subject: [dpdk-dev] [PATCH v3 1/2] eal: add 128-bit cmpset (x86-64 only)

This operation can be used for non-blocking algorithms, such as a non- blocking stack or ring.

---
 .../common/include/arch/x86/rte_atomic_64.h        | 22
++++++++++++++++++++++
 1 file changed, 22 insertions(+)
lib/librte_eal/common/include/arch/x86/rte_atomic_64.h +0 -0
index fd2ec9c53..34c2addf8 100644

Since this is a 128b operation should there be a new file created with the name rte_atomic_128.h?

Quoted 12 lines
lib/librte_eal/common/include/arch/x86/rte_atomic_64.h +1 -0
@@ -34,6 +34,7 @@
 /*
  * Inspired from FreeBSD src/sys/amd64/include/atomic.h
  * Copyright (c) 1998 Doug Rabson
+ * Copyright (c) 2019 Intel Corporation
  * All rights reserved.
  */
 
@@ -208,4 +209,25 @@ static inline void

rte_atomic64_clear(rte_atomic64_t
*v) } #endif

Quoted 5 lines

lib/librte_eal/common/include/arch/x86/rte_atomic_64.h

Quoted 3 lines
lib/librte_eal/common/include/arch/x86/rte_atomic_64.h +3 -0
+static inline int
+rte_atomic128_cmpset(volatile uint64_t *dst, uint64_t *exp, uint64_t
+*src) {

The API name suggests it is a 128b operation. 'dst', 'exp' and 'src' should be pointers to 128b (__int128)? Or we could define our own data type.

I agree, I'm not a big fan of the 64b pointers here. I avoided __int128 originally because it fails to compile with -pedantic, but on second thought (and with your suggestion of a separate data type), we can resolve that with this typedef:

typedef struct {
        RTE_STD_C11 __int128 val;
} rte_int128_t;
Quoted 3 lines

Since, it is a new API, can we define it with memory orderings which will be more conducive to relaxed memory ordering based architectures? You can refer to [1] and [2] for guidance.

I certainly see the value in controlling the operation's memory ordering, like in the __atomic intrinsics, but I'm not sure this patchset is the right place to address that. I see that work going a couple ways:
1. Expand the existing rte_atomicN_* interfaces with additional arguments. In that case, I'd prefer this be done in a separate patchset that addresses all the atomic operations, not just cmpset, so the interface changes are chosen according to the needs of the full set of atomic operations. If this approach is taken then there's no need to solve this while rte_atomic128_cmpset is experimental, since all the other functions are non-experimental anyway.

- Or -

2. Don't modify the existing rte_atomicN_* interfaces (or their strongly ordered behavior), and instead create new versions of them that take additional arguments. In this case, we can implement rte_atomic128_cmpset() as is and create a more flexible version in a later patchset.

Either way, I think the current interface (w.r.t. memory ordering options) can work and still leaves us in a good position for future changes/improvements.

Quoted 1 line

If this an external API, it requires 'experimental' tag.

Good catch -- will fix.

Quoted 3 lines

1. https://github.com/ARM-
software/progress64/blob/master/src/lockfree/aarch64.h#L63

I didn't know about aarch64's CASP instruction -- very cool!

Quoted 24 lines

2. https://github.com/ARM-
software/progress64/blob/master/src/lockfree/x86-64.h#L34

Quoted 21 lines
lib/librte_eal/common/include/arch/x86/rte_atomic_64.h +18 -1
+	uint8_t res;
+
+	asm volatile (
+		      MPLOCKED
+		      "cmpxchg16b %[dst];"
+		      " sete %[res]"
+		      : [dst] "=m" (*dst),
+			[res] "=r" (res)
+		      : "c" (src[1]),
+			"b" (src[0]),
+			"m" (*dst),
+			"d" (exp[1]),
+			"a" (exp[0])
+		      : "memory");
+
+	return res;
+}
+
 #endif /* _RTE_ATOMIC_X86_64_H_ */
--

2.13.6

#28 lore raw

Re: [PATCH v3 1/2] eal: add 128-bit cmpset (x86-64 only)

Quoted 38 lines
Quoted 30 lines

lib/librte_eal/common/include/arch/x86/rte_atomic_64.h

Quoted 15 lines

This operation can be used for non-blocking algorithms, such as a non- blocking stack or ring.

---
 .../common/include/arch/x86/rte_atomic_64.h        | 22
++++++++++++++++++++++
 1 file changed, 22 insertions(+)
lib/librte_eal/common/include/arch/x86/rte_atomic_64.h +0 -0
index fd2ec9c53..34c2addf8 100644

Since this is a 128b operation should there be a new file created with the name rte_atomic_128.h?

Quoted 12 lines
lib/librte_eal/common/include/arch/x86/rte_atomic_64.h +1 -0
@@ -34,6 +34,7 @@
 /*
  * Inspired from FreeBSD src/sys/amd64/include/atomic.h
  * Copyright (c) 1998 Doug Rabson
+ * Copyright (c) 2019 Intel Corporation
  * All rights reserved.
  */
 
@@ -208,4 +209,25 @@ static inline void

rte_atomic64_clear(rte_atomic64_t
*v) } #endif

Quoted 6 lines

lib/librte_eal/common/include/arch/x86/rte_atomic_64.h

Quoted 4 lines
lib/librte_eal/common/include/arch/x86/rte_atomic_64.h +4 -0
+static inline int
+rte_atomic128_cmpset(volatile uint64_t *dst, uint64_t *exp,
+uint64_t
+*src) {

The API name suggests it is a 128b operation. 'dst', 'exp' and 'src' should be pointers to 128b (__int128)? Or we could define our own data

type.

Quoted 8 lines

I agree, I'm not a big fan of the 64b pointers here. I avoided __int128 originally because it fails to compile with -pedantic, but on second thought (and with your suggestion of a separate data type), we can resolve that with this typedef:

typedef struct {
        RTE_STD_C11 __int128 val;
} rte_int128_t;

ok

Quoted 17 lines
Quoted 4 lines

Since, it is a new API, can we define it with memory orderings which will be more conducive to relaxed memory ordering based architectures? You can refer to [1] and [2] for guidance.

I certainly see the value in controlling the operation's memory ordering, like in the __atomic intrinsics, but I'm not sure this patchset is the right place to address that. I see that work going a couple ways:
1. Expand the existing rte_atomicN_* interfaces with additional arguments. In that case, I'd prefer this be done in a separate patchset that addresses all the atomic operations, not just cmpset, so the interface changes are chosen according to the needs of the full set of atomic operations. If this approach is taken then there's no need to solve this while rte_atomic128_cmpset is experimental, since all the other functions are non-experimental anyway.

- Or -

Quoted 8 lines

2. Don't modify the existing rte_atomicN_* interfaces (or their strongly ordered behavior), and instead create new versions of them that take additional arguments. In this case, we can implement rte_atomic128_cmpset() as is and create a more flexible version in a later patchset.

Either way, I think the current interface (w.r.t. memory ordering options) can work and still leaves us in a good position for future changes/improvements.

I do not see the need to modify/extend the existing rte_atomicN_* APIs as the corresponding __atomic intrinsics serve as replacements. I expect that at some point, DPDK code base will not be using rte_atomicN_* APIs.
However, __atomic intrinsics do not support 128b wide parameters. Hence DPDK needs to write its own. Since this is the first API in that regard, I prefer that we start with a signature that resembles __atomic intrinsics which have been proven to provide best flexibility for all the platforms supported by DPDK.

Quoted 34 lines
Quoted 1 line

If this an external API, it requires 'experimental' tag.

Good catch -- will fix.

Quoted 3 lines

1. https://github.com/ARM-
software/progress64/blob/master/src/lockfree/aarch64.h#L63

I didn't know about aarch64's CASP instruction -- very cool!

Quoted 24 lines

2. https://github.com/ARM-
software/progress64/blob/master/src/lockfree/x86-64.h#L34

Quoted 21 lines
lib/librte_eal/common/include/arch/x86/rte_atomic_64.h +18 -1
+	uint8_t res;
+
+	asm volatile (
+		      MPLOCKED
+		      "cmpxchg16b %[dst];"
+		      " sete %[res]"
+		      : [dst] "=m" (*dst),
+			[res] "=r" (res)
+		      : "c" (src[1]),
+			"b" (src[0]),
+			"m" (*dst),
+			"d" (exp[1]),
+			"a" (exp[0])
+		      : "memory");
+
+	return res;
+}
+
 #endif /* _RTE_ATOMIC_X86_64_H_ */
--

2.13.6

author
#29 lore raw

Re: [PATCH v3 1/2] eal: add 128-bit cmpset (x86-64 only)

Quoted 86 lines

-----Original Message-----
From: Honnappa Nagarahalli [mailto:[email protected]]
Sent: Thursday, January 17, 2019 11:28 PM
To: Eads, Gage <[email protected]>; [email protected]
Cc: [email protected]; [email protected]; Richardson, Bruce <[email protected]>; Ananyev, Konstantin <[email protected]>; nd <[email protected]>; nd <[email protected]>
Subject: RE: [dpdk-dev] [PATCH v3 1/2] eal: add 128-bit cmpset (x86-64 only)

Quoted 40 lines
Quoted 31 lines

lib/librte_eal/common/include/arch/x86/rte_atomic_64.h

Quoted 16 lines

This operation can be used for non-blocking algorithms, such as a non- blocking stack or ring.

---
 .../common/include/arch/x86/rte_atomic_64.h        | 22
++++++++++++++++++++++
 1 file changed, 22 insertions(+)

diff --git a/lib/librte_eal/common/include/arch/x86/rte_atomic_64.h b/lib/librte_eal/common/include/arch/x86/rte_atomic_64.h index fd2ec9c53..34c2addf8 100644

lib/librte_eal/common/include/arch/x86/rte_atomic_64.h +0 -0

Since this is a 128b operation should there be a new file created with the name rte_atomic_128.h?

Quoted 12 lines
lib/librte_eal/common/include/arch/x86/rte_atomic_64.h +1 -0
@@ -34,6 +34,7 @@
 /*
  * Inspired from FreeBSD src/sys/amd64/include/atomic.h
  * Copyright (c) 1998 Doug Rabson
+ * Copyright (c) 2019 Intel Corporation
  * All rights reserved.
  */
 
@@ -208,4 +209,25 @@ static inline void

rte_atomic64_clear(rte_atomic64_t
*v) } #endif

Quoted 7 lines

lib/librte_eal/common/include/arch/x86/rte_atomic_64.h

Quoted 4 lines
lib/librte_eal/common/include/arch/x86/rte_atomic_64.h +4 -0
+static inline int
+rte_atomic128_cmpset(volatile uint64_t *dst, uint64_t *exp,
+uint64_t
+*src) {

The API name suggests it is a 128b operation. 'dst', 'exp' and 'src' should be pointers to 128b (__int128)? Or we could define our own data

type.

Quoted 8 lines

I agree, I'm not a big fan of the 64b pointers here. I avoided __int128 originally because it fails to compile with -pedantic, but on second thought (and with your suggestion of a separate data type), we can resolve that with this typedef:

typedef struct {
        RTE_STD_C11 __int128 val;
} rte_int128_t;

ok

Quoted 8 lines
Quoted 4 lines

Since, it is a new API, can we define it with memory orderings which will be more conducive to relaxed memory ordering based architectures? You can refer to [1] and [2] for guidance.

I certainly see the value in controlling the operation's memory ordering, like in the __atomic intrinsics, but I'm not sure this patchset is the right place to address that. I see that work going a couple

ways:

Quoted 6 lines

1. Expand the existing rte_atomicN_* interfaces with additional arguments. In that case, I'd prefer this be done in a separate patchset that addresses all the atomic operations, not just cmpset, so the interface changes are chosen according to the needs of the full set of atomic operations. If this approach is taken then there's no need to solve this while rte_atomic128_cmpset is experimental, since all the

other functions are non-experimental anyway.

Quoted 7 lines

- Or -

2. Don't modify the existing rte_atomicN_* interfaces (or their strongly ordered behavior), and instead create new versions of them that take additional arguments. In this case, we can implement rte_atomic128_cmpset() as is and create a more flexible version in a later

patchset.

Quoted 1 line
Quoted 8 lines
Quoted 2 lines

Either way, I think the current interface (w.r.t. memory ordering options) can work and still leaves us in a good position for future

changes/improvements.

Quoted 1 line

I do not see the need to modify/extend the existing rte_atomicN_* APIs as the corresponding __atomic intrinsics serve as replacements. I expect that at some point, DPDK code base will not be using rte_atomicN_* APIs. However, __atomic intrinsics do not support 128b wide parameters. Hence

I don't think that's correct. From the GCC docs:

"16-byte integral types are also allowed if `__int128' (see __int128) is supported by the architecture."

This works with x86 -64 -- I assume aarch64 also, but haven't confirmed.

Source: https://gcc.gnu.org/onlinedocs/gcc-4.7.0/gcc/_005f_005fatomic-Builtins.html

Quoted 3 lines

DPDK needs to write its own. Since this is the first API in that regard, I prefer that we start with a signature that resembles __atomic intrinsics which have been proven to provide best flexibility for all the platforms supported by DPDK.

#30 lore raw

Re: [PATCH v3 1/2] eal: add 128-bit cmpset (x86-64 only)

Added other platform owners.

Quoted 65 lines
Quoted 18 lines
Quoted 18 lines
Quoted 11 lines

Review

Quoted 8 lines
(quoted diff) +0 -0
@@ -208,4 +209,25 @@ static inline void

rte_atomic64_clear(rte_atomic64_t
*v) } #endif

(quoted diff) +4 -0
+static inline int
+rte_atomic128_cmpset(volatile uint64_t *dst, uint64_t *exp,
+uint64_t
+*src) {

The API name suggests it is a 128b operation. 'dst', 'exp' and 'src' should be pointers to 128b (__int128)? Or we could define our own data

type.

I agree, I'm not a big fan of the 64b pointers here. I avoided __int128 originally because it fails to compile with -pedantic, but on second thought (and with your suggestion of a separate data type), we can resolve that with this typedef:

Quoted 8 lines
Quoted 3 lines
typedef struct {
        RTE_STD_C11 __int128 val;
} rte_int128_t;

ok

Quoted 3 lines
Quoted 3 lines

Since, it is a new API, can we define it with memory orderings which will be more conducive to relaxed memory ordering based

architectures?

Quoted 25 lines
Quoted 6 lines
Quoted 1 line

You can refer to [1] and [2] for guidance.

I certainly see the value in controlling the operation's memory ordering, like in the __atomic intrinsics, but I'm not sure this patchset is the right place to address that. I see that work going a couple

ways:

Quoted 7 lines

1. Expand the existing rte_atomicN_* interfaces with additional arguments. In that case, I'd prefer this be done in a separate patchset that addresses all the atomic operations, not just cmpset, so the interface changes are chosen according to the needs of the full set of atomic operations. If this approach is taken then there's no need to solve this while rte_atomic128_cmpset is experimental, since all the

other functions are non-experimental anyway.

Quoted 8 lines

- Or -

2. Don't modify the existing rte_atomicN_* interfaces (or their strongly ordered behavior), and instead create new versions of them that take additional arguments. In this case, we can implement rte_atomic128_cmpset() as is and create a more flexible version in a later

patchset.

Quoted 1 line
Quoted 7 lines
Quoted 2 lines

Either way, I think the current interface (w.r.t. memory ordering options) can work and still leaves us in a good position for future

changes/improvements.

Quoted 1 line

I do not see the need to modify/extend the existing rte_atomicN_* APIs as the corresponding __atomic intrinsics serve as replacements. I expect that at some point, DPDK code base will not be using

rte_atomicN_* APIs.

Quoted 2 lines

However, __atomic intrinsics do not support 128b wide parameters. Hence

I don't think that's correct. From the GCC docs:

Quoted 7 lines

"16-byte integral types are also allowed if `__int128' (see __int128) is supported by the architecture."

This works with x86 -64 -- I assume aarch64 also, but haven't confirmed.

Source: https://gcc.gnu.org/onlinedocs/gcc-4.7.0/gcc/_005f_005fatomic-
Builtins.html

(following is based on my reading, not based on experiments)
My understanding is that the __atomic_load_n/store_n were implemented using a compare-and-swap HW instruction (due to lack of HW 128b atomic load and store instructions). This introduced the side effect or store/load respectively. Where as the user does not expect such side effects. As suggested in [1], it looks like GCC delegated the implementation to libatomic which 'it seems' uses locks to implement 128b __atomic intrinsics (needs to be verified)

If __atomic intrinsics, for any of the supported platforms, do not have an optimal implementation, I prefer to add a DPDK API as an abstraction. A given platform can choose to implement such an API using __atomic intrinsics if it wants. The DPDK API can be similar to __atomic_compare_exchange_n.

[1] https://patchwork.ozlabs.org/patch/721686/
[2] https://gcc.gnu.org/ml/gcc/2017-01/msg00167.html

Quoted 5 lines
Quoted 4 lines

DPDK needs to write its own. Since this is the first API in that regard, I prefer that we start with a signature that resembles __atomic intrinsics which have been proven to provide best flexibility for

all the platforms supported by DPDK.

author
#31 lore raw

Re: [PATCH v3 1/2] eal: add 128-bit cmpset (x86-64 only)

Quoted 97 lines

-----Original Message-----
From: Honnappa Nagarahalli [mailto:[email protected]]
Sent: Tuesday, January 22, 2019 2:31 PM
To: Eads, Gage <[email protected]>; [email protected]
Cc: [email protected]; [email protected]; Richardson, Bruce <[email protected]>; Ananyev, Konstantin <[email protected]>; nd <[email protected]>; [email protected]; [email protected]; [email protected]; nd <[email protected]>
Subject: RE: [dpdk-dev] [PATCH v3 1/2] eal: add 128-bit cmpset (x86-64 only)

Added other platform owners.

Quoted 67 lines
Quoted 18 lines
Quoted 18 lines
Quoted 11 lines

Review

Quoted 8 lines
(quoted diff) +0 -0
@@ -208,4 +209,25 @@ static inline void

rte_atomic64_clear(rte_atomic64_t
*v) } #endif

(quoted diff) +4 -0
+static inline int
+rte_atomic128_cmpset(volatile uint64_t *dst, uint64_t *exp,
+uint64_t
+*src) {

The API name suggests it is a 128b operation. 'dst', 'exp' and 'src' should be pointers to 128b (__int128)? Or we could define our own data

type.

I agree, I'm not a big fan of the 64b pointers here. I avoided __int128 originally because it fails to compile with -pedantic, but on second thought (and with your suggestion of a separate data type), we can resolve that with this typedef:

Quoted 8 lines
Quoted 3 lines
typedef struct {
        RTE_STD_C11 __int128 val;
} rte_int128_t;

ok

Quoted 3 lines
Quoted 3 lines

Since, it is a new API, can we define it with memory orderings which will be more conducive to relaxed memory ordering based

architectures?

Quoted 26 lines
Quoted 6 lines
Quoted 1 line

You can refer to [1] and [2] for guidance.

I certainly see the value in controlling the operation's memory ordering, like in the __atomic intrinsics, but I'm not sure this patchset is the right place to address that. I see that work going a couple

ways:

Quoted 7 lines

1. Expand the existing rte_atomicN_* interfaces with additional arguments. In that case, I'd prefer this be done in a separate patchset that addresses all the atomic operations, not just cmpset, so the interface changes are chosen according to the needs of the full set of atomic operations. If this approach is taken then there's no need to solve this while rte_atomic128_cmpset is experimental, since all the

other functions are non-experimental anyway.

Quoted 9 lines

- Or -

2. Don't modify the existing rte_atomicN_* interfaces (or their strongly ordered behavior), and instead create new versions of them that take additional arguments. In this case, we can implement
rte_atomic128_cmpset() as is and create a more flexible version in a later

patchset.

Quoted 1 line
Quoted 8 lines
Quoted 3 lines

Either way, I think the current interface (w.r.t. memory ordering options) can work and still leaves us in a good position for future

changes/improvements.

Quoted 1 line

I do not see the need to modify/extend the existing rte_atomicN_* APIs as the corresponding __atomic intrinsics serve as replacements. I expect that at some point, DPDK code base will not be using

rte_atomicN_* APIs.

Quoted 2 lines

However, __atomic intrinsics do not support 128b wide parameters. Hence

I don't think that's correct. From the GCC docs:

Quoted 7 lines

"16-byte integral types are also allowed if `__int128' (see __int128) is supported by the architecture."

This works with x86 -64 -- I assume aarch64 also, but haven't confirmed.

Source: https://gcc.gnu.org/onlinedocs/gcc-4.7.0/gcc/_005f_005fatomic-
Builtins.html

(following is based on my reading, not based on experiments) My understanding is that the __atomic_load_n/store_n were implemented using a compare-and- swap HW instruction (due to lack of HW 128b atomic load and store instructions). This introduced the side effect or store/load respectively. Where as the user does not expect such side effects. As suggested in [1], it looks like GCC delegated the implementation to libatomic which 'it seems' uses locks to implement 128b __atomic intrinsics (needs to be verified)

Quoted 5 lines

If __atomic intrinsics, for any of the supported platforms, do not have an optimal implementation, I prefer to add a DPDK API as an abstraction. A given platform can choose to implement such an API using __atomic intrinsics if it wants. The DPDK API can be similar to __atomic_compare_exchange_n.

Certainly. From the linked discussions, I see how this would affect the design of (hypothetical functions) rte_atomic128_read() and rte_atomic128_set(), but I don't see anything that suggests (for the architectures being discussed) that __atomic_compare_exchange_n is suboptimal.

Quoted 9 lines

[1] https://patchwork.ozlabs.org/patch/721686/
[2] https://gcc.gnu.org/ml/gcc/2017-01/msg00167.html

Quoted 6 lines
Quoted 5 lines

DPDK needs to write its own. Since this is the first API in that regard, I prefer that we start with a signature that resembles __atomic intrinsics which have been proven to provide best flexibility for

all the platforms supported by DPDK.

#32 lore raw

Re: [PATCH v3 1/2] eal: add 128-bit cmpset (x86-64 only)

Quoted 91 lines
Quoted 87 lines

Added other platform owners.

Quoted 67 lines
Quoted 13 lines
Quoted 13 lines
Quoted 11 lines

Review

Quoted 8 lines
(quoted diff) +0 -0
@@ -208,4 +209,25 @@ static inline void

rte_atomic64_clear(rte_atomic64_t
*v) } #endif

(quoted diff) +4 -0
+static inline int
+rte_atomic128_cmpset(volatile uint64_t *dst, uint64_t *exp,
+uint64_t
+*src) {

The API name suggests it is a 128b operation. 'dst', 'exp' and 'src' should be pointers to 128b (__int128)? Or we could define our own data

type.

Quoted 12 lines
Quoted 7 lines

I agree, I'm not a big fan of the 64b pointers here. I avoided __int128 originally because it fails to compile with -pedantic, but on second thought (and with your suggestion of a separate data type), we can resolve that with this typedef:

typedef struct {
        RTE_STD_C11 __int128 val; } rte_int128_t;

ok

Quoted 3 lines
Quoted 3 lines

Since, it is a new API, can we define it with memory orderings which will be more conducive to relaxed memory ordering based

architectures?

Quoted 30 lines
Quoted 6 lines
Quoted 1 line

You can refer to [1] and [2] for guidance.

I certainly see the value in controlling the operation's memory ordering, like in the __atomic intrinsics, but I'm not sure this patchset is the right place to address that. I see that work going a couple

ways:

Quoted 7 lines

1. Expand the existing rte_atomicN_* interfaces with additional arguments. In that case, I'd prefer this be done in a separate patchset that addresses all the atomic operations, not just cmpset, so the interface changes are chosen according to the needs of the full set of atomic operations. If this approach is taken then there's no need to solve this while rte_atomic128_cmpset is experimental, since all the

other functions are non-experimental anyway.

Quoted 9 lines

- Or -

2. Don't modify the existing rte_atomicN_* interfaces (or their strongly ordered behavior), and instead create new versions of them that take additional arguments. In this case, we can implement
rte_atomic128_cmpset() as is and create a more flexible version in a later

patchset.

Quoted 5 lines

Either way, I think the current interface (w.r.t. memory ordering
options) can work and still leaves us in a good position for future

Quoted 5 lines

changes/improvements.

Quoted 1 line

I do not see the need to modify/extend the existing rte_atomicN_* APIs as the corresponding __atomic intrinsics serve as replacements. I expect that at some point, DPDK code base will not be using

rte_atomicN_* APIs.

Quoted 2 lines

However, __atomic intrinsics do not support 128b wide parameters. Hence

I don't think that's correct. From the GCC docs:

Quoted 8 lines

"16-byte integral types are also allowed if `__int128' (see __int128) is supported by the architecture."

This works with x86 -64 -- I assume aarch64 also, but haven't confirmed.

Source:
https://gcc.gnu.org/onlinedocs/gcc-4.7.0/gcc/_005f_005fatomic-
Builtins.html

(following is based on my reading, not based on experiments) My understanding is that the __atomic_load_n/store_n were implemented using a compare-and- swap HW instruction (due to lack of HW 128b atomic load and store instructions). This introduced the side effect or store/load respectively. Where as the user does not expect such side effects. As suggested in [1], it looks like GCC delegated the implementation to libatomic which 'it seems' uses locks to implement 128b __atomic intrinsics (needs to be verified)

Quoted 4 lines

If __atomic intrinsics, for any of the supported platforms, do not have an optimal implementation, I prefer to add a DPDK API as an abstraction. A given platform can choose to implement such an API using __atomic intrinsics if it wants. The DPDK API can be similar to

Quoted 7 lines

__atomic_compare_exchange_n.

Quoted 1 line

Certainly. From the linked discussions, I see how this would affect the design of (hypothetical functions) rte_atomic128_read() and rte_atomic128_set(), but I don't see anything that suggests (for the architectures being discussed) that __atomic_compare_exchange_n is suboptimal.

I wrote some code and generated assembly to verify what is happening. On aarch64, this call is delegated to libatomic and libatomic needs to be linked. In the generated assembly, it is clear that it uses locks (pthread mutex lock) to provide atomicity for. For 32b and 64b the compiler generates the expected inline assembly. Both, ' __atomic_always_lock_free' and ' __atomic_is_lock_free' return 0 to indicate that 128b __atomic intrinsics are not lock free. (gcc - 8.2)

Out of curiosity, I also did similar experiments on x86 (CPU E5-2660 v4). Even after using -mcx16 flag the call is delegated to libatomic. I see the 'lock cmpxchg16b' in the generated assembly. But, ' __atomic_always_lock_free' and ' __atomic_is_lock_free' return 0 to indicate that 128b __atomic intrinsics are NOT lock free with gcc version 7.3.0. However with gcc version 5.4.0, ' __atomic_is_lock_free' returns 1. I found more discussion at [3]. However, I am not an expert on x86.

[3] https://gcc.gnu.org/bugzilla/show_bug.cgi?id=80878

These problems do not exist with 32b and 64b.

Quoted 10 lines
Quoted 10 lines

[1] https://patchwork.ozlabs.org/patch/721686/
[2] https://gcc.gnu.org/ml/gcc/2017-01/msg00167.html

Quoted 6 lines
Quoted 5 lines

DPDK needs to write its own. Since this is the first API in that regard, I prefer that we start with a signature that resembles __atomic intrinsics which have been proven to provide best flexibility for

all the platforms supported by DPDK.

author
#33 lore raw

Re: [PATCH v3 1/2] eal: add 128-bit cmpset (x86-64 only)

Quoted 131 lines

-----Original Message-----
From: Honnappa Nagarahalli [mailto:[email protected]]
Sent: Wednesday, January 23, 2019 11:22 PM
To: Eads, Gage <[email protected]>; [email protected]
Cc: [email protected]; [email protected]; Richardson, Bruce <[email protected]>; Ananyev, Konstantin <[email protected]>; nd <[email protected]>; [email protected]; [email protected]; [email protected]; nd <[email protected]>
Subject: RE: [dpdk-dev] [PATCH v3 1/2] eal: add 128-bit cmpset (x86-64 only)

Quoted 56 lines
Quoted 56 lines

Added other platform owners.

Quoted 53 lines
Quoted 13 lines
Quoted 13 lines
Quoted 11 lines

Review

Quoted 8 lines
(quoted diff) +0 -0
@@ -208,4 +209,25 @@ static inline void

rte_atomic64_clear(rte_atomic64_t
*v) } #endif

(quoted diff) +4 -0
+static inline int
+rte_atomic128_cmpset(volatile uint64_t *dst, uint64_t
+*exp, uint64_t
+*src) {

The API name suggests it is a 128b operation. 'dst', 'exp' and 'src' should be pointers to 128b (__int128)? Or we could define our own data

type.

Quoted 13 lines
Quoted 7 lines

I agree, I'm not a big fan of the 64b pointers here. I avoided __int128 originally because it fails to compile with -pedantic, but on second thought (and with your suggestion of a separate data type), we can resolve that with this typedef:

typedef struct {
        RTE_STD_C11 __int128 val; } rte_int128_t;

ok

Quoted 4 lines
Quoted 4 lines

Since, it is a new API, can we define it with memory orderings which will be more conducive to relaxed memory ordering based

architectures?

Quoted 26 lines
Quoted 6 lines
Quoted 1 line

You can refer to [1] and [2] for guidance.

I certainly see the value in controlling the operation's memory ordering, like in the __atomic intrinsics, but I'm not sure this patchset is the right place to address that. I see that work going a couple

ways:

Quoted 7 lines

1. Expand the existing rte_atomicN_* interfaces with additional arguments. In that case, I'd prefer this be done in a separate patchset that addresses all the atomic operations, not just cmpset, so the interface changes are chosen according to the needs of the full set of atomic operations. If this approach is taken then there's no need to solve this while rte_atomic128_cmpset is experimental, since all the

other functions are non-experimental anyway.

Quoted 9 lines

- Or -

2. Don't modify the existing rte_atomicN_* interfaces (or their strongly ordered behavior), and instead create new versions of them that take additional arguments. In this case, we can implement
rte_atomic128_cmpset() as is and create a more flexible version in a later

patchset.

Quoted 1 line
Quoted 8 lines
Quoted 8 lines
Quoted 8 lines
Quoted 8 lines
Quoted 4 lines

Either way, I think the current interface (w.r.t. memory ordering
options) can work and still leaves us in a good position for future

changes/improvements.

Quoted 1 line

I do not see the need to modify/extend the existing rte_atomicN_* APIs as the corresponding __atomic intrinsics serve as

replacements.

Quoted 29 lines
Quoted 24 lines
Quoted 7 lines
Quoted 1 line

I expect that at some point, DPDK code base will not be using

rte_atomicN_* APIs.

Quoted 2 lines

However, __atomic intrinsics do not support 128b wide parameters. Hence

I don't think that's correct. From the GCC docs:

Quoted 8 lines

"16-byte integral types are also allowed if `__int128' (see __int128) is supported by the architecture."

This works with x86 -64 -- I assume aarch64 also, but haven't confirmed.

Source:
https://gcc.gnu.org/onlinedocs/gcc-4.7.0/gcc/_005f_005fatomic-
Builtins.html

(following is based on my reading, not based on experiments) My understanding is that the __atomic_load_n/store_n were implemented using a compare-and- swap HW instruction (due to lack of HW 128b atomic load and store instructions). This introduced the side effect or store/load respectively. Where as the user does not expect such side effects. As suggested in [1], it looks like GCC delegated the implementation to libatomic which 'it seems' uses locks to implement 128b __atomic intrinsics (needs to be verified)

Quoted 5 lines

If __atomic intrinsics, for any of the supported platforms, do not have an optimal implementation, I prefer to add a DPDK API as an abstraction. A given platform can choose to implement such an API using __atomic intrinsics if it wants. The DPDK API can be similar to

Quoted 7 lines

__atomic_compare_exchange_n.

Quoted 1 line

Certainly. From the linked discussions, I see how this would affect the design of (hypothetical functions) rte_atomic128_read() and rte_atomic128_set(), but I don't see anything that suggests (for the architectures being discussed) that __atomic_compare_exchange_n is

suboptimal.
I wrote some code and generated assembly to verify what is happening. On aarch64, this call is delegated to libatomic and libatomic needs to be linked. In the generated assembly, it is clear that it uses locks (pthread mutex lock) to provide atomicity for. For 32b and 64b the compiler generates the expected inline assembly. Both, ' __atomic_always_lock_free' and ' __atomic_is_lock_free' return 0 to indicate that 128b __atomic intrinsics are not lock free. (gcc - 8.2)

Out of curiosity, I also did similar experiments on x86 (CPU E5-2660 v4). Even after using -mcx16 flag the call is delegated to libatomic. I see the 'lock cmpxchg16b' in the generated assembly. But, ' __atomic_always_lock_free' and ' __atomic_is_lock_free' return 0 to indicate that 128b __atomic intrinsics are NOT lock free with gcc version 7.3.0. However with gcc version 5.4.0, ' __atomic_is_lock_free' returns 1. I found more discussion at [3]. However, I am not an expert on x86.

Quoted 4 lines

[3] https://gcc.gnu.org/bugzilla/show_bug.cgi?id=80878

These problems do not exist with 32b and 64b.

Thanks for investigating this. If GCC doesn't compile optimal code for aarch64 (i.e. LDXP+STXP or CASP) I don't think we have a choice but to use our own implementation for 128-bit atomics, and it makes sense to model the interface after the __atomic instrinsics as you suggested.

Quoted 10 lines
Quoted 10 lines
Quoted 10 lines

[1] https://patchwork.ozlabs.org/patch/721686/
[2] https://gcc.gnu.org/ml/gcc/2017-01/msg00167.html

Quoted 6 lines
Quoted 5 lines

DPDK needs to write its own. Since this is the first API in that regard, I prefer that we start with a signature that resembles __atomic intrinsics which have been proven to provide best flexibility for

all the platforms supported by DPDK.

author
#34 lore raw

PATCH v3 2/2 mempool/nb_stack: add non-blocking stack mempool

In reply to Gage Eads

This commit adds support for non-blocking (linked list based) stack mempool handler. The stack uses a 128-bit compare-and-swap instruction, and thus is limited to x86_64. The 128-bit CAS atomically updates the stack top pointer and a modification counter, which protects against the ABA problem.

In mempool_perf_autotest the lock-based stack outperforms the non-blocking handler*, however:
- For applications with preemptible pthreads, a lock-based stack's worst-case performance (i.e. one thread being preempted while holding the spinlock) is much worse than the non-blocking 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 1x-3.5x the non-blocking stack's.

---
 MAINTAINERS                                        |   4 +
 config/common_base                                 |   1 +
 doc/guides/prog_guide/env_abstraction_layer.rst    |   5 +
 drivers/mempool/Makefile                           |   3 +
 drivers/mempool/meson.build                        |   3 +-
 drivers/mempool/nb_stack/Makefile                  |  23 ++++
 drivers/mempool/nb_stack/meson.build               |   8 ++
 drivers/mempool/nb_stack/nb_lifo.h                 | 147 +++++++++++++++++++++
 drivers/mempool/nb_stack/rte_mempool_nb_stack.c    | 125 ++++++++++++++++++
 .../nb_stack/rte_mempool_nb_stack_version.map      |   4 +
 mk/rte.app.mk                                      |   7 +-
 11 files changed, 327 insertions(+), 3 deletions(-)
 create mode 100644 drivers/mempool/nb_stack/Makefile
 create mode 100644 drivers/mempool/nb_stack/meson.build
 create mode 100644 drivers/mempool/nb_stack/nb_lifo.h
 create mode 100644 drivers/mempool/nb_stack/rte_mempool_nb_stack.c
 create mode 100644 drivers/mempool/nb_stack/rte_mempool_nb_stack_version.map
MAINTAINERS +4 -0
index 470f36b9c..5519d3323 100644
@@ -416,6 +416,10 @@ M: Artem V. Andreev <[email protected]>
 M: Andrew Rybchenko <[email protected]>
 F: drivers/mempool/bucket/
 
+Non-blocking stack memory pool
+M: Gage Eads <[email protected]>
+F: drivers/mempool/nb_stack/
+
 
 Bus Drivers
 -----------
config/common_base +1 -0
index 964a6956e..8a51f36b1 100644
@@ -726,6 +726,7 @@ CONFIG_RTE_LIBRTE_MEMPOOL_DEBUG=n
 #
 CONFIG_RTE_DRIVER_MEMPOOL_BUCKET=y
 CONFIG_RTE_DRIVER_MEMPOOL_BUCKET_SIZE_KB=64
+CONFIG_RTE_DRIVER_MEMPOOL_NB_STACK=y
 CONFIG_RTE_DRIVER_MEMPOOL_RING=y
 CONFIG_RTE_DRIVER_MEMPOOL_STACK=y
 
doc/guides/prog_guide/env_abstraction_layer.rst +5 -0
index 929d76dba..9497b879c 100644
@@ -541,6 +541,11 @@ Known Issues
 
   5. It MUST not be used by multi-producer/consumer pthreads, whose scheduling policies are SCHED_FIFO or SCHED_RR.
 
+  Alternatively, x86_64 applications can use the non-blocking stack mempool handler. When considering this handler, note that:
+
+  - it is limited to the x86_64 platform, because it uses an instruction (16-byte compare-and-swap) that is not 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 handler operations.
+
 + 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.
drivers/mempool/Makefile +3 -0
index 28c2e8360..895cf8a34 100644
@@ -10,6 +10,9 @@ endif
 ifeq ($(CONFIG_RTE_EAL_VFIO)$(CONFIG_RTE_LIBRTE_FSLMC_BUS),yy)
 DIRS-$(CONFIG_RTE_LIBRTE_DPAA2_MEMPOOL) += dpaa2
 endif
+ifeq ($(CONFIG_RTE_ARCH_X86_64),y)
+DIRS-$(CONFIG_RTE_DRIVER_MEMPOOL_NB_STACK) += nb_stack
+endif
 DIRS-$(CONFIG_RTE_DRIVER_MEMPOOL_RING) += ring
 DIRS-$(CONFIG_RTE_DRIVER_MEMPOOL_STACK) += stack
 DIRS-$(CONFIG_RTE_LIBRTE_OCTEONTX_MEMPOOL) += octeontx
drivers/mempool/meson.build +2 -1
index 4527d9806..220cfaf63 100644
@@ -1,7 +1,8 @@
 # SPDX-License-Identifier: BSD-3-Clause
 # Copyright(c) 2017 Intel Corporation
 
-drivers = ['bucket', 'dpaa', 'dpaa2', 'octeontx', 'ring', 'stack']
+drivers = ['bucket', 'dpaa', 'dpaa2', 'nb_stack', 'octeontx', 'ring', 'stack']
+
 std_deps = ['mempool']
 config_flag_fmt = 'RTE_LIBRTE_@0@_MEMPOOL'
 driver_name_fmt = 'rte_mempool_@0@'
drivers/mempool/nb_stack/Makefile new file +23 -0
new file mode 100644
index 000000000..318b18283
@@ -0,0 +1,23 @@
+# SPDX-License-Identifier: BSD-3-Clause
+# Copyright(c) 2019 Intel Corporation
+
+include $(RTE_SDK)/mk/rte.vars.mk
+
+#
+# library name
+#
+LIB = librte_mempool_nb_stack.a
+
+CFLAGS += -O3
+CFLAGS += $(WERROR_FLAGS)
+
+# Headers
+LDLIBS += -lrte_eal -lrte_mempool
+
+EXPORT_MAP := rte_mempool_nb_stack_version.map
+
+LIBABIVER := 1
+
+SRCS-$(CONFIG_RTE_DRIVER_MEMPOOL_NB_STACK) += rte_mempool_nb_stack.c
+
+include $(RTE_SDK)/mk/rte.lib.mk
drivers/mempool/nb_stack/meson.build new file +8 -0
new file mode 100644
index 000000000..4a699511d
@@ -0,0 +1,8 @@
+# SPDX-License-Identifier: BSD-3-Clause
+# Copyright(c) 2019 Intel Corporation
+
+if arch_subdir != 'x86' or cc.sizeof('void *') == 4
+	build = false
+endif
+
+sources = files('rte_mempool_nb_stack.c')
drivers/mempool/nb_stack/nb_lifo.h new file +147 -0

147 lines not on this page · raw message

drivers/mempool/nb_stack/rte_mempool_nb_stack.c new file +125 -0

125 lines not on this page · raw message

drivers/mempool/nb_stack/rte_mempool_nb_stack_version.map new file +4 -0
new file mode 100644
index 000000000..fc8c95e91
@@ -0,0 +1,4 @@
+DPDK_19.05 {
+
+	local: *;
+};
mk/rte.app.mk +5 -2
index 02e8b6f05..d4b4aaaf6 100644
@@ -131,8 +131,11 @@ endif
 ifeq ($(CONFIG_RTE_BUILD_SHARED_LIB),n)
 # plugins (link only if static libraries)
 
-_LDLIBS-$(CONFIG_RTE_DRIVER_MEMPOOL_BUCKET) += -lrte_mempool_bucket
-_LDLIBS-$(CONFIG_RTE_DRIVER_MEMPOOL_STACK)  += -lrte_mempool_stack
+_LDLIBS-$(CONFIG_RTE_DRIVER_MEMPOOL_BUCKET)   += -lrte_mempool_bucket
+ifeq ($(CONFIG_RTE_ARCH_X86_64),y)
+_LDLIBS-$(CONFIG_RTE_DRIVER_MEMPOOL_NB_STACK) += -lrte_mempool_nb_stack
+endif
+_LDLIBS-$(CONFIG_RTE_DRIVER_MEMPOOL_STACK)    += -lrte_mempool_stack
 ifeq ($(CONFIG_RTE_LIBRTE_DPAA_BUS),y)
 _LDLIBS-$(CONFIG_RTE_LIBRTE_DPAA_MEMPOOL)   += -lrte_mempool_dpaa
 endif
Signature · 1 line
2.13.6
author
#35 lore raw

v4 cover Add non-blocking stack mempool handler

In reply to Gage Eads

For some users, 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.

This patchset introduces a non-blocking stack mempool handler. Note that the non-blocking algorithm relies on a 128-bit compare-and-swap, so it is limited to x86_64 machines.

In mempool_perf_autotest the lock-based stack outperforms the non-blocking handler*, however:
- For applications with preemptible pthreads, a lock-based stack's worst-case performance (i.e. one thread being preempted while holding the spinlock) is much worse than the non-blocking 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 1x-3.5x the non-blocking stack's.

v4:
- Simplified the meson.build x86_64 check

v3:
- Fix two more space-after-typecast issues
- Rework nb_stack's meson.build x86_64 check, borrowing from net/sfc/

v2:
- Merge separate docs commit into patch #2
- Fix two space-after-typecast issues
- Fix alphabetical sorting for build files
- Remove unnecessary include path from nb_stack/Makefile
- Add a comment to nb_lifo_len() justifying its approximate behavior
- Fix comparison with NULL
- Remove unnecessary void * cast
- Fix meson builds and limit them to x86_64
- Fix missing library error for non-x86_64 builds

Gage Eads (2):
eal: add 128-bit cmpset (x86-64 only) mempool/nb_stack: add non-blocking stack mempool

 MAINTAINERS                                        |   4 +
 config/common_base                                 |   1 +
 doc/guides/prog_guide/env_abstraction_layer.rst    |   5 +
 drivers/mempool/Makefile                           |   3 +
 drivers/mempool/meson.build                        |   3 +-
 drivers/mempool/nb_stack/Makefile                  |  23 ++++
 drivers/mempool/nb_stack/meson.build               |   6 +
 drivers/mempool/nb_stack/nb_lifo.h                 | 147 +++++++++++++++++++++
 drivers/mempool/nb_stack/rte_mempool_nb_stack.c    | 125 ++++++++++++++++++
 .../nb_stack/rte_mempool_nb_stack_version.map      |   4 +
 .../common/include/arch/x86/rte_atomic_64.h        |  22 +++
 mk/rte.app.mk                                      |   7 +-
 12 files changed, 347 insertions(+), 3 deletions(-)
 create mode 100644 drivers/mempool/nb_stack/Makefile
 create mode 100644 drivers/mempool/nb_stack/meson.build
 create mode 100644 drivers/mempool/nb_stack/nb_lifo.h
 create mode 100644 drivers/mempool/nb_stack/rte_mempool_nb_stack.c
 create mode 100644 drivers/mempool/nb_stack/rte_mempool_nb_stack_version.map
Signature · 1 line
2.13.6
author
#36 lore raw

PATCH v4 1/2 eal: add 128-bit cmpset (x86-64 only)

This operation can be used for non-blocking algorithms, such as a non-blocking stack or ring.

---
 .../common/include/arch/x86/rte_atomic_64.h        | 22 ++++++++++++++++++++++
 1 file changed, 22 insertions(+)
lib/librte_eal/common/include/arch/x86/rte_atomic_64.h +22 -0
index fd2ec9c53..34c2addf8 100644
@@ -34,6 +34,7 @@
 /*
  * Inspired from FreeBSD src/sys/amd64/include/atomic.h
  * Copyright (c) 1998 Doug Rabson
+ * Copyright (c) 2019 Intel Corporation
  * All rights reserved.
  */
 
@@ -208,4 +209,25 @@ static inline void rte_atomic64_clear(rte_atomic64_t *v)
 }
 #endif
 
+static inline int
+rte_atomic128_cmpset(volatile uint64_t *dst, uint64_t *exp, uint64_t *src)
+{
+	uint8_t res;
+
+	asm volatile (
+		      MPLOCKED
+		      "cmpxchg16b %[dst];"
+		      " sete %[res]"
+		      : [dst] "=m" (*dst),
+			[res] "=r" (res)
+		      : "c" (src[1]),
+			"b" (src[0]),
+			"m" (*dst),
+			"d" (exp[1]),
+			"a" (exp[0])
+		      : "memory");
+
+	return res;
+}
+
 #endif /* _RTE_ATOMIC_X86_64_H_ */
Signature · 1 line
2.13.6
author
#37 lore raw

PATCH v4 2/2 mempool/nb_stack: add non-blocking stack mempool

In reply to Gage Eads

This commit adds support for non-blocking (linked list based) stack mempool handler. The stack uses a 128-bit compare-and-swap instruction, and thus is limited to x86_64. The 128-bit CAS atomically updates the stack top pointer and a modification counter, which protects against the ABA problem.

In mempool_perf_autotest the lock-based stack outperforms the non-blocking handler*, however:
- For applications with preemptible pthreads, a lock-based stack's worst-case performance (i.e. one thread being preempted while holding the spinlock) is much worse than the non-blocking 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 1x-3.5x the non-blocking stack's.

---
 MAINTAINERS                                        |   4 +
 config/common_base                                 |   1 +
 doc/guides/prog_guide/env_abstraction_layer.rst    |   5 +
 drivers/mempool/Makefile                           |   3 +
 drivers/mempool/meson.build                        |   3 +-
 drivers/mempool/nb_stack/Makefile                  |  23 ++++
 drivers/mempool/nb_stack/meson.build               |   6 +
 drivers/mempool/nb_stack/nb_lifo.h                 | 147 +++++++++++++++++++++
 drivers/mempool/nb_stack/rte_mempool_nb_stack.c    | 125 ++++++++++++++++++
 .../nb_stack/rte_mempool_nb_stack_version.map      |   4 +
 mk/rte.app.mk                                      |   7 +-
 11 files changed, 325 insertions(+), 3 deletions(-)
 create mode 100644 drivers/mempool/nb_stack/Makefile
 create mode 100644 drivers/mempool/nb_stack/meson.build
 create mode 100644 drivers/mempool/nb_stack/nb_lifo.h
 create mode 100644 drivers/mempool/nb_stack/rte_mempool_nb_stack.c
 create mode 100644 drivers/mempool/nb_stack/rte_mempool_nb_stack_version.map
MAINTAINERS +4 -0
index 470f36b9c..5519d3323 100644
@@ -416,6 +416,10 @@ M: Artem V. Andreev <[email protected]>
 M: Andrew Rybchenko <[email protected]>
 F: drivers/mempool/bucket/
 
+Non-blocking stack memory pool
+M: Gage Eads <[email protected]>
+F: drivers/mempool/nb_stack/
+
 
 Bus Drivers
 -----------
config/common_base +1 -0
index 964a6956e..8a51f36b1 100644
@@ -726,6 +726,7 @@ CONFIG_RTE_LIBRTE_MEMPOOL_DEBUG=n
 #
 CONFIG_RTE_DRIVER_MEMPOOL_BUCKET=y
 CONFIG_RTE_DRIVER_MEMPOOL_BUCKET_SIZE_KB=64
+CONFIG_RTE_DRIVER_MEMPOOL_NB_STACK=y
 CONFIG_RTE_DRIVER_MEMPOOL_RING=y
 CONFIG_RTE_DRIVER_MEMPOOL_STACK=y
 
doc/guides/prog_guide/env_abstraction_layer.rst +5 -0
index 929d76dba..9497b879c 100644
@@ -541,6 +541,11 @@ Known Issues
 
   5. It MUST not be used by multi-producer/consumer pthreads, whose scheduling policies are SCHED_FIFO or SCHED_RR.
 
+  Alternatively, x86_64 applications can use the non-blocking stack mempool handler. When considering this handler, note that:
+
+  - it is limited to the x86_64 platform, because it uses an instruction (16-byte compare-and-swap) that is not 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 handler operations.
+
 + 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.
drivers/mempool/Makefile +3 -0
index 28c2e8360..895cf8a34 100644
@@ -10,6 +10,9 @@ endif
 ifeq ($(CONFIG_RTE_EAL_VFIO)$(CONFIG_RTE_LIBRTE_FSLMC_BUS),yy)
 DIRS-$(CONFIG_RTE_LIBRTE_DPAA2_MEMPOOL) += dpaa2
 endif
+ifeq ($(CONFIG_RTE_ARCH_X86_64),y)
+DIRS-$(CONFIG_RTE_DRIVER_MEMPOOL_NB_STACK) += nb_stack
+endif
 DIRS-$(CONFIG_RTE_DRIVER_MEMPOOL_RING) += ring
 DIRS-$(CONFIG_RTE_DRIVER_MEMPOOL_STACK) += stack
 DIRS-$(CONFIG_RTE_LIBRTE_OCTEONTX_MEMPOOL) += octeontx
drivers/mempool/meson.build +2 -1
index 4527d9806..220cfaf63 100644
@@ -1,7 +1,8 @@
 # SPDX-License-Identifier: BSD-3-Clause
 # Copyright(c) 2017 Intel Corporation
 
-drivers = ['bucket', 'dpaa', 'dpaa2', 'octeontx', 'ring', 'stack']
+drivers = ['bucket', 'dpaa', 'dpaa2', 'nb_stack', 'octeontx', 'ring', 'stack']
+
 std_deps = ['mempool']
 config_flag_fmt = 'RTE_LIBRTE_@0@_MEMPOOL'
 driver_name_fmt = 'rte_mempool_@0@'
drivers/mempool/nb_stack/Makefile new file +23 -0
new file mode 100644
index 000000000..318b18283
@@ -0,0 +1,23 @@
+# SPDX-License-Identifier: BSD-3-Clause
+# Copyright(c) 2019 Intel Corporation
+
+include $(RTE_SDK)/mk/rte.vars.mk
+
+#
+# library name
+#
+LIB = librte_mempool_nb_stack.a
+
+CFLAGS += -O3
+CFLAGS += $(WERROR_FLAGS)
+
+# Headers
+LDLIBS += -lrte_eal -lrte_mempool
+
+EXPORT_MAP := rte_mempool_nb_stack_version.map
+
+LIBABIVER := 1
+
+SRCS-$(CONFIG_RTE_DRIVER_MEMPOOL_NB_STACK) += rte_mempool_nb_stack.c
+
+include $(RTE_SDK)/mk/rte.lib.mk
drivers/mempool/nb_stack/meson.build new file +6 -0
new file mode 100644
index 000000000..7dec72242
@@ -0,0 +1,6 @@
+# SPDX-License-Identifier: BSD-3-Clause
+# Copyright(c) 2019 Intel Corporation
+
+build = dpdk_conf.has('RTE_ARCH_X86_64')
+
+sources = files('rte_mempool_nb_stack.c')
drivers/mempool/nb_stack/nb_lifo.h new file +147 -0

147 lines not on this page · raw message

drivers/mempool/nb_stack/rte_mempool_nb_stack.c new file +125 -0

125 lines not on this page · raw message

drivers/mempool/nb_stack/rte_mempool_nb_stack_version.map new file +4 -0
new file mode 100644
index 000000000..fc8c95e91
@@ -0,0 +1,4 @@
+DPDK_19.05 {
+
+	local: *;
+};
mk/rte.app.mk +5 -2
index 02e8b6f05..d4b4aaaf6 100644
@@ -131,8 +131,11 @@ endif
 ifeq ($(CONFIG_RTE_BUILD_SHARED_LIB),n)
 # plugins (link only if static libraries)
 
-_LDLIBS-$(CONFIG_RTE_DRIVER_MEMPOOL_BUCKET) += -lrte_mempool_bucket
-_LDLIBS-$(CONFIG_RTE_DRIVER_MEMPOOL_STACK)  += -lrte_mempool_stack
+_LDLIBS-$(CONFIG_RTE_DRIVER_MEMPOOL_BUCKET)   += -lrte_mempool_bucket
+ifeq ($(CONFIG_RTE_ARCH_X86_64),y)
+_LDLIBS-$(CONFIG_RTE_DRIVER_MEMPOOL_NB_STACK) += -lrte_mempool_nb_stack
+endif
+_LDLIBS-$(CONFIG_RTE_DRIVER_MEMPOOL_STACK)    += -lrte_mempool_stack
 ifeq ($(CONFIG_RTE_LIBRTE_DPAA_BUS),y)
 _LDLIBS-$(CONFIG_RTE_LIBRTE_DPAA_MEMPOOL)   += -lrte_mempool_dpaa
 endif
Signature · 1 line
2.13.6
#38 lore raw

Re: [PATCH v4 2/2] mempool/nb_stack: add non-blocking stack mempool

Hi Gage,
Thank you for your contribution on non-blocking data structures. I think they are important to extend DPDK into additional use cases.

I am wondering if it makes sense to decouple the NB stack data structure from mempool driver (similar to rte_ring)? I see that stack based mempool implements the stack data structure in the driver. But, NB stack might not be such a trivial data structure. It might be useful for the applications or other use cases as well.

I also suggest that we use C11 __atomic_xxx APIs for memory operations. The rte_atomic64_xxx APIs use __sync_xxx APIs which do not provide the capability to express memory orderings.

Please find few comments inline.

Quoted 83 lines

This commit adds support for non-blocking (linked list based) stack mempool handler. The stack uses a 128-bit compare-and-swap instruction, and thus is limited to x86_64. The 128-bit CAS atomically updates the stack top pointer and a modification counter, which protects against the ABA problem.

In mempool_perf_autotest the lock-based stack outperforms the non- blocking handler*, however:
- For applications with preemptible pthreads, a lock-based stack's worst-case performance (i.e. one thread being preempted while holding the spinlock) is much worse than the non-blocking 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 1x-3.5x the non-blocking stack's.

---
 MAINTAINERS                                        |   4 +
 config/common_base                                 |   1 +
 doc/guides/prog_guide/env_abstraction_layer.rst    |   5 +
 drivers/mempool/Makefile                           |   3 +
 drivers/mempool/meson.build                        |   3 +-
 drivers/mempool/nb_stack/Makefile                  |  23 ++++
 drivers/mempool/nb_stack/meson.build               |   6 +
 drivers/mempool/nb_stack/nb_lifo.h                 | 147
+++++++++++++++++++++
 drivers/mempool/nb_stack/rte_mempool_nb_stack.c    | 125
++++++++++++++++++
 .../nb_stack/rte_mempool_nb_stack_version.map      |   4 +
 mk/rte.app.mk                                      |   7 +-
 11 files changed, 325 insertions(+), 3 deletions(-)  create mode 100644
drivers/mempool/nb_stack/Makefile  create mode 100644
drivers/mempool/nb_stack/meson.build
 create mode 100644 drivers/mempool/nb_stack/nb_lifo.h
 create mode 100644 drivers/mempool/nb_stack/rte_mempool_nb_stack.c
 create mode 100644

drivers/mempool/nb_stack/rte_mempool_nb_stack_version.map

MAINTAINERS +4 -0
index 470f36b9c..5519d3323 100644
@@ -416,6 +416,10 @@ M: Artem V. Andreev <[email protected]>
 M: Andrew Rybchenko <[email protected]>
 F: drivers/mempool/bucket/
 
+Non-blocking stack memory pool
+M: Gage Eads <[email protected]>
+F: drivers/mempool/nb_stack/
+
 
 Bus Drivers
 -----------
config/common_base index renamed from config/common_base +0 -0

964a6956e..8a51f36b1 100644

config/common_base +0 -0
@@ -726,6 +726,7 @@ CONFIG_RTE_LIBRTE_MEMPOOL_DEBUG=n  #

CONFIG_RTE_DRIVER_MEMPOOL_BUCKET=y
CONFIG_RTE_DRIVER_MEMPOOL_BUCKET_SIZE_KB=64

config/common_base +1 -0
+CONFIG_RTE_DRIVER_MEMPOOL_NB_STACK=y
 CONFIG_RTE_DRIVER_MEMPOOL_RING=y
 CONFIG_RTE_DRIVER_MEMPOOL_STACK=y
doc/guides/prog_guide/env_abstraction_layer.rst +0 -0
index 929d76dba..9497b879c 100644
@@ -541,6 +541,11 @@ Known Issues
 
   5. It MUST not be used by multi-producer/consumer pthreads, whose

scheduling policies are SCHED_FIFO or SCHED_RR.

+ Alternatively, x86_64 applications can use the non-blocking stack mempool handler. When considering this handler, note that:

doc/guides/prog_guide/env_abstraction_layer.rst +2 -0
+
+  - it is limited to the x86_64 platform, because it uses an instruction (16-
Quoted 1 line

byte compare-and-swap) that is not available on other platforms.

                                                 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

Arm architecture supports similar instructions. I suggest to simplify this statement to indicate that 'nb_stack feature is available for x86_64 platforms currently'

Quoted 91 lines

+ - 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 handler operations.
+
+ 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.

drivers/mempool/Makefile index renamed from drivers/mempool/Makefile +0 -0

28c2e8360..895cf8a34 100644

drivers/mempool/Makefile +2 -0
@@ -10,6 +10,9 @@ endif
 ifeq ($(CONFIG_RTE_EAL_VFIO)$(CONFIG_RTE_LIBRTE_FSLMC_BUS),yy)
 DIRS-$(CONFIG_RTE_LIBRTE_DPAA2_MEMPOOL) += dpaa2  endif
+ifeq ($(CONFIG_RTE_ARCH_X86_64),y)
+DIRS-$(CONFIG_RTE_DRIVER_MEMPOOL_NB_STACK) += nb_stack endif
 DIRS-$(CONFIG_RTE_DRIVER_MEMPOOL_RING) += ring
 DIRS-$(CONFIG_RTE_DRIVER_MEMPOOL_STACK) += stack
 DIRS-$(CONFIG_RTE_LIBRTE_OCTEONTX_MEMPOOL) += octeontx diff --git

a/drivers/mempool/meson.build b/drivers/mempool/meson.build index 4527d9806..220cfaf63 100644

drivers/mempool/meson.build +0 -0
@@ -1,7 +1,8 @@
 # SPDX-License-Identifier: BSD-3-Clause  # Copyright(c) 2017 Intel

Corporation

drivers/mempool/meson.build +3 -1
-drivers = ['bucket', 'dpaa', 'dpaa2', 'octeontx', 'ring', 'stack']
+drivers = ['bucket', 'dpaa', 'dpaa2', 'nb_stack', 'octeontx', 'ring',
+'stack']
+
 std_deps = ['mempool']
 config_flag_fmt = 'RTE_LIBRTE_@0@_MEMPOOL'
 driver_name_fmt = 'rte_mempool_@0@'
drivers/mempool/nb_stack/Makefile new file +21 -0
new file mode 100644
index 000000000..318b18283
@@ -0,0 +1,23 @@
+# SPDX-License-Identifier: BSD-3-Clause # Copyright(c) 2019 Intel
+Corporation
+
+include $(RTE_SDK)/mk/rte.vars.mk
+
+#
+# library name
+#
+LIB = librte_mempool_nb_stack.a
+
+CFLAGS += -O3
+CFLAGS += $(WERROR_FLAGS)
+
+# Headers
+LDLIBS += -lrte_eal -lrte_mempool
+
+EXPORT_MAP := rte_mempool_nb_stack_version.map
+
+LIBABIVER := 1
+
+SRCS-$(CONFIG_RTE_DRIVER_MEMPOOL_NB_STACK) +=

rte_mempool_nb_stack.c

drivers/mempool/nb_stack/Makefile new file +2 -0
+
+include $(RTE_SDK)/mk/rte.lib.mk
drivers/mempool/nb_stack/meson.build new file +6 -0
new file mode 100644
index 000000000..7dec72242
@@ -0,0 +1,6 @@
+# SPDX-License-Identifier: BSD-3-Clause # Copyright(c) 2019 Intel
+Corporation
+
+build = dpdk_conf.has('RTE_ARCH_X86_64')
+
+sources = files('rte_mempool_nb_stack.c')
drivers/mempool/nb_stack/nb_lifo.h new file +5 -0
new file mode 100644
index 000000000..ad4a3401f
@@ -0,0 +1,147 @@
+/* SPDX-License-Identifier: BSD-3-Clause
+ * Copyright(c) 2019 Intel Corporation
+ */
+
+#ifndef _NB_LIFO_H_

drivers/mempool/nb_stack/nb_lifo.h line 15

Quoted 10 lines
drivers/mempool/nb_stack/nb_lifo.h new file +10 -0
+#define _NB_LIFO_H_
+
+struct nb_lifo_elem {
+	void *data;
+	struct nb_lifo_elem *next;
+};
+
+struct nb_lifo_head {
+	struct nb_lifo_elem *top; /**< Stack top */
+	uint64_t cnt; /**< Modification counter */ };

Minor comment, mentioning ABA problem in the comments for 'cnt' will be helpful.

Quoted 52 lines
drivers/mempool/nb_stack/nb_lifo.h new file +16 -0
+
+struct nb_lifo {
+	volatile struct nb_lifo_head head __rte_aligned(16);
+	rte_atomic64_t len;
+} __rte_cache_aligned;
+
+static __rte_always_inline void
+nb_lifo_init(struct nb_lifo *lifo)
+{
+	memset(lifo, 0, sizeof(*lifo));
+	rte_atomic64_set(&lifo->len, 0);
+}
+
+static __rte_always_inline unsigned int nb_lifo_len(struct nb_lifo
+*lifo) {
+	/* nb_lifo_push() and nb_lifo_pop() do not update the list's

contents

drivers/mempool/nb_stack/nb_lifo.h new file +1 -0
+	 * and lifo->len atomically, which can cause the list to appear

shorter

drivers/mempool/nb_stack/nb_lifo.h new file +4 -0
+	 * than it actually is if this function is called while other threads
+	 * are modifying the list.
+	 *
+	 * However, given the inherently approximate nature of the

get_count

drivers/mempool/nb_stack/nb_lifo.h new file +2 -0
+	 * callback -- even if the list and its size were updated atomically,
+	 * the size could change between when get_count executes and

when the

drivers/mempool/nb_stack/nb_lifo.h new file +4 -0
+	 * value is returned to the caller -- this is acceptable.
+	 *
+	 * The lifo->len updates are placed such that the list may appear to
+	 * have fewer elements than it does, but will never appear to have

more

drivers/mempool/nb_stack/nb_lifo.h new file +20 -0
+	 * elements. If the mempool is near-empty to the point that this is a
+	 * concern, the user should consider increasing the mempool size.
+	 */
+	return (unsigned int)rte_atomic64_read(&lifo->len);
+}
+
+static __rte_always_inline void
+nb_lifo_push(struct nb_lifo *lifo,
+	     struct nb_lifo_elem *first,
+	     struct nb_lifo_elem *last,
+	     unsigned int num)
+{
+	while (1) {
+		struct nb_lifo_head old_head, new_head;
+
+		old_head = lifo->head;
+
+		/* Swing the top pointer to the first element in the list and
+		 * make the last element point to the old top.
+		 */

drivers/mempool/nb_stack/nb_lifo.h line 74

Quoted 10 lines
drivers/mempool/nb_stack/nb_lifo.h new file +10 -0
+		new_head.top = first;
+		new_head.cnt = old_head.cnt + 1;
+
+		last->next = old_head.top;
+
+		if (rte_atomic128_cmpset((volatile uint64_t *)&lifo->head,
+					 (uint64_t *)&old_head,
+					 (uint64_t *)&new_head))
+			break;
+	}

Minor comment, this can be a do-while loop (for ex: similar to the one in __rte_ring_move_prod_head)

Quoted 44 lines
drivers/mempool/nb_stack/nb_lifo.h new file +43 -0
+
+	rte_atomic64_add(&lifo->len, num);
+}
+
+static __rte_always_inline void
+nb_lifo_push_single(struct nb_lifo *lifo, struct nb_lifo_elem *elem) {
+	nb_lifo_push(lifo, elem, elem, 1);
+}
+
+static __rte_always_inline struct nb_lifo_elem * nb_lifo_pop(struct
+nb_lifo *lifo,
+	    unsigned int num,
+	    void **obj_table,
+	    struct nb_lifo_elem **last)
+{
+	struct nb_lifo_head old_head;
+
+	/* Reserve num elements, if available */
+	while (1) {
+		uint64_t len = rte_atomic64_read(&lifo->len);
+
+		/* Does the list contain enough elements? */
+		if (len < num)
+			return NULL;
+
+		if (rte_atomic64_cmpset((volatile uint64_t *)&lifo->len,
+					len, len - num))
+			break;
+	}
+
+	/* Pop num elements */
+	while (1) {
+		struct nb_lifo_head new_head;
+		struct nb_lifo_elem *tmp;
+		unsigned int i;
+
+		old_head = lifo->head;
+
+		tmp = old_head.top;
+
+		/* Traverse the list to find the new head. A next pointer will
+		 * either point to another element or NULL; if a thread
+		 * encounters a pointer that has already been popped, the

CAS

drivers/mempool/nb_stack/nb_lifo.h line 122

Quoted 4 lines
drivers/mempool/nb_stack/nb_lifo.h new file +4 -0
+		 * will fail.
+		 */
+		for (i = 0; i < num && tmp != NULL; i++) {
+			if (obj_table)

This 'if' check can be outside the for loop. May be use RTE_ASSERT in the beginning of the function?

Quoted 48 lines
drivers/mempool/nb_stack/nb_lifo.h new file +25 -0
+				obj_table[i] = tmp->data;
+			if (last)
+				*last = tmp;
+			tmp = tmp->next;
+		}
+
+		/* If NULL was encountered, the list was modified while
+		 * traversing it. Retry.
+		 */
+		if (i != num)
+			continue;
+
+		new_head.top = tmp;
+		new_head.cnt = old_head.cnt + 1;
+
+		if (rte_atomic128_cmpset((volatile uint64_t *)&lifo->head,
+					 (uint64_t *)&old_head,
+					 (uint64_t *)&new_head))
+			break;
+	}
+
+	return old_head.top;
+}
+
+#endif /* _NB_LIFO_H_ */
drivers/mempool/nb_stack/rte_mempool_nb_stack.c new file +14 -0
new file mode 100644
index 000000000..1818a2cfa
@@ -0,0 +1,125 @@
+/* SPDX-License-Identifier: BSD-3-Clause
+ * Copyright(c) 2019 Intel Corporation
+ */
+
+#include <stdio.h>
+#include <rte_mempool.h>
+#include <rte_malloc.h>
+
+#include "nb_lifo.h"
+
+struct rte_mempool_nb_stack {
+	uint64_t size;
+	struct nb_lifo used_lifo; /**< LIFO containing mempool pointers  */
+	struct nb_lifo free_lifo; /**< LIFO containing unused LIFO elements

*/

drivers/mempool/nb_stack/rte_mempool_nb_stack.c new file +1 -0
+};

drivers/mempool/nb_stack/rte_mempool_nb_stack.c line 25

Quoted 10 lines
drivers/mempool/nb_stack/rte_mempool_nb_stack.c new file +10 -0
+
+static int
+nb_stack_alloc(struct rte_mempool *mp)
+{
+	struct rte_mempool_nb_stack *s;
+	struct nb_lifo_elem *elems;
+	unsigned int n = mp->size;
+	unsigned int size, i;
+
+	size = sizeof(*s) + n * sizeof(struct nb_lifo_elem);

IMO, the allocation of the stack elements can be moved under nb_lifo_init API, it would make the nb stack code modular.

Quoted 9 lines
drivers/mempool/nb_stack/rte_mempool_nb_stack.c new file +9 -0
+
+	/* Allocate our local memory structure */
+	s = rte_zmalloc_socket("mempool-nb_stack",
+			       size,
+			       RTE_CACHE_LINE_SIZE,
+			       mp->socket_id);
+	if (s == NULL) {
+		RTE_LOG(ERR, MEMPOOL, "Cannot allocate nb_stack!\n");
+		return -ENOMEM;

drivers/mempool/nb_stack/rte_mempool_nb_stack.c line 44

Quoted 10 lines
drivers/mempool/nb_stack/rte_mempool_nb_stack.c new file +10 -0
+	}
+
+	s->size = n;
+
+	nb_lifo_init(&s->used_lifo);
+	nb_lifo_init(&s->free_lifo);
+
+	elems = (struct nb_lifo_elem *)&s[1];
+	for (i = 0; i < n; i++)
+		nb_lifo_push_single(&s->free_lifo, &elems[i]);

This also can be added to nb_lifo_init API.

Quoted 116 lines
drivers/mempool/nb_stack/rte_mempool_nb_stack.c new file +80 -0
+
+	mp->pool_data = s;
+
+	return 0;
+}
+
+static int
+nb_stack_enqueue(struct rte_mempool *mp, void * const *obj_table,
+		 unsigned int n)
+{
+	struct rte_mempool_nb_stack *s = mp->pool_data;
+	struct nb_lifo_elem *first, *last, *tmp;
+	unsigned int i;
+
+	if (unlikely(n == 0))
+		return 0;
+
+	/* Pop n free elements */
+	first = nb_lifo_pop(&s->free_lifo, n, NULL, NULL);
+	if (unlikely(first == NULL))
+		return -ENOBUFS;
+
+	/* Prepare the list elements */
+	tmp = first;
+	for (i = 0; i < n; i++) {
+		tmp->data = obj_table[i];
+		last = tmp;
+		tmp = tmp->next;
+	}
+
+	/* Enqueue them to the used list */
+	nb_lifo_push(&s->used_lifo, first, last, n);
+
+	return 0;
+}
+
+static int
+nb_stack_dequeue(struct rte_mempool *mp, void **obj_table,
+		 unsigned int n)
+{
+	struct rte_mempool_nb_stack *s = mp->pool_data;
+	struct nb_lifo_elem *first, *last;
+
+	if (unlikely(n == 0))
+		return 0;
+
+	/* Pop n used elements */
+	first = nb_lifo_pop(&s->used_lifo, n, obj_table, &last);
+	if (unlikely(first == NULL))
+		return -ENOENT;
+
+	/* Enqueue the list elements to the free list */
+	nb_lifo_push(&s->free_lifo, first, last, n);
+
+	return 0;
+}
+
+static unsigned
+nb_stack_get_count(const struct rte_mempool *mp) {
+	struct rte_mempool_nb_stack *s = mp->pool_data;
+
+	return nb_lifo_len(&s->used_lifo);
+}
+
+static void
+nb_stack_free(struct rte_mempool *mp)
+{
+	rte_free(mp->pool_data);
+}
+
+static struct rte_mempool_ops ops_nb_stack = {
+	.name = "nb_stack",
+	.alloc = nb_stack_alloc,
+	.free = nb_stack_free,
+	.enqueue = nb_stack_enqueue,
+	.dequeue = nb_stack_dequeue,
+	.get_count = nb_stack_get_count
+};
+
+MEMPOOL_REGISTER_OPS(ops_nb_stack);
drivers/mempool/nb_stack/rte_mempool_nb_stack_version.map new file +4 -0
new file mode 100644
index 000000000..fc8c95e91
@@ -0,0 +1,4 @@
+DPDK_19.05 {
+
+	local: *;
+};
mk/rte.app.mk index 02e8b6f05..d4b4aaaf6 renamed from mk/rte.app.mk +0 -0

100644

mk/rte.app.mk +0 -1
@@ -131,8 +131,11 @@ endif
 ifeq ($(CONFIG_RTE_BUILD_SHARED_LIB),n)
 # plugins (link only if static libraries)
 
-_LDLIBS-$(CONFIG_RTE_DRIVER_MEMPOOL_BUCKET) += -

lrte_mempool_bucket
-_LDLIBS-$(CONFIG_RTE_DRIVER_MEMPOOL_STACK) += -
lrte_mempool_stack
+_LDLIBS-$(CONFIG_RTE_DRIVER_MEMPOOL_BUCKET) += -
lrte_mempool_bucket

mk/rte.app.mk +2 -0
+ifeq ($(CONFIG_RTE_ARCH_X86_64),y)
+_LDLIBS-$(CONFIG_RTE_DRIVER_MEMPOOL_NB_STACK) += -

lrte_mempool_nb_stack

mk/rte.app.mk +2 -0
+endif
+_LDLIBS-$(CONFIG_RTE_DRIVER_MEMPOOL_STACK)    += -

lrte_mempool_stack
ifeq ($(CONFIG_RTE_LIBRTE_DPAA_BUS),y)
_LDLIBS-$(CONFIG_RTE_LIBRTE_DPAA_MEMPOOL) += -lrte_mempool_dpaa
endif
--
2.13.6

author
#39 lore raw

Re: [PATCH v4 2/2] mempool/nb_stack: add non-blocking stack mempool

Quoted 14 lines

-----Original Message-----
From: Honnappa Nagarahalli [mailto:[email protected]]
Sent: Thursday, January 17, 2019 11:05 PM
To: Eads, Gage <[email protected]>; [email protected]
Cc: [email protected]; [email protected]; Richardson, Bruce <[email protected]>; Ananyev, Konstantin <[email protected]>; Gavin Hu (Arm Technology China) <[email protected]>; nd <[email protected]>; Honnappa Nagarahalli <[email protected]>; nd <[email protected]>
Subject: RE: [dpdk-dev] [PATCH v4 2/2] mempool/nb_stack: add non-blocking stack mempool

Quoted 4 lines

Hi Gage,
Thank you for your contribution on non-blocking data structures. I think they
are important to extend DPDK into additional use cases.

Glad to hear it. Be sure to check out my non-blocking ring patchset as well, if you haven't already: http://mails.dpdk.org/archives/dev/2019-January/123774.html

Quoted 6 lines

I am wondering if it makes sense to decouple the NB stack data structure from mempool driver (similar to rte_ring)? I see that stack based mempool implements the stack data structure in the driver. But, NB stack might not be such a trivial data structure. It might be useful for the applications or other use cases as well.

I agree -- and you're not the first to suggest this :).

I'm going to defer that work to a later patchset; creating a new lib/ directory requires tech board approval (IIRC), which would unnecessarily slow down this mempool handler from getting merged.

Quoted 4 lines

I also suggest that we use C11 __atomic_xxx APIs for memory operations. The rte_atomic64_xxx APIs use __sync_xxx APIs which do not provide the capability to express memory orderings.

Ok, I will add those (dependent on RTE_USE_C11_MEM_MODEL).

Quoted 88 lines

Please find few comments inline.

Quoted 84 lines

This commit adds support for non-blocking (linked list based) stack mempool handler. The stack uses a 128-bit compare-and-swap instruction, and thus is limited to x86_64. The 128-bit CAS atomically updates the stack top pointer and a modification counter, which protects against the ABA problem.

In mempool_perf_autotest the lock-based stack outperforms the non- blocking handler*, however:
- For applications with preemptible pthreads, a lock-based stack's worst-case performance (i.e. one thread being preempted while holding the spinlock) is much worse than the non-blocking 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 1x-3.5x the non-blocking stack's.

---
 MAINTAINERS                                        |   4 +
 config/common_base                                 |   1 +
 doc/guides/prog_guide/env_abstraction_layer.rst    |   5 +
 drivers/mempool/Makefile                           |   3 +
 drivers/mempool/meson.build                        |   3 +-
 drivers/mempool/nb_stack/Makefile                  |  23 ++++
 drivers/mempool/nb_stack/meson.build               |   6 +
 drivers/mempool/nb_stack/nb_lifo.h                 | 147
+++++++++++++++++++++
 drivers/mempool/nb_stack/rte_mempool_nb_stack.c    | 125
++++++++++++++++++
 .../nb_stack/rte_mempool_nb_stack_version.map      |   4 +
 mk/rte.app.mk                                      |   7 +-
 11 files changed, 325 insertions(+), 3 deletions(-)  create mode
100644 drivers/mempool/nb_stack/Makefile  create mode 100644
drivers/mempool/nb_stack/meson.build
 create mode 100644 drivers/mempool/nb_stack/nb_lifo.h
 create mode 100644 drivers/mempool/nb_stack/rte_mempool_nb_stack.c
 create mode 100644

drivers/mempool/nb_stack/rte_mempool_nb_stack_version.map

MAINTAINERS index 470f36b9c..5519d3323 renamed from MAINTAINERS +0 -0

100644

MAINTAINERS +4 -0
@@ -416,6 +416,10 @@ M: Artem V. Andreev <[email protected]>
 M: Andrew Rybchenko <[email protected]>
 F: drivers/mempool/bucket/
 
+Non-blocking stack memory pool
+M: Gage Eads <[email protected]>
+F: drivers/mempool/nb_stack/
+
 
 Bus Drivers
 -----------
config/common_base index renamed from config/common_base +0 -0

964a6956e..8a51f36b1 100644

config/common_base +0 -0
@@ -726,6 +726,7 @@ CONFIG_RTE_LIBRTE_MEMPOOL_DEBUG=n  #

CONFIG_RTE_DRIVER_MEMPOOL_BUCKET=y
CONFIG_RTE_DRIVER_MEMPOOL_BUCKET_SIZE_KB=64

config/common_base +1 -0
+CONFIG_RTE_DRIVER_MEMPOOL_NB_STACK=y
 CONFIG_RTE_DRIVER_MEMPOOL_RING=y
 CONFIG_RTE_DRIVER_MEMPOOL_STACK=y
doc/guides/prog_guide/env_abstraction_layer.rst +0 -0
index 929d76dba..9497b879c 100644
@@ -541,6 +541,11 @@ Known Issues
 
   5. It MUST not be used by multi-producer/consumer pthreads, whose

scheduling policies are SCHED_FIFO or SCHED_RR.

+ Alternatively, x86_64 applications can use the non-blocking stack mempool handler. When considering this handler, note that:

doc/guides/prog_guide/env_abstraction_layer.rst +3 -0
+
+  - it is limited to the x86_64 platform, because it uses an
+ instruction (16-
Quoted 1 line

byte compare-and-swap) that is not available on other platforms.

                                                 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ Arm
Quoted 3 lines

architecture supports similar instructions. I suggest to simplify this statement to indicate that 'nb_stack feature is available for x86_64 platforms currently'

Will do.

Quoted 94 lines
Quoted 94 lines

+ - 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 handler operations.
+
+ 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.

drivers/mempool/Makefile index renamed from drivers/mempool/Makefile +0 -0

28c2e8360..895cf8a34 100644

drivers/mempool/Makefile +2 -0
@@ -10,6 +10,9 @@ endif
 ifeq ($(CONFIG_RTE_EAL_VFIO)$(CONFIG_RTE_LIBRTE_FSLMC_BUS),yy)
 DIRS-$(CONFIG_RTE_LIBRTE_DPAA2_MEMPOOL) += dpaa2  endif
+ifeq ($(CONFIG_RTE_ARCH_X86_64),y)
+DIRS-$(CONFIG_RTE_DRIVER_MEMPOOL_NB_STACK) += nb_stack endif
 DIRS-$(CONFIG_RTE_DRIVER_MEMPOOL_RING) += ring
 DIRS-$(CONFIG_RTE_DRIVER_MEMPOOL_STACK) += stack
 DIRS-$(CONFIG_RTE_LIBRTE_OCTEONTX_MEMPOOL) += octeontx diff --git

a/drivers/mempool/meson.build b/drivers/mempool/meson.build index 4527d9806..220cfaf63 100644

drivers/mempool/meson.build +0 -0
@@ -1,7 +1,8 @@
 # SPDX-License-Identifier: BSD-3-Clause  # Copyright(c) 2017 Intel

Corporation

drivers/mempool/meson.build +3 -1
-drivers = ['bucket', 'dpaa', 'dpaa2', 'octeontx', 'ring', 'stack']
+drivers = ['bucket', 'dpaa', 'dpaa2', 'nb_stack', 'octeontx', 'ring',
+'stack']
+
 std_deps = ['mempool']
 config_flag_fmt = 'RTE_LIBRTE_@0@_MEMPOOL'
 driver_name_fmt = 'rte_mempool_@0@'
drivers/mempool/nb_stack/Makefile new file +21 -0
new file mode 100644
index 000000000..318b18283
@@ -0,0 +1,23 @@
+# SPDX-License-Identifier: BSD-3-Clause # Copyright(c) 2019 Intel
+Corporation
+
+include $(RTE_SDK)/mk/rte.vars.mk
+
+#
+# library name
+#
+LIB = librte_mempool_nb_stack.a
+
+CFLAGS += -O3
+CFLAGS += $(WERROR_FLAGS)
+
+# Headers
+LDLIBS += -lrte_eal -lrte_mempool
+
+EXPORT_MAP := rte_mempool_nb_stack_version.map
+
+LIBABIVER := 1
+
+SRCS-$(CONFIG_RTE_DRIVER_MEMPOOL_NB_STACK) +=

rte_mempool_nb_stack.c

drivers/mempool/nb_stack/Makefile new file +2 -0
+
+include $(RTE_SDK)/mk/rte.lib.mk
drivers/mempool/nb_stack/meson.build new file +6 -0
new file mode 100644
index 000000000..7dec72242
@@ -0,0 +1,6 @@
+# SPDX-License-Identifier: BSD-3-Clause # Copyright(c) 2019 Intel
+Corporation
+
+build = dpdk_conf.has('RTE_ARCH_X86_64')
+
+sources = files('rte_mempool_nb_stack.c')
drivers/mempool/nb_stack/nb_lifo.h new file +8 -0
new file mode 100644
index 000000000..ad4a3401f
@@ -0,0 +1,147 @@
+/* SPDX-License-Identifier: BSD-3-Clause
+ * Copyright(c) 2019 Intel Corporation  */
+
+#ifndef _NB_LIFO_H_
+#define _NB_LIFO_H_
+
+struct nb_lifo_elem {
+	void *data;
Quoted 9 lines

drivers/mempool/nb_stack/nb_lifo.h

Quoted 6 lines
drivers/mempool/nb_stack/nb_lifo.h new file +6 -0
+	struct nb_lifo_elem *next;
+};
+
+struct nb_lifo_head {
+	struct nb_lifo_elem *top; /**< Stack top */
+	uint64_t cnt; /**< Modification counter */ };

Minor comment, mentioning ABA problem in the comments for 'cnt' will be helpful.

Sure.

Quoted 56 lines
Quoted 56 lines
drivers/mempool/nb_stack/nb_lifo.h new file +16 -0
+
+struct nb_lifo {
+	volatile struct nb_lifo_head head __rte_aligned(16);
+	rte_atomic64_t len;
+} __rte_cache_aligned;
+
+static __rte_always_inline void
+nb_lifo_init(struct nb_lifo *lifo)
+{
+	memset(lifo, 0, sizeof(*lifo));
+	rte_atomic64_set(&lifo->len, 0);
+}
+
+static __rte_always_inline unsigned int nb_lifo_len(struct nb_lifo
+*lifo) {
+	/* nb_lifo_push() and nb_lifo_pop() do not update the list's

contents

drivers/mempool/nb_stack/nb_lifo.h new file +1 -0
+	 * and lifo->len atomically, which can cause the list to appear

shorter

drivers/mempool/nb_stack/nb_lifo.h new file +4 -0
+	 * than it actually is if this function is called while other threads
+	 * are modifying the list.
+	 *
+	 * However, given the inherently approximate nature of the

get_count

drivers/mempool/nb_stack/nb_lifo.h new file +2 -0
+	 * callback -- even if the list and its size were updated atomically,
+	 * the size could change between when get_count executes and

when the

drivers/mempool/nb_stack/nb_lifo.h new file +4 -0
+	 * value is returned to the caller -- this is acceptable.
+	 *
+	 * The lifo->len updates are placed such that the list may appear to
+	 * have fewer elements than it does, but will never appear to have

more

drivers/mempool/nb_stack/nb_lifo.h new file +24 -0
+	 * elements. If the mempool is near-empty to the point that this is a
+	 * concern, the user should consider increasing the mempool size.
+	 */
+	return (unsigned int)rte_atomic64_read(&lifo->len);
+}
+
+static __rte_always_inline void
+nb_lifo_push(struct nb_lifo *lifo,
+	     struct nb_lifo_elem *first,
+	     struct nb_lifo_elem *last,
+	     unsigned int num)
+{
+	while (1) {
+		struct nb_lifo_head old_head, new_head;
+
+		old_head = lifo->head;
+
+		/* Swing the top pointer to the first element in the list and
+		 * make the last element point to the old top.
+		 */
+		new_head.top = first;
+		new_head.cnt = old_head.cnt + 1;
+
+		last->next = old_head.top;
Quoted 9 lines

drivers/mempool/nb_stack/nb_lifo.h line 74

Quoted 6 lines
drivers/mempool/nb_stack/nb_lifo.h new file +6 -0
+
+		if (rte_atomic128_cmpset((volatile uint64_t *)&lifo->head,
+					 (uint64_t *)&old_head,
+					 (uint64_t *)&new_head))
+			break;
+	}

Minor comment, this can be a do-while loop (for ex: similar to the one in __rte_ring_move_prod_head)

Sure.

Quoted 42 lines
Quoted 42 lines
drivers/mempool/nb_stack/nb_lifo.h new file +42 -0
+
+	rte_atomic64_add(&lifo->len, num);
+}
+
+static __rte_always_inline void
+nb_lifo_push_single(struct nb_lifo *lifo, struct nb_lifo_elem *elem) {
+	nb_lifo_push(lifo, elem, elem, 1);
+}
+
+static __rte_always_inline struct nb_lifo_elem * nb_lifo_pop(struct
+nb_lifo *lifo,
+	    unsigned int num,
+	    void **obj_table,
+	    struct nb_lifo_elem **last)
+{
+	struct nb_lifo_head old_head;
+
+	/* Reserve num elements, if available */
+	while (1) {
+		uint64_t len = rte_atomic64_read(&lifo->len);
+
+		/* Does the list contain enough elements? */
+		if (len < num)
+			return NULL;
+
+		if (rte_atomic64_cmpset((volatile uint64_t *)&lifo->len,
+					len, len - num))
+			break;
+	}
+
+	/* Pop num elements */
+	while (1) {
+		struct nb_lifo_head new_head;
+		struct nb_lifo_elem *tmp;
+		unsigned int i;
+
+		old_head = lifo->head;
+
+		tmp = old_head.top;
+
+		/* Traverse the list to find the new head. A next pointer will
+		 * either point to another element or NULL; if a thread
Quoted 9 lines

drivers/mempool/nb_stack/nb_lifo.h line 122

Quoted 6 lines
drivers/mempool/nb_stack/nb_lifo.h new file +1 -0
+		 * encounters a pointer that has already been popped, the

CAS

drivers/mempool/nb_stack/nb_lifo.h new file +4 -0
+		 * will fail.
+		 */
+		for (i = 0; i < num && tmp != NULL; i++) {
+			if (obj_table)

This 'if' check can be outside the for loop. May be use RTE_ASSERT in the beginning of the function?

A NULL obj_table pointer isn't an error -- nb_stack_enqueue() calls this function with NULL because it doesn't need the popped elements added to a table. When the compiler inlines this function into nb_stack_enqueue(), it can use constant propagation to optimize away the if-statement.

I don't think that's possible for the other caller, nb_stack_dequeue, though, unless we add a NULL pointer check to the beginning of that function. Then it would be guaranteed that obj_table is non-NULL, and the compiler can optimize away the if-statement. I'll add that.

Quoted 50 lines
Quoted 50 lines
drivers/mempool/nb_stack/nb_lifo.h new file +25 -0
+				obj_table[i] = tmp->data;
+			if (last)
+				*last = tmp;
+			tmp = tmp->next;
+		}
+
+		/* If NULL was encountered, the list was modified while
+		 * traversing it. Retry.
+		 */
+		if (i != num)
+			continue;
+
+		new_head.top = tmp;
+		new_head.cnt = old_head.cnt + 1;
+
+		if (rte_atomic128_cmpset((volatile uint64_t *)&lifo->head,
+					 (uint64_t *)&old_head,
+					 (uint64_t *)&new_head))
+			break;
+	}
+
+	return old_head.top;
+}
+
+#endif /* _NB_LIFO_H_ */
drivers/mempool/nb_stack/rte_mempool_nb_stack.c new file +13 -0
new file mode 100644
index 000000000..1818a2cfa
@@ -0,0 +1,125 @@
+/* SPDX-License-Identifier: BSD-3-Clause
+ * Copyright(c) 2019 Intel Corporation  */
+
+#include <stdio.h>
+#include <rte_mempool.h>
+#include <rte_malloc.h>
+
+#include "nb_lifo.h"
+
+struct rte_mempool_nb_stack {
+	uint64_t size;
+	struct nb_lifo used_lifo; /**< LIFO containing mempool pointers  */
+	struct nb_lifo free_lifo; /**< LIFO containing unused LIFO elements

*/

drivers/mempool/nb_stack/rte_mempool_nb_stack.c new file +4 -0
+};
+
+static int
+nb_stack_alloc(struct rte_mempool *mp) {
Quoted 9 lines

drivers/mempool/nb_stack/rte_mempool_nb_stack.c line 25

Quoted 6 lines
drivers/mempool/nb_stack/rte_mempool_nb_stack.c new file +6 -0
+	struct rte_mempool_nb_stack *s;
+	struct nb_lifo_elem *elems;
+	unsigned int n = mp->size;
+	unsigned int size, i;
+
+	size = sizeof(*s) + n * sizeof(struct nb_lifo_elem);

IMO, the allocation of the stack elements can be moved under nb_lifo_init API, it would make the nb stack code modular.

(see below)

Quoted 12 lines
Quoted 12 lines
drivers/mempool/nb_stack/rte_mempool_nb_stack.c new file +12 -0
+
+	/* Allocate our local memory structure */
+	s = rte_zmalloc_socket("mempool-nb_stack",
+			       size,
+			       RTE_CACHE_LINE_SIZE,
+			       mp->socket_id);
+	if (s == NULL) {
+		RTE_LOG(ERR, MEMPOOL, "Cannot allocate nb_stack!\n");
+		return -ENOMEM;
+	}
+
+	s->size = n;
Quoted 9 lines

drivers/mempool/nb_stack/rte_mempool_nb_stack.c line 44

Quoted 7 lines
drivers/mempool/nb_stack/rte_mempool_nb_stack.c new file +7 -0
+
+	nb_lifo_init(&s->used_lifo);
+	nb_lifo_init(&s->free_lifo);
+
+	elems = (struct nb_lifo_elem *)&s[1];
+	for (i = 0; i < n; i++)
+		nb_lifo_push_single(&s->free_lifo, &elems[i]);

This also can be added to nb_lifo_init API.

Sure, good suggestions. I'll address this.

Appreciate the feedback!

Thanks,
Gage

author
#40 lore raw

Re: [PATCH v4 2/2] mempool/nb_stack: add non-blocking stack mempool

In reply to Honnappa Nagarahalli
Quoted 473 lines

-----Original Message-----
From: Eads, Gage
Sent: Friday, January 18, 2019 2:10 PM
To: 'Honnappa Nagarahalli' <[email protected]>; [email protected]
Cc: [email protected]; [email protected]; Richardson, Bruce <[email protected]>; Ananyev, Konstantin <[email protected]>; Gavin Hu (Arm Technology China) <[email protected]>; nd <[email protected]>; nd <[email protected]>
Subject: RE: [dpdk-dev] [PATCH v4 2/2] mempool/nb_stack: add non-blocking stack mempool

Quoted 12 lines

-----Original Message-----
From: Honnappa Nagarahalli [mailto:[email protected]]
Sent: Thursday, January 17, 2019 11:05 PM
To: Eads, Gage <[email protected]>; [email protected]
Cc: [email protected]; [email protected]; Richardson, Bruce <[email protected]>; Ananyev, Konstantin <[email protected]>; Gavin Hu (Arm Technology China) <[email protected]>; nd <[email protected]>; Honnappa Nagarahalli <[email protected]>; nd <[email protected]>
Subject: RE: [dpdk-dev] [PATCH v4 2/2] mempool/nb_stack: add non-blocking stack mempool

Quoted 4 lines

Hi Gage,
Thank you for your contribution on non-blocking data structures.
I think they are important to extend DPDK into additional use cases.

Glad to hear it. Be sure to check out my non-blocking ring patchset as well, if you haven't already: http://mails.dpdk.org/archives/dev/2019-
January/123774.html

Quoted 6 lines

I am wondering if it makes sense to decouple the NB stack data structure from mempool driver (similar to rte_ring)? I see that stack based mempool implements the stack data structure in the driver. But, NB stack might not be such a trivial data structure. It might be useful for the applications or other use cases as well.

I agree -- and you're not the first to suggest this :).

I'm going to defer that work to a later patchset; creating a new lib/ directory requires tech board approval (IIRC), which would unnecessarily slow down this mempool handler from getting merged.

Quoted 4 lines

I also suggest that we use C11 __atomic_xxx APIs for memory operations. The rte_atomic64_xxx APIs use __sync_xxx APIs which do not provide the capability to express memory orderings.

Ok, I will add those (dependent on RTE_USE_C11_MEM_MODEL).

Quoted 82 lines

Please find few comments inline.

Quoted 80 lines

This commit adds support for non-blocking (linked list based) stack mempool handler. The stack uses a 128-bit compare-and-swap instruction, and thus is limited to x86_64. The 128-bit CAS atomically updates the stack top pointer and a modification counter, which protects against the ABA problem.

In mempool_perf_autotest the lock-based stack outperforms the non- blocking handler*, however:
- For applications with preemptible pthreads, a lock-based stack's worst-case performance (i.e. one thread being preempted while holding the spinlock) is much worse than the non-blocking 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 1x-3.5x the non-blocking stack's.

---
 MAINTAINERS                                        |   4 +
 config/common_base                                 |   1 +
 doc/guides/prog_guide/env_abstraction_layer.rst    |   5 +
 drivers/mempool/Makefile                           |   3 +
 drivers/mempool/meson.build                        |   3 +-
 drivers/mempool/nb_stack/Makefile                  |  23 ++++
 drivers/mempool/nb_stack/meson.build               |   6 +
 drivers/mempool/nb_stack/nb_lifo.h                 | 147
+++++++++++++++++++++
 drivers/mempool/nb_stack/rte_mempool_nb_stack.c    | 125
++++++++++++++++++
 .../nb_stack/rte_mempool_nb_stack_version.map      |   4 +
 mk/rte.app.mk                                      |   7 +-
 11 files changed, 325 insertions(+), 3 deletions(-)  create mode
100644 drivers/mempool/nb_stack/Makefile  create mode 100644
drivers/mempool/nb_stack/meson.build
 create mode 100644 drivers/mempool/nb_stack/nb_lifo.h
 create mode 100644 drivers/mempool/nb_stack/rte_mempool_nb_stack.c
 create mode 100644

drivers/mempool/nb_stack/rte_mempool_nb_stack_version.map

MAINTAINERS index 470f36b9c..5519d3323 renamed from MAINTAINERS +0 -0

100644

MAINTAINERS +0 -0
@@ -416,6 +416,10 @@ M: Artem V. Andreev

<[email protected]>
M: Andrew Rybchenko <[email protected]>
F: drivers/mempool/bucket/

MAINTAINERS +4 -0
+Non-blocking stack memory pool
+M: Gage Eads <[email protected]>
+F: drivers/mempool/nb_stack/
+
 
 Bus Drivers
 -----------
config/common_base index renamed from config/common_base +0 -0

964a6956e..8a51f36b1 100644

config/common_base +0 -0
@@ -726,6 +726,7 @@ CONFIG_RTE_LIBRTE_MEMPOOL_DEBUG=n  #

CONFIG_RTE_DRIVER_MEMPOOL_BUCKET=y
CONFIG_RTE_DRIVER_MEMPOOL_BUCKET_SIZE_KB=64

config/common_base +1 -0
+CONFIG_RTE_DRIVER_MEMPOOL_NB_STACK=y
 CONFIG_RTE_DRIVER_MEMPOOL_RING=y
 CONFIG_RTE_DRIVER_MEMPOOL_STACK=y
doc/guides/prog_guide/env_abstraction_layer.rst +0 -0
index 929d76dba..9497b879c 100644
@@ -541,6 +541,11 @@ Known Issues
 
   5. It MUST not be used by multi-producer/consumer pthreads, whose

scheduling policies are SCHED_FIFO or SCHED_RR.

Quoted 9 lines
Quoted 6 lines

+ Alternatively, x86_64 applications can use the non-blocking stack mempool handler. When considering this handler, note that:

doc/guides/prog_guide/env_abstraction_layer.rst +3 -0
+
+  - it is limited to the x86_64 platform, because it uses an
+ instruction (16-

byte compare-and-swap) that is not available on other platforms.

^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ Arm architecture supports similar instructions. I suggest to simplify this statement to indicate that 'nb_stack

feature is available for x86_64 platforms currently'

Quoted 1 line

Will do.

Quoted 95 lines
Quoted 95 lines

+ - 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 handler operations.
+
+ 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.

drivers/mempool/Makefile +0 -0

index
28c2e8360..895cf8a34 100644

drivers/mempool/Makefile +2 -0
@@ -10,6 +10,9 @@ endif
 ifeq ($(CONFIG_RTE_EAL_VFIO)$(CONFIG_RTE_LIBRTE_FSLMC_BUS),yy)
 DIRS-$(CONFIG_RTE_LIBRTE_DPAA2_MEMPOOL) += dpaa2  endif
+ifeq ($(CONFIG_RTE_ARCH_X86_64),y)
+DIRS-$(CONFIG_RTE_DRIVER_MEMPOOL_NB_STACK) += nb_stack endif
 DIRS-$(CONFIG_RTE_DRIVER_MEMPOOL_RING) += ring
 DIRS-$(CONFIG_RTE_DRIVER_MEMPOOL_STACK) += stack
 DIRS-$(CONFIG_RTE_LIBRTE_OCTEONTX_MEMPOOL) += octeontx diff --git

a/drivers/mempool/meson.build b/drivers/mempool/meson.build index 4527d9806..220cfaf63 100644

drivers/mempool/meson.build +0 -0
@@ -1,7 +1,8 @@
 # SPDX-License-Identifier: BSD-3-Clause  # Copyright(c) 2017 Intel

Corporation

drivers/mempool/meson.build +3 -1
-drivers = ['bucket', 'dpaa', 'dpaa2', 'octeontx', 'ring', 'stack']
+drivers = ['bucket', 'dpaa', 'dpaa2', 'nb_stack', 'octeontx',
+'ring', 'stack']
+
 std_deps = ['mempool']
 config_flag_fmt = 'RTE_LIBRTE_@0@_MEMPOOL'
 driver_name_fmt = 'rte_mempool_@0@'
drivers/mempool/nb_stack/Makefile new file +21 -0
new file mode 100644
index 000000000..318b18283
@@ -0,0 +1,23 @@
+# SPDX-License-Identifier: BSD-3-Clause # Copyright(c) 2019 Intel
+Corporation
+
+include $(RTE_SDK)/mk/rte.vars.mk
+
+#
+# library name
+#
+LIB = librte_mempool_nb_stack.a
+
+CFLAGS += -O3
+CFLAGS += $(WERROR_FLAGS)
+
+# Headers
+LDLIBS += -lrte_eal -lrte_mempool
+
+EXPORT_MAP := rte_mempool_nb_stack_version.map
+
+LIBABIVER := 1
+
+SRCS-$(CONFIG_RTE_DRIVER_MEMPOOL_NB_STACK) +=

rte_mempool_nb_stack.c

drivers/mempool/nb_stack/Makefile new file +2 -0
+
+include $(RTE_SDK)/mk/rte.lib.mk
drivers/mempool/nb_stack/meson.build new file +6 -0
new file mode 100644
index 000000000..7dec72242
@@ -0,0 +1,6 @@
+# SPDX-License-Identifier: BSD-3-Clause # Copyright(c) 2019 Intel
+Corporation
+
+build = dpdk_conf.has('RTE_ARCH_X86_64')
+
+sources = files('rte_mempool_nb_stack.c')
drivers/mempool/nb_stack/nb_lifo.h new file +8 -0
new file mode 100644
index 000000000..ad4a3401f
@@ -0,0 +1,147 @@
+/* SPDX-License-Identifier: BSD-3-Clause
+ * Copyright(c) 2019 Intel Corporation  */
+
+#ifndef _NB_LIFO_H_
+#define _NB_LIFO_H_
+
+struct nb_lifo_elem {
+	void *data;
Quoted 9 lines

drivers/mempool/nb_stack/nb_lifo.h

Quoted 6 lines
drivers/mempool/nb_stack/nb_lifo.h new file +6 -0
+	struct nb_lifo_elem *next;
+};
+
+struct nb_lifo_head {
+	struct nb_lifo_elem *top; /**< Stack top */
+	uint64_t cnt; /**< Modification counter */ };

Minor comment, mentioning ABA problem in the comments for 'cnt' will be helpful.

Sure.

Quoted 57 lines
Quoted 57 lines
drivers/mempool/nb_stack/nb_lifo.h new file +16 -0
+
+struct nb_lifo {
+	volatile struct nb_lifo_head head __rte_aligned(16);
+	rte_atomic64_t len;
+} __rte_cache_aligned;
+
+static __rte_always_inline void
+nb_lifo_init(struct nb_lifo *lifo)
+{
+	memset(lifo, 0, sizeof(*lifo));
+	rte_atomic64_set(&lifo->len, 0);
+}
+
+static __rte_always_inline unsigned int nb_lifo_len(struct nb_lifo
+*lifo) {
+	/* nb_lifo_push() and nb_lifo_pop() do not update the list's

contents

drivers/mempool/nb_stack/nb_lifo.h new file +1 -0
+	 * and lifo->len atomically, which can cause the list to appear

shorter

drivers/mempool/nb_stack/nb_lifo.h new file +4 -0
+	 * than it actually is if this function is called while other threads
+	 * are modifying the list.
+	 *
+	 * However, given the inherently approximate nature of the

get_count

drivers/mempool/nb_stack/nb_lifo.h new file +2 -0
+	 * callback -- even if the list and its size were updated atomically,
+	 * the size could change between when get_count executes and

when the

drivers/mempool/nb_stack/nb_lifo.h new file +4 -0
+	 * value is returned to the caller -- this is acceptable.
+	 *
+	 * The lifo->len updates are placed such that the list may appear to
+	 * have fewer elements than it does, but will never appear to have

more

drivers/mempool/nb_stack/nb_lifo.h new file +25 -0
+	 * elements. If the mempool is near-empty to the point that this is a
+	 * concern, the user should consider increasing the mempool size.
+	 */
+	return (unsigned int)rte_atomic64_read(&lifo->len);
+}
+
+static __rte_always_inline void
+nb_lifo_push(struct nb_lifo *lifo,
+	     struct nb_lifo_elem *first,
+	     struct nb_lifo_elem *last,
+	     unsigned int num)
+{
+	while (1) {
+		struct nb_lifo_head old_head, new_head;
+
+		old_head = lifo->head;
+
+		/* Swing the top pointer to the first element in the list and
+		 * make the last element point to the old top.
+		 */
+		new_head.top = first;
+		new_head.cnt = old_head.cnt + 1;
+
+		last->next = old_head.top;
+
Quoted 9 lines

drivers/mempool/nb_stack/nb_lifo.h line 74

Quoted 5 lines
drivers/mempool/nb_stack/nb_lifo.h new file +5 -0
+		if (rte_atomic128_cmpset((volatile uint64_t *)&lifo->head,
+					 (uint64_t *)&old_head,
+					 (uint64_t *)&new_head))
+			break;
+	}

Minor comment, this can be a do-while loop (for ex: similar to the one in
__rte_ring_move_prod_head)

Sure.

Quoted 40 lines
Quoted 40 lines
drivers/mempool/nb_stack/nb_lifo.h new file +40 -0
+
+	rte_atomic64_add(&lifo->len, num); }
+
+static __rte_always_inline void
+nb_lifo_push_single(struct nb_lifo *lifo, struct nb_lifo_elem *elem) {
+	nb_lifo_push(lifo, elem, elem, 1); }
+
+static __rte_always_inline struct nb_lifo_elem * nb_lifo_pop(struct
+nb_lifo *lifo,
+	    unsigned int num,
+	    void **obj_table,
+	    struct nb_lifo_elem **last)
+{
+	struct nb_lifo_head old_head;
+
+	/* Reserve num elements, if available */
+	while (1) {
+		uint64_t len = rte_atomic64_read(&lifo->len);
+
+		/* Does the list contain enough elements? */
+		if (len < num)
+			return NULL;
+
+		if (rte_atomic64_cmpset((volatile uint64_t *)&lifo->len,
+					len, len - num))
+			break;
+	}
+
+	/* Pop num elements */
+	while (1) {
+		struct nb_lifo_head new_head;
+		struct nb_lifo_elem *tmp;
+		unsigned int i;
+
+		old_head = lifo->head;
+
+		tmp = old_head.top;
+
+		/* Traverse the list to find the new head. A next pointer will
+		 * either point to another element or NULL; if a thread
Quoted 9 lines

drivers/mempool/nb_stack/nb_lifo.h line 122

Quoted 6 lines
drivers/mempool/nb_stack/nb_lifo.h new file +1 -0
+		 * encounters a pointer that has already been popped, the

CAS

drivers/mempool/nb_stack/nb_lifo.h new file +4 -0
+		 * will fail.
+		 */
+		for (i = 0; i < num && tmp != NULL; i++) {
+			if (obj_table)

This 'if' check can be outside the for loop. May be use RTE_ASSERT in the beginning of the function?

A NULL obj_table pointer isn't an error -- nb_stack_enqueue() calls this function with NULL because it doesn't need the popped elements added to a table. When the compiler inlines this function into nb_stack_enqueue(), it can use constant propagation to optimize away the if-statement.

I don't think that's possible for the other caller, nb_stack_dequeue, though, unless we add a NULL pointer check to the beginning of that function. Then it would be guaranteed that obj_table is non-NULL, and the compiler can optimize away the if-statement. I'll add that.

Quoted 51 lines
Quoted 51 lines
drivers/mempool/nb_stack/nb_lifo.h new file +25 -0
+				obj_table[i] = tmp->data;
+			if (last)
+				*last = tmp;
+			tmp = tmp->next;
+		}
+
+		/* If NULL was encountered, the list was modified while
+		 * traversing it. Retry.
+		 */
+		if (i != num)
+			continue;
+
+		new_head.top = tmp;
+		new_head.cnt = old_head.cnt + 1;
+
+		if (rte_atomic128_cmpset((volatile uint64_t *)&lifo->head,
+					 (uint64_t *)&old_head,
+					 (uint64_t *)&new_head))
+			break;
+	}
+
+	return old_head.top;
+}
+
+#endif /* _NB_LIFO_H_ */
drivers/mempool/nb_stack/rte_mempool_nb_stack.c new file +14 -0
new file mode 100644
index 000000000..1818a2cfa
@@ -0,0 +1,125 @@
+/* SPDX-License-Identifier: BSD-3-Clause
+ * Copyright(c) 2019 Intel Corporation  */
+
+#include <stdio.h>
+#include <rte_mempool.h>
+#include <rte_malloc.h>
+
+#include "nb_lifo.h"
+
+struct rte_mempool_nb_stack {
+	uint64_t size;
+	struct nb_lifo used_lifo; /**< LIFO containing mempool pointers  */
+	struct nb_lifo free_lifo; /**< LIFO containing unused LIFO
+elements

*/

drivers/mempool/nb_stack/rte_mempool_nb_stack.c new file +4 -0
+};
+
+static int
+nb_stack_alloc(struct rte_mempool *mp) {
Quoted 9 lines

drivers/mempool/nb_stack/rte_mempool_nb_stack.c line 25

Quoted 6 lines
drivers/mempool/nb_stack/rte_mempool_nb_stack.c new file +6 -0
+	struct rte_mempool_nb_stack *s;
+	struct nb_lifo_elem *elems;
+	unsigned int n = mp->size;
+	unsigned int size, i;
+
+	size = sizeof(*s) + n * sizeof(struct nb_lifo_elem);

IMO, the allocation of the stack elements can be moved under nb_lifo_init API, it would make the nb stack code modular.

(see below)

Quoted 12 lines
Quoted 12 lines
drivers/mempool/nb_stack/rte_mempool_nb_stack.c new file +12 -0
+
+	/* Allocate our local memory structure */
+	s = rte_zmalloc_socket("mempool-nb_stack",
+			       size,
+			       RTE_CACHE_LINE_SIZE,
+			       mp->socket_id);
+	if (s == NULL) {
+		RTE_LOG(ERR, MEMPOOL, "Cannot allocate nb_stack!\n");
+		return -ENOMEM;
+	}
+
+	s->size = n;
Quoted 9 lines

drivers/mempool/nb_stack/rte_mempool_nb_stack.c line 44

Quoted 7 lines
drivers/mempool/nb_stack/rte_mempool_nb_stack.c new file +7 -0
+
+	nb_lifo_init(&s->used_lifo);
+	nb_lifo_init(&s->free_lifo);
+
+	elems = (struct nb_lifo_elem *)&s[1];
+	for (i = 0; i < n; i++)
+		nb_lifo_push_single(&s->free_lifo, &elems[i]);

This also can be added to nb_lifo_init API.

Quoted 2 lines

Sure, good suggestions. I'll address this.

On second thought, moving this push code into nb_lifo_init() doesn't work since we do it for one LIFO and not the other.

I'll think on it, but I'm not going to spend too many cycles -- modularizing nb_lifo can be deferred to the patchset that moves it to a separate library.

#41 lore raw

Re: [PATCH v4 2/2] mempool/nb_stack: add non-blocking stack mempool

19/01/2019 01:00, Eads, Gage:

Quoted 7 lines
Quoted 7 lines
Quoted 6 lines

I am wondering if it makes sense to decouple the NB stack data structure from mempool driver (similar to rte_ring)? I see that stack based mempool implements the stack data structure in the driver. But, NB stack might not be such a trivial data structure. It might be useful for the applications or other use cases as well.

Quoted 5 lines
Quoted 5 lines

I agree -- and you're not the first to suggest this :).

I'm going to defer that work to a later patchset; creating a new lib/ directory requires tech board approval (IIRC), which would unnecessarily slow down this mempool handler from getting merged.

You have time. This patch cannot go in 19.02.
You just need to be ready for 19.05-rc1 (more than 2 months).

[...]

Quoted 1 line

modularizing nb_lifo can be deferred to the patchset that moves it to a separate library.

Please introduce it in the right place from the beginning.

author
#42 lore raw

Re: [PATCH v4 2/2] mempool/nb_stack: add non-blocking stack mempool

Quoted 22 lines

-----Original Message-----
From: Thomas Monjalon [mailto:[email protected]]
Sent: Friday, January 18, 2019 6:15 PM
To: Eads, Gage <[email protected]>
Cc: [email protected]; Honnappa Nagarahalli <[email protected]>; [email protected]; [email protected]; Richardson, Bruce <[email protected]>; Ananyev, Konstantin <[email protected]>; Gavin Hu (Arm Technology China) <[email protected]>; nd <[email protected]>
Subject: Re: [dpdk-dev] [PATCH v4 2/2] mempool/nb_stack: add non-blocking stack mempool

19/01/2019 01:00, Eads, Gage:

Quoted 7 lines
Quoted 7 lines
Quoted 6 lines

I am wondering if it makes sense to decouple the NB stack data structure from mempool driver (similar to rte_ring)? I see that stack based mempool implements the stack data structure in the driver. But, NB stack might not be such a trivial data structure. It might be useful for the applications or other use cases as well.

Quoted 9 lines
Quoted 5 lines
Quoted 5 lines

I agree -- and you're not the first to suggest this :).

I'm going to defer that work to a later patchset; creating a new lib/ directory requires tech board approval (IIRC), which would unnecessarily slow down this mempool handler from getting merged.

You have time. This patch cannot go in 19.02.
You just need to be ready for 19.05-rc1 (more than 2 months).

Understood, I was concerned the process could take longer. The code itself isn't too complicated, but I'm not sure how much time it'll take to reach consensus on the interface. On the other hand, it may go quickly if we model it after the ring API -- my current thinking -- which folks seem to generally like.

Anyway, I'll rework this into a standalone stack library.

Thanks,
Gage

Quoted 6 lines

[...]

Quoted 1 line

modularizing nb_lifo can be deferred to the patchset that moves it to a

separate library.

Please introduce it in the right place from the beginning.