Spinlocks

Chickadee uses spinlocks to coordinate among different cores. Different operating system structures are protected by different locks.

A spinlock is a simple synchronization object providing mutual exclusion. A spinlock has two operations, lock and unlock. Only one core can have the lock at a time. Normal x86-64 load and store instructions can’t provide mutual exclusion: special instructions, such as lock xchg and mfence, are required.

Interrupts and deadlock

Chickadee kernel tasks can be suspended. This makes spinlocks risky: an interrupt received at the wrong time could cause deadlock. For example, imagine the following kernel code:

// This kernel task is trying to add a new process to its runqueue,
// so it locks the current CPU’s `runq_lock_`.
this_cpu()->runq_lock_.lock();
...

// Imagine a timer interrupt happens at the ellipsis.
// `k-cpu.cc:cpustate::schedule()` will attempt to run a new task.
// Its code:

// otherwise load the next process from the run queue
runq_lock_.lock_noirq();  // Deadlock: will spin forever with interrupts disabled!

To avoid problems like this, Chickadee spinlocks enforce a simple two-part lock discipline.

1. A spinlock can be locked only if interrupts are disabled.
2. cpustate::schedule() can be called only if no spinlocks are held.

This discipline prevents many deadlocks (but not all).

Using spinlocks

Our spinlock implementation, in k-lock.hh, is designed to help enforce this lock discipline. Here’s how a spinlock is normally used.

auto irqs = whatever_lock.lock();
...
whatever_lock.unlock(irqs);

The lock function automatically disables interrupts before acquiring the lock. It then returns a special irqstate object that remembers the previous interrupt state. This object must be passed to unlock(), which will restore interrupts if appropriate. (The lock/unlock pair is safe even if interrupts were already disabled.)

C++ features are used to enforce lock discipline. For example, if you return from a function without unlocking the lock, you’ll get an assertion failure:

auto irqs = whatever_lock.lock();
... no unlock() ...
return;
    // will fail an assertion `!flags && "forgot to unlock a spinlock"`

The lock and unlock functions also track how many spinlocks are held by the current CPU. If cpustate::schedule() is called with one or more spinlocks held, a different assertion will fail.

These features will constrain the kinds of code you can write. In general, the constraints are good: they will force you to be more clear and handle locks in a more standard way. But if you run into trouble, contact us.

Spinlocks also offer more dangerous lock_noirq() and unlock_noirq() functions. These functions lock and unlock without changing the interrupt state or tracking spinlock counts. If the lock constraints cause problems in some tricky situation, consider manually disabling interrupts and using lock_noirq().

Spinlock implementation

The spinlock implementation uses C++ standard atomics, which are the standard way to access atomic operations in modern C++. Specifically, the body of the lock uses the std::atomic_flag type, which offers test_and_set() and clear() operations. It’s important to use standard features when possible (rather than, for example, inline assembly), because it’s clearer than inline assembly and because threads cannot be implemented as a library.