DPDK patches and discussions
 help / color / mirror / Atom feed
From: Gavin Hu <gavin.hu@arm.com>
To: dev@dpdk.org
Cc: thomas@monjalon.net, jerinj@marvell.com, hemant.agrawal@nxp.com,
	stephen@networkplumber.org, nd@arm.com,
	Honnappa.Nagarahalli@arm.com, gavin.hu@arm.com,
	Joyce Kong <joyce.kong@arm.com>
Subject: [dpdk-dev] [PATCH v1] ticketlock: ticket based to improve fairness
Date: Sun, 13 Jan 2019 22:46:31 +0800	[thread overview]
Message-ID: <20190113144631.23493-1-gavin.hu@arm.com> (raw)

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
+ */
+
+#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_ */
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;
 };
-- 
2.11.0

             reply	other threads:[~2019-01-13 14:46 UTC|newest]

Thread overview: 74+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2019-01-13 14:46 Gavin Hu [this message]
2019-01-14  7:59 ` [dpdk-dev] [EXT] " Jerin Jacob Kollanukkaran
2019-01-14 16:57   ` Gavin Hu (Arm Technology China)
2019-01-14 23:36 ` [dpdk-dev] " Honnappa Nagarahalli
2019-01-18  9:15 ` [dpdk-dev] [PATCH v2 1/2] " Joyce Kong
2019-01-25  8:37   ` [dpdk-dev] [PATCH v3 0/2] ticketlock: implement ticketlock and add test case Joyce Kong
2019-02-19 10:48     ` [dpdk-dev] [PATCH v4 " Joyce Kong
2019-03-11  5:52       ` [dpdk-dev] [PATCH v5 " Joyce Kong
2019-02-19 10:48     ` [dpdk-dev] [PATCH v4 1/2] ticketlock: ticket based to improve fairness Joyce Kong
2019-03-11  5:52       ` [dpdk-dev] [PATCH v5 1/2] eal/ticketlock: " Joyce Kong
2019-03-13  9:41         ` Jerin Jacob Kollanukkaran
2019-03-15  6:57           ` Joyce Kong (Arm Technology China)
2019-03-15  6:57             ` Joyce Kong (Arm Technology China)
2019-03-13 15:36         ` Jerin Jacob Kollanukkaran
2019-03-15  6:58           ` Joyce Kong (Arm Technology China)
2019-03-15  6:58             ` Joyce Kong (Arm Technology China)
2019-02-19 10:48     ` [dpdk-dev] [PATCH v4 2/2] test/ticketlock: add ticket lock test case Joyce Kong
2019-03-11  5:52       ` [dpdk-dev] [PATCH v5 " Joyce Kong
2019-03-13 13:31         ` Jerin Jacob Kollanukkaran
2019-03-15  6:57           ` Joyce Kong (Arm Technology China)
2019-03-15  6:57             ` Joyce Kong (Arm Technology China)
2019-01-25  8:37   ` [dpdk-dev] [PATCH v3 1/2] ticketlock: ticket based to improve fairness Joyce Kong
2019-01-25  8:37   ` [dpdk-dev] [PATCH v3 2/2] test/ticketlock: add ticket lock test case Joyce Kong
2019-03-15  6:56   ` [dpdk-dev] [PATCH v6 0/2] ticketlock: implement ticketlock and add " Joyce Kong
2019-03-15  6:56     ` Joyce Kong
2019-03-15  6:56   ` [dpdk-dev] [PATCH v6 1/2] eal/ticketlock: ticket based to improve fairness Joyce Kong
2019-03-15  6:56     ` Joyce Kong
2019-03-15 12:55     ` Ananyev, Konstantin
2019-03-15 12:55       ` Ananyev, Konstantin
2019-03-19  9:44       ` Gavin Hu (Arm Technology China)
2019-03-19  9:44         ` Gavin Hu (Arm Technology China)
2019-03-19 10:15         ` Ananyev, Konstantin
2019-03-19 10:15           ` Ananyev, Konstantin
2019-03-20  5:11           ` Gavin Hu (Arm Technology China)
2019-03-20  5:11             ` Gavin Hu (Arm Technology China)
2019-03-20  9:47             ` Ananyev, Konstantin
2019-03-20  9:47               ` Ananyev, Konstantin
2019-03-22  2:04               ` Gavin Hu (Arm Technology China)
2019-03-22  2:04                 ` Gavin Hu (Arm Technology China)
2019-03-15  6:56   ` [dpdk-dev] [PATCH v6 2/2] test/ticketlock: add ticket lock test case Joyce Kong
2019-03-15  6:56     ` Joyce Kong
2019-03-21  9:13   ` [dpdk-dev] [PATCH v7 0/3] ticketlock: implement ticketlock and add " Joyce Kong
2019-03-21  9:13     ` Joyce Kong
2019-03-21  9:13   ` [dpdk-dev] [PATCH v7 2/3] eal/ticketlock: enable generic ticketlock on all arch Joyce Kong
2019-03-21  9:13     ` Joyce Kong
2019-03-21  9:13   ` [dpdk-dev] [PATCH v7 3/3] test/ticketlock: add ticket lock test case Joyce Kong
2019-03-21  9:13     ` Joyce Kong
2019-03-22 11:38     ` Ananyev, Konstantin
2019-03-22 11:38       ` Ananyev, Konstantin
2019-03-25 10:25       ` Joyce Kong (Arm Technology China)
2019-03-25 10:25         ` Joyce Kong (Arm Technology China)
2019-03-21  9:15   ` [dpdk-dev] [PATCH v7 1/3] eal/ticketlock: ticket based to improve fairness Joyce Kong
2019-03-21  9:15     ` Joyce Kong
2019-03-22 10:56     ` Ananyev, Konstantin
2019-03-22 10:56       ` Ananyev, Konstantin
2019-03-25 11:11   ` [dpdk-dev] [PATCH v8 0/3] ticketlock: implement ticketlock and add test case Joyce Kong
2019-03-25 11:11     ` Joyce Kong
2019-03-27 11:20     ` Ananyev, Konstantin
2019-03-27 11:20       ` Ananyev, Konstantin
2019-03-28 14:02       ` Thomas Monjalon
2019-03-28 14:02         ` Thomas Monjalon
2019-03-25 11:11   ` [dpdk-dev] [PATCH v8 1/3] eal/ticketlock: ticket based to improve fairness Joyce Kong
2019-03-25 11:11     ` Joyce Kong
2019-03-25 11:11   ` [dpdk-dev] [PATCH v8 2/3] eal/ticketlock: enable generic ticketlock on all arch Joyce Kong
2019-03-25 11:11     ` Joyce Kong
2019-03-25 11:11   ` [dpdk-dev] [PATCH v8 3/3] test/ticketlock: add ticket lock test case Joyce Kong
2019-03-25 11:11     ` Joyce Kong
2019-04-08 20:18     ` David Marchand
2019-04-08 20:18       ` David Marchand
2019-04-14 20:37       ` Thomas Monjalon
2019-04-14 20:37         ` Thomas Monjalon
2019-04-15  9:07         ` Joyce Kong (Arm Technology China)
2019-04-15  9:07           ` Joyce Kong (Arm Technology China)
2019-01-18  9:15 ` [dpdk-dev] [PATCH v2 2/2] " Joyce Kong

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=20190113144631.23493-1-gavin.hu@arm.com \
    --to=gavin.hu@arm.com \
    --cc=Honnappa.Nagarahalli@arm.com \
    --cc=dev@dpdk.org \
    --cc=hemant.agrawal@nxp.com \
    --cc=jerinj@marvell.com \
    --cc=joyce.kong@arm.com \
    --cc=nd@arm.com \
    --cc=stephen@networkplumber.org \
    --cc=thomas@monjalon.net \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).