gfm.core.memory source code

1 /**
2   This module provide support for aligned memory.
3  */
4 module gfm.core.memory;
5 
6 import core.memory : GC;
7 import core.exception : onOutOfMemoryError;
8 
9 import std.c.stdlib : malloc, free, realloc;
10 import std.conv : emplace;
11 import std.traits;
12 import std.algorithm: swap;
13 
14 
15 /// Returns: next pointer aligned with alignment bytes.
16 @nogc void* nextAlignedPointer(void* start, size_t alignment) pure nothrow
17 {
18     return cast(void*)nextMultipleOf(cast(size_t)(start), alignment);
19 }
20 
21 /// Allocates an aligned memory chunk.
22 /// Functionally equivalent to Visual C++ _aligned_malloc.
23 @nogc void* alignedMalloc(size_t size, size_t alignment) nothrow
24 {
25     if (size == 0)
26         return null;
27 
28     size_t request = requestedSize(size, alignment);
29     void* raw = malloc(request);
30 
31     static if( __VERSION__ > 2067 ) // onOutOfMemoryError wasn't nothrow before July 2014
32     {
33         if (request > 0 && raw == null) // malloc(0) can validly return anything
34             onOutOfMemoryError();
35     }
36 
37     return storeRawPointerAndReturnAligned(raw, alignment);
38 }
39 
40 /// Frees aligned memory allocated by alignedMalloc or alignedRealloc.
41 /// Functionally equivalent to Visual C++ _aligned_free.
42 @nogc void alignedFree(void* aligned) nothrow
43 {
44     // support for free(NULL)
45     if (aligned is null)
46         return;
47 
48     void** rawLocation = cast(void**)(cast(char*)aligned - size_t.sizeof);
49     free(*rawLocation);
50 }
51 
52 /// Reallocates an aligned memory chunk allocated by alignedMalloc or alignedRealloc.
53 /// Functionally equivalent to Visual C++ _aligned_realloc.
54 @nogc void* alignedRealloc(void* aligned, size_t size, size_t alignment) nothrow
55 {
56     if (aligned is null)
57         return alignedMalloc(size, alignment);
58 
59     if (size == 0)
60     {
61         alignedFree(aligned);
62         return null;
63     }
64 
65     void* raw = *cast(void**)(cast(char*)aligned - size_t.sizeof);
66 
67     size_t request = requestedSize(size, alignment);
68     void* newRaw = realloc(raw, request);
69 
70     static if( __VERSION__ > 2067 ) // onOutOfMemoryError wasn't nothrow before July 2014
71     {
72         if (request > 0 && newRaw == null) // realloc(0) can validly return anything
73             onOutOfMemoryError();
74     }
75 
76     // if newRaw is raw, nothing to do
77     if (raw is newRaw)
78         return aligned;
79 
80     // else write raw at the new location
81     return storeRawPointerAndReturnAligned(newRaw, alignment);
82 }
83 
84 private
85 {
86     // Returns number of bytes to actually allocate when asking
87     // for a particular alignement
88     @nogc size_t requestedSize(size_t askedSize, size_t alignment) pure nothrow
89     {
90         enum size_t pointerSize = size_t.sizeof;
91         return askedSize + alignment - 1 + pointerSize;
92     }
93 
94     @nogc void* storeRawPointerAndReturnAligned(void* raw, size_t alignment) nothrow
95     {
96         enum size_t pointerSize = size_t.sizeof;
97         char* start = cast(char*)raw + pointerSize;
98         void* aligned = nextAlignedPointer(start, alignment);
99         void** rawLocation = cast(void**)(cast(char*)aligned - pointerSize);
100         *rawLocation = raw;
101         return aligned;
102     }
103 
104     // Returns: x, multiple of powerOfTwo, so that x >= n.
105     @nogc size_t nextMultipleOf(size_t n, size_t powerOfTwo) pure nothrow
106     {
107         // check power-of-two
108         assert( (powerOfTwo != 0) && ((powerOfTwo & (powerOfTwo - 1)) == 0));
109 
110         size_t mask = ~(powerOfTwo - 1);
111         return (n + powerOfTwo - 1) & mask;
112     }
113 }
114 
115 unittest
116 {
117     assert(nextMultipleOf(0, 4) == 0);
118     assert(nextMultipleOf(1, 4) == 4);
119     assert(nextMultipleOf(2, 4) == 4);
120     assert(nextMultipleOf(3, 4) == 4);
121     assert(nextMultipleOf(4, 4) == 4);
122     assert(nextMultipleOf(5, 4) == 8);
123 
124     {
125         void* p = alignedMalloc(23, 16);
126         assert(p !is null);
127         assert(((cast(size_t)p) & 0xf) == 0);
128 
129         alignedFree(p);
130     }
131 
132     assert(alignedMalloc(0, 16) == null);
133     alignedFree(null);
134 
135     {
136         int alignment = 16;
137         int* p = null;
138 
139         // check if growing keep values in place
140         foreach(int i; 0..100)
141         {
142             p = cast(int*) alignedRealloc(p, (i + 1) * int.sizeof, alignment);
143             p[i] = i;
144         }
145 
146         foreach(int i; 0..100)
147             assert(p[i] == i);
148 
149 
150         p = cast(int*) alignedRealloc(p, 0, alignment);
151         assert(p is null);
152     }
153 }
154 
155 
156 /// Destructors called by the GC enjoy a variety of limitations and
157 /// relying on them is dangerous.
158 /// See_also: $(WEB p0nce.github.io/d-idioms/#The-trouble-with-class-destructors)
159 /// Example:
160 /// ---
161 /// class Resource
162 /// {
163 ///     ~this()
164 ///     {
165 ///         if (!alreadyClosed)
166 ///         {
167 ///             if (isCalledByGC())
168 ///                 assert(false, "Resource release relies on Garbage Collection");
169 ///             alreadyClosed = true;
170 ///             releaseResource();
171 ///         }
172 ///     }
173 /// }
174 /// ---
175 bool isCalledByGC() nothrow
176 {
177     import core.exception;
178     try
179     {
180         import core.memory;
181         cast(void) GC.malloc(1); // not ideal since it allocates
182         return false;
183     }
184     catch(InvalidMemoryOperationError e)
185     {
186         return true;
187     }
188 }
189 
190 unittest
191 {
192     import std.stdio;
193     class A
194     {
195         ~this()
196         {
197             assert(!isCalledByGC());
198         }
199     }
200     import std.typecons;
201     auto a = scoped!A();
202 }
203 
204 /// Crash if the GC is running.
205 /// Useful in destructors to avoid reliance GC resource release.
206 /// See_also: $(WEB p0nce.github.io/d-idioms/#GC-proof-resource-class)
207 void ensureNotInGC(string resourceName = null) nothrow
208 {
209     import core.exception;
210     try
211     {
212         import core.memory;
213         cast(void) GC.malloc(1); // not ideal since it allocates
214         return;
215     }
216     catch(InvalidMemoryOperationError e)
217     {
218         import core.stdc.stdio;
219         fprintf(stderr, "Error: clean-up of %s incorrectly depends on destructors called by the GC.\n",
220                         resourceName ? resourceName.ptr : "a resource".ptr);
221         assert(false); // crash
222     }
223 }
224 
225 
226 /// Allocates and construct a struct or class object.
227 /// Returns: Newly allocated object.
228 auto mallocEmplace(T, Args...)(Args args)
229 {
230     static if (is(T == class))
231         immutable size_t allocSize = __traits(classInstanceSize, T);
232     else
233         immutable size_t allocSize = T.sizeof;
234 
235     void* rawMemory = malloc(allocSize);
236     if (!rawMemory)
237         onOutOfMemoryError();
238 
239     static if (is(T == class))
240     {
241         T obj = emplace!T(rawMemory[0 .. allocSize], args);
242     }
243     else
244     {
245         T* obj = cast(T*)rawMemory;
246         emplace!T(obj, args);
247     }
248 
249     static if (hasIndirections!T)
250         GC.addRange(rawMemory, allocSize);
251 
252     return obj;
253 }
254 
255 /// Destroys and frees a class object created with $(D mallocEmplace).
256 void destroyFree(T)(T p) if (is(T == class))
257 {
258     if (p !is null)
259     {
260         destroy(p);
261 
262         static if (hasIndirections!T)
263             GC.removeRange(cast(void*)p);
264 
265         free(cast(void*)p);
266     }
267 }
268 
269 /// Destroys and frees a non-class object created with $(D mallocEmplace).
270 void destroyFree(T)(T* p) if (!is(T == class))
271 {
272     if (p !is null)
273     {
274         destroy(p);
275 
276         static if (hasIndirections!T)
277             GC.removeRange(cast(void*)p);
278 
279         free(cast(void*)p);
280     }
281 }
282 
283 unittest
284 {
285     class A
286     {
287         int _i;
288         this(int i)
289         {
290             _i = i;
291         }
292     }
293 
294     struct B
295     {
296         int i;
297     }
298 
299     void testMallocEmplace()
300     {
301         A a = mallocEmplace!A(4);
302         destroyFree(a);
303 
304         B* b = mallocEmplace!B(5);
305         destroyFree(b);
306     }
307 
308     testMallocEmplace();
309 }
310 
311 version( D_InlineAsm_X86 )
312 {
313     version = AsmX86;
314 }
315 else version( D_InlineAsm_X86_64 )
316 {
317     version = AsmX86;
318 }
319 
320 /// Inserts a breakpoint instruction. useful to trigger the debugger.
321 void debugBreak() nothrow @nogc
322 {
323     version( AsmX86 )
324     {
325         static if( __VERSION__ >= 2067 )
326         {
327             mixin("asm nothrow @nogc { int 3; }");
328         }
329         else
330         {
331             mixin("asm { int 3; }");
332         }
333     }
334     else version( GNU )
335     {
336         // __builtin_trap() is not the same thing unfortunately
337         asm
338         {
339             "int $0x03" : : : ;
340         }
341     }
342     else
343     {
344         static assert(false, "No debugBreak() for this compiler");
345     }
346 }
347 
348 auto assumeNoGC(T) (T t) if (isFunctionPointer!T || isDelegate!T)
349 {
350     enum attrs = functionAttributes!T | FunctionAttribute.nogc;
351     return cast(SetFunctionAttributes!(T, functionLinkage!T, attrs)) t;
352 }
353 
354 auto assumeNothrow(T) (T t) if (isFunctionPointer!T || isDelegate!T)
355 {
356     enum attrs = functionAttributes!T | FunctionAttribute.nothrow_;
357     return cast(SetFunctionAttributes!(T, functionLinkage!T, attrs)) t;
358 }
359 
360 auto assumeNothrowNoGC(T) (T t) if (isFunctionPointer!T || isDelegate!T)
361 {
362     enum attrs = functionAttributes!T | FunctionAttribute.nogc | FunctionAttribute.nothrow_;
363     return cast(SetFunctionAttributes!(T, functionLinkage!T, attrs)) t;
364 }
365 
366 unittest
367 {
368     void funcThatDoesGC()
369     {
370         throw new Exception("hello!");
371     }
372 
373     void anotherFunction() nothrow @nogc
374     {
375         assumeNothrowNoGC( (){ funcThatDoesGC(); } )();
376     }
377 
378     void aThirdFunction() @nogc
379     {
380         assumeNoGC( () { funcThatDoesGC(); } )();
381     }
382 }
383 
384 /// Must return -1 if a < b
385 ///              0 if a == b
386 ///              1 if a > b
387 alias nogcComparisonFunction(T) = int delegate(in T a, in T b) nothrow @nogc;
388 
389 /// @nogc quicksort
390 /// From the excellent: http://codereview.stackexchange.com/a/77788
391 void nogc_qsort(T)(T[] array, nogcComparisonFunction!T comparison) nothrow @nogc
392 {
393     if (array.length < 2)
394         return;
395 
396     int partition(T* arr, int left, int right) nothrow @nogc
397     {
398         immutable int mid = left + (right - left) / 2;
399         immutable T pivot = arr[mid];
400         // move the mid point value to the front.
401         swap(arr[mid],arr[left]);
402         int i = left + 1;
403         int j = right;
404         while (i <= j)
405         {
406             while(i <= j && comparison(arr[i], pivot) <= 0 )
407                 i++;
408 
409             while(i <= j && comparison(arr[j], pivot) > 0)
410                 j--;
411 
412             if (i < j)
413                 swap(arr[i], arr[j]);
414         }
415         swap(arr[i - 1], arr[left]);
416         return i - 1;
417     }
418 
419     void doQsort(T* array, int left, int right) nothrow @nogc
420     {
421         if (left >= right)
422             return;
423 
424         int part = partition(array, left, right);
425         doQsort(array, left, part - 1);
426         doQsort(array, part + 1, right);
427     }
428 
429     doQsort(array.ptr, 0, cast(int)(array.length) - 1);
430 }
431 
432 unittest
433 {
434     int[] testData = [110, 5, 10, 3, 22, 100, 1, 23];
435     nogc_qsort!int(testData, (a, b) => (a - b));
436     assert(testData == [1, 3, 5, 10, 22, 23, 100, 110]);
437 }