From: Thomas Gleixner <tglx@linutronix•de>
To: paulmck@kernel•org
Cc: linux-usb@vger•kernel.org, linux-ia64@vger•kernel.org,
Peter Zijlstra <peterz@infradead•org>,
linux-pci@vger•kernel.org,
Sebastian Siewior <bigeasy@linutronix•de>,
Oleg Nesterov <oleg@redhat•com>, Guo Ren <guoren@kernel•org>,
Joel Fernandes <joel@joelfernandes•org>,
Vincent Chen <deanbo422@gmail•com>,
Ingo Molnar <mingo@kernel•org>,
Davidlohr Bueso <dave@stgolabs•net>,
linux-acpi@vger•kernel.org, Brian Cain <bcain@codeaurora•org>,
Jonathan Corbet <corbet@lwn•net>,
linux-hexagon@vger•kernel.org,
"Rafael J. Wysocki" <rafael.j.wysocki@intel•com>,
linux-csky@vger•kernel.org,
Linus Torvalds <torvalds@linux-foundation•org>,
Darren Hart <dvhart@infradead•org>,
Zhang Rui <rui.zhang@intel•com>, Len Brown <lenb@kernel•org>,
Fenghua Yu <fenghua.yu@intel•com>, Arnd Bergmann <arnd@arndb•de>,
linux-pm@vger•kernel.org, linuxppc-dev@lists•ozlabs.org,
Greentime Hu <green.hu@gmail•com>,
Bjorn Helgaas <bhelgaas@google•com>,
Kurt Schwemmer <kurt.schwemmer@microsemi•com>,
platform-driver-x86@vger•kernel.org,
Kalle Valo <kvalo@codeaurora•org>,
kbuild test robot <lkp@intel•com>,
Felipe Balbi <balbi@kernel•org>, Michal Simek <monstr@monstr•eu>,
Tony Luck <tony.luck@intel•com>, Nick Hu <nickhu@andestech•com>,
Geoff Levand <geoff@infradead•org>,
netdev@vger•kernel.org, Randy Dunlap <rdunlap@infradead•org>,
linux-wireless@vger•kernel.org,
LKML <linux-kernel@vger•kernel.org>,
Davidlohr Bueso <dbueso@suse•de>,
Greg Kroah-Hartman <gregkh@linuxfoundation•org>,
Logan Gunthorpe <logang@deltatee•com>,
"David S. Miller" <davem@davemloft•net>,
Andy Shevchenko <andy@infradead•org>
Subject: Documentation/locking/locktypes: Further clarifications and wordsmithing
Date: Wed, 25 Mar 2020 13:27:49 +0100 [thread overview]
Message-ID: <87wo78y5yy.fsf@nanos.tec.linutronix.de> (raw)
In-Reply-To: <20200325002811.GO19865@paulmck-ThinkPad-P72>
The documentation of rw_semaphores is wrong as it claims that the non-owner
reader release is not supported by RT. That's just history biased memory
distortion.
Split the 'Owner semantics' section up and add separate sections for
semaphore and rw_semaphore to reflect reality.
Aside of that the following updates are done:
- Add pseudo code to document the spinlock state preserving mechanism on
PREEMPT_RT
- Wordsmith the bitspinlock and lock nesting sections
Co-developed-by: Paul McKenney <paulmck@kernel•org>
Signed-off-by: Paul McKenney <paulmck@kernel•org>
Signed-off-by: Thomas Gleixner <tglx@linutronix•de>
---
Documentation/locking/locktypes.rst | 150 +++++++++++++++++++++++-------------
1 file changed, 99 insertions(+), 51 deletions(-)
--- a/Documentation/locking/locktypes.rst
+++ b/Documentation/locking/locktypes.rst
@@ -67,6 +67,17 @@ Spinning locks implicitly disable preemp
_irqsave/restore() Save and disable / restore interrupt disabled state
=================== ====================================================
+Owner semantics
+===============
+
+The aforementioned lock types except semaphores have strict owner
+semantics:
+
+ The context (task) that acquired the lock must release it.
+
+rw_semaphores have a special interface which allows non-owner release for
+readers.
+
rtmutex
=======
@@ -83,6 +94,51 @@ interrupt handlers and soft interrupts.
and rwlock_t to be implemented via RT-mutexes.
+semaphore
+=========
+
+semaphore is a counting semaphore implementation.
+
+Semaphores are often used for both serialization and waiting, but new use
+cases should instead use separate serialization and wait mechanisms, such
+as mutexes and completions.
+
+semaphores and PREEMPT_RT
+----------------------------
+
+PREEMPT_RT does not change the semaphore implementation because counting
+semaphores have no concept of owners, thus preventing PREEMPT_RT from
+providing priority inheritance for semaphores. After all, an unknown
+owner cannot be boosted. As a consequence, blocking on semaphores can
+result in priority inversion.
+
+
+rw_semaphore
+============
+
+rw_semaphore is a multiple readers and single writer lock mechanism.
+
+On non-PREEMPT_RT kernels the implementation is fair, thus preventing
+writer starvation.
+
+rw_semaphore complies by default with the strict owner semantics, but there
+exist special-purpose interfaces that allow non-owner release for readers.
+These work independent of the kernel configuration.
+
+rw_semaphore and PREEMPT_RT
+---------------------------
+
+PREEMPT_RT kernels map rw_semaphore to a separate rt_mutex-based
+implementation, thus changing the fairness:
+
+ Because an rw_semaphore writer cannot grant its priority to multiple
+ readers, a preempted low-priority reader will continue holding its lock,
+ thus starving even high-priority writers. In contrast, because readers
+ can grant their priority to a writer, a preempted low-priority writer will
+ have its priority boosted until it releases the lock, thus preventing that
+ writer from starving readers.
+
+
raw_spinlock_t and spinlock_t
=============================
@@ -102,7 +158,7 @@ critical section is tiny, thus avoiding
spinlock_t
----------
-The semantics of spinlock_t change with the state of CONFIG_PREEMPT_RT.
+The semantics of spinlock_t change with the state of PREEMPT_RT.
On a non PREEMPT_RT enabled kernel spinlock_t is mapped to raw_spinlock_t
and has exactly the same semantics.
@@ -140,7 +196,16 @@ On a PREEMPT_RT enabled kernel spinlock_
kernels leave task state untouched. However, PREEMPT_RT must change
task state if the task blocks during acquisition. Therefore, it saves
the current task state before blocking and the corresponding lock wakeup
- restores it.
+ restores it, as shown below::
+
+ task->state = TASK_INTERRUPTIBLE
+ lock()
+ block()
+ task->saved_state = task->state
+ task->state = TASK_UNINTERRUPTIBLE
+ schedule()
+ lock wakeup
+ task->state = task->saved_state
Other types of wakeups would normally unconditionally set the task state
to RUNNING, but that does not work here because the task must remain
@@ -148,7 +213,22 @@ On a PREEMPT_RT enabled kernel spinlock_
wakeup attempts to awaken a task blocked waiting for a spinlock, it
instead sets the saved state to RUNNING. Then, when the lock
acquisition completes, the lock wakeup sets the task state to the saved
- state, in this case setting it to RUNNING.
+ state, in this case setting it to RUNNING::
+
+ task->state = TASK_INTERRUPTIBLE
+ lock()
+ block()
+ task->saved_state = task->state
+ task->state = TASK_UNINTERRUPTIBLE
+ schedule()
+ non lock wakeup
+ task->saved_state = TASK_RUNNING
+
+ lock wakeup
+ task->state = task->saved_state
+
+ This ensures that the real wakeup cannot be lost.
+
rwlock_t
========
@@ -228,17 +308,16 @@ while holding normal non-raw spinlocks b
bit spinlocks
-------------
-Bit spinlocks are problematic for PREEMPT_RT as they cannot be easily
-substituted by an RT-mutex based implementation for obvious reasons.
-
-The semantics of bit spinlocks are preserved on PREEMPT_RT kernels and the
-caveats vs. raw_spinlock_t apply.
-
-Some bit spinlocks are substituted by regular spinlock_t for PREEMPT_RT but
-this requires conditional (#ifdef'ed) code changes at the usage site while
-the spinlock_t substitution is simply done by the compiler and the
-conditionals are restricted to header files and core implementation of the
-locking primitives and the usage sites do not require any changes.
+PREEMPT_RT cannot substitute bit spinlocks because a single bit is too
+small to accommodate an RT-mutex. Therefore, the semantics of bit
+spinlocks are preserved on PREEMPT_RT kernels, so that the raw_spinlock_t
+caveats also apply to bit spinlocks.
+
+Some bit spinlocks are replaced with regular spinlock_t for PREEMPT_RT
+using conditional (#ifdef'ed) code changes at the usage site. In contrast,
+usage-site changes are not needed for the spinlock_t substitution.
+Instead, conditionals in header files and the core locking implemementation
+enable the compiler to do the substitution transparently.
Lock type nesting rules
@@ -254,46 +333,15 @@ Lock type nesting rules
- Spinning lock types can nest inside sleeping lock types.
-These rules apply in general independent of CONFIG_PREEMPT_RT.
+These constraints apply both in PREEMPT_RT and otherwise.
-As PREEMPT_RT changes the lock category of spinlock_t and rwlock_t from
-spinning to sleeping this has obviously restrictions how they can nest with
-raw_spinlock_t.
-
-This results in the following nest ordering:
+The fact that PREEMPT_RT changes the lock category of spinlock_t and
+rwlock_t from spinning to sleeping means that they cannot be acquired while
+holding a raw spinlock. This results in the following nesting ordering:
1) Sleeping locks
2) spinlock_t and rwlock_t
3) raw_spinlock_t and bit spinlocks
-Lockdep is aware of these constraints to ensure that they are respected.
-
-
-Owner semantics
-===============
-
-Most lock types in the Linux kernel have strict owner semantics, i.e. the
-context (task) which acquires a lock has to release it.
-
-There are two exceptions:
-
- - semaphores
- - rwsems
-
-semaphores have no owner semantics for historical reason, and as such
-trylock and release operations can be called from any context. They are
-often used for both serialization and waiting purposes. That's generally
-discouraged and should be replaced by separate serialization and wait
-mechanisms, such as mutexes and completions.
-
-rwsems have grown interfaces which allow non owner release for special
-purposes. This usage is problematic on PREEMPT_RT because PREEMPT_RT
-substitutes all locking primitives except semaphores with RT-mutex based
-implementations to provide priority inheritance for all lock types except
-the truly spinning ones. Priority inheritance on ownerless locks is
-obviously impossible.
-
-For now the rwsem non-owner release excludes code which utilizes it from
-being used on PREEMPT_RT enabled kernels. In same cases this can be
-mitigated by disabling portions of the code, in other cases the complete
-functionality has to be disabled until a workable solution has been found.
+Lockdep will complain if these constraints are violated, both in
+PREEMPT_RT and otherwise.
next prev parent reply other threads:[~2020-03-25 12:32 UTC|newest]
Thread overview: 41+ messages / expand[flat|nested] mbox.gz Atom feed top
2020-03-21 11:25 [patch V3 00/20] Lock ordering documentation and annotation for lockdep Thomas Gleixner
2020-03-21 11:25 ` [patch V3 01/20] PCI/switchtec: Fix init_completion race condition with poll_wait() Thomas Gleixner
2020-03-21 11:25 ` [patch V3 02/20] pci/switchtec: Replace completion wait queue usage for poll Thomas Gleixner
2020-03-21 11:25 ` [patch V3 03/20] usb: gadget: Use completion interface instead of open coding it Thomas Gleixner
2020-03-25 8:37 ` Felipe Balbi
2020-03-27 12:14 ` Sebastian Siewior
2020-03-21 11:25 ` [patch V3 04/20] orinoco_usb: Use the regular completion interfaces Thomas Gleixner
2020-03-22 14:42 ` Kalle Valo
2020-03-21 11:25 ` [patch V3 05/20] acpi: Remove header dependency Thomas Gleixner
2020-03-21 12:23 ` Andy Shevchenko
2020-03-22 7:02 ` Rafael J. Wysocki
2020-03-21 11:25 ` [patch V3 06/20] nds32: Remove mm.h from asm/uaccess.h Thomas Gleixner
2020-03-21 11:25 ` [patch V3 07/20] csky: " Thomas Gleixner
2020-03-21 11:25 ` [patch V3 08/20] hexagon: " Thomas Gleixner
2020-03-23 21:46 ` Brian Cain
2020-03-21 11:25 ` [patch V3 09/20] ia64: " Thomas Gleixner
2020-03-21 11:25 ` [patch V3 10/20] microblaze: " Thomas Gleixner
2020-03-21 11:25 ` [patch V3 11/20] rcuwait: Add @state argument to rcuwait_wait_event() Thomas Gleixner
2020-03-21 11:25 ` [patch V3 12/20] powerpc/ps3: Convert half completion to rcuwait Thomas Gleixner
2020-03-21 13:22 ` Thomas Gleixner
2020-03-27 19:14 ` Geoff Levand
2020-03-21 11:25 ` [patch V3 13/20] Documentation: Add lock ordering and nesting documentation Thomas Gleixner
2020-03-23 2:55 ` Paul E. McKenney
2020-03-24 23:13 ` Thomas Gleixner
2020-03-25 0:28 ` Paul E. McKenney
2020-03-25 12:27 ` Thomas Gleixner [this message]
2020-03-25 16:02 ` Documentation/locking/locktypes: Further clarifications and wordsmithing Sebastian Siewior
2020-03-25 16:39 ` Paul E. McKenney
2020-03-25 16:54 ` Sebastian Siewior
2020-03-25 16:58 ` [PATCH v2] Documentation/locking/locktypes: minor copy editor fixes Randy Dunlap
2020-03-26 2:40 ` Paul E. McKenney
2020-03-21 11:25 ` [patch V3 14/20] timekeeping: Split jiffies seqlock Thomas Gleixner
2020-03-21 11:25 ` [patch V3 15/20] sched/swait: Prepare usage in completions Thomas Gleixner
2020-03-21 11:26 ` [patch V3 16/20] completion: Use simple wait queues Thomas Gleixner
2020-03-23 15:20 ` [PATCH] completion: Use lockdep_assert_RT_in_threaded_ctx() in complete_all() Sebastian Siewior
2020-03-21 11:26 ` [patch V3 17/20] lockdep: Introduce wait-type checks Thomas Gleixner
2020-03-21 11:26 ` [patch V3 18/20] lockdep: Add hrtimer context tracing bits Thomas Gleixner
2020-03-21 11:26 ` [patch V3 19/20] lockdep: Annotate irq_work Thomas Gleixner
2020-03-21 11:26 ` [patch V3 20/20] lockdep: Add posixtimer context tracing bits Thomas Gleixner
2020-03-21 17:19 ` [patch V3 00/20] Lock ordering documentation and annotation for lockdep Davidlohr Bueso
2020-03-21 17:45 ` 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=87wo78y5yy.fsf@nanos.tec.linutronix.de \
--to=tglx@linutronix$(echo .)de \
--cc=andy@infradead$(echo .)org \
--cc=arnd@arndb$(echo .)de \
--cc=balbi@kernel$(echo .)org \
--cc=bcain@codeaurora$(echo .)org \
--cc=bhelgaas@google$(echo .)com \
--cc=bigeasy@linutronix$(echo .)de \
--cc=corbet@lwn$(echo .)net \
--cc=dave@stgolabs$(echo .)net \
--cc=davem@davemloft$(echo .)net \
--cc=dbueso@suse$(echo .)de \
--cc=deanbo422@gmail$(echo .)com \
--cc=dvhart@infradead$(echo .)org \
--cc=fenghua.yu@intel$(echo .)com \
--cc=geoff@infradead$(echo .)org \
--cc=green.hu@gmail$(echo .)com \
--cc=gregkh@linuxfoundation$(echo .)org \
--cc=guoren@kernel$(echo .)org \
--cc=joel@joelfernandes$(echo .)org \
--cc=kurt.schwemmer@microsemi$(echo .)com \
--cc=kvalo@codeaurora$(echo .)org \
--cc=lenb@kernel$(echo .)org \
--cc=linux-acpi@vger$(echo .)kernel.org \
--cc=linux-csky@vger$(echo .)kernel.org \
--cc=linux-hexagon@vger$(echo .)kernel.org \
--cc=linux-ia64@vger$(echo .)kernel.org \
--cc=linux-kernel@vger$(echo .)kernel.org \
--cc=linux-pci@vger$(echo .)kernel.org \
--cc=linux-pm@vger$(echo .)kernel.org \
--cc=linux-usb@vger$(echo .)kernel.org \
--cc=linux-wireless@vger$(echo .)kernel.org \
--cc=linuxppc-dev@lists$(echo .)ozlabs.org \
--cc=lkp@intel$(echo .)com \
--cc=logang@deltatee$(echo .)com \
--cc=mingo@kernel$(echo .)org \
--cc=monstr@monstr$(echo .)eu \
--cc=netdev@vger$(echo .)kernel.org \
--cc=nickhu@andestech$(echo .)com \
--cc=oleg@redhat$(echo .)com \
--cc=paulmck@kernel$(echo .)org \
--cc=peterz@infradead$(echo .)org \
--cc=platform-driver-x86@vger$(echo .)kernel.org \
--cc=rafael.j.wysocki@intel$(echo .)com \
--cc=rdunlap@infradead$(echo .)org \
--cc=rui.zhang@intel$(echo .)com \
--cc=tony.luck@intel$(echo .)com \
--cc=torvalds@linux-foundation$(echo .)org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox