[dpdk-dev] [PATCH v3 5/8] stack: add lock-free stack implementation

[Eads, Gage]

> -----Original Message-----
> From: Honnappa Nagarahalli [mailto:Honnappa.Nagarahalli at arm.com]
> Sent: Thursday, March 28, 2019 6:27 PM
> To: Eads, Gage <gage.eads at intel.com>; dev at dpdk.org
> Cc: olivier.matz at 6wind.com; arybchenko at solarflare.com; Richardson, Bruce
> <bruce.richardson at intel.com>; Ananyev, Konstantin
> <konstantin.ananyev at intel.com>; Gavin Hu (Arm Technology China)
> <Gavin.Hu at arm.com>; nd <nd at arm.com>; thomas at monjalon.net; nd
> <nd at arm.com>
> Subject: RE: [PATCH v3 5/8] stack: add lock-free stack implementation
> 
> <snip>
> 
> > diff --git a/lib/librte_stack/rte_stack.c
> > b/lib/librte_stack/rte_stack.c index
> > 96dffdf44..8f0361ea1 100644
> > --- a/lib/librte_stack/rte_stack.c
> > +++ b/lib/librte_stack/rte_stack.c
> 
> <snip>
> 
> > @@ -63,9 +81,16 @@ rte_stack_create(const char *name, unsigned int
> > count, int socket_id,
> >  	unsigned int sz;
> >  	int ret;
> >
> > -	RTE_SET_USED(flags);
> > +#ifdef RTE_ARCH_X86_64
> > +	RTE_BUILD_BUG_ON(sizeof(struct rte_stack_lf_head) != 16);
> This check should be independent of the platform.

Good catch. Will change the ifdef to RTE_ARCH_64.

[snip]

> > +/**
> > + * @internal Push several objects on the lock-free 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 enqueued.
> > + */
> > +static __rte_always_inline unsigned int __rte_experimental
> This is an internal function. Is '__rte_experimental' tag required? (applies to
> other instances in this patch) 

(Addressed in comments to patch 1/8)

[snip]
 
> >
> >  /**
> > @@ -225,7 +339,10 @@ rte_stack_free_count(struct rte_stack *s)
> >   *   NUMA. The value can be *SOCKET_ID_ANY* if there is no NUMA
> >   *   constraint for the reserved zone.
> >   * @param flags
> > - *   Reserved for future use.
> > + *   An OR of the following:
> > + *    - RTE_STACK_F_LF: If this flag is set, the stack uses lock-free
> > + *      variants of the push and pop functions. Otherwise, it achieves
> > + *      thread-safety using a lock.
> >   * @return
> >   *   On success, the pointer to the new allocated stack. NULL on error with
> >   *    rte_errno set appropriately. Possible errno values include:
> > diff --git a/lib/librte_stack/rte_stack_generic.h
> > b/lib/librte_stack/rte_stack_generic.h
> > new file mode 100644
> > index 000000000..5e4cbc38e
> > --- /dev/null
> > +++ b/lib/librte_stack/rte_stack_generic.h
> The name "...stack_generic.h" is confusing. It is implementing LF algorithm.
> IMO, the code should be re-organized differently.
> rte_stack.h, rte_stack.c - Contain the APIs (calling std or LF based on the flag)
> and top level structure definition rte_stack_std.c, rte_stack_std.h - Contain
> the standard implementation rte_stack_lf.c, rte_stack_lf.h - Contain the LF
> implementation rte_stack_lf_c11.h - Contain the LF C11 implementation
> 

'generic' here refers to the "generic API for atomic operations" (generic/rte_atomic.h:12), but I see how that can be misleading.

Yeah, I like this proposal, but with one tweak: use three lock-free header files: rte_stack_lf.h (common inline lock-free functions like rte_stack_lf_pop()), rte_stack_lf_c11.h (C11 implementation), rte_stack_lf_generic.h (generic atomic implementation). Since the name is *_lf_generic.h, it should be clear that it implements the lock-free functions, and this naming matches rte ring's (easier to pick up for those already used to the ring organization).

[snip]

> > +		/* old_head is updated on failure */
> > +		success = rte_atomic128_cmp_exchange(
> > +				(rte_int128_t *)&list->head,
> > +				(rte_int128_t *)&old_head,
> > +				(rte_int128_t *)&new_head,
> > +				1, __ATOMIC_ACQUIRE,
> > +				__ATOMIC_ACQUIRE);
> Just wondering if  'rte_atomic128_cmp_exchange' for x86 should have
> compiler barriers based on the memory order passed?
> C++11 memory model is getting mixed with barrier based model. I think this
> is something that needs to be discussed at a wider level.

The x86 implementation uses a compiler barrier (i.e. the inline assembly clobber list contains "memory") regardless of the memory order, so we're (conservatively) adhering to the C11 model, which guarantees ordering at both the compiler and processor levels. Whether/how we relax the x86 implementation (e.g. no compiler barrier if ordering == relaxed) is an interesting question.

Thanks,
Gage