mmtk/util/
object_forwarding.rs

1use crate::util::copy::*;
2use crate::util::metadata::MetadataSpec;
3use crate::util::{constants, ObjectReference};
4use crate::vm::ObjectModel;
5use crate::vm::VMBinding;
6use std::sync::atomic::Ordering;
7
8const FORWARDING_NOT_TRIGGERED_YET: u8 = 0b00;
9const BEING_FORWARDED: u8 = 0b10;
10const FORWARDED: u8 = 0b11;
11const FORWARDING_MASK: u8 = 0b11;
12#[allow(unused)]
13const FORWARDING_BITS: usize = 2;
14
15// copy address mask
16#[cfg(target_pointer_width = "64")]
17const FORWARDING_POINTER_MASK: usize = 0x00ff_ffff_ffff_fff8;
18#[cfg(target_pointer_width = "32")]
19const FORWARDING_POINTER_MASK: usize = 0xffff_fffc;
20
21/// Attempt to become the worker thread who will forward the object.
22/// The successful worker will set the object forwarding bits to BEING_FORWARDED, preventing other workers from forwarding the same object.
23pub fn attempt_to_forward<VM: VMBinding>(object: ObjectReference) -> u8 {
24    loop {
25        let old_value = get_forwarding_status::<VM>(object);
26        if old_value != FORWARDING_NOT_TRIGGERED_YET
27            || VM::VMObjectModel::LOCAL_FORWARDING_BITS_SPEC
28                .compare_exchange_metadata::<VM, u8>(
29                    object,
30                    old_value,
31                    BEING_FORWARDED,
32                    None,
33                    Ordering::SeqCst,
34                    Ordering::Relaxed,
35                )
36                .is_ok()
37        {
38            return old_value;
39        }
40    }
41}
42
43/// Spin-wait for the object's forwarding to become complete and then read the forwarding pointer to the new object.
44///
45/// # Arguments:
46///
47/// * `object`: the forwarded/being_forwarded object.
48/// * `forwarding_bits`: the last state of the forwarding bits before calling this function.
49///
50/// Returns a reference to the new object.
51///
52pub fn spin_and_get_forwarded_object<VM: VMBinding>(
53    object: ObjectReference,
54    forwarding_bits: u8,
55) -> ObjectReference {
56    let mut forwarding_bits = forwarding_bits;
57    while forwarding_bits == BEING_FORWARDED {
58        forwarding_bits = get_forwarding_status::<VM>(object);
59    }
60
61    if forwarding_bits == FORWARDED {
62        read_forwarding_pointer::<VM>(object)
63    } else {
64        // For some policies (such as Immix), we can have interleaving such that one thread clears
65        // the forwarding word while another thread was stuck spinning in the above loop.
66        // See: https://github.com/mmtk/mmtk-core/issues/579
67        debug_assert!(
68            forwarding_bits == FORWARDING_NOT_TRIGGERED_YET,
69            "Invalid/Corrupted forwarding word {:x} for object {}",
70            forwarding_bits,
71            object,
72        );
73        object
74    }
75}
76
77pub fn try_forward_object<VM: VMBinding>(
78    object: ObjectReference,
79    semantics: CopySemantics,
80    copy_context: &mut GCWorkerCopyContext<VM>,
81    on_after_forwarding: impl FnOnce(ObjectReference),
82) -> Option<ObjectReference> {
83    let new_object = VM::VMObjectModel::try_copy(object, semantics, copy_context)?;
84    on_after_forwarding(new_object);
85    if let Some(shift) = forwarding_bits_offset_in_forwarding_pointer::<VM>() {
86        VM::VMObjectModel::LOCAL_FORWARDING_POINTER_SPEC.store_atomic::<VM, usize>(
87            object,
88            new_object.to_raw_address().as_usize() | ((FORWARDED as usize) << shift),
89            None,
90            Ordering::SeqCst,
91        )
92    } else {
93        write_forwarding_pointer::<VM>(object, new_object);
94        VM::VMObjectModel::LOCAL_FORWARDING_BITS_SPEC.store_atomic::<VM, u8>(
95            object,
96            FORWARDED,
97            None,
98            Ordering::SeqCst,
99        );
100    }
101    Some(new_object)
102}
103
104/// Copy an object and set the forwarding state.
105///
106/// The caller can use `on_after_forwarding` to set extra metadata (including VO bits, mark bits,
107/// etc.) after the object is copied, but before the forwarding state is changed to `FORWARDED`. The
108/// atomic memory operation that sets the forwarding bits to `FORWARDED` has the `SeqCst` order.  It
109/// will guarantee that if another GC worker thread that attempts to forward the same object sees
110/// the forwarding bits being `FORWARDED`, it is guaranteed to see those extra metadata set.
111///
112/// Arguments:
113///
114/// *   `object`: The object to copy.
115/// *   `semantics`: The copy semantics.
116/// *   `copy_context`: A reference ot the `CopyContext` instance of the current GC worker.
117/// *   `on_after_forwarding`: A callback function that is called after `object` is copied, but
118///     before the forwarding bits are set.  Its argument is a reference to the new copy of
119///     `object`.
120pub fn forward_object<VM: VMBinding>(
121    object: ObjectReference,
122    semantics: CopySemantics,
123    copy_context: &mut GCWorkerCopyContext<VM>,
124    on_after_forwarding: impl FnOnce(ObjectReference),
125) -> ObjectReference {
126    let new_object = VM::VMObjectModel::copy(object, semantics, copy_context);
127    on_after_forwarding(new_object);
128    if let Some(shift) = forwarding_bits_offset_in_forwarding_pointer::<VM>() {
129        VM::VMObjectModel::LOCAL_FORWARDING_POINTER_SPEC.store_atomic::<VM, usize>(
130            object,
131            new_object.to_raw_address().as_usize() | ((FORWARDED as usize) << shift),
132            None,
133            Ordering::SeqCst,
134        )
135    } else {
136        write_forwarding_pointer::<VM>(object, new_object);
137        VM::VMObjectModel::LOCAL_FORWARDING_BITS_SPEC.store_atomic::<VM, u8>(
138            object,
139            FORWARDED,
140            None,
141            Ordering::SeqCst,
142        );
143    }
144    new_object
145}
146
147/// Return the forwarding bits for a given `ObjectReference`.
148pub fn get_forwarding_status<VM: VMBinding>(object: ObjectReference) -> u8 {
149    VM::VMObjectModel::LOCAL_FORWARDING_BITS_SPEC.load_atomic::<VM, u8>(
150        object,
151        None,
152        Ordering::SeqCst,
153    )
154}
155
156pub fn is_forwarded<VM: VMBinding>(object: ObjectReference) -> bool {
157    get_forwarding_status::<VM>(object) == FORWARDED
158}
159
160pub fn is_being_forwarded<VM: VMBinding>(object: ObjectReference) -> bool {
161    get_forwarding_status::<VM>(object) == BEING_FORWARDED
162}
163
164pub fn is_forwarded_or_being_forwarded<VM: VMBinding>(object: ObjectReference) -> bool {
165    get_forwarding_status::<VM>(object) != FORWARDING_NOT_TRIGGERED_YET
166}
167
168pub fn state_is_forwarded_or_being_forwarded(forwarding_bits: u8) -> bool {
169    forwarding_bits != FORWARDING_NOT_TRIGGERED_YET
170}
171
172pub fn state_is_being_forwarded(forwarding_bits: u8) -> bool {
173    forwarding_bits == BEING_FORWARDED
174}
175
176/// Zero the forwarding bits of an object.
177/// This function is used on new objects.
178pub fn clear_forwarding_bits<VM: VMBinding>(object: ObjectReference) {
179    VM::VMObjectModel::LOCAL_FORWARDING_BITS_SPEC.store_atomic::<VM, u8>(
180        object,
181        0,
182        None,
183        Ordering::SeqCst,
184    )
185}
186
187/// Read the forwarding pointer of an object.
188/// This function is called on forwarded/being_forwarded objects.
189pub fn read_forwarding_pointer<VM: VMBinding>(object: ObjectReference) -> ObjectReference {
190    debug_assert!(
191        is_forwarded_or_being_forwarded::<VM>(object),
192        "read_forwarding_pointer called for object {:?} that has not started forwarding!",
193        object,
194    );
195
196    // We write the forwarding poiner. We know it is an object reference.
197    unsafe {
198        // We use "unchecked" convertion becasue we guarantee the forwarding pointer we stored
199        // previously is from a valid `ObjectReference` which is never zero.
200        ObjectReference::from_raw_address_unchecked(crate::util::Address::from_usize(
201            VM::VMObjectModel::LOCAL_FORWARDING_POINTER_SPEC.load_atomic::<VM, usize>(
202                object,
203                Some(FORWARDING_POINTER_MASK),
204                Ordering::SeqCst,
205            ),
206        ))
207    }
208}
209
210/// Write the forwarding pointer of an object.
211/// This function is called on being_forwarded objects.
212pub fn write_forwarding_pointer<VM: VMBinding>(
213    object: ObjectReference,
214    new_object: ObjectReference,
215) {
216    debug_assert!(
217        is_being_forwarded::<VM>(object),
218        "write_forwarding_pointer called for object {:?} that is not being forwarded! Forwarding state = 0x{:x}",
219        object,
220        get_forwarding_status::<VM>(object),
221    );
222
223    trace!("write_forwarding_pointer({}, {})", object, new_object);
224    VM::VMObjectModel::LOCAL_FORWARDING_POINTER_SPEC.store_atomic::<VM, usize>(
225        object,
226        new_object.to_raw_address().as_usize(),
227        Some(FORWARDING_POINTER_MASK),
228        Ordering::SeqCst,
229    )
230}
231
232/// (This function is only used internal to the `util` module)
233///
234/// This function checks whether the forwarding pointer and forwarding bits can be written in the same atomic operation.
235///
236/// Returns `None` if this is not possible.
237/// Otherwise, returns `Some(shift)`, where `shift` is the left shift needed on forwarding bits.
238///
239#[cfg(target_endian = "little")]
240pub(super) fn forwarding_bits_offset_in_forwarding_pointer<VM: VMBinding>() -> Option<isize> {
241    use std::ops::Deref;
242    // if both forwarding bits and forwarding pointer are in-header
243    match (
244        VM::VMObjectModel::LOCAL_FORWARDING_POINTER_SPEC.deref(),
245        VM::VMObjectModel::LOCAL_FORWARDING_BITS_SPEC.deref(),
246    ) {
247        (MetadataSpec::InHeader(fp), MetadataSpec::InHeader(fb)) => {
248            let maybe_shift = fb.bit_offset - fp.bit_offset;
249            if maybe_shift >= 0 && maybe_shift < constants::BITS_IN_WORD as isize {
250                Some(maybe_shift)
251            } else {
252                None
253            }
254        }
255        _ => None,
256    }
257}
258
259#[cfg(target_endian = "big")]
260pub(super) fn forwarding_bits_offset_in_forwarding_pointer<VM: VMBinding>() -> Option<isize> {
261    unimplemented!()
262}
263
264pub(crate) fn debug_print_object_forwarding_info<VM: VMBinding>(object: ObjectReference) {
265    let forwarding_bits = get_forwarding_status::<VM>(object);
266    println!(
267        "forwarding bits = {:?}, forwarding pointer = {:?}",
268        forwarding_bits,
269        if state_is_forwarded_or_being_forwarded(forwarding_bits) {
270            Some(read_forwarding_pointer::<VM>(object))
271        } else {
272            None
273        }
274    )
275}
mmtk/util/object_forwarding.rs

mmtk/util/
object_forwarding.rs
