javm/
callstack.rs

1//! Kernel-internal call stack.
2//!
3//! Per v3 spec §3 "The Instance status state machine and kernel call
4//! stack":
5//!
6//! - **InstanceEntry** — pushed by CALL. Introduces a fresh invocation
7//!   of an Instance. Carries that invocation's PC, regs, and reference
8//!   to the in-flight Instance state.
9//!
10//! - **ReferenceEntry** — pushed by host_yield. Refers to an
11//!   InstanceEntry earlier in the stack; the referenced entry's PC and
12//!   regs are shared (the ReferenceEntry is just a "this position
13//!   also depends on entry N" pointer for yield-resume routing).
14//!
15//! Invariants (enforced via `enforce_invariants` in debug builds):
16//! - Exactly one entry is `Running` — the top of the stack.
17//! - All others are `Waiting`.
18//! - A `ReferenceEntry` at position `i` has
19//!   `target_position < i` and the target is an `InstanceEntry`.
20//!
21//! State storage: an `InstanceEntry` owns its in-flight working root
22//! cnode and references into a shared `CacheDirectory` for the underlying
23//! Image and Instance content. The Vm consults the stack top to find
24//! the actively executing Instance; it consults lower entries during
25//! yield-marker routing.
26
27use std::sync::Arc;
28
29use javm_cap::{CNodeCap, CapHash, CapHashOrRef, SlotIdx};
30use javm_exec::{GasCounter, Mem, PvmProgram, Regs};
31
32use crate::error::VmError;
33
34/// Per the spec §18 default; the chain spec may override.
35pub const DEFAULT_MAX_DEPTH: usize = 256;
36
37/// Status of a stack entry. Exactly one entry is `Running` (the top);
38/// all others are `Waiting`. Block-end faults any remaining `Waiting`
39/// entries per spec §3.
40#[derive(Clone, Copy, Debug, PartialEq, Eq)]
41pub enum EntryStatus {
42    Running,
43    Waiting,
44}
45
46/// In-flight state of an Instance currently on the call stack.
47///
48/// Owns the working root cnode, regs, and memory of this invocation.
49/// The Vm updates these in place as the interpreter runs. The
50/// `program` is shared (Arc) — multiple in-flight entries can share
51/// the same predecoded bytecode (e.g. siblings of the same image).
52pub struct InstanceEntry {
53    /// Reference back to the CacheDirectory entry this invocation is running.
54    /// Carried across the apply so the post-HALT settle can hash the
55    /// final working state into a `CapHash`.
56    pub instance_ref: CapHashOrRef,
57    /// Cached for quick read of the Instance's type identity.
58    pub image_hash_chain: CapHash,
59    /// Cached for quick read of the bound Image hash.
60    pub image_hash: CapHash,
61    /// Predecoded bytecode (keyed by `image_hash` in `ImageCache`).
62    pub program: Arc<PvmProgram>,
63    /// MainFrame cnode — the active CapTable. Owned by this entry; on
64    /// HALT it's commit-merged back into the cache.
65    pub root_cnode: CNodeCap,
66    /// `Image.yield_marker_slot`, cached for yield routing.
67    pub yield_marker_slot: Option<SlotIdx>,
68    /// Sorted slot indices declared pinned by this Image. Cached for
69    /// fast `is_pinned` checks.
70    pub pinned_slots: Vec<SlotIdx>,
71    /// Working registers.
72    pub regs: Regs,
73    /// Working memory (mapped RW overlays + ephemeral).
74    pub mem: Mem,
75    /// Local gas counter — pulls from `KernelAssist::gas_meter_*`
76    /// against the active gas slot.
77    pub gas: GasCounter,
78    /// Running vs. Waiting.
79    pub status: EntryStatus,
80}
81
82impl std::fmt::Debug for InstanceEntry {
83    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
84        f.debug_struct("InstanceEntry")
85            .field("image_hash_chain", &short_hex(&self.image_hash_chain))
86            .field("image_hash", &short_hex(&self.image_hash))
87            .field("pc", &self.regs.pc)
88            .field("status", &self.status)
89            .field("cnode.size_log", &self.root_cnode.size_log)
90            .finish_non_exhaustive()
91    }
92}
93
94/// Stack entry that refers to an InstanceEntry earlier on the stack.
95/// Pushed by `host_yield` after a yield marker matches the target's
96/// YieldCatcher; the target resumes when this entry rotates to the top
97/// (via CALL_RESUME or HALT-unwind).
98#[derive(Clone, Copy, Debug, PartialEq, Eq)]
99pub struct ReferenceEntry {
100    /// Index of the InstanceEntry this reference resumes.
101    pub target_position: usize,
102    /// Running vs. Waiting.
103    pub status: EntryStatus,
104}
105
106/// One slot on the call stack.
107///
108/// `InstanceEntry` is boxed because its working state (cnode + mem +
109/// regs) is significantly larger than a `ReferenceEntry` (3 words);
110/// keeping the enum's stack-side discriminant compact matters when
111/// the stack approaches the max-depth limit (256 by default).
112#[derive(Debug)]
113pub enum Entry {
114    Instance(Box<InstanceEntry>),
115    Reference(ReferenceEntry),
116}
117
118impl Entry {
119    pub fn status(&self) -> EntryStatus {
120        match self {
121            Entry::Instance(e) => e.status,
122            Entry::Reference(e) => e.status,
123        }
124    }
125
126    pub fn set_status(&mut self, s: EntryStatus) {
127        match self {
128            Entry::Instance(e) => e.status = s,
129            Entry::Reference(e) => e.status = s,
130        }
131    }
132
133    pub fn is_instance(&self) -> bool {
134        matches!(self, Entry::Instance(_))
135    }
136
137    pub fn as_instance(&self) -> Option<&InstanceEntry> {
138        match self {
139            Entry::Instance(e) => Some(e.as_ref()),
140            _ => None,
141        }
142    }
143
144    pub fn as_instance_mut(&mut self) -> Option<&mut InstanceEntry> {
145        match self {
146            Entry::Instance(e) => Some(e.as_mut()),
147            _ => None,
148        }
149    }
150}
151
152/// The kernel-internal call stack.
153///
154/// The stack drives control transfer (CALL/yield/HALT) and provides
155/// the structural invocation boundary that gives v3 its fault
156/// atomicity and yield-resume linearity (§3 "Why hierarchy is the
157/// invocation boundary").
158pub struct CallStack {
159    entries: Vec<Entry>,
160    max_depth: usize,
161}
162
163impl CallStack {
164    pub fn new(max_depth: usize) -> Self {
165        Self {
166            entries: Vec::new(),
167            max_depth,
168        }
169    }
170
171    pub fn with_default_depth() -> Self {
172        Self::new(DEFAULT_MAX_DEPTH)
173    }
174
175    pub fn len(&self) -> usize {
176        self.entries.len()
177    }
178
179    pub fn is_empty(&self) -> bool {
180        self.entries.is_empty()
181    }
182
183    pub fn entries(&self) -> &[Entry] {
184        &self.entries
185    }
186
187    /// Mutable slice into entries — used by the driver to save live
188    /// regs/mem/gas back into a *specific* InstanceEntry by position
189    /// after the interpreter exits (e.g. saving the yielder's state
190    /// while a ReferenceEntry sits on top).
191    pub fn entries_mut(&mut self) -> &mut [Entry] {
192        &mut self.entries
193    }
194
195    /// Push a fresh InstanceEntry. Transitions any prior top from
196    /// `Running` to `Waiting`; the new entry becomes `Running`.
197    pub fn push_instance(&mut self, mut entry: InstanceEntry) -> Result<(), VmError> {
198        if self.entries.len() >= self.max_depth {
199            return Err(VmError::CallStackFull);
200        }
201        if let Some(top) = self.entries.last_mut() {
202            top.set_status(EntryStatus::Waiting);
203        }
204        entry.status = EntryStatus::Running;
205        self.entries.push(Entry::Instance(Box::new(entry)));
206        Ok(())
207    }
208
209    /// Push a ReferenceEntry pointing at an InstanceEntry earlier on
210    /// the stack. The reference becomes `Running`; the prior top
211    /// drops to `Waiting`.
212    pub fn push_reference(&mut self, target_position: usize) -> Result<(), VmError> {
213        if self.entries.len() >= self.max_depth {
214            return Err(VmError::CallStackFull);
215        }
216        if target_position >= self.entries.len() {
217            return Err(VmError::ReferenceOutOfRange(target_position));
218        }
219        if !self.entries[target_position].is_instance() {
220            return Err(VmError::ReferenceNonInstance(target_position));
221        }
222        if let Some(top) = self.entries.last_mut() {
223            top.set_status(EntryStatus::Waiting);
224        }
225        self.entries.push(Entry::Reference(ReferenceEntry {
226            target_position,
227            status: EntryStatus::Running,
228        }));
229        Ok(())
230    }
231
232    /// Pop the top entry. The next entry (if any) is promoted from
233    /// `Waiting` to `Running`.
234    pub fn pop(&mut self) -> Option<Entry> {
235        let popped = self.entries.pop();
236        if let Some(top) = self.entries.last_mut() {
237            top.set_status(EntryStatus::Running);
238        }
239        popped
240    }
241
242    /// The currently-Running top of the stack.
243    pub fn running(&self) -> Option<&Entry> {
244        self.entries.last()
245    }
246
247    pub fn running_mut(&mut self) -> Option<&mut Entry> {
248        self.entries.last_mut()
249    }
250
251    /// Resolve a ReferenceEntry's effective `InstanceEntry`.
252    ///
253    /// If the top is an InstanceEntry, returns it; if it's a
254    /// ReferenceEntry, follows the `target_position` link.
255    pub fn running_instance(&self) -> Option<&InstanceEntry> {
256        match self.entries.last()? {
257            Entry::Instance(e) => Some(e.as_ref()),
258            Entry::Reference(r) => match self.entries.get(r.target_position)? {
259                Entry::Instance(e) => Some(e.as_ref()),
260                Entry::Reference(_) => None, // shouldn't happen — invariants
261            },
262        }
263    }
264
265    pub fn running_instance_mut(&mut self) -> Option<&mut InstanceEntry> {
266        let last_idx = self.entries.len().checked_sub(1)?;
267        let target_idx = match &self.entries[last_idx] {
268            Entry::Instance(_) => last_idx,
269            Entry::Reference(r) => r.target_position,
270        };
271        match self.entries.get_mut(target_idx)? {
272            Entry::Instance(e) => Some(e.as_mut()),
273            Entry::Reference(_) => None,
274        }
275    }
276
277    /// Debug-build assertion of the v3 stack invariants. Real callers
278    /// should rely on the push/pop primitives to maintain them; this
279    /// is for testing the construction primitives themselves.
280    pub fn enforce_invariants(&self) -> Result<(), VmError> {
281        if self.entries.is_empty() {
282            return Ok(());
283        }
284        // Exactly one Running, at the top.
285        for (i, e) in self.entries.iter().enumerate() {
286            let expected = if i == self.entries.len() - 1 {
287                EntryStatus::Running
288            } else {
289                EntryStatus::Waiting
290            };
291            if e.status() != expected {
292                return Err(VmError::Invariant(
293                    "exactly one Running entry, at the stack top",
294                ));
295            }
296        }
297        // ReferenceEntries must target an earlier InstanceEntry.
298        for (i, e) in self.entries.iter().enumerate() {
299            if let Entry::Reference(r) = e {
300                if r.target_position >= i {
301                    return Err(VmError::ReferenceOutOfRange(r.target_position));
302                }
303                if !matches!(self.entries[r.target_position], Entry::Instance(_)) {
304                    return Err(VmError::ReferenceNonInstance(r.target_position));
305                }
306            }
307        }
308        Ok(())
309    }
310}
311
312impl std::fmt::Debug for CallStack {
313    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
314        f.debug_struct("CallStack")
315            .field("len", &self.entries.len())
316            .field("max_depth", &self.max_depth)
317            .finish()
318    }
319}
320
321fn short_hex(bytes: &[u8]) -> String {
322    bytes.iter().take(4).map(|b| format!("{:02x}", b)).collect()
323}
324
325#[cfg(test)]
326mod tests {
327    use super::*;
328    use javm_exec::PvmProgram;
329
330    fn make_entry(tag: u8) -> InstanceEntry {
331        let prog = Arc::new(PvmProgram::new(vec![0u8], vec![1u8], vec![], 25).unwrap());
332        let cnode = CNodeCap::new(8).unwrap();
333        InstanceEntry {
334            instance_ref: CapHashOrRef::Hash([tag; 32]),
335            image_hash_chain: [tag; 32],
336            image_hash: [tag.wrapping_add(0x10); 32],
337            program: prog,
338            root_cnode: cnode,
339            yield_marker_slot: None,
340            pinned_slots: Vec::new(),
341            regs: Regs::new(),
342            mem: Mem::new(),
343            gas: GasCounter::new(1000),
344            status: EntryStatus::Waiting,
345        }
346    }
347
348    #[test]
349    fn empty_stack_invariants_hold() {
350        let s = CallStack::with_default_depth();
351        assert!(s.is_empty());
352        assert!(s.running().is_none());
353        s.enforce_invariants().unwrap();
354    }
355
356    #[test]
357    fn push_instance_makes_it_running() {
358        let mut s = CallStack::with_default_depth();
359        s.push_instance(make_entry(1)).unwrap();
360        assert_eq!(s.len(), 1);
361        assert_eq!(s.running().unwrap().status(), EntryStatus::Running);
362        s.enforce_invariants().unwrap();
363    }
364
365    #[test]
366    fn push_two_instances_top_running_rest_waiting() {
367        let mut s = CallStack::with_default_depth();
368        s.push_instance(make_entry(1)).unwrap();
369        s.push_instance(make_entry(2)).unwrap();
370        assert_eq!(s.len(), 2);
371        assert_eq!(s.entries()[0].status(), EntryStatus::Waiting);
372        assert_eq!(s.entries()[1].status(), EntryStatus::Running);
373        s.enforce_invariants().unwrap();
374    }
375
376    #[test]
377    fn pop_promotes_next() {
378        let mut s = CallStack::with_default_depth();
379        s.push_instance(make_entry(1)).unwrap();
380        s.push_instance(make_entry(2)).unwrap();
381        let popped = s.pop().unwrap();
382        assert_eq!(popped.status(), EntryStatus::Running);
383        // The remaining entry is now Running.
384        assert_eq!(s.running().unwrap().status(), EntryStatus::Running);
385        s.enforce_invariants().unwrap();
386    }
387
388    #[test]
389    fn pop_last_leaves_empty() {
390        let mut s = CallStack::with_default_depth();
391        s.push_instance(make_entry(1)).unwrap();
392        s.pop().unwrap();
393        assert!(s.is_empty());
394        s.enforce_invariants().unwrap();
395    }
396
397    #[test]
398    fn push_reference_targets_earlier_instance() {
399        let mut s = CallStack::with_default_depth();
400        s.push_instance(make_entry(1)).unwrap();
401        s.push_instance(make_entry(2)).unwrap();
402        s.push_reference(0).unwrap();
403        assert_eq!(s.len(), 3);
404        // The reference is Running; both instances are Waiting.
405        assert!(matches!(s.entries()[0].status(), EntryStatus::Waiting));
406        assert!(matches!(s.entries()[1].status(), EntryStatus::Waiting));
407        assert!(matches!(s.entries()[2].status(), EntryStatus::Running));
408        s.enforce_invariants().unwrap();
409    }
410
411    #[test]
412    fn push_reference_out_of_range_rejected() {
413        let mut s = CallStack::with_default_depth();
414        s.push_instance(make_entry(1)).unwrap();
415        let res = s.push_reference(5);
416        assert!(matches!(res, Err(VmError::ReferenceOutOfRange(5))));
417    }
418
419    #[test]
420    fn push_reference_targeting_reference_rejected() {
421        let mut s = CallStack::with_default_depth();
422        s.push_instance(make_entry(1)).unwrap();
423        s.push_reference(0).unwrap();
424        // The top is a ReferenceEntry at position 1; targeting it
425        // should be rejected.
426        let res = s.push_reference(1);
427        assert!(matches!(res, Err(VmError::ReferenceNonInstance(1))));
428    }
429
430    #[test]
431    fn push_beyond_max_depth_rejected() {
432        let mut s = CallStack::new(2);
433        s.push_instance(make_entry(1)).unwrap();
434        s.push_instance(make_entry(2)).unwrap();
435        let res = s.push_instance(make_entry(3));
436        assert!(matches!(res, Err(VmError::CallStackFull)));
437    }
438
439    #[test]
440    fn running_instance_resolves_through_reference() {
441        let mut s = CallStack::with_default_depth();
442        s.push_instance(make_entry(1)).unwrap();
443        s.push_reference(0).unwrap();
444        let ic = s.running_instance().unwrap();
445        // The reference points at entry 0 (tag=1).
446        assert_eq!(ic.image_hash_chain, [1u8; 32]);
447    }
448}
javm/callstack.rs

javm/
callstack.rs
