lib/mempool.c

   1 /*
   2  *      UCW Library -- Memory Pools (One-Time Allocation)
   3  *
   4  *      (c) 1997--2001 Martin Mares <mj@ucw.cz>
   5  *      (c) 2007 Pavel Charvat <pchar@ucw.cz>
   6  *
   7  *      This software may be freely distributed and used according to the terms
   8  *      of the GNU Lesser General Public License.
   9  */
  10
  11 #undef LOCAL_DEBUG
  12
  13 #include "lib/lib.h"
  14 #include "lib/mempool.h"
  15
  16 #include <string.h>
  17
  18 #define MP_CHUNK_TAIL ALIGN_TO(sizeof(struct mempool_chunk), CPU_STRUCT_ALIGN)
  19 #define MP_SIZE_MAX (~0U - MP_CHUNK_TAIL - CPU_PAGE_SIZE)
  20
  21 struct mempool_chunk {
  22   struct mempool_chunk *next;
  23   uns size;
  24 };
  25
  26 static uns
  27 mp_align_size(uns size)
  28 {
  29 #ifdef POOL_IS_MMAP
  30   return ALIGN_TO(size + MP_CHUNK_TAIL, CPU_PAGE_SIZE) - MP_CHUNK_TAIL;
  31 #else
  32   return ALIGN_TO(size, CPU_STRUCT_ALIGN);
  33 #endif
  34 }
  35
  36 void
  37 mp_init(struct mempool *pool, uns chunk_size)
  38 {
  39   chunk_size = mp_align_size(MAX(sizeof(struct mempool), chunk_size));
  40   *pool = (struct mempool) {
  41     .chunk_size = chunk_size,
  42     .threshold = chunk_size >> 1,
  43     .last_big = &pool->last_big };
  44 }
  45
  46 static void *
  47 mp_new_big_chunk(uns size)
  48 {
  49   struct mempool_chunk *chunk;
  50   chunk = xmalloc(size + MP_CHUNK_TAIL) + size;
  51   chunk->size = size;
  52   return chunk;
  53 }
  54
  55 static void
  56 mp_free_big_chunk(struct mempool_chunk *chunk)
  57 {
  58   xfree((void *)chunk - chunk->size);
  59 }
  60
  61 static void *
  62 mp_new_chunk(uns size)
  63 {
  64 #ifdef POOL_IS_MMAP
  65   struct mempool_chunk *chunk;
  66   chunk = page_alloc(size + MP_CHUNK_TAIL) + size;
  67   chunk->size = size;
  68   return chunk;
  69 #else
  70   return mp_new_big_chunk(size);
  71 #endif
  72 }
  73
  74 static void
  75 mp_free_chunk(struct mempool_chunk *chunk)
  76 {
  77 #ifdef POOL_IS_MMAP
  78   page_free((void *)chunk - chunk->size, chunk->size + MP_CHUNK_TAIL);
  79 #else
  80   mp_free_big_chunk(chunk);
  81 #endif
  82 }
  83
  84 struct mempool *
  85 mp_new(uns chunk_size)
  86 {
  87   chunk_size = mp_align_size(MAX(sizeof(struct mempool), chunk_size));
  88   struct mempool_chunk *chunk = mp_new_chunk(chunk_size);
  89   struct mempool *pool = (void *)chunk - chunk_size;
  90   DBG("Creating mempool %p with %u bytes long chunks", pool, chunk_size);
  91   chunk->next = NULL;
  92   *pool = (struct mempool) {
  93     .state = { .free = { chunk_size - sizeof(*pool) }, .last = { chunk } },
  94     .chunk_size = chunk_size,
  95     .threshold = chunk_size >> 1,
  96     .last_big = &pool->last_big };
  97   return pool;
  98 }
  99
 100 static void
 101 mp_free_chain(struct mempool_chunk *chunk)
 102 {
 103   while (chunk)
 104     {
 105       struct mempool_chunk *next = chunk->next;
 106       mp_free_chunk(chunk);
 107       chunk = next;
 108     }
 109 }
 110
 111 static void
 112 mp_free_big_chain(struct mempool_chunk *chunk)
 113 {
 114   while (chunk)
 115     {
 116       struct mempool_chunk *next = chunk->next;
 117       mp_free_big_chunk(chunk);
 118       chunk = next;
 119     }
 120 }
 121
 122 void
 123 mp_delete(struct mempool *pool)
 124 {
 125   DBG("Deleting mempool %p", pool);
 126   mp_free_big_chain(pool->state.last[1]);
 127   mp_free_chain(pool->unused);
 128   mp_free_chain(pool->state.last[0]); // can contain the mempool structure
 129 }
 130
 131 void
 132 mp_flush(struct mempool *pool)
 133 {
 134   mp_free_big_chain(pool->state.last[1]);
 135   struct mempool_chunk *chunk, *next;
 136   for (chunk = pool->state.last[0]; chunk && (void *)chunk - chunk->size != pool; chunk = next)
 137     {
 138       next = chunk->next;
 139       chunk->next = pool->unused;
 140       pool->unused = chunk;
 141     }
 142   pool->state.last[0] = chunk;
 143   pool->state.free[0] = chunk ? chunk->size - sizeof(*pool) : 0;
 144   pool->state.last[1] = NULL;
 145   pool->state.free[1] = 0;
 146   pool->state.next = NULL;
 147   pool->last_big = &pool->last_big;
 148 }
 149
 150 static void
 151 mp_stats_chain(struct mempool_chunk *chunk, struct mempool_stats *stats, uns idx)
 152 {
 153   while (chunk)
 154     {
 155       stats->chain_size[idx] += chunk->size + sizeof(*chunk);
 156       stats->chain_count[idx]++;
 157       chunk = chunk->next;
 158     }
 159   stats->total_size += stats->chain_size[idx];
 160 }
 161
 162 void
 163 mp_stats(struct mempool *pool, struct mempool_stats *stats)
 164 {
 165   bzero(stats, sizeof(*stats));
 166   mp_stats_chain(pool->state.last[0], stats, 0);
 167   mp_stats_chain(pool->state.last[1], stats, 1);
 168   mp_stats_chain(pool->unused, stats, 2);
 169 }
 170
 171 void *
 172 mp_alloc_internal(struct mempool *pool, uns size)
 173 {
 174   struct mempool_chunk *chunk;
 175   if (size <= pool->threshold)
 176     {
 177       pool->idx = 0;
 178       if (pool->unused)
 179         {
 180           chunk = pool->unused;
 181           pool->unused = chunk->next;
 182         }
 183       else
 184         chunk = mp_new_chunk(pool->chunk_size);
 185       chunk->next = pool->state.last[0];
 186       pool->state.last[0] = chunk;
 187       pool->state.free[0] = pool->chunk_size - size;
 188       return (void *)chunk - pool->chunk_size;
 189     }
 190   else if (likely(size <= MP_SIZE_MAX))
 191     {
 192       pool->idx = 1;
 193       uns aligned = ALIGN_TO(size, CPU_STRUCT_ALIGN);
 194       chunk = mp_new_big_chunk(aligned);
 195       chunk->next = pool->state.last[1];
 196       pool->state.last[1] = chunk;
 197       pool->state.free[1] = aligned - size;
 198       return pool->last_big = (void *)chunk - aligned;
 199     }
 200   else
 201     die("Cannot allocate %u bytes from a mempool", size);
 202 }
 203
 204 void *
 205 mp_alloc(struct mempool *pool, uns size)
 206 {
 207   return mp_alloc_fast(pool, size);
 208 }
 209
 210 void *
 211 mp_alloc_noalign(struct mempool *pool, uns size)
 212 {
 213   return mp_alloc_fast_noalign(pool, size);
 214 }
 215
 216 void *
 217 mp_alloc_zero(struct mempool *pool, uns size)
 218 {
 219   void *ptr = mp_alloc_fast(pool, size);
 220   bzero(ptr, size);
 221   return ptr;
 222 }
 223
 224 void *
 225 mp_start_internal(struct mempool *pool, uns size)
 226 {
 227   void *ptr = mp_alloc_internal(pool, size);
 228   pool->state.free[pool->idx] += size;
 229   return ptr;
 230 }
 231
 232 void *
 233 mp_start(struct mempool *pool, uns size)
 234 {
 235   return mp_start_fast(pool, size);
 236 }
 237
 238 void *
 239 mp_start_noalign(struct mempool *pool, uns size)
 240 {
 241   return mp_start_fast_noalign(pool, size);
 242 }
 243
 244 void *
 245 mp_grow_internal(struct mempool *pool, uns size)
 246 {
 247   if (unlikely(size > MP_SIZE_MAX))
 248     die("Cannot allocate %u bytes of memory", size);
 249   uns avail = mp_avail(pool);
 250   void *ptr = mp_ptr(pool);
 251   if (pool->idx)
 252     {
 253       uns amortized = likely(avail <= MP_SIZE_MAX / 2) ? avail * 2 : MP_SIZE_MAX;
 254       amortized = MAX(amortized, size);
 255       amortized = ALIGN_TO(amortized, CPU_STRUCT_ALIGN);
 256       struct mempool_chunk *chunk = pool->state.last[1], *next = chunk->next;
 257       ptr = xrealloc(ptr, amortized + MP_CHUNK_TAIL);
 258       chunk = ptr + amortized;
 259       chunk->next = next;
 260       chunk->size = amortized;
 261       pool->state.last[1] = chunk;
 262       pool->state.free[1] = amortized;
 263       pool->last_big = ptr;
 264       return ptr;
 265     }
 266   else
 267     {
 268       void *p = mp_start_internal(pool, size);
 269       memcpy(p, ptr, avail);
 270       return p;
 271     }
 272 }
 273
 274 uns
 275 mp_open(struct mempool *pool, void *ptr)
 276 {
 277   return mp_open_fast(pool, ptr);
 278 }
 279
 280 void *
 281 mp_realloc(struct mempool *pool, void *ptr, uns size)
 282 {
 283   return mp_realloc_fast(pool, ptr, size);
 284 }
 285
 286 void *
 287 mp_realloc_zero(struct mempool *pool, void *ptr, uns size)
 288 {
 289   uns old_size = mp_open_fast(pool, ptr);
 290   ptr = mp_grow(pool, size);
 291   if (size > old_size)
 292     bzero(ptr + old_size, size - old_size);
 293   mp_end(pool, ptr + size);
 294   return ptr;
 295 }
 296
 297 void *
 298 mp_spread_internal(struct mempool *pool, void *p, uns size)
 299 {
 300   void *old = mp_ptr(pool);
 301   void *new = mp_grow_internal(pool, p-old+size);
 302   return p-old+new;
 303 }
 304
 305 void
 306 mp_restore(struct mempool *pool, struct mempool_state *state)
 307 {
 308   struct mempool_chunk *chunk, *next;
 309   struct mempool_state s = *state;
 310   for (chunk = pool->state.last[0]; chunk != s.last[0]; chunk = next)
 311     {
 312       next = chunk->next;
 313       chunk->next = pool->unused;
 314       pool->unused = chunk;
 315     }
 316   for (chunk = pool->state.last[1]; chunk != s.last[1]; chunk = next)
 317     {
 318       next = chunk->next;
 319       mp_free_big_chunk(chunk);
 320     }
 321   pool->state = s;
 322   pool->last_big = &pool->last_big;
 323 }
 324
 325 struct mempool_state *
 326 mp_push(struct mempool *pool)
 327 {
 328   struct mempool_state state = pool->state;
 329   struct mempool_state *p = mp_alloc_fast(pool, sizeof(*p));
 330   *p = state;
 331   pool->state.next = p;
 332   return p;
 333 }
 334
 335 void
 336 mp_pop(struct mempool *pool)
 337 {
 338   ASSERT(pool->state.next);
 339   struct mempool_state state = pool->state;
 340   mp_restore(pool, &state);
 341 }
 342
 343 #ifdef TEST
 344
 345 #include "lib/getopt.h"
 346 #include <stdio.h>
 347 #include <stdlib.h>
 348 #include <time.h>
 349
 350 static void
 351 fill(byte *ptr, uns len, uns magic)
 352 {
 353   while (len--)
 354     *ptr++ = (magic++ & 255);
 355 }
 356
 357 static void
 358 check(byte *ptr, uns len, uns magic, uns align)
 359 {
 360   ASSERT(!((uintptr_t)ptr & (align - 1)));
 361   while (len--)
 362     if (*ptr++ != (magic++ & 255))
 363       ASSERT(0);
 364 }
 365
 366 int main(int argc, char **argv)
 367 {
 368   srand(time(NULL));
 369   log_init(argv[0]);
 370   cf_def_file = NULL;
 371   if (cf_getopt(argc, argv, CF_SHORT_OPTS, CF_NO_LONG_OPTS, NULL) >= 0 || argc != optind)
 372     die("Invalid usage");
 373
 374   uns max = 1000, n = 0, m = 0, can_realloc = 0;
 375   void *ptr[max];
 376   struct mempool_state *state[max];
 377   uns len[max], num[max], align[max];
 378   struct mempool *mp = mp_new(128), mp_static;
 379
 380   for (uns i = 0; i < 5000; i++)
 381     {
 382       for (uns j = 0; j < n; j++)
 383         check(ptr[j], len[j], j, align[j]);
 384 #if 0
 385       DBG("free_small=%u free_big=%u idx=%u chunk_size=%u last_big=%p", mp->state.free[0], mp->state.free[1], mp->idx, mp->chunk_size, mp->last_big);
 386       for (struct mempool_chunk *ch = mp->state.last[0]; ch; ch = ch->next)
 387         DBG("small %p %p %p %d", (byte *)ch - ch->size, ch, ch + 1, ch->size);
 388       for (struct mempool_chunk *ch = mp->state.last[1]; ch; ch = ch->next)
 389         DBG("big %p %p %p %d", (byte *)ch - ch->size, ch, ch + 1, ch->size);
 390 #endif
 391       int r = random_max(100);
 392       if ((r -= 1) < 0)
 393         {
 394           DBG("flush");
 395           mp_flush(mp);
 396           n = m = 0;
 397         }
 398       else if ((r -= 1) < 0)
 399         {
 400           DBG("delete & new");
 401           mp_delete(mp);
 402           if (random_max(2))
 403             mp = mp_new(random_max(0x1000) + 1);
 404           else
 405             mp = &mp_static, mp_init(mp, random_max(512) + 1);
 406           n = m = 0;
 407         }
 408       else if (n < max && (r -= 30) < 0)
 409         {
 410           len[n] = random_max(0x2000);
 411           DBG("alloc(%u)", len[n]);
 412           align[n] = random_max(2) ? CPU_STRUCT_ALIGN : 1;
 413           ptr[n] = (align[n] == 1) ? mp_alloc_fast_noalign(mp, len[n]) : mp_alloc_fast(mp, len[n]);
 414           DBG(" -> (%p)", ptr[n]);
 415           fill(ptr[n], len[n], n);
 416           n++;
 417           can_realloc = 1;
 418         }
 419       else if (n < max && (r -= 20) < 0)
 420         {
 421           len[n] = random_max(0x2000);
 422           DBG("start(%u)", len[n]);
 423           align[n] = random_max(2) ? CPU_STRUCT_ALIGN : 1;
 424           ptr[n] = (align[n] == 1) ? mp_start_fast_noalign(mp, len[n]) : mp_start_fast(mp, len[n]);
 425           DBG(" -> (%p)", ptr[n]);
 426           fill(ptr[n], len[n], n);
 427           n++;
 428           can_realloc = 1;
 429           goto grow;
 430         }
 431       else if (can_realloc && n && (r -= 10) < 0)
 432         {
 433           if (mp_open(mp, ptr[n - 1]) != len[n - 1])
 434             ASSERT(0);
 435 grow:
 436           {
 437             uns k = n - 1;
 438             for (uns i = random_max(4); i--; )
 439               {
 440                 uns l = len[k];
 441                 len[k] = random_max(0x2000);
 442                 DBG("grow(%u)", len[k]);
 443                 ptr[k] = mp_grow(mp, len[k]);
 444                 DBG(" -> (%p)", ptr[k]);
 445                 check(ptr[k], MIN(l, len[k]), k, align[k]);
 446                 fill(ptr[k], len[k], k);
 447               }
 448             mp_end(mp, ptr[k] + len[k]);
 449           }
 450         }
 451       else if (can_realloc && n && (r -= 20) < 0)
 452         {
 453           uns i = n - 1, l = len[i];
 454           DBG("realloc(%p, %u)", ptr[i], len[i]);
 455           ptr[i] = mp_realloc(mp, ptr[i], len[i] = random_max(0x2000));
 456           DBG(" -> (%p, %u)", ptr[i], len[i]);
 457           check(ptr[i],  MIN(len[i], l), i, align[i]);
 458           fill(ptr[i], len[i], i);
 459         }
 460       else if (m < max && (r -= 5) < 0)
 461         {
 462           DBG("push(%u)", m);
 463           num[m] = n;
 464           state[m++] = mp_push(mp);
 465           can_realloc = 0;
 466         }
 467       else if (m && (r -= 2) < 0)
 468         {
 469           m--;
 470           DBG("pop(%u)", m);
 471           mp_pop(mp);
 472           n = num[m];
 473           can_realloc = 0;
 474         }
 475       else if (m && (r -= 1) < 0)
 476         {
 477           uns i = random_max(m);
 478           DBG("restore(%u)", i);
 479           mp_restore(mp, state[i]);
 480           n = num[m = i];
 481           can_realloc = 0;
 482         }
 483       else if (can_realloc && n && (r -= 5) < 0)
 484         ASSERT(mp_size(mp, ptr[n - 1]) == len[n - 1]);
 485     }
 486
 487   mp_delete(mp);
 488   return 0;
 489 }
 490
 491 #endif