Added arena allocator.

4 files changed, 148 insertions, 5 deletions

diff --git a/Makefile b/Makefile
index 0ff5c08..1998703 100644
--- a/Makefile
+++ b/Makefile
@@ -6,7 +6,7 @@ ALL=bench
 
 all: $(ALL)
 
-bench: bench.o cached.o
+bench: bench.o arena.o cached.o
 
 clean:
 	$(RM) $(ALL) *.o
diff --git a/arena.c b/arena.c
new file mode 100644
index 0000000..9e15c2a
--- /dev/null
+++ b/arena.c
@@ -0,0 +1,82 @@
+#include <assert.h>
+#include <stdlib.h>
+#include <string.h>
+
+#include "arena.h"
+
+union align {
+	long long int l;
+	long double d;
+	void *p;
+};
+
+/* alignment for a long-ish builtin type? */
+#define ALIGN (sizeof(union align))
+/* ensure it's a power of two */
+static_assert(ALIGN && !(ALIGN & (ALIGN - 1)), "ALIGN not power of two");
+
+static unsigned char *data;
+static size_t total;
+static size_t used;
+
+/*
+ * round up to nearest multiple of ALIGN
+ */
+static size_t
+round_up(size_t minimum)
+{
+	return (minimum + ALIGN - 1) & ~(ALIGN - 1);
+}
+
+int
+ar_setup(size_t total_size)
+{
+	assert(data == NULL);
+
+	size_t adjusted = round_up(total_size);
+
+	void *p = calloc(1, adjusted);
+	if (p == NULL) {
+		return -1;
+	}
+
+	data = p;
+	total = adjusted;
+
+	return 0;
+}
+
+void *
+ar_alloc(size_t object_size)
+{
+	assert(data != NULL);
+
+	size_t adjusted = round_up(object_size);
+	if (used + adjusted > total) {
+		return NULL;
+	}
+
+	void *p = data + used;
+	used += adjusted;
+
+	return p;
+}
+
+void
+ar_free(void)
+{
+	assert(data != NULL);
+
+	memset(data, 0, total);
+	used = 0;
+}
+
+void
+ar_cleanup(void)
+{
+	assert(data != NULL);
+	free(data);
+	data = NULL;
+	total = 0;
+	used = 0;
+}
diff --git a/arena.h b/arena.h
new file mode 100644
index 0000000..43ce053
--- /dev/null
+++ b/arena.h
@@ -0,0 +1,18 @@
+#pragma once
+
+#ifndef ARENA_H_
+#define ARENA_H_
+
+int
+ar_setup(size_t total_size);
+
+void *
+ar_alloc(size_t object_size);
+
+void
+ar_free(void);
+
+void
+ar_cleanup(void);
+
+#endif
diff --git a/bench.c b/bench.c
index fb95c2e..966766b 100644
--- a/bench.c
+++ b/bench.c
@@ -1,12 +1,17 @@
+#include <assert.h>
 #include <stdio.h>
 #include <stdlib.h>
 #include <signal.h>
 #include <unistd.h>
 
+#include "arena.h"
 #include "cached.h"
 
 #define UNUSED __attribute__((unused))
 
+#define ALLOC_SIZE 4096
+#define ARENA_SIZE (1024*ALLOC_SIZE)
+
 static sig_atomic_t running;
 
 static void
@@ -51,6 +56,7 @@ bench_malloc(size_t allocs, size_t objsize)
 	while (running) {
 		for (size_t i = 0; i < allocs; i++) {
 			objs[i] = calloc(1, objsize);
+			assert(objs[i]);
 			count++;
 		}
 		for (size_t i = 0; i < allocs; i++) {
@@ -70,6 +76,7 @@ bench_ca_alloc(size_t allocs)
 	while (running) {
 		for (size_t i = 0; i < allocs; i++) {
 			objs[i] = ca_alloc();
+			assert(objs[i]);
 			count++;
 		}
 		for (size_t i = 0; i < allocs; i++) {
@@ -80,10 +87,28 @@ bench_ca_alloc(size_t allocs)
 	return count;
 }
 
+static size_t
+bench_ar_alloc(size_t allocs, size_t size)
+{
+	void *objs[allocs];
+	size_t count = 0;
+
+	while (running) {
+		for (size_t i = 0; i < allocs; i++) {
+			objs[i] = ar_alloc(size);
+			assert(objs[i]);
+			count++;
+		}
+		ar_free(); /* feels like cheating but it's not really */
+	}
+
+	return count;
+}
+
 static void
 bench_four(void)
 {
-	if (ca_setup(256, 4096) < 0) {
+	if (ca_setup(ALLOC_SIZE, 4096) < 0) {
 		panic("failed to setup cached allocator");
 	}
 
@@ -99,7 +124,7 @@ bench_four(void)
 static void
 bench_one(void)
 {
-	if (ca_setup(256, 1024) < 0) {
+	if (ca_setup(ALLOC_SIZE, 1024) < 0) {
 		panic("failed to setup cached allocator");
 	}
 
@@ -115,7 +140,7 @@ bench_one(void)
 static void
 bench_two(void)
 {
-	if (ca_setup(256, 16) < 0) {
+	if (ca_setup(ALLOC_SIZE, 16) < 0) {
 		panic("failed to setup cached allocator");
 	}
 
@@ -133,11 +158,27 @@ bench_three(void)
 {
 	set_alarm();
 
-	size_t allocs = bench_malloc(1024, 256);
+	size_t allocs = bench_malloc(1024, ALLOC_SIZE);
 
 	printf("%-12s\t%9zu allocs/second\n", "just_malloc", allocs);
 }
 
+static void
+bench_five(void)
+{
+	if (ar_setup(ARENA_SIZE) < 0) {
+		panic("failed to setup arena allocator");
+	}
+
+	set_alarm();
+
+	size_t allocs = bench_ar_alloc(1024, ALLOC_SIZE);
+
+	printf("%-12s\t%9zu allocs/second\n", "ar_alloc", allocs);
+
+	ar_cleanup();
+}
+
 int
 main(void)
 {
@@ -148,6 +189,8 @@ main(void)
 	bench_two();
 	bench_one();
 	bench_four();
+	puts("");
+	bench_five();
 
 	exit(EXIT_SUCCESS);
 }