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_restore(struct mempool *pool, struct mempool_state *state)
 299 {
 300   struct mempool_chunk *chunk, *next;
 301   struct mempool_state s = *state;
 302   for (chunk = pool->state.last[0]; chunk != s.last[0]; chunk = next)
 303     {
 304       next = chunk->next;
 305       chunk->next = pool->unused;
 306       pool->unused = chunk;
 307     }
 308   for (chunk = pool->state.last[1]; chunk != s.last[1]; chunk = next)
 309     {
 310       next = chunk->next;
 311       mp_free_big_chunk(chunk);
 312     }
 313   pool->state = s;
 314   pool->last_big = &pool->last_big;
 315 }
 316
 317 struct mempool_state *
 318 mp_push(struct mempool *pool)
 319 {
 320   struct mempool_state state = pool->state;
 321   struct mempool_state *p = mp_alloc_fast(pool, sizeof(*p));
 322   *p = state;
 323   pool->state.next = p;
 324   return p;
 325 }
 326
 327 void
 328 mp_pop(struct mempool *pool)
 329 {
 330   ASSERT(pool->state.next);
 331   struct mempool_state state = pool->state;
 332   mp_restore(pool, &state);
 333 }
 334
 335 #ifdef TEST
 336
 337 #include "lib/getopt.h"
 338 #include <stdio.h>
 339 #include <stdlib.h>
 340 #include <time.h>
 341
 342 static void
 343 fill(byte *ptr, uns len, uns magic)
 344 {
 345   while (len--)
 346     *ptr++ = (magic++ & 255);
 347 }
 348
 349 static void
 350 check(byte *ptr, uns len, uns magic, uns align)
 351 {
 352   ASSERT(!((uintptr_t)ptr & (align - 1)));
 353   while (len--)
 354     if (*ptr++ != (magic++ & 255))
 355       ASSERT(0);
 356 }
 357
 358 int main(int argc, char **argv)
 359 {
 360   srand(time(NULL));
 361   log_init(argv[0]);
 362   cf_def_file = NULL;
 363   if (cf_getopt(argc, argv, CF_SHORT_OPTS, CF_NO_LONG_OPTS, NULL) >= 0 || argc != optind)
 364     die("Invalid usage");
 365
 366   uns max = 1000, n = 0, m = 0, can_realloc = 0;
 367   void *ptr[max];
 368   struct mempool_state *state[max];
 369   uns len[max], num[max], align[max];
 370   struct mempool *mp = mp_new(128), mp_static;
 371
 372   for (uns i = 0; i < 5000; i++)
 373     {
 374       for (uns j = 0; j < n; j++)
 375         check(ptr[j], len[j], j, align[j]);
 376 #if 0
 377       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);
 378       for (struct mempool_chunk *ch = mp->state.last[0]; ch; ch = ch->next)
 379         DBG("small %p %p %p %d", (byte *)ch - ch->size, ch, ch + 1, ch->size);
 380       for (struct mempool_chunk *ch = mp->state.last[1]; ch; ch = ch->next)
 381         DBG("big %p %p %p %d", (byte *)ch - ch->size, ch, ch + 1, ch->size);
 382 #endif
 383       int r = random_max(100);
 384       if ((r -= 1) < 0)
 385         {
 386           DBG("flush");
 387           mp_flush(mp);
 388           n = m = 0;
 389         }
 390       else if ((r -= 1) < 0)
 391         {
 392           DBG("delete & new");
 393           mp_delete(mp);
 394           if (random_max(2))
 395             mp = mp_new(random_max(0x1000) + 1);
 396           else
 397             mp = &mp_static, mp_init(mp, random_max(512) + 1);
 398           n = m = 0;
 399         }
 400       else if (n < max && (r -= 30) < 0)
 401         {
 402           len[n] = random_max(0x2000);
 403           DBG("alloc(%u)", len[n]);
 404           align[n] = random_max(2) ? CPU_STRUCT_ALIGN : 1;
 405           ptr[n] = (align[n] == 1) ? mp_alloc_fast_noalign(mp, len[n]) : mp_alloc_fast(mp, len[n]);
 406           DBG(" -> (%p)", ptr[n]);
 407           fill(ptr[n], len[n], n);
 408           n++;
 409           can_realloc = 1;
 410         }
 411       else if (n < max && (r -= 20) < 0)
 412         {
 413           len[n] = random_max(0x2000);
 414           DBG("start(%u)", len[n]);
 415           align[n] = random_max(2) ? CPU_STRUCT_ALIGN : 1;
 416           ptr[n] = (align[n] == 1) ? mp_start_fast_noalign(mp, len[n]) : mp_start_fast(mp, len[n]);
 417           DBG(" -> (%p)", ptr[n]);
 418           fill(ptr[n], len[n], n);
 419           n++;
 420           can_realloc = 1;
 421           goto grow;
 422         }
 423       else if (can_realloc && n && (r -= 10) < 0)
 424         {
 425           if (mp_open(mp, ptr[n - 1]) != len[n - 1])
 426             ASSERT(0);
 427 grow:
 428           {
 429             uns k = n - 1;
 430             for (uns i = random_max(4); i--; )
 431               {
 432                 uns l = len[k];
 433                 len[k] = random_max(0x2000);
 434                 DBG("grow(%u)", len[k]);
 435                 ptr[k] = mp_grow(mp, len[k]);
 436                 DBG(" -> (%p)", ptr[k]);
 437                 check(ptr[k], MIN(l, len[k]), k, align[k]);
 438                 fill(ptr[k], len[k], k);
 439               }
 440             mp_end(mp, ptr[k] + len[k]);
 441           }
 442         }
 443       else if (can_realloc && n && (r -= 20) < 0)
 444         {
 445           uns i = n - 1, l = len[i];
 446           DBG("realloc(%p, %u)", ptr[i], len[i]);
 447           ptr[i] = mp_realloc(mp, ptr[i], len[i] = random_max(0x2000));
 448           DBG(" -> (%p, %u)", ptr[i], len[i]);
 449           check(ptr[i],  MIN(len[i], l), i, align[i]);
 450           fill(ptr[i], len[i], i);
 451         }
 452       else if (m < max && (r -= 5) < 0)
 453         {
 454           DBG("push(%u)", m);
 455           num[m] = n;
 456           state[m++] = mp_push(mp);
 457           can_realloc = 0;
 458         }
 459       else if (m && (r -= 2) < 0)
 460         {
 461           m--;
 462           DBG("pop(%u)", m);
 463           mp_pop(mp);
 464           n = num[m];
 465           can_realloc = 0;
 466         }
 467       else if (m && (r -= 1) < 0)
 468         {
 469           uns i = random_max(m);
 470           DBG("restore(%u)", i);
 471           mp_restore(mp, state[i]);
 472           n = num[m = i];
 473           can_realloc = 0;
 474         }
 475       else if (can_realloc && n && (r -= 5) < 0)
 476         ASSERT(mp_size(mp, ptr[n - 1]) == len[n - 1]);
 477     }
 478
 479   mp_delete(mp);
 480   return 0;
 481 }
 482
 483 #endif