[v3,1/8] stack: introduce rte stack library

  The rte_stack library provides an API for configuration and use of a
bounded stack of pointers. Push and pop operations are MT-safe, allowing
concurrent access, and the interface supports pushing and popping multiple
pointers at a time.

The library's interface is modeled after another DPDK data structure,
rte_ring, and its lock-based implementation is derived from the stack
mempool handler. An upcoming commit will migrate the stack mempool handler
to rte_stack.

Signed-off-by: Gage Eads <gage.eads@intel.com>
---
 MAINTAINERS                            |   6 +
 config/common_base                     |   5 +
 doc/api/doxy-api-index.md              |   1 +
 doc/api/doxy-api.conf.in               |   1 +
 doc/guides/prog_guide/index.rst        |   1 +
 doc/guides/prog_guide/stack_lib.rst    |  28 ++++
 doc/guides/rel_notes/release_19_05.rst |   5 +
 lib/Makefile                           |   2 +
 lib/librte_stack/Makefile              |  23 +++
 lib/librte_stack/meson.build           |   8 +
 lib/librte_stack/rte_stack.c           | 194 +++++++++++++++++++++++
 lib/librte_stack/rte_stack.h           | 274 +++++++++++++++++++++++++++++++++
 lib/librte_stack/rte_stack_pvt.h       |  34 ++++
 lib/librte_stack/rte_stack_version.map |   9 ++
 lib/meson.build                        |   2 +-
 mk/rte.app.mk                          |   1 +
 16 files changed, 593 insertions(+), 1 deletion(-)
 create mode 100644 doc/guides/prog_guide/stack_lib.rst
 create mode 100644 lib/librte_stack/Makefile
 create mode 100644 lib/librte_stack/meson.build
 create mode 100644 lib/librte_stack/rte_stack.c
 create mode 100644 lib/librte_stack/rte_stack.h
 create mode 100644 lib/librte_stack/rte_stack_pvt.h
 create mode 100644 lib/librte_stack/rte_stack_version.map
  

On Wed, Mar 06, 2019 at 08:45:52AM -0600, Gage Eads wrote:
> The rte_stack library provides an API for configuration and use of a
> bounded stack of pointers. Push and pop operations are MT-safe, allowing
> concurrent access, and the interface supports pushing and popping multiple
> pointers at a time.
> 
> The library's interface is modeled after another DPDK data structure,
> rte_ring, and its lock-based implementation is derived from the stack
> mempool handler. An upcoming commit will migrate the stack mempool handler
> to rte_stack.
> 
> Signed-off-by: Gage Eads <gage.eads@intel.com>

Reviewed-by: Olivier Matz <olivier.matz@6wind.com>
  

Hi Gage,
	Apologies for the late comments.

> -----Original Message-----
> From: Gage Eads <gage.eads@intel.com>
> Sent: Wednesday, March 6, 2019 8:46 AM
> To: dev@dpdk.org
> Cc: olivier.matz@6wind.com; arybchenko@solarflare.com;
> bruce.richardson@intel.com; konstantin.ananyev@intel.com; Gavin Hu (Arm
> Technology China) <Gavin.Hu@arm.com>; Honnappa Nagarahalli
> <Honnappa.Nagarahalli@arm.com>; nd <nd@arm.com>;
> thomas@monjalon.net
> Subject: [PATCH v3 1/8] stack: introduce rte stack library
> 
> The rte_stack library provides an API for configuration and use of a bounded
> stack of pointers. Push and pop operations are MT-safe, allowing concurrent
> access, and the interface supports pushing and popping multiple pointers at a
> time.
> 
> The library's interface is modeled after another DPDK data structure, rte_ring,
> and its lock-based implementation is derived from the stack mempool
> handler. An upcoming commit will migrate the stack mempool handler to
> rte_stack.
> 
> Signed-off-by: Gage Eads <gage.eads@intel.com>
> ---
>  MAINTAINERS                            |   6 +
>  config/common_base                     |   5 +
>  doc/api/doxy-api-index.md              |   1 +
>  doc/api/doxy-api.conf.in               |   1 +
>  doc/guides/prog_guide/index.rst        |   1 +
>  doc/guides/prog_guide/stack_lib.rst    |  28 ++++
>  doc/guides/rel_notes/release_19_05.rst |   5 +
>  lib/Makefile                           |   2 +
>  lib/librte_stack/Makefile              |  23 +++
>  lib/librte_stack/meson.build           |   8 +
>  lib/librte_stack/rte_stack.c           | 194 +++++++++++++++++++++++
>  lib/librte_stack/rte_stack.h           | 274
> +++++++++++++++++++++++++++++++++
>  lib/librte_stack/rte_stack_pvt.h       |  34 ++++
>  lib/librte_stack/rte_stack_version.map |   9 ++
>  lib/meson.build                        |   2 +-
>  mk/rte.app.mk                          |   1 +
>  16 files changed, 593 insertions(+), 1 deletion(-)  create mode 100644
> doc/guides/prog_guide/stack_lib.rst
>  create mode 100644 lib/librte_stack/Makefile  create mode 100644
> lib/librte_stack/meson.build  create mode 100644 lib/librte_stack/rte_stack.c
> create mode 100644 lib/librte_stack/rte_stack.h  create mode 100644
> lib/librte_stack/rte_stack_pvt.h  create mode 100644
> lib/librte_stack/rte_stack_version.map
> 
> diff --git a/MAINTAINERS b/MAINTAINERS
> index 097cfb4f3..5fca30823 100644
> --- a/MAINTAINERS
> +++ b/MAINTAINERS
> @@ -405,6 +405,12 @@ F: drivers/raw/skeleton_rawdev/
>  F: app/test/test_rawdev.c
>  F: doc/guides/prog_guide/rawdev.rst
> 
> +Stack API - EXPERIMENTAL
> +M: Gage Eads <gage.eads@intel.com>
> +M: Olivier Matz <olivier.matz@6wind.com>
> +F: lib/librte_stack/
> +F: doc/guides/prog_guide/stack_lib.rst
> +
> 
>  Memory Pool Drivers
>  -------------------
> diff --git a/config/common_base b/config/common_base index
> 0b09a9348..1b45dea6c 100644
> --- a/config/common_base
> +++ b/config/common_base
> @@ -980,3 +980,8 @@ CONFIG_RTE_APP_CRYPTO_PERF=y  # Compile the
> eventdev application  #  CONFIG_RTE_APP_EVENTDEV=y
> +
> +#
> +# Compile librte_stack
> +#
> +CONFIG_RTE_LIBRTE_STACK=y
> diff --git a/doc/api/doxy-api-index.md b/doc/api/doxy-api-index.md index
> d95ad566c..0df8848c0 100644
> --- a/doc/api/doxy-api-index.md
> +++ b/doc/api/doxy-api-index.md
> @@ -124,6 +124,7 @@ The public API headers are grouped by topics:
>    [mbuf]               (@ref rte_mbuf.h),
>    [mbuf pool ops]      (@ref rte_mbuf_pool_ops.h),
>    [ring]               (@ref rte_ring.h),
> +  [stack]              (@ref rte_stack.h),
>    [tailq]              (@ref rte_tailq.h),
>    [bitmap]             (@ref rte_bitmap.h)
> 
> diff --git a/doc/api/doxy-api.conf.in b/doc/api/doxy-api.conf.in index
> a365e669b..7722fc3e9 100644
> --- a/doc/api/doxy-api.conf.in
> +++ b/doc/api/doxy-api.conf.in
> @@ -55,6 +55,7 @@ INPUT                   = @TOPDIR@/doc/api/doxy-api-
> index.md \
>                            @TOPDIR@/lib/librte_ring \
>                            @TOPDIR@/lib/librte_sched \
>                            @TOPDIR@/lib/librte_security \
> +                          @TOPDIR@/lib/librte_stack \
>                            @TOPDIR@/lib/librte_table \
>                            @TOPDIR@/lib/librte_telemetry \
>                            @TOPDIR@/lib/librte_timer \ diff --git
> a/doc/guides/prog_guide/index.rst b/doc/guides/prog_guide/index.rst index
> 6726b1e8d..f4f60862f 100644
> --- a/doc/guides/prog_guide/index.rst
> +++ b/doc/guides/prog_guide/index.rst
> @@ -55,6 +55,7 @@ Programmer's Guide
>      metrics_lib
>      bpf_lib
>      ipsec_lib
> +    stack_lib
>      source_org
>      dev_kit_build_system
>      dev_kit_root_make_help
> diff --git a/doc/guides/prog_guide/stack_lib.rst
> b/doc/guides/prog_guide/stack_lib.rst
> new file mode 100644
> index 000000000..25a8cc38a
> --- /dev/null
> +++ b/doc/guides/prog_guide/stack_lib.rst
> @@ -0,0 +1,28 @@
> +..  SPDX-License-Identifier: BSD-3-Clause
> +    Copyright(c) 2019 Intel Corporation.
> +
> +Stack Library
> +=============
> +
> +DPDK's stack library provides an API for configuration and use of a
> +bounded stack of pointers.
> +
> +The stack library provides the following basic operations:
> +
> +*  Create a uniquely named stack of a user-specified size and using a
> +   user-specified socket.
> +
> +*  Push and pop a burst of one or more stack objects (pointers). These
> function
> +   are multi-threading safe.
> +
> +*  Free a previously created stack.
> +
> +*  Lookup a pointer to a stack by its name.
> +
> +*  Query a stack's current depth and number of free entries.
> +
> +Implementation
> +~~~~~~~~~~~~~~
> +
> +The stack consists of a contiguous array of pointers, a current index,
> +and a spinlock. Accesses to the stack are made multi-thread safe by the
> spinlock.
> diff --git a/doc/guides/rel_notes/release_19_05.rst
> b/doc/guides/rel_notes/release_19_05.rst
> index 4a3e2a7f3..8c649a954 100644
> --- a/doc/guides/rel_notes/release_19_05.rst
> +++ b/doc/guides/rel_notes/release_19_05.rst
> @@ -77,6 +77,11 @@ New Features
>    which includes the directory name, lib name, filenames, makefile, docs,
>    macros, functions, structs and any other strings in the code.
> 
> +* **Added Stack API.**
> +
> +  Added a new stack API for configuration and use of a bounded stack of
> + pointers. The API provides MT-safe push and pop operations that can
> + operate  on one or more pointers per operation.
> 
>  Removed Items
>  -------------
> diff --git a/lib/Makefile b/lib/Makefile index ffbfd0d94..d941bd849 100644
> --- a/lib/Makefile
> +++ b/lib/Makefile
> @@ -109,6 +109,8 @@ DIRS-$(CONFIG_RTE_LIBRTE_IPSEC) += librte_ipsec
> DEPDIRS-librte_ipsec := librte_eal librte_mbuf librte_cryptodev
> librte_security
>  DIRS-$(CONFIG_RTE_LIBRTE_TELEMETRY) += librte_telemetry  DEPDIRS-
> librte_telemetry := librte_eal librte_metrics librte_ethdev
> +DIRS-$(CONFIG_RTE_LIBRTE_STACK) += librte_stack DEPDIRS-librte_stack :=
> +librte_eal
> 
>  ifeq ($(CONFIG_RTE_EXEC_ENV_LINUXAPP),y)
>  DIRS-$(CONFIG_RTE_LIBRTE_KNI) += librte_kni diff --git
> a/lib/librte_stack/Makefile b/lib/librte_stack/Makefile new file mode 100644
> index 000000000..e956b6535
> --- /dev/null
> +++ b/lib/librte_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_stack.a
> +
> +CFLAGS += $(WERROR_FLAGS) -I$(SRCDIR) -O3 CFLAGS +=
> +-DALLOW_EXPERIMENTAL_API LDLIBS += -lrte_eal
> +
> +EXPORT_MAP := rte_stack_version.map
> +
> +LIBABIVER := 1
> +
> +# all source are stored in SRCS-y
> +SRCS-$(CONFIG_RTE_LIBRTE_STACK) := rte_stack.c
> +
> +# install includes
> +SYMLINK-$(CONFIG_RTE_LIBRTE_STACK)-include := rte_stack.h
> +
> +include $(RTE_SDK)/mk/rte.lib.mk
> diff --git a/lib/librte_stack/meson.build b/lib/librte_stack/meson.build new
> file mode 100644 index 000000000..99f43710e
> --- /dev/null
> +++ b/lib/librte_stack/meson.build
> @@ -0,0 +1,8 @@
> +# SPDX-License-Identifier: BSD-3-Clause # Copyright(c) 2019 Intel
> +Corporation
> +
> +allow_experimental_apis = true
> +
> +version = 1
> +sources = files('rte_stack.c')
> +headers = files('rte_stack.h')
> diff --git a/lib/librte_stack/rte_stack.c b/lib/librte_stack/rte_stack.c new file
> mode 100644 index 000000000..96dffdf44
> --- /dev/null
> +++ b/lib/librte_stack/rte_stack.c
> @@ -0,0 +1,194 @@
> +/* SPDX-License-Identifier: BSD-3-Clause
> + * Copyright(c) 2019 Intel Corporation
> + */
> +
> +#include <string.h>
> +
> +#include <rte_atomic.h>
> +#include <rte_eal.h>
> +#include <rte_eal_memconfig.h>
> +#include <rte_errno.h>
> +#include <rte_malloc.h>
> +#include <rte_memzone.h>
> +#include <rte_rwlock.h>
> +#include <rte_tailq.h>
> +
> +#include "rte_stack.h"
> +#include "rte_stack_pvt.h"
> +
> +int stack_logtype;
> +
> +TAILQ_HEAD(rte_stack_list, rte_tailq_entry);
> +
> +static struct rte_tailq_elem rte_stack_tailq = {
> +	.name = RTE_TAILQ_STACK_NAME,
> +};
> +EAL_REGISTER_TAILQ(rte_stack_tailq)
> +
> +static void
> +rte_stack_std_init(struct rte_stack *s) {
> +	rte_spinlock_init(&s->stack_std.lock);
> +}
> +
> +static void
> +rte_stack_init(struct rte_stack *s)
> +{
> +	memset(s, 0, sizeof(*s));
> +
> +	rte_stack_std_init(s);
> +}
> +
> +static ssize_t
> +rte_stack_get_memsize(unsigned int count) {
> +	ssize_t sz = sizeof(struct rte_stack);
> +
> +	/* Add padding to avoid false sharing conflicts */
> +	sz += RTE_CACHE_LINE_ROUNDUP(count * sizeof(void *)) +
> +		2 * RTE_CACHE_LINE_SIZE;
I did not understand how the false sharing is caused and how this padding is solving the issue. Verbose comments would help.

> +
> +	return sz;
> +}
> +
> +struct rte_stack *
> +rte_stack_create(const char *name, unsigned int count, int socket_id,
> +		 uint32_t flags)
> +{
> +	char mz_name[RTE_MEMZONE_NAMESIZE];
> +	struct rte_stack_list *stack_list;
> +	const struct rte_memzone *mz;
> +	struct rte_tailq_entry *te;
> +	struct rte_stack *s;
> +	unsigned int sz;
> +	int ret;
> +
> +	RTE_SET_USED(flags);
> +
> +	sz = rte_stack_get_memsize(count);
> +
> +	ret = snprintf(mz_name, sizeof(mz_name), "%s%s",
> +		       RTE_STACK_MZ_PREFIX, name);
> +	if (ret < 0 || ret >= (int)sizeof(mz_name)) {
> +		rte_errno = ENAMETOOLONG;
> +		return NULL;
> +	}
> +
> +	te = rte_zmalloc("STACK_TAILQ_ENTRY", sizeof(*te), 0);
> +	if (te == NULL) {
> +		STACK_LOG_ERR("Cannot reserve memory for tailq\n");
> +		rte_errno = ENOMEM;
> +		return NULL;
> +	}
> +
> +	rte_rwlock_write_lock(RTE_EAL_TAILQ_RWLOCK);
> +
I think there is a need to check if a stack with the same name exists already.

> +	mz = rte_memzone_reserve_aligned(mz_name, sz, socket_id,
> +					 0, __alignof__(*s));
> +	if (mz == NULL) {
> +		STACK_LOG_ERR("Cannot reserve stack memzone!\n");
> +		rte_rwlock_write_unlock(RTE_EAL_TAILQ_RWLOCK);
> +		rte_free(te);
> +		return NULL;
> +	}
> +
> +	s = mz->addr;
> +
> +	rte_stack_init(s);
> +
> +	/* Store the name for later lookups */
> +	ret = snprintf(s->name, sizeof(s->name), "%s", name);
> +	if (ret < 0 || ret >= (int)sizeof(s->name)) {
> +		rte_rwlock_write_unlock(RTE_EAL_TAILQ_RWLOCK);
> +
> +		rte_errno = ENAMETOOLONG;
> +		rte_free(te);
> +		rte_memzone_free(mz);
> +		return NULL;
> +	}
> +
> +	s->memzone = mz;
> +	s->capacity = count;
> +	s->flags = flags;
> +
> +	te->data = s;
> +
> +	stack_list = RTE_TAILQ_CAST(rte_stack_tailq.head, rte_stack_list);
> +
> +	TAILQ_INSERT_TAIL(stack_list, te, next);
> +
> +	rte_rwlock_write_unlock(RTE_EAL_TAILQ_RWLOCK);
> +
> +	return s;
> +}
> +
> +void
> +rte_stack_free(struct rte_stack *s)
> +{
> +	struct rte_stack_list *stack_list;
> +	struct rte_tailq_entry *te;
> +
> +	if (s == NULL)
> +		return;
> +
Adding a check to make sure the length of the stack is 0 would help catch issues?

> +	stack_list = RTE_TAILQ_CAST(rte_stack_tailq.head, rte_stack_list);
> +	rte_rwlock_write_lock(RTE_EAL_TAILQ_RWLOCK);
> +
> +	/* find out tailq entry */
> +	TAILQ_FOREACH(te, stack_list, next) {
> +		if (te->data == s)
> +			break;
> +	}
> +
> +	if (te == NULL) {
> +		rte_rwlock_write_unlock(RTE_EAL_TAILQ_RWLOCK);
> +		return;
> +	}
> +
> +	TAILQ_REMOVE(stack_list, te, next);
> +
> +	rte_rwlock_write_unlock(RTE_EAL_TAILQ_RWLOCK);
> +
> +	rte_free(te);
> +
> +	rte_memzone_free(s->memzone);
> +}
> +
> +struct rte_stack *
> +rte_stack_lookup(const char *name)
> +{
> +	struct rte_stack_list *stack_list;
> +	struct rte_tailq_entry *te;
> +	struct rte_stack *r = NULL;
> +
> +	if (name == NULL) {
> +		rte_errno = EINVAL;
> +		return NULL;
> +	}
> +
> +	stack_list = RTE_TAILQ_CAST(rte_stack_tailq.head, rte_stack_list);
> +
> +	rte_rwlock_read_lock(RTE_EAL_TAILQ_RWLOCK);
> +
> +	TAILQ_FOREACH(te, stack_list, next) {
> +		r = (struct rte_stack *) te->data;
> +		if (strncmp(name, r->name, RTE_STACK_NAMESIZE) == 0)
> +			break;
> +	}
> +
> +	rte_rwlock_read_unlock(RTE_EAL_TAILQ_RWLOCK);
> +
> +	if (te == NULL) {
> +		rte_errno = ENOENT;
> +		return NULL;
> +	}
> +
> +	return r;
> +}
> +
> +RTE_INIT(librte_stack_init_log)
> +{
> +	stack_logtype = rte_log_register("lib.stack");
> +	if (stack_logtype >= 0)
> +		rte_log_set_level(stack_logtype, RTE_LOG_NOTICE); }
> diff --git a/lib/librte_stack/rte_stack.h b/lib/librte_stack/rte_stack.h new file
> mode 100644 index 000000000..7a633deb5
> --- /dev/null
> +++ b/lib/librte_stack/rte_stack.h
> @@ -0,0 +1,274 @@
> +/* SPDX-License-Identifier: BSD-3-Clause
> + * Copyright(c) 2019 Intel Corporation
> + */
> +
> +/**
> + * @file rte_stack.h
> + * @b EXPERIMENTAL: this API may change without prior notice
> + *
> + * RTE Stack
> + *
> + * librte_stack provides an API for configuration and use of a bounded
> +stack of
> + * pointers. Push and pop operations are MT-safe, allowing concurrent
> +access,
> + * and the interface supports pushing and popping multiple pointers at a
> time.
> + */
> +
> +#ifndef _RTE_STACK_H_
> +#define _RTE_STACK_H_
> +
> +#ifdef __cplusplus
> +extern "C" {
> +#endif
> +
> +#include <rte_errno.h>
> +#include <rte_memzone.h>
> +#include <rte_spinlock.h>
> +
> +#define RTE_TAILQ_STACK_NAME "RTE_STACK"
> +#define RTE_STACK_MZ_PREFIX "STK_"
Nit, "STACK_" would be easier to debug

> +/** The maximum length of a stack name. */ #define RTE_STACK_NAMESIZE
> +(RTE_MEMZONE_NAMESIZE - \
> +			   sizeof(RTE_STACK_MZ_PREFIX) + 1)
> +
> +/* Structure containing the LIFO, its current length, and a lock for
> +mutual
> + * exclusion.
> + */
> +struct rte_stack_std {
> +	rte_spinlock_t lock; /**< LIFO lock */
> +	uint32_t len; /**< LIFO len */
> +	void *objs[]; /**< LIFO pointer table */ };
> +
> +/* The RTE stack structure contains the LIFO structure itself, plus
> +metadata
> + * such as its name and memzone pointer.
> + */
> +struct rte_stack {
> +	/** Name of the stack. */
> +	char name[RTE_STACK_NAMESIZE] __rte_cache_aligned;
> +	/** Memzone containing the rte_stack structure. */
> +	const struct rte_memzone *memzone;
> +	uint32_t capacity; /**< Usable size of the stack. */
> +	uint32_t flags; /**< Flags supplied at creation. */
> +	struct rte_stack_std stack_std; /**< LIFO structure. */ }
> +__rte_cache_aligned;
> +
> +/**
> + * @internal Push several objects on the stack (MT-safe).
> + *
> + * @param s
> + *   A pointer to the stack structure.
> + * @param obj_table
> + *   A pointer to a table of void * pointers (objects).
> + * @param n
> + *   The number of objects to push on the stack from the obj_table.
> + * @return
> + *   Actual number of objects pushed (either 0 or *n*).
> + */
> +static __rte_always_inline unsigned int __rte_experimental
This is an internal function. Is '__rte_experimental' tag required?

> +rte_stack_std_push(struct rte_stack *s, void * const *obj_table,
> +unsigned int n) {
Since this is an internal function, does it make sense to add '__' to the beginning of the function name (similar to what is done in rte_ring?).

> +	struct rte_stack_std *stack = &s->stack_std;
> +	unsigned int index;
> +	void **cache_objs;
> +
> +	rte_spinlock_lock(&stack->lock);
> +	cache_objs = &stack->objs[stack->len];
> +
> +	/* Is there sufficient space in the stack? */
> +	if ((stack->len + n) > s->capacity) {
> +		rte_spinlock_unlock(&stack->lock);
> +		return 0;
> +	}
> +
> +	/* Add elements back into the cache */
> +	for (index = 0; index < n; ++index, obj_table++)
> +		cache_objs[index] = *obj_table;
> +
> +	stack->len += n;
> +
> +	rte_spinlock_unlock(&stack->lock);
> +	return n;
> +}
> +
> +/**
> + * @warning
> + * @b EXPERIMENTAL: this API may change without prior notice
> + *
> + * Push several objects on the stack (MT-safe).
> + *
> + * @param s
> + *   A pointer to the stack structure.
> + * @param obj_table
> + *   A pointer to a table of void * pointers (objects).
> + * @param n
> + *   The number of objects to push on the stack from the obj_table.
> + * @return
> + *   Actual number of objects pushed (either 0 or *n*).
> + */
> +static __rte_always_inline unsigned int __rte_experimental
> +rte_stack_push(struct rte_stack *s, void * const *obj_table, unsigned
> +int n) {
> +	return rte_stack_std_push(s, obj_table, n); }
> +
> +/**
> + * @internal Pop several objects from the stack (MT-safe).
> + *
> + * @param s
> + *   A pointer to the stack structure.
> + * @param obj_table
> + *   A pointer to a table of void * pointers (objects).
> + * @param n
> + *   The number of objects to pull from the stack.
> + * @return
> + *   Actual number of objects popped (either 0 or *n*).
> + */
> +static __rte_always_inline unsigned int __rte_experimental
This is an internal function. Is '__rte_experimental' tag required?

> +rte_stack_std_pop(struct rte_stack *s, void **obj_table, unsigned int
> +n) {
> +	struct rte_stack_std *stack = &s->stack_std;
> +	unsigned int index, len;
> +	void **cache_objs;
> +
> +	rte_spinlock_lock(&stack->lock);
> +
> +	if (unlikely(n > stack->len)) {
> +		rte_spinlock_unlock(&stack->lock);
> +		return 0;
> +	}
> +
> +	cache_objs = stack->objs;
> +
> +	for (index = 0, len = stack->len - 1; index < n;
> +			++index, len--, obj_table++)
> +		*obj_table = cache_objs[len];
> +
> +	stack->len -= n;
> +	rte_spinlock_unlock(&stack->lock);
> +
> +	return n;
> +}
> +
> +/**
> + * @warning
> + * @b EXPERIMENTAL: this API may change without prior notice
> + *
> + * Pop several objects from the stack (MT-safe).
> + *
> + * @param s
> + *   A pointer to the stack structure.
> + * @param obj_table
> + *   A pointer to a table of void * pointers (objects).
> + * @param n
> + *   The number of objects to pull from the stack.
> + * @return
> + *   Actual number of objects popped (either 0 or *n*).
> + */
> +static __rte_always_inline unsigned int __rte_experimental
> +rte_stack_pop(struct rte_stack *s, void **obj_table, unsigned int n) {
> +	if (unlikely(n == 0 || obj_table == NULL))
> +		return 0;
's == NULL' can be added as well. Similar check is missing in 'rte_stack_push'. Since these are data-path APIs, RTE_ASSERT would be better.

> +
> +	return rte_stack_std_pop(s, obj_table, n); }
> +
> +/**
> + * @warning
> + * @b EXPERIMENTAL: this API may change without prior notice
> + *
> + * Return the number of used entries in a stack.
> + *
> + * @param s
> + *   A pointer to the stack structure.
> + * @return
> + *   The number of used entries in the stack.
> + */
> +static __rte_always_inline unsigned int __rte_experimental
> +rte_stack_count(struct rte_stack *s) {
> +	return (unsigned int)s->stack_std.len; }
> +
> +/**
> + * @warning
> + * @b EXPERIMENTAL: this API may change without prior notice
> + *
> + * Return the number of free entries in a stack.
> + *
> + * @param s
> + *   A pointer to the stack structure.
> + * @return
> + *   The number of free entries in the stack.
> + */
> +static __rte_always_inline unsigned int __rte_experimental
> +rte_stack_free_count(struct rte_stack *s) {
> +	return s->capacity - rte_stack_count(s); }
> +
> +/**
> + * @warning
> + * @b EXPERIMENTAL: this API may change without prior notice
> + *
> + * Create a new stack named *name* in memory.
> + *
> + * This function uses ``memzone_reserve()`` to allocate memory for a
> +stack of
> + * size *count*. The behavior of the stack is controlled by the *flags*.
> + *
> + * @param name
> + *   The name of the stack.
> + * @param count
> + *   The size of the stack.
> + * @param socket_id
> + *   The *socket_id* argument is the socket identifier in case of
> + *   NUMA. The value can be *SOCKET_ID_ANY* if there is no NUMA
> + *   constraint for the reserved zone.
> + * @param flags
> + *   Reserved for future use.
> + * @return
> + *   On success, the pointer to the new allocated stack. NULL on error with
> + *    rte_errno set appropriately. Possible errno values include:
> + *    - ENOSPC - the maximum number of memzones has already been
> allocated
> + *    - EEXIST - a stack with the same name already exists
This is not implemented currently

> + *    - ENOMEM - insufficient memory to create the stack
> + *    - ENAMETOOLONG - name size exceeds RTE_STACK_NAMESIZE
> + */
> +struct rte_stack *__rte_experimental
> +rte_stack_create(const char *name, unsigned int count, int socket_id,
> +		 uint32_t flags);
> +
> +/**
> + * @warning
> + * @b EXPERIMENTAL: this API may change without prior notice
> + *
> + * Free all memory used by the stack.
> + *
> + * @param s
> + *   Stack to free
> + */
> +void __rte_experimental
> +rte_stack_free(struct rte_stack *s);
> +
> +/**
> + * @warning
> + * @b EXPERIMENTAL: this API may change without prior notice
> + *
> + * Lookup a stack by its name.
> + *
> + * @param name
> + *   The name of the stack.
> + * @return
> + *   The pointer to the stack matching the name, or NULL if not found,
> + *   with rte_errno set appropriately. Possible rte_errno values include:
> + *    - ENOENT - Stack with name *name* not found.
> + *    - EINVAL - *name* pointer is NULL.
> + */
> +struct rte_stack * __rte_experimental
> +rte_stack_lookup(const char *name);
> +
> +#ifdef __cplusplus
> +}
> +#endif
> +
> +#endif /* _RTE_STACK_H_ */
> diff --git a/lib/librte_stack/rte_stack_pvt.h b/lib/librte_stack/rte_stack_pvt.h
> new file mode 100644
> index 000000000..4a6a7bdb3
> --- /dev/null
> +++ b/lib/librte_stack/rte_stack_pvt.h
> @@ -0,0 +1,34 @@
> +/* SPDX-License-Identifier: BSD-3-Clause
> + * Copyright(c) 2019 Intel Corporation
> + */
> +
> +#ifndef _RTE_STACK_PVT_H_
> +#define _RTE_STACK_PVT_H_
> +
> +#ifdef __cplusplus
> +extern "C" {
> +#endif
> +
> +#include <rte_log.h>
> +
> +extern int stack_logtype;
> +
> +#define STACK_LOG(level, fmt, args...) \
> +	rte_log(RTE_LOG_ ##level, stack_logtype, "%s(): "fmt "\n", \
> +		__func__, ##args)
> +
> +#define STACK_LOG_ERR(fmt, args...) \
> +	STACK_LOG(ERR, fmt, ## args)
> +
> +#define STACK_LOG_WARN(fmt, args...) \
> +	STACK_LOG(WARNING, fmt, ## args)
> +
> +#define STACK_LOG_INFO(fmt, args...) \
> +	STACK_LOG(INFO, fmt, ## args)
> +
> +
> +#ifdef __cplusplus
> +}
> +#endif
> +
> +#endif /* _RTE_STACK_PVT_H_ */
> diff --git a/lib/librte_stack/rte_stack_version.map
> b/lib/librte_stack/rte_stack_version.map
> new file mode 100644
> index 000000000..6662679c3
> --- /dev/null
> +++ b/lib/librte_stack/rte_stack_version.map
> @@ -0,0 +1,9 @@
> +EXPERIMENTAL {
> +	global:
> +
> +	rte_stack_create;
> +	rte_stack_free;
> +	rte_stack_lookup;
> +
> +	local: *;
> +};
> diff --git a/lib/meson.build b/lib/meson.build index 99957ba7d..90115477f
> 100644
> --- a/lib/meson.build
> +++ b/lib/meson.build
> @@ -22,7 +22,7 @@ libraries = [
>  	'gro', 'gso', 'ip_frag', 'jobstats',
>  	'kni', 'latencystats', 'lpm', 'member',
>  	'power', 'pdump', 'rawdev',
> -	'reorder', 'sched', 'security', 'vhost',
> +	'reorder', 'sched', 'security', 'stack', 'vhost',
>  	#ipsec lib depends on crypto and security
>  	'ipsec',
>  	# add pkt framework libs which use other libs from above diff --git
> a/mk/rte.app.mk b/mk/rte.app.mk index 3c40f9df2..8decfb851 100644
> --- a/mk/rte.app.mk
> +++ b/mk/rte.app.mk
> @@ -87,6 +87,7 @@ _LDLIBS-$(CONFIG_RTE_LIBRTE_SECURITY)       += -
> lrte_security
>  _LDLIBS-$(CONFIG_RTE_LIBRTE_COMPRESSDEV)    += -lrte_compressdev
>  _LDLIBS-$(CONFIG_RTE_LIBRTE_EVENTDEV)       += -lrte_eventdev
>  _LDLIBS-$(CONFIG_RTE_LIBRTE_RAWDEV)         += -lrte_rawdev
> +_LDLIBS-$(CONFIG_RTE_LIBRTE_STACK)          += -lrte_stack
>  _LDLIBS-$(CONFIG_RTE_LIBRTE_TIMER)          += -lrte_timer
>  _LDLIBS-$(CONFIG_RTE_LIBRTE_MEMPOOL)        += -lrte_mempool
>  _LDLIBS-$(CONFIG_RTE_DRIVER_MEMPOOL_RING)   += -lrte_mempool_ring
> --
> 2.13.6
  

@Thomas: I expect I can address Honnappa's feedback within a day or two. Since today is the 19.05 merge deadline, what do you think about these options for merging?
1. Merge V4 now and address these comments during RC1.
2. Delay merge until RC2, with all comments addressed.

In terms of risk, Honnappa identified an incorrect memory ordering argument (patch 6/8), but that doesn't affect the one platform (x86-64) that can (currently) use this library. His other comments address readability, error-checking, and performance, but aren't critical.  Beyond that, this patchset is isolated from the rest of DPDK. So, I think the risk to the project is very low.

(Also, note that I accidentally left off Olivier's Reviewed-by tag in V4's patches 1, 3, 5, and 6 -- I'll address that as well)

> -----Original Message-----
> From: Honnappa Nagarahalli [mailto:Honnappa.Nagarahalli@arm.com]
> Sent: Thursday, March 28, 2019 6:27 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>; thomas@monjalon.net; nd
> <nd@arm.com>
> Subject: RE: [PATCH v3 1/8] stack: introduce rte stack library
> 
> Hi Gage,
> 	Apologies for the late comments.
> 

No problem, I appreciate the feedback.

[snip]

> > +static ssize_t
> > +rte_stack_get_memsize(unsigned int count) {
> > +	ssize_t sz = sizeof(struct rte_stack);
> > +
> > +	/* Add padding to avoid false sharing conflicts */
> > +	sz += RTE_CACHE_LINE_ROUNDUP(count * sizeof(void *)) +
> > +		2 * RTE_CACHE_LINE_SIZE;
> I did not understand how the false sharing is caused and how this padding is
> solving the issue. Verbose comments would help.

The additional padding (beyond the CACHE_LINE_ROUNDUP) is to prevent false sharing caused by adjacent/next-line hardware prefetchers. I'll address this.

[snip]

> > +struct rte_stack *
> > +rte_stack_create(const char *name, unsigned int count, int socket_id,
> > +		 uint32_t flags)
> > +{
> > +	char mz_name[RTE_MEMZONE_NAMESIZE];
> > +	struct rte_stack_list *stack_list;
> > +	const struct rte_memzone *mz;
> > +	struct rte_tailq_entry *te;
> > +	struct rte_stack *s;
> > +	unsigned int sz;
> > +	int ret;
> > +
> > +	RTE_SET_USED(flags);
> > +
> > +	sz = rte_stack_get_memsize(count);
> > +
> > +	ret = snprintf(mz_name, sizeof(mz_name), "%s%s",
> > +		       RTE_STACK_MZ_PREFIX, name);
> > +	if (ret < 0 || ret >= (int)sizeof(mz_name)) {
> > +		rte_errno = ENAMETOOLONG;
> > +		return NULL;
> > +	}
> > +
> > +	te = rte_zmalloc("STACK_TAILQ_ENTRY", sizeof(*te), 0);
> > +	if (te == NULL) {
> > +		STACK_LOG_ERR("Cannot reserve memory for tailq\n");
> > +		rte_errno = ENOMEM;
> > +		return NULL;
> > +	}
> > +
> > +	rte_rwlock_write_lock(RTE_EAL_TAILQ_RWLOCK);
> > +
> I think there is a need to check if a stack with the same name exists already.

rte_memzone_reserve_aligned() does just that. This behavior is tested in the function test_stack_name_reuse(), added in commit " test/stack: add stack test".

> > +	mz = rte_memzone_reserve_aligned(mz_name, sz, socket_id,
> > +					 0, __alignof__(*s));
> > +	if (mz == NULL) {
> > +		STACK_LOG_ERR("Cannot reserve stack memzone!\n");
> > +		rte_rwlock_write_unlock(RTE_EAL_TAILQ_RWLOCK);
> > +		rte_free(te);
> > +		return NULL;
> > +	}

[snip]

> > +void
> > +rte_stack_free(struct rte_stack *s)
> > +{
> > +	struct rte_stack_list *stack_list;
> > +	struct rte_tailq_entry *te;
> > +
> > +	if (s == NULL)
> > +		return;
> > +
> Adding a check to make sure the length of the stack is 0 would help catch
> issues?

My preference is to leave that check to the user, for any apps that want to/can safely free non-empty stacks.

[snip]

> > +#define RTE_TAILQ_STACK_NAME "RTE_STACK"
> > +#define RTE_STACK_MZ_PREFIX "STK_"
> Nit, "STACK_" would be easier to debug

Since RTE_MEMZONE_NAMESIZE (32) doesn't give us a lot of space, I kept the prefix short. Adding 2 more characters *probably* won't make a difference...but I'd prefer the shortened name.

> > +/** The maximum length of a stack name. */ #define
> RTE_STACK_NAMESIZE
> > +(RTE_MEMZONE_NAMESIZE - \
> > +			   sizeof(RTE_STACK_MZ_PREFIX) + 1)
> > +

[snip]

> > +/**
> > + * @internal Push several objects on the stack (MT-safe).
> > + *
> > + * @param s
> > + *   A pointer to the stack structure.
> > + * @param obj_table
> > + *   A pointer to a table of void * pointers (objects).
> > + * @param n
> > + *   The number of objects to push on the stack from the obj_table.
> > + * @return
> > + *   Actual number of objects pushed (either 0 or *n*).
> > + */
> > +static __rte_always_inline unsigned int __rte_experimental
> This is an internal function. Is '__rte_experimental' tag required?

I don't think so, but I erred on the side of caution. I don't think the tag causes any problems.

> 
> > +rte_stack_std_push(struct rte_stack *s, void * const *obj_table,
> > +unsigned int n) {
> Since this is an internal function, does it make sense to add '__' to the
> beginning of the function name (similar to what is done in rte_ring?).

Makes sense. I'll address this.

[snip]

> > +/**
> > + * @internal Pop several objects from the stack (MT-safe).
> > + *
> > + * @param s
> > + *   A pointer to the stack structure.
> > + * @param obj_table
> > + *   A pointer to a table of void * pointers (objects).
> > + * @param n
> > + *   The number of objects to pull from the stack.
> > + * @return
> > + *   Actual number of objects popped (either 0 or *n*).
> > + */
> > +static __rte_always_inline unsigned int __rte_experimental
> This is an internal function. Is '__rte_experimental' tag required?

(see above)

[snip]

> > +static __rte_always_inline unsigned int __rte_experimental
> > +rte_stack_pop(struct rte_stack *s, void **obj_table, unsigned int n) {
> > +	if (unlikely(n == 0 || obj_table == NULL))
> > +		return 0;
> 's == NULL' can be added as well. Similar check is missing in 'rte_stack_push'.
> Since these are data-path APIs, RTE_ASSERT would be better.
> 

Good point. I'll add RTE_ASSERT for obj_table and s. That won't work for  "n == 0" -- the pop code assumes n > 0, so we can't allow that check to be compiled out.

[snip]

> > +/**
> > + * @warning
> > + * @b EXPERIMENTAL: this API may change without prior notice
> > + *
> > + * Create a new stack named *name* in memory.
> > + *
> > + * This function uses ``memzone_reserve()`` to allocate memory for a
> > +stack of
> > + * size *count*. The behavior of the stack is controlled by the *flags*.
> > + *
> > + * @param name
> > + *   The name of the stack.
> > + * @param count
> > + *   The size of the stack.
> > + * @param socket_id
> > + *   The *socket_id* argument is the socket identifier in case of
> > + *   NUMA. The value can be *SOCKET_ID_ANY* if there is no NUMA
> > + *   constraint for the reserved zone.
> > + * @param flags
> > + *   Reserved for future use.
> > + * @return
> > + *   On success, the pointer to the new allocated stack. NULL on error with
> > + *    rte_errno set appropriately. Possible errno values include:
> > + *    - ENOSPC - the maximum number of memzones has already been
> > allocated
> > + *    - EEXIST - a stack with the same name already exists
> This is not implemented currently

It is -- see above.

Thanks,
Gage
  

29/03/2019 20:23, Eads, Gage:
> @Thomas: I expect I can address Honnappa's feedback within a day or two. Since today is the 19.05 merge deadline, what do you think about these options for merging?
> 1. Merge V4 now and address these comments during RC1.
> 2. Delay merge until RC2, with all comments addressed.

I plan to release RC1 on Wednesday,
allowing last revision to be sent on Tuesday.

If it does not impact the rest of DPDK, the RC2 is also an option
to consider.
  

> 
> > > +static ssize_t
> > > +rte_stack_get_memsize(unsigned int count) {
> > > +	ssize_t sz = sizeof(struct rte_stack);
> > > +
> > > +	/* Add padding to avoid false sharing conflicts */
> > > +	sz += RTE_CACHE_LINE_ROUNDUP(count * sizeof(void *)) +
> > > +		2 * RTE_CACHE_LINE_SIZE;
> > I did not understand how the false sharing is caused and how this
> > padding is solving the issue. Verbose comments would help.
> 
> The additional padding (beyond the CACHE_LINE_ROUNDUP) is to prevent
> false sharing caused by adjacent/next-line hardware prefetchers. I'll address
> this.
> 
Is it not a generic problem? Or is it specific to this library?
  

> -----Original Message-----
> From: Honnappa Nagarahalli [mailto:Honnappa.Nagarahalli@arm.com]
> Sent: Monday, April 1, 2019 12:41 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>; thomas@monjalon.net; nd
> <nd@arm.com>
> Subject: RE: [PATCH v3 1/8] stack: introduce rte stack library
> 
> >
> > > > +static ssize_t
> > > > +rte_stack_get_memsize(unsigned int count) {
> > > > +	ssize_t sz = sizeof(struct rte_stack);
> > > > +
> > > > +	/* Add padding to avoid false sharing conflicts */
> > > > +	sz += RTE_CACHE_LINE_ROUNDUP(count * sizeof(void *)) +
> > > > +		2 * RTE_CACHE_LINE_SIZE;
> > > I did not understand how the false sharing is caused and how this
> > > padding is solving the issue. Verbose comments would help.
> >
> > The additional padding (beyond the CACHE_LINE_ROUNDUP) is to prevent
> > false sharing caused by adjacent/next-line hardware prefetchers. I'll
> > address this.
> >
> Is it not a generic problem? Or is it specific to this library?

This is not limited to this library, but it only affects systems with (enabled) next-line prefetchers, for example Intel products with an L2 adjacent cache line prefetcher[1]. For those systems, additional padding can potentially improve performance. As I understand it, this was the reason behind the 128B alignment added to rte_ring a couple years ago[2].

[1] https://software.intel.com/en-us/articles/disclosure-of-hw-prefetcher-control-on-some-intel-processors
[2] http://mails.dpdk.org/archives/dev/2017-February/058613.html