managed_heap/
managed.rs

1use super::address::Address;
2use super::heap::Heap;
3use super::trace::{GcRoot, Traceable};
4use super::types::HalfWord;
5
6/// A virtual Heap which can be garbage collected by calling gc().
7pub struct ManagedHeap {
8    heap: Heap,
9}
10
11impl ManagedHeap {
12    /// Expects the heap size in bytes.
13    pub fn new(size: usize) -> Self {
14        let heap = unsafe { Heap::new(size) };
15
16        ManagedHeap { heap }
17    }
18}
19
20impl ManagedHeap {
21    pub fn num_used_blocks(&self) -> usize {
22        self.heap.num_used_blocks()
23    }
24
25    pub fn num_free_blocks(&self) -> usize {
26        self.heap.num_free_blocks()
27    }
28
29    pub fn total_size(&self) -> usize {
30        self.heap.size()
31    }
32
33    pub fn used_size(&self) -> usize {
34        self.heap.used_size()
35    }
36}
37
38impl ManagedHeap {
39    /// Takes the blocksize as a number of usize values.
40    /// The size in bytes of the block is therefore size * mem::size_of::<usize>()
41    /// (technically + one more usize to store information about the block)
42    pub fn alloc(&mut self, size: HalfWord) -> Option<Address> {
43        self.heap.alloc(size)
44    }
45
46    /// Run the mark & sweep garbage collector.
47    /// roots should return an iterator over all objects still in use.
48    /// If an object is neither returned by one of the roots, nor from another
49    /// object in the root.children(), it gets automatically freed.
50    pub fn gc<T>(&mut self, roots: &mut [&mut GcRoot<T>])
51    where
52        T: Traceable + From<Address> + Into<Address>,
53    {
54        for traceable in roots.iter_mut().flat_map(|r| r.children()) {
55            traceable.mark();
56        }
57
58        let freeable: Vec<Address> = self
59            .heap
60            .used()
61            .map(|b| T::from(Address::from(*b)))
62            .filter(|t| !t.is_marked())
63            .map(|t| t.into())
64            .collect();
65
66        for a in freeable {
67            self.heap.free(a);
68        }
69
70        self.heap
71            .used()
72            .map(|b| Address::from(*b))
73            .map(T::from)
74            .for_each(|mut t| t.unmark());
75    }
76}
77
78#[cfg(test)]
79mod tests {
80    use super::*;
81
82    mod simple {
83        use super::*;
84        use std::ops::Add;
85
86        struct MockGcRoot {
87            used_elems: Vec<IntegerObject>,
88        }
89
90        impl MockGcRoot {
91            pub fn new(used_elems: Vec<IntegerObject>) -> Self {
92                MockGcRoot { used_elems }
93            }
94
95            pub fn clear(&mut self) {
96                self.used_elems.clear();
97            }
98        }
99
100        unsafe impl GcRoot<IntegerObject> for MockGcRoot {
101            fn children<'a>(&'a mut self) -> Box<Iterator<Item = &'a mut IntegerObject> + 'a> {
102                Box::new(self.used_elems.iter_mut())
103            }
104        }
105
106        #[derive(Debug)]
107        struct IntegerObject(Address);
108
109        impl IntegerObject {
110            pub fn new(heap: &mut ManagedHeap, value: isize) -> Self {
111                // reserve one usize for mark byte
112                let mut address = heap.alloc(2).unwrap();
113
114                address.write(false as usize);
115                address.add(1).write(value as usize);
116
117                IntegerObject(address)
118            }
119
120            pub fn get(&self) -> isize {
121                *self.0.add(1) as isize
122            }
123        }
124
125        impl From<Address> for IntegerObject {
126            fn from(address: Address) -> Self {
127                IntegerObject(address)
128            }
129        }
130
131        impl Into<Address> for IntegerObject {
132            fn into(self) -> Address {
133                self.0
134            }
135        }
136
137        unsafe impl Traceable for IntegerObject {
138            fn mark(&mut self) {
139                self.0.write(true as usize);
140            }
141
142            fn unmark(&mut self) {
143                self.0.write(false as usize);
144            }
145
146            fn is_marked(&self) -> bool {
147                (*self.0) != 0
148            }
149        }
150
151        #[test]
152        fn test_integer_object_constructor() {
153            let mut heap = ManagedHeap::new(100);
154            let mut i = IntegerObject::new(&mut heap, -42);
155
156            assert_eq!(-42, i.get());
157            assert_eq!(false, i.is_marked());
158
159            i.mark();
160            assert_eq!(true, i.is_marked());
161        }
162
163        #[test]
164        fn test_integer_gets_freed_when_not_marked() {
165            let mut heap = ManagedHeap::new(100);
166            let i = IntegerObject::new(&mut heap, 42);
167
168            let mut gc_root = MockGcRoot::new(vec![i]);
169            assert_eq!(1, heap.num_used_blocks());
170            assert_eq!(1, heap.num_free_blocks());
171
172            {
173                let mut roots: Vec<&mut GcRoot<IntegerObject>> = vec![&mut gc_root];
174                heap.gc(&mut roots[..]);
175                assert_eq!(1, heap.num_used_blocks());
176                assert_eq!(1, heap.num_free_blocks());
177            }
178
179            {
180                let mut roots: Vec<&mut GcRoot<IntegerObject>> = vec![&mut gc_root];
181                heap.gc(&mut roots[..]);
182                assert_eq!(1, heap.num_used_blocks());
183                assert_eq!(1, heap.num_free_blocks());
184            }
185
186            gc_root.clear();
187            let mut roots: Vec<&mut GcRoot<IntegerObject>> = vec![&mut gc_root];
188            heap.gc(&mut roots[..]);
189            assert_eq!(0, heap.num_used_blocks());
190            assert_eq!(1, heap.num_free_blocks());
191        }
192    }
193
194    mod complex {
195        use super::*;
196        use std::fmt;
197        use std::iter::Iterator;
198        use std::ops::Add;
199
200        struct MockGcRoot {
201            used_elems: Vec<LinkedList>,
202        }
203
204        impl MockGcRoot {
205            pub fn new(used_elems: Vec<LinkedList>) -> Self {
206                MockGcRoot { used_elems }
207            }
208
209            pub fn clear(&mut self) {
210                self.used_elems.clear();
211            }
212        }
213
214        unsafe impl GcRoot<LinkedList> for MockGcRoot {
215            fn children<'a>(&'a mut self) -> Box<Iterator<Item = &'a mut LinkedList> + 'a> {
216                Box::new(self.used_elems.iter_mut())
217            }
218        }
219
220        #[derive(Copy, Clone)]
221        struct LinkedList(Address);
222
223        impl LinkedList {
224            pub fn new(heap: &mut ManagedHeap, value: isize, next: Option<LinkedList>) -> Self {
225                // [mark byte, value, next], each 1 byte
226                let mut address = heap.alloc(3).unwrap();
227
228                address.write(false as usize);
229                address.add(1).write(value as usize);
230
231                let next = next.map(|n| n.0.into()).unwrap_or(0);
232                address.add(2).write(next);
233
234                LinkedList(address)
235            }
236
237            pub fn next(self) -> Option<LinkedList> {
238                let next = *self.0.add(2);
239
240                if next != 0 {
241                    let address = Address::from(next);
242                    Some(LinkedList(address))
243                } else {
244                    None
245                }
246            }
247
248            pub fn value(self) -> isize {
249                *self.0.add(1) as isize
250            }
251
252            pub fn iter(self) -> Iter {
253                Iter {
254                    current: Some(self),
255                }
256            }
257        }
258
259        impl From<Address> for LinkedList {
260            fn from(address: Address) -> Self {
261                LinkedList(address)
262            }
263        }
264
265        impl Into<Address> for LinkedList {
266            fn into(self) -> Address {
267                self.0
268            }
269        }
270
271        unsafe impl Traceable for LinkedList {
272            fn mark(&mut self) {
273                self.0.write(true as usize);
274                if let Some(mut next) = self.next() {
275                    next.mark();
276                }
277            }
278
279            fn unmark(&mut self) {
280                self.0.write(false as usize);
281            }
282
283            fn is_marked(&self) -> bool {
284                (*self.0) != 0
285            }
286        }
287
288        impl fmt::Debug for LinkedList {
289            fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
290                let string_list: Vec<String> = self
291                    .iter()
292                    .map(|l| l.value())
293                    .map(|v| format!("{}", v))
294                    .collect();
295
296                write!(f, "[{}]", string_list.join(", "))
297            }
298        }
299
300        struct Iter {
301            current: Option<LinkedList>,
302        }
303
304        impl Iterator for Iter {
305            type Item = LinkedList;
306
307            fn next(&mut self) -> Option<LinkedList> {
308                let curr = self.current;
309                self.current = self.current.and_then(|c| c.next());
310                curr
311            }
312        }
313
314        #[test]
315        fn test_linked_list_object_constructor() {
316            let mut heap = ManagedHeap::new(200);
317
318            let list = LinkedList::new(&mut heap, 3, None);
319            assert_eq!(1, heap.num_used_blocks());
320
321            let list = LinkedList::new(&mut heap, 2, Some(list));
322            assert_eq!(2, heap.num_used_blocks());
323
324            let list = LinkedList::new(&mut heap, 1, Some(list));
325            assert_eq!(3, heap.num_used_blocks());
326
327            let sum: isize = list.iter().map(|list| list.value()).sum();
328            assert_eq!(sum, 6);
329
330            assert_eq!(3, heap.num_used_blocks());
331            assert_eq!(1, heap.num_free_blocks());
332        }
333
334        macro_rules! list {
335            ($heap:expr; $($elems:tt)+) => {
336                construct_list!($heap; [$($elems)*])
337            };
338        }
339
340        macro_rules! construct_list {
341            ($heap:expr; [] $head:expr, $($elem:expr),*) => {
342                {
343                    let mut list = LinkedList::new($heap, $head, None);
344                    $(list = LinkedList::new($heap, $elem, Some(list));)*
345                    list
346                }
347            };
348            ($heap:expr; [$first:tt $($rest:tt)*] $($reversed:tt)*) => {
349                construct_list!($heap; [$($rest)*] $first $($reversed)*)
350            };
351        }
352
353        #[test]
354        fn test_single_linked_list_gets_freed_when_not_marked() {
355            let mut heap = ManagedHeap::new(100);
356            let list = LinkedList::new(&mut heap, 1, None);
357            assert_eq!("[1]", format!("{:?}", list));
358
359            let mut gc_root = MockGcRoot::new(vec![list]);
360            assert_eq!(1, heap.num_used_blocks());
361            assert_eq!(1, heap.num_free_blocks());
362
363            {
364                let mut roots: Vec<&mut GcRoot<LinkedList>> = vec![&mut gc_root];
365                heap.gc(&mut roots[..]);
366                assert_eq!(1, heap.num_used_blocks());
367                assert_eq!(1, heap.num_free_blocks());
368            }
369
370            {
371                let mut roots: Vec<&mut GcRoot<LinkedList>> = vec![&mut gc_root];
372                heap.gc(&mut roots[..]);
373                assert_eq!(1, heap.num_used_blocks());
374                assert_eq!(1, heap.num_free_blocks());
375            }
376
377            gc_root.clear();
378            let mut roots: Vec<&mut GcRoot<LinkedList>> = vec![&mut gc_root];
379            heap.gc(&mut roots[..]);
380            assert_eq!(0, heap.num_used_blocks());
381            assert_eq!(1, heap.num_free_blocks());
382        }
383
384        #[test]
385        fn test_double_linked_list_gets_freed_when_not_marked() {
386            let mut heap = ManagedHeap::new(100);
387            let list = list![&mut heap; 1, 2];
388            assert_eq!("[1, 2]", format!("{:?}", list));
389
390            let mut gc_root = MockGcRoot::new(vec![list]);
391            assert_eq!(2, heap.num_used_blocks());
392            assert_eq!(1, heap.num_free_blocks());
393
394            {
395                let mut roots: Vec<&mut GcRoot<LinkedList>> = vec![&mut gc_root];
396                heap.gc(&mut roots[..]);
397                assert_eq!(2, heap.num_used_blocks());
398                assert_eq!(1, heap.num_free_blocks());
399                assert_eq!(false, list.is_marked());
400            }
401
402            {
403                let mut roots: Vec<&mut GcRoot<LinkedList>> = vec![&mut gc_root];
404                heap.gc(&mut roots[..]);
405                assert_eq!(2, heap.num_used_blocks());
406                assert_eq!(1, heap.num_free_blocks());
407                assert_eq!(false, list.is_marked());
408            }
409
410            gc_root.clear();
411            let mut roots: Vec<&mut GcRoot<LinkedList>> = vec![&mut gc_root];
412            heap.gc(&mut roots[..]);
413            assert_eq!(0, heap.num_used_blocks());
414            assert_eq!(1, heap.num_free_blocks());
415        }
416
417        #[test]
418        fn test_triple_linked_list_gets_freed_when_not_marked() {
419            let mut heap = ManagedHeap::new(1000);
420            // Repeat a couple of times just to be sure
421            for _i in 0..20 {
422                let list = list![&mut heap; 1, 2, 3];
423
424                assert_eq!("[1, 2, 3]", format!("{:?}", list));
425
426                let mut gc_root = MockGcRoot::new(vec![list]);
427                assert_eq!(3, heap.num_used_blocks());
428                assert_eq!(1, heap.num_free_blocks());
429
430                {
431                    let mut roots: Vec<&mut GcRoot<LinkedList>> = vec![&mut gc_root];
432                    heap.gc(&mut roots[..]);
433                    assert_eq!(3, heap.num_used_blocks());
434                    assert_eq!(1, heap.num_free_blocks());
435                }
436
437                {
438                    let mut roots: Vec<&mut GcRoot<LinkedList>> = vec![&mut gc_root];
439                    heap.gc(&mut roots[..]);
440                    assert_eq!(3, heap.num_used_blocks());
441                    assert_eq!(1, heap.num_free_blocks());
442                }
443
444                gc_root.clear();
445                let mut roots: Vec<&mut GcRoot<LinkedList>> = vec![&mut gc_root];
446                heap.gc(&mut roots[..]);
447                assert_eq!(0, heap.num_used_blocks());
448                assert_eq!(1, heap.num_free_blocks());
449
450                let mut roots: Vec<&mut GcRoot<LinkedList>> = vec![&mut gc_root];
451                heap.gc(&mut roots[..]);
452                assert_eq!(0, heap.num_used_blocks());
453                assert_eq!(1, heap.num_free_blocks());
454            }
455        }
456    }
457}
managed_heap/managed.rs

managed_heap/
managed.rs
