[v5,1/2] eal/ticketlock: ticket based to improve fairness
Checks
Commit Message
The spinlock implementation is unfair, some threads may take locks
aggressively while leaving the other threads starving for long time.
This patch introduces ticketlock which 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.
Suggested-by: Jerin Jacob <jerinj@marvell.com>
Signed-off-by: Joyce kong <joyce.kong@arm.com>
Reviewed-by: Gavin Hu <gavin.hu@arm.com>
Reviewed-by: Ola Liljedahl <ola.liljedahl@arm.com>
Reviewed-by: Honnappa Nagarahalli <honnappa.nagarahalli@arm.com>
---
MAINTAINERS | 4 +
doc/api/doxy-api-index.md | 1 +
lib/librte_eal/common/Makefile | 2 +-
.../common/include/generic/rte_ticketlock.h | 203 +++++++++++++++++++++
lib/librte_eal/common/meson.build | 1 +
5 files changed, 210 insertions(+), 1 deletion(-)
create mode 100644 lib/librte_eal/common/include/generic/rte_ticketlock.h
Comments
On Mon, 2019-03-11 at 13:52 +0800, Joyce Kong wrote:
> The spinlock implementation is unfair, some threads may take locks
> aggressively while leaving the other threads starving for long time.
>
> This patch introduces ticketlock which 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.
>
> Suggested-by: Jerin Jacob <jerinj@marvell.com>
> Signed-off-by: Joyce kong <joyce.kong@arm.com>
> Reviewed-by: Gavin Hu <gavin.hu@arm.com>
> Reviewed-by: Ola Liljedahl <ola.liljedahl@arm.com>
> Reviewed-by: Honnappa Nagarahalli <honnappa.nagarahalli@arm.com>
> ---
> +static inline __rte_experimental int
> +rte_ticketlock_trylock(rte_ticketlock_t *tl)
> +{
> + unsigned int next = __atomic_load_n(&tl->next,
> __ATOMIC_RELAXED);
> + unsigned int cur = __atomic_load_n(&tl->current,
> __ATOMIC_RELAXED);
> + if (next == cur) {
> + if (__atomic_compare_exchange_n(&tl->next, &next,
> next+1,
> + 0, __ATOMIC_ACQUIRE, __ATOMIC_RELAXED))
gcc 8.2 emits the following compilation error.
/export/dpdk.org/build/include/generic/rte_ticketlock.h:93:46: error:
incompatible pointer types passing 'unsigned int *' to parameter of
type 'uint16_t *' (aka 'unsigned short *') [-Werror,-Wincompatible-
pointer-types]
if (__atomic_compare_exchange_n(&tl->next, &next,
next+1,
> + return 1;
> + }
> +
> + return 0;
> +}
> +
>
On Mon, 2019-03-11 at 13:52 +0800, Joyce Kong wrote:
> The spinlock implementation is unfair, some threads may take locks
> aggressively while leaving the other threads starving for long time.
>
> This patch introduces ticketlock which 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.
>
> Suggested-by: Jerin Jacob <jerinj@marvell.com>
> Signed-off-by: Joyce kong <joyce.kong@arm.com>
> Reviewed-by: Gavin Hu <gavin.hu@arm.com>
> Reviewed-by: Ola Liljedahl <ola.liljedahl@arm.com>
> Reviewed-by: Honnappa Nagarahalli <honnappa.nagarahalli@arm.com>
> ---
> diff --git a/MAINTAINERS b/MAINTAINERS
> index 097cfb4..12a091f 100644
> --- a/MAINTAINERS
> +++ b/MAINTAINERS
> @@ -210,6 +210,10 @@ M: Cristian Dumitrescu <
> cristian.dumitrescu@intel.com>
> F: lib/librte_eal/common/include/rte_bitmap.h
> F: app/test/test_bitmap.c
>
> +Ticketlock
> +M: Joyce Kong <joyce.kong@arm.com>
> +F: lib/librte_eal/common/include/generic/rte_ticketlock.h
Add F: app/test/test_ticketlock.c in the next patch
>
> +#include <rte_lcore.h>
> +#include <rte_common.h>
> +#include <rte_pause.h>
Sort the header in alphabetical order.
> +
> +/**
> + * The rte_ticketlock_t type.
> + */
> +typedef struct {
> + uint16_t current;
> + uint16_t next;
> +} rte_ticketlock_t;
> +
>
> +
> +/**
> + * Take the ticketlock.
> + *
> + * @param tl
> + * A pointer to the ticketlock.
> + */
> +static inline __rte_experimental void
> +rte_ticketlock_lock(rte_ticketlock_t *tl)
> +{
> + unsigned int me = __atomic_fetch_add(&tl->next, 1,
If current, next is uint16_t why "me" as unsigned int.
> __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)
> +{
> + unsigned int i = __atomic_load_n(&tl->current,
> __ATOMIC_RELAXED);
> + i++;
You can save this line by making
__atomic_store_n(&tl->current, i + 1, __ATOMIC_RELEASE);
The code looks good. Please check the above comments and earlier
reported compilation issue with clang 7.1
> -----Original Message-----
> From: Jerin Jacob Kollanukkaran <jerinj@marvell.com>
> Sent: Wednesday, March 13, 2019 5:41 PM
> To: Joyce Kong (Arm Technology China) <Joyce.Kong@arm.com>;
> dev@dpdk.org
> Cc: stephen@networkplumber.org; Honnappa Nagarahalli
> <Honnappa.Nagarahalli@arm.com>; thomas@monjalon.net; nd
> <nd@arm.com>; jerin.jacob@caviumnetworks.com; Gavin Hu (Arm
> Technology China) <Gavin.Hu@arm.com>
> Subject: Re: [dpdk-dev] [PATCH v5 1/2] eal/ticketlock: ticket based to improve
> fairness
>
> On Mon, 2019-03-11 at 13:52 +0800, Joyce Kong wrote:
> > The spinlock implementation is unfair, some threads may take locks
> > aggressively while leaving the other threads starving for long time.
> >
> > This patch introduces ticketlock which 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.
> >
> > Suggested-by: Jerin Jacob <jerinj@marvell.com>
> > Signed-off-by: Joyce kong <joyce.kong@arm.com>
> > Reviewed-by: Gavin Hu <gavin.hu@arm.com>
> > Reviewed-by: Ola Liljedahl <ola.liljedahl@arm.com>
> > Reviewed-by: Honnappa Nagarahalli <honnappa.nagarahalli@arm.com>
> > ---
> > +static inline __rte_experimental int
> > +rte_ticketlock_trylock(rte_ticketlock_t *tl) {
> > + unsigned int next = __atomic_load_n(&tl->next,
> > __ATOMIC_RELAXED);
> > + unsigned int cur = __atomic_load_n(&tl->current,
> > __ATOMIC_RELAXED);
> > + if (next == cur) {
> > + if (__atomic_compare_exchange_n(&tl->next, &next,
> > next+1,
> > + 0, __ATOMIC_ACQUIRE, __ATOMIC_RELAXED))
>
> gcc 8.2 emits the following compilation error.
>
> /export/dpdk.org/build/include/generic/rte_ticketlock.h:93:46: error:
> incompatible pointer types passing 'unsigned int *' to parameter of type
> 'uint16_t *' (aka 'unsigned short *') [-Werror,-Wincompatible- pointer-types]
> if (__atomic_compare_exchange_n(&tl->next, &next,
> next+1,
>
Fix the error by changing next and cur from unsigned int to unint16_t in V6.
>
> > + return 1;
> > + }
> > +
> > + return 0;
> > +}
> > +
> >
> -----Original Message-----
> From: Jerin Jacob Kollanukkaran <jerinj@marvell.com>
> Sent: Wednesday, March 13, 2019 11:36 PM
> To: Joyce Kong (Arm Technology China) <Joyce.Kong@arm.com>;
> dev@dpdk.org
> Cc: stephen@networkplumber.org; Honnappa Nagarahalli
> <Honnappa.Nagarahalli@arm.com>; thomas@monjalon.net; nd
> <nd@arm.com>; jerin.jacob@caviumnetworks.com; Gavin Hu (Arm
> Technology China) <Gavin.Hu@arm.com>
> Subject: Re: [dpdk-dev] [PATCH v5 1/2] eal/ticketlock: ticket based to improve
> fairness
>
> On Mon, 2019-03-11 at 13:52 +0800, Joyce Kong wrote:
> > The spinlock implementation is unfair, some threads may take locks
> > aggressively while leaving the other threads starving for long time.
> >
> > This patch introduces ticketlock which 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.
> >
> > Suggested-by: Jerin Jacob <jerinj@marvell.com>
> > Signed-off-by: Joyce kong <joyce.kong@arm.com>
> > Reviewed-by: Gavin Hu <gavin.hu@arm.com>
> > Reviewed-by: Ola Liljedahl <ola.liljedahl@arm.com>
> > Reviewed-by: Honnappa Nagarahalli <honnappa.nagarahalli@arm.com>
> > ---
> > diff --git a/MAINTAINERS b/MAINTAINERS index 097cfb4..12a091f 100644
> > --- a/MAINTAINERS
> > +++ b/MAINTAINERS
> > @@ -210,6 +210,10 @@ M: Cristian Dumitrescu <
> > cristian.dumitrescu@intel.com>
> > F: lib/librte_eal/common/include/rte_bitmap.h
> > F: app/test/test_bitmap.c
> >
> > +Ticketlock
> > +M: Joyce Kong <joyce.kong@arm.com>
> > +F: lib/librte_eal/common/include/generic/rte_ticketlock.h
>
>
> Add F: app/test/test_ticketlock.c in the next patch
>
Done in V6.
> >
> > +#include <rte_lcore.h>
> > +#include <rte_common.h>
> > +#include <rte_pause.h>
>
> Sort the header in alphabetical order.
>
Done in v6.
> > +
> > +/**
> > + * The rte_ticketlock_t type.
> > + */
> > +typedef struct {
> > + uint16_t current;
> > + uint16_t next;
> > +} rte_ticketlock_t;
> > +
> >
> > +
> > +/**
> > + * Take the ticketlock.
> > + *
> > + * @param tl
> > + * A pointer to the ticketlock.
> > + */
> > +static inline __rte_experimental void
> > +rte_ticketlock_lock(rte_ticketlock_t *tl) {
> > + unsigned int me = __atomic_fetch_add(&tl->next, 1,
>
> If current, next is uint16_t why "me" as unsigned int.
>
Change "me" to uint16_t to match current and next in v6.
> > __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) {
> > + unsigned int i = __atomic_load_n(&tl->current,
> > __ATOMIC_RELAXED);
> > + i++;
>
> You can save this line by making
> __atomic_store_n(&tl->current, i + 1, __ATOMIC_RELEASE);
>
Done in V6.
> The code looks good. Please check the above comments and earlier reported
> compilation issue with clang 7.1
>
@@ -210,6 +210,10 @@ M: Cristian Dumitrescu <cristian.dumitrescu@intel.com>
F: lib/librte_eal/common/include/rte_bitmap.h
F: app/test/test_bitmap.c
+Ticketlock
+M: Joyce Kong <joyce.kong@arm.com>
+F: lib/librte_eal/common/include/generic/rte_ticketlock.h
+
ARM v7
M: Jan Viktorin <viktorin@rehivetech.com>
M: Gavin Hu <gavin.hu@arm.com>
@@ -65,6 +65,7 @@ The public API headers are grouped by topics:
[atomic] (@ref rte_atomic.h),
[rwlock] (@ref rte_rwlock.h),
[spinlock] (@ref rte_spinlock.h)
+ [ticketlock] (@ref rte_ticketlock.h)
- **CPU arch**:
[branch prediction] (@ref rte_branch_prediction.h),
@@ -20,7 +20,7 @@ INC += rte_bitmap.h rte_vfio.h rte_hypervisor.h rte_test.h
INC += rte_reciprocal.h rte_fbarray.h rte_uuid.h
GENERIC_INC := rte_atomic.h rte_byteorder.h rte_cycles.h rte_prefetch.h
-GENERIC_INC += rte_spinlock.h rte_memcpy.h rte_cpuflags.h rte_rwlock.h
+GENERIC_INC += rte_spinlock.h rte_memcpy.h rte_cpuflags.h rte_rwlock.h rte_ticketlock.h
GENERIC_INC += rte_vect.h rte_pause.h rte_io.h
# defined in mk/arch/$(RTE_ARCH)/rte.vars.mk
new file mode 100644
@@ -0,0 +1,203 @@
+/* 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.
+ *
+ */
+
+#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;
+} 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)
+{
+ unsigned int 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)
+{
+ unsigned int 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)
+{
+ unsigned int next = __atomic_load_n(&tl->next, __ATOMIC_RELAXED);
+ unsigned int cur = __atomic_load_n(&tl->current, __ATOMIC_RELAXED);
+ if (next == cur) {
+ 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));
+}
+
+/**
+ * The rte_ticketlock_recursive_t type.
+ */
+#define TICKET_LOCK_INVALID_ID -1
+
+typedef struct {
+ rte_ticketlock_t tl; /**< the actual ticketlock */
+ int user; /**< core id using lock, TICKET_LOCK_INVALID_ID for unused */
+ unsigned int count; /**< count of time this lock has been called */
+} rte_ticketlock_recursive_t;
+
+/**
+ * A static recursive ticketlock initializer.
+ */
+#define RTE_TICKETLOCK_RECURSIVE_INITIALIZER {RTE_TICKETLOCK_INITIALIZER, \
+ TICKET_LOCK_INVALID_ID, 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);
+ __atomic_store_n(&tlr->user, TICKET_LOCK_INVALID_ID, __ATOMIC_RELAXED);
+ 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 (__atomic_load_n(&tlr->user, __ATOMIC_RELAXED) != id) {
+ rte_ticketlock_lock(&tlr->tl);
+ __atomic_store_n(&tlr->user, id, __ATOMIC_RELAXED);
+ }
+ 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) {
+ __atomic_store_n(&tlr->user, TICKET_LOCK_INVALID_ID,
+ __ATOMIC_RELAXED);
+ rte_ticketlock_unlock(&tlr->tl);
+ }
+}
+
+/**
+ * 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 (__atomic_load_n(&tlr->user, __ATOMIC_RELAXED) != id) {
+ if (rte_ticketlock_trylock(&tlr->tl) == 0)
+ return 0;
+ __atomic_store_n(&tlr->user, id, __ATOMIC_RELAXED);
+ }
+ tlr->count++;
+ return 1;
+}
+
+#endif /* _RTE_TICKETLOCK_H_ */
@@ -99,6 +99,7 @@ generic_headers = files(
'include/generic/rte_prefetch.h',
'include/generic/rte_rwlock.h',
'include/generic/rte_spinlock.h',
+ 'include/generic/rte_ticketlock.h',
'include/generic/rte_vect.h')
install_headers(generic_headers, subdir: 'generic')