ucw/mempool.c

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