]>
Commit | Line | Data |
---|---|---|
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 | ||
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; | |
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 | } |