[dpdk-dev] [PATCH v1] ticketlock: ticket based to improve fairness

[Honnappa Nagarahalli]

> Subject: [PATCH v1] ticketlock: ticket based to improve fairness
> 
> From: Joyce Kong <joyce.kong at arm.com>
> 
> The spinlock implementation is unfair, some threads may take locks
> aggressively while leaving the other threads starving for long time. As shown
> in the following test, within same period of time, there are threads taking
> locks much more times than the others.
> 
> The ticketlock gives each waiting thread a ticket and they can take the lock
> one by one, first come, first serviced, this avoids starvation for too long time
> and is more predictable.
> 
> *** spinlock_autotest without this patch *** Core [0] count = 89 Core [1]
> count = 84 Core [2] count = 94 ...
> Core [208] count = 171
> Core [209] count = 152
> Core [210] count = 161
> Core [211] count = 187
> 
> *** spinlock_autotest with this patch *** Core [0] count = 534 Core [1] count
> = 533 Core [2] count = 542 ...
> Core [208] count = 554
> Core [209] count = 556
> Core [210] count = 555
> Core [211] count = 551
> 
> Signed-off-by: Joyce Kong <joyce.kong at arm.com>
> Signed-off-by: Gavin Hu <gavin.hu at arm.com>
> ---
>  .../common/include/generic/rte_ticketlock.h        | 203
> +++++++++++++++++++++
>  lib/librte_eal/rte_eal_version.map                 |   8 +
>  2 files changed, 211 insertions(+)
>  create mode 100644 lib/librte_eal/common/include/generic/rte_ticketlock.h
> 
> 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 000000000..9d044bb31
> --- /dev/null
> +++ b/lib/librte_eal/common/include/generic/rte_ticketlock.h
> @@ -0,0 +1,203 @@
> +/* SPDX-License-Identifier: BSD-3-Clause
> + * Copyright(c) 2018-2019 Arm Corporation  */
                                                              ^^^^^^^^^^
Should be 'Limited'

> +
> +#ifndef _RTE_TICKETLOCK_H_
> +#define _RTE_TICKETLOCK_H_
> +
> +/**
> + * @file
> + *
> + * RTE ticketlocks
> + *
> + * This file defines an API for read-write locks, which are implemented
> + * in an architecture-specific way. This kind of lock simply waits in
> + * a loop repeatedly checking until the lock becomes available.
Needs update for ticket lock

> + *
> + * All locks must be initialised before use, and only initialised once.
> + *
> + */
> +
> +#include <rte_lcore.h>
> +#include <rte_common.h>
> +#include <rte_pause.h>
> +
> +/**
> + * The rte_ticketlock_t type.
> + */
> +typedef struct {
> +	uint16_t current;
> +	uint16_t next;
Any reason these are 16b?
Use 'volatile' for consistency with rte_spinlock_t? (though I do not prefer to use 'volatile' in general)

> +} 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);
> +
> +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();
> +}
Do we need to place the APIs under RTE_FORCE_INTRINSICS flag? I see that x86 has implementation which does not use intrinsics (lib/librte_eal/common/include/arch/x86/rte_spinlock.h).

> +
> +/**
> + * Release the ticketlock.
> + *
> + * @param tl
> + *   A pointer to the ticketlock.
> + */
> +static inline __rte_experimental void
> +rte_ticketlock_unlock(rte_ticketlock_t *tl);
> +
> +static inline __rte_experimental void
> +rte_ticketlock_unlock(rte_ticketlock_t *tl) {
> +	uint16_t i = __atomic_load_n(&tl->current, __ATOMIC_RELAXED);
> +	i++;
> +	__atomic_store_n(&tl->current, i, __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 me = __atomic_fetch_add(&tl->next, 1, __ATOMIC_RELAXED);
> +	while (__atomic_load_n(&tl->current, __ATOMIC_RELAXED) != me) {
What happens if other threads incremented 'tl->next' here?

> +		__atomic_sub_fetch(&tl->next, 1, __ATOMIC_RELAXED);
> +		return 0;
> +	}
> +
> +	return 1;
> +}
IMO, this implementation needs to be changed. We should try to take the lock if tl->next and tl->current are equal. Then tl->next should be incremented using a CAS (which makes sure no one else has taken the lock in the meanwhile)

> +
> +/**
> + * 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_RELAXED) !=
Load of tl->current should be __ATOMIC_ACQUIRE

> +			__atomic_load_n(&tl->next, __ATOMIC_RELAXED)); }
> +
> +/**
> + * The rte_ticketlock_recursive_t type.
> + */
> +typedef struct {
> +	rte_ticketlock_t tl; /**< the actual ticketlock */
> +	volatile int user; /**< core id using lock, -1 for unused */
> +	volatile int count; /**< count of time this lock has been called */ }
'count' can be 'unsigned int'?

> +rte_ticketlock_recursive_t;
> +
> +/**
> + * A static recursive ticketlock initializer.
> + */
> +#define RTE_TICKETLOCK_RECURSIVE_INITIALIZER
> +{RTE_TICKETLOCK_INITIALIZER, -1, 0}
> +
> +/**
> + * Initialize the recursive ticketlock to an unlocked state.
> + *
> + * @param tlr
> + *   A pointer to the recursive ticketlock.
> + */
> +static inline __rte_experimental void rte_ticketlock_recursive_init(
> +					rte_ticketlock_recursive_t *tlr)
> +{
> +	rte_ticketlock_init(&tlr->tl);
> +	tlr->user = -1;
> +	tlr->count = 0;
> +}
> +
> +/**
> + * Take the recursive ticketlock.
> + *
> + * @param tlr
> + *   A pointer to the recursive ticketlock.
> + */
> +static inline __rte_experimental void rte_ticketlock_recursive_lock(
> +					rte_ticketlock_recursive_t *tlr)
> +{
> +	int id = rte_gettid();
> +
> +	if (tlr->user != id) {
> +		rte_ticketlock_lock(&tlr->tl);
> +		tlr->user = id;
> +	}
> +	tlr->count++;
> +}
> +/**
> + * Release the recursive ticketlock.
> + *
> + * @param tlr
> + *   A pointer to the recursive ticketlock.
> + */
> +static inline __rte_experimental void rte_ticketlock_recursive_unlock(
> +					rte_ticketlock_recursive_t *tlr)
> +{
> +	if (--(tlr->count) == 0) {
> +		tlr->user = -1;
> +		rte_ticketlock_unlock(&tlr->tl);
> +	}
> +
Minor comment. Extra line.

> +}
> +
> +/**
> + * Try to take the recursive lock.
> + *
> + * @param tlr
> + *   A pointer to the recursive ticketlock.
> + * @return
> + *   1 if the lock is successfully taken; 0 otherwise.
> + */
> +static inline __rte_experimental int rte_ticketlock_recursive_trylock(
> +					rte_ticketlock_recursive_t *tlr)
> +{
> +	int id = rte_gettid();
> +
> +	if (tlr->user != id) {
> +		if (rte_ticketlock_trylock(&tlr->tl) == 0)
> +			return 0;
> +		tlr->user = id;
> +	}
> +	tlr->count++;
> +	return 1;
> +}
> +
> +#endif /* _RTE_TICKETLOCK_H_ */
> diff --git a/lib/librte_eal/rte_eal_version.map
> b/lib/librte_eal/rte_eal_version.map
> index eb5f7b9cb..f1841effa 100644
> --- a/lib/librte_eal/rte_eal_version.map
> +++ b/lib/librte_eal/rte_eal_version.map
> @@ -364,4 +364,12 @@ EXPERIMENTAL {
>  	rte_service_may_be_active;
>  	rte_socket_count;
>  	rte_socket_id_by_idx;
> +	rte_ticketlock_lock;
> +	rte_ticketlock_unlock;
> +	rte_ticketlock_islocked;
> +	rte_ticketlock_trylock;
> +	rte_ticketlock_recurrsive_lock;
> +	rte_ticketlock_recurrsive_unlock;
> +	rte_ticketlock_recurrsive_islocked;
> +	rte_ticketlock_recurrsive_trylock;
These are all 'inline' functions, they do not need to be versioned.

>  };
> --
> 2.11.0