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