mmtk/policy/immix/
line.rs

1use std::ops::Range;
2
3use super::block::Block;
4use crate::util::constants::LOG_BITS_IN_BYTE;
5use crate::util::linear_scan::{Region, RegionIterator};
6use crate::util::metadata::side_metadata::spec_defs::IX_LINE_REUSE_COUNT;
7use crate::util::metadata::side_metadata::*;
8use crate::util::rc;
9use crate::{
10    util::{Address, ObjectReference},
11    vm::*,
12};
13use atomic::Ordering;
14
15/// Data structure to reference a line within an immix block.
16#[repr(transparent)]
17#[derive(Debug, Clone, Copy, PartialOrd, PartialEq, Eq)]
18pub struct Line(Address);
19
20impl Region for Line {
21    const LOG_BYTES: usize = 8;
22
23    #[allow(clippy::assertions_on_constants)] // make sure line is not used when BLOCK_ONLY is turned on.
24    fn from_aligned_address(address: Address) -> Self {
25        debug_assert!(!super::BLOCK_ONLY);
26        debug_assert!(address.is_aligned_to(Self::BYTES));
27        Self(address)
28    }
29
30    fn start(&self) -> Address {
31        self.0
32    }
33}
34
35#[allow(clippy::assertions_on_constants)]
36impl Line {
37    pub const RESET_MARK_STATE: u8 = 1;
38    pub const MAX_MARK_STATE: u8 = 127;
39
40    /// Line mark table (side)
41    pub const MARK_TABLE: SideMetadataSpec =
42        crate::util::metadata::side_metadata::spec_defs::IX_LINE_MARK;
43
44    /// Get the block containing the line.
45    pub fn block(&self) -> Block {
46        debug_assert!(!super::BLOCK_ONLY);
47        Block::from_unaligned_address(self.0)
48    }
49
50    /// Get line index within its containing block.
51    pub fn get_index_within_block(&self) -> usize {
52        let addr = self.start();
53        addr.get_extent(Block::align(addr)) >> Line::LOG_BYTES
54    }
55
56    /// Mark the line. This will update the side line mark table.
57    pub fn mark(&self, state: u8) {
58        debug_assert!(!super::BLOCK_ONLY);
59        unsafe {
60            Self::MARK_TABLE.store::<u8>(self.start(), state);
61        }
62    }
63
64    /// Test line mark state.
65    pub fn is_marked(&self, state: u8) -> bool {
66        debug_assert!(!super::BLOCK_ONLY);
67        unsafe { Self::MARK_TABLE.load::<u8>(self.start()) == state }
68    }
69
70    /// Mark all lines the object is spanned to.
71    pub fn mark_lines_for_object<VM: VMBinding>(object: ObjectReference, state: u8) -> usize {
72        debug_assert!(!super::BLOCK_ONLY);
73        let start = object.to_object_start::<VM>();
74        let end = start + VM::VMObjectModel::get_current_size(object);
75        let start_line = Line::from_unaligned_address(start);
76        let mut end_line = Line::from_unaligned_address(end);
77        if !Line::is_aligned(end) {
78            end_line = end_line.next();
79        }
80        let mut marked_lines = 0;
81        let iter = RegionIterator::<Line>::new(start_line, end_line);
82        for line in iter {
83            if !line.is_marked(state) {
84                marked_lines += 1;
85            }
86            line.mark(state)
87        }
88        marked_lines
89    }
90
91    /// Bulk set the local mark bits of a line range.
92    ///
93    /// This is useful during concurrent marking. By doing this, concurrent marking will
94    /// conservatively consider all objects allocated in the line range as live, and the mutator
95    /// doesn't need to explicitly mark bump-allocated objects in the fast path.
96    pub fn initialize_mark_table_as_marked<VM: VMBinding>(lines: Range<Line>) {
97        let meta = VM::VMObjectModel::LOCAL_MARK_BIT_SPEC.extract_side_spec();
98        let start: *mut u8 = address_to_meta_address(meta, lines.start.start()).to_mut_ptr();
99        let limit: *mut u8 = address_to_meta_address(meta, lines.end.start()).to_mut_ptr();
100        unsafe {
101            let bytes = limit.offset_from(start) as usize;
102            std::ptr::write_bytes(start, 0xffu8, bytes);
103        }
104    }
105
106    pub fn inc_reuse_counts(lines: Range<Line>) {
107        let mut l = lines.start;
108        while l < lines.end {
109            let addr = l.start();
110            let count = IX_LINE_REUSE_COUNT.load_atomic::<u8>(addr, Ordering::SeqCst);
111            let new_count = if count == u8::MAX { 0 } else { count + 1 };
112            IX_LINE_REUSE_COUNT.store_atomic::<u8>(addr, new_count, Ordering::SeqCst);
113            l = l.next();
114        }
115    }
116
117    /// Bulk set line mark states.
118    pub fn bulk_set_line_mark_states(line_mark_state: u8, lines: Range<Line>) {
119        for line in RegionIterator::<Line>::new(lines.start, lines.end) {
120            line.mark(line_mark_state);
121        }
122    }
123
124    /// Eagerly mark all line mark states and all side mark bits in the gap.
125    ///
126    /// Useful during concurrent marking.
127    pub fn eager_mark_lines<VM: VMBinding>(line_mark_state: u8, lines: Range<Line>) {
128        Self::bulk_set_line_mark_states(line_mark_state, lines.clone());
129        Self::initialize_mark_table_as_marked::<VM>(lines);
130    }
131
132    pub fn clear_field_unlog_table<VM: VMBinding>(lines: Range<Line>) {
133        let unlog_bit = *VM::VMObjectModel::GLOBAL_FIELD_UNLOG_BIT_SPEC
134            .as_spec()
135            .extract_side_spec();
136        let log_meta_bits_per_line = const {
137            Line::LOG_BYTES + LOG_BITS_IN_BYTE as usize
138                - VM::VMObjectModel::GLOBAL_FIELD_UNLOG_BIT_SPEC.log_heap_bytes_per_unlog_byte()
139        };
140        debug_assert!((1 << log_meta_bits_per_line) >= 8);
141        let log_meta_bytes_per_line = log_meta_bits_per_line - LOG_BITS_IN_BYTE as usize;
142        // FIXME: Performance
143        let start = lines.start.start();
144        let meta_start = address_to_meta_address(&unlog_bit, start);
145        let meta_bytes =
146            Line::steps_between(&lines.start, &lines.end).unwrap() << log_meta_bytes_per_line;
147        crate::util::memory::zero(meta_start, meta_bytes)
148    }
149
150    pub fn initialize_field_unlog_table_as_unlogged<VM: VMBinding>(lines: Range<Line>) {
151        let unlog_bit = *VM::VMObjectModel::GLOBAL_FIELD_UNLOG_BIT_SPEC
152            .as_spec()
153            .extract_side_spec();
154        let log_meta_bits_per_line = const {
155            Line::LOG_BYTES + LOG_BITS_IN_BYTE as usize
156                - VM::VMObjectModel::GLOBAL_FIELD_UNLOG_BIT_SPEC.log_heap_bytes_per_unlog_byte()
157        };
158        debug_assert!((1 << log_meta_bits_per_line) >= 8);
159        let log_meta_bytes_per_line = log_meta_bits_per_line - LOG_BITS_IN_BYTE as usize;
160        // FIXME: Performance
161        let start = lines.start.start();
162        let meta_start = address_to_meta_address(&unlog_bit, start);
163        let meta_bytes =
164            Line::steps_between(&lines.start, &lines.end).unwrap() << log_meta_bytes_per_line;
165        unsafe {
166            std::ptr::write_bytes::<u8>(meta_start.to_mut_ptr(), 0xffu8, meta_bytes);
167        }
168    }
169}
170
171// type UInt<const BITS: usize> =
172
173pub trait UintType: 'static + Sized {
174    type Type: 'static + Sized + Copy + Eq + PartialEq;
175    fn is_zero(v: Self::Type) -> bool;
176}
177
178pub struct Uint<const BITS: usize> {}
179
180impl UintType for Uint<8> {
181    type Type = u8;
182    fn is_zero(v: Self::Type) -> bool {
183        v == 0
184    }
185}
186
187impl UintType for Uint<16> {
188    type Type = u16;
189    fn is_zero(v: Self::Type) -> bool {
190        v == 0
191    }
192}
193
194impl UintType for Uint<32> {
195    type Type = u32;
196    fn is_zero(v: Self::Type) -> bool {
197        v == 0
198    }
199}
200
201impl UintType for Uint<64> {
202    type Type = u64;
203    fn is_zero(v: Self::Type) -> bool {
204        v == 0
205    }
206}
207
208impl UintType for Uint<128> {
209    type Type = u128;
210    fn is_zero(v: Self::Type) -> bool {
211        v == 0
212    }
213}
214
215#[repr(transparent)]
216#[derive(Clone, Copy, Eq, PartialEq)]
217pub struct UInt256([u8; 256 / 8]);
218
219impl UintType for Uint<256> {
220    type Type = UInt256;
221    fn is_zero(v: Self::Type) -> bool {
222        v == UInt256([0; 256 / 8])
223    }
224}
225
226#[repr(transparent)]
227#[derive(Clone, Copy, Eq, PartialEq)]
228pub struct UInt512([u8; 512 / 8]);
229
230impl UintType for Uint<512> {
231    type Type = UInt512;
232    fn is_zero(v: Self::Type) -> bool {
233        v == UInt512([0; 512 / 8])
234    }
235}
236
237#[repr(transparent)]
238#[derive(Clone, Copy, Eq, PartialEq)]
239pub struct UInt1024([u8; 1024 / 8]);
240
241impl UintType for Uint<1024> {
242    type Type = UInt1024;
243    fn is_zero(v: Self::Type) -> bool {
244        v == UInt1024([0; 1024 / 8])
245    }
246}
247
248#[repr(transparent)]
249#[derive(Clone, Copy, Eq, PartialEq)]
250pub struct UInt2048([u8; 2048 / 8]);
251
252impl UintType for Uint<2048> {
253    type Type = UInt2048;
254    fn is_zero(v: Self::Type) -> bool {
255        v == UInt2048([0; 2048 / 8])
256    }
257}
258
259const LOG_BITS_PER_LINE: usize = Line::LOG_BYTES - rc::LOG_MIN_OBJECT_SIZE + rc::LOG_REF_COUNT_BITS;
260const BITS_PER_LINE: usize = 1 << LOG_BITS_PER_LINE;
261const LOG_BITS_PER_BLOCK: usize =
262    Block::LOG_BYTES - rc::LOG_MIN_OBJECT_SIZE + rc::LOG_REF_COUNT_BITS;
263const BITS_PER_BLOCK: usize = 1 << LOG_BITS_PER_BLOCK;
264
265pub struct RCArray {
266    table: &'static [<Uint<{ BITS_PER_LINE }> as UintType>::Type; BITS_PER_BLOCK / BITS_PER_LINE],
267}
268
269impl RCArray {
270    pub fn of(block: Block) -> Self {
271        Self {
272            table: unsafe { &*block.rc_table_start().to_ptr() },
273        }
274    }
275
276    pub fn is_dead(&self, i: usize) -> bool {
277        <Uint<{ BITS_PER_LINE }> as UintType>::is_zero(self.table[i])
278    }
279}
mmtk/policy/immix/line.rs

mmtk/policy/immix/
line.rs
