1.. SPDX-License-Identifier: GPL-2.0
2
3.. _kernel_hacking_locktypes:
4
5==========================
6Lock types and their rules
7==========================
8
9Introduction
10============
11
12The kernel provides a variety of locking primitives which can be divided
13into three categories:
14
15 - Sleeping locks
16 - CPU local locks
17 - Spinning locks
18
19This document conceptually describes these lock types and provides rules
20for their nesting, including the rules for use under PREEMPT_RT.
21
22
23Lock categories
24===============
25
26Sleeping locks
27--------------
28
29Sleeping locks can only be acquired in preemptible task context.
30
31Although implementations allow try_lock() from other contexts, it is
32necessary to carefully evaluate the safety of unlock() as well as of
33try_lock().  Furthermore, it is also necessary to evaluate the debugging
34versions of these primitives.  In short, don't acquire sleeping locks from
35other contexts unless there is no other option.
36
37Sleeping lock types:
38
39 - mutex
40 - rt_mutex
41 - semaphore
42 - rw_semaphore
43 - ww_mutex
44 - percpu_rw_semaphore
45
46On PREEMPT_RT kernels, these lock types are converted to sleeping locks:
47
48 - local_lock
49 - spinlock_t
50 - rwlock_t
51
52
53CPU local locks
54---------------
55
56 - local_lock
57
58On non-PREEMPT_RT kernels, local_lock functions are wrappers around
59preemption and interrupt disabling primitives. Contrary to other locking
60mechanisms, disabling preemption or interrupts are pure CPU local
61concurrency control mechanisms and not suited for inter-CPU concurrency
62control.
63
64
65Spinning locks
66--------------
67
68 - raw_spinlock_t
69 - bit spinlocks
70
71On non-PREEMPT_RT kernels, these lock types are also spinning locks:
72
73 - spinlock_t
74 - rwlock_t
75
76Spinning locks implicitly disable preemption and the lock / unlock functions
77can have suffixes which apply further protections:
78
79 ===================  ====================================================
80 _bh()                Disable / enable bottom halves (soft interrupts)
81 _irq()               Disable / enable interrupts
82 _irqsave/restore()   Save and disable / restore interrupt disabled state
83 ===================  ====================================================
84
85
86Owner semantics
87===============
88
89The aforementioned lock types except semaphores have strict owner
90semantics:
91
92  The context (task) that acquired the lock must release it.
93
94rw_semaphores have a special interface which allows non-owner release for
95readers.
96
97
98rtmutex
99=======
100
101RT-mutexes are mutexes with support for priority inheritance (PI).
102
103PI has limitations on non-PREEMPT_RT kernels due to preemption and
104interrupt disabled sections.
105
106PI clearly cannot preempt preemption-disabled or interrupt-disabled
107regions of code, even on PREEMPT_RT kernels.  Instead, PREEMPT_RT kernels
108execute most such regions of code in preemptible task context, especially
109interrupt handlers and soft interrupts.  This conversion allows spinlock_t
110and rwlock_t to be implemented via RT-mutexes.
111
112
113semaphore
114=========
115
116semaphore is a counting semaphore implementation.
117
118Semaphores are often used for both serialization and waiting, but new use
119cases should instead use separate serialization and wait mechanisms, such
120as mutexes and completions.
121
122semaphores and PREEMPT_RT
123----------------------------
124
125PREEMPT_RT does not change the semaphore implementation because counting
126semaphores have no concept of owners, thus preventing PREEMPT_RT from
127providing priority inheritance for semaphores.  After all, an unknown
128owner cannot be boosted. As a consequence, blocking on semaphores can
129result in priority inversion.
130
131
132rw_semaphore
133============
134
135rw_semaphore is a multiple readers and single writer lock mechanism.
136
137On non-PREEMPT_RT kernels the implementation is fair, thus preventing
138writer starvation.
139
140rw_semaphore complies by default with the strict owner semantics, but there
141exist special-purpose interfaces that allow non-owner release for readers.
142These interfaces work independent of the kernel configuration.
143
144rw_semaphore and PREEMPT_RT
145---------------------------
146
147PREEMPT_RT kernels map rw_semaphore to a separate rt_mutex-based
148implementation, thus changing the fairness:
149
150 Because an rw_semaphore writer cannot grant its priority to multiple
151 readers, a preempted low-priority reader will continue holding its lock,
152 thus starving even high-priority writers.  In contrast, because readers
153 can grant their priority to a writer, a preempted low-priority writer will
154 have its priority boosted until it releases the lock, thus preventing that
155 writer from starving readers.
156
157
158local_lock
159==========
160
161local_lock provides a named scope to critical sections which are protected
162by disabling preemption or interrupts.
163
164On non-PREEMPT_RT kernels local_lock operations map to the preemption and
165interrupt disabling and enabling primitives:
166
167 =========================== ======================
168 local_lock(&llock)          preempt_disable()
169 local_unlock(&llock)        preempt_enable()
170 local_lock_irq(&llock)      local_irq_disable()
171 local_unlock_irq(&llock)    local_irq_enable()
172 local_lock_save(&llock)     local_irq_save()
173 local_lock_restore(&llock)  local_irq_save()
174 =========================== ======================
175
176The named scope of local_lock has two advantages over the regular
177primitives:
178
179  - The lock name allows static analysis and is also a clear documentation
180    of the protection scope while the regular primitives are scopeless and
181    opaque.
182
183  - If lockdep is enabled the local_lock gains a lockmap which allows to
184    validate the correctness of the protection. This can detect cases where
185    e.g. a function using preempt_disable() as protection mechanism is
186    invoked from interrupt or soft-interrupt context. Aside of that
187    lockdep_assert_held(&llock) works as with any other locking primitive.
188
189local_lock and PREEMPT_RT
190-------------------------
191
192PREEMPT_RT kernels map local_lock to a per-CPU spinlock_t, thus changing
193semantics:
194
195  - All spinlock_t changes also apply to local_lock.
196
197local_lock usage
198----------------
199
200local_lock should be used in situations where disabling preemption or
201interrupts is the appropriate form of concurrency control to protect
202per-CPU data structures on a non PREEMPT_RT kernel.
203
204local_lock is not suitable to protect against preemption or interrupts on a
205PREEMPT_RT kernel due to the PREEMPT_RT specific spinlock_t semantics.
206
207
208raw_spinlock_t and spinlock_t
209=============================
210
211raw_spinlock_t
212--------------
213
214raw_spinlock_t is a strict spinning lock implementation regardless of the
215kernel configuration including PREEMPT_RT enabled kernels.
216
217raw_spinlock_t is a strict spinning lock implementation in all kernels,
218including PREEMPT_RT kernels.  Use raw_spinlock_t only in real critical
219core code, low-level interrupt handling and places where disabling
220preemption or interrupts is required, for example, to safely access
221hardware state.  raw_spinlock_t can sometimes also be used when the
222critical section is tiny, thus avoiding RT-mutex overhead.
223
224spinlock_t
225----------
226
227The semantics of spinlock_t change with the state of PREEMPT_RT.
228
229On a non-PREEMPT_RT kernel spinlock_t is mapped to raw_spinlock_t and has
230exactly the same semantics.
231
232spinlock_t and PREEMPT_RT
233-------------------------
234
235On a PREEMPT_RT kernel spinlock_t is mapped to a separate implementation
236based on rt_mutex which changes the semantics:
237
238 - Preemption is not disabled.
239
240 - The hard interrupt related suffixes for spin_lock / spin_unlock
241   operations (_irq, _irqsave / _irqrestore) do not affect the CPU's
242   interrupt disabled state.
243
244 - The soft interrupt related suffix (_bh()) still disables softirq
245   handlers.
246
247   Non-PREEMPT_RT kernels disable preemption to get this effect.
248
249   PREEMPT_RT kernels use a per-CPU lock for serialization which keeps
250   preemption disabled. The lock disables softirq handlers and also
251   prevents reentrancy due to task preemption.
252
253PREEMPT_RT kernels preserve all other spinlock_t semantics:
254
255 - Tasks holding a spinlock_t do not migrate.  Non-PREEMPT_RT kernels
256   avoid migration by disabling preemption.  PREEMPT_RT kernels instead
257   disable migration, which ensures that pointers to per-CPU variables
258   remain valid even if the task is preempted.
259
260 - Task state is preserved across spinlock acquisition, ensuring that the
261   task-state rules apply to all kernel configurations.  Non-PREEMPT_RT
262   kernels leave task state untouched.  However, PREEMPT_RT must change
263   task state if the task blocks during acquisition.  Therefore, it saves
264   the current task state before blocking and the corresponding lock wakeup
265   restores it, as shown below::
266
267    task->state = TASK_INTERRUPTIBLE
268     lock()
269       block()
270         task->saved_state = task->state
271	 task->state = TASK_UNINTERRUPTIBLE
272	 schedule()
273					lock wakeup
274					  task->state = task->saved_state
275
276   Other types of wakeups would normally unconditionally set the task state
277   to RUNNING, but that does not work here because the task must remain
278   blocked until the lock becomes available.  Therefore, when a non-lock
279   wakeup attempts to awaken a task blocked waiting for a spinlock, it
280   instead sets the saved state to RUNNING.  Then, when the lock
281   acquisition completes, the lock wakeup sets the task state to the saved
282   state, in this case setting it to RUNNING::
283
284    task->state = TASK_INTERRUPTIBLE
285     lock()
286       block()
287         task->saved_state = task->state
288	 task->state = TASK_UNINTERRUPTIBLE
289	 schedule()
290					non lock wakeup
291					  task->saved_state = TASK_RUNNING
292
293					lock wakeup
294					  task->state = task->saved_state
295
296   This ensures that the real wakeup cannot be lost.
297
298
299rwlock_t
300========
301
302rwlock_t is a multiple readers and single writer lock mechanism.
303
304Non-PREEMPT_RT kernels implement rwlock_t as a spinning lock and the
305suffix rules of spinlock_t apply accordingly. The implementation is fair,
306thus preventing writer starvation.
307
308rwlock_t and PREEMPT_RT
309-----------------------
310
311PREEMPT_RT kernels map rwlock_t to a separate rt_mutex-based
312implementation, thus changing semantics:
313
314 - All the spinlock_t changes also apply to rwlock_t.
315
316 - Because an rwlock_t writer cannot grant its priority to multiple
317   readers, a preempted low-priority reader will continue holding its lock,
318   thus starving even high-priority writers.  In contrast, because readers
319   can grant their priority to a writer, a preempted low-priority writer
320   will have its priority boosted until it releases the lock, thus
321   preventing that writer from starving readers.
322
323
324PREEMPT_RT caveats
325==================
326
327local_lock on RT
328----------------
329
330The mapping of local_lock to spinlock_t on PREEMPT_RT kernels has a few
331implications. For example, on a non-PREEMPT_RT kernel the following code
332sequence works as expected::
333
334  local_lock_irq(&local_lock);
335  raw_spin_lock(&lock);
336
337and is fully equivalent to::
338
339   raw_spin_lock_irq(&lock);
340
341On a PREEMPT_RT kernel this code sequence breaks because local_lock_irq()
342is mapped to a per-CPU spinlock_t which neither disables interrupts nor
343preemption. The following code sequence works perfectly correct on both
344PREEMPT_RT and non-PREEMPT_RT kernels::
345
346  local_lock_irq(&local_lock);
347  spin_lock(&lock);
348
349Another caveat with local locks is that each local_lock has a specific
350protection scope. So the following substitution is wrong::
351
352  func1()
353  {
354    local_irq_save(flags);    -> local_lock_irqsave(&local_lock_1, flags);
355    func3();
356    local_irq_restore(flags); -> local_lock_irqrestore(&local_lock_1, flags);
357  }
358
359  func2()
360  {
361    local_irq_save(flags);    -> local_lock_irqsave(&local_lock_2, flags);
362    func3();
363    local_irq_restore(flags); -> local_lock_irqrestore(&local_lock_2, flags);
364  }
365
366  func3()
367  {
368    lockdep_assert_irqs_disabled();
369    access_protected_data();
370  }
371
372On a non-PREEMPT_RT kernel this works correctly, but on a PREEMPT_RT kernel
373local_lock_1 and local_lock_2 are distinct and cannot serialize the callers
374of func3(). Also the lockdep assert will trigger on a PREEMPT_RT kernel
375because local_lock_irqsave() does not disable interrupts due to the
376PREEMPT_RT-specific semantics of spinlock_t. The correct substitution is::
377
378  func1()
379  {
380    local_irq_save(flags);    -> local_lock_irqsave(&local_lock, flags);
381    func3();
382    local_irq_restore(flags); -> local_lock_irqrestore(&local_lock, flags);
383  }
384
385  func2()
386  {
387    local_irq_save(flags);    -> local_lock_irqsave(&local_lock, flags);
388    func3();
389    local_irq_restore(flags); -> local_lock_irqrestore(&local_lock, flags);
390  }
391
392  func3()
393  {
394    lockdep_assert_held(&local_lock);
395    access_protected_data();
396  }
397
398
399spinlock_t and rwlock_t
400-----------------------
401
402The changes in spinlock_t and rwlock_t semantics on PREEMPT_RT kernels
403have a few implications.  For example, on a non-PREEMPT_RT kernel the
404following code sequence works as expected::
405
406   local_irq_disable();
407   spin_lock(&lock);
408
409and is fully equivalent to::
410
411   spin_lock_irq(&lock);
412
413Same applies to rwlock_t and the _irqsave() suffix variants.
414
415On PREEMPT_RT kernel this code sequence breaks because RT-mutex requires a
416fully preemptible context.  Instead, use spin_lock_irq() or
417spin_lock_irqsave() and their unlock counterparts.  In cases where the
418interrupt disabling and locking must remain separate, PREEMPT_RT offers a
419local_lock mechanism.  Acquiring the local_lock pins the task to a CPU,
420allowing things like per-CPU interrupt disabled locks to be acquired.
421However, this approach should be used only where absolutely necessary.
422
423A typical scenario is protection of per-CPU variables in thread context::
424
425  struct foo *p = get_cpu_ptr(&var1);
426
427  spin_lock(&p->lock);
428  p->count += this_cpu_read(var2);
429
430This is correct code on a non-PREEMPT_RT kernel, but on a PREEMPT_RT kernel
431this breaks. The PREEMPT_RT-specific change of spinlock_t semantics does
432not allow to acquire p->lock because get_cpu_ptr() implicitly disables
433preemption. The following substitution works on both kernels::
434
435  struct foo *p;
436
437  migrate_disable();
438  p = this_cpu_ptr(&var1);
439  spin_lock(&p->lock);
440  p->count += this_cpu_read(var2);
441
442On a non-PREEMPT_RT kernel migrate_disable() maps to preempt_disable()
443which makes the above code fully equivalent. On a PREEMPT_RT kernel
444migrate_disable() ensures that the task is pinned on the current CPU which
445in turn guarantees that the per-CPU access to var1 and var2 are staying on
446the same CPU.
447
448The migrate_disable() substitution is not valid for the following
449scenario::
450
451  func()
452  {
453    struct foo *p;
454
455    migrate_disable();
456    p = this_cpu_ptr(&var1);
457    p->val = func2();
458
459While correct on a non-PREEMPT_RT kernel, this breaks on PREEMPT_RT because
460here migrate_disable() does not protect against reentrancy from a
461preempting task. A correct substitution for this case is::
462
463  func()
464  {
465    struct foo *p;
466
467    local_lock(&foo_lock);
468    p = this_cpu_ptr(&var1);
469    p->val = func2();
470
471On a non-PREEMPT_RT kernel this protects against reentrancy by disabling
472preemption. On a PREEMPT_RT kernel this is achieved by acquiring the
473underlying per-CPU spinlock.
474
475
476raw_spinlock_t on RT
477--------------------
478
479Acquiring a raw_spinlock_t disables preemption and possibly also
480interrupts, so the critical section must avoid acquiring a regular
481spinlock_t or rwlock_t, for example, the critical section must avoid
482allocating memory.  Thus, on a non-PREEMPT_RT kernel the following code
483works perfectly::
484
485  raw_spin_lock(&lock);
486  p = kmalloc(sizeof(*p), GFP_ATOMIC);
487
488But this code fails on PREEMPT_RT kernels because the memory allocator is
489fully preemptible and therefore cannot be invoked from truly atomic
490contexts.  However, it is perfectly fine to invoke the memory allocator
491while holding normal non-raw spinlocks because they do not disable
492preemption on PREEMPT_RT kernels::
493
494  spin_lock(&lock);
495  p = kmalloc(sizeof(*p), GFP_ATOMIC);
496
497
498bit spinlocks
499-------------
500
501PREEMPT_RT cannot substitute bit spinlocks because a single bit is too
502small to accommodate an RT-mutex.  Therefore, the semantics of bit
503spinlocks are preserved on PREEMPT_RT kernels, so that the raw_spinlock_t
504caveats also apply to bit spinlocks.
505
506Some bit spinlocks are replaced with regular spinlock_t for PREEMPT_RT
507using conditional (#ifdef'ed) code changes at the usage site.  In contrast,
508usage-site changes are not needed for the spinlock_t substitution.
509Instead, conditionals in header files and the core locking implemementation
510enable the compiler to do the substitution transparently.
511
512
513Lock type nesting rules
514=======================
515
516The most basic rules are:
517
518  - Lock types of the same lock category (sleeping, CPU local, spinning)
519    can nest arbitrarily as long as they respect the general lock ordering
520    rules to prevent deadlocks.
521
522  - Sleeping lock types cannot nest inside CPU local and spinning lock types.
523
524  - CPU local and spinning lock types can nest inside sleeping lock types.
525
526  - Spinning lock types can nest inside all lock types
527
528These constraints apply both in PREEMPT_RT and otherwise.
529
530The fact that PREEMPT_RT changes the lock category of spinlock_t and
531rwlock_t from spinning to sleeping and substitutes local_lock with a
532per-CPU spinlock_t means that they cannot be acquired while holding a raw
533spinlock.  This results in the following nesting ordering:
534
535  1) Sleeping locks
536  2) spinlock_t, rwlock_t, local_lock
537  3) raw_spinlock_t and bit spinlocks
538
539Lockdep will complain if these constraints are violated, both in
540PREEMPT_RT and otherwise.
541