aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
-rw-r--r--.clang-format1
-rw-r--r--Makefile30
-rw-r--r--README.md17
-rw-r--r--arena.c68
-rw-r--r--arena.h21
-rw-r--r--bench.c36
-rw-r--r--cached.c12
-rw-r--r--cached.h18
-rw-r--r--pool.c48
-rw-r--r--pool.h19
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);