mmtk/policy/immix/
line.rs

1use std::ops::Range;
2
3use super::block::Block;
4use crate::util::constants::{LOG_BITS_IN_BYTE, LOG_BYTES_IN_WORD};
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 = Line::LOG_BYTES - LOG_BYTES_IN_WORD as usize
137            + if !VM::VMObjectModel::COMPRESSED_PTR_ENABLED {
138                0
139            } else {
140                1
141            };
142        debug_assert!((1 << log_meta_bits_per_line) >= 8);
143        let log_meta_bytes_per_line = log_meta_bits_per_line - LOG_BITS_IN_BYTE as usize;
144        // FIXME: Performance
145        let start = lines.start.start();
146        let meta_start = address_to_meta_address(&unlog_bit, start);
147        let meta_bytes =
148            Line::steps_between(&lines.start, &lines.end).unwrap() << log_meta_bytes_per_line;
149        crate::util::memory::zero(meta_start, meta_bytes)
150    }
151
152    pub fn initialize_field_unlog_table_as_unlogged<VM: VMBinding>(lines: Range<Line>) {
153        let unlog_bit = *VM::VMObjectModel::GLOBAL_FIELD_UNLOG_BIT_SPEC
154            .as_spec()
155            .extract_side_spec();
156        let log_meta_bits_per_line = Line::LOG_BYTES - LOG_BYTES_IN_WORD as usize
157            + if !VM::VMObjectModel::COMPRESSED_PTR_ENABLED {
158                0
159            } else {
160                1
161            };
162        debug_assert!((1 << log_meta_bits_per_line) >= 8);
163        let log_meta_bytes_per_line = log_meta_bits_per_line - LOG_BITS_IN_BYTE as usize;
164        // FIXME: Performance
165        let start = lines.start.start();
166        let meta_start = address_to_meta_address(&unlog_bit, start);
167        let meta_bytes =
168            Line::steps_between(&lines.start, &lines.end).unwrap() << log_meta_bytes_per_line;
169        unsafe {
170            std::ptr::write_bytes::<u8>(meta_start.to_mut_ptr(), 0xffu8, meta_bytes);
171        }
172    }
173}
174
175// type UInt<const BITS: usize> =
176
177pub trait UintType: 'static + Sized {
178    type Type: 'static + Sized + Copy + Eq + PartialEq;
179    fn is_zero(v: Self::Type) -> bool;
180}
181
182pub struct Uint<const BITS: usize> {}
183
184impl UintType for Uint<8> {
185    type Type = u8;
186    fn is_zero(v: Self::Type) -> bool {
187        v == 0
188    }
189}
190
191impl UintType for Uint<16> {
192    type Type = u16;
193    fn is_zero(v: Self::Type) -> bool {
194        v == 0
195    }
196}
197
198impl UintType for Uint<32> {
199    type Type = u32;
200    fn is_zero(v: Self::Type) -> bool {
201        v == 0
202    }
203}
204
205impl UintType for Uint<64> {
206    type Type = u64;
207    fn is_zero(v: Self::Type) -> bool {
208        v == 0
209    }
210}
211
212impl UintType for Uint<128> {
213    type Type = u128;
214    fn is_zero(v: Self::Type) -> bool {
215        v == 0
216    }
217}
218
219#[repr(transparent)]
220#[derive(Clone, Copy, Eq, PartialEq)]
221pub struct UInt256([u8; 256 / 8]);
222
223impl UintType for Uint<256> {
224    type Type = UInt256;
225    fn is_zero(v: Self::Type) -> bool {
226        v == UInt256([0; 256 / 8])
227    }
228}
229
230#[repr(transparent)]
231#[derive(Clone, Copy, Eq, PartialEq)]
232pub struct UInt512([u8; 512 / 8]);
233
234impl UintType for Uint<512> {
235    type Type = UInt512;
236    fn is_zero(v: Self::Type) -> bool {
237        v == UInt512([0; 512 / 8])
238    }
239}
240
241#[repr(transparent)]
242#[derive(Clone, Copy, Eq, PartialEq)]
243pub struct UInt1024([u8; 1024 / 8]);
244
245impl UintType for Uint<1024> {
246    type Type = UInt1024;
247    fn is_zero(v: Self::Type) -> bool {
248        v == UInt1024([0; 1024 / 8])
249    }
250}
251
252#[repr(transparent)]
253#[derive(Clone, Copy, Eq, PartialEq)]
254pub struct UInt2048([u8; 2048 / 8]);
255
256impl UintType for Uint<2048> {
257    type Type = UInt2048;
258    fn is_zero(v: Self::Type) -> bool {
259        v == UInt2048([0; 2048 / 8])
260    }
261}
262
263const LOG_BITS_PER_LINE: usize = Line::LOG_BYTES - rc::LOG_MIN_OBJECT_SIZE + rc::LOG_REF_COUNT_BITS;
264const BITS_PER_LINE: usize = 1 << LOG_BITS_PER_LINE;
265const LOG_BITS_PER_BLOCK: usize =
266    Block::LOG_BYTES - rc::LOG_MIN_OBJECT_SIZE + rc::LOG_REF_COUNT_BITS;
267const BITS_PER_BLOCK: usize = 1 << LOG_BITS_PER_BLOCK;
268
269pub struct RCArray {
270    table: &'static [<Uint<{ BITS_PER_LINE }> as UintType>::Type; BITS_PER_BLOCK / BITS_PER_LINE],
271}
272
273impl RCArray {
274    pub fn of(block: Block) -> Self {
275        Self {
276            table: unsafe { &*block.rc_table_start().to_ptr() },
277        }
278    }
279
280    pub fn is_dead(&self, i: usize) -> bool {
281        <Uint<{ BITS_PER_LINE }> as UintType>::is_zero(self.table[i])
282    }
283}
mmtk/policy/immix/line.rs

mmtk/policy/immix/
line.rs
