2 * UCW Library -- Memory Pools (One-Time Allocation)
4 * (c) 1997--2014 Martin Mares <mj@ucw.cz>
5 * (c) 2007--2014 Pavel Charvat <pchar@ucw.cz>
7 * This software may be freely distributed and used according to the terms
8 * of the GNU Lesser General Public License.
14 #include <ucw/alloc.h>
15 #include <ucw/mempool.h>
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)
22 struct mempool_chunk {
24 struct mempool *pool; // Can be useful when analysing coredump for memory leaks
26 struct mempool_chunk *next;
31 mp_align_size(uns size)
33 #ifdef CONFIG_UCW_POOL_IS_MMAP
34 return ALIGN_TO(size + MP_CHUNK_TAIL, CPU_PAGE_SIZE) - MP_CHUNK_TAIL;
36 return ALIGN_TO(size, CPU_STRUCT_ALIGN);
40 static void *mp_allocator_alloc(struct ucw_allocator *a, size_t size)
42 struct mempool *mp = (struct mempool *) a;
43 return mp_alloc_fast(mp, size);
46 static void *mp_allocator_realloc(struct ucw_allocator *a, void *ptr, size_t old_size, size_t new_size)
48 if (new_size <= old_size)
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.
55 struct mempool *mp = (struct mempool *) a;
56 void *new = mp_alloc_fast(mp, new_size);
57 memcpy(new, ptr, old_size);
61 static void mp_allocator_free(struct ucw_allocator *a UNUSED, void *ptr UNUSED)
67 mp_init(struct mempool *pool, uns chunk_size)
69 chunk_size = mp_align_size(MAX(sizeof(struct mempool), chunk_size));
70 *pool = (struct mempool) {
72 .alloc = mp_allocator_alloc,
73 .realloc = mp_allocator_realloc,
74 .free = mp_allocator_free,
76 .chunk_size = chunk_size,
77 .threshold = chunk_size >> 1,
78 .last_big = &pool->last_big
83 mp_new_big_chunk(struct mempool *pool, uns size)
85 struct mempool_chunk *chunk;
86 chunk = xmalloc(size + MP_CHUNK_TAIL) + size;
89 pool->total_size += size + MP_CHUNK_TAIL;
94 mp_free_big_chunk(struct mempool *pool, struct mempool_chunk *chunk)
96 pool->total_size -= chunk->size + MP_CHUNK_TAIL;
97 xfree((void *)chunk - chunk->size);
101 mp_new_chunk(struct mempool *pool, uns size)
103 #ifdef CONFIG_UCW_POOL_IS_MMAP
104 struct mempool_chunk *chunk;
105 chunk = page_alloc(size + MP_CHUNK_TAIL) + size;
108 pool->total_size += size + MP_CHUNK_TAIL;
111 return mp_new_big_chunk(pool, size);
116 mp_free_chunk(struct mempool *pool, struct mempool_chunk *chunk)
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);
122 mp_free_big_chunk(pool, chunk);
127 mp_new(uns chunk_size)
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);
137 *pool = (struct mempool) {
139 .alloc = mp_allocator_alloc,
140 .realloc = mp_allocator_realloc,
141 .free = mp_allocator_free,
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,
153 mp_free_chain(struct mempool *pool, struct mempool_chunk *chunk)
157 struct mempool_chunk *next = chunk->next;
158 mp_free_chunk(pool, chunk);
164 mp_free_big_chain(struct mempool *pool, struct mempool_chunk *chunk)
168 struct mempool_chunk *next = chunk->next;
169 mp_free_big_chunk(pool, chunk);
175 mp_delete(struct mempool *pool)
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
184 mp_flush(struct mempool *pool)
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)
191 chunk->next = pool->unused;
192 pool->unused = chunk;
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;
203 mp_stats_chain(struct mempool_chunk *chunk, struct mempool_stats *stats, uns idx)
207 stats->chain_size[idx] += chunk->size + MP_CHUNK_TAIL;
208 stats->chain_count[idx]++;
211 stats->total_size += stats->chain_size[idx];
215 mp_stats(struct mempool *pool, struct mempool_stats *stats)
217 bzero(stats, sizeof(*stats));
218 mp_stats_chain(pool->state.last[0], stats, 0);
219 mp_stats_chain(pool->state.last[1], stats, 1);
220 mp_stats_chain(pool->unused, stats, 2);
221 ASSERT(stats->total_size == pool->total_size);
222 stats->used_size = stats->chain_size[0] + stats->chain_size[1]
223 - MP_CHUNK_TAIL * (stats->chain_count[0] + stats->chain_count[1])
224 - pool->state.free[0] - pool->state.free[1];
228 mp_total_size(struct mempool *pool)
230 return pool->total_size;
234 mp_shrink(struct mempool *pool, u64 min_total_size)
238 struct mempool_chunk *chunk = pool->unused;
239 if (!chunk || pool->total_size - (chunk->size + MP_CHUNK_TAIL) < min_total_size)
241 pool->unused = chunk->next;
242 mp_free_chunk(pool, chunk);
247 mp_alloc_internal(struct mempool *pool, uns size)
249 struct mempool_chunk *chunk;
250 if (size <= pool->threshold)
255 chunk = pool->unused;
256 pool->unused = chunk->next;
260 chunk = mp_new_chunk(pool, pool->chunk_size);
265 chunk->next = pool->state.last[0];
266 pool->state.last[0] = chunk;
267 pool->state.free[0] = pool->chunk_size - size;
268 return (void *)chunk - pool->chunk_size;
270 else if (likely(size <= MP_SIZE_MAX))
273 uns aligned = ALIGN_TO(size, CPU_STRUCT_ALIGN);
274 chunk = mp_new_big_chunk(pool, aligned);
275 chunk->next = pool->state.last[1];
279 pool->state.last[1] = chunk;
280 pool->state.free[1] = aligned - size;
281 return pool->last_big = (void *)chunk - aligned;
284 die("Cannot allocate %u bytes from a mempool", size);
288 mp_alloc(struct mempool *pool, uns size)
290 return mp_alloc_fast(pool, size);
294 mp_alloc_noalign(struct mempool *pool, uns size)
296 return mp_alloc_fast_noalign(pool, size);
300 mp_alloc_zero(struct mempool *pool, uns size)
302 void *ptr = mp_alloc_fast(pool, size);
308 mp_start_internal(struct mempool *pool, uns size)
310 void *ptr = mp_alloc_internal(pool, size);
311 pool->state.free[pool->idx] += size;
316 mp_start(struct mempool *pool, uns size)
318 return mp_start_fast(pool, size);
322 mp_start_noalign(struct mempool *pool, uns size)
324 return mp_start_fast_noalign(pool, size);
328 mp_grow_internal(struct mempool *pool, uns size)
330 if (unlikely(size > MP_SIZE_MAX))
331 die("Cannot allocate %u bytes of memory", size);
332 uns avail = mp_avail(pool);
333 void *ptr = mp_ptr(pool);
336 uns amortized = likely(avail <= MP_SIZE_MAX / 2) ? avail * 2 : MP_SIZE_MAX;
337 amortized = MAX(amortized, size);
338 amortized = ALIGN_TO(amortized, CPU_STRUCT_ALIGN);
339 struct mempool_chunk *chunk = pool->state.last[1], *next = chunk->next;
340 pool->total_size = pool->total_size - chunk->size + amortized;
341 ptr = xrealloc(ptr, amortized + MP_CHUNK_TAIL);
342 chunk = ptr + amortized;
344 chunk->size = amortized;
345 pool->state.last[1] = chunk;
346 pool->state.free[1] = amortized;
347 pool->last_big = ptr;
352 void *p = mp_start_internal(pool, size);
353 memcpy(p, ptr, avail);
359 mp_open(struct mempool *pool, void *ptr)
361 return mp_open_fast(pool, ptr);
365 mp_realloc(struct mempool *pool, void *ptr, uns size)
367 return mp_realloc_fast(pool, ptr, size);
371 mp_realloc_zero(struct mempool *pool, void *ptr, uns size)
373 uns old_size = mp_open_fast(pool, ptr);
374 ptr = mp_grow(pool, size);
376 bzero(ptr + old_size, size - old_size);
377 mp_end(pool, ptr + size);
382 mp_spread_internal(struct mempool *pool, void *p, uns size)
384 void *old = mp_ptr(pool);
385 void *new = mp_grow_internal(pool, p-old+size);
390 mp_restore(struct mempool *pool, struct mempool_state *state)
392 struct mempool_chunk *chunk, *next;
393 struct mempool_state s = *state;
394 for (chunk = pool->state.last[0]; chunk != s.last[0]; chunk = next)
397 chunk->next = pool->unused;
398 pool->unused = chunk;
400 for (chunk = pool->state.last[1]; chunk != s.last[1]; chunk = next)
403 mp_free_big_chunk(pool, chunk);
406 pool->last_big = &pool->last_big;
409 struct mempool_state *
410 mp_push(struct mempool *pool)
412 struct mempool_state state = pool->state;
413 struct mempool_state *p = mp_alloc_fast(pool, sizeof(*p));
415 pool->state.next = p;
420 mp_pop(struct mempool *pool)
422 ASSERT(pool->state.next);
423 mp_restore(pool, pool->state.next);
428 #include <ucw/getopt.h>
434 fill(byte *ptr, uns len, uns magic)
437 *ptr++ = (magic++ & 255);
441 check(byte *ptr, uns len, uns magic, uns align)
443 ASSERT(!((uintptr_t)ptr & (align - 1)));
445 if (*ptr++ != (magic++ & 255))
449 int main(int argc, char **argv)
454 if (cf_getopt(argc, argv, CF_SHORT_OPTS, CF_NO_LONG_OPTS, NULL) >= 0 || argc != optind)
455 die("Invalid usage");
457 uns max = 1000, n = 0, m = 0, can_realloc = 0;
459 struct mempool_state *state[max];
460 uns len[max], num[max], align[max];
461 struct mempool *mp = mp_new(128), mp_static;
463 for (uns i = 0; i < 5000; i++)
465 for (uns j = 0; j < n; j++)
466 check(ptr[j], len[j], j, align[j]);
468 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);
469 for (struct mempool_chunk *ch = mp->state.last[0]; ch; ch = ch->next)
470 DBG("small %p %p %p %d", (byte *)ch - ch->size, ch, ch + 1, ch->size);
471 for (struct mempool_chunk *ch = mp->state.last[1]; ch; ch = ch->next)
472 DBG("big %p %p %p %d", (byte *)ch - ch->size, ch, ch + 1, ch->size);
474 int r = random_max(100);
481 else if ((r -= 1) < 0)
486 mp = mp_new(random_max(0x1000) + 1);
488 mp = &mp_static, mp_init(mp, random_max(512) + 1);
491 else if (n < max && (r -= 30) < 0)
493 len[n] = random_max(0x2000);
494 DBG("alloc(%u)", len[n]);
495 align[n] = random_max(2) ? CPU_STRUCT_ALIGN : 1;
496 ptr[n] = (align[n] == 1) ? mp_alloc_fast_noalign(mp, len[n]) : mp_alloc_fast(mp, len[n]);
497 DBG(" -> (%p)", ptr[n]);
498 fill(ptr[n], len[n], n);
502 else if (n < max && (r -= 20) < 0)
504 len[n] = random_max(0x2000);
505 DBG("start(%u)", len[n]);
506 align[n] = random_max(2) ? CPU_STRUCT_ALIGN : 1;
507 ptr[n] = (align[n] == 1) ? mp_start_fast_noalign(mp, len[n]) : mp_start_fast(mp, len[n]);
508 DBG(" -> (%p)", ptr[n]);
509 fill(ptr[n], len[n], n);
514 else if (can_realloc && n && (r -= 10) < 0)
516 if (mp_open(mp, ptr[n - 1]) != len[n - 1])
521 for (uns i = random_max(4); i--; )
524 len[k] = random_max(0x2000);
525 DBG("grow(%u)", len[k]);
526 ptr[k] = mp_grow(mp, len[k]);
527 DBG(" -> (%p)", ptr[k]);
528 check(ptr[k], MIN(l, len[k]), k, align[k]);
529 fill(ptr[k], len[k], k);
531 mp_end(mp, ptr[k] + len[k]);
534 else if (can_realloc && n && (r -= 20) < 0)
536 uns i = n - 1, l = len[i];
537 DBG("realloc(%p, %u)", ptr[i], len[i]);
538 ptr[i] = mp_realloc(mp, ptr[i], len[i] = random_max(0x2000));
539 DBG(" -> (%p, %u)", ptr[i], len[i]);
540 check(ptr[i], MIN(len[i], l), i, align[i]);
541 fill(ptr[i], len[i], i);
543 else if (m < max && (r -= 5) < 0)
547 state[m++] = mp_push(mp);
550 else if (m && (r -= 2) < 0)
558 else if (m && (r -= 1) < 0)
560 uns i = random_max(m);
561 DBG("restore(%u)", i);
562 mp_restore(mp, state[i]);
566 else if (can_realloc && n && (r -= 5) < 0)
567 ASSERT(mp_size(mp, ptr[n - 1]) == len[n - 1]);
570 struct mempool_stats stats;
571 mp_stats(mp, &stats);