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();
...[[INTERRUPT OCCURS]]

    // Imagine a timer interrupt happens at the ellipsis.
    // `k-cpu.cc:cpustate::schedule()` will attempt to run a new task.
    // Pretty soon, it executes:

    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, helps enforce lock discipline. The low-level spinlock::lock() function saves the current interrupt state, disables interrupts, and acquires the lock. It returns an irqstate object that represents the saved interrupt state. The low-level spinlock::unlock() function takes that irqstate object as an argument; it will restore interrupts if that is required.

auto irqs = whatever_lock.lock();
...[[interrupts are always disabled here]]...
whatever_lock.unlock(irqs);

In addition to this basic functionality, the irqstate will complain if it is goes out of scope without being passed to unlock:

auto irqs = whatever_lock.lock();
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.

In most cases, you won’t need to access irqstate objects, because you can use a spinlock_guard. Like standard C++ std::lock_guard and std::unique_lock objects, spinlock_guard automatically releases a lock when it goes out of scope.

{
    spinlock_guard guard(whatever_lock);
    ...
}

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.