1 /// 2 module std.experimental.allocator.building_blocks.free_list; 3 4 import std.experimental.allocator.common; 5 import std.typecons : Flag, Yes, No; 6 7 /** 8 9 $(HTTP en.wikipedia.org/wiki/Free_list, Free list allocator), stackable on top of 10 another allocator. Allocation requests between $(D min) and $(D max) bytes are 11 rounded up to $(D max) and served from a singly-linked list of buffers 12 deallocated in the past. All other allocations are directed to $(D 13 ParentAllocator). Due to the simplicity of free list management, allocations 14 from the free list are fast. 15 16 One instantiation is of particular interest: $(D FreeList!(0, unbounded)) puts 17 every deallocation in the freelist, and subsequently serves any allocation from 18 the freelist (if not empty). There is no checking of size matching, which would 19 be incorrect for a freestanding allocator but is both correct and fast when an 20 owning allocator on top of the free list allocator (such as $(D Segregator)) is 21 already in charge of handling size checking. 22 23 The following methods are defined if $(D ParentAllocator) defines them, and 24 forward to it: $(D expand), $(D owns), $(D reallocate). 25 26 */ 27 struct FreeList(ParentAllocator, 28 size_t minSize, size_t maxSize = minSize, 29 Flag!"adaptive" adaptive = No.adaptive) 30 { 31 import std.conv : text; 32 import std.exception : enforce; 33 import std.traits : hasMember; 34 import std.typecons : Ternary; 35 36 static assert(minSize != unbounded, "Use minSize = 0 for no low bound."); 37 static assert(maxSize >= (void*).sizeof, 38 "Maximum size must accommodate a pointer."); 39 40 private enum unchecked = minSize == 0 && maxSize == unbounded; 41 42 private enum hasTolerance = !unchecked && (minSize != maxSize 43 || maxSize == chooseAtRuntime); 44 45 static if (minSize == chooseAtRuntime) 46 { 47 /** 48 Returns the smallest allocation size eligible for allocation from the 49 freelist. (If $(D minSize != chooseAtRuntime), this is simply an alias 50 for $(D minSize).) 51 */ minFreeList52 @property size_t min() const 53 { 54 assert(_min != chooseAtRuntime); 55 return _min; 56 } 57 /** 58 If $(D FreeList) has been instantiated with $(D minSize == 59 chooseAtRuntime), then the $(D min) property is writable. Setting it 60 must precede any allocation. 61 62 Params: 63 low = new value for $(D min) 64 65 Precondition: $(D low <= max), or $(D maxSize == chooseAtRuntime) and 66 $(D max) has not yet been initialized. Also, no allocation has been 67 yet done with this allocator. 68 69 Postcondition: $(D min == low) 70 */ minFreeList71 @property void min(size_t low) 72 { 73 assert(low <= max || max == chooseAtRuntime); 74 minimize; 75 _min = low; 76 } 77 } 78 else 79 { 80 alias min = minSize; 81 } 82 83 static if (maxSize == chooseAtRuntime) 84 { 85 /** 86 Returns the largest allocation size eligible for allocation from the 87 freelist. (If $(D maxSize != chooseAtRuntime), this is simply an alias 88 for $(D maxSize).) All allocation requests for sizes greater than or 89 equal to $(D min) and less than or equal to $(D max) are rounded to $(D 90 max) and forwarded to the parent allocator. When the block fitting the 91 same constraint gets deallocated, it is put in the freelist with the 92 allocated size assumed to be $(D max). 93 */ maxFreeList94 @property size_t max() const { return _max; } 95 96 /** 97 If $(D FreeList) has been instantiated with $(D maxSize == 98 chooseAtRuntime), then the $(D max) property is writable. Setting it 99 must precede any allocation. 100 101 Params: 102 high = new value for $(D max) 103 104 Precondition: $(D high >= min), or $(D minSize == chooseAtRuntime) and 105 $(D min) has not yet been initialized. Also $(D high >= (void*).sizeof). Also, no allocation has been yet done with this allocator. 106 107 Postcondition: $(D max == high) 108 */ maxFreeList109 @property void max(size_t high) 110 { 111 assert((high >= min || min == chooseAtRuntime) 112 && high >= (void*).sizeof); 113 minimize; 114 _max = high; 115 } 116 117 /// 118 @safe unittest 119 { 120 import std.experimental.allocator.common : chooseAtRuntime; 121 import std.experimental.allocator.mallocator : Mallocator; 122 123 FreeList!(Mallocator, chooseAtRuntime, chooseAtRuntime) a; 124 a.min = 64; 125 a.max = 128; 126 assert(a.min == 64); 127 assert(a.max == 128); 128 } 129 } 130 else 131 { 132 alias max = maxSize; 133 } 134 tooSmallFreeList135 private bool tooSmall(size_t n) const 136 { 137 static if (minSize == 0) return false; 138 else return n < min; 139 } 140 tooLargeFreeList141 private bool tooLarge(size_t n) const 142 { 143 static if (maxSize == unbounded) return false; 144 else return n > max; 145 } 146 freeListEligibleFreeList147 private bool freeListEligible(size_t n) const 148 { 149 static if (unchecked) 150 { 151 return true; 152 } 153 else 154 { 155 static if (minSize == 0) 156 { 157 if (!n) return false; 158 } 159 static if (minSize == maxSize && minSize != chooseAtRuntime) 160 return n == maxSize; 161 else 162 return !tooSmall(n) && !tooLarge(n); 163 } 164 } 165 166 static if (!unchecked) blockForFreeList167 private void[] blockFor(Node* p) 168 { 169 assert(p); 170 return (cast(void*) p)[0 .. max]; 171 } 172 173 // statistics 174 static if (adaptive == Yes.adaptive) 175 { 176 private enum double windowLength = 1000.0; 177 private enum double tooFewMisses = 0.01; 178 private double probMiss = 1.0; // start with a high miss probability 179 private uint accumSamples, accumMisses; 180 updateStatsFreeList181 void updateStats() 182 { 183 assert(accumSamples >= accumMisses); 184 /* 185 Given that for the past windowLength samples we saw misses with 186 estimated probability probMiss, and assuming the new sample wasMiss or 187 not, what's the new estimated probMiss? 188 */ 189 probMiss = (probMiss * windowLength + accumMisses) 190 / (windowLength + accumSamples); 191 assert(probMiss <= 1.0); 192 accumSamples = 0; 193 accumMisses = 0; 194 // If probability to miss is under x%, yank one off the freelist 195 static if (!unchecked) 196 { 197 if (probMiss < tooFewMisses && _root) 198 { 199 auto b = blockFor(_root); 200 _root = _root.next; 201 parent.deallocate(b); 202 } 203 } 204 } 205 } 206 207 private struct Node { Node* next; } 208 static assert(ParentAllocator.alignment >= Node.alignof); 209 210 // state 211 /** 212 The parent allocator. Depending on whether $(D ParentAllocator) holds state 213 or not, this is a member variable or an alias for 214 `ParentAllocator.instance`. 215 */ 216 static if (stateSize!ParentAllocator) ParentAllocator parent; 217 else alias parent = ParentAllocator.instance; 218 private Node* root; 219 static if (minSize == chooseAtRuntime) private size_t _min = chooseAtRuntime; 220 static if (maxSize == chooseAtRuntime) private size_t _max = chooseAtRuntime; 221 222 /** 223 Alignment offered. 224 */ 225 alias alignment = ParentAllocator.alignment; 226 227 /** 228 If $(D maxSize == unbounded), returns $(D parent.goodAllocSize(bytes)). 229 Otherwise, returns $(D max) for sizes in the interval $(D [min, max]), and 230 $(D parent.goodAllocSize(bytes)) otherwise. 231 232 Precondition: 233 If set at runtime, $(D min) and/or $(D max) must be initialized 234 appropriately. 235 236 Postcondition: 237 $(D result >= bytes) 238 */ goodAllocSizeFreeList239 size_t goodAllocSize(size_t bytes) 240 { 241 assert(minSize != chooseAtRuntime && maxSize != chooseAtRuntime); 242 static if (maxSize != unbounded) 243 { 244 if (freeListEligible(bytes)) 245 { 246 assert(parent.goodAllocSize(max) == max, 247 text("Wrongly configured freelist: maximum should be ", 248 parent.goodAllocSize(max), " instead of ", max)); 249 return max; 250 } 251 } 252 return parent.goodAllocSize(bytes); 253 } 254 allocateEligibleFreeList255 private void[] allocateEligible(size_t bytes) 256 { 257 assert(bytes); 258 if (root) 259 { 260 // faster 261 auto result = (cast(ubyte*) root)[0 .. bytes]; 262 root = root.next; 263 return result; 264 } 265 // slower 266 static if (hasTolerance) 267 { 268 immutable toAllocate = max; 269 } 270 else 271 { 272 alias toAllocate = bytes; 273 } 274 assert(toAllocate == max || max == unbounded); 275 auto result = parent.allocate(toAllocate); 276 static if (hasTolerance) 277 { 278 if (result) result = result.ptr[0 .. bytes]; 279 } 280 static if (adaptive == Yes.adaptive) 281 { 282 ++accumMisses; 283 updateStats; 284 } 285 return result; 286 } 287 288 /** 289 Allocates memory either off of the free list or from the parent allocator. 290 If $(D n) is within $(D [min, max]) or if the free list is unchecked 291 ($(D minSize == 0 && maxSize == size_t.max)), then the free list is 292 consulted first. If not empty (hit), the block at the front of the free 293 list is removed from the list and returned. Otherwise (miss), a new block 294 of $(D max) bytes is allocated, truncated to $(D n) bytes, and returned. 295 296 Params: 297 n = number of bytes to allocate 298 299 Returns: 300 The allocated block, or $(D null). 301 302 Precondition: 303 If set at runtime, $(D min) and/or $(D max) must be initialized 304 appropriately. 305 306 Postcondition: $(D result.length == bytes || result is null) 307 */ allocateFreeList308 void[] allocate(size_t n) 309 { 310 static if (adaptive == Yes.adaptive) ++accumSamples; 311 assert(n < size_t.max / 2); 312 // fast path 313 if (freeListEligible(n)) 314 { 315 return allocateEligible(n); 316 } 317 // slower 318 static if (adaptive == Yes.adaptive) 319 { 320 updateStats; 321 } 322 return parent.allocate(n); 323 } 324 325 // Forwarding methods 326 mixin(forwardToMember("parent", 327 "expand", "owns", "reallocate")); 328 329 /** 330 If $(D block.length) is within $(D [min, max]) or if the free list is 331 unchecked ($(D minSize == 0 && maxSize == size_t.max)), then inserts the 332 block at the front of the free list. For all others, forwards to $(D 333 parent.deallocate) if $(D Parent.deallocate) is defined. 334 335 Params: 336 block = Block to deallocate. 337 338 Precondition: 339 If set at runtime, $(D min) and/or $(D max) must be initialized 340 appropriately. The block must have been allocated with this 341 freelist, and no dynamic changing of $(D min) or $(D max) is allowed to 342 occur between allocation and deallocation. 343 */ deallocateFreeList344 bool deallocate(void[] block) 345 { 346 if (freeListEligible(block.length)) 347 { 348 if (min == 0) 349 { 350 // In this case a null pointer might have made it this far. 351 if (block is null) return true; 352 } 353 auto t = root; 354 root = cast(Node*) block.ptr; 355 root.next = t; 356 return true; 357 } 358 static if (hasMember!(ParentAllocator, "deallocate")) 359 return parent.deallocate(block); 360 else 361 return false; 362 } 363 364 /** 365 Defined only if $(D ParentAllocator) defines $(D deallocateAll). If so, 366 forwards to it and resets the freelist. 367 */ 368 static if (hasMember!(ParentAllocator, "deallocateAll")) deallocateAllFreeList369 bool deallocateAll() 370 { 371 root = null; 372 return parent.deallocateAll(); 373 } 374 375 /** 376 Nonstandard function that minimizes the memory usage of the freelist by 377 freeing each element in turn. Defined only if $(D ParentAllocator) defines 378 $(D deallocate). 379 */ 380 static if (hasMember!(ParentAllocator, "deallocate") && !unchecked) minimizeFreeList381 void minimize() 382 { 383 while (root) 384 { 385 auto nuke = blockFor(root); 386 root = root.next; 387 parent.deallocate(nuke); 388 } 389 } 390 } 391 392 @system unittest 393 { 394 import std.experimental.allocator.gc_allocator : GCAllocator; 395 FreeList!(GCAllocator, 0, 8) fl; 396 assert(fl.root is null); 397 auto b1 = fl.allocate(7); 398 fl.allocate(8); 399 assert(fl.root is null); 400 fl.deallocate(b1); 401 assert(fl.root !is null); 402 fl.allocate(8); 403 assert(fl.root is null); 404 } 405 406 /** 407 Free list built on top of exactly one contiguous block of memory. The block is 408 assumed to have been allocated with $(D ParentAllocator), and is released in 409 $(D ContiguousFreeList)'s destructor (unless $(D ParentAllocator) is $(D 410 NullAllocator)). 411 412 $(D ContiguousFreeList) has most advantages of $(D FreeList) but fewer 413 disadvantages. It has better cache locality because items are closer to one 414 another. It imposes less fragmentation on its parent allocator. 415 416 The disadvantages of $(D ContiguousFreeList) over $(D FreeList) are its pay 417 upfront model (as opposed to $(D FreeList)'s pay-as-you-go approach), and a 418 hard limit on the number of nodes in the list. Thus, a large number of long- 419 lived objects may occupy the entire block, making it unavailable for serving 420 allocations from the free list. However, an absolute cap on the free list size 421 may be beneficial. 422 423 The options $(D minSize == unbounded) and $(D maxSize == unbounded) are not 424 available for $(D ContiguousFreeList). 425 */ 426 struct ContiguousFreeList(ParentAllocator, 427 size_t minSize, size_t maxSize = minSize) 428 { 429 import std.experimental.allocator.building_blocks.null_allocator 430 : NullAllocator; 431 import std.experimental.allocator.building_blocks.stats_collector 432 : StatsCollector, Options; 433 import std.traits : hasMember; 434 import std.typecons : Ternary; 435 436 alias Impl = FreeList!(NullAllocator, minSize, maxSize); 437 enum unchecked = minSize == 0 && maxSize == unbounded; 438 alias Node = Impl.Node; 439 440 alias SParent = StatsCollector!(ParentAllocator, Options.bytesUsed); 441 442 // state 443 /** 444 The parent allocator. Depending on whether $(D ParentAllocator) holds state 445 or not, this is a member variable or an alias for 446 `ParentAllocator.instance`. 447 */ 448 SParent parent; 449 FreeList!(NullAllocator, minSize, maxSize) fl; 450 void[] support; 451 size_t allocated; 452 453 /// Alignment offered. 454 enum uint alignment = (void*).alignof; 455 456 private void initialize(ubyte[] buffer, size_t itemSize = fl.max) 457 { 458 assert(itemSize != unbounded && itemSize != chooseAtRuntime); 459 assert(buffer.ptr.alignedAt(alignment)); 460 immutable available = buffer.length / itemSize; 461 if (available == 0) return; 462 support = buffer; 463 fl.root = cast(Node*) buffer.ptr; 464 auto past = cast(Node*) (buffer.ptr + available * itemSize); 465 for (auto n = fl.root; ; ) 466 { 467 auto next = cast(Node*) (cast(ubyte*) n + itemSize); 468 if (next == past) 469 { 470 n.next = null; 471 break; 472 } 473 assert(next < past); 474 assert(n < next); 475 n.next = next; 476 n = next; 477 } 478 } 479 480 /** 481 Constructors setting up the memory structured as a free list. 482 483 Params: 484 buffer = Buffer to structure as a free list. If $(D ParentAllocator) is not 485 $(D NullAllocator), the buffer is assumed to be allocated by $(D parent) 486 and will be freed in the destructor. 487 parent = Parent allocator. For construction from stateless allocators, use 488 their `instance` static member. 489 bytes = Bytes (not items) to be allocated for the free list. Memory will be 490 allocated during construction and deallocated in the destructor. 491 max = Maximum size eligible for freelisting. Construction with this 492 parameter is defined only if $(D maxSize == chooseAtRuntime) or $(D maxSize 493 == unbounded). 494 min = Minimum size eligible for freelisting. Construction with this 495 parameter is defined only if $(D minSize == chooseAtRuntime). If this 496 condition is met and no $(D min) parameter is present, $(D min) is 497 initialized with $(D max). 498 */ 499 static if (!stateSize!ParentAllocator) thisContiguousFreeList500 this(ubyte[] buffer) 501 { 502 initialize(buffer); 503 } 504 505 /// ditto 506 static if (stateSize!ParentAllocator) thisContiguousFreeList507 this(ParentAllocator parent, ubyte[] buffer) 508 { 509 initialize(buffer); 510 this.parent = SParent(parent); 511 } 512 513 /// ditto 514 static if (!stateSize!ParentAllocator) thisContiguousFreeList515 this(size_t bytes) 516 { 517 initialize(cast(ubyte[])(ParentAllocator.instance.allocate(bytes))); 518 } 519 520 /// ditto 521 static if (stateSize!ParentAllocator) thisContiguousFreeList522 this(ParentAllocator parent, size_t bytes) 523 { 524 initialize(cast(ubyte[])(parent.allocate(bytes))); 525 this.parent = SParent(parent); 526 } 527 528 /// ditto 529 static if (!stateSize!ParentAllocator 530 && (maxSize == chooseAtRuntime || maxSize == unbounded)) thisContiguousFreeList531 this(size_t bytes, size_t max) 532 { 533 static if (maxSize == chooseAtRuntime) fl.max = max; 534 static if (minSize == chooseAtRuntime) fl.min = max; 535 initialize(cast(ubyte[])(parent.allocate(bytes)), max); 536 } 537 538 /// ditto 539 static if (stateSize!ParentAllocator 540 && (maxSize == chooseAtRuntime || maxSize == unbounded)) thisContiguousFreeList541 this(ParentAllocator parent, size_t bytes, size_t max) 542 { 543 static if (maxSize == chooseAtRuntime) fl.max = max; 544 static if (minSize == chooseAtRuntime) fl.min = max; 545 initialize(cast(ubyte[])(parent.allocate(bytes)), max); 546 this.parent = SParent(parent); 547 } 548 549 /// ditto 550 static if (!stateSize!ParentAllocator 551 && (maxSize == chooseAtRuntime || maxSize == unbounded) 552 && minSize == chooseAtRuntime) thisContiguousFreeList553 this(size_t bytes, size_t min, size_t max) 554 { 555 static if (maxSize == chooseAtRuntime) fl.max = max; 556 fl.min = min; 557 initialize(cast(ubyte[])(parent.allocate(bytes)), max); 558 static if (stateSize!ParentAllocator) 559 this.parent = SParent(parent); 560 } 561 562 /// ditto 563 static if (stateSize!ParentAllocator 564 && (maxSize == chooseAtRuntime || maxSize == unbounded) 565 && minSize == chooseAtRuntime) thisContiguousFreeList566 this(ParentAllocator parent, size_t bytes, size_t min, size_t max) 567 { 568 static if (maxSize == chooseAtRuntime) fl.max = max; 569 fl.min = min; 570 initialize(cast(ubyte[])(parent.allocate(bytes)), max); 571 static if (stateSize!ParentAllocator) 572 this.parent = SParent(parent); 573 } 574 575 /** 576 If $(D n) is eligible for freelisting, returns $(D max). Otherwise, returns 577 $(D parent.goodAllocSize(n)). 578 579 Precondition: 580 If set at runtime, $(D min) and/or $(D max) must be initialized 581 appropriately. 582 583 Postcondition: 584 $(D result >= bytes) 585 */ goodAllocSizeContiguousFreeList586 size_t goodAllocSize(size_t n) 587 { 588 if (fl.freeListEligible(n)) return fl.max; 589 return parent.goodAllocSize(n); 590 } 591 592 /** 593 Allocate $(D n) bytes of memory. If $(D n) is eligible for freelist and the 594 freelist is not empty, pops the memory off the free list. In all other 595 cases, uses the parent allocator. 596 */ allocateContiguousFreeList597 void[] allocate(size_t n) 598 { 599 auto result = fl.allocate(n); 600 if (result) 601 { 602 // Only case we care about: eligible sizes allocated from us 603 ++allocated; 604 return result; 605 } 606 // All others, allocate from parent 607 return parent.allocate(n); 608 } 609 610 /** 611 Defined if `ParentAllocator` defines it. Checks whether the block 612 belongs to this allocator. 613 */ 614 static if (hasMember!(SParent, "owns") || unchecked) ownsContiguousFreeList615 Ternary owns(void[] b) 616 { 617 if (support.ptr <= b.ptr && b.ptr < support.ptr + support.length) 618 return Ternary.yes; 619 static if (unchecked) 620 return Ternary.no; 621 else 622 return parent.owns(b); 623 } 624 625 /** 626 Deallocates $(D b). If it's of eligible size, it's put on the free list. 627 Otherwise, it's returned to $(D parent). 628 629 Precondition: $(D b) has been allocated with this allocator, or is $(D 630 null). 631 */ deallocateContiguousFreeList632 bool deallocate(void[] b) 633 { 634 if (support.ptr <= b.ptr && b.ptr < support.ptr + support.length) 635 { 636 // we own this guy 637 import std.conv : text; 638 assert(fl.freeListEligible(b.length), text(b.length)); 639 assert(allocated); 640 --allocated; 641 // Put manually in the freelist 642 auto t = fl.root; 643 fl.root = cast(Node*) b.ptr; 644 fl.root.next = t; 645 return true; 646 } 647 return parent.deallocate(b); 648 } 649 650 /** 651 Deallocates everything from the parent. 652 */ 653 static if (hasMember!(ParentAllocator, "deallocateAll") 654 && stateSize!ParentAllocator) deallocateAllContiguousFreeList655 bool deallocateAll() 656 { 657 bool result = fl.deallocateAll && parent.deallocateAll; 658 allocated = 0; 659 return result; 660 } 661 662 /** 663 Returns `Ternary.yes` if no memory is currently allocated with this 664 allocator, `Ternary.no` otherwise. This method never returns 665 `Ternary.unknown`. 666 */ emptyContiguousFreeList667 Ternary empty() 668 { 669 return Ternary(allocated == 0 && parent.bytesUsed == 0); 670 } 671 } 672 673 /// 674 @safe unittest 675 { 676 import std.experimental.allocator.building_blocks.allocator_list 677 : AllocatorList; 678 import std.experimental.allocator.gc_allocator : GCAllocator; 679 680 import std.experimental.allocator.common : unbounded; 681 682 alias ScalableFreeList = AllocatorList!((n) => 683 ContiguousFreeList!(GCAllocator, 0, unbounded)(4096) 684 ); 685 } 686 687 @system unittest 688 { 689 import std.experimental.allocator.building_blocks.null_allocator 690 : NullAllocator; 691 import std.typecons : Ternary; 692 alias A = ContiguousFreeList!(NullAllocator, 0, 64); 693 auto a = A(new ubyte[1024]); 694 695 assert(a.empty == Ternary.yes); 696 697 assert(a.goodAllocSize(15) == 64); 698 assert(a.goodAllocSize(65) == NullAllocator.instance.goodAllocSize(65)); 699 700 auto b = a.allocate(100); 701 assert(a.empty == Ternary.yes); 702 assert(b.length == 0); 703 a.deallocate(b); 704 b = a.allocate(64); 705 assert(a.empty == Ternary.no); 706 assert(b.length == 64); 707 assert(a.owns(b) == Ternary.yes); 708 assert(a.owns(null) == Ternary.no); 709 a.deallocate(b); 710 } 711 712 @system unittest 713 { 714 import std.experimental.allocator.building_blocks.region : Region; 715 import std.experimental.allocator.gc_allocator : GCAllocator; 716 import std.typecons : Ternary; 717 alias A = ContiguousFreeList!(Region!GCAllocator, 0, 64); 718 auto a = A(Region!GCAllocator(1024 * 4), 1024); 719 720 assert(a.empty == Ternary.yes); 721 722 assert(a.goodAllocSize(15) == 64); 723 assert(a.goodAllocSize(65) == a.parent.goodAllocSize(65)); 724 725 auto b = a.allocate(100); 726 assert(a.empty == Ternary.no); 727 assert(a.allocated == 0); 728 assert(b.length == 100); 729 a.deallocate(b); 730 assert(a.empty == Ternary.yes); 731 b = a.allocate(64); 732 assert(a.empty == Ternary.no); 733 assert(b.length == 64); 734 assert(a.owns(b) == Ternary.yes); 735 assert(a.owns(null) == Ternary.no); 736 a.deallocate(b); 737 } 738 739 @system unittest 740 { 741 import std.experimental.allocator.gc_allocator : GCAllocator; 742 alias A = ContiguousFreeList!(GCAllocator, 64, 64); 743 auto a = A(1024); 744 const b = a.allocate(100); 745 assert(b.length == 100); 746 } 747 748 /** 749 FreeList shared across threads. Allocation and deallocation are lock-free. The 750 parameters have the same semantics as for $(D FreeList). 751 752 $(D expand) is defined to forward to $(D ParentAllocator.expand) 753 (it must be also $(D shared)). 754 */ 755 struct SharedFreeList(ParentAllocator, 756 size_t minSize, size_t maxSize = minSize, size_t approxMaxNodes = unbounded) 757 { 758 import std.conv : text; 759 import std.exception : enforce; 760 import std.traits : hasMember; 761 762 static assert(approxMaxNodes, "approxMaxNodes must not be null."); 763 static assert(minSize != unbounded, "Use minSize = 0 for no low bound."); 764 static assert(maxSize >= (void*).sizeof, 765 "Maximum size must accommodate a pointer."); 766 767 import core.atomic : atomicOp, cas; 768 import core.internal.spinlock : SpinLock; 769 770 private enum unchecked = minSize == 0 && maxSize == unbounded; 771 772 static if (minSize != chooseAtRuntime) 773 { 774 alias min = minSize; 775 } 776 else 777 { 778 private shared size_t _min = chooseAtRuntime; minSharedFreeList779 @property size_t min() const shared 780 { 781 assert(_min != chooseAtRuntime); 782 return _min; 783 } minSharedFreeList784 @property void min(size_t x) shared 785 { 786 enforce(x <= max); 787 enforce(cas(&_min, chooseAtRuntime, x), 788 "SharedFreeList.min must be initialized exactly once."); 789 } 790 static if (maxSize == chooseAtRuntime) 791 { 792 // Both bounds can be set, provide one function for setting both in 793 // one shot. setBoundsSharedFreeList794 void setBounds(size_t low, size_t high) shared 795 { 796 enforce(low <= high && high >= (void*).sizeof); 797 enforce(cas(&_min, chooseAtRuntime, low), 798 "SharedFreeList.min must be initialized exactly once."); 799 enforce(cas(&_max, chooseAtRuntime, high), 800 "SharedFreeList.max must be initialized exactly once."); 801 } 802 } 803 } 804 tooSmallSharedFreeList805 private bool tooSmall(size_t n) const shared 806 { 807 static if (minSize == 0) return false; 808 else static if (minSize == chooseAtRuntime) return n < _min; 809 else return n < minSize; 810 } 811 812 static if (maxSize != chooseAtRuntime) 813 { 814 alias max = maxSize; 815 } 816 else 817 { 818 private shared size_t _max = chooseAtRuntime; maxSharedFreeList819 @property size_t max() const shared { return _max; } maxSharedFreeList820 @property void max(size_t x) shared 821 { 822 enforce(x >= min && x >= (void*).sizeof); 823 enforce(cas(&_max, chooseAtRuntime, x), 824 "SharedFreeList.max must be initialized exactly once."); 825 } 826 } 827 tooLargeSharedFreeList828 private bool tooLarge(size_t n) const shared 829 { 830 static if (maxSize == unbounded) return false; 831 else static if (maxSize == chooseAtRuntime) return n > _max; 832 else return n > maxSize; 833 } 834 freeListEligibleSharedFreeList835 private bool freeListEligible(size_t n) const shared 836 { 837 static if (minSize == maxSize && minSize != chooseAtRuntime) 838 return n == maxSize; 839 else return !tooSmall(n) && !tooLarge(n); 840 } 841 842 static if (approxMaxNodes != chooseAtRuntime) 843 { 844 alias approxMaxLength = approxMaxNodes; 845 } 846 else 847 { 848 private shared size_t _approxMaxLength = chooseAtRuntime; approxMaxLengthSharedFreeList849 @property size_t approxMaxLength() const shared { return _approxMaxLength; } approxMaxLengthSharedFreeList850 @property void approxMaxLength(size_t x) shared { _approxMaxLength = enforce(x); } 851 } 852 853 static if (approxMaxNodes != unbounded) 854 { 855 private shared size_t nodes; incNodesSharedFreeList856 private void incNodes() shared 857 { 858 atomicOp!("+=")(nodes, 1); 859 } decNodesSharedFreeList860 private void decNodes() shared 861 { 862 assert(nodes); 863 atomicOp!("-=")(nodes, 1); 864 } resetNodesSharedFreeList865 private void resetNodes() shared 866 { 867 nodes = 0; 868 } nodesFullSharedFreeList869 private bool nodesFull() shared 870 { 871 return nodes >= approxMaxLength; 872 } 873 } 874 else 875 { incNodesSharedFreeList876 private static void incNodes() { } decNodesSharedFreeList877 private static void decNodes() { } resetNodesSharedFreeList878 private static void resetNodes() { } 879 private enum bool nodesFull = false; 880 } 881 versionSharedFreeList882 version (StdDdoc) 883 { 884 /** 885 Properties for getting (and possibly setting) the bounds. Setting bounds 886 is allowed only once , and before any allocation takes place. Otherwise, 887 the primitives have the same semantics as those of $(D FreeList). 888 */ 889 @property size_t min(); 890 /// Ditto 891 @property void min(size_t newMinSize); 892 /// Ditto 893 @property size_t max(); 894 /// Ditto 895 @property void max(size_t newMaxSize); 896 /// Ditto 897 void setBounds(size_t newMin, size_t newMax); 898 /// 899 @safe unittest 900 { 901 import std.experimental.allocator.common : chooseAtRuntime; 902 import std.experimental.allocator.mallocator : Mallocator; 903 904 shared SharedFreeList!(Mallocator, chooseAtRuntime, chooseAtRuntime) a; 905 // Set the maxSize first so setting the minSize doesn't throw 906 a.max = 128; 907 a.min = 64; 908 a.setBounds(64, 128); // equivalent 909 assert(a.max == 128); 910 assert(a.min == 64); 911 } 912 913 /** 914 Properties for getting (and possibly setting) the approximate maximum length of a shared freelist. 915 */ 916 @property size_t approxMaxLength() const shared; 917 /// ditto 918 @property void approxMaxLength(size_t x) shared; 919 /// 920 @safe unittest 921 { 922 import std.experimental.allocator.common : chooseAtRuntime; 923 import std.experimental.allocator.mallocator : Mallocator; 924 925 shared SharedFreeList!(Mallocator, 50, 50, chooseAtRuntime) a; 926 // Set the maxSize first so setting the minSize doesn't throw 927 a.approxMaxLength = 128; 928 assert(a.approxMaxLength == 128); 929 a.approxMaxLength = 1024; 930 assert(a.approxMaxLength == 1024); 931 a.approxMaxLength = 1; 932 assert(a.approxMaxLength == 1); 933 } 934 } 935 936 /** 937 The parent allocator. Depending on whether $(D ParentAllocator) holds state 938 or not, this is a member variable or an alias for 939 `ParentAllocator.instance`. 940 */ 941 static if (stateSize!ParentAllocator) shared ParentAllocator parent; 942 else alias parent = ParentAllocator.instance; 943 944 mixin(forwardToMember("parent", "expand")); 945 946 private SpinLock lock; 947 948 private struct Node { Node* next; } 949 static assert(ParentAllocator.alignment >= Node.alignof); 950 private Node* _root; 951 952 /// Standard primitives. 953 enum uint alignment = ParentAllocator.alignment; 954 955 /// Ditto goodAllocSizeSharedFreeList956 size_t goodAllocSize(size_t bytes) shared 957 { 958 if (freeListEligible(bytes)) return maxSize == unbounded ? bytes : max; 959 return parent.goodAllocSize(bytes); 960 } 961 962 /// Ditto 963 static if (hasMember!(ParentAllocator, "owns")) ownsSharedFreeList964 Ternary owns(void[] b) shared const 965 { 966 return parent.owns(b); 967 } 968 969 /// Ditto 970 static if (hasMember!(ParentAllocator, "reallocate")) reallocateSharedFreeList971 bool reallocate(ref void[] b, size_t s) shared 972 { 973 return parent.reallocate(b, s); 974 } 975 976 /// Ditto allocateSharedFreeList977 void[] allocate(size_t bytes) shared 978 { 979 assert(bytes < size_t.max / 2); 980 if (!freeListEligible(bytes)) return parent.allocate(bytes); 981 if (maxSize != unbounded) bytes = max; 982 983 // Try to pop off the freelist 984 lock.lock(); 985 if (!_root) 986 { 987 lock.unlock(); 988 return allocateFresh(bytes); 989 } 990 else 991 { 992 auto oldRoot = _root; 993 _root = _root.next; 994 decNodes(); 995 lock.unlock(); 996 return (cast(ubyte*) oldRoot)[0 .. bytes]; 997 } 998 } 999 allocateFreshSharedFreeList1000 private void[] allocateFresh(const size_t bytes) shared 1001 { 1002 assert(bytes == max || max == unbounded); 1003 return parent.allocate(bytes); 1004 } 1005 1006 /// Ditto deallocateSharedFreeList1007 bool deallocate(void[] b) shared 1008 { 1009 if (!nodesFull && freeListEligible(b.length)) 1010 { 1011 auto newRoot = cast(shared Node*) b.ptr; 1012 lock.lock(); 1013 newRoot.next = _root; 1014 _root = newRoot; 1015 incNodes(); 1016 lock.unlock(); 1017 return true; 1018 } 1019 static if (hasMember!(ParentAllocator, "deallocate")) 1020 return parent.deallocate(b); 1021 else 1022 return false; 1023 } 1024 1025 /// Ditto deallocateAllSharedFreeList1026 bool deallocateAll() shared 1027 { 1028 bool result = false; 1029 lock.lock(); 1030 scope(exit) lock.unlock(); 1031 static if (hasMember!(ParentAllocator, "deallocateAll")) 1032 { 1033 result = parent.deallocateAll(); 1034 } 1035 else static if (hasMember!(ParentAllocator, "deallocate")) 1036 { 1037 result = true; 1038 for (auto n = _root; n;) 1039 { 1040 auto tmp = n.next; 1041 if (!parent.deallocate((cast(ubyte*) n)[0 .. max])) 1042 result = false; 1043 n = tmp; 1044 } 1045 } 1046 _root = null; 1047 resetNodes(); 1048 return result; 1049 } 1050 1051 /** 1052 Nonstandard function that minimizes the memory usage of the freelist by 1053 freeing each element in turn. Defined only if $(D ParentAllocator) defines 1054 $(D deallocate). 1055 */ 1056 static if (hasMember!(ParentAllocator, "deallocate") && !unchecked) minimizeSharedFreeList1057 void minimize() shared 1058 { 1059 lock.lock(); 1060 scope(exit) lock.unlock(); 1061 1062 for (auto n = _root; n;) 1063 { 1064 auto tmp = n.next; 1065 parent.deallocate((cast(ubyte*) n)[0 .. max]); 1066 n = tmp; 1067 } 1068 1069 _root = null; 1070 resetNodes(); 1071 } 1072 } 1073 1074 @system unittest 1075 { 1076 import core.thread : ThreadGroup; 1077 import std.algorithm.comparison : equal; 1078 import std.experimental.allocator.mallocator : Mallocator; 1079 import std.range : repeat; 1080 1081 static shared SharedFreeList!(Mallocator, 64, 128, 10) a; 1082 1083 assert(a.goodAllocSize(1) == platformAlignment); 1084 1085 auto b = a.allocate(96); 1086 a.deallocate(b); 1087 fun()1088 void fun() 1089 { 1090 auto b = cast(size_t[]) a.allocate(96); 1091 b[] = cast(size_t) &b; 1092 1093 assert(b.equal(repeat(cast(size_t) &b, b.length))); 1094 a.deallocate(b); 1095 } 1096 1097 auto tg = new ThreadGroup; 1098 foreach (i; 0 .. 20) 1099 { 1100 tg.create(&fun); 1101 } 1102 1103 tg.joinAll(); 1104 } 1105 1106 @system unittest 1107 { 1108 import std.experimental.allocator.mallocator : Mallocator; 1109 static shared SharedFreeList!(Mallocator, 64, 128, 10) a; 1110 auto b = a.allocate(100); 1111 a.deallocate(b); 1112 assert(a.nodes == 1); 1113 b = []; 1114 a.deallocateAll(); 1115 assert(a.nodes == 0); 1116 } 1117 1118 @system unittest 1119 { 1120 import std.experimental.allocator.mallocator : Mallocator; 1121 static shared SharedFreeList!(Mallocator, 64, 128, 10) a; 1122 auto b = a.allocate(100); 1123 auto c = a.allocate(100); 1124 a.deallocate(c); 1125 assert(a.nodes == 1); 1126 c = []; 1127 a.minimize(); 1128 assert(a.nodes == 0); 1129 a.deallocate(b); 1130 assert(a.nodes == 1); 1131 b = []; 1132 a.minimize(); 1133 assert(a.nodes == 0); 1134 } 1135 1136 @system unittest 1137 { 1138 import std.experimental.allocator.mallocator : Mallocator; 1139 static shared SharedFreeList!(Mallocator, 64, 128, 10) a; 1140 auto b = a.allocate(100); 1141 auto c = a.allocate(100); 1142 assert(a.nodes == 0); 1143 a.deallocate(b); 1144 a.deallocate(c); 1145 assert(a.nodes == 2); 1146 b = []; 1147 c = []; 1148 a.minimize(); 1149 assert(a.nodes == 0); 1150 } 1151 1152 @system unittest 1153 { 1154 import std.experimental.allocator.mallocator : Mallocator; 1155 shared SharedFreeList!(Mallocator, chooseAtRuntime, chooseAtRuntime) a; 1156 scope(exit) a.deallocateAll(); 1157 auto c = a.allocate(64); 1158 assert(a.reallocate(c, 96)); 1159 assert(c.length == 96); 1160 a.deallocate(c); 1161 } 1162 1163 @system unittest 1164 { 1165 import std.experimental.allocator.mallocator : Mallocator; 1166 shared SharedFreeList!(Mallocator, chooseAtRuntime, chooseAtRuntime, chooseAtRuntime) a; 1167 scope(exit) a.deallocateAll; 1168 a.allocate(64); 1169 } 1170 1171 @system unittest 1172 { 1173 import std.experimental.allocator.mallocator : Mallocator; 1174 shared SharedFreeList!(Mallocator, 30, 40) a; 1175 scope(exit) a.deallocateAll; 1176 a.allocate(64); 1177 } 1178 1179 @system unittest 1180 { 1181 import std.experimental.allocator.mallocator : Mallocator; 1182 shared SharedFreeList!(Mallocator, 30, 40, chooseAtRuntime) a; 1183 scope(exit) a.deallocateAll; 1184 a.allocate(64); 1185 } 1186 1187 @system unittest 1188 { 1189 // Pull request #5556 1190 import std.experimental.allocator.mallocator : Mallocator; 1191 shared SharedFreeList!(Mallocator, 0, chooseAtRuntime) a; 1192 scope(exit) a.deallocateAll; 1193 a.max = 64; 1194 a.allocate(64); 1195 } 1196 1197 @system unittest 1198 { 1199 // Pull request #5556 1200 import std.experimental.allocator.mallocator : Mallocator; 1201 shared SharedFreeList!(Mallocator, chooseAtRuntime, 64) a; 1202 scope(exit) a.deallocateAll; 1203 a.min = 32; 1204 a.allocate(64); 1205 } 1206