]>
Commit | Line | Data |
---|---|---|
5fee5ec3 IB |
1 | // Written in the D programming language. |
2 | /** | |
3 | Source: $(PHOBOSSRC std/experimental/allocator/building_blocks/_free_tree.d) | |
4 | */ | |
b4c522fa IB |
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 | ||
5fee5ec3 | 19 | Common uses of `FreeTree` include: |
b4c522fa IB |
20 | |
21 | $(UL | |
5fee5ec3 | 22 | $(LI Adding `deallocate` capability to an allocator that lacks it (such as simple regions).) |
b4c522fa IB |
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 | |
5fee5ec3 | 30 | free tree is expected to be $(BIGOH log n) where `n` is the number of |
b4c522fa IB |
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 | |
5fee5ec3 IB |
36 | ParentAllocator). If at this point `ParentAllocator` also fails to allocate, |
37 | `FreeTree` frees everything and then tries the parent allocator again. | |
b4c522fa IB |
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 | ||
5fee5ec3 | 46 | `FreeTree` rounds up small allocations to at least $(D 4 * size_t.sizeof), |
b4c522fa | 47 | which on 64-bit system is one cache line size. If very small objects need to |
5fee5ec3 | 48 | be efficiently allocated, the `FreeTree` should be fronted with an |
b4c522fa IB |
49 | appropriate small object allocator. |
50 | ||
5fee5ec3 | 51 | The following methods are defined if `ParentAllocator` defines them, and forward to it: `allocateAll`, `expand`, `owns`, `reallocate`. |
b4c522fa IB |
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 | /** | |
5fee5ec3 | 246 | The `FreeTree` is word aligned. |
b4c522fa IB |
247 | */ |
248 | enum uint alignment = size_t.alignof; | |
249 | ||
250 | /** | |
5fee5ec3 | 251 | The `FreeTree` allocator is noncopyable. |
b4c522fa IB |
252 | */ |
253 | this(this) @disable; | |
254 | ||
255 | /** | |
5fee5ec3 | 256 | The destructor of `FreeTree` releases all memory back to the parent |
b4c522fa IB |
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 | ||
5fee5ec3 | 281 | Allocates `n` bytes of memory. First consults the free tree, and returns |
b4c522fa IB |
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 | |
5fee5ec3 | 285 | ParentAllocator) defines `deallocate`, `FreeTree` releases all of its |
b4c522fa IB |
286 | contents and tries again. |
287 | ||
5fee5ec3 | 288 | TODO: Splitting and coalescing should be implemented if `ParentAllocator` does not defined `deallocate`. |
b4c522fa IB |
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 | ||
5fee5ec3 | 326 | /** Places `b` into the free tree. */ |
b4c522fa IB |
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); | |
5fee5ec3 IB |
346 | () nothrow @nogc { a.deallocate(b1); }(); |
347 | () nothrow @nogc { a.deallocate(b3); }(); | |
348 | () nothrow @nogc { a.deallocate(b2); }(); | |
b4c522fa IB |
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); | |
5fee5ec3 | 371 | () nothrow @nogc { a.deallocate(b); }(); |
b4c522fa IB |
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 | ||
5fee5ec3 | 381 | /** Defined if `ParentAllocator.deallocate` exists, and returns to it |
b4c522fa IB |
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 | ||
5fee5ec3 | 399 | Defined if `ParentAllocator.deallocateAll` exists, and forwards to it. |
b4c522fa IB |
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 | ||
5fee5ec3 | 414 | version (StdUnittest) |
b4c522fa IB |
415 | @system unittest |
416 | { | |
417 | import std.experimental.allocator.gc_allocator; | |
418 | testAllocator!(() => FreeTree!GCAllocator()); | |
419 | } | |
420 | ||
5fee5ec3 IB |
421 | // https://issues.dlang.org/show_bug.cgi?id=16506 |
422 | @system unittest | |
b4c522fa IB |
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; | |
5fee5ec3 | 433 | () nothrow @nogc { myAlloc.deallocate(_payload); }(); |
b4c522fa IB |
434 | } |
435 | ||
436 | f!Mallocator(33); | |
437 | f!Mallocator(43); | |
438 | f!GCAllocator(1); | |
439 | } | |
440 | ||
5fee5ec3 IB |
441 | // https://issues.dlang.org/show_bug.cgi?id=16507 |
442 | @system unittest | |
b4c522fa IB |
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); | |
5fee5ec3 | 455 | () nothrow @nogc { ft.deallocate(x); }(); |
b4c522fa IB |
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); | |
5fee5ec3 | 484 | () nothrow @nogc { ft.deallocate(x); }(); |
b4c522fa IB |
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 | } | |
5fee5ec3 IB |
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 | } |