Skip to main content

Crate grommet_core

Crate grommet_core 

Source
Expand description

Key-affine fair scheduling as a pure data structure.

There is no async, no clock, no IO and no allocation policy here beyond the queues this module owns. Time is an explicit monotonic Duration supplied by the caller, and work items are opaque payloads. The exceptions are [ring] and [waker_slot], which are here for unsafe containment rather than because they are part of the scheduling model; see below.

§Fairness model

Each key has at most one in-flight item, so a key with a million queued items occupies exactly one dispatch slot, the same as a key with one. Given that, fairness reduces to which ready key is dispatched next?

A completed key is never greedily re-dispatched. Both new arrivals and completions place a key at the BACK of a round-robin ready ring, and dispatch always pops from the FRONT. A key sitting at position k is therefore dispatched within k dispatches: a strict bound, hence starvation-free. One key cannot monopolize a shard.

There is one ring per work class, each with its own in-flight budget, so a flood of one class cannot starve another. A key routes to a ring based on the class of its CURRENT queue head, so a key with mixed classes moves between rings in FIFO order as it drains.

§Trusting the caller

Everything this module knows about a payload: its affine key, its work class and its optional deadline: is stamped once by the caller at admission and never recomputed. A caller-supplied trait implementation that answered inconsistently on a second call would otherwise desynchronize the ready rings from the per-key queues, so the opportunity is removed rather than documented away.

§Unsafe code

This crate is where the workspace keeps its unsafe, so that there is one place to audit rather than a policy with exceptions. Every other crate is #![deny(unsafe_code)], and here it is confined to modules that opt back in one at a time:

  • the queue slab, which indexes without bounds checks;
  • [waker_slot], which guards an Option<Waker> with a two-bit lock;
  • [ring], which guards a slot’s value with a publication stamp;
  • the cell shim the last two share, which is one constructor and one accessor and exists so that both present loom’s checked UnsafeCell shape rather than each rolling its own.

Each states the invariant it relies on at the top of its file, debug_assert!s it at every use, and is checked by a model test under Miri. The two synchronization primitives are additionally model-checked by loom, which verifies the exclusion arguments mechanically: a slot read that escaped its stamp fails the model as a causality violation rather than passing as undefined behaviour that happens not to bite.

Modules§

timer
A predictable, shard-local hierarchical timer wheel.

Structs§

Admit
A work item being admitted, with its scheduling metadata already stamped.
Completion
The result of a dispatched item, returned to the scheduler.
Config
Per-shard scheduling limits.
Dispatch
A work item that the scheduler has granted exclusive ownership of its key.
Scheduler
A key-affine, class-fair scheduler over opaque payloads P and per-key state S.
Snapshot
Instantaneous scheduler gauges.

Enums§

Disposition
What became of a key’s state once its work finished.

Type Aliases§

ClassId
Index of a work class, in 0..CLASSES.