mmtk/util/
linear_scan.rs

1use crate::util::metadata::vo_bit;
2use crate::util::Address;
3use crate::util::ObjectReference;
4use crate::vm::ObjectModel;
5use crate::vm::VMBinding;
6use std::marker::PhantomData;
7
8// FIXME: Lisp2 uses linear scanning to discover allocated objects in the Lisp2Space.
9// It should use a local metadata (specific to the Lisp2Space) for that purpose.
10// In the future, we should let Lisp2 do linear scanning using its local metadata instead.
11
12/// Iterate over an address range, and find each object by VO bit.
13/// ATOMIC_LOAD_VO_BIT can be set to false if it is known that loading VO bit
14/// non-atomically is correct (e.g. a single thread is scanning this address range, and
15/// it is the only thread that accesses VO bit).
16pub struct ObjectIterator<VM: VMBinding, S: LinearScanObjectSize, const ATOMIC_LOAD_VO_BIT: bool> {
17    start: Address,
18    end: Address,
19    cursor: Address,
20    _p: PhantomData<(VM, S)>,
21}
22
23impl<VM: VMBinding, S: LinearScanObjectSize, const ATOMIC_LOAD_VO_BIT: bool>
24    ObjectIterator<VM, S, ATOMIC_LOAD_VO_BIT>
25{
26    /// Create an iterator for the address range. The caller must ensure
27    /// that the VO bit metadata is mapped for the address range.
28    pub fn new(start: Address, end: Address) -> Self {
29        debug_assert!(start < end);
30        debug_assert!(
31            start.is_aligned_to(ObjectReference::ALIGNMENT),
32            "start is not word-aligned: {start}"
33        );
34        debug_assert!(
35            end.is_aligned_to(ObjectReference::ALIGNMENT),
36            "end is not word-aligned: {end}"
37        );
38        ObjectIterator {
39            start,
40            end,
41            cursor: start,
42            _p: PhantomData,
43        }
44    }
45}
46
47impl<VM: VMBinding, S: LinearScanObjectSize, const ATOMIC_LOAD_VO_BIT: bool> std::iter::Iterator
48    for ObjectIterator<VM, S, ATOMIC_LOAD_VO_BIT>
49{
50    type Item = ObjectReference;
51
52    fn next(&mut self) -> Option<<Self as Iterator>::Item> {
53        while self.cursor < self.end {
54            let is_object = if ATOMIC_LOAD_VO_BIT {
55                vo_bit::is_vo_bit_set_for_addr(self.cursor)
56            } else {
57                unsafe { vo_bit::is_vo_bit_set_unsafe(self.cursor) }
58            };
59
60            // VO bits can only be set at addresses aligned to `ObjectReference::ALIGNMENT`.
61            if let Some(object) = is_object {
62                // The object size may not be a multiple of `ObjectReference::ALIGNMENT`.
63                self.cursor = (self.cursor + S::size(object)).align_up(ObjectReference::ALIGNMENT);
64                return Some(object);
65            } else {
66                self.cursor += ObjectReference::ALIGNMENT;
67            }
68        }
69
70        None
71    }
72}
73
74/// Describe object size for linear scan. Different policies may have
75/// different object sizes (e.g. extra metadata, etc)
76pub trait LinearScanObjectSize {
77    /// The object size in bytes for the given object.
78    fn size(object: ObjectReference) -> usize;
79}
80
81/// Default object size as ObjectModel::get_current_size()
82pub struct DefaultObjectSize<VM: VMBinding>(PhantomData<VM>);
83impl<VM: VMBinding> LinearScanObjectSize for DefaultObjectSize<VM> {
84    fn size(object: ObjectReference) -> usize {
85        VM::VMObjectModel::get_current_size(object)
86    }
87}
88
89/// Region represents a memory region with a properly aligned address as its start and a fixed size for the region.
90/// Region provides a set of utility methods, along with a RegionIterator that linearly scans at the step of a region.
91pub trait Region: Copy + PartialEq + PartialOrd {
92    /// log2 of the size in bytes for the region.
93    const LOG_BYTES: usize;
94    /// The size in bytes for the region.
95    const BYTES: usize = 1 << Self::LOG_BYTES;
96
97    /// Create a region from an address that is aligned to the region boundary. The method should panic if the address
98    /// is not properly aligned to the region. For performance, this method should always be inlined.
99    fn from_aligned_address(address: Address) -> Self;
100    /// Return the start address of the region. For performance, this method should always be inlined.
101    fn start(&self) -> Address;
102
103    /// Create a region from an arbitrary address.
104    fn from_unaligned_address(address: Address) -> Self {
105        Self::from_aligned_address(Self::align(address))
106    }
107
108    /// Align the address to the region.
109    fn align(address: Address) -> Address {
110        address.align_down(Self::BYTES)
111    }
112    /// Check if an address is aligned to the region.
113    fn is_aligned(address: Address) -> bool {
114        address.is_aligned_to(Self::BYTES)
115    }
116
117    /// Return the end address of the region. Note that the end address is not in the region.
118    fn end(&self) -> Address {
119        self.start() + Self::BYTES
120    }
121    /// Return the next region after this one.
122    fn next(&self) -> Self {
123        self.next_nth(1)
124    }
125    /// Return the next nth region after this one.
126    fn next_nth(&self, n: usize) -> Self {
127        debug_assert!(self.start().as_usize() < usize::MAX - (n << Self::LOG_BYTES));
128        Self::from_aligned_address(self.start() + (n << Self::LOG_BYTES))
129    }
130    /// Get the number of lines between the given two lines.
131    fn steps_between(start: &Self, end: &Self) -> Option<usize> {
132        if start.start() > end.start() {
133            return None;
134        }
135        Some((end.start() - start.start()) >> Self::LOG_BYTES)
136    }
137    /// Check if the given address is in the region.
138    fn includes_address(&self, addr: Address) -> bool {
139        Self::align(addr) == self.start()
140    }
141}
142
143/// An unstraddlable region.  No object can straddle (i.e. span over, overrlap with) more than one
144/// [`UnstraddlableRegion`].  In other words, any object is either in the region or not in the
145/// region.
146///
147/// For example, in [`crate::policy::immix::ImmixSpace`], a [`crate::policy::immix::block::Block`]
148/// is an unstraddlable region because objects cannot straddle multiple blocks.  In contrast a
149/// [`crate::policy::immix::line::Line`] is not an unstraddlable region because an object can
150/// straddle multiple lines.
151///
152/// Because the raw address of a [`ObjectReference`] must be inside an object, an object is in an
153/// [`UnstraddlableRegion`] if an only if the raw address of its [`ObjectReference`] is in the
154/// [`UnstraddlableRegion`].
155// The doc comment above links to `crate::policy::*` items. The `policy` module itself is private
156// (not re-exported at the crate root), so those items are technically unreachable from outside
157// the crate even though they are declared `pub`. `cargo doc --document-private-items` (used by
158// GC implementers and by `ci-doc.sh`) documents them anyway, so the links do resolve there.
159#[allow(rustdoc::private_intra_doc_links)]
160pub trait UnstraddlableRegion: Region {
161    /// Return the region that contains the object.
162    fn containing(object: ObjectReference) -> Self {
163        Self::from_unaligned_address(object.to_raw_address())
164    }
165
166    /// Reeturn whether a region contains an object.
167    fn contains(&self, object: ObjectReference) -> bool {
168        self.includes_address(object.to_raw_address())
169    }
170}
171
172/// An iterator for contiguous regions.
173pub struct RegionIterator<R: Region> {
174    current: R,
175    end: R,
176}
177
178impl<R: Region> RegionIterator<R> {
179    /// Create an iterator from the start region (inclusive) to the end region (exclusive).
180    pub fn new(start: R, end: R) -> Self {
181        Self {
182            current: start,
183            end,
184        }
185    }
186}
187
188impl<R: Region> Iterator for RegionIterator<R> {
189    type Item = R;
190
191    fn next(&mut self) -> Option<R> {
192        if self.current < self.end {
193            let ret = self.current;
194            self.current = self.current.next();
195            Some(ret)
196        } else {
197            None
198        }
199    }
200}
201
202#[cfg(test)]
203mod tests {
204    use super::*;
205    use crate::util::constants::LOG_BYTES_IN_PAGE;
206
207    const PAGE_SIZE: usize = 1 << LOG_BYTES_IN_PAGE;
208
209    #[derive(Copy, Clone, Debug, PartialEq, PartialOrd)]
210    struct Page(Address);
211
212    impl Region for Page {
213        const LOG_BYTES: usize = LOG_BYTES_IN_PAGE as usize;
214
215        fn from_aligned_address(address: Address) -> Self {
216            debug_assert!(address.is_aligned_to(Self::BYTES));
217            Self(address)
218        }
219
220        fn start(&self) -> Address {
221            self.0
222        }
223    }
224
225    #[test]
226    fn test_region_methods() {
227        let addr4k = unsafe { Address::from_usize(PAGE_SIZE) };
228        let addr4k1 = unsafe { Address::from_usize(PAGE_SIZE + 1) };
229
230        // align
231        debug_assert_eq!(Page::align(addr4k), addr4k);
232        debug_assert_eq!(Page::align(addr4k1), addr4k);
233        debug_assert!(Page::is_aligned(addr4k));
234        debug_assert!(!Page::is_aligned(addr4k1));
235
236        let page = Page::from_aligned_address(addr4k);
237        // start/end
238        debug_assert_eq!(page.start(), addr4k);
239        debug_assert_eq!(page.end(), addr4k + PAGE_SIZE);
240        // next
241        debug_assert_eq!(page.next().start(), addr4k + PAGE_SIZE);
242        debug_assert_eq!(page.next_nth(1).start(), addr4k + PAGE_SIZE);
243        debug_assert_eq!(page.next_nth(2).start(), addr4k + 2 * PAGE_SIZE);
244    }
245
246    #[test]
247    fn test_region_iterator_normal() {
248        let addr4k = unsafe { Address::from_usize(PAGE_SIZE) };
249        let page = Page::from_aligned_address(addr4k);
250        let end_page = page.next_nth(5);
251
252        let mut results = vec![];
253        let iter = RegionIterator::new(page, end_page);
254        for p in iter {
255            results.push(p);
256        }
257        debug_assert_eq!(
258            results,
259            vec![
260                page,
261                page.next_nth(1),
262                page.next_nth(2),
263                page.next_nth(3),
264                page.next_nth(4)
265            ]
266        );
267    }
268
269    #[test]
270    fn test_region_iterator_same_start_end() {
271        let addr4k = unsafe { Address::from_usize(PAGE_SIZE) };
272        let page = Page::from_aligned_address(addr4k);
273
274        let mut results = vec![];
275        let iter = RegionIterator::new(page, page);
276        for p in iter {
277            results.push(p);
278        }
279        debug_assert_eq!(results, vec![]);
280    }
281
282    #[test]
283    fn test_region_iterator_smaller_end() {
284        let addr4k = unsafe { Address::from_usize(PAGE_SIZE) };
285        let page = Page::from_aligned_address(addr4k);
286        let end = Page::from_aligned_address(Address::ZERO);
287
288        let mut results = vec![];
289        let iter = RegionIterator::new(page, end);
290        for p in iter {
291            results.push(p);
292        }
293        debug_assert_eq!(results, vec![]);
294    }
295}
mmtk/util/linear_scan.rs

mmtk/util/
linear_scan.rs
