2 * A sorted array to quickly lookup pools.
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
8 module core.internal.gc.pooltable;
10 static import cstdlib=core.stdc.stdlib;
12 struct PoolTable(Pool)
14 import core.stdc.string : memmove;
16 void Dtor() nothrow @nogc
23 bool insert(Pool* pool) nothrow @nogc
25 auto newpools = cast(Pool **)cstdlib.realloc(pools, (npools + 1) * pools[0].sizeof);
31 // Sort pool into newpooltable[]
33 for (; i < npools; ++i)
35 if (pool.baseAddr < pools[i].baseAddr)
39 memmove(pools + i + 1, pools + i, (npools - i) * pools[0].sizeof);
44 foreach (idx; i .. npools)
45 pools[idx].ptIndex = idx;
47 _minAddr = pools[0].baseAddr;
48 _maxAddr = pools[npools - 1].topAddr;
53 @property size_t length() const scope @safe pure nothrow @nogc
58 ref inout(Pool*) opIndex(size_t idx) inout return @trusted pure nothrow @nogc
59 in { assert(idx < length); }
65 inout(Pool*)[] opSlice(size_t a, size_t b) inout return @trusted pure nothrow @nogc
66 in { assert(a <= length && b <= length); }
72 /// Returns: A slice over all pools in this `PoolTable`
73 inout(Pool*)[] opSlice() inout return @trusted pure nothrow @nogc
75 return this.pools[0 .. this.length];
78 alias opDollar = length;
81 * Find Pool that pointer is in.
82 * Return null if not in a Pool.
83 * Assume pooltable[] is sorted.
85 Pool *findPool(void *p) nothrow @nogc
87 if (p >= minAddr && p < maxAddr)
91 // let dmd allocate a register for this.pools
92 auto pools = this.pools;
97 /* The pooltable[] is sorted by address, so do a binary search
100 size_t high = npools - 1;
103 size_t mid = (low + high) >> 1;
104 auto pool = pools[mid];
105 if (p < pool.baseAddr)
107 else if (p >= pool.topAddr)
116 // semi-stable partition, returns right half for which pred is false
117 Pool*[] minimize() pure nothrow @nogc
119 static void swap(ref Pool* a, ref Pool* b)
121 auto c = a; a = b; b = c;
125 // find first bad entry
126 for (; i < npools; ++i)
127 if (pools[i].isFree) break;
129 // move good in front of bad entries
131 for (; j < npools; ++j)
133 if (!pools[j].isFree) // keep
135 swap(pools[i], pools[j]);
136 pools[i].ptIndex = i;
140 // npooltable[0 .. i] => used pools
141 // npooltable[i .. npools] => free pools
145 _minAddr = pools[0].baseAddr;
146 _maxAddr = pools[i - 1].topAddr;
150 _minAddr = _maxAddr = null;
153 immutable len = npools;
155 // return freed pools to the caller
156 return pools[npools .. len];
159 void Invariant() const nothrow @nogc
163 foreach (i; 0 .. npools)
164 assert(pools[i].ptIndex == i);
166 foreach (i, pool; pools[0 .. npools - 1])
167 assert(pool.baseAddr < pools[i + 1].baseAddr);
169 assert(_minAddr == pools[0].baseAddr);
170 assert(_maxAddr == pools[npools - 1].topAddr);
173 @property const(void)* minAddr() const @safe pure nothrow @nogc { return _minAddr; }
174 @property const(void)* maxAddr() const @safe pure nothrow @nogc { return _maxAddr; }
179 void* _minAddr, _maxAddr;
186 enum PAGESIZE = 4096;
188 static struct MockPool
190 byte* baseAddr, topAddr;
191 size_t freepages, npages, ptIndex;
192 @property bool isFree() const scope pure nothrow @nogc { return freepages == npages; }
194 PoolTable!MockPool pooltable;
198 foreach (ref pool; pooltable[0 .. $])
199 pool.freepages = pool.npages;
200 pooltable.minimize();
201 assert(pooltable.length == 0);
203 foreach (i; 0 .. NPOOLS)
205 auto pool = cast(MockPool*)cstdlib.malloc(MockPool.sizeof);
206 *pool = MockPool.init;
207 assert(pooltable.insert(pool));
213 foreach (pool; pooltable[0 .. $])
215 pool.npages = NPAGES;
216 pool.freepages = NPAGES / 2;
220 // all pools are free
222 assert(pooltable.length == NPOOLS);
223 auto freed = pooltable.minimize();
224 assert(freed.length == NPOOLS);
225 assert(pooltable.length == 0);
230 assert(pooltable.length == NPOOLS);
231 freed = pooltable.minimize();
232 assert(freed.length == 0);
233 assert(pooltable.length == NPOOLS);
235 // preserves order of used pools
240 MockPool*[NPOOLS] opools = pooltable[0 .. NPOOLS];
241 // make the 2nd pool free
242 pooltable[2].freepages = NPAGES;
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]);
251 // test that PoolTable reduces min/max address span
258 // fill with fake addresses
260 foreach (pool; pooltable[0 .. NPOOLS])
262 pool.baseAddr = cast(byte*)(i++ * NPAGES * PAGESIZE);
263 pool.topAddr = pool.baseAddr + NPAGES * PAGESIZE;
265 base = pooltable[0].baseAddr;
266 top = pooltable[NPOOLS - 1].topAddr;
269 freed = pooltable.minimize();
270 assert(freed.length == 0);
271 assert(pooltable.length == NPOOLS);
272 assert(pooltable.minAddr == base);
273 assert(pooltable.maxAddr == top);
275 pooltable[NPOOLS - 1].freepages = NPAGES;
276 pooltable[NPOOLS - 2].freepages = NPAGES;
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);
284 pooltable[0].freepages = NPAGES;
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);
294 foreach (pool; pooltable[0 .. $])
295 pool.freepages = NPAGES;
296 freed = pooltable.minimize();
297 assert(freed.length == NPOOLS - 3);
298 assert(pooltable.length == 0);