flynnel 0.6.0

K-aware NUMA-aware work-stealing scheduler with extended-Flynn-taxonomy dispatch (MIMD / SIMC / MIMC / MISD / SIMT / MIMT): a rayon-shaped pool reshaped around per-call execution-class plans with first-class CPU+GPU hybrid (join_hybrid, hybrid_pipeline) and per-call dispatch profiles.
Documentation
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
//! KHPD: K-axis Hierarchical Publication Deque, MMF-backed.
//!
//! Owner publishes
//! to a ring of fixed-size **publication lines**; each line holds
//! `LINE_ITEMS = 3` items inline and is claimed atomically as a
//! group by a single thief CAS. The amortization win vs the
//! per-item LOH / Chase-Lev shape: one Release-store on the line's
//! state byte publishes K items together; one cache-line transfer
//! delivers K items to the claiming thief.
//!
//! ## Layout
//!
//! ```text
//! +-----------------------------+
//! | KhpdHeader (64B)            |  magic, capacity, owner_pid,
//! |                             |  tail, head (each on its own line)
//! +-----------------------------+
//! | PublicationLine[0]  (64B)   |  state (8B) + 3 LineItems (48B)
//! | PublicationLine[1]          |
//! | ...                         |
//! | PublicationLine[capacity-1] |
//! +-----------------------------+
//! ```
//!
//! Each `PublicationLine` is exactly one cache line so adjacent
//! lines never share a coherence-traffic line. `state` is an
//! `AtomicU64` packed as `(epoch: u32, n_items: u16, claim: u16)`;
//! the publisher increments `epoch` and stores `n_items` + claim =
//! READY in one store, the claimer CAS-takes by setting `claim =
//! CLAIMED`, and the consumer's release advances `state` to the
//! next round's epoch.
//!
//! ## Per-item line layout
//!
//! `LineItem` is 16 bytes: `closure_id` (4 B) plus `latch_offset`
//! (4 B) plus `args_inline` (8 B). For payloads larger than 8
//! bytes, the caller routes through
//! [`super::chase_lev_mmf::MmfChaseLevDeque`] (48 B per slot) or
//! [`super::lcrq_lifo::LohDeque`] (40 B per slot).
//!
//! This is the single-tier shape: one publication ring shared by
//! all thieves regardless of coherence distance. The in-process
//! per-tier equivalent is [`crate::sched::deque_tier`].

#![allow(clippy::missing_errors_doc)]

use std::fs::{File, OpenOptions};
use std::io;
use std::path::Path;
use std::sync::atomic::{AtomicI64, AtomicU64, Ordering, fence};

use memmap2::{MmapMut, MmapOptions};

use super::stager::StagingTable;

/// Magic byte sequence marking a valid KHPD file. ASCII "FKHP".
pub const KHPD_MAGIC: u64 = 0x464B_4850_0000_0001;

/// Cache-line size; one publication line per cache line.
pub const KHPD_LINE_SIZE: usize = 64;

/// Items per publication line. State (8 B) + 3 * 16 = 56 B; 8 B
/// trailing padding rounds the line to 64.
pub const LINE_ITEMS: usize = 3;

/// Bytes per inline args payload in one [`LineItem`].
pub const KHPD_ARGS_INLINE_BYTES: usize = 8;

/// `state` packed-bit-field layout: epoch in the top 32 bits,
/// `n_items` in the next 16, `claim` in the bottom 16.
const STATE_EMPTY: u64 = 0;
const CLAIM_BIT: u64 = 1;

/// Header sits at file offset 0; cache-line aligned. `head` and
/// `tail` each get their own cache line to prevent producer and
/// consumer counters from invalidating each other.
#[repr(C, align(64))]
pub struct KhpdHeader {
    /// Magic constant.
    pub magic: u64,
    /// Number of publication lines; always a power of two.
    pub capacity: u64,
    /// Pid of the owner process; informational. Cleared on
    /// `close_owner()`.
    pub owner_pid: AtomicU64,
    /// Epoch counter advanced on owner shutdown.
    pub epoch: AtomicU64,
    /// Padding to push `tail` to its own cache line.
    pub _pad_meta: [u8; 24],
    /// Producer counter. Owner `fetch_add(1)` per published line.
    pub tail: AtomicI64,
    /// Padding to push `head` to its own line.
    pub _pad_tail: [u8; 56],
    /// Consumer counter. Thieves CAS this to claim a line.
    pub head: AtomicI64,
    /// Padding to round the header to two whole cache lines after
    /// `head`.
    pub _pad_head: [u8; 56],
}

/// One item carried in a publication line. 16 bytes.
#[repr(C, align(8))]
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct LineItem {
    /// Pass-registry id.
    pub closure_id: u32,
    /// Latch arena offset.
    pub latch_offset: u32,
    /// Inline args (up to 8 bytes).
    pub args_inline: [u8; KHPD_ARGS_INLINE_BYTES],
}

impl LineItem {
    /// Build a line item from caller fields.
    pub fn new(closure_id: u32, latch_offset: u32, args: &[u8]) -> Result<Self, PushError> {
        if args.len() > KHPD_ARGS_INLINE_BYTES {
            return Err(PushError::PayloadTooLarge);
        }
        let mut item = Self {
            closure_id,
            latch_offset,
            args_inline: [0u8; KHPD_ARGS_INLINE_BYTES],
        };
        item.args_inline[..args.len()].copy_from_slice(args);
        Ok(item)
    }

    /// Live arg bytes.
    pub fn args(&self) -> &[u8] {
        // Without a separate `args_len` field, we treat the whole
        // 8-byte payload as the args. Callers that need a length
        // must encode it in the args themselves (the bench's adder
        // does exactly this: two u32s = 8 bytes; both halves are
        // meaningful).
        &self.args_inline
    }
}

/// One publication line: state + LINE_ITEMS items + padding.
#[repr(C, align(64))]
pub struct PublicationLine {
    /// `(epoch: u32) << 32 | (n_items: u16) << 16 | (claim: u16)`.
    /// `claim` = 0 (empty), 1 (READY for claim).
    pub state: AtomicU64,
    /// Inline items.
    pub items: [LineItem; LINE_ITEMS],
    /// Trailing padding to round to 64 bytes.
    pub _pad: [u8; 8],
}

/// Total file size for a KHPD with `capacity` publication lines.
pub const fn khpd_file_size(capacity: usize) -> usize {
    std::mem::size_of::<KhpdHeader>() + capacity * KHPD_LINE_SIZE
}

/// Outcome of [`KhpdDeque::publish`].
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum PushError {
    /// Ring at capacity; consumer hasn't caught up.
    Full,
    /// Items count exceeds [`LINE_ITEMS`].
    TooManyItems,
    /// Args payload exceeds [`KHPD_ARGS_INLINE_BYTES`].
    PayloadTooLarge,
}

/// Outcome of [`KhpdDeque::steal_line`].
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum Steal {
    /// Got a publication line; carries up to LINE_ITEMS items.
    Success(StealResult),
    /// Ring was empty (head >= tail).
    Empty,
    /// Lost the CAS race on `head` to a competing thief.
    Retry,
}

/// Result of a successful steal: the publication line's items.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct StealResult {
    /// How many of the `items` slots are filled.
    pub n_items: usize,
    /// The items (only `items[..n_items]` are valid).
    pub items: [LineItem; LINE_ITEMS],
}

/// MMF-backed KHPD deque. Single owner, arbitrarily many thieves.
pub struct KhpdDeque {
    _file: File,
    mmap: MmapMut,
    capacity: usize,
    capacity_mask: i64,
    /// Staging buffers, one per staging thread. Items accumulate in
    /// the caller's own buffer until it calls `publish()`, which
    /// flushes the caller's buffer into publication lines and leaves
    /// every other thread's alone.
    ///
    /// A buffer per thread rather than one behind a mutex, because
    /// nothing here was ever meant to be shared: "only the originator
    /// stages" is the contract, and a per-thread buffer makes it true
    /// by construction instead of leaving a lock to absorb a caller
    /// that breaks it. It is also the faster arm, measured on zen3 at
    /// 2.55 ns per push against 5.03 for the mutex it replaces.
    pending: StagingTable<LineItem>,
}

// SAFETY: All fields are Send. Mmap handle is Send+Sync per memmap2.
// Every line access goes through the per-line state-atomic protocol.
// `pending` is a StagingTable, whose buffers are each reached only by
// the one thread that owns their index, so owner-side accesses need no
// linearizing: there is nothing to linearize them against.
unsafe impl Send for KhpdDeque {}
// SAFETY: same justification as the Send impl directly above.
unsafe impl Sync for KhpdDeque {}

impl KhpdDeque {
    /// Create a fresh KHPD file. `capacity` rounds to the next
    /// power of two; min 2.
    pub fn create<P: AsRef<Path>>(path: P, capacity: usize) -> io::Result<Self> {
        let capacity = capacity.max(2).next_power_of_two();
        let size = khpd_file_size(capacity);

        let file = OpenOptions::new()
            .read(true)
            .write(true)
            .create(true)
            .truncate(true)
            .open(path.as_ref())?;
        file.set_len(size as u64)?;

        // SAFETY: `map_mut` is unsafe because the kernel cannot
        // prevent another process from truncating the file. This
        // call site upholds the soundness contract by writing only
        // through the KHPD per-line state-atomic protocol; file
        // size is fixed by `set_len` above and never shrunk for the
        // lifetime of any mapping.
        let mut mmap = unsafe { MmapOptions::new().len(size).map_mut(&file)? };

        let header_ptr = mmap.as_mut_ptr() as *mut KhpdHeader;
        // SAFETY: mmap is page-aligned (well above the 64-byte
        // alignment KhpdHeader requires); the map covers
        // `khpd_file_size(capacity)` bytes by construction.
        unsafe {
            (*header_ptr).magic = KHPD_MAGIC;
            (*header_ptr).capacity = capacity as u64;
            (*header_ptr).owner_pid = AtomicU64::new(std::process::id() as u64);
            (*header_ptr).epoch = AtomicU64::new(0);
            std::ptr::write_bytes((*header_ptr)._pad_meta.as_mut_ptr(), 0, 24);
            (*header_ptr).tail = AtomicI64::new(0);
            std::ptr::write_bytes((*header_ptr)._pad_tail.as_mut_ptr(), 0, 56);
            (*header_ptr).head = AtomicI64::new(0);
            std::ptr::write_bytes((*header_ptr)._pad_head.as_mut_ptr(), 0, 56);
        }

        // Zero the lines (state == 0 == STATE_EMPTY).
        let lines_start = std::mem::size_of::<KhpdHeader>();
        // SAFETY: lines_start..lines_start + capacity*KHPD_LINE_SIZE
        // is the unwritten tail of the map.
        unsafe {
            std::ptr::write_bytes(
                mmap.as_mut_ptr().add(lines_start),
                0,
                capacity * KHPD_LINE_SIZE,
            );
        }

        mmap.flush()?;

        Ok(Self {
            _file: file,
            mmap,
            capacity,
            capacity_mask: (capacity as i64) - 1,
            pending: StagingTable::new(),
        })
    }

    /// Open an existing KHPD file.
    pub fn open<P: AsRef<Path>>(path: P) -> io::Result<Self> {
        let file = OpenOptions::new()
            .read(true)
            .write(true)
            .open(path.as_ref())?;
        let size = file.metadata()?.len() as usize;
        if size < std::mem::size_of::<KhpdHeader>() {
            return Err(io::Error::new(
                io::ErrorKind::InvalidData,
                "khpd file too small",
            ));
        }
        // SAFETY: same protocol-only-access justification as `create`.
        let mmap = unsafe { MmapOptions::new().len(size).map_mut(&file)? };
        let header_ptr = mmap.as_ptr() as *const KhpdHeader;
        // SAFETY: map size verified to cover header.
        let (magic, capacity) =
            unsafe { ((*header_ptr).magic, (*header_ptr).capacity as usize) };
        if magic != KHPD_MAGIC {
            return Err(io::Error::new(
                io::ErrorKind::InvalidData,
                format!("khpd magic mismatch {magic:#x}"),
            ));
        }
        if !capacity.is_power_of_two() || capacity < 2 {
            return Err(io::Error::new(
                io::ErrorKind::InvalidData,
                format!("khpd capacity {capacity} not pow2 >= 2"),
            ));
        }
        if size < khpd_file_size(capacity) {
            return Err(io::Error::new(
                io::ErrorKind::InvalidData,
                format!(
                    "khpd file size {size} below expected {}",
                    khpd_file_size(capacity)
                ),
            ));
        }
        Ok(Self {
            _file: file,
            mmap,
            capacity,
            capacity_mask: (capacity as i64) - 1,
            pending: StagingTable::new(),
        })
    }

    /// Capacity in publication lines (always a power of two).
    pub fn capacity(&self) -> usize {
        self.capacity
    }

    /// Owner pid at create time, or 0 after `close_owner()`.
    pub fn owner_pid(&self) -> u64 {
        self.header().owner_pid.load(Ordering::Acquire)
    }

    /// Advance epoch + zero pid on shutdown.
    pub fn close_owner(&self) {
        self.header().owner_pid.store(0, Ordering::Release);
        self.header().epoch.fetch_add(1, Ordering::Release);
    }

    fn header(&self) -> &KhpdHeader {
        // SAFETY: header is at the start of the map; mmap is
        // page-aligned.
        unsafe { &*(self.mmap.as_ptr() as *const KhpdHeader) }
    }

    fn line_ptr(&self, idx: i64) -> *mut PublicationLine {
        let line_idx = (idx & self.capacity_mask) as usize;
        let off = std::mem::size_of::<KhpdHeader>() + line_idx * KHPD_LINE_SIZE;
        // SAFETY: `line_idx` < capacity; `off` is in-bounds + 64-byte aligned.
        unsafe { self.mmap.as_ptr().add(off) as *mut PublicationLine }
    }

    /// Snapshot `(head, tail, ring_size_lines, pending_items)`.
    ///
    /// The pending count totals every thread's staging buffer, so it
    /// answers what the deque is holding rather than what the caller
    /// has staged. It is a total taken while threads may be staging,
    /// not an instant; [`Self::stage`] answers the caller's own count,
    /// which is what a flush decision uses.
    pub fn snapshot_size(&self) -> (i64, i64, i64, usize) {
        let h = self.header();
        let head = h.head.load(Ordering::Acquire);
        let tail = h.tail.load(Ordering::Acquire);
        (head, tail, tail - head, self.pending.staged_total())
    }

    /// Owner-side stage. Adds one item to the calling thread's pending
    /// buffer. Returns that thread's running pending count, so the
    /// caller can decide to flush at LINE_ITEMS.
    ///
    /// Each staging thread accumulates and publishes its own items, so
    /// a count here is a local decision and never moves because some
    /// other thread staged.
    pub fn stage(&self, item: LineItem) -> Result<usize, PushError> {
        Ok(self.pending.with_mine(|buffer| {
            buffer.push(item);
            buffer.len()
        }))
    }

    /// Owner-side publish. Drains the pending buffer into one or
    /// more publication lines (`LINE_ITEMS` items per line). Reserves
    /// the whole batch with a single `tail.fetch_add(n_lines)` up front,
    /// then per-line: waits for `state == STATE_EMPTY`, fills items,
    /// and Release-stores the packed state. Returns the number of
    /// lines published.
    /// Publishes the calling thread's staged items and leaves every
    /// other thread's where they are. A thread stages and publishes
    /// its own batch, so items from two threads land in separate
    /// publication lines rather than sharing one. The ring is claimed
    /// per batch through a compare-exchange on `tail` against the
    /// `head` the full check read, so concurrent publishers take
    /// disjoint lines and never together reserve past capacity.
    pub fn publish(&self) -> Result<usize, PushError> {
        self.pending.with_mine(|buffer| self.publish_staged(buffer))
    }

    /// Drain `staged` into publication lines. Separated from
    /// [`Self::publish`] so the borrow of the staging buffer is one
    /// argument rather than a closure wrapped around the whole body.
    fn publish_staged(&self, p: &mut Vec<LineItem>) -> Result<usize, PushError> {
        if p.is_empty() {
            return Ok(0);
        }
        // How many lines do we need?
        let total = p.len();
        let n_lines = total.div_ceil(LINE_ITEMS);
        // Reserve `n_lines` ring slots, or back off without moving
        // tail when the ring would overflow. The check and the claim
        // are one compare-exchange on tail, so two publishers that read
        // the same head cannot both pass the check and together reserve
        // past capacity. A reservation past capacity waits below on a
        // slot whose line the consumer at head has not reached, and
        // when head is a line another publisher reserved and is itself
        // waiting to fill, neither side moves.
        let h = self.header();
        let mut tail_snap = h.tail.load(Ordering::Relaxed);
        let base = loop {
            let head_snap = h.head.load(Ordering::Acquire);
            if (tail_snap - head_snap + n_lines as i64) > self.capacity as i64 {
                return Err(PushError::Full);
            }
            match h.tail.compare_exchange_weak(
                tail_snap,
                tail_snap + n_lines as i64,
                Ordering::AcqRel,
                Ordering::Relaxed,
            ) {
                Ok(claimed) => break claimed,
                Err(current) => tail_snap = current,
            }
        };

        let mut item_iter = p.drain(..);
        for line_i in 0..n_lines {
            let idx = base + line_i as i64;
            let line = self.line_ptr(idx);
            // Spin-wait for the slot to be reusable. The line's
            // state has top-32-bit epoch == idx (initially 0; the
            // consumer's release advances it to `idx + 1` for
            // round 2). Producer's expected pre-publish state =
            // (idx_round << 32) where idx_round = idx / capacity.
            // For the first round at this physical slot, state
            // should be 0 (initial). For subsequent rounds, state
            // should be `(idx - capacity) << 32 | RELEASED`.
            //
            // Simpler invariant: consumer's release stores
            // `(idx + 1) << 32` (= empty for the next round). So
            // producer at `idx` spins until state's top 32 bits ==
            // `idx_top` where `idx_top = (idx / capacity) << 32` -
            // ah this gets tangled. The cleanest version:
            // consumer releases by storing `0` (empty). Producer
            // spins until state == 0.
            //
            // SAFETY: line is in-bounds + aligned.
            unsafe {
                loop {
                    let st = (*line).state.load(Ordering::Acquire);
                    if st == STATE_EMPTY {
                        break;
                    }
                    std::hint::spin_loop();
                }

                // Fill items.
                let mut n_filled = 0usize;
                for i in 0..LINE_ITEMS {
                    match item_iter.next() {
                        Some(item) => {
                            (*line).items[i] = item;
                            n_filled += 1;
                        }
                        None => break,
                    }
                }
                // Pack state: (epoch:32 from base+line_i) | n_filled
                // | CLAIM_BIT marker (=1 means READY).
                let new_state =
                    ((idx as u64) << 32) | ((n_filled as u64) << 16) | CLAIM_BIT;
                (*line).state.store(new_state, Ordering::Release);
            }
        }
        Ok(n_lines)
    }

    /// Thief-side. Claim one publication line.
    pub fn steal_line(&self) -> Steal {
        let h = self.header();
        let head = h.head.load(Ordering::Acquire);
        fence(Ordering::SeqCst);
        let tail = h.tail.load(Ordering::Acquire);
        if head >= tail {
            return Steal::Empty;
        }
        let line = self.line_ptr(head);
        // SAFETY: line in-bounds + aligned.
        let state = unsafe { (*line).state.load(Ordering::Acquire) };
        // Validate: state's epoch matches our head and CLAIM_BIT
        // is set.
        let expected_epoch = (head as u64) << 32;
        if state & 0xFFFF_FFFF_0000_0000 != expected_epoch {
            // Publisher hasn't written this line for our round yet.
            return Steal::Retry;
        }
        if state & CLAIM_BIT == 0 {
            // Line empty (no items for this round). Skip.
            return Steal::Retry;
        }
        // CAS head to claim.
        let won = h
            .head
            .compare_exchange(head, head + 1, Ordering::SeqCst, Ordering::Relaxed)
            .is_ok();
        if !won {
            return Steal::Retry;
        }
        // We own the line; read items + release state to `EMPTY` for
        // the next round at this physical slot.
        // SAFETY: line is in-bounds + aligned; CAS established
        // exclusive read access.
        let result = unsafe {
            let n_items = ((state >> 16) & 0xFFFF) as usize;
            let n_items = n_items.min(LINE_ITEMS);
            StealResult {
                n_items,
                items: (*line).items,
            }
        };
        // Release the line: store STATE_EMPTY so the next round's
        // producer (at idx = head + capacity) sees the slot ready.
        // SAFETY: still our line; the Release synchronizes with
        // the next producer's Acquire-spin in `publish`.
        unsafe {
            (*line).state.store(STATE_EMPTY, Ordering::Release);
        }
        Steal::Success(result)
    }

    /// Force any dirty pages to disk.
    pub fn flush_to_disk(&self) -> io::Result<()> {
        self.mmap.flush()
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    use std::sync::Arc;
    use std::sync::atomic::{AtomicUsize, Ordering as O};
    use std::thread;

    fn temp_path(name: &str) -> std::path::PathBuf {
        let mut p = std::env::temp_dir();
        let pid = std::process::id();
        let nonce = std::time::SystemTime::now()
            .duration_since(std::time::UNIX_EPOCH)
            .map(|d| d.as_nanos())
            .unwrap_or(0);
        p.push(format!("flynnel_khpd_{pid}_{nonce}_{name}.bin"));
        p
    }

    fn item(id: u32) -> LineItem {
        LineItem::new(id, u32::MAX, &id.to_le_bytes()).expect("item")
    }

    #[test]
    fn create_open_round_trips_header() {
        let path = temp_path("create_open");
        let _d = KhpdDeque::create(&path, 8).expect("create");
        let o = KhpdDeque::open(&path).expect("open");
        assert_eq!(o.capacity(), 8);
        assert_eq!(o.owner_pid(), std::process::id() as u64);
        std::fs::remove_file(&path).ok();
    }

    #[test]
    fn open_rejects_bad_magic() {
        let path = temp_path("badmagic");
        std::fs::write(&path, vec![0u8; 8192]).expect("seed");
        assert!(KhpdDeque::open(&path).is_err());
        std::fs::remove_file(&path).ok();
    }

    #[test]
    fn stage_then_publish_writes_one_line() {
        let path = temp_path("stage_publish");
        let d = KhpdDeque::create(&path, 4).expect("create");
        d.stage(item(1)).expect("stage 1");
        d.stage(item(2)).expect("stage 2");
        let lines = d.publish().expect("publish");
        assert_eq!(lines, 1);
        let (_, tail, sz, pending) = d.snapshot_size();
        assert_eq!(tail, 1);
        assert_eq!(sz, 1);
        assert_eq!(pending, 0);
        std::fs::remove_file(&path).ok();
    }

    #[test]
    fn publish_spans_multiple_lines() {
        let path = temp_path("multi_line");
        let d = KhpdDeque::create(&path, 4).expect("create");
        // 7 items: 3 + 3 + 1 = 3 lines.
        for i in 1..=7u32 {
            d.stage(item(i)).expect("stage");
        }
        let lines = d.publish().expect("publish");
        assert_eq!(lines, 3);
        let (_, tail, sz, _) = d.snapshot_size();
        assert_eq!(tail, 3);
        assert_eq!(sz, 3);
        std::fs::remove_file(&path).ok();
    }

    #[test]
    fn steal_returns_items_in_publication_order() {
        let path = temp_path("fifo");
        let d = KhpdDeque::create(&path, 4).expect("create");
        for i in 1..=5u32 {
            d.stage(item(i)).expect("stage");
        }
        d.publish().expect("publish");
        // Steal returns line 0 first (items 1,2,3), then line 1 (4,5).
        loop {
            match d.steal_line() {
                Steal::Success(r) => {
                    assert_eq!(r.n_items, 3);
                    assert_eq!(r.items[0].closure_id, 1);
                    assert_eq!(r.items[1].closure_id, 2);
                    assert_eq!(r.items[2].closure_id, 3);
                    break;
                }
                Steal::Empty | Steal::Retry => std::thread::yield_now(),
            }
        }
        loop {
            match d.steal_line() {
                Steal::Success(r) => {
                    assert_eq!(r.n_items, 2);
                    assert_eq!(r.items[0].closure_id, 4);
                    assert_eq!(r.items[1].closure_id, 5);
                    break;
                }
                Steal::Empty | Steal::Retry => std::thread::yield_now(),
            }
        }
        // Now empty.
        loop {
            match d.steal_line() {
                Steal::Empty => break,
                Steal::Retry => continue,
                Steal::Success(_) => panic!("unexpected success after drain"),
            }
        }
        std::fs::remove_file(&path).ok();
    }

    #[test]
    fn oversize_args_rejected() {
        let big = vec![0u8; KHPD_ARGS_INLINE_BYTES + 1];
        let err = LineItem::new(0, 0, &big).expect_err("oversize");
        assert_eq!(err, PushError::PayloadTooLarge);
    }

    #[test]
    fn ring_full_at_capacity_returns_full() {
        let path = temp_path("full");
        let d = KhpdDeque::create(&path, 2).expect("create");
        // Fill the ring (2 publication lines * 3 items = 6 items).
        for i in 1..=6u32 {
            d.stage(item(i)).expect("stage");
        }
        d.publish().expect("publish 2 lines");
        // Now stage more + publish; ring is full.
        d.stage(item(7)).expect("stage 7");
        let err = d.publish().expect_err("publish past capacity");
        assert_eq!(err, PushError::Full);
        std::fs::remove_file(&path).ok();
    }

    #[test]
    fn close_owner_zeros_pid_and_advances_epoch() {
        let path = temp_path("close");
        let d = KhpdDeque::create(&path, 2).expect("create");
        let before = d.header().epoch.load(O::Acquire);
        d.close_owner();
        assert_eq!(d.owner_pid(), 0);
        assert_eq!(d.header().epoch.load(O::Acquire), before + 1);
        std::fs::remove_file(&path).ok();
    }

    #[test]
    fn concurrent_thieves_no_double_take() {
        // Stress: 5000 items via repeated stage+publish; 2 thieves
        // race to drain. Every item must be consumed exactly once.
        let path = temp_path("stress");
        let d = Arc::new(KhpdDeque::create(&path, 64).expect("create"));
        let n = 5_000usize;
        let consumed = Arc::new(AtomicUsize::new(0));
        let sum = Arc::new(AtomicUsize::new(0));

        let mut thieves = Vec::new();
        for _ in 0..2 {
            let d = Arc::clone(&d);
            let consumed = Arc::clone(&consumed);
            let sum = Arc::clone(&sum);
            thieves.push(thread::spawn(move || {
                while consumed.load(O::Relaxed) < n {
                    match d.steal_line() {
                        Steal::Success(r) => {
                            for i in 0..r.n_items {
                                consumed.fetch_add(1, O::Relaxed);
                                sum.fetch_add(r.items[i].closure_id as usize, O::Relaxed);
                            }
                        }
                        Steal::Empty | Steal::Retry => std::thread::yield_now(),
                    }
                }
            }));
        }

        // Publisher: stage LINE_ITEMS, publish, repeat until n items
        // total.
        let mut pushed = 0usize;
        while pushed < n {
            let want = LINE_ITEMS.min(n - pushed);
            for _ in 0..want {
                d.stage(item(pushed as u32)).expect("stage");
                pushed += 1;
            }
            loop {
                match d.publish() {
                    Ok(_) => break,
                    Err(PushError::Full) => {
                        std::thread::yield_now();
                    }
                    Err(other) => panic!("publish: {other:?}"),
                }
            }
        }

        for t in thieves {
            t.join().expect("thief");
        }
        let expected: usize = (0..n).sum();
        assert_eq!(
            sum.load(O::Relaxed),
            expected,
            "stress sum mismatch (expected every item consumed exactly once)"
        );
        std::fs::remove_file(&path).ok();
    }
}