aboutsummaryrefslogtreecommitdiff
path: root/lib/sqfs
diff options
context:
space:
mode:
authorMatt Turner <mattst88@gmail.com>2020-04-19 16:01:22 -0700
committerDavid Oberhollenzer <goliath@infraroot.at>2020-04-22 14:48:46 +0200
commit20756f4354f333005bc59a2d07593d5d1429d287 (patch)
treedf1e0475927fa7b395c20ed9e777011f9f592b63 /lib/sqfs
parent566f67ce915f9175ed9075bb1d6c553249c9a426 (diff)
Import and use Mesa's hash table
With `perf record`/`perf report` I saw that 30% of the time was spent in `sqfs_frag_table_find_tail_end` with tar2sqfs for a tarball containing the Gentoo ebuild repository (many thousands of small files). The reason was the bucketing hash table in frag_table.c: too many elements in too few buckets meant lots of walking over the linked lists. This patch replaces that hash table with the hash table implementation from Mesa. Its implementation is more complex (is is an open-addressing, linear-reprobing) hash table, but it is much better suited for the task. On my 4c/8t Skylake, the time to run tar2sqfs drops from 7.5s to less than 3s. CPU usage increases from ~207% to ~356%, presumably indicating an increase in available parallelism due to the removal of the hash table as a bottleneck. The `perf report` profile with this patch shows that the time spent in `sqfs_frag_table_find_tail_end` has dropped from ~30% to 0.01%. Output from ministat: x before + after N Min Max Median Avg Stddev x 20 7.476 7.685 7.5725 7.5615 0.051254268 + 20 2.79 2.901 2.846 2.84475 0.03543842 Difference at 95.0% confidence -4.71675 +/- 0.0282015 -62.3785% +/- 0.241477% (Student's t, pooled s = 0.0440618) I imported only the bits of the hash table implementation that were needed for frag_table.c. Among the changes I made after importing are - removed usage of ralloc, Mesa's recursive memory allocator - Replaced ralloc -> malloc ralloc_free -> free rzalloc_array -> calloc - Removed mem_ctx parameters - Added free()s to the appropriate places (valgrind confirms there are no leaks) - removed _mesa_-prefix from function names Fixes: #40 Signed-off-by: Matt Turner <mattst88@gmail.com>
Diffstat (limited to 'lib/sqfs')
-rw-r--r--lib/sqfs/Makemodule.am1
-rw-r--r--lib/sqfs/frag_table.c116
2 files changed, 45 insertions, 72 deletions
diff --git a/lib/sqfs/Makemodule.am b/lib/sqfs/Makemodule.am
index 942c37c..32b4c25 100644
--- a/lib/sqfs/Makemodule.am
+++ b/lib/sqfs/Makemodule.am
@@ -36,6 +36,7 @@ libsquashfs_la_LIBADD += $(ZSTD_LIBS) $(PTHREAD_LIBS)
# directly "import" stuff from libutil
libsquashfs_la_SOURCES += lib/util/str_table.c lib/util/alloc.c
libsquashfs_la_SOURCES += lib/util/xxhash.c
+libsquashfs_la_SOURCES += lib/util/hash_table.c lib/util/hash_table.h
if WINDOWS
libsquashfs_la_SOURCES += lib/sqfs/win32/io_file.c
diff --git a/lib/sqfs/frag_table.c b/lib/sqfs/frag_table.c
index 51164e6..59811bb 100644
--- a/lib/sqfs/frag_table.c
+++ b/lib/sqfs/frag_table.c
@@ -14,13 +14,12 @@
#include "sqfs/block.h"
#include "compat.h"
+#include "lib/util/hash_table.h"
+
#include <stdlib.h>
#include <string.h>
-#define NUM_BUCKETS (128)
-
-
typedef struct chunk_info_t {
struct chunk_info_t *next;
sqfs_u32 index;
@@ -37,23 +36,32 @@ struct sqfs_frag_table_t {
size_t used;
sqfs_fragment_t *table;
- chunk_info_t chunks[NUM_BUCKETS];
+ struct hash_table *ht;
};
+static uint32_t chunk_info_hash(const void *key)
+{
+ const chunk_info_t *chunk = key;
+ return chunk->hash;
+}
+
+static bool chunk_info_equals(const void *a, const void *b)
+{
+ const chunk_info_t *a_ = a, *b_ = b;
+ return a_->size == b_->size &&
+ a_->hash == b_->hash;
+}
+
+static void delete_function(struct hash_entry *entry)
+{
+ free(entry->data);
+}
+
static void frag_table_destroy(sqfs_object_t *obj)
{
sqfs_frag_table_t *tbl = (sqfs_frag_table_t *)obj;
- chunk_info_t *info;
- size_t i;
-
- for (i = 0; i < NUM_BUCKETS; ++i) {
- while (tbl->chunks[i].next != NULL) {
- info = tbl->chunks[i].next;
- tbl->chunks[i].next = info->next;
- free(info);
- }
- }
+ hash_table_destroy(tbl->ht, delete_function);
free(tbl->table);
free(tbl);
}
@@ -62,38 +70,15 @@ static sqfs_object_t *frag_table_copy(const sqfs_object_t *obj)
{
const sqfs_frag_table_t *tbl = (const sqfs_frag_table_t *)obj;
sqfs_frag_table_t *copy;
- const chunk_info_t *it;
- chunk_info_t *last;
- size_t i;
copy = malloc(sizeof(*copy));
if (copy == NULL)
return NULL;
memcpy(copy, tbl, sizeof(*tbl));
- for (i = 0; i < NUM_BUCKETS; ++i)
- copy->chunks[i].next = NULL;
-
- for (i = 0; i < NUM_BUCKETS; ++i) {
- last = &(copy->chunks[i]);
- it = tbl->chunks[i].next;
-
- while (it != NULL) {
- last->next = malloc(sizeof(*it));
- if (last->next == NULL)
- goto fail;
-
- memcpy(last->next, it, sizeof(*it));
- last = last->next;
- last->next = NULL;
- it = it->next;
- }
- }
+ copy->ht = hash_table_clone(tbl->ht);
return (sqfs_object_t *)copy;
-fail:
- frag_table_destroy((sqfs_object_t *)copy);
- return NULL;
}
sqfs_frag_table_t *sqfs_frag_table_create(sqfs_u32 flags)
@@ -107,6 +92,8 @@ sqfs_frag_table_t *sqfs_frag_table_create(sqfs_u32 flags)
if (tbl == NULL)
return NULL;
+ tbl->ht = hash_table_create(chunk_info_hash, chunk_info_equals);
+
((sqfs_object_t *)tbl)->copy = frag_table_copy;
((sqfs_object_t *)tbl)->destroy = frag_table_destroy;
return tbl;
@@ -267,30 +254,16 @@ int sqfs_frag_table_add_tail_end(sqfs_frag_table_t *tbl,
sqfs_u32 index, sqfs_u32 offset,
sqfs_u32 size, sqfs_u32 hash)
{
- size_t idx = hash % NUM_BUCKETS;
- chunk_info_t *new, *it;
-
- if (tbl->chunks[idx].size == 0 && tbl->chunks[idx].hash == 0) {
- tbl->chunks[idx].index = index;
- tbl->chunks[idx].offset = offset;
- tbl->chunks[idx].size = size;
- tbl->chunks[idx].hash = hash;
- } else {
- new = calloc(1, sizeof(*new));
- if (new == NULL)
- return SQFS_ERROR_ALLOC;
+ chunk_info_t *new = calloc(1, sizeof(*new));
+ if (new == NULL)
+ return SQFS_ERROR_ALLOC;
- new->index = index;
- new->offset = offset;
- new->size = size;
- new->hash = hash;
+ new->index = index;
+ new->offset = offset;
+ new->size = size;
+ new->hash = hash;
- it = &tbl->chunks[idx];
- while (it->next != NULL)
- it = it->next;
-
- it->next = new;
- }
+ hash_table_insert_pre_hashed(tbl->ht, new->hash, new, new);
return 0;
}
@@ -299,19 +272,18 @@ int sqfs_frag_table_find_tail_end(sqfs_frag_table_t *tbl,
sqfs_u32 hash, sqfs_u32 size,
sqfs_u32 *index, sqfs_u32 *offset)
{
- size_t idx = hash % NUM_BUCKETS;
- chunk_info_t *it;
+ struct hash_entry *entry;
+ chunk_info_t *chunk, search;
- if (tbl->chunks[idx].size == 0 && tbl->chunks[idx].hash == 0)
- return SQFS_ERROR_NO_ENTRY;
+ search.hash = hash;
+ search.size = size;
- for (it = &tbl->chunks[idx]; it != NULL; it = it->next) {
- if (it->hash == hash && it->size == size) {
- *index = it->index;
- *offset = it->offset;
- return 0;
- }
- }
+ entry = hash_table_search_pre_hashed(tbl->ht, hash, &search);
+ if (!entry)
+ return SQFS_ERROR_NO_ENTRY;
- return SQFS_ERROR_NO_ENTRY;
+ chunk = entry->data;
+ *index = chunk->index;
+ *offset = chunk->offset;
+ return 0;
}