14.2.5 Review of Locking Implementations

Naive pseudocode for simple lock and unlock operations are shown below. Note that the atomic_xchg() primitive implies a memory barrier both before and after the atomic exchange operation, which eliminates the need for an explicit memory barrier in spin_lock(). Note also that, despite the names, atomic_read() and atomic_set() do not execute any atomic instructions, instead, it merely executes a simple load and store, respectively. This pseudocode follows a number of Linux implementations for the unlock operation, which is a simple non-atomic store following a memory barrier. These minimal implementations must possess all the locking properties laid out in Section [*].



  1 void spin_lock(spinlock_t *lck)
  2 {
  3   while (atomic_xchg(&lck->a, 1) != 0)
  4     while (atomic_read(&lck->a) != 0)
  5       continue;
  6 }
  7 
  8 void spin_unlock(spinlock_t lck)
  9 {
 10   smp_mb();
 11   atomic_set(&lck->a, 0);
 12 }


The spin_lock() primitive cannot proceed until the preceding spin_unlock() primitive completes. If CPU 1 is releasing a lock that CPU 2 is attempting to acquire, the sequence of operations might be as follows:



CPU 1 CPU 2
(critical section) atomic_xchg(
smp_mb(); lck->a->1
lck->a=0; lck->a->1
lck->a->0
(implicit smp_mb() 1)
atomic_xchg(
(implicit smp_mb() 2)
(critical section)


In this particular case, pairwise memory barriers suffice to keep the two critical sections in place. CPU 2's atomic_xchg(&lck->a, 1) has seen CPU 1's lck->a=0, so therefore everything in CPU 2's following critical section must see everything that CPU 1's preceding critical section did. Conversely, CPU 1's critical section cannot see anything that CPU 2's critical section will do.

@@@

Paul E. McKenney 2011-12-16