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:
new->next = i->next; i->next = new;
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
next
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.
Of course, the writes must be in this
order, otherwise the new element appears in the list with an
invalid next
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:
new->next = i->next; wmb(); i->next = new;
The wmb()
is a write memory barrier
(include/asm/system.h): neither
the compiler nor the CPU will allow any writes to memory after the
wmb()
to be visible to other hardware
before any of the writes before the wmb()
.
As i386 does not do write reordering, this bug would never show up on that platform. On other SMP platforms, however, it will.
There is also rmb()
for read ordering: to ensure
any previous variable reads occur before following reads. The simple
mb()
macro combines both
rmb()
and wmb()
.
Some atomic operations are defined to act as a memory barrier
(ie. as per the mb()
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
spin_lock()
call, and operations before
releasing a spinlock will never be moved after the
spin_unlock()
call.