From 33addf7dd8d2ff29c0462705c9af3903b1a3ab1c Mon Sep 17 00:00:00 2001 From: Tavian Barnes Date: Fri, 30 May 2014 14:31:18 -0400 Subject: pool: Add memory pool API. --- libdimension/Makefile.am | 2 + libdimension/dimension.h | 3 +- libdimension/dimension/pool.h | 60 ++++++++++++++++++++ libdimension/pool.c | 123 +++++++++++++++++++++++++++++++++++++++++ libdimension/tests/Makefile.am | 6 +- libdimension/tests/pool.c | 87 +++++++++++++++++++++++++++++ 6 files changed, 279 insertions(+), 2 deletions(-) create mode 100644 libdimension/dimension/pool.h create mode 100644 libdimension/pool.c create mode 100644 libdimension/tests/pool.c diff --git a/libdimension/Makefile.am b/libdimension/Makefile.am index 06fa7b8..fb14a2e 100644 --- a/libdimension/Makefile.am +++ b/libdimension/Makefile.am @@ -54,6 +54,7 @@ nobase_include_HEADERS = dimension.h \ dimension/pigments.h \ dimension/png.h \ dimension/polynomial.h \ + dimension/pool.h \ dimension/ray_trace.h \ dimension/refcount.h \ dimension/scene.h \ @@ -101,6 +102,7 @@ libdimension_la_SOURCES = $(nobase_include_HEADERS) \ profile.h \ point_light.c \ polynomial.c \ + pool.c \ prtree.c \ prtree.h \ ray_trace.c \ diff --git a/libdimension/dimension.h b/libdimension/dimension.h index 708cd8a..d9cfff9 100644 --- a/libdimension/dimension.h +++ b/libdimension/dimension.h @@ -1,5 +1,5 @@ /************************************************************************* - * Copyright (C) 2009-2011 Tavian Barnes * + * Copyright (C) 2009-2014 Tavian Barnes * * * * This file is part of The Dimension Library. * * * @@ -77,6 +77,7 @@ typedef void dmnsn_free_fn(void *ptr); #include #include #include +#include #include #include #include diff --git a/libdimension/dimension/pool.h b/libdimension/dimension/pool.h new file mode 100644 index 0000000..9b6574a --- /dev/null +++ b/libdimension/dimension/pool.h @@ -0,0 +1,60 @@ +/************************************************************************* + * Copyright (C) 2014 Tavian Barnes * + * * + * This file is part of The Dimension Library. * + * * + * The Dimension Library is free software; you can redistribute it and/ * + * or modify it under the terms of the GNU Lesser General Public License * + * as published by the Free Software Foundation; either version 3 of the * + * License, or (at your option) any later version. * + * * + * The Dimension Library is distributed in the hope that it will be * + * useful, but WITHOUT ANY WARRANTY; without even the implied warranty * + * of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU * + * Lesser General Public License for more details. * + * * + * You should have received a copy of the GNU Lesser General Public * + * License along with this program. If not, see * + * . * + *************************************************************************/ + +/** + * @file + * Memory pools. Rather than more complicated garbage collection methods like + * reference counting, objects are allocated out of pools which are freed all at + * once once a scene is rendered (for example). + */ + +#include /* For size_t */ + +/* Forward-declare dmnsn_pool. */ +typedef struct dmnsn_pool dmnsn_pool; + +/** + * Create a new memory pool. + * @return The new pool. + */ +dmnsn_pool *dmnsn_new_pool(void); + +/** + * Allocate some memory from a pool. + * @param[in] pool The memory pool to allocate from. + * @param[in] size The size of the memory block to allocate. + * @param[in] callback An optional callback to invoke before the memory is freed. + * @return The allocated memory area. + */ +void *dmnsn_pool_alloc(dmnsn_pool *pool, size_t size, dmnsn_callback_fn *callback); + +/** + * Allocate some memory from a pool. + * @param[in] pool The memory pool to allocate from. + * @param[in] type The type of the memory block to allocate. + * @return The allocated memory area. + */ +#define DMNSN_POOL_ALLOC(pool, type) ((type *)dmnsn_pool_alloc((pool), sizeof(type), NULL)) + +/** + * Free a memory pool and all associated allocations. + * @param[in] pool The memory pool to free. + */ +void dmnsn_delete_pool(dmnsn_pool *pool); diff --git a/libdimension/pool.c b/libdimension/pool.c new file mode 100644 index 0000000..57c357a --- /dev/null +++ b/libdimension/pool.c @@ -0,0 +1,123 @@ +/************************************************************************* + * Copyright (C) 2014 Tavian Barnes * + * * + * This file is part of The Dimension Library. * + * * + * The Dimension Library is free software; you can redistribute it and/ * + * or modify it under the terms of the GNU Lesser General Public License * + * as published by the Free Software Foundation; either version 3 of the * + * License, or (at your option) any later version. * + * * + * The Dimension Library is distributed in the hope that it will be * + * useful, but WITHOUT ANY WARRANTY; without even the implied warranty * + * of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU * + * Lesser General Public License for more details. * + * * + * You should have received a copy of the GNU Lesser General Public * + * License along with this program. If not, see * + * . * + *************************************************************************/ + +/** + * @file + * Memory pool implementation. + */ + +#include "dimension-internal.h" + +/** A single allocation and associated destructor. */ +typedef struct dmnsn_allocation { + void *ptr; + dmnsn_callback_fn *callback; +} dmnsn_allocation; + +/** Number of pointers per block, we want a block to fit in a single page. */ +#define DMNSN_POOL_BLOCK_SIZE ((4096 - 4*sizeof(void *))/sizeof(dmnsn_allocation)) + +/** A single block in a thread pool. */ +typedef struct dmnsn_pool_block { + /** Current index into allocs[]. */ + size_t i; + /** All allocations in the current block. */ + dmnsn_allocation allocs[DMNSN_POOL_BLOCK_SIZE]; + /** Tail pointer to the previous block in the global chain. */ + struct dmnsn_pool_block *prev; +} dmnsn_pool_block; + +/** dmnsn_pool implementation. */ +struct dmnsn_pool { + /** Thread-local block. */ + pthread_key_t thread_block; + + /** Global chain of pools. */ + dmnsn_pool_block *chain; + /** Mutex guarding the global chain. */ + pthread_mutex_t mutex; +}; + +dmnsn_pool * +dmnsn_new_pool(void) +{ + dmnsn_pool *pool = DMNSN_MALLOC(dmnsn_pool); + dmnsn_key_create(&pool->thread_block, NULL); + pool->chain = NULL; + dmnsn_initialize_mutex(&pool->mutex); + return pool; +} + +void * +dmnsn_pool_alloc(dmnsn_pool *pool, size_t size, dmnsn_callback_fn *callback) +{ + dmnsn_pool_block *old_block = pthread_getspecific(pool->thread_block); + + dmnsn_pool_block *new_block = old_block; + if (dmnsn_unlikely(!old_block || old_block->i == DMNSN_POOL_BLOCK_SIZE)) { + new_block = DMNSN_MALLOC(dmnsn_pool_block); + new_block->i = 0; + } + + dmnsn_allocation *alloc = new_block->allocs + new_block->i; + void *result = alloc->ptr = dmnsn_malloc(size); + alloc->callback = callback; + ++new_block->i; + + if (dmnsn_unlikely(new_block != old_block)) { + dmnsn_setspecific(pool->thread_block, new_block); + + dmnsn_lock_mutex(&pool->mutex); + new_block->prev = pool->chain; + pool->chain = new_block; + dmnsn_unlock_mutex(&pool->mutex); + } + + return result; +} + +void +dmnsn_delete_pool(dmnsn_pool *pool) +{ + if (!pool) { + return; + } + + dmnsn_pool_block *block = pool->chain; + while (block) { + /* Free all the allocations in reverse order */ + for (size_t i = block->i; i-- > 0;) { + dmnsn_allocation *alloc = block->allocs + i; + if (alloc->callback) { + alloc->callback(alloc->ptr); + } + dmnsn_free(alloc->ptr); + } + + /* Free the block itself and go to the previous one */ + dmnsn_pool_block *saved = block; + block = block->prev; + dmnsn_free(saved); + } + + dmnsn_destroy_mutex(&pool->mutex); + dmnsn_key_delete(pool->thread_block); + dmnsn_free(pool); +} diff --git a/libdimension/tests/Makefile.am b/libdimension/tests/Makefile.am index bcfa2c6..5238e7b 100644 --- a/libdimension/tests/Makefile.am +++ b/libdimension/tests/Makefile.am @@ -1,5 +1,5 @@ ########################################################################### -## Copyright (C) 2009-2012 Tavian Barnes ## +## Copyright (C) 2009-2014 Tavian Barnes ## ## ## ## This file is part of The Dimension Build Suite. ## ## ## @@ -26,6 +26,7 @@ check_PROGRAMS = warning.test \ warning-as-error.test \ error.test \ custom-error-fn.test \ + pool.test \ refcount.test \ dictionary.test \ polynomial.test \ @@ -74,6 +75,9 @@ error_test_LDADD = libdimension-tests.la custom_error_fn_test_SOURCES = custom-error-fn.c custom_error_fn_test_LDADD = libdimension-tests.la +pool_test_SOURCES = pool.c +pool_test_LDADD = libdimension-unit-test.la + refcount_test_SOURCES = refcount.c refcount_test_LDADD = libdimension-unit-test.la diff --git a/libdimension/tests/pool.c b/libdimension/tests/pool.c new file mode 100644 index 0000000..68ecfae --- /dev/null +++ b/libdimension/tests/pool.c @@ -0,0 +1,87 @@ +/************************************************************************* + * Copyright (C) 2014 Tavian Barnes * + * * + * This file is part of The Dimension Test Suite. * + * * + * The Dimension Test Suite is free software; you can redistribute it * + * and/or modify it under the terms of the GNU General Public License as * + * published by the Free Software Foundation; either version 3 of the * + * License, or (at your option) any later version. * + * * + * The Dimension Test Suite is distributed in the hope that it will be * + * useful, but WITHOUT ANY WARRANTY; without even the implied warranty * + * of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU * + * General Public License for more details. * + * * + * You should have received a copy of the GNU General Public License * + * along with this program. If not, see . * + *************************************************************************/ + +/** + * @file + * Tests for memory pools. + */ + +#include "../dimension-internal.h" +#include "tests.h" +#include "../future.c" +#include "../threads.c" + +static dmnsn_pool *pool; + +DMNSN_TEST_SETUP(pool) +{ + pool = dmnsn_new_pool(); +} + +DMNSN_TEST_TEARDOWN(pool) +{ + dmnsn_delete_pool(pool); +} + +DMNSN_TEST(pool, simple) +{ + for (int i = 0; i < 10000; ++i) { + int *p = DMNSN_POOL_ALLOC(pool, int); + *p = i; + } + + /* Leak checking will tell us if something bad happened */ +} + +static int counter = 0; + +static void +callback(void *ptr) +{ + ++counter; +} + +DMNSN_TEST(pool, callback) +{ + dmnsn_pool_alloc(pool, sizeof(int), NULL); + dmnsn_pool_alloc(pool, sizeof(int), callback); + dmnsn_pool_alloc(pool, sizeof(int), callback); + dmnsn_pool_alloc(pool, sizeof(int), NULL); + + dmnsn_delete_pool(pool); + pool = NULL; + + ck_assert_int_eq(counter, 2); +} + +static int +alloc_thread(void *ptr, unsigned int thread, unsigned int nthreads) +{ + for (unsigned int i = thread; i < 10000; i += nthreads) { + int *p = DMNSN_POOL_ALLOC(pool, int); + *p = i; + } + return 0; +} + +DMNSN_TEST(pool, threaded) +{ + int ret = dmnsn_execute_concurrently(NULL, alloc_thread, NULL, 64); + ck_assert_int_eq(ret, 0); +} -- cgit v1.2.3