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 */ 8module core.internal.gc.pooltable; 9 10static import cstdlib=core.stdc.stdlib; 11 12struct 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 176package: 177 Pool** pools; 178 size_t npools; 179 void* _minAddr, _maxAddr; 180} 181 182unittest 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} 301