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        stress_defrag: bool,
76    ) {
77        let in_defrag = defrag_enabled
78            && (emergency_collection
79                || (collection_attempts > 1)
80                || !exhausted_reusable_space
81                || stress_defrag
82                || (collect_whole_heap && user_triggered && full_heap_system_gc));
83
84        {
85            // These details are useful for debugging why a debug GC is triggered or not triggered.
86            // We encode those conditions into a bitfield because we can't pass too many args to the
87            // eBPF tracer via the USDT arguments.
88            let decision_word = (defrag_enabled as u32)
89                | (emergency_collection as u32) << 1
90                | (collect_whole_heap as u32) << 2
91                | (user_triggered as u32) << 3
92                | (exhausted_reusable_space as u32) << 4
93                | (full_heap_system_gc as u32) << 5
94                | (stress_defrag as u32) << 6;
95
96            info!(
97                "Defrag: {i}, collection_attempts: {c}, decision_word: 0b{d:b}",
98                i = in_defrag,
99                c = collection_attempts,
100                d = decision_word,
101            );
102
103            probe!(
104                mmtk,
105                immix_defrag,
106                in_defrag,
107                collection_attempts,
108                decision_word
109            );
110        }
111
112        self.in_defrag_collection
113            .store(in_defrag, Ordering::Release)
114    }
115
116    /// Get the number of defrag headroom pages.
117    pub fn defrag_headroom_pages<VM: VMBinding>(&self, space: &ImmixSpace<VM>) -> usize {
118        space.get_page_resource().reserved_pages()
119            * (*space.common().options.immix_defrag_headroom_percent)
120            / 100
121    }
122
123    /// Check if the defrag space is exhausted.
124    pub fn space_exhausted(&self) -> bool {
125        self.defrag_space_exhausted.load(Ordering::Acquire)
126    }
127
128    /// Update available_clean_pages_for_defrag counter when a clean block is allocated.
129    pub fn notify_new_clean_block(&self, copy: bool) {
130        if copy {
131            let available_clean_pages_for_defrag =
132                self.available_clean_pages_for_defrag.fetch_update(
133                    Ordering::SeqCst,
134                    Ordering::SeqCst,
135                    |available_clean_pages_for_defrag| {
136                        if available_clean_pages_for_defrag <= Block::PAGES {
137                            Some(0)
138                        } else {
139                            Some(available_clean_pages_for_defrag - Block::PAGES)
140                        }
141                    },
142                );
143            if available_clean_pages_for_defrag.unwrap() <= Block::PAGES {
144                self.defrag_space_exhausted.store(true, Ordering::SeqCst);
145            }
146        }
147    }
148
149    /// Prepare work. Should be called in ImmixSpace::prepare.
150    pub fn prepare<VM: VMBinding>(&self, space: &ImmixSpace<VM>, plan_stats: StatsForDefrag) {
151        debug_assert!(space.is_defrag_enabled());
152        self.defrag_space_exhausted.store(false, Ordering::Release);
153
154        // Calculate available free space for defragmentation.
155
156        let mut available_clean_pages_for_defrag = plan_stats.total_pages as isize
157            - plan_stats.reserved_pages as isize
158            + self.defrag_headroom_pages(space) as isize;
159        if available_clean_pages_for_defrag < 0 {
160            available_clean_pages_for_defrag = 0
161        };
162
163        self.available_clean_pages_for_defrag
164            .store(available_clean_pages_for_defrag as usize, Ordering::Release);
165
166        if self.in_defrag() {
167            self.establish_defrag_spill_threshold(space)
168        }
169
170        self.available_clean_pages_for_defrag.store(
171            available_clean_pages_for_defrag as usize + plan_stats.collection_reserved_pages,
172            Ordering::Release,
173        );
174    }
175
176    /// Get the numebr of all the recyclable lines in all the reusable blocks.
177    fn get_available_lines<VM: VMBinding>(
178        &self,
179        space: &ImmixSpace<VM>,
180        spill_avail_histograms: &mut Histogram,
181    ) -> usize {
182        let mut total_available_lines = 0;
183        space.reusable_blocks.iterate_blocks(|block| {
184            let bucket = block.get_holes();
185            let unavailable_lines = match block.get_state() {
186                BlockState::Reusable { unavailable_lines } => unavailable_lines as usize,
187                s => unreachable!("{:?} {:?}", block, s),
188            };
189            let available_lines = Block::LINES - unavailable_lines;
190            spill_avail_histograms[bucket] += available_lines;
191            total_available_lines += available_lines;
192        });
193        total_available_lines
194    }
195
196    /// Calculate the defrag threshold.
197    fn establish_defrag_spill_threshold<VM: VMBinding>(&self, space: &ImmixSpace<VM>) {
198        let mut spill_avail_histograms = self.new_histogram();
199        let clean_lines = self.get_available_lines(space, &mut spill_avail_histograms);
200        let available_lines = clean_lines
201            + (self
202                .available_clean_pages_for_defrag
203                .load(Ordering::Acquire)
204                << (LOG_BYTES_IN_PAGE as usize - Line::LOG_BYTES));
205
206        // Number of lines we will evacuate.
207        let mut required_lines = 0isize;
208        // Number of to-space free lines we can use for defragmentation.
209        let mut limit = (available_lines as f32 / Self::DEFRAG_LINE_REUSE_RATIO) as isize;
210        let mut threshold = Block::LINES >> 1;
211        let mark_histograms = self.mark_histograms.lock();
212        // Blocks are grouped by buckets, indexed by the number of holes in the block.
213        // `mark_histograms` remembers the number of live lines for each bucket.
214        // Here, reversely iterate all the bucket to find a threshold that all buckets above this
215        // threshold can be evacuated, without causing to-space overflow.
216        for index in (Self::MIN_SPILL_THRESHOLD..Self::NUM_BINS).rev() {
217            threshold = index;
218            // Calculate total number of live lines in this bucket.
219            let this_bucket_mark = mark_histograms
220                .iter()
221                .map(|v| v[threshold] as isize)
222                .sum::<isize>();
223            // Calculate the number of free lines in this bucket.
224            let this_bucket_avail = spill_avail_histograms[threshold] as isize;
225            // Update counters
226            limit -= this_bucket_avail;
227            required_lines += this_bucket_mark;
228            // Stop scanning. Lines to evacuate exceeds the free to-space lines.
229            if limit < required_lines {
230                break;
231            }
232        }
233        // println!("threshold: {}", threshold);
234        debug_assert!(threshold >= Self::MIN_SPILL_THRESHOLD);
235        self.defrag_spill_threshold
236            .store(threshold, Ordering::Release);
237    }
238
239    /// Reset the in-defrag state.
240    pub fn reset_in_defrag(&self) {
241        self.in_defrag_collection.store(false, Ordering::Release);
242    }
243}
mmtk/policy/immix/defrag.rs

mmtk/policy/immix/
defrag.rs
