libphobos/libdruntime/core/internal/gc/pooltable.d

   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     import core.internal.gc.impl.conservative.gc : PAGESIZE;
 185
 186     enum NPOOLS = 6;
 187     enum NPAGES = 10;
 188
 189     static struct MockPool
 190     {
 191         byte* baseAddr, topAddr;
 192         size_t freepages, npages, ptIndex;
 193         @property bool isFree() const scope pure nothrow @nogc { return freepages == npages; }
 194     }
 195     PoolTable!MockPool pooltable;
 196
 197     void reset()
 198     {
 199         foreach (ref pool; pooltable[0 .. $])
 200             pool.freepages = pool.npages;
 201         pooltable.minimize();
 202         assert(pooltable.length == 0);
 203
 204         foreach (i; 0 .. NPOOLS)
 205         {
 206             auto pool = cast(MockPool*)cstdlib.malloc(MockPool.sizeof);
 207             *pool = MockPool.init;
 208             assert(pooltable.insert(pool));
 209         }
 210     }
 211
 212     void usePools()
 213     {
 214         foreach (pool; pooltable[0 .. $])
 215         {
 216             pool.npages = NPAGES;
 217             pool.freepages = NPAGES / 2;
 218         }
 219     }
 220
 221     // all pools are free
 222     reset();
 223     assert(pooltable.length == NPOOLS);
 224     auto freed = pooltable.minimize();
 225     assert(freed.length == NPOOLS);
 226     assert(pooltable.length == 0);
 227
 228     // all pools used
 229     reset();
 230     usePools();
 231     assert(pooltable.length == NPOOLS);
 232     freed = pooltable.minimize();
 233     assert(freed.length == 0);
 234     assert(pooltable.length == NPOOLS);
 235
 236     // preserves order of used pools
 237     reset();
 238     usePools();
 239
 240     {
 241         MockPool*[NPOOLS] opools = pooltable[0 .. NPOOLS];
 242         // make the 2nd pool free
 243         pooltable[2].freepages = NPAGES;
 244
 245         pooltable.minimize();
 246         assert(pooltable.length == NPOOLS - 1);
 247         assert(pooltable[0] == opools[0]);
 248         assert(pooltable[1] == opools[1]);
 249         assert(pooltable[2] == opools[3]);
 250     }
 251
 252     // test that PoolTable reduces min/max address span
 253     reset();
 254     usePools();
 255
 256     byte* base, top;
 257
 258     {
 259         // fill with fake addresses
 260         size_t i;
 261         foreach (pool; pooltable[0 .. NPOOLS])
 262         {
 263             pool.baseAddr = cast(byte*)(i++ * NPAGES * PAGESIZE);
 264             pool.topAddr = pool.baseAddr + NPAGES * PAGESIZE;
 265         }
 266         base = pooltable[0].baseAddr;
 267         top = pooltable[NPOOLS - 1].topAddr;
 268     }
 269
 270     freed = pooltable.minimize();
 271     assert(freed.length == 0);
 272     assert(pooltable.length == NPOOLS);
 273     assert(pooltable.minAddr == base);
 274     assert(pooltable.maxAddr == top);
 275
 276     pooltable[NPOOLS - 1].freepages = NPAGES;
 277     pooltable[NPOOLS - 2].freepages = NPAGES;
 278
 279     freed = pooltable.minimize();
 280     assert(freed.length == 2);
 281     assert(pooltable.length == NPOOLS - 2);
 282     assert(pooltable.minAddr == base);
 283     assert(pooltable.maxAddr == pooltable[NPOOLS - 3].topAddr);
 284
 285     pooltable[0].freepages = NPAGES;
 286
 287     freed = pooltable.minimize();
 288     assert(freed.length == 1);
 289     assert(pooltable.length == NPOOLS - 3);
 290     assert(pooltable.minAddr != base);
 291     assert(pooltable.minAddr == pooltable[0].baseAddr);
 292     assert(pooltable.maxAddr == pooltable[NPOOLS - 4].topAddr);
 293
 294     // free all
 295     foreach (pool; pooltable[0 .. $])
 296         pool.freepages = NPAGES;
 297     freed = pooltable.minimize();
 298     assert(freed.length == NPOOLS - 3);
 299     assert(pooltable.length == 0);
 300     pooltable.Dtor();
 301 }