<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN">
<HTML
><HEAD
><TITLE
>Avoiding Locks: Read And Write Ordering</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="Big Reader Locks"
HREF="x256.html"><LINK
REL="NEXT"
TITLE="Avoiding Locks: Atomic Operations"
HREF="x286.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="x256.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="x286.html"
ACCESSKEY="N"
>Next >>></A
></TD
></TR
></TABLE
><HR
ALIGN="LEFT"
WIDTH="100%"></DIV
><DIV
CLASS="SECT1"
><H1
CLASS="SECT1"
><A
NAME="LOCK-AVOIDANCE-RW"
></A
>Avoiding Locks: Read And Write Ordering</H1
><P
> Sometimes it is possible to avoid locking. Consider the
following case from the 2.2 firewall code, which inserted an
element into a single linked list in user context:
</P
><TABLE
BORDER="0"
BGCOLOR="#E0E0E0"
WIDTH="100%"
><TR
><TD
><PRE
CLASS="PROGRAMLISTING"
> new->next = i->next;
i->next = new;
</PRE
></TD
></TR
></TABLE
><P
> Here the author (Alan Cox, who knows what he's doing) assumes
that the pointer assignments are atomic. This is important,
because networking packets would traverse this list on bottom
halves without a lock. Depending on their exact timing, they
would either see the new element in the list with a valid
<TT
CLASS="STRUCTFIELD"
><I
>next</I
></TT
> pointer, or it would not be in the
list yet. A lock is still required against other CPUs inserting
or deleting from the list, of course.
</P
><P
> Of course, the writes <I
CLASS="EMPHASIS"
>must</I
> be in this
order, otherwise the new element appears in the list with an
invalid <TT
CLASS="STRUCTFIELD"
><I
>next</I
></TT
> pointer, and any other
CPU iterating at the wrong time will jump through it into garbage.
Because modern CPUs reorder, Alan's code actually read as follows:
</P
><TABLE
BORDER="0"
BGCOLOR="#E0E0E0"
WIDTH="100%"
><TR
><TD
><PRE
CLASS="PROGRAMLISTING"
> new->next = i->next;
wmb();
i->next = new;
</PRE
></TD
></TR
></TABLE
><P
> The <TT
CLASS="FUNCTION"
>wmb()</TT
> is a write memory barrier
(<TT
CLASS="FILENAME"
>include/asm/system.h</TT
>): neither
the compiler nor the CPU will allow any writes to memory after the
<TT
CLASS="FUNCTION"
>wmb()</TT
> to be visible to other hardware
before any of the writes before the <TT
CLASS="FUNCTION"
>wmb()</TT
>.
</P
><P
> As i386 does not do write reordering, this bug would never
show up on that platform. On other SMP platforms, however, it
will.
</P
><P
> There is also <TT
CLASS="FUNCTION"
>rmb()</TT
> for read ordering: to ensure
any previous variable reads occur before following reads. The simple
<TT
CLASS="FUNCTION"
>mb()</TT
> macro combines both
<TT
CLASS="FUNCTION"
>rmb()</TT
> and <TT
CLASS="FUNCTION"
>wmb()</TT
>.
</P
><P
> Some atomic operations are defined to act as a memory barrier
(ie. as per the <TT
CLASS="FUNCTION"
>mb()</TT
> macro, but if in
doubt, be explicit.
Also,
spinlock operations act as partial barriers: operations after
gaining a spinlock will never be moved to precede the
<TT
CLASS="FUNCTION"
>spin_lock()</TT
> call, and operations before
releasing a spinlock will never be moved after the
<TT
CLASS="FUNCTION"
>spin_unlock()</TT
> call.
</P
></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="x256.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="x286.html"
ACCESSKEY="N"
>Next >>></A
></TD
></TR
><TR
><TD
WIDTH="33%"
ALIGN="left"
VALIGN="top"
>Big Reader Locks</TD
><TD
WIDTH="34%"
ALIGN="center"
VALIGN="top"
><A
HREF="c196.html"
ACCESSKEY="U"
>Up</A
></TD
><TD
WIDTH="33%"
ALIGN="right"
VALIGN="top"
>Avoiding Locks: Atomic Operations</TD
></TR
></TABLE
></DIV
></BODY
></HTML
>
