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            // `update()` allows infallable atomic update, but is not stablized until 1.95.
134            // Migrate to `update()` after bumping MSRV.
135            #[allow(deprecated)]
136            let available_clean_pages_for_defrag =
137                self.available_clean_pages_for_defrag.fetch_update(
138                    Ordering::SeqCst,
139                    Ordering::SeqCst,
140                    |available_clean_pages_for_defrag| {
141                        Some(available_clean_pages_for_defrag.saturating_sub(Block::PAGES))
142                    },
143                );
144            if available_clean_pages_for_defrag.unwrap() <= Block::PAGES {
145                self.defrag_space_exhausted.store(true, Ordering::SeqCst);
146            }
147        }
148    }
149
150    /// Prepare work. Should be called in ImmixSpace::prepare.
151    pub fn prepare<VM: VMBinding>(&self, space: &ImmixSpace<VM>, plan_stats: StatsForDefrag) {
152        debug_assert!(space.is_defrag_enabled());
153        self.defrag_space_exhausted.store(false, Ordering::Release);
154
155        // Calculate available free space for defragmentation.
156
157        let mut available_clean_pages_for_defrag = plan_stats.total_pages as isize
158            - plan_stats.reserved_pages as isize
159            + self.defrag_headroom_pages(space) as isize;
160        if available_clean_pages_for_defrag < 0 {
161            available_clean_pages_for_defrag = 0
162        };
163
164        self.available_clean_pages_for_defrag
165            .store(available_clean_pages_for_defrag as usize, Ordering::Release);
166
167        if self.in_defrag() {
168            self.establish_defrag_spill_threshold(space)
169        }
170
171        self.available_clean_pages_for_defrag.store(
172            available_clean_pages_for_defrag as usize + plan_stats.collection_reserved_pages,
173            Ordering::Release,
174        );
175    }
176
177    /// Get the numebr of all the recyclable lines in all the reusable blocks.
178    fn get_available_lines<VM: VMBinding>(
179        &self,
180        space: &ImmixSpace<VM>,
181        spill_avail_histograms: &mut Histogram,
182    ) -> usize {
183        let mut total_available_lines = 0;
184        space.reusable_blocks.iterate_blocks(|block| {
185            let bucket = block.get_holes();
186            let unavailable_lines = match block.get_state() {
187                BlockState::Reusable { unavailable_lines } => unavailable_lines as usize,
188                s => unreachable!("{:?} {:?}", block, s),
189            };
190            let available_lines = Block::LINES - unavailable_lines;
191            spill_avail_histograms[bucket] += available_lines;
192            total_available_lines += available_lines;
193        });
194        total_available_lines
195    }
196
197    /// Calculate the defrag threshold.
198    fn establish_defrag_spill_threshold<VM: VMBinding>(&self, space: &ImmixSpace<VM>) {
199        let mut spill_avail_histograms = self.new_histogram();
200        let clean_lines = self.get_available_lines(space, &mut spill_avail_histograms);
201        let available_lines = clean_lines
202            + (self
203                .available_clean_pages_for_defrag
204                .load(Ordering::Acquire)
205                << (LOG_BYTES_IN_PAGE as usize - Line::LOG_BYTES));
206
207        // Number of lines we will evacuate.
208        let mut required_lines = 0isize;
209        // Number of to-space free lines we can use for defragmentation.
210        let mut limit = (available_lines as f32 / Self::DEFRAG_LINE_REUSE_RATIO) as isize;
211        let mut threshold = Block::LINES >> 1;
212        let mark_histograms = self.mark_histograms.lock();
213        // Blocks are grouped by buckets, indexed by the number of holes in the block.
214        // `mark_histograms` remembers the number of live lines for each bucket.
215        // Here, reversely iterate all the bucket to find a threshold that all buckets above this
216        // threshold can be evacuated, without causing to-space overflow.
217        for index in (Self::MIN_SPILL_THRESHOLD..Self::NUM_BINS).rev() {
218            threshold = index;
219            // Calculate total number of live lines in this bucket.
220            let this_bucket_mark = mark_histograms
221                .iter()
222                .map(|v| v[threshold] as isize)
223                .sum::<isize>();
224            // Calculate the number of free lines in this bucket.
225            let this_bucket_avail = spill_avail_histograms[threshold] as isize;
226            // Update counters
227            limit -= this_bucket_avail;
228            required_lines += this_bucket_mark;
229            // Stop scanning. Lines to evacuate exceeds the free to-space lines.
230            if limit < required_lines {
231                break;
232            }
233        }
234        // println!("threshold: {}", threshold);
235        debug_assert!(threshold >= Self::MIN_SPILL_THRESHOLD);
236        self.defrag_spill_threshold
237            .store(threshold, Ordering::Release);
238    }
239
240    /// Reset the in-defrag state.
241    pub fn reset_in_defrag(&self) {
242        self.in_defrag_collection.store(false, Ordering::Release);
243    }
244}
mmtk/policy/immix/defrag.rs

mmtk/policy/immix/
defrag.rs
