vj_sim/sched/
order.rs

1//! SCHED::ORDER — canonical ordering & intra-region commit infrastructure
2//! (scheduler.md §6, ARCHITECTURE §4 item 3; ledger SC-010, SC-012, SC-013,
3//! SC-014, DT-005, DT-010).
4//!
5//! This module is the one place that turns a ready-set of [`PendingActivation`]s
6//! into the canonical, thread-count-independent dispatch order (DT-005's
7//! precondition for `DeterminismController::partition`), and the one place that
8//! resolves same-cell write hazards within a delta cycle by canonical-key order
9//! rather than by submission/arrival order (SC-010, SC-012 — the generalized
10//! NANDi per-bank write-queue fix: buffer, never apply-on-arrival, commit in
11//! canonical order).
12
13use crate::determinism::CanonicalEventKey;
14use crate::sched::{PendingActivation, ProcessId, SchedTime};
15use crate::state::StateCellId;
16
17/// The 4 fields of [`CanonicalEventKey`] a ready-set activation determines on
18/// its own. `local_send_seq` is assigned later, at effect-emission time (per
19/// the existing determinism test's own convention), so it is not part of
20/// ready-set ordering and is not returned here.
21pub fn canonical_key_of(a: &PendingActivation) -> (SchedTime, u32, u32, ProcessId) {
22    (
23        a.logical_order.0,
24        a.logical_order.1 as u32,
25        a.reconv_iter,
26        a.proc,
27    )
28}
29
30/// Sorts `ready` in place into the canonical, thread-count-independent
31/// dispatch order: `(SimTime, Region, reconv_iter, registration_order)`
32/// (DT-005 — this must run before any `DeterminismController::partition`
33/// call). `logical_order.2` is the registration-order tiebreak
34/// (`PendingActivation::logical_order: (SchedTime, Region, u64)`).
35pub fn sort_ready_set(ready: &mut [PendingActivation]) {
36    ready.sort_by_key(|a| {
37        (
38            a.logical_order.0,
39            a.logical_order.1 as u32,
40            a.reconv_iter,
41            a.logical_order.2,
42        )
43    });
44}
45
46/// Buffers writes to state cells and resolves same-cell write hazards within
47/// one delta cycle by canonical-key order, never by push/thread/arrival order
48/// (SC-010, SC-012). Generic over `T` so Task 7 (NBA commit) reuses this
49/// instead of hand-rolling its own last-write-wins resolver.
50///
51/// **Not** reused by `commit_blocking_write`: a blocking write commits
52/// synchronously, one call, one cell, inside one `resume()`; two processes'
53/// blocking writes to the same cell in the same Active pass are two separate,
54/// sequential `commit_blocking_write` calls already made in canonical
55/// dispatch order, so the last call to physically run already *is* the
56/// last-write-wins outcome — there is no multi-entry buffer to resolve.
57pub struct WriteBuffer<T> {
58    entries: Vec<(CanonicalEventKey, StateCellId, T)>,
59}
60
61impl<T> Default for WriteBuffer<T> {
62    fn default() -> Self {
63        Self {
64            entries: Vec::new(),
65        }
66    }
67}
68
69impl<T> WriteBuffer<T> {
70    pub fn new() -> Self {
71        Self::default()
72    }
73
74    pub fn push(&mut self, key: CanonicalEventKey, cell: StateCellId, value: T) {
75        self.entries.push((key, cell, value));
76    }
77
78    /// Groups buffered writes by [`StateCellId`] and keeps, for each cell,
79    /// the entry with the maximum [`CanonicalEventKey`] — comparing by
80    /// canonical key, never by push/`Vec` insertion order. Output order is
81    /// by `StateCellId` (stable, deterministic — not caller-order-dependent).
82    pub fn resolve_last_write_wins(self) -> Vec<(StateCellId, T)> {
83        let mut by_cell: std::collections::BTreeMap<StateCellId, (CanonicalEventKey, T)> =
84            std::collections::BTreeMap::new();
85        for (key, cell, value) in self.entries {
86            match by_cell.get(&cell) {
87                Some((existing_key, _)) if *existing_key >= key => {
88                    // A later-or-equal-ranked write is already buffered for
89                    // this cell; this entry loses regardless of push order.
90                }
91                _ => {
92                    by_cell.insert(cell, (key, value));
93                }
94            }
95        }
96        by_cell
97            .into_iter()
98            .map(|(cell, (_, value))| (cell, value))
99            .collect()
100    }
101}
102
103#[cfg(test)]
104mod tests {
105    use super::*;
106    use crate::sched::ResumeArg;
107    use vj_abi::Region;
108
109    fn activation(
110        id: u64,
111        proc: ProcessId,
112        ticks: u64,
113        region: Region,
114        reconv_iter: u32,
115        registration_order: u64,
116    ) -> PendingActivation {
117        PendingActivation {
118            id,
119            proc,
120            arg: ResumeArg::Start,
121            reconv_iter,
122            logical_order: (SchedTime { ticks }, region, registration_order),
123        }
124    }
125
126    fn key(
127        ticks: u64,
128        region: Region,
129        reconv_iter: u32,
130        proc: ProcessId,
131        seq: u64,
132    ) -> CanonicalEventKey {
133        CanonicalEventKey {
134            vtime: SchedTime { ticks },
135            region_ordinal: region as u32,
136            reconv_iter,
137            canonical_process_id: proc,
138            local_send_seq: seq,
139        }
140    }
141
142    #[test]
143    fn sort_ready_set_is_insertion_order_independent() {
144        let a = activation(1, 10, 5, Region::Active, 0, 0);
145        let b = activation(2, 11, 5, Region::Active, 0, 1);
146        let c = activation(3, 12, 5, Region::Active, 0, 2);
147        let d = activation(4, 13, 5, Region::Active, 0, 3);
148
149        let mut order1 = vec![c, a, d, b];
150        let mut order2 = vec![b, d, a, c];
151
152        sort_ready_set(&mut order1);
153        sort_ready_set(&mut order2);
154
155        let procs1: Vec<ProcessId> = order1.iter().map(|x| x.proc).collect();
156        let procs2: Vec<ProcessId> = order2.iter().map(|x| x.proc).collect();
157        assert_eq!(procs1, procs2);
158        assert_eq!(procs1, vec![10, 11, 12, 13]);
159    }
160
161    #[test]
162    fn sort_ready_set_orders_by_time_then_region_then_reconv_iter_then_registration() {
163        // Each activation differs from its neighbor in exactly the next
164        // tiebreak field, so the expected order below is exercised strictly:
165        // time first, then region, then reconv_iter, then registration_order.
166        let earliest_time = activation(1, 100, 1, Region::Active, 0, 5); // time=1 wins outright
167        let later_time_early_region = activation(2, 101, 2, Region::Active, 0, 9);
168        let later_time_later_region = activation(3, 102, 2, Region::Nba, 0, 0);
169        let same_tr_early_reconv = activation(4, 103, 2, Region::Nba, 1, 9);
170        let same_tr_late_reconv_early_reg = activation(5, 104, 2, Region::Nba, 2, 0);
171        let same_tr_late_reconv_late_reg = activation(6, 105, 2, Region::Nba, 2, 1);
172
173        let mut ready = vec![
174            same_tr_late_reconv_late_reg,
175            same_tr_early_reconv,
176            later_time_later_region,
177            earliest_time,
178            same_tr_late_reconv_early_reg,
179            later_time_early_region,
180        ];
181
182        sort_ready_set(&mut ready);
183
184        let procs: Vec<ProcessId> = ready.iter().map(|x| x.proc).collect();
185        assert_eq!(procs, vec![100, 101, 102, 103, 104, 105]);
186    }
187
188    #[test]
189    fn write_buffer_last_write_wins_is_key_order_not_push_order() {
190        let cell = StateCellId(7);
191        let k0 = key(1, Region::Active, 0, 0, 0);
192        let k1 = key(2, Region::Active, 0, 0, 0);
193        let k2 = key(3, Region::Active, 0, 0, 0);
194        assert!(k0 < k1);
195        assert!(k1 < k2);
196
197        let mut buf: WriteBuffer<u32> = WriteBuffer::new();
198        // Push order deliberately NOT key order: k2, k0, k1.
199        buf.push(k2, cell, 200);
200        buf.push(k0, cell, 0);
201        buf.push(k1, cell, 100);
202
203        let resolved = buf.resolve_last_write_wins();
204        assert_eq!(resolved, vec![(cell, 200)]);
205    }
206
207    #[test]
208    fn write_buffer_out_of_order_submission_still_commits_in_key_order() {
209        let cell = StateCellId(3);
210        let k_t5 = key(5, Region::Nba, 0, 0, 0);
211        let k_t3 = key(3, Region::Nba, 0, 0, 0);
212
213        let mut buf: WriteBuffer<&'static str> = WriteBuffer::new();
214        // Submitted out of order: t=5 first (correct answer), then t=3.
215        buf.push(k_t5, cell, "t5-value");
216        buf.push(k_t3, cell, "t3-value");
217
218        let resolved = buf.resolve_last_write_wins();
219        assert_eq!(resolved, vec![(cell, "t5-value")]);
220    }
221
222    #[test]
223    fn dt010_single_canonical_key_type_used_by_both_ready_set_and_write_buffer() {
224        let a = activation(1, 42, 5, Region::Active, 0, 0);
225        let (ticks, region_ordinal, reconv_iter, proc) = canonical_key_of(&a);
226        let built_key = CanonicalEventKey {
227            vtime: ticks,
228            region_ordinal,
229            reconv_iter,
230            canonical_process_id: proc,
231            local_send_seq: 0,
232        };
233
234        let mut buf: WriteBuffer<u8> = WriteBuffer::new();
235        buf.push(built_key, StateCellId(1), 1);
236        let resolved = buf.resolve_last_write_wins();
237        assert_eq!(resolved, vec![(StateCellId(1), 1)]);
238    }
239}
vj_sim/sched/order.rs

vj_sim/sched/
order.rs
