7 #include "build_assert/build_assert.h"
11 #define ALIGNOF(t) __alignof__(t)
13 /* Alignment by measuring structure padding. */
14 #define ALIGNOF(t) (sizeof(struct { char c; t _h; }) - 1 - sizeof(t))
17 /* FIXME: Doesn't handle non-page-aligned poolsize. */
20 #define MIN_SIZE (getpagesize() * 2)
22 /* Metadata looks like this:
23 * <unsigned long metalen> <page states> <align-pad> [<1-byte-len> <free|bit|uniform> bits...]* [unsigned long next].
26 #define BITS_PER_PAGE 2
34 static enum page_state get_page_state(const uint8_t *bits, unsigned long page)
36 bits += sizeof(unsigned long);
37 return bits[page * 2 / CHAR_BIT] >> (page * 2 % CHAR_BIT) & 3;
40 static void set_page_state(uint8_t *bits, unsigned long page, enum page_state s)
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));
47 /* Assumes a is a power of two. */
48 static unsigned long align_up(unsigned long x, unsigned long a)
50 return (x + a - 1) & ~(a - 1);
53 static unsigned long div_up(unsigned long x, unsigned long a)
55 return (x + a - 1) / a;
58 static unsigned long metadata_length(void *pool, unsigned long poolsize)
60 return *(unsigned long *)pool;
63 void alloc_init(void *pool, unsigned long poolsize)
65 /* FIXME: Alignment assumptions about pool. */
66 unsigned long *metalen = pool, pages, pagestatebytes, i;
68 if (poolsize < MIN_SIZE)
71 pages = poolsize / getpagesize();
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);
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));
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);
90 static void *alloc_get_pages(void *pool, unsigned long poolsize,
91 unsigned long pages, unsigned long align)
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)) {
101 if (++free >= pages) {
103 char *ret = (char *)pool + i * getpagesize();
105 /* They might ask for multi-page alignment. */
106 if ((unsigned long)ret % align)
109 for (j = i+1; j < i + pages; j++)
110 set_page_state(pool, j, TAKEN);
111 set_page_state(pool, i, TAKEN_START);
125 void *alloc_get(void *pool, unsigned long poolsize,
126 unsigned long size, unsigned long align)
128 if (poolsize < MIN_SIZE)
131 if (size >= getpagesize() || align > getpagesize()) {
132 unsigned long pages = (size + getpagesize()-1) / getpagesize();
133 return alloc_get_pages(pool, poolsize, pages, align);
136 /* FIXME: Sub-page allocations. */
137 return alloc_get_pages(pool, poolsize, 1, align);
140 void alloc_free(void *pool, unsigned long poolsize, void *free)
142 unsigned long pagenum, metalen;
147 assert(poolsize >= MIN_SIZE);
149 metalen = metadata_length(pool, poolsize);
151 assert((char *)free >= (char *)pool + metalen);
152 assert((char *)pool + poolsize > (char *)free);
153 assert((unsigned long)free % getpagesize() == 0);
155 pagenum = ((char *)free - (char *)pool) / getpagesize();
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);
163 bool alloc_check(void *pool, unsigned long poolsize)
165 unsigned long i, metalen, pagestatebytes;
166 enum page_state last_state = FREE;
168 if (poolsize < MIN_SIZE)
171 metalen = metadata_length(pool, poolsize);
172 if (get_page_state(pool, 0) != TAKEN_START)
175 pagestatebytes = div_up(poolsize / getpagesize() * BITS_PER_PAGE,
177 if (metalen < (sizeof(unsigned long)
178 + align_up(pagestatebytes, ALIGNOF(unsigned long))
179 + sizeof(unsigned long)))
182 for (i = 1; i < poolsize / getpagesize(); i++) {
183 enum page_state state = get_page_state(pool, i);
185 /* Metadata pages will be marked TAKEN. */
186 if (i < div_up(metalen, getpagesize())) {
187 if (get_page_state(pool, 0) != TAKEN)
197 if (last_state == FREE)