From 8d90ee5fdba7ae0543045753028887945c4cdf5d Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Thu, 6 Sep 2007 16:17:42 +0200 Subject: [PATCH] Added a simple allocator for fixed-size objects. --- lib/Makefile | 5 ++- lib/eltpool.c | 100 +++++++++++++++++++++++++++++++++++++++++++++++ lib/eltpool.h | 62 +++++++++++++++++++++++++++++ lib/eltpool.test | 4 ++ 4 files changed, 169 insertions(+), 2 deletions(-) create mode 100644 lib/eltpool.c create mode 100644 lib/eltpool.h create mode 100644 lib/eltpool.test diff --git a/lib/Makefile b/lib/Makefile index fe3d0ff0..c204d6e6 100644 --- a/lib/Makefile +++ b/lib/Makefile @@ -10,7 +10,7 @@ endif LIBUCW_MODS= \ threads \ - alloc alloc_str realloc bigalloc mempool mempool-str mempool-fmt \ + alloc alloc_str realloc bigalloc mempool mempool-str mempool-fmt eltpool \ mmap pagecache partmap hashfunc \ lists slists simple-lists sorter bitsig \ log log-file proctitle \ @@ -101,7 +101,7 @@ $(o)/lib/kmp-test: $(o)/lib/kmp-test.o $(LIBUCW) $(LIBCHARSET) $(o)/lib/ipaccess-test: $(o)/lib/ipaccess-test.o $(LIBUCW) TESTS+=$(addprefix $(o)/lib/,regex.test unicode-utf8.test hash-test.test mempool.test stkstring.test \ - slists.test kmp-test.test bbuf.test getopt.test fastbuf.test) + slists.test kmp-test.test bbuf.test getopt.test fastbuf.test eltpool.test) $(o)/lib/regex.test: $(o)/lib/regex-t $(o)/lib/unicode-utf8.test: $(o)/lib/unicode-utf8-t @@ -114,6 +114,7 @@ $(o)/lib/kmp-test.test: $(o)/lib/kmp-test $(o)/lib/bbuf.test: $(o)/lib/bbuf-t $(o)/lib/getopt.test: $(o)/lib/getopt-t $(o)/lib/fastbuf.test: $(o)/lib/fb-file-t $(o)/lib/fb-grow-t $(o)/lib/fb-pool-t +$(o)/lib/eltpool.test: $(o)/lib/eltpool-t ifdef CONFIG_UCW_THREADS TESTS+=$(addprefix $(o)/lib/,asio.test) diff --git a/lib/eltpool.c b/lib/eltpool.c new file mode 100644 index 00000000..f82de845 --- /dev/null +++ b/lib/eltpool.c @@ -0,0 +1,100 @@ +/* + * UCW Library -- Fast Allocator for Fixed-Size Elements + * + * (c) 2007 Martin Mares + * + * This software may be freely distributed and used according to the terms + * of the GNU Lesser General Public License. + */ + +/* + * This allocator is optimized for intensive allocation and freeing of small + * blocks of identical sizes. System memory is allocated by multiples of the + * page size and it is returned back only when the whole eltpool is deleted. + * + * In the future, we can add returning of memory to the system and also cache + * coloring like in the SLAB allocator used in the Linux kernel. + */ + +#undef LOCAL_DEBUG + +#include "lib/lib.h" +#include "lib/eltpool.h" + +struct eltpool * +ep_new(uns elt_size, uns elts_per_chunk) +{ + struct eltpool *pool = xmalloc_zero(sizeof(*pool)); + pool->elt_size = ALIGN_TO(MAX(elt_size, sizeof(struct eltpool_free)), CPU_STRUCT_ALIGN); + pool->chunk_size = CPU_PAGE_SIZE; + while (pool->elt_size * elts_per_chunk + sizeof(struct eltpool_chunk) > pool->chunk_size) + pool->chunk_size *= 2; + pool->elts_per_chunk = (pool->chunk_size - sizeof(struct eltpool_chunk)) / pool->elt_size; + DBG("ep_new(): got elt_size=%d, epc=%d; used chunk_size=%d, epc=%d", elt_size, elts_per_chunk, pool->chunk_size, pool->elts_per_chunk); + return pool; +} + +void +ep_delete(struct eltpool *pool) +{ + struct eltpool_chunk *ch; + while (ch = pool->first_chunk) + { + pool->first_chunk = ch->next; + page_free(ch, pool->chunk_size); + } + xfree(pool); +} + +void * +ep_alloc_slow(struct eltpool *pool) +{ + struct eltpool_chunk *ch = page_alloc(pool->chunk_size); + void *p = (void *)(ch+1); + for (uns i=1; ielts_per_chunk; i++) + { + struct eltpool_free *f = p; + f->next = pool->first_free; + pool->first_free = f; + p += pool->elt_size; + } + ch->next = pool->first_chunk; + pool->first_chunk = ch; + return p; +} + +#ifdef TEST + +#include +#include "lib/clists.h" + +struct argh { + cnode n; + byte x[1]; +} PACKED; + +int main(void) +{ + struct eltpool *ep = ep_new(sizeof(struct argh), 64); + clist l; + clist_init(&l); + for (uns i=0; i<65536; i++) + { + struct argh *a = ep_alloc(ep); + if (i % 3) + clist_add_tail(&l, &a->n); + else + clist_add_head(&l, &a->n); + if (!(i % 5)) + { + a = clist_head(&l); + clist_remove(&a->n); + ep_free(ep, a); + } + } + ep_delete(ep); + puts("OK"); + return 0; +} + +#endif diff --git a/lib/eltpool.h b/lib/eltpool.h new file mode 100644 index 00000000..a682405c --- /dev/null +++ b/lib/eltpool.h @@ -0,0 +1,62 @@ +/* + * UCW Library -- Fast Allocator for Fixed-Size Elements + * + * (c) 2007 Martin Mares + * + * This software may be freely distributed and used according to the terms + * of the GNU Lesser General Public License. + */ + +#ifndef _UCW_ELTPOOL_H +#define _UCW_ELTPOOL_H + +struct eltpool { + struct eltpool_chunk *first_chunk; + struct eltpool_free *first_free; + uns elt_size; + uns chunk_size; + uns elts_per_chunk; +}; + +struct eltpool_chunk { + struct eltpool_chunk *next; + /* Chunk data continue here */ +}; + +struct eltpool_free { + struct eltpool_free *next; +}; + +struct eltpool *ep_new(uns elt_size, uns elts_per_chunk); +void ep_delete(struct eltpool *pool); +void *ep_alloc_slow(struct eltpool *pool); + +static inline void * +ep_alloc(struct eltpool *pool) +{ +#ifdef CONFIG_FAKE_ELTPOOL + return xmalloc(pool->elt_size); +#else + struct eltpool_free *elt; + if (elt = pool->first_free) + pool->first_free = elt->next; + else + elt = ep_alloc_slow(pool); + return elt; +#endif +} + +static inline void +ep_free(struct eltpool *pool, void *p) +{ +#ifdef CONFIG_FAKE_ELTPOOL + (void) pool; + xfree(p); +#else + struct eltpool_free *elt = p; + elt->next = pool->first_free; + pool->first_free = elt; +#endif +} + +#endif diff --git a/lib/eltpool.test b/lib/eltpool.test new file mode 100644 index 00000000..85bed694 --- /dev/null +++ b/lib/eltpool.test @@ -0,0 +1,4 @@ +# Tests for eltpools + +Run: ../obj/lib/eltpool-t +Out: OK -- 2.39.5