From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from foss.arm.com (foss.arm.com [217.140.101.70]) by dpdk.org (Postfix) with ESMTP id 3A281239; Fri, 18 Jan 2019 10:16:50 +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 9058BEBD; Fri, 18 Jan 2019 01:16:49 -0800 (PST) Received: from net-arm-thunderx2.shanghai.arm.com (net-arm-thunderx2.shanghai.arm.com [10.169.40.106]) by usa-sjc-imap-foss1.foss.arm.com (Postfix) with ESMTPA id EBD123F5C1; Fri, 18 Jan 2019 01:16:47 -0800 (PST) From: Joyce Kong To: dev@dpdk.org Cc: OSS-DPDK-dev@arm.com, nd@arm.com, thomas@monjalon.net, jerin.jacob@caviumnetworks.com, stephen@networkplumber.org, honnappa.nagarahalli@arm.com, gavin.hu@arm.com, stable@dpdk.org, Joyce kong Date: Fri, 18 Jan 2019 17:15:42 +0800 Message-Id: <1547802943-18711-1-git-send-email-joyce.kong@arm.com> X-Mailer: git-send-email 2.7.4 In-Reply-To: <20190113144631.23493-1-gavin.hu@arm.com> References: <20190113144631.23493-1-gavin.hu@arm.com> Subject: [dpdk-dev] [PATCH v2 1/2] 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 List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Fri, 18 Jan 2019 09:16:50 -0000 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. *** ticketlock_autotest with this patch *** Core [0] count = 496 Core [1] count = 495 Core [2] count = 498 ... Core [209] count = 488 Core [210] count = 490 Core [211] count = 474 Suggested-by: Jerin Jacob Signed-off-by: Joyce kong Reviewed-by: Gavin Hu Reviewed-by: Phil Yang --- doc/api/doxy-api-index.md | 1 + lib/librte_eal/common/Makefile | 2 +- .../common/include/generic/rte_ticketlock.h | 198 +++++++++++++++++++++ lib/librte_eal/common/meson.build | 1 + 4 files changed, 201 insertions(+), 1 deletion(-) create mode 100644 lib/librte_eal/common/include/generic/rte_ticketlock.h 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 87d8c45..99e948b 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..2979528 --- /dev/null +++ b/lib/librte_eal/common/include/generic/rte_ticketlock.h @@ -0,0 +1,198 @@ +/* SPDX-License-Identifier: BSD-3-Clause + * Copyright(c) 2018-2019 Arm 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. + * + * All locks must be initialised before use, and only initialised once. + * + */ + +#include +#include +#include + +/** + * 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) +{ + 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) +{ + 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/common/meson.build b/lib/librte_eal/common/meson.build index 2a10d57..23f9416 100644 --- a/lib/librte_eal/common/meson.build +++ b/lib/librte_eal/common/meson.build @@ -98,6 +98,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