Module ordering 

Ordering substrate for AdaptiveRing: push stamps, the cross-process ordering header, per-producer watermarks, and the single-drainer lease.

The composed MPSC / MPMC shapes give per-producer FIFO only. This module is what turns global FIFO into a consumer-side discipline on those shapes: every push carries an 8-byte stamp in slot bytes [0..8), and a consumer that k-way-merges ring heads by stamp delivers items in global stamp order without the Vyukov data structure’s shared-CAS cost on the producer side.

Stamp sources

• StampKind::Tsc: rdtsc per push (~20 cycles, zero coherence traffic). Selected only when the invariant-TSC probe passes: CPUID leaf 0x8000_0007 EDX bit 8, which both Intel (“Invariant TSC available if 1”, SDM CPUID reference) and AMD (“TSC runs at constant rate with P/T states and does not stop in deep C-states”, APM 8000_0007h EDX) define identically. The probe first confirms the extended leaf exists via CPUID 0x8000_0000. Cross-core skew on one socket is nanoseconds; the merge treats it as the documented approximation window.
• StampKind::SharedCounter: fetch_add on a shared atom in the ordering header. Exact total order, but every producer pays the contended-cache-line cost the composed shapes otherwise avoid. Opt-in for callers that need exactness and accept the contention.
• StampKind::Monotonic: system-wide monotonic clock (CLOCK_MONOTONIC on unix, QueryPerformanceCounter on Windows). The non-x86 fallback; also valid on x86.

Per-producer stamp monotonicity is enforced at the stamp site: the issued stamp is max(source_now, last_issued + 1), so a producer thread migrating across cores with slightly-skewed TSC reads still emits strictly increasing stamps.

The ordering region

One small shared region per stamped ring, separate from the ring backings, holding the header below plus one cache line per producer slot:

+------------------------------------------------+
| OrderingHeader (one cache line)                |
|   magic: u64                                   |
|   mode: AtomicU32 (0=Unordered, 1=MergeByStamp,|
|         2=MergeStrict)                         |
|   stamp_kind: u32 (0=Tsc, 1=SharedCounter,     |
|         2=Monotonic)                           |
|   inversions: AtomicU64                        |
|   shared_stamp: AtomicU64 (counter mode)       |
|   drainer_token: AtomicU64                     |
|   drainer_heartbeat: AtomicU64                 |
|   drainer_epoch: AtomicU64                     |
+------------------------------------------------+
| ProducerLine[0]: issued + watermark (64B)      |
| ProducerLine[1]: ...                           |
| ... max_producers lines ...                    |
+------------------------------------------------+

File locale: <prefix>.ordering.bin. ShmFs locale: {prefix}_ordering named region. Anon: in-process page. The region is MMF-resident on purpose: the ordered-switch flag must be visible to every process attached to the ring, unlike the process-local shape_tag.

Watermarks (MergeStrict)

ProducerLine.watermark is the producer’s last PUBLISHED stamp, stored with Release after the ring push. Items inside a ring are stamp-ordered per producer, so a non-empty ring’s head bounds everything that producer has in flight. An EMPTY ring’s producer may hold a stamped-but-unpublished item, bounded below by its watermark: any future item from producer j has stamp > watermark[j]. The strict release gate is therefore candidate <= min(watermark[j]) over empty, in-use rings. Idle producers refresh their watermark (a heartbeat) so the gate does not couple consumer latency to producer silence forever.

Drainer lease

With M concurrent consumers, “global FIFO delivery” is meaningless downstream - two concurrent pops race regardless of pop order - so merge mode implies ONE active drainer. The lease lives in the header (drainer_token + heartbeat + epoch) and follows the OwnerLease claim protocol (CAS-claim when free, heartbeat-grace takeover when the holder goes silent), embedded here so every locale - including Anon and ShmFs, which OwnerLease’s file backing cannot serve - gets the same mechanism from the same region.

Structs

LeaseGenLine

Second header line: the drainer-lease GENERATION, alone on its own cache line. Bumped only on lease claim / takeover / release and on epoch ticks - all rare events - so a merge drainer’s per-pop lease verification is one load of a line that is NEVER written in steady state (an L1 hit with zero coherence traffic), instead of loads on the first header line that every SharedCounter push fetch_adds. Measured on the Zen3 KVM guest: per-pop loads of that stamp-hot line cost a cache-to-cache transfer each (~130 ns) and tripled the merge rungs.

OrderingHeader

Ordering header. One cache line at offset 0 of the region.

OrderingRegion

The mapped ordering region: header + producer lines, in any of the three locales.

ProducerLine

Per-producer ordering state. One cache line per producer slot so one producer’s stamp bookkeeping never invalidates a sibling’s L1 line.

Enums

OrderingMode

How a stamped ring’s consumer side interprets stamps.

StampKind

Which clock the stamps come from. Fixed at region creation; openers read it from the header so every process attached to the ring stamps from the same source.

Constants

MONOTONIC_FRESHNESS_GUARD_NANOS

Freshness guard for Monotonic stamps, in nanoseconds. Same role as TSC_FRESHNESS_GUARD_CYCLES.

ORDERING_MAGIC

Magic number identifying an ordering region. ASCII “ORDR” + version.

STAMPED_PAYLOAD_BYTES

Payload bytes available per slot in stamped mode: the stamp costs 8 of the 64 Lamport slot bytes, leaving 56 - exactly the Vyukov payload size, since Vyukov spends the same 8 bytes on its per-slot sequence atom.

STAMP_BYTES

Stamp width at the front of every stamped slot.

TSC_FRESHNESS_GUARD_CYCLES

Freshness guard for TSC stamps during a merge pop: when at least one ring is empty, a candidate younger than this many cycles may be raced by a stamped-but-unpublished item from the empty ring’s producer (the stamp-to-publish window). The merge re-peeks until the candidate ages past the guard. ~2-3us on contemporary cores; orders of magnitude above any producer’s stamp-to-publish latency.

Functions

default_stamp_kind

Pick the default stamp kind for this host: TSC when the invariant probe passes, the shared counter on x86 without an invariant TSC, and the monotonic clock everywhere else.

has_invariant_tsc

Invariant-TSC probe: CPUID leaf 0x8000_0007 EDX bit 8, after confirming the leaf exists via CPUID 0x8000_0000 (the maximum extended function leaf, per the Intel SDM CPUID reference; AMD defines the same bit as TscInvariant in APM 8000_0007h EDX).

monotonic_nanos

System-wide monotonic clock in nanoseconds. Comparable across processes on the same boot.

ordering_region_size

Total region size for max_producers producer slots.

read_tsc

Raw TSC read. Callers go through the StampKind stamp plumbing; exposed for the merge pop’s freshness-guard “now” reads.