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
//! `DispatchBackend` impl over [`super::urd::UrdDeque`] + MMF
//! latch arena. Push-based cross-process dispatch with one
//! per-thief mailbox cache line; the owner picks the target by
//! round-robin (or by an explicit thief index).

#![allow(clippy::missing_errors_doc)]

use std::path::PathBuf;
use std::sync::atomic::{AtomicU64, Ordering};

use super::chase_lev_backend::DispatchHandle;
use super::khpd::{KHPD_ARGS_INLINE_BYTES, LineItem};
use super::latch_mmf::{ERR, MmfLatchArena, SET, UNSET, spin_phase};
use super::pass_registry::{self, Pass};
use super::stager::StagingTable;
use super::urd::{Drain, MAILBOX_ITEMS, UrdDeque};

use crate::backend::{Backend, BackendCapabilities, BackendError, DispatchBackend, KernelHandle};

/// `DispatchBackend` impl over a URD deque + MMF latch arena.
pub struct SharedMemoryUrdBackend {
    deque: UrdDeque,
    latches: MmfLatchArena,
    backend_id: u32,
    deque_path: PathBuf,
    latches_path: PathBuf,
    caps: BackendCapabilities,
    dispatched: AtomicU64,
    /// Staging buffers, one per staging thread. Items accumulate in
    /// the caller's own buffer until `flush()` (or auto-flush at
    /// MAILBOX_ITEMS) publishes one mailbox-worth via
    /// [`UrdDeque::publish_round_robin`].
    ///
    /// A buffer per thread rather than one behind a mutex: staging is
    /// owner-side, so there is nothing to exclude, and it is the
    /// faster arm besides. See [`super::stager`] for the measurement.
    pending: StagingTable<LineItem>,
}

impl SharedMemoryUrdBackend {
    /// Create the URD deque + latch arena.
    pub fn create(
        backend_id: u32,
        deque_path: impl Into<PathBuf>,
        latches_path: impl Into<PathBuf>,
        n_mailboxes: usize,
        latch_capacity: usize,
    ) -> Result<Self, BackendError> {
        let deque_path = deque_path.into();
        let latches_path = latches_path.into();
        let deque = UrdDeque::create(&deque_path, n_mailboxes)
            .map_err(|e| BackendError::Memory(format!("create URD deque: {e}")))?;
        let latches = MmfLatchArena::create(&latches_path, latch_capacity)
            .map_err(|e| BackendError::Memory(format!("create latch arena: {e}")))?;
        let caps = Self::caps_for(deque.n_mailboxes());
        Ok(Self {
            deque,
            latches,
            backend_id,
            deque_path,
            latches_path,
            caps,
            dispatched: AtomicU64::new(0),
            pending: StagingTable::new(),
        })
    }

    /// Attach to an existing URD deque + latch arena.
    pub fn open(
        backend_id: u32,
        deque_path: impl Into<PathBuf>,
        latches_path: impl Into<PathBuf>,
    ) -> Result<Self, BackendError> {
        let deque_path = deque_path.into();
        let latches_path = latches_path.into();
        let deque = UrdDeque::open(&deque_path)
            .map_err(|e| BackendError::Memory(format!("open URD deque: {e}")))?;
        let latches = MmfLatchArena::open(&latches_path)
            .map_err(|e| BackendError::Memory(format!("open latch arena: {e}")))?;
        let caps = Self::caps_for(deque.n_mailboxes());
        Ok(Self {
            deque,
            latches,
            backend_id,
            deque_path,
            latches_path,
            caps,
            dispatched: AtomicU64::new(0),
            pending: StagingTable::new(),
        })
    }

    fn caps_for(n_mailboxes: usize) -> BackendCapabilities {
        BackendCapabilities {
            simt_width: 1,
            max_threads_in_flight: (n_mailboxes * MAILBOX_ITEMS).max(1) as u32,
            launch_latency_ns: 150,
            h2d_bw_bytes_per_sec: 0,
        }
    }

    /// Path of the URD deque file.
    pub fn deque_path(&self) -> &std::path::Path {
        &self.deque_path
    }

    /// Path of the latch arena file.
    pub fn latches_path(&self) -> &std::path::Path {
        &self.latches_path
    }

    /// Total items dispatched.
    pub fn dispatched(&self) -> u64 {
        self.dispatched.load(Ordering::Relaxed)
    }

    /// Owner-side: stage one item + auto-flush at MAILBOX_ITEMS.
    /// Returns a [`DispatchHandle`] the caller waits on.
    pub fn dispatch_marshal(
        &self,
        closure_id: u32,
        args: &[u8],
    ) -> Result<DispatchHandle, BackendError> {
        if args.len() > KHPD_ARGS_INLINE_BYTES {
            return Err(BackendError::Launch(format!(
                "URD args length {} exceeds slot capacity {}",
                args.len(),
                KHPD_ARGS_INLINE_BYTES
            )));
        }
        let latch_offset = self.latches.alloc();
        let item = LineItem::new(closure_id, latch_offset, args)
            .map_err(|e| BackendError::Launch(format!("URD build item: {e:?}")))?;
        // Published straight out of the caller's own buffer. The
        // buffer belongs to this thread, so holding it across the
        // publish blocks nobody, and clearing it afterward keeps its
        // capacity where handing the vector away would make the next
        // batch allocate.
        //
        // Cleared whether or not the publish succeeded, which is what
        // the drain-then-publish this replaces did: a caller retrying
        // a failed dispatch must not find the items still staged and
        // send them a second time.
        self.pending.with_mine(|buffer| {
            buffer.push(item);
            if buffer.len() < MAILBOX_ITEMS {
                return Ok(());
            }
            let outcome = self.deque.publish_round_robin(buffer);
            buffer.clear();
            outcome
                .map(|_| ())
                .map_err(|e| BackendError::Launch(format!("URD publish: {e:?}")))
        })?;
        self.dispatched.fetch_add(1, Ordering::Relaxed);
        Ok(DispatchHandle { latch_offset })
    }

    /// Owner-side: stage N items, then publish in round-robin
    /// batches of MAILBOX_ITEMS items each. This is the
    /// producer-fast entry point.
    pub fn dispatch_marshal_batch(
        &self,
        items: &[(u32, &[u8])],
    ) -> Result<Vec<DispatchHandle>, BackendError> {
        let mut handles = Vec::with_capacity(items.len());
        // Build all the LineItems up-front so we don't lock /
        // unlock per item.
        let mut line_items = Vec::with_capacity(items.len());
        for (closure_id, args) in items {
            if args.len() > KHPD_ARGS_INLINE_BYTES {
                return Err(BackendError::Launch(format!(
                    "URD args length {} exceeds slot capacity {}",
                    args.len(),
                    KHPD_ARGS_INLINE_BYTES
                )));
            }
            let latch_offset = self.latches.alloc();
            let item = LineItem::new(*closure_id, latch_offset, args)
                .map_err(|e| BackendError::Launch(format!("URD build item: {e:?}")))?;
            line_items.push(item);
            handles.push(DispatchHandle { latch_offset });
        }
        // Publish in MAILBOX_ITEMS-sized chunks via round-robin.
        for chunk in line_items.chunks(MAILBOX_ITEMS) {
            self.deque
                .publish_round_robin(chunk)
                .map_err(|e| BackendError::Launch(format!("URD publish: {e:?}")))?;
        }
        self.dispatched
            .fetch_add(items.len() as u64, Ordering::Relaxed);
        Ok(handles)
    }

    /// Owner-side: explicit flush of the calling thread's staged
    /// items. Each staging thread accumulates and flushes its own, so
    /// this leaves every other thread's buffer where it is.
    pub fn flush(&self) -> Result<usize, BackendError> {
        self.pending.with_mine(|buffer| {
            if buffer.is_empty() {
                return Ok(0);
            }
            let staged = buffer.len();
            // Published in place and cleared afterward, for the
            // reasons given on the auto-flush in dispatch_marshal: the
            // buffer is this thread's, so nothing waits on it, and
            // clearing keeps the capacity the next batch would
            // otherwise have to allocate.
            let mut outcome = Ok(());
            for chunk in buffer.chunks(MAILBOX_ITEMS) {
                if let Err(e) = self.deque.publish_round_robin(chunk) {
                    outcome = Err(BackendError::Launch(format!("URD publish: {e:?}")));
                    break;
                }
            }
            buffer.clear();
            outcome.map(|()| staged)
        })
    }

    /// Peer-side: drain one mailbox (`mailbox_idx`) and execute
    /// every item via the local pass_registry.
    pub fn drain_mailbox(&self, mailbox_idx: usize) -> Result<Option<usize>, BackendError> {
        let result = match self.deque.drain_mailbox(mailbox_idx) {
            Drain::Success(r) => r,
            Drain::Empty => return Ok(None),
        };
        for i in 0..result.n_items {
            let item = result.items[i];
            let pass = Pass {
                closure_id: item.closure_id,
                args: item.args_inline.to_vec(),
            };
            match pass_registry::execute(&pass) {
                Ok(reply) => self
                    .latches
                    .publish(item.latch_offset, &reply)
                    .map_err(|e| {
                        BackendError::Launch(format!("URD latch publish: {e:?}"))
                    })?,
                Err(err) => {
                    let msg = err.to_string();
                    let bytes = msg.as_bytes();
                    let n = bytes.len().min(64);
                    self.latches
                        .publish_err(item.latch_offset, &bytes[..n])
                        .map_err(|e| {
                            BackendError::Launch(format!("URD latch publish_err: {e:?}"))
                        })?;
                }
            }
        }
        Ok(Some(result.n_items))
    }

    /// Originator-side non-blocking poll on a single dispatch handle.
    pub fn poll_handle(
        &self,
        handle: DispatchHandle,
    ) -> Result<Option<Result<Vec<u8>, String>>, BackendError> {
        let is_set = self
            .latches
            .is_set(handle.latch_offset)
            .map_err(|e| BackendError::Launch(format!("latch poll: {e:?}")))?;
        if !is_set {
            return Ok(None);
        }
        let mut buf = Vec::new();
        let state = self
            .latches
            .read_result(handle.latch_offset, &mut buf)
            .map_err(|e| BackendError::Launch(format!("latch read: {e:?}")))?;
        self.latches
            .reset(handle.latch_offset)
            .map_err(|e| BackendError::Launch(format!("latch reset: {e:?}")))?;
        match state {
            SET => Ok(Some(Ok(buf))),
            ERR => Ok(Some(Err(String::from_utf8_lossy(&buf).into_owned()))),
            UNSET => Ok(None),
            other => Err(BackendError::Launch(format!(
                "latch read returned unexpected state: {other}"
            ))),
        }
    }

    /// Originator-side blocking wait: [`spin_phase`] over `iter_budget`
    /// polls, then yields until the result is set.
    pub fn wait_handle(
        &self,
        handle: DispatchHandle,
        iter_budget: u32,
    ) -> Result<Result<Vec<u8>, String>, BackendError> {
        let spun = spin_phase(
            &self.latches,
            handle.latch_offset,
            iter_budget,
            crate::sched::levers::backend_spin_monitor(),
            |e| BackendError::Launch(format!("latch line: {e:?}")),
            || self.poll_handle(handle),
        )?;
        if let Some(r) = spun {
            return Ok(r);
        }
        loop {
            if let Some(r) = self.poll_handle(handle)? {
                return Ok(r);
            }
            std::thread::yield_now();
        }
    }
}

impl DispatchBackend for SharedMemoryUrdBackend {
    fn id(&self) -> Backend {
        Backend::SharedMemoryWorker {
            backend_id: self.backend_id,
        }
    }

    fn capabilities(&self) -> BackendCapabilities {
        self.caps
    }

    fn dispatch_parallel_for(&self, _count: u32, _work: &(dyn Fn(u32) + Send + Sync)) {}

    fn dispatch_one(&self, _work: Box<dyn FnOnce() + Send>) {
        panic!(
            "SharedMemoryUrdBackend does not support dispatch_one; \
             use dispatch_marshal / dispatch_marshal_batch"
        );
    }

    fn register_kernel(&self, name: &str, _source: &[u8]) -> Result<KernelHandle, BackendError> {
        let id = pass_registry::hash_name(name);
        Ok(KernelHandle(id as u64))
    }

    fn dispatch_kernel(
        &self,
        _handle: KernelHandle,
        _count: u32,
        _args: &[crate::backend::KernelArg<'_>],
    ) -> Result<(), BackendError> {
        // Same rationale as KHPD: 8-byte inline args don't fit the
        // generic KernelArg wire envelope. Callers route through
        // dispatch_marshal / dispatch_marshal_batch with raw 8-byte
        // payloads.
        Err(BackendError::NotSupported)
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::backend::shared_mem::pass_registry::{hash_name, register, unregister};

    fn temp_paths(label: &str) -> (PathBuf, PathBuf) {
        let mut d = std::env::temp_dir();
        let mut l = 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);
        d.push(format!("flynnel_urd_be_d_{pid}_{nonce}_{label}.bin"));
        l.push(format!("flynnel_urd_be_l_{pid}_{nonce}_{label}.bin"));
        (d, l)
    }

    #[test]
    fn dispatch_marshal_batch_round_trips_across_mailboxes() {
        let (d, l) = temp_paths("batch");
        // n_mailboxes=4 so 6 items (2 batches of MAILBOX_ITEMS=3
        // each) land in DIFFERENT mailboxes via round-robin. This
        // eliminates the `publish_to` spin-wait that would deadlock
        // under parallel-test load when only a single mailbox is
        // available and no concurrent drain thread is running. The
        // test drains all 4 mailboxes sequentially after dispatch.
        let be = SharedMemoryUrdBackend::create(0, &d, &l, 4, 64).expect("create");
        let id = hash_name("flynnel.test.urd.adder");
        register(id, |args| {
            let a = u32::from_le_bytes(args[0..4].try_into().unwrap());
            let b = u32::from_le_bytes(args[4..8].try_into().unwrap());
            Ok((a + b).to_le_bytes().to_vec())
        });

        let mut payloads = Vec::with_capacity(6);
        for i in 0..6u32 {
            let mut p = [0u8; 8];
            p[..4].copy_from_slice(&i.to_le_bytes());
            p[4..].copy_from_slice(&(i * 2).to_le_bytes());
            payloads.push(p);
        }
        let items: Vec<(u32, &[u8])> =
            payloads.iter().map(|p| (id, p.as_slice())).collect();
        // With 4 mailboxes and 2 batches, round-robin lands batch 0
        // in mailbox 0 and batch 1 in mailbox 1. Neither publish
        // call spin-waits because both target mailboxes are EMPTY
        // (fresh init).
        let handles = be.dispatch_marshal_batch(&items).expect("dispatch");
        assert_eq!(handles.len(), 6);

        // Drain every mailbox (sequential; no concurrency required).
        let mut total_drained = 0usize;
        for mb in 0..4 {
            if let Some(n) = be.drain_mailbox(mb).expect("drain") {
                total_drained += n;
            }
        }
        assert_eq!(total_drained, 6, "all 6 items must drain across mailboxes 0..3");

        // Every handle's latch was published by drain_mailbox; wait
        // resolves immediately. The handle->mailbox mapping is
        // round-robin-positional, so handles[0..3] land in
        // mailbox 0's published batch and handles[3..6] in mailbox 1.
        for (i, h) in handles.iter().enumerate() {
            let r = be.wait_handle(*h, 1024).expect("wait").expect("ok");
            let v = u32::from_le_bytes(r[..4].try_into().unwrap());
            assert_eq!(v, i as u32 + i as u32 * 2);
        }

        unregister(id);
        std::fs::remove_file(&d).ok();
        std::fs::remove_file(&l).ok();
    }

    #[test]
    fn dispatch_one_panics() {
        let (d, l) = temp_paths("panic");
        let be = SharedMemoryUrdBackend::create(0, &d, &l, 1, 8).expect("create");
        let r = std::panic::catch_unwind(std::panic::AssertUnwindSafe(|| {
            be.dispatch_one(Box::new(|| ()));
        }));
        assert!(r.is_err());
        std::fs::remove_file(&d).ok();
        std::fs::remove_file(&l).ok();
    }
}