Re: [dpdk-dev] [PATCH v6 1/2] eal/ticketlock: ticket based to improve fairness

["Gavin Hu (Arm Technology China)" <Gavin.Hu@arm.com>]

Hi Konstantin, 

> -----Original Message-----
> From: Ananyev, Konstantin <konstantin.ananyev@intel.com>
> Sent: Friday, March 15, 2019 8:56 PM
> To: Joyce Kong (Arm Technology China) <Joyce.Kong@arm.com>;
> dev@dpdk.org
> Cc: nd <nd@arm.com>; stephen@networkplumber.org;
> jerin.jacob@caviumnetworks.com; thomas@monjalon.net; Honnappa
> Nagarahalli <Honnappa.Nagarahalli@arm.com>; Gavin Hu (Arm
> Technology China) <Gavin.Hu@arm.com>
> Subject: RE: [dpdk-dev] [PATCH v6 1/2] eal/ticketlock: ticket based to
> improve fairness
> 
> Hi,
> 
> > diff --git a/lib/librte_eal/common/include/generic/rte_ticketlock.h
> b/lib/librte_eal/common/include/generic/rte_ticketlock.h
> > new file mode 100644
> > index 0000000..d63aaaa
> > --- /dev/null
> > +++ b/lib/librte_eal/common/include/generic/rte_ticketlock.h
> > @@ -0,0 +1,308 @@
> > +/* SPDX-License-Identifier: BSD-3-Clause
> > + * Copyright(c) 2019 Arm Limited
> > + */
> > +
> > +#ifndef _RTE_TICKETLOCK_H_
> > +#define _RTE_TICKETLOCK_H_
> > +
> > +/**
> > + * @file
> > + *
> > + * RTE ticket locks
> > + *
> > + * This file defines an API for ticket locks, which give each waiting
> > + * thread a ticket and take the lock one by one, first come, first
> > + * serviced.
> > + *
> > + * All locks must be initialised before use, and only initialised once.
> > + *
> > + */
> > +
> > +#ifdef __cplusplus
> > +extern "C" {
> > +#endif
> > +
> > +#include <rte_common.h>
> > +#include <rte_lcore.h>
> > +#include <rte_pause.h>
> > +
> > +/**
> > + * The rte_ticketlock_t type.
> > + */
> > +typedef struct {
> > +	uint16_t current;
> > +	uint16_t next;
> > +} rte_ticketlock_t;
> > +
> > +/**
> > + * A static ticketlock initializer.
> > + */
> > +#define RTE_TICKETLOCK_INITIALIZER { 0 }
> > +
> > +/**
> > + * Initialize the ticketlock to an unlocked state.
> > + *
> > + * @param tl
> > + *   A pointer to the ticketlock.
> > + */
> > +static inline __rte_experimental void
> > +rte_ticketlock_init(rte_ticketlock_t *tl)
> > +{
> > +	__atomic_store_n(&tl->current, 0, __ATOMIC_RELAXED);
> > +	__atomic_store_n(&tl->next, 0, __ATOMIC_RELAXED);
> > +}
> > +
> > +/**
> > + * Take the ticketlock.
> > + *
> > + * @param tl
> > + *   A pointer to the ticketlock.
> > + */
> > +static inline __rte_experimental void
> > +rte_ticketlock_lock(rte_ticketlock_t *tl)
> > +{
> > +	uint16_t me = __atomic_fetch_add(&tl->next, 1,
> __ATOMIC_RELAXED);
> > +	while (__atomic_load_n(&tl->current, __ATOMIC_ACQUIRE) != me)
> > +		rte_pause();
> > +}
> > +
> > +/**
> > + * Release the ticketlock.
> > + *
> > + * @param tl
> > + *   A pointer to the ticketlock.
> > + */
> > +static inline __rte_experimental void
> > +rte_ticketlock_unlock(rte_ticketlock_t *tl)
> > +{
> > +	uint16_t i = __atomic_load_n(&tl->current, __ATOMIC_RELAXED);
> > +	__atomic_store_n(&tl->current, i+1, __ATOMIC_RELEASE);
> > +}
> > +
> > +/**
> > + * Try to take the lock.
> > + *
> > + * @param tl
> > + *   A pointer to the ticketlock.
> > + * @return
> > + *   1 if the lock is successfully taken; 0 otherwise.
> > + */
> > +static inline __rte_experimental int
> > +rte_ticketlock_trylock(rte_ticketlock_t *tl)
> > +{
> > +	uint16_t next = __atomic_load_n(&tl->next, __ATOMIC_RELAXED);
> > +	uint16_t cur = __atomic_load_n(&tl->current, __ATOMIC_RELAXED);
> > +	if (next == cur) {
> 
> Probably a naïve one:
> Suppose next==cur==1 here, then this thread will experience really long
> context switch,

By saying context switch, do you mean running to here, it is out of CPU time and starving for CPU? 

> so next time it continues its execution tl->next value will wrap-up and will
> be 1 again, and tl->current==0 (lock held).
> I suppose this function will set tl->next=2 and will return a success?

If this thread was swapped out and another thread took/attempted to take the lock, yes, tl->next == 2 here,
But as next == 1 unchanged, so it would not return a success. 

> Wouldn't be better here and in _is_locked_ to do load/store for
> next/current values in one go
> (using 32bit op)?
> Konstantin

To load both in one go is feasible, but no necessary as we need to compare them. 
We don't need store both as in this function tl->current is read only.
tl->next is read-update-store, I ever thought of combining the two if-statements to one __atomic_compare_exchange_n(&(&tl->next,&tl->current, tl->next+1, ...),
but tl->next+1 is out of atomicity and may be the old value and corrupt the ticket lock waiting chain. 

The current code works ok except it may fail spuriously(in case during context switch, the lock was taken and released by other threads, moving tl->next forward, in this case
The lock is available but not obtained by this trylock).  Anyway, as the name suggests, it is a try/attempt, a spurious fail is not a big deal? And in most cases, dpdk running on dedicated cores,
the context switch will not happen at all. 

Any more comments are welcome!
> 
> > +		if (__atomic_compare_exchange_n(&tl->next, &next,
> next+1,
> > +		    0, __ATOMIC_ACQUIRE, __ATOMIC_RELAXED))
> > +			return 1;
> > +	}
> > +
> > +	return 0;
> > +}
> > +
> > +/**
> > + * Test if the lock is taken.
> > + *
> > + * @param tl
> > + *   A pointer to the ticketlock.
> > + * @return
> > + *   1 if the lock icurrently taken; 0 otherwise.
> > + */
> > +static inline __rte_experimental int
> > +rte_ticketlock_is_locked(rte_ticketlock_t *tl)
> > +{
> > +	return (__atomic_load_n(&tl->current, __ATOMIC_ACQUIRE) !=
> > +		__atomic_load_n(&tl->next, __ATOMIC_ACQUIRE));
> > +}
> > +