[v5,1/2] eal/ticketlock: ticket based to improve fairness

Message ID 1552283564-113385-2-git-send-email-joyce.kong@arm.com
State Superseded, archived
Delegated to: Thomas Monjalon
Headers show
Series
  • ticketlock: implement ticketlock and add test case
Related show

Checks

Context Check Description
ci/intel-Performance-Testing success Performance Testing PASS
ci/mellanox-Performance-Testing success Performance Testing PASS
ci/Intel-compilation success Compilation OK
ci/checkpatch success coding style OK

Commit Message

Joyce Kong March 11, 2019, 5:52 a.m.
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

Jerin Jacob Kollanukkaran March 13, 2019, 9:41 a.m. | #1
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;
> +}
> +
>
Jerin Jacob Kollanukkaran March 13, 2019, 3:36 p.m. | #2
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
Joyce Kong March 15, 2019, 6:57 a.m. | #3
> -----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;
> > +}
> > +
> >
Joyce Kong March 15, 2019, 6:58 a.m. | #4
> -----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
>

Patch

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
+
 ARM v7
 M: Jan Viktorin <viktorin@rehivetech.com>
 M: Gavin Hu <gavin.hu@arm.com>
diff --git a/doc/api/doxy-api-index.md b/doc/api/doxy-api-index.md
index d95ad56..aacc66b 100644
--- a/doc/api/doxy-api-index.md
+++ b/doc/api/doxy-api-index.md
@@ -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),
diff --git a/lib/librte_eal/common/Makefile b/lib/librte_eal/common/Makefile
index c487201..ac3305c 100644
--- a/lib/librte_eal/common/Makefile
+++ b/lib/librte_eal/common/Makefile
@@ -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
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..b99737a
--- /dev/null
+++ b/lib/librte_eal/common/include/generic/rte_ticketlock.h
@@ -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_ */
diff --git a/lib/librte_eal/common/meson.build b/lib/librte_eal/common/meson.build
index 5ecae0b..0670e41 100644
--- a/lib/librte_eal/common/meson.build
+++ b/lib/librte_eal/common/meson.build
@@ -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')