<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN">
<HTML
><HEAD
><TITLE
>Deadlock: Simple and Advanced</TITLE
><META
NAME="GENERATOR"
CONTENT="Modular DocBook HTML Stylesheet Version 1.7"><LINK
REL="HOME"
TITLE="Unreliable Guide To Locking"
HREF="book1.html"><LINK
REL="UP"
TITLE="Common Techniques"
HREF="c196.html"><LINK
REL="PREVIOUS"
TITLE="Common Techniques"
HREF="c196.html"><LINK
REL="NEXT"
TITLE="Per-CPU Data"
HREF="x250.html"></HEAD
><BODY
CLASS="SECT1"
BGCOLOR="#FFFFFF"
TEXT="#000000"
LINK="#0000FF"
VLINK="#840084"
ALINK="#0000FF"
><DIV
CLASS="NAVHEADER"
><TABLE
SUMMARY="Header navigation table"
WIDTH="100%"
BORDER="0"
CELLPADDING="0"
CELLSPACING="0"
><TR
><TH
COLSPAN="3"
ALIGN="center"
>Unreliable Guide To Locking</TH
></TR
><TR
><TD
WIDTH="10%"
ALIGN="left"
VALIGN="bottom"
><A
HREF="c196.html"
ACCESSKEY="P"
><<< Previous</A
></TD
><TD
WIDTH="80%"
ALIGN="center"
VALIGN="bottom"
>Common Techniques</TD
><TD
WIDTH="10%"
ALIGN="right"
VALIGN="bottom"
><A
HREF="x250.html"
ACCESSKEY="N"
>Next >>></A
></TD
></TR
></TABLE
><HR
ALIGN="LEFT"
WIDTH="100%"></DIV
><DIV
CLASS="SECT1"
><H1
CLASS="SECT1"
><A
NAME="TECHNIQUES-DEADLOCKS"
></A
>Deadlock: Simple and Advanced</H1
><P
> There is a coding bug where a piece of code tries to grab a
spinlock twice: it will spin forever, waiting for the lock to
be released (spinlocks, rwlocks and semaphores are not
recursive in Linux). This is trivial to diagnose: not a
stay-up-five-nights-talk-to-fluffy-code-bunnies kind of
problem.
</P
><P
> For a slightly more complex case, imagine you have a region
shared by a bottom half and user context. If you use a
<TT
CLASS="FUNCTION"
>spin_lock()</TT
> call to protect it, it is
possible that the user context will be interrupted by the bottom
half while it holds the lock, and the bottom half will then spin
forever trying to get the same lock.
</P
><P
> Both of these are called deadlock, and as shown above, it can
occur even with a single CPU (although not on UP compiles,
since spinlocks vanish on kernel compiles with
<SPAN
CLASS="SYMBOL"
>CONFIG_SMP</SPAN
>=n. You'll still get data corruption
in the second example).
</P
><P
> This complete lockup is easy to diagnose: on SMP boxes the
watchdog timer or compiling with <SPAN
CLASS="SYMBOL"
>DEBUG_SPINLOCKS</SPAN
> set
(<TT
CLASS="FILENAME"
>include/linux/spinlock.h</TT
>) will show this up
immediately when it happens.
</P
><P
> A more complex problem is the so-called `deadly embrace',
involving two or more locks. Say you have a hash table: each
entry in the table is a spinlock, and a chain of hashed
objects. Inside a softirq handler, you sometimes want to
alter an object from one place in the hash to another: you
grab the spinlock of the old hash chain and the spinlock of
the new hash chain, and delete the object from the old one,
and insert it in the new one.
</P
><P
> There are two problems here. First, if your code ever
tries to move the object to the same chain, it will deadlock
with itself as it tries to lock it twice. Secondly, if the
same softirq on another CPU is trying to move another object
in the reverse direction, the following could happen:
</P
><DIV
CLASS="TABLE"
><A
NAME="AEN226"
></A
><P
><B
>Table 1. Consequences</B
></P
><TABLE
BORDER="1"
BGCOLOR="#E0E0E0"
CELLSPACING="0"
CELLPADDING="4"
CLASS="CALSTABLE"
><THEAD
><TR
><TH
ALIGN="LEFT"
VALIGN="TOP"
>CPU 1</TH
><TH
ALIGN="LEFT"
VALIGN="TOP"
>CPU 2</TH
></TR
></THEAD
><TBODY
><TR
><TD
ALIGN="LEFT"
VALIGN="TOP"
>Grab lock A -> OK</TD
><TD
ALIGN="LEFT"
VALIGN="TOP"
>Grab lock B -> OK</TD
></TR
><TR
><TD
ALIGN="LEFT"
VALIGN="TOP"
>Grab lock B -> spin</TD
><TD
ALIGN="LEFT"
VALIGN="TOP"
>Grab lock A -> spin</TD
></TR
></TBODY
></TABLE
></DIV
><P
> The two CPUs will spin forever, waiting for the other to give up
their lock. It will look, smell, and feel like a crash.
</P
><DIV
CLASS="SECT2"
><H2
CLASS="SECT2"
><A
NAME="TECHS-DEADLOCK-PREVENT"
></A
>Preventing Deadlock</H2
><P
> Textbooks will tell you that if you always lock in the same
order, you will never get this kind of deadlock. Practice
will tell you that this approach doesn't scale: when I
create a new lock, I don't understand enough of the kernel
to figure out where in the 5000 lock hierarchy it will fit.
</P
><P
> The best locks are encapsulated: they never get exposed in
headers, and are never held around calls to non-trivial
functions outside the same file. You can read through this
code and see that it will never deadlock, because it never
tries to grab another lock while it has that one. People
using your code don't even need to know you are using a
lock.
</P
><P
> A classic problem here is when you provide callbacks or
hooks: if you call these with the lock held, you risk simple
deadlock, or a deadly embrace (who knows what the callback
will do?). Remember, the other programmers are out to get
you, so don't do this.
</P
></DIV
><DIV
CLASS="SECT2"
><H2
CLASS="SECT2"
><A
NAME="TECHS-DEADLOCK-OVERPREVENT"
></A
>Overzealous Prevention Of Deadlocks</H2
><P
> Deadlocks are problematic, but not as bad as data
corruption. Code which grabs a read lock, searches a list,
fails to find what it wants, drops the read lock, grabs a
write lock and inserts the object has a race condition.
</P
><P
> If you don't see why, please stay the fuck away from my code.
</P
></DIV
></DIV
><DIV
CLASS="NAVFOOTER"
><HR
ALIGN="LEFT"
WIDTH="100%"><TABLE
SUMMARY="Footer navigation table"
WIDTH="100%"
BORDER="0"
CELLPADDING="0"
CELLSPACING="0"
><TR
><TD
WIDTH="33%"
ALIGN="left"
VALIGN="top"
><A
HREF="c196.html"
ACCESSKEY="P"
><<< Previous</A
></TD
><TD
WIDTH="34%"
ALIGN="center"
VALIGN="top"
><A
HREF="book1.html"
ACCESSKEY="H"
>Home</A
></TD
><TD
WIDTH="33%"
ALIGN="right"
VALIGN="top"
><A
HREF="x250.html"
ACCESSKEY="N"
>Next >>></A
></TD
></TR
><TR
><TD
WIDTH="33%"
ALIGN="left"
VALIGN="top"
>Common Techniques</TD
><TD
WIDTH="34%"
ALIGN="center"
VALIGN="top"
><A
HREF="c196.html"
ACCESSKEY="U"
>Up</A
></TD
><TD
WIDTH="33%"
ALIGN="right"
VALIGN="top"
>Per-CPU Data</TD
></TR
></TABLE
></DIV
></BODY
></HTML
>
