mmtk/policy/marksweepspace/native_ms/
block.rs

1// adapted from Immix
2
3use atomic::Ordering;
4
5use super::BlockList;
6use super::MarkSweepSpace;
7use crate::util::constants::LOG_BYTES_IN_PAGE;
8use crate::util::heap::chunk_map::*;
9use crate::util::linear_scan::Region;
10use crate::util::object_enum::BlockMayHaveObjects;
11use crate::vm::ObjectModel;
12use crate::{
13    util::{
14        metadata::side_metadata::SideMetadataSpec, Address, ObjectReference, OpaquePointer,
15        VMThread,
16    },
17    vm::VMBinding,
18};
19
20use std::num::NonZeroUsize;
21
22/// A 64KB region for MiMalloc.
23/// This is also known as MiMalloc page. We try to avoid getting confused with the OS 4K page. So we call it block.
24/// This type always holds a non-zero address to refer to a block. The underlying `NonZeroUsize` type ensures the
25/// size of `Option<Block>` is the same as `Block` itself.
26// TODO: If we actually use the first block, we would need to turn the type into `Block(Address)`, and use `None` and
27// `Block(Address::ZERO)` to differentiate those.
28#[derive(Clone, Copy, PartialOrd, PartialEq)]
29#[repr(transparent)]
30pub struct Block(NonZeroUsize);
31
32impl std::fmt::Debug for Block {
33    fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
34        write!(f, "Block(0x{:x})", self.0)
35    }
36}
37
38impl Region for Block {
39    const LOG_BYTES: usize = 16;
40
41    fn from_aligned_address(address: Address) -> Self {
42        debug_assert!(address.is_aligned_to(Self::BYTES));
43        debug_assert!(!address.is_zero());
44        Self(unsafe { NonZeroUsize::new_unchecked(address.as_usize()) })
45    }
46
47    fn start(&self) -> Address {
48        unsafe { Address::from_usize(self.0.get()) }
49    }
50}
51
52impl BlockMayHaveObjects for Block {
53    fn may_have_objects(&self) -> bool {
54        self.get_state() != BlockState::Unallocated
55    }
56}
57
58impl Block {
59    /// Log pages in block
60    pub const LOG_PAGES: usize = Self::LOG_BYTES - LOG_BYTES_IN_PAGE as usize;
61
62    pub const METADATA_SPECS: [SideMetadataSpec; 7] = [
63        Self::MARK_TABLE,
64        Self::NEXT_BLOCK_TABLE,
65        Self::PREV_BLOCK_TABLE,
66        Self::FREE_LIST_TABLE,
67        Self::SIZE_TABLE,
68        Self::BLOCK_LIST_TABLE,
69        Self::TLS_TABLE,
70    ];
71
72    /// Block mark table (side)
73    pub const MARK_TABLE: SideMetadataSpec =
74        crate::util::metadata::side_metadata::spec_defs::MS_BLOCK_MARK;
75
76    pub const NEXT_BLOCK_TABLE: SideMetadataSpec =
77        crate::util::metadata::side_metadata::spec_defs::MS_BLOCK_NEXT;
78
79    pub const PREV_BLOCK_TABLE: SideMetadataSpec =
80        crate::util::metadata::side_metadata::spec_defs::MS_BLOCK_PREV;
81
82    pub const FREE_LIST_TABLE: SideMetadataSpec =
83        crate::util::metadata::side_metadata::spec_defs::MS_FREE;
84
85    // needed for non GC context
86    #[cfg(feature = "malloc_native_mimalloc")]
87    pub const LOCAL_FREE_LIST_TABLE: SideMetadataSpec =
88        crate::util::metadata::side_metadata::spec_defs::MS_LOCAL_FREE;
89
90    #[cfg(feature = "malloc_native_mimalloc")]
91    pub const THREAD_FREE_LIST_TABLE: SideMetadataSpec =
92        crate::util::metadata::side_metadata::spec_defs::MS_THREAD_FREE;
93
94    pub const SIZE_TABLE: SideMetadataSpec =
95        crate::util::metadata::side_metadata::spec_defs::MS_BLOCK_SIZE;
96
97    pub const BLOCK_LIST_TABLE: SideMetadataSpec =
98        crate::util::metadata::side_metadata::spec_defs::MS_BLOCK_LIST;
99
100    pub const TLS_TABLE: SideMetadataSpec =
101        crate::util::metadata::side_metadata::spec_defs::MS_BLOCK_TLS;
102
103    pub fn load_free_list(&self) -> Address {
104        unsafe { Address::from_usize(Block::FREE_LIST_TABLE.load::<usize>(self.start())) }
105    }
106
107    pub fn store_free_list(&self, free_list: Address) {
108        unsafe { Block::FREE_LIST_TABLE.store::<usize>(self.start(), free_list.as_usize()) }
109    }
110
111    #[cfg(feature = "malloc_native_mimalloc")]
112    pub fn load_local_free_list(&self) -> Address {
113        unsafe { Address::from_usize(Block::LOCAL_FREE_LIST_TABLE.load::<usize>(self.start())) }
114    }
115
116    #[cfg(feature = "malloc_native_mimalloc")]
117    pub fn store_local_free_list(&self, local_free: Address) {
118        unsafe { Block::LOCAL_FREE_LIST_TABLE.store::<usize>(self.start(), local_free.as_usize()) }
119    }
120
121    #[cfg(feature = "malloc_native_mimalloc")]
122    pub fn load_thread_free_list(&self) -> Address {
123        unsafe {
124            Address::from_usize(
125                Block::THREAD_FREE_LIST_TABLE.load_atomic::<usize>(self.start(), Ordering::SeqCst),
126            )
127        }
128    }
129
130    #[cfg(feature = "malloc_native_mimalloc")]
131    pub fn store_thread_free_list(&self, thread_free: Address) {
132        unsafe {
133            Block::THREAD_FREE_LIST_TABLE.store::<usize>(self.start(), thread_free.as_usize())
134        }
135    }
136
137    #[cfg(feature = "malloc_native_mimalloc")]
138    pub fn cas_thread_free_list(&self, old_thread_free: Address, new_thread_free: Address) -> bool {
139        Block::THREAD_FREE_LIST_TABLE
140            .compare_exchange_atomic::<usize>(
141                self.start(),
142                old_thread_free.as_usize(),
143                new_thread_free.as_usize(),
144                Ordering::SeqCst,
145                Ordering::SeqCst,
146            )
147            .is_ok()
148    }
149
150    pub fn load_prev_block(&self) -> Option<Block> {
151        let prev = unsafe { Block::PREV_BLOCK_TABLE.load::<usize>(self.start()) };
152        NonZeroUsize::new(prev).map(Block)
153    }
154
155    pub fn load_next_block(&self) -> Option<Block> {
156        let next = unsafe { Block::NEXT_BLOCK_TABLE.load::<usize>(self.start()) };
157        NonZeroUsize::new(next).map(Block)
158    }
159
160    pub fn store_next_block(&self, next: Block) {
161        unsafe {
162            Block::NEXT_BLOCK_TABLE.store::<usize>(self.start(), next.start().as_usize());
163        }
164    }
165
166    pub fn clear_next_block(&self) {
167        unsafe {
168            Block::NEXT_BLOCK_TABLE.store::<usize>(self.start(), 0);
169        }
170    }
171
172    pub fn store_prev_block(&self, prev: Block) {
173        unsafe {
174            Block::PREV_BLOCK_TABLE.store::<usize>(self.start(), prev.start().as_usize());
175        }
176    }
177
178    pub fn clear_prev_block(&self) {
179        unsafe {
180            Block::PREV_BLOCK_TABLE.store::<usize>(self.start(), 0);
181        }
182    }
183
184    pub fn store_block_list(&self, block_list: &BlockList) {
185        let block_list_usize: usize = block_list as *const BlockList as usize;
186        unsafe {
187            Block::BLOCK_LIST_TABLE.store::<usize>(self.start(), block_list_usize);
188        }
189    }
190
191    pub fn load_block_list(&self) -> *mut BlockList {
192        let block_list =
193            Block::BLOCK_LIST_TABLE.load_atomic::<usize>(self.start(), Ordering::SeqCst);
194        block_list as *mut BlockList
195    }
196
197    pub fn load_block_cell_size(&self) -> usize {
198        Block::SIZE_TABLE.load_atomic::<usize>(self.start(), Ordering::SeqCst)
199    }
200
201    pub fn store_block_cell_size(&self, size: usize) {
202        debug_assert_ne!(size, 0);
203        unsafe { Block::SIZE_TABLE.store::<usize>(self.start(), size) }
204    }
205
206    pub fn store_tls(&self, tls: VMThread) {
207        let tls_usize: usize = tls.0.to_address().as_usize();
208        unsafe { Block::TLS_TABLE.store(self.start(), tls_usize) }
209    }
210
211    pub fn load_tls(&self) -> VMThread {
212        let tls = Block::TLS_TABLE.load_atomic::<usize>(self.start(), Ordering::SeqCst);
213        VMThread(OpaquePointer::from_address(unsafe {
214            Address::from_usize(tls)
215        }))
216    }
217
218    pub fn has_free_cells(&self) -> bool {
219        !self.load_free_list().is_zero()
220    }
221
222    /// Get block mark state.
223    pub fn get_state(&self) -> BlockState {
224        let byte = Self::MARK_TABLE.load_atomic::<u8>(self.start(), Ordering::SeqCst);
225        byte.into()
226    }
227
228    /// Set block mark state.
229    pub fn set_state(&self, state: BlockState) {
230        let state = u8::from(state);
231        Self::MARK_TABLE.store_atomic::<u8>(self.start(), state, Ordering::SeqCst);
232    }
233
234    /// Release this block if it is unmarked. Return true if the block is released.
235    pub fn attempt_release<VM: VMBinding>(self, space: &MarkSweepSpace<VM>) -> bool {
236        match self.get_state() {
237            // We should not have unallocated blocks in a block list
238            BlockState::Unallocated => unreachable!(),
239            BlockState::Unmarked => {
240                let block_list = self.load_block_list();
241                unsafe { &mut *block_list }.remove(self);
242                space.release_block(self);
243                true
244            }
245            BlockState::Marked => {
246                // The block is live.
247                false
248            }
249        }
250    }
251
252    /// Sweep the block. This is done either lazily in the allocation phase, or eagerly at the end of a GC.
253    pub fn sweep<VM: VMBinding>(&self) {
254        // The important point here is that we need to distinguish cell address, allocation address, and object reference.
255        // We only know cell addresses here. We do not know the allocation address, and we also do not know the object reference.
256        // The mark bit is set for object references, and we need to use the mark bit to decide whether a cell is live or not.
257
258        // We haven't implemented for malloc/free cases, for which we do not have mark bit. We could use valid object bit instead.
259        if cfg!(feature = "malloc_native_mimalloc") {
260            unimplemented!()
261        }
262
263        // Check if we can treat it as the simple case: cell address === object reference.
264        // If the binding does not use allocation offset, and they use the same allocation alignment which the cell size is aligned to,
265        // then we have cell address === allocation address.
266        // Furthermore, if the binding does not have an offset between allocation and object reference, then allocation address === cell address.
267        if !VM::USE_ALLOCATION_OFFSET
268            && VM::MAX_ALIGNMENT == VM::MIN_ALIGNMENT
269            && crate::util::conversions::raw_is_aligned(
270                self.load_block_cell_size(),
271                VM::MAX_ALIGNMENT,
272            )
273            && VM::VMObjectModel::UNIFIED_OBJECT_REFERENCE_ADDRESS
274        {
275            // In this case, we can use the simplest and the most efficicent sweep.
276            self.simple_sweep::<VM>()
277        } else {
278            // Otherwise we fallback to a generic but slow sweep. This roughly has ~10% mutator overhead for lazy sweeping.
279            self.naive_brute_force_sweep::<VM>()
280        }
281    }
282
283    /// This implementation uses object reference and cell address interchangably. This is not correct for most cases.
284    /// However, in certain cases, such as OpenJDK, this is correct, and efficient. See the sweep method for the invariants
285    /// that we need to use this method correctly.
286    fn simple_sweep<VM: VMBinding>(&self) {
287        let cell_size = self.load_block_cell_size();
288        debug_assert_ne!(cell_size, 0);
289        let mut cell = self.start();
290        let mut last = unsafe { Address::zero() };
291        while cell + cell_size <= self.start() + Block::BYTES {
292            // The invariants we checked earlier ensures that we can use cell and object reference interchangably
293            // We may not really have an object in this cell, but if we do, this object reference is correct.
294            // About unsafe: We know `cell` is non-zero here.
295            let potential_object = unsafe { ObjectReference::from_raw_address_unchecked(cell) };
296
297            if !VM::VMObjectModel::LOCAL_MARK_BIT_SPEC
298                .is_marked::<VM>(potential_object, Ordering::SeqCst)
299            {
300                // clear VO bit if it is ever set. It is possible that the VO bit is never set for this cell (i.e. there was no object in this cell before this GC),
301                // we unset the bit anyway.
302                #[cfg(feature = "vo_bit")]
303                crate::util::metadata::vo_bit::unset_vo_bit_nocheck(potential_object);
304                unsafe {
305                    cell.store::<Address>(last);
306                }
307                last = cell;
308            }
309            cell += cell_size;
310        }
311
312        self.store_free_list(last);
313    }
314
315    /// This is a naive implementation that is inefficient but should be correct.
316    /// In this implementation, we simply go through each possible object
317    /// reference and see if it has the mark bit set. If we find mark bit, that means the cell is alive. If we didn't find
318    /// the mark bit in the entire cell, it means the cell is dead.
319    fn naive_brute_force_sweep<VM: VMBinding>(&self) {
320        use crate::util::constants::MIN_OBJECT_SIZE;
321
322        // Cell size for this block.
323        let cell_size = self.load_block_cell_size();
324        // Current cell
325        let mut cell = self.start();
326        // Last free cell in the free list
327        let mut last = Address::ZERO;
328        // Current cursor
329        let mut cursor = cell;
330
331        debug!("Sweep block {:?}, cell size {}", self, cell_size);
332
333        while cell + cell_size <= self.end() {
334            // possible object ref
335            let potential_object_ref = unsafe {
336                // We know cursor plus an offset cannot be 0.
337                ObjectReference::from_raw_address_unchecked(
338                    cursor + VM::VMObjectModel::OBJECT_REF_OFFSET_LOWER_BOUND,
339                )
340            };
341            trace!(
342                "{:?}: cell = {}, last cell in free list = {}, cursor = {}, potential object = {}",
343                self,
344                cell,
345                last,
346                cursor,
347                potential_object_ref
348            );
349
350            if VM::VMObjectModel::LOCAL_MARK_BIT_SPEC
351                .is_marked::<VM>(potential_object_ref, Ordering::SeqCst)
352            {
353                debug!("{:?} Live cell: {}", self, cell);
354                // If the mark bit is set, the cell is alive.
355                // We directly jump to the end of the cell.
356                cell += cell_size;
357                cursor = cell;
358            } else {
359                // If the mark bit is not set, we don't know if the cell is alive or not. We keep search for the mark bit.
360                cursor += MIN_OBJECT_SIZE;
361
362                if cursor >= cell + cell_size {
363                    // We now stepped to the next cell. This means we did not find mark bit in the current cell, and we can add this cell to free list.
364                    debug!(
365                        "{:?} Free cell: {}, last cell in freelist is {}",
366                        self, cell, last
367                    );
368
369                    // Clear VO bit: we don't know where the object reference actually is, so we bulk zero the cell.
370                    #[cfg(feature = "vo_bit")]
371                    crate::util::metadata::vo_bit::bzero_vo_bit(cell, cell_size);
372
373                    // store the previous cell to make the free list
374                    debug_assert!(last.is_zero() || (last >= self.start() && last < self.end()));
375                    unsafe {
376                        cell.store::<Address>(last);
377                    }
378                    last = cell;
379                    cell += cell_size;
380                    debug_assert_eq!(cursor, cell);
381                }
382            }
383        }
384
385        self.store_free_list(last);
386    }
387
388    /// Get the chunk containing the block.
389    pub fn chunk(&self) -> Chunk {
390        Chunk::from_unaligned_address(self.start())
391    }
392
393    /// Initialize a clean block after acquired from page-resource.
394    pub fn init(&self) {
395        self.set_state(BlockState::Unmarked);
396    }
397
398    /// Deinitalize a block before releasing.
399    pub fn deinit(&self) {
400        self.set_state(BlockState::Unallocated);
401    }
402}
403
404/// The block allocation state.
405#[derive(Debug, PartialEq, Clone, Copy)]
406pub enum BlockState {
407    /// the block is not allocated.
408    Unallocated,
409    /// the block is allocated but not marked.
410    Unmarked,
411    /// the block is allocated and marked.
412    Marked,
413}
414
415impl BlockState {
416    /// Private constant
417    const MARK_UNALLOCATED: u8 = 0;
418    /// Private constant
419    const MARK_UNMARKED: u8 = u8::MAX;
420    /// Private constant
421    const MARK_MARKED: u8 = u8::MAX - 1;
422}
423
424impl From<u8> for BlockState {
425    fn from(state: u8) -> Self {
426        match state {
427            Self::MARK_UNALLOCATED => BlockState::Unallocated,
428            Self::MARK_UNMARKED => BlockState::Unmarked,
429            Self::MARK_MARKED => BlockState::Marked,
430            _ => unreachable!(),
431        }
432    }
433}
434
435impl From<BlockState> for u8 {
436    fn from(state: BlockState) -> Self {
437        match state {
438            BlockState::Unallocated => BlockState::MARK_UNALLOCATED,
439            BlockState::Unmarked => BlockState::MARK_UNMARKED,
440            BlockState::Marked => BlockState::MARK_MARKED,
441        }
442    }
443}
mmtk/policy/marksweepspace/native_ms/block.rs

mmtk/policy/marksweepspace/native_ms/
block.rs
