Single CAS

[ghost]

I'm convinced that there is a way to trigger a pulse -> signal with only a single CAS.

Right now there is three opeartions

• Atomic or to set a flag,
• Atomic swap to read the pending waitlist
• Atomic dec to mark the trigger as ready to free

The or and the dec cannot be merged because the waitlist needs to be read and is protected by the value of the dec.

[ghost]

There is a complicated scheme that I came up with. We just use one AtomicPointer per node.

struct Node {
    state: AtomicUint
}

The pulse gets a pointer to the first signal. When it fires, it swaps the state with a value that represents a fired pulse. The state it swaps is a link to the next node, if it is NULL it is the end of the list. The pulse has the follow this handle where it will find either a wakeup token, or another node. A wakeup token will be woken and the chain will be followed.

The trick is that a Node is shared, a wake token is not. A node may have at most two parents, the Signal, and the Pulse. If the pulse reaches the node and swaps the state to fired (or error) it has now signalled to the Signal that it's ownership of the Node is complete. And the Node may be freed (as far as the Pulse is concerned). A wake token is only owned by one item in the chain, therefore it is consumed by whoever takes it.

There is a case where a Signal is dropped before the Pulse is asserted. In that case the Pulse needs to be told to cleanup the Node's memory. The best idea I have is to make the state a tagged pointer. If the lowest bit is set to 1, it means the Node has been dropped. If the next is just 1, it is the end of the chain too. but it may also contain a link to a Signal.

So, TL;DR. Everything is forced into the state. The waitlist is both wake tokens, and signal node.