1 // Written in the D programming language. 2 /** 3 D's built-in garbage-collected allocator. 4 5 Source: $(PHOBOSSRC std/experimental/allocator/_gc_allocator.d) 6 */ 7 module std.experimental.allocator.gc_allocator; 8 import std.experimental.allocator.common; 9 10 /** 11 D's built-in garbage-collected allocator. 12 */ 13 struct GCAllocator 14 { 15 import core.memory : GC; 16 import std.typecons : Ternary; 17 version (StdUnittest) @system unittest { testAllocator!(() => GCAllocator.instance); } 18 19 /** 20 The alignment is a static constant equal to `platformAlignment`, which 21 ensures proper alignment for any D data type. 22 */ 23 enum uint alignment = platformAlignment; 24 25 /** 26 Standard allocator methods per the semantics defined above. The $(D 27 deallocate) and `reallocate` methods are `@system` because they may 28 move memory around, leaving dangling pointers in user code. 29 */ 30 pure nothrow @trusted void[] allocate(size_t bytes) shared const 31 { 32 if (!bytes) return null; 33 auto p = GC.malloc(bytes); 34 return p ? p[0 .. bytes] : null; 35 } 36 37 /// Ditto 38 pure nothrow @trusted bool expand(ref void[] b, size_t delta) shared const 39 { 40 if (delta == 0) return true; 41 if (b is null) return false; 42 immutable curLength = GC.sizeOf(b.ptr); 43 assert(curLength != 0); // we have a valid GC pointer here 44 immutable desired = b.length + delta; 45 if (desired > curLength) // check to see if the current block can't hold the data 46 { 47 immutable sizeRequest = desired - curLength; 48 immutable newSize = GC.extend(b.ptr, sizeRequest, sizeRequest); 49 if (newSize == 0) 50 { 51 // expansion unsuccessful 52 return false; 53 } 54 assert(newSize >= desired); 55 } 56 b = b.ptr[0 .. desired]; 57 return true; 58 } 59 60 /// Ditto 61 pure nothrow @system bool reallocate(ref void[] b, size_t newSize) shared const 62 { 63 import core.exception : OutOfMemoryError; 64 try 65 { 66 auto p = cast(ubyte*) GC.realloc(b.ptr, newSize); 67 b = p[0 .. newSize]; 68 } 69 catch (OutOfMemoryError) 70 { 71 // leave the block in place, tell caller 72 return false; 73 } 74 return true; 75 } 76 77 /// Ditto 78 pure nothrow @trusted @nogc 79 Ternary resolveInternalPointer(const void* p, ref void[] result) shared const 80 { 81 auto r = GC.addrOf(cast(void*) p); 82 if (!r) return Ternary.no; 83 result = r[0 .. GC.sizeOf(r)]; 84 return Ternary.yes; 85 } 86 87 /// Ditto 88 pure nothrow @system @nogc 89 bool deallocate(void[] b) shared const 90 { 91 GC.free(b.ptr); 92 return true; 93 } 94 95 /// Ditto 96 pure nothrow @safe @nogc 97 size_t goodAllocSize(size_t n) shared const 98 { 99 if (n == 0) 100 return 0; 101 if (n <= 16) 102 return 16; 103 104 import core.bitop : bsr; 105 106 auto largestBit = bsr(n-1) + 1; 107 if (largestBit <= 12) // 4096 or less 108 return size_t(1) << largestBit; 109 110 // larger, we use a multiple of 4096. 111 return ((n + 4095) / 4096) * 4096; 112 } 113 114 package pure nothrow @trusted void[] allocateZeroed()(size_t bytes) shared const 115 { 116 if (!bytes) return null; 117 auto p = GC.calloc(bytes); 118 return p ? p[0 .. bytes] : null; 119 } 120 121 /** 122 Returns the global instance of this allocator type. The garbage collected 123 allocator is thread-safe, therefore all of its methods and `instance` itself 124 are `shared`. 125 */ 126 127 static shared const GCAllocator instance; 128 129 // Leave it undocummented for now. 130 nothrow @trusted void collect() shared const 131 { 132 GC.collect(); 133 } 134 } 135 136 /// 137 pure @system unittest 138 { 139 auto buffer = GCAllocator.instance.allocate(1024 * 1024 * 4); 140 // deallocate upon scope's end (alternatively: leave it to collection) 141 scope(exit) GCAllocator.instance.deallocate(buffer); 142 //... 143 } 144 145 pure @safe unittest 146 { 147 auto b = GCAllocator.instance.allocate(10_000); 148 assert(GCAllocator.instance.expand(b, 1)); 149 } 150 151 pure @system unittest 152 { 153 import core.memory : GC; 154 import std.typecons : Ternary; 155 156 // test allocation sizes 157 assert((() nothrow @safe @nogc => GCAllocator.instance.goodAllocSize(1))() == 16); 158 for (size_t s = 16; s <= 8192; s *= 2) 159 { 160 assert((() nothrow @safe @nogc => GCAllocator.instance.goodAllocSize(s))() == s); 161 assert((() nothrow @safe @nogc => GCAllocator.instance.goodAllocSize(s - (s / 2) + 1))() == s); 162 163 auto buffer = GCAllocator.instance.allocate(s); 164 scope(exit) () nothrow @nogc { GCAllocator.instance.deallocate(buffer); }(); 165 166 void[] p; 167 assert((() nothrow @safe => GCAllocator.instance.resolveInternalPointer(null, p))() == Ternary.no); 168 assert((() nothrow @safe => GCAllocator.instance.resolveInternalPointer(&buffer[0], p))() == Ternary.yes); 169 assert(p.ptr is buffer.ptr && p.length >= buffer.length); 170 171 assert(GC.sizeOf(buffer.ptr) == s); 172 173 // the GC should provide power of 2 as "good" sizes, but other sizes are allowed, too 174 version (none) 175 { 176 auto buffer2 = GCAllocator.instance.allocate(s - (s / 2) + 1); 177 scope(exit) () nothrow @nogc { GCAllocator.instance.deallocate(buffer2); }(); 178 179 assert(GC.sizeOf(buffer2.ptr) == s); 180 } 181 } 182 183 // anything above a page is simply rounded up to next page 184 assert((() nothrow @safe @nogc => GCAllocator.instance.goodAllocSize(4096 * 4 + 1))() == 4096 * 5); 185 } 186 187 pure nothrow @safe unittest 188 { 189 import std.typecons : Ternary; 190 191 void[] buffer = GCAllocator.instance.allocate(42); 192 void[] result; 193 Ternary found = GCAllocator.instance.resolveInternalPointer(&buffer[0], result); 194 195 assert(found == Ternary.yes && &result[0] == &buffer[0] && result.length >= buffer.length); 196 assert(GCAllocator.instance.resolveInternalPointer(null, result) == Ternary.no); 197 void *badPtr = (() @trusted => cast(void*)(0xdeadbeef))(); 198 assert(GCAllocator.instance.resolveInternalPointer(badPtr, result) == Ternary.no); 199 }