mmtk/
global_state.rs

1use atomic_refcell::AtomicRefCell;
2use std::collections::HashMap;
3use std::sync::atomic::{AtomicBool, AtomicUsize, Ordering};
4use std::time::Instant;
5
6/// This stores some global states for an MMTK instance.
7/// Some MMTK components like plans and allocators may keep an reference to the struct, and can access it.
8// This used to be a part of the `BasePlan`. In that case, any component that accesses
9// the states needs a reference to the plan. It makes it harder for us to reason about the access pattern
10// for the plan, as many components hold references to the plan. Besides, the states
11// actually are not related with a plan, they are just global states for MMTK. So we refactored
12// those fields to this separate struct. For components that access the state, they just need
13// a reference to the struct, and are no longer dependent on the plan.
14// We may consider further break down the fields into smaller structs.
15pub struct GlobalState {
16    /// The current GC status.
17    pub(crate) gc_status: GcStatusWord,
18    /// When did the last GC start? Only accessed by the last parked worker.
19    pub(crate) gc_start_time: AtomicRefCell<Option<Instant>>,
20    /// Is the current GC an emergency collection? Emergency means we may run out of memory soon, and we should
21    /// attempt to collect as much as we can.
22    pub(crate) emergency_collection: AtomicBool,
23    /// Is the current GC triggered by the user?
24    pub(crate) user_triggered_collection: AtomicBool,
25    /// Is the current GC triggered internally by MMTK? This is unused for now. We may have internally triggered GC
26    /// for a concurrent plan.
27    pub(crate) internal_triggered_collection: AtomicBool,
28    /// Is the last GC internally triggered?
29    pub(crate) last_internal_triggered_collection: AtomicBool,
30    // Has an allocation succeeded since the emergency collection?
31    pub(crate) allocation_success: AtomicBool,
32    // Maximum number of failed attempts by a single thread
33    pub(crate) max_collection_attempts: AtomicUsize,
34    // Current collection attempt
35    pub(crate) cur_collection_attempts: AtomicUsize,
36    /// A counter for per-mutator stack scanning
37    pub(crate) scanned_stacks: AtomicUsize,
38    /// Have we scanned all the stacks?
39    pub(crate) stacks_prepared: AtomicBool,
40    /// A counter that keeps tracks of the number of bytes allocated since last stress test
41    pub(crate) allocation_bytes: AtomicUsize,
42    /// Are we inside the benchmark harness?
43    pub(crate) inside_harness: AtomicBool,
44    /// A counteer that keeps tracks of the number of bytes allocated by malloc
45    #[cfg(feature = "malloc_counted_size")]
46    pub(crate) malloc_bytes: AtomicUsize,
47    /// This stores the live bytes and the used bytes (by pages) for each space in last GC. This counter is only updated in the GC release phase.
48    pub(crate) live_bytes_in_last_gc: AtomicRefCell<HashMap<&'static str, LiveBytesStats>>,
49    /// The number of used pages at the end of the last GC. This can be used to estimate how many pages we have allocated since last GC.
50    pub(crate) used_pages_after_last_gc: AtomicUsize,
51}
52
53impl GlobalState {
54    /// Is MMTk initialized?
55    pub fn is_initialized(&self) -> bool {
56        self.gc_status.is_initialized()
57    }
58
59    /// Set the collection kind for the current GC. This is called before
60    /// scheduling collection to determin what kind of collection it will be.
61    pub fn set_collection_kind(
62        &self,
63        last_collection_was_exhaustive: bool,
64        heap_can_grow: bool,
65    ) -> bool {
66        self.cur_collection_attempts.store(
67            if self.user_triggered_collection.load(Ordering::Relaxed) {
68                1
69            } else {
70                self.determine_collection_attempts()
71            },
72            Ordering::Relaxed,
73        );
74
75        let emergency_collection = !self.is_internal_triggered_collection()
76            && last_collection_was_exhaustive
77            && self.cur_collection_attempts.load(Ordering::Relaxed) > 1
78            && !heap_can_grow;
79        self.emergency_collection
80            .store(emergency_collection, Ordering::Relaxed);
81
82        emergency_collection
83    }
84
85    fn determine_collection_attempts(&self) -> usize {
86        if !self.allocation_success.load(Ordering::Relaxed) {
87            self.max_collection_attempts.fetch_add(1, Ordering::Relaxed);
88        } else {
89            self.allocation_success.store(false, Ordering::Relaxed);
90            self.max_collection_attempts.store(1, Ordering::Relaxed);
91        }
92
93        self.max_collection_attempts.load(Ordering::Relaxed)
94    }
95
96    fn is_internal_triggered_collection(&self) -> bool {
97        let is_internal_triggered = self
98            .last_internal_triggered_collection
99            .load(Ordering::SeqCst);
100        // Remove this assertion when we have concurrent GC.
101        assert!(
102            !is_internal_triggered,
103            "We have no concurrent GC implemented. We should not have internally triggered GC"
104        );
105        is_internal_triggered
106    }
107
108    pub fn is_emergency_collection(&self) -> bool {
109        self.emergency_collection.load(Ordering::Relaxed)
110    }
111
112    /// Return true if this collection was triggered by application code.
113    pub fn is_user_triggered_collection(&self) -> bool {
114        self.user_triggered_collection.load(Ordering::Relaxed)
115    }
116
117    /// Reset collection state information.
118    pub fn reset_collection_trigger(&self) {
119        self.last_internal_triggered_collection.store(
120            self.internal_triggered_collection.load(Ordering::SeqCst),
121            Ordering::Relaxed,
122        );
123        self.internal_triggered_collection
124            .store(false, Ordering::SeqCst);
125        self.user_triggered_collection
126            .store(false, Ordering::Relaxed);
127    }
128
129    /// Are the stacks scanned?
130    pub fn stacks_prepared(&self) -> bool {
131        self.stacks_prepared.load(Ordering::SeqCst)
132    }
133
134    /// Prepare for stack scanning. This is usually used with `inform_stack_scanned()`.
135    /// This should be called before doing stack scanning.
136    pub fn prepare_for_stack_scanning(&self) {
137        self.scanned_stacks.store(0, Ordering::SeqCst);
138        self.stacks_prepared.store(false, Ordering::SeqCst);
139    }
140
141    /// Inform that 1 stack has been scanned. The argument `n_mutators` indicates the
142    /// total stacks we should scan. This method returns true if the number of scanned
143    /// stacks equals the total mutator count. Otherwise it returns false. This method
144    /// is thread safe and we guarantee only one thread will return true.
145    pub fn inform_stack_scanned(&self, n_mutators: usize) -> bool {
146        let old = self.scanned_stacks.fetch_add(1, Ordering::SeqCst);
147        debug_assert!(
148            old < n_mutators,
149            "The number of scanned stacks ({}) is more than the number of mutators ({})",
150            old,
151            n_mutators
152        );
153        let scanning_done = old + 1 == n_mutators;
154        if scanning_done {
155            self.stacks_prepared.store(true, Ordering::SeqCst);
156        }
157        scanning_done
158    }
159
160    /// Increase the allocation bytes and return the current allocation bytes after increasing
161    pub fn increase_allocation_bytes_by(&self, size: usize) -> usize {
162        let old_allocation_bytes = self.allocation_bytes.fetch_add(size, Ordering::SeqCst);
163        trace!(
164            "Stress GC: old_allocation_bytes = {}, size = {}, allocation_bytes = {}",
165            old_allocation_bytes,
166            size,
167            self.allocation_bytes.load(Ordering::Relaxed),
168        );
169        old_allocation_bytes + size
170    }
171
172    #[cfg(feature = "malloc_counted_size")]
173    pub fn get_malloc_bytes_in_pages(&self) -> usize {
174        crate::util::conversions::bytes_to_pages_up(self.malloc_bytes.load(Ordering::Relaxed))
175    }
176
177    #[cfg(feature = "malloc_counted_size")]
178    pub(crate) fn increase_malloc_bytes_by(&self, size: usize) {
179        self.malloc_bytes.fetch_add(size, Ordering::SeqCst);
180    }
181
182    #[cfg(feature = "malloc_counted_size")]
183    pub(crate) fn decrease_malloc_bytes_by(&self, size: usize) {
184        self.malloc_bytes.fetch_sub(size, Ordering::SeqCst);
185    }
186
187    pub(crate) fn set_used_pages_after_last_gc(&self, pages: usize) {
188        self.used_pages_after_last_gc
189            .store(pages, Ordering::Relaxed);
190    }
191
192    pub(crate) fn get_used_pages_after_last_gc(&self) -> usize {
193        self.used_pages_after_last_gc.load(Ordering::Relaxed)
194    }
195}
196
197impl Default for GlobalState {
198    fn default() -> Self {
199        Self {
200            gc_status: GcStatusWord::new(GcStatus::Uninitialized),
201            gc_start_time: AtomicRefCell::new(None),
202            stacks_prepared: AtomicBool::new(false),
203            emergency_collection: AtomicBool::new(false),
204            user_triggered_collection: AtomicBool::new(false),
205            internal_triggered_collection: AtomicBool::new(false),
206            last_internal_triggered_collection: AtomicBool::new(false),
207            allocation_success: AtomicBool::new(false),
208            max_collection_attempts: AtomicUsize::new(0),
209            cur_collection_attempts: AtomicUsize::new(0),
210            scanned_stacks: AtomicUsize::new(0),
211            allocation_bytes: AtomicUsize::new(0),
212            inside_harness: AtomicBool::new(false),
213            #[cfg(feature = "malloc_counted_size")]
214            malloc_bytes: AtomicUsize::new(0),
215            live_bytes_in_last_gc: AtomicRefCell::new(HashMap::new()),
216            used_pages_after_last_gc: AtomicUsize::new(0),
217        }
218    }
219}
220
221/// The status of MMTk's GC subsystem. This doubles as the "is MMTk initialized" flag (via
222/// [`GcStatus::Uninitialized`]) and as the state that tracks whether a GC is running and, if so,
223/// what phase it is in. See [`GcStatusWord`] for how this is stored atomically and which
224/// transitions between variants are legal.
225#[derive(PartialEq, Copy, Clone, Debug)]
226pub enum GcStatus {
227    /// MMTk has not been initialized yet, i.e. `initialize_collection()` has not been called, so
228    /// there are no GC worker threads available to run a collection. This is the same condition
229    /// reported by [`PauseRequestOutcome::Uninitialized`]: [`GcStatusWord::try_request_pause`]
230    /// returns that variant exactly when the status is `GcStatus::Uninitialized`.
231    Uninitialized,
232    /// MMTk is initialized, and no GC is running, pending, or requested.
233    NotInGC,
234    /// A concurrent GC's background work (e.g. concurrent marking) is running while mutators
235    /// continue to run normally. See `ConcurrentPlan::concurrent_work_in_progress`.
236    InConcurrentGC,
237    /// A stop-the-world pause is active: mutators are stopped and GC workers are doing pause
238    /// work (e.g. tracing).
239    InPause,
240    /// A GC pause has been requested (by [`GcStatusWord::try_request_pause`]) but mutators have
241    /// not all stopped yet.
242    PauseRequested,
243}
244
245/// The outcome of [`GcStatusWord::try_request_pause`].
246#[derive(Debug, PartialEq, Eq)]
247pub(crate) enum PauseRequestOutcome {
248    /// MMTk has not been initialized yet (`initialize_collection()` has not been called), so
249    /// there are no GC worker threads to run a collection; no pause was (or could be) requested.
250    Uninitialized,
251    /// A pause was already requested (by this call or a racing one); the caller does not need
252    /// to do anything further.
253    AlreadyRequested,
254    /// This call transitioned the status to `PauseRequested`; the caller is responsible for
255    /// requesting the pause (e.g. notifying the scheduler) exactly once.
256    Requested,
257}
258
259/// A lock-free, atomic encoding of [`GcStatus`]. This packs the variant tag into a `usize` so
260/// the whole status fits in a single machine word and can be updated with compare-and-swap
261/// instead of behind a `Mutex<GcStatus>`. The tag is kept to [`Self::TAG_BITS`] bits (rather than
262/// using the whole word) to leave room for a payload-carrying variant (e.g. a nesting depth) to
263/// be added later without needing to re-encode the rest.
264///
265/// `GcStatus` is a state machine: only a handful of transitions between its variants are legal.
266/// Every legal transition is exposed here as its own method, each performing its own
267/// compare-and-swap retry loop and asserting that the transition is legal for the status it
268/// finds. Do not add a generic "set the status to X" method: doing so would make it possible to
269/// bypass the state machine's invariants.
270pub(crate) struct GcStatusWord(AtomicUsize);
271
272impl GcStatusWord {
273    /// Number of bits used to encode the variant tag. 3 bits is enough to distinguish the 5
274    /// variants, leaving the rest of the word free for a future payload-carrying variant.
275    const TAG_BITS: u32 = 3;
276    const TAG_MASK: usize = (1 << Self::TAG_BITS) - 1;
277
278    fn encode(status: GcStatus) -> usize {
279        match status {
280            GcStatus::Uninitialized => 0,
281            GcStatus::NotInGC => 1,
282            GcStatus::InConcurrentGC => 2,
283            GcStatus::InPause => 3,
284            GcStatus::PauseRequested => 4,
285        }
286    }
287
288    fn decode(bits: usize) -> GcStatus {
289        match bits & Self::TAG_MASK {
290            0 => GcStatus::Uninitialized,
291            1 => GcStatus::NotInGC,
292            2 => GcStatus::InConcurrentGC,
293            3 => GcStatus::InPause,
294            4 => GcStatus::PauseRequested,
295            _ => unreachable!("invalid encoded GcStatus tag"),
296        }
297    }
298
299    pub(crate) fn new(status: GcStatus) -> Self {
300        GcStatusWord(AtomicUsize::new(Self::encode(status)))
301    }
302
303    /// Read the current status.
304    pub(crate) fn load(&self) -> GcStatus {
305        Self::decode(self.0.load(Ordering::SeqCst))
306    }
307
308    /// Retry `f` (a pure function of the current status) via [`AtomicUsize::fetch_update`] until
309    /// it succeeds, and return the status it transitioned *from* (not the new status). Returning
310    /// the old status (rather than the new one) lets a caller tell whether it "won" the race when
311    /// multiple threads concurrently drive the same transition: only the thread whose CAS
312    /// actually moved the status away from a given old value can be sure it is the one
313    /// responsible for that transition, so it is the one that should perform any side effect that
314    /// must happen exactly once (e.g. notifying the scheduler). If `transition` returned the new
315    /// status instead, every racing thread would observe the same new status and none could tell
316    /// which of them caused it. `f` may be invoked more than once under contention.
317    fn transition<F: FnMut(GcStatus) -> GcStatus>(&self, mut f: F) -> GcStatus {
318        let old_bits = self
319            .0
320            .fetch_update(Ordering::SeqCst, Ordering::SeqCst, |bits| {
321                Some(Self::encode(f(Self::decode(bits))))
322            })
323            .unwrap(); // `f` always returns a status to move to, so this never returns `Err`.
324        Self::decode(old_bits)
325    }
326
327    pub(crate) fn is_initialized(&self) -> bool {
328        self.load() != GcStatus::Uninitialized
329    }
330
331    /// `Uninitialized` -> `NotInGC`.
332    pub(crate) fn set_initialized(&self) {
333        self.transition(|status| {
334            assert!(
335                status == GcStatus::Uninitialized,
336                "Trying to set initialized GC status when it is not uninitialized"
337            );
338            GcStatus::NotInGC
339        });
340    }
341
342    /// Any status other than `Uninitialized` -> `Uninitialized`.
343    pub(crate) fn set_uninitialized(&self) {
344        self.transition(|status| {
345            assert!(
346                status != GcStatus::Uninitialized,
347                "Trying to set uninitialized GC status when it is already uninitialized"
348            );
349            GcStatus::Uninitialized
350        });
351    }
352
353    /// `PauseRequested` -> `InPause`.
354    pub(crate) fn set_in_pause(&self) {
355        self.transition(|status| {
356            assert!(
357                status == GcStatus::PauseRequested,
358                "Trying to set in-pause GC status in invalid status: {:?}",
359                status
360            );
361            GcStatus::InPause
362        });
363    }
364
365    /// `InPause` -> `InConcurrentGC`, e.g. once a GC pause has finished but concurrent work (such
366    /// as concurrent marking) was scheduled to continue after mutators resume.
367    pub(crate) fn set_in_concurrent_gc(&self) {
368        self.transition(|status| {
369            assert!(
370                status == GcStatus::InPause,
371                "Trying to set in-concurrent-gc GC status in invalid status: {:?}",
372                status
373            );
374            GcStatus::InConcurrentGC
375        });
376    }
377
378    /// `InPause` -> `NotInGC`, e.g. once a GC pause has finished and no concurrent work remains.
379    pub(crate) fn set_not_in_gc(&self) {
380        self.transition(|status| {
381            assert!(
382                status == GcStatus::InPause,
383                "Trying to set not-in-gc GC status in invalid status: {:?}",
384                status
385            );
386            GcStatus::NotInGC
387        });
388    }
389
390    /// `NotInGC`/`InConcurrentGC` -> `PauseRequested`, unless MMTk is not yet initialized, or a
391    /// pause has already been requested. See [`PauseRequestOutcome`].
392    pub(crate) fn try_request_pause(&self) -> PauseRequestOutcome {
393        // `fetch_update`'s closure returning `None` aborts the update and makes `fetch_update`
394        // return `Err` with the status that caused the abort, so `Uninitialized`/`PauseRequested`
395        // (which must not transition here) are reported that way instead of via a CAS.
396        match self
397            .0
398            .fetch_update(Ordering::SeqCst, Ordering::SeqCst, |bits| {
399                let status = Self::decode(bits);
400                if matches!(status, GcStatus::Uninitialized | GcStatus::PauseRequested) {
401                    return None;
402                }
403                assert!(
404                    matches!(status, GcStatus::NotInGC | GcStatus::InConcurrentGC),
405                    "Trying to request a GC pause in invalid status: {:?}",
406                    status
407                );
408                Some(Self::encode(GcStatus::PauseRequested))
409            }) {
410            Ok(_) => PauseRequestOutcome::Requested,
411            Err(bits) => match Self::decode(bits) {
412                GcStatus::Uninitialized => PauseRequestOutcome::Uninitialized,
413                GcStatus::PauseRequested => PauseRequestOutcome::AlreadyRequested,
414                status => unreachable!(
415                    "fetch_update aborted the transition for an unexpected status: {:?}",
416                    status
417                ),
418            },
419        }
420    }
421}
422
423#[cfg(test)]
424mod gc_status_tests {
425    use super::{GcStatus, GcStatusWord, PauseRequestOutcome};
426
427    #[test]
428    fn encode_decode_roundtrip() {
429        let statuses = [
430            GcStatus::Uninitialized,
431            GcStatus::NotInGC,
432            GcStatus::InConcurrentGC,
433            GcStatus::InPause,
434            GcStatus::PauseRequested,
435        ];
436        for status in statuses {
437            assert_eq!(GcStatusWord::decode(GcStatusWord::encode(status)), status);
438        }
439    }
440
441    #[test]
442    fn new_and_load_roundtrip() {
443        let statuses = [
444            GcStatus::Uninitialized,
445            GcStatus::NotInGC,
446            GcStatus::InConcurrentGC,
447            GcStatus::InPause,
448            GcStatus::PauseRequested,
449        ];
450        for status in statuses {
451            assert_eq!(GcStatusWord::new(status).load(), status);
452        }
453    }
454
455    #[test]
456    fn set_initialized_from_uninitialized() {
457        let word = GcStatusWord::new(GcStatus::Uninitialized);
458        assert!(!word.is_initialized());
459        word.set_initialized();
460        assert_eq!(word.load(), GcStatus::NotInGC);
461        assert!(word.is_initialized());
462    }
463
464    #[test]
465    #[should_panic(expected = "not uninitialized")]
466    fn set_initialized_panics_if_already_initialized() {
467        GcStatusWord::new(GcStatus::NotInGC).set_initialized();
468    }
469
470    #[test]
471    fn set_uninitialized_from_not_in_gc() {
472        let word = GcStatusWord::new(GcStatus::NotInGC);
473        word.set_uninitialized();
474        assert_eq!(word.load(), GcStatus::Uninitialized);
475    }
476
477    #[test]
478    #[should_panic(expected = "already uninitialized")]
479    fn set_uninitialized_panics_if_already_uninitialized() {
480        GcStatusWord::new(GcStatus::Uninitialized).set_uninitialized();
481    }
482
483    #[test]
484    fn try_request_pause_from_not_in_gc() {
485        let word = GcStatusWord::new(GcStatus::NotInGC);
486        assert_eq!(word.try_request_pause(), PauseRequestOutcome::Requested);
487        assert_eq!(word.load(), GcStatus::PauseRequested);
488    }
489
490    #[test]
491    fn try_request_pause_from_in_concurrent_gc() {
492        let word = GcStatusWord::new(GcStatus::InConcurrentGC);
493        assert_eq!(word.try_request_pause(), PauseRequestOutcome::Requested);
494        assert_eq!(word.load(), GcStatus::PauseRequested);
495    }
496
497    #[test]
498    fn try_request_pause_when_already_requested() {
499        let word = GcStatusWord::new(GcStatus::PauseRequested);
500        assert_eq!(
501            word.try_request_pause(),
502            PauseRequestOutcome::AlreadyRequested
503        );
504        // Idempotent: the status is unchanged, not "double requested".
505        assert_eq!(word.load(), GcStatus::PauseRequested);
506    }
507
508    /// A GC pause should never be requested while one is already underway: by the time the
509    /// status reaches `InPause`, all mutators must already be stopped, so no mutator should be
510    /// calling `try_request_pause` at all. Observing `InPause` here indicates a state-machine
511    /// violation elsewhere, so it must panic rather than being silently treated as a no-op.
512    #[test]
513    #[should_panic(expected = "invalid status")]
514    fn try_request_pause_panics_when_already_in_pause() {
515        GcStatusWord::new(GcStatus::InPause).try_request_pause();
516    }
517
518    /// Allocation can call `poll()` (and thus `try_request_pause`) before
519    /// `initialize_collection()` has been called, e.g. if the heap fills up before the VM
520    /// binding initializes MMTk's GC worker threads. This must not panic here: the caller (e.g.
521    /// `Space::not_acquiring`) is responsible for producing a clear "GC is not allowed here"
522    /// error once it knows allocation has genuinely failed.
523    #[test]
524    fn try_request_pause_when_uninitialized() {
525        let word = GcStatusWord::new(GcStatus::Uninitialized);
526        assert_eq!(word.try_request_pause(), PauseRequestOutcome::Uninitialized);
527        assert_eq!(word.load(), GcStatus::Uninitialized);
528    }
529
530    #[test]
531    fn set_in_pause_from_pause_requested() {
532        let word = GcStatusWord::new(GcStatus::PauseRequested);
533        word.set_in_pause();
534        assert_eq!(word.load(), GcStatus::InPause);
535    }
536
537    #[test]
538    #[should_panic(expected = "invalid status")]
539    fn set_in_pause_panics_if_not_requested() {
540        GcStatusWord::new(GcStatus::NotInGC).set_in_pause();
541    }
542
543    #[test]
544    fn set_in_concurrent_gc_from_in_pause() {
545        let word = GcStatusWord::new(GcStatus::InPause);
546        word.set_in_concurrent_gc();
547        assert_eq!(word.load(), GcStatus::InConcurrentGC);
548    }
549
550    #[test]
551    #[should_panic(expected = "invalid status")]
552    fn set_in_concurrent_gc_panics_if_not_in_pause() {
553        GcStatusWord::new(GcStatus::NotInGC).set_in_concurrent_gc();
554    }
555
556    #[test]
557    fn set_not_in_gc_from_in_pause() {
558        let word = GcStatusWord::new(GcStatus::InPause);
559        word.set_not_in_gc();
560        assert_eq!(word.load(), GcStatus::NotInGC);
561    }
562
563    #[test]
564    #[should_panic(expected = "invalid status")]
565    fn set_not_in_gc_panics_if_not_in_pause() {
566        GcStatusWord::new(GcStatus::InConcurrentGC).set_not_in_gc();
567    }
568}
569
570/// Statistics for the live bytes in the last GC. The statistics is per space.
571#[derive(Copy, Clone, Debug)]
572pub struct LiveBytesStats {
573    /// Total accumulated bytes of live objects in the space.
574    pub live_bytes: usize,
575    /// Total pages used by the space.
576    pub used_pages: usize,
577    /// Total bytes used by the space, computed from `used_pages`.
578    /// The ratio of live_bytes and used_bytes reflects the utilization of the memory in the space.
579    pub used_bytes: usize,
580}
mmtk/global_state.rs

mmtk/
global_state.rs
