1 /**
2  * Array container with paged allocation for internal usage.
3  *
4  * Copyright: Copyright Per Nordlöw 2018.
5  * License:   $(HTTP www.boost.org/LICENSE_1_0.txt, Boost License 1.0).
6  * Authors:   Per Nordlöw
7  */
8 module paged_dynamic_array;
9 
10 import core.stdc.stdio: printf;
11 
12 // version = PRINTF;
13 
14 private static void *os_mem_map(size_t nbytes) nothrow @nogc
15 {   void *p;
16 
17     import core.sys.posix.sys.mman;
18     p = mmap(null, nbytes, PROT_READ | PROT_WRITE, MAP_PRIVATE | MAP_ANON, -1, 0);
19     return (p == MAP_FAILED) ? null : p;
20 }
21 
22 private static int os_mem_unmap(void *base, size_t nbytes) nothrow @nogc
23 {
24     import core.sys.posix.sys.mman;
25     return munmap(base, nbytes);
26 }
27 
28 struct PagedDynamicArray(T)
29 {
30     import core.internal.traits : hasElaborateDestructor;
31     import core.exception : onOutOfMemoryErrorNoGC;
32 
33     @safe nothrow @nogc:
34 
35     @disable this(this);
36 
37     enum PAGESIZE = 4096;       // Linux $(shell getconf PAGESIZE)
38 
39     ~this()
40     {
41         reset();
42     }
43 
44     void reset()
45     {
46         length = 0;
47     }
48 
49     @property size_t length() const
50     {
51         return _length;
52     }
53 
54     @property size_t capacityInBytes() const
55     {
56         version(D_Coverage) {} else pragma(inline, true);
57         return _capacityInPages*PAGESIZE;
58     }
59 
60     /// Set length to `newLength`.
61     @property void length(size_t newLength) @trusted
62     {
63         if (newLength == 0)     // if zero `newLength` free stuff
64         {
65             version(PRINTF) printf("### %s() zeroed\n", __FUNCTION__.ptr);
66             if (_ptr != null)
67             {
68                 os_mem_unmap(_ptr, capacityInBytes);
69                 _ptr = null;
70             }
71             _capacityInPages = 0;
72         }
73         else
74         {
75             capacity = newLength; // set capacity
76         }
77         _length = newLength;
78     }
79 
80     /// Set capacity to `newCapacity`.
81     @property void capacity(size_t newCapacity) @trusted
82     {
83         import core.checkedint : mulu;
84 
85         if (newCapacity*T.sizeof > capacityInBytes) // common case first
86         {
87             bool overflow = false;
88             const size_t reqsize = mulu(T.sizeof, newCapacity, overflow);
89             const size_t newCapacityInPages = (reqsize + PAGESIZE - 1) / PAGESIZE;
90             version(PRINTF) printf("### %s() newCapacityInPages:%lu\n", __FUNCTION__.ptr, newCapacityInPages);
91             if (overflow)
92             {
93                 onOutOfMemoryErrorNoGC();
94             }
95 
96             static if (hasElaborateDestructor!T)
97             {
98                 static assert("destroy T");
99                 //
100                 // if (newLength < _length)
101                 // {
102                 //     foreach (ref val; _ptr[newLength .. _length])
103                 //     {
104                 //         common.destroy(val);
105                 //     }
106                 // }
107             }
108 
109             const newCapacityInBytes = newCapacityInPages*PAGESIZE;
110 
111             T* newPtr;
112             version(linux)
113             {
114                 if (_ptr !is null)  // if should do remap
115                 {
116                     version(PRINTF) printf("### %s() mremap(%p)\n", __FUNCTION__.ptr, _ptr);
117                     _ptr = cast(T*)mremap(_ptr, capacityInBytes,
118                                           newCapacityInBytes,
119                                           MREMAP_MAYMOVE);
120                     goto done;
121                 }
122             }
123 
124             newPtr = cast(T*)os_mem_map(newCapacityInBytes);
125             import core.stdc..string : memcpy;
126             if (_ptr !is null)
127             {
128                 memcpy(newPtr, _ptr, capacityInBytes); // TODO can we copy pages faster than this?
129                 os_mem_unmap(_ptr, capacityInBytes);
130             }
131             _ptr = newPtr;
132 
133         done:
134             _capacityInPages = newCapacityInPages;
135 
136             // rely on mmap zeroing for us
137             // if (newLength > _length)
138             // {
139             //     foreach (ref val; _ptr[_length .. newLength])
140             //     {
141             //         common.initialize(val);
142             //     }
143             // }
144         }
145     }
146 
147     @property bool empty() const
148     {
149         return !length;
150     }
151 
152     @property ref inout(T) front() inout
153     in { assert(!empty); }
154     do
155     {
156         return _ptr[0];
157     }
158 
159     @property ref inout(T) back() inout @trusted
160     in { assert(!empty); }
161     do
162     {
163         return _ptr[_length - 1];
164     }
165 
166     ref inout(T) opIndex(size_t idx) inout @trusted
167     in { assert(idx < length); }
168     do
169     {
170         return _ptr[idx];
171     }
172 
173     inout(T)[] opSlice() inout @trusted
174     {
175         return _ptr[0 .. _length];
176     }
177 
178     inout(T)[] opSlice(size_t a, size_t b) inout @trusted
179     in { assert(a < b && b <= length); }
180     do
181     {
182         return _ptr[a .. b];
183     }
184 
185     inout(T)* ptr() inout @system
186     {
187         return _ptr;
188     }
189 
190     alias length opDollar;
191 
192     void insertBack()(auto ref T val) @trusted
193     {
194         import core.checkedint : addu;
195         bool overflow = false;
196         const size_t newlength = addu(length, 1, overflow);
197         if (overflow)
198         {
199             onOutOfMemoryErrorNoGC();
200         }
201         length = newlength;
202         back = val;
203     }
204 
205     void popBack() @system
206     {
207         if (hasElaborateDestructor!T)
208         {
209             // destroy back element
210         }
211         length = length - 1;
212     }
213 
214     void remove(size_t idx) @system
215     in { assert(idx < length); }
216     do
217     {
218         if (hasElaborateDestructor!T)
219         {
220             // destroy `idx`:th element
221         }
222         foreach (i; idx .. length - 1)
223             _ptr[i] = _ptr[i+1]; // TODO move if hasElaborateDestructor!T
224         popBack();
225     }
226 
227     invariant
228     {
229         // TODO assert(!_ptr == !_length);
230     }
231 
232 private:
233     T* _ptr;
234     size_t _length;
235     size_t _capacityInPages;    // of size `PAGESIZE`
236 }
237 
238 version(linux)
239 {
240     enum MREMAP_MAYMOVE = 1;
241     nothrow @nogc:
242     extern(C) void *mremap(void *old_address, size_t old_size,
243                            size_t new_size, int flags, ... /* void *new_address */);
244 
245 }
246 
247 unittest
248 {
249     PagedDynamicArray!size_t ary;
250 
251     assert(ary[] == []);
252     ary.insertBack(5);
253     assert(ary[] == [5]);
254     assert(ary[$-1] == 5);
255     ary.popBack();
256     assert(ary[] == []);
257     ary.insertBack(0);
258     ary.insertBack(1);
259     assert(ary[] == [0, 1]);
260     assert(ary[0 .. 1] == [0]);
261     assert(ary[1 .. 2] == [1]);
262     assert(ary[$ - 2 .. $] == [0, 1]);
263     size_t idx;
264     foreach (val; ary) assert(idx++ == val);
265     foreach_reverse (val; ary) assert(--idx == val);
266     foreach (i, val; ary) assert(i == val);
267     foreach_reverse (i, val; ary) assert(i == val);
268 
269     ary.insertBack(2);
270     ary.remove(1);
271     assert(ary[] == [0, 2]);
272 
273     assert(!ary.empty);
274     ary.reset();
275     assert(ary.empty);
276     ary.insertBack(0);
277     assert(!ary.empty);
278     destroy(ary);
279     assert(ary.empty);
280 
281     // not copyable
282     static assert(!__traits(compiles, { PagedDynamicArray!size_t ary2 = ary; }));
283     PagedDynamicArray!size_t ary2;
284     static assert(!__traits(compiles, ary = ary2));
285     static void foo(PagedDynamicArray!size_t copy) {}
286     static assert(!__traits(compiles, foo(ary)));
287 
288     ary2.insertBack(0);
289     assert(ary.empty);
290     assert(ary2[] == [0]);
291 }
292 
293 unittest
294 {
295     import core.exception;
296     try
297     {
298         // Overflow ary.length.
299         auto ary = PagedDynamicArray!size_t(cast(size_t*)0xdeadbeef, -1);
300         ary.insertBack(0);
301     }
302     catch (OutOfMemoryError)
303     {
304     }
305     try
306     {
307         // Overflow requested memory size for common.xrealloc().
308         auto ary = PagedDynamicArray!size_t(cast(size_t*)0xdeadbeef, -2);
309         ary.insertBack(0);
310     }
311     catch (OutOfMemoryError)
312     {
313     }
314 }