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