aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
-rw-r--r--Makefile2
-rw-r--r--bench.c41
-rw-r--r--pool.c164
-rw-r--r--pool.h18
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