]>
Commit | Line | Data |
---|---|---|
b4c522fa IB |
1 | /// |
2 | module std.experimental.allocator.building_blocks.free_tree; | |
3 | ||
4 | import std.experimental.allocator.common; | |
5 | ||
6 | //debug = std_experimental_allocator_free_tree; | |
7 | ||
8 | /** | |
9 | ||
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 | |
14 | efficiently. | |
15 | ||
16 | Common uses of $(D FreeTree) include: | |
17 | ||
18 | $(UL | |
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.) | |
23 | ) | |
24 | ||
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. | |
29 | ||
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. | |
35 | ||
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. | |
42 | ||
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. | |
47 | ||
48 | The following methods are defined if $(D ParentAllocator) defines them, and forward to it: $(D allocateAll), $(D expand), $(D owns), $(D reallocate). | |
49 | */ | |
50 | struct FreeTree(ParentAllocator) | |
51 | { | |
52 | static assert(ParentAllocator.alignment % size_t.alignof == 0, | |
53 | "FreeTree must be on top of a word-aligned allocator"); | |
54 | ||
55 | import std.algorithm.comparison : min, max; | |
56 | import std.algorithm.mutation : swap; | |
57 | import std.traits : hasMember; | |
58 | ||
59 | // State | |
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 | |
63 | ||
64 | private struct Node | |
65 | { | |
66 | Node*[2] kid; | |
67 | Node* sibling; | |
68 | size_t size; | |
69 | ref Node* left() { return kid[0]; } | |
70 | ref Node* right() { return kid[1]; } | |
71 | } | |
72 | ||
73 | // Removes "which" from the tree, returns the memory it occupied | |
74 | private void[] remove(ref Node* which) | |
75 | { | |
76 | assert(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; | |
81 | else | |
82 | { | |
83 | // result has two kids | |
84 | static bool toggler; | |
85 | // Crude randomization: alternate left/right choices | |
86 | toggler = !toggler; | |
87 | auto newRoot = which.kid[toggler], orphan = which.kid[!toggler]; | |
88 | which = newRoot; | |
89 | for (Node* n = void; (n = newRoot.kid[!toggler]) !is null; ) | |
90 | { | |
91 | newRoot = n; | |
92 | } | |
93 | newRoot.kid[!toggler] = orphan; | |
94 | } | |
95 | return result; | |
96 | } | |
97 | ||
98 | private void[] findAndRemove(ref Node* n, size_t s) | |
99 | { | |
100 | if (!n) return null; | |
101 | if (s == n.size) | |
102 | { | |
103 | if (auto sis = n.sibling) | |
104 | { | |
105 | // Nice, give away one from the freelist | |
106 | auto result = (cast(ubyte*) sis)[0 .. sis.size]; | |
107 | n.sibling = sis.sibling; | |
108 | return result; | |
109 | } | |
110 | return remove(n); | |
111 | } | |
112 | return findAndRemove(n.kid[s > n.size], s); | |
113 | } | |
114 | ||
115 | debug(std_experimental_allocator_free_tree) | |
116 | private void dump() | |
117 | { | |
118 | import std.stdio : writef, writefln, writeln; | |
119 | writeln(typeof(this).stringof, "@", &this, " {"); | |
120 | scope(exit) writeln("}"); | |
121 | ||
122 | if (!root) return; | |
123 | ||
124 | static void recurse(Node* n, uint indent = 4) | |
125 | { | |
126 | if (!n) | |
127 | { | |
128 | writefln("%*s(null)", indent, ""); | |
129 | return; | |
130 | } | |
131 | for (auto sis = n; sis; sis = sis.sibling) | |
132 | { | |
133 | writef("%*s%x (%s bytes) ", indent, "", | |
134 | cast(void*) n, n.size); | |
135 | } | |
136 | writeln; | |
137 | if (!n.left && !n.right) return; | |
138 | recurse(n.left, indent + 4); | |
139 | recurse(n.right, indent + 4); | |
140 | } | |
141 | recurse(root); | |
142 | } | |
143 | ||
144 | private string formatSizes() | |
145 | { | |
146 | string result = "("; | |
147 | void recurse(Node* n) | |
148 | { | |
149 | if (!n) | |
150 | { | |
151 | result ~= "_"; | |
152 | return; | |
153 | } | |
154 | import std.conv : to; | |
155 | result ~= to!string(n.size); | |
156 | for (auto sis = n.sibling; sis; sis = sis.sibling) | |
157 | { | |
158 | result ~= "+moar"; | |
159 | } | |
160 | if (n.left || n.right) | |
161 | { | |
162 | result ~= " ("; | |
163 | recurse(n.left); | |
164 | result ~= ' '; | |
165 | recurse(n.right); | |
166 | result ~= ")"; | |
167 | } | |
168 | } | |
169 | recurse(root); | |
170 | return result ~= ")"; | |
171 | } | |
172 | ||
173 | private static void rotate(ref Node* parent, bool toRight) | |
174 | { | |
175 | assert(parent); | |
176 | auto opposing = parent.kid[!toRight]; | |
177 | if (!opposing) return; | |
178 | parent.kid[!toRight] = opposing.kid[toRight]; | |
179 | opposing.kid[toRight] = parent; | |
180 | parent = opposing; | |
181 | } | |
182 | ||
183 | // Inserts which into the tree, making it the new root | |
184 | private void insertAsRoot(Node* which) | |
185 | { | |
186 | assert(which); | |
187 | debug(std_experimental_allocator_free_tree) | |
188 | { | |
189 | assertValid; | |
190 | scope(exit) assertValid; | |
191 | } | |
192 | ||
193 | static void recurse(ref Node* where, Node* which) | |
194 | { | |
195 | if (!where) | |
196 | { | |
197 | where = which; | |
198 | which.left = null; | |
199 | which.right = null; | |
200 | which.sibling = null; | |
201 | return; | |
202 | } | |
203 | if (which.size == where.size) | |
204 | { | |
205 | // Special handling of duplicates | |
206 | which.sibling = where.sibling; | |
207 | where.sibling = which; | |
208 | which.left = null; | |
209 | which.right = null; | |
210 | return; | |
211 | } | |
212 | bool goRight = which.size > where.size; | |
213 | recurse(where.kid[goRight], which); | |
214 | rotate(where, !goRight); | |
215 | } | |
216 | recurse(root, which); | |
217 | } | |
218 | ||
219 | private void assertValid() | |
220 | { | |
221 | debug(std_experimental_allocator_free_tree) | |
222 | { | |
223 | static bool isBST(Node* n, size_t lb = 0, size_t ub = size_t.max) | |
224 | { | |
225 | if (!n) return true; | |
226 | for (auto sis = n.sibling; sis; sis = sis.sibling) | |
227 | { | |
228 | assert(n.size == sis.size); | |
229 | assert(sis.left is null); | |
230 | assert(sis.right is null); | |
231 | } | |
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); | |
235 | } | |
236 | if (isBST(root)) return; | |
237 | dump; | |
238 | assert(0); | |
239 | } | |
240 | } | |
241 | ||
242 | /** | |
243 | The $(D FreeTree) is word aligned. | |
244 | */ | |
245 | enum uint alignment = size_t.alignof; | |
246 | ||
247 | /** | |
248 | The $(D FreeTree) allocator is noncopyable. | |
249 | */ | |
250 | this(this) @disable; | |
251 | ||
252 | /** | |
253 | The destructor of $(D FreeTree) releases all memory back to the parent | |
254 | allocator. | |
255 | */ | |
256 | static if (hasMember!(ParentAllocator, "deallocate")) | |
257 | ~this() | |
258 | { | |
259 | clear; | |
260 | } | |
261 | ||
262 | /** | |
263 | Returns $(D parent.goodAllocSize(max(Node.sizeof, s))). | |
264 | */ | |
265 | static if (stateSize!ParentAllocator) | |
266 | size_t goodAllocSize(size_t s) | |
267 | { | |
268 | return parent.goodAllocSize(max(Node.sizeof, s)); | |
269 | } | |
270 | else | |
271 | static size_t goodAllocSize(size_t s) | |
272 | { | |
273 | return parent.goodAllocSize(max(Node.sizeof, s)); | |
274 | } | |
275 | ||
276 | /** | |
277 | ||
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. | |
284 | ||
285 | TODO: Splitting and coalescing should be implemented if $(D ParentAllocator) does not defined $(D deallocate). | |
286 | ||
287 | */ | |
288 | void[] allocate(size_t n) | |
289 | { | |
290 | assertValid; | |
291 | if (n == 0) return null; | |
292 | ||
293 | immutable s = goodAllocSize(n); | |
294 | ||
295 | // Consult the free tree. | |
296 | auto result = findAndRemove(root, s); | |
297 | if (result.ptr) return result.ptr[0 .. n]; | |
298 | ||
299 | // No block found, try the parent allocator. | |
300 | result = parent.allocate(s); | |
301 | if (result.ptr) return result.ptr[0 .. n]; | |
302 | ||
303 | // Parent ran out of juice, desperation mode on | |
304 | static if (hasMember!(ParentAllocator, "deallocate")) | |
305 | { | |
306 | clear; | |
307 | // Try parent allocator again. | |
308 | result = parent.allocate(s); | |
309 | if (result.ptr) return result.ptr[0 .. n]; | |
310 | return null; | |
311 | } | |
312 | else | |
313 | { | |
314 | // TODO: get smart here | |
315 | return null; | |
316 | } | |
317 | } | |
318 | ||
319 | // Forwarding methods | |
320 | mixin(forwardToMember("parent", | |
321 | "allocateAll", "expand", "owns", "reallocate")); | |
322 | ||
323 | /** Places $(D b) into the free tree. */ | |
324 | bool deallocate(void[] b) | |
325 | { | |
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); | |
331 | insertAsRoot(which); | |
332 | return true; | |
333 | } | |
334 | ||
335 | @system unittest // test a few simple configurations | |
336 | { | |
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); | |
343 | a.deallocate(b1); | |
344 | a.deallocate(b3); | |
345 | a.deallocate(b2); | |
346 | assert(a.formatSizes == "(20480 (12288 32768))", a.formatSizes); | |
347 | ||
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); | |
354 | } | |
355 | ||
356 | @system unittest // build a complex free tree | |
357 | { | |
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]; | |
362 | void[][] allocs; | |
363 | foreach (s; sizes) | |
364 | allocs ~= a.allocate(s); | |
365 | foreach_reverse (b; allocs) | |
366 | { | |
367 | assert(b.ptr); | |
368 | a.deallocate(b); | |
369 | } | |
370 | a.assertValid; | |
371 | allocs = null; | |
372 | foreach (s; sizes) | |
373 | allocs ~= a.allocate(s); | |
374 | assert(a.root is null); | |
375 | a.assertValid; | |
376 | } | |
377 | ||
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")) | |
381 | void clear() | |
382 | { | |
383 | void recurse(Node* n) | |
384 | { | |
385 | if (!n) return; | |
386 | recurse(n.left); | |
387 | recurse(n.right); | |
388 | parent.deallocate((cast(ubyte*) n)[0 .. n.size]); | |
389 | } | |
390 | recurse(root); | |
391 | root = null; | |
392 | } | |
393 | ||
394 | /** | |
395 | ||
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). | |
399 | ||
400 | */ | |
401 | static if (hasMember!(ParentAllocator, "deallocateAll")) | |
402 | bool deallocateAll() | |
403 | { | |
404 | // This is easy, just nuke the root and deallocate all from the | |
405 | // parent | |
406 | root = null; | |
407 | return parent.deallocateAll; | |
408 | } | |
409 | } | |
410 | ||
411 | @system unittest | |
412 | { | |
413 | import std.experimental.allocator.gc_allocator; | |
414 | testAllocator!(() => FreeTree!GCAllocator()); | |
415 | } | |
416 | ||
417 | @system unittest // issue 16506 | |
418 | { | |
419 | import std.experimental.allocator.gc_allocator : GCAllocator; | |
420 | import std.experimental.allocator.mallocator : Mallocator; | |
421 | ||
422 | static void f(ParentAllocator)(size_t sz) | |
423 | { | |
424 | static FreeTree!ParentAllocator myAlloc; | |
425 | byte[] _payload = cast(byte[]) myAlloc.allocate(sz); | |
426 | assert(_payload, "_payload is null"); | |
427 | _payload[] = 0; | |
428 | myAlloc.deallocate(_payload); | |
429 | } | |
430 | ||
431 | f!Mallocator(33); | |
432 | f!Mallocator(43); | |
433 | f!GCAllocator(1); | |
434 | } | |
435 | ||
436 | @system unittest // issue 16507 | |
437 | { | |
438 | static struct MyAllocator | |
439 | { | |
440 | byte dummy; | |
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; | |
445 | } | |
446 | ||
447 | FreeTree!MyAllocator ft; | |
448 | void[] x = ft.allocate(1); | |
449 | ft.deallocate(x); | |
450 | ft.allocate(1000); | |
451 | MyAllocator.alive = false; | |
452 | } | |
453 | ||
454 | @system unittest // "desperation mode" | |
455 | { | |
456 | uint myDeallocCounter = 0; | |
457 | ||
458 | struct MyAllocator | |
459 | { | |
460 | byte[] allocation; | |
461 | void[] allocate(size_t s) | |
462 | { | |
463 | if (allocation.ptr) return null; | |
464 | allocation = new byte[](s); | |
465 | return allocation; | |
466 | } | |
467 | bool deallocate(void[] ) | |
468 | { | |
469 | ++myDeallocCounter; | |
470 | allocation = null; | |
471 | return true; | |
472 | } | |
473 | enum alignment = size_t.sizeof; | |
474 | } | |
475 | ||
476 | FreeTree!MyAllocator ft; | |
477 | void[] x = ft.allocate(1); | |
478 | ft.deallocate(x); | |
479 | assert(myDeallocCounter == 0); | |
480 | x = ft.allocate(1000); // Triggers "desperation mode". | |
481 | assert(myDeallocCounter == 1); | |
482 | assert(x.ptr); | |
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); | |
487 | } |