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 */
FallbackAllocator(Primary,Fallback)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 : Region;
346 import std.typecons : Ternary;
347
348 auto a = FallbackAllocator!(Region!(), Region!())(
349 Region!()(new ubyte[4096 * 1024]),
350 Region!()(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
version(StdUnittest)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 */
forward(alias arg)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 {
fun(T)410 void fun(T)(auto ref T, string) { /* ... */ }
gun(T...)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 {
checkByRef(T)422 static void checkByRef(T)(auto ref T value)
423 {
424 static assert(__traits(isRef, value));
425 }
426
checkByVal(T)427 static void checkByVal(T)(auto ref T value)
428 {
429 static assert(!__traits(isRef, value));
430 }
431
test1(ref int a)432 static void test1(ref int a) { checkByRef(forward!a); }
test2(int a)433 static void test2(int a) { checkByVal(forward!a); }
test3()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
version(StdUnittest)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 : Region;
510 import std.typecons : Ternary;
511
512 alias A = FallbackAllocator!(Region!(), Region!());
513 auto a = A(Region!()(new ubyte[16_384]), Region!()(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 }
521