Initial cut at file/mem allocator (pages only)

diff --git a/alloc/_info.c b/alloc/_info.c
new file mode 100644 (file)
index 0000000..588dd86
--- /dev/null
+++ b/alloc/_info.c
@@ -0,0 +1,102 @@
+#include <stdio.h>
+#include <string.h>
+#include "config.h"
+
+/**
+ * alloc - memory allocator routines
+ *
+ * The alloc module implements a simple allocator which you can use to
+ * dynamically allocate space within a region of memory.  This can be useful
+ * for suballocations within a given region, or a memory-mapped file.
+ *
+ * All metadata is kept within the memory handed to the allocator: you only
+ * need hand the pointer and the size of the memory to each call.
+ *
+ * The region contents is always in offsets, so it can be mapped in different
+ * places, but is not endian-safe.
+ *
+ * Example:
+ *     #include <sys/mman.h>
+ *     #include <unistd.h>
+ *     #include <sys/types.h>
+ *     #include <err.h>
+ *     #include "alloc/alloc.h"
+ *
+ *     static void usage(const char *name)
+ *     {
+ *             errx(1, "Usage: %s --create <mapfile>\n"
+ *                  " %s --check <mapfile>\n"
+ *                  " %s --alloc <mapfile>\n"
+ *                  " %s --free=<offset> <mapfile>\n", name, name, name);
+ *     }
+ *
+ *     // Create a memory mapped file, and allocate from within it
+ *     int main(int argc, char *argv[])
+ *     {
+ *             void *a, *p;
+ *             int fd;
+ *             enum { CREATE, CHECK, ALLOC, FREE } cmd;
+ *
+ *             if (argc != 3)
+ *                     usage(argv[0]);
+ *
+ *             if (strcmp(argv[1], "--create") == 0)
+ *                     cmd = CREATE;
+ *             else if (strcmp(argv[1], "--check") == 0)
+ *                     cmd = CHECK;
+ *             else if (strcmp(argv[1], "--alloc") == 0)
+ *                     cmd = ALLOC;
+ *             else if (strncmp(argv[1], "--free=", strlen("--free=")) == 0)
+ *                     cmd = FREE;
+ *             else
+ *                     usage(argv[0]);
+ *
+ *             if (cmd == CREATE) {
+ *                     fd = open(argv[2], O_RDWR|O_CREAT|O_EXCL, 0600);
+ *                     if (fd < 0)
+ *                             err(1, "Could not create %s", argv[2]);
+ *                     if (ftruncate(fd, 1048576) != 0)
+ *                             err(1, "Could not set length on %s", argv[2]);
+ *             } else {
+ *                     fd = open(argv[2], O_RDWR);
+ *                     if (fd < 0)
+ *                             err(1, "Could not open %s", argv[2]);
+ *             }
+ *
+ *             a = mmap(NULL, 1048576, PROT_READ|PROT_WRITE, MAP_SHARED, fd,0);
+ *             if (a == MAP_FAILED)
+ *                     err(1, "Could not map %s", argv[2]);
+ *
+ *             switch (cmd) {
+ *             case CREATE:
+ *                     alloc_init(a, 1048576);
+ *                     break;
+ *             case CHECK:
+ *                     if (!alloc_check(a, 1048576))
+ *                             err(1, "Region is corrupt");
+ *                     break;
+ *             case ALLOC:
+ *                     p = alloc_get(a, 1048576, 1024, 16);
+ *                     if (!p)
+ *                             errx(1, "Could not allocate");
+ *                     printf("%zu\n", (char *)p - (char *)a);
+ *                     break;
+ *             case FREE:
+ *                     p = (char *)a + atol(argv[1] + strlen("--free="));
+ *                     alloc_free(a, 1048576, p);
+ *                     break;
+ *             }
+ *             return 0;
+ *     }
+ */
+int main(int argc, char *argv[])
+{
+       if (argc != 2)
+               return 1;
+
+       if (strcmp(argv[1], "depends") == 0) {
+               return 0;
+       }
+
+       return 1;
+}

diff --git a/alloc/alloc.c b/alloc/alloc.c
new file mode 100644 (file)
index 0000000..f363834
--- /dev/null
+++ b/alloc/alloc.c
@@ -0,0 +1,139 @@
+#include <unistd.h>
+#include <stdint.h>
+#include <string.h>
+#include <limits.h>
+#include <assert.h>
+#include "alloc.h"
+
+/* FIXME: Doesn't handle non-page-aligned poolsize. */
+/* FIXME: Doesn't handle sub-page allocations. */
+
+#define MIN_SIZE (getpagesize() * 2)
+
+enum page_state
+{
+       FREE,
+       TAKEN,
+       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)
+{
+       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[page * 2 / CHAR_BIT] &= ~(3 << (page * 2 % CHAR_BIT));
+       bits[page * 2 / CHAR_BIT] |= ((uint8_t)s << (page * 2 % CHAR_BIT));
+}
+
+static unsigned long metadata_length(void *pool, unsigned long poolsize)
+{
+       return ((poolsize / getpagesize() * 2 / CHAR_BIT) + getpagesize() - 1)
+               & ~(getpagesize() - 1);
+}
+
+void *alloc_get(void *pool, unsigned long poolsize,
+               unsigned long size, unsigned long align)
+{
+       unsigned long i, free, want, metalen;
+
+       if (poolsize < MIN_SIZE)
+               return NULL;
+
+       /* FIXME: Necessary for this. */
+       if (size == 0)
+               size = 1;
+
+       want = (size + getpagesize() - 1) / getpagesize();
+       metalen = metadata_length(pool, poolsize);
+
+       free = 0;
+       for (i = 0; i < (poolsize - metalen) / getpagesize(); i++) {
+               switch (get_page_state(pool, i)) {
+               case FREE:
+                       if (++free >= want) {
+                               unsigned int j;
+                               char *ret = (char *)pool + metalen
+                                       + (i - want + 1) * getpagesize();
+
+                               if ((unsigned long)ret % align)
+                                       continue;
+
+                               for (j = i; j > i - want + 1; j--)
+                                       set_page_state(pool, j, TAKEN);
+                               set_page_state(pool, i - want + 1, TAKEN_START);
+                               return ret;
+                       }
+                       break;
+               case TAKEN_START:
+               case TAKEN:
+                       free = 0;
+                       break;
+               }
+       }
+
+       return NULL;
+}
+
+void alloc_free(void *pool, unsigned long poolsize, void *free)
+{
+       unsigned long pagenum, metalen;
+
+       if (poolsize < MIN_SIZE)
+               return;
+
+       if (!free)
+               return;
+
+       metalen = metadata_length(pool, poolsize);
+
+       assert(free > pool && (char *)pool + poolsize > (char *)free);
+       assert((unsigned long)free % getpagesize() == 0);
+
+       pagenum = ((char *)free - (char *)pool - metalen) / getpagesize();
+
+       assert(get_page_state(pool, pagenum) == TAKEN_START);
+       set_page_state(pool, pagenum, FREE);
+       while (get_page_state(pool, ++pagenum) == TAKEN)
+               set_page_state(pool, pagenum, FREE);
+}
+
+bool alloc_check(void *pool, unsigned long poolsize)
+{
+       unsigned int i, metalen;
+       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++) {
+               enum page_state state = get_page_state(pool, i);
+               switch (state) {
+               case FREE:
+               case TAKEN_START:
+                       break;
+               case TAKEN:
+                       if (last_state == FREE)
+                               return false;
+                       break;
+               default:
+                       return false;
+               }
+               last_state = state;
+       }
+       return true;
+}

diff --git a/alloc/alloc.h b/alloc/alloc.h
new file mode 100644 (file)
index 0000000..7d0aa14
--- /dev/null
+++ b/alloc/alloc.h
@@ -0,0 +1,11 @@
+#ifndef ALLOC_H
+#define ALLOC_H
+#include <stdbool.h>
+
+void alloc_init(void *pool, unsigned long poolsize);
+void *alloc_get(void *pool, unsigned long poolsize,
+               unsigned long size, unsigned long align);
+void alloc_free(void *pool, unsigned long poolsize, void *free);
+bool alloc_check(void *pool, unsigned long poolsize);
+
+#endif /* ALLOC_H */

diff --git a/alloc/test/run.c b/alloc/test/run.c
new file mode 100644 (file)
index 0000000..b0fbe81
--- /dev/null
+++ b/alloc/test/run.c
@@ -0,0 +1,136 @@
+#include "alloc/alloc.h"
+#include "tap.h"
+#include "alloc/alloc.c"
+#include <stdlib.h>
+
+#define POOL_ORD 16
+#define POOL_SIZE (1 << POOL_ORD)
+
+#define sort(p, num, cmp) \
+       qsort((p), (num), sizeof(*p), (int(*)(const void *, const void *))cmp)
+
+static int addr_cmp(void **a, void **b)
+{
+       return (*a) - (*b);
+}
+
+static bool unique(void *p[], unsigned int num)
+{
+       unsigned int i;
+
+       for (i = 1; i < num; i++)
+               if (p[i] == p[i-1])
+                       return false;
+       return true;
+}      
+
+int main(int argc, char *argv[])
+{
+       void *mem;
+       unsigned int i, num, max_size;
+       void *p[POOL_SIZE];
+
+       plan_tests(141);
+
+       /* FIXME: Needs to be page aligned for now. */
+       posix_memalign(&mem, getpagesize(), POOL_SIZE);
+
+       /* Small pool, all allocs fail, even 0-length. */
+       alloc_init(mem, 0);
+       ok1(alloc_check(mem, 0));
+       ok1(alloc_get(mem, 0, 1, 1) == NULL);
+       ok1(alloc_get(mem, 0, 128, 1) == NULL);
+       ok1(alloc_get(mem, 0, 0, 1) == NULL);
+
+       /* Free of NULL should work. */
+       alloc_free(mem, 0, NULL);
+
+       alloc_init(mem, POOL_SIZE);
+       ok1(alloc_check(mem, POOL_SIZE));
+       /* Find largest allocation which works. */
+       for (max_size = POOL_SIZE * 2; max_size; max_size--) {
+               p[0] = alloc_get(mem, POOL_SIZE, max_size, 1);
+               if (p[0])
+                       break;
+       }
+       ok1(max_size < POOL_SIZE);
+       ok1(max_size > 0);
+       ok1(alloc_check(mem, POOL_SIZE));
+
+       /* Free it, should be able to reallocate it. */
+       alloc_free(mem, POOL_SIZE, p[0]);
+       ok1(alloc_check(mem, POOL_SIZE));
+
+       p[0] = alloc_get(mem, POOL_SIZE, max_size, 1);
+       ok1(p[0]);
+       ok1(alloc_check(mem, POOL_SIZE));
+       alloc_free(mem, POOL_SIZE, p[0]);
+       ok1(alloc_check(mem, POOL_SIZE));
+
+       /* Allocate a whole heap. */
+       for (i = 0; i < POOL_SIZE; i++) {
+               p[i] = alloc_get(mem, POOL_SIZE, 1, 1);
+               if (!p[i])
+                       break;
+       }
+
+       num = i;
+       /* Can't allocate this many. */
+       ok1(num != POOL_SIZE);
+       ok1(alloc_check(mem, POOL_SIZE));
+
+       /* Sort them. */
+       sort(p, num, addr_cmp);
+
+       /* Uniqueness check */
+       ok1(unique(p, num));
+
+       /* Free every second one. */
+       for (i = 0; i < num; i += 2) {
+               alloc_free(mem, POOL_SIZE, p[i]);
+               ok1(alloc_check(mem, POOL_SIZE));
+       }
+       for (i = 1; i < num; i += 2) {
+               alloc_free(mem, POOL_SIZE, p[i]);
+               ok1(alloc_check(mem, POOL_SIZE));
+       }
+       ok1(alloc_check(mem, POOL_SIZE));
+
+       /* Should be able to reallocate max size. */
+       p[0] = alloc_get(mem, POOL_SIZE, max_size, 1);
+       ok1(p[0]);
+       ok1(alloc_check(mem, POOL_SIZE));
+
+       /* Re-initializing should be the same as freeing everything */
+       alloc_init(mem, POOL_SIZE);
+       ok1(alloc_check(mem, POOL_SIZE));
+       p[0] = alloc_get(mem, POOL_SIZE, max_size, 1);
+       ok1(p[0]);
+       ok1(alloc_check(mem, POOL_SIZE));
+       alloc_free(mem, POOL_SIZE, p[0]);
+       ok1(alloc_check(mem, POOL_SIZE));
+
+       /* Alignment constraints should be met, as long as powers of two */
+       for (i = 0; i < POOL_ORD-2 /* FIXME: Should be -1 */; i++) {
+               p[i] = alloc_get(mem, POOL_SIZE, i, 1 << i);
+               ok1(p[i]);
+               ok1(((unsigned long)p[i] % (1 << i)) == 0);
+               ok1(alloc_check(mem, POOL_SIZE));
+       }
+
+       for (i = 0; i < POOL_ORD-2 /* FIXME: Should be -1 */; i++) {
+               alloc_free(mem, POOL_SIZE, p[i]);
+               ok1(alloc_check(mem, POOL_SIZE));
+       }
+
+       /* Alignment constraints for a single-byte allocation. */
+       for (i = 0; i < POOL_ORD; i++) {
+               p[0] = alloc_get(mem, POOL_SIZE, 1, 1 << i);
+               ok1(p[0]);
+               ok1(alloc_check(mem, POOL_SIZE));
+               alloc_free(mem, POOL_SIZE, p[0]);
+               ok1(alloc_check(mem, POOL_SIZE));
+       }
+
+       return exit_status();
+}