[v1] ticketlock: ticket based to improve fairness
Checks
Commit Message
From: Joyce Kong <joyce.kong@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@arm.com>
Signed-off-by: Gavin Hu <gavin.hu@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
Comments
On Sun, 2019-01-13 at 22:46 +0800, Gavin Hu wrote:
> -------------------------------------------------------------------
> ---
> From: Joyce Kong <joyce.kong@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 ***
This comment needs to be updated as it is new API now
and we need add test case for the same. I think,
making modification to exiting spinlock test case would be fine.
> 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@arm.com>
> Signed-off-by: Gavin Hu <gavin.hu@arm.com>
> ---
>
> -----Original Message-----
> From: Jerin Jacob Kollanukkaran <jerinj@marvell.com>
> Sent: Monday, January 14, 2019 4:00 PM
> To: Gavin Hu (Arm Technology China) <Gavin.Hu@arm.com>;
> dev@dpdk.org
> Cc: stephen@networkplumber.org; Honnappa Nagarahalli
> <Honnappa.Nagarahalli@arm.com>; thomas@monjalon.net; nd
> <nd@arm.com>; Joyce Kong (Arm Technology China)
> <Joyce.Kong@arm.com>; hemant.agrawal@nxp.com
> Subject: Re: [EXT] [PATCH v1] ticketlock: ticket based to improve fairness
>
> On Sun, 2019-01-13 at 22:46 +0800, Gavin Hu wrote:
> > -------------------------------------------------------------------
> > ---
> > From: Joyce Kong <joyce.kong@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 ***
>
> This comment needs to be updated as it is new API now
> and we need add test case for the same. I think,
> making modification to exiting spinlock test case would be fine.
Thanks for you comments, we will do it and send a v2.
> Subject: [PATCH v1] ticketlock: ticket based to improve fairness
>
> From: Joyce Kong <joyce.kong@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@arm.com>
> Signed-off-by: Gavin Hu <gavin.hu@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
new file mode 100644
@@ -0,0 +1,203 @@
+/* SPDX-License-Identifier: BSD-3-Clause
+ * Copyright(c) 2018-2019 Arm Corporation
+ */
+
+#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.
+ *
+ * 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);
+
+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);
+
+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) {
+ __atomic_sub_fetch(&tl->next, 1, __ATOMIC_RELAXED);
+ return 0;
+ }
+
+ return 1;
+}
+
+/**
+ * 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) !=
+ __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 */
+} 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);
+ }
+
+}
+
+/**
+ * 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_ */
@@ -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;
};