veridian_kernel/browser/
js_gc.rs

1//! JavaScript Garbage Collector
2//!
3//! Conservative mark-sweep GC for the JS object arena. Uses tri-color
4//! marking with root scanning from the VM stack, call frames, and globals.
5
6#![allow(dead_code)]
7
8use alloc::vec::Vec;
9
10use super::js_vm::{JsObject, JsValue, JsVm, ObjectId};
11
12// ---------------------------------------------------------------------------
13// GC cell wrapper
14// ---------------------------------------------------------------------------
15
16/// A GC-managed cell wrapping a JsObject
17#[derive(Debug, Clone)]
18pub struct GcCell {
19    /// The object data
20    pub data: JsObject,
21    /// Whether this cell is marked (reachable)
22    pub marked: bool,
23    /// Approximate size in bytes
24    pub size: usize,
25}
26
27impl GcCell {
28    pub fn new(data: JsObject) -> Self {
29        let size = estimate_object_size(&data);
30        Self {
31            data,
32            marked: false,
33            size,
34        }
35    }
36}
37
38// ---------------------------------------------------------------------------
39// GC Arena
40// ---------------------------------------------------------------------------
41
42/// Arena for garbage-collected objects
43pub struct GcArena {
44    /// Object slots (None = free)
45    objects: Vec<Option<GcCell>>,
46    /// Free list (indices of None slots)
47    free_list: Vec<usize>,
48    /// Total bytes allocated
49    bytes_allocated: usize,
50    /// GC threshold in bytes (trigger collection when exceeded)
51    threshold: usize,
52    /// Number of live objects
53    live_count: usize,
54    /// Number of collections performed
55    collection_count: usize,
56}
57
58impl Default for GcArena {
59    fn default() -> Self {
60        Self::new()
61    }
62}
63
64impl GcArena {
65    /// Default threshold: 8MB equivalent in bytes
66    const DEFAULT_THRESHOLD: usize = 8 * 1024 * 1024;
67
68    pub fn new() -> Self {
69        Self {
70            objects: Vec::with_capacity(256),
71            free_list: Vec::new(),
72            bytes_allocated: 0,
73            threshold: Self::DEFAULT_THRESHOLD,
74            live_count: 0,
75            collection_count: 0,
76        }
77    }
78
79    /// Allocate a new object, returning its ID
80    pub fn allocate(&mut self, obj: JsObject) -> ObjectId {
81        let cell = GcCell::new(obj);
82        self.bytes_allocated += cell.size;
83        self.live_count += 1;
84
85        if let Some(idx) = self.free_list.pop() {
86            self.objects[idx] = Some(cell);
87            idx
88        } else {
89            let idx = self.objects.len();
90            self.objects.push(Some(cell));
91            idx
92        }
93    }
94
95    /// Get an object by ID
96    pub fn get(&self, id: ObjectId) -> Option<&JsObject> {
97        self.objects
98            .get(id)
99            .and_then(|slot| slot.as_ref().map(|c| &c.data))
100    }
101
102    /// Get a mutable object by ID
103    pub fn get_mut(&mut self, id: ObjectId) -> Option<&mut JsObject> {
104        self.objects
105            .get_mut(id)
106            .and_then(|slot| slot.as_mut().map(|c| &mut c.data))
107    }
108
109    /// Whether the threshold has been exceeded
110    pub fn should_collect(&self) -> bool {
111        self.bytes_allocated >= self.threshold
112    }
113
114    /// Number of live objects
115    pub fn live_count(&self) -> usize {
116        self.live_count
117    }
118
119    /// Total bytes allocated
120    pub fn bytes_allocated(&self) -> usize {
121        self.bytes_allocated
122    }
123
124    /// Number of collections performed
125    pub fn collection_count(&self) -> usize {
126        self.collection_count
127    }
128
129    /// Total capacity (slots)
130    pub fn capacity(&self) -> usize {
131        self.objects.len()
132    }
133}
134
135// ---------------------------------------------------------------------------
136// GC Heap (mark-sweep collector)
137// ---------------------------------------------------------------------------
138
139/// Garbage collector coordinating mark and sweep phases
140pub struct GcHeap {
141    pub arena: GcArena,
142}
143
144impl Default for GcHeap {
145    fn default() -> Self {
146        Self::new()
147    }
148}
149
150impl GcHeap {
151    pub fn new() -> Self {
152        Self {
153            arena: GcArena::new(),
154        }
155    }
156
157    /// Allocate an object. May trigger GC if threshold exceeded.
158    pub fn allocate(&mut self, obj: JsObject) -> ObjectId {
159        self.arena.allocate(obj)
160    }
161
162    /// Run a full garbage collection cycle using roots from the VM
163    pub fn collect(&mut self, vm: &JsVm) {
164        self.mark_phase(vm);
165        self.sweep_phase();
166        self.arena.collection_count += 1;
167
168        // Grow threshold after collection (adaptive)
169        if self.arena.bytes_allocated > self.arena.threshold / 2 {
170            self.arena.threshold = self.arena.threshold.saturating_mul(2);
171        }
172    }
173
174    /// Mark phase: scan roots, mark all reachable objects
175    fn mark_phase(&mut self, vm: &JsVm) {
176        // Unmark all
177        for cell in self.arena.objects.iter_mut().flatten() {
178            cell.marked = false;
179        }
180
181        // Scan roots
182        let mut worklist = Vec::new();
183
184        // Root 1: operand stack
185        for val in &vm.stack {
186            if let Some(oid) = extract_object_id(val) {
187                worklist.push(oid);
188            }
189        }
190
191        // Root 2: call frame locals
192        for frame in &vm.call_stack {
193            for val in &frame.locals {
194                if let Some(oid) = extract_object_id(val) {
195                    worklist.push(oid);
196                }
197            }
198        }
199
200        // Root 3: global variables
201        for val in vm.globals.values() {
202            if let Some(oid) = extract_object_id(val) {
203                worklist.push(oid);
204            }
205        }
206
207        // Trace object graph (BFS)
208        while let Some(oid) = worklist.pop() {
209            if oid >= self.arena.objects.len() {
210                continue;
211            }
212            if let Some(cell) = &self.arena.objects[oid] {
213                if cell.marked {
214                    continue;
215                }
216            } else {
217                continue;
218            }
219
220            // Mark this object
221            if let Some(cell) = &mut self.arena.objects[oid] {
222                cell.marked = true;
223
224                // Trace properties
225                let props: Vec<JsValue> = cell.data.properties.values().cloned().collect();
226                for val in &props {
227                    if let Some(child_oid) = extract_object_id(val) {
228                        worklist.push(child_oid);
229                    }
230                }
231
232                // Trace prototype chain
233                if let Some(proto) = cell.data.prototype {
234                    worklist.push(proto);
235                }
236            }
237        }
238    }
239
240    /// Sweep phase: free unmarked objects
241    fn sweep_phase(&mut self) {
242        for i in 0..self.arena.objects.len() {
243            let should_free = if let Some(cell) = &self.arena.objects[i] {
244                !cell.marked
245            } else {
246                false
247            };
248
249            if should_free {
250                if let Some(cell) = self.arena.objects[i].take() {
251                    self.arena.bytes_allocated =
252                        self.arena.bytes_allocated.saturating_sub(cell.size);
253                    self.arena.live_count = self.arena.live_count.saturating_sub(1);
254                    self.arena.free_list.push(i);
255                }
256            }
257        }
258    }
259
260    /// Check if a collection should be triggered
261    pub fn should_collect(&self) -> bool {
262        self.arena.should_collect()
263    }
264}
265
266// ---------------------------------------------------------------------------
267// Helpers
268// ---------------------------------------------------------------------------
269
270/// Extract ObjectId from a JsValue if it refers to an object
271fn extract_object_id(val: &JsValue) -> Option<ObjectId> {
272    match val {
273        JsValue::Object(oid) => Some(*oid),
274        _ => None,
275    }
276}
277
278/// Estimate the memory size of a JsObject in bytes
279fn estimate_object_size(obj: &JsObject) -> usize {
280    let base = 64; // struct overhead
281    let props: usize = obj.properties.keys().map(|k| k.len() + 32).sum();
282    base + props
283}
284
285// ---------------------------------------------------------------------------
286// Tests
287// ---------------------------------------------------------------------------
288
289#[cfg(test)]
290mod tests {
291    use alloc::collections::BTreeMap;
292    #[allow(unused_imports)]
293    use alloc::vec;
294
295    use super::*;
296
297    fn make_vm() -> JsVm {
298        JsVm::new()
299    }
300
301    #[test]
302    fn test_gc_arena_allocate() {
303        let mut arena = GcArena::new();
304        let id = arena.allocate(JsObject::new());
305        assert_eq!(id, 0);
306        assert_eq!(arena.live_count(), 1);
307        assert!(arena.bytes_allocated() > 0);
308    }
309
310    #[test]
311    fn test_gc_arena_get() {
312        let mut arena = GcArena::new();
313        let mut obj = JsObject::new();
314        obj.set("x", JsValue::Number(42));
315        let id = arena.allocate(obj);
316
317        let retrieved = arena.get(id).unwrap();
318        assert!(retrieved.properties.contains_key("x"));
319    }
320
321    #[test]
322    fn test_gc_arena_get_mut() {
323        let mut arena = GcArena::new();
324        let id = arena.allocate(JsObject::new());
325        arena.get_mut(id).unwrap().set("y", JsValue::Boolean(true));
326        assert!(arena.get(id).unwrap().properties.contains_key("y"));
327    }
328
329    #[test]
330    fn test_gc_arena_free_list() {
331        let mut arena = GcArena::new();
332        let _id0 = arena.allocate(JsObject::new());
333        let _id1 = arena.allocate(JsObject::new());
334        assert_eq!(arena.live_count(), 2);
335        assert_eq!(arena.capacity(), 2);
336    }
337
338    #[test]
339    fn test_gc_heap_allocate() {
340        let mut heap = GcHeap::new();
341        let id = heap.allocate(JsObject::new());
342        assert_eq!(id, 0);
343        assert_eq!(heap.arena.live_count(), 1);
344    }
345
346    #[test]
347    fn test_gc_collect_empty() {
348        let mut heap = GcHeap::new();
349        let vm = make_vm();
350        heap.collect(&vm);
351        assert_eq!(heap.arena.collection_count(), 1);
352    }
353
354    #[test]
355    fn test_gc_collect_unreachable() {
356        let mut heap = GcHeap::new();
357        heap.allocate(JsObject::new());
358        heap.allocate(JsObject::new());
359        assert_eq!(heap.arena.live_count(), 2);
360
361        // No roots referencing these objects
362        let vm = make_vm();
363        heap.collect(&vm);
364
365        // Both should be swept
366        assert_eq!(heap.arena.live_count(), 0);
367        assert_eq!(heap.arena.free_list.len(), 2);
368    }
369
370    #[test]
371    fn test_gc_collect_reachable_from_stack() {
372        let mut heap = GcHeap::new();
373        let oid = heap.allocate(JsObject::new());
374        let _unreachable = heap.allocate(JsObject::new());
375
376        let mut vm = make_vm();
377        vm.stack.push(JsValue::Object(oid));
378
379        heap.collect(&vm);
380
381        // Only the reachable one survives
382        assert_eq!(heap.arena.live_count(), 1);
383        assert!(heap.arena.get(oid).is_some());
384    }
385
386    #[test]
387    fn test_gc_collect_reachable_from_globals() {
388        let mut heap = GcHeap::new();
389        let oid = heap.allocate(JsObject::new());
390        let _dead = heap.allocate(JsObject::new());
391
392        let mut vm = make_vm();
393        vm.globals.insert("alive".into(), JsValue::Object(oid));
394
395        heap.collect(&vm);
396        assert_eq!(heap.arena.live_count(), 1);
397    }
398
399    #[test]
400    fn test_gc_collect_transitive() {
401        let mut heap = GcHeap::new();
402        let child = heap.allocate(JsObject::new());
403        let mut parent = JsObject::new();
404        parent.set("child", JsValue::Object(child));
405        let parent_id = heap.allocate(parent);
406
407        let mut vm = make_vm();
408        vm.stack.push(JsValue::Object(parent_id));
409
410        heap.collect(&vm);
411
412        // Both parent and child survive (transitive reachability)
413        assert_eq!(heap.arena.live_count(), 2);
414    }
415
416    #[test]
417    fn test_gc_reuse_freed_slot() {
418        let mut heap = GcHeap::new();
419        let _id0 = heap.allocate(JsObject::new());
420        let _id1 = heap.allocate(JsObject::new());
421
422        let vm = make_vm();
423        heap.collect(&vm);
424
425        // Free list should have 2 entries
426        assert_eq!(heap.arena.free_list.len(), 2);
427
428        // Next allocation reuses a freed slot
429        let id2 = heap.allocate(JsObject::new());
430        assert!(id2 <= 1); // should reuse 0 or 1
431    }
432
433    #[test]
434    fn test_gc_should_collect() {
435        let heap = GcHeap::new();
436        assert!(!heap.should_collect());
437    }
438
439    #[test]
440    fn test_gc_arena_default() {
441        let arena = GcArena::default();
442        assert_eq!(arena.live_count(), 0);
443        assert_eq!(arena.bytes_allocated(), 0);
444        assert_eq!(arena.collection_count(), 0);
445    }
446
447    #[test]
448    fn test_gc_heap_default() {
449        let heap = GcHeap::default();
450        assert_eq!(heap.arena.live_count(), 0);
451    }
452
453    #[test]
454    fn test_gc_cell_new() {
455        let obj = JsObject::new();
456        let cell = GcCell::new(obj);
457        assert!(!cell.marked);
458        assert!(cell.size > 0);
459    }
460
461    #[test]
462    fn test_estimate_object_size() {
463        let mut obj = JsObject::new();
464        let base_size = estimate_object_size(&obj);
465        obj.set("key", JsValue::Number(0));
466        let with_prop = estimate_object_size(&obj);
467        assert!(with_prop > base_size);
468    }
469
470    #[test]
471    fn test_extract_object_id() {
472        assert_eq!(extract_object_id(&JsValue::Object(5)), Some(5));
473        assert_eq!(extract_object_id(&JsValue::Number(42)), None);
474        assert_eq!(extract_object_id(&JsValue::Null), None);
475        assert_eq!(extract_object_id(&JsValue::Function(3)), None);
476    }
477
478    #[test]
479    fn test_gc_collect_prototype_chain() {
480        let mut heap = GcHeap::new();
481        let proto = heap.allocate(JsObject::new());
482        let mut child = JsObject::new();
483        child.prototype = Some(proto);
484        let child_id = heap.allocate(child);
485
486        let mut vm = make_vm();
487        vm.stack.push(JsValue::Object(child_id));
488
489        heap.collect(&vm);
490        // Both child and prototype survive
491        assert_eq!(heap.arena.live_count(), 2);
492    }
493
494    #[test]
495    fn test_gc_multiple_collections() {
496        let mut heap = GcHeap::new();
497        let vm = make_vm();
498
499        heap.allocate(JsObject::new());
500        heap.collect(&vm);
501        assert_eq!(heap.arena.collection_count(), 1);
502
503        heap.allocate(JsObject::new());
504        heap.collect(&vm);
505        assert_eq!(heap.arena.collection_count(), 2);
506        assert_eq!(heap.arena.live_count(), 0);
507    }
508
509    #[test]
510    fn test_gc_collect_with_call_frame_locals() {
511        use super::super::{js_compiler::FunctionTemplate, js_vm::CallFrame};
512
513        let mut heap = GcHeap::new();
514        let oid = heap.allocate(JsObject::new());
515
516        let mut vm = make_vm();
517        vm.call_stack.push(CallFrame {
518            function_id: 0,
519            ip: 0,
520            base_slot: 0,
521            locals: vec![JsValue::Object(oid)],
522            bytecode: Vec::new(),
523            constants: Vec::new(),
524        });
525
526        heap.collect(&vm);
527        assert_eq!(heap.arena.live_count(), 1);
528    }
529
530    #[test]
531    fn test_gc_threshold_grows() {
532        let mut heap = GcHeap::new();
533        let initial_threshold = heap.arena.threshold;
534
535        // Allocate enough to exceed half threshold
536        for _ in 0..100_000 {
537            heap.allocate(JsObject::new());
538        }
539
540        let mut vm = make_vm();
541        // Keep all alive via globals
542        for i in 0..heap.arena.objects.len() {
543            if heap.arena.objects[i].is_some() {
544                vm.globals
545                    .insert(alloc::format!("o{}", i), JsValue::Object(i));
546            }
547        }
548
549        heap.collect(&vm);
550
551        if heap.arena.bytes_allocated > initial_threshold / 2 {
552            assert!(heap.arena.threshold > initial_threshold);
553        }
554    }
555
556    #[test]
557    fn test_gc_arena_invalid_get() {
558        let arena = GcArena::new();
559        assert!(arena.get(999).is_none());
560    }
561}
veridian_kernel/browser/js_gc.rs

veridian_kernel/browser/
js_gc.rs
