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

mmtk/util/
linear_scan.rs
