mmtk/util/
rc.rs

1use std::marker::PhantomData;
2use std::sync::atomic::{AtomicU32, AtomicUsize};
3
4use crate::util::linear_scan::Region;
5use crate::util::{metadata::side_metadata::address_to_meta_address, Address};
6use crate::{
7    policy::immix::{block::Block, line::Line},
8    util::{metadata::side_metadata::SideMetadataSpec, ObjectReference},
9    vm::*,
10};
11use atomic::Ordering;
12
13/// Log2 of the number of bits used to store each object's reference count in the RC table.
14pub const LOG_REF_COUNT_BITS: usize = 1;
15/// Number of bits used to store each object's reference count in the RC table.
16pub const REF_COUNT_BITS: u8 = 1 << LOG_REF_COUNT_BITS;
17/// Bit mask covering the bits used to store a reference count.
18pub const REF_COUNT_MASK: u8 = (((1u16 << REF_COUNT_BITS) - 1) & 0xff) as u8;
19/// The maximum representable reference count. Once an object's count reaches this value it
20/// is treated as saturated/sticky and is no longer incremented or decremented.
21pub const MAX_REF_COUNT: u8 = REF_COUNT_MASK;
22
23/// Log2 of the minimum object size, i.e. the granularity at which reference counts are tracked.
24pub const LOG_MIN_OBJECT_SIZE: usize = crate::util::constants::LOG_MIN_OBJECT_SIZE as _;
25/// The minimum object size, i.e. the granularity at which reference counts are tracked.
26pub const MIN_OBJECT_SIZE: usize = 1 << LOG_MIN_OBJECT_SIZE;
27
28/// Side metadata recording which Immix lines are "straddled" by an object that spans
29/// multiple lines, so straddling objects can be identified without scanning their contents.
30pub const RC_STRADDLE_LINES: SideMetadataSpec =
31    crate::util::metadata::side_metadata::spec_defs::RC_STRADDLE_LINES;
32
33/// Side metadata spec for the per-object reference count table.
34pub const RC_TABLE: SideMetadataSpec = crate::util::metadata::side_metadata::spec_defs::RC_TABLE;
35
36static INC_BUFFER_SIZE: AtomicUsize = AtomicUsize::new(0);
37
38static TOTAL_INCS_PACKETS: AtomicU32 = AtomicU32::new(0);
39
40static TOTAL_INCS: AtomicU32 = AtomicU32::new(0);
41static ROOT_INCS: AtomicU32 = AtomicU32::new(0);
42static MATURE_INCS: AtomicU32 = AtomicU32::new(0);
43static NURSERY_INCS: AtomicU32 = AtomicU32::new(0);
44static FAST_NURSERY_INCS: AtomicU32 = AtomicU32::new(0);
45static LOS_INCS: AtomicU32 = AtomicU32::new(0);
46
47static PROMOTED_OBJECTS: AtomicU32 = AtomicU32::new(0);
48static PROMOTED_SCALARS: [AtomicU32; 3] = [AtomicU32::new(0), AtomicU32::new(0), AtomicU32::new(0)];
49static PROMOTED_PRIM_ARRAYS: [AtomicU32; 3] =
50    [AtomicU32::new(0), AtomicU32::new(0), AtomicU32::new(0)];
51static PROMOTED_OBJECT_ARRAYS: [AtomicU32; 3] =
52    [AtomicU32::new(0), AtomicU32::new(0), AtomicU32::new(0)];
53
54/// A zero-sized helper type providing methods to read and update per-object reference count
55/// metadata for LXR's reference counting plan.
56#[repr(transparent)]
57#[derive(Debug, Copy)]
58pub struct RefCountHelper<VM: VMBinding>(PhantomData<VM>);
59
60impl<VM: VMBinding> RefCountHelper<VM> {
61    /// A singleton instance of `RefCountHelper` (the type is zero-sized, so it can be freely copied/cloned).
62    pub const NEW: Self = Self(PhantomData);
63    /// Whether extra reference-counting sanity checks are enabled (debug builds or the `sanity` feature).
64    pub const SANITY: bool = cfg!(debug_assertions) || cfg!(feature = "sanity");
65
66    /// Returns the current size of the global increment buffer, i.e. the number of pending
67    /// reference count increments that have been enqueued but not yet processed.
68    pub fn inc_buffer_size(&self) -> usize {
69        INC_BUFFER_SIZE.load(Ordering::Relaxed)
70    }
71
72    /// Increases the global increment buffer size counter by `delta`.
73    pub fn increase_inc_buffer_size(&self, delta: usize) {
74        INC_BUFFER_SIZE.store(
75            INC_BUFFER_SIZE
76                .load(Ordering::Relaxed)
77                .saturating_add(delta),
78            Ordering::Relaxed,
79        );
80    }
81
82    /// Resets the global increment buffer size counter to zero.
83    pub fn reset_inc_buffer_size(&self) {
84        INC_BUFFER_SIZE.store(0, Ordering::Relaxed)
85    }
86
87    /// Atomically updates the reference count of object `o` by applying `f` to its current
88    /// value, following the same semantics as `AtomicU8::fetch_update`.
89    pub fn fetch_update(
90        &self,
91        o: ObjectReference,
92        f: impl FnMut(u8) -> Option<u8>,
93    ) -> Result<u8, u8> {
94        RC_TABLE.fetch_update_atomic(o.to_raw_address(), Ordering::Relaxed, Ordering::Relaxed, f)
95    }
96
97    /// Returns `true` if object `o`'s reference count has saturated at `MAX_REF_COUNT` (sticky).
98    pub fn is_stuck(&self, o: ObjectReference) -> bool {
99        self.count(o) == MAX_REF_COUNT
100    }
101
102    /// Forces object `o`'s reference count to `MAX_REF_COUNT`, permanently marking it as sticky
103    /// so it is never reclaimed by reference counting.
104    pub fn stick(&self, o: ObjectReference) -> Result<u8, u8> {
105        self.fetch_update(o, |x| {
106            debug_assert!(x <= MAX_REF_COUNT);
107            if x == MAX_REF_COUNT {
108                None
109            } else {
110                Some(MAX_REF_COUNT)
111            }
112        })
113    }
114
115    /// Increments object `o`'s reference count by one, leaving it unchanged (saturating) once
116    /// it has reached `MAX_REF_COUNT`.
117    pub fn inc(&self, o: ObjectReference) -> Result<u8, u8> {
118        #[cfg(feature = "vo_bit")]
119        debug_assert!(
120            crate::util::metadata::vo_bit::is_vo_bit_set(o),
121            "{o}: VO bit not set",
122        );
123
124        self.fetch_update(o, |x| {
125            debug_assert!(x <= MAX_REF_COUNT);
126            if x == MAX_REF_COUNT {
127                None
128            } else {
129                Some(x + 1)
130            }
131        })
132    }
133
134    /// Decrements object `o`'s reference count by one, unless it is already zero or has
135    /// saturated at `MAX_REF_COUNT` (sticky), in which case it is left unchanged.
136    pub fn dec(&self, o: ObjectReference) -> Result<u8, u8> {
137        #[cfg(feature = "vo_bit")]
138        debug_assert!(
139            crate::util::metadata::vo_bit::is_vo_bit_set(o),
140            "{o}: VO bit not set",
141        );
142
143        self.fetch_update(o, |x| {
144            debug_assert!(x <= MAX_REF_COUNT);
145            if x == 0 || x == MAX_REF_COUNT
146            /* sticky */
147            {
148                None
149            } else {
150                Some(x - 1)
151            }
152        })
153    }
154
155    /// Atomically sets object `o`'s reference count to `count`.
156    pub fn set(&self, o: ObjectReference, count: u8) {
157        RC_TABLE.store_atomic(o.to_raw_address(), count, Ordering::Relaxed)
158    }
159
160    /// Sets object `o`'s reference count to `count` using a non-atomic store, for use where the
161    /// caller can guarantee there is no concurrent access.
162    pub fn set_relaxed(&self, o: ObjectReference, count: u8) {
163        unsafe { RC_TABLE.store(o.to_raw_address(), count) }
164    }
165
166    /// Sets the reference count for the line containing object `o` to `count` using a non-atomic store,
167    /// for use where the caller can guarantee there is no concurrent access.
168    pub fn set_line_relaxed(&self, line: Line, count: u8) {
169        unsafe { RC_TABLE.store(line.start(), count) }
170    }
171
172    /// Returns object `o`'s current reference count.
173    pub fn count(&self, o: ObjectReference) -> u8 {
174        RC_TABLE.load_atomic(o.to_raw_address(), Ordering::Relaxed)
175    }
176
177    /// Returns the reference count stored in the RC table at address `addr`. If this
178    /// returns a non-zero value, it indicates that `addr` is the address of an object reference,
179    /// or the start of a straddle line.
180    pub fn count_by_address(&self, addr: Address) -> u8 {
181        RC_TABLE.load_atomic(addr, Ordering::Relaxed)
182    }
183
184    /// Returns `true` if the RC table entry at `o`'s address is zero. Used for both individual
185    /// objects and line-granularity entries (e.g. straddle line markers), which share the same table.
186    pub fn object_or_line_is_dead(&self, o: ObjectReference) -> bool {
187        RC_TABLE.load_byte(o.to_raw_address()) == 0
188    }
189
190    /// Returns a slice view over the raw RC table memory covering block `b`, reinterpreted as an
191    /// array of `UInt`, allowing the block's reference counts to be scanned in bulk.
192    pub fn rc_table_range<UInt: Sized>(&self, b: Block) -> &'static [UInt] {
193        debug_assert!({
194            let log_bits_in_uint: usize =
195                (std::mem::size_of::<UInt>() << 3).trailing_zeros() as usize;
196            Block::LOG_BYTES - super::rc::LOG_MIN_OBJECT_SIZE + super::rc::LOG_REF_COUNT_BITS
197                >= log_bits_in_uint
198        });
199        let start = address_to_meta_address(&super::rc::RC_TABLE, b.start()).to_ptr::<UInt>();
200        let limit = address_to_meta_address(&super::rc::RC_TABLE, b.end()).to_ptr::<UInt>();
201        let rc_table = unsafe { std::slice::from_raw_parts(start, limit.offset_from(start) as _) };
202        rc_table
203    }
204
205    /// Returns `true` if object `o`'s reference count is zero.
206    #[allow(unused)]
207    pub fn is_dead(&self, o: ObjectReference) -> bool {
208        let v: u8 = RC_TABLE.load_atomic(o.to_raw_address(), Ordering::Relaxed);
209        v == 0
210    }
211
212    /// Returns `true` if object `o`'s reference count is zero (dead) or has saturated at
213    /// `MAX_REF_COUNT` (sticky).
214    pub fn is_dead_or_stuck(&self, o: ObjectReference) -> bool {
215        let v: u8 = RC_TABLE.load_atomic(o.to_raw_address(), Ordering::Relaxed);
216        v == 0 || v == MAX_REF_COUNT
217    }
218
219    /// Returns `true` if object `o` is in a straddle line. The function does not check rc table.
220    pub fn object_is_in_straddle_line_no_rc_check(&self, o: ObjectReference) -> bool {
221        // This directly reads line-granularity straddle line metadata with an unaligned address.
222        // It is still correct, but may break side metadata assertions.
223        unsafe { RC_STRADDLE_LINES.load::<u8>(o.to_raw_address()) != 0 }
224    }
225
226    /// Returns `true` if address `a` falls within a live object whose containing line is marked
227    /// as a straddle line.
228    pub fn object_is_in_straddle_line(&self, o: ObjectReference) -> bool {
229        let line = Line::from_unaligned_address(o.to_raw_address());
230        self.count(o) != 0 && unsafe { RC_STRADDLE_LINES.load::<u8>(line.start()) != 0 }
231    }
232
233    fn mark_straddle_object_with_size(&self, o: ObjectReference, size: usize) {
234        debug_assert!(size > Line::BYTES);
235        let start = o.to_object_start::<VM>();
236        let end = start + size;
237        let start_line = Line::from_unaligned_address(start).next();
238        let end_line = Line::from_unaligned_address(end);
239        // Note that `end_line` may be the last line overlapping with `o`.
240        // In that case, `end_line` will not be marked.
241        // It is OK because when searching for available lines (`rc_get_next_available_lines`),
242        // it always skips the first line in a hole.
243        let mut line = start_line;
244        while line != end_line {
245            unsafe { RC_STRADDLE_LINES.store(line.start(), 1u8) };
246            self.set_line_relaxed(line, 1);
247            line = line.next();
248        }
249    }
250
251    /// Marks every line (other than the first) spanned by object `o` as a straddle line, so the
252    /// object can be identified from any of the lines it straddles.
253    pub fn mark_straddle_object(&self, o: ObjectReference) {
254        let size = VM::VMObjectModel::get_current_size(o);
255        self.mark_straddle_object_with_size(o, size)
256    }
257
258    /// Clears the straddle-line and reference-count markers set by `mark_straddle_object` for
259    /// every line (other than the first) spanned by object `o`.
260    pub fn unmark_straddle_object(&self, o: ObjectReference) {
261        // debug_assert!(crate::args::RC_NURSERY_EVACUATION);
262        let size = VM::VMObjectModel::get_current_size(o);
263        if size > Line::BYTES {
264            let start = o.to_object_start::<VM>();
265            let end = start + size;
266            let start_line = Line::from_unaligned_address(start).next();
267            let end_line = Line::from_unaligned_address(end);
268            // Note that `end_line` may be the last line overlapping with `o`.
269            // In that case, `end_line` will not be marked.
270            // It is OK because when searching for available lines (`rc_get_next_available_lines`),
271            // it always skips the first line in a hole.
272            let mut line = start_line;
273            while line != end_line {
274                self.set_line_relaxed(line, 0);
275                unsafe { RC_STRADDLE_LINES.store(line.start(), 0u8) };
276                line = line.next();
277            }
278        }
279    }
280
281    /// Debug assertion that every `MIN_OBJECT_SIZE` granule within object `o` has a reference
282    /// count of zero, used to verify that a reclaimed object has been fully cleared.
283    pub fn assert_zero_ref_count(&self, o: ObjectReference) {
284        let size = VM::VMObjectModel::get_current_size(o);
285        for i in (0..size).step_by(MIN_OBJECT_SIZE) {
286            let a = o.to_raw_address() + i;
287            assert_eq!(0, self.count_by_address(a));
288        }
289    }
290
291    /// Called when object `o` is promoted to mature space; marks it as a straddle object if it
292    /// spans more than one line, deriving its size from the VM binding.
293    pub fn promote(&self, o: ObjectReference) {
294        let size = o.get_size::<VM>();
295        if size > Line::BYTES {
296            self.mark_straddle_object_with_size(o, size);
297        }
298    }
299
300    /// Same as `promote`, but with the object's size supplied by the caller instead of being
301    /// queried from the VM binding.
302    pub fn promote_with_size(&self, o: ObjectReference, size: usize) {
303        if size > Line::BYTES {
304            self.mark_straddle_object_with_size(o, size);
305        }
306    }
307}
308
309impl<VM: VMBinding> Clone for RefCountHelper<VM> {
310    fn clone(&self) -> Self {
311        Self(PhantomData)
312    }
313}
mmtk/util/rc.rs

mmtk/util/
rc.rs
