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
2.1. Race Conditions and Critical Regions
3. Locking in the Linux Kernel
3.1. Two Main Types of Kernel Locks: Spinlocks and Semaphores
3.2. Locks and Uniprocessor Kernels
3.3. Locking Only In User Context
3.4. Locking Between User Context and Softirqs
3.5. Locking Between User Context and Tasklets
3.6. Locking Between User Context and Timers
3.7. Locking Between Tasklets/Timers
3.7.1. The Same Tasklet/Timer
3.7.2. Different Tasklets/Timers
3.8. Locking Between Softirqs
3.8.1. The Same Softirq
3.8.2. Different Softirqs
4. Hard IRQ Context
4.1. Locking Between Hard IRQ and Softirqs/Tasklets
4.2. Locking Between Two Hard IRQ Handlers
5. Cheat Sheet For Locking
5.1. Table of Minimum Requirements
6. Common Examples
6.1. All In User Context
6.2. Accessing From Interrupt Context
6.3. Exposing Objects Outside This File
6.3.1. Using Atomic Operations For The Reference Count
6.4. Protecting The Objects Themselves
7. Common Problems
7.1. Deadlock: Simple and Advanced
7.2. Preventing Deadlock
7.2.1. Overzealous Prevention Of Deadlocks
7.3. Racing Timers: A Kernel Pastime
7.4. The Fucked Up Sparc
8. Locking Speed
8.1. Read/Write Lock Variants
8.2. Avoiding Locks: Read Copy Update
8.3. Per-CPU Data
8.4. Data Which Mostly Used By An IRQ Handler
9. What Functions Are Safe To Call From Interrupts?
9.1. Some Functions Which Sleep
9.2. Some Functions Which Don't Sleep
10. Further reading
11. Thanks
List of Tables
2-1. Expected Results
2-2. Possible Results
5-1. Table of Locking Requirements
7-1. Consequences