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())
}
}