Thread (27 messages) 27 messages, 5 authors, 2021-04-14

Re: [dpdk-dev] [PATCH v1] eal: add ticket based reader writer lock

From: Ruifeng Wang <hidden>
Date: 2021-01-27 10:26:48

-----Original Message-----
From: dev <redacted> On Behalf Of Stephen Hemminger
Sent: Friday, January 15, 2021 1:35 AM
To: dev@dpdk.org
Cc: Stephen Hemminger <stephen@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 <stephen@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>
quoted hunk ↗ jump to hunk
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?
quoted hunk ↗ jump to hunk
+		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
  
Keyboard shortcuts
hback out one level
jnext message in thread
kprevious message in thread
ldrill in
Escclose help / fold thread tree
?toggle this help