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