Re: Add zstd support to libbacktrace
Some more tweaks of the libbacktrace zstd decompressor to make
decompressing slightly faster: unpack all the literal data into the
output buffer, rather than using scratch space. Bootstrapped and ran
libbacktrace tests on x86_64-pc-linux-gnu. Committed to mainline.
Ian
* elf.c (elf_fetch_backward_init): New static function.
(ZSTD_TABLE_SIZE): Use huffman scratch space size rather than
literal size.
(ZSTD_TABLE_WORK_LIT_SIZE): Don't define.
(elf_zstd_read_huff): Use elf_fetch_backward_init.
(elf_zstd_read_literals): New static function.
(ZSTD_LIT_RAW, ZSTD_LIT_RLE, ZSTD_LIT_HUFF): Don't define.
(struct elf_zstd_literals): Don't define.
(elf_zstd_literal_output): Remove static function.
(elf_zstd_decompress): Use elf_fetch_backward_init and
elf_zstd_read_literals. Rewrite literal copying.<
diff --git a/libbacktrace/elf.c b/libbacktrace/elf.c
index ece02db27f1..135a94245a4 100644
--- a/libbacktrace/elf.c
+++ b/libbacktrace/elf.c
@@ -1223,6 +1223,57 @@ elf_fetch_bits_backward (const unsigned char **ppin,
return 1;
}
+/* Initialize backward fetching when the bitstream starts with a 1 bit in the
+ last byte in memory (which is the first one that we read). This is used by
+ zstd decompression. Returns 1 on success, 0 on error. */
+
+static int
+elf_fetch_backward_init (const unsigned char **ppin,
+const unsigned char *pinend,
+uint64_t *pval, unsigned int *pbits)
+{
+ const unsigned char *pin;
+ unsigned int stream_start;
+ uint64_t val;
+ unsigned int bits;
+
+ pin = *ppin;
+ stream_start = (unsigned int)*pin;
+ if (unlikely (stream_start == 0))
+{
+ elf_uncompress_failed ();
+ return 0;
+}
+ val = 0;
+ bits = 0;
+
+ /* Align to a 32-bit boundary. */
+ while uintptr_t)pin) & 3) != 0)
+{
+ val <<= 8;
+ val |= (uint64_t)*pin;
+ bits += 8;
+ --pin;
+}
+
+ val <<= 8;
+ val |= (uint64_t)*pin;
+ bits += 8;
+
+ *ppin = pin;
+ *pval = val;
+ *pbits = bits;
+ if (!elf_fetch_bits_backward (ppin, pinend, pval, pbits))
+return 0;
+
+ *pbits -= __builtin_clz (stream_start) - (sizeof (unsigned int) - 1) * 8 + 1;
+
+ if (!elf_fetch_bits_backward (ppin, pinend, pval, pbits))
+return 0;
+
+ return 1;
+}
+
/* Huffman code tables, like the rest of the zlib format, are defined
by RFC 1951. We store a Huffman code table as a series of tables
stored sequentially in memory. Each entry in a table is 16 bits.
@@ -2617,14 +2668,13 @@ elf_zlib_inflate_and_verify (const unsigned char *pin,
size_t sin,
- scratch space, one of
- to build an FSE table: 512 uint16_t values == 1024 bytes
- to build a Huffman tree: 512 uint16_t + 256 uint32_t == 2048 bytes
- - buffer for literal values == 2048 bytes
*/
#define ZSTD_TABLE_SIZE\
(2 * 512 * sizeof (struct elf_zstd_fse_baseline_entry) \
+ 256 * sizeof (struct elf_zstd_fse_baseline_entry) \
+ 2048 * sizeof (uint16_t) \
- + 2048)
+ + 512 * sizeof (uint16_t) + 256 * sizeof (uint32_t))
#define ZSTD_TABLE_LITERAL_FSE_OFFSET (0)
@@ -2642,8 +2692,6 @@ elf_zlib_inflate_and_verify (const unsigned char *pin,
size_t sin,
#define ZSTD_TABLE_WORK_OFFSET \
(ZSTD_TABLE_HUFFMAN_OFFSET + 2048 * sizeof (uint16_t))
-#define ZSTD_TABLE_WORK_LIT_SIZE 2048
-
/* An entry in a zstd FSE table. */
struct elf_zstd_fse_entry
@@ -3427,7 +3475,6 @@ elf_zstd_read_huff (const unsigned char **ppin, const
unsigned char *pinend,
uint16_t *scratch;
const unsigned char *pfse;
const unsigned char *pback;
- unsigned char stream_start;
uint64_t val;
unsigned int bits;
unsigned int state1, state2;
@@ -3454,31 +3501,8 @@ elf_zstd_read_huff (const unsigned char **ppin, const
unsigned char *pinend,
FSE_TABLE. */
pback = pin + hdr - 1;
- stream_start = *pback;
- if (unlikely (stream_start == 0))
- {
- elf_uncompress_failed ();
- return 0;
- }
- val = 0;
- bits = 0;
- while uintptr_t)pback) & 3) != 0)
- {
- val <<= 8;
- val |= (uint64_t)*pback;
- bits += 8;
- --pback;
- }
- val <<= 8;
- val |= (uint64_t)*pback;
- bits += 8;
-
- if (!elf_fetch_bits_backward (, pfse, , ))
- return 0;
-
- bits -= __builtin_clz (stream_start) - 24 + 1;
- if (!elf_fetch_bits_backward (, pfse, , ))
+ if (!elf_fetch_backward_init (, pfse, , ))
return 0;
bits -= fse_table_bits;
@@ -3702,331 +3726,615 @@ elf_zstd_read_huff (const unsigned char **ppin, const
unsigned char *pinend,
return 1;
}
-/* The information used to decompress a sequence code, which can be a literal
- length, an offset, or a match length. */
+/* Read and decompress the literals and store them ending at POUTEND. This
+ works because we are going to use all the
Re: Add zstd support to libbacktrace
On Wed, Dec 7, 2022 at 4:22 PM Ian Lance Taylor wrote:
>
> This patch adds zstd support to libbacktrace, to support the new
> linker option --compress-debug-sections=zstd.
This patch rewrites and simplifies the main zstd decompression loop
using some ideas from the reference implementation. This speeds it up
a bit, although it still runs at about 35% of the speed of the
reference implementaiton. Bootstrapped and ran libbacktrace tests on
x86_64-pc-linux-gnu. Committed to mainline.
Ian
* elf.c (ZSTD_TABLE_*): Use elf_zstd_fse_baseline_entry.
(ZSTD_ENCODE_BASELINE_BITS): Define.
(ZSTD_DECODE_BASELINE, ZSTD_DECODE_BASEBITS): Define.
(elf_zstd_literal_length_base): New static const array.
(elf_zstd_match_length_base): Likewise.
(struct elf_zstd_fse_baseline_entry): Define.
(elf_zstd_make_literal_baseline_fse): New static function.
(elf_zstd_make_offset_baseline_fse): Likewise.
(elf_zstd_make_match_baseline_fse): Likewise.
(print_table, main): Use elf_zstd_fse_baseline_entry.
(elf_zstd_lit_table, elf_zstd_match_table): Likewise.
(elf_zstd_offset_table): Likewise.
(struct elf_zstd_seq_decode): Likewise. Remove use_rle and rle
fields.
(elf_zstd_unpack_seq_decode): Use elf_zstd_fse_baseline_entry,
taking a conversion function. Convert RLE to FSE.
(elf_zstd_literal_length_baseline): Remove.
(elf_zstd_literal_length_bits): Remove.
(elf_zstd_match_length_baseline): Remove.
(elf_zstd_match_length_bits): Remove.
(elf_zstd_decompress): Use elf_zstd_fse_baseline_entry. Rewrite
and simplify main loop.
diff --git a/libbacktrace/elf.c b/libbacktrace/elf.c
index 15e6f284db6..ece02db27f1 100644
--- a/libbacktrace/elf.c
+++ b/libbacktrace/elf.c
@@ -2610,9 +2610,9 @@ elf_zlib_inflate_and_verify (const unsigned char *pin,
size_t sin,
}
/* For working memory during zstd compression, we need
- - a literal length FSE table: 512 32-bit values == 2048 bytes
- - a match length FSE table: 512 32-bit values == 2048 bytes
- - a offset FSE table: 256 32-bit values == 1024 bytes
+ - a literal length FSE table: 512 64-bit values == 4096 bytes
+ - a match length FSE table: 512 64-bit values == 4096 bytes
+ - a offset FSE table: 256 64-bit values == 2048 bytes
- a Huffman tree: 2048 uint16_t values == 4096 bytes
- scratch space, one of
- to build an FSE table: 512 uint16_t values == 1024 bytes
@@ -2620,21 +2620,24 @@ elf_zlib_inflate_and_verify (const unsigned char *pin,
size_t sin,
- buffer for literal values == 2048 bytes
*/
-#define ZSTD_TABLE_SIZE\
- (2 * 512 * sizeof (struct elf_zstd_fse_entry)\
- + 256 * sizeof (struct elf_zstd_fse_entry) \
- + 2048 * sizeof (uint16_t) \
+#define ZSTD_TABLE_SIZE\
+ (2 * 512 * sizeof (struct elf_zstd_fse_baseline_entry) \
+ + 256 * sizeof (struct elf_zstd_fse_baseline_entry) \
+ + 2048 * sizeof (uint16_t) \
+ 2048)
#define ZSTD_TABLE_LITERAL_FSE_OFFSET (0)
-#define ZSTD_TABLE_MATCH_FSE_OFFSET (512 * sizeof (struct elf_zstd_fse_entry))
+#define ZSTD_TABLE_MATCH_FSE_OFFSET\
+ (512 * sizeof (struct elf_zstd_fse_baseline_entry))
-#define ZSTD_TABLE_OFFSET_FSE_OFFSET \
- (ZSTD_TABLE_MATCH_FSE_OFFSET + 512 * sizeof (struct elf_zstd_fse_entry))
+#define ZSTD_TABLE_OFFSET_FSE_OFFSET \
+ (ZSTD_TABLE_MATCH_FSE_OFFSET \
+ + 512 * sizeof (struct elf_zstd_fse_baseline_entry))
-#define ZSTD_TABLE_HUFFMAN_OFFSET \
- (ZSTD_TABLE_OFFSET_FSE_OFFSET + 256 * sizeof (struct elf_zstd_fse_entry))
+#define ZSTD_TABLE_HUFFMAN_OFFSET \
+ (ZSTD_TABLE_OFFSET_FSE_OFFSET
\
+ + 256 * sizeof (struct elf_zstd_fse_baseline_entry))
#define ZSTD_TABLE_WORK_OFFSET \
(ZSTD_TABLE_HUFFMAN_OFFSET + 2048 * sizeof (uint16_t))
@@ -2645,8 +2648,11 @@ elf_zlib_inflate_and_verify (const unsigned char *pin,
size_t sin,
struct elf_zstd_fse_entry
{
+ /* The value that this FSE entry represents. */
unsigned char symbol;
+ /* The number of bits to read to determine the next state. */
unsigned char bits;
+ /* Add the bits to this base to get the next state. */
uint16_t base;
};
@@ -2925,6 +2931,270 @@ elf_zstd_build_fse (const int16_t *norm, int idx,
uint16_t *next,
return 1;
}
+/* Encode the baseline and bits into a single 32-bit value. */
+
+#define ZSTD_ENCODE_BASELINE_BITS(baseline, basebits) \
+ ((uint32_t)(baseline) | ((uint32_t)(basebits) << 24))
+
+#define ZSTD_DECODE_BASELINE(baseline_basebits)\
+ ((uint32_t)(baseline_basebits) & 0xff)
+
+#define ZSTD_DECODE_BASEBITS(baseline_basebits)\
+ ((uint32_t)(baseline_basebits) >> 24)
+
+/* Given a literal length code, we need to read a number of bits and add that
+ to a baseline. For states 0 to 15 the baseline is the state and the number
+ of bits is zero. */
+
+#define
Add zstd support to libbacktrace
This patch adds zstd support to libbacktrace, to support the new linker option --compress-debug-sections=zstd. The zstd format is fairly complicated, so it's likely that there are some bugs here. It does pass the tests, at least. Unfortunately this decompressor only runs at about 1/3 the speed to the zstd library decompressor. Still, it's smaller and simpler, and I think it uses less memory. Plus of course it uses the signal-safe libbacktrace memory allocator. Perhaps people can make a bit faster over time. Bootstrapped and ran libbacktrace and Go tests while using a linker that compressed using zstd. Committed to mainline. Ian Support decompressing --compress-debug-sections=zstd. * configure.ac: Check for zstd library and --compress-debug-sections=zstd linker option. * Makefile.am (zstdtest_*): New targets. (zstdtest_alloc_*, ctestzstd_*): New targets. (BUILDTESTS): Add zstdtest, zstdtest_alloc, ctestzstd as appropriate. * elf.c (ELFCOMPRESS_ZSTD): Define. (elf_fetch_bits): Rename from elf_zlib_fetch. Update uses. (elf_fetch_bits_backward): New static function. (ZLIB_HUFFMAN_*): Rename from HUFFMAN_*. Update uses. (ZLIB_TABLE_*): Rename from ZDEBUG_TABLE_*. Update uses. (ZSTD_TABLE_*): Define. (struct elf_zstd_fse_entry): Define. (elf_zstd_read_fse): New static function. (elf_zstd_build_fse): Likewise. (lit): Define if BACKTRACE_GENERATE_ZSTD_FSE_TABLES. (match, offset, next, print_table, main): Likewise. (elf_zstd_lit_table): New static const array. (elf_zstd_match_table, elf_zstd_offset_table): Likewise. (elf_zstd_read_huff): New static function. (struct elf_zstd_seq_decode): Define. (elf_zstd_unpack_seq_decode): New static function. (ZSTD_LIT_*): Define. (struct elf_zstd_literals): Define. (elf_zstd_literal_output): New static function. (ZSTD_LITERAL_LENGTH_BASELINE_OFFSET): Define. (elf_zstd_literal_length_baseline): New static const array. (elf_zstd_literal_length_bits): Likewise. (ZSTD_MATCH_LENGTH_BASELINE_OFFSET): Define. (elf_zstd_match_length_baseline): New static const array. (elf_zstd_match_length_bits): Likewise. (elf_zstd_decompress): New static function. (ZDEBUG_TABLE_SIZE): New definition. (elf_uncompress_chdr): Support ELF_COMPRESS_ZSTD. (backtrace_uncompress_zstd): New function. (elf_add): Use ZLIB_TABLE_SIZE for zlib-gnu sections. * internal.h (backtrace_uncompress_zstd): Declare. * zstdtest.c: New file. * configure, config.h.in, Makefile.in: Regenerate. diff --git a/libbacktrace/Makefile.am b/libbacktrace/Makefile.am index 9f8516d00e2..047b573c29a 100644 --- a/libbacktrace/Makefile.am +++ b/libbacktrace/Makefile.am @@ -368,6 +368,25 @@ ztest_alloc_CFLAGS = $(ztest_CFLAGS) BUILDTESTS += ztest_alloc +zstdtest_SOURCES = zstdtest.c testlib.c +zstdtest_CFLAGS = $(libbacktrace_TEST_CFLAGS) -DSRCDIR=\"$(srcdir)\" +zstdtest_LDADD = libbacktrace.la +zstdtest_alloc_LDADD = libbacktrace_alloc.la + +if HAVE_ZSTD +zstdtest_LDADD += -lzstd +zstdtest_alloc_LDADD += -lzstd +endif +zstdtest_LDADD += $(CLOCK_GETTIME_LINK) +zstdtest_alloc_LDADD += $(CLOCK_GETTIME_LINK) + +BUILDTESTS += zstdtest + +zstdtest_alloc_SOURCES = $(zstdtest_SOURCES) +zstdtest_alloc_CFLAGS = $(zstdtest_CFLAGS) + +BUILDTESTS += zstdtest_alloc + endif HAVE_ELF edtest_SOURCES = edtest.c edtest2_build.c testlib.c @@ -450,6 +469,17 @@ ctesta_LDADD = libbacktrace.la BUILDTESTS += ctestg ctesta +if HAVE_COMPRESSED_DEBUG_ZSTD + +ctestzstd_SOURCES = btest.c testlib.c +ctestzstd_CFLAGS = $(libbacktrace_TEST_CFLAGS) +ctestzstd_LDFLAGS = -Wl,--compress-debug-sections=zstd +ctestzstd_LDADD = libbacktrace.la + +BUILDTESTS += ctestzstd + +endif + ctestg_alloc_SOURCES = $(ctestg_SOURCES) ctestg_alloc_CFLAGS = $(ctestg_CFLAGS) ctestg_alloc_LDFLAGS = $(ctestg_LDFLAGS) diff --git a/libbacktrace/configure.ac b/libbacktrace/configure.ac index 1daaa2f62d2..d0a0475cfa8 100644 --- a/libbacktrace/configure.ac +++ b/libbacktrace/configure.ac @@ -495,6 +495,21 @@ AC_LINK_IFELSE([AC_LANG_PROGRAM(,)], LDFLAGS=$LDFLAGS_hold]) AM_CONDITIONAL(HAVE_COMPRESSED_DEBUG, test "$libgo_cv_ld_compress" = yes) +AC_CHECK_LIB([zstd], [ZSTD_compress], +[AC_DEFINE(HAVE_ZSTD, 1, [Define if -lzstd is available.])]) +AM_CONDITIONAL(HAVE_ZSTD, test "$ac_cv_lib_zstd_ZSTD_compress" = yes) + +dnl Test whether the linker supports --compress-debug-sections=zstd option. +AC_CACHE_CHECK([whether --compress-debug-sections=zstd is supported], +[libgo_cv_ld_compress_zstd], +[LDFLAGS_hold=$LDFLAGS +LDFLAGS="$LDFLAGS -Wl,--compress-debug-sections=zstd" +AC_LINK_IFELSE([AC_LANG_PROGRAM(,)], +[libgo_cv_ld_compress_zstd=yes], +[libgo_cv_ld_compress_zstd=no]) +LDFLAGS=$LDFLAGS_hold]) +AM_CONDITIONAL(HAVE_COMPRESSED_DEBUG_ZSTD, test "$libgo_cv_ld_compress_zstd" = yes) + AC_ARG_VAR(OBJCOPY, [location of objcopy]) AC_CHECK_PROG(OBJCOPY, objcopy, objcopy,) AC_CHECK_PROG(READELF, readelf, readelf) diff --git a/libbacktrace/elf.c b/libbacktrace/elf.c index 181d195fe35..15e6f284db6 100644 --- a/libbacktrace/elf.c +++ b/libbacktrace/elf.c @@ -184,6 +184,7 @@
