Our current spinlocks are essentially
struct spinlock { unsigned int word; };
void lock(struct spinlock *s)
{
while(!cmpxchg(&s->word, 0, 1) cpu_pause();
}this is alright for raw throughput but is palpably unfair to other less fortunate CPUs.
Two options (and we'll need both) are available:
-
Ticket locks
These are pretty much just struct spinlock { u16 next_ticket, u16 curr_ticket; };. Waiters increment next_ticket (thru an atomic fetch_add), then wait for curr_ticket to be == their ticket. This is still cache-awful but at least it's much fairer. Throughput should take a hit, but that's okay. (note: while writing this up, i noticed that a spin_try_lock in this would be tricky, but it's doable with a single 32-bit cmpxchg).
-
MCS locks
MCS locks basically make waiters spin on their own cacheline, so it's OPTIMAL for systems with lots of threads and CPUs. The idea here is to essentially make a linked list of CPUs and use percpu accessors to access these separate structs. These are kept percpu and we should keep one struct per level (irqsave, normal (no preempt)).
We likely want both, MCS locks aren't necessarily needed in many cases, e.g riscv machines that have a small-ish amount of CPUs.
NOTE: it's super important to keep the current struct spinlock size, we do not want to bloat up all the various users of spinlocks in the kernel.
Our current spinlocks are essentially
this is alright for raw throughput but is palpably unfair to other less fortunate CPUs.
Two options (and we'll need both) are available:
Ticket locks
These are pretty much just
struct spinlock { u16 next_ticket, u16 curr_ticket; };. Waiters increment next_ticket (thru an atomic fetch_add), then wait for curr_ticket to be == their ticket. This is still cache-awful but at least it's much fairer. Throughput should take a hit, but that's okay. (note: while writing this up, i noticed that a spin_try_lock in this would be tricky, but it's doable with a single 32-bit cmpxchg).MCS locks
MCS locks basically make waiters spin on their own cacheline, so it's OPTIMAL for systems with lots of threads and CPUs. The idea here is to essentially make a linked list of CPUs and use percpu accessors to access these separate structs. These are kept percpu and we should keep one struct per level (irqsave, normal (no preempt)).
We likely want both, MCS locks aren't necessarily needed in many cases, e.g riscv machines that have a small-ish amount of CPUs.
NOTE: it's super important to keep the current struct spinlock size, we do not want to bloat up all the various users of spinlocks in the kernel.