Kernel: Blocking overhaul and missing synchronization primitives

[Hendiadyoin1]

We currently have the following Synchronization "Primitives":

• Mutex: Rather efficient lock interacting with the scheduler
• Spinlock: Hot loop lock, May be Rank aware enforcing acquisition order
• WaitQueue: Not quite a condition variable, uses Blockers
• Blockers/BlockerSets: Similar to wait queues, but usually special purpose and support timeouts
  Like for Futices, Thread joins or ARP routing

The main issues are as follows

• There is a special BigLock mutex, which is very broadly scoped and needs special handling in a lot of places
  Ideally this should be removed (ongoing effort)
• Blockers are not very well documented
• WaitQueue cannot virtually atomically unblock mutices or Spinlocks, which would make it a full CV
• The blocking code is quite old and crusty in some places, dancing with a lot of unranked Spinlocks
• Do we really need RecursiveSpinlocks in this many places
  like why is a mutexes block list recursive-spinlock protected?

Missing (useful) Primitives may include

• proper Condition Variables (see above)
• Latches for tracking asynchronous HW task completion (Usually may also be doable with a CV and may CVs to work)

[spholz]

The problem with our current WaitQueues is that they can't be used in a way that doesn't suffer from lost wakeups (https://discord.com/channels/830522505605283862/830525093905170492/1376226491830108160).

[spholz]

We currently use WaitQueues like this:

if (should_block())
    wait_queue.wait_forever()

for example here:

serenity/Kernel/Bus/USB/xHCI/xHCIController.cpp

Lines 354 to 355 in 361ff11

	enqueue_command(transfer_request_block);
	m_command_completion_queue.wait_forever();

and here:

serenity/Kernel/FileSystem/FIFO.cpp

Lines 58 to 59 in 361ff11

	locker.unlock();
	m_read_open_queue.wait_forever("FIFO"sv);

The problem is that another thread could do wait_queue.wake_all() between the if (should_block()) and wait_queue.wait_forever(), causing a lost wakeup.
We probably need to redesign WaitQueues from the ground up to avoid such lost wakeups.
Some kind of atomic unlock and block operation (like condition variables) would be needed.

https://read.seas.harvard.edu/cs1610/2025/doc/wait-queues/ has a nice explanation of WaitQueues and some implementation ideas.

[implicitfield]

I've tried out reimplementing WaitQueue on this branch. It's not quite PR-worthy yet, mainly because it looks like the scheduler can issue spurious wakeups when resuming a stopped process since this "WaitQueueV2" design isn't based on blockers (not sure if it should be, though I'm leaning toward not doing that). It's all very heavily based on the above link, and that does mean that we do now always need some sort of proper block condition to evaluate (see the FinalizerTask rework on that branch).

[spholz]

I've tried out reimplementing WaitQueue on this branch.

Oh, thanks for working on this! I was putting this off for a while now since looking at Blocker code was uh not very nice.

I don't really have time to take an in-depth look at your branch right now though (sorry!).

It's not quite PR-worthy yet, mainly because it looks like the scheduler can issue spurious wakeups when resuming a stopped process since this "WaitQueueV2" design isn't based on blockers (not sure if it should be, though I'm leaning toward not doing that).

I do think that making this not Blocker-based is the right approach. And in fact, I think/hope that we might be able to remove some blockers and implement them as WaitQueues instead. This current Blocker code is not very nice and pretty hard to follow.

It's all very heavily based on the above link, and that does mean that we do now always need some sort of proper block condition to evaluate (see the FinalizerTask rework on that branch).

I do like the general design from that link. But I think we could maybe additionally introduce a class that stores a single flag and waiter that can wait for a certain condition. I can't really think of a good name for it, but it could be used in places where code just needs to wait for a condition that can be signaled by setting an (atomic) bool. That seems nicer than having to supply a lambda that checks for the unblocking condition each time.

[implicitfield]

Oh, thanks for working on this! I was putting this off for a while now since looking at Blocker code was uh not very nice.

Yeah, that's why I tried to avoid Blockers as well. Luckily, I guess there's no need to use those for this if the issue with stopped threads can be addressed (which might be as simple as just setting a flag from within Waiter to let the scheduler know that the block wasn't issued by a Blocker).

I do like the general design from that link. But I think we could maybe additionally introduce a class that stores a single flag and waiter that can wait for a certain condition. I can't really think of a good name for it, but it could be used in places where code just needs to wait for a condition that can be signaled by setting an (atomic) bool. That seems nicer than having to supply a lambda that checks for the unblocking condition each time.

That does seem nice for these basic use-cases (though I can't really think of a particularly descriptive name for such a class either), since these lambdas are kind of verbose just for a single condition.