mmtk/util/
int_array_freelist.rs

1use super::freelist::*;
2use std::ptr::NonNull;
3
4#[derive(Debug)]
5pub struct IntArrayFreeList {
6    pub head: i32,
7    pub heads: i32,
8    pub table: Option<Vec<i32>>,
9    parent: Option<NonNull<IntArrayFreeList>>,
10}
11
12unsafe impl Send for IntArrayFreeList {}
13unsafe impl Sync for IntArrayFreeList {}
14
15impl FreeList for IntArrayFreeList {
16    fn head(&self) -> i32 {
17        self.head
18    }
19    fn heads(&self) -> i32 {
20        self.heads
21    }
22    fn get_entry(&self, index: i32) -> i32 {
23        self.table()[index as usize]
24    }
25    fn set_entry(&mut self, index: i32, value: i32) {
26        self.table_mut()[index as usize] = value;
27    }
28}
29
30impl IntArrayFreeList {
31    pub fn new(units: usize, grain: i32, heads: usize) -> Self {
32        debug_assert!(units <= MAX_UNITS as usize && heads <= MAX_HEADS as usize);
33        // allocate the data structure, including space for top & bottom sentinels
34        let len = (units + 1 + heads) << 1;
35        let mut iafl = IntArrayFreeList {
36            head: -1,
37            heads: heads as _,
38            table: Some(vec![0; len]), // len=2052
39            parent: None,
40        };
41        iafl.initialize_heap(units as _, grain);
42        iafl
43    }
44    pub fn from_parent(parent: &IntArrayFreeList, ordinal: i32) -> Self {
45        let parent_ptr = std::ptr::NonNull::from(parent);
46        let iafl = IntArrayFreeList {
47            head: -(1 + ordinal),
48            heads: parent.heads,
49            table: None,
50            parent: Some(parent_ptr),
51        };
52        debug_assert!(-iafl.head <= iafl.heads);
53        iafl
54    }
55    pub(crate) fn get_ordinal(&self) -> i32 {
56        -self.head - 1
57    }
58    fn table(&self) -> &Vec<i32> {
59        match self.parent {
60            Some(p) => unsafe { p.as_ref().table() },
61            None => self.table.as_ref().unwrap(),
62        }
63    }
64
65    // FIXME: We need a safe implementation
66
67    fn table_mut(&mut self) -> &mut Vec<i32> {
68        match self.parent {
69            Some(mut p) => unsafe { p.as_mut().table_mut() },
70            None => self.table.as_mut().unwrap(),
71        }
72    }
73    pub fn resize_freelist(&mut self, units: usize, grain: i32) {
74        // debug_assert!(self.parent.is_none() && !selected_plan::PLAN.is_initialized());
75        *self.table_mut() = vec![0; (units + 1 + self.heads as usize) << 1];
76        self.initialize_heap(units as _, grain);
77    }
78}
79
80#[cfg(test)]
81mod tests {
82    use super::FreeList;
83    use super::*;
84
85    const LIST_SIZE: usize = 5;
86    const TOP_SENTINEL: i32 = -1;
87    const FIRST_UNIT: i32 = 0;
88    const LAST_UNIT: i32 = LIST_SIZE as i32 - 1;
89    const BOTTOM_SENTINEL: i32 = LIST_SIZE as i32;
90
91    #[test]
92    #[allow(clippy::cognitive_complexity)] // extensive checks, and it doesn't matter for tests
93    fn new_free_list_grain1() {
94        let l = IntArrayFreeList::new(LIST_SIZE, 1, 1);
95        assert_eq!(l.head(), TOP_SENTINEL);
96
97        assert_eq!(l.get_prev(TOP_SENTINEL), LAST_UNIT);
98        assert_eq!(l.get_next(TOP_SENTINEL), FIRST_UNIT);
99
100        assert_eq!(l.get_size(FIRST_UNIT), 1);
101        assert_eq!(l.get_left(FIRST_UNIT), -1);
102        assert_eq!(l.get_prev(FIRST_UNIT), -1);
103        assert_eq!(l.get_right(FIRST_UNIT), 1);
104        assert_eq!(l.get_next(FIRST_UNIT), 1);
105        assert!(l.is_free(FIRST_UNIT));
106        assert!(l.is_coalescable(FIRST_UNIT));
107        assert!(!l.is_multi(FIRST_UNIT));
108
109        assert_eq!(l.get_size(1), 1);
110        assert_eq!(l.get_left(1), 0);
111        assert_eq!(l.get_prev(1), 0);
112        assert_eq!(l.get_right(1), 2);
113        assert_eq!(l.get_next(1), 2);
114        assert!(l.is_free(1));
115        assert!(l.is_coalescable(1));
116        assert!(!l.is_multi(1));
117
118        assert_eq!(l.get_size(LAST_UNIT), 1);
119        assert_eq!(l.get_left(LAST_UNIT), LAST_UNIT - 1);
120        assert_eq!(l.get_prev(LAST_UNIT), LAST_UNIT - 1);
121        assert_eq!(l.get_right(LAST_UNIT), BOTTOM_SENTINEL);
122        assert_eq!(l.get_next(LAST_UNIT), -1);
123        assert!(l.is_free(LAST_UNIT));
124        assert!(l.is_coalescable(LAST_UNIT));
125        assert!(!l.is_multi(LAST_UNIT));
126
127        assert_eq!(l.get_prev(BOTTOM_SENTINEL), BOTTOM_SENTINEL);
128        assert_eq!(l.get_next(BOTTOM_SENTINEL), BOTTOM_SENTINEL);
129    }
130
131    #[test]
132    #[allow(clippy::cognitive_complexity)] // extensive checks, and it doesn't matter for tests
133    fn new_free_list_grain2() {
134        let l = IntArrayFreeList::new(LIST_SIZE, 2, 1);
135        assert_eq!(l.head(), TOP_SENTINEL);
136
137        assert_eq!(l.get_prev(TOP_SENTINEL), LAST_UNIT);
138        assert_eq!(l.get_next(TOP_SENTINEL), FIRST_UNIT);
139
140        assert_eq!(l.get_size(FIRST_UNIT), 2);
141        assert_eq!(l.get_left(FIRST_UNIT), -1);
142        assert_eq!(l.get_prev(FIRST_UNIT), -1);
143        assert_eq!(l.get_right(FIRST_UNIT), 2);
144        assert_eq!(l.get_next(FIRST_UNIT), 2);
145        assert!(l.is_free(FIRST_UNIT));
146        assert!(l.is_coalescable(FIRST_UNIT));
147        assert!(l.is_multi(FIRST_UNIT));
148
149        assert_eq!(l.get_size(2), 2);
150        assert_eq!(l.get_left(2), 0);
151        assert_eq!(l.get_prev(2), 0);
152        assert_eq!(l.get_right(2), 4);
153        assert_eq!(l.get_next(2), 4);
154        assert!(l.is_free(2));
155        assert!(l.is_coalescable(2));
156        assert!(l.is_multi(2));
157
158        assert_eq!(l.get_size(LAST_UNIT), 1);
159        assert_eq!(l.get_left(LAST_UNIT), LAST_UNIT - 2);
160        assert_eq!(l.get_prev(LAST_UNIT), LAST_UNIT - 2);
161        assert_eq!(l.get_right(LAST_UNIT), BOTTOM_SENTINEL);
162        assert_eq!(l.get_next(LAST_UNIT), -1);
163        assert!(l.is_free(LAST_UNIT));
164        assert!(l.is_coalescable(LAST_UNIT));
165        assert!(!l.is_multi(LAST_UNIT));
166
167        assert_eq!(l.get_prev(BOTTOM_SENTINEL), BOTTOM_SENTINEL);
168        assert_eq!(l.get_next(BOTTOM_SENTINEL), BOTTOM_SENTINEL);
169    }
170
171    #[test]
172    #[should_panic]
173    fn free_list_access_out_of_bounds() {
174        let l = IntArrayFreeList::new(LIST_SIZE, 1, 1);
175        l.get_size((LIST_SIZE + 1) as i32);
176    }
177
178    #[test]
179    fn alloc_fit() {
180        let mut l = IntArrayFreeList::new(LIST_SIZE, 2, 1);
181        let result = l.alloc(2);
182        assert_eq!(result, 0);
183
184        const NEXT: i32 = 2;
185
186        assert_eq!(l.get_prev(TOP_SENTINEL), LAST_UNIT);
187        assert_eq!(l.get_next(TOP_SENTINEL), NEXT);
188
189        assert_eq!(l.get_size(FIRST_UNIT), 2);
190        assert_eq!(l.get_left(FIRST_UNIT), -1);
191        assert_eq!(l.get_prev(FIRST_UNIT), -1);
192        assert_eq!(l.get_right(FIRST_UNIT), 2);
193        assert_eq!(l.get_next(FIRST_UNIT), 2);
194        assert!(!l.is_free(FIRST_UNIT)); // not free
195        assert!(l.is_coalescable(FIRST_UNIT));
196        assert!(l.is_multi(FIRST_UNIT));
197
198        assert_eq!(l.get_size(2), 2);
199        assert_eq!(l.get_left(2), 0);
200        assert_eq!(l.get_prev(2), -1); // no prev now
201        assert_eq!(l.get_right(2), 4);
202        assert_eq!(l.get_next(2), 4);
203        assert!(l.is_free(2));
204        assert!(l.is_coalescable(2));
205        assert!(l.is_multi(2));
206    }
207
208    #[test]
209    #[allow(clippy::cognitive_complexity)] // extensive checks, and it doesn't matter for tests
210    fn alloc_split() {
211        let mut l = IntArrayFreeList::new(LIST_SIZE, 2, 1);
212        let result = l.alloc(1);
213        assert_eq!(result, 0);
214
215        const NEXT: i32 = 1;
216        assert_eq!(l.get_prev(TOP_SENTINEL), LAST_UNIT);
217        assert_eq!(l.get_next(TOP_SENTINEL), NEXT);
218
219        assert_eq!(l.get_size(FIRST_UNIT), 1);
220        assert_eq!(l.get_left(FIRST_UNIT), -1);
221        assert_eq!(l.get_prev(FIRST_UNIT), 1); // prev is 1 now
222        assert_eq!(l.get_right(FIRST_UNIT), 1); // right is 1 now
223        assert_eq!(l.get_next(FIRST_UNIT), 2);
224        assert!(!l.is_free(FIRST_UNIT)); // not free
225        assert!(l.is_coalescable(FIRST_UNIT));
226        assert!(!l.is_multi(FIRST_UNIT)); // not multi
227
228        assert_eq!(l.get_size(1), 1);
229        assert_eq!(l.get_left(1), 0); // unit1's left is 0
230        assert_eq!(l.get_prev(1), -1); // unit1's prev is -1 (no prev, unit1 is removed form the list)
231        assert_eq!(l.get_right(1), 2);
232        assert_eq!(l.get_next(1), 2);
233        assert!(l.is_free(1)); // not free
234        assert!(l.is_coalescable(1));
235        assert!(!l.is_multi(1)); // not multi
236
237        assert_eq!(l.get_size(2), 2);
238        assert_eq!(l.get_left(2), 1);
239        assert_eq!(l.get_prev(2), 1); // uni2's prev is 1 now
240        assert_eq!(l.get_right(2), 4);
241        assert_eq!(l.get_next(2), 4);
242        assert!(l.is_free(2));
243        assert!(l.is_coalescable(2));
244        assert!(l.is_multi(2));
245    }
246
247    #[test]
248    fn alloc_split_twice() {
249        let mut l = IntArrayFreeList::new(LIST_SIZE, 2, 1);
250        // Alloc size 1 and cause split
251        let res1 = l.alloc(1);
252        assert_eq!(res1, 0);
253        // Alloc size 1
254        let res2 = l.alloc(1);
255        assert_eq!(res2, 1);
256
257        // Next available unit has no prev now
258        assert_eq!(l.get_prev(2), -1);
259    }
260
261    #[test]
262    fn alloc_skip() {
263        let mut l = IntArrayFreeList::new(LIST_SIZE, 2, 1);
264        // Alloc size 1 and cause split
265        let res1 = l.alloc(1);
266        assert_eq!(res1, 0);
267        // Alloc size 2, we skip unit1
268        let res2 = l.alloc(2);
269        assert_eq!(res2, 2);
270
271        // unit1 is still free, and linked with unit4
272        assert!(l.is_free(1));
273        assert_eq!(l.get_next(1), 4);
274        assert_eq!(l.get_prev(4), 1);
275    }
276
277    #[test]
278    fn alloc_exhaust() {
279        let mut l = IntArrayFreeList::new(LIST_SIZE, 2, 1);
280        let res1 = l.alloc(2);
281        assert_eq!(res1, 0);
282        let res2 = l.alloc(2);
283        assert_eq!(res2, 2);
284        let res3 = l.alloc(2);
285        assert_eq!(res3, FAILURE);
286    }
287
288    #[test]
289    fn free_unit() {
290        let mut l = IntArrayFreeList::new(LIST_SIZE, 2, 1);
291        let res1 = l.alloc(2);
292        assert_eq!(res1, 0);
293        let res2 = l.alloc(2);
294        assert_eq!(res2, 2);
295
296        // Unit4 is still free, but has no prev
297        assert_eq!(l.get_prev(4), -1);
298
299        // Free Unit2
300        let freed = l.free(res2, false);
301        assert_eq!(freed, res2);
302        assert!(l.is_free(res2));
303    }
304
305    #[test]
306    fn free_coalesce() {
307        let mut l = IntArrayFreeList::new(LIST_SIZE, 2, 1);
308        let res1 = l.alloc(2);
309        assert_eq!(res1, 0);
310        let res2 = l.alloc(2);
311        assert_eq!(res2, 2);
312
313        // Free Unit2. It will coalesce with Unit4
314        let coalesced_size = l.free(res2, true);
315        assert_eq!(coalesced_size, 3);
316    }
317
318    #[test]
319    fn free_cant_coalesce() {
320        let mut l = IntArrayFreeList::new(LIST_SIZE, 2, 1);
321        let res1 = l.alloc(2);
322        assert_eq!(res1, 0);
323        let res2 = l.alloc(2);
324        assert_eq!(res2, 2);
325        let res3 = l.alloc(1);
326        assert_eq!(res3, 4);
327
328        // Free Unit2. It cannot coalesce with Unit4
329        let coalesced_size = l.free(res2, true);
330        assert_eq!(coalesced_size, 2);
331    }
332
333    #[test]
334    fn free_realloc() {
335        let mut l = IntArrayFreeList::new(LIST_SIZE, 2, 1);
336        let res1 = l.alloc(2);
337        assert_eq!(res1, 0);
338        let res2 = l.alloc(2);
339        assert_eq!(res2, 2);
340
341        // Unit4 is still free, but has no prev
342        assert_eq!(l.get_prev(4), -1);
343
344        // Free Unit2
345        let freed = l.free(res2, false);
346        assert_eq!(freed, res2);
347        assert!(l.is_free(res2));
348
349        // Alloc again
350        let res3 = l.alloc(2);
351        assert_eq!(res3, 2);
352        assert!(!l.is_free(res3));
353
354        let res4 = l.alloc(1);
355        assert_eq!(res4, 4);
356    }
357
358    #[test]
359    fn multi_heads_alloc_free() {
360        let parent = IntArrayFreeList::new(LIST_SIZE, 1, 2);
361        let mut child1 = IntArrayFreeList::from_parent(&parent, 0);
362        let child2 = IntArrayFreeList::from_parent(&parent, 1);
363
364        // child1 alloc
365        let res = child1.alloc(1);
366        assert_eq!(res, 0);
367        assert!(!parent.is_free(0));
368        assert!(!child1.is_free(0));
369        assert!(!child2.is_free(0));
370
371        // child1 free
372        child1.free(0, false);
373        assert!(parent.is_free(0));
374        assert!(child1.is_free(0));
375        assert!(child2.is_free(0));
376    }
377
378    #[test]
379    #[should_panic]
380    fn multi_heads_exceed_heads() {
381        let parent = IntArrayFreeList::new(LIST_SIZE, 1, 2);
382        let _child1 = IntArrayFreeList::from_parent(&parent, 0);
383        let _child2 = IntArrayFreeList::from_parent(&parent, 1);
384        let _child3 = IntArrayFreeList::from_parent(&parent, 2);
385    }
386}
mmtk/util/int_array_freelist.rs

mmtk/util/
int_array_freelist.rs
