From 723019f727ce53b392389bdadcc1701ae47e6a14 Mon Sep 17 00:00:00 2001 From: David Oberhollenzer Date: Sun, 7 Mar 2021 18:15:50 +0100 Subject: Optionally use a pool allocator for rb-tree nodes This commit restructures the rbtree code to optionally use a pool allocator for the nodes. The option is made depenend on the presence of a pre-processor flag. To the configure script is added an option to enable/disable the use of custom allocators. It makes sense to still allow the malloc/free based routes for better ASAN based instrumentation. Signed-off-by: David Oberhollenzer --- Makefile.am | 5 +++++ configure.ac | 9 +++++++++ include/rbtree.h | 5 +++++ lib/sqfs/Makemodule.am | 4 ++++ lib/util/Makemodule.am | 5 ++++- lib/util/rbtree.c | 46 +++++++++++++++++++++++++++++++++++++++++----- 6 files changed, 68 insertions(+), 6 deletions(-) diff --git a/Makefile.am b/Makefile.am index 99e90a0..5326d2d 100644 --- a/Makefile.am +++ b/Makefile.am @@ -7,6 +7,11 @@ if WITH_LZO AM_CPPFLAGS += -DWITH_LZO endif +if CUSTOM_ALLOC +else +AM_CPPFLAGS += -DNO_CUSTOM_ALLOC +endif + noinst_LTLIBRARIES = noinst_LIBRARIES = noinst_PROGRAMS = diff --git a/configure.ac b/configure.ac index 32ae8ba..95750a8 100644 --- a/configure.ac +++ b/configure.ac @@ -107,6 +107,11 @@ AC_ARG_WITH([tools], [Only build libsquashfs, do not build the tools.])], [], [with_tools="yes"]) +AC_ARG_ENABLE([custom-alloc], + [AS_HELP_STRING([--disable-custom-alloc], + [Do not used any custom allocators.])], + [], [enable_custom_alloc="yes"]) + AC_ARG_ENABLE([corpora-tests], [AS_HELP_STRING([--enable-corpora-tests], [Perform corpora based reproducability tests.])], @@ -268,6 +273,8 @@ AC_CHECK_FUNCS([strndup getsubopt]) ##### generate output ##### +AM_CONDITIONAL([CUSTOM_ALLOC], [test "x$enable_custom_alloc" = "xyes"]) + AC_CONFIG_HEADERS([config.h]) AC_CONFIG_FILES([lib/sqfs/libsquashfs1.pc]) AC_CONFIG_FILES([Doxyfile]) @@ -303,6 +310,8 @@ AC_MSG_RESULT([ SELinux support: ${with_selinux} Using pthreads: ${with_pthread} + Custom allocators: ${enable_custom_alloc} + Building tools: ${with_tools} Doxygen found: ${with_doxygen} diff --git a/include/rbtree.h b/include/rbtree.h index b1ddcd2..aac175b 100644 --- a/include/rbtree.h +++ b/include/rbtree.h @@ -9,6 +9,7 @@ #include "config.h" #include "sqfs/predef.h" +#include "mempool.h" #include "compat.h" #include @@ -26,6 +27,10 @@ typedef struct rbtree_node_t { typedef struct rbtree_t { rbtree_node_t *root; +#ifndef NO_CUSTOM_ALLOC + mem_pool_t *pool; +#endif + int (*key_compare)(const void *ctx, const void *lhs, const void *hrs); diff --git a/lib/sqfs/Makemodule.am b/lib/sqfs/Makemodule.am index 9702b76..b770fd4 100644 --- a/lib/sqfs/Makemodule.am +++ b/lib/sqfs/Makemodule.am @@ -44,6 +44,10 @@ libsquashfs_la_SOURCES += lib/util/hash_table.c include/hash_table.h libsquashfs_la_SOURCES += lib/util/rbtree.c include/rbtree.h libsquashfs_la_SOURCES += lib/util/array.c include/array.h +if CUSTOM_ALLOC +libsquashfs_la_SOURCES += lib/util/mempool.c include/mempool.h +endif + if WINDOWS libsquashfs_la_SOURCES += lib/sqfs/win32/io_file.c libsquashfs_la_CFLAGS += -DWINVER=0x0600 -D_WIN32_WINNT=0x0600 diff --git a/lib/util/Makemodule.am b/lib/util/Makemodule.am index 80bec4f..39352f4 100644 --- a/lib/util/Makemodule.am +++ b/lib/util/Makemodule.am @@ -2,10 +2,13 @@ libutil_a_SOURCES = include/util.h include/str_table.h include/hash_table.h libutil_a_SOURCES += lib/util/str_table.c lib/util/alloc.c libutil_a_SOURCES += lib/util/rbtree.c include/rbtree.h libutil_a_SOURCES += lib/util/array.c include/array.h -libutil_a_SOURCES += lib/util/mempool.c include/mempool.h libutil_a_SOURCES += lib/util/xxhash.c lib/util/hash_table.c libutil_a_SOURCES += lib/util/fast_urem_by_const.h libutil_a_CFLAGS = $(AM_CFLAGS) libutil_a_CPPFLAGS = $(AM_CPPFLAGS) +if CUSTOM_ALLOC +libutil_a_SOURCES += lib/util/mempool.c include/mempool.h +endif + noinst_LIBRARIES += libutil.a diff --git a/lib/util/rbtree.c b/lib/util/rbtree.c index d8f1305..8839f82 100644 --- a/lib/util/rbtree.c +++ b/lib/util/rbtree.c @@ -14,6 +14,7 @@ #define IS_RED(n) ((n) && (n)->is_red) +#ifdef NO_CUSTOM_ALLOC static void destroy_nodes_dfs(rbtree_node_t *n) { rbtree_node_t *l, *r; @@ -26,6 +27,12 @@ static void destroy_nodes_dfs(rbtree_node_t *n) destroy_nodes_dfs(r); } } +#else +static void destroy_nodes_dfs(rbtree_node_t *n) +{ + (void)n; +} +#endif static void flip_colors(rbtree_node_t *n) { @@ -89,11 +96,16 @@ static rbtree_node_t *subtree_insert(rbtree_t *tree, rbtree_node_t *root, return subtree_balance(root); } -static rbtree_node_t *mknode(const rbtree_t *t, const void *key, const void *value) +static rbtree_node_t *mknode(rbtree_t *t, const void *key, const void *value) { rbtree_node_t *node; +#ifdef NO_CUSTOM_ALLOC node = calloc(1, sizeof(*node) + t->key_size_padded + t->value_size); +#else + node = mem_pool_allocate(t->pool); +#endif + if (node == NULL) return NULL; @@ -105,11 +117,17 @@ static rbtree_node_t *mknode(const rbtree_t *t, const void *key, const void *val return node; } -static rbtree_node_t *copy_node(const rbtree_t *t, const rbtree_node_t *n) +static rbtree_node_t *copy_node(rbtree_t *nt, const rbtree_t *t, + const rbtree_node_t *n) { rbtree_node_t *out; +#ifdef NO_CUSTOM_ALLOC out = calloc(1, sizeof(*out) + t->key_size_padded + t->value_size); +#else + out = mem_pool_allocate(nt->pool); +#endif + if (out == NULL) return NULL; @@ -118,7 +136,7 @@ static rbtree_node_t *copy_node(const rbtree_t *t, const rbtree_node_t *n) out->right = NULL; if (n->left != NULL) { - out->left = copy_node(t, n->left); + out->left = copy_node(nt, t, n->left); if (out->left == NULL) { destroy_nodes_dfs(out); @@ -127,7 +145,7 @@ static rbtree_node_t *copy_node(const rbtree_t *t, const rbtree_node_t *n) } if (n->right != NULL) { - out->right = copy_node(t, n->right); + out->right = copy_node(nt, t, n->right); if (out->right == NULL) { destroy_nodes_dfs(out); @@ -176,6 +194,12 @@ int rbtree_init(rbtree_t *tree, size_t keysize, size_t valuesize, if (SZ_ADD_OV(size, tree->value_size, &size)) return SQFS_ERROR_OVERFLOW; +#ifndef NO_CUSTOM_ALLOC + /* initialize the underlying pool allocator */ + tree->pool = mem_pool_create(size); + if (tree->pool == NULL) + return SQFS_ERROR_ALLOC; +#endif return 0; } @@ -184,8 +208,16 @@ int rbtree_copy(const rbtree_t *tree, rbtree_t *out) memcpy(out, tree, sizeof(*out)); out->root = NULL; +#ifndef NO_CUSTOM_ALLOC + out->pool = mem_pool_create(sizeof(rbtree_node_t) + + tree->key_size_padded + + tree->value_size); + if (out->pool == NULL) + return SQFS_ERROR_ALLOC; +#endif + if (tree->root != NULL) { - out->root = copy_node(tree, tree->root); + out->root = copy_node(out, tree, tree->root); if (out->root == NULL) { memset(out, 0, sizeof(*out)); @@ -198,7 +230,11 @@ int rbtree_copy(const rbtree_t *tree, rbtree_t *out) void rbtree_cleanup(rbtree_t *tree) { +#ifdef NO_CUSTOM_ALLOC destroy_nodes_dfs(tree->root); +#else + mem_pool_destroy(tree->pool); +#endif memset(tree, 0, sizeof(*tree)); } -- cgit v1.2.3