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