From f94fcf7052d45be9842bca09d813b45e3da8d0c3 Mon Sep 17 00:00:00 2001 From: "Peter H. Froehlich" Date: Fri, 24 May 2019 00:40:13 +0200 Subject: Added pool allocator. --- Makefile | 2 +- bench.c | 41 +++++++++++++++- pool.c | 164 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ pool.h | 18 +++++++ 4 files changed, 223 insertions(+), 2 deletions(-) create mode 100644 pool.c create mode 100644 pool.h 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; @@ -87,6 +88,26 @@ bench_ca_alloc(size_t allocs) return count; } +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) { @@ -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 +#include +#include +#include +#include + +#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 -- cgit 1.4.1-2-gfad0