mod dynamic_box; mod random; use crate::object::{ObjectHeader, ObjectKind}; use crate::resource_budget::{ BudgetVec, Reservation, ResourceFailure, ResourceReason, RuntimeBudget, RuntimeResource as Q, VecGrowth, }; use crate::typed_storage::TypedStorage; use crate::value_contract::{self, ValueError, ValueGroup}; use dynamic_box::DynamicBox; use prometeu_bytecode::registry::{BuiltinId, Registry, TypeId, TypeKind}; use prometeu_bytecode::{HeapRef, Value}; use std::sync::Arc; use std::sync::atomic::{AtomicU64, AtomicUsize, Ordering}; /// Internal stored object: header plus opaque payload bytes. #[derive(Debug)] pub struct StoredObject { pub header: ObjectHeader, /// Raw payload bytes for byte-oriented kinds (e.g., String, Bytes). pub payload: BudgetVec, /// Optional typed elements for `ObjectKind::Array`. /// When present, `header.payload_len` must equal `array_elems.len() as u32`. pub array_elems: Option>, /// Optional captured environment for `ObjectKind::Closure`. /// Invariants for closures: /// - `header.payload_len == 8` and `payload` bytes are `[fn_id: u32][env_len: u32]` (LE). /// - The actual `env_len` Value slots are stored here (not in `payload`) so /// they stay directly GC-visible. The GC must traverse exactly `env_len` /// entries from this slice, in order. pub closure_env: Option>, /// Registry-backed compact Struct/Array fields, never raw Value elements. typed: Option, /// Immutable native Value slots; not accessible through collection helpers. dynamic_box: Option, } /// One native object allocation, distinct from auxiliary handle-table storage. #[derive(Debug)] pub struct StoredAllocation(BudgetVec); impl std::ops::Deref for StoredAllocation { type Target = StoredObject; fn deref(&self) -> &StoredObject { &self.0[0] } } impl std::ops::DerefMut for StoredAllocation { fn deref_mut(&mut self) -> &mut StoredObject { &mut self.0[0] } } impl StoredAllocation { fn bytes(&self) -> usize { (self.0.accounted_bytes() + self.payload.accounted_bytes() + self.array_elems.as_ref().map_or(0, BudgetVec::accounted_bytes) + self.closure_env.as_ref().map_or(0, BudgetVec::accounted_bytes) + self.typed.as_ref().map_or(0, TypedStorage::bytes) + self.dynamic_box.as_ref().map_or(0, DynamicBox::bytes)) as usize } } // Candidate allocations own all reservations until a fully initialized object // is published. Dropping the candidate leaves handle tables unchanged. struct PreparedInsertion { storage: BudgetVec, new_slot: Option, } struct PreparedSlot { charge: Reservation, objects: Option>>, generations: Option>, free: Option>, } /// Non-moving, generation-checked heap with safepoint mark/sweep. #[derive(Debug)] pub struct Heap { // Tombstone-aware store: Some(obj) = live allocation; None = freed slot. objects: BudgetVec>, // Same index as objects. Maximum-generation reclaimed slots are never reused. generations: BudgetVec, // Reclaimed slots available for deterministic reuse (LIFO). free_list: BudgetVec, budget: RuntimeBudget, slots_charge: Reservation, /// Total bytes currently used by all objects in the heap. pub used_bytes: Arc, /// Monotonic count of heap allocation events for internal engineering telemetry. pub allocation_count: Arc, } impl Heap { #[cfg(test)] fn set_test_array(&mut self, r: HeapRef, values: &[Value]) { let data = BudgetVec::from_slice(&self.budget, Q::GuestBytes, values).unwrap(); let obj = self.objects[r.index as usize].as_mut().unwrap(); let old = obj.bytes(); obj.array_elems = Some(data); obj.header.payload_len = values.len() as u32; let new = obj.bytes(); self.used_bytes.fetch_sub(old, Ordering::Relaxed); self.used_bytes.fetch_add(new, Ordering::Relaxed); } #[cfg(test)] pub fn new() -> Self { Self::with_budget(&RuntimeBudget::default()) } pub fn with_budget(budget: &RuntimeBudget) -> Self { Self { objects: BudgetVec::new(budget, Q::AuxiliaryBytes), generations: BudgetVec::new(budget, Q::AuxiliaryBytes), free_list: BudgetVec::new(budget, Q::AuxiliaryBytes), budget: budget.clone(), slots_charge: budget.empty_charge(Q::HandleSlots), used_bytes: Arc::new(AtomicUsize::new(0)), allocation_count: Arc::new(AtomicU64::new(0)), } } fn check_slot(&self) -> Result<(), ResourceFailure> { if self.free_list.is_empty() { self.budget.check(Q::HandleSlots, self.objects.len() as u64 + 1)?; } Ok(()) } fn prepare_insertion(&self) -> Result { self.check_slot()?; let mut storage = BudgetVec::new(&self.budget, Q::GuestBytes); storage.reserve(1)?; let new_slot = if self.free_list.is_empty() { Some(PreparedSlot { charge: self.budget.reserve(Q::HandleSlots, 1)?, objects: self.objects.prepare_growth(1)?, generations: self.generations.prepare_growth(1)?, free: self .free_list .prepare_growth(self.objects.len() + 1 - self.free_list.len())?, }) } else { None }; Ok(PreparedInsertion { storage, new_slot }) } fn insert_object(&mut self, obj: StoredObject) -> Result { let prepared = self.prepare_insertion()?; Ok(self.commit_insertion(prepared, obj)) } fn commit_insertion(&mut self, mut prepared: PreparedInsertion, obj: StoredObject) -> HeapRef { prepared.storage.push(obj).expect("object header reserved before initialization"); let obj = StoredAllocation(prepared.storage); let bytes = obj.bytes(); let handle = if let Some(PreparedSlot { charge: slot_charge, objects, generations, free }) = prepared.new_slot { self.objects.commit_growth(objects); self.generations.commit_growth(generations); self.free_list.commit_growth(free); let idx = self.objects.len(); self.objects.push(Some(obj)).expect("reserved handle slot"); self.generations.push(1).expect("reserved generation slot"); self.slots_charge.absorb(slot_charge); HeapRef { index: idx as u32, generation: 1 } } else { let idx = self.free_list.pop().expect("reserved reusable handle"); debug_assert!(self.objects[idx].is_none()); self.objects[idx] = Some(obj); HeapRef { index: idx as u32, generation: self.generations[idx] } }; self.used_bytes.fetch_add(bytes, Ordering::Relaxed); self.allocation_count.fetch_add(1, Ordering::Relaxed); handle } #[cfg(test)] pub fn allocate_object( &mut self, kind: ObjectKind, payload: &[u8], ) -> Result { self.check_slot()?; let payload_len = self.payload_len(payload.len())?; let payload = BudgetVec::from_slice(&self.budget, Q::GuestBytes, payload)?; self.insert_object(StoredObject { header: ObjectHeader::new(kind, payload_len), payload, array_elems: None, closure_env: None, typed: None, dynamic_box: None, }) } #[cfg(test)] pub fn allocate_array(&mut self, elements: Vec) -> Result { self.check_slot()?; let payload_len = self.payload_len(elements.len())?; let elems = BudgetVec::from_slice(&self.budget, Q::GuestBytes, &elements)?; self.insert_object(StoredObject { header: ObjectHeader::new(ObjectKind::Array, payload_len), payload: BudgetVec::new(&self.budget, Q::GuestBytes), array_elems: Some(elems), closure_env: None, typed: None, dynamic_box: None, }) } fn payload_len(&self, len: usize) -> Result { u32::try_from(len).map_err(|_| { self.budget.failure(Q::GuestBytes, ResourceReason::SizeOverflow, len as u64) }) } pub(crate) fn alloc_typed_closure( &mut self, fn_id: u32, fn_type: TypeId, env_values: &[Value], ) -> Result { self.check_slot()?; let env_len = self.payload_len(env_values.len())?; let mut bytes = [0; 12]; bytes[..4].copy_from_slice(&fn_id.to_le_bytes()); bytes[4..8].copy_from_slice(&env_len.to_le_bytes()); bytes[8..12].copy_from_slice(&fn_type.0.to_le_bytes()); let payload = BudgetVec::from_slice(&self.budget, Q::GuestBytes, &bytes)?; let env = BudgetVec::from_slice(&self.budget, Q::GuestBytes, env_values)?; self.insert_object(StoredObject { header: ObjectHeader::new(ObjectKind::Closure, 12), payload, array_elems: None, closure_env: Some(env), typed: None, dynamic_box: None, }) } /// Returns true if this handle refers to an allocated object. pub fn is_valid(&self, r: HeapRef) -> bool { let idx = r.index as usize; if idx >= self.objects.len() { return false; } r.generation != 0 && self.generations[idx] == r.generation && self.objects[idx].is_some() } /// Get immutable access to an object's header by handle. pub fn header(&self, r: HeapRef) -> Option<&ObjectHeader> { if !self.is_valid(r) { return None; } self.objects.get(r.index as usize).and_then(|slot| slot.as_ref()).map(|o| &o.header) } /// Internal: get mutable access to an object's header by handle. fn header_mut(&mut self, r: HeapRef) -> Option<&mut ObjectHeader> { if !self.is_valid(r) { return None; } self.objects.get_mut(r.index as usize).and_then(|slot| slot.as_mut()).map(|o| &mut o.header) } pub(crate) fn closure_type(&self, r: HeapRef) -> Result { if !self.is_valid(r) { return Err(ValueError::InvalidHandle); } let object = self.objects[r.index as usize].as_ref().unwrap(); if object.header.kind != ObjectKind::Closure || object.payload.len() != 12 { return Err(ValueError::Type); } Ok(TypeId(u32::from_le_bytes(object.payload[8..12].try_into().unwrap()))) } #[cfg(test)] pub fn alloc_closure(&mut self, fn_id: u32, env: &[Value]) -> Result { self.alloc_typed_closure(fn_id, TypeId(0), env) } /// Read the `fn_id` stored in a closure object. Returns None if kind mismatch or invalid ref. pub fn closure_fn_id(&self, r: HeapRef) -> Option { if !self.is_valid(r) { return None; } let idx = r.index as usize; let slot = self.objects.get(idx)?.as_ref()?; if slot.header.kind != ObjectKind::Closure { return None; } if slot.payload.len() < 8 { return None; } debug_assert_eq!(slot.header.payload_len, 12); let mut bytes = [0u8; 4]; bytes.copy_from_slice(&slot.payload[0..4]); Some(u32::from_le_bytes(bytes)) } /// Get the captured environment slice of a closure. Returns None if kind mismatch or invalid ref. pub(crate) fn closure_env_slice(&self, r: HeapRef) -> Option<&[Value]> { if !self.is_valid(r) { return None; } let idx = r.index as usize; let slot = self.objects.get(idx)?.as_ref()?; if slot.header.kind != ObjectKind::Closure { return None; } if slot.payload.len() >= 8 { let mut nbytes = [0u8; 4]; nbytes.copy_from_slice(&slot.payload[4..8]); let env_len = u32::from_le_bytes(nbytes) as usize; if let Some(env) = slot.closure_env.as_deref() { debug_assert_eq!(env.len(), env_len); } } slot.closure_env.as_deref() } /// Mark phase: starting from the given roots, traverse and set mark bits /// on all reachable objects. Uses an explicit stack to avoid recursion. #[cfg(test)] pub fn mark_from_roots>( &mut self, roots: I, ) -> Result<(), ResourceFailure> { self.mark(roots) } pub fn mark_session_roots>( &mut self, roots: I, ) -> Result<(), ResourceFailure> { self.mark(roots) } fn enqueue_mark(&mut self, r: HeapRef, stack: &mut BudgetVec) { if let Some(header) = self.header_mut(r) && !header.is_marked() { // Each live object enters at most once; reserve(len()) bounds the entire traversal. header.set_marked(true); stack.push(r).expect("mark worklist reserved for every live object"); } } fn children(&self, r: HeapRef) -> &[Value] { let obj = self.objects[r.index as usize].as_ref().expect("validated worklist handle"); match obj.header.kind { ObjectKind::Array => obj.array_elems.as_deref().unwrap_or(&[]), ObjectKind::Closure => obj.closure_env.as_deref().unwrap_or(&[]), ObjectKind::DynamicBox => obj.dynamic_box.as_ref().map_or(&[], DynamicBox::values), _ => &[], } } fn mark>(&mut self, roots: I) -> Result<(), ResourceFailure> { let mut stack = BudgetVec::new(&self.budget, Q::TemporaryBytes); stack.reserve(self.len())?; // Fail before changing any mark bit. for root in roots { self.enqueue_mark(root, &mut stack); } while let Some(r) = stack.pop() { let typed_count = self.objects[r.index as usize] .as_ref() .unwrap() .typed .as_ref() .map_or(0, TypedStorage::root_count); for i in 0..typed_count { let child = self.objects[r.index as usize] .as_ref() .unwrap() .typed .as_ref() .unwrap() .root_at(i); if let Some(child) = child { self.enqueue_mark(child, &mut stack); } } for i in 0..self.children(r).len() { let child = crate::roots::value_heap_ref(&self.children(r)[i]); if let Some(child) = child { self.enqueue_mark(child, &mut stack); } } } Ok(()) } /// Sweep phase: reclaim unmarked objects by turning their slots into /// tombstones (None), and clear the mark bit on the remaining live ones /// to prepare for the next GC cycle. Does not move or compact objects. pub fn sweep(&mut self) { for (idx, slot) in self.objects.iter_mut().enumerate() { if let Some(obj) = slot { if obj.header.is_marked() { // Live: clear mark for next cycle. obj.header.set_marked(false); } else { // Unreachable: reclaim by dropping and turning into tombstone. self.used_bytes.fetch_sub(obj.bytes(), Ordering::Relaxed); *slot = None; if let Some(next) = self.generations[idx].checked_add(1) { self.generations[idx] = next; self.free_list .push(idx) .expect("recycling capacity reserved with handle slot"); } } } } } /// Current number of allocated (live) objects. pub fn len(&self) -> usize { self.objects.iter().filter(|s| s.is_some()).count() } pub fn allocation_count(&self) -> u64 { self.allocation_count.load(Ordering::Relaxed) } /// Host-side observations only, outside guest execution and atomic commits. #[cfg(feature = "resource-diagnostics")] pub fn diagnostic_typed_storage(&self) -> Vec { use crate::resource_diagnostics::{StorageObject, StorageValue}; self.objects .iter() .enumerate() .filter_map(|(index, object)| { let storage = object.as_ref()?.typed.as_ref()?; let groups = (0..storage.len()) .map(|i| { storage .read(i) .expect("initialized typed storage") .as_slice() .iter() .map(StorageValue::observe) .collect() }) .collect(); Some(StorageObject { reference: HeapRef { index: index as u32, generation: self.generations[index] }, type_id: storage.type_id(), groups, }) }) .collect() } #[cfg(feature = "resource-diagnostics")] pub(crate) fn diagnostic_handles(&self) -> (usize, usize) { (self.free_list.len(), self.objects.len() - self.free_list.len() - self.len()) } } // Internal consumer seam for PLN-0176 step 18 / AGD-0054. Executable image // publication and collection instructions are separate integration work. #[allow(dead_code)] impl Heap { fn typed_object(&self, r: HeapRef) -> Result<&TypedStorage, ValueError> { if r.is_null() { return Err(ValueError::NullReference); } if !self.is_valid(r) { return Err(ValueError::InvalidHandle); } self.objects[r.index as usize].as_ref().unwrap().typed.as_ref().ok_or(ValueError::Type) } pub(crate) fn concrete_type( &self, r: HeapRef, registry: &Registry, ) -> Result { let storage = self.typed_object(r)?; if !std::ptr::eq(storage.registry(), registry) { return Err(ValueError::Type); } Ok(storage.type_id()) } pub(crate) fn typed_array_len( &self, r: HeapRef, registry: &Registry, ) -> Result { self.concrete_type(r, registry)?; let storage = self.typed_object(r)?; if registry.type_layout(storage.type_id()).unwrap().array.is_none() { return Err(ValueError::Type); } Ok(storage.len()) } pub(crate) fn allocate_typed_struct( &mut self, registry: Arc, type_id: TypeId, ) -> Result { let prepared = self.prepare_insertion()?; let storage = TypedStorage::new_struct(registry, type_id, &self.budget)?; Ok(self.insert_typed(prepared, ObjectKind::Struct, 0, storage)) } pub(crate) fn allocate_typed_array( &mut self, registry: Arc, type_id: TypeId, count: u32, ) -> Result { let prepared = self.prepare_insertion()?; let storage = TypedStorage::new_array(registry, type_id, count, &self.budget)?; Ok(self.insert_typed(prepared, ObjectKind::Array, count, storage)) } fn insert_typed( &mut self, prepared: PreparedInsertion, kind: ObjectKind, count: u32, storage: TypedStorage, ) -> HeapRef { self.commit_insertion( prepared, StoredObject { header: ObjectHeader::new(kind, count), payload: BudgetVec::new(&self.budget, Q::GuestBytes), array_elems: None, closure_env: None, typed: Some(storage), dynamic_box: None, }, ) } pub(crate) fn load_typed( &self, registry: &Registry, r: HeapRef, index: usize, ) -> Result { self.concrete_type(r, registry)?; let storage = self.typed_object(r)?; let values = storage.read(index)?; value_contract::validate(registry, self, storage.slot_type(index)?, values.as_slice())?; Ok(values) } /// Caller has checked all receivers, bounds and groups for the entire attempt. /// This commit path performs no allocation, provenance lookup or guest callback. pub(crate) fn commit_typed(&mut self, r: HeapRef, index: usize, values: &[Value]) { self.objects[r.index as usize] .as_mut() .unwrap() .typed .as_mut() .unwrap() .write_validated(index, values) .expect("prevalidated storage publication"); } pub(crate) fn store_typed( &mut self, registry: &Registry, r: HeapRef, index: usize, values: &[Value], ) -> Result<(), ValueError> { self.concrete_type(r, registry)?; let ty = self.typed_object(r)?.slot_type(index)?; value_contract::validate(registry, self, ty, values)?; // No mutation/publication or owner cloning occurs before complete validation. self.objects[r.index as usize] .as_mut() .unwrap() .typed .as_mut() .unwrap() .write_validated(index, values) } } #[allow(dead_code)] impl Heap { pub(crate) fn allocate_dynamic_box( &mut self, registry: Arc, type_id: TypeId, values: &[Value], ) -> Result { // Validate before reserving anything. The source remains live and borrowed // through publication, and this path never invokes GC or the scheduler. validate_box_group(®istry, self, type_id, values)?; self.check_slot()?; let payload_len = self.payload_len(values.len())?; let dynamic_box = DynamicBox::new(registry, type_id, values, &self.budget)?; Ok(self.insert_object(StoredObject { header: ObjectHeader::new(ObjectKind::DynamicBox, payload_len), payload: BudgetVec::new(&self.budget, Q::GuestBytes), array_elems: None, closure_env: None, typed: None, dynamic_box: Some(dynamic_box), })?) } pub(crate) fn dynamic_box_values( &self, registry: &Registry, r: HeapRef, type_id: TypeId, ) -> Result<&[Value], ValueError> { if r.is_null() { return Err(ValueError::Type); } if !self.is_valid(r) { return Err(ValueError::InvalidHandle); } let object = self.objects[r.index as usize].as_ref().unwrap(); if object.header.kind != ObjectKind::DynamicBox { return Err(ValueError::Type); } let values = object.dynamic_box.as_ref().ok_or(ValueError::Type)?.typed_values(registry, type_id)?; if object.header.payload_len as usize != values.len() { return Err(ValueError::Type); } validate_box_group(registry, self, type_id, values)?; Ok(values) } } fn validate_box_group( registry: &Registry, heap: &Heap, type_id: TypeId, values: &[Value], ) -> Result<(), ValueError> { let layout = registry.type_layout(type_id).ok_or(ValueError::Type)?; if layout.storage.slots <= 1 || matches!( registry.declarations().types[type_id.0 as usize].kind, TypeKind::Builtin(BuiltinId::DYNAMIC) ) || values.iter().all(|value| matches!(value, Value::Null)) { return Err(ValueError::Type); } // Only vec2, pixel and present trait views reach this path. In particular, // validating a malicious Dynamic box cannot recurse into another box. value_contract::validate(registry, heap, type_id, values) } #[cfg(test)] mod dynamic_tests; #[cfg(test)] mod tests { use super::*; #[test] fn stale_references_cannot_access_a_reused_incarnation() { let mut heap = Heap::new(); let old = heap.alloc_closure(7, &[]).unwrap(); assert_eq!((old.index, old.generation), (0, 1)); heap.sweep(); let live = heap.alloc_closure(9, &[]).unwrap(); assert_eq!(live.index, old.index); assert_eq!(live.generation, 2); assert!(!heap.is_valid(old)); assert!(heap.header(old).is_none()); assert!(heap.closure_fn_id(old).is_none()); assert!(heap.closure_env_slice(old).is_none()); assert_eq!(heap.closure_fn_id(live), Some(9)); // Stale roots never retain the newer object at the same index. heap.mark_from_roots([old]).unwrap(); heap.sweep(); assert!(!heap.is_valid(live)); } #[test] fn maximum_generation_is_retired_without_wraparound() { let mut heap = Heap::new(); let first = heap.allocate_object(ObjectKind::Bytes, &[]).unwrap(); heap.generations[first.index as usize] = u32::MAX; let last = HeapRef { index: first.index, generation: u32::MAX }; assert!(heap.is_valid(last)); heap.sweep(); assert!(!heap.is_valid(last)); assert!(heap.free_list.is_empty()); let next = heap.allocate_object(ObjectKind::Bytes, &[]).unwrap(); assert_ne!(next.index, last.index); assert_eq!(next.generation, 1); assert_eq!(heap.generations[last.index as usize], u32::MAX); } #[test] fn basic_allocation_returns_valid_refs() { let mut heap = Heap::new(); let r1 = heap.allocate_object(ObjectKind::String, b"hello").unwrap(); let r2 = heap.allocate_object(ObjectKind::Bytes, &[1, 2, 3, 4]).unwrap(); let r3 = heap.allocate_array(vec![]).unwrap(); assert!(heap.is_valid(r1)); assert!(heap.is_valid(r2)); assert!(heap.is_valid(r3)); assert_eq!(heap.len(), 3); let h1 = heap.header(r1).unwrap(); assert_eq!(h1.kind, ObjectKind::String); assert_eq!(h1.payload_len, 5); let h2 = heap.header(r2).unwrap(); assert_eq!(h2.kind, ObjectKind::Bytes); assert_eq!(h2.payload_len, 4); let h3 = heap.header(r3).unwrap(); assert_eq!(h3.kind, ObjectKind::Array); assert_eq!(h3.payload_len, 0); } #[test] fn mark_reachable_through_array() { let mut heap = Heap::new(); // Target object B (unreferenced yet) let b = heap.allocate_object(ObjectKind::Bytes, &[9, 9, 9]).unwrap(); // Array A that contains a reference to B among other primitives let a = heap .allocate_array(vec![Value::Int32(1), Value::HeapRef(b), Value::Boolean(false)]) .unwrap(); // Mark starting from root A heap.mark_from_roots([a]).unwrap(); // Both A and B must be marked; random other objects are not allocated assert!(heap.header(a).unwrap().is_marked()); assert!(heap.header(b).unwrap().is_marked()); } #[test] fn mark_does_not_mark_unreachable() { let mut heap = Heap::new(); let unreachable = heap.allocate_object(ObjectKind::String, b"orphan").unwrap(); let root = heap.allocate_object(ObjectKind::Bytes, &[1, 2, 3]).unwrap(); heap.mark_from_roots([root]).unwrap(); assert!(heap.header(root).unwrap().is_marked()); assert!(!heap.header(unreachable).unwrap().is_marked()); } #[test] fn mark_handles_cycles() { let mut heap = Heap::new(); // Create two arrays that reference each other: A -> B, B -> A // Allocate empty arrays first to get handles let a = heap.allocate_array(vec![]).unwrap(); let b = heap.allocate_array(vec![]).unwrap(); // Now mutate their internal vectors via re-allocation pattern: // replace with arrays containing cross-references. Since our simple // heap doesn't support in-place element edits via API, simulate by // directly editing stored objects. heap.set_test_array(a, &[Value::HeapRef(b)]); heap.set_test_array(b, &[Value::HeapRef(a)]); // Mark from A; should terminate and mark both. heap.mark_from_roots([a]).unwrap(); assert!(heap.header(a).unwrap().is_marked()); assert!(heap.header(b).unwrap().is_marked()); } #[test] fn closure_allocation_with_empty_env() { let mut heap = Heap::new(); let c = heap.alloc_closure(42, &[]).unwrap(); assert!(heap.is_valid(c)); let h = heap.header(c).unwrap(); assert_eq!(h.kind, ObjectKind::Closure); // payload has only metadata (8 bytes) assert_eq!(h.payload_len, 12); assert_eq!(heap.closure_fn_id(c), Some(42)); let env = heap.closure_env_slice(c).unwrap(); assert_eq!(env.len(), 0); } #[test] fn closure_allocation_with_env_and_access() { let mut heap = Heap::new(); let a = heap.allocate_object(ObjectKind::String, b"a").unwrap(); let env_vals = vec![Value::Int32(7), Value::HeapRef(a), Value::Boolean(true)]; let c = heap.alloc_closure(7, &env_vals).unwrap(); let h = heap.header(c).unwrap(); assert_eq!(h.kind, ObjectKind::Closure); assert_eq!(h.payload_len, 12); assert_eq!(heap.closure_fn_id(c), Some(7)); let env = heap.closure_env_slice(c).unwrap(); assert_eq!(env, &env_vals[..]); // GC traversal should see the inner HeapRef in closure env when marking. heap.mark_from_roots([c]).unwrap(); assert!(heap.header(c).unwrap().is_marked()); assert!(heap.header(a).unwrap().is_marked()); } #[test] fn sweep_reclaims_unreachable_and_invalidates_handles() { let mut heap = Heap::new(); // Allocate two objects; only one will be a root. let unreachable = heap.allocate_object(ObjectKind::String, b"orphan").unwrap(); let root = heap.allocate_object(ObjectKind::Bytes, &[1, 2, 3]).unwrap(); // Mark from root and then sweep. heap.mark_from_roots([root]).unwrap(); // Precondition: root marked, unreachable not marked. assert!(heap.header(root).unwrap().is_marked()); assert!(!heap.header(unreachable).unwrap().is_marked()); heap.sweep(); // Unreachable must be reclaimed: handle becomes invalid. assert!(!heap.is_valid(unreachable)); assert!(heap.header(unreachable).is_none()); // Root must survive and have its mark bit cleared for next cycle. assert!(heap.is_valid(root)); assert!(!heap.header(root).unwrap().is_marked()); } #[test] fn sweep_keeps_indices_stable_and_len_counts_live() { let mut heap = Heap::new(); let a = heap.allocate_object(ObjectKind::String, b"a").unwrap(); let b = heap.allocate_object(ObjectKind::String, b"b").unwrap(); let c = heap.allocate_object(ObjectKind::String, b"c").unwrap(); // Only keep A live. heap.mark_from_roots([a]).unwrap(); heap.sweep(); // B and C are now invalidated, A remains valid. assert!(heap.is_valid(a)); assert!(!heap.is_valid(b)); assert!(!heap.is_valid(c)); // Len counts only live objects. assert_eq!(heap.len(), 1); // Indices are stable: A's index is still within the backing store bounds. // We can't access internal vector here, but stability is implied by handle not changing. assert_eq!(heap.header(a).unwrap().kind, ObjectKind::String); } #[test] fn sweep_reuses_freed_slot_on_next_allocation() { let mut heap = Heap::new(); let dead = heap.allocate_object(ObjectKind::String, b"dead").unwrap(); let live = heap.allocate_object(ObjectKind::String, b"live").unwrap(); heap.mark_from_roots([live]).unwrap(); heap.sweep(); assert!(!heap.is_valid(dead)); assert_eq!(heap.free_list, vec![dead.index as usize]); let reused = heap.allocate_object(ObjectKind::Bytes, &[1, 2, 3]).unwrap(); assert_eq!(reused.index, dead.index); assert_eq!(reused.generation, dead.generation + 1); assert!(!heap.is_valid(dead)); assert!(heap.is_valid(reused)); assert!(heap.is_valid(live)); } #[test] fn live_handles_remain_stable_when_freelist_is_reused() { let mut heap = Heap::new(); let live = heap.allocate_object(ObjectKind::String, b"live").unwrap(); let dead = heap.allocate_object(ObjectKind::String, b"dead").unwrap(); heap.mark_from_roots([live]).unwrap(); heap.sweep(); let replacement = heap.allocate_object(ObjectKind::Bytes, &[9]).unwrap(); assert_eq!(replacement.index, dead.index); assert_ne!(replacement, dead); assert!(!heap.is_valid(dead)); assert_eq!(heap.header(live).unwrap().kind, ObjectKind::String); assert_eq!(heap.header(replacement).unwrap().kind, ObjectKind::Bytes); assert_eq!(live.index, 0); } #[test] fn freelist_reuse_is_deterministic_lifo() { let mut heap = Heap::new(); let a = heap.allocate_object(ObjectKind::String, b"a").unwrap(); let b = heap.allocate_object(ObjectKind::String, b"b").unwrap(); let c = heap.allocate_object(ObjectKind::String, b"c").unwrap(); heap.mark_from_roots([]).unwrap(); heap.sweep(); assert_eq!(heap.free_list, vec![a.index as usize, b.index as usize, c.index as usize]); let r1 = heap.allocate_object(ObjectKind::Bytes, &[1]).unwrap(); let r2 = heap.allocate_object(ObjectKind::Bytes, &[2]).unwrap(); let r3 = heap.allocate_object(ObjectKind::Bytes, &[3]).unwrap(); assert_eq!(r1.index, c.index); assert_eq!(r1.generation, c.generation + 1); assert_eq!(r2.index, b.index); assert_eq!(r2.generation, b.generation + 1); assert_eq!(r3.index, a.index); assert_eq!(r3.generation, a.generation + 1); } #[test] fn sweep_reclaims_unrooted_cycle() { let mut heap = Heap::new(); // Build a 2-node cycle A <-> B using internal mutation (module-private access). let a = heap.allocate_array(vec![]).unwrap(); let b = heap.allocate_array(vec![]).unwrap(); // Make A point to B and B point to A. heap.set_test_array(a, &[Value::HeapRef(b)]); heap.set_test_array(b, &[Value::HeapRef(a)]); // No roots: perform sweep directly; both should be reclaimed. heap.sweep(); assert!(!heap.is_valid(a)); assert!(!heap.is_valid(b)); assert_eq!(heap.len(), 0); } #[test] fn gc_scans_closure_env_and_keeps_captured_heap_object() { let mut heap = Heap::new(); // Captured heap object. let obj = heap.allocate_object(ObjectKind::Bytes, &[4, 5, 6]).unwrap(); // Closure capturing the heap object among other primitive values. let env = [Value::Boolean(true), Value::HeapRef(obj), Value::Int32(123)]; let clo = heap.alloc_closure(1, &env).unwrap(); // Mark from closure root: both closure and captured object must be marked. heap.mark_from_roots([clo]).unwrap(); assert!(heap.header(clo).unwrap().is_marked()); assert!(heap.header(obj).unwrap().is_marked()); // Sweep should keep both and clear their marks. heap.sweep(); assert!(heap.is_valid(clo)); assert!(heap.is_valid(obj)); assert!(!heap.header(clo).unwrap().is_marked()); assert!(!heap.header(obj).unwrap().is_marked()); } #[test] fn gc_scans_nested_closures_and_keeps_inner_when_outer_is_rooted() { let mut heap = Heap::new(); // Inner closure (no env). let inner = heap.alloc_closure(2, &[]).unwrap(); // Outer closure captures the inner closure as a Value::HeapRef. let outer = heap.alloc_closure(3, &[Value::HeapRef(inner)]).unwrap(); // Root only the outer closure. heap.mark_from_roots([outer]).unwrap(); // Both must be marked reachable. assert!(heap.header(outer).unwrap().is_marked()); assert!(heap.header(inner).unwrap().is_marked()); // After sweep, both survive and have marks cleared. heap.sweep(); assert!(heap.is_valid(outer)); assert!(heap.is_valid(inner)); assert!(!heap.header(outer).unwrap().is_marked()); assert!(!heap.header(inner).unwrap().is_marked()); } #[test] fn gc_collects_unreferenced_closure_and_captures() { let mut heap = Heap::new(); // Captured heap object and a closure capturing it. let captured = heap.allocate_object(ObjectKind::String, b"dead").unwrap(); let clo = heap.alloc_closure(9, &[Value::HeapRef(captured)]).unwrap(); // No roots are provided; sweeping should reclaim both. heap.sweep(); assert!(!heap.is_valid(clo)); assert!(!heap.is_valid(captured)); assert_eq!(heap.len(), 0); } fn tiny_heap(resource: Q, limit: u64) -> (Heap, RuntimeBudget) { let budget = RuntimeBudget::new( crate::resource_budget::RuntimeLimits::default().lowered(resource, limit).unwrap(), ); (Heap::with_budget(&budget), budget) } #[test] fn guest_header_and_payload_limits_refund_failed_construction() { let required = (size_of::() + 12 + size_of::()) as u64; let (mut heap, budget) = tiny_heap(Q::GuestBytes, required - 1); assert_eq!(heap.alloc_closure(0, &[Value::Int64(9)]).unwrap_err().resource, Q::GuestBytes); for q in [Q::GuestBytes, Q::HandleSlots, Q::AuxiliaryBytes, Q::TemporaryBytes] { assert_eq!(budget.used(q), 0, "{q:?}"); } assert_eq!(heap.allocation_count(), 0); let (mut heap, budget) = tiny_heap(Q::GuestBytes, required); let r = heap.alloc_closure(0, &[Value::Int64(9)]).unwrap(); assert!(heap.is_valid(r)); assert_eq!(budget.used(Q::GuestBytes), required); assert_eq!(heap.used_bytes.load(Ordering::Relaxed) as u64, required); assert!(heap.alloc_closure(0, &[]).is_err()); assert_eq!(heap.len(), 1); heap.sweep(); assert_eq!(budget.used(Q::GuestBytes), 0); assert_eq!(heap.used_bytes.load(Ordering::Relaxed), 0); } #[test] fn table_growth_is_atomic_when_a_later_table_exceeds_auxiliary_quota() { let per_slot = (size_of::>() + size_of::() + size_of::()) as u64; let (mut heap, budget) = tiny_heap(Q::AuxiliaryBytes, 2 * per_slot - 1); let first = heap.allocate_object(ObjectKind::Bytes, &[]).unwrap(); let guest = budget.used(Q::GuestBytes); let error = heap.allocate_object(ObjectKind::Bytes, &[]).unwrap_err(); assert_eq!(error.resource, Q::AuxiliaryBytes); assert_eq!(budget.used(Q::AuxiliaryBytes), per_slot); assert_eq!(budget.used(Q::GuestBytes), guest); assert_eq!(budget.used(Q::HandleSlots), 1); assert_eq!(budget.used(Q::TemporaryBytes), 0); assert_eq!(heap.objects.len(), 1); assert_eq!(heap.generations.len(), 1); assert_eq!(heap.allocation_count(), 1); assert!(heap.is_valid(first)); } #[test] fn handle_limit_counts_free_and_retired_slots_and_reuse_does_not_charge_twice() { let (mut heap, budget) = tiny_heap(Q::HandleSlots, 1); let first = heap.allocate_object(ObjectKind::Bytes, &[]).unwrap(); assert_eq!( heap.allocate_object(ObjectKind::Bytes, &[]).unwrap_err().resource, Q::HandleSlots ); heap.sweep(); assert_eq!(budget.used(Q::HandleSlots), 1); let reused = heap.allocate_object(ObjectKind::Bytes, &[]).unwrap(); assert_eq!((reused.index, reused.generation), (first.index, 2)); assert_eq!(budget.used(Q::HandleSlots), 1); heap.generations[reused.index as usize] = u32::MAX; heap.sweep(); assert!(heap.free_list.is_empty()); assert_eq!(budget.used(Q::GuestBytes), 0); assert_eq!(budget.used(Q::HandleSlots), 1); assert_eq!( heap.allocate_object(ObjectKind::Bytes, &[]).unwrap_err().resource, Q::HandleSlots ); drop(heap); assert_eq!(budget.used(Q::HandleSlots), 0); assert_eq!(budget.used(Q::AuxiliaryBytes), 0); } #[test] fn mark_worklist_refusal_changes_no_marks_or_objects() { let (mut heap, budget) = tiny_heap(Q::TemporaryBytes, 0); let root = heap.allocate_array(vec![Value::Int64(8)]).unwrap(); let bytes = budget.used(Q::GuestBytes); let error = heap.mark_from_roots([root]).unwrap_err(); assert_eq!(error.resource, Q::TemporaryBytes); assert!(!heap.header(root).unwrap().is_marked()); assert!(heap.is_valid(root)); assert_eq!(budget.used(Q::GuestBytes), bytes); assert_eq!(budget.used(Q::TemporaryBytes), 0); } #[test] fn duplicate_edges_and_roots_need_one_work_slot_per_live_object() { let (mut heap, budget) = tiny_heap(Q::TemporaryBytes, size_of::() as u64); let root = HeapRef { index: 0, generation: 1 }; assert_eq!(heap.allocate_array(vec![Value::HeapRef(root); 1024]).unwrap(), root); heap.mark_from_roots(std::iter::repeat_n(root, 1024)).unwrap(); assert!(heap.header(root).unwrap().is_marked()); assert_eq!(budget.used(Q::TemporaryBytes), 0); heap.sweep(); assert!(heap.is_valid(root)); } #[test] fn quota_pressure_does_not_collect_outside_a_safepoint() { let (mut heap, budget) = tiny_heap(Q::GuestBytes, size_of::() as u64); let unreachable = heap.allocate_object(ObjectKind::Bytes, &[]).unwrap(); assert!(heap.allocate_object(ObjectKind::Bytes, &[]).is_err()); assert!(heap.is_valid(unreachable)); heap.sweep(); assert_eq!(budget.used(Q::GuestBytes), 0); let replacement = heap.allocate_object(ObjectKind::Bytes, &[]).unwrap(); assert_eq!(replacement.index, unreachable.index); assert_ne!(replacement.generation, unreachable.generation); } }