1/** 2Utility and ancillary artifacts of `std.experimental.allocator`. This module 3shouldn't be used directly; its functionality will be migrated into more 4appropriate parts of `std`. 5 6Authors: $(HTTP erdani.com, Andrei Alexandrescu), Timon Gehr (`Ternary`) 7*/ 8module std.experimental.allocator.common; 9import std.algorithm.comparison, std.traits; 10 11/** 12Returns the size in bytes of the state that needs to be allocated to hold an 13object of type $(D T). $(D stateSize!T) is zero for $(D struct)s that are not 14nested and have no nonstatic member variables. 15 */ 16template stateSize(T) 17{ 18 static if (is(T == class) || is(T == interface)) 19 enum stateSize = __traits(classInstanceSize, T); 20 else static if (is(T == struct) || is(T == union)) 21 enum stateSize = Fields!T.length || isNested!T ? T.sizeof : 0; 22 else static if (is(T == void)) 23 enum size_t stateSize = 0; 24 else 25 enum stateSize = T.sizeof; 26} 27 28@safe @nogc nothrow pure 29unittest 30{ 31 static assert(stateSize!void == 0); 32 struct A {} 33 static assert(stateSize!A == 0); 34 struct B { int x; } 35 static assert(stateSize!B == 4); 36 interface I1 {} 37 //static assert(stateSize!I1 == 2 * size_t.sizeof); 38 class C1 {} 39 static assert(stateSize!C1 == 3 * size_t.sizeof); 40 class C2 { char c; } 41 static assert(stateSize!C2 == 4 * size_t.sizeof); 42 static class C3 { char c; } 43 static assert(stateSize!C3 == 2 * size_t.sizeof + char.sizeof); 44} 45 46/** 47Returns `true` if the `Allocator` has the alignment known at compile time; 48otherwise it returns `false`. 49 */ 50template hasStaticallyKnownAlignment(Allocator) 51{ 52 enum hasStaticallyKnownAlignment = __traits(compiles, 53 {enum x = Allocator.alignment;}); 54} 55 56/** 57$(D chooseAtRuntime) is a compile-time constant of type $(D size_t) that several 58parameterized structures in this module recognize to mean deferral to runtime of 59the exact value. For example, $(D BitmappedBlock!(Allocator, 4096)) (described in 60detail below) defines a block allocator with block size of 4096 bytes, whereas 61$(D BitmappedBlock!(Allocator, chooseAtRuntime)) defines a block allocator that has a 62field storing the block size, initialized by the user. 63*/ 64enum chooseAtRuntime = size_t.max - 1; 65 66/** 67$(D unbounded) is a compile-time constant of type $(D size_t) that several 68parameterized structures in this module recognize to mean "infinite" bounds for 69the parameter. For example, $(D Freelist) (described in detail below) accepts a 70$(D maxNodes) parameter limiting the number of freelist items. If $(D unbounded) 71is passed for $(D maxNodes), then there is no limit and no checking for the 72number of nodes. 73*/ 74enum unbounded = size_t.max; 75 76/** 77The alignment that is guaranteed to accommodate any D object allocation on the 78current platform. 79*/ 80enum uint platformAlignment = std.algorithm.comparison.max(double.alignof, real.alignof); 81 82/** 83The default good size allocation is deduced as $(D n) rounded up to the 84allocator's alignment. 85*/ 86size_t goodAllocSize(A)(auto ref A a, size_t n) 87{ 88 return n.roundUpToMultipleOf(a.alignment); 89} 90 91/** 92Returns s rounded up to a multiple of base. 93*/ 94@safe @nogc nothrow pure 95package size_t roundUpToMultipleOf(size_t s, uint base) 96{ 97 assert(base); 98 auto rem = s % base; 99 return rem ? s + base - rem : s; 100} 101 102@safe @nogc nothrow pure 103unittest 104{ 105 assert(10.roundUpToMultipleOf(11) == 11); 106 assert(11.roundUpToMultipleOf(11) == 11); 107 assert(12.roundUpToMultipleOf(11) == 22); 108 assert(118.roundUpToMultipleOf(11) == 121); 109} 110 111/** 112Returns `n` rounded up to a multiple of alignment, which must be a power of 2. 113*/ 114@safe @nogc nothrow pure 115package size_t roundUpToAlignment(size_t n, uint alignment) 116{ 117 import std.math : isPowerOf2; 118 assert(alignment.isPowerOf2); 119 immutable uint slack = cast(uint) n & (alignment - 1); 120 const result = slack 121 ? n + alignment - slack 122 : n; 123 assert(result >= n); 124 return result; 125} 126 127@safe @nogc nothrow pure 128unittest 129{ 130 assert(10.roundUpToAlignment(4) == 12); 131 assert(11.roundUpToAlignment(2) == 12); 132 assert(12.roundUpToAlignment(8) == 16); 133 assert(118.roundUpToAlignment(64) == 128); 134} 135 136/** 137Returns `n` rounded down to a multiple of alignment, which must be a power of 2. 138*/ 139@safe @nogc nothrow pure 140package size_t roundDownToAlignment(size_t n, uint alignment) 141{ 142 import std.math : isPowerOf2; 143 assert(alignment.isPowerOf2); 144 return n & ~size_t(alignment - 1); 145} 146 147@safe @nogc nothrow pure 148unittest 149{ 150 assert(10.roundDownToAlignment(4) == 8); 151 assert(11.roundDownToAlignment(2) == 10); 152 assert(12.roundDownToAlignment(8) == 8); 153 assert(63.roundDownToAlignment(64) == 0); 154} 155 156/** 157Advances the beginning of `b` to start at alignment `a`. The resulting buffer 158may therefore be shorter. Returns the adjusted buffer, or null if obtaining a 159non-empty buffer is impossible. 160*/ 161@nogc nothrow pure 162package void[] roundUpToAlignment(void[] b, uint a) 163{ 164 auto e = b.ptr + b.length; 165 auto p = cast(void*) roundUpToAlignment(cast(size_t) b.ptr, a); 166 if (e <= p) return null; 167 return p[0 .. e - p]; 168} 169 170@nogc nothrow pure 171@system unittest 172{ 173 void[] empty; 174 assert(roundUpToAlignment(empty, 4) == null); 175 char[128] buf; 176 // At least one pointer inside buf is 128-aligned 177 assert(roundUpToAlignment(buf, 128) !is null); 178} 179 180/** 181Like `a / b` but rounds the result up, not down. 182*/ 183@safe @nogc nothrow pure 184package size_t divideRoundUp(size_t a, size_t b) 185{ 186 assert(b); 187 return (a + b - 1) / b; 188} 189 190/** 191Returns `s` rounded up to a multiple of `base`. 192*/ 193@nogc nothrow pure 194package void[] roundStartToMultipleOf(void[] s, uint base) 195{ 196 assert(base); 197 auto p = cast(void*) roundUpToMultipleOf( 198 cast(size_t) s.ptr, base); 199 auto end = s.ptr + s.length; 200 return p[0 .. end - p]; 201} 202 203nothrow pure 204@system unittest 205{ 206 void[] p; 207 assert(roundStartToMultipleOf(p, 16) is null); 208 p = new ulong[10]; 209 assert(roundStartToMultipleOf(p, 16) is p); 210} 211 212/** 213Returns $(D s) rounded up to the nearest power of 2. 214*/ 215@safe @nogc nothrow pure 216package size_t roundUpToPowerOf2(size_t s) 217{ 218 import std.meta : AliasSeq; 219 assert(s <= (size_t.max >> 1) + 1); 220 --s; 221 static if (size_t.sizeof == 4) 222 alias Shifts = AliasSeq!(1, 2, 4, 8, 16); 223 else 224 alias Shifts = AliasSeq!(1, 2, 4, 8, 16, 32); 225 foreach (i; Shifts) 226 { 227 s |= s >> i; 228 } 229 return s + 1; 230} 231 232@safe @nogc nothrow pure 233unittest 234{ 235 assert(0.roundUpToPowerOf2 == 0); 236 assert(1.roundUpToPowerOf2 == 1); 237 assert(2.roundUpToPowerOf2 == 2); 238 assert(3.roundUpToPowerOf2 == 4); 239 assert(7.roundUpToPowerOf2 == 8); 240 assert(8.roundUpToPowerOf2 == 8); 241 assert(10.roundUpToPowerOf2 == 16); 242 assert(11.roundUpToPowerOf2 == 16); 243 assert(12.roundUpToPowerOf2 == 16); 244 assert(118.roundUpToPowerOf2 == 128); 245 assert((size_t.max >> 1).roundUpToPowerOf2 == (size_t.max >> 1) + 1); 246 assert(((size_t.max >> 1) + 1).roundUpToPowerOf2 == (size_t.max >> 1) + 1); 247} 248 249/** 250Returns the number of trailing zeros of $(D x). 251*/ 252@safe @nogc nothrow pure 253package uint trailingZeros(ulong x) 254{ 255 uint result; 256 while (result < 64 && !(x & (1UL << result))) 257 { 258 ++result; 259 } 260 return result; 261} 262 263@safe @nogc nothrow pure 264unittest 265{ 266 assert(trailingZeros(0) == 64); 267 assert(trailingZeros(1) == 0); 268 assert(trailingZeros(2) == 1); 269 assert(trailingZeros(3) == 0); 270 assert(trailingZeros(4) == 2); 271} 272 273/** 274Returns `true` if `ptr` is aligned at `alignment`. 275*/ 276@nogc nothrow pure 277package bool alignedAt(T)(T* ptr, uint alignment) 278{ 279 return cast(size_t) ptr % alignment == 0; 280} 281 282/** 283Returns the effective alignment of `ptr`, i.e. the largest power of two that is 284a divisor of `ptr`. 285*/ 286@nogc nothrow pure 287package uint effectiveAlignment(void* ptr) 288{ 289 return 1U << trailingZeros(cast(size_t) ptr); 290} 291 292@nogc nothrow pure 293@system unittest 294{ 295 int x; 296 assert(effectiveAlignment(&x) >= int.alignof); 297} 298 299/** 300Aligns a pointer down to a specified alignment. The resulting pointer is less 301than or equal to the given pointer. 302*/ 303@nogc nothrow pure 304package void* alignDownTo(void* ptr, uint alignment) 305{ 306 import std.math : isPowerOf2; 307 assert(alignment.isPowerOf2); 308 return cast(void*) (cast(size_t) ptr & ~(alignment - 1UL)); 309} 310 311/** 312Aligns a pointer up to a specified alignment. The resulting pointer is greater 313than or equal to the given pointer. 314*/ 315@nogc nothrow pure 316package void* alignUpTo(void* ptr, uint alignment) 317{ 318 import std.math : isPowerOf2; 319 assert(alignment.isPowerOf2); 320 immutable uint slack = cast(size_t) ptr & (alignment - 1U); 321 return slack ? ptr + alignment - slack : ptr; 322} 323 324@safe @nogc nothrow pure 325package bool isGoodStaticAlignment(uint x) 326{ 327 import std.math : isPowerOf2; 328 return x.isPowerOf2; 329} 330 331@safe @nogc nothrow pure 332package bool isGoodDynamicAlignment(uint x) 333{ 334 import std.math : isPowerOf2; 335 return x.isPowerOf2 && x >= (void*).sizeof; 336} 337 338/** 339The default $(D reallocate) function first attempts to use $(D expand). If $(D 340Allocator.expand) is not defined or returns $(D false), $(D reallocate) 341allocates a new block of memory of appropriate size and copies data from the old 342block to the new block. Finally, if $(D Allocator) defines $(D deallocate), $(D 343reallocate) uses it to free the old memory block. 344 345$(D reallocate) does not attempt to use $(D Allocator.reallocate) even if 346defined. This is deliberate so allocators may use it internally within their own 347implementation of $(D reallocate). 348 349*/ 350bool reallocate(Allocator)(ref Allocator a, ref void[] b, size_t s) 351{ 352 if (b.length == s) return true; 353 static if (hasMember!(Allocator, "expand")) 354 { 355 if (b.length <= s && a.expand(b, s - b.length)) return true; 356 } 357 auto newB = a.allocate(s); 358 if (newB.length != s) return false; 359 if (newB.length <= b.length) newB[] = b[0 .. newB.length]; 360 else newB[0 .. b.length] = b[]; 361 static if (hasMember!(Allocator, "deallocate")) 362 a.deallocate(b); 363 b = newB; 364 return true; 365} 366 367/** 368 369The default $(D alignedReallocate) function first attempts to use $(D expand). 370If $(D Allocator.expand) is not defined or returns $(D false), $(D 371alignedReallocate) allocates a new block of memory of appropriate size and 372copies data from the old block to the new block. Finally, if $(D Allocator) 373defines $(D deallocate), $(D alignedReallocate) uses it to free the old memory 374block. 375 376$(D alignedReallocate) does not attempt to use $(D Allocator.reallocate) even if 377defined. This is deliberate so allocators may use it internally within their own 378implementation of $(D reallocate). 379 380*/ 381bool alignedReallocate(Allocator)(ref Allocator alloc, 382 ref void[] b, size_t s, uint a) 383{ 384 static if (hasMember!(Allocator, "expand")) 385 { 386 if (b.length <= s && b.ptr.alignedAt(a) 387 && alloc.expand(b, s - b.length)) return true; 388 } 389 else 390 { 391 if (b.length == s) return true; 392 } 393 auto newB = alloc.alignedAllocate(s, a); 394 if (newB.length <= b.length) newB[] = b[0 .. newB.length]; 395 else newB[0 .. b.length] = b[]; 396 static if (hasMember!(Allocator, "deallocate")) 397 alloc.deallocate(b); 398 b = newB; 399 return true; 400} 401 402/** 403Forwards each of the methods in `funs` (if defined) to `member`. 404*/ 405/*package*/ string forwardToMember(string member, string[] funs...) 406{ 407 string result = " import std.traits : hasMember, Parameters;\n"; 408 foreach (fun; funs) 409 { 410 result ~= " 411 static if (hasMember!(typeof("~member~"), `"~fun~"`)) 412 auto ref "~fun~"(Parameters!(typeof("~member~"."~fun~")) args) 413 { 414 return "~member~"."~fun~"(args); 415 }\n"; 416 } 417 return result; 418} 419 420version (unittest) 421{ 422 import std.experimental.allocator : IAllocator, ISharedAllocator; 423 424 package void testAllocator(alias make)() 425 { 426 import std.conv : text; 427 import std.math : isPowerOf2; 428 import std.stdio : writeln, stderr; 429 import std.typecons : Ternary; 430 alias A = typeof(make()); 431 scope(failure) stderr.writeln("testAllocator failed for ", A.stringof); 432 433 auto a = make(); 434 435 // Test alignment 436 static assert(A.alignment.isPowerOf2); 437 438 // Test goodAllocSize 439 assert(a.goodAllocSize(1) >= A.alignment, 440 text(a.goodAllocSize(1), " < ", A.alignment)); 441 assert(a.goodAllocSize(11) >= 11.roundUpToMultipleOf(A.alignment)); 442 assert(a.goodAllocSize(111) >= 111.roundUpToMultipleOf(A.alignment)); 443 444 // Test allocate 445 assert(a.allocate(0) is null); 446 447 auto b1 = a.allocate(1); 448 assert(b1.length == 1); 449 auto b2 = a.allocate(2); 450 assert(b2.length == 2); 451 assert(b2.ptr + b2.length <= b1.ptr || b1.ptr + b1.length <= b2.ptr); 452 453 // Test alignedAllocate 454 static if (hasMember!(A, "alignedAllocate")) 455 {{ 456 auto b3 = a.alignedAllocate(1, 256); 457 assert(b3.length <= 1); 458 assert(b3.ptr.alignedAt(256)); 459 assert(a.alignedReallocate(b3, 2, 512)); 460 assert(b3.ptr.alignedAt(512)); 461 static if (hasMember!(A, "alignedDeallocate")) 462 { 463 a.alignedDeallocate(b3); 464 } 465 }} 466 else 467 { 468 static assert(!hasMember!(A, "alignedDeallocate")); 469 // This seems to be a bug in the compiler: 470 //static assert(!hasMember!(A, "alignedReallocate"), A.stringof); 471 } 472 473 static if (hasMember!(A, "allocateAll")) 474 {{ 475 auto aa = make(); 476 if (aa.allocateAll().ptr) 477 { 478 // Can't get any more memory 479 assert(!aa.allocate(1).ptr); 480 } 481 auto ab = make(); 482 const b4 = ab.allocateAll(); 483 assert(b4.length); 484 // Can't get any more memory 485 assert(!ab.allocate(1).ptr); 486 }} 487 488 static if (hasMember!(A, "expand")) 489 {{ 490 assert(a.expand(b1, 0)); 491 auto len = b1.length; 492 if (a.expand(b1, 102)) 493 { 494 assert(b1.length == len + 102, text(b1.length, " != ", len + 102)); 495 } 496 auto aa = make(); 497 void[] b5 = null; 498 assert(aa.expand(b5, 0)); 499 assert(b5 is null); 500 assert(!aa.expand(b5, 1)); 501 assert(b5.length == 0); 502 }} 503 504 void[] b6 = null; 505 assert(a.reallocate(b6, 0)); 506 assert(b6.length == 0); 507 assert(a.reallocate(b6, 1)); 508 assert(b6.length == 1, text(b6.length)); 509 assert(a.reallocate(b6, 2)); 510 assert(b6.length == 2); 511 512 // Test owns 513 static if (hasMember!(A, "owns")) 514 {{ 515 assert(a.owns(null) == Ternary.no); 516 assert(a.owns(b1) == Ternary.yes); 517 assert(a.owns(b2) == Ternary.yes); 518 assert(a.owns(b6) == Ternary.yes); 519 }} 520 521 static if (hasMember!(A, "resolveInternalPointer")) 522 {{ 523 void[] p; 524 assert(a.resolveInternalPointer(null, p) == Ternary.no); 525 Ternary r = a.resolveInternalPointer(b1.ptr, p); 526 assert(p.ptr is b1.ptr && p.length >= b1.length); 527 r = a.resolveInternalPointer(b1.ptr + b1.length / 2, p); 528 assert(p.ptr is b1.ptr && p.length >= b1.length); 529 r = a.resolveInternalPointer(b2.ptr, p); 530 assert(p.ptr is b2.ptr && p.length >= b2.length); 531 r = a.resolveInternalPointer(b2.ptr + b2.length / 2, p); 532 assert(p.ptr is b2.ptr && p.length >= b2.length); 533 r = a.resolveInternalPointer(b6.ptr, p); 534 assert(p.ptr is b6.ptr && p.length >= b6.length); 535 r = a.resolveInternalPointer(b6.ptr + b6.length / 2, p); 536 assert(p.ptr is b6.ptr && p.length >= b6.length); 537 static int[10] b7 = [ 1, 2, 3 ]; 538 assert(a.resolveInternalPointer(b7.ptr, p) == Ternary.no); 539 assert(a.resolveInternalPointer(b7.ptr + b7.length / 2, p) == Ternary.no); 540 assert(a.resolveInternalPointer(b7.ptr + b7.length, p) == Ternary.no); 541 int[3] b8 = [ 1, 2, 3 ]; 542 assert(a.resolveInternalPointer(b8.ptr, p) == Ternary.no); 543 assert(a.resolveInternalPointer(b8.ptr + b8.length / 2, p) == Ternary.no); 544 assert(a.resolveInternalPointer(b8.ptr + b8.length, p) == Ternary.no); 545 }} 546 } 547 548 package void testAllocatorObject(AllocInterface)(AllocInterface a) 549 if (is(AllocInterface : IAllocator) 550 || is (AllocInterface : shared ISharedAllocator)) 551 { 552 import std.conv : text; 553 import std.math : isPowerOf2; 554 import std.stdio : writeln, stderr; 555 import std.typecons : Ternary; 556 scope(failure) stderr.writeln("testAllocatorObject failed for ", 557 AllocInterface.stringof); 558 559 assert(a); 560 561 // Test alignment 562 assert(a.alignment.isPowerOf2); 563 564 // Test goodAllocSize 565 assert(a.goodAllocSize(1) >= a.alignment, 566 text(a.goodAllocSize(1), " < ", a.alignment)); 567 assert(a.goodAllocSize(11) >= 11.roundUpToMultipleOf(a.alignment)); 568 assert(a.goodAllocSize(111) >= 111.roundUpToMultipleOf(a.alignment)); 569 570 // Test empty 571 assert(a.empty != Ternary.no); 572 573 // Test allocate 574 assert(a.allocate(0) is null); 575 576 auto b1 = a.allocate(1); 577 assert(b1.length == 1); 578 auto b2 = a.allocate(2); 579 assert(b2.length == 2); 580 assert(b2.ptr + b2.length <= b1.ptr || b1.ptr + b1.length <= b2.ptr); 581 582 // Test alignedAllocate 583 { 584 // If not implemented it will return null, so those should pass 585 auto b3 = a.alignedAllocate(1, 256); 586 assert(b3.length <= 1); 587 assert(b3.ptr.alignedAt(256)); 588 if (a.alignedReallocate(b3, 1, 256)) 589 { 590 // If it is false, then the wrapped allocator did not implement 591 // this 592 assert(a.alignedReallocate(b3, 2, 512)); 593 assert(b3.ptr.alignedAt(512)); 594 } 595 } 596 597 // Test allocateAll 598 { 599 auto aa = a.allocateAll(); 600 if (aa.ptr) 601 { 602 // Can't get any more memory 603 assert(!a.allocate(1).ptr); 604 a.deallocate(aa); 605 } 606 const b4 = a.allocateAll(); 607 if (b4.ptr) 608 { 609 // Can't get any more memory 610 assert(!a.allocate(1).ptr); 611 } 612 } 613 614 // Test expand 615 { 616 assert(a.expand(b1, 0)); 617 auto len = b1.length; 618 if (a.expand(b1, 102)) 619 { 620 assert(b1.length == len + 102, text(b1.length, " != ", len + 102)); 621 } 622 } 623 624 void[] b6 = null; 625 assert(a.reallocate(b6, 0)); 626 assert(b6.length == 0); 627 assert(a.reallocate(b6, 1)); 628 assert(b6.length == 1, text(b6.length)); 629 assert(a.reallocate(b6, 2)); 630 assert(b6.length == 2); 631 632 // Test owns 633 { 634 if (a.owns(null) != Ternary.unknown) 635 { 636 assert(a.owns(null) == Ternary.no); 637 assert(a.owns(b1) == Ternary.yes); 638 assert(a.owns(b2) == Ternary.yes); 639 assert(a.owns(b6) == Ternary.yes); 640 } 641 } 642 643 // Test resolveInternalPointer 644 { 645 void[] p; 646 if (a.resolveInternalPointer(null, p) != Ternary.unknown) 647 { 648 assert(a.resolveInternalPointer(null, p) == Ternary.no); 649 Ternary r = a.resolveInternalPointer(b1.ptr, p); 650 assert(p.ptr is b1.ptr && p.length >= b1.length); 651 r = a.resolveInternalPointer(b1.ptr + b1.length / 2, p); 652 assert(p.ptr is b1.ptr && p.length >= b1.length); 653 r = a.resolveInternalPointer(b2.ptr, p); 654 assert(p.ptr is b2.ptr && p.length >= b2.length); 655 r = a.resolveInternalPointer(b2.ptr + b2.length / 2, p); 656 assert(p.ptr is b2.ptr && p.length >= b2.length); 657 r = a.resolveInternalPointer(b6.ptr, p); 658 assert(p.ptr is b6.ptr && p.length >= b6.length); 659 r = a.resolveInternalPointer(b6.ptr + b6.length / 2, p); 660 assert(p.ptr is b6.ptr && p.length >= b6.length); 661 static int[10] b7 = [ 1, 2, 3 ]; 662 assert(a.resolveInternalPointer(b7.ptr, p) == Ternary.no); 663 assert(a.resolveInternalPointer(b7.ptr + b7.length / 2, p) == Ternary.no); 664 assert(a.resolveInternalPointer(b7.ptr + b7.length, p) == Ternary.no); 665 int[3] b8 = [ 1, 2, 3 ]; 666 assert(a.resolveInternalPointer(b8.ptr, p) == Ternary.no); 667 assert(a.resolveInternalPointer(b8.ptr + b8.length / 2, p) == Ternary.no); 668 assert(a.resolveInternalPointer(b8.ptr + b8.length, p) == Ternary.no); 669 } 670 } 671 672 // Test deallocateAll 673 { 674 if (a.deallocateAll()) 675 { 676 if (a.empty != Ternary.unknown) 677 { 678 assert(a.empty == Ternary.yes); 679 } 680 } 681 } 682 } 683} 684