squashfs-tools-ng.git/lib/util, branch v1.0.1

Cleanup: mark sqfs_xattr_writer_flush writer argument as const

2020-06-09T04:51:31+00:00

It does not make any changes to the writer itself, so mark it as const. This also requires some similar changes to the string table. Signed-off-by: David Oberhollenzer

hash table: switch to sqfs_* types, mark functions as hidden

2020-05-21T17:51:54+00:00

Signed-off-by: David Oberhollenzer

Cleanup: move hash table header to include directory

2020-05-19T14:17:29+00:00

Signed-off-by: David Oberhollenzer

Enable uint128_t path

2020-04-27T10:49:25+00:00

I forgot to enable this when I copied it over from Mesa. Mesa's meson configuration system checks that a C program using the uint128_t type compiles, but I think this is likely unnecessary. Simply check the macro that clang and gcc define. This cuts the .text size of hash_table.o by 160 bytes or about 4% on my system. Signed-off-by: Matt Turner

Add hash table code to libutil.a

2020-04-27T10:08:58+00:00

Not only does this build the hashtable into libutil.a, it also makes sure the headers end up in the distribution tarball. Signed-off-by: David Oberhollenzer

Import and use Mesa's hash table

2020-04-22T12:48:46+00:00

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

Restore workaround for unaligned reads in xxhash

2020-03-18T12:33:47+00:00

The code was originally used inside the block processor, where 32 bit aligned data could be guaranteed. If it is available in libutil, I cannot possibly guarantee for alignment in future use elsewhere. Even for the block processor it was rather risky "remember this detail very well" buisness. This commit restores the unaligned read treatment of the original. Signed-off-by: David Oberhollenzer

Cleanup: Move xxhash32 code to libutil

2020-03-18T12:33:47+00:00

Signed-off-by: David Oberhollenzer

Add a deep copy function for the str_table_t helper

2020-03-03T23:28:39+00:00

Signed-off-by: David Oberhollenzer

Add a very simple red-black tree implementation

2020-02-22T00:20:58+00:00

Signed-off-by: David Oberhollenzer