pool: Add memory pool API.

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);
+}