1 /** 2 * D Documentation Generator 3 * Copyright: © 2014 Economic Modeling Specialists, Intl., © 2015 Ferdinand Majerech 4 * Authors: Brian Schott, Ferdinand Majerech 5 * License: $(LINK2 http://www.boost.org/LICENSE_1_0.txt Boost License 1.0) 6 */ 7 8 /// std.allocator-compatible memory allocator. 9 module allocator; 10 11 public import std.experimental.allocator; 12 public import std.experimental.allocator.building_blocks.fallback_allocator; 13 public import std.experimental.allocator.gc_allocator; 14 public import std.experimental.allocator.mallocator; 15 import std.stdio; 16 import std.exception: assumeWontThrow; 17 import std.typecons: Ternary; 18 19 20 /** Allocator used by hmod (block allocator with a GC fallback for allcs bigger than block size) 21 */ 22 public alias Allocator = FallbackAllocator!( 23 HmodBlockAllocator!(32 * 1024), 24 GCAllocator); 25 26 27 /** A somewhat incomplete (no dealloc) std.allocator implementation - passed to 28 * libdparse. 29 * 30 * All data is deallocated in destructor. 31 * 32 * Allocates memory in fixed-size blocks and tries to place allocations into 33 * those blocks. Allocations larger than a block fail. 34 * 35 * Based on BlockAllocator from Brian Schott's containers library 36 */ 37 struct HmodBlockAllocator(size_t blockSize) 38 { 39 union 40 { 41 private size_t bytesAllocated_; 42 /// Number of bytes allocated over time. 43 const size_t bytesAllocated; 44 } 45 // Since we don't support deallocation (right now), these two are the same 46 /// The highest number of bytes allocated at any given moment. 47 alias bytesHighTide = bytesAllocated; 48 union 49 { 50 private size_t bytesWithSlack_; 51 /// Number of bytes allocated at the moment, including slack (wasted space) 52 const size_t bytesWithSlack; 53 } 54 union 55 { 56 private size_t bytesGivenUp_; 57 /// Total size of allocations that failed (bigger than block size). 58 const size_t bytesGivenUp; 59 } 60 union 61 { 62 private size_t allocsGivenUp_; 63 /// Number of allocations that failed. 64 const size_t allocsGivenUp; 65 } 66 union 67 { 68 private size_t bytesAttemptedToDeallocate_; 69 /// Number of bytes the user has attempted to deallocate. 70 const size_t bytesAttemptedToDeallocate; 71 } 72 /** 73 * Copy construction disabled because this struct clears its memory with a 74 * destructor. 75 */ 76 @disable this(this); 77 78 /** 79 * Frees all memory allocated by this allocator 80 */ 81 ~this() /*pure nothrow*/ @trusted 82 { 83 Node* current = root; 84 Node* previous = void; 85 while (current !is null) 86 { 87 previous = current; 88 current = current.next; 89 assert (previous == previous.memory.ptr); 90 Mallocator.instance.deallocate(previous.memory); 91 } 92 root = null; 93 } 94 95 /** 96 * Standard allocator operation. 97 * 98 * Returns null if bytes > blockSize. 99 */ 100 void[] allocate(size_t bytes) /*pure*/ nothrow @trusted 101 out (result) 102 { 103 import std.format : format; 104 assert (!result.length || result.length == bytes, 105 format("Allocated %d bytes when %d bytes were requested.", 106 result.length, bytes)); 107 } 108 body 109 { 110 void updateStats(void[] result) 111 { 112 if (!result.length) 113 { 114 ++allocsGivenUp_; 115 bytesGivenUp_ += bytes; 116 return; 117 } 118 bytesAllocated_ += result.length; 119 } 120 if (bytes > maxAllocationSize) 121 { 122 debug 123 { 124 import std.exception : assumeWontThrow; 125 writeln("Big alloc: ", bytes).assumeWontThrow; 126 } 127 updateStats(null); 128 return null; 129 } 130 131 // Allocate from the beginning of the list. Filled blocks go later in 132 // the list. 133 // Give up after three blocks. We don't want to do a full linear scan. 134 size_t i; 135 for (Node* current = root; current !is null && i < 3; current = current.next) 136 { 137 void[] mem = allocateInNode(current, bytes); 138 if (mem !is null) 139 { 140 updateStats(mem); 141 return mem; 142 } 143 i++; 144 } 145 Node* n = allocateNewNode(); 146 bytesWithSlack_ += n.memory.length; 147 void[] mem = allocateInNode(n, bytes); 148 n.next = root; 149 root = n; 150 updateStats(mem); 151 return mem; 152 } 153 154 //TODO implement deallocate if/when libdparse uses it (needs allocator design changes) 155 /// Dummy deallocation function, to keep track of how much the user tried to deallocate. 156 bool deallocate(void[] b) pure nothrow @trusted 157 { 158 bytesAttemptedToDeallocate_ += b.length; 159 return false; 160 } 161 162 /// Was the given buffer allocated with this allocator? 163 Ternary owns(void[] b) const pure nothrow @trusted 164 { 165 for (const(Node)* current = root; current !is null; current = current.next) 166 { 167 if (b.ptr >= current.memory.ptr && b.ptr + b.length <= current.memory.ptr + current.used) 168 return Ternary.yes; 169 } 170 return Ternary.no; 171 } 172 /** 173 * The maximum number of bytes that can be allocated at a time with this 174 * allocator. This is smaller than blockSize because of some internal 175 * bookkeeping information. 176 */ 177 enum maxAllocationSize = blockSize - Node.sizeof; 178 179 /** 180 * Allocator's memory alignment 181 */ 182 enum alignment = platformAlignment; 183 184 /// Write allocation statistics to standard output. 185 void writeStats() 186 { 187 writefln("allocated: %.2fMiB\n" ~ 188 "deallocate attempts: %.2fMiB\n" ~ 189 "high tide: %.2f\n" ~ 190 "allocated + slack: %.2f\n" ~ 191 "given up (bytes): %.2f\n" ~ 192 "given up (allocs): %s\n", 193 bytesAllocated / 1000_000.0, 194 bytesAttemptedToDeallocate_ / 1000_000.0, 195 bytesHighTide / 1000_000.0, 196 bytesWithSlack / 1000_000.0, 197 bytesGivenUp / 1000_000.0, 198 allocsGivenUp); 199 } 200 private: 201 202 /** 203 * Allocates a new node along with its memory 204 */ 205 Node* allocateNewNode() /*pure*/ nothrow const @trusted 206 { 207 void[] memory = Mallocator.instance.allocate(blockSize).assumeWontThrow; 208 Node* n = cast(Node*) memory.ptr; 209 n.used = roundUpToMultipleOf(Node.sizeof, platformAlignment); 210 n.memory = memory; 211 n.next = null; 212 return n; 213 } 214 215 /** 216 * Allocates memory from the given node 217 */ 218 void[] allocateInNode(Node* node, size_t bytes) pure nothrow const @safe 219 in 220 { 221 assert (node !is null); 222 } 223 body 224 { 225 if (node.used + bytes > node.memory.length) 226 return null; 227 immutable prev = node.used; 228 node.used = roundUpToMultipleOf(node.used + bytes, platformAlignment); 229 return node.memory[prev .. prev + bytes]; 230 } 231 232 /** 233 * Single linked list of allocated blocks 234 */ 235 static struct Node 236 { 237 void[] memory; 238 size_t used; 239 Node* next; 240 } 241 242 /** 243 * Pointer to the first item in the node list 244 */ 245 Node* root; 246 247 /** 248 * Returns s rounded up to a multiple of base. 249 */ 250 static size_t roundUpToMultipleOf(size_t s, uint base) pure nothrow @safe 251 { 252 assert(base); 253 auto rem = s % base; 254 return rem ? s + base - rem : s; 255 } 256 }