1 // Written in the D programming language. 2 /** 3 Source: $(PHOBOSSRC std/experimental/allocator/building_blocks/region.d) 4 */ 5 module std.experimental.allocator.building_blocks.region; 6 7 import std.experimental.allocator.building_blocks.null_allocator; 8 import std.experimental.allocator.common; 9 import std.typecons : Flag, Yes, No; 10 11 version (OSX) 12 version = Darwin; 13 else version (iOS) 14 version = Darwin; 15 else version (TVOS) 16 version = Darwin; 17 else version (WatchOS) 18 version = Darwin; 19 20 /** 21 A `Region` allocator allocates memory straight from one contiguous chunk. 22 There is no deallocation, and once the region is full, allocation requests 23 return `null`. Therefore, `Region`s are often used (a) in conjunction with 24 more sophisticated allocators; or (b) for batch-style very fast allocations 25 that deallocate everything at once. 26 27 The region only stores three pointers, corresponding to the current position in 28 the store and the limits. One allocation entails rounding up the allocation 29 size for alignment purposes, bumping the current pointer, and comparing it 30 against the limit. 31 32 `Region` deallocates the chunk of memory during destruction. 33 34 The `minAlign` parameter establishes alignment. If $(D minAlign > 1), the 35 sizes of all allocation requests are rounded up to a multiple of `minAlign`. 36 Applications aiming at maximum speed may want to choose $(D minAlign = 1) and 37 control alignment externally. 38 39 */ 40 struct Region(ParentAllocator, 41 uint minAlign = platformAlignment, 42 Flag!"growDownwards" growDownwards = No.growDownwards) 43 { 44 static assert(minAlign.isGoodStaticAlignment); 45 static assert(ParentAllocator.alignment >= minAlign); 46 47 import std.traits : hasMember; 48 import std.typecons : Ternary; 49 50 // state 51 /** 52 The _parent allocator. Depending on whether `ParentAllocator` holds state 53 or not, this is a member variable or an alias for 54 `ParentAllocator.instance`. 55 */ 56 static if (stateSize!ParentAllocator) 57 { 58 ParentAllocator parent; 59 } 60 else 61 { 62 alias parent = ParentAllocator.instance; 63 } 64 65 private BorrowedRegion!(minAlign, growDownwards) _impl; 66 67 private void* roundedBegin() const pure nothrow @trusted @nogc 68 { 69 return _impl.roundedBegin; 70 } 71 72 private void* roundedEnd() const pure nothrow @trusted @nogc 73 { 74 return _impl.roundedEnd; 75 } 76 /** 77 Constructs a region backed by a user-provided store. 78 Assumes the memory was allocated with `ParentAllocator`. 79 80 Params: 81 store = User-provided store backing up the region. Assumed to have been 82 allocated with `ParentAllocator`. 83 n = Bytes to allocate using `ParentAllocator`. If `parent.allocate(n)` 84 returns `null`, the region will be initialized as empty (correctly 85 initialized but unable to allocate). 86 */ 87 this(ubyte[] store) pure nothrow @nogc 88 { 89 _impl = store; 90 } 91 92 /// Ditto 93 static if (!stateSize!ParentAllocator) 94 this(size_t n) 95 { 96 this(cast(ubyte[]) (parent.allocate(n.roundUpToAlignment(alignment)))); 97 } 98 99 /// Ditto 100 static if (stateSize!ParentAllocator) 101 this(ParentAllocator parent, size_t n) 102 { 103 this.parent = parent; 104 this(cast(ubyte[]) (parent.allocate(n.roundUpToAlignment(alignment)))); 105 } 106 107 /* 108 TODO: The postblit of `BasicRegion` should be disabled because such objects 109 should not be copied around naively. 110 */ 111 112 /** 113 If `ParentAllocator` defines `deallocate`, the region defines a destructor 114 that uses `ParentAllocator.deallocate` to free the memory chunk. 115 */ 116 static if (hasMember!(ParentAllocator, "deallocate")) 117 ~this() 118 { 119 with (_impl) parent.deallocate(_begin[0 .. _end - _begin]); 120 } 121 122 /** 123 Rounds the given size to a multiple of the `alignment` 124 */ 125 size_t goodAllocSize(size_t n) const pure nothrow @safe @nogc 126 { 127 return _impl.goodAllocSize(n); 128 } 129 130 /** 131 Alignment offered. 132 */ 133 alias alignment = minAlign; 134 135 /** 136 Allocates `n` bytes of memory. The shortest path involves an alignment 137 adjustment (if $(D alignment > 1)), an increment, and a comparison. 138 139 Params: 140 n = number of bytes to allocate 141 142 Returns: 143 A properly-aligned buffer of size `n` or `null` if request could not 144 be satisfied. 145 */ 146 void[] allocate(size_t n) pure nothrow @trusted @nogc 147 { 148 return _impl.allocate(n); 149 } 150 151 /** 152 Allocates `n` bytes of memory aligned at alignment `a`. 153 154 Params: 155 n = number of bytes to allocate 156 a = alignment for the allocated block 157 158 Returns: 159 Either a suitable block of `n` bytes aligned at `a`, or `null`. 160 */ 161 void[] alignedAllocate(size_t n, uint a) pure nothrow @trusted @nogc 162 { 163 return _impl.alignedAllocate(n, a); 164 } 165 166 /// Allocates and returns all memory available to this region. 167 void[] allocateAll() pure nothrow @trusted @nogc 168 { 169 return _impl.allocateAll; 170 } 171 172 /** 173 Expands an allocated block in place. Expansion will succeed only if the 174 block is the last allocated. Defined only if `growDownwards` is 175 `No.growDownwards`. 176 */ 177 static if (growDownwards == No.growDownwards) 178 bool expand(ref void[] b, size_t delta) pure nothrow @safe @nogc 179 { 180 return _impl.expand(b, delta); 181 } 182 183 /** 184 Deallocates `b`. This works only if `b` was obtained as the last call 185 to `allocate`; otherwise (i.e. another allocation has occurred since) it 186 does nothing. 187 188 Params: 189 b = Block previously obtained by a call to `allocate` against this 190 allocator (`null` is allowed). 191 */ 192 bool deallocate(void[] b) pure nothrow @nogc 193 { 194 return _impl.deallocate(b); 195 } 196 197 /** 198 Deallocates all memory allocated by this region, which can be subsequently 199 reused for new allocations. 200 */ 201 bool deallocateAll() pure nothrow @nogc 202 { 203 return _impl.deallocateAll; 204 } 205 206 /** 207 Queries whether `b` has been allocated with this region. 208 209 Params: 210 b = Arbitrary block of memory (`null` is allowed; `owns(null)` returns 211 `false`). 212 213 Returns: 214 `true` if `b` has been allocated with this region, `false` otherwise. 215 */ 216 Ternary owns(const void[] b) const pure nothrow @trusted @nogc 217 { 218 return _impl.owns(b); 219 } 220 221 /** 222 Returns `Ternary.yes` if no memory has been allocated in this region, 223 `Ternary.no` otherwise. (Never returns `Ternary.unknown`.) 224 */ 225 Ternary empty() const pure nothrow @safe @nogc 226 { 227 return _impl.empty; 228 } 229 230 /// Nonstandard property that returns bytes available for allocation. 231 size_t available() const @safe pure nothrow @nogc 232 { 233 return _impl.available; 234 } 235 } 236 237 /// 238 @system nothrow unittest 239 { 240 import std.algorithm.comparison : max; 241 import std.experimental.allocator.building_blocks.allocator_list 242 : AllocatorList; 243 import std.experimental.allocator.mallocator : Mallocator; 244 import std.typecons : Ternary; 245 // Create a scalable list of regions. Each gets at least 1MB at a time by 246 // using malloc. 247 auto batchAllocator = AllocatorList!( 248 (size_t n) => Region!Mallocator(max(n, 1024 * 1024)) 249 )(); 250 assert(batchAllocator.empty == Ternary.yes); 251 auto b = batchAllocator.allocate(101); 252 assert(b.length == 101); 253 assert(batchAllocator.empty == Ternary.no); 254 // This will cause a second allocation 255 b = batchAllocator.allocate(2 * 1024 * 1024); 256 assert(b.length == 2 * 1024 * 1024); 257 // Destructor will free the memory 258 } 259 260 @system nothrow @nogc unittest 261 { 262 import std.experimental.allocator.mallocator : Mallocator; 263 import std.typecons : Ternary; 264 265 static void testAlloc(Allocator)(ref Allocator a) 266 { 267 assert((() pure nothrow @safe @nogc => a.empty)() == Ternary.yes); 268 const b = a.allocate(101); 269 assert(b.length == 101); 270 assert((() nothrow @safe @nogc => a.owns(b))() == Ternary.yes); 271 272 // Ensure deallocate inherits from parent allocators 273 auto c = a.allocate(42); 274 assert(c.length == 42); 275 assert((() nothrow @nogc => a.deallocate(c))()); 276 assert((() pure nothrow @safe @nogc => a.empty)() == Ternary.no); 277 } 278 279 // Create a 64 KB region allocated with malloc 280 auto reg = Region!(Mallocator, Mallocator.alignment, 281 Yes.growDownwards)(1024 * 64); 282 testAlloc(reg); 283 284 // Create a 64 KB shared region allocated with malloc 285 auto sharedReg = SharedRegion!(Mallocator, Mallocator.alignment, 286 Yes.growDownwards)(1024 * 64); 287 testAlloc(sharedReg); 288 } 289 290 @system nothrow @nogc unittest 291 { 292 // test 'this(ubyte[] store)' constructed regions properly clean up 293 // their inner storage after destruction 294 import std.experimental.allocator.mallocator : Mallocator; 295 296 static shared struct LocalAllocator 297 { 298 nothrow @nogc: 299 enum alignment = Mallocator.alignment; 300 void[] buf; 301 bool deallocate(void[] b) 302 { 303 assert(buf.ptr == b.ptr && buf.length == b.length); 304 return true; 305 } 306 307 void[] allocate(size_t n) 308 { 309 return null; 310 } 311 312 } 313 314 enum bufLen = 10 * Mallocator.alignment; 315 void[] tmp = Mallocator.instance.allocate(bufLen); 316 317 LocalAllocator a; 318 a.buf = cast(typeof(a.buf)) tmp[1 .. $]; 319 320 auto reg = Region!(LocalAllocator, Mallocator.alignment, 321 Yes.growDownwards)(cast(ubyte[]) a.buf); 322 auto sharedReg = SharedRegion!(LocalAllocator, Mallocator.alignment, 323 Yes.growDownwards)(cast(ubyte[]) a.buf); 324 reg.parent = a; 325 sharedReg.parent = a; 326 327 Mallocator.instance.deallocate(tmp); 328 } 329 330 version (StdUnittest) 331 @system unittest 332 { 333 import std.experimental.allocator.mallocator : Mallocator; 334 335 testAllocator!(() => Region!(Mallocator)(1024 * 64)); 336 testAllocator!(() => Region!(Mallocator, Mallocator.alignment, Yes.growDownwards)(1024 * 64)); 337 338 testAllocator!(() => SharedRegion!(Mallocator)(1024 * 64)); 339 testAllocator!(() => SharedRegion!(Mallocator, Mallocator.alignment, Yes.growDownwards)(1024 * 64)); 340 } 341 342 @system nothrow @nogc unittest 343 { 344 import std.experimental.allocator.mallocator : Mallocator; 345 346 auto reg = Region!(Mallocator)(1024 * 64); 347 auto b = reg.allocate(101); 348 assert(b.length == 101); 349 assert((() pure nothrow @safe @nogc => reg.expand(b, 20))()); 350 assert((() pure nothrow @safe @nogc => reg.expand(b, 73))()); 351 assert((() pure nothrow @safe @nogc => !reg.expand(b, 1024 * 64))()); 352 assert((() nothrow @nogc => reg.deallocateAll())()); 353 } 354 355 /** 356 A `BorrowedRegion` allocates directly from a user-provided block of memory. 357 358 Unlike a `Region`, a `BorrowedRegion` does not own the memory it allocates from 359 and will not deallocate that memory upon destruction. Instead, it is the user's 360 responsibility to ensure that the memory is properly disposed of. 361 362 In all other respects, a `BorrowedRegion` behaves exactly like a `Region`. 363 */ 364 struct BorrowedRegion(uint minAlign = platformAlignment, 365 Flag!"growDownwards" growDownwards = No.growDownwards) 366 { 367 static assert(minAlign.isGoodStaticAlignment); 368 369 import std.typecons : Ternary; 370 371 // state 372 private void* _current, _begin, _end; 373 374 private void* roundedBegin() const pure nothrow @trusted @nogc 375 { 376 return cast(void*) roundUpToAlignment(cast(size_t) _begin, alignment); 377 } 378 379 private void* roundedEnd() const pure nothrow @trusted @nogc 380 { 381 return cast(void*) roundDownToAlignment(cast(size_t) _end, alignment); 382 } 383 384 /** 385 Constructs a region backed by a user-provided store. 386 387 Params: 388 store = User-provided store backing up the region. 389 */ 390 this(ubyte[] store) pure nothrow @nogc 391 { 392 _begin = store.ptr; 393 _end = store.ptr + store.length; 394 static if (growDownwards) 395 _current = roundedEnd(); 396 else 397 _current = roundedBegin(); 398 } 399 400 /* 401 TODO: The postblit of `BorrowedRegion` should be disabled because such objects 402 should not be copied around naively. 403 */ 404 405 /** 406 Rounds the given size to a multiple of the `alignment` 407 */ 408 size_t goodAllocSize(size_t n) const pure nothrow @safe @nogc 409 { 410 return n.roundUpToAlignment(alignment); 411 } 412 413 /** 414 Alignment offered. 415 */ 416 alias alignment = minAlign; 417 418 /** 419 Allocates `n` bytes of memory. The shortest path involves an alignment 420 adjustment (if $(D alignment > 1)), an increment, and a comparison. 421 422 Params: 423 n = number of bytes to allocate 424 425 Returns: 426 A properly-aligned buffer of size `n` or `null` if request could not 427 be satisfied. 428 */ 429 void[] allocate(size_t n) pure nothrow @trusted @nogc 430 { 431 const rounded = goodAllocSize(n); 432 if (n == 0 || rounded < n || available < rounded) return null; 433 434 static if (growDownwards) 435 { 436 assert(available >= rounded); 437 auto result = (_current - rounded)[0 .. n]; 438 assert(result.ptr >= _begin); 439 _current = result.ptr; 440 assert(owns(result) == Ternary.yes); 441 } 442 else 443 { 444 auto result = _current[0 .. n]; 445 _current += rounded; 446 } 447 448 return result; 449 } 450 451 /** 452 Allocates `n` bytes of memory aligned at alignment `a`. 453 454 Params: 455 n = number of bytes to allocate 456 a = alignment for the allocated block 457 458 Returns: 459 Either a suitable block of `n` bytes aligned at `a`, or `null`. 460 */ 461 void[] alignedAllocate(size_t n, uint a) pure nothrow @trusted @nogc 462 { 463 import std.math.traits : isPowerOf2; 464 assert(a.isPowerOf2); 465 466 const rounded = goodAllocSize(n); 467 if (n == 0 || rounded < n || available < rounded) return null; 468 469 static if (growDownwards) 470 { 471 auto tmpCurrent = _current - rounded; 472 auto result = tmpCurrent.alignDownTo(a); 473 if (result <= tmpCurrent && result >= _begin) 474 { 475 _current = result; 476 return cast(void[]) result[0 .. n]; 477 } 478 } 479 else 480 { 481 // Just bump the pointer to the next good allocation 482 auto newCurrent = _current.alignUpTo(a); 483 if (newCurrent < _current || newCurrent > _end) 484 return null; 485 486 auto save = _current; 487 _current = newCurrent; 488 auto result = allocate(n); 489 if (result.ptr) 490 { 491 assert(result.length == n); 492 return result; 493 } 494 // Failed, rollback 495 _current = save; 496 } 497 return null; 498 } 499 500 /// Allocates and returns all memory available to this region. 501 void[] allocateAll() pure nothrow @trusted @nogc 502 { 503 static if (growDownwards) 504 { 505 auto result = _begin[0 .. available]; 506 _current = _begin; 507 } 508 else 509 { 510 auto result = _current[0 .. available]; 511 _current = _end; 512 } 513 return result; 514 } 515 516 /** 517 Expands an allocated block in place. Expansion will succeed only if the 518 block is the last allocated. Defined only if `growDownwards` is 519 `No.growDownwards`. 520 */ 521 static if (growDownwards == No.growDownwards) 522 bool expand(ref void[] b, size_t delta) pure nothrow @safe @nogc 523 { 524 assert(owns(b) == Ternary.yes || b is null); 525 assert((() @trusted => b.ptr + b.length <= _current)() || b is null); 526 if (b is null || delta == 0) return delta == 0; 527 auto newLength = b.length + delta; 528 if ((() @trusted => _current < b.ptr + b.length + alignment)()) 529 { 530 immutable currentGoodSize = this.goodAllocSize(b.length); 531 immutable newGoodSize = this.goodAllocSize(newLength); 532 immutable goodDelta = newGoodSize - currentGoodSize; 533 // This was the last allocation! Allocate some more and we're done. 534 if (goodDelta == 0 535 || (() @trusted => allocate(goodDelta).length == goodDelta)()) 536 { 537 b = (() @trusted => b.ptr[0 .. newLength])(); 538 assert((() @trusted => _current < b.ptr + b.length + alignment)()); 539 return true; 540 } 541 } 542 return false; 543 } 544 545 /** 546 Deallocates `b`. This works only if `b` was obtained as the last call 547 to `allocate`; otherwise (i.e. another allocation has occurred since) it 548 does nothing. 549 550 Params: 551 b = Block previously obtained by a call to `allocate` against this 552 allocator (`null` is allowed). 553 */ 554 bool deallocate(void[] b) pure nothrow @nogc 555 { 556 assert(owns(b) == Ternary.yes || b.ptr is null); 557 auto rounded = goodAllocSize(b.length); 558 static if (growDownwards) 559 { 560 if (b.ptr == _current) 561 { 562 _current += rounded; 563 return true; 564 } 565 } 566 else 567 { 568 if (b.ptr + rounded == _current) 569 { 570 assert(b.ptr !is null || _current is null); 571 _current = b.ptr; 572 return true; 573 } 574 } 575 return false; 576 } 577 578 /** 579 Deallocates all memory allocated by this region, which can be subsequently 580 reused for new allocations. 581 */ 582 bool deallocateAll() pure nothrow @nogc 583 { 584 static if (growDownwards) 585 { 586 _current = roundedEnd(); 587 } 588 else 589 { 590 _current = roundedBegin(); 591 } 592 return true; 593 } 594 595 /** 596 Queries whether `b` has been allocated with this region. 597 598 Params: 599 b = Arbitrary block of memory (`null` is allowed; `owns(null)` returns 600 `false`). 601 602 Returns: 603 `true` if `b` has been allocated with this region, `false` otherwise. 604 */ 605 Ternary owns(const void[] b) const pure nothrow @trusted @nogc 606 { 607 return Ternary(b && (&b[0] >= _begin) && (&b[0] + b.length <= _end)); 608 } 609 610 /** 611 Returns `Ternary.yes` if no memory has been allocated in this region, 612 `Ternary.no` otherwise. (Never returns `Ternary.unknown`.) 613 */ 614 Ternary empty() const pure nothrow @safe @nogc 615 { 616 static if (growDownwards) 617 return Ternary(_current == roundedEnd()); 618 else 619 return Ternary(_current == roundedBegin()); 620 } 621 622 /// Nonstandard property that returns bytes available for allocation. 623 size_t available() const @safe pure nothrow @nogc 624 { 625 static if (growDownwards) 626 { 627 return _current - _begin; 628 } 629 else 630 { 631 return _end - _current; 632 } 633 } 634 } 635 636 /// 637 @system nothrow @nogc unittest 638 { 639 import std.typecons : Ternary; 640 641 ubyte[1024] store; 642 auto myRegion = BorrowedRegion!(1)(store[]); 643 644 assert(myRegion.empty == Ternary.yes); 645 assert(myRegion.available == store.length); 646 647 void[] b = myRegion.allocate(101); 648 649 assert(b.length == 101); 650 assert(myRegion.empty == Ternary.no); 651 assert(myRegion.owns(b) == Ternary.yes); 652 assert(myRegion.available == store.length - b.length); 653 654 void[] b2 = myRegion.allocate(256); 655 656 // Can only free the most recent allocation 657 assert(myRegion.deallocate(b) == false); 658 assert(myRegion.deallocate(b2) == true); 659 660 myRegion.deallocateAll(); 661 662 assert(myRegion.empty == Ternary.yes); 663 } 664 665 @system nothrow @nogc unittest 666 { 667 import std.experimental.allocator.mallocator : AlignedMallocator; 668 import std.typecons : Ternary; 669 670 ubyte[] buf = cast(ubyte[]) AlignedMallocator.instance.alignedAllocate(64, 64); 671 auto reg = BorrowedRegion!(64, Yes.growDownwards)(buf); 672 assert(reg.alignedAllocate(10, 32).length == 10); 673 assert(!reg.available); 674 } 675 676 /** 677 678 `InSituRegion` is a convenient region that carries its storage within itself 679 (in the form of a statically-sized array). 680 681 The first template argument is the size of the region and the second is the 682 needed alignment. Depending on the alignment requested and platform details, 683 the actual available storage may be smaller than the compile-time parameter. To 684 make sure that at least `n` bytes are available in the region, use 685 $(D InSituRegion!(n + a - 1, a)). 686 687 Given that the most frequent use of `InSituRegion` is as a stack allocator, it 688 allocates starting at the end on systems where stack grows downwards, such that 689 hot memory is used first. 690 691 */ 692 struct InSituRegion(size_t size, size_t minAlign = platformAlignment) 693 { 694 import std.algorithm.comparison : max; 695 import std.conv : to; 696 import std.traits : hasMember; 697 import std.typecons : Ternary; 698 import core.thread.types : isStackGrowingDown; 699 700 static assert(minAlign.isGoodStaticAlignment); 701 static assert(size >= minAlign); 702 703 static if (isStackGrowingDown) 704 enum growDownwards = Yes.growDownwards; 705 else 706 enum growDownwards = No.growDownwards; 707 708 @disable this(this); 709 710 // state { 711 private BorrowedRegion!(minAlign, growDownwards) _impl; 712 union 713 { 714 private ubyte[size] _store = void; 715 private double _forAlignmentOnly1; 716 } 717 // } 718 719 /** 720 An alias for `minAlign`, which must be a valid alignment (nonzero power 721 of 2). The start of the region and all allocation requests will be rounded 722 up to a multiple of the alignment. 723 724 ---- 725 InSituRegion!(4096) a1; 726 assert(a1.alignment == platformAlignment); 727 InSituRegion!(4096, 64) a2; 728 assert(a2.alignment == 64); 729 ---- 730 */ 731 alias alignment = minAlign; 732 733 private void lazyInit() 734 { 735 assert(!_impl._current); 736 _impl = typeof(_impl)(_store); 737 assert(_impl._current.alignedAt(alignment)); 738 } 739 740 /** 741 Allocates `bytes` and returns them, or `null` if the region cannot 742 accommodate the request. For efficiency reasons, if $(D bytes == 0) the 743 function returns an empty non-null slice. 744 */ 745 void[] allocate(size_t n) 746 { 747 // Fast path 748 entry: 749 auto result = _impl.allocate(n); 750 if (result.length == n) return result; 751 // Slow path 752 if (_impl._current) return null; // no more room 753 lazyInit; 754 assert(_impl._current); 755 goto entry; 756 } 757 758 /** 759 As above, but the memory allocated is aligned at `a` bytes. 760 */ 761 void[] alignedAllocate(size_t n, uint a) 762 { 763 // Fast path 764 entry: 765 auto result = _impl.alignedAllocate(n, a); 766 if (result.length == n) return result; 767 // Slow path 768 if (_impl._current) return null; // no more room 769 lazyInit; 770 assert(_impl._current); 771 goto entry; 772 } 773 774 /** 775 Deallocates `b`. This works only if `b` was obtained as the last call 776 to `allocate`; otherwise (i.e. another allocation has occurred since) it 777 does nothing. This semantics is tricky and therefore `deallocate` is 778 defined only if `Region` is instantiated with `Yes.defineDeallocate` 779 as the third template argument. 780 781 Params: 782 b = Block previously obtained by a call to `allocate` against this 783 allocator (`null` is allowed). 784 */ 785 bool deallocate(void[] b) 786 { 787 if (!_impl._current) return b is null; 788 return _impl.deallocate(b); 789 } 790 791 /** 792 Returns `Ternary.yes` if `b` is the result of a previous allocation, 793 `Ternary.no` otherwise. 794 */ 795 Ternary owns(const void[] b) pure nothrow @safe @nogc 796 { 797 if (!_impl._current) return Ternary.no; 798 return _impl.owns(b); 799 } 800 801 /** 802 Expands an allocated block in place. Expansion will succeed only if the 803 block is the last allocated. 804 */ 805 static if (hasMember!(typeof(_impl), "expand")) 806 bool expand(ref void[] b, size_t delta) 807 { 808 if (!_impl._current) lazyInit; 809 return _impl.expand(b, delta); 810 } 811 812 /** 813 Deallocates all memory allocated with this allocator. 814 */ 815 bool deallocateAll() 816 { 817 // We don't care to lazily init the region 818 return _impl.deallocateAll; 819 } 820 821 /** 822 Allocates all memory available with this allocator. 823 */ 824 void[] allocateAll() 825 { 826 if (!_impl._current) lazyInit; 827 return _impl.allocateAll; 828 } 829 830 /** 831 Nonstandard function that returns the bytes available for allocation. 832 */ 833 size_t available() 834 { 835 if (!_impl._current) lazyInit; 836 return _impl.available; 837 } 838 } 839 840 /// 841 @system unittest 842 { 843 // 128KB region, allocated to x86's cache line 844 InSituRegion!(128 * 1024, 16) r1; 845 auto a1 = r1.allocate(101); 846 assert(a1.length == 101); 847 848 // 128KB region, with fallback to the garbage collector. 849 import std.experimental.allocator.building_blocks.fallback_allocator 850 : FallbackAllocator; 851 import std.experimental.allocator.building_blocks.free_list 852 : FreeList; 853 import std.experimental.allocator.building_blocks.bitmapped_block 854 : BitmappedBlock; 855 import std.experimental.allocator.gc_allocator : GCAllocator; 856 FallbackAllocator!(InSituRegion!(128 * 1024), GCAllocator) r2; 857 const a2 = r2.allocate(102); 858 assert(a2.length == 102); 859 860 // Reap with GC fallback. 861 InSituRegion!(128 * 1024, 8) tmp3; 862 FallbackAllocator!(BitmappedBlock!(64, 8), GCAllocator) r3; 863 r3.primary = BitmappedBlock!(64, 8)(cast(ubyte[]) (tmp3.allocateAll())); 864 const a3 = r3.allocate(103); 865 assert(a3.length == 103); 866 867 // Reap/GC with a freelist for small objects up to 16 bytes. 868 InSituRegion!(128 * 1024, 64) tmp4; 869 FreeList!(FallbackAllocator!(BitmappedBlock!(64, 64), GCAllocator), 0, 16) r4; 870 r4.parent.primary = BitmappedBlock!(64, 64)(cast(ubyte[]) (tmp4.allocateAll())); 871 const a4 = r4.allocate(104); 872 assert(a4.length == 104); 873 } 874 875 @system pure nothrow unittest 876 { 877 import std.typecons : Ternary; 878 879 InSituRegion!(4096, 1) r1; 880 auto a = r1.allocate(2001); 881 assert(a.length == 2001); 882 import std.conv : text; 883 assert(r1.available == 2095, text(r1.available)); 884 // Ensure deallocate inherits from parent 885 assert((() nothrow @nogc => r1.deallocate(a))()); 886 assert((() nothrow @nogc => r1.deallocateAll())()); 887 888 InSituRegion!(65_536, 1024*4) r2; 889 assert(r2.available <= 65_536); 890 a = r2.allocate(2001); 891 assert(a.length == 2001); 892 const void[] buff = r2.allocate(42); 893 assert((() nothrow @safe @nogc => r2.owns(buff))() == Ternary.yes); 894 assert((() nothrow @nogc => r2.deallocateAll())()); 895 } 896 897 version (CRuntime_Musl) 898 { 899 // sbrk and brk are disabled in Musl: 900 // https://git.musl-libc.org/cgit/musl/commit/?id=7a995fe706e519a4f55399776ef0df9596101f93 901 // https://git.musl-libc.org/cgit/musl/commit/?id=863d628d93ea341b6a32661a1654320ce69f6a07 902 } 903 version (DragonFlyBSD) 904 { 905 // sbrk is deprecated in favor of mmap (we could implement a mmap + MAP_NORESERVE + PROT_NONE version) 906 // brk has been removed 907 // https://web.archive.org/web/20221006070113/https://www.dragonflydigest.com/2019/02/22/22586.html 908 // http://gitweb.dragonflybsd.org/dragonfly.git/commitdiff/dc676eaefa61b0f47bbea1c53eab86fd5ccd78c6 909 // http://gitweb.dragonflybsd.org/dragonfly.git/commitdiff/4b5665564ef37dc939a3a9ffbafaab9894c18885 910 // http://gitweb.dragonflybsd.org/dragonfly.git/commitdiff/8618d94a0e2ff8303ad93c123a3fa598c26a116e 911 } 912 else 913 { 914 private extern(C) void* sbrk(long) nothrow @nogc; 915 private extern(C) int brk(shared void*) nothrow @nogc; 916 } 917 918 /** 919 920 Allocator backed by $(D $(LINK2 https://en.wikipedia.org/wiki/Sbrk, sbrk)) 921 for Posix systems. Due to the fact that `sbrk` is not thread-safe 922 $(HTTP lifecs.likai.org/2010/02/sbrk-is-not-thread-safe.html, by design), 923 `SbrkRegion` uses a mutex internally. This implies 924 that uncontrolled calls to `brk` and `sbrk` may affect the workings of $(D 925 SbrkRegion) adversely. 926 927 */ 928 version (CRuntime_Musl) {} else 929 version (DragonFlyBSD) {} else 930 version (Posix) struct SbrkRegion(uint minAlign = platformAlignment) 931 { 932 import core.sys.posix.pthread : pthread_mutex_init, pthread_mutex_destroy, 933 pthread_mutex_t, pthread_mutex_lock, pthread_mutex_unlock, 934 935 PTHREAD_MUTEX_INITIALIZER; 936 private static shared pthread_mutex_t sbrkMutex = PTHREAD_MUTEX_INITIALIZER; 937 import std.typecons : Ternary; 938 939 static assert(minAlign.isGoodStaticAlignment); 940 static assert(size_t.sizeof == (void*).sizeof); 941 private shared void* _brkInitial, _brkCurrent; 942 943 /** 944 Instance shared by all callers. 945 */ 946 static shared SbrkRegion instance; 947 948 /** 949 Standard allocator primitives. 950 */ 951 enum uint alignment = minAlign; 952 953 /** 954 Rounds the given size to a multiple of thew `alignment` 955 */ 956 size_t goodAllocSize(size_t n) shared const pure nothrow @safe @nogc 957 { 958 return n.roundUpToMultipleOf(alignment); 959 } 960 961 /// Ditto 962 void[] allocate(size_t bytes) shared @trusted nothrow @nogc 963 { 964 // Take alignment rounding into account 965 const rounded = goodAllocSize(bytes); 966 967 pthread_mutex_lock(cast(pthread_mutex_t*) &sbrkMutex) == 0 || assert(0); 968 scope(exit) pthread_mutex_unlock(cast(pthread_mutex_t*) &sbrkMutex) == 0 969 || assert(0); 970 // Assume sbrk returns the old break. Most online documentation confirms 971 // that, except for https://web.archive.org/web/20171014020821/http://www.inf.udec.cl/~leo/Malloc_tutorial.pdf, 972 // which claims the returned value is not portable. 973 auto p = sbrk(rounded); 974 if (p == cast(void*) -1) 975 { 976 return null; 977 } 978 if (!_brkInitial) 979 { 980 _brkInitial = cast(shared) p; 981 assert(cast(size_t) _brkInitial % minAlign == 0, 982 "Too large alignment chosen for " ~ typeof(this).stringof); 983 } 984 _brkCurrent = cast(shared) (p + rounded); 985 return p[0 .. bytes]; 986 } 987 988 /// Ditto 989 void[] alignedAllocate(size_t bytes, uint a) shared @trusted nothrow @nogc 990 { 991 pthread_mutex_lock(cast(pthread_mutex_t*) &sbrkMutex) == 0 || assert(0); 992 scope(exit) pthread_mutex_unlock(cast(pthread_mutex_t*) &sbrkMutex) == 0 993 || assert(0); 994 if (!_brkInitial) 995 { 996 // This is one extra call, but it'll happen only once. 997 _brkInitial = cast(shared) sbrk(0); 998 assert(cast(size_t) _brkInitial % minAlign == 0, 999 "Too large alignment chosen for " ~ typeof(this).stringof); 1000 (_brkInitial != cast(void*) -1) || assert(0); 1001 _brkCurrent = _brkInitial; 1002 } 1003 immutable size_t delta = cast(shared void*) roundUpToMultipleOf( 1004 cast(size_t) _brkCurrent, a) - _brkCurrent; 1005 // Still must make sure the total size is aligned to the allocator's 1006 // alignment. 1007 immutable rounded = (bytes + delta).roundUpToMultipleOf(alignment); 1008 1009 auto p = sbrk(rounded); 1010 if (p == cast(void*) -1) 1011 { 1012 return null; 1013 } 1014 _brkCurrent = cast(shared) (p + rounded); 1015 return p[delta .. delta + bytes]; 1016 } 1017 1018 /** 1019 1020 The `expand` method may only succeed if the argument is the last block 1021 allocated. In that case, `expand` attempts to push the break pointer to 1022 the right. 1023 1024 */ 1025 bool expand(ref void[] b, size_t delta) shared nothrow @trusted @nogc 1026 { 1027 if (b is null || delta == 0) return delta == 0; 1028 assert(_brkInitial && _brkCurrent); // otherwise where did b come from? 1029 pthread_mutex_lock(cast(pthread_mutex_t*) &sbrkMutex) == 0 || assert(0); 1030 scope(exit) pthread_mutex_unlock(cast(pthread_mutex_t*) &sbrkMutex) == 0 1031 || assert(0); 1032 1033 // Take alignment rounding into account 1034 const rounded = goodAllocSize(b.length); 1035 1036 const slack = rounded - b.length; 1037 if (delta <= slack) 1038 { 1039 b = b.ptr[0 .. b.length + delta]; 1040 return true; 1041 } 1042 1043 if (_brkCurrent != b.ptr + rounded) return false; 1044 // Great, can expand the last block 1045 delta -= slack; 1046 1047 const roundedDelta = goodAllocSize(delta); 1048 auto p = sbrk(roundedDelta); 1049 if (p == cast(void*) -1) 1050 { 1051 return false; 1052 } 1053 _brkCurrent = cast(shared) (p + roundedDelta); 1054 b = b.ptr[0 .. b.length + slack + delta]; 1055 return true; 1056 } 1057 1058 /// Ditto 1059 Ternary owns(const void[] b) shared pure nothrow @trusted @nogc 1060 { 1061 // No need to lock here. 1062 assert(!_brkCurrent || !b || &b[0] + b.length <= _brkCurrent); 1063 return Ternary(_brkInitial && b && (&b[0] >= _brkInitial)); 1064 } 1065 1066 /** 1067 1068 The `deallocate` method only works (and returns `true`) on systems 1069 that support reducing the break address (i.e. accept calls to `sbrk` 1070 with negative offsets). OSX does not accept such. In addition the argument 1071 must be the last block allocated. 1072 1073 */ 1074 bool deallocate(void[] b) shared nothrow @nogc 1075 { 1076 // Take alignment rounding into account 1077 const rounded = goodAllocSize(b.length); 1078 pthread_mutex_lock(cast(pthread_mutex_t*) &sbrkMutex) == 0 || assert(0); 1079 scope(exit) pthread_mutex_unlock(cast(pthread_mutex_t*) &sbrkMutex) == 0 1080 || assert(0); 1081 if (_brkCurrent != b.ptr + rounded) return false; 1082 assert(b.ptr >= _brkInitial); 1083 if (sbrk(-rounded) == cast(void*) -1) 1084 return false; 1085 _brkCurrent = cast(shared) b.ptr; 1086 return true; 1087 } 1088 1089 /** 1090 The `deallocateAll` method only works (and returns `true`) on systems 1091 that support reducing the break address (i.e. accept calls to `sbrk` 1092 with negative offsets). OSX does not accept such. 1093 */ 1094 nothrow @nogc 1095 bool deallocateAll() shared 1096 { 1097 pthread_mutex_lock(cast(pthread_mutex_t*) &sbrkMutex) == 0 || assert(0); 1098 scope(exit) pthread_mutex_unlock(cast(pthread_mutex_t*) &sbrkMutex) == 0 1099 || assert(0); 1100 return !_brkInitial || brk(_brkInitial) == 0; 1101 } 1102 1103 /// Standard allocator API. 1104 Ternary empty() shared pure nothrow @safe @nogc 1105 { 1106 // Also works when they're both null. 1107 return Ternary(_brkCurrent == _brkInitial); 1108 } 1109 } 1110 1111 version (CRuntime_Musl) {} else 1112 version (DragonFlyBSD) {} else 1113 version (Posix) @system nothrow @nogc unittest 1114 { 1115 // Let's test the assumption that sbrk(n) returns the old address 1116 const p1 = sbrk(0); 1117 const p2 = sbrk(4096); 1118 assert(p1 == p2); 1119 const p3 = sbrk(0); 1120 assert(p3 == p2 + 4096); 1121 // Try to reset brk, but don't make a fuss if it doesn't work 1122 sbrk(-4096); 1123 } 1124 1125 version (CRuntime_Musl) {} else 1126 version (DragonFlyBSD) {} else 1127 version (Posix) @system nothrow @nogc unittest 1128 { 1129 import std.typecons : Ternary; 1130 import std.algorithm.comparison : min; 1131 alias alloc = SbrkRegion!(min(8, platformAlignment)).instance; 1132 assert((() nothrow @safe @nogc => alloc.empty)() == Ternary.yes); 1133 auto a = alloc.alignedAllocate(2001, 4096); 1134 assert(a.length == 2001); 1135 assert((() nothrow @safe @nogc => alloc.empty)() == Ternary.no); 1136 auto oldBrkCurr = alloc._brkCurrent; 1137 auto b = alloc.allocate(2001); 1138 assert(b.length == 2001); 1139 assert((() nothrow @safe @nogc => alloc.expand(b, 0))()); 1140 assert(b.length == 2001); 1141 // Expand with a small size to fit the rounded slack due to alignment 1142 assert((() nothrow @safe @nogc => alloc.expand(b, 1))()); 1143 assert(b.length == 2002); 1144 // Exceed the rounded slack due to alignment 1145 assert((() nothrow @safe @nogc => alloc.expand(b, 10))()); 1146 assert(b.length == 2012); 1147 assert((() nothrow @safe @nogc => alloc.owns(a))() == Ternary.yes); 1148 assert((() nothrow @safe @nogc => alloc.owns(b))() == Ternary.yes); 1149 // reducing the brk does not work on OSX 1150 version (Darwin) {} else 1151 { 1152 assert((() nothrow @nogc => alloc.deallocate(b))()); 1153 // Check that expand and deallocate work well 1154 assert(oldBrkCurr == alloc._brkCurrent); 1155 assert((() nothrow @nogc => alloc.deallocate(a))()); 1156 assert((() nothrow @nogc => alloc.deallocateAll())()); 1157 } 1158 const void[] c = alloc.allocate(2001); 1159 assert(c.length == 2001); 1160 assert((() nothrow @safe @nogc => alloc.owns(c))() == Ternary.yes); 1161 assert((() nothrow @safe @nogc => alloc.owns(null))() == Ternary.no); 1162 } 1163 1164 /** 1165 The threadsafe version of the `Region` allocator. 1166 Allocations and deallocations are lock-free based using $(REF cas, core,atomic). 1167 */ 1168 shared struct SharedRegion(ParentAllocator, 1169 uint minAlign = platformAlignment, 1170 Flag!"growDownwards" growDownwards = No.growDownwards) 1171 { 1172 static assert(minAlign.isGoodStaticAlignment); 1173 static assert(ParentAllocator.alignment >= minAlign); 1174 1175 import std.traits : hasMember; 1176 import std.typecons : Ternary; 1177 1178 // state 1179 /** 1180 The _parent allocator. Depending on whether `ParentAllocator` holds state 1181 or not, this is a member variable or an alias for 1182 `ParentAllocator.instance`. 1183 */ 1184 static if (stateSize!ParentAllocator) 1185 { 1186 ParentAllocator parent; 1187 } 1188 else 1189 { 1190 alias parent = ParentAllocator.instance; 1191 } 1192 private shared SharedBorrowedRegion!(minAlign, growDownwards) _impl; 1193 1194 private void* roundedBegin() const pure nothrow @trusted @nogc 1195 { 1196 return _impl.roundedBegin; 1197 } 1198 1199 private void* roundedEnd() const pure nothrow @trusted @nogc 1200 { 1201 return _impl.roundedEnd; 1202 } 1203 1204 1205 /** 1206 Constructs a region backed by a user-provided store. 1207 Assumes the memory was allocated with `ParentAllocator`. 1208 1209 Params: 1210 store = User-provided store backing up the region. Assumed to have been 1211 allocated with `ParentAllocator`. 1212 n = Bytes to allocate using `ParentAllocator`. If `parent.allocate(n)` 1213 returns `null`, the region will be initialized as empty (correctly 1214 initialized but unable to allocate). 1215 */ 1216 this(ubyte[] store) pure nothrow @nogc 1217 { 1218 _impl = store; 1219 } 1220 1221 /// Ditto 1222 this(size_t n) 1223 { 1224 this(cast(ubyte[]) (parent.allocate(n.roundUpToAlignment(alignment)))); 1225 } 1226 1227 /** 1228 Rounds the given size to a multiple of the `alignment` 1229 */ 1230 size_t goodAllocSize(size_t n) const pure nothrow @safe @nogc 1231 { 1232 return _impl.goodAllocSize(n); 1233 } 1234 1235 /** 1236 Alignment offered. 1237 */ 1238 alias alignment = minAlign; 1239 1240 /** 1241 Allocates `n` bytes of memory. The allocation is served by atomically incrementing 1242 a pointer which keeps track of the current used space. 1243 1244 Params: 1245 n = number of bytes to allocate 1246 1247 Returns: 1248 A properly-aligned buffer of size `n`, or `null` if request could not 1249 be satisfied. 1250 */ 1251 void[] allocate(size_t n) pure nothrow @trusted @nogc 1252 { 1253 return _impl.allocate(n); 1254 } 1255 1256 /** 1257 Deallocates `b`. This works only if `b` was obtained as the last call 1258 to `allocate`; otherwise (i.e. another allocation has occurred since) it 1259 does nothing. 1260 1261 Params: 1262 b = Block previously obtained by a call to `allocate` against this 1263 allocator (`null` is allowed). 1264 */ 1265 bool deallocate(void[] b) pure nothrow @nogc 1266 { 1267 return _impl.deallocate(b); 1268 } 1269 1270 /** 1271 Deallocates all memory allocated by this region, which can be subsequently 1272 reused for new allocations. 1273 */ 1274 bool deallocateAll() pure nothrow @nogc 1275 { 1276 return _impl.deallocateAll; 1277 } 1278 1279 /** 1280 Allocates `n` bytes of memory aligned at alignment `a`. 1281 Params: 1282 n = number of bytes to allocate 1283 a = alignment for the allocated block 1284 1285 Returns: 1286 Either a suitable block of `n` bytes aligned at `a`, or `null`. 1287 */ 1288 void[] alignedAllocate(size_t n, uint a) pure nothrow @trusted @nogc 1289 { 1290 return _impl.alignedAllocate(n, a); 1291 } 1292 1293 /** 1294 Queries whether `b` has been allocated with this region. 1295 1296 Params: 1297 b = Arbitrary block of memory (`null` is allowed; `owns(null)` returns 1298 `false`). 1299 1300 Returns: 1301 `true` if `b` has been allocated with this region, `false` otherwise. 1302 */ 1303 Ternary owns(const void[] b) const pure nothrow @trusted @nogc 1304 { 1305 return _impl.owns(b); 1306 } 1307 1308 /** 1309 Returns `Ternary.yes` if no memory has been allocated in this region, 1310 `Ternary.no` otherwise. (Never returns `Ternary.unknown`.) 1311 */ 1312 Ternary empty() const pure nothrow @safe @nogc 1313 { 1314 return _impl.empty; 1315 } 1316 1317 /** 1318 If `ParentAllocator` defines `deallocate`, the region defines a destructor 1319 that uses `ParentAllocator.deallocate` to free the memory chunk. 1320 */ 1321 static if (hasMember!(ParentAllocator, "deallocate")) 1322 ~this() 1323 { 1324 with (_impl) parent.deallocate(cast(void[]) _begin[0 .. _end - _begin]); 1325 } 1326 } 1327 1328 @system unittest 1329 { 1330 import std.experimental.allocator.mallocator : Mallocator; 1331 1332 static void testAlloc(Allocator)(ref Allocator a, bool growDownwards) 1333 { 1334 import core.thread : ThreadGroup; 1335 import std.algorithm.sorting : sort; 1336 import core.internal.spinlock : SpinLock; 1337 1338 SpinLock lock = SpinLock(SpinLock.Contention.brief); 1339 enum numThreads = 100; 1340 void[][numThreads] buf; 1341 size_t count = 0; 1342 1343 void fun() 1344 { 1345 void[] b = a.allocate(63); 1346 assert(b.length == 63); 1347 1348 lock.lock(); 1349 buf[count] = b; 1350 count++; 1351 lock.unlock(); 1352 } 1353 1354 auto tg = new ThreadGroup; 1355 foreach (i; 0 .. numThreads) 1356 { 1357 tg.create(&fun); 1358 } 1359 tg.joinAll(); 1360 1361 sort!((a, b) => a.ptr < b.ptr)(buf[0 .. numThreads]); 1362 foreach (i; 0 .. numThreads - 1) 1363 { 1364 assert(buf[i].ptr + a.goodAllocSize(buf[i].length) == buf[i + 1].ptr); 1365 } 1366 1367 assert(!a.deallocate(buf[1])); 1368 1369 foreach (i; 0 .. numThreads) 1370 { 1371 if (!growDownwards) 1372 assert(a.deallocate(buf[numThreads - 1 - i])); 1373 else 1374 assert(a.deallocate(buf[i])); 1375 } 1376 1377 assert(a.deallocateAll()); 1378 void[] b = a.allocate(63); 1379 assert(b.length == 63); 1380 assert(a.deallocate(b)); 1381 } 1382 1383 auto a1 = SharedRegion!(Mallocator, Mallocator.alignment, 1384 Yes.growDownwards)(1024 * 64); 1385 1386 auto a2 = SharedRegion!(Mallocator, Mallocator.alignment, 1387 No.growDownwards)(1024 * 64); 1388 1389 testAlloc(a1, true); 1390 testAlloc(a2, false); 1391 } 1392 1393 @system unittest 1394 { 1395 import std.experimental.allocator.mallocator : Mallocator; 1396 1397 static void testAlloc(Allocator)(ref Allocator a, bool growDownwards) 1398 { 1399 import core.thread : ThreadGroup; 1400 import std.algorithm.sorting : sort; 1401 import core.internal.spinlock : SpinLock; 1402 1403 SpinLock lock = SpinLock(SpinLock.Contention.brief); 1404 enum numThreads = 100; 1405 void[][2 * numThreads] buf; 1406 size_t count = 0; 1407 1408 void fun() 1409 { 1410 void[] b = a.allocate(63); 1411 assert(b.length == 63); 1412 1413 lock.lock(); 1414 buf[count] = b; 1415 count++; 1416 lock.unlock(); 1417 1418 b = a.alignedAllocate(63, 32); 1419 assert(b.length == 63); 1420 assert(cast(size_t) b.ptr % 32 == 0); 1421 1422 lock.lock(); 1423 buf[count] = b; 1424 count++; 1425 lock.unlock(); 1426 } 1427 1428 auto tg = new ThreadGroup; 1429 foreach (i; 0 .. numThreads) 1430 { 1431 tg.create(&fun); 1432 } 1433 tg.joinAll(); 1434 1435 sort!((a, b) => a.ptr < b.ptr)(buf[0 .. 2 * numThreads]); 1436 foreach (i; 0 .. 2 * numThreads - 1) 1437 { 1438 assert(buf[i].ptr + buf[i].length <= buf[i + 1].ptr); 1439 } 1440 1441 assert(!a.deallocate(buf[1])); 1442 assert(a.deallocateAll()); 1443 1444 void[] b = a.allocate(13); 1445 assert(b.length == 13); 1446 assert(a.deallocate(b)); 1447 } 1448 1449 auto a1 = SharedRegion!(Mallocator, Mallocator.alignment, 1450 Yes.growDownwards)(1024 * 64); 1451 1452 auto a2 = SharedRegion!(Mallocator, Mallocator.alignment, 1453 No.growDownwards)(1024 * 64); 1454 1455 testAlloc(a1, true); 1456 testAlloc(a2, false); 1457 } 1458 1459 /** 1460 A `SharedBorrowedRegion` allocates directly from a user-provided block of memory. 1461 1462 Unlike a `SharedRegion`, a `SharedBorrowedRegion` does not own the memory it 1463 allocates from and will not deallocate that memory upon destruction. Instead, 1464 it is the user's responsibility to ensure that the memory is properly disposed 1465 of. 1466 1467 In all other respects, a `SharedBorrowedRegion` behaves exactly like a `SharedRegion`. 1468 */ 1469 shared struct SharedBorrowedRegion(uint minAlign = platformAlignment, 1470 Flag!"growDownwards" growDownwards = No.growDownwards) 1471 { 1472 static assert(minAlign.isGoodStaticAlignment); 1473 1474 import std.typecons : Ternary; 1475 1476 // state 1477 private void* _current, _begin, _end; 1478 1479 private void* roundedBegin() shared const pure nothrow @trusted @nogc 1480 { 1481 return cast(void*) roundUpToAlignment(cast(size_t) _begin, alignment); 1482 } 1483 1484 private void* roundedEnd() shared const pure nothrow @trusted @nogc 1485 { 1486 return cast(void*) roundDownToAlignment(cast(size_t) _end, alignment); 1487 } 1488 1489 /** 1490 Constructs a region backed by a user-provided store. 1491 1492 Params: 1493 store = User-provided store backing up the region. Must not be aliased. 1494 */ 1495 this(ubyte[] store) shared pure nothrow @nogc 1496 { 1497 _begin = cast(typeof(_begin)) store.ptr; 1498 _end = cast(typeof(_end)) (store.ptr + store.length); 1499 static if (growDownwards) 1500 _current = cast(typeof(_current)) roundedEnd(); 1501 else 1502 _current = cast(typeof(_current)) roundedBegin(); 1503 } 1504 1505 /* 1506 TODO: The postblit of `SharedBorrowedRegion` should be disabled because 1507 such objects should not be copied around naively. 1508 */ 1509 1510 /** 1511 Rounds the given size to a multiple of the `alignment` 1512 */ 1513 size_t goodAllocSize(size_t n) shared const pure nothrow @safe @nogc 1514 { 1515 return n.roundUpToAlignment(alignment); 1516 } 1517 1518 /** 1519 Alignment offered. 1520 */ 1521 alias alignment = minAlign; 1522 1523 /** 1524 Allocates `n` bytes of memory. The allocation is served by atomically incrementing 1525 a pointer which keeps track of the current used space. 1526 1527 Params: 1528 n = number of bytes to allocate 1529 1530 Returns: 1531 A properly-aligned buffer of size `n`, or `null` if request could not 1532 be satisfied. 1533 */ 1534 void[] allocate(size_t n) shared pure nothrow @trusted @nogc 1535 { 1536 import core.atomic : cas, atomicLoad; 1537 1538 if (n == 0) return null; 1539 const rounded = goodAllocSize(n); 1540 1541 shared void* localCurrent, localNewCurrent; 1542 static if (growDownwards) 1543 { 1544 do 1545 { 1546 localCurrent = atomicLoad(_current); 1547 localNewCurrent = localCurrent - rounded; 1548 if (localNewCurrent > localCurrent || localNewCurrent < _begin) 1549 return null; 1550 } while (!cas(&_current, localCurrent, localNewCurrent)); 1551 1552 return cast(void[]) localNewCurrent[0 .. n]; 1553 } 1554 else 1555 { 1556 do 1557 { 1558 localCurrent = atomicLoad(_current); 1559 localNewCurrent = localCurrent + rounded; 1560 if (localNewCurrent < localCurrent || localNewCurrent > _end) 1561 return null; 1562 } while (!cas(&_current, localCurrent, localNewCurrent)); 1563 1564 return cast(void[]) localCurrent[0 .. n]; 1565 } 1566 1567 assert(0, "Unexpected error in SharedBorrowedRegion.allocate"); 1568 } 1569 1570 /** 1571 Allocates `n` bytes of memory aligned at alignment `a`. 1572 1573 Params: 1574 n = number of bytes to allocate 1575 a = alignment for the allocated block 1576 1577 Returns: 1578 Either a suitable block of `n` bytes aligned at `a`, or `null`. 1579 */ 1580 void[] alignedAllocate(size_t n, uint a) shared pure nothrow @trusted @nogc 1581 { 1582 import core.atomic : cas, atomicLoad; 1583 import std.math.traits : isPowerOf2; 1584 1585 assert(a.isPowerOf2); 1586 if (n == 0) return null; 1587 1588 const rounded = goodAllocSize(n); 1589 shared void* localCurrent, localNewCurrent; 1590 1591 static if (growDownwards) 1592 { 1593 do 1594 { 1595 localCurrent = atomicLoad(_current); 1596 auto alignedCurrent = cast(void*)(localCurrent - rounded); 1597 localNewCurrent = cast(shared(void*)) alignedCurrent.alignDownTo(a); 1598 if (alignedCurrent > localCurrent || localNewCurrent > alignedCurrent || 1599 localNewCurrent < _begin) 1600 return null; 1601 } while (!cas(&_current, localCurrent, localNewCurrent)); 1602 1603 return cast(void[]) localNewCurrent[0 .. n]; 1604 } 1605 else 1606 { 1607 do 1608 { 1609 localCurrent = atomicLoad(_current); 1610 auto alignedCurrent = alignUpTo(cast(void*) localCurrent, a); 1611 localNewCurrent = cast(shared(void*)) (alignedCurrent + rounded); 1612 if (alignedCurrent < localCurrent || localNewCurrent < alignedCurrent || 1613 localNewCurrent > _end) 1614 return null; 1615 } while (!cas(&_current, localCurrent, localNewCurrent)); 1616 1617 return cast(void[]) (localNewCurrent - rounded)[0 .. n]; 1618 } 1619 1620 assert(0, "Unexpected error in SharedBorrowedRegion.alignedAllocate"); 1621 } 1622 1623 /** 1624 Deallocates `b`. This works only if `b` was obtained as the last call 1625 to `allocate`; otherwise (i.e. another allocation has occurred since) it 1626 does nothing. 1627 1628 Params: 1629 b = Block previously obtained by a call to `allocate` against this 1630 allocator (`null` is allowed). 1631 */ 1632 bool deallocate(void[] b) shared pure nothrow @nogc 1633 { 1634 import core.atomic : cas, atomicLoad; 1635 1636 const rounded = goodAllocSize(b.length); 1637 shared void* localCurrent, localNewCurrent; 1638 1639 // The cas is done only once, because only the last allocation can be reverted 1640 localCurrent = atomicLoad(_current); 1641 static if (growDownwards) 1642 { 1643 localNewCurrent = localCurrent + rounded; 1644 if (b.ptr == localCurrent) 1645 return cas(&_current, localCurrent, localNewCurrent); 1646 } 1647 else 1648 { 1649 localNewCurrent = localCurrent - rounded; 1650 if (b.ptr == localNewCurrent) 1651 return cas(&_current, localCurrent, localNewCurrent); 1652 } 1653 1654 return false; 1655 } 1656 1657 /** 1658 Deallocates all memory allocated by this region, which can be subsequently 1659 reused for new allocations. 1660 */ 1661 bool deallocateAll() shared pure nothrow @nogc 1662 { 1663 import core.atomic : atomicStore; 1664 static if (growDownwards) 1665 { 1666 atomicStore(_current, cast(shared(void*)) roundedEnd()); 1667 } 1668 else 1669 { 1670 atomicStore(_current, cast(shared(void*)) roundedBegin()); 1671 } 1672 return true; 1673 } 1674 1675 /** 1676 Queries whether `b` has been allocated with this region. 1677 1678 Params: 1679 b = Arbitrary block of memory (`null` is allowed; `owns(null)` returns 1680 `false`). 1681 1682 Returns: 1683 `true` if `b` has been allocated with this region, `false` otherwise. 1684 */ 1685 Ternary owns(const void[] b) shared const pure nothrow @trusted @nogc 1686 { 1687 return Ternary(b && (&b[0] >= _begin) && (&b[0] + b.length <= _end)); 1688 } 1689 1690 /** 1691 Returns `Ternary.yes` if no memory has been allocated in this region, 1692 `Ternary.no` otherwise. (Never returns `Ternary.unknown`.) 1693 */ 1694 Ternary empty() shared const pure nothrow @safe @nogc 1695 { 1696 import core.atomic : atomicLoad; 1697 1698 auto localCurrent = atomicLoad(_current); 1699 static if (growDownwards) 1700 return Ternary(localCurrent == roundedEnd()); 1701 else 1702 return Ternary(localCurrent == roundedBegin()); 1703 } 1704 }