Spin Locking

We know that xv6 uses SpinLocks, sleep and wakeup for its locking. In this post, let us discuss SpinLocks.

SpinLocks are defined in spinlock.c.

Basics

There are primarily two functions related to locks, acquire and release

acquire

Acquiring the lock seems simple enough on the surface.

while (locked == 1);
locked = 1;
cpu = mycpu();

But two processors can simultaniously execute this! Therefore we need an atomic operation to read and write to locked in one instruction. Fortunately RISC-V has one such instrcution - AMOSWAP, which we will use.

Another thing to note is that we need to disable preemption or interrupts while we are in the critical section!

Therefore, we have-

   1 -> [  Locked  ] -> y
   if (y != 0) try again

release

release is quite simple, just put value 0 in the locked field!

Theory

Now, acquire() disables the interrupts and release() re-enables them. But now, situations with multiple locks becomes problematic.

acquire(&lk1);
acquire(&lk2);

// Critical Section

release(&lk2);    // Interrupts re-enabled prematurely!!

// Some more operations

release(&lk1);

So, we store a counter noff and a status int intena (interrupts enabled) for each hart.

If this is the first acquire (noff =​= 0), we set intena to current interrupt status (0 if disables, 1 otherwise). We then increment the counter regardless.

During release, we decrement the counter and if it becomes 0, we restore the interrupts to their saved state in intena!

Code

Structure

The struct spinlock itself, is defined in spinlock.h.

struct spinlock {
  uint locked;       // Is the lock held?

  // For debugging:
  char *name;        // Name of lock.
  struct cpu *cpu;   // The cpu holding the lock.
};

It contains an int locked, which indicates that the lock is free/unacquired when locked = 0 and otherwise for locked = 1

Imports

We first import the necessary files. Nothing too exciting here.

#include "types.h"
#include "param.h"
#include "memlayout.h"
#include "spinlock.h"
#include "riscv.h"
#include "proc.h"
#include "defs.h"

Initalising the lock

Before we can even acquire the lock, we need to actually initialise it! Its steps are easy enough to be obvious.

void
initlock(struct spinlock *lk, char *name)
{
  lk->name = name;
  lk->locked = 0;
  lk->cpu = 0;
}

Acquiring the Lock

Let’ start writing the acquire function!

void acquire(struct spinlock *lk) {
  <<aq_disable_interrupt>>
  <<aq_atomic_swap>>
  <<aq_misc>>
}

1. As discussed earlier we first disable the interrupts. push_off() takes care of that. We also ensure we already aren’t holding the lock.

     push_off();
     if(holding(lk))
         panic("acquire");

2.    while(__sync_lock_test_and_set(&lk->locked, 1) != 0);

3. We need to ensure that compiler optimisations do not mess with the order, also store the cpu’s information in the struct.

      __sync_synchronize();
      lk->cpu = mycpu();

Our final acquire function-

void acquire(struct spinlock *lk) {
  push_off();
  if(holding(lk))
      panic("acquire");
  while(__sync_lock_test_and_set(&lk->locked, 1) != 0);
  __sync_synchronize();
  lk->cpu = mycpu();
}

Releasing the lock

Releasing is a lot simpler.

void release(struct spinlock *lk) {
  <<rl_misc>>
  <<rl_en_int>>
}

1. Ensure we are holding the lock, scrub cpu information, synchronise, and release the lock

      if(!holding(lk))
        panic("release");
   
      lk->cpu = 0;
   
      __sync_synchronize();
   
      __sync_lock_release(&lk->locked);

2. Re-enable Interrupts

      pop_off();

Release function-

void release(struct spinlock *lk) {
  if(!holding(lk))
    panic("release");

  lk->cpu = 0;

  __sync_synchronize();

  __sync_lock_release(&lk->locked);
  pop_off();
}