free_tree.d revision 1.1.1.1
1/// 2module std.experimental.allocator.building_blocks.free_tree; 3 4import std.experimental.allocator.common; 5 6//debug = std_experimental_allocator_free_tree; 7 8/** 9 10The Free Tree allocator, stackable on top of any other allocator, bears 11similarity with the free list allocator. Instead of a singly-linked list of 12previously freed blocks, it maintains a binary search tree. This allows the 13Free Tree allocator to manage blocks of arbitrary lengths and search them 14efficiently. 15 16Common uses of $(D FreeTree) include: 17 18$(UL 19$(LI Adding $(D deallocate) capability to an allocator that lacks it (such as simple regions).) 20$(LI Getting the benefits of multiple adaptable freelists that do not need to 21be tuned for one specific size but insted automatically adapts itself to 22frequently used sizes.) 23) 24 25The free tree has special handling of duplicates (a singly-linked list per 26node) in anticipation of large number of duplicates. Allocation time from the 27free tree is expected to be $(BIGOH log n) where $(D n) is the number of 28distinct sizes (not total nodes) kept in the free tree. 29 30Allocation requests first search the tree for a buffer of suitable size 31deallocated in the past. If a match is found, the node is removed from the tree 32and the memory is returned. Otherwise, the allocation is directed to $(D 33ParentAllocator). If at this point $(D ParentAllocator) also fails to allocate, 34$(D FreeTree) frees everything and then tries the parent allocator again. 35 36Upon deallocation, the deallocated block is inserted in the internally 37maintained free tree (not returned to the parent). The free tree is not kept 38balanced. Instead, it has a last-in-first-out flavor because newly inserted 39blocks are rotated to the root of the tree. That way allocations are cache 40friendly and also frequently used sizes are more likely to be found quickly, 41whereas seldom used sizes migrate to the leaves of the tree. 42 43$(D FreeTree) rounds up small allocations to at least $(D 4 * size_t.sizeof), 44which on 64-bit system is one cache line size. If very small objects need to 45be efficiently allocated, the $(D FreeTree) should be fronted with an 46appropriate small object allocator. 47 48The following methods are defined if $(D ParentAllocator) defines them, and forward to it: $(D allocateAll), $(D expand), $(D owns), $(D reallocate). 49*/ 50struct FreeTree(ParentAllocator) 51{ 52 static assert(ParentAllocator.alignment % size_t.alignof == 0, 53 "FreeTree must be on top of a word-aligned allocator"); 54 55 import std.algorithm.comparison : min, max; 56 import std.algorithm.mutation : swap; 57 import std.traits : hasMember; 58 59 // State 60 static if (stateSize!ParentAllocator) private ParentAllocator parent; 61 else private alias parent = ParentAllocator.instance; 62 private Node* root; // that's the entire added state 63 64 private struct Node 65 { 66 Node*[2] kid; 67 Node* sibling; 68 size_t size; 69 ref Node* left() { return kid[0]; } 70 ref Node* right() { return kid[1]; } 71 } 72 73 // Removes "which" from the tree, returns the memory it occupied 74 private void[] remove(ref Node* which) 75 { 76 assert(which); 77 assert(!which.sibling); 78 auto result = (cast(ubyte*) which)[0 .. which.size]; 79 if (!which.right) which = which.left; 80 else if (!which.left) which = which.right; 81 else 82 { 83 // result has two kids 84 static bool toggler; 85 // Crude randomization: alternate left/right choices 86 toggler = !toggler; 87 auto newRoot = which.kid[toggler], orphan = which.kid[!toggler]; 88 which = newRoot; 89 for (Node* n = void; (n = newRoot.kid[!toggler]) !is null; ) 90 { 91 newRoot = n; 92 } 93 newRoot.kid[!toggler] = orphan; 94 } 95 return result; 96 } 97 98 private void[] findAndRemove(ref Node* n, size_t s) 99 { 100 if (!n) return null; 101 if (s == n.size) 102 { 103 if (auto sis = n.sibling) 104 { 105 // Nice, give away one from the freelist 106 auto result = (cast(ubyte*) sis)[0 .. sis.size]; 107 n.sibling = sis.sibling; 108 return result; 109 } 110 return remove(n); 111 } 112 return findAndRemove(n.kid[s > n.size], s); 113 } 114 115 debug(std_experimental_allocator_free_tree) 116 private void dump() 117 { 118 import std.stdio : writef, writefln, writeln; 119 writeln(typeof(this).stringof, "@", &this, " {"); 120 scope(exit) writeln("}"); 121 122 if (!root) return; 123 124 static void recurse(Node* n, uint indent = 4) 125 { 126 if (!n) 127 { 128 writefln("%*s(null)", indent, ""); 129 return; 130 } 131 for (auto sis = n; sis; sis = sis.sibling) 132 { 133 writef("%*s%x (%s bytes) ", indent, "", 134 cast(void*) n, n.size); 135 } 136 writeln; 137 if (!n.left && !n.right) return; 138 recurse(n.left, indent + 4); 139 recurse(n.right, indent + 4); 140 } 141 recurse(root); 142 } 143 144 private string formatSizes() 145 { 146 string result = "("; 147 void recurse(Node* n) 148 { 149 if (!n) 150 { 151 result ~= "_"; 152 return; 153 } 154 import std.conv : to; 155 result ~= to!string(n.size); 156 for (auto sis = n.sibling; sis; sis = sis.sibling) 157 { 158 result ~= "+moar"; 159 } 160 if (n.left || n.right) 161 { 162 result ~= " ("; 163 recurse(n.left); 164 result ~= ' '; 165 recurse(n.right); 166 result ~= ")"; 167 } 168 } 169 recurse(root); 170 return result ~= ")"; 171 } 172 173 private static void rotate(ref Node* parent, bool toRight) 174 { 175 assert(parent); 176 auto opposing = parent.kid[!toRight]; 177 if (!opposing) return; 178 parent.kid[!toRight] = opposing.kid[toRight]; 179 opposing.kid[toRight] = parent; 180 parent = opposing; 181 } 182 183 // Inserts which into the tree, making it the new root 184 private void insertAsRoot(Node* which) 185 { 186 assert(which); 187 debug(std_experimental_allocator_free_tree) 188 { 189 assertValid; 190 scope(exit) assertValid; 191 } 192 193 static void recurse(ref Node* where, Node* which) 194 { 195 if (!where) 196 { 197 where = which; 198 which.left = null; 199 which.right = null; 200 which.sibling = null; 201 return; 202 } 203 if (which.size == where.size) 204 { 205 // Special handling of duplicates 206 which.sibling = where.sibling; 207 where.sibling = which; 208 which.left = null; 209 which.right = null; 210 return; 211 } 212 bool goRight = which.size > where.size; 213 recurse(where.kid[goRight], which); 214 rotate(where, !goRight); 215 } 216 recurse(root, which); 217 } 218 219 private void assertValid() 220 { 221 debug(std_experimental_allocator_free_tree) 222 { 223 static bool isBST(Node* n, size_t lb = 0, size_t ub = size_t.max) 224 { 225 if (!n) return true; 226 for (auto sis = n.sibling; sis; sis = sis.sibling) 227 { 228 assert(n.size == sis.size); 229 assert(sis.left is null); 230 assert(sis.right is null); 231 } 232 return lb < n.size && n.size <= ub 233 && isBST(n.left, lb, min(ub, n.size)) 234 && isBST(n.right, max(lb, n.size), ub); 235 } 236 if (isBST(root)) return; 237 dump; 238 assert(0); 239 } 240 } 241 242 /** 243 The $(D FreeTree) is word aligned. 244 */ 245 enum uint alignment = size_t.alignof; 246 247 /** 248 The $(D FreeTree) allocator is noncopyable. 249 */ 250 this(this) @disable; 251 252 /** 253 The destructor of $(D FreeTree) releases all memory back to the parent 254 allocator. 255 */ 256 static if (hasMember!(ParentAllocator, "deallocate")) 257 ~this() 258 { 259 clear; 260 } 261 262 /** 263 Returns $(D parent.goodAllocSize(max(Node.sizeof, s))). 264 */ 265 static if (stateSize!ParentAllocator) 266 size_t goodAllocSize(size_t s) 267 { 268 return parent.goodAllocSize(max(Node.sizeof, s)); 269 } 270 else 271 static size_t goodAllocSize(size_t s) 272 { 273 return parent.goodAllocSize(max(Node.sizeof, s)); 274 } 275 276 /** 277 278 Allocates $(D n) bytes of memory. First consults the free tree, and returns 279 from it if a suitably sized block is found. Otherwise, the parent allocator 280 is tried. If allocation from the parent succeeds, the allocated block is 281 returned. Otherwise, the free tree tries an alternate strategy: If $(D 282 ParentAllocator) defines $(D deallocate), $(D FreeTree) releases all of its 283 contents and tries again. 284 285 TODO: Splitting and coalescing should be implemented if $(D ParentAllocator) does not defined $(D deallocate). 286 287 */ 288 void[] allocate(size_t n) 289 { 290 assertValid; 291 if (n == 0) return null; 292 293 immutable s = goodAllocSize(n); 294 295 // Consult the free tree. 296 auto result = findAndRemove(root, s); 297 if (result.ptr) return result.ptr[0 .. n]; 298 299 // No block found, try the parent allocator. 300 result = parent.allocate(s); 301 if (result.ptr) return result.ptr[0 .. n]; 302 303 // Parent ran out of juice, desperation mode on 304 static if (hasMember!(ParentAllocator, "deallocate")) 305 { 306 clear; 307 // Try parent allocator again. 308 result = parent.allocate(s); 309 if (result.ptr) return result.ptr[0 .. n]; 310 return null; 311 } 312 else 313 { 314 // TODO: get smart here 315 return null; 316 } 317 } 318 319 // Forwarding methods 320 mixin(forwardToMember("parent", 321 "allocateAll", "expand", "owns", "reallocate")); 322 323 /** Places $(D b) into the free tree. */ 324 bool deallocate(void[] b) 325 { 326 if (!b.ptr) return true; 327 auto which = cast(Node*) b.ptr; 328 which.size = goodAllocSize(b.length); 329 // deliberately don't initialize which.left and which.right 330 assert(which.size >= Node.sizeof); 331 insertAsRoot(which); 332 return true; 333 } 334 335 @system unittest // test a few simple configurations 336 { 337 import std.experimental.allocator.gc_allocator; 338 FreeTree!GCAllocator a; 339 auto b1 = a.allocate(10000); 340 auto b2 = a.allocate(20000); 341 auto b3 = a.allocate(30000); 342 assert(b1.ptr && b2.ptr && b3.ptr); 343 a.deallocate(b1); 344 a.deallocate(b3); 345 a.deallocate(b2); 346 assert(a.formatSizes == "(20480 (12288 32768))", a.formatSizes); 347 348 b1 = a.allocate(10000); 349 assert(a.formatSizes == "(20480 (_ 32768))", a.formatSizes); 350 b1 = a.allocate(30000); 351 assert(a.formatSizes == "(20480)", a.formatSizes); 352 b1 = a.allocate(20000); 353 assert(a.formatSizes == "(_)", a.formatSizes); 354 } 355 356 @system unittest // build a complex free tree 357 { 358 import std.experimental.allocator.gc_allocator, std.range; 359 FreeTree!GCAllocator a; 360 uint[] sizes = [3008,704,1856,576,1632,672,832,1856,1120,2656,1216,672, 361 448,992,2400,1376,2688,2656,736,1440]; 362 void[][] allocs; 363 foreach (s; sizes) 364 allocs ~= a.allocate(s); 365 foreach_reverse (b; allocs) 366 { 367 assert(b.ptr); 368 a.deallocate(b); 369 } 370 a.assertValid; 371 allocs = null; 372 foreach (s; sizes) 373 allocs ~= a.allocate(s); 374 assert(a.root is null); 375 a.assertValid; 376 } 377 378 /** Defined if $(D ParentAllocator.deallocate) exists, and returns to it 379 all memory held in the free tree. */ 380 static if (hasMember!(ParentAllocator, "deallocate")) 381 void clear() 382 { 383 void recurse(Node* n) 384 { 385 if (!n) return; 386 recurse(n.left); 387 recurse(n.right); 388 parent.deallocate((cast(ubyte*) n)[0 .. n.size]); 389 } 390 recurse(root); 391 root = null; 392 } 393 394 /** 395 396 Defined if $(D ParentAllocator.deallocateAll) exists, and forwards to it. 397 Also nullifies the free tree (it's assumed the parent frees all memory 398 stil managed by the free tree). 399 400 */ 401 static if (hasMember!(ParentAllocator, "deallocateAll")) 402 bool deallocateAll() 403 { 404 // This is easy, just nuke the root and deallocate all from the 405 // parent 406 root = null; 407 return parent.deallocateAll; 408 } 409} 410 411@system unittest 412{ 413 import std.experimental.allocator.gc_allocator; 414 testAllocator!(() => FreeTree!GCAllocator()); 415} 416 417@system unittest // issue 16506 418{ 419 import std.experimental.allocator.gc_allocator : GCAllocator; 420 import std.experimental.allocator.mallocator : Mallocator; 421 422 static void f(ParentAllocator)(size_t sz) 423 { 424 static FreeTree!ParentAllocator myAlloc; 425 byte[] _payload = cast(byte[]) myAlloc.allocate(sz); 426 assert(_payload, "_payload is null"); 427 _payload[] = 0; 428 myAlloc.deallocate(_payload); 429 } 430 431 f!Mallocator(33); 432 f!Mallocator(43); 433 f!GCAllocator(1); 434} 435 436@system unittest // issue 16507 437{ 438 static struct MyAllocator 439 { 440 byte dummy; 441 static bool alive = true; 442 void[] allocate(size_t s) { return new byte[](s); } 443 bool deallocate(void[] ) { if (alive) assert(false); return true; } 444 enum alignment = size_t.sizeof; 445 } 446 447 FreeTree!MyAllocator ft; 448 void[] x = ft.allocate(1); 449 ft.deallocate(x); 450 ft.allocate(1000); 451 MyAllocator.alive = false; 452} 453 454@system unittest // "desperation mode" 455{ 456 uint myDeallocCounter = 0; 457 458 struct MyAllocator 459 { 460 byte[] allocation; 461 void[] allocate(size_t s) 462 { 463 if (allocation.ptr) return null; 464 allocation = new byte[](s); 465 return allocation; 466 } 467 bool deallocate(void[] ) 468 { 469 ++myDeallocCounter; 470 allocation = null; 471 return true; 472 } 473 enum alignment = size_t.sizeof; 474 } 475 476 FreeTree!MyAllocator ft; 477 void[] x = ft.allocate(1); 478 ft.deallocate(x); 479 assert(myDeallocCounter == 0); 480 x = ft.allocate(1000); // Triggers "desperation mode". 481 assert(myDeallocCounter == 1); 482 assert(x.ptr); 483 void[] y = ft.allocate(1000); /* Triggers "desperation mode" but there's 484 nothing to deallocate so MyAllocator can't deliver. */ 485 assert(myDeallocCounter == 1); 486 assert(y.ptr is null); 487} 488