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
103
104
105
106
107
108
109
110
111
112
113

//! 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(decl_macro)]
//! # #![feature(slice_get_slice)]
//! # extern crate alloc;
//! # extern crate drone;
//! # fn main() {}
//! # use std as core;
//! use drone::heap;
//!
//! heap! {
//!   //! The global allocator.
//!   // Uncomment the following line to use it as a global allocator.
//!   // #![global_allocator]
//!
//!   // 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(decl_macro)]
//! # #![feature(slice_get_slice)]
//! # extern crate alloc;
//! # extern crate drone;
//! # use std as core;
//! # pub mod symbols { #[no_mangle] pub static HEAP_START: usize = 0; }
//! use drone::heap;
//!
//! heap!(); // Provides `init` function inside the current scope.
//!
//! fn main() {
//!   extern "C" {
//!     // A symbol defined in the linker-script. Represents the beginning of
//!     // the heap region.
//!     static mut HEAP_START: usize;
//!   }
//!
//!   unsafe {
//!     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.
//!
//! [`heap!`]: ../macro.heap.html

#[doc(hidden)] // FIXME https://github.com/rust-lang/rust/issues/45266
mod pool;
#[doc(hidden)] // FIXME https://github.com/rust-lang/rust/issues/45266
mod allocator;

pub use self::allocator::Allocator;
pub use self::pool::Pool;
pub use drone_macros::heap_imp;

/// Configure a heap allocator.
///
/// See the [`module-level documentation`] for more details.
///
/// [`module-level documentation`]: heap/index.html
pub macro heap($($tokens:tt)*) {
  $crate::heap::heap_imp!($($tokens)*);
}