1/**
2 * A sorted array to quickly lookup pools.
3 *
4 * Copyright: D Language Foundation 2001 - 2021
5 * License:   $(HTTP www.boost.org/LICENSE_1_0.txt, Boost License 1.0).
6 * Authors:   Walter Bright, David Friedman, Sean Kelly, Martin Nowak
7 */
8module core.internal.gc.pooltable;
9
10static import cstdlib=core.stdc.stdlib;
11
12struct PoolTable(Pool)
13{
14    import core.stdc.string : memmove;
15
16    void Dtor() nothrow @nogc
17    {
18        cstdlib.free(pools);
19        pools = null;
20        npools = 0;
21    }
22
23    bool insert(Pool* pool) nothrow @nogc
24    {
25        auto newpools = cast(Pool **)cstdlib.realloc(pools, (npools + 1) * pools[0].sizeof);
26        if (!newpools)
27            return false;
28
29        pools = newpools;
30
31        // Sort pool into newpooltable[]
32        size_t i;
33        for (; i < npools; ++i)
34        {
35            if (pool.baseAddr < pools[i].baseAddr)
36                break;
37        }
38        if (i != npools)
39            memmove(pools + i + 1, pools + i, (npools - i) * pools[0].sizeof);
40        pools[i] = pool;
41
42        ++npools;
43
44        foreach (idx; i .. npools)
45            pools[idx].ptIndex = idx;
46
47        _minAddr = pools[0].baseAddr;
48        _maxAddr = pools[npools - 1].topAddr;
49
50        return true;
51    }
52
53    @property size_t length() const scope @safe pure nothrow @nogc
54    {
55        return npools;
56    }
57
58    ref inout(Pool*) opIndex(size_t idx) inout return @trusted pure nothrow @nogc
59    in { assert(idx < length); }
60    do
61    {
62        return pools[idx];
63    }
64
65    inout(Pool*)[] opSlice(size_t a, size_t b) inout return @trusted pure nothrow @nogc
66    in { assert(a <= length && b <= length); }
67    do
68    {
69        return pools[a .. b];
70    }
71
72    /// Returns: A slice over all pools in this `PoolTable`
73    inout(Pool*)[] opSlice() inout return @trusted pure nothrow @nogc
74    {
75        return this.pools[0 .. this.length];
76    }
77
78    alias opDollar = length;
79
80    /**
81     * Find Pool that pointer is in.
82     * Return null if not in a Pool.
83     * Assume pooltable[] is sorted.
84     */
85    Pool *findPool(void *p) nothrow @nogc
86    {
87        if (p >= minAddr && p < maxAddr)
88        {
89            assert(npools);
90
91            // let dmd allocate a register for this.pools
92            auto pools = this.pools;
93
94            if (npools == 1)
95                return pools[0];
96
97            /* The pooltable[] is sorted by address, so do a binary search
98             */
99            size_t low = 0;
100            size_t high = npools - 1;
101            while (low <= high)
102            {
103                size_t mid = (low + high) >> 1;
104                auto pool = pools[mid];
105                if (p < pool.baseAddr)
106                    high = mid - 1;
107                else if (p >= pool.topAddr)
108                    low = mid + 1;
109                else
110                    return pool;
111            }
112        }
113        return null;
114    }
115
116    // semi-stable partition, returns right half for which pred is false
117    Pool*[] minimize() pure nothrow @nogc
118    {
119        static void swap(ref Pool* a, ref Pool* b)
120        {
121            auto c = a; a = b; b = c;
122        }
123
124        size_t i;
125        // find first bad entry
126        for (; i < npools; ++i)
127            if (pools[i].isFree) break;
128
129        // move good in front of bad entries
130        size_t j = i + 1;
131        for (; j < npools; ++j)
132        {
133            if (!pools[j].isFree) // keep
134            {
135                swap(pools[i], pools[j]);
136                pools[i].ptIndex = i;
137                ++i;
138            }
139        }
140        // npooltable[0 .. i]      => used pools
141        // npooltable[i .. npools] => free pools
142
143        if (i)
144        {
145            _minAddr = pools[0].baseAddr;
146            _maxAddr = pools[i - 1].topAddr;
147        }
148        else
149        {
150            _minAddr = _maxAddr = null;
151        }
152
153        immutable len = npools;
154        npools = i;
155        // return freed pools to the caller
156        return pools[npools .. len];
157    }
158
159    void Invariant() const nothrow @nogc
160    {
161        if (!npools) return;
162
163        foreach (i; 0 .. npools)
164            assert(pools[i].ptIndex == i);
165
166        foreach (i, pool; pools[0 .. npools - 1])
167            assert(pool.baseAddr < pools[i + 1].baseAddr);
168
169        assert(_minAddr == pools[0].baseAddr);
170        assert(_maxAddr == pools[npools - 1].topAddr);
171    }
172
173    @property const(void)* minAddr() const @safe pure nothrow @nogc { return _minAddr; }
174    @property const(void)* maxAddr() const @safe pure nothrow @nogc { return _maxAddr; }
175
176package:
177    Pool** pools;
178    size_t npools;
179    void* _minAddr, _maxAddr;
180}
181
182unittest
183{
184    enum NPOOLS = 6;
185    enum NPAGES = 10;
186    enum PAGESIZE = 4096;
187
188    static struct MockPool
189    {
190        byte* baseAddr, topAddr;
191        size_t freepages, npages, ptIndex;
192        @property bool isFree() const scope pure nothrow @nogc { return freepages == npages; }
193    }
194    PoolTable!MockPool pooltable;
195
196    void reset()
197    {
198        foreach (ref pool; pooltable[0 .. $])
199            pool.freepages = pool.npages;
200        pooltable.minimize();
201        assert(pooltable.length == 0);
202
203        foreach (i; 0 .. NPOOLS)
204        {
205            auto pool = cast(MockPool*)cstdlib.malloc(MockPool.sizeof);
206            *pool = MockPool.init;
207            assert(pooltable.insert(pool));
208        }
209    }
210
211    void usePools()
212    {
213        foreach (pool; pooltable[0 .. $])
214        {
215            pool.npages = NPAGES;
216            pool.freepages = NPAGES / 2;
217        }
218    }
219
220    // all pools are free
221    reset();
222    assert(pooltable.length == NPOOLS);
223    auto freed = pooltable.minimize();
224    assert(freed.length == NPOOLS);
225    assert(pooltable.length == 0);
226
227    // all pools used
228    reset();
229    usePools();
230    assert(pooltable.length == NPOOLS);
231    freed = pooltable.minimize();
232    assert(freed.length == 0);
233    assert(pooltable.length == NPOOLS);
234
235    // preserves order of used pools
236    reset();
237    usePools();
238
239    {
240        MockPool*[NPOOLS] opools = pooltable[0 .. NPOOLS];
241        // make the 2nd pool free
242        pooltable[2].freepages = NPAGES;
243
244        pooltable.minimize();
245        assert(pooltable.length == NPOOLS - 1);
246        assert(pooltable[0] == opools[0]);
247        assert(pooltable[1] == opools[1]);
248        assert(pooltable[2] == opools[3]);
249    }
250
251    // test that PoolTable reduces min/max address span
252    reset();
253    usePools();
254
255    byte* base, top;
256
257    {
258        // fill with fake addresses
259        size_t i;
260        foreach (pool; pooltable[0 .. NPOOLS])
261        {
262            pool.baseAddr = cast(byte*)(i++ * NPAGES * PAGESIZE);
263            pool.topAddr = pool.baseAddr + NPAGES * PAGESIZE;
264        }
265        base = pooltable[0].baseAddr;
266        top = pooltable[NPOOLS - 1].topAddr;
267    }
268
269    freed = pooltable.minimize();
270    assert(freed.length == 0);
271    assert(pooltable.length == NPOOLS);
272    assert(pooltable.minAddr == base);
273    assert(pooltable.maxAddr == top);
274
275    pooltable[NPOOLS - 1].freepages = NPAGES;
276    pooltable[NPOOLS - 2].freepages = NPAGES;
277
278    freed = pooltable.minimize();
279    assert(freed.length == 2);
280    assert(pooltable.length == NPOOLS - 2);
281    assert(pooltable.minAddr == base);
282    assert(pooltable.maxAddr == pooltable[NPOOLS - 3].topAddr);
283
284    pooltable[0].freepages = NPAGES;
285
286    freed = pooltable.minimize();
287    assert(freed.length == 1);
288    assert(pooltable.length == NPOOLS - 3);
289    assert(pooltable.minAddr != base);
290    assert(pooltable.minAddr == pooltable[0].baseAddr);
291    assert(pooltable.maxAddr == pooltable[NPOOLS - 4].topAddr);
292
293    // free all
294    foreach (pool; pooltable[0 .. $])
295        pool.freepages = NPAGES;
296    freed = pooltable.minimize();
297    assert(freed.length == NPOOLS - 3);
298    assert(pooltable.length == 0);
299    pooltable.Dtor();
300}
301