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
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
use crate::plan::global::CommonPlan;
use crate::plan::global::CreateSpecificPlanArgs;
use crate::plan::ObjectQueue;
use crate::plan::Plan;
use crate::policy::copyspace::CopySpace;
use crate::policy::gc_work::{TraceKind, TRACE_KIND_TRANSITIVE_PIN};
use crate::policy::space::Space;
use crate::scheduler::*;
use crate::util::copy::CopySemantics;
use crate::util::heap::gc_trigger::SpaceStats;
use crate::util::heap::VMRequest;
use crate::util::statistics::counter::EventCounter;
use crate::util::Address;
use crate::util::ObjectReference;
use crate::util::VMWorkerThread;
use crate::vm::{ObjectModel, VMBinding};
use std::sync::atomic::AtomicBool;
use std::sync::atomic::Ordering;
use std::sync::{Arc, Mutex};

use mmtk_macros::{HasSpaces, PlanTraceObject};

/// Common implementation for generational plans. Each generational plan
/// should include this type, and forward calls to it where possible.
#[derive(HasSpaces, PlanTraceObject)]
pub struct CommonGenPlan<VM: VMBinding> {
    /// The nursery space.
    #[space]
    #[copy_semantics(CopySemantics::PromoteToMature)]
    pub nursery: CopySpace<VM>,
    /// The common plan.
    #[parent]
    pub common: CommonPlan<VM>,
    /// Is this GC full heap?
    pub gc_full_heap: AtomicBool,
    /// Is next GC full heap?
    pub next_gc_full_heap: AtomicBool,
    pub full_heap_gc_count: Arc<Mutex<EventCounter>>,
}

impl<VM: VMBinding> CommonGenPlan<VM> {
    pub fn new(mut args: CreateSpecificPlanArgs<VM>) -> Self {
        let nursery = CopySpace::new(
            args.get_space_args("nursery", true, VMRequest::discontiguous()),
            true,
        );
        let full_heap_gc_count = args
            .global_args
            .stats
            .new_event_counter("majorGC", true, true);
        let common = CommonPlan::new(args);

        CommonGenPlan {
            nursery,
            common,
            gc_full_heap: AtomicBool::default(),
            next_gc_full_heap: AtomicBool::new(false),
            full_heap_gc_count,
        }
    }

    /// Prepare Gen. This should be called by a single thread in GC prepare work.
    pub fn prepare(&mut self, tls: VMWorkerThread) {
        let full_heap = !self.is_current_gc_nursery();
        if full_heap {
            self.full_heap_gc_count.lock().unwrap().inc();
        }
        self.common.prepare(tls, full_heap);
        self.nursery.prepare(true);
        self.nursery
            .set_copy_for_sft_trace(Some(CopySemantics::PromoteToMature));
    }

    /// Release Gen. This should be called by a single thread in GC release work.
    pub fn release(&mut self, tls: VMWorkerThread) {
        let full_heap = !self.is_current_gc_nursery();
        self.common.release(tls, full_heap);
        self.nursery.release();
    }

    /// Independent of how many pages remain in the page budget (a function of heap size), we must
    /// ensure we never exhaust virtual memory. Therefore we must never let the nursery grow to the
    /// extent that it can't be copied into the mature space.
    ///
    /// Returns `true` if the nursery has grown to the extent that it may not be able to be copied
    /// into the mature space.
    fn virtual_memory_exhausted(plan: &dyn GenerationalPlan<VM = VM>) -> bool {
        ((plan.get_collection_reserved_pages() as f64
            * VM::VMObjectModel::VM_WORST_CASE_COPY_EXPANSION) as usize)
            > plan.get_mature_physical_pages_available()
    }

    /// Check if we need a GC based on the nursery space usage. This method may mark
    /// the following GC as a full heap GC.
    pub fn collection_required<P: Plan<VM = VM>>(
        &self,
        plan: &P,
        space_full: bool,
        space: Option<SpaceStats<VM>>,
    ) -> bool {
        let cur_nursery = self.nursery.reserved_pages();
        let max_nursery = self.common.base.gc_trigger.get_max_nursery_pages();
        let nursery_full = cur_nursery >= max_nursery;
        trace!(
            "nursery_full = {:?} (nursery = {}, max_nursery = {})",
            nursery_full,
            cur_nursery,
            max_nursery,
        );
        if nursery_full {
            return true;
        }
        if Self::virtual_memory_exhausted(plan.generational().unwrap()) {
            return true;
        }

        // Is the GC triggered by nursery?
        // - if space is none, it is not. Return false immediately.
        // - if space is some, we further check its descriptor.
        let is_triggered_by_nursery = space.map_or(false, |s| {
            s.0.common().descriptor == self.nursery.common().descriptor
        });
        // If space is full and the GC is not triggered by nursery, next GC will be full heap GC.
        if space_full && !is_triggered_by_nursery {
            self.next_gc_full_heap.store(true, Ordering::SeqCst);
        }

        self.common.base.collection_required(plan, space_full)
    }

    pub fn force_full_heap_collection(&self) {
        self.next_gc_full_heap.store(true, Ordering::SeqCst);
    }

    pub fn last_collection_full_heap(&self) -> bool {
        self.gc_full_heap.load(Ordering::Relaxed)
    }

    /// Check if we should do a full heap GC. It returns true if we should have a full heap GC.
    /// It also sets gc_full_heap based on the result.
    pub fn requires_full_heap_collection<P: Plan<VM = VM>>(&self, plan: &P) -> bool {
        // Allow the same 'true' block for if-else.
        // The conditions are complex, and it is easier to read if we put them to separate if blocks.
        #[allow(clippy::if_same_then_else, clippy::needless_bool)]
        let is_full_heap = if crate::plan::generational::FULL_NURSERY_GC {
            trace!("full heap: forced full heap");
            // For barrier overhead measurements, we always do full gc in nursery collections.
            true
        } else if self
            .common
            .base
            .global_state
            .user_triggered_collection
            .load(Ordering::SeqCst)
            && *self.common.base.options.full_heap_system_gc
        {
            trace!("full heap: user triggered");
            // User triggered collection, and we force full heap for user triggered collection
            true
        } else if self.next_gc_full_heap.load(Ordering::SeqCst)
            || self
                .common
                .base
                .global_state
                .cur_collection_attempts
                .load(Ordering::SeqCst)
                > 1
        {
            trace!(
                "full heap: next_gc_full_heap = {}, cur_collection_attempts = {}",
                self.next_gc_full_heap.load(Ordering::SeqCst),
                self.common
                    .base
                    .global_state
                    .cur_collection_attempts
                    .load(Ordering::SeqCst)
            );
            // Forces full heap collection
            true
        } else if Self::virtual_memory_exhausted(plan.generational().unwrap()) {
            trace!("full heap: virtual memory exhausted");
            true
        } else {
            // We use an Appel-style nursery. The default GC (even for a "heap-full" collection)
            // for generational GCs should be a nursery GC. A full-heap GC should only happen if
            // there is not enough memory available for allocating into the nursery (i.e. the
            // available pages in the nursery are less than the minimum nursery pages), if the
            // virtual memory has been exhausted, or if it is an emergency GC.
            false
        };

        self.gc_full_heap.store(is_full_heap, Ordering::SeqCst);

        info!(
            "{}",
            if is_full_heap {
                "Full heap GC"
            } else {
                "Nursery GC"
            }
        );

        is_full_heap
    }

    /// Trace objects for spaces in generational and common plans for a full heap GC.
    #[allow(unused)] // We now use `PlanTraceObject`, and this mehtod is not used.
    pub fn trace_object_full_heap<Q: ObjectQueue>(
        &self,
        queue: &mut Q,
        object: ObjectReference,
        worker: &mut GCWorker<VM>,
    ) -> ObjectReference {
        if self.nursery.in_space(object) {
            return self.nursery.trace_object::<Q>(
                queue,
                object,
                Some(CopySemantics::PromoteToMature),
                worker,
            );
        }
        self.common.trace_object::<Q>(queue, object, worker)
    }

    /// Trace objects for spaces in generational and common plans for a nursery GC.
    pub fn trace_object_nursery<Q: ObjectQueue, const KIND: TraceKind>(
        &self,
        queue: &mut Q,
        object: ObjectReference,
        worker: &mut GCWorker<VM>,
    ) -> ObjectReference {
        assert!(
            KIND != TRACE_KIND_TRANSITIVE_PIN,
            "A copying nursery cannot pin objects"
        );

        // Evacuate nursery objects
        if self.nursery.in_space(object) {
            return self.nursery.trace_object::<Q>(
                queue,
                object,
                Some(CopySemantics::PromoteToMature),
                worker,
            );
        }
        // We may alloc large object into LOS as nursery objects. Trace them here.
        if self.common.get_los().in_space(object) {
            return self.common.get_los().trace_object::<Q>(queue, object);
        }
        object
    }

    /// Is the current GC a nursery GC?
    pub fn is_current_gc_nursery(&self) -> bool {
        !self.gc_full_heap.load(Ordering::SeqCst)
    }

    /// Check a plan to see if the next GC should be a full heap GC.
    ///
    /// Note that this function should be called after all spaces have been released. This is
    /// required as we may get incorrect values since this function uses
    /// [`get_available_pages`](crate::plan::Plan::get_available_pages)
    /// whose value depends on which spaces have been released.
    pub fn should_next_gc_be_full_heap(plan: &dyn Plan<VM = VM>) -> bool {
        let available = plan.get_available_pages();
        let min_nursery = plan.base().gc_trigger.get_min_nursery_pages();
        let next_gc_full_heap = available < min_nursery;
        trace!(
            "next gc will be full heap? {}, available pages = {}, min nursery = {}",
            next_gc_full_heap,
            available,
            min_nursery
        );
        next_gc_full_heap
    }

    /// Set next_gc_full_heap to the given value.
    pub fn set_next_gc_full_heap(&self, next_gc_full_heap: bool) {
        self.next_gc_full_heap
            .store(next_gc_full_heap, Ordering::SeqCst);
    }

    /// Get pages reserved for the collection by a generational plan. A generational plan should
    /// add their own reservation with the value returned by this method.
    pub fn get_collection_reserved_pages(&self) -> usize {
        self.nursery.reserved_pages()
    }

    /// Get pages used by a generational plan. A generational plan should add their own used pages
    /// with the value returned by this method.
    pub fn get_used_pages(&self) -> usize {
        self.nursery.reserved_pages() + self.common.get_used_pages()
    }
}

/// This trait includes methods that are specific to generational plans. This trait needs
/// to be object safe.
pub trait GenerationalPlan: Plan {
    /// Is the current GC a nursery GC? If a GC is not a nursery GC, it will be a full heap GC.
    /// This should only be called during GC.
    fn is_current_gc_nursery(&self) -> bool;

    /// Is the object in the nursery?
    fn is_object_in_nursery(&self, object: ObjectReference) -> bool;

    /// Is the address in the nursery? As we only know addresses rather than object references, the
    /// implementation cannot access per-object metadata. If the plan does not have knowledge whether
    /// the address is in nursery or not (e.g. mature/nursery objects share the same space and are
    /// only differentiated by object metadata), the implementation should return `false` as a more
    /// conservative result.
    fn is_address_in_nursery(&self, addr: Address) -> bool;

    /// Return the number of pages available for allocation into the mature space.
    fn get_mature_physical_pages_available(&self) -> usize;

    /// Return the number of used pages in the mature space.
    fn get_mature_reserved_pages(&self) -> usize;

    /// Return whether last GC is a full GC.
    fn last_collection_full_heap(&self) -> bool;

    /// Force the next collection to be full heap.
    fn force_full_heap_collection(&self);
}

/// This trait is the extension trait for [`GenerationalPlan`] (see Rust's extension trait pattern).
/// Generally any method should be put to [`GenerationalPlan`] if possible while keeping [`GenerationalPlan`]
/// object safe. In this case, generic methods will be put to this extension trait.
pub trait GenerationalPlanExt<VM: VMBinding>: GenerationalPlan<VM = VM> {
    /// Trace an object in nursery collection. If the object is in nursery, we should call `trace_object`
    /// on the space. Otherwise, we can just return the object.
    fn trace_object_nursery<Q: ObjectQueue, const KIND: TraceKind>(
        &self,
        queue: &mut Q,
        object: ObjectReference,
        worker: &mut GCWorker<VM>,
    ) -> ObjectReference;
}

/// Is current GC only collecting objects allocated since last GC? This method can be called
/// with any plan (generational or not). For non generational plans, it will always return false.
pub fn is_nursery_gc<VM: VMBinding>(plan: &dyn Plan<VM = VM>) -> bool {
    plan.generational()
        .map_or(false, |plan| plan.is_current_gc_nursery())
}