summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorTavian Barnes <tavianator@tavianator.com>2014-05-30 14:31:18 -0400
committerTavian Barnes <tavianator@tavianator.com>2014-05-30 14:31:55 -0400
commit33addf7dd8d2ff29c0462705c9af3903b1a3ab1c (patch)
tree684923ba2fbdb5691181829e908f13e16de92540
parent7d4646404b96c970eb141289c2aa8b3937282842 (diff)
downloaddimension-33addf7dd8d2ff29c0462705c9af3903b1a3ab1c.tar.xz
pool: Add memory pool API.
-rw-r--r--libdimension/Makefile.am2
-rw-r--r--libdimension/dimension.h3
-rw-r--r--libdimension/dimension/pool.h60
-rw-r--r--libdimension/pool.c123
-rw-r--r--libdimension/tests/Makefile.am6
-rw-r--r--libdimension/tests/pool.c87
6 files changed, 279 insertions, 2 deletions
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 <tavianator@tavianator.com> *
+ * Copyright (C) 2009-2014 Tavian Barnes <tavianator@tavianator.com> *
* *
* This file is part of The Dimension Library. *
* *
@@ -77,6 +77,7 @@ typedef void dmnsn_free_fn(void *ptr);
#include <dimension/compiler.h>
#include <dimension/error.h>
#include <dimension/malloc.h>
+#include <dimension/pool.h>
#include <dimension/refcount.h>
#include <dimension/array.h>
#include <dimension/dictionary.h>
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 <tavianator@tavianator.com> *
+ * *
+ * 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 *
+ * <http://www.gnu.org/licenses/>. *
+ *************************************************************************/
+
+/**
+ * @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 <stddef.h> /* 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 <tavianator@tavianator.com> *
+ * *
+ * 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 *
+ * <http://www.gnu.org/licenses/>. *
+ *************************************************************************/
+
+/**
+ * @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 <tavianator@tavianator.com> ##
+## Copyright (C) 2009-2014 Tavian Barnes <tavianator@tavianator.com> ##
## ##
## 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 <tavianator@tavianator.com> *
+ * *
+ * 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 <http://www.gnu.org/licenses/>. *
+ *************************************************************************/
+
+/**
+ * @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);
+}