Allocator now has metadata.

diff --git a/alloc/_info.c b/alloc/_info.c
index 588dd86814fc42ca4c6be44ab9ce806d4a080cdd..59a663804a426b0b0eb474eda99655669ba3fea0 100644 (file)
--- a/alloc/_info.c
+++ b/alloc/_info.c
@@ -95,6 +95,7 @@ int main(int argc, char *argv[])
                return 1;
 
        if (strcmp(argv[1], "depends") == 0) {
                return 1;
 
        if (strcmp(argv[1], "depends") == 0) {

+               printf("build_assert\n");

                return 0;
        }
 
                return 0;
        }
 

diff --git a/alloc/alloc.c b/alloc/alloc.c
index 3ec6952c82c8b6d20187ea722d56a907d518548f..1bf9ade7f2e5c13fe06f81dfe7fd171b6287309f 100644 (file)
--- a/alloc/alloc.c
+++ b/alloc/alloc.c
@@ -4,12 +4,26 @@
 #include <limits.h>
 #include <assert.h>
 #include "alloc.h"
 #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 non-page-aligned poolsize. */

-/* FIXME: Doesn't handle sub-page allocations. */

 
 

+/* FIXME: Reduce. */

 #define MIN_SIZE (getpagesize() * 2)
 
 #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,
 enum page_state
 {
        FREE,


@@ -17,65 +31,82 @@ enum page_state
        TAKEN_START,
 };
 
        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)
 {
 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)
 {
        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));
 }
 
        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)
 {
 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)
 
        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. */
 
        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:
                switch (get_page_state(pool, i)) {
                case FREE:

-                       if (++free >= want) {
+                       if (++free >= pages) {

                                unsigned long j;
                                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;
 
 
                                /* 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;
                                        set_page_state(pool, j, TAKEN);
                                set_page_state(pool, i, TAKEN_START);
                                return ret;


@@ -91,22 +122,37 @@ void *alloc_get(void *pool, unsigned long poolsize,
        return NULL;
 }
 
        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;
 
 void alloc_free(void *pool, unsigned long poolsize, void *free)
 {
        unsigned long pagenum, metalen;
 

-       if (poolsize < MIN_SIZE)
-               return;
-

        if (!free)
                return;
 
        if (!free)
                return;
 

+       assert(poolsize >= MIN_SIZE);
+

        metalen = metadata_length(pool, poolsize);
 
        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);
 
        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);
 
        assert(get_page_state(pool, pagenum) == TAKEN_START);
        set_page_state(pool, pagenum, FREE);


@@ -116,15 +162,33 @@ void alloc_free(void *pool, unsigned long poolsize, void *free)
 
 bool alloc_check(void *pool, unsigned long poolsize)
 {
 
 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);
        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);
                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:
                switch (state) {
                case FREE:
                case TAKEN_START:

diff --git a/config.h b/config.h
index 030a23824e9d315d006f18effaf40a89b008dd01..d1f3cd1783c2e324dc8ca5d1d4055fa4fe453da3 100644 (file)
--- a/config.h
+++ b/config.h
@@ -1,5 +1,6 @@
 /* Simple config.h for gcc. */
 #define HAVE_TYPEOF 1
 /* Simple config.h for gcc. */
 #define HAVE_TYPEOF 1

+#define HAVE_ALIGNOF 1

 #define HAVE_STATEMENT_EXPR 1
 #define HAVE_BUILTIN_EXPECT 1
 #define HAVE_ATTRIBUTE_PRINTF 1
 #define HAVE_STATEMENT_EXPR 1
 #define HAVE_BUILTIN_EXPECT 1
 #define HAVE_ATTRIBUTE_PRINTF 1