Big-ish rework and cleanup; a README even.

10 files changed, 183 insertions, 87 deletions

diff --git a/.clang-format b/.clang-format
index 1585e79..e4b788e 100644
--- a/.clang-format
+++ b/.clang-format
@@ -7,5 +7,6 @@ IndentCaseLabels: false
 
 AlwaysBreakAfterReturnType: All
 AlignAfterOpenBracket: DontAlign
+AlignTrailingComments: false
 ContinuationIndentWidth: 16
 SortIncludes: false
diff --git a/Makefile b/Makefile
index 3dbb76a..2b45044 100644
--- a/Makefile
+++ b/Makefile
@@ -1,19 +1,35 @@
-CFLAGS=-std=gnu11 -Wall -Wextra -Wpedantic -Og -g -D_DEFAULT_SOURCE \
-       -fsanitize=undefined -fsanitize=address
-LDFLAGS=-fsanitize=undefined -fsanitize=address
+CFLAGS+=-std=c11 -Wall -Wextra -Wpedantic
+CFLAGS+=-D_DEFAULT_SOURCE
 
 ALL=bench
 
-all: $(ALL)
+dev: CFLAGS+=-Og -g3
+dev: CFLAGS+=-fsanitize=undefined -fsanitize=address
+dev: LDFLAGS+=-fsanitize=undefined -fsanitize=address
+dev: $(ALL)
+
+prod: CFLAGS+=-O2 -s
+prod: LDFLAGS+=-s
+prod: $(ALL)
+
+musl: CC=musl-gcc
+musl: CFLAGS+=-Os -s
+musl: LDFLAGS+=-static -s
+musl: $(ALL)
 
 bench: bench.o arena.o cached.o pool.o
 
-clean:
-	$(RM) $(ALL) *.o
+bench.o: bench.c arena.h cached.h pool.h
 
-.PHONY:	all check clean format
+arena.o: arena.c arena.h
+cached.o: cached.c cached.h
+pool.o: pool.c pool.h
 
+clean:
+	$(RM) $(ALL) *.o
 check:
 	cppcheck --enable=all --std=c11 *.[ch]
 format:
 	clang-format -i *.[ch]
+
+.PHONY:	dev prod musl  check clean format
diff --git a/README.md b/README.md
new file mode 100644
index 0000000..07f3cef
--- /dev/null
+++ b/README.md
@@ -0,0 +1,17 @@
+# Simple Allocators
+
+If you're curious about simple memory allocation schemes in C, maybe you'll be
+able to learn a thing or two here.
+
+## Limitations
+
+I've tried to keep the code for these allocators as simple as possible, so if
+you want to use any of them "in production" you'll have to add a few more bells
+and whistles.
+For starters, real programs will require more than just one object size, so you
+will have to generalize the code for *cached* and *pool* allocators to support
+"allocator objects" of some kind.
+The *arena* allocator already supports "arbitrary" object sizes, but it has a
+fixed maximum capacity that may not be appropriate for all programs; code to
+"grow" the arena when necessary might be a good addition.
+Nothing here is thread-safe either, so you may need to throw in a lock or three.
diff --git a/arena.c b/arena.c
index 9e15c2a..bf78edc 100644
--- a/arena.c
+++ b/arena.c
@@ -1,47 +1,49 @@
+#include "arena.h"
+
 #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 largest scalar type. Before max_align_t was added in C11, code
+ * like this usually declared a union of several long-ish types, resulting in a
+ * suitable sizeof result. Hopefully anyway. This is cleaner.
+ */
+#define ALIGN (sizeof(max_align_t))
 
-/* 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");
+/*
+ * We need this property below to round up to multiples of `ALIGN`. (Of course
+ * it's almost certainly true anyway.)
+ */
+static_assert(ALIGN && !(ALIGN & (ALIGN - 1)), "ALIGN not a power of two");
 
-static unsigned char *data;
-static size_t total;
-static size_t used;
+static unsigned char *arena; /* memory allocated for the arena */
+static size_t capacity; /* capacity of the arena in bytes */
+static size_t used; /* bytes used so far (from beginning) */
 
 /*
- * round up to nearest multiple of ALIGN
+ * Round up `minimum` to nearest multiple of ALIGN.
  */
-static size_t
+static inline size_t
 round_up(size_t minimum)
 {
 	return (minimum + ALIGN - 1) & ~(ALIGN - 1);
 }
 
 int
-ar_setup(size_t total_size)
+ar_setup(size_t arena_size)
 {
-	assert(data == NULL);
+	assert(!arena);
 
-	size_t adjusted = round_up(total_size);
+	size_t adjusted = round_up(arena_size);
 
 	void *p = calloc(1, adjusted);
 	if (p == NULL) {
 		return -1;
 	}
 
-	data = p;
-	total = adjusted;
+	arena = p;
+	capacity = adjusted;
 
 	return 0;
 }
@@ -49,14 +51,14 @@ ar_setup(size_t total_size)
 void *
 ar_alloc(size_t object_size)
 {
-	assert(data != NULL);
+	assert(arena);
 
-	size_t adjusted = round_up(object_size);
-	if (used + adjusted > total) {
-		return NULL;
+	size_t adjusted = round_up(object_size); /* keep `used` aligned */
+	if (used + adjusted > capacity) {
+		return NULL; /* out of space */
 	}
 
-	void *p = data + used;
+	void *p = arena + used;
 	used += adjusted;
 
 	return p;
@@ -65,18 +67,20 @@ ar_alloc(size_t object_size)
 void
 ar_free(void)
 {
-	assert(data != NULL);
+	assert(arena);
 
-	memset(data, 0, total);
+	memset(arena, 0, capacity);
 	used = 0;
 }
 
 void
 ar_cleanup(void)
 {
-	assert(data != NULL);
-	free(data);
-	data = NULL;
-	total = 0;
+	assert(arena);
+
+	free(arena);
+	arena = NULL;
+
+	capacity = 0;
 	used = 0;
 }
diff --git a/arena.h b/arena.h
index 43ce053..5bc4c69 100644
--- a/arena.h
+++ b/arena.h
@@ -3,15 +3,34 @@
 #ifndef ARENA_H_
 #define ARENA_H_
 
+#include <stddef.h>
+
+/**
+ * Create arena holding up to `arena_size` bytes.
+ * Return 0 on success, <0 on failure.
+ */
 int
-ar_setup(size_t total_size);
+ar_setup(size_t arena_size);
 
+/**
+ * Allocate `object_size` bytes from the arena.
+ * Return NULL on failure.
+ */
 void *
 ar_alloc(size_t object_size);
 
+/**
+ * Free all allocations made in the arena.
+ * Invalidates all pointers you may still be holding.
+ * The arena still exists, ready for `ar_alloc` calls.
+ */
 void
 ar_free(void);
 
+/**
+ * Destroy the arena, freeing all memory allocated in `ar_setup`.
+ * Invalidates all pointers you may still be holding.
+ */
 void
 ar_cleanup(void);
 
diff --git a/bench.c b/bench.c
index d8eeaf8..15cc5c1 100644
--- a/bench.c
+++ b/bench.c
@@ -1,19 +1,21 @@
+#include "arena.h"
+#include "cached.h"
+#include "pool.h"
+
 #include <assert.h>
 #include <stdio.h>
 #include <stdlib.h>
 #include <signal.h>
 #include <unistd.h>
 
-#include "arena.h"
-#include "cached.h"
-#include "pool.h"
-
 #define UNUSED __attribute__((unused))
 
-#define ALLOC_SIZE 4096
+#define ALLOC_SIZE (4096)
 #define ARENA_SIZE (1024 * ALLOC_SIZE)
+#define POOL_SIZE (1024)
+#define MEASURE_SECONDS (1)
 
-static sig_atomic_t running;
+static volatile sig_atomic_t running;
 
 static void
 panic(const char *msg)
@@ -45,7 +47,7 @@ static void
 set_alarm(void)
 {
 	running = 1;
-	alarm(1);
+	alarm(MEASURE_SECONDS);
 }
 
 static size_t
@@ -137,7 +139,8 @@ bench_four(void)
 
 	size_t allocs = bench_ca_alloc(1024);
 
-	printf("%-12s\t%9zu allocs/second\n", "huge_cache", allocs);
+	printf("%-12s\t%9zu allocs/second\n", "huge_cache",
+			allocs / MEASURE_SECONDS);
 
 	ca_cleanup();
 }
@@ -153,7 +156,8 @@ bench_one(void)
 
 	size_t allocs = bench_ca_alloc(1024);
 
-	printf("%-12s\t%9zu allocs/second\n", "large_cache", allocs);
+	printf("%-12s\t%9zu allocs/second\n", "large_cache",
+			allocs / MEASURE_SECONDS);
 
 	ca_cleanup();
 }
@@ -169,7 +173,8 @@ bench_two(void)
 
 	size_t allocs = bench_ca_alloc(1024);
 
-	printf("%-12s\t%9zu allocs/second\n", "small_cache", allocs);
+	printf("%-12s\t%9zu allocs/second\n", "small_cache",
+			allocs / MEASURE_SECONDS);
 
 	ca_cleanup();
 }
@@ -181,7 +186,8 @@ bench_three(void)
 
 	size_t allocs = bench_malloc(1024, ALLOC_SIZE);
 
-	printf("%-12s\t%9zu allocs/second\n", "just_malloc", allocs);
+	printf("%-12s\t%9zu allocs/second\n", "just_malloc",
+			allocs / MEASURE_SECONDS);
 }
 
 static void
@@ -195,7 +201,8 @@ bench_five(void)
 
 	size_t allocs = bench_ar_alloc(1024, ALLOC_SIZE);
 
-	printf("%-12s\t%9zu allocs/second\n", "ar_alloc", allocs);
+	printf("%-12s\t%9zu allocs/second\n", "ar_alloc",
+			allocs / MEASURE_SECONDS);
 
 	ar_cleanup();
 }
@@ -203,7 +210,7 @@ bench_five(void)
 static void
 bench_six(void)
 {
-	if (pl_setup(4096, 1024) < 0) {
+	if (pl_setup(POOL_SIZE, ALLOC_SIZE) < 0) {
 		panic("failed to setup pool allocator");
 	}
 
@@ -211,7 +218,8 @@ bench_six(void)
 
 	size_t allocs = bench_pl_alloc(1024);
 
-	printf("%-12s\t%9zu allocs/second\n", "pl_alloc", allocs);
+	printf("%-12s\t%9zu allocs/second\n", "pl_alloc",
+			allocs / MEASURE_SECONDS);
 
 	pl_cleanup();
 }
diff --git a/cached.c b/cached.c
index 8174cda..c587ec5 100644
--- a/cached.c
+++ b/cached.c
@@ -1,9 +1,9 @@
+#include "cached.h"
+
 #include <assert.h>
 #include <stdlib.h>
 #include <string.h>
 
-#include "cached.h"
-
 static size_t object_size;
 static size_t max_cached;
 static size_t num_cached;
@@ -18,7 +18,7 @@ ca_setup(size_t osize, size_t csize)
 	}
 
 	cache = calloc(csize, sizeof(*cache));
-	if (cache == NULL) {
+	if (!cache) {
 		return -2;
 	}
 
@@ -32,7 +32,7 @@ ca_setup(size_t osize, size_t csize)
 void *
 ca_alloc(void)
 {
-	assert(cache != NULL);
+	assert(cache);
 
 	if (num_cached > 0) {
 		void *object = cache[--num_cached];
@@ -45,9 +45,9 @@ ca_alloc(void)
 void
 ca_free(void *object)
 {
-	assert(cache != NULL);
+	assert(cache);
 
-	if (object == NULL) {
+	if (!object) {
 		/* free(3) also does nothing for NULL */
 		return;
 	}
diff --git a/cached.h b/cached.h
index 32ca61c..454bcc3 100644
--- a/cached.h
+++ b/cached.h
@@ -3,15 +3,31 @@
 #ifndef CACHED_H_
 #define CACHED_H_
 
+#include <stddef.h>
+
+/**
+ * Create cache of size `slots` for allocating chunks of `object_size` bytes.
+ * Return 0 on success, <0 on failure.
+ */
 int
-ca_setup(size_t object_size, size_t cache_size);
+ca_setup(size_t object_size, size_t slots);
 
+/**
+ * Allocate a chunk of memory.
+ * Return NULL on failure.
+ */
 void *
 ca_alloc(void);
 
+/**
+ * Free a chunk of memory obtained from `ca_alloc`.
+ */
 void
 ca_free(void *object);
 
+/**
+ * Destroy the cache, freeing all memory still allocated.
+ */
 void
 ca_cleanup(void);
 
diff --git a/pool.c b/pool.c
index d0cee9b..649a9e4 100644
--- a/pool.c
+++ b/pool.c
@@ -1,37 +1,35 @@
+#include "pool.h"
+
 #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;
+static void *pool; /* the actual pool of memory */
+static size_t blocks; /* number of blocks */
+static size_t block_size; /* size of one block */
 
-/* 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;
+static uint64_t *used; /* bitmap to track allocated blocks */
+static const size_t BITS = sizeof(*used) * CHAR_BIT; /* bits per slot */
 
-/* Allocate a bitmap with at least `blocks` bits. */
+/*
+ * Allocate a bitmap with at least `size` bits.
+ * Returns NULL on failure.
+ */
 static uint64_t *
-bitmap(size_t blocks)
+bitmap(size_t size)
 {
-	assert(blocks > 0);
+	assert(size > 0);
 
-	const size_t slots = (blocks / BITS) + 1;
+	const size_t slots = (size / BITS) + 1;
 
-	uint64_t *p = calloc(1, sizeof(*p) * slots);
+	uint64_t *p = calloc(slots, sizeof(*p));
 	return p; /* this is fine */
 }
 
 /* Mark given `block` as free. */
-static void
+static inline void
 bitmap_free(size_t block)
 {
 	assert(block < blocks);
@@ -43,7 +41,7 @@ bitmap_free(size_t block)
 }
 
 /* Mark given `block` as used. */
-static void
+static inline void
 bitmap_used(size_t block)
 {
 	assert(block < blocks);
@@ -71,7 +69,7 @@ find_zero(const uint64_t bits)
 }
 
 static inline uint64_t
-log2(const uint64_t x)
+ulog2(const uint64_t x)
 {
 	return ((BITS - 1) - __builtin_clzl(x)); /* count leading zeros */
 }
@@ -83,24 +81,24 @@ 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 i * BITS + ulog2(free);
 		}
 	}
 	return -1;
 }
 
 int
-pl_setup(size_t object_size, size_t pool_size)
+pl_setup(size_t pool_size, size_t object_size)
 {
 	assert(object_size > 0 && pool_size > 0);
 
 	void *p = calloc(pool_size, object_size);
-	if (p == NULL) {
+	if (!p) {
 		return -1;
 	}
 
 	uint64_t *q = bitmap(pool_size);
-	if (q == NULL) {
+	if (!q) {
 		free(p);
 		return -2;
 	}
@@ -137,7 +135,7 @@ pl_free(void *object)
 {
 	assert(pool);
 
-	if (object == NULL) {
+	if (!object) {
 		/* free(3) also does nothing for NULL */
 		return;
 	}
diff --git a/pool.h b/pool.h
index d678598..fa34cab 100644
--- a/pool.h
+++ b/pool.h
@@ -3,15 +3,32 @@
 #ifndef POOL_H_
 #define POOL_H_
 
+#include <stddef.h>
+
+/**
+ * Create pool with `slots` chunks of `object_size` bytes.
+ * Return 0 on success, <0 on failure.
+ */
 int
-pl_setup(size_t object_size, size_t pool_size);
+pl_setup(size_t slots, size_t object_size);
 
+/**
+ * Allocate one chunk from the pool.
+ * Return NULL on failure.
+ */
 void *
 pl_alloc(void);
 
+/**
+ * Free a chunk of memory obtained from `pl_alloc`.
+ */
 void
 pl_free(void *object);
 
+/**
+ * Destroy the pool, freeing all memory allocated in `pl_setup`.
+ * Invalidates all pointers you may still be holding.
+ */
 void
 pl_cleanup(void);