Pre-RFC: Investigate switching to intrusive waker lists by default

[jamesmunns]

This needs a more formal write up, but the root issue is that:

• The current waker infrastructure of embassy-sync uses an "AtomicWaker" style waker
• AtomicWakers only support storing the waker of a single task at a time
• This means that if two tasks are interested in the same thing, the tasks will constantly "churn", fighting for the waker spot

As one potential fix to this is using the primitives from maitake-sync:

• It's possible to use maitake-sync in a no-std configuration
• maitake-sync is extensively tested, with both miri (for UB checking) and loom (for atomic ordering checking).
• maitake-sync has a WaitCell type, suitable for a single waker, for owned items that won't (or shouldn't) have two tasks waiting on it
• maitake-sync has a WaitQueue type, which is an intrusive linked list configuration. It requires a blocking mutex for adding/removing nodes from the queue

There is however one major blocker: maitake-sync currently uses a spinlock mutex for its blocking mutex, and is not generic over different blocking mutex, like the RawMutex trait of embassy-sync. The author of maitake-sync, @hawkw (I am also a maintainer, but Eliza has done the vast majority of heavy lifting), has mentioned that she is open to parameterizing the maitake-sync collections similarly to how embassy-sync does it.

So my concrete proposal would be:

• Split out the RawMutex traits into a separate crate (embassy-sync-mutex, or something?), to allow for both embassy-sync and maitake-sync to rely on this
• Implement support for RawMutex parameterization of maitake-sync primitives
• Replace embassy-sync's current AtomicWaker-like primitives with EITHER WaitCell or WaitQueue from maitake-sync, as appropriate

This will require a fair bit of work, but should IDEALLY not have any publicly breaking interface changes for users of embassy-sync, though it may have some (mostly benefitial, ideally) functional changes.

I expect this change would:

• Make "single waiter" cases slightly slower, at least in cases where a WaitQueue was used because it is potentially possible to await from two tasks
• Make "multiple waiter" cases in a single executor significantly more efficient, as there is no burned CPU churning on waking
• Make "multiple waiter" cases in an interupt executor configuration significantly more efficient and predictable, as a churning high prio waker will not starve lower prio executor tasks

Overall, I think this is worth investigating/discussing, as it has come up a number of times in chat (not a ton! But enough now that it is a semi-known failure mode).

Some open questions include:

• Should embassy-sync use maitake-sync, or fork/copy the primitives used there, to allow "in-project" maintenance
• How do we avoid burdening a "somewhat unrelated" project with embassy's concerns? by forking? by adding embassy folks to the maitake-sync owners?
• Do we expose/re-export maitake's other concurrency primitives? They are likely useful, but having another (particularly non-1.0) crate in embassy-sync's public API always is a little dicey, due to versioning maintenance

CC: @hawkw @ivmarkov @Dirbaio

[ivmarkov]

(UPDATED)

• Split out the RawMutex traits into a separate crate (embassy-sync-mutex, or something?), to allow for both embassy-sync and maitake-sync to rely on this

Splitting out RawMutex into its own micro-crate (ala embassy-time-driver and embassy-net-driver) - that is - if you decide against forking a subset of maintake-sync into embassy-sync - might have use-cases beyond your idea of re-using it in maintake-sync so that embassy-sync can depend on maintake-sync rather than fork it.

For example, that would give "easier time" to RawMutex implementor code that lives outside the embassy-sync crate. esp-idf-hal is currently such one, by providing two separate mutex implementations - one - based on "disable all interrupts (+ spinlocks for multi-core)" and another - based on regular FreeRTOS mutexes.

The thing is, the "one size fits all" approach of critical-section just does not work for traditional RTOSes, where you might need different types of blocking mutexes, depending on the context where you would like to use those. Abstracting by using RawMutex instead (and sure - by introducing generics that way) is one way to solve that in driver crates.

Currently, esp-idf-hal depends directly on embassy-sync, which is a bit painful. For example, our next release would be a breaking one, because embassy-sync currently went from 0.5 to 0.6. That's definitely not the only reason but could've been the only reason to issue a breaking release, which is not ideal.

[jamesmunns]

Splitting out RawMutex into its own micro-crate (ala embassy-time-driver and embassy-net-driver) - that is - if you decide against forking a subset of maintake-sync into embassy-sync - might have use-cases beyond your idea of re-using it in maintake-sync so that embassy-sync can depend on maintake-sync rather than fork it.

Just confirming that I agree 100%! I didn't spell this out, but I definitely think this is a positive.

[hawkw]

Regarding abstracting over raw mutex types, I would encourage investigating whether the lock_api crate can be used for that purpose --- it's pretty widespread in the non-embedded world, as parking-lot uses lock-api, but it also claims to have no-std support. I would look into whether its traits are suitable for our purpose. If they are, it's probably better to use the commonly-used trait rather than inventing a new version of it.

[xgroleau]

This would be great as this would also fix #1204 when using multiple executor with different interrupt priorities which would make embassy better equipped when users needs to do real time operations.

[peterkrull]

I'm just leaving a comment here to express interest in using WaitQueue as well. Presumably it would simplify the type signatures of the PubSubChannel and Watch channels since the number of senders/receivers would no longer need to be defined at compile time, and obtaining a receiver would always succeed.