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