Allocator now has metadata.
[ccan] / alloc / alloc.c
1 #include <unistd.h>
2 #include <stdint.h>
3 #include <string.h>
4 #include <limits.h>
5 #include <assert.h>
6 #include "alloc.h"
7 #include "build_assert/build_assert.h"
8 #include "config.h"
9
10 #if HAVE_ALIGNOF
11 #define ALIGNOF(t) __alignof__(t)
12 #else
13 /* Alignment by measuring structure padding. */
14 #define ALIGNOF(t) (sizeof(struct { char c; t _h; }) - 1 - sizeof(t))
15 #endif
16
17 /* FIXME: Doesn't handle non-page-aligned poolsize. */
18
19 /* FIXME: Reduce. */
20 #define MIN_SIZE (getpagesize() * 2)
21
22 /* Metadata looks like this:
23  * <unsigned long metalen> <page states> <align-pad> [<1-byte-len> <free|bit|uniform> bits...]* [unsigned long next]. 
24  */
25
26 #define BITS_PER_PAGE 2
27 enum page_state
28 {
29         FREE,
30         TAKEN,
31         TAKEN_START,
32 };
33
34 static enum page_state get_page_state(const uint8_t *bits, unsigned long page)
35 {
36         bits += sizeof(unsigned long);
37         return bits[page * 2 / CHAR_BIT] >> (page * 2 % CHAR_BIT) & 3;
38 }
39
40 static void set_page_state(uint8_t *bits, unsigned long page, enum page_state s)
41 {
42         bits += sizeof(unsigned long);
43         bits[page * 2 / CHAR_BIT] &= ~(3 << (page * 2 % CHAR_BIT));
44         bits[page * 2 / CHAR_BIT] |= ((uint8_t)s << (page * 2 % CHAR_BIT));
45 }
46
47 /* Assumes a is a power of two. */
48 static unsigned long align_up(unsigned long x, unsigned long a)
49 {
50         return (x + a - 1) & ~(a - 1);
51 }
52
53 static unsigned long div_up(unsigned long x, unsigned long a)
54 {
55         return (x + a - 1) / a;
56 }
57
58 static unsigned long metadata_length(void *pool, unsigned long poolsize)
59 {
60         return *(unsigned long *)pool;
61 }
62
63 void alloc_init(void *pool, unsigned long poolsize)
64 {
65         /* FIXME: Alignment assumptions about pool. */
66         unsigned long *metalen = pool, pages, pagestatebytes, i;
67
68         if (poolsize < MIN_SIZE)
69                 return;
70
71         pages = poolsize / getpagesize();
72
73         /* First comes the metadata length, then 2 bits per page, then
74          * the next pointer. */
75         pagestatebytes = div_up(pages * BITS_PER_PAGE, CHAR_BIT);
76         *metalen = sizeof(*metalen)
77                 + align_up(pagestatebytes, ALIGNOF(unsigned long))
78                 + sizeof(unsigned long);
79
80         /* Mark all the bits FREE to start, and zero the next pointer. */
81         BUILD_ASSERT(FREE == 0);
82         memset(metalen + 1, 0, *metalen - sizeof(*metalen));
83
84         /* Mark the metadata page(s) allocated. */
85         set_page_state(pool, 0, TAKEN_START);
86         for (i = 1; i < div_up(*metalen, getpagesize()); i++)
87                 set_page_state(pool, i, TAKEN);
88 }
89
90 static void *alloc_get_pages(void *pool, unsigned long poolsize,
91                              unsigned long pages, unsigned long align)
92 {
93         long i;
94         unsigned long free;
95
96         free = 0;
97         /* We allocate from far end, to increase ability to expand metadata. */
98         for (i = poolsize / getpagesize() - 1; i >= 0; i--) {
99                 switch (get_page_state(pool, i)) {
100                 case FREE:
101                         if (++free >= pages) {
102                                 unsigned long j;
103                                 char *ret = (char *)pool + i * getpagesize();
104
105                                 /* They might ask for multi-page alignment. */
106                                 if ((unsigned long)ret % align)
107                                         continue;
108
109                                 for (j = i+1; j < i + pages; j++)
110                                         set_page_state(pool, j, TAKEN);
111                                 set_page_state(pool, i, TAKEN_START);
112                                 return ret;
113                         }
114                         break;
115                 case TAKEN_START:
116                 case TAKEN:
117                         free = 0;
118                         break;
119                 }
120         }
121
122         return NULL;
123 }
124
125 void *alloc_get(void *pool, unsigned long poolsize,
126                 unsigned long size, unsigned long align)
127 {
128         if (poolsize < MIN_SIZE)
129                 return NULL;
130
131         if (size >= getpagesize() || align > getpagesize()) {
132                 unsigned long pages = (size + getpagesize()-1) / getpagesize();
133                 return alloc_get_pages(pool, poolsize, pages, align);
134         }
135
136         /* FIXME: Sub-page allocations. */
137         return alloc_get_pages(pool, poolsize, 1, align);
138 }
139
140 void alloc_free(void *pool, unsigned long poolsize, void *free)
141 {
142         unsigned long pagenum, metalen;
143
144         if (!free)
145                 return;
146
147         assert(poolsize >= MIN_SIZE);
148
149         metalen = metadata_length(pool, poolsize);
150
151         assert((char *)free >= (char *)pool + metalen);
152         assert((char *)pool + poolsize > (char *)free);
153         assert((unsigned long)free % getpagesize() == 0);
154
155         pagenum = ((char *)free - (char *)pool) / getpagesize();
156
157         assert(get_page_state(pool, pagenum) == TAKEN_START);
158         set_page_state(pool, pagenum, FREE);
159         while (get_page_state(pool, ++pagenum) == TAKEN)
160                 set_page_state(pool, pagenum, FREE);
161 }
162
163 bool alloc_check(void *pool, unsigned long poolsize)
164 {
165         unsigned long i, metalen, pagestatebytes;
166         enum page_state last_state = FREE;
167
168         if (poolsize < MIN_SIZE)
169                 return true;
170
171         metalen = metadata_length(pool, poolsize);
172         if (get_page_state(pool, 0) != TAKEN_START)
173                 return false;
174
175         pagestatebytes = div_up(poolsize / getpagesize() * BITS_PER_PAGE,
176                                 CHAR_BIT);
177         if (metalen < (sizeof(unsigned long)
178                        + align_up(pagestatebytes, ALIGNOF(unsigned long))
179                        + sizeof(unsigned long)))
180                 return false;
181
182         for (i = 1; i < poolsize / getpagesize(); i++) {
183                 enum page_state state = get_page_state(pool, i);
184
185                 /* Metadata pages will be marked TAKEN. */
186                 if (i < div_up(metalen, getpagesize())) {
187                         if (get_page_state(pool, 0) != TAKEN)
188                                 return false;
189                         continue;
190                 }
191
192                 switch (state) {
193                 case FREE:
194                 case TAKEN_START:
195                         break;
196                 case TAKEN:
197                         if (last_state == FREE)
198                                 return false;
199                         break;
200                 default:
201                         return false;
202                 }
203                 last_state = state;
204         }
205         return true;
206 }