From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from foss.arm.com (usa-sjc-mx-foss1.foss.arm.com [217.140.101.70]) by dpdk.org (Postfix) with ESMTP id A9B092C19 for ; Mon, 25 Mar 2019 12:11:26 +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 0217015AD; Mon, 25 Mar 2019 04:11:26 -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 82DAE3F575; Mon, 25 Mar 2019 04:11:24 -0700 (PDT) From: Joyce Kong 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: Mon, 25 Mar 2019 19:11:07 +0800 Message-Id: <1553512269-146074-2-git-send-email-joyce.kong@arm.com> X-Mailer: git-send-email 2.7.4 In-Reply-To: <1553512269-146074-1-git-send-email-joyce.kong@arm.com> References: <1553512269-146074-1-git-send-email-joyce.kong@arm.com> 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 v8 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 List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Mon, 25 Mar 2019 11:11:27 -0000 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 Signed-off-by: Joyce Kong Reviewed-by: Gavin Hu Reviewed-by: Ola Liljedahl Reviewed-by: Honnappa Nagarahalli Acked-by: Konstantin Ananyev --- 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 F: lib/librte_eal/common/include/rte_bitmap.h F: app/test/test_bitmap.c +Ticketlock +M: Joyce Kong +F: lib/librte_eal/common/include/generic/rte_ticketlock.h + ARM v7 M: Jan Viktorin M: Gavin Hu 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..191146f --- /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 +#include +#include + +/** + * 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 = old.tickets; + 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 From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from dpdk.org (dpdk.org [92.243.14.124]) by dpdk.space (Postfix) with ESMTP id F3303A05D3 for ; Mon, 25 Mar 2019 12:11:32 +0100 (CET) Received: from [92.243.14.124] (localhost [127.0.0.1]) by dpdk.org (Postfix) with ESMTP id 70EA22C2F; Mon, 25 Mar 2019 12:11:28 +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 A9B092C19 for ; Mon, 25 Mar 2019 12:11:26 +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 0217015AD; Mon, 25 Mar 2019 04:11:26 -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 82DAE3F575; Mon, 25 Mar 2019 04:11:24 -0700 (PDT) From: Joyce Kong 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: Mon, 25 Mar 2019 19:11:07 +0800 Message-Id: <1553512269-146074-2-git-send-email-joyce.kong@arm.com> X-Mailer: git-send-email 2.7.4 In-Reply-To: <1553512269-146074-1-git-send-email-joyce.kong@arm.com> References: <1553512269-146074-1-git-send-email-joyce.kong@arm.com> 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 v8 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 List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: dev-bounces@dpdk.org Sender: "dev" Content-Type: text/plain; charset="UTF-8" Message-ID: <20190325111107.7GWCM1-OkvzmtPItwYVsw0zOEqdmLZSU0vQuXajKE98@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 Signed-off-by: Joyce Kong Reviewed-by: Gavin Hu Reviewed-by: Ola Liljedahl Reviewed-by: Honnappa Nagarahalli Acked-by: Konstantin Ananyev --- 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 F: lib/librte_eal/common/include/rte_bitmap.h F: app/test/test_bitmap.c +Ticketlock +M: Joyce Kong +F: lib/librte_eal/common/include/generic/rte_ticketlock.h + ARM v7 M: Jan Viktorin M: Gavin Hu 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..191146f --- /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 +#include +#include + +/** + * 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 = old.tickets; + 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