[PATCH] lib/lzo: Avoid output overruns when compressing

[PATCH] lib/lzo: Avoid output overruns when compressing

[Herbert Xu]

The compression code in LZO never checked for output overruns.
Fix this by checking for end of buffer before each write.

Fixes: 64c70b1cf43d ("Add LZO1X algorithm to the kernel")
Signed-off-by: Herbert Xu <herbert@gondor.apana.org.au>

diff --git a/lib/lzo/lzo1x_compress.c b/lib/lzo/lzo1x_compress.c
index 47d6d43ea957..5d2f2f851694 100644
--- a/lib/lzo/lzo1x_compress.c
+++ b/lib/lzo/lzo1x_compress.c
@@ -18,10 +18,10 @@
 #include <linux/lzo.h>
 #include "lzodefs.h"
 
-static noinline size_t
+static noinline int
 lzo1x_1_do_compress(const unsigned char *in, size_t in_len,
-		    unsigned char *out, size_t *out_len,
-		    size_t ti, void *wrkmem, signed char *state_offset,
+		    unsigned char **out, unsigned char *op_end,
+		    size_t *tp, void *wrkmem, signed char *state_offset,
 		    const unsigned char bitstream_version)
 {
 	const unsigned char *ip;
@@ -30,8 +30,9 @@ lzo1x_1_do_compress(const unsigned char *in, size_t in_len,
 	const unsigned char * const ip_end = in + in_len - 20;
 	const unsigned char *ii;
 	lzo_dict_t * const dict = (lzo_dict_t *) wrkmem;
+	size_t ti = *tp;
 
-	op = out;
+	op = *out;
 	ip = in;
 	ii = ip;
 	ip += ti < 4 ? 4 - ti : 0;
@@ -116,25 +117,41 @@ lzo1x_1_do_compress(const unsigned char *in, size_t in_len,
 		if (t != 0) {
 			if (t <= 3) {
 				op[*state_offset] |= t;
+				if (!HAVE_OP(4))
+					return LZO_E_OUTPUT_OVERRUN;
 				COPY4(op, ii);
 				op += t;
 			} else if (t <= 16) {
+				if (!HAVE_OP(1))
+					return LZO_E_OUTPUT_OVERRUN;
 				*op++ = (t - 3);
+				if (!HAVE_OP(16))
+					return LZO_E_OUTPUT_OVERRUN;
 				COPY8(op, ii);
 				COPY8(op + 8, ii + 8);
 				op += t;
 			} else {
 				if (t <= 18) {
+					if (!HAVE_OP(1))
+						return LZO_E_OUTPUT_OVERRUN;
 					*op++ = (t - 3);
 				} else {
 					size_t tt = t - 18;
+					if (!HAVE_OP(1))
+						return LZO_E_OUTPUT_OVERRUN;
 					*op++ = 0;
 					while (unlikely(tt > 255)) {
 						tt -= 255;
+						if (!HAVE_OP(1))
+							return LZO_E_OUTPUT_OVERRUN;
 						*op++ = 0;
 					}
+					if (!HAVE_OP(1))
+						return LZO_E_OUTPUT_OVERRUN;
 					*op++ = tt;
 				}
+				if (!HAVE_OP(t))
+					return LZO_E_OUTPUT_OVERRUN;
 				do {
 					COPY8(op, ii);
 					COPY8(op + 8, ii + 8);
@@ -151,6 +168,8 @@ lzo1x_1_do_compress(const unsigned char *in, size_t in_len,
 		if (unlikely(run_length)) {
 			ip += run_length;
 			run_length -= MIN_ZERO_RUN_LENGTH;
+			if (!HAVE_OP(4))
+				return LZO_E_OUTPUT_OVERRUN;
 			put_unaligned_le32((run_length << 21) | 0xfffc18
 					   | (run_length & 0x7), op);
 			op += 4;
@@ -243,10 +262,14 @@ lzo1x_1_do_compress(const unsigned char *in, size_t in_len,
 		ip += m_len;
 		if (m_len <= M2_MAX_LEN && m_off <= M2_MAX_OFFSET) {
 			m_off -= 1;
+			if (!HAVE_OP(2))
+				return LZO_E_OUTPUT_OVERRUN;
 			*op++ = (((m_len - 1) << 5) | ((m_off & 7) << 2));
 			*op++ = (m_off >> 3);
 		} else if (m_off <= M3_MAX_OFFSET) {
 			m_off -= 1;
+			if (!HAVE_OP(1))
+				return LZO_E_OUTPUT_OVERRUN;
 			if (m_len <= M3_MAX_LEN)
 				*op++ = (M3_MARKER | (m_len - 2));
 			else {
@@ -254,14 +277,22 @@ lzo1x_1_do_compress(const unsigned char *in, size_t in_len,
 				*op++ = M3_MARKER | 0;
 				while (unlikely(m_len > 255)) {
 					m_len -= 255;
+					if (!HAVE_OP(1))
+						return LZO_E_OUTPUT_OVERRUN;
 					*op++ = 0;
 				}
+				if (!HAVE_OP(1))
+					return LZO_E_OUTPUT_OVERRUN;
 				*op++ = (m_len);
 			}
+			if (!HAVE_OP(2))
+				return LZO_E_OUTPUT_OVERRUN;
 			*op++ = (m_off << 2);
 			*op++ = (m_off >> 6);
 		} else {
 			m_off -= 0x4000;
+			if (!HAVE_OP(1))
+				return LZO_E_OUTPUT_OVERRUN;
 			if (m_len <= M4_MAX_LEN)
 				*op++ = (M4_MARKER | ((m_off >> 11) & 8)
 						| (m_len - 2));
@@ -282,11 +313,17 @@ lzo1x_1_do_compress(const unsigned char *in, size_t in_len,
 				m_len -= M4_MAX_LEN;
 				*op++ = (M4_MARKER | ((m_off >> 11) & 8));
 				while (unlikely(m_len > 255)) {
+					if (!HAVE_OP(1))
+						return LZO_E_OUTPUT_OVERRUN;
 					m_len -= 255;
 					*op++ = 0;
 				}
+				if (!HAVE_OP(1))
+					return LZO_E_OUTPUT_OVERRUN;
 				*op++ = (m_len);
 			}
+			if (!HAVE_OP(2))
+				return LZO_E_OUTPUT_OVERRUN;
 			*op++ = (m_off << 2);
 			*op++ = (m_off >> 6);
 		}
@@ -295,14 +332,16 @@ lzo1x_1_do_compress(const unsigned char *in, size_t in_len,
 		ii = ip;
 		goto next;
 	}
-	*out_len = op - out;
-	return in_end - (ii - ti);
+	*out = op;
+	*tp = in_end - (ii - ti);
+	return LZO_E_OK;
 }
 
 static int lzogeneric1x_1_compress(const unsigned char *in, size_t in_len,
 		     unsigned char *out, size_t *out_len,
 		     void *wrkmem, const unsigned char bitstream_version)
 {
+	unsigned char * const op_end = out + *out_len;
 	const unsigned char *ip = in;
 	unsigned char *op = out;
 	unsigned char *data_start;
@@ -326,14 +365,17 @@ static int lzogeneric1x_1_compress(const unsigned char *in, size_t in_len,
 	while (l > 20) {
 		size_t ll = min_t(size_t, l, m4_max_offset + 1);
 		uintptr_t ll_end = (uintptr_t) ip + ll;
+		int err;
+
 		if ((ll_end + ((t + ll) >> 5)) <= ll_end)
 			break;
 		BUILD_BUG_ON(D_SIZE * sizeof(lzo_dict_t) > LZO1X_1_MEM_COMPRESS);
 		memset(wrkmem, 0, D_SIZE * sizeof(lzo_dict_t));
-		t = lzo1x_1_do_compress(ip, ll, op, out_len, t, wrkmem,
-					&state_offset, bitstream_version);
+		err = lzo1x_1_do_compress(ip, ll, &op, op_end, &t, wrkmem,
+					  &state_offset, bitstream_version);
+		if (err != LZO_E_OK)
+			return err;
 		ip += ll;
-		op += *out_len;
 		l  -= ll;
 	}
 	t += l;
@@ -342,20 +384,32 @@ static int lzogeneric1x_1_compress(const unsigned char *in, size_t in_len,
 		const unsigned char *ii = in + in_len - t;
 
 		if (op == data_start && t <= 238) {
+			if (!HAVE_OP(1))
+				return LZO_E_OUTPUT_OVERRUN;
 			*op++ = (17 + t);
 		} else if (t <= 3) {
 			op[state_offset] |= t;
 		} else if (t <= 18) {
+			if (!HAVE_OP(1))
+				return LZO_E_OUTPUT_OVERRUN;
 			*op++ = (t - 3);
 		} else {
 			size_t tt = t - 18;
+			if (!HAVE_OP(1))
+				return LZO_E_OUTPUT_OVERRUN;
 			*op++ = 0;
 			while (tt > 255) {
 				tt -= 255;
+				if (!HAVE_OP(1))
+					return LZO_E_OUTPUT_OVERRUN;
 				*op++ = 0;
 			}
+			if (!HAVE_OP(1))
+				return LZO_E_OUTPUT_OVERRUN;
 			*op++ = tt;
 		}
+		if (!HAVE_OP(t))
+			return LZO_E_OUTPUT_OVERRUN;
 		if (t >= 16) do {
 			COPY8(op, ii);
 			COPY8(op + 8, ii + 8);
@@ -368,6 +422,8 @@ static int lzogeneric1x_1_compress(const unsigned char *in, size_t in_len,
 		} while (--t > 0);
 	}
 
+	if (!HAVE_OP(3))
+		return LZO_E_OUTPUT_OVERRUN;
 	*op++ = M4_MARKER | 1;
 	*op++ = 0;
 	*op++ = 0;
diff --git a/lib/lzo/lzo1x_decompress_safe.c b/lib/lzo/lzo1x_decompress_safe.c
index c94f4928e188..4d5a1b58a4a0 100644
--- a/lib/lzo/lzo1x_decompress_safe.c
+++ b/lib/lzo/lzo1x_decompress_safe.c
@@ -21,7 +21,6 @@
 #include "lzodefs.h"
 
 #define HAVE_IP(x)      ((size_t)(ip_end - ip) >= (size_t)(x))
-#define HAVE_OP(x)      ((size_t)(op_end - op) >= (size_t)(x))
 #define NEED_IP(x)      if (!HAVE_IP(x)) goto input_overrun
 #define NEED_OP(x)      if (!HAVE_OP(x)) goto output_overrun
 #define TEST_LB(m_pos)  if ((m_pos) < out) goto lookbehind_overrun
diff --git a/lib/lzo/lzodefs.h b/lib/lzo/lzodefs.h
index b60851fcf6ce..8b1a46993acf 100644
--- a/lib/lzo/lzodefs.h
+++ b/lib/lzo/lzodefs.h
@@ -19,6 +19,7 @@
  */
 #define LZO_VERSION 1
 
+#define HAVE_OP(x)      ((size_t)(op_end - op) >= (size_t)(x))
 #define COPY4(dst, src)	\
 		put_unaligned(get_unaligned((const u32 *)(src)), (u32 *)(dst))
 #if defined(CONFIG_X86_64) || defined(CONFIG_ARM64)
-- 
Email: Herbert Xu <herbert@gondor.apana.org.au>
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt

Re: [PATCH] lib/lzo: Avoid output overruns when compressing

[Sergey Senozhatsky]

On (25/02/23 14:55), Herbert Xu wrote:
[..]
>  		} else if (m_off <= M3_MAX_OFFSET) {
>  			m_off -= 1;
> +			if (!HAVE_OP(1))
> +				return LZO_E_OUTPUT_OVERRUN;
>  			if (m_len <= M3_MAX_LEN)
>  				*op++ = (M3_MARKER | (m_len - 2));
>  			else {
[..]
>  		} else {
>  			m_off -= 0x4000;
> +			if (!HAVE_OP(1))
> +				return LZO_E_OUTPUT_OVERRUN;
>  			if (m_len <= M4_MAX_LEN)
>  				*op++ = (M4_MARKER | ((m_off >> 11) & 8)
>  						| (m_len - 2));

Made me wonder if HAVE_OP() in these two cases should have been
under if, but it covers both if and else branches, so it's all
right.

[..]
> +++ b/lib/lzo/lzo1x_decompress_safe.c
> @@ -21,7 +21,6 @@
>  #include "lzodefs.h"
>  
>  #define HAVE_IP(x)      ((size_t)(ip_end - ip) >= (size_t)(x))
> -#define HAVE_OP(x)      ((size_t)(op_end - op) >= (size_t)(x))
>  #define NEED_IP(x)      if (!HAVE_IP(x)) goto input_overrun
>  #define NEED_OP(x)      if (!HAVE_OP(x)) goto output_overrun

A bit of a pity that NEED_OP() with "goto output_overrun" is only
for decompression.  It looks equally relevant to the compression
path.  I'm not insisting on doing something similar in compression
tho.

Overall this look right, and kudos to Herbert for doing this.

I did some testing (using my usual zram test scripts, but modified
zram to allocate only one physical page for comp buf and to check
for overrun ret status).  Haven't noticed any problems.

FWIW
Reviewed-and-tested-by: Sergey Senozhatsky <senozhatsky@chromium.org>

Re: [PATCH] lib/lzo: Avoid output overruns when compressing

[Herbert Xu]

On Sun, Feb 23, 2025 at 05:40:31PM +0900, Sergey Senozhatsky wrote:
>
> A bit of a pity that NEED_OP() with "goto output_overrun" is only
> for decompression.  It looks equally relevant to the compression
> path.  I'm not insisting on doing something similar in compression
> tho.

I thought HAVE_OP looked nicer but I'll switch to NEED_OP for
the sake of consistency.

Thanks,
-- 
Email: Herbert Xu <herbert@gondor.apana.org.au>
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt

Re: [PATCH] lib/lzo: Avoid output overruns when compressing

[Markus F.X.J. Oberhumer]

LZO declares "*out_len" as output parameter because

  #define lzo1x_worst_compress(x) ((x) + ((x) / 16) + 64 + 3 + 2)

~Markus


On 2025-02-23 07:55, Herbert Xu wrote:
> The compression code in LZO never checked for output overruns.
> Fix this by checking for end of buffer before each write.
> 
> Fixes: 64c70b1cf43d ("Add LZO1X algorithm to the kernel")
> Signed-off-by: Herbert Xu <herbert@gondor.apana.org.au>
> 
> diff --git a/lib/lzo/lzo1x_compress.c b/lib/lzo/lzo1x_compress.c
> index 47d6d43ea957..5d2f2f851694 100644
> --- a/lib/lzo/lzo1x_compress.c
> +++ b/lib/lzo/lzo1x_compress.c
> @@ -18,10 +18,10 @@
>  #include <linux/lzo.h>
>  #include "lzodefs.h"
>  
> -static noinline size_t
> +static noinline int
>  lzo1x_1_do_compress(const unsigned char *in, size_t in_len,
> -		    unsigned char *out, size_t *out_len,
> -		    size_t ti, void *wrkmem, signed char *state_offset,
> +		    unsigned char **out, unsigned char *op_end,
> +		    size_t *tp, void *wrkmem, signed char *state_offset,
>  		    const unsigned char bitstream_version)
>  {
>  	const unsigned char *ip;
> @@ -30,8 +30,9 @@ lzo1x_1_do_compress(const unsigned char *in, size_t in_len,
>  	const unsigned char * const ip_end = in + in_len - 20;
>  	const unsigned char *ii;
>  	lzo_dict_t * const dict = (lzo_dict_t *) wrkmem;
> +	size_t ti = *tp;
>  
> -	op = out;
> +	op = *out;
>  	ip = in;
>  	ii = ip;
>  	ip += ti < 4 ? 4 - ti : 0;
> @@ -116,25 +117,41 @@ lzo1x_1_do_compress(const unsigned char *in, size_t in_len,
>  		if (t != 0) {
>  			if (t <= 3) {
>  				op[*state_offset] |= t;
> +				if (!HAVE_OP(4))
> +					return LZO_E_OUTPUT_OVERRUN;
>  				COPY4(op, ii);
>  				op += t;
>  			} else if (t <= 16) {
> +				if (!HAVE_OP(1))
> +					return LZO_E_OUTPUT_OVERRUN;
>  				*op++ = (t - 3);
> +				if (!HAVE_OP(16))
> +					return LZO_E_OUTPUT_OVERRUN;
>  				COPY8(op, ii);
>  				COPY8(op + 8, ii + 8);
>  				op += t;
>  			} else {
>  				if (t <= 18) {
> +					if (!HAVE_OP(1))
> +						return LZO_E_OUTPUT_OVERRUN;
>  					*op++ = (t - 3);
>  				} else {
>  					size_t tt = t - 18;
> +					if (!HAVE_OP(1))
> +						return LZO_E_OUTPUT_OVERRUN;
>  					*op++ = 0;
>  					while (unlikely(tt > 255)) {
>  						tt -= 255;
> +						if (!HAVE_OP(1))
> +							return LZO_E_OUTPUT_OVERRUN;
>  						*op++ = 0;
>  					}
> +					if (!HAVE_OP(1))
> +						return LZO_E_OUTPUT_OVERRUN;
>  					*op++ = tt;
>  				}
> +				if (!HAVE_OP(t))
> +					return LZO_E_OUTPUT_OVERRUN;
>  				do {
>  					COPY8(op, ii);
>  					COPY8(op + 8, ii + 8);
> @@ -151,6 +168,8 @@ lzo1x_1_do_compress(const unsigned char *in, size_t in_len,
>  		if (unlikely(run_length)) {
>  			ip += run_length;
>  			run_length -= MIN_ZERO_RUN_LENGTH;
> +			if (!HAVE_OP(4))
> +				return LZO_E_OUTPUT_OVERRUN;
>  			put_unaligned_le32((run_length << 21) | 0xfffc18
>  					   | (run_length & 0x7), op);
>  			op += 4;
> @@ -243,10 +262,14 @@ lzo1x_1_do_compress(const unsigned char *in, size_t in_len,
>  		ip += m_len;
>  		if (m_len <= M2_MAX_LEN && m_off <= M2_MAX_OFFSET) {
>  			m_off -= 1;
> +			if (!HAVE_OP(2))
> +				return LZO_E_OUTPUT_OVERRUN;
>  			*op++ = (((m_len - 1) << 5) | ((m_off & 7) << 2));
>  			*op++ = (m_off >> 3);
>  		} else if (m_off <= M3_MAX_OFFSET) {
>  			m_off -= 1;
> +			if (!HAVE_OP(1))
> +				return LZO_E_OUTPUT_OVERRUN;
>  			if (m_len <= M3_MAX_LEN)
>  				*op++ = (M3_MARKER | (m_len - 2));
>  			else {
> @@ -254,14 +277,22 @@ lzo1x_1_do_compress(const unsigned char *in, size_t in_len,
>  				*op++ = M3_MARKER | 0;
>  				while (unlikely(m_len > 255)) {
>  					m_len -= 255;
> +					if (!HAVE_OP(1))
> +						return LZO_E_OUTPUT_OVERRUN;
>  					*op++ = 0;
>  				}
> +				if (!HAVE_OP(1))
> +					return LZO_E_OUTPUT_OVERRUN;
>  				*op++ = (m_len);
>  			}
> +			if (!HAVE_OP(2))
> +				return LZO_E_OUTPUT_OVERRUN;
>  			*op++ = (m_off << 2);
>  			*op++ = (m_off >> 6);
>  		} else {
>  			m_off -= 0x4000;
> +			if (!HAVE_OP(1))
> +				return LZO_E_OUTPUT_OVERRUN;
>  			if (m_len <= M4_MAX_LEN)
>  				*op++ = (M4_MARKER | ((m_off >> 11) & 8)
>  						| (m_len - 2));
> @@ -282,11 +313,17 @@ lzo1x_1_do_compress(const unsigned char *in, size_t in_len,
>  				m_len -= M4_MAX_LEN;
>  				*op++ = (M4_MARKER | ((m_off >> 11) & 8));
>  				while (unlikely(m_len > 255)) {
> +					if (!HAVE_OP(1))
> +						return LZO_E_OUTPUT_OVERRUN;
>  					m_len -= 255;
>  					*op++ = 0;
>  				}
> +				if (!HAVE_OP(1))
> +					return LZO_E_OUTPUT_OVERRUN;
>  				*op++ = (m_len);
>  			}
> +			if (!HAVE_OP(2))
> +				return LZO_E_OUTPUT_OVERRUN;
>  			*op++ = (m_off << 2);
>  			*op++ = (m_off >> 6);
>  		}
> @@ -295,14 +332,16 @@ lzo1x_1_do_compress(const unsigned char *in, size_t in_len,
>  		ii = ip;
>  		goto next;
>  	}
> -	*out_len = op - out;
> -	return in_end - (ii - ti);
> +	*out = op;
> +	*tp = in_end - (ii - ti);
> +	return LZO_E_OK;
>  }
>  
>  static int lzogeneric1x_1_compress(const unsigned char *in, size_t in_len,
>  		     unsigned char *out, size_t *out_len,
>  		     void *wrkmem, const unsigned char bitstream_version)
>  {
> +	unsigned char * const op_end = out + *out_len;
>  	const unsigned char *ip = in;
>  	unsigned char *op = out;
>  	unsigned char *data_start;
> @@ -326,14 +365,17 @@ static int lzogeneric1x_1_compress(const unsigned char *in, size_t in_len,
>  	while (l > 20) {
>  		size_t ll = min_t(size_t, l, m4_max_offset + 1);
>  		uintptr_t ll_end = (uintptr_t) ip + ll;
> +		int err;
> +
>  		if ((ll_end + ((t + ll) >> 5)) <= ll_end)
>  			break;
>  		BUILD_BUG_ON(D_SIZE * sizeof(lzo_dict_t) > LZO1X_1_MEM_COMPRESS);
>  		memset(wrkmem, 0, D_SIZE * sizeof(lzo_dict_t));
> -		t = lzo1x_1_do_compress(ip, ll, op, out_len, t, wrkmem,
> -					&state_offset, bitstream_version);
> +		err = lzo1x_1_do_compress(ip, ll, &op, op_end, &t, wrkmem,
> +					  &state_offset, bitstream_version);
> +		if (err != LZO_E_OK)
> +			return err;
>  		ip += ll;
> -		op += *out_len;
>  		l  -= ll;
>  	}
>  	t += l;
> @@ -342,20 +384,32 @@ static int lzogeneric1x_1_compress(const unsigned char *in, size_t in_len,
>  		const unsigned char *ii = in + in_len - t;
>  
>  		if (op == data_start && t <= 238) {
> +			if (!HAVE_OP(1))
> +				return LZO_E_OUTPUT_OVERRUN;
>  			*op++ = (17 + t);
>  		} else if (t <= 3) {
>  			op[state_offset] |= t;
>  		} else if (t <= 18) {
> +			if (!HAVE_OP(1))
> +				return LZO_E_OUTPUT_OVERRUN;
>  			*op++ = (t - 3);
>  		} else {
>  			size_t tt = t - 18;
> +			if (!HAVE_OP(1))
> +				return LZO_E_OUTPUT_OVERRUN;
>  			*op++ = 0;
>  			while (tt > 255) {
>  				tt -= 255;
> +				if (!HAVE_OP(1))
> +					return LZO_E_OUTPUT_OVERRUN;
>  				*op++ = 0;
>  			}
> +			if (!HAVE_OP(1))
> +				return LZO_E_OUTPUT_OVERRUN;
>  			*op++ = tt;
>  		}
> +		if (!HAVE_OP(t))
> +			return LZO_E_OUTPUT_OVERRUN;
>  		if (t >= 16) do {
>  			COPY8(op, ii);
>  			COPY8(op + 8, ii + 8);
> @@ -368,6 +422,8 @@ static int lzogeneric1x_1_compress(const unsigned char *in, size_t in_len,
>  		} while (--t > 0);
>  	}
>  
> +	if (!HAVE_OP(3))
> +		return LZO_E_OUTPUT_OVERRUN;
>  	*op++ = M4_MARKER | 1;
>  	*op++ = 0;
>  	*op++ = 0;
> diff --git a/lib/lzo/lzo1x_decompress_safe.c b/lib/lzo/lzo1x_decompress_safe.c
> index c94f4928e188..4d5a1b58a4a0 100644
> --- a/lib/lzo/lzo1x_decompress_safe.c
> +++ b/lib/lzo/lzo1x_decompress_safe.c
> @@ -21,7 +21,6 @@
>  #include "lzodefs.h"
>  
>  #define HAVE_IP(x)      ((size_t)(ip_end - ip) >= (size_t)(x))
> -#define HAVE_OP(x)      ((size_t)(op_end - op) >= (size_t)(x))
>  #define NEED_IP(x)      if (!HAVE_IP(x)) goto input_overrun
>  #define NEED_OP(x)      if (!HAVE_OP(x)) goto output_overrun
>  #define TEST_LB(m_pos)  if ((m_pos) < out) goto lookbehind_overrun
> diff --git a/lib/lzo/lzodefs.h b/lib/lzo/lzodefs.h
> index b60851fcf6ce..8b1a46993acf 100644
> --- a/lib/lzo/lzodefs.h
> +++ b/lib/lzo/lzodefs.h
> @@ -19,6 +19,7 @@
>   */
>  #define LZO_VERSION 1
>  
> +#define HAVE_OP(x)      ((size_t)(op_end - op) >= (size_t)(x))
>  #define COPY4(dst, src)	\
>  		put_unaligned(get_unaligned((const u32 *)(src)), (u32 *)(dst))
>  #if defined(CONFIG_X86_64) || defined(CONFIG_ARM64)
> 

-- 
Markus Oberhumer, <markus@oberhumer.com>, http://www.oberhumer.com/

Re: [PATCH] lib/lzo: Avoid output overruns when compressing

[David Sterba]

On Sun, Feb 23, 2025 at 02:55:24PM +0800, Herbert Xu wrote:
> The compression code in LZO never checked for output overruns.
> Fix this by checking for end of buffer before each write.

Does it have to check for the overruns? The worst case compression
result size is known and can be calculated by the formula. Using big
enough buffer is part of the correct usage of LZO. All in-kernel users
of lzo1x_1_compress() seem to provide the target buffer calculated by
lzo1x_worst_compress(). F2FS, JFFS2, BTRFS. Not sure about ZRAM.

What strikes me as alarming that you insert about 20 branches into a
realtime compression algorithm, where everything is basically a hot
path.  Branches that almost never happen, and never if the output buffer
is big enough.

Please drop the patch.

Re: [PATCH] lib/lzo: Avoid output overruns when compressing

[Herbert Xu]

On Wed, Feb 26, 2025 at 02:00:37PM +0100, David Sterba wrote:
>
> Does it have to check for the overruns? The worst case compression
> result size is known and can be calculated by the formula. Using big

If the caller is using different algorithms, then yes the checks
are essential.  Otherwise the caller would have to allocate enough
memory not just for LZO, but for the worst-case compression length
for *any* algorithm.  Adding a single algorithm would have the
potential of breaking all users.
 
> What strikes me as alarming that you insert about 20 branches into a
> realtime compression algorithm, where everything is basically a hot
> path.  Branches that almost never happen, and never if the output buffer
> is big enough.

OK, if that is a real concern then I will add a _safe version of
LZO compression alongside the existing code.

Cheers,
-- 
Email: Herbert Xu <herbert@gondor.apana.org.au>
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt

[v2 PATCH] crypto: lzo - Fix compression buffer overrun

[Herbert Xu]

Unlike the decompression code, the compression code in LZO never
checked for output overruns.  It instead assumes that the caller
always provides enough buffer space, disregarding the buffer length
provided by the caller.

Add a safe compression interface that checks for the end of buffer
before each write.  Use the safe interface in crypto/lzo.

Signed-off-by: Herbert Xu <herbert@gondor.apana.org.au>
---
 crypto/lzo-rle.c              |  2 +-
 crypto/lzo.c                  |  2 +-
 include/linux/lzo.h           |  8 +++
 lib/lzo/Makefile              |  2 +-
 lib/lzo/lzo1x_compress.c      | 99 ++++++++++++++++++++++++++---------
 lib/lzo/lzo1x_compress_safe.c | 18 +++++++
 6 files changed, 103 insertions(+), 28 deletions(-)
 create mode 100644 lib/lzo/lzo1x_compress_safe.c

diff --git a/crypto/lzo-rle.c b/crypto/lzo-rle.c
index 0631d975bfac..0abc2d87f042 100644
--- a/crypto/lzo-rle.c
+++ b/crypto/lzo-rle.c
@@ -55,7 +55,7 @@ static int __lzorle_compress(const u8 *src, unsigned int slen,
 	size_t tmp_len = *dlen; /* size_t(ulong) <-> uint on 64 bit */
 	int err;
 
-	err = lzorle1x_1_compress(src, slen, dst, &tmp_len, ctx);
+	err = lzorle1x_1_compress_safe(src, slen, dst, &tmp_len, ctx);
 
 	if (err != LZO_E_OK)
 		return -EINVAL;
diff --git a/crypto/lzo.c b/crypto/lzo.c
index ebda132dd22b..8338851c7406 100644
--- a/crypto/lzo.c
+++ b/crypto/lzo.c
@@ -55,7 +55,7 @@ static int __lzo_compress(const u8 *src, unsigned int slen,
 	size_t tmp_len = *dlen; /* size_t(ulong) <-> uint on 64 bit */
 	int err;
 
-	err = lzo1x_1_compress(src, slen, dst, &tmp_len, ctx);
+	err = lzo1x_1_compress_safe(src, slen, dst, &tmp_len, ctx);
 
 	if (err != LZO_E_OK)
 		return -EINVAL;
diff --git a/include/linux/lzo.h b/include/linux/lzo.h
index e95c7d1092b2..4d30e3624acd 100644
--- a/include/linux/lzo.h
+++ b/include/linux/lzo.h
@@ -24,10 +24,18 @@
 int lzo1x_1_compress(const unsigned char *src, size_t src_len,
 		     unsigned char *dst, size_t *dst_len, void *wrkmem);
 
+/* Same as above but does not write more than dst_len to dst. */
+int lzo1x_1_compress_safe(const unsigned char *src, size_t src_len,
+			  unsigned char *dst, size_t *dst_len, void *wrkmem);
+
 /* This requires 'wrkmem' of size LZO1X_1_MEM_COMPRESS */
 int lzorle1x_1_compress(const unsigned char *src, size_t src_len,
 		     unsigned char *dst, size_t *dst_len, void *wrkmem);
 
+/* Same as above but does not write more than dst_len to dst. */
+int lzorle1x_1_compress_safe(const unsigned char *src, size_t src_len,
+			     unsigned char *dst, size_t *dst_len, void *wrkmem);
+
 /* safe decompression with overrun testing */
 int lzo1x_decompress_safe(const unsigned char *src, size_t src_len,
 			  unsigned char *dst, size_t *dst_len);
diff --git a/lib/lzo/Makefile b/lib/lzo/Makefile
index 2f58fafbbddd..fc7b2b7ef4b2 100644
--- a/lib/lzo/Makefile
+++ b/lib/lzo/Makefile
@@ -1,5 +1,5 @@
 # SPDX-License-Identifier: GPL-2.0-only
-lzo_compress-objs := lzo1x_compress.o
+lzo_compress-objs := lzo1x_compress.o lzo1x_compress_safe.o
 lzo_decompress-objs := lzo1x_decompress_safe.o
 
 obj-$(CONFIG_LZO_COMPRESS) += lzo_compress.o
diff --git a/lib/lzo/lzo1x_compress.c b/lib/lzo/lzo1x_compress.c
index 47d6d43ea957..c89d97bf9693 100644
--- a/lib/lzo/lzo1x_compress.c
+++ b/lib/lzo/lzo1x_compress.c
@@ -18,11 +18,19 @@
 #include <linux/lzo.h>
 #include "lzodefs.h"
 
-static noinline size_t
-lzo1x_1_do_compress(const unsigned char *in, size_t in_len,
-		    unsigned char *out, size_t *out_len,
-		    size_t ti, void *wrkmem, signed char *state_offset,
-		    const unsigned char bitstream_version)
+#ifndef LZO_SAFE
+#define LZO_SAFE(name) name
+#define HAVE_OP(x) 1
+#endif
+
+#define NEED_OP(x) if (!HAVE_OP(x)) goto output_overrun
+
+static noinline int
+LZO_SAFE(lzo1x_1_do_compress)(const unsigned char *in, size_t in_len,
+			      unsigned char **out, unsigned char *op_end,
+			      size_t *tp, void *wrkmem,
+			      signed char *state_offset,
+			      const unsigned char bitstream_version)
 {
 	const unsigned char *ip;
 	unsigned char *op;
@@ -30,8 +38,9 @@ lzo1x_1_do_compress(const unsigned char *in, size_t in_len,
 	const unsigned char * const ip_end = in + in_len - 20;
 	const unsigned char *ii;
 	lzo_dict_t * const dict = (lzo_dict_t *) wrkmem;
+	size_t ti = *tp;
 
-	op = out;
+	op = *out;
 	ip = in;
 	ii = ip;
 	ip += ti < 4 ? 4 - ti : 0;
@@ -116,25 +125,32 @@ lzo1x_1_do_compress(const unsigned char *in, size_t in_len,
 		if (t != 0) {
 			if (t <= 3) {
 				op[*state_offset] |= t;
+				NEED_OP(4);
 				COPY4(op, ii);
 				op += t;
 			} else if (t <= 16) {
+				NEED_OP(17);
 				*op++ = (t - 3);
 				COPY8(op, ii);
 				COPY8(op + 8, ii + 8);
 				op += t;
 			} else {
 				if (t <= 18) {
+					NEED_OP(1);
 					*op++ = (t - 3);
 				} else {
 					size_t tt = t - 18;
+					NEED_OP(1);
 					*op++ = 0;
 					while (unlikely(tt > 255)) {
 						tt -= 255;
+						NEED_OP(1);
 						*op++ = 0;
 					}
+					NEED_OP(1);
 					*op++ = tt;
 				}
+				NEED_OP(t);
 				do {
 					COPY8(op, ii);
 					COPY8(op + 8, ii + 8);
@@ -151,6 +167,7 @@ lzo1x_1_do_compress(const unsigned char *in, size_t in_len,
 		if (unlikely(run_length)) {
 			ip += run_length;
 			run_length -= MIN_ZERO_RUN_LENGTH;
+			NEED_OP(4);
 			put_unaligned_le32((run_length << 21) | 0xfffc18
 					   | (run_length & 0x7), op);
 			op += 4;
@@ -243,10 +260,12 @@ lzo1x_1_do_compress(const unsigned char *in, size_t in_len,
 		ip += m_len;
 		if (m_len <= M2_MAX_LEN && m_off <= M2_MAX_OFFSET) {
 			m_off -= 1;
+			NEED_OP(2);
 			*op++ = (((m_len - 1) << 5) | ((m_off & 7) << 2));
 			*op++ = (m_off >> 3);
 		} else if (m_off <= M3_MAX_OFFSET) {
 			m_off -= 1;
+			NEED_OP(1);
 			if (m_len <= M3_MAX_LEN)
 				*op++ = (M3_MARKER | (m_len - 2));
 			else {
@@ -254,14 +273,18 @@ lzo1x_1_do_compress(const unsigned char *in, size_t in_len,
 				*op++ = M3_MARKER | 0;
 				while (unlikely(m_len > 255)) {
 					m_len -= 255;
+					NEED_OP(1);
 					*op++ = 0;
 				}
+				NEED_OP(1);
 				*op++ = (m_len);
 			}
+			NEED_OP(2);
 			*op++ = (m_off << 2);
 			*op++ = (m_off >> 6);
 		} else {
 			m_off -= 0x4000;
+			NEED_OP(1);
 			if (m_len <= M4_MAX_LEN)
 				*op++ = (M4_MARKER | ((m_off >> 11) & 8)
 						| (m_len - 2));
@@ -282,11 +305,14 @@ lzo1x_1_do_compress(const unsigned char *in, size_t in_len,
 				m_len -= M4_MAX_LEN;
 				*op++ = (M4_MARKER | ((m_off >> 11) & 8));
 				while (unlikely(m_len > 255)) {
+					NEED_OP(1);
 					m_len -= 255;
 					*op++ = 0;
 				}
+				NEED_OP(1);
 				*op++ = (m_len);
 			}
+			NEED_OP(2);
 			*op++ = (m_off << 2);
 			*op++ = (m_off >> 6);
 		}
@@ -295,14 +321,20 @@ lzo1x_1_do_compress(const unsigned char *in, size_t in_len,
 		ii = ip;
 		goto next;
 	}
-	*out_len = op - out;
-	return in_end - (ii - ti);
+	*out = op;
+	*tp = in_end - (ii - ti);
+	return LZO_E_OK;
+
+output_overrun:
+	return LZO_E_OUTPUT_OVERRUN;
 }
 
-static int lzogeneric1x_1_compress(const unsigned char *in, size_t in_len,
-		     unsigned char *out, size_t *out_len,
-		     void *wrkmem, const unsigned char bitstream_version)
+static int LZO_SAFE(lzogeneric1x_1_compress)(
+	const unsigned char *in, size_t in_len,
+	unsigned char *out, size_t *out_len,
+	void *wrkmem, const unsigned char bitstream_version)
 {
+	unsigned char * const op_end = out + *out_len;
 	const unsigned char *ip = in;
 	unsigned char *op = out;
 	unsigned char *data_start;
@@ -326,14 +358,18 @@ static int lzogeneric1x_1_compress(const unsigned char *in, size_t in_len,
 	while (l > 20) {
 		size_t ll = min_t(size_t, l, m4_max_offset + 1);
 		uintptr_t ll_end = (uintptr_t) ip + ll;
+		int err;
+
 		if ((ll_end + ((t + ll) >> 5)) <= ll_end)
 			break;
 		BUILD_BUG_ON(D_SIZE * sizeof(lzo_dict_t) > LZO1X_1_MEM_COMPRESS);
 		memset(wrkmem, 0, D_SIZE * sizeof(lzo_dict_t));
-		t = lzo1x_1_do_compress(ip, ll, op, out_len, t, wrkmem,
-					&state_offset, bitstream_version);
+		err = LZO_SAFE(lzo1x_1_do_compress)(
+			ip, ll, &op, op_end, &t, wrkmem,
+			&state_offset, bitstream_version);
+		if (err != LZO_E_OK)
+			return err;
 		ip += ll;
-		op += *out_len;
 		l  -= ll;
 	}
 	t += l;
@@ -342,20 +378,26 @@ static int lzogeneric1x_1_compress(const unsigned char *in, size_t in_len,
 		const unsigned char *ii = in + in_len - t;
 
 		if (op == data_start && t <= 238) {
+			NEED_OP(1);
 			*op++ = (17 + t);
 		} else if (t <= 3) {
 			op[state_offset] |= t;
 		} else if (t <= 18) {
+			NEED_OP(1);
 			*op++ = (t - 3);
 		} else {
 			size_t tt = t - 18;
+			NEED_OP(1);
 			*op++ = 0;
 			while (tt > 255) {
 				tt -= 255;
+				NEED_OP(1);
 				*op++ = 0;
 			}
+			NEED_OP(1);
 			*op++ = tt;
 		}
+		NEED_OP(t);
 		if (t >= 16) do {
 			COPY8(op, ii);
 			COPY8(op + 8, ii + 8);
@@ -368,31 +410,38 @@ static int lzogeneric1x_1_compress(const unsigned char *in, size_t in_len,
 		} while (--t > 0);
 	}
 
+	NEED_OP(3);
 	*op++ = M4_MARKER | 1;
 	*op++ = 0;
 	*op++ = 0;
 
 	*out_len = op - out;
 	return LZO_E_OK;
+
+output_overrun:
+	return LZO_E_OUTPUT_OVERRUN;
 }
 
-int lzo1x_1_compress(const unsigned char *in, size_t in_len,
-		     unsigned char *out, size_t *out_len,
-		     void *wrkmem)
+int LZO_SAFE(lzo1x_1_compress)(const unsigned char *in, size_t in_len,
+			       unsigned char *out, size_t *out_len,
+			       void *wrkmem)
 {
-	return lzogeneric1x_1_compress(in, in_len, out, out_len, wrkmem, 0);
+	return LZO_SAFE(lzogeneric1x_1_compress)(
+		in, in_len, out, out_len, wrkmem, 0);
 }
 
-int lzorle1x_1_compress(const unsigned char *in, size_t in_len,
-		     unsigned char *out, size_t *out_len,
-		     void *wrkmem)
+int LZO_SAFE(lzorle1x_1_compress)(const unsigned char *in, size_t in_len,
+				  unsigned char *out, size_t *out_len,
+				  void *wrkmem)
 {
-	return lzogeneric1x_1_compress(in, in_len, out, out_len,
-				       wrkmem, LZO_VERSION);
+	return LZO_SAFE(lzogeneric1x_1_compress)(
+		in, in_len, out, out_len, wrkmem, LZO_VERSION);
 }
 
-EXPORT_SYMBOL_GPL(lzo1x_1_compress);
-EXPORT_SYMBOL_GPL(lzorle1x_1_compress);
+EXPORT_SYMBOL_GPL(LZO_SAFE(lzo1x_1_compress));
+EXPORT_SYMBOL_GPL(LZO_SAFE(lzorle1x_1_compress));
 
+#ifndef LZO_SAFE
 MODULE_LICENSE("GPL");
 MODULE_DESCRIPTION("LZO1X-1 Compressor");
+#endif
diff --git a/lib/lzo/lzo1x_compress_safe.c b/lib/lzo/lzo1x_compress_safe.c
new file mode 100644
index 000000000000..371c9f849492
--- /dev/null
+++ b/lib/lzo/lzo1x_compress_safe.c
@@ -0,0 +1,18 @@
+// SPDX-License-Identifier: GPL-2.0-only
+/*
+ *  LZO1X Compressor from LZO
+ *
+ *  Copyright (C) 1996-2012 Markus F.X.J. Oberhumer <markus@oberhumer.com>
+ *
+ *  The full LZO package can be found at:
+ *  http://www.oberhumer.com/opensource/lzo/
+ *
+ *  Changed for Linux kernel use by:
+ *  Nitin Gupta <nitingupta910@gmail.com>
+ *  Richard Purdie <rpurdie@openedhand.com>
+ */
+
+#define LZO_SAFE(name) name##_safe
+#define HAVE_OP(x) ((size_t)(op_end - op) >= (size_t)(x))
+
+#include "lzo1x_compress.c"
-- 
2.39.5

-- 
Email: Herbert Xu <herbert@gondor.apana.org.au>
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt

[v3 PATCH] crypto: lzo - Fix compression buffer overrun

[Herbert Xu]

Unlike the decompression code, the compression code in LZO never
checked for output overruns.  It instead assumes that the caller
always provides enough buffer space, disregarding the buffer length
provided by the caller.

Add a safe compression interface that checks for the end of buffer
before each write.  Use the safe interface in crypto/lzo.

Signed-off-by: Herbert Xu <herbert@gondor.apana.org.au>
---
 crypto/lzo-rle.c              |   2 +-
 crypto/lzo.c                  |   2 +-
 include/linux/lzo.h           |   8 +++
 lib/lzo/Makefile              |   2 +-
 lib/lzo/lzo1x_compress.c      | 102 +++++++++++++++++++++++++---------
 lib/lzo/lzo1x_compress_safe.c |  18 ++++++
 6 files changed, 106 insertions(+), 28 deletions(-)
 create mode 100644 lib/lzo/lzo1x_compress_safe.c

--
v3 fixes the modular build.

diff --git a/crypto/lzo-rle.c b/crypto/lzo-rle.c
index 0631d975bfac..0abc2d87f042 100644
--- a/crypto/lzo-rle.c
+++ b/crypto/lzo-rle.c
@@ -55,7 +55,7 @@ static int __lzorle_compress(const u8 *src, unsigned int slen,
 	size_t tmp_len = *dlen; /* size_t(ulong) <-> uint on 64 bit */
 	int err;
 
-	err = lzorle1x_1_compress(src, slen, dst, &tmp_len, ctx);
+	err = lzorle1x_1_compress_safe(src, slen, dst, &tmp_len, ctx);
 
 	if (err != LZO_E_OK)
 		return -EINVAL;
diff --git a/crypto/lzo.c b/crypto/lzo.c
index ebda132dd22b..8338851c7406 100644
--- a/crypto/lzo.c
+++ b/crypto/lzo.c
@@ -55,7 +55,7 @@ static int __lzo_compress(const u8 *src, unsigned int slen,
 	size_t tmp_len = *dlen; /* size_t(ulong) <-> uint on 64 bit */
 	int err;
 
-	err = lzo1x_1_compress(src, slen, dst, &tmp_len, ctx);
+	err = lzo1x_1_compress_safe(src, slen, dst, &tmp_len, ctx);
 
 	if (err != LZO_E_OK)
 		return -EINVAL;
diff --git a/include/linux/lzo.h b/include/linux/lzo.h
index e95c7d1092b2..4d30e3624acd 100644
--- a/include/linux/lzo.h
+++ b/include/linux/lzo.h
@@ -24,10 +24,18 @@
 int lzo1x_1_compress(const unsigned char *src, size_t src_len,
 		     unsigned char *dst, size_t *dst_len, void *wrkmem);
 
+/* Same as above but does not write more than dst_len to dst. */
+int lzo1x_1_compress_safe(const unsigned char *src, size_t src_len,
+			  unsigned char *dst, size_t *dst_len, void *wrkmem);
+
 /* This requires 'wrkmem' of size LZO1X_1_MEM_COMPRESS */
 int lzorle1x_1_compress(const unsigned char *src, size_t src_len,
 		     unsigned char *dst, size_t *dst_len, void *wrkmem);
 
+/* Same as above but does not write more than dst_len to dst. */
+int lzorle1x_1_compress_safe(const unsigned char *src, size_t src_len,
+			     unsigned char *dst, size_t *dst_len, void *wrkmem);
+
 /* safe decompression with overrun testing */
 int lzo1x_decompress_safe(const unsigned char *src, size_t src_len,
 			  unsigned char *dst, size_t *dst_len);
diff --git a/lib/lzo/Makefile b/lib/lzo/Makefile
index 2f58fafbbddd..fc7b2b7ef4b2 100644
--- a/lib/lzo/Makefile
+++ b/lib/lzo/Makefile
@@ -1,5 +1,5 @@
 # SPDX-License-Identifier: GPL-2.0-only
-lzo_compress-objs := lzo1x_compress.o
+lzo_compress-objs := lzo1x_compress.o lzo1x_compress_safe.o
 lzo_decompress-objs := lzo1x_decompress_safe.o
 
 obj-$(CONFIG_LZO_COMPRESS) += lzo_compress.o
diff --git a/lib/lzo/lzo1x_compress.c b/lib/lzo/lzo1x_compress.c
index 47d6d43ea957..7b10ca86a893 100644
--- a/lib/lzo/lzo1x_compress.c
+++ b/lib/lzo/lzo1x_compress.c
@@ -18,11 +18,22 @@
 #include <linux/lzo.h>
 #include "lzodefs.h"
 
-static noinline size_t
-lzo1x_1_do_compress(const unsigned char *in, size_t in_len,
-		    unsigned char *out, size_t *out_len,
-		    size_t ti, void *wrkmem, signed char *state_offset,
-		    const unsigned char bitstream_version)
+#undef LZO_UNSAFE
+
+#ifndef LZO_SAFE
+#define LZO_UNSAFE 1
+#define LZO_SAFE(name) name
+#define HAVE_OP(x) 1
+#endif
+
+#define NEED_OP(x) if (!HAVE_OP(x)) goto output_overrun
+
+static noinline int
+LZO_SAFE(lzo1x_1_do_compress)(const unsigned char *in, size_t in_len,
+			      unsigned char **out, unsigned char *op_end,
+			      size_t *tp, void *wrkmem,
+			      signed char *state_offset,
+			      const unsigned char bitstream_version)
 {
 	const unsigned char *ip;
 	unsigned char *op;
@@ -30,8 +41,9 @@ lzo1x_1_do_compress(const unsigned char *in, size_t in_len,
 	const unsigned char * const ip_end = in + in_len - 20;
 	const unsigned char *ii;
 	lzo_dict_t * const dict = (lzo_dict_t *) wrkmem;
+	size_t ti = *tp;
 
-	op = out;
+	op = *out;
 	ip = in;
 	ii = ip;
 	ip += ti < 4 ? 4 - ti : 0;
@@ -116,25 +128,32 @@ lzo1x_1_do_compress(const unsigned char *in, size_t in_len,
 		if (t != 0) {
 			if (t <= 3) {
 				op[*state_offset] |= t;
+				NEED_OP(4);
 				COPY4(op, ii);
 				op += t;
 			} else if (t <= 16) {
+				NEED_OP(17);
 				*op++ = (t - 3);
 				COPY8(op, ii);
 				COPY8(op + 8, ii + 8);
 				op += t;
 			} else {
 				if (t <= 18) {
+					NEED_OP(1);
 					*op++ = (t - 3);
 				} else {
 					size_t tt = t - 18;
+					NEED_OP(1);
 					*op++ = 0;
 					while (unlikely(tt > 255)) {
 						tt -= 255;
+						NEED_OP(1);
 						*op++ = 0;
 					}
+					NEED_OP(1);
 					*op++ = tt;
 				}
+				NEED_OP(t);
 				do {
 					COPY8(op, ii);
 					COPY8(op + 8, ii + 8);
@@ -151,6 +170,7 @@ lzo1x_1_do_compress(const unsigned char *in, size_t in_len,
 		if (unlikely(run_length)) {
 			ip += run_length;
 			run_length -= MIN_ZERO_RUN_LENGTH;
+			NEED_OP(4);
 			put_unaligned_le32((run_length << 21) | 0xfffc18
 					   | (run_length & 0x7), op);
 			op += 4;
@@ -243,10 +263,12 @@ lzo1x_1_do_compress(const unsigned char *in, size_t in_len,
 		ip += m_len;
 		if (m_len <= M2_MAX_LEN && m_off <= M2_MAX_OFFSET) {
 			m_off -= 1;
+			NEED_OP(2);
 			*op++ = (((m_len - 1) << 5) | ((m_off & 7) << 2));
 			*op++ = (m_off >> 3);
 		} else if (m_off <= M3_MAX_OFFSET) {
 			m_off -= 1;
+			NEED_OP(1);
 			if (m_len <= M3_MAX_LEN)
 				*op++ = (M3_MARKER | (m_len - 2));
 			else {
@@ -254,14 +276,18 @@ lzo1x_1_do_compress(const unsigned char *in, size_t in_len,
 				*op++ = M3_MARKER | 0;
 				while (unlikely(m_len > 255)) {
 					m_len -= 255;
+					NEED_OP(1);
 					*op++ = 0;
 				}
+				NEED_OP(1);
 				*op++ = (m_len);
 			}
+			NEED_OP(2);
 			*op++ = (m_off << 2);
 			*op++ = (m_off >> 6);
 		} else {
 			m_off -= 0x4000;
+			NEED_OP(1);
 			if (m_len <= M4_MAX_LEN)
 				*op++ = (M4_MARKER | ((m_off >> 11) & 8)
 						| (m_len - 2));
@@ -282,11 +308,14 @@ lzo1x_1_do_compress(const unsigned char *in, size_t in_len,
 				m_len -= M4_MAX_LEN;
 				*op++ = (M4_MARKER | ((m_off >> 11) & 8));
 				while (unlikely(m_len > 255)) {
+					NEED_OP(1);
 					m_len -= 255;
 					*op++ = 0;
 				}
+				NEED_OP(1);
 				*op++ = (m_len);
 			}
+			NEED_OP(2);
 			*op++ = (m_off << 2);
 			*op++ = (m_off >> 6);
 		}
@@ -295,14 +324,20 @@ lzo1x_1_do_compress(const unsigned char *in, size_t in_len,
 		ii = ip;
 		goto next;
 	}
-	*out_len = op - out;
-	return in_end - (ii - ti);
+	*out = op;
+	*tp = in_end - (ii - ti);
+	return LZO_E_OK;
+
+output_overrun:
+	return LZO_E_OUTPUT_OVERRUN;
 }
 
-static int lzogeneric1x_1_compress(const unsigned char *in, size_t in_len,
-		     unsigned char *out, size_t *out_len,
-		     void *wrkmem, const unsigned char bitstream_version)
+static int LZO_SAFE(lzogeneric1x_1_compress)(
+	const unsigned char *in, size_t in_len,
+	unsigned char *out, size_t *out_len,
+	void *wrkmem, const unsigned char bitstream_version)
 {
+	unsigned char * const op_end = out + *out_len;
 	const unsigned char *ip = in;
 	unsigned char *op = out;
 	unsigned char *data_start;
@@ -326,14 +361,18 @@ static int lzogeneric1x_1_compress(const unsigned char *in, size_t in_len,
 	while (l > 20) {
 		size_t ll = min_t(size_t, l, m4_max_offset + 1);
 		uintptr_t ll_end = (uintptr_t) ip + ll;
+		int err;
+
 		if ((ll_end + ((t + ll) >> 5)) <= ll_end)
 			break;
 		BUILD_BUG_ON(D_SIZE * sizeof(lzo_dict_t) > LZO1X_1_MEM_COMPRESS);
 		memset(wrkmem, 0, D_SIZE * sizeof(lzo_dict_t));
-		t = lzo1x_1_do_compress(ip, ll, op, out_len, t, wrkmem,
-					&state_offset, bitstream_version);
+		err = LZO_SAFE(lzo1x_1_do_compress)(
+			ip, ll, &op, op_end, &t, wrkmem,
+			&state_offset, bitstream_version);
+		if (err != LZO_E_OK)
+			return err;
 		ip += ll;
-		op += *out_len;
 		l  -= ll;
 	}
 	t += l;
@@ -342,20 +381,26 @@ static int lzogeneric1x_1_compress(const unsigned char *in, size_t in_len,
 		const unsigned char *ii = in + in_len - t;
 
 		if (op == data_start && t <= 238) {
+			NEED_OP(1);
 			*op++ = (17 + t);
 		} else if (t <= 3) {
 			op[state_offset] |= t;
 		} else if (t <= 18) {
+			NEED_OP(1);
 			*op++ = (t - 3);
 		} else {
 			size_t tt = t - 18;
+			NEED_OP(1);
 			*op++ = 0;
 			while (tt > 255) {
 				tt -= 255;
+				NEED_OP(1);
 				*op++ = 0;
 			}
+			NEED_OP(1);
 			*op++ = tt;
 		}
+		NEED_OP(t);
 		if (t >= 16) do {
 			COPY8(op, ii);
 			COPY8(op + 8, ii + 8);
@@ -368,31 +413,38 @@ static int lzogeneric1x_1_compress(const unsigned char *in, size_t in_len,
 		} while (--t > 0);
 	}
 
+	NEED_OP(3);
 	*op++ = M4_MARKER | 1;
 	*op++ = 0;
 	*op++ = 0;
 
 	*out_len = op - out;
 	return LZO_E_OK;
+
+output_overrun:
+	return LZO_E_OUTPUT_OVERRUN;
 }
 
-int lzo1x_1_compress(const unsigned char *in, size_t in_len,
-		     unsigned char *out, size_t *out_len,
-		     void *wrkmem)
+int LZO_SAFE(lzo1x_1_compress)(const unsigned char *in, size_t in_len,
+			       unsigned char *out, size_t *out_len,
+			       void *wrkmem)
 {
-	return lzogeneric1x_1_compress(in, in_len, out, out_len, wrkmem, 0);
+	return LZO_SAFE(lzogeneric1x_1_compress)(
+		in, in_len, out, out_len, wrkmem, 0);
 }
 
-int lzorle1x_1_compress(const unsigned char *in, size_t in_len,
-		     unsigned char *out, size_t *out_len,
-		     void *wrkmem)
+int LZO_SAFE(lzorle1x_1_compress)(const unsigned char *in, size_t in_len,
+				  unsigned char *out, size_t *out_len,
+				  void *wrkmem)
 {
-	return lzogeneric1x_1_compress(in, in_len, out, out_len,
-				       wrkmem, LZO_VERSION);
+	return LZO_SAFE(lzogeneric1x_1_compress)(
+		in, in_len, out, out_len, wrkmem, LZO_VERSION);
 }
 
-EXPORT_SYMBOL_GPL(lzo1x_1_compress);
-EXPORT_SYMBOL_GPL(lzorle1x_1_compress);
+EXPORT_SYMBOL_GPL(LZO_SAFE(lzo1x_1_compress));
+EXPORT_SYMBOL_GPL(LZO_SAFE(lzorle1x_1_compress));
 
+#ifndef LZO_UNSAFE
 MODULE_LICENSE("GPL");
 MODULE_DESCRIPTION("LZO1X-1 Compressor");
+#endif
diff --git a/lib/lzo/lzo1x_compress_safe.c b/lib/lzo/lzo1x_compress_safe.c
new file mode 100644
index 000000000000..371c9f849492
--- /dev/null
+++ b/lib/lzo/lzo1x_compress_safe.c
@@ -0,0 +1,18 @@
+// SPDX-License-Identifier: GPL-2.0-only
+/*
+ *  LZO1X Compressor from LZO
+ *
+ *  Copyright (C) 1996-2012 Markus F.X.J. Oberhumer <markus@oberhumer.com>
+ *
+ *  The full LZO package can be found at:
+ *  http://www.oberhumer.com/opensource/lzo/
+ *
+ *  Changed for Linux kernel use by:
+ *  Nitin Gupta <nitingupta910@gmail.com>
+ *  Richard Purdie <rpurdie@openedhand.com>
+ */
+
+#define LZO_SAFE(name) name##_safe
+#define HAVE_OP(x) ((size_t)(op_end - op) >= (size_t)(x))
+
+#include "lzo1x_compress.c"
-- 
2.39.5

-- 
Email: Herbert Xu <herbert@gondor.apana.org.au>
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt

Re: [v3 PATCH] crypto: lzo - Fix compression buffer overrun

[David Sterba]

On Thu, Feb 27, 2025 at 05:04:46PM +0800, Herbert Xu wrote:
> Unlike the decompression code, the compression code in LZO never
> checked for output overruns.  It instead assumes that the caller
> always provides enough buffer space, disregarding the buffer length
> provided by the caller.
> 
> Add a safe compression interface that checks for the end of buffer
> before each write.  Use the safe interface in crypto/lzo.
> 
> Signed-off-by: Herbert Xu <herbert@gondor.apana.org.au>

Thanks.

Reviewed-by: David Sterba <dsterba@suse.com>

Re: [PATCH] lib/lzo: Avoid output overruns when compressing

[David Sterba]

On Thu, Feb 27, 2025 at 09:46:10AM +0800, Herbert Xu wrote:
> On Wed, Feb 26, 2025 at 02:00:37PM +0100, David Sterba wrote:
> >
> > Does it have to check for the overruns? The worst case compression
> > result size is known and can be calculated by the formula. Using big
> 
> If the caller is using different algorithms, then yes the checks
> are essential.  Otherwise the caller would have to allocate enough
> memory not just for LZO, but for the worst-case compression length
> for *any* algorithm.  Adding a single algorithm would have the
> potential of breaking all users.
>  
> > What strikes me as alarming that you insert about 20 branches into a
> > realtime compression algorithm, where everything is basically a hot
> > path.  Branches that almost never happen, and never if the output buffer
> > is big enough.
> 
> OK, if that is a real concern then I will add a _safe version of
> LZO compression alongside the existing code.

Makes sense, thanks. The in-kernel users are OK, but the crypto API also
exports the compression so there's no guarantee it's used correctly. As
it needs changes to the LZO code itself I don't see a better way than to
have 2 versions, conveniently done by the macros as yo did.

Re: [PATCH] lib/lzo: Avoid output overruns when compressing

[Sergey Senozhatsky]

On (25/02/26 14:00), David Sterba wrote:
> What strikes me as alarming that you insert about 20 branches into a
> realtime compression algorithm, where everything is basically a hot
> path.  Branches that almost never happen, and never if the output buffer
> is big enough.
> 
> Please drop the patch.

David, just for educational purposes, there's only safe variant of lzo
decompression, which seems to be doing a lot of NEED_OP (HAVE_OP) adding
branches and so on, basically what Herbert is adding to the compression
path.  So my question is - why NEED_OP (if (!HAVE_OP(x)) goto output_overrun)
is a no go for compression, but appears to be fine for decompression?

Re: [PATCH] lib/lzo: Avoid output overruns when compressing

[Ard Biesheuvel]

On Fri, 28 Feb 2025 at 06:24, Sergey Senozhatsky
<senozhatsky@chromium.org> wrote:
>
> On (25/02/26 14:00), David Sterba wrote:
> > What strikes me as alarming that you insert about 20 branches into a
> > realtime compression algorithm, where everything is basically a hot
> > path.  Branches that almost never happen, and never if the output buffer
> > is big enough.
> >
> > Please drop the patch.
>
> David, just for educational purposes, there's only safe variant of lzo
> decompression, which seems to be doing a lot of NEED_OP (HAVE_OP) adding
> branches and so on, basically what Herbert is adding to the compression
> path.  So my question is - why NEED_OP (if (!HAVE_OP(x)) goto output_overrun)
> is a no go for compression, but appears to be fine for decompression?
>

Because compression has a bounded worst case (compressing data with
LZO can actually increase the size but only by a limited amount),
whereas decompressing a small input could produce gigabytes of output.

Re: [PATCH] lib/lzo: Avoid output overruns when compressing

[Sergey Senozhatsky]

On (25/02/28 13:43), Ard Biesheuvel wrote:
> On Fri, 28 Feb 2025 at 06:24, Sergey Senozhatsky
> <senozhatsky@chromium.org> wrote:
> >
> > On (25/02/26 14:00), David Sterba wrote:
> > > What strikes me as alarming that you insert about 20 branches into a
> > > realtime compression algorithm, where everything is basically a hot
> > > path.  Branches that almost never happen, and never if the output buffer
> > > is big enough.
> > >
> > > Please drop the patch.
> >
> > David, just for educational purposes, there's only safe variant of lzo
> > decompression, which seems to be doing a lot of NEED_OP (HAVE_OP) adding
> > branches and so on, basically what Herbert is adding to the compression
> > path.  So my question is - why NEED_OP (if (!HAVE_OP(x)) goto output_overrun)
> > is a no go for compression, but appears to be fine for decompression?
> >
> 
> Because compression has a bounded worst case (compressing data with
> LZO can actually increase the size but only by a limited amount),
> whereas decompressing a small input could produce gigabytes of output.

One can argue that sometimes we know the upper bound.  E.g. zswap
and zram always compress physical pages, so decompression cannot
result in a bigger (than the original physical page) data.

Re: [PATCH] lib/lzo: Avoid output overruns when compressing

[David Sterba]

On Fri, Feb 28, 2025 at 10:55:35PM +0900, Sergey Senozhatsky wrote:
> On (25/02/28 13:43), Ard Biesheuvel wrote:
> > On Fri, 28 Feb 2025 at 06:24, Sergey Senozhatsky
> > <senozhatsky@chromium.org> wrote:
> > >
> > > On (25/02/26 14:00), David Sterba wrote:
> > > > What strikes me as alarming that you insert about 20 branches into a
> > > > realtime compression algorithm, where everything is basically a hot
> > > > path.  Branches that almost never happen, and never if the output buffer
> > > > is big enough.
> > > >
> > > > Please drop the patch.
> > >
> > > David, just for educational purposes, there's only safe variant of lzo
> > > decompression, which seems to be doing a lot of NEED_OP (HAVE_OP) adding
> > > branches and so on, basically what Herbert is adding to the compression
> > > path.  So my question is - why NEED_OP (if (!HAVE_OP(x)) goto output_overrun)
> > > is a no go for compression, but appears to be fine for decompression?
> > >
> > 
> > Because compression has a bounded worst case (compressing data with
> > LZO can actually increase the size but only by a limited amount),
> > whereas decompressing a small input could produce gigabytes of output.
> 
> One can argue that sometimes we know the upper bound.  E.g. zswap
> and zram always compress physical pages, so decompression cannot
> result in a bigger (than the original physical page) data.

So for ZRAM it would make sense to have "unsafe" decompression as the
data never leave the kernel space and cannot be tampered with from the
outside, unlike what filesystem deals with. This can gain some speed up.