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;
24 bool insert(Pool* pool)
26 auto newpools = cast(Pool **)cstdlib.realloc(pools, (npools + 1) * pools[0].sizeof);
32 // Sort pool into newpooltable[]
34 for (; i < npools; ++i)
36 if (pool.baseAddr < pools[i].baseAddr)
40 memmove(pools + i + 1, pools + i, (npools - i) * pools[0].sizeof);
45 foreach (idx; i .. npools)
46 pools[idx].ptIndex = idx;
48 _minAddr = pools[0].baseAddr;
49 _maxAddr = pools[npools - 1].topAddr;
54 @property size_t length() pure const
59 ref inout(Pool*) opIndex(size_t idx) inout pure
60 in { assert(idx < length); }
66 inout(Pool*)[] opSlice(size_t a, size_t b) inout pure
67 in { assert(a <= length && b <= length); }
73 alias opDollar = length;
76 * Find Pool that pointer is in.
77 * Return null if not in a Pool.
78 * Assume pooltable[] is sorted.
80 Pool *findPool(void *p) nothrow
82 if (p >= minAddr && p < maxAddr)
86 // let dmd allocate a register for this.pools
87 auto pools = this.pools;
92 /* The pooltable[] is sorted by address, so do a binary search
95 size_t high = npools - 1;
98 size_t mid = (low + high) >> 1;
99 auto pool = pools[mid];
100 if (p < pool.baseAddr)
102 else if (p >= pool.topAddr)
111 // semi-stable partition, returns right half for which pred is false
112 Pool*[] minimize() pure
114 static void swap(ref Pool* a, ref Pool* b)
116 auto c = a; a = b; b = c;
120 // find first bad entry
121 for (; i < npools; ++i)
122 if (pools[i].isFree) break;
124 // move good in front of bad entries
126 for (; j < npools; ++j)
128 if (!pools[j].isFree) // keep
130 swap(pools[i], pools[j]);
131 pools[i].ptIndex = i;
135 // npooltable[0 .. i] => used pools
136 // npooltable[i .. npools] => free pools
140 _minAddr = pools[0].baseAddr;
141 _maxAddr = pools[i - 1].topAddr;
145 _minAddr = _maxAddr = null;
148 immutable len = npools;
150 // return freed pools to the caller
151 return pools[npools .. len];
154 void Invariant() const
158 foreach (i; 0 .. npools)
159 assert(pools[i].ptIndex == i);
161 foreach (i, pool; pools[0 .. npools - 1])
162 assert(pool.baseAddr < pools[i + 1].baseAddr);
164 assert(_minAddr == pools[0].baseAddr);
165 assert(_maxAddr == pools[npools - 1].topAddr);
168 @property const(void)* minAddr() pure const { return _minAddr; }
169 @property const(void)* maxAddr() pure const { return _maxAddr; }
174 void* _minAddr, _maxAddr;
181 enum PAGESIZE = 4096;
183 static struct MockPool
185 byte* baseAddr, topAddr;
186 size_t freepages, npages, ptIndex;
187 @property bool isFree() const pure nothrow { return freepages == npages; }
189 PoolTable!MockPool pooltable;
193 foreach (ref pool; pooltable[0 .. $])
194 pool.freepages = pool.npages;
195 pooltable.minimize();
196 assert(pooltable.length == 0);
198 foreach (i; 0 .. NPOOLS)
200 auto pool = cast(MockPool*)cstdlib.malloc(MockPool.sizeof);
201 *pool = MockPool.init;
202 assert(pooltable.insert(pool));
208 foreach (pool; pooltable[0 .. $])
210 pool.npages = NPAGES;
211 pool.freepages = NPAGES / 2;
215 // all pools are free
217 assert(pooltable.length == NPOOLS);
218 auto freed = pooltable.minimize();
219 assert(freed.length == NPOOLS);
220 assert(pooltable.length == 0);
225 assert(pooltable.length == NPOOLS);
226 freed = pooltable.minimize();
227 assert(freed.length == 0);
228 assert(pooltable.length == NPOOLS);
230 // preserves order of used pools
235 MockPool*[NPOOLS] opools = pooltable[0 .. NPOOLS];
236 // make the 2nd pool free
237 pooltable[2].freepages = NPAGES;
239 pooltable.minimize();
240 assert(pooltable.length == NPOOLS - 1);
241 assert(pooltable[0] == opools[0]);
242 assert(pooltable[1] == opools[1]);
243 assert(pooltable[2] == opools[3]);
246 // test that PoolTable reduces min/max address span
253 // fill with fake addresses
255 foreach (pool; pooltable[0 .. NPOOLS])
257 pool.baseAddr = cast(byte*)(i++ * NPAGES * PAGESIZE);
258 pool.topAddr = pool.baseAddr + NPAGES * PAGESIZE;
260 base = pooltable[0].baseAddr;
261 top = pooltable[NPOOLS - 1].topAddr;
264 freed = pooltable.minimize();
265 assert(freed.length == 0);
266 assert(pooltable.length == NPOOLS);
267 assert(pooltable.minAddr == base);
268 assert(pooltable.maxAddr == top);
270 pooltable[NPOOLS - 1].freepages = NPAGES;
271 pooltable[NPOOLS - 2].freepages = NPAGES;
273 freed = pooltable.minimize();
274 assert(freed.length == 2);
275 assert(pooltable.length == NPOOLS - 2);
276 assert(pooltable.minAddr == base);
277 assert(pooltable.maxAddr == pooltable[NPOOLS - 3].topAddr);
279 pooltable[0].freepages = NPAGES;
281 freed = pooltable.minimize();
282 assert(freed.length == 1);
283 assert(pooltable.length == NPOOLS - 3);
284 assert(pooltable.minAddr != base);
285 assert(pooltable.minAddr == pooltable[0].baseAddr);
286 assert(pooltable.maxAddr == pooltable[NPOOLS - 4].topAddr);
289 foreach (pool; pooltable[0 .. $])
290 pool.freepages = NPAGES;
291 freed = pooltable.minimize();
292 assert(freed.length == NPOOLS - 3);
293 assert(pooltable.length == 0);