cgc_single_threaded/
heap.rs

1use crate::api::*;
2use crate::mem::*;
3
4#[cfg(not(feature = "trace-gc-timings"))]
5const TRACE_GC_TIMINGS: bool = false;
6#[cfg(feature = "trace-gc-timings")]
7const TRACE_GC_TIMINGS: bool = true;
8
9#[cfg(not(feature = "trace-gc"))]
10const TRACE_GC: bool = false;
11#[cfg(feature = "trace-gc")]
12const TRACE_GC: bool = true;
13pub struct HeapInner<T: Trace + ?Sized> {
14    forward: TaggedPointer<u8>,
15    soft_mark: bool,
16    gen: u8,
17    pub(crate) value: T,
18}
19
20impl<T: Trace + ?Sized> HeapInner<T> {
21    pub fn is_marked(&self) -> bool {
22        self.forward.bit_is_set(0)
23    }
24    pub fn set_soft_mark(&mut self) {
25        self.soft_mark = true;
26    }
27
28    pub fn is_soft_marked(&self) -> bool {
29        self.soft_mark
30    }
31
32    pub fn reset_soft_mark(&mut self) {
33        self.soft_mark = false;
34    }
35    pub fn generation(&self) -> u8 {
36        self.gen
37    }
38
39    pub fn inc_gen(&mut self) {
40        if self.gen < 5 {
41            self.gen += 1;
42        }
43    }
44    pub(crate) fn mark(&mut self, b: bool) {
45        if b {
46            self.forward.set_bit(0);
47        } else {
48            self.forward.unset_bit(0);
49        }
50    }
51
52    pub fn fwdptr(&self) -> Address {
53        Address::from(self.forward.untagged() as usize)
54    }
55
56    pub fn set_fwdptr(&mut self, addr: Address) {
57        let new_x = TaggedPointer::new(addr.to_mut_ptr::<u8>());
58        self.forward = new_x;
59    }
60}
61
62pub struct GcHandle<T: Trace + ?Sized>(pub(crate) *mut HeapInner<T>);
63pub struct RootHandle(*mut dyn RootedTrait);
64
65use super::space::*;
66
67struct GcValue {
68    slot: Address,
69
70    value: *mut HeapInner<dyn Trace>,
71}
72
73impl GcValue {
74    fn value(&self) -> &mut HeapInner<dyn Trace> {
75        unsafe { &mut *self.value }
76    }
77    fn relocate(&self, addr: Address) {
78        if self.slot.is_non_null() {
79            unsafe {
80                let slot = self.slot.to_mut_ptr::<*mut *mut u8>();
81                *slot = addr.to_mut_ptr();
82            }
83        }
84        if !self.value().is_marked() {
85            self.value().set_fwdptr(addr);
86            self.value().mark(true);
87        }
88    }
89}
90
91#[derive(Copy, Clone, PartialEq, Eq, Debug)]
92pub enum GCType {
93    None,
94    NewSpace,
95    OldSpace,
96}
97
98pub struct Heap {
99    new_space: Space,
100    old_space: Space,
101    needs_gc: GCType,
102    heap: Vec<*mut HeapInner<dyn Trace>>,
103    rootset: Vec<RootHandle>,
104    /// If this value is true then when heap is dropped GC cycle is performed to drop all values.
105    pub do_gc_after_drop: bool,
106}
107
108impl Heap {
109    pub fn root<T: Trace + Sized + 'static>(&mut self, value: Handle<T>) -> Rooted<T> {
110        let root: *mut RootedInner<T> = Box::into_raw(Box::new(RootedInner {
111            counter: 1,
112            inner: value.inner,
113        }));
114        self.rootset.push(RootHandle(root));
115        Rooted { inner: root }
116    }
117    pub fn new(new_page_size: usize, old_page_size: usize, do_gc_after_drop: bool) -> Heap {
118        Self {
119            do_gc_after_drop,
120            new_space: Space::new(page_align(new_page_size)),
121            old_space: Space::new(page_align(old_page_size)),
122            needs_gc: GCType::None,
123            heap: vec![],
124            rootset: vec![],
125        }
126    }
127
128    pub fn allocate<T: Trace + 'static>(&mut self, value: T) -> Rooted<T> {
129        let mut needs_gc = false;
130        let memory = self
131            .new_space
132            .allocate(std::mem::size_of::<HeapInner<T>>(), &mut needs_gc);
133        self.needs_gc = GCType::NewSpace;
134
135        let inner = memory.to_mut_ptr::<HeapInner<T>>();
136
137        unsafe {
138            inner.write(HeapInner {
139                forward: TaggedPointer::null(),
140                soft_mark: false,
141                gen: 0,
142                value,
143            });
144        }
145
146        let root = Box::into_raw(Box::new(RootedInner {
147            counter: 1,
148            inner: inner,
149        }));
150        self.rootset.push(RootHandle(root));
151        self.heap.push(inner);
152        Rooted { inner: root }
153    }
154
155    pub fn needs_gc(&self) -> bool {
156        self.needs_gc != GCType::None
157    }
158
159    pub fn safepoint(&mut self) {
160        if self.needs_gc() {
161            self.collect();
162        }
163    }
164
165    pub fn collect(&mut self) {
166        let time = std::time::Instant::now();
167        let mut collection = Collection {
168            gc_type: self.needs_gc,
169            tmp_space: Space::new(self.new_space.page_size),
170            heap: self,
171            grey_set: LinkedList::new(),
172            black_set: vec![],
173            new_heap: vec![],
174        };
175        collection.collect(false);
176        if TRACE_GC_TIMINGS {
177            log::trace!("GC finished in {}ns", time.elapsed().as_nanos());
178        }
179    }
180}
181
182use std::collections::LinkedList;
183impl std::hash::Hash for RootHandle {
184    fn hash<H: std::hash::Hasher>(&self, state: &mut H) {
185        (self.0 as *const u8 as usize).hash(state);
186    }
187}
188struct Collection<'a> {
189    heap: &'a mut Heap,
190    tmp_space: Space,
191    black_set: Vec<GcValue>,
192    grey_set: LinkedList<GcValue>,
193    gc_type: GCType,
194    new_heap: Vec<*mut HeapInner<dyn Trace>>,
195}
196
197impl<'a> Collection<'a> {
198    fn collect(&mut self, _: bool) {
199        let time = std::time::Instant::now();
200        let mut grey = LinkedList::new();
201        if self.gc_type == GCType::None {
202            self.gc_type = GCType::NewSpace;
203            self.heap.needs_gc = GCType::NewSpace;
204        }
205        self.tmp_space = Space::new(self.heap.new_space.page_size);
206        if TRACE_GC {
207            log::trace!("GC Type: {:?}", self.gc_type);
208        }
209
210        if TRACE_GC {
211            log::trace!("GC Phase 1: Mark roots");
212        }
213        self.heap.rootset.retain(|root| unsafe {
214            let retain;
215            if (&*root.0).is_rooted() {
216                if TRACE_GC {
217                    log::trace!(
218                        "Root {:p} identified at {:p}",
219                        (&*root.0).inner(),
220                        (&*root.0).slot().to_ptr::<u8>()
221                    );
222                }
223                let value = GcValue {
224                    slot: (*root.0).slot(),
225                    value: (&*root.0).inner(),
226                };
227                //value.value().mark(true);
228                grey.push_back(value);
229                retain = true;
230            } else {
231                let _ = Box::from_raw(root.0);
232                retain = false;
233            }
234            retain
235        });
236        self.grey_set = grey;
237        if TRACE_GC {
238            log::trace!("GC Phase 2: Copy objects");
239        }
240        self.process_grey();
241
242        let space = if self.gc_type == GCType::NewSpace {
243            &mut self.heap.new_space
244        } else {
245            &mut self.heap.old_space
246        };
247        space.swap(&mut self.tmp_space);
248        if TRACE_GC {
249            log::trace!("GC Phase 3: Finalization");
250        }
251        while let Some(item) = self.heap.heap.pop() {
252            if unsafe { !(&*item).is_marked() } && unsafe { !(&*item).is_soft_marked() } {
253                unsafe {
254                    if TRACE_GC {
255                        log::trace!("Finalize {:p}", item);
256                    }
257                    (&mut *item).value.finalize();
258                    std::ptr::drop_in_place(item);
259                }
260            }
261        }
262        while let Some(item) = self.black_set.pop() {
263            item.value().reset_soft_mark();
264        }
265        for root in self.heap.rootset.iter() {
266            unsafe {
267                self.new_heap.push((&*root.0).inner());
268                for r in (&*root.0).references() {
269                    self.new_heap.push((&*r).inner());
270                }
271            }
272        }
273        std::mem::swap(&mut self.heap.heap, &mut self.new_heap);
274        if self.gc_type != GCType::NewSpace || self.heap.needs_gc == GCType::NewSpace {
275            // Reset GC flag
276            self.heap.needs_gc = GCType::None;
277            if TRACE_GC_TIMINGS {
278                log::trace!(
279                    "GC with type {:?} finished in {}ns",
280                    self.gc_type,
281                    time.elapsed().as_nanos()
282                );
283            }
284        } else {
285            if TRACE_GC {
286                log::trace!("GC Phase 4: Restart GC for old space");
287            }
288            // Or call gc for old space.
289            self.collect(true);
290        }
291    }
292
293    fn visit(&mut self, value: &mut HeapInner<dyn Trace>) {
294        value.value.references().iter().for_each(|item| unsafe {
295            self.grey_set.push_back(GcValue {
296                slot: (&**item).slot(),
297                value: (&**item).inner(),
298            })
299        });
300    }
301    fn copy_to(
302        value: &mut HeapInner<dyn Trace>,
303        old_space: &mut Space,
304        new_space: &mut Space,
305        needs_gc: &mut GCType,
306    ) -> Address {
307        let bytes = std::mem::size_of_val(value);
308        value.inc_gen();
309        let result;
310        if value.generation() >= 5 {
311            let mut gc = false;
312            result = old_space.allocate(bytes, &mut gc);
313            if gc {
314                *needs_gc = GCType::OldSpace;
315            }
316        } else {
317            let mut gc = false;
318            result = new_space.allocate(bytes, &mut gc);
319            if gc {
320                *needs_gc = GCType::NewSpace;
321            }
322        }
323        unsafe {
324            std::ptr::copy_nonoverlapping(
325                value as *mut HeapInner<dyn Trace> as *mut u8,
326                result.to_mut_ptr::<u8>(),
327                bytes,
328            );
329        }
330        result
331    }
332    fn process_grey(&mut self) {
333        while let Some(value) = self.grey_set.pop_front() {
334            if !value.value().is_marked() {
335                if !self.is_in_current_space(value.value()) {
336                    if !value.value().is_soft_marked() {
337                        value.value().set_soft_mark();
338                        self.visit(value.value());
339                        self.new_heap.push(value.value());
340                        self.black_set.push(value);
341                    }
342                    continue;
343                }
344                let hvalue;
345                if self.gc_type == GCType::NewSpace {
346                    let mut g = GCType::None;
347                    hvalue = Self::copy_to(
348                        value.value(),
349                        &mut self.heap.old_space,
350                        &mut self.tmp_space,
351                        &mut g,
352                    );
353                    if let GCType::OldSpace = g {
354                        self.heap.needs_gc = GCType::OldSpace;
355                    }
356                } else {
357                    hvalue = Self::copy_to(
358                        value.value(),
359                        &mut self.tmp_space,
360                        &mut self.heap.new_space,
361                        &mut GCType::None,
362                    );
363                }
364                if TRACE_GC {
365                    log::trace!("Copy {:p}->{:p}", value.value(), hvalue.to_mut_ptr::<u8>());
366                }
367
368                value.relocate(hvalue);
369                self.visit(value.value());
370            } else {
371                value.relocate(value.value().fwdptr());
372            }
373        }
374    }
375
376    fn is_in_current_space(&self, val: &mut HeapInner<dyn Trace>) -> bool {
377        (self.gc_type == GCType::OldSpace && val.generation() >= 5)
378            || (self.gc_type == GCType::NewSpace && val.generation() < 5)
379    }
380}
381
382impl Drop for Heap {
383    fn drop(&mut self) {
384        self.heap.iter().for_each(|item| unsafe {
385            (&mut **item).value.finalize();
386            std::ptr::drop_in_place(*item);
387        });
388        self.old_space.clear();
389        self.new_space.clear();
390    }
391}
cgc_single_threaded/heap.rs

cgc_single_threaded/
heap.rs
