2 module std.experimental.allocator.building_blocks.free_tree;
4 import std.experimental.allocator.common;
6 //debug = std_experimental_allocator_free_tree;
10 The Free Tree allocator, stackable on top of any other allocator, bears
11 similarity with the free list allocator. Instead of a singly-linked list of
12 previously freed blocks, it maintains a binary search tree. This allows the
13 Free Tree allocator to manage blocks of arbitrary lengths and search them
16 Common uses of $(D FreeTree) include:
19 $(LI Adding $(D deallocate) capability to an allocator that lacks it (such as simple regions).)
20 $(LI Getting the benefits of multiple adaptable freelists that do not need to
21 be tuned for one specific size but insted automatically adapts itself to
22 frequently used sizes.)
25 The free tree has special handling of duplicates (a singly-linked list per
26 node) in anticipation of large number of duplicates. Allocation time from the
27 free tree is expected to be $(BIGOH log n) where $(D n) is the number of
28 distinct sizes (not total nodes) kept in the free tree.
30 Allocation requests first search the tree for a buffer of suitable size
31 deallocated in the past. If a match is found, the node is removed from the tree
32 and the memory is returned. Otherwise, the allocation is directed to $(D
33 ParentAllocator). If at this point $(D ParentAllocator) also fails to allocate,
34 $(D FreeTree) frees everything and then tries the parent allocator again.
36 Upon deallocation, the deallocated block is inserted in the internally
37 maintained free tree (not returned to the parent). The free tree is not kept
38 balanced. Instead, it has a last-in-first-out flavor because newly inserted
39 blocks are rotated to the root of the tree. That way allocations are cache
40 friendly and also frequently used sizes are more likely to be found quickly,
41 whereas seldom used sizes migrate to the leaves of the tree.
43 $(D FreeTree) rounds up small allocations to at least $(D 4 * size_t.sizeof),
44 which on 64-bit system is one cache line size. If very small objects need to
45 be efficiently allocated, the $(D FreeTree) should be fronted with an
46 appropriate small object allocator.
48 The following methods are defined if $(D ParentAllocator) defines them, and forward to it: $(D allocateAll), $(D expand), $(D owns), $(D reallocate).
50 struct FreeTree(ParentAllocator)
52 static assert(ParentAllocator.alignment % size_t.alignof == 0,
53 "FreeTree must be on top of a word-aligned allocator");
55 import std.algorithm.comparison : min, max;
56 import std.algorithm.mutation : swap;
57 import std.traits : hasMember;
60 static if (stateSize!ParentAllocator) private ParentAllocator parent;
61 else private alias parent = ParentAllocator.instance;
62 private Node* root; // that's the entire added state
69 ref Node* left() { return kid[0]; }
70 ref Node* right() { return kid[1]; }
73 // Removes "which" from the tree, returns the memory it occupied
74 private void[] remove(ref Node* which)
77 assert(!which.sibling);
78 auto result = (cast(ubyte*) which)[0 .. which.size];
79 if (!which.right) which = which.left;
80 else if (!which.left) which = which.right;
83 // result has two kids
85 // Crude randomization: alternate left/right choices
87 auto newRoot = which.kid[toggler], orphan = which.kid[!toggler];
89 for (Node* n = void; (n = newRoot.kid[!toggler]) !is null; )
93 newRoot.kid[!toggler] = orphan;
98 private void[] findAndRemove(ref Node* n, size_t s)
103 if (auto sis = n.sibling)
105 // Nice, give away one from the freelist
106 auto result = (cast(ubyte*) sis)[0 .. sis.size];
107 n.sibling = sis.sibling;
112 return findAndRemove(n.kid[s > n.size], s);
115 debug(std_experimental_allocator_free_tree)
118 import std.stdio : writef, writefln, writeln;
119 writeln(typeof(this).stringof, "@", &this, " {");
120 scope(exit) writeln("}");
124 static void recurse(Node* n, uint indent = 4)
128 writefln("%*s(null)", indent, "");
131 for (auto sis = n; sis; sis = sis.sibling)
133 writef("%*s%x (%s bytes) ", indent, "",
134 cast(void*) n, n.size);
137 if (!n.left && !n.right) return;
138 recurse(n.left, indent + 4);
139 recurse(n.right, indent + 4);
144 private string formatSizes()
147 void recurse(Node* n)
154 import std.conv : to;
155 result ~= to!string(n.size);
156 for (auto sis = n.sibling; sis; sis = sis.sibling)
160 if (n.left || n.right)
170 return result ~= ")";
173 private static void rotate(ref Node* parent, bool toRight)
176 auto opposing = parent.kid[!toRight];
177 if (!opposing) return;
178 parent.kid[!toRight] = opposing.kid[toRight];
179 opposing.kid[toRight] = parent;
183 // Inserts which into the tree, making it the new root
184 private void insertAsRoot(Node* which)
187 debug(std_experimental_allocator_free_tree)
190 scope(exit) assertValid;
193 static void recurse(ref Node* where, Node* which)
200 which.sibling = null;
203 if (which.size == where.size)
205 // Special handling of duplicates
206 which.sibling = where.sibling;
207 where.sibling = which;
212 bool goRight = which.size > where.size;
213 recurse(where.kid[goRight], which);
214 rotate(where, !goRight);
216 recurse(root, which);
219 private void assertValid()
221 debug(std_experimental_allocator_free_tree)
223 static bool isBST(Node* n, size_t lb = 0, size_t ub = size_t.max)
226 for (auto sis = n.sibling; sis; sis = sis.sibling)
228 assert(n.size == sis.size);
229 assert(sis.left is null);
230 assert(sis.right is null);
232 return lb < n.size && n.size <= ub
233 && isBST(n.left, lb, min(ub, n.size))
234 && isBST(n.right, max(lb, n.size), ub);
236 if (isBST(root)) return;
243 The $(D FreeTree) is word aligned.
245 enum uint alignment = size_t.alignof;
248 The $(D FreeTree) allocator is noncopyable.
253 The destructor of $(D FreeTree) releases all memory back to the parent
256 static if (hasMember!(ParentAllocator, "deallocate"))
263 Returns $(D parent.goodAllocSize(max(Node.sizeof, s))).
265 static if (stateSize!ParentAllocator)
266 size_t goodAllocSize(size_t s)
268 return parent.goodAllocSize(max(Node.sizeof, s));
271 static size_t goodAllocSize(size_t s)
273 return parent.goodAllocSize(max(Node.sizeof, s));
278 Allocates $(D n) bytes of memory. First consults the free tree, and returns
279 from it if a suitably sized block is found. Otherwise, the parent allocator
280 is tried. If allocation from the parent succeeds, the allocated block is
281 returned. Otherwise, the free tree tries an alternate strategy: If $(D
282 ParentAllocator) defines $(D deallocate), $(D FreeTree) releases all of its
283 contents and tries again.
285 TODO: Splitting and coalescing should be implemented if $(D ParentAllocator) does not defined $(D deallocate).
288 void[] allocate(size_t n)
291 if (n == 0) return null;
293 immutable s = goodAllocSize(n);
295 // Consult the free tree.
296 auto result = findAndRemove(root, s);
297 if (result.ptr) return result.ptr[0 .. n];
299 // No block found, try the parent allocator.
300 result = parent.allocate(s);
301 if (result.ptr) return result.ptr[0 .. n];
303 // Parent ran out of juice, desperation mode on
304 static if (hasMember!(ParentAllocator, "deallocate"))
307 // Try parent allocator again.
308 result = parent.allocate(s);
309 if (result.ptr) return result.ptr[0 .. n];
314 // TODO: get smart here
319 // Forwarding methods
320 mixin(forwardToMember("parent",
321 "allocateAll", "expand", "owns", "reallocate"));
323 /** Places $(D b) into the free tree. */
324 bool deallocate(void[] b)
326 if (!b.ptr) return true;
327 auto which = cast(Node*) b.ptr;
328 which.size = goodAllocSize(b.length);
329 // deliberately don't initialize which.left and which.right
330 assert(which.size >= Node.sizeof);
335 @system unittest // test a few simple configurations
337 import std.experimental.allocator.gc_allocator;
338 FreeTree!GCAllocator a;
339 auto b1 = a.allocate(10000);
340 auto b2 = a.allocate(20000);
341 auto b3 = a.allocate(30000);
342 assert(b1.ptr && b2.ptr && b3.ptr);
346 assert(a.formatSizes == "(20480 (12288 32768))", a.formatSizes);
348 b1 = a.allocate(10000);
349 assert(a.formatSizes == "(20480 (_ 32768))", a.formatSizes);
350 b1 = a.allocate(30000);
351 assert(a.formatSizes == "(20480)", a.formatSizes);
352 b1 = a.allocate(20000);
353 assert(a.formatSizes == "(_)", a.formatSizes);
356 @system unittest // build a complex free tree
358 import std.experimental.allocator.gc_allocator, std.range;
359 FreeTree!GCAllocator a;
360 uint[] sizes = [3008,704,1856,576,1632,672,832,1856,1120,2656,1216,672,
361 448,992,2400,1376,2688,2656,736,1440];
364 allocs ~= a.allocate(s);
365 foreach_reverse (b; allocs)
373 allocs ~= a.allocate(s);
374 assert(a.root is null);
378 /** Defined if $(D ParentAllocator.deallocate) exists, and returns to it
379 all memory held in the free tree. */
380 static if (hasMember!(ParentAllocator, "deallocate"))
383 void recurse(Node* n)
388 parent.deallocate((cast(ubyte*) n)[0 .. n.size]);
396 Defined if $(D ParentAllocator.deallocateAll) exists, and forwards to it.
397 Also nullifies the free tree (it's assumed the parent frees all memory
398 stil managed by the free tree).
401 static if (hasMember!(ParentAllocator, "deallocateAll"))
404 // This is easy, just nuke the root and deallocate all from the
407 return parent.deallocateAll;
413 import std.experimental.allocator.gc_allocator;
414 testAllocator!(() => FreeTree!GCAllocator());
417 @system unittest // issue 16506
419 import std.experimental.allocator.gc_allocator : GCAllocator;
420 import std.experimental.allocator.mallocator : Mallocator;
422 static void f(ParentAllocator)(size_t sz)
424 static FreeTree!ParentAllocator myAlloc;
425 byte[] _payload = cast(byte[]) myAlloc.allocate(sz);
426 assert(_payload, "_payload is null");
428 myAlloc.deallocate(_payload);
436 @system unittest // issue 16507
438 static struct MyAllocator
441 static bool alive = true;
442 void[] allocate(size_t s) { return new byte[](s); }
443 bool deallocate(void[] ) { if (alive) assert(false); return true; }
444 enum alignment = size_t.sizeof;
447 FreeTree!MyAllocator ft;
448 void[] x = ft.allocate(1);
451 MyAllocator.alive = false;
454 @system unittest // "desperation mode"
456 uint myDeallocCounter = 0;
461 void[] allocate(size_t s)
463 if (allocation.ptr) return null;
464 allocation = new byte[](s);
467 bool deallocate(void[] )
473 enum alignment = size_t.sizeof;
476 FreeTree!MyAllocator ft;
477 void[] x = ft.allocate(1);
479 assert(myDeallocCounter == 0);
480 x = ft.allocate(1000); // Triggers "desperation mode".
481 assert(myDeallocCounter == 1);
483 void[] y = ft.allocate(1000); /* Triggers "desperation mode" but there's
484 nothing to deallocate so MyAllocator can't deliver. */
485 assert(myDeallocCounter == 1);
486 assert(y.ptr is null);