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 */
8 module core.internal.gc.pooltable;
9
10 static import cstdlib=core.stdc.stdlib;
11
PoolTable(Pool)12 struct 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
176 package:
177 Pool** pools;
178 size_t npools;
179 void* _minAddr, _maxAddr;
180 }
181
182 unittest
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;
isFreeMockPool192 @property bool isFree() const scope pure nothrow @nogc { return freepages == npages; }
193 }
194 PoolTable!MockPool pooltable;
195
reset()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
usePools()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;
foreach(pool;pooltable[0..NPOOLS])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