aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorDavid Oberhollenzer <david.oberhollenzer@sigma-star.at>2021-03-07 18:15:50 +0100
committerDavid Oberhollenzer <david.oberhollenzer@sigma-star.at>2021-03-07 18:15:50 +0100
commit723019f727ce53b392389bdadcc1701ae47e6a14 (patch)
tree148912aacb539269a89b0d473abb9a85466628e0
parent8f79a36a592c796c19037a2513c6fc7098698dee (diff)
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 <david.oberhollenzer@sigma-star.at>
-rw-r--r--Makefile.am5
-rw-r--r--configure.ac9
-rw-r--r--include/rbtree.h5
-rw-r--r--lib/sqfs/Makemodule.am4
-rw-r--r--lib/util/Makemodule.am5
-rw-r--r--lib/util/rbtree.c46
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 <stddef.h>
@@ -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));
}