From: Xueyuan Chen <xueyuan.chen21@gmail.com>
To: Minchan Kim <minchan@kernel.org>,
Sergey Senozhatsky <senozhatsky@chromium.org>,
Jens Axboe <axboe@kernel.dk>
Cc: linux-kernel@vger.kernel.org, linux-block@vger.kernel.org,
Xueyuan Chen <xueyuan.chen21@gmail.com>
Subject: [PATCH RFC 2/3] lib/lz4: add safe decompression from two input buffers
Date: Sun, 22 Nov 2026 01:09:25 +0800 [thread overview]
Message-ID: <20261122-zram-split-decomp-mm-rfc-v1-2-4e69b08c0fed@gmail.com> (raw)
In-Reply-To: <20261122-zram-split-decomp-mm-rfc-v1-0-4e69b08c0fed@gmail.com>
LZ4_decompress_generic() assumes contiguous input. Its wide literal
loads can cross the boundary between independently mapped fragments.
Add a dictionary-free block decoder that reads from two buffers and
handles literals, lengths and offsets that cross the split.
Signed-off-by: Xueyuan Chen <xueyuan.chen21@gmail.com>
---
include/linux/lz4.h | 18 ++++++
lib/lz4/lz4_decompress.c | 163 +++++++++++++++++++++++++++++++++++++++++++++++
2 files changed, 181 insertions(+)
diff --git a/include/linux/lz4.h b/include/linux/lz4.h
index ad6042a718b5..3b6217bd9a9b 100644
--- a/include/linux/lz4.h
+++ b/include/linux/lz4.h
@@ -292,6 +292,24 @@ int LZ4_decompress_fast(const char *source, char *dest, int originalSize);
int LZ4_decompress_safe(const char *source, char *dest, int compressedSize,
int maxDecompressedSize);
+/**
+ * LZ4_decompress_safe_split() - Decode a single block from two buffers
+ * @first: address of the first input fragment
+ * @first_len: bytes in the first input fragment
+ * @second: address of the second input fragment
+ * @second_len: bytes in the second input fragment
+ * @dst: output buffer, disjoint from the input buffers
+ * @capacity: bytes available in the output buffer
+ *
+ * The fragments, in order, contain one dictionary-free LZ4 block.
+ * Their addresses need not be adjacent. An empty fragment may be NULL.
+ *
+ * Return: the decoded size, or -EINVAL on error.
+ */
+int LZ4_decompress_safe_split(const u8 *first, size_t first_len,
+ const u8 *second, size_t second_len,
+ u8 *dst, int capacity);
+
/**
* LZ4_decompress_safe_partial() - Decompress a block of size 'compressedSize'
* at position 'source' into buffer 'dest'
diff --git a/lib/lz4/lz4_decompress.c b/lib/lz4/lz4_decompress.c
index 3a2cd9acada4..548197faa3e3 100644
--- a/lib/lz4/lz4_decompress.c
+++ b/lib/lz4/lz4_decompress.c
@@ -39,6 +39,11 @@
#include <linux/kernel.h>
#include <linux/unaligned.h>
+#ifndef STATIC
+#include <linux/errno.h>
+#include <linux/limits.h>
+#endif
+
/*-*****************************
* Decompression functions
*******************************/
@@ -705,6 +710,164 @@ int LZ4_decompress_fast_usingDict(const char *source, char *dest,
}
#ifndef STATIC
+struct lz4_split_input {
+ const u8 *first;
+ const u8 *second;
+ size_t split;
+ size_t size;
+ size_t pos;
+};
+
+static __always_inline size_t
+lz4_split_input_left(const struct lz4_split_input *in)
+{
+ return in->size - in->pos;
+}
+
+static __always_inline int lz4_split_get_byte(struct lz4_split_input *in)
+{
+ size_t pos = in->pos;
+
+ if (unlikely(pos == in->size))
+ return -1;
+ in->pos++;
+ if (pos < in->split)
+ return in->first[pos];
+ return in->second[pos - in->split];
+}
+
+/* The caller has checked that two bytes remain in the block. */
+static __always_inline int lz4_split_get_offset(struct lz4_split_input *in)
+{
+ size_t pos = in->pos;
+
+ in->pos += 2;
+ if (pos >= in->split)
+ return get_unaligned_le16(in->second + (pos - in->split));
+ if (in->split - pos >= 2)
+ return get_unaligned_le16(in->first + pos);
+ return in->first[pos] | (in->second[0] << 8);
+}
+
+static __always_inline bool
+lz4_split_copy_literals(struct lz4_split_input *in, u8 *dst, size_t len)
+{
+ size_t pos = in->pos;
+
+ if (unlikely(len > lz4_split_input_left(in)))
+ return false;
+ if (!len)
+ return true;
+ if (pos < in->split) {
+ size_t n = min(len, in->split - pos);
+
+ memcpy(dst, in->first + pos, n);
+ pos += n;
+ dst += n;
+ len -= n;
+ }
+ if (len)
+ memcpy(dst, in->second + (pos - in->split), len);
+ in->pos = pos + len;
+ return true;
+}
+
+/* The decoder has checked the lookbehind distance and output capacity. */
+static __always_inline void
+lz4_split_copy_match(u8 *dst, size_t distance, size_t len)
+{
+ size_t copied = min(distance, len);
+
+ if (distance == 1) {
+ memset(dst, dst[-1], len);
+ return;
+ }
+
+ memcpy(dst, dst - distance, copied);
+ /* Reuse the period already written, keeping each copy disjoint. */
+ while (len - copied > copied) {
+ memcpy(dst + copied, dst, copied);
+ copied *= 2;
+ }
+ if (copied < len)
+ memcpy(dst + copied, dst, len - copied);
+}
+
+static __always_inline int
+lz4_split_read_length(struct lz4_split_input *in, int length, int limit)
+{
+ int byte;
+
+ if (length > limit)
+ return -EINVAL;
+ if (length < RUN_MASK)
+ return length;
+
+ do {
+ byte = lz4_split_get_byte(in);
+ if (byte < 0 || byte > limit - length)
+ return -EINVAL;
+ length += byte;
+ } while (byte == 255);
+ return length;
+}
+
+int LZ4_decompress_safe_split(const u8 *first, size_t first_len,
+ const u8 *second, size_t second_len,
+ u8 *dst, int capacity)
+{
+ struct lz4_split_input in = {
+ .first = first,
+ .second = second,
+ .split = first_len,
+ };
+ int written = 0, min_last_literals = 0;
+
+ if (capacity < 0 || !dst || (!first && first_len) ||
+ (!second && second_len) || first_len > SIZE_MAX - second_len)
+ return -EINVAL;
+ in.size = first_len + second_len;
+
+ for (;;) {
+ int token, literal, distance, match;
+
+ token = lz4_split_get_byte(&in);
+ if (token < 0)
+ return -EINVAL;
+ literal = lz4_split_read_length(&in, token >> ML_BITS,
+ capacity - written);
+ if (literal < 0 ||
+ !lz4_split_copy_literals(&in, dst + written, literal))
+ return -EINVAL;
+ written += literal;
+ if (!lz4_split_input_left(&in))
+ return literal >= min_last_literals ? written : -EINVAL;
+
+ /* A match must leave room for the final literal sequence. */
+ if (lz4_split_input_left(&in) < 2 + 1 + LASTLITERALS ||
+ capacity - written < MFLIMIT)
+ return -EINVAL;
+
+ distance = lz4_split_get_offset(&in);
+ if (!distance || distance > written)
+ return -EINVAL;
+ match = lz4_split_read_length(&in, token & ML_MASK,
+ capacity - written - MINMATCH -
+ LASTLITERALS);
+ if (match < 0)
+ return -EINVAL;
+ match += MINMATCH;
+ lz4_split_copy_match(dst + written, distance, match);
+ written += match;
+ /*
+ * Leave at least LASTLITERALS bytes and end at least MFLIMIT
+ * bytes past the start of the last match.
+ */
+ min_last_literals = max(LASTLITERALS, MFLIMIT - match);
+ }
+}
+EXPORT_SYMBOL_GPL(LZ4_decompress_safe_split);
+
EXPORT_SYMBOL(LZ4_decompress_safe);
EXPORT_SYMBOL(LZ4_decompress_safe_partial);
EXPORT_SYMBOL(LZ4_decompress_fast);
--
2.47.3
next prev parent reply other threads:[~2026-11-21 17:09 UTC|newest]
Thread overview: 5+ messages / expand[flat|nested] mbox.gz Atom feed top
2026-11-21 17:09 [PATCH RFC 0/3] zram: avoid copying spanning LZ4 objects before decompression Xueyuan Chen
2026-11-21 17:09 ` [PATCH RFC 1/3] zram: allow backends to decompress from two input buffers Xueyuan Chen
2026-11-21 17:09 ` Xueyuan Chen [this message]
2026-11-21 17:09 ` [PATCH RFC 3/3] zram: use split-input decompression for LZ4 and LZ4HC Xueyuan Chen
2026-11-21 20:15 ` [PATCH RFC 0/3] zram: avoid copying spanning LZ4 objects before decompression Eric Biggers
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=20261122-zram-split-decomp-mm-rfc-v1-2-4e69b08c0fed@gmail.com \
--to=xueyuan.chen21@gmail.com \
--cc=axboe@kernel.dk \
--cc=linux-block@vger.kernel.org \
--cc=linux-kernel@vger.kernel.org \
--cc=minchan@kernel.org \
--cc=senozhatsky@chromium.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox