[PATCH v3 0/7] (mainly) xz imports from Linux

[PATCH v3 0/7] (mainly) xz imports from Linux

[Jan Beulich]

While going through their 5.15.3 log I did notice two changes, which made
me go check what else we might be missing. The series here is the result.
Linux has also updated zstd, but that includes a pretty large change which
I'm not ready to deal with right now. Them moving closer to the upstream
zstd sources is certainly a good thing, so I suppose sooner or later we
will want to follow them in doing so.

The only change in v3 is the re-adding of some previously dropped S-o-b in
patches 2 and 3, to satisfy the rules newly established by 5e326b61693c.

As the series has R-b by Luca and as the (not) retaining of certain tags
was the only open issue in v1 and v2, I won't wait long until committing
this; perhaps just until after the weekend.

1: xz: add fall-through comments to a switch statement
2: xz: fix XZ_DYNALLOC to avoid useless memory reallocations
3: decompressors: fix spelling mistakes
4: xz: avoid overlapping memcpy() with invalid input with in-place decompression
5: xz: fix spelling in comments
6: xz: move s->lzma.len = 0 initialization to lzma_reset()
7: xz: validate the value before assigning it to an enum variable

Jan

[PATCH v3 1/7] xz: add fall-through comments to a switch statement

[Jan Beulich]

From: Lasse Collin <lasse.collin@tukaani.org>

It's good style. I was also told that GCC 7 is more strict and might
give a warning when such comments are missing.

Suggested-by: Andrei Borzenkov <arvidjaar@gmail.com>
Signed-off-by: Lasse Collin <lasse.collin@tukaani.org>
Signed-off-by: Jiri Kosina <jkosina@suse.cz>
[Linux commit: 5a244f48ecbbd03a11eb84819c5c599db81823ee]
Signed-off-by: Jan Beulich <jbeulich@suse.com>
Reviewed-by: Luca Fancellu <luca.fancellu@arm.com>
---
Linux has meanwhile further moved to using the "fallthrough" pseudo-
keyword, but us doing so requires the tool stack to first make this
available for use in at least stubdom builds.
---
v2: Retain the other S-o-b, for lack of mailing list source of the
    original submission.

--- a/xen/common/xz/dec_stream.c
+++ b/xen/common/xz/dec_stream.c
@@ -583,6 +583,8 @@ static enum xz_ret __init dec_main(struc
 			if (ret != XZ_OK)
 				return ret;
 
+		/* Fall through */
+
 		case SEQ_BLOCK_START:
 			/* We need one byte of input to continue. */
 			if (b->in_pos == b->in_size)
@@ -606,6 +608,8 @@ static enum xz_ret __init dec_main(struc
 			s->temp.pos = 0;
 			s->sequence = SEQ_BLOCK_HEADER;
 
+		/* Fall through */
+
 		case SEQ_BLOCK_HEADER:
 			if (!fill_temp(s, b))
 				return XZ_OK;
@@ -616,6 +620,8 @@ static enum xz_ret __init dec_main(struc
 
 			s->sequence = SEQ_BLOCK_UNCOMPRESS;
 
+		/* Fall through */
+
 		case SEQ_BLOCK_UNCOMPRESS:
 			ret = dec_block(s, b);
 			if (ret != XZ_STREAM_END)
@@ -623,6 +629,8 @@ static enum xz_ret __init dec_main(struc
 
 			s->sequence = SEQ_BLOCK_PADDING;
 
+		/* Fall through */
+
 		case SEQ_BLOCK_PADDING:
 			/*
 			 * Size of Compressed Data + Block Padding
@@ -643,6 +651,8 @@ static enum xz_ret __init dec_main(struc
 
 			s->sequence = SEQ_BLOCK_CHECK;
 
+		/* Fall through */
+
 		case SEQ_BLOCK_CHECK:
 			if (s->check_type == XZ_CHECK_CRC32) {
 				ret = crc32_validate(s, b);
@@ -665,6 +675,8 @@ static enum xz_ret __init dec_main(struc
 
 			s->sequence = SEQ_INDEX_PADDING;
 
+		/* Fall through */
+
 		case SEQ_INDEX_PADDING:
 			while ((s->index.size + (b->in_pos - s->in_start))
 					& 3) {
@@ -687,6 +699,8 @@ static enum xz_ret __init dec_main(struc
 
 			s->sequence = SEQ_INDEX_CRC32;
 
+		/* Fall through */
+
 		case SEQ_INDEX_CRC32:
 			ret = crc32_validate(s, b);
 			if (ret != XZ_STREAM_END)
@@ -695,6 +709,8 @@ static enum xz_ret __init dec_main(struc
 			s->temp.size = STREAM_HEADER_SIZE;
 			s->sequence = SEQ_STREAM_FOOTER;
 
+		/* Fall through */
+
 		case SEQ_STREAM_FOOTER:
 			if (!fill_temp(s, b))
 				return XZ_OK;

[PATCH v3 2/7] xz: fix XZ_DYNALLOC to avoid useless memory reallocations

[Jan Beulich]

From: Lasse Collin <lasse.collin@tukaani.org>

s->dict.allocated was initialized to 0 but never set after a successful
allocation, thus the code always thought that the dictionary buffer has
to be reallocated.

Link: http://lkml.kernel.org/r/20191104185107.3b6330df@tukaani.org
Reported-by: Yu Sun <yusun2@cisco.com>
Signed-off-by: Lasse Collin <lasse.collin@tukaani.org>
Acked-by: Daniel Walker <danielwa@cisco.com>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
[Linux commit: 8e20ba2e53fc6198cbfbcc700e9f884157052a8d]
Signed-off-by: Jan Beulich <jbeulich@suse.com>
Reviewed-by: Luca Fancellu <luca.fancellu@arm.com>
---
v3: Retain all Linux side S-o-b, as per 5e326b61693c.

--- a/xen/common/xz/dec_lzma2.c
+++ b/xen/common/xz/dec_lzma2.c
@@ -1146,6 +1146,7 @@ XZ_EXTERN enum xz_ret __init xz_dec_lzma
 
 		if (DEC_IS_DYNALLOC(s->dict.mode)) {
 			if (s->dict.allocated < s->dict.size) {
+				s->dict.allocated = s->dict.size;
 				large_free(s->dict.buf);
 				s->dict.buf = large_malloc(s->dict.size);
 				if (s->dict.buf == NULL) {

[PATCH v3 3/7] decompressors: fix spelling mistakes

[Jan Beulich]

From: Zhen Lei <thunder.leizhen@huawei.com>

Fix some spelling mistakes in comments:
sentinal ==> sentinel
compresed ==> compressed
immediatelly ==> immediately
dervied ==> derived
splitted ==> split
nore ==> not
independed ==> independent
asumed ==> assumed

Link: https://lkml.kernel.org/r/20210604085656.12257-1-thunder.leizhen@huawei.com
Signed-off-by: Zhen Lei <thunder.leizhen@huawei.com>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
[Linux commit: 05911c5d964956442d17fe21db239de5a1dace4a]
Signed-off-by: Jan Beulich <jbeulich@suse.com>
Reviewed-by: Luca Fancellu <luca.fancellu@arm.com>
---
v3: Retain all Linux side S-o-b, as per 5e326b61693c.

--- a/xen/common/bunzip2.c
+++ b/xen/common/bunzip2.c
@@ -73,7 +73,7 @@
 
 /* This is what we know about each Huffman coding group */
 struct group_data {
-	/* We have an extra slot at the end of limit[] for a sentinal value. */
+	/* We have an extra slot at the end of limit[] for a sentinel value. */
 	int limit[MAX_HUFCODE_BITS+1];
 	int base[MAX_HUFCODE_BITS];
 	int permute[MAX_SYMBOLS];
@@ -326,7 +326,7 @@ static int __init get_next_block(struct
 			pp <<= 1;
 			base[i+1] = pp-(t += temp[i]);
 		}
-		limit[maxLen+1] = INT_MAX; /* Sentinal value for
+		limit[maxLen+1] = INT_MAX; /* Sentinel value for
 					    * reading next sym. */
 		limit[maxLen] = pp+temp[maxLen]-1;
 		base[minLen] = 0;
--- a/xen/common/unxz.c
+++ b/xen/common/unxz.c
@@ -23,7 +23,7 @@
  * uncompressible. Thus, we must look for worst-case expansion when the
  * compressor is encoding uncompressible data.
  *
- * The structure of the .xz file in case of a compresed kernel is as follows.
+ * The structure of the .xz file in case of a compressed kernel is as follows.
  * Sizes (as bytes) of the fields are in parenthesis.
  *
  *    Stream Header (12)
--- a/xen/common/unzstd.c
+++ b/xen/common/unzstd.c
@@ -16,7 +16,7 @@
  * 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.
+ * The structure of the .zst file in case of a compressed kernel is as follows.
  * Maximum sizes (as bytes) of the fields are in parenthesis.
  *
  *    Frame Header: (18)
--- a/xen/common/xz/dec_bcj.c
+++ b/xen/common/xz/dec_bcj.c
@@ -422,7 +422,7 @@ XZ_EXTERN enum xz_ret __init xz_dec_bcj_
 
 	/*
 	 * Flush pending already filtered data to the output buffer. Return
-	 * immediatelly if we couldn't flush everything, or if the next
+	 * immediately if we couldn't flush everything, or if the next
 	 * filter in the chain had already returned XZ_STREAM_END.
 	 */
 	if (s->temp.filtered > 0) {
--- a/xen/common/xz/dec_lzma2.c
+++ b/xen/common/xz/dec_lzma2.c
@@ -147,8 +147,8 @@ struct lzma_dec {
 
 	/*
 	 * LZMA properties or related bit masks (number of literal
-	 * context bits, a mask dervied from the number of literal
-	 * position bits, and a mask dervied from the number
+	 * context bits, a mask derived from the number of literal
+	 * position bits, and a mask derived from the number
 	 * position bits)
 	 */
 	uint32_t lc;
@@ -484,7 +484,7 @@ static always_inline void rc_normalize(s
 }
 
 /*
- * Decode one bit. In some versions, this function has been splitted in three
+ * Decode one bit. In some versions, this function has been split in three
  * functions so that the compiler is supposed to be able to more easily avoid
  * an extra branch. In this particular version of the LZMA decoder, this
  * doesn't seem to be a good idea (tested with GCC 3.3.6, 3.4.6, and 4.3.3
@@ -761,7 +761,7 @@ static bool_t __init lzma_main(struct xz
 }
 
 /*
- * Reset the LZMA decoder and range decoder state. Dictionary is nore reset
+ * Reset the LZMA decoder and range decoder state. Dictionary is not reset
  * here, because LZMA state may be reset without resetting the dictionary.
  */
 static void __init lzma_reset(struct xz_dec_lzma2 *s)
--- a/xen/common/zstd/huf.h
+++ b/xen/common/zstd/huf.h
@@ -131,7 +131,7 @@ typedef enum {
 	HUF_repeat_none,  /**< Cannot use the previous table */
 	HUF_repeat_check, /**< Can use the previous table but it must be checked. Note : The previous table must have been constructed by HUF_compress{1,
 			     4}X_repeat */
-	HUF_repeat_valid  /**< Can use the previous table and it is asumed to be valid */
+	HUF_repeat_valid  /**< Can use the previous table and it is assumed to be valid */
 } HUF_repeat;
 /** HUF_compress4X_repeat() :
 *   Same as HUF_compress4X_wksp(), but considers using hufTable if *repeat != HUF_repeat_none.

[PATCH v3 4/7] xz: avoid overlapping memcpy() with invalid input with in-place decompression

[Jan Beulich]

From: Lasse Collin <lasse.collin@tukaani.org>

With valid files, the safety margin described in lib/decompress_unxz.c
ensures that these buffers cannot overlap. But if the uncompressed size
of the input is larger than the caller thought, which is possible when
the input file is invalid/corrupt, the buffers can overlap. Obviously
the result will then be garbage (and usually the decoder will return
an error too) but no other harm will happen when such an over-run occurs.

This change only affects uncompressed LZMA2 chunks and so this
should have no effect on performance.

Link: https://lore.kernel.org/r/20211010213145.17462-2-xiang@kernel.org
Signed-off-by: Lasse Collin <lasse.collin@tukaani.org>
Signed-off-by: Gao Xiang <hsiangkao@linux.alibaba.com>
[Linux commit: 83d3c4f22a36d005b55f44628f46cc0d319a75e8]
Signed-off-by: Jan Beulich <jbeulich@suse.com>
Reviewed-by: Luca Fancellu <luca.fancellu@arm.com>
---
v2: Retain one more S-o-b.

--- a/xen/common/unxz.c
+++ b/xen/common/unxz.c
@@ -127,7 +127,7 @@
  * memeq and memzero are not used much and any remotely sane implementation
  * is fast enough. memcpy/memmove speed matters in multi-call mode, but
  * the kernel image is decompressed in single-call mode, in which only
- * memcpy speed can matter and only if there is a lot of uncompressible data
+ * memmove speed can matter and only if there is a lot of uncompressible data
  * (LZMA2 stores uncompressible chunks in uncompressed form). Thus, the
  * functions below should just be kept small; it's probably not worth
  * optimizing for speed.
--- a/xen/common/xz/dec_lzma2.c
+++ b/xen/common/xz/dec_lzma2.c
@@ -387,7 +387,14 @@ static void __init dict_uncompressed(str
 
 		*left -= copy_size;
 
-		memcpy(dict->buf + dict->pos, b->in + b->in_pos, copy_size);
+		/*
+		 * If doing in-place decompression in single-call mode and the
+		 * uncompressed size of the file is larger than the caller
+		 * thought (i.e. it is invalid input!), the buffers below may
+		 * overlap and cause undefined behavior with memcpy().
+		 * With valid inputs memcpy() would be fine here.
+		 */
+		memmove(dict->buf + dict->pos, b->in + b->in_pos, copy_size);
 		dict->pos += copy_size;
 
 		if (dict->full < dict->pos)
@@ -397,7 +404,11 @@ static void __init dict_uncompressed(str
 			if (dict->pos == dict->end)
 				dict->pos = 0;
 
-			memcpy(b->out + b->out_pos, b->in + b->in_pos,
+			/*
+			 * Like above but for multi-call mode: use memmove()
+			 * to avoid undefined behavior with invalid input.
+			 */
+			memmove(b->out + b->out_pos, b->in + b->in_pos,
 					copy_size);
 		}
 
@@ -421,6 +432,12 @@ static uint32_t __init dict_flush(struct
 		if (dict->pos == dict->end)
 			dict->pos = 0;
 
+		/*
+		 * These buffers cannot overlap even if doing in-place
+		 * decompression because in multi-call mode dict->buf
+		 * has been allocated by us in this file; it's not
+		 * provided by the caller like in single-call mode.
+		 */
 		memcpy(b->out + b->out_pos, dict->buf + dict->start,
 				copy_size);
 	}

[PATCH v3 5/7] xz: validate the value before assigning it to an enum variable

[Jan Beulich]

From: Lasse Collin <lasse.collin@tukaani.org>

This might matter, for example, if the underlying type of enum xz_check
was a signed char. In such a case the validation wouldn't have caught an
unsupported header. I don't know if this problem can occur in the kernel
on any arch but it's still good to fix it because some people might copy
the XZ code to their own projects from Linux instead of the upstream
XZ Embedded repository.

This change may increase the code size by a few bytes. An alternative
would have been to use an unsigned int instead of enum xz_check but
using an enumeration looks cleaner.

Link: https://lore.kernel.org/r/20211010213145.17462-3-xiang@kernel.org
Signed-off-by: Lasse Collin <lasse.collin@tukaani.org>
Signed-off-by: Gao Xiang <hsiangkao@linux.alibaba.com>
[Linux commit: 4f8d7abaa413c34da9d751289849dbfb7c977d05]
Signed-off-by: Jan Beulich <jbeulich@suse.com>
Reviewed-by: Luca Fancellu <luca.fancellu@arm.com>
---
v2: Retain one more S-o-b.

--- a/xen/common/xz/dec_stream.c
+++ b/xen/common/xz/dec_stream.c
@@ -402,12 +402,12 @@ static enum xz_ret __init dec_stream_hea
 	 * we will accept other check types too, but then the check won't
 	 * be verified and a warning (XZ_UNSUPPORTED_CHECK) will be given.
 	 */
+	if (s->temp.buf[HEADER_MAGIC_SIZE + 1] > XZ_CHECK_MAX)
+		return XZ_OPTIONS_ERROR;
+
 	s->check_type = s->temp.buf[HEADER_MAGIC_SIZE + 1];
 
 #ifdef XZ_DEC_ANY_CHECK
-	if (s->check_type > XZ_CHECK_MAX)
-		return XZ_OPTIONS_ERROR;
-
 	if (s->check_type > XZ_CHECK_CRC32)
 		return XZ_UNSUPPORTED_CHECK;
 #else

[PATCH v3 6/7] xz: move s->lzma.len = 0 initialization to lzma_reset()

[Jan Beulich]

From: Lasse Collin <lasse.collin@tukaani.org>

It's a more logical place even if the resetting needs to be done
only once per LZMA2 stream (if lzma_reset() called in the middle
of an LZMA2 stream, .len will already be 0).

Link: https://lore.kernel.org/r/20211010213145.17462-4-xiang@kernel.org
Signed-off-by: Lasse Collin <lasse.collin@tukaani.org>
Signed-off-by: Gao Xiang <hsiangkao@linux.alibaba.com>
[Linux commit: a98a25408b0e9b0264abcc3dabfafd9ff2ea1046]
Signed-off-by: Jan Beulich <jbeulich@suse.com>
Reviewed-by: Luca Fancellu <luca.fancellu@arm.com>
---
v2: Retain one more S-o-b.

--- a/xen/common/xz/dec_lzma2.c
+++ b/xen/common/xz/dec_lzma2.c
@@ -791,6 +791,7 @@ static void __init lzma_reset(struct xz_
 	s->lzma.rep1 = 0;
 	s->lzma.rep2 = 0;
 	s->lzma.rep3 = 0;
+	s->lzma.len = 0;
 
 	/*
 	 * All probabilities are initialized to the same value. This hack
@@ -1174,8 +1175,6 @@ XZ_EXTERN enum xz_ret __init xz_dec_lzma
 		}
 	}
 
-	s->lzma.len = 0;
-
 	s->lzma2.sequence = SEQ_CONTROL;
 	s->lzma2.need_dict_reset = true;
 

[PATCH v3 7/7] xz: fix spelling in comments

[Jan Beulich]

From: Lasse Collin <lasse.collin@tukaani.org>

uncompressible -> incompressible
non-splitted -> non-split

Link: https://lore.kernel.org/r/20211010213145.17462-6-xiang@kernel.org
Signed-off-by: Lasse Collin <lasse.collin@tukaani.org>
Signed-off-by: Gao Xiang <hsiangkao@linux.alibaba.com>
[Linux commit: 0a434e0a2c9f4395e4560aac22677ef25ab4afd9]
Signed-off-by: Jan Beulich <jbeulich@suse.com>
Reviewed-by: Luca Fancellu <luca.fancellu@arm.com>
---
v2: Retain one more S-o-b.

--- a/xen/common/unxz.c
+++ b/xen/common/unxz.c
@@ -20,8 +20,8 @@
  *
  * 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.
+ * incompressible. Thus, we must look for worst-case expansion when the
+ * compressor is encoding incompressible data.
  *
  * The structure of the .xz file in case of a compressed kernel is as follows.
  * Sizes (as bytes) of the fields are in parenthesis.
@@ -58,7 +58,7 @@
  * uncompressed size of the payload is in practice never less than the
  * payload size itself. The LZMA2 format would allow uncompressed size
  * to be less than the payload size, but no sane compressor creates such
- * files. LZMA2 supports storing uncompressible data in uncompressed form,
+ * files. LZMA2 supports storing incompressible data in uncompressed form,
  * so there's never a need to create payloads whose uncompressed size is
  * smaller than the compressed size.
  *
@@ -127,8 +127,8 @@
  * memeq and memzero are not used much and any remotely sane implementation
  * is fast enough. memcpy/memmove speed matters in multi-call mode, but
  * the kernel image is decompressed in single-call mode, in which only
- * memmove speed can matter and only if there is a lot of uncompressible data
- * (LZMA2 stores uncompressible chunks in uncompressed form). Thus, the
+ * memmove speed can matter and only if there is a lot of incompressible data
+ * (LZMA2 stores incompressible chunks in uncompressed form). Thus, the
  * functions below should just be kept small; it's probably not worth
  * optimizing for speed.
  */
--- a/xen/common/xz/dec_lzma2.c
+++ b/xen/common/xz/dec_lzma2.c
@@ -505,7 +505,7 @@ static always_inline void rc_normalize(s
  * functions so that the compiler is supposed to be able to more easily avoid
  * an extra branch. In this particular version of the LZMA decoder, this
  * doesn't seem to be a good idea (tested with GCC 3.3.6, 3.4.6, and 4.3.3
- * on x86). Using a non-splitted version results in nicer looking code too.
+ * on x86). Using a non-split version results in nicer looking code too.
  *
  * NOTE: This must return an int. Do not make it return a bool or the speed
  * of the code generated by GCC 3.x decreases 10-15 %. (GCC 4.3 doesn't care,

Re: [PATCH v3 0/7] (mainly) xz imports from Linux

[Jan Beulich]

On 03.03.2022 11:03, Jan Beulich wrote:
> While going through their 5.15.3 log I did notice two changes, which made
> me go check what else we might be missing. The series here is the result.
> Linux has also updated zstd, but that includes a pretty large change which
> I'm not ready to deal with right now. Them moving closer to the upstream
> zstd sources is certainly a good thing, so I suppose sooner or later we
> will want to follow them in doing so.
> 
> The only change in v3 is the re-adding of some previously dropped S-o-b in
> patches 2 and 3, to satisfy the rules newly established by 5e326b61693c.
> 
> As the series has R-b by Luca and as the (not) retaining of certain tags
> was the only open issue in v1 and v2, I won't wait long until committing
> this; perhaps just until after the weekend.

I did notice only when already in the process of sending that I should also
have converted to the new Origin: tag. I've done this locally, but won't
resend just for this.

Jan

> 1: xz: add fall-through comments to a switch statement
> 2: xz: fix XZ_DYNALLOC to avoid useless memory reallocations
> 3: decompressors: fix spelling mistakes
> 4: xz: avoid overlapping memcpy() with invalid input with in-place decompression
> 5: xz: fix spelling in comments
> 6: xz: move s->lzma.len = 0 initialization to lzma_reset()
> 7: xz: validate the value before assigning it to an enum variable
> 
> Jan

Re: [PATCH v3 0/7] (mainly) xz imports from Linux

[Andrew Cooper]

On 03/03/2022 10:03, Jan Beulich wrote:
> 1: xz: add fall-through comments to a switch statement
> 2: xz: fix XZ_DYNALLOC to avoid useless memory reallocations
> 3: decompressors: fix spelling mistakes
> 4: xz: avoid overlapping memcpy() with invalid input with in-place decompression
> 5: xz: fix spelling in comments
> 6: xz: move s->lzma.len = 0 initialization to lzma_reset()
> 7: xz: validate the value before assigning it to an enum variable

Acked-by: Andrew Cooper <andrew.cooper3@citrix.com>