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
Three Main Types of Kernel Locks: Spinlocks, Mutexes and Semaphores
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. Further reading
12. 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