mmtk/util/
treadmill.rs

1use std::collections::HashSet;
2use std::mem::swap;
3use std::sync::Mutex;
4
5use crate::util::ObjectReference;
6
7use super::object_enum::ObjectEnumerator;
8
9/// A data structure for recording objects in the LOS.
10///
11/// All operations are protected by a single mutex [`TreadMill::sync`].
12pub struct TreadMill {
13    sync: Mutex<TreadMillSync>,
14}
15
16/// The synchronized part of [`TreadMill`]
17#[derive(Default)]
18struct TreadMillSync {
19    /// The from-space.  During GC, it contains old objects with unknown liveness.
20    from_space: HashSet<ObjectReference>,
21    /// The to-space.  During mutator time, it contains old objects; during GC, it contains objects
22    /// determined to be live.
23    to_space: HashSet<ObjectReference>,
24    /// The collection nursery.  During GC, it contains young objects with unknown liveness.
25    collect_nursery: HashSet<ObjectReference>,
26    /// The allocation nursery.  During mutator time, it contains young objects; during GC, it
27    /// remains empty.
28    alloc_nursery: HashSet<ObjectReference>,
29}
30
31impl std::fmt::Debug for TreadMill {
32    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
33        let sync = self.sync.lock().unwrap();
34        f.debug_struct("TreadMill")
35            .field("from_space", &sync.from_space)
36            .field("to_space", &sync.to_space)
37            .field("collect_nursery", &sync.collect_nursery)
38            .field("alloc_nursery", &sync.alloc_nursery)
39            .finish()
40    }
41}
42
43impl TreadMill {
44    pub fn new() -> Self {
45        TreadMill {
46            sync: Mutex::new(Default::default()),
47        }
48    }
49
50    /// Add an object to the treadmill.
51    ///
52    /// New objects are normally added to `alloc_nursery`.  But when allocating as live (e.g. when
53    /// concurrent marking is active), we directly add into the `to_space`.
54    pub fn add_to_treadmill(&self, object: ObjectReference, nursery: bool) {
55        let mut sync = self.sync.lock().unwrap();
56        if nursery {
57            trace!("Adding {} to alloc_nursery", object);
58            sync.alloc_nursery.insert(object);
59        } else {
60            trace!("Adding {} to to_space", object);
61            sync.to_space.insert(object);
62        }
63    }
64
65    /// Take all objects from the `collect_nursery`.  This is called during sweeping at which time
66    /// all unreachable young objects are in the collection nursery.
67    pub fn collect_nursery(&self) -> impl IntoIterator<Item = ObjectReference> {
68        let mut sync = self.sync.lock().unwrap();
69        std::mem::take(&mut sync.collect_nursery)
70    }
71
72    /// Take all objects from the `alloc_nursery`.
73    pub fn collect_alloc_nursery(&self) -> impl IntoIterator<Item = ObjectReference> {
74        let mut sync = self.sync.lock().unwrap();
75        std::mem::take(&mut sync.alloc_nursery)
76    }
77
78    /// Take all objects from the `from_space`.  This is called during sweeping at which time all
79    /// unreachable old objects are in the from-space.
80    pub fn collect_mature(&self) -> impl IntoIterator<Item = ObjectReference> {
81        let mut sync = self.sync.lock().unwrap();
82        std::mem::take(&mut sync.from_space)
83    }
84
85    /// Retain objects in the to-space that satisfy the given predicate.  This is called during LXR's SATB sweeping
86    pub fn retain_mature(&self, f: impl FnMut(&ObjectReference) -> bool) {
87        let mut sync = self.sync.lock().unwrap();
88        sync.to_space.retain(f);
89    }
90
91    /// Remove an object from whichever set contains it.  Returns true if the object was found.
92    /// Called by `rc_free` when an object's reference count reaches zero.
93    pub fn remove_mature(&self, object: ObjectReference) -> bool {
94        let mut sync = self.sync.lock().unwrap();
95        assert!(sync.from_space.is_empty());
96        sync.to_space.remove(&object)
97    }
98
99    /// Move an object to `to_space`.  Called when an object is determined to be reachable.
100    pub fn copy(&self, object: ObjectReference, is_in_nursery: bool) {
101        let mut sync = self.sync.lock().unwrap();
102        if is_in_nursery {
103            debug_assert!(
104                sync.collect_nursery.contains(&object),
105                "copy source object ({}) must be in collect_nursery",
106                object
107            );
108            sync.collect_nursery.remove(&object);
109        } else {
110            debug_assert!(
111                sync.from_space.contains(&object),
112                "copy source object ({}) must be in from_space",
113                object
114            );
115            sync.from_space.remove(&object);
116        }
117        sync.to_space.insert(object);
118    }
119
120    /// Return true if the to-space is empty.
121    pub fn is_to_space_empty(&self) -> bool {
122        let sync = self.sync.lock().unwrap();
123        sync.to_space.is_empty()
124    }
125
126    /// Return true if the from-space is empty.
127    pub fn is_from_space_empty(&self) -> bool {
128        let sync = self.sync.lock().unwrap();
129        sync.from_space.is_empty()
130    }
131
132    /// Return true if the allocation nursery is empty.
133    pub fn is_alloc_nursery_empty(&self) -> bool {
134        let sync = self.sync.lock().unwrap();
135        sync.alloc_nursery.is_empty()
136    }
137
138    /// Return true if the collection nursery is empty.
139    pub fn is_collect_nursery_empty(&self) -> bool {
140        let sync = self.sync.lock().unwrap();
141        sync.collect_nursery.is_empty()
142    }
143
144    /// Flip object sets.
145    ///
146    /// It will flip the allocation nursery and the collection nursery.
147    ///
148    /// If `full_heap` is true, it will also flip the from-space and the to-space.
149    pub fn flip(&mut self, full_heap: bool) {
150        let sync = self.sync.get_mut().unwrap();
151        swap(&mut sync.alloc_nursery, &mut sync.collect_nursery);
152        trace!("Flipped alloc_nursery and collect_nursery");
153        if full_heap {
154            swap(&mut sync.from_space, &mut sync.to_space);
155            trace!("Flipped from_space and to_space");
156        }
157    }
158
159    /// Enumerate objects.
160    ///
161    /// Objects in the allocation nursery and the to-spaces are always enumerated.  They include all
162    /// objects during mutator time, and objects determined to be live during a GC.
163    ///
164    /// If `all` is true, it will enumerate the collection nursery and the from-space, too.
165    pub(crate) fn enumerate_objects(&self, enumerator: &mut dyn ObjectEnumerator, all: bool) {
166        let sync = self.sync.lock().unwrap();
167        let mut enumerated = 0usize;
168        let mut visit_objects = |set: &HashSet<ObjectReference>| {
169            for object in set.iter() {
170                enumerator.visit_object(*object);
171                enumerated += 1;
172            }
173        };
174        visit_objects(&sync.alloc_nursery);
175        visit_objects(&sync.to_space);
176
177        if all {
178            visit_objects(&sync.collect_nursery);
179            visit_objects(&sync.from_space);
180        }
181
182        debug!("Enumerated {enumerated} objects in LOS.  all: {all}.  from_space: {fs}, to_space: {ts}, collect_nursery: {cn}, alloc_nursery: {an}",
183            fs=sync.from_space.len(),
184            ts=sync.to_space.len(),
185            cn=sync.collect_nursery.len(),
186            an=sync.alloc_nursery.len(),
187        );
188    }
189}
190
191impl Default for TreadMill {
192    fn default() -> Self {
193        Self::new()
194    }
195}
mmtk/util/treadmill.rs

mmtk/util/
treadmill.rs
