Re: [PATCH v2] lib/lz4: backport upstream fast decode loop

Re: [PATCH v2] lib/lz4: backport upstream fast decode loop

[sashiko-bot]

Thank you for your contribution! Sashiko AI review found 1 potential
issue to consider:
- [High] lib/lz4: 32-bit size_t overflow in LZ4_decompress_generic()
  length addition
--

commit 007dc43642875bedabb77ae7e51314787e661069
Author: S. Biplab Raut <Biplab.Raut@amd.com>

lib/lz4: backport upstream fast decode loop

This commit backports the upstream LZ4 v1.9.2 fast decode loop and shared
variable-length reader into LZ4_decompress_generic(), along with size_t
overflow and match-length bounds checks.

Link: https://github.com/lz4/lz4/commit/28356e02ad6f6dac529302cedf707712c5b628fe
Link: https://github.com/lz4/lz4/pull/645

> diff --git a/lib/lz4/lz4_decompress.c b/lib/lz4/lz4_decompress.c
> index 3a2cd9acada4a..1155d5a369f43 100644
> --- a/lib/lz4/lz4_decompress.c
> +++ b/lib/lz4/lz4_decompress.c
> @@ -49,12 +49,176 @@

[ ... ]

> +static FORCE_INLINE size_t
> +read_variable_length(const BYTE **ip, const BYTE *lencheck,
> +		     int loop_check, int initial_check,
> +		     enum variable_length_error *error)
> +{
> +	size_t length = 0;
> +	size_t s;
> +
> +	if (initial_check && unlikely((*ip) >= lencheck)) {
> +		/* overflow detection */
> +		*error = initial_error;
> +		return length;
> +	}
> +
> +	do {
> +		s = **ip;
> +		(*ip)++;
> +		if (unlikely(length > SIZE_MAX - s)) {
> +			*error = overflow_error;
> +			return length;
> +		}
> +		length += s;
> +		if (loop_check && unlikely((*ip) >= lencheck)) {
> +			/* overflow detection */
> +			*error = loop_error;
> +			return length;
> +		}
> +	} while (s == 255);
> +
> +	return length;
> +}

[ ... ]

> @@ -293,44 +655,30 @@ static FORCE_INLINE int LZ4_decompress_generic(
>  		length = token & ML_MASK;
>  
>  _copy_match:
> -		if ((checkOffset) && (unlikely(match + dictSize < lowPrefix))) {
> -			/* Error : offset outside buffers */
> -			goto _output_error;
> -		}
> -
> -		/* costs ~1%; silence an msan warning when offset == 0 */
> -		/*
> -		 * note : when partialDecoding, there is no guarantee that
> -		 * at least 4 bytes remain available in output buffer
> -		 */
> -		if (!partialDecoding) {
> -			assert(oend > op);
> -			assert(oend - op >= 4);
> -
> -			LZ4_write32(op, (U32)offset);
> -		}
> -
>  		if (length == ML_MASK) {
> -			unsigned int s;
> -
> -			do {
> -				s = *ip++;
> -
> -				if ((endOnInput) && (ip > iend - LASTLITERALS))
> -					goto _output_error;
> -
> -				length += s;
> -			} while (s == 255);
> +			enum variable_length_error error = ok;
>  
> -			if ((safeDecode)
> -				&& unlikely(
> -					(uptrval)(op) + length < (uptrval)op)) {
> -				/* overflow detection */
> +			length += read_variable_length(&ip,
> +					iend - LASTLITERALS + 1,
> +					(int)endOnInput, 0, &error);
> +			if (error != ok)
>  				goto _output_error;
> -			}
>  		}
>  
>  		length += MINMATCH;
> +		if ((safeDecode) && unlikely((uptrval)(op) +
> +					length < (uptrval)op)) {
> +			/* overflow detection */
> +			goto _output_error;
> +		}

[Severity: High]
Can adding the result of read_variable_length() to length still wrap a
32-bit size_t in LZ4_decompress_generic()?

read_variable_length() starts its local accumulator at 0 and checks
length > SIZE_MAX - s, without accounting for the caller's initial
RUN_MASK (15) on literal lengths or ML_MASK + MINMATCH (19) on match
lengths in both the fast and safe loops.  On 32-bit architectures, a
crafted ~16 MiB extension chain can return a value in [SIZE_MAX - 18,
SIZE_MAX] with error == ok, wrapping length to 0..14 for literals or
0..18 for matches before the op + length and ip + length wrap checks.

When a match length wraps to 0..3 (below MINMATCH), cpy = op + length can
stay at or below oend - MATCH_SAFEGUARD_DISTANCE (12) when op is in
[oend - 15, oend - 12], bypassing the safeguard check and writing up to 4
bytes past oend in the second LZ4_copy8(op, match):

lib/lz4/lz4_decompress.c:LZ4_decompress_generic() {
    ...
		op += 8;

		if (unlikely(cpy > oend - MATCH_SAFEGUARD_DISTANCE)) {
    ...
		} else {
			LZ4_copy8(op, match);
			if (length > 16)
				LZ4_wildCopy(op + 8, match + 8, cpy);
		}
		op = cpy; /* wildcopy correction */
}

Checking for overflow when adding the base length and MINMATCH (or passing
the initial length into read_variable_length()) would prevent the wrap.

-- 
Sashiko AI review · https://sashiko.dev/#/patchset/20261114171452.1484344-1-Biplab.Raut@amd.com?part=1