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

[sashiko-bot@kernel.org]

Thank you for your contribution! Sashiko AI review found 1 potential issue(s) to consider:
- [Medium] lib/lz4: pointer overflow check before adding MINMATCH in LZ4_decompress_generic()
--

commit 470e38e27e55da2aeb57c59ceef99c817952636e
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 into
LZ4_decompress_generic() for x86 and non-clang arm64 targets, along with
the shared variable-length reader and updated safe-loop control flow.

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..bb201c9484dda 100644
> --- a/lib/lz4/lz4_decompress.c
> +++ b/lib/lz4/lz4_decompress.c

[ ... ]

> @@ -116,15 +273,200 @@ static FORCE_INLINE int LZ4_decompress_generic(

[ ... ]

> +		/* get matchlength */
> +		length = token & ML_MASK;
> +
> +		if (length == ML_MASK) {
> +			enum variable_length_error error = ok;
> +
> +			if ((checkOffset) &&
> +			    (unlikely(match + dictSize < lowPrefix))) {
> +				/* Error : offset outside buffers */
> +				goto _output_error;
> +			}
> +			length += read_variable_length(&ip,
> +					iend - LASTLITERALS + 1,
> +					(int)endOnInput, 0, &error);
> +			if (error != ok)
> +				goto _output_error;
> +			if ((safeDecode) && unlikely((uptrval)(op) +
> +						length < (uptrval)op)) {
> +				/* overflow detection */
> +				goto _output_error;
> +			}
> +			length += MINMATCH;
> +			if (op + length >= oend - FASTLOOP_SAFE_DISTANCE)
> +				goto safe_match_copy;

[Severity: Medium]
In LZ4_decompress_generic() in lib/lz4/lz4_decompress.c, can checking for
(uptrval)(op) + length < (uptrval)op before adding MINMATCH (4) allow
op + length to wrap around the address space?

When safeDecode is enabled and a match token has length == ML_MASK, if a
crafted input stream supplies enough 0xff extension bytes so that
(uptrval)op + length lands within 4 bytes of the top of the address space
prior to length += MINMATCH, the overflow check passes because op <=
oend - FASTLOOP_SAFE_DISTANCE.

Adding MINMATCH then wraps op + length around to 0x0..0x3, which bypasses
the op + length >= oend - FASTLOOP_SAFE_DISTANCE check, sets cpy = op +
length to 0x0..0x3, copies 32 bytes in LZ4_wildCopy32(op, match, cpy)
before terminating because d < cpy is false, and leaves op pointing to
0x0..0x3 for the next iteration.

Additionally, read_variable_length() accumulates into an unsigned int
length, which can wrap modulo 2^32 if srcSize exceeds roughly 16.8 MB of
0xff bytes.

[ ... ]

> @@ -293,38 +645,16 @@ static FORCE_INLINE int LZ4_decompress_generic(
>  		length = token & ML_MASK;
>  
>  _copy_match:

[ ... ]

>  		if (length == ML_MASK) {
> -			unsigned int s;
> +			enum variable_length_error error = ok;
>  
> -			do {
> -				s = *ip++;
> -
> -				if ((endOnInput) && (ip > iend - LASTLITERALS))
> -					goto _output_error;
> -
> -				length += s;
> -			} while (s == 255);
> -
> -			if ((safeDecode)
> -				&& unlikely(
> -					(uptrval)(op) + length < (uptrval)op)) {
> +			length += read_variable_length(&ip,
> +					iend - LASTLITERALS + 1,
> +					(int)endOnInput, 0, &error);
> +			if (error != ok)
> +				goto _output_error;
> +			if ((safeDecode) && unlikely((uptrval)(op) +
> +						length < (uptrval)op)) {
>  				/* overflow detection */
>  				goto _output_error;
>  			}
>  		}
>  
>  		length += MINMATCH;

[Severity: Medium]
Similarly in the safe loop of LZ4_decompress_generic() in
lib/lz4/lz4_decompress.c, should length += MINMATCH happen before checking
(uptrval)(op) + length < (uptrval)op (or should the check include
MINMATCH) so that cpy = op + length cannot wrap around by up to 4 bytes
and bypass the subsequent cpy > oend - MATCH_SAFEGUARD_DISTANCE bounds
check?

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