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 */ 8module gc.pooltable; 9 10static import cstdlib=core.stdc.stdlib; 11 12struct PoolTable(Pool) 13{ 14 import core.stdc.string : memmove; 15 16nothrow: 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 161package: 162 Pool** pools; 163 size_t npools; 164 void* _minAddr, _maxAddr; 165} 166 167unittest 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; 177 @property bool isFree() const pure nothrow { return freepages == npages; } 178 } 179 PoolTable!MockPool pooltable; 180 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 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; 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