Module shared_deque_urd 

SharedDequeUrd - UMWAIT Rendezvous Deque, MMF-backed.

Per-thief mailbox cache lines instead of a shared deque. Each mailbox is one 64-byte line carrying state (8 B) + MAILBOX_ITEMS = 3 line items (48 B) + 8 B trailing padding. The owner picks a mailbox by round-robin (or by an explicit target index) and writes the items in; the addressed thief observes the cache-line transition and reads its items. There is no shared head/tail counter on the steal path - each thief has its own state byte and never CASes a contended atomic.

Wait strategy: runtime dispatch on WAITPKG

Thieves idle on their mailbox’s state byte. The wait primitive is chosen at runtime by subetha_core::has_waitpkg:

• WAITPKG available (Intel Tremont / Tiger Lake+ and AMD Zen 5+): thief uses UMONITOR + UMWAIT to halt until the cache line transitions OR a TSC deadline fires. Power-efficient; the thief does not burn pipeline slots polling.
• WAITPKG not available (most pre-2020 silicon including AMD Zen+/2/3/4): thief uses std::hint::spin_loop (PAUSE on x86) in a tight Acquire-load loop on the state byte.

Both branches end the wait when state carries the ready bit for the expected epoch.

Why this shape vs SharedDeque / SharedDequeKhpd

SharedDeque (Chase-Lev) and SharedDequeKhpd are pull-based: thieves CAS the deque to discover work. URD is push-based: the owner picks the target thief by writing its mailbox. Two architectural consequences:

1. No CAS contention at the steal site. N thieves on a shared deque CAS the same head; under contention each push racing N thieves can take O(N) failed CASes. URD’s per-thief mailbox has zero contention because the owner is the only writer and the thief is the only reader.
2. Owner-controlled distribution. Round-robin / locality-aware / variance-driven targeting is the owner’s choice, not a thief’s victim-pick. The orchestrator gets explicit say in which thief does what.

Trade-offs: the thief is bound to one mailbox (no work-stealing between mailboxes), the owner pays one mailbox-spin per publish if the previous batch has not been consumed yet, and the per-mailbox slot count is fixed at MAILBOX_ITEMS.

Structs

DrainResult

Items pulled from a mailbox.

Mailbox

One per-thief mailbox cache line.

SharedDequeUrd

MMF-backed UMWAIT Rendezvous Deque. Single owner, N pre-configured thieves.

UrdHeader

File header. Cache-line aligned.

Enums

Drain

Outcome of SharedDequeUrd::drain_mailbox.

PublishError

Outcome of SharedDequeUrd::publish_to.

PublishStrategy

Publish strategy chosen at runtime per CPUID.

WaitStrategy

Wait strategy chosen at runtime per CPUID.

Constants

MAILBOX_ITEMS

Items per mailbox: state (8 B) + 3 * 16 = 56 B; 8 B trailing pad.

URD_MAGIC

Magic byte sequence marking a valid URD file. ASCII ‘WURD’ + ver.

URD_MAILBOX_SIZE

Cache-line size; one mailbox per cache line.

Functions

urd_file_size

Total file size for a URD with n_mailboxes mailboxes.