1 /// 2 module std.experimental.allocator.building_blocks.affix_allocator; 3 4 /** 5 6 Allocator that adds some extra data before (of type $(D Prefix)) and/or after 7 (of type $(D Suffix)) any allocation made with its parent allocator. This is 8 useful for uses where additional allocation-related information is needed, such 9 as mutexes, reference counts, or walls for debugging memory corruption errors. 10 11 If $(D Prefix) is not $(D void), $(D Allocator) must guarantee an alignment at 12 least as large as $(D Prefix.alignof). 13 14 Suffixes are slower to get at because of alignment rounding, so prefixes should 15 be preferred. However, small prefixes blunt the alignment so if a large 16 alignment with a small affix is needed, suffixes should be chosen. 17 18 The following methods are defined if $(D Allocator) defines them, and forward to it: $(D deallocateAll), $(D empty), $(D owns). 19 */ 20 struct AffixAllocator(Allocator, Prefix, Suffix = void) 21 { 22 import std.algorithm.comparison : min; 23 import std.conv : emplace; 24 import std.experimental.allocator : IAllocator, theAllocator; 25 import std.experimental.allocator.common : stateSize, forwardToMember, 26 roundUpToMultipleOf, alignedAt, alignDownTo, roundUpToMultipleOf, 27 hasStaticallyKnownAlignment; 28 import std.math : isPowerOf2; 29 import std.traits : hasMember; 30 import std.typecons : Ternary; 31 32 static if (hasStaticallyKnownAlignment!Allocator) 33 { 34 static assert( 35 !stateSize!Prefix || Allocator.alignment >= Prefix.alignof, 36 "AffixAllocator does not work with allocators offering a smaller" 37 ~ " alignment than the prefix alignment."); 38 } 39 static assert(alignment % Suffix.alignof == 0, 40 "This restriction could be relaxed in the future."); 41 42 /** 43 If $(D Prefix) is $(D void), the alignment is that of the parent. Otherwise, the alignment is the same as the $(D Prefix)'s alignment. 44 */ 45 static if (hasStaticallyKnownAlignment!Allocator) 46 { 47 enum uint alignment = isPowerOf2(stateSize!Prefix) 48 ? min(stateSize!Prefix, Allocator.alignment) 49 : (stateSize!Prefix ? Prefix.alignof : Allocator.alignment); 50 } 51 else static if (is(Prefix == void)) 52 { 53 enum uint alignment = platformAlignment; 54 } 55 else 56 { 57 enum uint alignment = Prefix.alignof; 58 } 59 60 /** 61 If the parent allocator $(D Allocator) is stateful, an instance of it is 62 stored as a member. Otherwise, $(D AffixAllocator) uses 63 `Allocator.instance`. In either case, the name $(D _parent) is uniformly 64 used for accessing the parent allocator. 65 */ 66 static if (stateSize!Allocator) 67 { 68 Allocator _parent; 69 static if (is(Allocator == IAllocator)) 70 { parentAffixAllocator71 Allocator parent() 72 { 73 if (_parent is null) _parent = theAllocator; 74 assert(alignment <= _parent.alignment); 75 return _parent; 76 } 77 } 78 else 79 { 80 alias parent = _parent; 81 } 82 } 83 else 84 { 85 alias parent = Allocator.instance; 86 } 87 ImplAffixAllocator88 private template Impl() 89 { 90 91 size_t goodAllocSize(size_t s) 92 { 93 import std.experimental.allocator.common : goodAllocSize; 94 auto a = actualAllocationSize(s); 95 return roundUpToMultipleOf(parent.goodAllocSize(a) 96 - stateSize!Prefix - stateSize!Suffix, 97 this.alignment); 98 } 99 100 private size_t actualAllocationSize(size_t s) const 101 { 102 assert(s > 0); 103 static if (!stateSize!Suffix) 104 { 105 return s + stateSize!Prefix; 106 } 107 else 108 { 109 return 110 roundUpToMultipleOf(s + stateSize!Prefix, Suffix.alignof) 111 + stateSize!Suffix; 112 } 113 } 114 115 private void[] actualAllocation(void[] b) const 116 { 117 assert(b !is null); 118 return (b.ptr - stateSize!Prefix) 119 [0 .. actualAllocationSize(b.length)]; 120 } 121 122 void[] allocate(size_t bytes) 123 { 124 if (!bytes) return null; 125 auto result = parent.allocate(actualAllocationSize(bytes)); 126 if (result is null) return null; 127 static if (stateSize!Prefix) 128 { 129 assert(result.ptr.alignedAt(Prefix.alignof)); 130 emplace!Prefix(cast(Prefix*) result.ptr); 131 } 132 static if (stateSize!Suffix) 133 { 134 auto suffixP = result.ptr + result.length - Suffix.sizeof; 135 assert(suffixP.alignedAt(Suffix.alignof)); 136 emplace!Suffix(cast(Suffix*)(suffixP)); 137 } 138 return result[stateSize!Prefix .. stateSize!Prefix + bytes]; 139 } 140 141 static if (hasMember!(Allocator, "allocateAll")) 142 void[] allocateAll() 143 { 144 auto result = parent.allocateAll(); 145 if (result is null) return null; 146 if (result.length < actualAllocationSize(1)) 147 { 148 deallocate(result); 149 return null; 150 } 151 static if (stateSize!Prefix) 152 { 153 assert(result.length > stateSize!Prefix); 154 emplace!Prefix(cast(Prefix*) result.ptr); 155 result = result[stateSize!Prefix .. $]; 156 } 157 static if (stateSize!Suffix) 158 { 159 assert(result.length > stateSize!Suffix); 160 // Ehm, find a properly aligned place for the suffix 161 auto p = (result.ptr + result.length - stateSize!Suffix) 162 .alignDownTo(Suffix.alignof); 163 assert(p > result.ptr); 164 emplace!Suffix(cast(Suffix*) p); 165 result = result[0 .. p - result.ptr]; 166 } 167 return result; 168 } 169 170 static if (hasMember!(Allocator, "owns")) 171 Ternary owns(void[] b) 172 { 173 if (b is null) return Ternary.no; 174 return parent.owns(actualAllocation(b)); 175 } 176 177 static if (hasMember!(Allocator, "resolveInternalPointer")) 178 Ternary resolveInternalPointer(const void* p, ref void[] result) 179 { 180 void[] p1; 181 Ternary r = parent.resolveInternalPointer(p, p1); 182 if (r != Ternary.yes || p1 is null) 183 return r; 184 p1 = p1[stateSize!Prefix .. $]; 185 auto p2 = (p1.ptr + p1.length - stateSize!Suffix) 186 .alignDownTo(Suffix.alignof); 187 result = p1[0 .. p2 - p1.ptr]; 188 return Ternary.yes; 189 } 190 191 static if (!stateSize!Suffix && hasMember!(Allocator, "expand")) 192 bool expand(ref void[] b, size_t delta) 193 { 194 if (!b.ptr) return delta == 0; 195 auto t = actualAllocation(b); 196 const result = parent.expand(t, delta); 197 if (!result) return false; 198 b = b.ptr[0 .. b.length + delta]; 199 return true; 200 } 201 202 static if (hasMember!(Allocator, "reallocate")) 203 bool reallocate(ref void[] b, size_t s) 204 { 205 if (b is null) 206 { 207 b = allocate(s); 208 return b.length == s; 209 } 210 auto t = actualAllocation(b); 211 const result = parent.reallocate(t, actualAllocationSize(s)); 212 if (!result) return false; // no harm done 213 b = t.ptr[stateSize!Prefix .. stateSize!Prefix + s]; 214 return true; 215 } 216 217 static if (hasMember!(Allocator, "deallocate")) 218 bool deallocate(void[] b) 219 { 220 if (!b.ptr) return true; 221 return parent.deallocate(actualAllocation(b)); 222 } 223 224 /* The following methods are defined if $(D ParentAllocator) defines 225 them, and forward to it: $(D deallocateAll), $(D empty).*/ 226 mixin(forwardToMember("parent", 227 "deallocateAll", "empty")); 228 229 // Computes suffix type given buffer type 230 private template Payload2Affix(Payload, Affix) 231 { 232 static if (is(Payload[] : void[])) 233 alias Payload2Affix = Affix; 234 else static if (is(Payload[] : shared(void)[])) 235 alias Payload2Affix = shared Affix; 236 else static if (is(Payload[] : immutable(void)[])) 237 alias Payload2Affix = shared Affix; 238 else static if (is(Payload[] : const(shared(void))[])) 239 alias Payload2Affix = shared Affix; 240 else static if (is(Payload[] : const(void)[])) 241 alias Payload2Affix = const Affix; 242 else 243 static assert(0, "Internal error for type " ~ Payload.stringof); 244 } 245 246 // Extra functions 247 static if (stateSize!Prefix) 248 { 249 static auto ref prefix(T)(T[] b) 250 { 251 assert(b.ptr && b.ptr.alignedAt(Prefix.alignof)); 252 return (cast(Payload2Affix!(T, Prefix)*) b.ptr)[-1]; 253 } 254 } 255 static if (stateSize!Suffix) 256 auto ref suffix(T)(T[] b) 257 { 258 assert(b.ptr); 259 auto p = b.ptr - stateSize!Prefix 260 + actualAllocationSize(b.length); 261 assert(p && p.alignedAt(Suffix.alignof)); 262 return (cast(Payload2Affix!(T, Suffix)*) p)[-1]; 263 } 264 } 265 versionAffixAllocator266 version (StdDdoc) 267 { 268 /** 269 Standard allocator methods. Each is defined if and only if the parent 270 allocator defines the homonym method (except for $(D goodAllocSize), 271 which may use the global default). Also, the methods will be $(D 272 shared) if the parent allocator defines them as such. 273 */ 274 size_t goodAllocSize(size_t); 275 /// Ditto 276 void[] allocate(size_t); 277 /// Ditto 278 Ternary owns(void[]); 279 /// Ditto 280 bool expand(ref void[] b, size_t delta); 281 /// Ditto 282 bool reallocate(ref void[] b, size_t s); 283 /// Ditto 284 bool deallocate(void[] b); 285 /// Ditto 286 bool deallocateAll(); 287 /// Ditto 288 Ternary empty(); 289 290 /** 291 The `instance` singleton is defined if and only if the parent allocator 292 has no state and defines its own `it` object. 293 */ 294 static AffixAllocator instance; 295 296 /** 297 Affix access functions offering references to the affixes of a 298 block `b` previously allocated with this allocator. `b` may not be null. 299 They are defined if and only if the corresponding affix is not `void`. 300 301 The qualifiers of the affix are not always the same as the qualifiers 302 of the argument. This is because the affixes are not part of the data 303 itself, but instead are just $(I associated) with the data and known 304 to the allocator. The table below documents the type of `preffix(b)` and 305 `affix(b)` depending on the type of `b`. 306 307 $(BOOKTABLE Result of `prefix`/`suffix` depending on argument (`U` is 308 any unqualified type, `Affix` is `Prefix` or `Suffix`), 309 $(TR $(TH Argument$(NBSP)Type) $(TH Return) $(TH Comments)) 310 311 $(TR $(TD `shared(U)[]`) $(TD `ref shared Affix`) 312 $(TD Data is shared across threads and the affix follows suit.)) 313 314 $(TR $(TD `immutable(U)[]`) $(TD `ref shared Affix`) 315 $(TD Although the data is immutable, the allocator "knows" the 316 underlying memory is mutable, so `immutable` is elided for the affix 317 which is independent from the data itself. However, the result is 318 `shared` because `immutable` is implicitly shareable so multiple 319 threads may access and manipulate the affix for the same data.)) 320 321 $(TR $(TD `const(shared(U))[]`) $(TD `ref shared Affix`) 322 $(TD The data is always shareable across threads. Even if the data 323 is `const`, the affix is modifiable by the same reasoning as for 324 `immutable`.)) 325 326 $(TR $(TD `const(U)[]`) $(TD `ref const Affix`) 327 $(TD The input may have originated from `U[]` or `immutable(U)[]`, 328 so it may be actually shared or not. Returning an unqualified affix 329 may result in race conditions, whereas returning a `shared` affix 330 may result in inadvertent sharing of mutable thread-local data 331 across multiple threads. So the returned type is conservatively 332 `ref const`.)) 333 334 $(TR $(TD `U[]`) $(TD `ref Affix`) 335 $(TD Unqualified data has unqualified affixes.)) 336 ) 337 338 Precondition: `b !is null` and `b` must have been allocated with 339 this allocator. 340 */ 341 static ref auto prefix(T)(T[] b); 342 /// Ditto 343 ref auto suffix(T)(T[] b); 344 } 345 else static if (is(typeof(Allocator.instance) == shared)) 346 { 347 static shared AffixAllocator instance; 348 shared { mixin Impl!(); } 349 } 350 else 351 { 352 mixin Impl!(); 353 static if (stateSize!Allocator == 0) 354 static __gshared AffixAllocator instance; 355 } 356 } 357 358 /// 359 @system unittest 360 { 361 import std.experimental.allocator.mallocator : Mallocator; 362 // One word before and after each allocation. 363 alias A = AffixAllocator!(Mallocator, size_t, size_t); 364 auto b = A.instance.allocate(11); 365 A.instance.prefix(b) = 0xCAFE_BABE; 366 A.instance.suffix(b) = 0xDEAD_BEEF; 367 assert(A.instance.prefix(b) == 0xCAFE_BABE 368 && A.instance.suffix(b) == 0xDEAD_BEEF); 369 } 370 371 @system unittest 372 { 373 import std.experimental.allocator.gc_allocator : GCAllocator; 374 import std.experimental.allocator : theAllocator, IAllocator; 375 376 // One word before and after each allocation. 377 auto A = AffixAllocator!(IAllocator, size_t, size_t)(theAllocator); 378 auto a = A.allocate(11); 379 A.prefix(a) = 0xCAFE_BABE; 380 A.suffix(a) = 0xDEAD_BEEF; 381 assert(A.prefix(a) == 0xCAFE_BABE 382 && A.suffix(a) == 0xDEAD_BEEF); 383 384 // One word before and after each allocation. 385 auto B = AffixAllocator!(IAllocator, size_t, size_t)(); 386 auto b = B.allocate(11); 387 B.prefix(b) = 0xCAFE_BABE; 388 B.suffix(b) = 0xDEAD_BEEF; 389 assert(B.prefix(b) == 0xCAFE_BABE 390 && B.suffix(b) == 0xDEAD_BEEF); 391 } 392 393 @system unittest 394 { 395 import std.experimental.allocator.building_blocks.bitmapped_block 396 : BitmappedBlock; 397 import std.experimental.allocator.common : testAllocator; 398 testAllocator!({ 399 auto a = AffixAllocator!(BitmappedBlock!128, ulong, ulong) 400 (BitmappedBlock!128(new ubyte[128 * 4096])); 401 return a; 402 }); 403 } 404 405 @system unittest 406 { 407 import std.experimental.allocator.mallocator : Mallocator; 408 alias A = AffixAllocator!(Mallocator, size_t); 409 auto b = A.instance.allocate(10); 410 A.instance.prefix(b) = 10; 411 assert(A.instance.prefix(b) == 10); 412 413 import std.experimental.allocator.building_blocks.null_allocator 414 : NullAllocator; 415 alias B = AffixAllocator!(NullAllocator, size_t); 416 b = B.instance.allocate(100); 417 assert(b is null); 418 } 419 420 @system unittest 421 { 422 import std.experimental.allocator; 423 import std.experimental.allocator.gc_allocator; 424 import std.typecons : Ternary; 425 alias MyAllocator = AffixAllocator!(GCAllocator, uint); 426 auto a = MyAllocator.instance.makeArray!(shared int)(100); 427 static assert(is(typeof(&MyAllocator.instance.prefix(a)) == shared(uint)*)); 428 auto b = MyAllocator.instance.makeArray!(shared const int)(100); 429 static assert(is(typeof(&MyAllocator.instance.prefix(b)) == shared(uint)*)); 430 auto c = MyAllocator.instance.makeArray!(immutable int)(100); 431 static assert(is(typeof(&MyAllocator.instance.prefix(c)) == shared(uint)*)); 432 auto d = MyAllocator.instance.makeArray!(int)(100); 433 static assert(is(typeof(&MyAllocator.instance.prefix(d)) == uint*)); 434 auto e = MyAllocator.instance.makeArray!(const int)(100); 435 static assert(is(typeof(&MyAllocator.instance.prefix(e)) == const(uint)*)); 436 437 void[] p; 438 assert(MyAllocator.instance.resolveInternalPointer(null, p) == Ternary.no); 439 Ternary r = MyAllocator.instance.resolveInternalPointer(d.ptr, p); 440 assert(p.ptr is d.ptr && p.length >= d.length); 441 } 442