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