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,
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
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.
- A spinlock can be locked only if interrupts are disabled.
cpustate::schedule()can be called only if no spinlocks are held.
This discipline prevents many deadlocks (but not all).
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);
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"`
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
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
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
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.