Unreliable Guide To Locking

Rusty Russell


This documentation is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 2 of the License, or (at your option) any later version.

This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.

You should have received a copy of the GNU General Public License along with this program; if not, write to the Free Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA

For more details see the file COPYING in the source distribution of Linux.

Table of Contents

1. Introduction
2. The Problem With Concurrency
Race Conditions and Critical Regions
3. Locking in the Linux Kernel
Two Main Types of Kernel Locks: Spinlocks and Mutexes
Locks and Uniprocessor Kernels
Locking Only In User Context
Locking Between User Context and Softirqs
Locking Between User Context and Tasklets
Locking Between User Context and Timers
Locking Between Tasklets/Timers
The Same Tasklet/Timer
Different Tasklets/Timers
Locking Between Softirqs
The Same Softirq
Different Softirqs
4. Hard IRQ Context
Locking Between Hard IRQ and Softirqs/Tasklets
Locking Between Two Hard IRQ Handlers
5. Cheat Sheet For Locking
Table of Minimum Requirements
6. The trylock Functions
7. Common Examples
All In User Context
Accessing From Interrupt Context
Exposing Objects Outside This File
Using Atomic Operations For The Reference Count
Protecting The Objects Themselves
8. Common Problems
Deadlock: Simple and Advanced
Preventing Deadlock
Overzealous Prevention Of Deadlocks
Racing Timers: A Kernel Pastime
9. Locking Speed
Read/Write Lock Variants
Avoiding Locks: Read Copy Update
Per-CPU Data
Data Which Mostly Used By An IRQ Handler
10. What Functions Are Safe To Call From Interrupts?
Some Functions Which Sleep
Some Functions Which Don't Sleep
11. Mutex API reference
mutex_init — initialize the mutex
mutex_is_locked — is the mutex locked
mutex_trylock_recursive — trylock variant that allows recursive locking
mutex_lock — acquire the mutex
mutex_unlock — release the mutex
ww_mutex_unlock — release the w/w mutex
mutex_lock_interruptible — acquire the mutex, interruptible
mutex_trylock — try to acquire the mutex, without waiting
atomic_dec_and_mutex_lock — return holding mutex if we dec to 0
12. Futex API reference
struct futex_q — The hashed futex queue entry, one per waiting task
hash_futex — Return the hash bucket in the global hash
match_futex — Check whether two futex keys are equal
get_futex_key — Get parameters which are the keys for a futex
fault_in_user_writeable — Fault in user address and verify RW access
futex_top_waiter — Return the highest priority waiter on a futex
futex_lock_pi_atomic — Atomic work required to acquire a pi aware futex
__unqueue_futex — Remove the futex_q from its futex_hash_bucket
requeue_futex — Requeue a futex_q from one hb to another
requeue_pi_wake_futex — Wake a task that acquired the lock during requeue
futex_proxy_trylock_atomic — Attempt an atomic lock for the top waiter
futex_requeue — Requeue waiters from uaddr1 to uaddr2
queue_me — Enqueue the futex_q on the futex_hash_bucket
unqueue_me — Remove the futex_q from its futex_hash_bucket
fixup_owner — Post lock pi_state and corner case management
futex_wait_queue_me queue_me and wait for wakeup, timeout, or signal
futex_wait_setup — Prepare to wait on a futex
handle_early_requeue_pi_wakeup — Detect early wakeup on the initial futex
futex_wait_requeue_pi — Wait on uaddr and take uaddr2
sys_set_robust_list — Set the robust-futex list head of a task
sys_get_robust_list — Get the robust-futex list head of a task
13. Further reading
14. Thanks

List of Tables

2.1. Expected Results
2.2. Possible Results
5.1. Table of Locking Requirements
5.2. Legend for Locking Requirements Table
8.1. Consequences