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