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