1 // Written in the D programming language.
2 /**
3 Source: $(PHOBOSSRC std/experimental/allocator/building_blocks/fallback_allocator.d)
4 */
5 module std.experimental.allocator.building_blocks.fallback_allocator;
6 
7 import std.experimental.allocator.common;
8 
9 /**
10 `FallbackAllocator` is the allocator equivalent of an "or" operator in
11 algebra. An allocation request is first attempted with the `Primary`
12 allocator. If that returns `null`, the request is forwarded to the $(D
13 Fallback) allocator. All other requests are dispatched appropriately to one of
14 the two allocators.
15 
16 In order to work, `FallbackAllocator` requires that `Primary` defines the
17 `owns` method. This is needed in order to decide which allocator was
18 responsible for a given allocation.
19 
20 `FallbackAllocator` is useful for fast, special-purpose allocators backed up
21 by general-purpose allocators. The example below features a stack region backed
22 up by the `GCAllocator`.
23 */
24 struct FallbackAllocator(Primary, Fallback)
25 {
26     import std.algorithm.comparison : min;
27     import std.traits : hasMember;
28     import std.typecons : Ternary;
29 
30     // Need both allocators to be stateless
31     // This is to avoid using default initialized stateful allocators
32     static if (!stateSize!Primary && !stateSize!Fallback)
33     version (StdUnittest)
34     @system unittest
35     {
36         testAllocator!(() => FallbackAllocator());
37     }
38 
39     /// The primary allocator.
40     static if (stateSize!Primary) Primary primary;
41     else alias primary = Primary.instance;
42 
43     /// The fallback allocator.
44     static if (stateSize!Fallback) Fallback fallback;
45     else alias fallback = Fallback.instance;
46 
47     /**
48     If both `Primary` and `Fallback` are stateless, `FallbackAllocator`
49     defines a static instance called `instance`.
50     */
51     static if (!stateSize!Primary && !stateSize!Fallback)
52     {
53         static FallbackAllocator instance;
54     }
55 
56     /**
57     The alignment offered is the minimum of the two allocators' alignment.
58     */
59     enum uint alignment = min(Primary.alignment, Fallback.alignment);
60 
61     /**
62     Allocates memory trying the primary allocator first. If it returns $(D
63     null), the fallback allocator is tried.
64     */
65     void[] allocate(size_t s)
66     {
67         auto result = primary.allocate(s);
68         return result.length == s ? result : fallback.allocate(s);
69     }
70 
71     static if (hasMember!(Primary, "allocateZeroed")
72             || (hasMember!(Fallback, "allocateZeroed")))
73     package(std) void[] allocateZeroed()(size_t s)
74     {
75         // Try to allocate with primary.
76         static if (hasMember!(Primary, "allocateZeroed"))
77         {
78             void[] result = primary.allocateZeroed(s);
79             if (result.length == s) return result;
80         }
81         else
82         {
83             void[] result = primary.allocate(s);
84             if (result.length == s)
85             {
86                 (() @trusted => (cast(ubyte[]) result)[] = 0)();
87                 return result;
88             }
89         }
90         // Allocate with fallback.
91         static if (hasMember!(Fallback, "allocateZeroed"))
92         {
93             return fallback.allocateZeroed(s);
94         }
95         else
96         {
97             result = fallback.allocate(s);
98             (() @trusted => (cast(ubyte[]) result)[] = 0)(); // OK even if result is null.
99             return result;
100         }
101     }
102 
103     /**
104     `FallbackAllocator` offers `alignedAllocate` iff at least one of the
105     allocators also offers it. It attempts to allocate using either or both.
106     */
107     static if (hasMember!(Primary, "alignedAllocate")
108         || hasMember!(Fallback, "alignedAllocate"))
109     void[] alignedAllocate(size_t s, uint a)
110     {
111         static if (hasMember!(Primary, "alignedAllocate"))
112         {{
113             auto result = primary.alignedAllocate(s, a);
114             if (result.length == s) return result;
115         }}
116         static if (hasMember!(Fallback, "alignedAllocate"))
117         {{
118             auto result = fallback.alignedAllocate(s, a);
119             if (result.length == s) return result;
120         }}
121         return null;
122     }
123 
124     /**
125 
126     `expand` is defined if and only if at least one of the allocators
127     defines `expand`. It works as follows. If `primary.owns(b)`, then the
128     request is forwarded to `primary.expand` if it is defined, or fails
129     (returning `false`) otherwise. If `primary` does not own `b`, then
130     the request is forwarded to `fallback.expand` if it is defined, or fails
131     (returning `false`) otherwise.
132 
133     */
134     static if (hasMember!(Primary, "owns")
135         && (hasMember!(Primary, "expand") || hasMember!(Fallback, "expand")))
136     bool expand(ref void[] b, size_t delta)
137     {
138         if (!delta) return true;
139         if (!b.ptr) return false;
140         if (primary.owns(b) == Ternary.yes)
141         {
142             static if (hasMember!(Primary, "expand"))
143                 return primary.expand(b, delta);
144             else
145                 return false;
146         }
147         static if (hasMember!(Fallback, "expand"))
148             return fallback.expand(b, delta);
149         else
150             return false;
151     }
152 
153     /**
154 
155     `reallocate` works as follows. If `primary.owns(b)`, then $(D
156     primary.reallocate(b, newSize)) is attempted. If it fails, an attempt is
157     made to move the allocation from `primary` to `fallback`.
158 
159     If `primary` does not own `b`, then $(D fallback.reallocate(b,
160     newSize)) is attempted. If that fails, an attempt is made to move the
161     allocation from `fallback` to `primary`.
162 
163     */
164     static if (hasMember!(Primary, "owns"))
165     bool reallocate(ref void[] b, size_t newSize)
166     {
167         bool crossAllocatorMove(From, To)(ref From from, ref To to)
168         {
169             auto b1 = to.allocate(newSize);
170             if (b1.length != newSize) return false;
171             if (b.length < newSize) b1[0 .. b.length] = b[];
172             else b1[] = b[0 .. newSize];
173             static if (hasMember!(From, "deallocate"))
174                 from.deallocate(b);
175             b = b1;
176             return true;
177         }
178 
179         if (b is null || primary.owns(b) == Ternary.yes)
180         {
181             return primary.reallocate(b, newSize)
182                 // Move from primary to fallback
183                 || crossAllocatorMove(primary, fallback);
184         }
185         return fallback.reallocate(b, newSize)
186             // Interesting. Move from fallback to primary.
187             || crossAllocatorMove(fallback, primary);
188     }
189 
190     static if (hasMember!(Primary, "owns")
191         && (hasMember!(Primary, "alignedAllocate")
192             || hasMember!(Fallback, "alignedAllocate")))
193     bool alignedReallocate(ref void[] b, size_t newSize, uint a)
194     {
195         bool crossAllocatorMove(From, To)(ref From from, ref To to)
196         {
197             static if (!hasMember!(To, "alignedAllocate"))
198             {
199                 return false;
200             }
201             else
202             {
203                 auto b1 = to.alignedAllocate(newSize, a);
204                 if (b1.length != newSize) return false;
205                 if (b.length < newSize) b1[0 .. b.length] = b[];
206                 else b1[] = b[0 .. newSize];
207                 static if (hasMember!(From, "deallocate"))
208                     from.deallocate(b);
209                 b = b1;
210                 return true;
211             }
212         }
213 
214         static if (hasMember!(Primary, "alignedAllocate"))
215         {
216             if (b is null || primary.owns(b) == Ternary.yes)
217             {
218                 return primary.alignedReallocate(b, newSize, a)
219                     || crossAllocatorMove(primary, fallback);
220             }
221         }
222         static if (hasMember!(Fallback, "alignedAllocate"))
223         {
224             return fallback.alignedReallocate(b, newSize, a)
225                 || crossAllocatorMove(fallback, primary);
226         }
227         else
228         {
229             return false;
230         }
231     }
232 
233     /**
234     `owns` is defined if and only if both allocators define `owns`.
235     Returns $(D primary.owns(b) | fallback.owns(b)).
236     */
237     static if (hasMember!(Primary, "owns") && hasMember!(Fallback, "owns"))
238     Ternary owns(void[] b)
239     {
240         return primary.owns(b) | fallback.owns(b);
241     }
242 
243     /**
244     `resolveInternalPointer` is defined if and only if both allocators
245     define it.
246     */
247     static if (hasMember!(Primary, "resolveInternalPointer")
248         && hasMember!(Fallback, "resolveInternalPointer"))
249     Ternary resolveInternalPointer(const void* p, ref void[] result)
250     {
251         Ternary r = primary.resolveInternalPointer(p, result);
252         return r == Ternary.no ? fallback.resolveInternalPointer(p, result) : r;
253     }
254 
255     /**
256     `deallocate` is defined if and only if at least one of the allocators
257     define    `deallocate`. It works as follows. If `primary.owns(b)`,
258     then the request is forwarded to `primary.deallocate` if it is defined,
259     or is a no-op otherwise. If `primary` does not own `b`, then the
260     request is forwarded to `fallback.deallocate` if it is defined, or is a
261     no-op otherwise.
262     */
263     static if (hasMember!(Primary, "owns") &&
264         (hasMember!(Primary, "deallocate")
265             || hasMember!(Fallback, "deallocate")))
266     bool deallocate(void[] b)
267     {
268         if (primary.owns(b) == Ternary.yes)
269         {
270             static if (hasMember!(Primary, "deallocate"))
271                 return primary.deallocate(b);
272             else
273                 return false;
274         }
275         else
276         {
277             static if (hasMember!(Fallback, "deallocate"))
278                 return fallback.deallocate(b);
279             else
280                 return false;
281         }
282     }
283 
284     /**
285     `empty` is defined if both allocators also define it.
286 
287     Returns: $(D primary.empty & fallback.empty)
288     */
289     static if (hasMember!(Primary, "empty")
290                && hasMember!(Fallback, "empty"))
291     Ternary empty()
292     {
293         return primary.empty & fallback.empty;
294     }
295 }
296 
297 @system unittest
298 {
299     import std.conv : text;
300     import std.experimental.allocator.building_blocks.region : InSituRegion;
301     import std.experimental.allocator.gc_allocator : GCAllocator;
302     import std.typecons : Ternary;
303     FallbackAllocator!(InSituRegion!16_384, GCAllocator) a;
304     // This allocation uses the stack
305     auto b1 = a.allocate(1024);
306     assert(b1.length == 1024, text(b1.length));
307     assert((() pure nothrow @safe @nogc => a.primary.owns(b1))() == Ternary.yes);
308     assert((() nothrow => a.reallocate(b1, 2048))());
309     assert(b1.length == 2048, text(b1.length));
310     assert((() pure nothrow @safe @nogc => a.primary.owns(b1))() == Ternary.yes);
311     // This large allocation will go to the GCAllocator
312     auto b2 = a.allocate(1024 * 1024);
313     assert((() pure nothrow @safe @nogc => a.primary.owns(b2))() == Ternary.no);
314     // Ensure deallocate inherits from parent allocators
315     () nothrow @nogc { a.deallocate(b1); }();
316     () nothrow @nogc { a.deallocate(b2); }();
317 }
318 
319 @system unittest
320 {
321     import std.experimental.allocator.building_blocks.bitmapped_block : BitmappedBlockWithInternalPointers;
322     import std.typecons : Ternary;
323 
324     alias A =
325         FallbackAllocator!(
326             BitmappedBlockWithInternalPointers!(4096),
327             BitmappedBlockWithInternalPointers!(4096)
328         );
329 
330     A a = A(
331             BitmappedBlockWithInternalPointers!(4096)(new ubyte[4096 * 1024]),
332             BitmappedBlockWithInternalPointers!(4096)(new ubyte[4096 * 1024])
333     );
334 
335     assert((() nothrow @safe @nogc => a.empty)() == Ternary.yes);
336     auto b = a.allocate(201);
337     assert(b.length == 201);
338     assert(a.reallocate(b, 202));
339     assert(b.length == 202);
340     assert((() nothrow @safe @nogc => a.empty)() == Ternary.no);
341 }
342 
343 @system unittest
344 {
345     import std.experimental.allocator.building_blocks.region : BorrowedRegion;
346     import std.typecons : Ternary;
347 
348     auto a = FallbackAllocator!(BorrowedRegion!(), BorrowedRegion!())(
349                 BorrowedRegion!()(new ubyte[4096 * 1024]),
350                 BorrowedRegion!()(new ubyte[4096 * 1024]));
351 
352     auto b = a.alignedAllocate(42, 8);
353     assert(b.length == 42);
354     assert((() nothrow @nogc => a.alignedReallocate(b, 100, 8))());
355     assert(b.length == 100);
356 }
357 
358 version (StdUnittest)
359 @system unittest
360 {
361     import std.experimental.allocator.building_blocks.bitmapped_block : BitmappedBlockWithInternalPointers;
362     import std.typecons : Ternary;
363 
364     alias A =
365         FallbackAllocator!(
366             BitmappedBlockWithInternalPointers!(4096),
367             BitmappedBlockWithInternalPointers!(4096)
368         );
369 
370     // Run testAllocator here since both allocators stateful
371     testAllocator!(
372         () => A(
373             BitmappedBlockWithInternalPointers!(4096)(new ubyte[4096 * 1024]),
374             BitmappedBlockWithInternalPointers!(4096)(new ubyte[4096 * 1024])
375         )
376     );
377 }
378 
379 @system unittest
380 {
381     import std.experimental.allocator.mallocator : Mallocator;
382     import std.typecons : Ternary;
383 
384     alias a = FallbackAllocator!(Mallocator, Mallocator).instance;
385 
386     auto b = a.allocate(42);
387     assert(b.length == 42);
388     assert((() nothrow @nogc => a.reallocate(b, 100))());
389     assert(b.length == 100);
390 }
391 
392 /*
393 Forwards an argument from one function to another
394 */
395 private auto ref forward(alias arg)()
396 {
397     static if (__traits(isRef, arg))
398     {
399         return arg;
400     }
401     else
402     {
403         import std.algorithm.mutation : move;
404         return move(arg);
405     }
406 }
407 
408 @safe unittest
409 {
410     void fun(T)(auto ref T, string) { /* ... */ }
411     void gun(T...)(auto ref T args)
412     {
413         fun(forward!(args[0]), forward!(args[1]));
414     }
415     gun(42, "hello");
416     int x;
417     gun(x, "hello");
418 }
419 
420 @safe unittest
421 {
422     static void checkByRef(T)(auto ref T value)
423     {
424         static assert(__traits(isRef, value));
425     }
426 
427     static void checkByVal(T)(auto ref T value)
428     {
429         static assert(!__traits(isRef, value));
430     }
431 
432     static void test1(ref int a) { checkByRef(forward!a); }
433     static void test2(int a) { checkByVal(forward!a); }
434     static void test3() { int a; checkByVal(forward!a); }
435 }
436 
437 /**
438 Convenience function that uses type deduction to return the appropriate
439 `FallbackAllocator` instance. To initialize with allocators that don't have
440 state, use their `it` static member.
441 */
442 FallbackAllocator!(Primary, Fallback)
443 fallbackAllocator(Primary, Fallback)(auto ref Primary p, auto ref Fallback f)
444 {
445     alias R = FallbackAllocator!(Primary, Fallback);
446 
447     static if (stateSize!Primary)
448         static if (stateSize!Fallback)
449             return R(forward!p, forward!f);
450         else
451             return R(forward!p);
452     else
453         static if (stateSize!Fallback)
454             return R(forward!f);
455         else
456             return R();
457 }
458 
459 ///
460 @system unittest
461 {
462     import std.experimental.allocator.building_blocks.region : Region;
463     import std.experimental.allocator.gc_allocator : GCAllocator;
464     import std.typecons : Ternary;
465     auto a = fallbackAllocator(Region!GCAllocator(1024), GCAllocator.instance);
466     auto b1 = a.allocate(1020);
467     assert(b1.length == 1020);
468     assert(a.primary.owns(b1) == Ternary.yes);
469     auto b2 = a.allocate(10);
470     assert(b2.length == 10);
471     assert(a.primary.owns(b2) == Ternary.no);
472 }
473 
474 version (StdUnittest)
475 @system unittest
476 {
477     import std.experimental.allocator.building_blocks.region : Region;
478     import std.experimental.allocator.gc_allocator : GCAllocator;
479     testAllocator!(() => fallbackAllocator(Region!GCAllocator(1024), GCAllocator.instance));
480 }
481 
482 // Ensure `owns` inherits function attributes
483 @system unittest
484 {
485     import std.experimental.allocator.building_blocks.region : InSituRegion;
486     import std.typecons : Ternary;
487 
488     FallbackAllocator!(InSituRegion!16_384, InSituRegion!16_384) a;
489     auto buff = a.allocate(42);
490     assert((() pure nothrow @safe @nogc => a.owns(buff))() == Ternary.yes);
491 }
492 
493 @system unittest
494 {
495     import std.experimental.allocator.gc_allocator : GCAllocator;
496     import std.typecons : Ternary;
497 
498     auto a = fallbackAllocator(GCAllocator.instance, GCAllocator.instance);
499     auto b = a.allocate(1020);
500     assert(b.length == 1020);
501 
502     void[] p;
503     assert((() nothrow @safe @nogc => a.resolveInternalPointer(null, p))() == Ternary.no);
504     assert((() nothrow @safe @nogc => a.resolveInternalPointer(&b[0], p))() == Ternary.yes);
505 }
506 
507 @system unittest
508 {
509     import std.experimental.allocator.building_blocks.region : BorrowedRegion;
510     import std.typecons : Ternary;
511 
512     alias A = FallbackAllocator!(BorrowedRegion!(), BorrowedRegion!());
513     auto a = A(BorrowedRegion!()(new ubyte[16_384]), BorrowedRegion!()(new ubyte[16_384]));
514 
515     auto b = a.allocate(42);
516     assert(b.length == 42);
517     assert((() pure nothrow @safe @nogc => a.owns(b))() == Ternary.yes);
518     assert((() nothrow @safe @nogc => a.expand(b, 58))());
519     assert(b.length == 100);
520 }