mmtk/util/heap/layout/
map64.rs

1use super::map::CreateFreeListResult;
2use super::map::VMMap;
3use crate::util::constants::*;
4use crate::util::conversions;
5use crate::util::freelist::FreeList;
6use crate::util::heap::layout::heap_parameters::*;
7use crate::util::heap::layout::vm_layout::*;
8use crate::util::heap::space_descriptor::SpaceDescriptor;
9use crate::util::os::*;
10use crate::util::raw_memory_freelist::RawMemoryFreeList;
11use crate::util::Address;
12use std::cell::UnsafeCell;
13
14const NON_MAP_FRACTION: f64 = 1.0 - 8.0 / 4096.0;
15
16pub struct Map64 {
17    inner: UnsafeCell<Map64Inner>,
18}
19
20struct Map64Inner {
21    finalized: bool,
22    descriptor_map: Vec<SpaceDescriptor>,
23    base_address: Vec<Address>,
24    high_water: Vec<Address>,
25}
26
27unsafe impl Send for Map64 {}
28unsafe impl Sync for Map64 {}
29
30impl Map64 {
31    pub fn new() -> Self {
32        let mut high_water = vec![Address::ZERO; MAX_SPACES];
33        let mut base_address = vec![Address::ZERO; MAX_SPACES];
34
35        for i in 0..MAX_SPACES {
36            let base = unsafe { Address::from_usize(i << vm_layout().log_space_extent) };
37            high_water[i] = base;
38            base_address[i] = base;
39        }
40
41        let descriptor_map = vec![SpaceDescriptor::UNINITIALIZED; MAX_SPACES];
42
43        Self {
44            inner: UnsafeCell::new(Map64Inner {
45                descriptor_map,
46                high_water,
47                base_address,
48                finalized: false,
49            }),
50        }
51    }
52}
53
54impl VMMap for Map64 {
55    fn insert(&self, start: Address, extent: usize, descriptor: SpaceDescriptor) {
56        debug_assert!(Self::is_space_start(start));
57        debug_assert!(extent <= vm_layout().space_size_64());
58        debug_assert!(extent >= self.min_contiguous_extent());
59        // Each space will call this on exclusive address ranges. It is fine to mutate the descriptor map,
60        // as each space will update different indices.
61        let self_mut = unsafe { self.mut_self() };
62        let index = Self::space_index(start).unwrap();
63        self_mut.descriptor_map[index] = descriptor;
64    }
65
66    fn create_freelist(&self, start: Address) -> CreateFreeListResult {
67        let units = vm_layout().space_size_64() >> LOG_BYTES_IN_PAGE;
68        self.create_parent_freelist(start, units, units as _)
69    }
70
71    fn create_parent_freelist(
72        &self,
73        start: Address,
74        mut units: usize,
75        grain: i32,
76    ) -> CreateFreeListResult {
77        debug_assert!(start.is_aligned_to(BYTES_IN_CHUNK));
78
79        assert!(units >= conversions::bytes_to_pages_up(self.min_contiguous_extent()));
80
81        // This is only called during creating a page resource/space/plan/mmtk instance, which is single threaded.
82        let self_mut = unsafe { self.mut_self() };
83        let index = Self::space_index(start).unwrap();
84
85        units = (units as f64 * NON_MAP_FRACTION) as _;
86        let list_extent =
87            conversions::pages_to_bytes(RawMemoryFreeList::size_in_pages(units as _, 1) as _);
88
89        let heads = 1;
90        let pages_per_block = RawMemoryFreeList::default_block_size(units as _, heads);
91        let list = Box::new(RawMemoryFreeList::new(
92            start,
93            start + list_extent,
94            pages_per_block,
95            units as _,
96            grain,
97            heads,
98            MmapStrategy::RAW_MEMORY_FREELIST,
99        ));
100
101        /* Adjust the base address and highwater to account for the allocated chunks for the map */
102        let base = conversions::chunk_align_up(start + list_extent);
103
104        self_mut.high_water[index] = base;
105        self_mut.base_address[index] = base;
106
107        let space_displacement = base - start;
108        CreateFreeListResult {
109            free_list: list,
110            space_displacement,
111        }
112    }
113
114    /// # Safety
115    ///
116    /// Caller must ensure that only one thread is calling this method.
117    unsafe fn allocate_contiguous_chunks(
118        &self,
119        descriptor: SpaceDescriptor,
120        chunks: usize,
121        _head: Address,
122        maybe_freelist: Option<&mut dyn FreeList>,
123    ) -> Address {
124        debug_assert!(Self::space_index(descriptor.get_start()).unwrap() == descriptor.get_index());
125        // Each space will call this on exclusive address ranges. It is fine to mutate the descriptor map,
126        // as each space will update different indices.
127        let self_mut = self.mut_self();
128
129        let index = descriptor.get_index();
130        let rtn = self.inner().high_water[index];
131        let extent = chunks << LOG_BYTES_IN_CHUNK;
132        self_mut.high_water[index] = rtn + extent;
133
134        if let Some(freelist) = maybe_freelist {
135            let Some(rmfl) = freelist.downcast_mut::<RawMemoryFreeList>() else {
136                // `Map64` allocates chunks by raising the high water mark to provide previously
137                // uncovered address range to the caller.  Therefore if the `PageResource` that
138                // made the allocation request is based on freelist, the freelist must be grown to
139                // accommodate the new chunks.  Currently only `RawMemoryFreeList` can grow.
140                panic!("Map64 requires a growable free list implementation (RawMemoryFreeList).");
141            };
142            rmfl.grow_freelist(conversions::bytes_to_pages_up(extent) as _);
143            let base_page = conversions::bytes_to_pages_up(rtn - self.inner().base_address[index]);
144            for offset in (0..(chunks * PAGES_IN_CHUNK)).step_by(PAGES_IN_CHUNK) {
145                rmfl.set_uncoalescable((base_page + offset) as _);
146                /* The 32-bit implementation requires that pages are returned allocated to the caller */
147                rmfl.alloc_from_unit(PAGES_IN_CHUNK as _, (base_page + offset) as _);
148            }
149        }
150        rtn
151    }
152
153    fn get_next_contiguous_region(&self, _start: Address) -> Address {
154        unreachable!()
155    }
156
157    fn get_contiguous_region_chunks(&self, _start: Address) -> usize {
158        unreachable!()
159    }
160
161    fn get_contiguous_region_size(&self, _start: Address) -> usize {
162        unreachable!()
163    }
164
165    fn get_available_discontiguous_chunks(&self) -> usize {
166        panic!("We don't use discontiguous chunks for 64-bit!");
167    }
168
169    fn get_chunk_consumer_count(&self) -> usize {
170        panic!("We don't use discontiguous chunks for 64-bit!");
171    }
172
173    fn free_all_chunks(&self, _any_chunk: Address) {
174        unreachable!()
175    }
176
177    unsafe fn free_contiguous_chunks(&self, _start: Address) -> usize {
178        unreachable!()
179    }
180
181    fn finalize_static_space_map(
182        &self,
183        _from: Address,
184        _to: Address,
185        _on_discontig_start_determined: &mut dyn FnMut(Address),
186    ) {
187        // This is only called during boot process by a single thread.
188        // It is fine to get a mutable reference.
189        let self_mut: &mut Map64Inner = unsafe { self.mut_self() };
190
191        // Note: When using Map64, the starting address of each space is adjusted as soon as the
192        // `RawMemoryFreeList` instance in its underlying `FreeListPageResource` is created.  We no
193        // longer need to adjust the starting address here.  So we ignore the
194        // `_on_discontig_start_determined` callback which may adjust the starting address.
195
196        self_mut.finalized = true;
197    }
198
199    fn is_finalized(&self) -> bool {
200        self.inner().finalized
201    }
202
203    fn get_descriptor_for_address(&self, address: Address) -> SpaceDescriptor {
204        if let Some(index) = Self::space_index(address) {
205            self.inner().descriptor_map[index]
206        } else {
207            SpaceDescriptor::UNINITIALIZED
208        }
209    }
210
211    fn min_contiguous_extent(&self) -> usize {
212        // The underlying RawMemoryFreeList will occupy a portion of address range as its own metadata from
213        // the space extent. As we always allocate in the granularity of chunks, for one chunk of space,
214        // we would need a small fraction as the metadata. So make the minimal space size allowed to be two chunks.
215        BYTES_IN_CHUNK * 2
216    }
217}
218
219impl Map64 {
220    /// # Safety
221    ///
222    /// The caller needs to guarantee there is no race condition. Either only one single thread
223    /// is using this method, or multiple threads are accessing mutally exclusive data (e.g. different indices in arrays).
224    /// In other cases, use mut_self_with_sync().
225    #[allow(clippy::mut_from_ref)]
226    unsafe fn mut_self(&self) -> &mut Map64Inner {
227        &mut *self.inner.get()
228    }
229
230    fn inner(&self) -> &Map64Inner {
231        unsafe { &*self.inner.get() }
232    }
233
234    fn space_index(addr: Address) -> Option<usize> {
235        if addr > vm_layout().heap_end {
236            return None;
237        }
238        Some(addr >> vm_layout().space_shift_64())
239    }
240
241    fn is_space_start(base: Address) -> bool {
242        (base & !vm_layout().space_mask_64()) == 0
243    }
244}
245
246impl Default for Map64 {
247    fn default() -> Self {
248        Self::new()
249    }
250}
mmtk/util/heap/layout/map64.rs

mmtk/util/heap/layout/
map64.rs
