6.5 Re-entrant locks

It might appear that some deadlocks and lock-ordering challenges could be avoided by using re-entrant locks, which are also called recursive locks. The idea is that if the lock is held by a process and if that process attempts to acquire the lock again, then the kernel could just allow this (since the process already has the lock), instead of calling panic, as the xv6 kernel does.

It turns out, however, that re-entrant locks make it harder to reason about concurrency: re-entrant locks break the intuition that locks cause critical sections to be atomic with respect to other critical sections. Consider the following functions f and g, and a hypothetical function h:

⬇


              1
              
              
              
            struct spinlock lock;


              2
              
              
              
            int data = 0; // protected by lock


              3
              
              
              
            


              4
              
              
              
            f() {


              5
              
              
              
              acquire(&lock);


              6
              
              
              
              if(data == 0){


              7
              
              
              
                call_once();


              8
              
              
              
                h();


              9
              
              
              
                data = 1;


              10
              
              
              
              }


              11
              
              
              
              release(&lock);


              12
              
              
              
            }


              13
              
              
              
            


              14
              
              
              
            g() {


              15
              
              
              
              aquire(&lock);


              16
              
              
              
              if(data == 0){


              17
              
              
              
                call_once();


              18
              
              
              
                data = 1;


              19
              
              
              
              }


              20
              
              
              
              release(&lock);


              21
              
              
              
            }


              22
              
              
              
            


              23
              
              
              
            h() {


              24
              
              
              
                ...


              25
              
              
              
            }

Looking at this code fragment, the intuition is that call_once will be called only once: either by f, or by g, but not by both.

But if re-entrant locks are allowed, and h happens to call g, call_once will be called twice.

If re-entrant locks aren’t allowed, then h calling g results in a deadlock, which is not great either. But, assuming it would be a serious error to call call_once, a deadlock is preferable. The kernel developer will observe the deadlock (the kernel panics) and can fix the code to avoid it, while calling call_once twice may silently result in an error that is difficult to track down.

For this reason, xv6 uses the simpler to understand non-re-entrant locks. As long as programmers keep the locking rules in mind, however, either approach can be made to work. If xv6 were to use re-entrant locks, one would have to modify acquire to notice that the lock is currently held by the calling thread. One would also have to add a count of nested acquires to struct spinlock, in similar style to push_off, which is discussed next.