mmtk/util/
freelist.rs

1use downcast_rs::{impl_downcast, Downcast};
2
3pub const FAILURE: i32 = -1;
4
5pub const MAX_HEADS: i32 = 128; // somewhat arbitrary
6const TOTAL_BITS: i32 = 32;
7const UNIT_BITS: i32 = TOTAL_BITS - 2;
8pub const MAX_UNITS: i32 = ((1 << UNIT_BITS) - 1) - MAX_HEADS - 1;
9
10const NEXT_MASK: i32 = (1 << UNIT_BITS) - 1;
11const PREV_MASK: i32 = (1 << UNIT_BITS) - 1;
12const FREE_MASK: i32 = 1 << (TOTAL_BITS - 1);
13const MULTI_MASK: i32 = 1 << (TOTAL_BITS - 1);
14const COALESC_MASK: i32 = 1 << (TOTAL_BITS - 2);
15const SIZE_MASK: i32 = (1 << UNIT_BITS) - 1;
16
17pub trait FreeList: Sync + Downcast {
18    fn head(&self) -> i32;
19    // fn head_mut(&mut self) -> &mut i32;
20    fn heads(&self) -> i32;
21    // fn heads_mut(&mut self) -> &mut i32;
22    // fn resize_freelist(&mut self);
23    // fn resize_freelist(&mut self, units: i32, heads: i32);
24    fn get_entry(&self, index: i32) -> i32;
25    fn set_entry(&mut self, index: i32, value: i32);
26
27    fn alloc(&mut self, size: i32) -> i32 {
28        let mut unit = self.head();
29        let mut s = 0;
30        while ({
31            unit = self.get_next(unit);
32            unit != self.head()
33        }) && ({
34            s = self.get_size(unit);
35            s < size
36        }) {}
37        // loop {
38        //   unit = self.get_next(unit);
39        //   // println!("Current unit={}", unit);
40        //   if unit != self.head() {
41        //     break;
42        //   }
43        //   s = self.get_size(unit);
44        //   if s < size {
45        //     break;
46        //   }
47        // }
48        if unit == self.head() {
49            FAILURE
50        } else {
51            self.__alloc(size, unit, s)
52        }
53    }
54
55    fn alloc_from_unit(&mut self, size: i32, unit: i32) -> i32 {
56        if self.get_free(unit) {
57            let s = self.get_size(unit);
58            if s >= size {
59                return self.__alloc(size, unit, s);
60            }
61        }
62        FAILURE
63    }
64
65    /// Free a previously allocated contiguous lump of units
66    fn free(&mut self, unit: i32, return_coalesced_size: bool) -> i32 {
67        debug_assert!(!self.get_free(unit));
68        let mut freed = self.get_size(unit);
69        let left = self.get_left(unit);
70        let start = if self.is_coalescable(unit) && self.get_free(left) {
71            left
72        } else {
73            unit
74        };
75        let right = self.get_right(unit);
76        let end = if self.is_coalescable(right) && self.get_free(right) {
77            right
78        } else {
79            unit
80        };
81        if start != end {
82            self.__coalesce(start, end);
83        }
84
85        if return_coalesced_size {
86            freed = self.get_size(start);
87        }
88        self.add_to_free(start);
89
90        freed
91    }
92
93    fn size(&self, unit: i32) -> i32 {
94        self.get_size(unit)
95    }
96
97    fn initialize_heap(&mut self, units: i32, grain: i32) {
98        // Initialize the sentinels
99        // Set top sentinels per heads
100        for i in 1..=self.heads() {
101            self.set_sentinel(-i);
102        }
103        // Set bottom sentinel
104        self.set_sentinel(units);
105
106        // create the free list item
107        let offset = units % grain;
108        let mut cursor = units - offset;
109        if offset > 0 {
110            self.set_size(cursor, offset);
111            self.add_to_free(cursor);
112        }
113        cursor -= grain;
114        while cursor >= 0 {
115            self.set_size(cursor, grain);
116            self.add_to_free(cursor);
117            cursor -= grain;
118        }
119    }
120
121    fn add_to_free(&mut self, unit: i32) {
122        self.set_free(unit, true);
123        let next = self.get_next(self.head());
124        self.set_next(unit, next);
125        let head = self.head();
126        self.set_next(head, unit);
127        let head = self.head();
128        self.set_prev(unit, head);
129        self.set_prev(next, unit);
130    }
131
132    fn get_right(&self, unit: i32) -> i32 {
133        unit + self.get_size(unit)
134    }
135
136    fn set_sentinel(&mut self, unit: i32) {
137        self.set_lo_entry(unit, NEXT_MASK & unit);
138        self.set_hi_entry(unit, PREV_MASK & unit);
139    }
140
141    fn get_size(&self, unit: i32) -> i32 {
142        if (self.get_hi_entry(unit) & MULTI_MASK) == MULTI_MASK {
143            self.get_hi_entry(unit + 1) & SIZE_MASK
144        } else {
145            1
146        }
147    }
148
149    fn set_size(&mut self, unit: i32, size: i32) {
150        let hi = self.get_hi_entry(unit);
151        if size > 1 {
152            self.set_hi_entry(unit, hi | MULTI_MASK);
153            self.set_hi_entry(unit + 1, MULTI_MASK | size);
154            self.set_hi_entry(unit + size - 1, MULTI_MASK | size);
155        } else {
156            self.set_hi_entry(unit, hi & !MULTI_MASK);
157        }
158    }
159
160    fn get_free(&self, unit: i32) -> bool {
161        (self.get_lo_entry(unit) & FREE_MASK) == FREE_MASK
162    }
163
164    fn set_free(&mut self, unit: i32, is_free: bool) {
165        let size;
166        let lo = self.get_lo_entry(unit);
167        if is_free {
168            self.set_lo_entry(unit, lo | FREE_MASK);
169            size = self.get_size(unit);
170            if size > 1 {
171                let lo = self.get_lo_entry(unit + size - 1);
172                self.set_lo_entry(unit + size - 1, lo | FREE_MASK);
173            }
174        } else {
175            self.set_lo_entry(unit, lo & !FREE_MASK);
176            size = self.get_size(unit);
177            if size > 1 {
178                let lo = self.get_lo_entry(unit + size - 1);
179                self.set_lo_entry(unit + size - 1, lo & !FREE_MASK);
180            }
181        }
182    }
183
184    fn get_next(&self, unit: i32) -> i32 {
185        let next = self.get_hi_entry(unit) & NEXT_MASK;
186        if next <= MAX_UNITS {
187            next
188        } else {
189            self.head()
190        }
191    }
192
193    fn set_next(&mut self, unit: i32, next: i32) {
194        debug_assert!((next >= -self.heads()) && (next <= MAX_UNITS));
195        let old_value = self.get_hi_entry(unit);
196        let new_value = (old_value & !NEXT_MASK) | (next & NEXT_MASK);
197        self.set_hi_entry(unit, new_value);
198    }
199
200    // Return the previous link. If no previous link, return head
201    fn get_prev(&self, unit: i32) -> i32 {
202        let prev = self.get_lo_entry(unit) & PREV_MASK;
203        if prev <= MAX_UNITS {
204            prev
205        } else {
206            self.head()
207        }
208    }
209
210    fn set_prev(&mut self, unit: i32, prev: i32) {
211        debug_assert!((prev >= -self.heads()) && (prev <= MAX_UNITS));
212        let old_value = self.get_lo_entry(unit);
213        let new_value = (old_value & !PREV_MASK) | (prev & PREV_MASK);
214        self.set_lo_entry(unit, new_value);
215    }
216
217    // Return the left unit. If it is a multi unit, return the start of the unit.
218    fn get_left(&self, unit: i32) -> i32 {
219        if (self.get_hi_entry(unit - 1) & MULTI_MASK) == MULTI_MASK {
220            unit - (self.get_hi_entry(unit - 1) & SIZE_MASK)
221        } else {
222            unit - 1
223        }
224    }
225
226    fn is_coalescable(&self, unit: i32) -> bool {
227        (self.get_lo_entry(unit) & COALESC_MASK) == 0
228    }
229
230    fn clear_uncoalescable(&mut self, unit: i32) {
231        let lo = self.get_lo_entry(unit);
232        self.set_lo_entry(unit, lo & !COALESC_MASK);
233    }
234
235    fn set_uncoalescable(&mut self, unit: i32) {
236        let lo = self.get_lo_entry(unit);
237        self.set_lo_entry(unit, lo | COALESC_MASK);
238    }
239
240    fn is_multi(&self, i: i32) -> bool {
241        let hi = self.get_hi_entry(i);
242        (hi & MULTI_MASK) == MULTI_MASK
243    }
244
245    fn is_free(&self, i: i32) -> bool {
246        let lo = self.get_lo_entry(i);
247        (lo & FREE_MASK) == FREE_MASK
248    }
249
250    fn get_lo_entry(&self, unit: i32) -> i32 {
251        self.get_entry((unit + self.heads()) << 1)
252    }
253
254    fn get_hi_entry(&self, unit: i32) -> i32 {
255        self.get_entry(((unit + self.heads()) << 1) + 1)
256    }
257
258    fn set_lo_entry(&mut self, unit: i32, value: i32) {
259        let heads = self.heads();
260        self.set_entry((unit + heads) << 1, value);
261    }
262
263    fn set_hi_entry(&mut self, unit: i32, value: i32) {
264        let heads = self.heads();
265        self.set_entry(((unit + heads) << 1) + 1, value);
266    }
267
268    // Private methods
269
270    fn __alloc(&mut self, size: i32, unit: i32, unit_size: i32) -> i32 {
271        if unit_size >= size {
272            if unit_size > size {
273                self.__split(unit, size);
274            }
275            self.__remove_from_free(unit);
276            self.set_free(unit, false);
277        }
278        unit
279    }
280
281    fn __split(&mut self, unit: i32, size: i32) {
282        let basesize = self.get_size(unit);
283        debug_assert!(basesize > size);
284        self.set_size(unit, size);
285        self.set_size(unit + size, basesize - size);
286        self.add_to_free(unit + size);
287    }
288
289    fn __coalesce(&mut self, start: i32, end: i32) {
290        if self.get_free(end) {
291            self.__remove_from_free(end);
292        }
293        if self.get_free(start) {
294            self.__remove_from_free(start);
295        }
296        let size = self.get_size(end);
297        self.set_size(start, end - start + size);
298    }
299
300    fn __remove_from_free(&mut self, unit: i32) {
301        let next = self.get_next(unit);
302        let prev = self.get_prev(unit);
303        self.set_next(prev, next);
304        self.set_prev(next, prev);
305    }
306}
307
308impl_downcast!(FreeList);
mmtk/util/freelist.rs

mmtk/util/
freelist.rs
