mmtk/policy/marksweepspace/native_ms/
block_list.rs

1use super::{Block, BlockState};
2use crate::util::alloc::allocator;
3use crate::util::linear_scan::Region;
4use crate::vm::VMBinding;
5use std::sync::atomic::AtomicBool;
6use std::sync::atomic::Ordering;
7
8/// List of blocks owned by the allocator
9#[repr(C)]
10pub struct BlockList {
11    pub first: Option<Block>,
12    pub last: Option<Block>,
13    pub size: usize,
14    pub lock: AtomicBool,
15}
16
17impl std::fmt::Debug for BlockList {
18    fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
19        write!(f, "BlockList {:?}", self.iter().collect::<Vec<Block>>())
20    }
21}
22
23impl BlockList {
24    const fn new(size: usize) -> BlockList {
25        BlockList {
26            first: None,
27            last: None,
28            size,
29            lock: AtomicBool::new(false),
30        }
31    }
32
33    /// List has no blocks
34    pub fn is_empty(&self) -> bool {
35        self.first.is_none()
36    }
37
38    /// Remove a block from the list
39    pub fn remove(&mut self, block: Block) {
40        match (block.load_prev_block(), block.load_next_block()) {
41            (None, None) => {
42                self.first = None;
43                self.last = None;
44            }
45            (None, Some(next)) => {
46                next.clear_prev_block();
47                self.first = Some(next);
48                next.store_block_list(self);
49            }
50            (Some(prev), None) => {
51                prev.clear_next_block();
52                self.last = Some(prev);
53                prev.store_block_list(self);
54            }
55            (Some(prev), Some(next)) => {
56                prev.store_next_block(next);
57                next.store_prev_block(prev);
58            }
59        }
60    }
61
62    /// Pop the first block in the list
63    pub fn pop(&mut self) -> Option<Block> {
64        if let Some(head) = self.first {
65            if let Some(next) = head.load_next_block() {
66                self.first = Some(next);
67                next.clear_prev_block();
68                next.store_block_list(self);
69            } else {
70                self.first = None;
71                self.last = None;
72            }
73            head.clear_next_block();
74            head.clear_prev_block();
75            Some(head)
76        } else {
77            None
78        }
79    }
80
81    /// Push block to the front of the list
82    pub fn push(&mut self, block: Block) {
83        if self.is_empty() {
84            block.clear_next_block();
85            block.clear_prev_block();
86            self.first = Some(block);
87            self.last = Some(block);
88        } else {
89            let self_head = self.first.unwrap();
90            block.store_next_block(self_head);
91            self_head.store_prev_block(block);
92            block.clear_prev_block();
93            self.first = Some(block);
94        }
95        block.store_block_list(self);
96    }
97
98    /// Moves all the blocks of `other` into `self`, leaving `other` empty.
99    pub fn append(&mut self, other: &mut BlockList) {
100        debug_assert_eq!(self.size, other.size);
101        if !other.is_empty() {
102            debug_assert!(
103                other.first.unwrap().load_prev_block().is_none(),
104                "The other list's head has prev block: prev{} -> head{}",
105                other.first.unwrap().load_prev_block().unwrap().start(),
106                other.first.unwrap().start()
107            );
108            if self.is_empty() {
109                self.first = other.first;
110                self.last = other.last;
111            } else {
112                debug_assert!(
113                    self.first.unwrap().load_prev_block().is_none(),
114                    "Current list's head has prev block: prev{} -> head{}",
115                    self.first.unwrap().load_prev_block().unwrap().start(),
116                    self.first.unwrap().start()
117                );
118                let self_tail = self.last.unwrap();
119                let other_head = other.first.unwrap();
120                self_tail.store_next_block(other_head);
121                other_head.store_prev_block(self_tail);
122                self.last = other.last;
123            }
124            let mut cursor = other.first;
125            while let Some(block) = cursor {
126                block.store_block_list(self);
127                cursor = block.load_next_block();
128            }
129            other.reset();
130        }
131    }
132
133    /// Remove all blocks
134    fn reset(&mut self) {
135        self.first = None;
136        self.last = None;
137    }
138
139    /// Lock the list. The MiMalloc allocator mostly uses thread-local block lists, and those operations on the list
140    /// do not need synchronisation. However, in cases where a block list may be accessed by multiple threads, we need
141    /// to lock the list before accessing it.
142    ///
143    /// Our current sole use for locking is parallel sweeping. During the Release phase, multiple GC worker threads can
144    /// sweep chunks and release mutators at the same time, and the same `BlockList` can be reached by traversing blocks in a chunk,
145    /// and also by traversing blocks held by a mutator.  This lock is necessary to prevent
146    /// multiple GC workers from mutating the same `BlockList` instance.
147    pub fn lock(&mut self) {
148        let mut success = false;
149        while !success {
150            success = self
151                .lock
152                .compare_exchange(false, true, Ordering::SeqCst, Ordering::SeqCst)
153                .is_ok();
154        }
155    }
156
157    /// Unlock list. See the comments on the lock method.
158    pub fn unlock(&mut self) {
159        self.lock.store(false, Ordering::SeqCst);
160    }
161
162    /// Get an iterator for the block list.
163    pub fn iter(&self) -> BlockListIterator {
164        BlockListIterator { cursor: self.first }
165    }
166
167    /// Release unmarked blocks, and sweep other blocks in the block list. Used by eager sweeping.
168    pub fn release_and_sweep_blocks<VM: VMBinding>(&self, space: &super::MarkSweepSpace<VM>) {
169        for block in self.iter() {
170            // We should not have unallocated blocks in a block list
171            debug_assert_ne!(block.get_state(), BlockState::Unallocated);
172            if !block.attempt_release(space) {
173                block.sweep::<VM>();
174            }
175        }
176    }
177
178    /// Release unmarked blocks, and do not sweep any blocks. Used by lazy sweeping
179    pub fn release_blocks<VM: VMBinding>(&self, space: &super::MarkSweepSpace<VM>) {
180        for block in self.iter() {
181            // We should not have unallocated blocks in a block list
182            debug_assert_ne!(block.get_state(), BlockState::Unallocated);
183            block.attempt_release(space);
184        }
185    }
186}
187
188pub struct BlockListIterator {
189    cursor: Option<Block>,
190}
191
192impl Iterator for BlockListIterator {
193    type Item = Block;
194
195    fn next(&mut self) -> Option<Self::Item> {
196        let ret = self.cursor;
197        if let Some(cur) = self.cursor {
198            self.cursor = cur.load_next_block();
199        }
200        ret
201    }
202}
203
204/// Log2 of pointer size
205const MI_INTPTR_SHIFT: usize = crate::util::constants::LOG_BYTES_IN_ADDRESS as usize;
206/// pointer size in bytes
207const MI_INTPTR_SIZE: usize = 1 << MI_INTPTR_SHIFT;
208/// pointer size in bits
209const MI_INTPTR_BITS: usize = MI_INTPTR_SIZE * 8;
210/// Number of bins in BlockLists. Reserve bin0 as an empty bin.
211pub(crate) const MI_BIN_FULL: usize = MAX_BIN + 1;
212/// The largest valid bin.
213pub(crate) const MAX_BIN: usize = 48;
214
215/// Largest object size allowed with our mimalloc implementation, in bytes
216pub(crate) const MI_LARGE_OBJ_SIZE_MAX: usize =
217    crate::util::rust_util::min_of_usize(Block::BYTES, MAX_BIN_SIZE);
218/// Largest object size in words
219const MI_LARGE_OBJ_WSIZE_MAX: usize = MI_LARGE_OBJ_SIZE_MAX / MI_INTPTR_SIZE;
220/// The object size for the last bin. We should not try allocate objects larger than this with the allocator.
221pub(crate) const MAX_BIN_SIZE: usize = 8192 * MI_INTPTR_SIZE;
222
223/// All the bins for the block lists
224// Each block list takes roughly 8bytes * 4 * 49 = 1658 bytes. It is more reasonable to heap allocate them, and
225// just put them behind a boxed pointer.
226pub type BlockLists = Box<[BlockList; MAX_BIN + 1]>;
227
228/// Create an empty set of block lists of different size classes (bins)
229pub(crate) fn new_empty_block_lists() -> BlockLists {
230    let ret = Box::new([
231        BlockList::new(MI_INTPTR_SIZE),
232        BlockList::new(MI_INTPTR_SIZE),
233        BlockList::new(2 * MI_INTPTR_SIZE),
234        BlockList::new(3 * MI_INTPTR_SIZE),
235        BlockList::new(4 * MI_INTPTR_SIZE),
236        BlockList::new(5 * MI_INTPTR_SIZE),
237        BlockList::new(6 * MI_INTPTR_SIZE),
238        BlockList::new(7 * MI_INTPTR_SIZE),
239        BlockList::new(8 * MI_INTPTR_SIZE), /* 8 */
240        BlockList::new(10 * MI_INTPTR_SIZE),
241        BlockList::new(12 * MI_INTPTR_SIZE),
242        BlockList::new(14 * MI_INTPTR_SIZE),
243        BlockList::new(16 * MI_INTPTR_SIZE),
244        BlockList::new(20 * MI_INTPTR_SIZE),
245        BlockList::new(24 * MI_INTPTR_SIZE),
246        BlockList::new(28 * MI_INTPTR_SIZE),
247        BlockList::new(32 * MI_INTPTR_SIZE), /* 16 */
248        BlockList::new(40 * MI_INTPTR_SIZE),
249        BlockList::new(48 * MI_INTPTR_SIZE),
250        BlockList::new(56 * MI_INTPTR_SIZE),
251        BlockList::new(64 * MI_INTPTR_SIZE),
252        BlockList::new(80 * MI_INTPTR_SIZE),
253        BlockList::new(96 * MI_INTPTR_SIZE),
254        BlockList::new(112 * MI_INTPTR_SIZE),
255        BlockList::new(128 * MI_INTPTR_SIZE), /* 24 */
256        BlockList::new(160 * MI_INTPTR_SIZE),
257        BlockList::new(192 * MI_INTPTR_SIZE),
258        BlockList::new(224 * MI_INTPTR_SIZE),
259        BlockList::new(256 * MI_INTPTR_SIZE),
260        BlockList::new(320 * MI_INTPTR_SIZE),
261        BlockList::new(384 * MI_INTPTR_SIZE),
262        BlockList::new(448 * MI_INTPTR_SIZE),
263        BlockList::new(512 * MI_INTPTR_SIZE), /* 32 */
264        BlockList::new(640 * MI_INTPTR_SIZE),
265        BlockList::new(768 * MI_INTPTR_SIZE),
266        BlockList::new(896 * MI_INTPTR_SIZE),
267        BlockList::new(1024 * MI_INTPTR_SIZE),
268        BlockList::new(1280 * MI_INTPTR_SIZE),
269        BlockList::new(1536 * MI_INTPTR_SIZE),
270        BlockList::new(1792 * MI_INTPTR_SIZE),
271        BlockList::new(2048 * MI_INTPTR_SIZE), /* 40 */
272        BlockList::new(2560 * MI_INTPTR_SIZE),
273        BlockList::new(3072 * MI_INTPTR_SIZE),
274        BlockList::new(3584 * MI_INTPTR_SIZE),
275        BlockList::new(4096 * MI_INTPTR_SIZE),
276        BlockList::new(5120 * MI_INTPTR_SIZE),
277        BlockList::new(6144 * MI_INTPTR_SIZE),
278        BlockList::new(7168 * MI_INTPTR_SIZE),
279        BlockList::new(8192 * MI_INTPTR_SIZE), /* 48 */
280    ]);
281
282    debug_assert_eq!(
283        ret[MAX_BIN].size, MAX_BIN_SIZE,
284        "MAX_BIN_SIZE = {}, actual max bin size  = {}, please update the constants",
285        MAX_BIN_SIZE, ret[MAX_BIN].size
286    );
287
288    ret
289}
290
291/// Returns how many pages the block lists uses.
292#[allow(unused)]
293pub(crate) fn pages_used_by_blocklists(lists: &BlockLists) -> usize {
294    let mut pages = 0;
295    for bin in 1..=MAX_BIN {
296        let list = &lists[bin];
297
298        // walk the blocks
299        let mut cursor = list.first;
300        while let Some(block) = cursor {
301            pages += Block::BYTES >> crate::util::constants::LOG_BYTES_IN_PAGE;
302            cursor = block.load_next_block();
303        }
304    }
305
306    pages
307}
308
309/// Align a byte size to a size in machine words
310/// i.e. byte size == `wsize*sizeof(void*)`
311/// adapted from _mi_wsize_from_size in mimalloc
312fn mi_wsize_from_size(size: usize) -> usize {
313    size.div_ceil(MI_INTPTR_SIZE)
314}
315
316pub fn mi_bin<VM: VMBinding>(size: usize, align: usize) -> usize {
317    let size = allocator::get_maximum_aligned_size::<VM>(size, align);
318    mi_bin_from_size(size)
319}
320
321fn mi_bin_from_size(size: usize) -> usize {
322    // adapted from _mi_bin in mimalloc
323    let mut wsize: usize = mi_wsize_from_size(size);
324    debug_assert!(wsize <= MI_LARGE_OBJ_WSIZE_MAX);
325    let bin: u8;
326    if wsize <= 1 {
327        bin = 1;
328    } else if wsize <= 8 {
329        bin = wsize as u8;
330        // bin = ((wsize + 1) & !1) as u8; // round to double word sizes
331    } else {
332        wsize -= 1;
333        let b = (MI_INTPTR_BITS - 1 - usize::leading_zeros(wsize) as usize) as u8; // note: wsize != 0
334        bin = ((b << 2) + ((wsize >> (b - 2)) & 0x03) as u8) - 3;
335    }
336    bin as usize
337}
338
339#[cfg(test)]
340mod tests {
341    use super::*;
342
343    fn get_bin_size_range(bin: usize, bins: &BlockLists) -> Option<(usize, usize)> {
344        if bin == 0 || bin > MAX_BIN {
345            None
346        } else if bin == 1 {
347            Some((0, bins[1].size))
348        } else {
349            Some((bins[bin - 1].size, bins[bin].size))
350        }
351    }
352
353    #[test]
354    fn test_mi_bin() {
355        let block_lists = new_empty_block_lists();
356        for size in 0..=MAX_BIN_SIZE {
357            let bin = mi_bin_from_size(size);
358            let bin_range = get_bin_size_range(bin, &block_lists);
359            assert!(bin_range.is_some(), "Invalid bin {} for size {}", bin, size);
360            assert!(
361                size >= bin_range.unwrap().0 && bin < bin_range.unwrap().1,
362                "Assigning size={} to bin={} ({:?}) incorrect",
363                size,
364                bin,
365                bin_range.unwrap()
366            );
367        }
368    }
369}
mmtk/policy/marksweepspace/native_ms/block_list.rs

mmtk/policy/marksweepspace/native_ms/
block_list.rs
