Added pool allocator.

4 files changed, 223 insertions, 2 deletions

diff --git a/Makefile b/Makefile
index 1998703..3dbb76a 100644
--- a/Makefile
+++ b/Makefile
@@ -6,7 +6,7 @@ ALL=bench
 
 all: $(ALL)
 
-bench: bench.o arena.o cached.o
+bench: bench.o arena.o cached.o pool.o
 
 clean:
 	$(RM) $(ALL) *.o
diff --git a/bench.c b/bench.c
index 966766b..d8eeaf8 100644
--- a/bench.c
+++ b/bench.c
@@ -6,11 +6,12 @@
 
 #include "arena.h"
 #include "cached.h"
+#include "pool.h"
 
 #define UNUSED __attribute__((unused))
 
 #define ALLOC_SIZE 4096
-#define ARENA_SIZE (1024*ALLOC_SIZE)
+#define ARENA_SIZE (1024 * ALLOC_SIZE)
 
 static sig_atomic_t running;
 
@@ -88,6 +89,26 @@ bench_ca_alloc(size_t allocs)
 }
 
 static size_t
+bench_pl_alloc(size_t allocs)
+{
+	void *objs[allocs];
+	size_t count = 0;
+
+	while (running) {
+		for (size_t i = 0; i < allocs; i++) {
+			objs[i] = pl_alloc();
+			assert(objs[i]);
+			count++;
+		}
+		for (size_t i = 0; i < allocs; i++) {
+			pl_free(objs[i]);
+		}
+	}
+
+	return count;
+}
+
+static size_t
 bench_ar_alloc(size_t allocs, size_t size)
 {
 	void *objs[allocs];
@@ -179,6 +200,22 @@ bench_five(void)
 	ar_cleanup();
 }
 
+static void
+bench_six(void)
+{
+	if (pl_setup(4096, 1024) < 0) {
+		panic("failed to setup pool allocator");
+	}
+
+	set_alarm();
+
+	size_t allocs = bench_pl_alloc(1024);
+
+	printf("%-12s\t%9zu allocs/second\n", "pl_alloc", allocs);
+
+	pl_cleanup();
+}
+
 int
 main(void)
 {
@@ -191,6 +228,8 @@ main(void)
 	bench_four();
 	puts("");
 	bench_five();
+	puts("");
+	bench_six();
 
 	exit(EXIT_SUCCESS);
 }
diff --git a/pool.c b/pool.c
new file mode 100644
index 0000000..d0cee9b
--- /dev/null
+++ b/pool.c
@@ -0,0 +1,164 @@
+#include <assert.h>
+#include <limits.h>
+#include <stdint.h>
+#include <stdlib.h>
+#include <string.h>
+
+#include "pool.h"
+
+/* the actual pool of memory */
+static void *pool;
+/* size of one block in the pool */
+static size_t block_size;
+/* number of blocks in the pool */
+static size_t blocks;
+
+/* bitmap to track allocated blocks */
+static uint64_t *used;
+/* number of bits in each slot of `used` */
+static const size_t BITS = sizeof(*used) * CHAR_BIT;
+
+/* Allocate a bitmap with at least `blocks` bits. */
+static uint64_t *
+bitmap(size_t blocks)
+{
+	assert(blocks > 0);
+
+	const size_t slots = (blocks / BITS) + 1;
+
+	uint64_t *p = calloc(1, sizeof(*p) * slots);
+	return p; /* this is fine */
+}
+
+/* Mark given `block` as free. */
+static void
+bitmap_free(size_t block)
+{
+	assert(block < blocks);
+
+	const size_t slot = (block / BITS);
+	const size_t bit = (block % BITS);
+
+	used[slot] &= ~(1UL << bit);
+}
+
+/* Mark given `block` as used. */
+static void
+bitmap_used(size_t block)
+{
+	assert(block < blocks);
+
+	const size_t slot = (block / BITS);
+	const size_t bit = (block % BITS);
+
+	used[slot] |= (1UL << bit);
+}
+
+/*
+ * Find right-most zero bit. Returns 0 if there is none. Examples:
+ *
+ * 00000000	01010011	11111111	bits
+ *
+ * 11111111	10101100	00000000	~bits
+ * 00000001	01010100	00000000	bits+1
+ * --------	--------	--------
+ * 00000001	00000100	00000000	~bits & (bits+1)
+ */
+static inline uint64_t
+find_zero(const uint64_t bits)
+{
+	return ~bits & (bits + 1);
+}
+
+static inline uint64_t
+log2(const uint64_t x)
+{
+	return ((BITS - 1) - __builtin_clzl(x)); /* count leading zeros */
+}
+
+/* Find a free block. Returns -1 if there is none. */
+static int
+bitmap_alloc(void)
+{
+	for (size_t i = 0; i < blocks / BITS; i++) {
+		uint64_t free = find_zero(used[i]);
+		if (free != 0) {
+			return i * BITS + log2(free);
+		}
+	}
+	return -1;
+}
+
+int
+pl_setup(size_t object_size, size_t pool_size)
+{
+	assert(object_size > 0 && pool_size > 0);
+
+	void *p = calloc(pool_size, object_size);
+	if (p == NULL) {
+		return -1;
+	}
+
+	uint64_t *q = bitmap(pool_size);
+	if (q == NULL) {
+		free(p);
+		return -2;
+	}
+
+	pool = p;
+	used = q;
+
+	block_size = object_size;
+	blocks = pool_size;
+
+	return 0;
+}
+
+void *
+pl_alloc(void)
+{
+	assert(pool);
+
+	int block = bitmap_alloc();
+	if (block < 0) {
+		return NULL;
+	}
+
+	bitmap_used(block);
+
+	const uintptr_t p = (uintptr_t)pool;
+	const uintptr_t o = p + block * block_size;
+
+	return (void *)o;
+}
+
+void
+pl_free(void *object)
+{
+	assert(pool);
+
+	if (object == NULL) {
+		/* free(3) also does nothing for NULL */
+		return;
+	}
+
+	/* memset here to catch dangling references */
+	memset(object, 0, block_size);
+
+	const uintptr_t o = (uintptr_t)object;
+	const uintptr_t p = (uintptr_t)pool;
+	const uintptr_t offset = o - p;
+	const size_t block = offset / block_size;
+
+	bitmap_free(block);
+}
+
+void
+pl_cleanup(void)
+{
+	assert(pool);
+
+	free(used);
+	free(pool);
+	pool = NULL;
+}
diff --git a/pool.h b/pool.h
new file mode 100644
index 0000000..d678598
--- /dev/null
+++ b/pool.h
@@ -0,0 +1,18 @@
+#pragma once
+
+#ifndef POOL_H_
+#define POOL_H_
+
+int
+pl_setup(size_t object_size, size_t pool_size);
+
+void *
+pl_alloc(void);
+
+void
+pl_free(void *object);
+
+void
+pl_cleanup(void);
+
+#endif