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 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147
// // Copyright 2017 yvt, all rights reserved. // // Licensed under the MIT license <LICENSE-MIT or // http://opensource.org/licenses/MIT>. This file may // not be copied, modified,or distributed except // according to those terms. // //! Free space bitmap-based external memory allocator. //! //! This allocator uses a simple bitmap to track the allocation state, and //! relies on a naïve bit scan for allocation. //! //! ## Memory Overhead //! //! Since it uses a bitmap to track free space, it consumes a memory proportional //! to the size of the heap. The memory consumption is estimated to be roughly //! `size / 8` bytes, where `size` is the size of the heap measured by the //! number of allocation units. //! //! `BitmapAlloc` does not store information about individual allocated regions //! by itself. Therefore, `BitmapAlloc` would be preferred when the number of //! allocations is quite high and each allocation is very small (preferably, //! just one allocation unit). //! //! The following table shows the memory overhead comparison between `Tlsf` and //! `BitmapAlloc` with a varying number of allocations (assuming the heap is //! fully occupied). //! //! | `size` | # of allocations | `Tlsf` (bytes) | `BitmapAloc` (bytes) | //! | ------ | ---------------- | -------------- | -------------------- | //! | 1,024 | 0 | 1,118 | 128 | //! | | 1 | 1,174 | 128 | //! | | 256 | 15,454 | 128 | //! | | 1,024 | 58,462 | 128 | //! | 65,536 | 0 | 1,118 | 8,192 | //! | | 1 | 1,174 | 8,192 | //! | | 1,024 | 58,462 | 8,192 | //! | | 65,536 | 3,671,134 | 8,192 | //! //! ## Performance //! //! The allocation throughput is roughly the same as of jemalloc. use std::ops::Range; use int::BinaryInteger; use bitmaputils::*; /// Free space bitmap-based external memory allocator. /// /// See [the module-level documentation] for more. /// /// [the module-level documentation]: index.html pub struct BitmapAlloc { bitmap: Vec<usize>, size: usize, next: usize, } /// A handle type to a region allocated in a `BitmapAlloc`. /// /// `BitmapAllocRegion` returned by a `BitmapAlloc` only can be used with the /// same `BitmapAlloc`. #[derive(Debug, PartialEq, Eq, Hash)] pub struct BitmapAllocRegion { range: Range<usize>, } impl BitmapAlloc { /// Construct a `BitmapAlloc`. pub fn new(size: usize) -> Self { let width = <usize>::max_digits() as usize; Self { bitmap: vec![0; (size + width - 1) / width], size, next: 0, } } /// Alias of [`alloc_next`]. /// /// [`alloc_next`]: #method.alloc_next pub fn alloc(&mut self, size: usize) -> Option<(BitmapAllocRegion, usize)> { self.alloc_next(size) } /// Allocate a region of the size `size` using a Next-Fit strategy. /// The time complexity is linear to the size of the heap. /// /// Returns a handle of the allocated region and its offset if the /// allocation succeeds. Returns `None` otherwise. /// /// `size` must not be zero. pub fn alloc_next(&mut self, size: usize) -> Option<(BitmapAllocRegion, usize)> { let next = self.next; self.alloc_inner(size, next).or_else( || self.alloc_first(size), ) } /// Allocate a region of the size `size` using a First-Fit strategy. /// The time complexity is linear to the size of the heap. /// /// Returns a handle of the allocated region and its offset if the /// allocation succeeds. Returns `None` otherwise. /// /// `size` must not be zero. pub fn alloc_first(&mut self, size: usize) -> Option<(BitmapAllocRegion, usize)> { self.alloc_inner(size, 0) } fn alloc_inner(&mut self, size: usize, start: usize) -> Option<(BitmapAllocRegion, usize)> { assert!(size != 0); if start + size > self.size { return None; } find_zeros(&self.bitmap, start, size).and_then(|offs| { let range = offs..offs + size; if range.end <= self.size { set_bits_ranged(&mut self.bitmap, range.clone()); if range.end == self.size { self.next = 0; } else { self.next = range.end; } Some((BitmapAllocRegion { range }, offs)) } else { None } }) } /// Deallocate the specified region. /// /// `r` must originate from the same instance of `BitmapAlloc`. Otherwise, /// `BitmapAlloc` enters an inconsistent state and possibly panics, but does /// not cause an undefined behavior. pub fn dealloc_relaxed(&mut self, r: BitmapAllocRegion) { // Optimize for stack-like usage if self.next == r.range.end { self.next = r.range.start; } clear_bits_ranged(&mut self.bitmap, r.range); } }