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 }