mmtk/policy/immix/
defrag.rs

1use super::{
2    block::{Block, BlockState},
3    line::Line,
4    ImmixSpace,
5};
6use crate::util::linear_scan::Region;
7use crate::{policy::space::Space, Plan};
8use crate::{util::constants::LOG_BYTES_IN_PAGE, vm::*};
9use spin::Mutex;
10use std::sync::atomic::{AtomicBool, AtomicUsize, Ordering};
11
12pub type Histogram = [usize; Defrag::NUM_BINS];
13
14#[derive(Debug, Default)]
15pub struct Defrag {
16    /// Is current GC a defrag GC?
17    in_defrag_collection: AtomicBool,
18    /// Is defrag space exhausted?
19    defrag_space_exhausted: AtomicBool,
20    /// A list of completed mark histograms reported by workers
21    pub mark_histograms: Mutex<Vec<Histogram>>,
22    /// A block with number of holes greater than this threshold will be defragmented.
23    pub defrag_spill_threshold: AtomicUsize,
24    /// The number of remaining clean pages in defrag space.
25    available_clean_pages_for_defrag: AtomicUsize,
26}
27
28pub struct StatsForDefrag {
29    total_pages: usize,
30    reserved_pages: usize,
31    collection_reserved_pages: usize,
32}
33
34impl StatsForDefrag {
35    pub fn new<VM: VMBinding>(plan: &dyn Plan<VM = VM>) -> Self {
36        Self {
37            total_pages: plan.get_total_pages(),
38            reserved_pages: plan.get_reserved_pages(),
39            collection_reserved_pages: plan.get_collection_reserved_pages(),
40        }
41    }
42}
43
44impl Defrag {
45    const NUM_BINS: usize = (Block::LINES >> 1) + 1;
46    const DEFRAG_LINE_REUSE_RATIO: f32 = 0.99;
47    const MIN_SPILL_THRESHOLD: usize = 2;
48
49    /// Allocate a new local histogram.
50    pub const fn new_histogram(&self) -> Histogram {
51        [0; Self::NUM_BINS]
52    }
53
54    /// Report back a completed mark histogram
55    pub fn add_completed_mark_histogram(&self, histogram: Histogram) {
56        self.mark_histograms.lock().push(histogram)
57    }
58
59    /// Check if the current GC is a defrag GC.
60    pub fn in_defrag(&self) -> bool {
61        self.in_defrag_collection.load(Ordering::Acquire)
62    }
63
64    /// Determine whether the current GC should do defragmentation.
65    #[allow(clippy::too_many_arguments)]
66    pub fn decide_whether_to_defrag(
67        &self,
68        defrag_enabled: bool,
69        emergency_collection: bool,
70        collect_whole_heap: bool,
71        collection_attempts: usize,
72        user_triggered: bool,
73        exhausted_reusable_space: bool,
74        full_heap_system_gc: bool,
75        rc_enabled: bool,
76        stress_defrag: bool,
77    ) {
78        let in_defrag = defrag_enabled
79            && (emergency_collection
80                || (collection_attempts > 1)
81                || !exhausted_reusable_space
82                || stress_defrag
83                || (collect_whole_heap && user_triggered && full_heap_system_gc))
84            && !rc_enabled;
85
86        {
87            // These details are useful for debugging why a debug GC is triggered or not triggered.
88            // We encode those conditions into a bitfield because we can't pass too many args to the
89            // eBPF tracer via the USDT arguments.
90            let decision_word = (defrag_enabled as u32)
91                | (emergency_collection as u32) << 1
92                | (collect_whole_heap as u32) << 2
93                | (user_triggered as u32) << 3
94                | (exhausted_reusable_space as u32) << 4
95                | (full_heap_system_gc as u32) << 5
96                | (stress_defrag as u32) << 6;
97
98            info!(
99                "Defrag: {i}, collection_attempts: {c}, decision_word: 0b{d:b}",
100                i = in_defrag,
101                c = collection_attempts,
102                d = decision_word,
103            );
104
105            probe!(
106                mmtk,
107                immix_defrag,
108                in_defrag,
109                collection_attempts,
110                decision_word
111            );
112        }
113
114        self.in_defrag_collection
115            .store(in_defrag, Ordering::Release)
116    }
117
118    /// Get the number of defrag headroom pages.
119    pub fn defrag_headroom_pages<VM: VMBinding>(&self, space: &ImmixSpace<VM>) -> usize {
120        space.get_page_resource().reserved_pages()
121            * (*space.common().options.immix_defrag_headroom_percent)
122            / 100
123    }
124
125    /// Check if the defrag space is exhausted.
126    pub fn space_exhausted(&self) -> bool {
127        self.defrag_space_exhausted.load(Ordering::Acquire)
128    }
129
130    /// Update available_clean_pages_for_defrag counter when a clean block is allocated.
131    pub fn notify_new_clean_block(&self, copy: bool) {
132        if copy {
133            let available_clean_pages_for_defrag =
134                self.available_clean_pages_for_defrag.fetch_update(
135                    Ordering::SeqCst,
136                    Ordering::SeqCst,
137                    |available_clean_pages_for_defrag| {
138                        if available_clean_pages_for_defrag <= Block::PAGES {
139                            Some(0)
140                        } else {
141                            Some(available_clean_pages_for_defrag - Block::PAGES)
142                        }
143                    },
144                );
145            if available_clean_pages_for_defrag.unwrap() <= Block::PAGES {
146                self.defrag_space_exhausted.store(true, Ordering::SeqCst);
147            }
148        }
149    }
150
151    /// Prepare work. Should be called in ImmixSpace::prepare.
152    pub fn prepare<VM: VMBinding>(&self, space: &ImmixSpace<VM>, plan_stats: StatsForDefrag) {
153        debug_assert!(space.is_defrag_enabled());
154        self.defrag_space_exhausted.store(false, Ordering::Release);
155
156        // Calculate available free space for defragmentation.
157
158        let mut available_clean_pages_for_defrag = plan_stats.total_pages as isize
159            - plan_stats.reserved_pages as isize
160            + self.defrag_headroom_pages(space) as isize;
161        if available_clean_pages_for_defrag < 0 {
162            available_clean_pages_for_defrag = 0
163        };
164
165        self.available_clean_pages_for_defrag
166            .store(available_clean_pages_for_defrag as usize, Ordering::Release);
167
168        if self.in_defrag() {
169            self.establish_defrag_spill_threshold(space)
170        }
171
172        self.available_clean_pages_for_defrag.store(
173            available_clean_pages_for_defrag as usize + plan_stats.collection_reserved_pages,
174            Ordering::Release,
175        );
176    }
177
178    /// Get the numebr of all the recyclable lines in all the reusable blocks.
179    fn get_available_lines<VM: VMBinding>(
180        &self,
181        space: &ImmixSpace<VM>,
182        spill_avail_histograms: &mut Histogram,
183    ) -> usize {
184        let mut total_available_lines = 0;
185        space.reusable_blocks.iterate_blocks(|block| {
186            let bucket = block.get_holes();
187            let unavailable_lines = match block.get_state() {
188                BlockState::Reusable { unavailable_lines } => unavailable_lines as usize,
189                s => unreachable!("{:?} {:?}", block, s),
190            };
191            let available_lines = Block::LINES - unavailable_lines;
192            spill_avail_histograms[bucket] += available_lines;
193            total_available_lines += available_lines;
194        });
195        total_available_lines
196    }
197
198    /// Calculate the defrag threshold.
199    fn establish_defrag_spill_threshold<VM: VMBinding>(&self, space: &ImmixSpace<VM>) {
200        let mut spill_avail_histograms = self.new_histogram();
201        let clean_lines = self.get_available_lines(space, &mut spill_avail_histograms);
202        let available_lines = clean_lines
203            + (self
204                .available_clean_pages_for_defrag
205                .load(Ordering::Acquire)
206                << (LOG_BYTES_IN_PAGE as usize - Line::LOG_BYTES));
207
208        // Number of lines we will evacuate.
209        let mut required_lines = 0isize;
210        // Number of to-space free lines we can use for defragmentation.
211        let mut limit = (available_lines as f32 / Self::DEFRAG_LINE_REUSE_RATIO) as isize;
212        let mut threshold = Block::LINES >> 1;
213        let mark_histograms = self.mark_histograms.lock();
214        // Blocks are grouped by buckets, indexed by the number of holes in the block.
215        // `mark_histograms` remembers the number of live lines for each bucket.
216        // Here, reversely iterate all the bucket to find a threshold that all buckets above this
217        // threshold can be evacuated, without causing to-space overflow.
218        for index in (Self::MIN_SPILL_THRESHOLD..Self::NUM_BINS).rev() {
219            threshold = index;
220            // Calculate total number of live lines in this bucket.
221            let this_bucket_mark = mark_histograms
222                .iter()
223                .map(|v| v[threshold] as isize)
224                .sum::<isize>();
225            // Calculate the number of free lines in this bucket.
226            let this_bucket_avail = spill_avail_histograms[threshold] as isize;
227            // Update counters
228            limit -= this_bucket_avail;
229            required_lines += this_bucket_mark;
230            // Stop scanning. Lines to evacuate exceeds the free to-space lines.
231            if limit < required_lines {
232                break;
233            }
234        }
235        // println!("threshold: {}", threshold);
236        debug_assert!(threshold >= Self::MIN_SPILL_THRESHOLD);
237        self.defrag_spill_threshold
238            .store(threshold, Ordering::Release);
239    }
240
241    /// Reset the in-defrag state.
242    pub fn reset_in_defrag(&self) {
243        self.in_defrag_collection.store(false, Ordering::Release);
244    }
245}
mmtk/policy/immix/defrag.rs

mmtk/policy/immix/
defrag.rs
