]> mj.ucw.cz Git - libucw.git/blob - ucw/mempool.c
make Sherlock compilable on Darwin without hacks due to missing direct IO
[libucw.git] / ucw / 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 "ucw/lib.h"
14 #include "ucw/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 CONFIG_UCW_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 CONFIG_UCW_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 CONFIG_UCW_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 u64
172 mp_total_size(struct mempool *pool)
173 {
174   struct mempool_stats stats;
175   mp_stats(pool, &stats);
176   return stats.total_size;
177 }
178
179 void *
180 mp_alloc_internal(struct mempool *pool, uns size)
181 {
182   struct mempool_chunk *chunk;
183   if (size <= pool->threshold)
184     {
185       pool->idx = 0;
186       if (pool->unused)
187         {
188           chunk = pool->unused;
189           pool->unused = chunk->next;
190         }
191       else
192         chunk = mp_new_chunk(pool->chunk_size);
193       chunk->next = pool->state.last[0];
194       pool->state.last[0] = chunk;
195       pool->state.free[0] = pool->chunk_size - size;
196       return (void *)chunk - pool->chunk_size;
197     }
198   else if (likely(size <= MP_SIZE_MAX))
199     {
200       pool->idx = 1;
201       uns aligned = ALIGN_TO(size, CPU_STRUCT_ALIGN);
202       chunk = mp_new_big_chunk(aligned);
203       chunk->next = pool->state.last[1];
204       pool->state.last[1] = chunk;
205       pool->state.free[1] = aligned - size;
206       return pool->last_big = (void *)chunk - aligned;
207     }
208   else
209     die("Cannot allocate %u bytes from a mempool", size);
210 }
211
212 void *
213 mp_alloc(struct mempool *pool, uns size)
214 {
215   return mp_alloc_fast(pool, size);
216 }
217
218 void *
219 mp_alloc_noalign(struct mempool *pool, uns size)
220 {
221   return mp_alloc_fast_noalign(pool, size);
222 }
223
224 void *
225 mp_alloc_zero(struct mempool *pool, uns size)
226 {
227   void *ptr = mp_alloc_fast(pool, size);
228   bzero(ptr, size);
229   return ptr;
230 }
231
232 void *
233 mp_start_internal(struct mempool *pool, uns size)
234 {
235   void *ptr = mp_alloc_internal(pool, size);
236   pool->state.free[pool->idx] += size;
237   return ptr;
238 }
239
240 void *
241 mp_start(struct mempool *pool, uns size)
242 {
243   return mp_start_fast(pool, size);
244 }
245
246 void *
247 mp_start_noalign(struct mempool *pool, uns size)
248 {
249   return mp_start_fast_noalign(pool, size);
250 }
251
252 void *
253 mp_grow_internal(struct mempool *pool, uns size)
254 {
255   if (unlikely(size > MP_SIZE_MAX))
256     die("Cannot allocate %u bytes of memory", size);
257   uns avail = mp_avail(pool);
258   void *ptr = mp_ptr(pool);
259   if (pool->idx)
260     {
261       uns amortized = likely(avail <= MP_SIZE_MAX / 2) ? avail * 2 : MP_SIZE_MAX;
262       amortized = MAX(amortized, size);
263       amortized = ALIGN_TO(amortized, CPU_STRUCT_ALIGN);
264       struct mempool_chunk *chunk = pool->state.last[1], *next = chunk->next;
265       ptr = xrealloc(ptr, amortized + MP_CHUNK_TAIL);
266       chunk = ptr + amortized;
267       chunk->next = next;
268       chunk->size = amortized;
269       pool->state.last[1] = chunk;
270       pool->state.free[1] = amortized;
271       pool->last_big = ptr;
272       return ptr;
273     }
274   else
275     {
276       void *p = mp_start_internal(pool, size);
277       memcpy(p, ptr, avail);
278       return p;
279     }
280 }
281
282 uns
283 mp_open(struct mempool *pool, void *ptr)
284 {
285   return mp_open_fast(pool, ptr);
286 }
287
288 void *
289 mp_realloc(struct mempool *pool, void *ptr, uns size)
290 {
291   return mp_realloc_fast(pool, ptr, size);
292 }
293
294 void *
295 mp_realloc_zero(struct mempool *pool, void *ptr, uns size)
296 {
297   uns old_size = mp_open_fast(pool, ptr);
298   ptr = mp_grow(pool, size);
299   if (size > old_size)
300     bzero(ptr + old_size, size - old_size);
301   mp_end(pool, ptr + size);
302   return ptr;
303 }
304
305 void *
306 mp_spread_internal(struct mempool *pool, void *p, uns size)
307 {
308   void *old = mp_ptr(pool);
309   void *new = mp_grow_internal(pool, p-old+size);
310   return p-old+new;
311 }
312
313 void
314 mp_restore(struct mempool *pool, struct mempool_state *state)
315 {
316   struct mempool_chunk *chunk, *next;
317   struct mempool_state s = *state;
318   for (chunk = pool->state.last[0]; chunk != s.last[0]; chunk = next)
319     {
320       next = chunk->next;
321       chunk->next = pool->unused;
322       pool->unused = chunk;
323     }
324   for (chunk = pool->state.last[1]; chunk != s.last[1]; chunk = next)
325     {
326       next = chunk->next;
327       mp_free_big_chunk(chunk);
328     }
329   pool->state = s;
330   pool->last_big = &pool->last_big;
331 }
332
333 struct mempool_state *
334 mp_push(struct mempool *pool)
335 {
336   struct mempool_state state = pool->state;
337   struct mempool_state *p = mp_alloc_fast(pool, sizeof(*p));
338   *p = state;
339   pool->state.next = p;
340   return p;
341 }
342
343 void
344 mp_pop(struct mempool *pool)
345 {
346   ASSERT(pool->state.next);
347   struct mempool_state state = pool->state;
348   mp_restore(pool, &state);
349 }
350
351 #ifdef TEST
352
353 #include "ucw/getopt.h"
354 #include <stdio.h>
355 #include <stdlib.h>
356 #include <time.h>
357
358 static void
359 fill(byte *ptr, uns len, uns magic)
360 {
361   while (len--)
362     *ptr++ = (magic++ & 255);
363 }
364
365 static void
366 check(byte *ptr, uns len, uns magic, uns align)
367 {
368   ASSERT(!((uintptr_t)ptr & (align - 1)));
369   while (len--)
370     if (*ptr++ != (magic++ & 255))
371       ASSERT(0);
372 }
373
374 int main(int argc, char **argv)
375 {
376   srand(time(NULL));
377   log_init(argv[0]);
378   cf_def_file = NULL;
379   if (cf_getopt(argc, argv, CF_SHORT_OPTS, CF_NO_LONG_OPTS, NULL) >= 0 || argc != optind)
380     die("Invalid usage");
381
382   uns max = 1000, n = 0, m = 0, can_realloc = 0;
383   void *ptr[max];
384   struct mempool_state *state[max];
385   uns len[max], num[max], align[max];
386   struct mempool *mp = mp_new(128), mp_static;
387
388   for (uns i = 0; i < 5000; i++)
389     {
390       for (uns j = 0; j < n; j++)
391         check(ptr[j], len[j], j, align[j]);
392 #if 0
393       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);
394       for (struct mempool_chunk *ch = mp->state.last[0]; ch; ch = ch->next)
395         DBG("small %p %p %p %d", (byte *)ch - ch->size, ch, ch + 1, ch->size);
396       for (struct mempool_chunk *ch = mp->state.last[1]; ch; ch = ch->next)
397         DBG("big %p %p %p %d", (byte *)ch - ch->size, ch, ch + 1, ch->size);
398 #endif
399       int r = random_max(100);
400       if ((r -= 1) < 0)
401         {
402           DBG("flush");
403           mp_flush(mp);
404           n = m = 0;
405         }
406       else if ((r -= 1) < 0)
407         {
408           DBG("delete & new");
409           mp_delete(mp);
410           if (random_max(2))
411             mp = mp_new(random_max(0x1000) + 1);
412           else
413             mp = &mp_static, mp_init(mp, random_max(512) + 1);
414           n = m = 0;
415         }
416       else if (n < max && (r -= 30) < 0)
417         {
418           len[n] = random_max(0x2000);
419           DBG("alloc(%u)", len[n]);
420           align[n] = random_max(2) ? CPU_STRUCT_ALIGN : 1;
421           ptr[n] = (align[n] == 1) ? mp_alloc_fast_noalign(mp, len[n]) : mp_alloc_fast(mp, len[n]);
422           DBG(" -> (%p)", ptr[n]);
423           fill(ptr[n], len[n], n);
424           n++;
425           can_realloc = 1;
426         }
427       else if (n < max && (r -= 20) < 0)
428         {
429           len[n] = random_max(0x2000);
430           DBG("start(%u)", len[n]);
431           align[n] = random_max(2) ? CPU_STRUCT_ALIGN : 1;
432           ptr[n] = (align[n] == 1) ? mp_start_fast_noalign(mp, len[n]) : mp_start_fast(mp, len[n]);
433           DBG(" -> (%p)", ptr[n]);
434           fill(ptr[n], len[n], n);
435           n++;
436           can_realloc = 1;
437           goto grow;
438         }
439       else if (can_realloc && n && (r -= 10) < 0)
440         {
441           if (mp_open(mp, ptr[n - 1]) != len[n - 1])
442             ASSERT(0);
443 grow:
444           {
445             uns k = n - 1;
446             for (uns i = random_max(4); i--; )
447               {
448                 uns l = len[k];
449                 len[k] = random_max(0x2000);
450                 DBG("grow(%u)", len[k]);
451                 ptr[k] = mp_grow(mp, len[k]);
452                 DBG(" -> (%p)", ptr[k]);
453                 check(ptr[k], MIN(l, len[k]), k, align[k]);
454                 fill(ptr[k], len[k], k);
455               }
456             mp_end(mp, ptr[k] + len[k]);
457           }
458         }
459       else if (can_realloc && n && (r -= 20) < 0)
460         {
461           uns i = n - 1, l = len[i];
462           DBG("realloc(%p, %u)", ptr[i], len[i]);
463           ptr[i] = mp_realloc(mp, ptr[i], len[i] = random_max(0x2000));
464           DBG(" -> (%p, %u)", ptr[i], len[i]);
465           check(ptr[i],  MIN(len[i], l), i, align[i]);
466           fill(ptr[i], len[i], i);
467         }
468       else if (m < max && (r -= 5) < 0)
469         {
470           DBG("push(%u)", m);
471           num[m] = n;
472           state[m++] = mp_push(mp);
473           can_realloc = 0;
474         }
475       else if (m && (r -= 2) < 0)
476         {
477           m--;
478           DBG("pop(%u)", m);
479           mp_pop(mp);
480           n = num[m];
481           can_realloc = 0;
482         }
483       else if (m && (r -= 1) < 0)
484         {
485           uns i = random_max(m);
486           DBG("restore(%u)", i);
487           mp_restore(mp, state[i]);
488           n = num[m = i];
489           can_realloc = 0;
490         }
491       else if (can_realloc && n && (r -= 5) < 0)
492         ASSERT(mp_size(mp, ptr[n - 1]) == len[n - 1]);
493     }
494
495   mp_delete(mp);
496   return 0;
497 }
498
499 #endif