The OpenD Programming Language

1 // Written in the D programming language.
2 /**
3 The C heap allocator.
4 
5 Source: $(PHOBOSSRC std/experimental/allocator/mallocator.d)
6 */
7 module std.experimental.allocator.mallocator;
8 import std.experimental.allocator.common;
9 
10 /**
11    The C heap allocator.
12  */
13 struct Mallocator
14 {
15     version (StdUnittest) @system unittest { testAllocator!(() => Mallocator.instance); }
16 
17     /**
18     The alignment is a static constant equal to `platformAlignment`, which
19     ensures proper alignment for any D data type.
20     */
21     enum uint alignment = platformAlignment;
22 
23     /**
24     Standard allocator methods per the semantics defined above. The
25     `deallocate` and `reallocate` methods are `@system` because they
26     may move memory around, leaving dangling pointers in user code. Somewhat
27     paradoxically, `malloc` is `@safe` but that's only useful to safe
28     programs that can afford to leak memory allocated.
29     */
30     @trusted @nogc nothrow pure
31     void[] allocate(size_t bytes) shared const
32     {
33         import core.memory : pureMalloc;
34         if (!bytes) return null;
35         auto p = pureMalloc(bytes);
36         return p ? p[0 .. bytes] : null;
37     }
38 
39     /// Ditto
40     @system @nogc nothrow pure
41     bool deallocate(void[] b) shared const
42     {
43         import core.memory : pureFree;
44         pureFree(b.ptr);
45         return true;
46     }
47 
48     /// Ditto
49     @system @nogc nothrow pure
50     bool reallocate(ref void[] b, size_t s) shared const
51     {
52         import core.memory : pureRealloc;
53         if (!s)
54         {
55             // fuzzy area in the C standard, see http://goo.gl/ZpWeSE
56             // so just deallocate and nullify the pointer
57             deallocate(b);
58             b = null;
59             return true;
60         }
61         auto p = cast(ubyte*) pureRealloc(b.ptr, s);
62         if (!p) return false;
63         b = p[0 .. s];
64         return true;
65     }
66 
67     @trusted @nogc nothrow pure
68     package void[] allocateZeroed()(size_t bytes) shared const
69     {
70         import core.memory : pureCalloc;
71         if (!bytes) return null;
72         auto p = pureCalloc(1, bytes);
73         return p ? p[0 .. bytes] : null;
74     }
75 
76     /**
77     Returns the global instance of this allocator type. The C heap allocator is
78     thread-safe, therefore all of its methods and `it` itself are
79     `shared`.
80     */
81     static shared Mallocator instance;
82 }
83 
84 ///
85 @nogc @system nothrow unittest
86 {
87     auto buffer = Mallocator.instance.allocate(1024 * 1024 * 4);
88     scope(exit) Mallocator.instance.deallocate(buffer);
89     //...
90 }
91 
92 @nogc @system nothrow pure unittest
93 {
94     @nogc nothrow pure
95     static void test(A)()
96     {
97         int* p = null;
98         p = cast(int*) A.instance.allocate(int.sizeof);
99         scope(exit) () nothrow @nogc { A.instance.deallocate(p[0 .. int.sizeof]); }();
100         *p = 42;
101         assert(*p == 42);
102     }
103     test!Mallocator();
104 }
105 
106 @nogc @system nothrow pure unittest
107 {
108     static void test(A)()
109     {
110         import std.experimental.allocator : make;
111         Object p = null;
112         p = A.instance.make!Object();
113         assert(p !is null);
114     }
115 
116     test!Mallocator();
117 }
118 
119 version (Windows)
120 {
121     // DMD Win 32 bit, DigitalMars C standard library misses the _aligned_xxx
122     // functions family (snn.lib)
123     version (CRuntime_DigitalMars)
124     {
125         // Helper to cast the infos written before the aligned pointer
126         // this header keeps track of the size (required to realloc) and of
127         // the base ptr (required to free).
128         private struct AlignInfo
129         {
130             void* basePtr;
131             size_t size;
132 
133             @nogc nothrow
134             static AlignInfo* opCall(void* ptr)
135             {
136                 return cast(AlignInfo*) (ptr - AlignInfo.sizeof);
137             }
138         }
139 
140         @nogc nothrow
141         private void* _aligned_malloc(size_t size, size_t alignment)
142         {
143             import core.stdc.stdlib : malloc;
144             size_t offset = alignment + size_t.sizeof * 2 - 1;
145 
146             // unaligned chunk
147             void* basePtr = malloc(size + offset);
148             if (!basePtr) return null;
149 
150             // get aligned location within the chunk
151             void* alignedPtr = cast(void**)((cast(size_t)(basePtr) + offset)
152                 & ~(alignment - 1));
153 
154             // write the header before the aligned pointer
155             AlignInfo* head = AlignInfo(alignedPtr);
156             head.basePtr = basePtr;
157             head.size = size;
158 
159             return alignedPtr;
160         }
161 
162         @nogc nothrow
163         private void* _aligned_realloc(void* ptr, size_t size, size_t alignment)
164         {
165             import core.stdc.stdlib : free;
166             import core.stdc.string : memcpy;
167 
168             if (!ptr) return _aligned_malloc(size, alignment);
169 
170             // gets the header from the exising pointer
171             AlignInfo* head = AlignInfo(ptr);
172 
173             // gets a new aligned pointer
174             void* alignedPtr = _aligned_malloc(size, alignment);
175             if (!alignedPtr)
176             {
177                 //to https://msdn.microsoft.com/en-us/library/ms235462.aspx
178                 //see Return value: in this case the original block is unchanged
179                 return null;
180             }
181 
182             // copy exising data
183             memcpy(alignedPtr, ptr, head.size);
184             free(head.basePtr);
185 
186             return alignedPtr;
187         }
188 
189         @nogc nothrow
190         private void _aligned_free(void *ptr)
191         {
192             import core.stdc.stdlib : free;
193             if (!ptr) return;
194             AlignInfo* head = AlignInfo(ptr);
195             free(head.basePtr);
196         }
197 
198     }
199     // DMD Win 64 bit, uses microsoft standard C library which implements them
200     else
201     {
202         @nogc nothrow private extern(C) void* _aligned_malloc(size_t, size_t);
203         @nogc nothrow private extern(C) void _aligned_free(void *memblock);
204         @nogc nothrow private extern(C) void* _aligned_realloc(void *, size_t, size_t);
205     }
206 }
207 
208 /**
209    Aligned allocator using OS-specific primitives, under a uniform API.
210  */
211 struct AlignedMallocator
212 {
213     version (StdUnittest) @system unittest { testAllocator!(() => typeof(this).instance); }
214 
215     /**
216     The default alignment is `platformAlignment`.
217     */
218     enum uint alignment = platformAlignment;
219 
220     /**
221     Forwards to $(D alignedAllocate(bytes, platformAlignment)).
222     */
223     @trusted @nogc nothrow
224     void[] allocate(size_t bytes) shared
225     {
226         if (!bytes) return null;
227         return alignedAllocate(bytes, alignment);
228     }
229 
230     /**
231     Uses $(HTTP man7.org/linux/man-pages/man3/posix_memalign.3.html,
232     `posix_memalign`) on Posix and
233     $(HTTP msdn.microsoft.com/en-us/library/8z34s9c6(v=vs.80).aspx,
234     `__aligned_malloc`) on Windows.
235     */
236     version (Posix)
237     @trusted @nogc nothrow
238     void[] alignedAllocate(size_t bytes, uint a) shared
239     {
240         import core.stdc.errno : ENOMEM, EINVAL;
241         import core.sys.posix.stdlib : posix_memalign;
242         assert(a.isGoodDynamicAlignment);
243         void* result;
244         auto code = posix_memalign(&result, a, bytes);
245 
246 version (OSX)
247 version (LDC_AddressSanitizer)
248 {
249         // The return value with AddressSanitizer may be -1 instead of ENOMEM
250         // or EINVAL. See https://bugs.llvm.org/show_bug.cgi?id=36510
251         if (code == -1)
252             return null;
253 }
254         if (code == ENOMEM)
255             return null;
256 
257         else if (code == EINVAL)
258         {
259             assert(0, "AlignedMallocator.alignment is not a power of two "
260                 ~"multiple of (void*).sizeof, according to posix_memalign!");
261         }
262         else if (code != 0)
263             assert(0, "posix_memalign returned an unknown code!");
264 
265         else
266             return result[0 .. bytes];
267     }
268     else version (Windows)
269     @trusted @nogc nothrow
270     void[] alignedAllocate(size_t bytes, uint a) shared
271     {
272         auto result = _aligned_malloc(bytes, a);
273         return result ? result[0 .. bytes] : null;
274     }
275     else static assert(0);
276 
277     /**
278     Calls `free(b.ptr)` on Posix and
279     $(HTTP msdn.microsoft.com/en-US/library/17b5h8td(v=vs.80).aspx,
280     `__aligned_free(b.ptr)`) on Windows.
281     */
282     version (Posix)
283     @system @nogc nothrow
284     bool deallocate(void[] b) shared
285     {
286         import core.stdc.stdlib : free;
287         free(b.ptr);
288         return true;
289     }
290     else version (Windows)
291     @system @nogc nothrow
292     bool deallocate(void[] b) shared
293     {
294         _aligned_free(b.ptr);
295         return true;
296     }
297     else static assert(0);
298 
299     /**
300     Forwards to $(D alignedReallocate(b, newSize, platformAlignment)).
301     Should be used with blocks obtained with `allocate` otherwise the custom
302     alignment passed with `alignedAllocate` can be lost.
303     */
304     @system @nogc nothrow
305     bool reallocate(ref void[] b, size_t newSize) shared
306     {
307         return alignedReallocate(b, newSize, alignment);
308     }
309 
310     /**
311     On Posix there is no `realloc` for aligned memory, so `alignedReallocate` emulates
312     the needed behavior by using `alignedAllocate` to get a new block. The existing
313     block is copied to the new block and then freed.
314     On Windows, calls $(HTTPS msdn.microsoft.com/en-us/library/y69db7sx.aspx,
315     $(D __aligned_realloc(b.ptr, newSize, a))).
316     */
317     version (Windows)
318     @system @nogc nothrow
319     bool alignedReallocate(ref void[] b, size_t s, uint a) shared
320     {
321         if (!s)
322         {
323             deallocate(b);
324             b = null;
325             return true;
326         }
327         auto p = cast(ubyte*) _aligned_realloc(b.ptr, s, a);
328         if (!p) return false;
329         b = p[0 .. s];
330         return true;
331     }
332 
333     /// ditto
334     version (Posix)
335     @system @nogc nothrow
336     bool alignedReallocate(ref void[] b, size_t s, uint a) shared
337     {
338         if (!s)
339         {
340             deallocate(b);
341             b = null;
342             return true;
343         }
344         auto p = alignedAllocate(s, a);
345         if (!p.ptr)
346         {
347             return false;
348         }
349         import std.algorithm.comparison : min;
350         const upTo = min(s, b.length);
351         p[0 .. upTo] = b[0 .. upTo];
352         deallocate(b);
353         b = p;
354         return true;
355     }
356 
357     /**
358     Returns the global instance of this allocator type. The C heap allocator is
359     thread-safe, therefore all of its methods and `instance` itself are
360     `shared`.
361     */
362     static shared AlignedMallocator instance;
363 }
364 
365 ///
366 @nogc @system nothrow unittest
367 {
368     auto buffer = AlignedMallocator.instance.alignedAllocate(1024 * 1024 * 4,
369         128);
370     scope(exit) AlignedMallocator.instance.deallocate(buffer);
371     //...
372 }
373 
374 version (Posix)
375 @nogc @system nothrow unittest
376 {
377     // https://issues.dlang.org/show_bug.cgi?id=16398
378     // test the "pseudo" alignedReallocate for Posix
379     void[] b = AlignedMallocator.instance.alignedAllocate(16, 32);
380     (cast(ubyte[]) b)[] = ubyte(1);
381     AlignedMallocator.instance.alignedReallocate(b, 32, 32);
382     ubyte[16] o;
383     o[] = 1;
384     assert((cast(ubyte[]) b)[0 .. 16] == o);
385     AlignedMallocator.instance.alignedReallocate(b, 4, 32);
386     assert((cast(ubyte[]) b)[0 .. 3] == o[0 .. 3]);
387     AlignedMallocator.instance.alignedReallocate(b, 128, 32);
388     assert((cast(ubyte[]) b)[0 .. 3] == o[0 .. 3]);
389     AlignedMallocator.instance.deallocate(b);
390 
391     void[] c;
392     AlignedMallocator.instance.alignedReallocate(c, 32, 32);
393     assert(c.ptr);
394 
395     version (LDC_AddressSanitizer) {} else // AddressSanitizer does not support such large memory allocations (0x10000000000 max)
396     version (DragonFlyBSD) {} else    /* FIXME: Malloc on DragonFly does not return NULL when allocating more than UINTPTR_MAX
397                                        * $(LINK: https://bugs.dragonflybsd.org/issues/3114, dragonfly bug report)
398                                        * $(LINK: https://github.com/dlang/druntime/pull/1999#discussion_r157536030, PR Discussion) */
399     assert(!AlignedMallocator.instance.alignedReallocate(c, size_t.max, 4096));
400     AlignedMallocator.instance.deallocate(c);
401 }
402 
403 version (CRuntime_DigitalMars)
404 @nogc @system nothrow unittest
405 {
406     void* m;
407 
408     size_t m_addr() { return cast(size_t) m; }
409 
410     m = _aligned_malloc(16, 0x10);
411     if (m)
412     {
413         assert((m_addr & 0xF) == 0);
414         _aligned_free(m);
415     }
416 
417     m = _aligned_malloc(16, 0x100);
418     if (m)
419     {
420         assert((m_addr & 0xFF) == 0);
421         _aligned_free(m);
422     }
423 
424     m = _aligned_malloc(16, 0x1000);
425     if (m)
426     {
427         assert((m_addr & 0xFFF) == 0);
428         _aligned_free(m);
429     }
430 
431     m = _aligned_malloc(16, 0x10);
432     if (m)
433     {
434         assert((cast(size_t) m & 0xF) == 0);
435         m = _aligned_realloc(m, 32, 0x10000);
436         if (m) assert((m_addr & 0xFFFF) == 0);
437         _aligned_free(m);
438     }
439 
440     m = _aligned_malloc(8, 0x10);
441     if (m)
442     {
443         *cast(ulong*) m = 0X01234567_89ABCDEF;
444         m = _aligned_realloc(m, 0x800, 0x1000);
445         if (m) assert(*cast(ulong*) m == 0X01234567_89ABCDEF);
446         _aligned_free(m);
447     }
448 }