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 114 115 116
#![no_std] #![cfg_attr(not(feature = "use_libc"), feature(asm))] //! A simple memory allocator, written for educational purposes. //! //! This module was written primarily for the code to be read. The allocator //! enclosed can be used as a memory allocator in a rust program. //! //! ## Usage //! //! ```rust //! use basic_allocator::UnixAllocator; //! //! #[global_allocator] //! static ALLOCATOR: UnixAllocator = UnixAllocator::new(); //! fn main() { //! println!("It works!") //! } //! ``` //! //! See also //! [`core::alloc::GlobalAlloc`](https://doc.rust-lang.org/nightly/core/alloc/trait.GlobalAlloc.html). //! //! ## Major Components //! //! This module has several parts. //! //! ### [`BlockList`](blocklist/struct.BlockList.html) //! //! A `BlockList` is a linked list of _freed_ memory not returned to the OS, //! which can be reused by the allocator. //! //! The free block starts with a header, and then has unused memory after that. //! The header is 16 bytes, and consists of a pointer to the next block and the //! size of the block as a whole. //! //! ### [`RawAlloc`](allocators/struct.RawAlloc.html) //! //! A `RawAlloc` is a single-threaded, non-thread-safe heap and freed memory //! manager, implementing //! [`core::alloc::GlobalAlloc`](https://doc.rust-lang.org/nightly/core/alloc/trait.GlobalAlloc.html). //! However, because it is not thread-safe, it canot be used as a global //! allocator.BlockList //! //! ### [`UnixAllocator`](allocators/struct.UnixAllocator.html) //! //! A `UnixAllocator` wraps `RawAlloc` with a spin lock to make it thread-safe, //! allowing it to be used as the global allocator. It also combines `RawAlloc` //! with a unix-specific `UnixHeapGrower` to use virtual memory pages as its //! underlying basis for making those calls. //! //! ### [`HeapGrower`](allocators/struct.HeapGrower.html) //! //! `HeapGrower` is a simple trait interface meant to abstract over the calls to //! the OS to expand the heap. //! //! ## Implementation //! //! Free memory is maintained in a linked list. The allocator has a pointer to //! the first block, and each block starts with a header with a pointer to the //! next block and the size of the current block. Blocks are in-order, so that //! merges are easily implemented. //! //! ### Allocation //! //! When [`RawAlloc`](allocators/struct.RawAlloc.html) is //! [called](allocators/struct.RawAlloc.html#method.alloc) to allocate `size` bytes: //! //! 1. The [`BlockList`](blocklist/struct.BlockList.html) is iterated through, and if any //! free block is found there large enough for the request, it is used. If //! the found block is just the right size, "popped" out of the linked list, //! and returned as a block of free memory; otherwise, the last `size` bytes //! of the block is returned as free memory, and the block's header is //! adjusted as needed. //! 2. If no suitable block is found in the list, the appropriate //! [`HeapGrower`](allocators/struct.HeapGrower.html) instance is //! [called](allocators/trait.HeapGrower.html#tymethod.grow_heap) to "grow the heap". //! For the [`UnixHeapGrower`](allocators/struct.UnixHeapGrower.html), this means that //! one or more pages of virtual memory are requested from the OS. The first //! `size` bytes are returned, and the remainder of the page is added to the //! [`BlockList`](blocklist/struct.BlockList.html). //! //! ### Deallocation //! //! When [`RawAlloc`](allocators/struct.RawAlloc.html) is //! [called](allocators/struct.RawAlloc.html#method.dealloc) to deallocate `size` bytes at //! a pointer `ptr`: //! //! 1. The [`BlockList`](blocklist/struct.BlockList.html) is iterated through to find //! where in the list `ptr` should be to remain sorted. //! 2. `ptr` is inserted, and an attempt is made to merge with both the //! preceding and following blocks. Each attempt is successful only if the //! two blocks involved are adjacent. //! //! ## Possible Extensions //! //! This is a very simple allocator, by design. There are a number of ways it //! could be better, in terms of features and performance: //! //! 1. It could return memory to the OS when it was done with a page //! 2. It could not require 16-byte alignment //! 3. It could have a thread-safe linked-list implementation, removing the need //! for a spin lock //! 4. It could implement //! [`realloc`](https://doc.rust-lang.org/core/alloc/trait.GlobalAlloc.html#method.realloc), //! so that containers could be resized in place when possible //! //! ... and probably more. Beyond those basic features, there are lots of //! optimizations in other allocators that make them more performant. pub mod allocators; pub mod blocklist; mod unix; pub use allocators::{RawAlloc, UnixAllocator}; pub use blocklist::BlockList;