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 u64
 172 mp_total_size(struct mempool *pool)
 173 {
 174   struct mempool_stats stats;
 175   mp_stats(pool, &stats);
 176   return stats.total_size;
 177 }
 178
 179 void *
 180 mp_alloc_internal(struct mempool *pool, uns size)
 181 {
 182   struct mempool_chunk *chunk;
 183   if (size <= pool->threshold)
 184     {
 185       pool->idx = 0;
 186       if (pool->unused)
 187         {
 188           chunk = pool->unused;
 189           pool->unused = chunk->next;
 190         }
 191       else
 192         chunk = mp_new_chunk(pool->chunk_size);
 193       chunk->next = pool->state.last[0];
 194       pool->state.last[0] = chunk;
 195       pool->state.free[0] = pool->chunk_size - size;
 196       return (void *)chunk - pool->chunk_size;
 197     }
 198   else if (likely(size <= MP_SIZE_MAX))
 199     {
 200       pool->idx = 1;
 201       uns aligned = ALIGN_TO(size, CPU_STRUCT_ALIGN);
 202       chunk = mp_new_big_chunk(aligned);
 203       chunk->next = pool->state.last[1];
 204       pool->state.last[1] = chunk;
 205       pool->state.free[1] = aligned - size;
 206       return pool->last_big = (void *)chunk - aligned;
 207     }
 208   else
 209     die("Cannot allocate %u bytes from a mempool", size);
 210 }
 211
 212 void *
 213 mp_alloc(struct mempool *pool, uns size)
 214 {
 215   return mp_alloc_fast(pool, size);
 216 }
 217
 218 void *
 219 mp_alloc_noalign(struct mempool *pool, uns size)
 220 {
 221   return mp_alloc_fast_noalign(pool, size);
 222 }
 223
 224 void *
 225 mp_alloc_zero(struct mempool *pool, uns size)
 226 {
 227   void *ptr = mp_alloc_fast(pool, size);
 228   bzero(ptr, size);
 229   return ptr;
 230 }
 231
 232 void *
 233 mp_start_internal(struct mempool *pool, uns size)
 234 {
 235   void *ptr = mp_alloc_internal(pool, size);
 236   pool->state.free[pool->idx] += size;
 237   return ptr;
 238 }
 239
 240 void *
 241 mp_start(struct mempool *pool, uns size)
 242 {
 243   return mp_start_fast(pool, size);
 244 }
 245
 246 void *
 247 mp_start_noalign(struct mempool *pool, uns size)
 248 {
 249   return mp_start_fast_noalign(pool, size);
 250 }
 251
 252 void *
 253 mp_grow_internal(struct mempool *pool, uns size)
 254 {
 255   if (unlikely(size > MP_SIZE_MAX))
 256     die("Cannot allocate %u bytes of memory", size);
 257   uns avail = mp_avail(pool);
 258   void *ptr = mp_ptr(pool);
 259   if (pool->idx)
 260     {
 261       uns amortized = likely(avail <= MP_SIZE_MAX / 2) ? avail * 2 : MP_SIZE_MAX;
 262       amortized = MAX(amortized, size);
 263       amortized = ALIGN_TO(amortized, CPU_STRUCT_ALIGN);
 264       struct mempool_chunk *chunk = pool->state.last[1], *next = chunk->next;
 265       ptr = xrealloc(ptr, amortized + MP_CHUNK_TAIL);
 266       chunk = ptr + amortized;
 267       chunk->next = next;
 268       chunk->size = amortized;
 269       pool->state.last[1] = chunk;
 270       pool->state.free[1] = amortized;
 271       pool->last_big = ptr;
 272       return ptr;
 273     }
 274   else
 275     {
 276       void *p = mp_start_internal(pool, size);
 277       memcpy(p, ptr, avail);
 278       return p;
 279     }
 280 }
 281
 282 uns
 283 mp_open(struct mempool *pool, void *ptr)
 284 {
 285   return mp_open_fast(pool, ptr);
 286 }
 287
 288 void *
 289 mp_realloc(struct mempool *pool, void *ptr, uns size)
 290 {
 291   return mp_realloc_fast(pool, ptr, size);
 292 }
 293
 294 void *
 295 mp_realloc_zero(struct mempool *pool, void *ptr, uns size)
 296 {
 297   uns old_size = mp_open_fast(pool, ptr);
 298   ptr = mp_grow(pool, size);
 299   if (size > old_size)
 300     bzero(ptr + old_size, size - old_size);
 301   mp_end(pool, ptr + size);
 302   return ptr;
 303 }
 304
 305 void *
 306 mp_spread_internal(struct mempool *pool, void *p, uns size)
 307 {
 308   void *old = mp_ptr(pool);
 309   void *new = mp_grow_internal(pool, p-old+size);
 310   return p-old+new;
 311 }
 312
 313 void
 314 mp_restore(struct mempool *pool, struct mempool_state *state)
 315 {
 316   struct mempool_chunk *chunk, *next;
 317   struct mempool_state s = *state;
 318   for (chunk = pool->state.last[0]; chunk != s.last[0]; chunk = next)
 319     {
 320       next = chunk->next;
 321       chunk->next = pool->unused;
 322       pool->unused = chunk;
 323     }
 324   for (chunk = pool->state.last[1]; chunk != s.last[1]; chunk = next)
 325     {
 326       next = chunk->next;
 327       mp_free_big_chunk(chunk);
 328     }
 329   pool->state = s;
 330   pool->last_big = &pool->last_big;
 331 }
 332
 333 struct mempool_state *
 334 mp_push(struct mempool *pool)
 335 {
 336   struct mempool_state state = pool->state;
 337   struct mempool_state *p = mp_alloc_fast(pool, sizeof(*p));
 338   *p = state;
 339   pool->state.next = p;
 340   return p;
 341 }
 342
 343 void
 344 mp_pop(struct mempool *pool)
 345 {
 346   ASSERT(pool->state.next);
 347   struct mempool_state state = pool->state;
 348   mp_restore(pool, &state);
 349 }
 350
 351 #ifdef TEST
 352
 353 #include "lib/getopt.h"
 354 #include <stdio.h>
 355 #include <stdlib.h>
 356 #include <time.h>
 357
 358 static void
 359 fill(byte *ptr, uns len, uns magic)
 360 {
 361   while (len--)
 362     *ptr++ = (magic++ & 255);
 363 }
 364
 365 static void
 366 check(byte *ptr, uns len, uns magic, uns align)
 367 {
 368   ASSERT(!((uintptr_t)ptr & (align - 1)));
 369   while (len--)
 370     if (*ptr++ != (magic++ & 255))
 371       ASSERT(0);
 372 }
 373
 374 int main(int argc, char **argv)
 375 {
 376   srand(time(NULL));
 377   log_init(argv[0]);
 378   cf_def_file = NULL;
 379   if (cf_getopt(argc, argv, CF_SHORT_OPTS, CF_NO_LONG_OPTS, NULL) >= 0 || argc != optind)
 380     die("Invalid usage");
 381
 382   uns max = 1000, n = 0, m = 0, can_realloc = 0;
 383   void *ptr[max];
 384   struct mempool_state *state[max];
 385   uns len[max], num[max], align[max];
 386   struct mempool *mp = mp_new(128), mp_static;
 387
 388   for (uns i = 0; i < 5000; i++)
 389     {
 390       for (uns j = 0; j < n; j++)
 391         check(ptr[j], len[j], j, align[j]);
 392 #if 0
 393       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);
 394       for (struct mempool_chunk *ch = mp->state.last[0]; ch; ch = ch->next)
 395         DBG("small %p %p %p %d", (byte *)ch - ch->size, ch, ch + 1, ch->size);
 396       for (struct mempool_chunk *ch = mp->state.last[1]; ch; ch = ch->next)
 397         DBG("big %p %p %p %d", (byte *)ch - ch->size, ch, ch + 1, ch->size);
 398 #endif
 399       int r = random_max(100);
 400       if ((r -= 1) < 0)
 401         {
 402           DBG("flush");
 403           mp_flush(mp);
 404           n = m = 0;
 405         }
 406       else if ((r -= 1) < 0)
 407         {
 408           DBG("delete & new");
 409           mp_delete(mp);
 410           if (random_max(2))
 411             mp = mp_new(random_max(0x1000) + 1);
 412           else
 413             mp = &mp_static, mp_init(mp, random_max(512) + 1);
 414           n = m = 0;
 415         }
 416       else if (n < max && (r -= 30) < 0)
 417         {
 418           len[n] = random_max(0x2000);
 419           DBG("alloc(%u)", len[n]);
 420           align[n] = random_max(2) ? CPU_STRUCT_ALIGN : 1;
 421           ptr[n] = (align[n] == 1) ? mp_alloc_fast_noalign(mp, len[n]) : mp_alloc_fast(mp, len[n]);
 422           DBG(" -> (%p)", ptr[n]);
 423           fill(ptr[n], len[n], n);
 424           n++;
 425           can_realloc = 1;
 426         }
 427       else if (n < max && (r -= 20) < 0)
 428         {
 429           len[n] = random_max(0x2000);
 430           DBG("start(%u)", len[n]);
 431           align[n] = random_max(2) ? CPU_STRUCT_ALIGN : 1;
 432           ptr[n] = (align[n] == 1) ? mp_start_fast_noalign(mp, len[n]) : mp_start_fast(mp, len[n]);
 433           DBG(" -> (%p)", ptr[n]);
 434           fill(ptr[n], len[n], n);
 435           n++;
 436           can_realloc = 1;
 437           goto grow;
 438         }
 439       else if (can_realloc && n && (r -= 10) < 0)
 440         {
 441           if (mp_open(mp, ptr[n - 1]) != len[n - 1])
 442             ASSERT(0);
 443 grow:
 444           {
 445             uns k = n - 1;
 446             for (uns i = random_max(4); i--; )
 447               {
 448                 uns l = len[k];
 449                 len[k] = random_max(0x2000);
 450                 DBG("grow(%u)", len[k]);
 451                 ptr[k] = mp_grow(mp, len[k]);
 452                 DBG(" -> (%p)", ptr[k]);
 453                 check(ptr[k], MIN(l, len[k]), k, align[k]);
 454                 fill(ptr[k], len[k], k);
 455               }
 456             mp_end(mp, ptr[k] + len[k]);
 457           }
 458         }
 459       else if (can_realloc && n && (r -= 20) < 0)
 460         {
 461           uns i = n - 1, l = len[i];
 462           DBG("realloc(%p, %u)", ptr[i], len[i]);
 463           ptr[i] = mp_realloc(mp, ptr[i], len[i] = random_max(0x2000));
 464           DBG(" -> (%p, %u)", ptr[i], len[i]);
 465           check(ptr[i],  MIN(len[i], l), i, align[i]);
 466           fill(ptr[i], len[i], i);
 467         }
 468       else if (m < max && (r -= 5) < 0)
 469         {
 470           DBG("push(%u)", m);
 471           num[m] = n;
 472           state[m++] = mp_push(mp);
 473           can_realloc = 0;
 474         }
 475       else if (m && (r -= 2) < 0)
 476         {
 477           m--;
 478           DBG("pop(%u)", m);
 479           mp_pop(mp);
 480           n = num[m];
 481           can_realloc = 0;
 482         }
 483       else if (m && (r -= 1) < 0)
 484         {
 485           uns i = random_max(m);
 486           DBG("restore(%u)", i);
 487           mp_restore(mp, state[i]);
 488           n = num[m = i];
 489           can_realloc = 0;
 490         }
 491       else if (can_realloc && n && (r -= 5) < 0)
 492         ASSERT(mp_size(mp, ptr[n - 1]) == len[n - 1]);
 493     }
 494
 495   mp_delete(mp);
 496   return 0;
 497 }
 498
 499 #endif