1<html><head><meta http-equiv="Content-Type" content="text/html; charset=ANSI_X3.4-1968"><title>Unreliable Guide To Locking</title><meta name="generator" content="DocBook XSL Stylesheets V1.78.1"><link rel="home" href="index.html" title="Unreliable Guide To Locking"><link rel="next" href="intro.html" title="Chapter 1. Introduction"></head><body bgcolor="white" text="black" link="#0000FF" vlink="#840084" alink="#0000FF"><div class="navheader"><table width="100%" summary="Navigation header"><tr><th colspan="3" align="center">Unreliable Guide To Locking</th></tr><tr><td width="20%" align="left"> </td><th width="60%" align="center"> </th><td width="20%" align="right"> <a accesskey="n" href="intro.html">Next</a></td></tr></table><hr></div><div class="book"><div class="titlepage"><div><div><h1 class="title"><a name="LKLockingGuide"></a>Unreliable Guide To Locking</h1></div><div><div class="authorgroup"><div class="author"><h3 class="author"><span class="firstname">Rusty</span> <span class="surname">Russell</span></h3><div class="affiliation"><div class="address"><p><br> 2      <code class="email"><<a class="email" href="mailto:rusty@rustcorp.com.au">rusty@rustcorp.com.au</a>></code><br> 3     </p></div></div></div></div></div><div><p class="copyright">Copyright © 2003 Rusty Russell</p></div><div><div class="legalnotice"><a name="idp1124255804"></a><p> 4 This documentation is free software; you can redistribute 5 it and/or modify it under the terms of the GNU General Public 6 License as published by the Free Software Foundation; either 7 version 2 of the License, or (at your option) any later 8 version. 9 </p><p> 10 This program is distributed in the hope that it will be 11 useful, but WITHOUT ANY WARRANTY; without even the implied 12 warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. 13 See the GNU General Public License for more details. 14 </p><p> 15 You should have received a copy of the GNU General Public 16 License along with this program; if not, write to the Free 17 Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, 18 MA 02111-1307 USA 19 </p><p> 20 For more details see the file COPYING in the source 21 distribution of Linux. 22 </p></div></div></div><hr></div><div class="toc"><p><b>Table of Contents</b></p><dl class="toc"><dt><span class="chapter"><a href="intro.html">1. Introduction</a></span></dt><dt><span class="chapter"><a href="races.html">2. The Problem With Concurrency</a></span></dt><dd><dl><dt><span class="sect1"><a href="races.html#race-condition">Race Conditions and Critical Regions</a></span></dt></dl></dd><dt><span class="chapter"><a href="locks.html">3. Locking in the Linux Kernel</a></span></dt><dd><dl><dt><span class="sect1"><a href="locks.html#lock-intro">Two Main Types of Kernel Locks: Spinlocks and Mutexes</a></span></dt><dt><span class="sect1"><a href="uniprocessor.html">Locks and Uniprocessor Kernels</a></span></dt><dt><span class="sect1"><a href="usercontextlocking.html">Locking Only In User Context</a></span></dt><dt><span class="sect1"><a href="lock-user-bh.html">Locking Between User Context and Softirqs</a></span></dt><dt><span class="sect1"><a href="lock-user-tasklet.html">Locking Between User Context and Tasklets</a></span></dt><dt><span class="sect1"><a href="lock-user-timers.html">Locking Between User Context and Timers</a></span></dt><dt><span class="sect1"><a href="lock-tasklets.html">Locking Between Tasklets/Timers</a></span></dt><dd><dl><dt><span class="sect2"><a href="lock-tasklets.html#lock-tasklets-same">The Same Tasklet/Timer</a></span></dt><dt><span class="sect2"><a href="lock-tasklets.html#lock-tasklets-different">Different Tasklets/Timers</a></span></dt></dl></dd><dt><span class="sect1"><a href="lock-softirqs.html">Locking Between Softirqs</a></span></dt><dd><dl><dt><span class="sect2"><a href="lock-softirqs.html#lock-softirqs-same">The Same Softirq</a></span></dt><dt><span class="sect2"><a href="lock-softirqs.html#lock-softirqs-different">Different Softirqs</a></span></dt></dl></dd></dl></dd><dt><span class="chapter"><a href="hardirq-context.html">4. Hard IRQ Context</a></span></dt><dd><dl><dt><span class="sect1"><a href="hardirq-context.html#hardirq-softirq">Locking Between Hard IRQ and Softirqs/Tasklets</a></span></dt><dt><span class="sect1"><a href="hardirq-hardirq.html">Locking Between Two Hard IRQ Handlers</a></span></dt></dl></dd><dt><span class="chapter"><a href="cheatsheet.html">5. Cheat Sheet For Locking</a></span></dt><dd><dl><dt><span class="sect1"><a href="cheatsheet.html#minimum-lock-reqirements">Table of Minimum Requirements</a></span></dt></dl></dd><dt><span class="chapter"><a href="trylock-functions.html">6. The trylock Functions</a></span></dt><dt><span class="chapter"><a href="Examples.html">7. Common Examples</a></span></dt><dd><dl><dt><span class="sect1"><a href="Examples.html#examples-usercontext">All In User Context</a></span></dt><dt><span class="sect1"><a href="examples-interrupt.html">Accessing From Interrupt Context</a></span></dt><dt><span class="sect1"><a href="examples-refcnt.html">Exposing Objects Outside This File</a></span></dt><dd><dl><dt><span class="sect2"><a href="examples-refcnt.html#examples-refcnt-atomic">Using Atomic Operations For The Reference Count</a></span></dt></dl></dd><dt><span class="sect1"><a href="examples-lock-per-obj.html">Protecting The Objects Themselves</a></span></dt></dl></dd><dt><span class="chapter"><a href="common-problems.html">8. Common Problems</a></span></dt><dd><dl><dt><span class="sect1"><a href="common-problems.html#deadlock">Deadlock: Simple and Advanced</a></span></dt><dt><span class="sect1"><a href="techs-deadlock-prevent.html">Preventing Deadlock</a></span></dt><dd><dl><dt><span class="sect2"><a href="techs-deadlock-prevent.html#techs-deadlock-overprevent">Overzealous Prevention Of Deadlocks</a></span></dt></dl></dd><dt><span class="sect1"><a href="racing-timers.html">Racing Timers: A Kernel Pastime</a></span></dt></dl></dd><dt><span class="chapter"><a href="Efficiency.html">9. Locking Speed</a></span></dt><dd><dl><dt><span class="sect1"><a href="Efficiency.html#efficiency-rwlocks">Read/Write Lock Variants</a></span></dt><dt><span class="sect1"><a href="efficiency-read-copy-update.html">Avoiding Locks: Read Copy Update</a></span></dt><dt><span class="sect1"><a href="per-cpu.html">Per-CPU Data</a></span></dt><dt><span class="sect1"><a href="mostly-hardirq.html">Data Which Mostly Used By An IRQ Handler</a></span></dt></dl></dd><dt><span class="chapter"><a href="sleeping-things.html">10. What Functions Are Safe To Call From Interrupts?</a></span></dt><dd><dl><dt><span class="sect1"><a href="sleeping-things.html#sleeping">Some Functions Which Sleep</a></span></dt><dt><span class="sect1"><a href="dont-sleep.html">Some Functions Which Don't Sleep</a></span></dt></dl></dd><dt><span class="chapter"><a href="apiref-mutex.html">11. Mutex API reference</a></span></dt><dd><dl><dt><span class="refentrytitle"><a href="API-mutex-init.html"><span class="phrase">mutex_init</span></a></span><span class="refpurpose"> — 23 initialize the mutex 24 </span></dt><dt><span class="refentrytitle"><a href="API-mutex-is-locked.html"><span class="phrase">mutex_is_locked</span></a></span><span class="refpurpose"> — 25 is the mutex locked 26 </span></dt><dt><span class="refentrytitle"><a href="API-mutex-lock.html"><span class="phrase">mutex_lock</span></a></span><span class="refpurpose"> — 27 acquire the mutex 28 </span></dt><dt><span class="refentrytitle"><a href="API-mutex-unlock.html"><span class="phrase">mutex_unlock</span></a></span><span class="refpurpose"> — 29 release the mutex 30 </span></dt><dt><span class="refentrytitle"><a href="API-ww-mutex-unlock.html"><span class="phrase">ww_mutex_unlock</span></a></span><span class="refpurpose"> — 31 release the w/w mutex 32 </span></dt><dt><span class="refentrytitle"><a href="API-mutex-lock-interruptible.html"><span class="phrase">mutex_lock_interruptible</span></a></span><span class="refpurpose"> — 33 acquire the mutex, interruptible 34 </span></dt><dt><span class="refentrytitle"><a href="API-mutex-trylock.html"><span class="phrase">mutex_trylock</span></a></span><span class="refpurpose"> — 35 try to acquire the mutex, without waiting 36 </span></dt><dt><span class="refentrytitle"><a href="API-atomic-dec-and-mutex-lock.html"><span class="phrase">atomic_dec_and_mutex_lock</span></a></span><span class="refpurpose"> — 37 return holding mutex if we dec to 0 38 </span></dt></dl></dd><dt><span class="chapter"><a href="apiref-futex.html">12. Futex API reference</a></span></dt><dd><dl><dt><span class="refentrytitle"><a href="API-struct-futex-q.html"><span class="phrase">struct futex_q</span></a></span><span class="refpurpose"> — 39 The hashed futex queue entry, one per waiting task 40 </span></dt><dt><span class="refentrytitle"><a href="API-get-futex-key.html"><span class="phrase">get_futex_key</span></a></span><span class="refpurpose"> — 41 Get parameters which are the keys for a futex 42 </span></dt><dt><span class="refentrytitle"><a href="API-fault-in-user-writeable.html"><span class="phrase">fault_in_user_writeable</span></a></span><span class="refpurpose"> — 43 Fault in user address and verify RW access 44 </span></dt><dt><span class="refentrytitle"><a href="API-futex-top-waiter.html"><span class="phrase">futex_top_waiter</span></a></span><span class="refpurpose"> — 45 Return the highest priority waiter on a futex 46 </span></dt><dt><span class="refentrytitle"><a href="API-futex-lock-pi-atomic.html"><span class="phrase">futex_lock_pi_atomic</span></a></span><span class="refpurpose"> — 47 Atomic work required to acquire a pi aware futex 48 </span></dt><dt><span class="refentrytitle"><a href="API---unqueue-futex.html"><span class="phrase">__unqueue_futex</span></a></span><span class="refpurpose"> — 49 Remove the futex_q from its futex_hash_bucket 50 </span></dt><dt><span class="refentrytitle"><a href="API-requeue-futex.html"><span class="phrase">requeue_futex</span></a></span><span class="refpurpose"> — 51 Requeue a futex_q from one hb to another 52 </span></dt><dt><span class="refentrytitle"><a href="API-requeue-pi-wake-futex.html"><span class="phrase">requeue_pi_wake_futex</span></a></span><span class="refpurpose"> — 53 Wake a task that acquired the lock during requeue 54 </span></dt><dt><span class="refentrytitle"><a href="API-futex-proxy-trylock-atomic.html"><span class="phrase">futex_proxy_trylock_atomic</span></a></span><span class="refpurpose"> — 55 Attempt an atomic lock for the top waiter 56 </span></dt><dt><span class="refentrytitle"><a href="API-futex-requeue.html"><span class="phrase">futex_requeue</span></a></span><span class="refpurpose"> — 57 Requeue waiters from uaddr1 to uaddr2 58 </span></dt><dt><span class="refentrytitle"><a href="API-queue-me.html"><span class="phrase">queue_me</span></a></span><span class="refpurpose"> — 59 Enqueue the futex_q on the futex_hash_bucket 60 </span></dt><dt><span class="refentrytitle"><a href="API-unqueue-me.html"><span class="phrase">unqueue_me</span></a></span><span class="refpurpose"> — 61 Remove the futex_q from its futex_hash_bucket 62 </span></dt><dt><span class="refentrytitle"><a href="API-fixup-owner.html"><span class="phrase">fixup_owner</span></a></span><span class="refpurpose"> — 63 Post lock pi_state and corner case management 64 </span></dt><dt><span class="refentrytitle"><a href="API-futex-wait-queue-me.html"><span class="phrase">futex_wait_queue_me</span></a></span><span class="refpurpose"> — 65 <code class="function">queue_me</code> and wait for wakeup, timeout, or signal 66 </span></dt><dt><span class="refentrytitle"><a href="API-futex-wait-setup.html"><span class="phrase">futex_wait_setup</span></a></span><span class="refpurpose"> — 67 Prepare to wait on a futex 68 </span></dt><dt><span class="refentrytitle"><a href="API-handle-early-requeue-pi-wakeup.html"><span class="phrase">handle_early_requeue_pi_wakeup</span></a></span><span class="refpurpose"> — 69 Detect early wakeup on the initial futex 70 </span></dt><dt><span class="refentrytitle"><a href="API-futex-wait-requeue-pi.html"><span class="phrase">futex_wait_requeue_pi</span></a></span><span class="refpurpose"> — 71 Wait on uaddr and take uaddr2 72 </span></dt><dt><span class="refentrytitle"><a href="API-sys-set-robust-list.html"><span class="phrase">sys_set_robust_list</span></a></span><span class="refpurpose"> — 73 Set the robust-futex list head of a task 74 </span></dt><dt><span class="refentrytitle"><a href="API-sys-get-robust-list.html"><span class="phrase">sys_get_robust_list</span></a></span><span class="refpurpose"> — 75 Get the robust-futex list head of a task 76 </span></dt></dl></dd><dt><span class="chapter"><a href="references.html">13. Further reading</a></span></dt><dt><span class="chapter"><a href="thanks.html">14. Thanks</a></span></dt><dt><span class="glossary"><a href="glossary.html">Glossary</a></span></dt></dl></div><div class="list-of-tables"><p><b>List of Tables</b></p><dl><dt>2.1. <a href="races.html#idp1123300436">Expected Results</a></dt><dt>2.2. <a href="races.html#idp1123560364">Possible Results</a></dt><dt>5.1. <a href="cheatsheet.html#idp1123787068">Table of Locking Requirements</a></dt><dt>5.2. <a href="cheatsheet.html#idp1123093084">Legend for Locking Requirements Table</a></dt><dt>8.1. <a href="common-problems.html#idp1121820172">Consequences</a></dt></dl></div></div><div class="navfooter"><hr><table width="100%" summary="Navigation footer"><tr><td width="40%" align="left"> </td><td width="20%" align="center"> </td><td width="40%" align="right"> <a accesskey="n" href="intro.html">Next</a></td></tr><tr><td width="40%" align="left" valign="top"> </td><td width="20%" align="center"> </td><td width="40%" align="right" valign="top"> Chapter 1. Introduction</td></tr></table></div></body></html> 77