lib: prepare xxhash for preboot environment
A message that is not in the archive (sent off-list or not yet received): [email protected]
A message that is not in the archive (sent off-list or not yet received): [email protected]
Quoted 4 lines · Nick Terrell
Don't export symbols if PREBOOT is defined.
This change is necessary to get xxhash to work in a preboot environment, which is needed to support zstd-compressed kernels.
Hmm, I thought using this:
#define __DISABLE_EXPORTS
before the #include of the .c files solved this?
-Kees
Quoted 103 lines
Signed-off-by Nick Terrell <[email protected]>--- lib/xxhash.c | 21 ++++++++++++--------- 1 file changed, 12 insertions(+), 9 deletions(-)lib/xxhash.c +12
-9@@ -80,13 +80,11 @@ void xxh32_copy_state(struct xxh32_state *dst, const struct xxh32_state *src) {memcpy (dst, src,sizeof (*dst)); } -EXPORT_SYMBOL (xxh32_copy_state);void xxh64_copy_state (struct xxh64_state *dst,const struct xxh64_state *src) {memcpy (dst, src,sizeof (*dst)); } -EXPORT_SYMBOL (xxh64_copy_state);/*-*************************** * Simple Hash Functions @@ -151,7 +149,6 @@ uint32_t xxh32(const void *input, const size_t len, const uint32_t seed)return h32; } -EXPORT_SYMBOL (xxh32);static uint64_t xxh64_round (uint64_t acc,const uint64_t input) {@@ -234,7 +231,6 @@ uint64_t xxh64(const void *input, const size_t len, const uint64_t seed)return h64; } -EXPORT_SYMBOL (xxh64);/*-************************************************** * Advanced Hash Functions @@ -251,7 +247,6 @@ void xxh32_reset(struct xxh32_state *statePtr, const uint32_t seed) state.v4 = seed -PRIME32_1 ;memcpy (statePtr, &state,sizeof (state)); } -EXPORT_SYMBOL (xxh32_reset);void xxh64_reset (struct xxh64_state *statePtr,const uint64_t seed) {@@ -265,7 +260,6 @@ void xxh64_reset(struct xxh64_state *statePtr, const uint64_t seed) state.v4 = seed -PRIME64_1 ;memcpy (statePtr, &state,sizeof (state)); } -EXPORT_SYMBOL (xxh64_reset);int xxh32_update (struct xxh32_state *state,const void *input,const size_t len) {@@ -334,7 +328,6 @@ int xxh32_update(struct xxh32_state *state, const void *input, const size_t len)return 0 ; } -EXPORT_SYMBOL (xxh32_update);uint32_t xxh32_digest (const struct xxh32_state *state) {@@ -372,7 +365,6 @@ uint32_t xxh32_digest(const struct xxh32_state *state)return h32; } -EXPORT_SYMBOL (xxh32_digest);int xxh64_update (struct xxh64_state *state,const void *input,const size_t len) {@@ -439,7 +431,6 @@ int xxh64_update(struct xxh64_state *state, const void *input, const size_t len)return 0 ; } -EXPORT_SYMBOL (xxh64_update);uint64_t xxh64_digest (const struct xxh64_state *state) {@@ -494,7 +485,19 @@ uint64_t xxh64_digest(const struct xxh64_state *state)return h64; } + +#ifndef PREBOOT +EXPORT_SYMBOL (xxh32_copy_state); +EXPORT_SYMBOL (xxh64_copy_state); +EXPORT_SYMBOL (xxh32); +EXPORT_SYMBOL (xxh64); +EXPORT_SYMBOL (xxh32_reset); +EXPORT_SYMBOL (xxh64_reset); +EXPORT_SYMBOL (xxh32_update); +EXPORT_SYMBOL (xxh32_digest); +EXPORT_SYMBOL (xxh64_update);EXPORT_SYMBOL (xxh64_digest);MODULE_LICENSE ("Dual BSD/GPL" );MODULE_DESCRIPTION ("xxHash" ); +#endif Signature · 1 line
2.25.1
Signature · 1 line
Kees Cook
Quoted 5 lines · Kees Cook
Quoted 2 lines · Nick Terrell
Don't export symbols if PREBOOT is defined.
Quoted 8 lines
Quoted 2 lines
This change is necessary to get xxhash to work in a preboot environment, which is needed to support zstd-compressed kernels.
Hmm, I thought using this:
#define
__DISABLE_EXPORTSbefore the #include of the .c files solved this?
I was able to get __DISABLE_EXPORTS to work. However, that still leaves the MODULE_LICENSE() and MODULE_DESCRIPTION() in. I would prefer to use the same method other decompressors use, because it is a well tested route and debugging is hard in the preboot environment. If you feel strongly about it I will change it.
I will plan on submitting a v3 tomorrow morning that fixes the style nits, and splits PREBOOT into XXH_PREBOOT and ZSTD_PREBOOT.
Thanks for reviewing the patches!
-Nick
Quoted 108 lines
-Kees
Quoted 103 lines
Signed-off-by Nick Terrell <[email protected]>---
lib/xxhash.c| 21 ++++++++++++---------1 file changed, 12 insertions(+), 9 deletions(-)lib/xxhash.c +12
-9@@ -80,13 +80,11 @@ void xxh32_copy_state(struct xxh32_state *dst, const struct xxh32_state *src) {memcpy (dst, src,sizeof (*dst)); } -EXPORT_SYMBOL (xxh32_copy_state);void xxh64_copy_state (struct xxh64_state *dst,const struct xxh64_state *src) {memcpy (dst, src,sizeof (*dst)); } -EXPORT_SYMBOL (xxh64_copy_state);/*-*************************** * Simple Hash Functions @@ -151,7 +149,6 @@ uint32_t xxh32(const void *input, const size_t len, const uint32_t seed)return h32; } -EXPORT_SYMBOL (xxh32);static uint64_t xxh64_round (uint64_t acc,const uint64_t input) {@@ -234,7 +231,6 @@ uint64_t xxh64(const void *input, const size_t len, const uint64_t seed)return h64; } -EXPORT_SYMBOL (xxh64);/*-************************************************** * Advanced Hash Functions @@ -251,7 +247,6 @@ void xxh32_reset(struct xxh32_state *statePtr, const uint32_t seed) state.v4 = seed -PRIME32_1 ;memcpy (statePtr, &state,sizeof (state)); } -EXPORT_SYMBOL (xxh32_reset);void xxh64_reset (struct xxh64_state *statePtr,const uint64_t seed) {@@ -265,7 +260,6 @@ void xxh64_reset(struct xxh64_state *statePtr, const uint64_t seed) state.v4 = seed -PRIME64_1 ;memcpy (statePtr, &state,sizeof (state)); } -EXPORT_SYMBOL (xxh64_reset);int xxh32_update (struct xxh32_state *state,const void *input,const size_t len) {@@ -334,7 +328,6 @@ int xxh32_update(struct xxh32_state *state, const void *input, const size_t len)return 0 ; } -EXPORT_SYMBOL (xxh32_update);uint32_t xxh32_digest (const struct xxh32_state *state) {@@ -372,7 +365,6 @@ uint32_t xxh32_digest(const struct xxh32_state *state)return h32; } -EXPORT_SYMBOL (xxh32_digest);int xxh64_update (struct xxh64_state *state,const void *input,const size_t len) {@@ -439,7 +431,6 @@ int xxh64_update(struct xxh64_state *state, const void *input, const size_t len)return 0 ; } -EXPORT_SYMBOL (xxh64_update);uint64_t xxh64_digest (const struct xxh64_state *state) {@@ -494,7 +485,19 @@ uint64_t xxh64_digest(const struct xxh64_state *state)return h64; } + +#ifndef PREBOOT +EXPORT_SYMBOL (xxh32_copy_state); +EXPORT_SYMBOL (xxh64_copy_state); +EXPORT_SYMBOL (xxh32); +EXPORT_SYMBOL (xxh64); +EXPORT_SYMBOL (xxh32_reset); +EXPORT_SYMBOL (xxh64_reset); +EXPORT_SYMBOL (xxh32_update); +EXPORT_SYMBOL (xxh32_digest); +EXPORT_SYMBOL (xxh64_update);EXPORT_SYMBOL (xxh64_digest);MODULE_LICENSE ("Dual BSD/GPL" );MODULE_DESCRIPTION ("xxHash" ); +#endif Signature · 1 line
2.25.1Signature · 1 line
Kees Cook
A message that is not in the archive (sent off-list or not yet received): [email protected]
Re: [PATCH v2 3/7] lib: add zstd support to decompress
Quoted 157 lines · Nick Terrell
* Add
unzstd()and the zstd decompress interface.
* Add zstd support todecompress_method().The
decompress_method()andunzstd()functions are used to decompress the initramfs and the initrd. The__decompress()function is used in the preboot environment to decompress a zstd compressed kernel.The zstd decompression function allows the input and output buffers to overlap because that is used by x86 kernel decompression.
Signed-off-by Nick Terrell <[email protected]>--- include/linux/decompress/unzstd.h | 11 + lib/Kconfig | 4 + lib/Makefile | 1 + lib/decompress.c | 5 + lib/decompress_unzstd.c | 337 ++++++++++++++++++++++++++++++ 5 files changed, 358 insertions(+) create mode 100644 include/linux/decompress/unzstd.h create mode 100644 lib/decompress_unzstd.cinclude/linux/decompress/unzstd.h new file +11
-0@@ -0,0 +1,11 @@ +/* SPDX-License-Identifier: GPL-2.0 */ +#ifndef LINUX_DECOMPRESS_UNZSTD_H +#define LINUX_DECOMPRESS_UNZSTD_H + +int unzstd (unsigned char *inbuf,long len, +long (*fill)(void *,unsigned long ), +long (*flush)(void *,unsigned long ), +unsigned char *output, +long *pos, +void (*error_fn)(char *x)); +#endif lib/Kconfig +4
-0@@ -336,6 +336,10 @@ config DECOMPRESS_LZ4 select LZ4_DECOMPRESS tristate +config DECOMPRESS_ZSTD + select ZSTD_DECOMPRESS + tristate + # # Generic allocator support is selected if needed #lib/Makefile +1
-0@@ -160,6 +160,7 @@ lib-$(CONFIG_DECOMPRESS_LZMA) += decompress_unlzma.o lib-$(CONFIG_DECOMPRESS_XZ) += decompress_unxz.o lib-$(CONFIG_DECOMPRESS_LZO) += decompress_unlzo.o lib-$(CONFIG_DECOMPRESS_LZ4) += decompress_unlz4.o +lib-$(CONFIG_DECOMPRESS_ZSTD) += decompress_unzstd.o obj-$(CONFIG_TEXTSEARCH) += textsearch.o obj-$(CONFIG_TEXTSEARCH_KMP) += ts_kmp.olib/decompress.c +5
-0@@ -13,6 +13,7 @@#include <linux/decompress/inflate.h> #include <linux/decompress/unlzo.h> #include <linux/decompress/unlz4.h> +#include <linux/decompress/unzstd.h> #include <linux/types.h> #include <linux/string.h> @@ -37,6 +38,9 @@#ifndef CONFIG_DECOMPRESS_LZ4 # define unlz4 NULL#endif +#ifndef CONFIG_DECOMPRESS_ZSTD +# define unzstd NULL +#endif struct compress_format {unsigned char magic[2 ];@@ -52,6 +56,7 @@ static const struct compress_format compressed_formats[] __initconst = { { {0xfd, 0x37}, "xz", unxz }, { {0x89, 0x4c}, "lzo", unlzo }, { {0x02, 0x21}, "lz4", unlz4 }, + { {0x28, 0xb5}, "zstd", unzstd }, { {0, 0}, NULL, NULL } };lib/decompress_unzstd.c new file +56
-0@@ -0,0 +1,337 @@ +// SPDX-License-Identifier: GPL-2.0 + +/* +* Important notes about in-place decompression +* +* At least on x86, the kernel is decompressed in place: the compressed data +* is placed to the end of the output buffer, and the decompressor overwrites +* most of the compressed data. There must be enough safety margin to +* guarantee that the write position is always behind the read position. +* +* The safety margin for ZSTD with a 128 KB block size is calculated below. +* Note that the margin with ZSTD is bigger than with GZIP or XZ! +* +* The worst case for in-place decompression is that the beginning of +* the file is compressed extremely well, and the rest of the file is +* uncompressible. Thus, we must look for worst-case expansion when the +* compressor is encoding uncompressible data. +* +* The structure of the .zst file in case of a compresed kernel is as follows. +* Maximum sizes (as bytes) of the fields are in parenthesis. +* +* Frame Header: (18) +* Blocks: (N) +* Checksum: (4) +* +* The frame header and checksum overhead is at most 22 bytes. +* +* ZSTD stores the data in blocks. Each block has a header whose size is +* a 3 bytes. After the block header, there is up to 128 KB of payload. +* The maximum uncompressed size of the payload is 128 KB. The minimum +* uncompressed size of the payload is never less than the payload size +* (excluding the block header). +* +* The assumption, that the uncompressed size of the payload is never +* smaller than the payload itself, is valid only when talking about +* the payload as a whole. It is possible that the payload has parts where +* the decompressor consumes more input than it produces output. Calculating +* the worst case for this would be tricky. Instead of trying to do that, +* let's simply make sure that the decompressor never overwrites any bytes +* of the payload which it is currently reading. +* +* Now we have enough information to calculate the safety margin. We need +* - 22 bytes for the .zst file format headers; +* - 3 bytes per every 128 KiB of uncompressed size (one block header per +* block); and +* - 128 KiB (biggest possible zstd block size) to make sure that the +* decompressor never overwrites anything from the block it is currently +* reading. +* +* We get the following formula: +* +* safety_margin = 22 + uncompressed_size * 3 / 131072 + 131072 +* <= 22 + (uncompressed_size >> 15) + 131072 +*/ + +#ifdef STATIC
lib/decompress_unzstd.c line 66
Quoted 10 lines
lib/decompress_unzstd.c new file +10
-0+/* +* Preboot environments #include "path/to/decompress_unzstd.c". +* All of the source files we depend on must be #included. +* zstd's only source dependeny is xxhash, which has no source +* dependencies. +* +* zstd and xxhash both avoid declaring themselves as modules +* when PREBOOT is defined. +*/ +# define PREBOOT
Can you use ZSTD_PREBOOT for this? Other decompressors namespace this define.
(And a style nit: I'd put the comment above the #ifdef STATIC and use a single space, not a tab, for the "indented" #-lines)
Quoted 274 lines
lib/decompress_unzstd.c new file +271
-0+# include "xxhash.c" +# include "zstd/entropy_common.c" +# include "zstd/fse_decompress.c" +# include "zstd/huf_decompress.c" +# include "zstd/zstd_common.c" +# include "zstd/decompress.c" +#endif + +#include <linux/decompress/mm.h> +#include <linux/kernel.h> +#include <linux/zstd.h> + +/* 8 MB maximum window size */ +#define ZSTD_WINDOWSIZE_MAX (1 << 23) +/* Size of the input and output buffers in multi-call mdoe */ +#define ZSTD_IOBUF_SIZE 4096 + +static int INIT handle_zstd_error(size_t ret, void (*error)(char *x)) +{ +const int err =ZSTD_getErrorCode (ret); + +if (!ZSTD_isError (ret)) +return 0 ; + +switch (err) { +case ZSTD_error_memory_allocation: +error ("ZSTD decompressor ran out of memory" ); +break ; +case ZSTD_error_prefix_unknown: +error ("Input is not in the ZSTD format (wrong magic bytes)" ); +break ; +case ZSTD_error_dstSize_tooSmall: +case ZSTD_error_corruption_detected: +case ZSTD_error_checksum_wrong: +error ("ZSTD-compressed data is corrupt" ); +break ; +default : +error ("ZSTD-compressed data is probably corrupt" ); +break ; + } +return -1 ; +} + +/* +* Handle the case where we have the entire input and output in one segment. +* We can allocate less memory (no circular buffer for the sliding window), +* and avoid some memcpy() calls. +*/ +static int INIT decompress_single(const u8 *in_buf, long in_len, u8 *out_buf, +long out_len,long *in_pos, +void (*error)(char *x)) +{ +const size_t wksp_size =ZSTD_DCtxWorkspaceBound (); +void *wksp =large_malloc (wksp_size); +ZSTD_DCtx *dctx =ZSTD_initDCtx (wksp, wksp_size); +int err; +size_t ret; + +if (dctx ==NULL ) { +error ("Out of memory while allocating ZSTD_DCtx" ); + err =-1 ; + goto out; + } +/* +* Find out how large the frame actually is, there may be junk at +* the end of the frame that ZSTD_decompressDCtx() can't handle. +*/ + ret =ZSTD_findFrameCompressedSize (in_buf, in_len); + err =handle_zstd_error (ret, error); +if (err) + goto out; + in_len = (long )ret; + + ret =ZSTD_decompressDCtx (dctx, out_buf, out_len, in_buf, in_len); + err =handle_zstd_error (ret, error); +if (err) + goto out; + +if (in_pos !=NULL ) + *in_pos = in_len; + + err =0 ; +out: +if (wksp !=NULL ) +large_free (wksp); +return err; +} + +static int INIT __unzstd(unsigned char *in_buf, long in_len, +long (*fill)(void *,unsigned long ), +long (*flush)(void *,unsigned long ), +unsigned char *out_buf,long out_len, +long *in_pos, +void (*error)(char *x)) +{ +ZSTD_inBuffer in; +ZSTD_outBuffer out; +ZSTD_frameParams params; +void *in_allocated =NULL ; +void *out_allocated =NULL ; +void *wksp =NULL ; +size_t wksp_size; +ZSTD_DStream *dstream; +int err; +size_t ret; + +if (out_len ==0 ) + out_len =LONG_MAX ;/* no limit */ + +if (fill ==NULL && flush ==NULL ) +/* +* We can decompress faster and with less memory when we have a +* single chunk. +*/ +return decompress_single (in_buf, in_len, out_buf, out_len, + in_pos, error); + +/* +* If in_buf is not provided, we must be using fill(), so allocate +* a large enough buffer. If it is provided, it must be at least +* ZSTD_IOBUF_SIZE large. +*/ +if (in_buf ==NULL ) { + in_allocated =malloc (ZSTD_IOBUF_SIZE ); +if (in_allocated ==NULL ) { +error ("Out of memory while allocating input buffer" ); + err =-1 ; + goto out; + } + in_buf = in_allocated; + in_len =0 ; + } +/* Read the first chunk, since we need to decode the frame header. */ +if (fill !=NULL ) + in_len =fill (in_buf,ZSTD_IOBUF_SIZE ); +if (in_len <0 ) { +error ("ZSTD-compressed data is truncated" ); + err =-1 ; + goto out; + } +/* Set the first non-empty input buffer. */ + in.src = in_buf; + in.pos =0 ; + in.size = in_len; +/* Allocate the output buffer if we are using flush(). */ +if (flush !=NULL ) { + out_allocated =malloc (ZSTD_IOBUF_SIZE ); +if (out_allocated ==NULL ) { +error ("Out of memory while allocating output buffer" ); + err =-1 ; + goto out; + } + out_buf = out_allocated; + out_len =ZSTD_IOBUF_SIZE ; + } +/* Set the output buffer. */ + out.dst = out_buf; + out.pos =0 ; + out.size = out_len; + +/* +* We need to know the window size to allocate the ZSTD_DStream. +* Since we are streaming, we need to allocate a buffer for the sliding +* window. The window size varies from 1 KB to ZSTD_WINDOWSIZE_MAX +* (8 MB), so it is important to use the actual value so as not to +* waste memory when it is smaller. +*/ + ret =ZSTD_getFrameParams (¶ms, in.src, in.size); + err =handle_zstd_error (ret, error); +if (err) + goto out; +if (ret !=0 ) { +error ("ZSTD-compressed data has an incomplete frame header" ); + err =-1 ; + goto out; + } +if (params.windowSize >ZSTD_WINDOWSIZE_MAX ) { +error ("ZSTD-compressed data has too large a window size" ); + err =-1 ; + goto out; + } + +/* +* Allocate the ZSTD_DStream now that we know how much memory is +* required. +*/ + wksp_size =ZSTD_DStreamWorkspaceBound (params.windowSize); + wksp =large_malloc (wksp_size); + dstream =ZSTD_initDStream (params.windowSize, wksp, wksp_size); +if (dstream ==NULL ) { +error ("Out of memory while allocating ZSTD_DStream" ); + err =-1 ; + goto out; + } + +/* +* Decompression loop: +* Read more data if necessary (error if no more data can be read). +* Call the decompression function, which returns 0 when finished. +* Flush any data produced if using flush(). +*/ +if (in_pos !=NULL ) + *in_pos =0 ; +do { +/* +* If we need to reload data, either we have fill() and can +* try to get more data, or we don't and the input is truncated. +*/ +if (in.pos == in.size) { +if (in_pos !=NULL ) + *in_pos += in.pos; + in_len = fill ?fill (in_buf,ZSTD_IOBUF_SIZE ) :-1 ; +if (in_len <0 ) { +error ("ZSTD-compressed data is truncated" ); + err =-1 ; + goto out; + } + in.pos =0 ; + in.size = in_len; + } +/* Returns zero when the frame is complete. */ + ret =ZSTD_decompressStream (dstream, &out, &in); + err =handle_zstd_error (ret, error); +if (err) + goto out; +/* Flush all of the data produced if using flush(). */ +if (flush !=NULL && out.pos >0 ) { +if (out.pos !=flush (out.dst, out.pos)) { +error ("Failed to flush()" ); + err =-1 ; + goto out; + } + out.pos =0 ; + } + }while (ret !=0 ); + +if (in_pos !=NULL ) + *in_pos += in.pos; + + err =0 ; +out: +if (in_allocated !=NULL ) +free (in_allocated); +if (out_allocated !=NULL ) +free (out_allocated); +if (wksp !=NULL ) +large_free (wksp); +return err; +} + +#ifndef PREBOOT +STATIC int INIT unzstd(unsigned char *buf, long len, +long (*fill)(void *,unsigned long ), +long (*flush)(void *,unsigned long ), +unsigned char *out_buf, +long *pos, +void (*error)(char *x)) +{ +return __unzstd (buf, len, fill, flush, out_buf,0 , pos, error); +} +#else +STATIC int INIT __decompress(unsigned char *buf, long len, +long (*fill)(void *,unsigned long ), +long (*flush)(void *,unsigned long ), +unsigned char *out_buf,long out_len, +long *pos, +void (*error)(char *x)) +{ +return __unzstd (buf, len, fill, flush, out_buf, out_len, pos, error); +} +#endif Signature · 1 line
2.25.1
Signature · 1 line
Kees Cook
[PATCH v2 8/7] .gitignore: add ZSTD-compressed files
In reply to a message not in the archiveFor now, that's arch/x86/boot/compressed/vmlinux.bin.zst but probably more will come, thus let's be consistent with all other compressors.
---
Otherwise, "git status" will complain.
.gitignore | 1 + 1 file changed, 1 insertion(+)
.gitignore +1 -0
@@ -43,6 +43,7 @@ *.tab.[ch] *.tar *.xz +*.zst Module.symvers modules.builtin modules.order
Signature · 1 line
2.26.0.rc2
Re: [PATCH v2 8/7] .gitignore: add ZSTD-compressed files
Quoted 6 lines · Adam Borowski
For now, that's
arch/x86/boot/compressed/vmlinux.bin.zstbut probably more will come, thus let's be consistent with all other compressors.
Thanks for the review, I will include that in v3 tomorrow!
Quoted 23 lines
Signed-off-by Adam Borowski <[email protected]>---
Otherwise, "git status" will complain..gitignore | 1 +
1 file changed, 1 insertion(+).gitignore +1
-0@@ -43,6 +43,7 @@ *.tab.[ch] *.tar *.xz +*.zstModule.symvers
modules.builtin
modules.orderSignature · 1 line
2.26.0.rc2