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 }