]> mj.ucw.cz Git - libucw.git/blob - lib/eltpool.c
Merge with git+ssh://git.ucw.cz/projects/sherlock/GIT/sherlock.git
[libucw.git] / lib / eltpool.c
1 /*
2  *      UCW Library -- Fast Allocator for Fixed-Size Elements
3  *
4  *      (c) 2007 Martin Mares <mj@ucw.cz>
5  *
6  *      This software may be freely distributed and used according to the terms
7  *      of the GNU Lesser General Public License.
8  */
9
10 /*
11  *  This allocator is optimized for intensive allocation and freeing of small
12  *  blocks of identical sizes. System memory is allocated by multiples of the
13  *  page size and it is returned back only when the whole eltpool is deleted.
14  *
15  *  In the future, we can add returning of memory to the system and also cache
16  *  coloring like in the SLAB allocator used in the Linux kernel.
17  */
18
19 #undef LOCAL_DEBUG
20
21 #include "lib/lib.h"
22 #include "lib/eltpool.h"
23
24 struct eltpool *
25 ep_new(uns elt_size, uns elts_per_chunk)
26 {
27   struct eltpool *pool = xmalloc_zero(sizeof(*pool));
28   pool->elt_size = ALIGN_TO(MAX(elt_size, sizeof(struct eltpool_free)), CPU_STRUCT_ALIGN);
29   pool->chunk_size = CPU_PAGE_SIZE;
30   while (pool->elt_size * elts_per_chunk + sizeof(struct eltpool_chunk) > pool->chunk_size)
31     pool->chunk_size *= 2;
32   pool->elts_per_chunk = (pool->chunk_size - sizeof(struct eltpool_chunk)) / pool->elt_size;
33   DBG("ep_new(): got elt_size=%d, epc=%d; used chunk_size=%d, epc=%d", elt_size, elts_per_chunk, pool->chunk_size, pool->elts_per_chunk);
34   return pool;
35 }
36
37 void
38 ep_delete(struct eltpool *pool)
39 {
40   struct eltpool_chunk *ch;
41   while (ch = pool->first_chunk)
42     {
43       pool->first_chunk = ch->next;
44       page_free(ch, pool->chunk_size);
45     }
46   xfree(pool);
47 }
48
49 void *
50 ep_alloc_slow(struct eltpool *pool)
51 {
52   struct eltpool_chunk *ch = page_alloc(pool->chunk_size);
53   void *p = (void *)(ch+1);
54   for (uns i=1; i<pool->elts_per_chunk; i++)
55     {
56       struct eltpool_free *f = p;
57       f->next = pool->first_free;
58       pool->first_free = f;
59       p += pool->elt_size;
60     }
61   ch->next = pool->first_chunk;
62   pool->first_chunk = ch;
63   return p;
64 }
65
66 #ifdef TEST
67
68 #include <stdio.h>
69 #include "lib/clists.h"
70
71 struct argh {
72   cnode n;
73   byte x[1];
74 } PACKED;
75
76 int main(void)
77 {
78   struct eltpool *ep = ep_new(sizeof(struct argh), 64);
79   clist l;
80   clist_init(&l);
81   for (uns i=0; i<65536; i++)
82     {
83       struct argh *a = ep_alloc(ep);
84       if (i % 3)
85         clist_add_tail(&l, &a->n);
86       else
87         clist_add_head(&l, &a->n);
88       if (!(i % 5))
89         {
90           a = clist_head(&l);
91           clist_remove(&a->n);
92           ep_free(ep, a);
93         }
94     }
95   ep_delete(ep);
96   puts("OK");
97   return 0;
98 }
99
100 #endif