mmtk/util/
raw_memory_freelist.rs

1use super::freelist::*;
2use crate::util::address::Address;
3use crate::util::constants::*;
4use crate::util::conversions;
5use crate::util::os::*;
6
7/** log2 of the number of bits used by a free list entry (two entries per unit) */
8const LOG_ENTRY_BITS: usize = i32::BITS.ilog2() as _;
9
10/** log2 of the number of bytes used by a free list entry (two entries per unit) */
11const LOG_BYTES_IN_ENTRY: usize = LOG_ENTRY_BITS - (LOG_BITS_IN_BYTE as usize);
12
13/** log2 of the number of bytes used by a free list unit */
14const LOG_BYTES_IN_UNIT: usize = LOG_BYTES_IN_ENTRY + 1;
15
16#[derive(Debug)]
17pub struct RawMemoryFreeList {
18    pub head: i32,
19    pub heads: i32,
20    base: Address,
21    limit: Address,
22    high_water: Address,
23    max_units: i32,
24    grain: i32,
25    current_units: i32,
26    pages_per_block: i32,
27    strategy: MmapStrategy,
28    slice: &'static mut [i32],
29}
30
31impl FreeList for RawMemoryFreeList {
32    fn head(&self) -> i32 {
33        self.head
34    }
35    fn heads(&self) -> i32 {
36        self.heads
37    }
38    fn get_entry(&self, index: i32) -> i32 {
39        #[cfg(debug_assertions)]
40        {
41            let len = (self.high_water - self.base) >> LOG_BYTES_IN_ENTRY;
42            debug_assert_eq!(
43                len,
44                self.slice.len(),
45                "Length does not match.  \
46                high_water: {h}, base: {b}, computed len: {len}, \
47                slice len: {sl}",
48                h = self.high_water,
49                b = self.base,
50                sl = self.slice.len()
51            );
52        }
53        self.slice[index as usize]
54    }
55    fn set_entry(&mut self, index: i32, value: i32) {
56        #[cfg(debug_assertions)]
57        {
58            let len = (self.high_water - self.base) >> LOG_BYTES_IN_ENTRY;
59            debug_assert_eq!(
60                len,
61                self.slice.len(),
62                "Length does not match.  \
63                high_water: {h}, base: {b}, computed len: {len}, \
64                slice len: {sl}",
65                h = self.high_water,
66                b = self.base,
67                sl = self.slice.len()
68            );
69        }
70        self.slice[index as usize] = value;
71    }
72    fn alloc(&mut self, size: i32) -> i32 {
73        if self.current_units == 0 {
74            return FAILURE;
75        }
76        let mut unit = self.head();
77        let mut s = 0;
78        while ({
79            unit = self.get_next(unit);
80            unit != self.head()
81        }) && ({
82            s = self.get_size(unit);
83            s < size
84        }) {}
85        if unit == self.head() {
86            FAILURE
87        } else {
88            self.__alloc(size, unit, s)
89        }
90    }
91}
92
93impl RawMemoryFreeList {
94    fn units_per_block(&self) -> i32 {
95        (conversions::pages_to_bytes(self.pages_per_block as _) >> LOG_BYTES_IN_UNIT) as _
96    }
97    fn units_in_first_block(&self) -> i32 {
98        self.units_per_block() - self.heads - 1
99    }
100    pub fn default_block_size(units: i32, heads: i32) -> i32 {
101        usize::min(Self::size_in_pages(units, heads) as _, 16) as _
102    }
103    pub fn size_in_pages(units: i32, heads: i32) -> i32 {
104        let map_size = ((units + heads + 1) as usize) << LOG_BYTES_IN_UNIT;
105        conversions::bytes_to_pages_up(map_size as _) as _
106    }
107
108    pub fn new(
109        base: Address,
110        limit: Address,
111        pages_per_block: i32,
112        units: i32,
113        grain: i32,
114        heads: i32,
115        strategy: MmapStrategy,
116    ) -> Self {
117        debug_assert!(units <= MAX_UNITS && heads <= MAX_HEADS);
118        debug_assert!(
119            base + conversions::pages_to_bytes(Self::size_in_pages(units, heads) as _) <= limit
120        );
121        Self {
122            head: -1,
123            heads,
124            base,
125            limit,
126            high_water: base,
127            max_units: units,
128            grain,
129            current_units: 0,
130            pages_per_block,
131            strategy,
132            // SAFETY: when a RawMemoryFreelist is created, its address range is
133            // base..base, a zero-sized slice starting at base
134            slice: unsafe { std::slice::from_raw_parts_mut(base.to_mut_ptr::<i32>(), 0) },
135        }
136    }
137
138    fn current_capacity(&self) -> i32 {
139        let list_blocks = conversions::bytes_to_pages_up(self.high_water - self.base) as i32
140            / self.pages_per_block;
141        self.units_in_first_block() + (list_blocks - 1) * self.units_per_block()
142    }
143
144    pub fn grow_freelist(&mut self, units: i32) -> bool {
145        let required_units = units + self.current_units;
146        if required_units > self.max_units {
147            return false;
148        }
149        let blocks = if required_units > self.current_capacity() {
150            let units_requested = required_units - self.current_capacity();
151            (units_requested + self.units_per_block() - 1) / self.units_per_block()
152        } else {
153            0
154        };
155        self.grow_list_by_blocks(blocks, required_units);
156        true
157    }
158    fn grow_list_by_blocks(&mut self, blocks: i32, new_max: i32) {
159        debug_assert!(
160            (new_max <= self.grain) || (((new_max / self.grain) * self.grain) == new_max)
161        );
162
163        if blocks > 0 {
164            // Allocate more VM from the OS
165            self.raise_high_water(blocks);
166        }
167
168        let len = (self.high_water - self.base) >> LOG_BYTES_IN_ENTRY;
169        // SAFETY: The memory is mapped and valid after `raise_high_water`.
170        self.slice = unsafe { std::slice::from_raw_parts_mut(self.base.to_mut_ptr::<i32>(), len) };
171
172        let old_max = self.current_units;
173        assert!(
174            new_max <= self.current_capacity(),
175            "blocks and new max are inconsistent: need more blocks for the requested capacity"
176        );
177        assert!(
178            new_max <= self.max_units,
179            "Requested list to grow larger than the configured maximum"
180        );
181        self.current_units = new_max;
182
183        if old_max == 0 {
184            // First allocation of capacity: initialize the sentinels.
185            for i in 1..=self.heads {
186                self.set_sentinel(-i);
187            }
188        } else {
189            // Turn the old top-of-heap sentinel into a single used block
190            self.set_size(old_max, 1);
191        }
192
193        if new_max == 0 {
194            return;
195        }
196
197        // Set a sentinel at the top of the new range
198        self.set_sentinel(new_max);
199
200        let mut cursor = new_max;
201
202        /* A series of grain size regions in the middle */
203        let grain = i32::min(self.grain, new_max - old_max);
204        cursor -= grain;
205        while cursor >= old_max {
206            self.set_size(cursor, grain);
207            self.add_to_free(cursor);
208            cursor -= grain;
209        }
210    }
211
212    fn raise_high_water(&mut self, blocks: i32) {
213        let mut grow_extent = conversions::pages_to_bytes((self.pages_per_block * blocks) as _);
214        assert_ne!(
215            self.high_water, self.limit,
216            "Attempt to grow FreeList beyond limit"
217        );
218        if self.high_water + grow_extent > self.limit {
219            grow_extent = self.high_water - self.limit;
220        }
221        self.mmap(self.high_water, grow_extent);
222        self.high_water += grow_extent;
223    }
224
225    fn mmap(&self, start: Address, bytes: usize) {
226        let res = OS::dzmmap(
227            start,
228            bytes,
229            self.strategy,
230            &MmapAnnotation::Misc {
231                name: "RawMemoryFreeList",
232            },
233        );
234        assert!(
235            res.is_ok(),
236            "Failed to mmap memory for RawMemoryFreeList: start = {start}, bytes = {bytes}, strategy = {:?}",
237            self.strategy
238        );
239    }
240    pub fn get_limit(&self) -> Address {
241        self.limit
242    }
243}
244
245/**
246 * See documentation of `mod tests` below for the necessity of `impl Drop`.
247 */
248#[cfg(test)]
249impl Drop for RawMemoryFreeList {
250    fn drop(&mut self) {
251        let len = self.high_water - self.base;
252        if len != 0 {
253            let _ = OS::munmap(self.base, len);
254        }
255    }
256}
257
258/**
259 * The initialization of `RawMemoryFreeList` involves memory-mapping a fixed range of virtual address.
260 *
261 * This raises an implicit assumption that a test process can only have one `RawMemoryFreeList` instance at a time unless each instance uses different fixed address ranges.
262 *
263 * We use a single fixed address range for all the following tests. So the tests cannot be executed in parallel. Which means:
264 *
265 * 1. Each test should hold a global mutex to prevent parallel execution.
266 * 2. `RawMemoryFreeList` should implement `Drop` trait to unmap the memory properly at the end of each test.
267 */
268#[cfg(test)]
269mod tests {
270    use super::FreeList;
271    use super::*;
272    use std::sync::{Mutex, MutexGuard};
273
274    const TOP_SENTINEL: i32 = -1;
275    const FIRST_UNIT: i32 = 0;
276
277    lazy_static! {
278        /**
279         * See documentation of `mod tests` above for for the necessity of this mutex.
280         */
281        static ref MUTEX: Mutex<()> = Mutex::new(());
282    }
283
284    fn new_raw_memory_freelist<'a>(
285        list_size: usize,
286        grain: i32,
287    ) -> (MutexGuard<'a, ()>, RawMemoryFreeList, i32, i32, i32) {
288        /*
289         * Note: The mutex could be poisoned!
290         * Test `free_list_access_out_of_bounds` below is expected to panic and poison the mutex.
291         * So we need to manually recover the lock here, if it is poisoned.
292         *
293         * See documentation of `mod tests` above for more details.
294         */
295        let guard = match MUTEX.lock() {
296            Ok(guard) => guard,
297            Err(poisoned) => poisoned.into_inner(),
298        };
299        let start = crate::util::test_util::RAW_MEMORY_FREELIST_TEST_REGION.start;
300        let extent = BYTES_IN_PAGE;
301        let pages_per_block = RawMemoryFreeList::default_block_size(list_size as _, 1);
302        assert_eq!(pages_per_block, 1);
303        let mut l = RawMemoryFreeList::new(
304            start,
305            start + extent,
306            pages_per_block,
307            list_size as _,
308            grain,
309            1,
310            MmapStrategy::TEST,
311        );
312        // Grow the free-list to do the actual memory-mapping.
313        l.grow_freelist(list_size as _);
314        let last_unit = list_size as i32 - grain;
315        let bottom_sentinel = list_size as i32;
316        (guard, l, list_size as _, last_unit, bottom_sentinel)
317    }
318
319    #[test]
320    #[allow(clippy::cognitive_complexity)] // extensive checks, and it doesn't matter for tests
321    fn new_free_list_grain1() {
322        let (_guard, l, _, last_unit, bottom_sentinel) = new_raw_memory_freelist(5, 1);
323        assert_eq!(l.head(), TOP_SENTINEL);
324
325        assert_eq!(l.get_prev(TOP_SENTINEL), last_unit);
326        assert_eq!(l.get_next(TOP_SENTINEL), FIRST_UNIT);
327
328        assert_eq!(l.get_size(FIRST_UNIT), 1);
329        assert_eq!(l.get_left(FIRST_UNIT), -1);
330        assert_eq!(l.get_prev(FIRST_UNIT), -1);
331        assert_eq!(l.get_right(FIRST_UNIT), 1);
332        assert_eq!(l.get_next(FIRST_UNIT), 1);
333        assert!(l.is_free(FIRST_UNIT));
334        assert!(l.is_coalescable(FIRST_UNIT));
335        assert!(!l.is_multi(FIRST_UNIT));
336
337        assert_eq!(l.get_size(1), 1);
338        assert_eq!(l.get_left(1), 0);
339        assert_eq!(l.get_prev(1), 0);
340        assert_eq!(l.get_right(1), 2);
341        assert_eq!(l.get_next(1), 2);
342        assert!(l.is_free(1));
343        assert!(l.is_coalescable(1));
344        assert!(!l.is_multi(1));
345
346        assert_eq!(l.get_size(last_unit), 1);
347        assert_eq!(l.get_left(last_unit), last_unit - 1);
348        assert_eq!(l.get_prev(last_unit), last_unit - 1);
349        assert_eq!(l.get_right(last_unit), bottom_sentinel);
350        assert_eq!(l.get_next(last_unit), -1);
351        assert!(l.is_free(last_unit));
352        assert!(l.is_coalescable(last_unit));
353        assert!(!l.is_multi(last_unit));
354
355        assert_eq!(l.get_prev(bottom_sentinel), bottom_sentinel);
356        assert_eq!(l.get_next(bottom_sentinel), bottom_sentinel);
357    }
358
359    #[test]
360    #[allow(clippy::cognitive_complexity)] // extensive checks, and it doesn't matter for tests
361    fn new_free_list_grain2() {
362        let (_guard, l, _, last_unit, bottom_sentinel) = new_raw_memory_freelist(6, 2);
363        assert_eq!(l.head(), TOP_SENTINEL);
364
365        assert_eq!(l.get_prev(TOP_SENTINEL), last_unit);
366        assert_eq!(l.get_next(TOP_SENTINEL), FIRST_UNIT);
367
368        assert_eq!(l.get_size(FIRST_UNIT), 2);
369        assert_eq!(l.get_left(FIRST_UNIT), -1);
370        assert_eq!(l.get_prev(FIRST_UNIT), -1);
371        assert_eq!(l.get_right(FIRST_UNIT), 2);
372        assert_eq!(l.get_next(FIRST_UNIT), 2);
373        assert!(l.is_free(FIRST_UNIT));
374        assert!(l.is_coalescable(FIRST_UNIT));
375        assert!(l.is_multi(FIRST_UNIT));
376
377        assert_eq!(l.get_size(2), 2);
378        assert_eq!(l.get_left(2), 0);
379        assert_eq!(l.get_prev(2), 0);
380        assert_eq!(l.get_right(2), 4);
381        assert_eq!(l.get_next(2), 4);
382        assert!(l.is_free(2));
383        assert!(l.is_coalescable(2));
384        assert!(l.is_multi(2));
385
386        assert_eq!(l.get_size(last_unit), 2);
387        assert_eq!(l.get_left(last_unit), last_unit - 2);
388        assert_eq!(l.get_prev(last_unit), last_unit - 2);
389        assert_eq!(l.get_right(last_unit), bottom_sentinel);
390        assert_eq!(l.get_next(last_unit), -1);
391        assert!(l.is_free(last_unit));
392        assert!(l.is_coalescable(last_unit));
393        assert!(l.is_multi(last_unit));
394
395        assert_eq!(l.get_prev(bottom_sentinel), bottom_sentinel);
396        assert_eq!(l.get_next(bottom_sentinel), bottom_sentinel);
397    }
398
399    #[test]
400    #[should_panic]
401    fn free_list_access_out_of_bounds() {
402        let (_guard, l, _, _, _) = new_raw_memory_freelist(5, 1);
403        l.get_size(4096);
404        // `_guard` should be dropped during stack unwinding
405    }
406
407    #[test]
408    fn alloc_fit() {
409        let (_guard, mut l, _, last_unit, _) = new_raw_memory_freelist(6, 2);
410        let result = l.alloc(2);
411        assert_eq!(result, 0);
412
413        const NEXT: i32 = 2;
414
415        assert_eq!(l.get_prev(TOP_SENTINEL), last_unit);
416        assert_eq!(l.get_next(TOP_SENTINEL), NEXT);
417
418        assert_eq!(l.get_size(FIRST_UNIT), 2);
419        assert_eq!(l.get_left(FIRST_UNIT), -1);
420        assert_eq!(l.get_prev(FIRST_UNIT), -1);
421        assert_eq!(l.get_right(FIRST_UNIT), 2);
422        assert_eq!(l.get_next(FIRST_UNIT), 2);
423        assert!(!l.is_free(FIRST_UNIT)); // not free
424        assert!(l.is_coalescable(FIRST_UNIT));
425        assert!(l.is_multi(FIRST_UNIT));
426
427        assert_eq!(l.get_size(2), 2);
428        assert_eq!(l.get_left(2), 0);
429        assert_eq!(l.get_prev(2), -1); // no prev now
430        assert_eq!(l.get_right(2), 4);
431        assert_eq!(l.get_next(2), 4);
432        assert!(l.is_free(2));
433        assert!(l.is_coalescable(2));
434        assert!(l.is_multi(2));
435    }
436
437    #[test]
438    #[allow(clippy::cognitive_complexity)] // extensive checks, and it doesn't matter for tests
439    fn alloc_split() {
440        let (_guard, mut l, _, last_unit, _) = new_raw_memory_freelist(6, 2);
441        let result = l.alloc(1);
442        assert_eq!(result, 0);
443
444        const NEXT: i32 = 1;
445        assert_eq!(l.get_prev(TOP_SENTINEL), last_unit);
446        assert_eq!(l.get_next(TOP_SENTINEL), NEXT);
447
448        assert_eq!(l.get_size(FIRST_UNIT), 1);
449        assert_eq!(l.get_left(FIRST_UNIT), -1);
450        assert_eq!(l.get_prev(FIRST_UNIT), 1); // prev is 1 now
451        assert_eq!(l.get_right(FIRST_UNIT), 1); // right is 1 now
452        assert_eq!(l.get_next(FIRST_UNIT), 2);
453        assert!(!l.is_free(FIRST_UNIT)); // not free
454        assert!(l.is_coalescable(FIRST_UNIT));
455        assert!(!l.is_multi(FIRST_UNIT)); // not multi
456
457        assert_eq!(l.get_size(1), 1);
458        assert_eq!(l.get_left(1), 0); // unit1's left is 0
459        assert_eq!(l.get_prev(1), -1); // unit1's prev is -1 (no prev, unit1 is removed form the list)
460        assert_eq!(l.get_right(1), 2);
461        assert_eq!(l.get_next(1), 2);
462        assert!(l.is_free(1)); // not free
463        assert!(l.is_coalescable(1));
464        assert!(!l.is_multi(1)); // not multi
465
466        assert_eq!(l.get_size(2), 2);
467        assert_eq!(l.get_left(2), 1);
468        assert_eq!(l.get_prev(2), 1); // uni2's prev is 1 now
469        assert_eq!(l.get_right(2), 4);
470        assert_eq!(l.get_next(2), 4);
471        assert!(l.is_free(2));
472        assert!(l.is_coalescable(2));
473        assert!(l.is_multi(2));
474    }
475
476    #[test]
477    fn alloc_split_twice() {
478        let (_guard, mut l, _, _, _) = new_raw_memory_freelist(6, 2);
479        // Alloc size 1 and cause split
480        let res1 = l.alloc(1);
481        assert_eq!(res1, 0);
482        // Alloc size 1
483        let res2 = l.alloc(1);
484        assert_eq!(res2, 1);
485
486        // Next available unit has no prev now
487        assert_eq!(l.get_prev(2), -1);
488    }
489
490    #[test]
491    fn alloc_skip() {
492        let (_guard, mut l, _, _, _) = new_raw_memory_freelist(6, 2);
493        // Alloc size 1 and cause split
494        let res1 = l.alloc(1);
495        assert_eq!(res1, 0);
496        // Alloc size 2, we skip unit1
497        let res2 = l.alloc(2);
498        assert_eq!(res2, 2);
499
500        // unit1 is still free, and linked with unit4
501        assert!(l.is_free(1));
502        assert_eq!(l.get_next(1), 4);
503        assert_eq!(l.get_prev(4), 1);
504    }
505
506    #[test]
507    fn alloc_exhaust() {
508        let (_guard, mut l, _, _, _) = new_raw_memory_freelist(6, 2);
509        let res1 = l.alloc(2);
510        assert_eq!(res1, 0);
511        let res2 = l.alloc(2);
512        assert_eq!(res2, 2);
513        let res3 = l.alloc(2);
514        assert_eq!(res3, 4);
515        let res4 = l.alloc(2);
516        assert_eq!(res4, FAILURE);
517    }
518
519    #[test]
520    fn free_unit() {
521        let (_guard, mut l, _, _, _) = new_raw_memory_freelist(6, 2);
522        let res1 = l.alloc(2);
523        assert_eq!(res1, 0);
524        let res2 = l.alloc(2);
525        assert_eq!(res2, 2);
526
527        // Unit4 is still free, but has no prev
528        assert_eq!(l.get_prev(4), -1);
529
530        // Free Unit2
531        let freed = l.free(res2, false);
532        assert_eq!(freed, res2);
533        assert!(l.is_free(res2));
534    }
535
536    #[test]
537    fn free_coalesce() {
538        let (_guard, mut l, _, _, _) = new_raw_memory_freelist(6, 2);
539        let res1 = l.alloc(2);
540        assert_eq!(res1, 0);
541        let res2 = l.alloc(2);
542        assert_eq!(res2, 2);
543
544        // Free Unit2. It will coalesce with Unit4
545        let coalesced_size = l.free(res2, true);
546        assert_eq!(coalesced_size, 4);
547    }
548
549    #[test]
550    fn free_cant_coalesce() {
551        let (_guard, mut l, _, _, _) = new_raw_memory_freelist(6, 2);
552        let res1 = l.alloc(2);
553        assert_eq!(res1, 0);
554        let res2 = l.alloc(2);
555        assert_eq!(res2, 2);
556        let res3 = l.alloc(1);
557        assert_eq!(res3, 4);
558
559        // Free Unit2. It cannot coalesce with Unit4
560        let coalesced_size = l.free(res2, true);
561        assert_eq!(coalesced_size, 2);
562    }
563
564    #[test]
565    fn free_realloc() {
566        let (_guard, mut l, _, _, _) = new_raw_memory_freelist(6, 2);
567        let res1 = l.alloc(2);
568        assert_eq!(res1, 0);
569        let res2 = l.alloc(2);
570        assert_eq!(res2, 2);
571
572        // Unit4 is still free, but has no prev
573        assert_eq!(l.get_prev(4), -1);
574
575        // Free Unit2
576        let freed = l.free(res2, false);
577        assert_eq!(freed, res2);
578        assert!(l.is_free(res2));
579
580        // Alloc again
581        let res3 = l.alloc(2);
582        assert_eq!(res3, 2);
583        assert!(!l.is_free(res3));
584
585        let res4 = l.alloc(1);
586        assert_eq!(res4, 4);
587    }
588}
mmtk/util/raw_memory_freelist.rs

mmtk/util/
raw_memory_freelist.rs
