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
98
99
100
101
102
//! Dynamic memory allocation.
//!
//! Drone provides an efficient lock-free allocator based on an array of
//! fixed-size memory pools. It allows deterministic constant time allocations
//! and deallocations well-suited for real-time systems. It doesn't need to
//! store allocation metadata or each allocation, neither an expensive run-time
//! initialization. The drawback is that it may need to be tuned for the
//! particular application.
//!
//! # Configuration
//!
//! Allocator is configured statically by `heap!` macro.
//!
//! ```
//! # #![feature(alloc)]
//! # #![feature(allocator_api)]
//! # #![feature(const_fn)]
//! # #![feature(proc_macro)]
//! # #![feature(slice_get_slice)]
//! # extern crate alloc;
//! # extern crate drone_core;
//! # fn main() {}
//! # use std as core;
//! use drone_core::heap;
//!
//! heap! {
//! /// The allocator struct.
//! Heap;
//! /// The global allocator.
//! // Uncomment the following line to use it as a global allocator.
//! // #[global_allocator]
//! ALLOC;
//!
//! // The size of the heap should be known at the compile-time. It should
//! // equal the sum of all defined pools.
//! size = 0x40000;
//! // Use 4 pools of different size.
//! pools = [
//! [0x4; 0x4000], // 4-byte blocks with the capacity of 0x4000
//! [0x20; 0x800], // 32-byte blocks with the capacity of 0x800
//! [0x100; 0x100], // 256-byte blocks with the capacity of 0x100
//! [0x800; 0x20], // 2048-byte blocks with the capacity of 0x20
//! ];
//! }
//! ```
//!
//! # Initialization
//!
//! Allocator needs a simple run-time initialization before using.
//!
//! ```
//! # #![feature(alloc)]
//! # #![feature(allocator_api)]
//! # #![feature(const_fn)]
//! # #![feature(proc_macro)]
//! # #![feature(slice_get_slice)]
//! # extern crate alloc;
//! # extern crate drone_core;
//! # use std as core;
//! # pub mod symbols { #[no_mangle] pub static HEAP_START: usize = 0; }
//! use drone_core::heap;
//!
//! heap!(Heap; ALLOC);
//!
//! fn main() {
//! extern "C" {
//! // A symbol defined in the linker-script. Represents the beginning of
//! // the heap region.
//! static mut HEAP_START: usize;
//! }
//!
//! unsafe {
//! ALLOC.init(&mut HEAP_START);
//! }
//! }
//! ```
//!
//! # Operation
//!
//! Allocation steps:
//!
//! 1. Given a size of memory to allocate, binary search for a pool with the
//! lower size of blocks which can fit the size. This step should compute in
//! *O(log N)* time, where *N* is the total number of pools.
//!
//! 2. Get a free block from the pool. This step should compute in *O(1)* time.
//! If the pool is exhausted, retry this step with the next bigger pool.
//!
//! Deallocation steps:
//!
//! 1. Given a pointer of the memory to deallocate, binary search for a pool for
//! which the pointer belongs. This step should compute in *O(log N)* time,
//! where *N* is the total number of pools.
//!
//! 2. Mark a block as free in the pool. This step should compute in *O(1)*
//! time.
pub use Allocator;
pub use Pool;