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