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