1// Written in the D programming language.
2/**
3Source: $(PHOBOSSRC std/experimental/allocator/building_blocks/quantizer.d)
4*/
5module std.experimental.allocator.building_blocks.quantizer;
6
7import std.experimental.allocator.common;
8
9/**
10This allocator sits on top of `ParentAllocator` and quantizes allocation sizes,
11usually from arbitrary positive numbers to a small set of round numbers (e.g.
12powers of two, page sizes etc). This technique is commonly used to:
13
14$(UL
15$(LI Preallocate more memory than requested such that later on, when
16reallocation is needed (e.g. to grow an array), expansion can be done quickly
17in place. Reallocation to smaller sizes is also fast (in-place) when the new
18size requested is within the same quantum as the existing size. Code that's
19reallocation-heavy can therefore benefit from fronting a generic allocator with
20a `Quantizer`. These advantages are present even if `ParentAllocator` does not
21support reallocation at all.)
22$(LI Improve behavior of allocators sensitive to allocation sizes, such as
23`FreeList` and `FreeTree`. Rounding allocation requests up makes for smaller
24free lists/trees at the cost of slack memory (internal fragmentation).)
25)
26
27The following methods are forwarded to the parent allocator if present:
28`allocateAll`, `owns`, `deallocateAll`, `empty`.
29
30Preconditions: `roundingFunction` must satisfy three constraints. These are
31not enforced (save for the use of `assert`) for the sake of efficiency.
32$(OL
33$(LI $(D roundingFunction(n) >= n) for all `n` of type `size_t`;)
34$(LI `roundingFunction` must be monotonically increasing, i.e. $(D
35roundingFunction(n1) <= roundingFunction(n2)) for all $(D n1 < n2);)
36$(LI `roundingFunction` must be `nothrow`, `@safe`, `@nogc` and `pure`, i.e.
37always return the same value for a given `n`.)
38)
39*/
40struct Quantizer(ParentAllocator, alias roundingFunction)
41{
42    import std.traits : hasMember;
43
44    /**
45    The parent allocator. Depending on whether `ParentAllocator` holds state
46    or not, this is a member variable or an alias for
47    `ParentAllocator.instance`.
48    */
49    static if (stateSize!ParentAllocator)
50    {
51        ParentAllocator parent;
52    }
53    else
54    {
55        alias parent = ParentAllocator.instance;
56        __gshared Quantizer instance;
57    }
58
59    /**
60    Returns `roundingFunction(n)`.
61    */
62    size_t goodAllocSize(size_t n)
63    {
64        auto result = roundingFunction(n);
65        assert(result >= n);
66        return result;
67    }
68
69    /**
70    Alignment is identical to that of the parent.
71    */
72    enum alignment = ParentAllocator.alignment;
73
74    /**
75    Gets a larger buffer `buf` by calling
76    `parent.allocate(goodAllocSize(n))`. If `buf` is `null`, returns
77    `null`. Otherwise, returns $(D buf[0 .. n]).
78    */
79    void[] allocate(size_t n)
80    {
81        auto result = parent.allocate(goodAllocSize(n));
82        return result.ptr ? result.ptr[0 .. n] : null;
83    }
84
85    static if (hasMember!(ParentAllocator, "allocateZeroed"))
86    package(std) void[] allocateZeroed()(size_t n)
87    {
88        auto result = parent.allocateZeroed(goodAllocSize(n));
89        return result.ptr ? result.ptr[0 .. n] : null;
90    }
91
92    /**
93    Defined only if `parent.alignedAllocate` exists and works similarly to
94    `allocate` by forwarding to
95    $(D parent.alignedAllocate(goodAllocSize(n), a)).
96    */
97    static if (hasMember!(ParentAllocator, "alignedAllocate"))
98    void[] alignedAllocate(size_t n, uint a)
99    {
100        auto result = parent.alignedAllocate(goodAllocSize(n), a);
101        return result.ptr ? result.ptr[0 .. n] : null;
102    }
103
104    /**
105    First checks whether there's enough slack memory preallocated for `b`
106    by evaluating $(D b.length + delta <= goodAllocSize(b.length)). If that's
107    the case, expands `b` in place. Otherwise, attempts to use
108    `parent.expand` appropriately if present.
109    */
110    bool expand(ref void[] b, size_t delta)
111    {
112        if (!b || delta == 0) return delta == 0;
113        immutable allocated = goodAllocSize(b.length),
114            needed = b.length + delta,
115            neededAllocation = goodAllocSize(needed);
116        assert(b.length <= allocated);
117        assert(needed <= neededAllocation);
118        assert(allocated <= neededAllocation);
119        // Second test needed because expand must work for null pointers, too.
120        if (allocated == neededAllocation)
121        {
122            // Nice!
123            b = (() @trusted => b.ptr[0 .. needed])();
124            return true;
125        }
126        // Hail Mary
127        static if (hasMember!(ParentAllocator, "expand"))
128        {
129            // Expand to the appropriate quantum
130            auto original = (() @trusted => b.ptr[0 .. allocated])();
131            assert(goodAllocSize(needed) >= allocated);
132            if (!parent.expand(original, neededAllocation - allocated))
133                return false;
134            // Dial back the size
135            b = (() @trusted => original.ptr[0 .. needed])();
136            return true;
137        }
138        else
139        {
140            return false;
141        }
142    }
143
144    /**
145    Expands or shrinks allocated block to an allocated size of $(D
146    goodAllocSize(s)). Expansion occurs in place under the conditions required
147    by `expand`. Shrinking occurs in place if $(D goodAllocSize(b.length)
148    == goodAllocSize(s)).
149    */
150    bool reallocate(ref void[] b, size_t s)
151    {
152        if (!b.ptr)
153        {
154            b = allocate(s);
155            return b.length == s;
156        }
157        if (s >= b.length && expand(b, s - b.length)) return true;
158        immutable toAllocate = goodAllocSize(s),
159            allocated = goodAllocSize(b.length);
160        // Are the lengths within the same quantum?
161        if (allocated == toAllocate)
162        {
163            // Reallocation (whether up or down) will be done in place
164            b = b.ptr[0 .. s];
165            return true;
166        }
167        // Defer to parent (or global) with quantized size
168        auto original = b.ptr[0 .. allocated];
169        if (!parent.reallocate(original, toAllocate)) return false;
170        b = original.ptr[0 .. s];
171        return true;
172    }
173
174    /**
175    Defined only if `ParentAllocator.alignedAllocate` exists. Expansion
176    occurs in place under the conditions required by `expand`. Shrinking
177    occurs in place if $(D goodAllocSize(b.length) == goodAllocSize(s)).
178    */
179    static if (hasMember!(ParentAllocator, "alignedAllocate"))
180    bool alignedReallocate(ref void[] b, size_t s, uint a)
181    {
182        if (!b.ptr)
183        {
184            b = alignedAllocate(s, a);
185            return b.length == s;
186        }
187        if (s >= b.length && b.ptr.alignedAt(a) && expand(b, s - b.length)) return true;
188        immutable toAllocate = goodAllocSize(s),
189            allocated = goodAllocSize(b.length);
190        // Are the lengths within the same quantum?
191        if (allocated == toAllocate && b.ptr.alignedAt(a))
192        {
193            assert(b.ptr); // code above must have caught this
194            // Reallocation (whether up or down) will be done in place
195            b = b.ptr[0 .. s];
196            return true;
197        }
198        // Defer to parent (or global) with quantized size
199        auto original = b.ptr[0 .. allocated];
200        if (!parent.alignedReallocate(original, toAllocate, a)) return false;
201        b = original.ptr[0 .. s];
202        return true;
203    }
204
205    /**
206    Defined if `ParentAllocator.deallocate` exists and forwards to
207    $(D parent.deallocate(b.ptr[0 .. goodAllocSize(b.length)])).
208    */
209    static if (hasMember!(ParentAllocator, "deallocate"))
210    bool deallocate(void[] b)
211    {
212        if (!b.ptr) return true;
213        return parent.deallocate(b.ptr[0 .. goodAllocSize(b.length)]);
214    }
215
216    // Forwarding methods
217    mixin(forwardToMember("parent",
218        "allocateAll", "owns", "deallocateAll", "empty"));
219}
220
221///
222@system unittest
223{
224    import std.experimental.allocator.building_blocks.free_tree : FreeTree;
225    import std.experimental.allocator.gc_allocator : GCAllocator;
226
227    size_t roundUpToMultipleOf(size_t s, uint base)
228    {
229        auto rem = s % base;
230        return rem ? s + base - rem : s;
231    }
232
233    // Quantize small allocations to a multiple of cache line, large ones to a
234    // multiple of page size
235    alias MyAlloc = Quantizer!(
236        FreeTree!GCAllocator,
237        n => roundUpToMultipleOf(n, n <= 16_384 ? 64 : 4096));
238    MyAlloc alloc;
239    const buf = alloc.allocate(256);
240    assert(buf.ptr);
241}
242
243version (StdUnittest)
244@system unittest
245{
246    import std.experimental.allocator.gc_allocator : GCAllocator;
247    alias MyAlloc = Quantizer!(GCAllocator,
248        (size_t n) => n.roundUpToMultipleOf(64));
249    testAllocator!(() => MyAlloc());
250
251    assert((() pure nothrow @safe @nogc => MyAlloc().goodAllocSize(1))() == 64);
252
253    auto a = MyAlloc();
254    auto b = a.allocate(42);
255    assert(b.length == 42);
256    // Inplace expand, since goodAllocSize is 64
257    assert((() @safe => a.expand(b, 22))());
258    //assert((() nothrow @safe => a.expand(b, 22))());
259    assert(b.length == 64);
260    // Trigger parent.expand, which may or may not succed
261    //() nothrow @safe { a.expand(b, 1); }();
262    () @safe { a.expand(b, 1); }();
263    assert(a.reallocate(b, 100));
264    assert(b.length == 100);
265    // Ensure deallocate inherits from parent
266    () nothrow @nogc { a.deallocate(b); }();
267}
268
269@system unittest
270{
271    import std.experimental.allocator.building_blocks.region : Region;
272    import std.experimental.allocator.mallocator : Mallocator;
273    import std.typecons : Ternary;
274
275    alias Alloc = Quantizer!(Region!(Mallocator),
276            (size_t n) => n.roundUpToMultipleOf(64));
277    auto a = Alloc(Region!Mallocator(1024 * 64));
278    const b = a.allocate(42);
279    assert(b.length == 42);
280    // Check that owns inherits from parent, i.e. Region
281    assert((() pure nothrow @safe @nogc => a.owns(b))() == Ternary.yes);
282    assert((() pure nothrow @safe @nogc => a.owns(null))() == Ternary.no);
283
284    auto c = a.allocate(42);
285    assert(c.length == 42);
286    assert((() pure nothrow @safe @nogc => a.owns(c))() == Ternary.yes);
287    // Inplace expand, since goodAllocSize is 64
288    assert((() nothrow @safe => a.expand(c, 22))());
289    assert(c.length == 64);
290    // Trigger parent.expand
291    assert((() nothrow @safe => a.expand(c, 1))());
292    assert(c.length == 65);
293    // Check that reallocate inherits from parent
294    assert((() nothrow @nogc => a.reallocate(c, 100))());
295    assert(c.length == 100);
296}
297
298version (StdUnittest)
299@system unittest
300{
301    import std.experimental.allocator.building_blocks.region : Region;
302    import std.experimental.allocator.mallocator : Mallocator;
303
304    alias MyAlloc = Quantizer!(Region!(Mallocator),
305            (size_t n) => n.roundUpToMultipleOf(64));
306    testAllocator!(() => MyAlloc(Region!Mallocator(1024 * 64)));
307
308    auto a = MyAlloc(Region!Mallocator(1024 * 64));
309    void[] b;
310    assert((() nothrow @nogc => a.alignedReallocate(b, 42, 16))());
311    assert(b.length == 42);
312    assert(alignedAt(&b[0], 16));
313}
314
315version (StdUnittest)
316@system unittest
317{
318    import std.experimental.allocator.building_blocks.region : Region;
319    import std.typecons : Ternary;
320
321    alias MyAlloc = Quantizer!(Region!(),
322        (size_t n) => n.roundUpToMultipleOf(64));
323    testAllocator!(() => MyAlloc(Region!()(new ubyte[1024 * 64])));
324
325    auto a = MyAlloc(Region!()(new ubyte[1024 * 64]));
326    // Check that empty inherits from parent
327    assert((() pure nothrow @safe @nogc => a.empty)() == Ternary.yes);
328    auto b = a.allocate(42);
329    assert(b.length == 42);
330    assert((() pure nothrow @safe @nogc => a.empty)() == Ternary.no);
331    // Check that deallocateAll inherits from parent
332    assert((() nothrow @nogc => a.deallocateAll())());
333    assert((() pure nothrow @safe @nogc => a.empty)() == Ternary.yes);
334}
335