From mboxrd@z Thu Jan 1 00:00:00 1970
Return-Path: <dev-bounces@dpdk.org>
Received: from dpdk.org (dpdk.org [92.243.14.124])
by dpdk.space (Postfix) with ESMTP id 910F8A00E6
for <public@inbox.dpdk.org>; Thu, 21 Mar 2019 10:16:26 +0100 (CET)
Received: from [92.243.14.124] (localhost [127.0.0.1])
by dpdk.org (Postfix) with ESMTP id 5159B1B466;
Thu, 21 Mar 2019 10:16:26 +0100 (CET)
Received: from foss.arm.com (usa-sjc-mx-foss1.foss.arm.com [217.140.101.70])
by dpdk.org (Postfix) with ESMTP id 818621B464
for <dev@dpdk.org>; Thu, 21 Mar 2019 10:16:24 +0100 (CET)
Received: from usa-sjc-imap-foss1.foss.arm.com (unknown [10.72.51.249])
by usa-sjc-mx-foss1.foss.arm.com (Postfix) with ESMTP id EFA36374;
Thu, 21 Mar 2019 02:16:23 -0700 (PDT)
Received: from net-arm-thunderx2.shanghai.arm.com
(net-arm-thunderx2.shanghai.arm.com [10.169.40.112])
by usa-sjc-imap-foss1.foss.arm.com (Postfix) with ESMTPA id 806DF3F71A;
Thu, 21 Mar 2019 02:16:22 -0700 (PDT)
From: Joyce Kong <joyce.kong@arm.com>
To: dev@dpdk.org
Cc: nd@arm.com, stephen@networkplumber.org, jerin.jacob@caviumnetworks.com,
konstantin.ananyev@intel.com, thomas@monjalon.net,
honnappa.nagarahalli@arm.com, gavin.hu@arm.com
Date: Thu, 21 Mar 2019 17:15:55 +0800
Message-Id: <1553159755-206102-1-git-send-email-joyce.kong@arm.com>
X-Mailer: git-send-email 2.7.4
In-Reply-To: <1547802943-18711-1-git-send-email-joyce.kong@arm.com>
References: <1547802943-18711-1-git-send-email-joyce.kong@arm.com>
Subject: [dpdk-dev] [PATCH v7 1/3] eal/ticketlock: ticket based to improve
fairness
X-BeenThere: dev@dpdk.org
X-Mailman-Version: 2.1.15
Precedence: list
List-Id: DPDK patches and discussions <dev.dpdk.org>
List-Unsubscribe: <https://mails.dpdk.org/options/dev>,
<mailto:dev-request@dpdk.org?subject=unsubscribe>
List-Archive: <http://mails.dpdk.org/archives/dev/>
List-Post: <mailto:dev@dpdk.org>
List-Help: <mailto:dev-request@dpdk.org?subject=help>
List-Subscribe: <https://mails.dpdk.org/listinfo/dev>,
<mailto:dev-request@dpdk.org?subject=subscribe>
Errors-To: dev-bounces@dpdk.org
Sender: "dev" <dev-bounces@dpdk.org>
Content-Type: text/plain; charset="UTF-8"
Message-ID: <20190321091555.FA6t-pqN_q6azmPE0obSrNzUfCzuYwKaHHW-TnQEDRc@z>
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 | 215 +++++++++++++++++++++
lib/librte_eal/common/meson.build | 1 +
5 files changed, 222 insertions(+), 1 deletion(-)
create mode 100644 lib/librte_eal/common/include/generic/rte_ticketlock.h
diff --git a/MAINTAINERS b/MAINTAINERS
index 452b8eb..3521271 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..c5203cb
--- /dev/null
+++ b/lib/librte_eal/common/include/generic/rte_ticketlock.h
@@ -0,0 +1,215 @@
+/* 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.
+ *
+ */
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+#include <rte_common.h>
+#include <rte_lcore.h>
+#include <rte_pause.h>
+
+/**
+ * The rte_ticketlock_t type.
+ */
+typedef union {
+ uint32_t tickets;
+ struct {
+ uint16_t current;
+ uint16_t next;
+ } s;
+} 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->tickets, 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)
+{
+ uint16_t me = __atomic_fetch_add(&tl->s.next, 1, __ATOMIC_RELAXED);
+ while (__atomic_load_n(&tl->s.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)
+{
+ uint16_t i = __atomic_load_n(&tl->s.current, __ATOMIC_RELAXED);
+ __atomic_store_n(&tl->s.current, i + 1, __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)
+{
+ rte_ticketlock_t old, new;
+ old.tickets = __atomic_load_n(&tl->tickets, __ATOMIC_RELAXED);
+ new.tickets = __atomic_load_n(&tl->tickets, __ATOMIC_RELAXED);
+ new.s.next++;
+ if (old.s.next == old.s.current) {
+ if (__atomic_compare_exchange_n(&tl->tickets, &old.tickets,
+ new.tickets, 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 is currently taken; 0 otherwise.
+ */
+static inline __rte_experimental int
+rte_ticketlock_is_locked(rte_ticketlock_t *tl)
+{
+ rte_ticketlock_t tic;
+ tic.tickets = __atomic_load_n(&tl->tickets, __ATOMIC_ACQUIRE);
+ return (tic.s.current != tic.s.next);
+}
+
+/**
+ * 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;
+}
+
+#ifdef __cplusplus
+}
+#endif
+
+#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')
--
2.7.4