mmtk/plan/lxr/gc_work/
tracing.rs

1use super::super::LXR;
2use super::ProcessEdgesBase;
3use crate::plan::concurrent::Pause;
4use crate::plan::PlanTraceObject;
5use crate::plan::VectorQueue;
6use crate::policy::gc_work::DEFAULT_TRACE;
7use crate::policy::immix::block::Block;
8use crate::policy::space::Space;
9use crate::scheduler::RootKind;
10use crate::util::copy::CopySemantics;
11use crate::util::linear_scan::UnstraddlableRegion;
12use crate::util::rc::RefCountHelper;
13use crate::util::{ObjectReference, VMThread};
14use crate::vm::slot::Slot;
15use crate::{
16    plan::ObjectQueue,
17    scheduler::{GCWork, GCWorker, WorkBucketStage},
18    vm::*,
19    MMTK,
20};
21use atomic::Ordering;
22use std::ops::{Deref, DerefMut};
23use std::sync::Arc;
24
25pub struct LXRConcurrentTraceObjects<VM: VMBinding> {
26    plan: &'static LXR<VM>,
27    // objects to mark and scan
28    objects: Option<Vec<ObjectReference>>,
29    objects_arc: Option<Arc<Vec<ObjectReference>>>,
30    // recursively generated objects
31    next_objects: VectorQueue<ObjectReference>,
32    rc: RefCountHelper<VM>,
33    worker: *mut GCWorker<VM>,
34}
35
36impl<VM: VMBinding> LXRConcurrentTraceObjects<VM> {
37    const SATB_BUFFER_SIZE: usize = 8192;
38
39    pub fn new(objects: Vec<ObjectReference>, mmtk: &'static MMTK<VM>) -> Self {
40        let plan = mmtk.get_plan().downcast_ref::<LXR<VM>>().unwrap();
41        super::super::NUM_CONCURRENT_TRACING_PACKETS.fetch_add(1, Ordering::SeqCst);
42        Self {
43            plan,
44            objects: Some(objects),
45            objects_arc: None,
46            next_objects: VectorQueue::default(),
47            rc: RefCountHelper::NEW,
48            worker: std::ptr::null_mut(),
49        }
50    }
51
52    pub fn new_arc(objects: Arc<Vec<ObjectReference>>, mmtk: &'static MMTK<VM>) -> Self {
53        let plan = mmtk.get_plan().downcast_ref::<LXR<VM>>().unwrap();
54        super::super::NUM_CONCURRENT_TRACING_PACKETS.fetch_add(1, Ordering::SeqCst);
55        Self {
56            plan,
57            objects: None,
58            objects_arc: Some(objects),
59            next_objects: VectorQueue::default(),
60            rc: RefCountHelper::NEW,
61            worker: std::ptr::null_mut(),
62        }
63    }
64
65    #[cold]
66    fn flush(&mut self) {
67        if !self.next_objects.is_empty() {
68            let objects = self.next_objects.take();
69            let worker = unsafe { &mut *self.worker };
70            debug_assert!(self.plan.cm_enabled());
71            let w = Self::new(objects, worker.mmtk);
72            worker.add_work(WorkBucketStage::ConcurrentResumable, w);
73        }
74    }
75
76    fn trace_object(&mut self, object: ObjectReference) -> ObjectReference {
77        if self.plan.immix_space.in_space(object) {
78            if self.rc.count(object) == 0 {
79                return object;
80            }
81            self.plan
82                .immix_space
83                .trace_object_without_moving_rc(self, object);
84        } else if self.plan.los().in_space(object) {
85            if self.rc.count(object) == 0 {
86                return object;
87            }
88            self.plan.los().trace_object(self, object);
89        } else {
90            // Not reference counted. Forward to common plan.
91            let worker = unsafe { &mut *self.worker };
92            self.plan
93                .common
94                .trace_object::<Self, DEFAULT_TRACE>(self, object, worker);
95        }
96        object
97    }
98
99    fn trace_objects(&mut self, objects: &[ObjectReference]) {
100        for o in objects {
101            self.trace_object(*o);
102        }
103    }
104
105    fn scan_and_enqueue<const CHECK_REMSET: bool>(&mut self, object: ObjectReference) {
106        object.iterate_fields::<VM, _>(unsafe { (*self.worker).tls }.0, |s| {
107            let Some(t) = s.load() else {
108                return;
109            };
110            if super::super::MATURE_EVACUATION && CHECK_REMSET && self.plan.in_defrag(t) {
111                self.plan.mature_evac_remset.record(s, t, self.plan);
112            }
113            self.next_objects.push(t);
114            if self.next_objects.len() > Self::SATB_BUFFER_SIZE {
115                self.flush();
116            }
117        });
118    }
119}
120
121impl<VM: VMBinding> ObjectQueue for LXRConcurrentTraceObjects<VM> {
122    fn enqueue(&mut self, object: ObjectReference) {
123        if cfg!(feature = "sanity") {
124            assert!(
125                object.to_raw_address().is_mapped(),
126                "Invalid obj {:?}: address is not mapped",
127                object
128            );
129        }
130        let should_check_remset = !self.plan.in_defrag(object);
131        if should_check_remset {
132            self.scan_and_enqueue::<true>(object)
133        } else {
134            self.scan_and_enqueue::<false>(object)
135        }
136    }
137}
138
139unsafe impl<VM: VMBinding> Send for LXRConcurrentTraceObjects<VM> {}
140
141impl<VM: VMBinding> GCWork<VM> for LXRConcurrentTraceObjects<VM> {
142    fn do_work(&mut self, worker: &mut GCWorker<VM>, mmtk: &'static MMTK<VM>) {
143        self.worker = worker;
144        debug_assert!(!mmtk.scheduler.work_buckets[WorkBucketStage::RCProcessIncs].is_open());
145        // mark objects
146        if let Some(objects) = self.objects.take() {
147            self.trace_objects(&objects)
148        } else if let Some(objects) = self.objects_arc.take() {
149            self.trace_objects(&objects)
150        }
151        let pause_opt = self.plan.current_pause();
152        if pause_opt == Some(Pause::FinalMark) || pause_opt.is_none() {
153            let mut next_objects = vec![];
154            while !self.next_objects.is_empty() {
155                let pause_opt = self.plan.current_pause();
156                if !(pause_opt == Some(Pause::FinalMark) || pause_opt.is_none()) {
157                    break;
158                }
159                next_objects.clear();
160                self.next_objects.swap(&mut next_objects);
161                self.trace_objects(&next_objects);
162            }
163        }
164        self.flush();
165        // CM: Decrease counter
166        super::super::NUM_CONCURRENT_TRACING_PACKETS.fetch_sub(1, Ordering::SeqCst);
167        debug_assert!(!mmtk.scheduler.work_buckets[WorkBucketStage::RCProcessIncs].is_open());
168    }
169}
170
171pub struct ProcessModBufSATB {
172    nodes: Option<Vec<ObjectReference>>,
173    nodes_arc: Option<Arc<Vec<ObjectReference>>>,
174}
175
176impl ProcessModBufSATB {
177    pub fn new(nodes: Vec<ObjectReference>) -> Self {
178        // super::NUM_CONCURRENT_TRACING_PACKETS.fetch_add(1, Ordering::SeqCst);
179        Self {
180            nodes: Some(nodes),
181            nodes_arc: None,
182        }
183    }
184    pub fn new_arc(nodes: Arc<Vec<ObjectReference>>) -> Self {
185        // super::NUM_CONCURRENT_TRACING_PACKETS.fetch_add(1, Ordering::SeqCst);
186        Self {
187            nodes: None,
188            nodes_arc: Some(nodes),
189        }
190    }
191}
192
193impl<VM: VMBinding> GCWork<VM> for ProcessModBufSATB {
194    fn do_work(&mut self, worker: &mut GCWorker<VM>, mmtk: &'static MMTK<VM>) {
195        let mut w = if let Some(nodes) = self.nodes.take() {
196            if nodes.is_empty() {
197                return;
198            }
199            if cfg!(any(feature = "sanity", debug_assertions)) {
200                for o in &nodes {
201                    assert!(
202                        o.to_raw_address().is_mapped(),
203                        "Invalid object {:?}: address is not mapped",
204                        o
205                    );
206                }
207            }
208            LXRConcurrentTraceObjects::new(nodes, mmtk)
209        } else if let Some(nodes) = self.nodes_arc.take() {
210            if nodes.is_empty() {
211                return;
212            }
213            if cfg!(any(feature = "sanity", debug_assertions)) {
214                for o in &*nodes {
215                    assert!(
216                        o.to_raw_address().is_mapped(),
217                        "Invalid object {:?}: address is not mapped",
218                        o
219                    );
220                }
221            }
222            LXRConcurrentTraceObjects::new_arc(nodes, mmtk)
223        } else {
224            return;
225        };
226
227        let current_pause = mmtk
228            .get_plan()
229            .downcast_ref::<LXR<VM>>()
230            .unwrap()
231            .current_pause();
232        if current_pause != Some(Pause::FinalMark) {
233            worker.scheduler().work_buckets[WorkBucketStage::ConcurrentResumable].add(w);
234        } else {
235            GCWork::do_work(&mut w, worker, mmtk);
236        }
237    }
238}
239
240pub struct LXRStopTheWorldProcessEdges<VM: VMBinding, const FULL_GC: bool> {
241    lxr: &'static LXR<VM>,
242    pause: Pause,
243    base: ProcessEdgesBase<VM>,
244    forwarded_roots: Vec<ObjectReference>,
245    next_slots: VectorQueue<VM::VMSlot>,
246    next_slot_count: u32,
247    remset_recorded_slots: bool,
248    should_record_forwarded_roots: bool,
249}
250
251impl<VM: VMBinding, const FULL_GC: bool> LXRStopTheWorldProcessEdges<VM, FULL_GC> {
252    const OVERWRITE_REFERENCE: bool = super::super::MATURE_EVACUATION;
253
254    pub fn new_remset(slots: Vec<VM::VMSlot>, mmtk: &'static MMTK<VM>) -> Self {
255        let mut me = Self::new(slots, false, mmtk, WorkBucketStage::Closure);
256        me.remset_recorded_slots = true;
257        me
258    }
259
260    pub fn new(
261        slots: Vec<VM::VMSlot>,
262        roots: bool,
263        mmtk: &'static MMTK<VM>,
264        bucket: WorkBucketStage,
265    ) -> Self {
266        let base = ProcessEdgesBase::new(slots, roots, mmtk, bucket);
267        let lxr = base.plan().downcast_ref::<LXR<VM>>().unwrap();
268        Self {
269            lxr,
270            base,
271            pause: Pause::RefCount,
272            forwarded_roots: vec![],
273            next_slots: VectorQueue::new(),
274            next_slot_count: 0,
275            remset_recorded_slots: false,
276            should_record_forwarded_roots: false,
277        }
278    }
279
280    #[cold]
281    fn flush(&mut self) {
282        if !self.next_slots.is_empty() {
283            let slots = self.next_slots.take();
284            let w = Self::new(slots, false, self.mmtk(), self.bucket);
285            self.worker()
286                .add_boxed_work(WorkBucketStage::Unconstrained, Box::new(w));
287        }
288        assert!(self.nodes.is_empty());
289        self.next_slot_count = 0;
290    }
291
292    fn process_slots(&mut self) {
293        self.should_record_forwarded_roots = self.roots
294            && !self
295                .root_kind
296                .map(|r| r.should_skip_decs())
297                .unwrap_or_default();
298        self.pause = self.lxr.current_pause().unwrap();
299        if self.should_record_forwarded_roots {
300            self.forwarded_roots.reserve(self.slots.len());
301        }
302        let slots = std::mem::take(&mut self.slots);
303        if self.roots && self.root_kind == Some(RootKind::Weak) {
304            self.process_slots_impl::<true, false>(&slots);
305        } else if self.remset_recorded_slots {
306            self.process_slots_impl::<false, true>(&slots);
307        } else {
308            self.process_slots_impl::<false, false>(&slots);
309        }
310        self.roots = false;
311        self.remset_recorded_slots = false;
312        let should_record_forwarded_roots = self.should_record_forwarded_roots;
313        self.should_record_forwarded_roots = false;
314        let mut slots = vec![];
315        while !self.next_slots.is_empty() {
316            self.next_slot_count = 0;
317            slots.clear();
318            self.next_slots.swap(&mut slots);
319            self.process_slots_impl::<false, false>(&slots);
320        }
321        self.flush();
322        if should_record_forwarded_roots {
323            let roots = std::mem::take(&mut self.forwarded_roots);
324            self.lxr.curr_roots.read().unwrap().push(roots);
325        }
326    }
327}
328
329impl<VM: VMBinding, const FULL_GC: bool> GCWork<VM> for LXRStopTheWorldProcessEdges<VM, FULL_GC> {
330    fn do_work(&mut self, worker: &mut GCWorker<VM>, _mmtk: &'static MMTK<VM>) {
331        self.set_worker(worker);
332        self.process_slots();
333        if !self.nodes.is_empty() {
334            self.flush();
335        }
336    }
337}
338
339impl<VM: VMBinding, const FULL_GC: bool> LXRStopTheWorldProcessEdges<VM, FULL_GC> {
340    #[inline]
341    fn full_gc_trace_object<const WEAK_ROOT: bool>(
342        &mut self,
343        object: ObjectReference,
344    ) -> ObjectReference {
345        debug_assert!(FULL_GC);
346        debug_assert!(object.is_in_any_space());
347        debug_assert!(object.to_raw_address().is_aligned_to(8));
348        // debug_assert!(object.class_is_valid::<VM>());
349        let in_immix_space = self.lxr.immix_space.in_space(object);
350        if WEAK_ROOT && !(in_immix_space && Block::containing(object).is_defrag_source()) {
351            return object;
352        }
353        let x = if in_immix_space {
354            let pause = self.pause;
355            let worker = self.worker();
356            self.lxr.immix_space.rc_trace_object(
357                self,
358                object,
359                CopySemantics::DefaultCopy,
360                pause,
361                true,
362                worker,
363            )
364        } else if self.lxr.los().in_space(object) {
365            self.lxr.los().trace_object(self, object)
366        } else {
367            let worker = self.worker();
368            self.lxr
369                .common
370                .trace_object::<Self, DEFAULT_TRACE>(self, object, worker)
371        };
372        if self.should_record_forwarded_roots {
373            self.forwarded_roots.push(x)
374        }
375        x
376    }
377
378    #[inline]
379    fn mature_evac_trace_object<const WEAK_ROOT: bool, const REMSET: bool>(
380        &mut self,
381        object: ObjectReference,
382    ) -> ObjectReference {
383        debug_assert!(!FULL_GC);
384        // The memory (lines) of these slots can be reused at any time during mature evacuation.
385        // Filter out invalid target objects.
386        if REMSET && (!object.is_in_any_space() || !object.to_raw_address().is_aligned_to(8)) {
387            return object;
388        }
389        let in_immix_space = self.lxr.immix_space.in_space(object);
390        let in_common_space = !in_immix_space && !self.lxr.los().in_space(object);
391        // A zero reference count means the object is dead, but only for the spaces LXR
392        // reference counts.
393        if !in_common_space && self.lxr.rc.count(object) == 0 {
394            return object;
395        }
396        if WEAK_ROOT && !(in_immix_space && Block::containing(object).is_defrag_source()) {
397            return object;
398        }
399        debug_assert!(object.is_in_any_space(), "Invalid {:?}", object);
400        debug_assert!(
401            object.to_raw_address().is_aligned_to(8),
402            "Invalid {:?} remset={}",
403            object,
404            self.remset_recorded_slots
405        );
406        let object = object.get_forwarded_object().unwrap_or(object);
407        let new_object = if self.lxr.immix_space.in_space(object) {
408            if self.lxr.rc.object_is_in_straddle_line(object) {
409                return object;
410            }
411            let pause = self.pause;
412            let worker = self.worker();
413            self.lxr.immix_space.rc_trace_object(
414                self,
415                object,
416                CopySemantics::DefaultCopy,
417                pause,
418                true,
419                worker,
420            )
421        } else if self.lxr.los().in_space(object) {
422            self.lxr.los().trace_object(self, object)
423        } else {
424            let worker = self.worker();
425            self.lxr
426                .common
427                .trace_object::<Self, DEFAULT_TRACE>(self, object, worker)
428        };
429        if self.should_record_forwarded_roots {
430            self.forwarded_roots.push(new_object)
431        }
432        new_object
433    }
434
435    #[inline]
436    fn __process_slot<const WEAK_ROOT: bool, const REMSET: bool>(&mut self, slot: VM::VMSlot) {
437        let Some(object) = slot.load() else {
438            return;
439        };
440        let new_object = if !FULL_GC {
441            self.mature_evac_trace_object::<WEAK_ROOT, REMSET>(object)
442        } else {
443            self.full_gc_trace_object::<WEAK_ROOT>(object)
444        };
445        if Self::OVERWRITE_REFERENCE && new_object != object {
446            slot.store(new_object);
447        }
448    }
449
450    fn process_slots_impl<const WEAK_ROOT: bool, const REMSET: bool>(
451        &mut self,
452        slots: &[VM::VMSlot],
453    ) {
454        for s in slots {
455            self.__process_slot::<WEAK_ROOT, REMSET>(*s);
456        }
457    }
458}
459
460impl<VM: VMBinding, const FULL_GC: bool> ObjectQueue for LXRStopTheWorldProcessEdges<VM, FULL_GC> {
461    fn enqueue(&mut self, object: ObjectReference) {
462        let limit: usize = if FULL_GC { 8192 } else { 1024 };
463        // TODO: Use actual TLS.
464        object.iterate_fields::<VM, _>(VMThread::UNINITIALIZED, |s| {
465            let Some(o) = s.load() else {
466                return;
467            };
468            if self.lxr.is_rc_object(o) && self.lxr.is_marked(o) && !self.lxr.in_defrag(o) {
469                return;
470            }
471            self.next_slots.push(s);
472            self.next_slot_count += 1;
473            if self.next_slot_count as usize >= limit {
474                self.flush();
475            }
476        });
477    }
478}
479
480impl<VM: VMBinding, const FULL_GC: bool> Deref for LXRStopTheWorldProcessEdges<VM, FULL_GC> {
481    type Target = ProcessEdgesBase<VM>;
482    fn deref(&self) -> &Self::Target {
483        &self.base
484    }
485}
486
487impl<VM: VMBinding, const FULL_GC: bool> DerefMut for LXRStopTheWorldProcessEdges<VM, FULL_GC> {
488    fn deref_mut(&mut self) -> &mut Self::Target {
489        &mut self.base
490    }
491}
492
493/// Stop-the-world tracing of roots reported as objects rather than as slots.
494pub struct LXRStopTheWorldProcessNodes<VM: VMBinding, const FULL_GC: bool> {
495    lxr: &'static LXR<VM>,
496    mmtk: &'static MMTK<VM>,
497    // Use a raw pointer for the same reason `ProcessEdgesBase` does: this is dereferenced on
498    // every traced object.
499    worker: *mut GCWorker<VM>,
500    /// The root objects to mark. These must not move.
501    nodes: Vec<ObjectReference>,
502    /// Fields of the marked roots, handed on to the slot-based closure.
503    next_slots: VectorQueue<VM::VMSlot>,
504    next_slot_count: u32,
505    /// The bucket the slot closure over the roots' children runs in.
506    closure_bucket: WorkBucketStage,
507}
508
509unsafe impl<VM: VMBinding, const FULL_GC: bool> Send for LXRStopTheWorldProcessNodes<VM, FULL_GC> {}
510
511impl<VM: VMBinding, const FULL_GC: bool> LXRStopTheWorldProcessNodes<VM, FULL_GC> {
512    pub fn new(
513        nodes: Vec<ObjectReference>,
514        mmtk: &'static MMTK<VM>,
515        closure_bucket: WorkBucketStage,
516    ) -> Self {
517        let lxr = mmtk.get_plan().downcast_ref::<LXR<VM>>().unwrap();
518        Self {
519            lxr,
520            mmtk,
521            worker: std::ptr::null_mut(),
522            nodes,
523            next_slots: VectorQueue::new(),
524            next_slot_count: 0,
525            closure_bucket,
526        }
527    }
528
529    fn worker(&self) -> &'static mut GCWorker<VM> {
530        unsafe { &mut *self.worker }
531    }
532
533    #[cold]
534    fn flush(&mut self) {
535        if !self.next_slots.is_empty() {
536            let slots = self.next_slots.take();
537            let bucket = self.closure_bucket;
538            let w =
539                LXRStopTheWorldProcessEdges::<VM, FULL_GC>::new(slots, false, self.mmtk, bucket);
540            self.worker().add_work(bucket, w);
541        }
542        self.next_slot_count = 0;
543    }
544
545    /// Mark `object` without moving it. This mirrors the per-space dispatch of
546    /// [`LXRStopTheWorldProcessEdges::mature_evac_trace_object`] minus every path that could
547    /// evacuate.
548    fn trace_object(&mut self, object: ObjectReference) -> ObjectReference {
549        debug_assert!(object.is_in_any_space(), "Invalid {:?}", object);
550        let in_immix_space = self.lxr.immix_space.in_space(object);
551        let in_common_space = !in_immix_space && !self.lxr.los().in_space(object);
552        // A zero reference count means the object is dead, but only for the spaces LXR
553        // reference counts.
554        if !in_common_space && self.lxr.rc.count(object) == 0 {
555            return object;
556        }
557        if in_immix_space {
558            self.lxr
559                .immix_space
560                .trace_object_without_moving_rc(self, object)
561        } else if !in_common_space {
562            self.lxr.los().trace_object(self, object)
563        } else {
564            // Not reference counted. Forward to the common plan.
565            let worker = self.worker();
566            self.lxr
567                .common
568                .trace_object::<Self, DEFAULT_TRACE>(self, object, worker)
569        }
570    }
571}
572
573impl<VM: VMBinding, const FULL_GC: bool> ObjectQueue for LXRStopTheWorldProcessNodes<VM, FULL_GC> {
574    fn enqueue(&mut self, object: ObjectReference) {
575        let limit: usize = if FULL_GC { 8192 } else { 1024 };
576        // TODO: Use actual TLS.
577        object.iterate_fields::<VM, _>(VMThread::UNINITIALIZED, |s| {
578            let Some(o) = s.load() else {
579                return;
580            };
581            if self.lxr.is_rc_object(o) && self.lxr.is_marked(o) && !self.lxr.in_defrag(o) {
582                return;
583            }
584            self.next_slots.push(s);
585            self.next_slot_count += 1;
586            if self.next_slot_count as usize >= limit {
587                self.flush();
588            }
589        });
590    }
591}
592
593impl<VM: VMBinding, const FULL_GC: bool> GCWork<VM> for LXRStopTheWorldProcessNodes<VM, FULL_GC> {
594    fn do_work(&mut self, worker: &mut GCWorker<VM>, _mmtk: &'static MMTK<VM>) {
595        self.worker = worker;
596        let nodes = std::mem::take(&mut self.nodes);
597        for object in nodes {
598            let new_object = self.trace_object(object);
599            debug_assert_eq!(
600                object, new_object,
601                "Root node {} moved to {}: a root reported as an object has no slot to update",
602                object, new_object
603            );
604        }
605        self.flush();
606    }
607}
mmtk/plan/lxr/gc_work/tracing.rs

mmtk/plan/lxr/gc_work/
tracing.rs
