#include <limits.h>
#include <assert.h>
#include "alloc.h"
+#include "build_assert/build_assert.h"
+#include "config.h"
+
+#if HAVE_ALIGNOF
+#define ALIGNOF(t) __alignof__(t)
+#else
+/* Alignment by measuring structure padding. */
+#define ALIGNOF(t) (sizeof(struct { char c; t _h; }) - 1 - sizeof(t))
+#endif
/* FIXME: Doesn't handle non-page-aligned poolsize. */
-/* FIXME: Doesn't handle sub-page allocations. */
+/* FIXME: Reduce. */
#define MIN_SIZE (getpagesize() * 2)
+/* Metadata looks like this:
+ * <unsigned long metalen> <page states> <align-pad> [<1-byte-len> <free|bit|uniform> bits...]* [unsigned long next].
+ */
+
+#define BITS_PER_PAGE 2
enum page_state
{
FREE,
TAKEN_START,
};
-void alloc_init(void *pool, unsigned long poolsize)
-{
- uint8_t *bits = pool;
- unsigned int pages = poolsize / getpagesize();
-
- if (poolsize < MIN_SIZE)
- return;
-
- memset(bits, 0, (pages * 2 + CHAR_BIT - 1)/ CHAR_BIT);
-}
-
static enum page_state get_page_state(const uint8_t *bits, unsigned long page)
{
+ bits += sizeof(unsigned long);
return bits[page * 2 / CHAR_BIT] >> (page * 2 % CHAR_BIT) & 3;
}
static void set_page_state(uint8_t *bits, unsigned long page, enum page_state s)
{
+ bits += sizeof(unsigned long);
bits[page * 2 / CHAR_BIT] &= ~(3 << (page * 2 % CHAR_BIT));
bits[page * 2 / CHAR_BIT] |= ((uint8_t)s << (page * 2 % CHAR_BIT));
}
+/* Assumes a is a power of two. */
+static unsigned long align_up(unsigned long x, unsigned long a)
+{
+ return (x + a - 1) & ~(a - 1);
+}
+
+static unsigned long div_up(unsigned long x, unsigned long a)
+{
+ return (x + a - 1) / a;
+}
+
static unsigned long metadata_length(void *pool, unsigned long poolsize)
{
- return ((poolsize / getpagesize() * 2 / CHAR_BIT) + getpagesize() - 1)
- & ~(getpagesize() - 1);
+ return *(unsigned long *)pool;
}
-void *alloc_get(void *pool, unsigned long poolsize,
- unsigned long size, unsigned long align)
+void alloc_init(void *pool, unsigned long poolsize)
{
- long i;
- unsigned long free, want, metalen;
+ /* FIXME: Alignment assumptions about pool. */
+ unsigned long *metalen = pool, pages, pagestatebytes, i;
if (poolsize < MIN_SIZE)
- return NULL;
+ return;
- /* FIXME: Necessary for this. */
- if (size == 0)
- size = 1;
+ pages = poolsize / getpagesize();
- want = (size + getpagesize() - 1) / getpagesize();
- metalen = metadata_length(pool, poolsize);
+ /* First comes the metadata length, then 2 bits per page, then
+ * the next pointer. */
+ pagestatebytes = div_up(pages * BITS_PER_PAGE, CHAR_BIT);
+ *metalen = sizeof(*metalen)
+ + align_up(pagestatebytes, ALIGNOF(unsigned long))
+ + sizeof(unsigned long);
+
+ /* Mark all the bits FREE to start, and zero the next pointer. */
+ BUILD_ASSERT(FREE == 0);
+ memset(metalen + 1, 0, *metalen - sizeof(*metalen));
+
+ /* Mark the metadata page(s) allocated. */
+ set_page_state(pool, 0, TAKEN_START);
+ for (i = 1; i < div_up(*metalen, getpagesize()); i++)
+ set_page_state(pool, i, TAKEN);
+}
+
+static void *alloc_get_pages(void *pool, unsigned long poolsize,
+ unsigned long pages, unsigned long align)
+{
+ long i;
+ unsigned long free;
free = 0;
/* We allocate from far end, to increase ability to expand metadata. */
- for (i = (poolsize - metalen) / getpagesize() - 1; i >= 0; i--) {
+ for (i = poolsize / getpagesize() - 1; i >= 0; i--) {
switch (get_page_state(pool, i)) {
case FREE:
- if (++free >= want) {
+ if (++free >= pages) {
unsigned long j;
- char *ret = (char *)pool + metalen
- + i * getpagesize();
+ char *ret = (char *)pool + i * getpagesize();
/* They might ask for multi-page alignment. */
if ((unsigned long)ret % align)
continue;
- for (j = i+1; j < i + want; j++)
+ for (j = i+1; j < i + pages; j++)
set_page_state(pool, j, TAKEN);
set_page_state(pool, i, TAKEN_START);
return ret;
return NULL;
}
+void *alloc_get(void *pool, unsigned long poolsize,
+ unsigned long size, unsigned long align)
+{
+ if (poolsize < MIN_SIZE)
+ return NULL;
+
+ if (size >= getpagesize() || align > getpagesize()) {
+ unsigned long pages = (size + getpagesize()-1) / getpagesize();
+ return alloc_get_pages(pool, poolsize, pages, align);
+ }
+
+ /* FIXME: Sub-page allocations. */
+ return alloc_get_pages(pool, poolsize, 1, align);
+}
+
void alloc_free(void *pool, unsigned long poolsize, void *free)
{
unsigned long pagenum, metalen;
- if (poolsize < MIN_SIZE)
- return;
-
if (!free)
return;
+ assert(poolsize >= MIN_SIZE);
+
metalen = metadata_length(pool, poolsize);
- assert(free > pool && (char *)pool + poolsize > (char *)free);
+ assert((char *)free >= (char *)pool + metalen);
+ assert((char *)pool + poolsize > (char *)free);
assert((unsigned long)free % getpagesize() == 0);
- pagenum = ((char *)free - (char *)pool - metalen) / getpagesize();
+ pagenum = ((char *)free - (char *)pool) / getpagesize();
assert(get_page_state(pool, pagenum) == TAKEN_START);
set_page_state(pool, pagenum, FREE);
bool alloc_check(void *pool, unsigned long poolsize)
{
- unsigned int i, metalen;
+ unsigned long i, metalen, pagestatebytes;
enum page_state last_state = FREE;
if (poolsize < MIN_SIZE)
return true;
metalen = metadata_length(pool, poolsize);
- for (i = 0; i < (poolsize - metalen) / getpagesize(); i++) {
+ if (get_page_state(pool, 0) != TAKEN_START)
+ return false;
+
+ pagestatebytes = div_up(poolsize / getpagesize() * BITS_PER_PAGE,
+ CHAR_BIT);
+ if (metalen < (sizeof(unsigned long)
+ + align_up(pagestatebytes, ALIGNOF(unsigned long))
+ + sizeof(unsigned long)))
+ return false;
+
+ for (i = 1; i < poolsize / getpagesize(); i++) {
enum page_state state = get_page_state(pool, i);
+
+ /* Metadata pages will be marked TAKEN. */
+ if (i < div_up(metalen, getpagesize())) {
+ if (get_page_state(pool, 0) != TAKEN)
+ return false;
+ continue;
+ }
+
switch (state) {
case FREE:
case TAKEN_START: