Expand description
Timer state structures.
This module contains the heart of the intrusive timer implementation, and as such the structures inside are full of tricky concurrency and unsafe code.
§Ground rules
The heart of the timer implementation here is the TimerShared
structure,
shared between the TimerEntry
and the driver. Generally, we permit access
to TimerShared
ONLY via either 1) a mutable reference to TimerEntry
or
2) a held driver lock.
It follows from this that any changes made while holding BOTH 1 and 2 will
be reliably visible, regardless of ordering. This is because of the acq/rel
fences on the driver lock ensuring ordering with 2, and rust mutable
reference rules for 1 (a mutable reference to an object can’t be passed
between threads without an acq/rel
barrier, and same-thread we have local
happens-before ordering).
§State field
Each timer has a state field associated with it. This field contains either
the current scheduled time, or a special flag value indicating its state.
This state can either indicate that the timer is on the ‘pending’ queue (and
thus will be fired with an Ok(())
result soon) or that it has already been
fired/deregistered.
This single state field allows for code that is firing the timer to
synchronize with any racing reset
calls reliably.
§Cached vs true timeouts
To allow for the use case of a timeout that is periodically reset before expiration to be as lightweight as possible, we support optimistically lock-free timer resets, in the case where a timer is rescheduled to a later point than it was originally scheduled for.
This is accomplished by lazily rescheduling timers. That is, we update the
state field with the true expiration of the timer from the holder of
the TimerEntry
. When the driver services timers (ie, whenever it’s
walking lists of timers), it checks this “true when” value, and reschedules
based on it.
We do, however, also need to track what the expiration time was when we originally registered the timer; this is used to locate the right linked list when the timer is being cancelled. This is referred to as the “cached when” internally.
There is of course a race condition between timer reset and timer
expiration. If the driver fails to observe the updated expiration time, it
could trigger expiration of the timer too early. However, because
mark_pending
performs a compare-and-swap, it will identify this race and
refuse to mark the timer as pending.
Structs§
- This structure holds the current shared state of the timer - its scheduled time (if registered), or otherwise the result of the timer completing, as well as the registered waker.
- A timer entry.
- An
TimerHandle
is the (non-enforced) “unique” pointer from the driver to the timer entry. Generally, at most oneTimerHandle
exists for a timer at a time (enforced by the timer state machine). - The shared state structure of a timer. This structure is shared between the frontend (
Entry
) and driver backend.
Constants§
- The largest safe integer to use for ticks.