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

["Eads, Gage" <gage.eads@intel.com>]

> -----Original Message-----
> From: Eads, Gage
> Sent: Friday, January 18, 2019 2:10 PM
> To: 'Honnappa Nagarahalli' <Honnappa.Nagarahalli@arm.com>; dev@dpdk.org
> Cc: olivier.matz@6wind.com; arybchenko@solarflare.com; Richardson, Bruce
> <bruce.richardson@intel.com>; Ananyev, Konstantin
> <konstantin.ananyev@intel.com>; Gavin Hu (Arm Technology China)
> <Gavin.Hu@arm.com>; nd <nd@arm.com>; nd <nd@arm.com>
> Subject: RE: [dpdk-dev] [PATCH v4 2/2] mempool/nb_stack: add non-blocking
> stack mempool
> 
> 
> 
> > -----Original Message-----
> > From: Honnappa Nagarahalli [mailto:Honnappa.Nagarahalli@arm.com]
> > Sent: Thursday, January 17, 2019 11:05 PM
> > To: Eads, Gage <gage.eads@intel.com>; dev@dpdk.org
> > Cc: olivier.matz@6wind.com; arybchenko@solarflare.com; Richardson,
> > Bruce <bruce.richardson@intel.com>; Ananyev, Konstantin
> > <konstantin.ananyev@intel.com>; Gavin Hu (Arm Technology China)
> > <Gavin.Hu@arm.com>; nd <nd@arm.com>; Honnappa Nagarahalli
> > <Honnappa.Nagarahalli@arm.com>; nd <nd@arm.com>
> > Subject: RE: [dpdk-dev] [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.
> >
> 
> 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
> 
> > 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.
> 
> > 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).
> 
> > Please find few comments inline.
> >
> > >
> > > 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.
> > >
> > > Signed-off-by: Gage Eads <gage.eads@intel.com>
> > > Acked-by: Andrew Rybchenko <arybchenko@solarflare.com>
> > > ---
> > >  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
> > >
> > > diff --git a/MAINTAINERS b/MAINTAINERS index 470f36b9c..5519d3323
> > > 100644
> > > --- a/MAINTAINERS
> > > +++ b/MAINTAINERS
> > > @@ -416,6 +416,10 @@ M: Artem V. Andreev
> > > <artem.andreev@oktetlabs.ru>
> > >  M: Andrew Rybchenko <arybchenko@solarflare.com>
> > >  F: drivers/mempool/bucket/
> > >
> > > +Non-blocking stack memory pool
> > > +M: Gage Eads <gage.eads@intel.com>
> > > +F: drivers/mempool/nb_stack/
> > > +
> > >
> > >  Bus Drivers
> > >  -----------
> > > diff --git a/config/common_base b/config/common_base index
> > > 964a6956e..8a51f36b1 100644
> > > --- a/config/common_base
> > > +++ b/config/common_base
> > > @@ -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
> > >
> > > diff --git a/doc/guides/prog_guide/env_abstraction_layer.rst
> > > b/doc/guides/prog_guide/env_abstraction_layer.rst
> > > index 929d76dba..9497b879c 100644
> > > --- a/doc/guides/prog_guide/env_abstraction_layer.rst
> > > +++ b/doc/guides/prog_guide/env_abstraction_layer.rst
> > > @@ -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.
> >
> > ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ Arm 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.
> 
> > > +  - 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.
> > > diff --git a/drivers/mempool/Makefile b/drivers/mempool/Makefile
> > > index
> > > 28c2e8360..895cf8a34 100644
> > > --- a/drivers/mempool/Makefile
> > > +++ b/drivers/mempool/Makefile
> > > @@ -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
> > > --- a/drivers/mempool/meson.build
> > > +++ b/drivers/mempool/meson.build
> > > @@ -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@'
> > > diff --git a/drivers/mempool/nb_stack/Makefile
> > > b/drivers/mempool/nb_stack/Makefile
> > > new file mode 100644
> > > index 000000000..318b18283
> > > --- /dev/null
> > > +++ b/drivers/mempool/nb_stack/Makefile
> > > @@ -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
> > > diff --git a/drivers/mempool/nb_stack/meson.build
> > > b/drivers/mempool/nb_stack/meson.build
> > > new file mode 100644
> > > index 000000000..7dec72242
> > > --- /dev/null
> > > +++ b/drivers/mempool/nb_stack/meson.build
> > > @@ -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')
> > > diff --git a/drivers/mempool/nb_stack/nb_lifo.h
> > > b/drivers/mempool/nb_stack/nb_lifo.h
> > > new file mode 100644
> > > index 000000000..ad4a3401f
> > > --- /dev/null
> > > +++ b/drivers/mempool/nb_stack/nb_lifo.h
> > > @@ -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 */ };
> > Minor comment, mentioning ABA problem in the comments for 'cnt' will
> > be helpful.
> >
> 
> Sure.
> 
> > > +
> > > +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.
> > > +	 */
> > > +	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;
> > > +	}
> > Minor comment, this can be a do-while loop (for ex: similar to the one
> > in
> > __rte_ring_move_prod_head)
> >
> 
> Sure.
> 
> > > +
> > > +	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.
> > > +		 */
> > > +		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.
> 
> > > +				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_ */
> > > 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..1818a2cfa
> > > --- /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);
> > 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)
> 
> > > +
> > > +	/* 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]);
> > This also can be added to nb_lifo_init API.
> >
> 
> 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.