comet/
allocator.rs

1use crate::{
2    block::Block,
3    globals::LINE_SIZE,
4    header::HeapObjectHeader,
5    internal::{block_list::BlockList, space_bitmap::SpaceBitmap},
6};
7
8pub mod normal;
9pub mod overflow;
10
11/// A type alias for the block, the current low and high offset.
12pub type BlockTuple = (*mut Block, u16, u16);
13
14/// Trait for the allocators in the immix space.
15///
16/// Only use `get_all_blocks()` and `allocate()` from outside.
17pub trait Allocator {
18    fn line_bitmap(&self) -> &SpaceBitmap<LINE_SIZE>;
19    /// Get all block managed by the allocator, draining any local
20    /// collections.
21    fn get_all_blocks(&mut self, list: &mut BlockList);
22
23    /// Get the current block to allocate from.
24    fn take_current_block(&mut self) -> Option<BlockTuple>;
25
26    /// Set the current block to allocate from.
27    fn put_current_block(&mut self, block_tuple: BlockTuple);
28
29    /// Get a new block from a block resource.
30    fn get_new_block(&mut self) -> Option<BlockTuple>;
31
32    /// Callback if no hole of `size` bytes was found in the current block.
33    fn handle_no_hole(&mut self, size: usize) -> Option<BlockTuple>;
34
35    /// Callback if the given `block` has no holes left.
36    fn handle_full_block(&mut self, block: *mut Block);
37
38    /// Allocate an object of `size` bytes or return `None`.
39    ///
40    /// This allocation will be aligned (see `HeapObjectHeader.get_size()`). This
41    /// object is not initialized, just the memory chunk is allocated.
42    ///
43    /// This will try to find a hole in the `take_current_block()`. If there
44    /// Is no hole `handle_no_hole()` will be called. If this function returns
45    /// `None` a 'get_new_block()' is requested.
46    fn allocate(&mut self, size: usize) -> Option<*mut HeapObjectHeader> {
47        self.take_current_block()
48            .and_then(|tp| self.scan_for_hole(size, tp))
49            .or_else(|| self.handle_no_hole(size))
50            .or_else(|| self.get_new_block())
51            .map(|tp| self.allocate_from_block(size, tp))
52            .map(|(tp, object)| {
53                self.put_current_block(tp);
54
55                object
56            })
57    }
58
59    /// Scan a block tuple for a hole of `size` bytes and return a matching
60    /// hole.
61    ///
62    /// If no hole was found `handle_full_block()` is called and None
63    /// returned.
64    #[inline]
65    fn scan_for_hole(&mut self, size: usize, block_tuple: BlockTuple) -> Option<BlockTuple> {
66        let (block, low, high) = block_tuple;
67        match (high - low as u16) as usize >= size {
68            true => Some(block_tuple),
69            false => match unsafe { (*block).scan_block(self.line_bitmap(), high) } {
70                None => {
71                    self.handle_full_block(block);
72                    None
73                }
74                Some((low, high)) => self.scan_for_hole(size, (block, low, high)),
75            },
76        }
77    }
78
79    /// Allocate an uninitialized object of `size` bytes from the block tuple.
80    ///
81    /// Returns the block tuple with a modified low offset and the allocated
82    /// object pointer.
83    ///
84    /// _Note_: This must only be called if there is a hole of `size` bytes
85    /// starting at low offset!
86    fn allocate_from_block(
87        &self,
88        size: usize,
89        block_tuple: BlockTuple,
90    ) -> (BlockTuple, *mut HeapObjectHeader) {
91        let (block, low, high) = block_tuple;
92
93        let object = unsafe { (*block).offset(low as usize) };
94
95        ((block, low as u16 + size as u16, high), object.cast())
96    }
97}
comet/allocator.rs

comet/
allocator.rs
