path: root/Documentation/kernel-hacking/locking.rst

.. _kernel_hacking_lock:

===========================
Unreliable Guide To Locking
===========================

:Author: Rusty Russell

Introduction
============

Welcome, to Rusty's Remarkably Unreliable Guide to Kernel Locking
issues. This document describes the locking systems in the Linux Kernel
in 2.6.

With the wide availability of HyperThreading, and preemption in the
Linux Kernel, everyone hacking on the kernel needs to know the
fundamentals of concurrency and locking for SMP.

The Problem With Concurrency
============================

(Skip this if you know what a Race Condition is).

In a normal program, you can increment a counter like so:

::

          very_important_count++;


This is what they would expect to happen:


.. table:: Expected Results

  +------------------------------------+------------------------------------+
  | Instance 1                         | Instance 2                         |
  +====================================+====================================+
  | read very_important_count (5)      |                                    |
  +------------------------------------+------------------------------------+
  | add 1 (6)                          |                                    |
  +------------------------------------+------------------------------------+
  | write very_important_count (6)     |                                    |
  +------------------------------------+------------------------------------+
  |                                    | read very_important_count (6)      |
  +------------------------------------+------------------------------------+
  |                                    | add 1 (7)                          |
  +------------------------------------+------------------------------------+
  |                                    | write very_important_count (7)     |
  +------------------------------------+------------------------------------+

This is what might happen:

.. table:: Possible Results

  +------------------------------------+------------------------------------+
  | Instance 1                         | Instance 2                         |
  +====================================+====================================+
  | read very_important_count (5)      |                                    |
  +------------------------------------+------------------------------------+
  |                                    | read very_important_count (5)      |
  +------------------------------------+------------------------------------+
  | add 1 (6)                          |                                    |
  +------------------------------------+------------------------------------+
  |                                    | add 1 (6)                          |
  +------------------------------------+------------------------------------+
  | write very_important_count (6)     |                                    |
  +------------------------------------+------------------------------------+
  |                                    | write very_important_count (6)     |
  +------------------------------------+------------------------------------+


Race Conditions and Critical Regions
------------------------------------

This overlap, where the result depends on the relative timing of
multiple tasks, is called a race condition. The piece of code containing
the concurrency issue is called a critical region. And especially since
Linux starting running on SMP machines, they became one of the major
issues in kernel design and implementation.

Preemption can have the same effect, even if there is only one CPU: by
preempting one task during the critical region, we have exactly the same
race condition. In this case the thread which preempts might run the
critical region itself.

The solution is to recognize when these simultaneous accesses occur, and
use locks to make sure that only one instance can enter the critical
region at any time. There are many friendly primitives in the Linux
kernel to help you do this. And then there are the unfriendly
primitives, but I'll pretend they don't exist.

Locking in the Linux Kernel
===========================

If I could give you one piece of advice on locking: **keep it simple**.

Be reluctant to introduce new locks.

Two Main Types of Kernel Locks: Spinlocks and Mutexes
-----------------------------------------------------

There are two main types of kernel locks. The fundamental type is the
spinlock (``include/asm/spinlock.h``), which is a very simple
single-holder lock: if you can't get the spinlock, you keep trying
(spinning) until you can. Spinlocks are very small and fast, and can be
used anywhere.

The second type is a mutex (``include/linux/mutex.h``): it is like a
spinlock, but you may block holding a mutex. If you can't lock a mutex,
your task will suspend itself, and be woken up when the mutex is
released. This means the CPU can do something else while y