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

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