> -----Original Message----- > From: dev <dev-boun...@dpdk.org> On Behalf Of Stephen Hemminger > Sent: Friday, January 15, 2021 1:35 AM > To: dev@dpdk.org > Cc: Stephen Hemminger <step...@networkplumber.org> > Subject: [dpdk-dev] [PATCH v1] eal: add ticket based reader writer lock > > This patch implements a reader/writer ticket lock. > This lock type acts like rte_rwlock() but uses a ticket algorithm and are > fair for > multiple writers and readers. > Writers have priority over readers.
The lock is ticket based to be fair. So writers should have no priority? > > The tests are just a clone of existing rte_rwlock with test and function names > changed. So the new ticket rwlocks should be drop in replacement for most > users. > > Signed-off-by: Stephen Hemminger <step...@networkplumber.org> > --- > Ps: I have additional tests for rwlock that test for fairness. > Would these be valuable? > > app/test/autotest_data.py | 6 + > app/test/meson.build | 5 + > app/test/test_ticket_rwlock.c | 554 ++++++++++++++++++ > doc/api/doxy-api-index.md | 1 + > lib/librte_eal/arm/include/meson.build | 1 + > .../arm/include/rte_ticket_rwlock.h | 22 + > .../include/generic/rte_ticket_rwlock.h | 218 +++++++ > lib/librte_eal/include/meson.build | 1 + > lib/librte_eal/ppc/include/meson.build | 1 + > .../ppc/include/rte_ticket_rwlock.h | 18 + > lib/librte_eal/x86/include/meson.build | 1 + > .../x86/include/rte_ticket_rwlock.h | 18 + > 12 files changed, 846 insertions(+) > create mode 100644 app/test/test_ticket_rwlock.c create mode 100644 > lib/librte_eal/arm/include/rte_ticket_rwlock.h > create mode 100644 lib/librte_eal/include/generic/rte_ticket_rwlock.h > create mode 100644 lib/librte_eal/ppc/include/rte_ticket_rwlock.h > create mode 100644 lib/librte_eal/x86/include/rte_ticket_rwlock.h > <snip> > diff --git a/lib/librte_eal/include/generic/rte_ticket_rwlock.h > b/lib/librte_eal/include/generic/rte_ticket_rwlock.h > new file mode 100644 > index 000000000000..b3637358c1f7 > --- /dev/null > +++ b/lib/librte_eal/include/generic/rte_ticket_rwlock.h > @@ -0,0 +1,218 @@ > +/* SPDX-License-Identifier: BSD-3-Clause > + * Copyright(c) 2021 Microsoft Corporation */ > + > +#ifndef _RTE_TICKET_RWLOCK_H_ > +#define _RTE_TICKET_RWLOCK_H_ > + > +/** > + * @file > + * > + * Ticket based reader/writer lock > + * > + * This file defines an API for ticket style read-write locks. > + * This types of lock act like rte_rwlock but provide fairness > + * and requests are handled first come, first serviced. > + * > + * All locks must be initialized before use, and only initialized once. > + * > + * References: > + * "Spinlocks and Read-Write Locks" > + * http://locklessinc.com/articles/locks/ > + * "Scalable Read-Writer Synchronization for Shared-Memory > Multiprocessors" > + * > https://www.cs.rochester.edu/research/synchronization/pseudocode/rw.ht > ml > + */ > + > +#ifdef __cplusplus > +extern "C" { > +#endif > + > +typedef union { > + uint64_t tickets; > + struct { > + union { > + struct { > + uint16_t write; /* current writer */ > + uint16_t read; /* current reader */ > + }; > + uint32_t readwrite; /* atomic for both read and > write */ > + }; > + uint16_t next; /* next ticket */ > + }; > +} rte_rwticketlock_t; > + > +/** > + * A static rwticket initializer. > + */ > +#define RTE_RWTICKETLOCK_INITIALIZER { 0 } > + > +/** > + * @warning > + * @b EXPERIMENTAL: this API may change without prior notice. > + * > + * Initialize the rwticketlock to an unlocked state. > + * > + * @param rwl > + * A pointer to the rwticketlock structure. > + */ > +__rte_experimental > +static inline void > +rte_rwticketlock_init(rte_rwticketlock_t *rwl) { > + rwl->tickets = 0; > +} > + > +/** > + * @warning > + * @b EXPERIMENTAL: this API may change without prior notice. > + * Take a write lock. Loop until the lock is held. > + * > + * @param rwl > + * A pointer to a rwticketlock structure. > + */ > +__rte_experimental > +static inline void > +rte_rwticket_write_lock(rte_rwticketlock_t *rwl) { > + uint16_t me; > + > + me = __atomic_fetch_add(&rwl->next, 1, __ATOMIC_RELAXED); > + rte_wait_until_equal_16(&rwl->write, me, __ATOMIC_ACQUIRE); } > + > +/** > + * @warning > + * @b EXPERIMENTAL: this API may change without prior notice. > + * > + * Try to take a write lock. > + * > + * @param rwl > + * A pointer to a rwticketlock structure. > + * @return > + * - zero if the lock is successfully taken > + * - -EBUSY if lock could not be acquired for writing because > + * it was already locked for reading or writing > + */ > +__rte_experimental > +static inline int > +rte_rwticket_write_trylock(rte_rwticketlock_t *rwl) { > + rte_rwticketlock_t old, new; > + > + old.tickets = __atomic_load_n(&rwl->tickets, __ATOMIC_RELAXED); > + if (old.write != old.next) > + return -EBUSY; > + > + new.tickets = old.tickets; > + new.next = old.next + 1; > + if (__atomic_compare_exchange_n(&rwl->tickets, &old.tickets, > new.tickets, > + 0, __ATOMIC_ACQUIRE, > __ATOMIC_RELAXED)) > + return 0; > + else > + return -EBUSY; > +} > + > +/** > + * @warning > + * @b EXPERIMENTAL: this API may change without prior notice. > + * > + * Release a write lock. > + * > + * @param rwl > + * A pointer to a rwticketlock structure. > + */ > +__rte_experimental > +static inline void > +rte_rwticket_write_unlock(rte_rwticketlock_t *rwl) { > + rte_rwticketlock_t t; > + > + t.tickets = __atomic_load_n(&rwl->tickets, __ATOMIC_RELAXED); > + t.write++; > + t.read++; > + __atomic_store_n(&rwl->readwrite, t.readwrite, > __ATOMIC_RELEASE); } > + > +/** > + * @warning > + * @b EXPERIMENTAL: this API may change without prior notice. > + * > + * > + * Take a read lock. Loop until the lock is held. > + * > + * @param l Nit, 'rwl'. > + * A pointer to a rwticketlock structure. > + */ > +__rte_experimental > +static inline void > +rte_rwticket_read_lock(rte_rwticketlock_t *rwl) { > + uint16_t me; > + > + me = __atomic_fetch_add(&rwl->next, 1, __ATOMIC_RELAXED); > + rte_wait_until_equal_16(&rwl->read, me, __ATOMIC_ACQUIRE); > + __atomic_fetch_add(&rwl->read, 1, __ATOMIC_RELAXED); } > + > +/** > + * @warning > + * @b EXPERIMENTAL: this API may change without prior notice. > + * > + * Try to take a read lock. > + * > + * @param rwl > + * A pointer to a rwticketlock structure. > + * > + * @return > + * - zero if the lock is successfully taken > + * - -EBUSY if lock could not be acquired for reading because a > + * writer holds the lock > + */ > +__rte_experimental > +static inline int > +rte_rwticket_read_trylock(rte_rwticketlock_t *rwl) { > + rte_rwticketlock_t old, new; > + int success; > + > + old.tickets = __atomic_load_n(&rwl->tickets, __ATOMIC_RELAXED); > + > + do { > + uint16_t me = old.next; /* this is our ticket */ When __atomic_compare_exchange_n fails, old.tickets needs a reload. > + > + /* does writer have the lock now? */ > + if (old.read != me && old.write != me) Check (old.read != me) should be enough? > + return -EBUSY; > + > + /* expect to be the next reader */ > + new.tickets = old.tickets; > + old.read = me; This line is unnecessary? > + new.read = new.next = me + 1; > + success = __atomic_compare_exchange_n(&rwl->tickets, > &old.tickets, new.tickets, > + 0, __ATOMIC_ACQUIRE, > __ATOMIC_RELAXED); > + } while (!success); > + > + return 0; > +} > + > +/** > + * @warning > + * @b EXPERIMENTAL: this API may change without prior notice. > + * > + * Release a read lock. > + * > + * @param rwl > + * A pointer to the rwticketlock structure. > + */ > +__rte_experimental > +static inline void > +rte_rwticket_read_unlock(rte_rwticketlock_t *rwl) { > + __atomic_add_fetch(&rwl->write, 1, __ATOMIC_RELEASE); } > + > +#ifdef __cplusplus > +} > +#endif > + > +#endif /* _RTE_TICKET_RWLOCK_H_ */ > diff --git a/lib/librte_eal/include/meson.build > b/lib/librte_eal/include/meson.build > index 0dea342e1deb..fe5c19748926 100644 > --- a/lib/librte_eal/include/meson.build > +++ b/lib/librte_eal/include/meson.build > @@ -65,6 +65,7 @@ generic_headers = files( > 'generic/rte_rwlock.h', > 'generic/rte_spinlock.h', > 'generic/rte_ticketlock.h', > + 'generic/rte_ticket_rwlock.h', > 'generic/rte_vect.h', > ) > install_headers(generic_headers, subdir: 'generic') diff --git > a/lib/librte_eal/ppc/include/meson.build > b/lib/librte_eal/ppc/include/meson.build > index dae40ede546e..0bc560327749 100644 > --- a/lib/librte_eal/ppc/include/meson.build > +++ b/lib/librte_eal/ppc/include/meson.build > @@ -16,6 +16,7 @@ arch_headers = files( > 'rte_rwlock.h', > 'rte_spinlock.h', > 'rte_ticketlock.h', > + 'rte_ticket_rwlock.h', > 'rte_vect.h', > ) > install_headers(arch_headers, subdir: get_option('include_subdir_arch')) > diff --git a/lib/librte_eal/ppc/include/rte_ticket_rwlock.h > b/lib/librte_eal/ppc/include/rte_ticket_rwlock.h > new file mode 100644 > index 000000000000..4768d5bfa8ef > --- /dev/null > +++ b/lib/librte_eal/ppc/include/rte_ticket_rwlock.h > @@ -0,0 +1,18 @@ > +/* SPDX-License-Identifier: BSD-3-Clause > + * Copyright(c) 2021 Microsoft Corporation */ > + > +#ifndef _RTE_FAIR_RWLOCK_PPC_64_H_ > +#define _RTE_FAIR_RWLOCK_PPC_64_H_ > + > +#ifdef __cplusplus > +extern "C" { > +#endif > + > +#include "generic/rte_ticket_rwlock.h" > + > +#ifdef __cplusplus > +} > +#endif > + > +#endif /* _RTE_FAIR_RWLOCK_PPC_64_H_ */ > diff --git a/lib/librte_eal/x86/include/meson.build > b/lib/librte_eal/x86/include/meson.build > index 549cc21a42ed..e9169f0d1da5 100644 > --- a/lib/librte_eal/x86/include/meson.build > +++ b/lib/librte_eal/x86/include/meson.build > @@ -20,6 +20,7 @@ arch_headers = files( > 'rte_rwlock.h', > 'rte_spinlock.h', > 'rte_ticketlock.h', > + 'rte_ticket_rwlock.h', > 'rte_vect.h', > ) > install_headers(arch_headers, subdir: get_option('include_subdir_arch')) > diff --git a/lib/librte_eal/x86/include/rte_ticket_rwlock.h > b/lib/librte_eal/x86/include/rte_ticket_rwlock.h > new file mode 100644 > index 000000000000..83c8bd0899d3 > --- /dev/null > +++ b/lib/librte_eal/x86/include/rte_ticket_rwlock.h > @@ -0,0 +1,18 @@ > +/* SPDX-License-Identifier: BSD-3-Clause > + * Copyright(c) 2021 Microsoft Corporation */ > + > +#ifndef _RTE_FAIR_RWLOCK_X86_64_H_ > +#define _RTE_FAIR_RWLOCK_X86_64_H_ > + > +#ifdef __cplusplus > +extern "C" { > +#endif > + > +#include "generic/rte_ticket_rwlock.h" > + > +#ifdef __cplusplus > +} > +#endif > + > +#endif /* _RTE_FAIR_RWLOCK_X86_64_H_ */ > -- > 2.29.2
