1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202

//! This module updates of VO bits during GC.  It is used for spaces that do not clear the metadata
//! of some dead objects during GC.  Currently, only ImmixSpace is affected.
//!
//! | Policy            | When are VO bits of dead objects cleared                      |
//! |-------------------|---------------------------------------------------------------|
//! | MarkSweepSpace    | when sweeping cells of dead objects                           |
//! | MarkCompactSpace  | when compacting                                               |
//! | CopySpace         | when releasing the space                                      |
//!
//! The policies listed above trivially clear the VO bits for dead objects (individually or in
//! bulk), and make the VO bits available during tracing.
//!
//! For ImmixSpace, if a line contains both live and dead objects, live objects will be traced,
//! but dead objects will not be visited.  Therefore we cannot clear the VO bits of individual
//! dead objects.  We cannot clear all VO bits for the line in bulk because it contains live
//! objects.  This module updates the VO bits for such regions (e.g. Immix lines, or Immix blocks
//! if Immix is configured to be block-only).
//!
//! We implement several strategies depending on whether mmtk-core or the VM binding also requires
//! the VO bits to also be available during tracing.
//!
//! The handling is very sensitive to `VOBitUpdateStrategy`, and may be a bit verbose.
//! We abstract VO-bit-related code out of the main GC algorithms (such as Immix) to make it more
//! readable.

use atomic::Ordering;

use crate::{
    util::{
        linear_scan::Region,
        metadata::{vo_bit, MetadataSpec},
        ObjectReference,
    },
    vm::{ObjectModel, VMBinding},
};

/// The strategy to update the valid object (VO) bits.
///
/// Each stategy has its strength and limitation.  We should choose a strategy according to the
/// configuration of the VM binding.
///
/// Current experiments show that the `CopyFromMarkBits` strategy is faster while also makes the
/// VO bits available during tracing.  We also include the `ClearAndReconstruct` strategy because
///
/// 1.  It was the strategy described in the original paper that described the algorithm for
///     filtering roots using VO bits for stack-conservative GC.  See: *Fast Conservative Garbage
///     Collection* published in OOPSLA'14 <https://dl.acm.org/doi/10.1145/2660193.2660198>
/// 2.  It does not require mark bits to be on the side.  It will be needed if we implement
///     in-header mark bits in the future.
#[derive(Debug)]
enum VOBitUpdateStrategy {
    /// Clear all VO bits after stacks are scanned, and reconstruct the VO bits during tracing.
    ///
    /// Pros:
    /// -   Proven to work by published paper.
    ///
    /// Cons:
    /// -   VO bits are not available during tracing.
    ClearAndReconstruct,
    /// Copy the mark bits metadata over to the VO bits metadata after tracing.
    ///
    /// Pros:
    /// -   VO bits are available during tracing.
    /// -   Faster according to current experiment.
    ///
    /// Cons:
    /// -   Requires marking bits to be on the side.
    CopyFromMarkBits,
}

impl VOBitUpdateStrategy {
    /// Return `true` if the VO bit metadata is available during tracing.
    pub fn vo_bit_available_during_tracing(&self) -> bool {
        match *self {
            VOBitUpdateStrategy::ClearAndReconstruct => false,
            VOBitUpdateStrategy::CopyFromMarkBits => true,
        }
    }
}

/// Select a strategy for the VM.  It is a `const` function so it always returns the same strategy
/// for a given VM.
const fn strategy<VM: VMBinding>() -> VOBitUpdateStrategy {
    // CopyFromMarkBits performs better than ClearAndReconstruct, and it also allows using
    // VO bits during tracing. We use it as the default strategy.
    // TODO: Revisit this choice in the future if non-trivial changes are made and the performance
    // characterestics may change for the strategies.
    match VM::VMObjectModel::LOCAL_MARK_BIT_SPEC.as_spec() {
        // Note that currently ImmixSpace doesn't support in-header mark bits,
        // but the DummyVM for testing declares mark bits to be "in header" as a place holder
        // because it never runs GC.
        MetadataSpec::InHeader(_) => VOBitUpdateStrategy::ClearAndReconstruct,
        MetadataSpec::OnSide(_) => VOBitUpdateStrategy::CopyFromMarkBits,
    }
}

pub(crate) fn validate_config<VM: VMBinding>() {
    assert!(
        !(VM::VMObjectModel::NEED_VO_BITS_DURING_TRACING
            && VM::VMObjectModel::LOCAL_MARK_BIT_SPEC
                .as_spec()
                .is_in_header()),
        "The VM binding needs VO bits during tracing but also has in-header mark bits.  \
We currently don't have an appropriate strategy for this case."
    );

    let s = strategy::<VM>();
    match s {
        VOBitUpdateStrategy::ClearAndReconstruct => {
            // Always valid
        }
        VOBitUpdateStrategy::CopyFromMarkBits => {
            let mark_bit_spec = VM::VMObjectModel::LOCAL_MARK_BIT_SPEC;
            assert!(
                mark_bit_spec.is_on_side(),
                "The {s:?} strategy requires the mark bits to be on the side."
            );

            let mark_bit_meta = mark_bit_spec.extract_side_spec();
            let vo_bit_meta = vo_bit::VO_BIT_SIDE_METADATA_SPEC;

            assert_eq!(
                mark_bit_meta.log_bytes_in_region,
                vo_bit_meta.log_bytes_in_region,
                "The {s:?} strategy requires the mark bits to have the same granularity as the VO bits."
            );
            assert_eq!(mark_bit_meta.log_num_of_bits, vo_bit_meta.log_num_of_bits,
                "The {s:?} strategy requires the mark bits to have the same number of bits per object as the VO bits.");
        }
    }
}

pub(crate) fn need_to_clear_vo_bits_before_tracing<VM: VMBinding>() -> bool {
    match strategy::<VM>() {
        VOBitUpdateStrategy::ClearAndReconstruct => true,
        VOBitUpdateStrategy::CopyFromMarkBits => false,
    }
}

pub(crate) fn on_trace_object<VM: VMBinding>(object: ObjectReference) {
    if strategy::<VM>().vo_bit_available_during_tracing() {
        // If the VO bits are available during tracing,
        // we validate the objects we trace using the VO bits.
        debug_assert!(
            vo_bit::is_vo_bit_set(object),
            "{:x}: VO bit not set",
            object
        );
    }
}

pub(crate) fn on_object_marked<VM: VMBinding>(object: ObjectReference) {
    match strategy::<VM>() {
        VOBitUpdateStrategy::ClearAndReconstruct => {
            // In this strategy, we set the VO bit when an object is marked.
            vo_bit::set_vo_bit(object);
        }
        VOBitUpdateStrategy::CopyFromMarkBits => {
            // VO bit was not cleared before tracing in this strategy.  Do nothing.
        }
    }
}

pub(crate) fn on_object_forwarded<VM: VMBinding>(new_object: ObjectReference) {
    match strategy::<VM>() {
        VOBitUpdateStrategy::ClearAndReconstruct => {
            // In this strategy, we set the VO bit of the to-space object when forwarded.
            vo_bit::set_vo_bit(new_object);
        }
        VOBitUpdateStrategy::CopyFromMarkBits => {
            // In this strategy, we will copy mark bits to VO bits.
            // We need to set mark bits for to-space objects, too.
            VM::VMObjectModel::LOCAL_MARK_BIT_SPEC.store_atomic::<VM, u8>(
                new_object,
                1,
                None,
                Ordering::SeqCst,
            );

            // We set the VO bit for the to-space object eagerly.
            vo_bit::set_vo_bit(new_object);
        }
    }
}

pub(crate) fn on_region_swept<VM: VMBinding, R: Region>(region: &R, is_occupied: bool) {
    match strategy::<VM>() {
        VOBitUpdateStrategy::ClearAndReconstruct => {
            // Do nothing.  The VO bit metadata is already reconstructed.
        }
        VOBitUpdateStrategy::CopyFromMarkBits => {
            // In this strategy, we need to update the VO bits state after marking.
            if is_occupied {
                // If the block has live objects, copy the VO bits from mark bits.
                vo_bit::bcopy_vo_bit_from_mark_bit::<VM>(region.start(), R::BYTES);
            } else {
                // If the block has no live objects, simply clear the VO bits.
                vo_bit::bzero_vo_bit(region.start(), R::BYTES);
            }
        }
    }
}