mmtk/util/heap/layout/
map32.rs

1use super::map::CreateFreeListResult;
2use super::map::VMMap;
3use crate::mmtk::SFT_MAP;
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::int_array_freelist::IntArrayFreeList;
10use crate::util::rust_util::zeroed_alloc::new_zeroed_vec;
11use crate::util::Address;
12use std::cell::UnsafeCell;
13use std::sync::{Mutex, MutexGuard};
14
15pub struct Map32 {
16    sync: Mutex<()>,
17    inner: UnsafeCell<Map32Inner>,
18}
19
20#[doc(hidden)]
21pub struct Map32Inner {
22    prev_link: Vec<i32>,
23    next_link: Vec<i32>,
24    region_map: IntArrayFreeList,
25    global_page_map: IntArrayFreeList,
26    shared_discontig_fl_count: usize,
27    total_available_discontiguous_chunks: usize,
28    finalized: bool,
29    descriptor_map: Vec<SpaceDescriptor>,
30}
31
32unsafe impl Send for Map32 {}
33unsafe impl Sync for Map32 {}
34
35impl Map32 {
36    pub fn new() -> Self {
37        let max_chunks = vm_layout().max_chunks();
38        Map32 {
39            inner: UnsafeCell::new(Map32Inner {
40                prev_link: vec![-1; max_chunks],
41                next_link: vec![-1; max_chunks],
42                region_map: IntArrayFreeList::new(max_chunks, max_chunks as _, 1),
43                global_page_map: IntArrayFreeList::new(1, 1, MAX_SPACES),
44                shared_discontig_fl_count: 0,
45                total_available_discontiguous_chunks: 0,
46                finalized: false,
47                // This can be big on 64-bit machines.  Use `new_zeroed_vec`.
48                descriptor_map: new_zeroed_vec(max_chunks),
49            }),
50            sync: Mutex::new(()),
51        }
52    }
53}
54
55impl std::ops::Deref for Map32 {
56    type Target = Map32Inner;
57    fn deref(&self) -> &Self::Target {
58        unsafe { &*self.inner.get() }
59    }
60}
61
62impl VMMap for Map32 {
63    fn insert(&self, start: Address, extent: usize, descriptor: SpaceDescriptor) {
64        // Each space will call this on exclusive address ranges. It is fine to mutate the descriptor map,
65        // as each space will update different indices.
66        let self_mut: &mut Map32Inner = unsafe { self.mut_self() };
67        let mut e = 0;
68        while e < extent {
69            let index = (start + e).chunk_index();
70            assert!(
71                self.descriptor_map[index].is_empty(),
72                "Conflicting virtual address request"
73            );
74            debug!(
75                "Set descriptor {:?} for Chunk {}",
76                descriptor,
77                conversions::chunk_index_to_address(index)
78            );
79            self_mut.descriptor_map[index] = descriptor;
80            //   VM.barriers.objectArrayStoreNoGCBarrier(spaceMap, index, space);
81            e += BYTES_IN_CHUNK;
82        }
83    }
84
85    fn create_freelist(&self, _start: Address) -> CreateFreeListResult {
86        let free_list = Box::new(IntArrayFreeList::from_parent(
87            &self.global_page_map,
88            self.get_discontig_freelist_pr_ordinal() as _,
89        ));
90        CreateFreeListResult {
91            free_list,
92            space_displacement: 0,
93        }
94    }
95
96    fn create_parent_freelist(
97        &self,
98        _start: Address,
99        units: usize,
100        grain: i32,
101    ) -> CreateFreeListResult {
102        let free_list = Box::new(IntArrayFreeList::new(units, grain, 1));
103        CreateFreeListResult {
104            free_list,
105            space_displacement: 0,
106        }
107    }
108
109    unsafe fn allocate_contiguous_chunks(
110        &self,
111        descriptor: SpaceDescriptor,
112        chunks: usize,
113        head: Address,
114        _maybe_freelist: Option<&mut dyn FreeList>,
115    ) -> Address {
116        let (_sync, self_mut) = self.mut_self_with_sync();
117        let chunk = self_mut.region_map.alloc(chunks as _);
118        if chunk == -1 {
119            return Address::zero();
120        }
121        self_mut.total_available_discontiguous_chunks -= chunks;
122        let rtn = conversions::chunk_index_to_address(chunk as _);
123        self.insert(rtn, chunks << LOG_BYTES_IN_CHUNK, descriptor);
124        if head.is_zero() {
125            debug_assert!(self.next_link[chunk as usize] == -1);
126        } else {
127            self_mut.next_link[chunk as usize] = head.chunk_index() as _;
128            self_mut.prev_link[head.chunk_index()] = chunk;
129        }
130        debug_assert!(self.prev_link[chunk as usize] == -1);
131        rtn
132    }
133
134    fn get_next_contiguous_region(&self, start: Address) -> Address {
135        if start.is_zero() {
136            return Address::ZERO;
137        }
138        debug_assert!(start == conversions::chunk_align_down(start));
139        let chunk = start.chunk_index();
140        if self.next_link[chunk] == -1 {
141            unsafe { Address::zero() }
142        } else {
143            let a = self.next_link[chunk];
144            conversions::chunk_index_to_address(a as _)
145        }
146    }
147
148    fn get_contiguous_region_chunks(&self, start: Address) -> usize {
149        debug_assert!(start == conversions::chunk_align_down(start));
150        let chunk = start.chunk_index();
151        self.region_map.size(chunk as i32) as _
152    }
153
154    fn get_contiguous_region_size(&self, start: Address) -> usize {
155        self.get_contiguous_region_chunks(start) << LOG_BYTES_IN_CHUNK
156    }
157
158    fn get_available_discontiguous_chunks(&self) -> usize {
159        self.total_available_discontiguous_chunks
160    }
161
162    fn get_chunk_consumer_count(&self) -> usize {
163        self.shared_discontig_fl_count
164    }
165    #[allow(clippy::while_immutable_condition)]
166    fn free_all_chunks(&self, any_chunk: Address) {
167        debug!("free_all_chunks: {}", any_chunk);
168        let (_sync, self_mut) = self.mut_self_with_sync();
169        debug_assert!(any_chunk == conversions::chunk_align_down(any_chunk));
170        if !any_chunk.is_zero() {
171            let chunk = any_chunk.chunk_index();
172            while self_mut.next_link[chunk] != -1 {
173                let x = self_mut.next_link[chunk];
174                self.free_contiguous_chunks_no_lock(x);
175            }
176            while self_mut.prev_link[chunk] != -1 {
177                let x = self_mut.prev_link[chunk];
178                self.free_contiguous_chunks_no_lock(x);
179            }
180            self.free_contiguous_chunks_no_lock(chunk as _);
181        }
182    }
183
184    unsafe fn free_contiguous_chunks(&self, start: Address) -> usize {
185        debug!("free_contiguous_chunks: {}", start);
186        let (_sync, _) = self.mut_self_with_sync();
187        debug_assert!(start == conversions::chunk_align_down(start));
188        let chunk = start.chunk_index();
189        self.free_contiguous_chunks_no_lock(chunk as _)
190    }
191
192    fn finalize_static_space_map(
193        &self,
194        from: Address,
195        to: Address,
196        on_discontig_start_determined: &mut dyn FnMut(Address),
197    ) {
198        // This is only called during boot process by a single thread.
199        // It is fine to get a mutable reference.
200        let self_mut: &mut Map32Inner = unsafe { self.mut_self() };
201        /* establish bounds of discontiguous space */
202        let start_address = from;
203        let first_chunk = start_address.chunk_index();
204        let last_chunk = to.chunk_index();
205        let unavail_start_chunk = last_chunk + 1;
206        let trailing_chunks = vm_layout().max_chunks() - unavail_start_chunk;
207        let pages = (1 + last_chunk - first_chunk) * PAGES_IN_CHUNK;
208        // start_address=0xb0000000, first_chunk=704, last_chunk=703, unavail_start_chunk=704, trailing_chunks=320, pages=0
209        // startAddress=0x68000000 firstChunk=416 lastChunk=703 unavailStartChunk=704 trailingChunks=320 pages=294912
210        self_mut.global_page_map.resize_freelist(pages, pages as _);
211
212        on_discontig_start_determined(start_address);
213
214        // [
215        //  2: -1073741825
216        //  3: -1073741825
217        //  5: -2147482624
218        //  2048: -2147483648
219        //  2049: -2147482624
220        //  2050: 1024
221        //  2051: 1024
222        // ]
223        /* set up the region map free list */
224        self_mut.region_map.alloc(first_chunk as _); // block out entire bottom of address range
225        for _ in first_chunk..=last_chunk {
226            self_mut.region_map.alloc(1);
227        }
228        let alloced_chunk = self_mut.region_map.alloc(trailing_chunks as _);
229        debug_assert!(
230            alloced_chunk == unavail_start_chunk as i32,
231            "{} != {}",
232            alloced_chunk,
233            unavail_start_chunk
234        );
235        /* set up the global page map and place chunks on free list */
236        let mut first_page = 0;
237        for chunk_index in first_chunk..=last_chunk {
238            self_mut.total_available_discontiguous_chunks += 1;
239            self_mut.region_map.free(chunk_index as _, false); // put this chunk on the free list
240            self_mut.global_page_map.set_uncoalescable(first_page);
241            let alloced_pages = self_mut.global_page_map.alloc(PAGES_IN_CHUNK as _); // populate the global page map
242            debug_assert!(alloced_pages == first_page);
243            first_page += PAGES_IN_CHUNK as i32;
244        }
245        self_mut.finalized = true;
246    }
247
248    fn is_finalized(&self) -> bool {
249        self.finalized
250    }
251
252    fn get_descriptor_for_address(&self, address: Address) -> SpaceDescriptor {
253        let index = address.chunk_index();
254        self.descriptor_map
255            .get(index)
256            .copied()
257            .unwrap_or(SpaceDescriptor::UNINITIALIZED)
258    }
259
260    fn min_contiguous_extent(&self) -> usize {
261        BYTES_IN_CHUNK
262    }
263}
264
265impl Map32 {
266    /// # Safety
267    ///
268    /// The caller needs to guarantee there is no race condition. Either only one single thread
269    /// is using this method, or multiple threads are accessing mutally exclusive data (e.g. different indices in arrays).
270    /// In other cases, use mut_self_with_sync().
271    #[allow(clippy::mut_from_ref)]
272    unsafe fn mut_self(&self) -> &mut Map32Inner {
273        &mut *self.inner.get()
274    }
275
276    /// Get a mutable reference to the inner Map32Inner with a lock.
277    /// The caller should only use the mutable reference while holding the lock.
278    #[allow(clippy::mut_from_ref)]
279    fn mut_self_with_sync(&self) -> (MutexGuard<'_, ()>, &mut Map32Inner) {
280        let guard = self.sync.lock().unwrap();
281        (guard, unsafe { self.mut_self() })
282    }
283
284    fn free_contiguous_chunks_no_lock(&self, chunk: i32) -> usize {
285        unsafe {
286            let chunks = self.mut_self().region_map.free(chunk, false);
287            self.mut_self().total_available_discontiguous_chunks += chunks as usize;
288            let next = self.next_link[chunk as usize];
289            let prev = self.prev_link[chunk as usize];
290            if next != -1 {
291                self.mut_self().prev_link[next as usize] = prev
292            };
293            if prev != -1 {
294                self.mut_self().next_link[prev as usize] = next
295            };
296            self.mut_self().prev_link[chunk as usize] = -1;
297            self.mut_self().next_link[chunk as usize] = -1;
298            for offset in 0..chunks {
299                let index = (chunk + offset) as usize;
300                let chunk_start = conversions::chunk_index_to_address(index);
301                debug!("Clear descriptor for Chunk {}", chunk_start);
302                self.mut_self().descriptor_map[index] = SpaceDescriptor::UNINITIALIZED;
303                SFT_MAP.clear(chunk_start);
304            }
305            chunks as _
306        }
307    }
308
309    fn get_discontig_freelist_pr_ordinal(&self) -> usize {
310        // This is only called during creating a page resource/space/plan/mmtk instance, which is single threaded.
311        let self_mut: &mut Map32Inner = unsafe { self.mut_self() };
312        self_mut.shared_discontig_fl_count += 1;
313        self.shared_discontig_fl_count
314    }
315}
316
317impl Default for Map32 {
318    fn default() -> Self {
319        Self::new()
320    }
321}
mmtk/util/heap/layout/map32.rs

mmtk/util/heap/layout/
map32.rs
