libphobos/src/std/experimental/allocator/building_blocks/affix_allocator.d

   1 // Written in the D programming language.
   2 /**
   3 Source: $(PHOBOSSRC std/experimental/allocator/building_blocks/affix_allocator.d)
   4 */
   5 module std.experimental.allocator.building_blocks.affix_allocator;
   6
   7 /**
   8
   9 Allocator that adds some extra data before (of type `Prefix`) and/or after
  10 (of type `Suffix`) any allocation made with its parent allocator. This is
  11 useful for uses where additional allocation-related information is needed, such
  12 as mutexes, reference counts, or walls for debugging memory corruption errors.
  13
  14 If `Prefix` is not `void`, `Allocator` must guarantee an alignment at
  15 least as large as `Prefix.alignof`.
  16
  17 Suffixes are slower to get at because of alignment rounding, so prefixes should
  18 be preferred. However, small prefixes blunt the alignment so if a large
  19 alignment with a small affix is needed, suffixes should be chosen.
  20
  21 The following methods are defined if `Allocator` defines them, and forward to it: `deallocateAll`, `empty`, `owns`.
  22  */
  23 struct AffixAllocator(Allocator, Prefix, Suffix = void)
  24 {
  25     import std.algorithm.comparison : min;
  26     import core.lifetime : emplace;
  27     import std.experimental.allocator : RCIAllocator, theAllocator;
  28     import std.experimental.allocator.common : stateSize, forwardToMember,
  29         roundUpToMultipleOf, alignedAt, alignDownTo, roundUpToMultipleOf,
  30         hasStaticallyKnownAlignment;
  31     import std.math.traits : isPowerOf2;
  32     import std.traits : hasMember;
  33     import std.typecons : Ternary;
  34
  35     static if (hasStaticallyKnownAlignment!Allocator)
  36     {
  37         static assert(
  38                 !stateSize!Prefix || Allocator.alignment >= Prefix.alignof,
  39                 "AffixAllocator does not work with allocators offering a smaller"
  40                 ~ " alignment than the prefix alignment.");
  41     }
  42     static assert(alignment % Suffix.alignof == 0,
  43         "This restriction could be relaxed in the future.");
  44
  45     /**
  46     If `Prefix` is `void`, the alignment is that of the parent. Otherwise, the alignment is the same as the `Prefix`'s alignment.
  47     */
  48     static if (hasStaticallyKnownAlignment!Allocator)
  49     {
  50         enum uint alignment = isPowerOf2(stateSize!Prefix)
  51             ? min(stateSize!Prefix, Allocator.alignment)
  52             : (stateSize!Prefix ? Prefix.alignof : Allocator.alignment);
  53     }
  54     else static if (is(Prefix == void))
  55     {
  56         enum uint alignment = platformAlignment;
  57     }
  58     else
  59     {
  60         enum uint alignment = Prefix.alignof;
  61     }
  62
  63     /**
  64     If the parent allocator `Allocator` is stateful, an instance of it is
  65     stored as a member. Otherwise, `AffixAllocator` uses
  66     `Allocator.instance`. In either case, the name `_parent` is uniformly
  67     used for accessing the parent allocator.
  68     */
  69     static if (stateSize!Allocator)
  70     {
  71         Allocator _parent;
  72         static if (is(Allocator == RCIAllocator))
  73         {
  74             @nogc nothrow pure @safe
  75             Allocator parent()
  76             {
  77                 static @nogc nothrow
  78                 RCIAllocator wrapAllocatorObject()
  79                 {
  80                     import std.experimental.allocator.gc_allocator : GCAllocator;
  81                     import std.experimental.allocator : allocatorObject;
  82
  83                     return allocatorObject(GCAllocator.instance);
  84                 }
  85
  86                 if (_parent.isNull)
  87                 {
  88                     // If the `_parent` allocator is `null` we will assign
  89                     // an object that references the GC as the `parent`.
  90                     auto fn = (() @trusted =>
  91                             cast(RCIAllocator function() @nogc nothrow pure @safe)(&wrapAllocatorObject))();
  92                     _parent = fn();
  93                 }
  94
  95                 // `RCIAllocator.alignment` currently doesn't have any attributes
  96                 // so we must cast; throughout the allocators module, `alignment`
  97                 // is defined as an `enum` for the existing allocators.
  98                 // `alignment` should always be `@nogc nothrow pure @safe`; once
  99                 // this is enforced by the interface we can remove the cast
 100                 auto pureAlign = (() @trusted =>
 101                         cast(uint delegate() @nogc nothrow pure @safe)(&_parent.alignment))();
 102                 assert(alignment <= pureAlign());
 103                 return _parent;
 104             }
 105         }
 106         else
 107         {
 108             alias parent = _parent;
 109         }
 110     }
 111     else
 112     {
 113         alias parent = Allocator.instance;
 114     }
 115
 116     private template Impl()
 117     {
 118
 119         size_t goodAllocSize(size_t s)
 120         {
 121             import std.experimental.allocator.common : goodAllocSize;
 122             auto a = actualAllocationSize(s);
 123             return roundUpToMultipleOf(parent.goodAllocSize(a)
 124                     - stateSize!Prefix - stateSize!Suffix,
 125                 this.alignment);
 126         }
 127
 128         private size_t actualAllocationSize(size_t s) const
 129         {
 130             assert(s > 0);
 131             static if (!stateSize!Suffix)
 132             {
 133                 return s + stateSize!Prefix;
 134             }
 135             else
 136             {
 137                 return
 138                     roundUpToMultipleOf(s + stateSize!Prefix, Suffix.alignof)
 139                     + stateSize!Suffix;
 140             }
 141         }
 142
 143         private void[] actualAllocation(void[] b) const
 144         {
 145             assert(b !is null);
 146             return (b.ptr - stateSize!Prefix)
 147                 [0 .. actualAllocationSize(b.length)];
 148         }
 149
 150         // Common code shared between allocate and allocateZeroed.
 151         private enum _processAndReturnAllocateResult =
 152         q{
 153             if (result is null) return null;
 154             static if (stateSize!Prefix)
 155             {
 156                 assert(result.ptr.alignedAt(Prefix.alignof));
 157                 emplace!Prefix(cast(Prefix*) result.ptr);
 158             }
 159             static if (stateSize!Suffix)
 160             {
 161                 auto suffixP = result.ptr + result.length - Suffix.sizeof;
 162                 assert(suffixP.alignedAt(Suffix.alignof));
 163                 emplace!Suffix(cast(Suffix*)(suffixP));
 164             }
 165             return result[stateSize!Prefix .. stateSize!Prefix + bytes];
 166         };
 167
 168         void[] allocate(size_t bytes)
 169         {
 170             if (!bytes) return null;
 171             auto result = parent.allocate(actualAllocationSize(bytes));
 172             mixin(_processAndReturnAllocateResult);
 173         }
 174
 175         static if (hasMember!(Allocator, "allocateZeroed"))
 176         package(std) void[] allocateZeroed()(size_t bytes)
 177         {
 178             if (!bytes) return null;
 179             auto result = parent.allocateZeroed(actualAllocationSize(bytes));
 180             mixin(_processAndReturnAllocateResult);
 181         }
 182
 183         static if (hasMember!(Allocator, "allocateAll"))
 184         void[] allocateAll()
 185         {
 186             auto result = parent.allocateAll();
 187             if (result is null) return null;
 188             if (result.length < actualAllocationSize(1))
 189             {
 190                 deallocate(result);
 191                 return null;
 192             }
 193             static if (stateSize!Prefix)
 194             {
 195                 assert(result.length > stateSize!Prefix);
 196                 emplace!Prefix(cast(Prefix*) result.ptr);
 197                 result = result[stateSize!Prefix .. $];
 198             }
 199             static if (stateSize!Suffix)
 200             {
 201                 assert(result.length > stateSize!Suffix);
 202                 // Ehm, find a properly aligned place for the suffix
 203                 auto p = (result.ptr + result.length - stateSize!Suffix)
 204                     .alignDownTo(Suffix.alignof);
 205                 assert(p > result.ptr);
 206                 emplace!Suffix(cast(Suffix*) p);
 207                 result = result[0 .. p - result.ptr];
 208             }
 209             return result;
 210         }
 211
 212         static if (hasMember!(Allocator, "owns"))
 213         Ternary owns(void[] b)
 214         {
 215             if (b is null) return Ternary.no;
 216             return parent.owns((() @trusted => actualAllocation(b))());
 217         }
 218
 219         static if (hasMember!(Allocator, "resolveInternalPointer"))
 220         Ternary resolveInternalPointer(const void* p, ref void[] result)
 221         {
 222             void[] p1;
 223             Ternary r = parent.resolveInternalPointer(p, p1);
 224             if (r != Ternary.yes || p1 is null)
 225                 return r;
 226             p1 = p1[stateSize!Prefix .. $];
 227             auto p2 = (() @trusted => (&p1[0] + p1.length - stateSize!Suffix)
 228                                       .alignDownTo(Suffix.alignof))();
 229             result = p1[0 .. p2 - &p1[0]];
 230             return Ternary.yes;
 231         }
 232
 233         static if (!stateSize!Suffix && hasMember!(Allocator, "expand")
 234                     && hasMember!(Allocator, "owns"))
 235         bool expand(ref void[] b, size_t delta)
 236         {
 237             if (!b || delta == 0) return delta == 0;
 238             if (owns(b) == Ternary.no) return false;
 239             auto t = (() @trusted => actualAllocation(b))();
 240             const result = parent.expand(t, delta);
 241             if (!result) return false;
 242             b = (() @trusted => b.ptr[0 .. b.length + delta])();
 243             return true;
 244         }
 245
 246         static if (hasMember!(Allocator, "reallocate"))
 247         bool reallocate(ref void[] b, size_t s)
 248         {
 249             if (b is null)
 250             {
 251                 b = allocate(s);
 252                 return b.length == s;
 253             }
 254             auto t = actualAllocation(b);
 255             const result = parent.reallocate(t, actualAllocationSize(s));
 256             if (!result) return false; // no harm done
 257             b = t.ptr[stateSize!Prefix .. stateSize!Prefix + s];
 258             return true;
 259         }
 260
 261         static if (hasMember!(Allocator, "deallocate"))
 262         bool deallocate(void[] b)
 263         {
 264             if (!b.ptr) return true;
 265             return parent.deallocate(actualAllocation(b));
 266         }
 267
 268         /* The following methods are defined if `ParentAllocator` defines
 269         them, and forward to it: `deallocateAll`, `empty`.*/
 270         mixin(forwardToMember("parent",
 271             "deallocateAll", "empty"));
 272
 273         // Computes suffix type given buffer type
 274         private template Payload2Affix(Payload, Affix)
 275         {
 276             static if (is(Payload[] : void[]))
 277                 alias Payload2Affix = Affix;
 278             else static if (is(Payload[] : shared(void)[]))
 279                 alias Payload2Affix = shared Affix;
 280             else static if (is(Payload[] : immutable(void)[]))
 281                 alias Payload2Affix = shared Affix;
 282             else static if (is(Payload[] : const(shared(void))[]))
 283                 alias Payload2Affix = shared Affix;
 284             else static if (is(Payload[] : const(void)[]))
 285                 alias Payload2Affix = const Affix;
 286             else
 287                 static assert(0, "Internal error for type " ~ Payload.stringof);
 288         }
 289
 290         // Extra functions
 291         static if (stateSize!Prefix)
 292         {
 293             static auto ref prefix(T)(T[] b)
 294             {
 295                 assert(b.ptr && b.ptr.alignedAt(Prefix.alignof));
 296                 return (cast(Payload2Affix!(T, Prefix)*) b.ptr)[-1];
 297             }
 298         }
 299         static if (stateSize!Suffix)
 300             auto ref suffix(T)(T[] b)
 301             {
 302                 assert(b.ptr);
 303                 auto p = b.ptr - stateSize!Prefix
 304                     + actualAllocationSize(b.length);
 305                 assert(p && p.alignedAt(Suffix.alignof));
 306                 return (cast(Payload2Affix!(T, Suffix)*) p)[-1];
 307             }
 308     }
 309
 310     version (StdDdoc)
 311     {
 312         /**
 313         Standard allocator methods. Each is defined if and only if the parent
 314         allocator defines the homonym method (except for `goodAllocSize`,
 315         which may use the global default). Also, the methods will be $(D
 316         shared) if the parent allocator defines them as such.
 317         */
 318         size_t goodAllocSize(size_t);
 319         /// Ditto
 320         void[] allocate(size_t);
 321         /// Ditto
 322         Ternary owns(void[]);
 323         /// Ditto
 324         bool expand(ref void[] b, size_t delta);
 325         /// Ditto
 326         bool reallocate(ref void[] b, size_t s);
 327         /// Ditto
 328         bool deallocate(void[] b);
 329         /// Ditto
 330         bool deallocateAll();
 331         /// Ditto
 332         Ternary empty();
 333
 334         /**
 335         The `instance` singleton is defined if and only if the parent allocator
 336         has no state and defines its own `it` object.
 337         */
 338         static AffixAllocator instance;
 339
 340         /**
 341         Affix access functions offering references to the affixes of a
 342         block `b` previously allocated with this allocator. `b` may not be null.
 343         They are defined if and only if the corresponding affix is not `void`.
 344
 345         The qualifiers of the affix are not always the same as the qualifiers
 346         of the argument. This is because the affixes are not part of the data
 347         itself, but instead are just $(I associated) with the data and known
 348         to the allocator. The table below documents the type of `preffix(b)` and
 349         `affix(b)` depending on the type of `b`.
 350
 351         $(BOOKTABLE Result of `prefix`/`suffix` depending on argument (`U` is
 352         any unqualified type, `Affix` is `Prefix` or `Suffix`),
 353             $(TR $(TH Argument$(NBSP)Type) $(TH Return) $(TH Comments))
 354
 355             $(TR $(TD `shared(U)[]`) $(TD `ref shared Affix`)
 356             $(TD Data is shared across threads and the affix follows suit.))
 357
 358             $(TR $(TD `immutable(U)[]`) $(TD `ref shared Affix`)
 359             $(TD Although the data is immutable, the allocator "knows" the
 360             underlying memory is mutable, so `immutable` is elided for the affix
 361             which is independent from the data itself. However, the result is
 362             `shared` because `immutable` is implicitly shareable so multiple
 363             threads may access and manipulate the affix for the same data.))
 364
 365             $(TR $(TD `const(shared(U))[]`) $(TD `ref shared Affix`)
 366             $(TD The data is always shareable across threads. Even if the data
 367             is `const`, the affix is modifiable by the same reasoning as for
 368             `immutable`.))
 369
 370             $(TR $(TD `const(U)[]`) $(TD `ref const Affix`)
 371             $(TD The input may have originated from `U[]` or `immutable(U)[]`,
 372             so it may be actually shared or not. Returning an unqualified affix
 373             may result in race conditions, whereas returning a `shared` affix
 374             may result in inadvertent sharing of mutable thread-local data
 375             across multiple threads. So the returned type is conservatively
 376             `ref const`.))
 377
 378             $(TR $(TD `U[]`) $(TD `ref Affix`)
 379             $(TD Unqualified data has unqualified affixes.))
 380         )
 381
 382         Precondition: `b !is null` and `b` must have been allocated with
 383         this allocator.
 384         */
 385         static ref auto prefix(T)(T[] b);
 386         /// Ditto
 387         ref auto suffix(T)(T[] b);
 388     }
 389     else static if (is(typeof(Allocator.instance) == shared))
 390     {
 391         static assert(stateSize!Allocator == 0);
 392         static shared AffixAllocator instance;
 393         shared { mixin Impl!(); }
 394     }
 395     else static if (is(Allocator == shared))
 396     {
 397         static assert(stateSize!Allocator != 0);
 398         shared { mixin Impl!(); }
 399     }
 400     else
 401     {
 402         mixin Impl!();
 403         static if (stateSize!Allocator == 0)
 404             __gshared AffixAllocator instance;
 405     }
 406 }
 407
 408 ///
 409 @system unittest
 410 {
 411     import std.experimental.allocator.mallocator : Mallocator;
 412     // One word before and after each allocation.
 413     alias A = AffixAllocator!(Mallocator, size_t, size_t);
 414     auto b = A.instance.allocate(11);
 415     A.instance.prefix(b) = 0xCAFE_BABE;
 416     A.instance.suffix(b) = 0xDEAD_BEEF;
 417     assert(A.instance.prefix(b) == 0xCAFE_BABE
 418         && A.instance.suffix(b) == 0xDEAD_BEEF);
 419 }
 420
 421 @system unittest
 422 {
 423     import std.experimental.allocator.gc_allocator : GCAllocator;
 424     import std.experimental.allocator : theAllocator, RCIAllocator;
 425
 426     // One word before and after each allocation.
 427     auto A = AffixAllocator!(RCIAllocator, size_t, size_t)(theAllocator);
 428     auto a = A.allocate(11);
 429     A.prefix(a) = 0xCAFE_BABE;
 430     A.suffix(a) = 0xDEAD_BEEF;
 431     assert(A.prefix(a) == 0xCAFE_BABE
 432         && A.suffix(a) == 0xDEAD_BEEF);
 433
 434     // One word before and after each allocation.
 435     auto B = AffixAllocator!(RCIAllocator, size_t, size_t)();
 436     auto b = B.allocate(11);
 437     B.prefix(b) = 0xCAFE_BABE;
 438     B.suffix(b) = 0xDEAD_BEEF;
 439     assert(B.prefix(b) == 0xCAFE_BABE
 440         && B.suffix(b) == 0xDEAD_BEEF);
 441 }
 442
 443 version (StdUnittest)
 444 @system unittest
 445 {
 446     import std.experimental.allocator.building_blocks.bitmapped_block
 447         : BitmappedBlock;
 448     import std.experimental.allocator.common : testAllocator;
 449     testAllocator!({
 450         auto a = AffixAllocator!(BitmappedBlock!128, ulong, ulong)
 451             (BitmappedBlock!128(new ubyte[128 * 4096]));
 452         return a;
 453     });
 454 }
 455
 456 // Test empty
 457 @system unittest
 458 {
 459     import std.experimental.allocator.building_blocks.bitmapped_block : BitmappedBlock;
 460     import std.typecons : Ternary;
 461
 462     auto a = AffixAllocator!(BitmappedBlock!128, ulong, ulong)
 463                 (BitmappedBlock!128(new ubyte[128 * 4096]));
 464     assert((() pure nothrow @safe @nogc => a.empty)() == Ternary.yes);
 465     auto b = a.allocate(42);
 466     assert(b.length == 42);
 467     assert((() pure nothrow @safe @nogc => a.empty)() == Ternary.no);
 468 }
 469
 470 @system unittest
 471 {
 472     import std.experimental.allocator.mallocator : Mallocator;
 473     alias A = AffixAllocator!(Mallocator, size_t);
 474     auto b = A.instance.allocate(10);
 475     A.instance.prefix(b) = 10;
 476     assert(A.instance.prefix(b) == 10);
 477
 478     import std.experimental.allocator.building_blocks.null_allocator
 479         : NullAllocator;
 480     alias B = AffixAllocator!(NullAllocator, size_t);
 481     b = B.instance.allocate(100);
 482     assert(b is null);
 483 }
 484
 485 @system unittest
 486 {
 487     import std.experimental.allocator;
 488     import std.experimental.allocator.gc_allocator;
 489     import std.typecons : Ternary;
 490     alias MyAllocator = AffixAllocator!(GCAllocator, uint);
 491     auto a = MyAllocator.instance.makeArray!(shared int)(100);
 492     static assert(is(typeof(&MyAllocator.instance.prefix(a)) == shared(uint)*));
 493     auto b = MyAllocator.instance.makeArray!(shared const int)(100);
 494     static assert(is(typeof(&MyAllocator.instance.prefix(b)) == shared(uint)*));
 495     auto c = MyAllocator.instance.makeArray!(immutable int)(100);
 496     static assert(is(typeof(&MyAllocator.instance.prefix(c)) == shared(uint)*));
 497     auto d = MyAllocator.instance.makeArray!(int)(100);
 498     static assert(is(typeof(&MyAllocator.instance.prefix(d)) == uint*));
 499     auto e = MyAllocator.instance.makeArray!(const int)(100);
 500     static assert(is(typeof(&MyAllocator.instance.prefix(e)) == const(uint)*));
 501
 502     void[] p;
 503     assert((() nothrow @safe @nogc => MyAllocator.instance.resolveInternalPointer(null, p))() == Ternary.no);
 504     assert((() nothrow @safe => MyAllocator.instance.resolveInternalPointer(&d[0], p))() == Ternary.yes);
 505     assert(p.ptr is d.ptr && p.length >= d.length);
 506 }
 507
 508 @system unittest
 509 {
 510     import std.experimental.allocator.gc_allocator;
 511     alias a = AffixAllocator!(GCAllocator, uint).instance;
 512
 513     // Check that goodAllocSize inherits from parent, i.e. GCAllocator
 514     assert(__traits(compiles, (() nothrow @safe @nogc => a.goodAllocSize(1))()));
 515
 516     // Ensure deallocate inherits from parent
 517     auto b = a.allocate(42);
 518     assert(b.length == 42);
 519     () nothrow @nogc { a.deallocate(b); }();
 520 }
 521
 522 @system unittest
 523 {
 524     import std.experimental.allocator.building_blocks.region : Region;
 525
 526     auto a = AffixAllocator!(Region!(), uint)(Region!()(new ubyte[1024 * 64]));
 527     auto b = a.allocate(42);
 528     assert(b.length == 42);
 529     // Test that expand infers from parent
 530     assert((() pure nothrow @safe @nogc => a.expand(b, 58))());
 531     assert(b.length == 100);
 532     // Test that deallocateAll infers from parent
 533     assert((() nothrow @nogc => a.deallocateAll())());
 534 }
 535
 536 // Test that reallocate infers from parent
 537 @system unittest
 538 {
 539     import std.experimental.allocator.mallocator : Mallocator;
 540
 541     alias a = AffixAllocator!(Mallocator, uint).instance;
 542     auto b = a.allocate(42);
 543     assert(b.length == 42);
 544     assert((() nothrow @nogc => a.reallocate(b, 100))());
 545     assert(b.length == 100);
 546     assert((() nothrow @nogc => a.deallocate(b))());
 547 }
 548
 549 @system unittest
 550 {
 551     import std.experimental.allocator : processAllocator, RCISharedAllocator;
 552     import std.traits;
 553
 554     alias SharedAllocT = shared AffixAllocator!(RCISharedAllocator, int);
 555     static assert(is(RCISharedAllocator == shared));
 556     static assert(!is(SharedAllocT.instance));
 557
 558     SharedAllocT a = SharedAllocT(processAllocator);
 559     auto buf = a.allocate(10);
 560     static assert(is(typeof(a.allocate) == shared));
 561     assert(buf.length == 10);
 562 }