mmtk/util/metadata/vo_bit/
helper.rs

1//! This module updates of VO bits during GC.  It is used for spaces that do not clear the metadata
2//! of some dead objects during GC.  Currently, only ImmixSpace is affected.
3//!
4//! | Policy            | When are VO bits of dead objects cleared                      |
5//! |-------------------|---------------------------------------------------------------|
6//! | MarkSweepSpace    | when sweeping cells of dead objects                           |
7//! | MarkCompactSpace  | when compacting                                               |
8//! | CopySpace         | when releasing the space                                      |
9//!
10//! The policies listed above trivially clear the VO bits for dead objects (individually or in
11//! bulk), and make the VO bits available during tracing.
12//!
13//! For ImmixSpace, if a line contains both live and dead objects, live objects will be traced,
14//! but dead objects will not be visited.  Therefore we cannot clear the VO bits of individual
15//! dead objects.  We cannot clear all VO bits for the line in bulk because it contains live
16//! objects.  This module updates the VO bits for such regions (e.g. Immix lines, or Immix blocks
17//! if Immix is configured to be block-only).
18//!
19//! We implement several strategies depending on whether mmtk-core or the VM binding also requires
20//! the VO bits to also be available during tracing.
21//!
22//! The handling is very sensitive to `VOBitUpdateStrategy`, and may be a bit verbose.
23//! We abstract VO-bit-related code out of the main GC algorithms (such as Immix) to make it more
24//! readable.
25
26use atomic::Ordering;
27
28use crate::{
29    util::{
30        linear_scan::Region,
31        metadata::{vo_bit, MetadataSpec},
32        ObjectReference,
33    },
34    vm::{ObjectModel, VMBinding},
35};
36
37/// The strategy to update the valid object (VO) bits.
38///
39/// Each stategy has its strength and limitation.  We should choose a strategy according to the
40/// configuration of the VM binding.
41///
42/// Current experiments show that the `CopyFromMarkBits` strategy is faster while also makes the
43/// VO bits available during tracing.  We also include the `ClearAndReconstruct` strategy because
44///
45/// 1.  It was the strategy described in the original paper that described the algorithm for
46///     filtering roots using VO bits for stack-conservative GC.  See: *Fast Conservative Garbage
47///     Collection* published in OOPSLA'14 <https://dl.acm.org/doi/10.1145/2660193.2660198>
48/// 2.  It does not require mark bits to be on the side.  It will be needed if we implement
49///     in-header mark bits in the future.
50#[derive(Debug)]
51enum VOBitUpdateStrategy {
52    /// Clear all VO bits after stacks are scanned, and reconstruct the VO bits during tracing.
53    ///
54    /// Pros:
55    /// -   Proven to work by published paper.
56    ///
57    /// Cons:
58    /// -   VO bits are not available during tracing.
59    ClearAndReconstruct,
60    /// Copy the mark bits metadata over to the VO bits metadata after tracing.
61    ///
62    /// Pros:
63    /// -   VO bits are available during tracing.
64    /// -   Faster according to current experiment.
65    ///
66    /// Cons:
67    /// -   Requires marking bits to be on the side.
68    CopyFromMarkBits,
69}
70
71impl VOBitUpdateStrategy {
72    /// Return `true` if the VO bit metadata is available during tracing.
73    pub fn vo_bit_available_during_tracing(&self) -> bool {
74        match *self {
75            VOBitUpdateStrategy::ClearAndReconstruct => false,
76            VOBitUpdateStrategy::CopyFromMarkBits => true,
77        }
78    }
79}
80
81/// Select a strategy for the VM.  It is a `const` function so it always returns the same strategy
82/// for a given VM.
83const fn strategy<VM: VMBinding>() -> VOBitUpdateStrategy {
84    // CopyFromMarkBits performs better than ClearAndReconstruct, and it also allows using
85    // VO bits during tracing. We use it as the default strategy.
86    // TODO: Revisit this choice in the future if non-trivial changes are made and the performance
87    // characterestics may change for the strategies.
88    match VM::VMObjectModel::LOCAL_MARK_BIT_SPEC.as_spec() {
89        // Note that currently ImmixSpace doesn't support in-header mark bits,
90        // but the DummyVM for testing declares mark bits to be "in header" as a place holder
91        // because it never runs GC.
92        MetadataSpec::InHeader(_) => VOBitUpdateStrategy::ClearAndReconstruct,
93        MetadataSpec::OnSide(_) => VOBitUpdateStrategy::CopyFromMarkBits,
94    }
95}
96
97pub(crate) fn validate_config<VM: VMBinding>() {
98    assert!(
99        !(VM::VMObjectModel::NEED_VO_BITS_DURING_TRACING
100            && VM::VMObjectModel::LOCAL_MARK_BIT_SPEC
101                .as_spec()
102                .is_in_header()),
103        "The VM binding needs VO bits during tracing but also has in-header mark bits.  \
104We currently don't have an appropriate strategy for this case."
105    );
106
107    let s = strategy::<VM>();
108    match s {
109        VOBitUpdateStrategy::ClearAndReconstruct => {
110            // Always valid
111        }
112        VOBitUpdateStrategy::CopyFromMarkBits => {
113            let mark_bit_spec = VM::VMObjectModel::LOCAL_MARK_BIT_SPEC;
114            assert!(
115                mark_bit_spec.is_on_side(),
116                "The {s:?} strategy requires the mark bits to be on the side."
117            );
118
119            let mark_bit_meta = mark_bit_spec.extract_side_spec();
120            let vo_bit_meta = vo_bit::VO_BIT_SIDE_METADATA_SPEC;
121
122            assert_eq!(
123                mark_bit_meta.log_bytes_in_region,
124                vo_bit_meta.log_bytes_in_region,
125                "The {s:?} strategy requires the mark bits to have the same granularity as the VO bits."
126            );
127            assert_eq!(mark_bit_meta.log_num_of_bits, vo_bit_meta.log_num_of_bits,
128                "The {s:?} strategy requires the mark bits to have the same number of bits per object as the VO bits.");
129        }
130    }
131}
132
133pub(crate) fn need_to_clear_vo_bits_before_tracing<VM: VMBinding>() -> bool {
134    match strategy::<VM>() {
135        VOBitUpdateStrategy::ClearAndReconstruct => true,
136        VOBitUpdateStrategy::CopyFromMarkBits => false,
137    }
138}
139
140pub(crate) fn on_trace_object<VM: VMBinding>(object: ObjectReference) {
141    if strategy::<VM>().vo_bit_available_during_tracing() {
142        // If the VO bits are available during tracing,
143        // we validate the objects we trace using the VO bits.
144        debug_assert!(
145            vo_bit::is_vo_bit_set(object),
146            "{:x}: VO bit not set",
147            object
148        );
149    }
150}
151
152pub(crate) fn on_object_marked<VM: VMBinding>(object: ObjectReference) {
153    match strategy::<VM>() {
154        VOBitUpdateStrategy::ClearAndReconstruct => {
155            // In this strategy, we set the VO bit when an object is marked.
156            vo_bit::set_vo_bit(object);
157        }
158        VOBitUpdateStrategy::CopyFromMarkBits => {
159            // VO bit was not cleared before tracing in this strategy.  Do nothing.
160        }
161    }
162}
163
164pub(crate) fn on_object_forwarded<VM: VMBinding>(new_object: ObjectReference) {
165    match strategy::<VM>() {
166        VOBitUpdateStrategy::ClearAndReconstruct => {
167            // In this strategy, we set the VO bit of the to-space object when forwarded.
168            vo_bit::set_vo_bit(new_object);
169        }
170        VOBitUpdateStrategy::CopyFromMarkBits => {
171            // In this strategy, we will copy mark bits to VO bits.
172            // We need to set mark bits for to-space objects, too.
173            VM::VMObjectModel::LOCAL_MARK_BIT_SPEC.store_atomic::<VM, u8>(
174                new_object,
175                1,
176                None,
177                Ordering::SeqCst,
178            );
179
180            // We set the VO bit for the to-space object eagerly.
181            vo_bit::set_vo_bit(new_object);
182        }
183    }
184}
185
186pub(crate) fn on_region_swept<VM: VMBinding, R: Region>(region: &R, is_occupied: bool) {
187    match strategy::<VM>() {
188        VOBitUpdateStrategy::ClearAndReconstruct => {
189            // Do nothing.  The VO bit metadata is already reconstructed.
190        }
191        VOBitUpdateStrategy::CopyFromMarkBits => {
192            // In this strategy, we need to update the VO bits state after marking.
193            if is_occupied {
194                // If the block has live objects, copy the VO bits from mark bits.
195                vo_bit::bcopy_vo_bit_from_mark_bit::<VM>(region.start(), R::BYTES);
196            } else {
197                // If the block has no live objects, simply clear the VO bits.
198                vo_bit::bzero_vo_bit(region.start(), R::BYTES);
199            }
200        }
201    }
202}
mmtk/util/metadata/vo_bit/helper.rs

mmtk/util/metadata/vo_bit/
helper.rs
