Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Replace the spinlocks with better implementations #97

Open
heatd opened this issue Mar 19, 2024 · 2 comments
Open

Replace the spinlocks with better implementations #97

heatd opened this issue Mar 19, 2024 · 2 comments
Labels
enhancement New feature or request

Comments

@heatd
Copy link
Owner

heatd commented Mar 19, 2024

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:

  1. 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).

  2. 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.

@heatd heatd added the enhancement New feature or request label Mar 19, 2024
@heatd
Copy link
Owner Author

heatd commented Mar 19, 2024

cc @petershh

@heatd
Copy link
Owner Author

heatd commented Mar 19, 2024

spin_try_lock ticket lock prototyping: https://godbolt.org/z/cGb6ccrKh

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
enhancement New feature or request
Projects
None yet
Development

No branches or pull requests

1 participant