1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97

use crate::{
    block::Block,
    globals::LINE_SIZE,
    header::HeapObjectHeader,
    internal::{block_list::BlockList, space_bitmap::SpaceBitmap},
};

pub mod normal;
pub mod overflow;

/// A type alias for the block, the current low and high offset.
pub type BlockTuple = (*mut Block, u16, u16);

/// Trait for the allocators in the immix space.
///
/// Only use `get_all_blocks()` and `allocate()` from outside.
pub trait Allocator {
    fn line_bitmap(&self) -> &SpaceBitmap<LINE_SIZE>;
    /// Get all block managed by the allocator, draining any local
    /// collections.
    fn get_all_blocks(&mut self, list: &mut BlockList);

    /// Get the current block to allocate from.
    fn take_current_block(&mut self) -> Option<BlockTuple>;

    /// Set the current block to allocate from.
    fn put_current_block(&mut self, block_tuple: BlockTuple);

    /// Get a new block from a block resource.
    fn get_new_block(&mut self) -> Option<BlockTuple>;

    /// Callback if no hole of `size` bytes was found in the current block.
    fn handle_no_hole(&mut self, size: usize) -> Option<BlockTuple>;

    /// Callback if the given `block` has no holes left.
    fn handle_full_block(&mut self, block: *mut Block);

    /// Allocate an object of `size` bytes or return `None`.
    ///
    /// This allocation will be aligned (see `HeapObjectHeader.get_size()`). This
    /// object is not initialized, just the memory chunk is allocated.
    ///
    /// This will try to find a hole in the `take_current_block()`. If there
    /// Is no hole `handle_no_hole()` will be called. If this function returns
    /// `None` a 'get_new_block()' is requested.
    fn allocate(&mut self, size: usize) -> Option<*mut HeapObjectHeader> {
        self.take_current_block()
            .and_then(|tp| self.scan_for_hole(size, tp))
            .or_else(|| self.handle_no_hole(size))
            .or_else(|| self.get_new_block())
            .map(|tp| self.allocate_from_block(size, tp))
            .map(|(tp, object)| {
                self.put_current_block(tp);

                object
            })
    }

    /// Scan a block tuple for a hole of `size` bytes and return a matching
    /// hole.
    ///
    /// If no hole was found `handle_full_block()` is called and None
    /// returned.
    #[inline]
    fn scan_for_hole(&mut self, size: usize, block_tuple: BlockTuple) -> Option<BlockTuple> {
        let (block, low, high) = block_tuple;
        match (high - low as u16) as usize >= size {
            true => Some(block_tuple),
            false => match unsafe { (*block).scan_block(self.line_bitmap(), high) } {
                None => {
                    self.handle_full_block(block);
                    None
                }
                Some((low, high)) => self.scan_for_hole(size, (block, low, high)),
            },
        }
    }

    /// Allocate an uninitialized object of `size` bytes from the block tuple.
    ///
    /// Returns the block tuple with a modified low offset and the allocated
    /// object pointer.
    ///
    /// _Note_: This must only be called if there is a hole of `size` bytes
    /// starting at low offset!
    fn allocate_from_block(
        &self,
        size: usize,
        block_tuple: BlockTuple,
    ) -> (BlockTuple, *mut HeapObjectHeader) {
        let (block, low, high) = block_tuple;

        let object = unsafe { (*block).offset(low as usize) };

        ((block, low as u16 + size as u16, high), object.cast())
    }
}