All of lore.kernel.org
 help / color / mirror / Atom feed
From: Thomas Gleixner <tglx@linutronix.de>
To: LKML <linux-kernel@vger.kernel.org>
Cc: Peter Zijlstra <peterz@infradead.org>,
	Ingo Molnar <mingo@kernel.org>,
	Juri Lelli <juri.lelli@redhat.com>,
	Steven Rostedt <rostedt@goodmis.org>,
	Daniel Bristot de Oliveira <bristot@redhat.com>,
	Will Deacon <will@kernel.org>, Waiman Long <longman@redhat.com>,
	Boqun Feng <boqun.feng@gmail.com>,
	Sebastian Andrzej Siewior <bigeasy@linutronix.de>,
	Davidlohr Bueso <dave@stgolabs.net>,
	Mike Galbraith <efault@gmx.de>
Subject: [patch V4 16/68] locking: Add base code for RT rw_semaphore and rwlock
Date: Wed, 11 Aug 2021 14:22:50 +0200 (CEST)	[thread overview]
Message-ID: <20210811121415.103224895@linutronix.de> (raw)
In-Reply-To: 20210811120348.855823694@linutronix.de

From: Thomas Gleixner <tglx@linutronix.de>

On PREEMPT_RT rw_semaphores and rwlocks are substituted with a rtmutex and
a reader count. The implementation is writer unfair as it is not feasible
to do priority inheritance on multiple readers, but experience has shown
that realtime workloads are not the typical workloads which are sensitive
to writer starvation.

The inner workings of rw_semaphores and rwlocks on RT are almost identical
except for the task state and signal handling. rw_semaphores are not state
preserving over a contention, they are expected to enter and leave with state
== TASK_RUNNING. rwlocks have a mechanism to preserve the state of the task
at entry and restore it after unblocking taking potential non-lock related
wakeups into account. rw_semaphores can also be subject to signal handling
interrupting a blocked state, while rwlocks ignore signals.

To avoid code duplication, provide a shared implementation which takes the
small difference vs. state and signals into account. The code is included
into the relevant rw_semaphore/rwlock base code and compiled for each use
case separately.

Signed-off-by: Thomas Gleixner <tglx@linutronix.de>
---
 include/linux/rwbase_rt.h  |   38 ++++++
 kernel/locking/rwbase_rt.c |  263 +++++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 301 insertions(+)
 create mode 100644 include/linux/rwbase_rt.h
 create mode 100644 kernel/locking/rwbase_rt.c
---
--- /dev/null
+++ b/include/linux/rwbase_rt.h
@@ -0,0 +1,38 @@
+// SPDX-License-Identifier: GPL-2.0-only
+#ifndef _LINUX_RW_BASE_RT_H
+#define _LINUX_RW_BASE_RT_H
+
+#include <linux/rtmutex.h>
+#include <linux/atomic.h>
+
+#define READER_BIAS		(1U << 31)
+#define WRITER_BIAS		(1U << 30)
+
+struct rwbase_rt {
+	atomic_t		readers;
+	struct rt_mutex_base	rtmutex;
+};
+
+#define __RWBASE_INITIALIZER(name)				\
+{								\
+	.readers = ATOMIC_INIT(READER_BIAS),			\
+	.rtmutex = __RT_MUTEX_BASE_INITIALIZER(name.rtmutex),	\
+}
+
+#define init_rwbase_rt(rwbase)					\
+	do {							\
+		rt_mutex_base_init(&(rwbase)->rtmutex);		\
+		atomic_set(&(rwbase)->readers, READER_BIAS);	\
+	} while (0)
+
+
+static __always_inline bool rw_base_is_locked(struct rwbase_rt *rwb)
+{
+	return atomic_read(&rwb->readers) != READER_BIAS;
+}
+
+static __always_inline bool rw_base_is_contended(struct rwbase_rt *rwb)
+{
+	return atomic_read(&rwb->readers) > 0;
+}
+#endif
--- /dev/null
+++ b/kernel/locking/rwbase_rt.c
@@ -0,0 +1,263 @@
+// SPDX-License-Identifier: GPL-2.0-only
+
+/*
+ * RT-specific reader/writer semaphores and reader/writer locks
+ *
+ * down_write/write_lock()
+ *  1) Lock rtmutex
+ *  2) Remove the reader BIAS to force readers into the slow path
+ *  3) Wait until all readers have left the critical region
+ *  4) Mark it write locked
+ *
+ * up_write/write_unlock()
+ *  1) Remove the write locked marker
+ *  2) Set the reader BIAS so readers can use the fast path again
+ *  3) Unlock rtmutex to release blocked readers
+ *
+ * down_read/read_lock()
+ *  1) Try fast path acquisition (reader BIAS is set)
+ *  2) Take tmutex::wait_lock which protects the writelocked flag
+ *  3) If !writelocked, acquire it for read
+ *  4) If writelocked, block on tmutex
+ *  5) unlock rtmutex, goto 1)
+ *
+ * up_read/read_unlock()
+ *  1) Try fast path release (reader count != 1)
+ *  2) Wake the writer waiting in down_write()/write_lock() #3
+ *
+ * down_read/read_lock()#3 has the consequence, that rw semaphores and rw
+ * locks on RT are not writer fair, but writers, which should be avoided in
+ * RT tasks (think mmap_sem), are subject to the rtmutex priority/DL
+ * inheritance mechanism.
+ *
+ * It's possible to make the rw primitives writer fair by keeping a list of
+ * active readers. A blocked writer would force all newly incoming readers
+ * to block on the rtmutex, but the rtmutex would have to be proxy locked
+ * for one reader after the other. We can't use multi-reader inheritance
+ * because there is no way to support that with SCHED_DEADLINE.
+ * Implementing the one by one reader boosting/handover mechanism is a
+ * major surgery for a very dubious value.
+ *
+ * The risk of writer starvation is there, but the pathological use cases
+ * which trigger it are not necessarily the typical RT workloads.
+ *
+ * Common code shared between RT rw_semaphore and rwlock
+ */
+
+static __always_inline int rwbase_read_trylock(struct rwbase_rt *rwb)
+{
+	int r;
+
+	/*
+	 * Increment reader count, if sem->readers < 0, i.e. READER_BIAS is
+	 * set.
+	 */
+	for (r = atomic_read(&rwb->readers); r < 0;) {
+		if (likely(atomic_try_cmpxchg(&rwb->readers, &r, r + 1)))
+			return 1;
+	}
+	return 0;
+}
+
+static int __sched __rwbase_read_lock(struct rwbase_rt *rwb,
+				      unsigned int state)
+{
+	struct rt_mutex_base *rtm = &rwb->rtmutex;
+	int ret;
+
+	raw_spin_lock_irq(&rtm->wait_lock);
+	/*
+	 * Allow readers as long as the writer has not completely
+	 * acquired the semaphore for write.
+	 */
+	if (atomic_read(&rwb->readers) != WRITER_BIAS) {
+		atomic_inc(&rwb->readers);
+		raw_spin_unlock_irq(&rtm->wait_lock);
+		return 0;
+	}
+
+	/*
+	 * Call into the slow lock path with the rtmutex->wait_lock
+	 * held, so this can't result in the following race:
+	 *
+	 * Reader1		Reader2		Writer
+	 *			down_read()
+	 *					down_write()
+	 *					rtmutex_lock(m)
+	 *					wait()
+	 * down_read()
+	 * unlock(m->wait_lock)
+	 *			up_read()
+	 *			wake(Writer)
+	 *					lock(m->wait_lock)
+	 *					sem->writelocked=true
+	 *					unlock(m->wait_lock)
+	 *
+	 *					up_write()
+	 *					sem->writelocked=false
+	 *					rtmutex_unlock(m)
+	 *			down_read()
+	 *					down_write()
+	 *					rtmutex_lock(m)
+	 *					wait()
+	 * rtmutex_lock(m)
+	 *
+	 * That would put Reader1 behind the writer waiting on
+	 * Reader2 to call up_read() which might be unbound.
+	 */
+
+	/*
+	 * For rwlocks this returns 0 unconditionally, so the below
+	 * !ret conditionals are optimized out.
+	 */
+	ret = rwbase_rtmutex_slowlock_locked(rtm, state);
+
+	/*
+	 * On success the rtmutex is held, so there can't be a writer
+	 * active. Increment the reader count and immediately drop the
+	 * rtmutex again.
+	 *
+	 * rtmutex->wait_lock has to be unlocked in any case of course.
+	 */
+	if (!ret)
+		atomic_inc(&rwb->readers);
+	raw_spin_unlock_irq(&rtm->wait_lock);
+	if (!ret)
+		rwbase_rtmutex_unlock(rtm);
+	return ret;
+}
+
+static __always_inline int rwbase_read_lock(struct rwbase_rt *rwb,
+					    unsigned int state)
+{
+	if (rwbase_read_trylock(rwb))
+		return 0;
+
+	return __rwbase_read_lock(rwb, state);
+}
+
+static void __sched __rwbase_read_unlock(struct rwbase_rt *rwb,
+					 unsigned int state)
+{
+	struct rt_mutex_base *rtm = &rwb->rtmutex;
+	struct task_struct *owner;
+
+	raw_spin_lock_irq(&rtm->wait_lock);
+	/*
+	 * Wake the writer, i.e. the rtmutex owner. It might release the
+	 * rtmutex concurrently in the fast path (due to a signal), but to
+	 * clean up rwb->readers it needs to acquire rtm->wait_lock. The
+	 * worst case which can happen is a spurious wakeup.
+	 */
+	owner = rt_mutex_owner(rtm);
+	if (owner)
+		wake_up_state(owner, state);
+
+	raw_spin_unlock_irq(&rtm->wait_lock);
+}
+
+static __always_inline void rwbase_read_unlock(struct rwbase_rt *rwb,
+					       unsigned int state)
+{
+	/*
+	 * rwb->readers can only hit 0 when a writer is waiting for the
+	 * active readers to leave the critical region.
+	 */
+	if (unlikely(atomic_dec_and_test(&rwb->readers)))
+		__rwbase_read_unlock(rwb, state);
+}
+
+static inline void __rwbase_write_unlock(struct rwbase_rt *rwb, int bias,
+					 unsigned long flags)
+{
+	struct rt_mutex_base *rtm = &rwb->rtmutex;
+
+	atomic_add(READER_BIAS - bias, &rwb->readers);
+	raw_spin_unlock_irqrestore(&rtm->wait_lock, flags);
+	rwbase_rtmutex_unlock(rtm);
+}
+
+static inline void rwbase_write_unlock(struct rwbase_rt *rwb)
+{
+	struct rt_mutex_base *rtm = &rwb->rtmutex;
+	unsigned long flags;
+
+	raw_spin_lock_irqsave(&rtm->wait_lock, flags);
+	__rwbase_write_unlock(rwb, WRITER_BIAS, flags);
+}
+
+static inline void rwbase_write_downgrade(struct rwbase_rt *rwb)
+{
+	struct rt_mutex_base *rtm = &rwb->rtmutex;
+	unsigned long flags;
+
+	raw_spin_lock_irqsave(&rtm->wait_lock, flags);
+	/* Release it and account current as reader */
+	__rwbase_write_unlock(rwb, WRITER_BIAS - 1, flags);
+}
+
+static int __sched rwbase_write_lock(struct rwbase_rt *rwb,
+				     unsigned int state)
+{
+	struct rt_mutex_base *rtm = &rwb->rtmutex;
+	unsigned long flags;
+
+	/* Take the rtmutex as a first step */
+	if (rwbase_rtmutex_lock_state(rtm, state))
+		return -EINTR;
+
+	/* Force readers into slow path */
+	atomic_sub(READER_BIAS, &rwb->readers);
+
+	raw_spin_lock_irqsave(&rtm->wait_lock, flags);
+	/*
+	 * set_current_state() for rw_semaphore
+	 * current_save_and_set_rtlock_wait_state() for rwlock
+	 */
+	rwbase_set_and_save_current_state(state);
+
+	/* Block until all readers have left the critical region. */
+	for (; atomic_read(&rwb->readers);) {
+		/* Optimized out for rwlocks */
+		if (rwbase_signal_pending_state(state, current)) {
+			__set_current_state(TASK_RUNNING);
+			__rwbase_write_unlock(rwb, 0, flags);
+			return -EINTR;
+		}
+		raw_spin_unlock_irqrestore(&rtm->wait_lock, flags);
+
+		/*
+		 * Schedule and wait for the readers to leave the critical
+		 * section. The last reader leaving it wakes the waiter.
+		 */
+		if (atomic_read(&rwb->readers) != 0)
+			rwbase_schedule();
+		set_current_state(state);
+		raw_spin_lock_irqsave(&rtm->wait_lock, flags);
+	}
+
+	atomic_set(&rwb->readers, WRITER_BIAS);
+	rwbase_restore_current_state();
+	raw_spin_unlock_irqrestore(&rtm->wait_lock, flags);
+	return 0;
+}
+
+static inline int rwbase_write_trylock(struct rwbase_rt *rwb)
+{
+	struct rt_mutex_base *rtm = &rwb->rtmutex;
+	unsigned long flags;
+
+	if (!rwbase_rtmutex_trylock(rtm))
+		return 0;
+
+	atomic_sub(READER_BIAS, &rwb->readers);
+
+	raw_spin_lock_irqsave(&rtm->wait_lock, flags);
+	if (!atomic_read(&rwb->readers)) {
+		atomic_set(&rwb->readers, WRITER_BIAS);
+		raw_spin_unlock_irqrestore(&rtm->wait_lock, flags);
+		return 1;
+	}
+	__rwbase_write_unlock(rwb, 0, flags);
+	return 0;
+}


  parent reply	other threads:[~2021-08-11 12:24 UTC|newest]

Thread overview: 70+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2021-08-11 12:22 [patch V4 00/68] locking, sched: The PREEMPT-RT locking infrastructure Thomas Gleixner
2021-08-11 12:22 ` [patch V4 01/68] sched: Split out the wakeup state check Thomas Gleixner
2021-08-11 12:22 ` [patch V4 02/68] sched: Introduce TASK_RTLOCK_WAIT Thomas Gleixner
2021-08-11 12:22 ` [patch V4 03/68] sched: Reorganize current::__state helpers Thomas Gleixner
2021-08-11 12:22 ` [patch V4 04/68] sched: Prepare for RT sleeping spin/rwlocks Thomas Gleixner
2021-08-11 12:22 ` [patch V4 05/68] sched: Rework the __schedule() preempt argument Thomas Gleixner
2021-08-11 12:22 ` [patch V4 06/68] sched: Provide schedule point for RT locks Thomas Gleixner
2021-08-11 12:22 ` [patch V4 07/68] sched/wake_q: Provide WAKE_Q_HEAD_INITIALIZER Thomas Gleixner
2021-08-11 12:22 ` [patch V4 08/68] media/atomisp: Use lockdep instead of *mutex_is_locked() Thomas Gleixner
2021-08-11 12:22 ` [patch V4 09/68] rtmutex: Remove rt_mutex_is_locked() Thomas Gleixner
2021-08-11 12:22 ` [patch V4 10/68] rtmutex: Convert macros to inlines Thomas Gleixner
2021-08-11 12:22 ` [patch V4 11/68] rtmutex: Switch to try_cmpxchg() Thomas Gleixner
2021-08-11 12:22 ` [patch V4 12/68] rtmutex: Split API and implementation Thomas Gleixner
2021-08-11 12:22 ` [patch V4 13/68] rtmutex: Split out the inner parts of struct rtmutex Thomas Gleixner
2021-08-11 12:22 ` [patch V4 14/68] locking/rtmutex: Provide rt_mutex_slowlock_locked() Thomas Gleixner
2021-08-11 12:22 ` [patch V4 15/68] rtmutex: Provide rt_mutex_base_is_locked() Thomas Gleixner
2021-08-11 12:22 ` Thomas Gleixner [this message]
2021-08-11 12:22 ` [patch V4 17/68] locking/rwsem: Add rtmutex based R/W semaphore implementation Thomas Gleixner
2021-08-11 12:22 ` [patch V4 18/68] locking/rtmutex: Add wake_state to rt_mutex_waiter Thomas Gleixner
2021-08-11 12:22 ` [patch V4 19/68] locking/rtmutex: Provide rt_wake_q and helpers Thomas Gleixner
2021-08-11 12:22 ` [patch V4 20/68] locking/rtmutex: Use rt_mutex_wake_q_head Thomas Gleixner
2021-08-11 12:22 ` [patch V4 21/68] locking/rtmutex: Prepare RT rt_mutex_wake_q for RT locks Thomas Gleixner
2021-08-11 12:22 ` [patch V4 22/68] locking/rtmutex: Guard regular sleeping locks specific functions Thomas Gleixner
2021-08-11 12:22 ` [patch V4 23/68] locking/spinlock: Split the lock types header Thomas Gleixner
2021-08-11 12:23 ` [patch V4 24/68] locking/rtmutex: Prevent future include recursion hell Thomas Gleixner
2021-08-11 12:23 ` [patch V4 25/68] locking/lockdep: Reduce includes in debug_locks.h Thomas Gleixner
2021-08-11 12:23 ` [patch V4 26/68] rbtree: Split out the rbtree type definitions Thomas Gleixner
2021-08-11 12:23 ` [patch V4 27/68] locking/rtmutex: Include only rbtree types Thomas Gleixner
2021-08-11 12:23 ` [patch V4 28/68] locking/spinlock: Provide RT specific spinlock type Thomas Gleixner
2021-08-11 12:23 ` [patch V4 29/68] locking/spinlock: Provide RT variant header Thomas Gleixner
2021-08-11 12:23 ` [patch V4 30/68] locking/rtmutex: Provide the spin/rwlock core lock function Thomas Gleixner
2021-08-11 12:23 ` [patch V4 31/68] locking/spinlock: Provide RT variant Thomas Gleixner
2021-08-11 12:23 ` [patch V4 32/68] locking/rwlock: " Thomas Gleixner
2021-08-11 12:23 ` [patch V4 33/68] locking/rtmutex: Squash !RT tasks to DEFAULT_PRIO Thomas Gleixner
2021-08-11 12:23 ` [patch V4 34/68] locking/mutex: Consolidate core headers Thomas Gleixner
2021-08-11 12:23 ` [patch V4 35/68] locking/mutex: Move waiter to core header Thomas Gleixner
2021-08-11 12:23 ` [patch V4 36/68] locking/ww_mutex: Move ww_mutex declarations into ww_mutex.h Thomas Gleixner
2021-08-11 12:23 ` [patch V4 37/68] locking/mutex: Make mutex::wait_lock raw Thomas Gleixner
2021-08-11 12:23 ` [patch V4 38/68] locking/ww_mutex: Simplify lockdep annotation Thomas Gleixner
2021-08-11 12:23 ` [patch V4 39/68] locking/ww_mutex: Gather mutex_waiter initialization Thomas Gleixner
2021-08-11 12:23 ` [patch V4 40/68] locking/ww_mutex: Split up ww_mutex_unlock() Thomas Gleixner
2021-08-11 12:23 ` [patch V4 41/68] locking/ww_mutex: Split W/W implementation logic Thomas Gleixner
2021-08-11 12:23 ` [patch V4 42/68] locking/ww_mutex: Remove __sched annotation Thomas Gleixner
2021-08-11 12:23 ` [patch V4 43/68] locking/ww_mutex: Abstract waiter iteration Thomas Gleixner
2021-08-11 12:23 ` [patch V4 44/68] locking/ww_mutex: Abstract waiter enqueueing Thomas Gleixner
2021-08-11 12:23 ` [patch V4 45/68] locking/ww_mutex: Abstract mutex accessors Thomas Gleixner
2021-08-11 12:23 ` [patch V4 46/68] locking/ww_mutex: Abstract mutex types Thomas Gleixner
2021-08-11 12:23 ` [patch V4 47/68] locking/ww_mutex: Abstract internal lock access Thomas Gleixner
2021-08-11 12:23 ` [patch V4 48/68] locking/ww_mutex: Implement rt_mutex accessors Thomas Gleixner
2021-08-11 12:23 ` [patch V4 49/68] locking/ww_mutex: Add RT priority to W/W order Thomas Gleixner
2021-08-11 12:23 ` [patch V4 50/68] locking/ww_mutex: Add rt_mutex based lock type and accessors Thomas Gleixner
2021-08-11 12:23 ` [patch V4 51/68] locking/rtmutex: Extend the rtmutex core to support ww_mutex Thomas Gleixner
2021-08-11 12:23 ` [patch V4 52/68] locking/ww_mutex: Implement rtmutex based ww_mutex API functions Thomas Gleixner
2021-08-11 12:23 ` [patch V4 53/68] locking/rtmutex: Add mutex variant for RT Thomas Gleixner
2021-08-11 12:23 ` [patch V4 54/68] lib/test_lockup: Adapt to changed variables Thomas Gleixner
2021-08-11 12:23 ` [patch V4 55/68] futex: Validate waiter correctly in futex_proxy_trylock_atomic() Thomas Gleixner
2021-08-11 12:23 ` [patch V4 56/68] futex: Cleanup stale comments Thomas Gleixner
2021-08-11 12:23 ` [patch V4 57/68] futex: Clarify futex_requeue() PI handling Thomas Gleixner
2021-08-11 12:23 ` [patch V4 58/68] futex: Remove bogus condition for requeue PI Thomas Gleixner
2021-08-11 12:23 ` [patch V4 59/68] futex: Correct the number of requeued waiters for PI Thomas Gleixner
2021-08-11 12:23 ` [patch V4 60/68] futex: Restructure futex_requeue() Thomas Gleixner
2021-08-11 12:23 ` [patch V4 61/68] futex: Clarify comment in futex_requeue() Thomas Gleixner
2021-08-11 12:23 ` [patch V4 62/68] futex: Reorder sanity checks " Thomas Gleixner
2021-08-11 12:23 ` [patch V4 63/68] futex: Simplify handle_early_requeue_pi_wakeup() Thomas Gleixner
2021-08-11 12:23 ` [patch V4 64/68] futex: Prevent requeue_pi() lock nesting issue on RT Thomas Gleixner
2021-08-11 12:23 ` [patch V4 65/68] rtmutex: Prevent lockdep false positive with PI futexes Thomas Gleixner
2021-08-11 12:23 ` [patch V4 66/68] preempt: Adjust PREEMPT_LOCK_OFFSET for RT Thomas Gleixner
2021-08-11 12:23 ` [patch V4 67/68] locking/rtmutex: Implement equal priority lock stealing Thomas Gleixner
2021-08-11 12:23 ` [patch V4 68/68] locking/rtmutex: Add adaptive spinwait mechanism Thomas Gleixner
2021-08-13  8:05 ` [patch V4 69/68] locking/rt: Add missing __might_sleep() to spin/rwlocks Thomas Gleixner

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=20210811121415.103224895@linutronix.de \
    --to=tglx@linutronix.de \
    --cc=bigeasy@linutronix.de \
    --cc=boqun.feng@gmail.com \
    --cc=bristot@redhat.com \
    --cc=dave@stgolabs.net \
    --cc=efault@gmx.de \
    --cc=juri.lelli@redhat.com \
    --cc=linux-kernel@vger.kernel.org \
    --cc=longman@redhat.com \
    --cc=mingo@kernel.org \
    --cc=peterz@infradead.org \
    --cc=rostedt@goodmis.org \
    --cc=will@kernel.org \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line before the message body.
This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.