Understanding xv6: Locking

Locking

any code that accesses shared data must have strategy for correctness despite concurrency. A lock provides mutual exclusion.
machine shares one disk among multiple processor. This would lead to race condition.

Race Condition:

linked-list of request to IDE disk without consideration of race conditon:

1 struct list {
2 int data;
3 struct list *next;
4 };
5
6 struct list *list = 0;
7
8 void
9 insert(int data)
10 {
11 struct list *l;
12
13 l = malloc(sizeof *l);
14 l->data = data;
15 l->next = list;
16 list = l;
17 }

The race conditon happens at line between 15 and 16:
If two CPUs concurrently execute line 15 before line 16, the second will overwrite the first and first data will be lost.

correct version of linked-list of request to IDE disk

6 struct list *list = 0;
struct lock listlock;
7
8 void
9 insert(int data)
10 {
11 struct list *l;
12 l = malloc(sizeof *l);
13 l->data = data;
14
acquire(&listlock);
15 l->next = list;
16 list = l;
release(&listlock);
17 }

line 15 & 16 is now critical section that will executed atomically.
You can think of locking as "serialization" of concurrent critical section that should be executed atomically.

Deadlock:

in following concurrent code path,
Thread1 acquire lock A
Thread2 acquire lock B
Thread1 acquire lock B (block)
Thread2 acquire lock A (block)
-> each acquires will block indefinitely.
Both acquires will block indefinitely, because in both cases the other thread holds the needed lock, and won’t release it until its acquire returns.

lock-ordering is important in function specification.

Interrupt Handler:

kernel code can be stopped to run interrupt handler at any moment.
-> if the both interrupt handler code and kernel code use same shared data, it will be required to use locking, however this locking would cause deadlock.

Example:
suppose iderw() held the idelock and interrupted to run ideintr() that also will try to hold the idelock.
-> Deadlock occurs: ideintr() waits for idelock to be release, but iderw() cannot continue until the ideintr() return.

xv6 solves this problem by disabling the interrupt feature at the acquire() and re-enabling the interrupt feature at the release().

spinlock.c

 24 void
 25 acquire(struct spinlock *lk) 
 27   pushcli(); // disable interrupts to avoid deadlock.
....
 46 void
 47 release(struct spinlock *lk) 
 67   popcli(); //re-enable interrupts after release

pushcli() to disable the interrupt:

104 void
105 pushcli(void)
106 {
107   int eflags;
108
109   eflags = readeflags();
110   cli(); //cli to disable interrupt 
111   if(mycpu()->ncli == 0)
112     mycpu()->intena = eflags & FL_IF;
113   mycpu()->ncli += 1;
114 }

popcli() to re-enable the interrupt:

116 void
117 popcli(void)
118 {
119   if(readeflags()&FL_IF)
120     panic("popcli - interruptible");
121   if(--mycpu()->ncli < 0)
122     panic("popcli");
123   if(mycpu()->ncli == 0 && mycpu()->intena)
124     sti(); //sti to enable the interrupt 
125 }

Instructions and memory ordering:

many compilers and processors execute code out of order to achieve higher performance.
-> this ordering may violate the lock-order chains of the function and causes deadlock.
To avoid this situation, when locking, it tells hardware and compiler not to perform ordering by __sync_synchronize().

 24 void
 25 acquire(struct spinlock *lk)
 ...
 38   __sync_synchronize(); //Tell the C compiler and the processor to not  move loads or stores past this point 

Locks implementation in xv6

spin-lock and sleep-lock exist.
spin-lock:
if "locked" field is zero, lock is available, if it is one, lock is held by other process.
spinlock.h

1 // Mutual exclusion lock.
  2 struct spinlock {
  3   uint locked;       // Is the lock held?
  4
  5   // For debugging:
  6   char *name;        // Name of lock.
  7   struct cpu *cpu;   // The cpu holding the lock.
  8   uint pcs[10];      // The call stack (an array of program counters)
  9                      // that locked the lock.
 10 };
 11

Lock is acquired function acquire().
wrong version of the acquire():
It causes race condition between line 25 and line 26.

21 void
22 acquire(struct spinlock *lk)
23 {
24 for(;;) {
25 if(!lk->locked) {
26 lk->locked = 1;
27 break;
28 }
29 }
30 }

correct version of the acquire():
checking and setting should be atomic -> xchg instruction is atomic.
If "locked" field is 1, xchg() will return 1 and loop continue until the lock is released.
if "locked" field is 0, xchg() will return 0 and can stop loop.

24 void
 25 acquire(struct spinlock *lk)
 26 {
 27   pushcli(); // disable interrupts to avoid deadlock.
 28   if(holding(lk))
 29     panic("acquire");
 30
 31   // The xchg is atomic.
 32   while(xchg(&lk->locked, 1) != 0) 
 33     ;
 34
...

Lock is released by function release().
This function uses assembly instruction to clear the fields and release the lock, because these two things should be done atomically.

46 void
 47 release(struct spinlock *lk)
 48 {
 49   if(!holding(lk))
 50     panic("release");
 51
 52   lk->pcs[0] = 0;
 53   lk->cpu = 0;
 54
 55   // Tell the C compiler and the processor to not move loads or stores
 56   // past this point, to ensure that all the stores in the critical
 57   // section are visible to other cores before the lock is released.
 58   // Both the C compiler and the hardware may re-order loads and
 59   // stores; __sync_synchronize() tells them both not to.
 60   __sync_synchronize();
 61
 62   // Release the lock, equivalent to lk->locked = 0.
 63   // This code can't use a C assignment, since it might
 64   // not be atomic. A real OS would use C atomics here.
 65   asm volatile("movl $0, %0" : "+m" (lk->locked) : );
 67   popcli(); //re-enable the interrupt after release
 68 }

 ...