From a5bde5d8fde8a8cb28e59a672d5ddc5b9c1e7656 Mon Sep 17 00:00:00 2001 From: Breno Leitao Date: Wed, 5 Aug 2026 07:52:36 -0700 Subject: workqueue: skip the node_nr_active update for non-unbound workqueues apply_wqattrs_commit() updates node_nr_active->max unconditionally. wq->node_nr_active[] is only allocated for unbound workqueues, so guard the call before per-cpu workqueues start using this path. No functional change: only unbound workqueues reach apply_wqattrs_*() today. Signed-off-by: Breno Leitao Signed-off-by: Tejun Heo --- fs/smb/common/compress/compress.c | 399 +++++++++++++++++++++++++++++++++ fs/smb/common/compress/compress.h | 28 +++ fs/smb/common/compress/lz77.c | 461 ++++++++++++++++++++++++++++++++++++++ fs/smb/common/compress/lz77.h | 46 ++++ 4 files changed, 934 insertions(+) create mode 100644 fs/smb/common/compress/compress.c create mode 100644 fs/smb/common/compress/compress.h create mode 100644 fs/smb/common/compress/lz77.c create mode 100644 fs/smb/common/compress/lz77.h (limited to 'fs/smb/common/compress') diff --git a/fs/smb/common/compress/compress.c b/fs/smb/common/compress/compress.c new file mode 100644 index 000000000..b07a31759 --- /dev/null +++ b/fs/smb/common/compress/compress.c @@ -0,0 +1,399 @@ +// SPDX-License-Identifier: GPL-2.0-or-later +/* + * SMB2 compression transform helpers. + * + * Copyright (C) 2026 Namjae Jeon + */ +#include +#include +#include +#include + +#include "compress.h" +#include "lz77.h" + +#define SMB2_COMPRESSION_CHAINED_HDR_LEN \ + offsetof(struct smb2_compression_hdr, CompressionAlgorithm) +#define SMB2_COMPRESSION_PAYLOAD_BASE_LEN \ + (sizeof(struct smb2_compression_payload_hdr) - sizeof(__le32)) + +/* + * A NONE payload carries bytes verbatim. Keep both cursors and remaining + * lengths together so every chained payload handler applies identical bounds + * accounting. + */ +static int smb_decompress_none(const u8 **src, u32 *slen, u8 **dst, u32 *dlen, + u32 len) +{ + if (len > *slen || len > *dlen) + return -EINVAL; + + memcpy(*dst, *src, len); + *src += len; + *slen -= len; + *dst += len; + *dlen -= len; + return 0; +} + +/* + * Pattern_V1 represents a run of one byte. Its wire payload is always the + * fixed-size smb2_compression_pattern_v1 structure. + */ +static int smb_decompress_pattern(const u8 **src, u32 *slen, u8 **dst, + u32 *dlen, u32 len) +{ + const struct smb2_compression_pattern_v1 *pattern; + u32 repetitions; + + if (len != sizeof(*pattern) || len > *slen) + return -EINVAL; + + pattern = (const struct smb2_compression_pattern_v1 *)*src; + repetitions = le32_to_cpu(pattern->Repetitions); + if (repetitions > *dlen) + return -EINVAL; + + memset(*dst, pattern->Pattern, repetitions); + *src += len; + *slen -= len; + *dst += repetitions; + *dlen -= repetitions; + return 0; +} + +/* + * LZ77 payload Length includes the four-byte OriginalPayloadSize field. + * Consume that field before passing the compressed stream to the raw codec. + */ +static int smb_decompress_lz77_payload(const u8 **src, u32 *slen, u8 **dst, + u32 *dlen, u32 len) +{ + u32 orig_size; + int rc; + + if (len < sizeof(__le32) || len > *slen) + return -EINVAL; + + orig_size = get_unaligned_le32(*src); + if (orig_size > *dlen) + return -EINVAL; + + *src += sizeof(__le32); + *slen -= sizeof(__le32); + len -= sizeof(__le32); + + rc = smb_lz77_decompress(*src, len, *dst, orig_size); + if (rc) + return rc; + + *src += len; + *slen -= len; + *dst += orig_size; + *dlen -= orig_size; + return 0; +} + +static int smb_decompress_chained(__le16 alg, bool allow_chained, + const struct smb2_compression_hdr *hdr, + u32 slen, void *dst, u32 dlen) +{ + const struct smb2_compression_payload_hdr *payload; + const u8 *src = (const u8 *)hdr + SMB2_COMPRESSION_CHAINED_HDR_LEN; + u32 orig_size = le32_to_cpu(hdr->OriginalCompressedSegmentSize); + u32 remaining = slen - SMB2_COMPRESSION_CHAINED_HDR_LEN; + u8 *out = dst; + u32 out_remaining = dlen; + bool first = true; + int rc; + + if (!allow_chained || orig_size != dlen) + return -EINVAL; + + /* + * The chained transform has an eight-byte top-level header. The next + * bytes are a sequence of payload headers whose Length fields account + * for payload data, including OriginalPayloadSize where applicable. + */ + while (remaining) { + __le16 payload_alg; + __le16 flags; + u32 len; + + if (remaining < SMB2_COMPRESSION_PAYLOAD_BASE_LEN) + return -EINVAL; + + payload = (const struct smb2_compression_payload_hdr *)src; + payload_alg = payload->CompressionAlgorithm; + flags = payload->Flags; + len = le32_to_cpu(payload->Length); + + /* + * CHAINED marks only the first payload. Requiring NONE on every + * later payload rejects ambiguous or independently chained data. + */ + if ((first && flags != cpu_to_le16(SMB2_COMPRESSION_FLAG_CHAINED)) || + (!first && flags != cpu_to_le16(SMB2_COMPRESSION_FLAG_NONE))) + return -EINVAL; + + src += SMB2_COMPRESSION_PAYLOAD_BASE_LEN; + remaining -= SMB2_COMPRESSION_PAYLOAD_BASE_LEN; + + if (payload_alg == SMB3_COMPRESS_NONE) { + rc = smb_decompress_none(&src, &remaining, &out, + &out_remaining, len); + } else if (payload_alg == SMB3_COMPRESS_PATTERN) { + rc = smb_decompress_pattern(&src, &remaining, &out, + &out_remaining, len); + } else if (payload_alg == alg && alg == SMB3_COMPRESS_LZ77) { + rc = smb_decompress_lz77_payload(&src, &remaining, &out, + &out_remaining, len); + } else { + return -EINVAL; + } + if (rc) + return rc; + first = false; + } + + return out_remaining ? -EINVAL : 0; +} + +static int smb_decompress_unchained(__le16 alg, + const struct smb2_compression_hdr *hdr, + u32 slen, void *dst, u32 dlen) +{ + u32 orig_size, offset, comp_size; + + if (hdr->CompressionAlgorithm != alg || + !smb_compress_alg_valid(hdr->CompressionAlgorithm, false)) + return -EINVAL; + + orig_size = le32_to_cpu(hdr->OriginalCompressedSegmentSize); + offset = le32_to_cpu(hdr->Offset); + if (offset > slen - sizeof(*hdr) || offset > dlen || + orig_size > dlen - offset || orig_size + offset != dlen) + return -EINVAL; + + memcpy(dst, (const u8 *)hdr + sizeof(*hdr), offset); + comp_size = slen - sizeof(*hdr) - offset; + return smb_lz77_decompress((const u8 *)hdr + sizeof(*hdr) + offset, + comp_size, (u8 *)dst + offset, orig_size); +} + +/** + * smb_compression_decompress() - decode an SMB2 compression transform + * @alg: negotiated general-purpose compression algorithm + * @allow_chained: whether chained transforms were negotiated + * @src: transform header followed by compressed payload data + * @slen: total number of bytes available at @src + * @dst: output buffer for the reconstructed SMB2 message + * @dlen: exact expected size of the reconstructed SMB2 message + * + * Validate the transform type and negotiated capabilities before dispatching + * to the chained or unchained decoder. The caller supplies the expected output + * size after applying its transport-specific message size limits. + * + * Return: 0 on success, otherwise a negative errno. + */ +int smb_compression_decompress(__le16 alg, bool allow_chained, + const void *src, u32 slen, void *dst, u32 dlen) +{ + const struct smb2_compression_hdr *hdr = src; + + if (!src || !dst || slen < sizeof(*hdr) || + hdr->ProtocolId != SMB2_COMPRESSION_TRANSFORM_ID || + alg == SMB3_COMPRESS_NONE) + return -EINVAL; + + if (hdr->Flags == cpu_to_le16(SMB2_COMPRESSION_FLAG_CHAINED)) + return smb_decompress_chained(alg, allow_chained, hdr, slen, + dst, dlen); + + if (hdr->Flags != cpu_to_le16(SMB2_COMPRESSION_FLAG_NONE)) + return -EINVAL; + + return smb_decompress_unchained(alg, hdr, slen, dst, dlen); +} +EXPORT_SYMBOL_GPL(smb_compression_decompress); + +struct smb_compression_builder { + u8 *pos; + u32 remaining; + bool first; +}; + +/* + * Reserve one chained payload header and initialize its common fields. + * OriginalPayloadSize is present only for LZNT1/LZ77/LZ77+Huffman payloads. + */ +static struct smb2_compression_payload_hdr * +smb_compression_add_payload(struct smb_compression_builder *builder, + __le16 alg, u32 payload_len, bool orig_size) +{ + struct smb2_compression_payload_hdr *payload; + u32 hdr_len = SMB2_COMPRESSION_PAYLOAD_BASE_LEN; + u32 total_len; + + if (orig_size) + hdr_len += sizeof(payload->OriginalPayloadSize); + if (check_add_overflow(hdr_len, payload_len, &total_len) || + total_len > builder->remaining) + return NULL; + + payload = (struct smb2_compression_payload_hdr *)builder->pos; + payload->CompressionAlgorithm = alg; + payload->Flags = cpu_to_le16(builder->first ? + SMB2_COMPRESSION_FLAG_CHAINED : SMB2_COMPRESSION_FLAG_NONE); + payload->Length = cpu_to_le32(payload_len + + (orig_size ? sizeof(payload->OriginalPayloadSize) : 0)); + + builder->pos += hdr_len; + builder->remaining -= hdr_len; + builder->first = false; + return payload; +} + +static int smb_compression_add_pattern(struct smb_compression_builder *builder, + u8 pattern, u32 repetitions) +{ + struct smb2_compression_pattern_v1 *payload; + + if (!smb_compression_add_payload(builder, SMB3_COMPRESS_PATTERN, + sizeof(*payload), false)) + return -ENOSPC; + + payload = (struct smb2_compression_pattern_v1 *)builder->pos; + payload->Pattern = pattern; + payload->Reserved1 = 0; + payload->Reserved2 = 0; + payload->Repetitions = cpu_to_le32(repetitions); + builder->pos += sizeof(*payload); + builder->remaining -= sizeof(*payload); + return 0; +} + +static int smb_compression_add_none(struct smb_compression_builder *builder, + const u8 *src, u32 len) +{ + if (!smb_compression_add_payload(builder, SMB3_COMPRESS_NONE, len, false)) + return -ENOSPC; + + memcpy(builder->pos, src, len); + builder->pos += len; + builder->remaining -= len; + return 0; +} + +static int smb_compression_add_lz77(struct smb_compression_builder *builder, + const u8 *src, u32 len) +{ + struct smb2_compression_payload_hdr *payload; + u32 comp_len; + int rc; + + if (builder->remaining <= sizeof(*payload)) + return -ENOSPC; + + comp_len = builder->remaining - sizeof(*payload); + payload = smb_compression_add_payload(builder, SMB3_COMPRESS_LZ77, + comp_len, true); + if (!payload) + return -ENOSPC; + + rc = smb_lz77_compress(src, len, builder->pos, &comp_len); + if (rc) + return rc; + + payload->Length = cpu_to_le32(comp_len + + sizeof(payload->OriginalPayloadSize)); + payload->OriginalPayloadSize = cpu_to_le32(len); + builder->pos += comp_len; + builder->remaining -= comp_len; + return 0; +} + +/** + * smb_compression_compress_chained() - build a chained SMB2 transform + * @alg: negotiated general-purpose compression algorithm + * @allow_pattern: whether Pattern_V1 was negotiated + * @src: complete uncompressed SMB2 message + * @slen: size of @src + * @dst: output buffer for the transform + * @dlen: input capacity of @dst and output transform size + * + * Following the algorithm in [MS-SMB2] 3.1.4.4, encode sufficiently long + * repeated runs at the front and back as Pattern_V1 payloads. Compress a + * middle region larger than 1 KiB with LZ77; smaller middle regions are + * represented by a chained NONE payload. + * + * This helper does not decide whether the final transform is smaller than the + * original message. The transport caller owns that policy decision. + * + * Return: 0 on success, otherwise a negative errno. + */ +int smb_compression_compress_chained(__le16 alg, bool allow_pattern, + const void *src, u32 slen, + void *dst, u32 *dlen) +{ + struct smb2_compression_hdr *hdr = dst; + struct smb_compression_builder builder; + const u8 *input = src; + u32 forward = 0, backward = 0, middle_len; + int rc; + + if (!src || !dst || !dlen || alg != SMB3_COMPRESS_LZ77 || + *dlen <= SMB2_COMPRESSION_CHAINED_HDR_LEN || !slen) + return -EINVAL; + + hdr->ProtocolId = SMB2_COMPRESSION_TRANSFORM_ID; + hdr->OriginalCompressedSegmentSize = cpu_to_le32(slen); + builder.pos = (u8 *)dst + SMB2_COMPRESSION_CHAINED_HDR_LEN; + builder.remaining = *dlen - SMB2_COMPRESSION_CHAINED_HDR_LEN; + builder.first = true; + + if (allow_pattern && slen > 32) { + for (forward = 1; forward < slen; forward++) { + if (input[forward] != input[0]) + break; + } + if (forward <= 32) + forward = 0; + + for (backward = 1; backward < slen - forward; backward++) { + if (input[slen - backward - 1] != input[slen - 1]) + break; + } + if (backward <= 32) + backward = 0; + } + + if (forward) { + rc = smb_compression_add_pattern(&builder, input[0], forward); + if (rc) + return rc; + } + + middle_len = slen - forward - backward; + if (middle_len > 1024) + rc = smb_compression_add_lz77(&builder, input + forward, + middle_len); + else if (middle_len) + rc = smb_compression_add_none(&builder, + input + forward, middle_len); + else + rc = 0; + if (rc) + return rc; + + if (backward) { + rc = smb_compression_add_pattern(&builder, input[slen - 1], + backward); + if (rc) + return rc; + } + + *dlen = builder.pos - (u8 *)dst; + return 0; +} +EXPORT_SYMBOL_GPL(smb_compression_compress_chained); diff --git a/fs/smb/common/compress/compress.h b/fs/smb/common/compress/compress.h new file mode 100644 index 000000000..7ace3bf4b --- /dev/null +++ b/fs/smb/common/compress/compress.h @@ -0,0 +1,28 @@ +/* SPDX-License-Identifier: GPL-2.0-only */ +/* + * Copyright (C) 2026 Namjae Jeon + */ +#ifndef _COMMON_SMB_COMPRESS_H +#define _COMMON_SMB_COMPRESS_H + +#include "../smb2pdu.h" + +/* + * SMB3_COMPRESS_NONE is valid only in chained payload headers. It is never + * negotiated as a compression algorithm. + */ +static __always_inline bool smb_compress_alg_valid(__le16 alg, bool valid_none) +{ + if (alg == SMB3_COMPRESS_NONE) + return valid_none; + + return alg == SMB3_COMPRESS_LZ77 || alg == SMB3_COMPRESS_PATTERN; +} + +int smb_compression_decompress(__le16 alg, bool allow_chained, + const void *src, u32 slen, void *dst, u32 dlen); +int smb_compression_compress_chained(__le16 alg, bool allow_pattern, + const void *src, u32 slen, + void *dst, u32 *dlen); + +#endif /* _COMMON_SMB_COMPRESS_H */ diff --git a/fs/smb/common/compress/lz77.c b/fs/smb/common/compress/lz77.c new file mode 100644 index 000000000..9216d973d --- /dev/null +++ b/fs/smb/common/compress/lz77.c @@ -0,0 +1,461 @@ +// SPDX-License-Identifier: GPL-2.0-only +/* + * Copyright (C) 2024-2026, SUSE LLC + * Copyright (C) 2026 Namjae Jeon + * + * Authors: Enzo Matsumiya + * Namjae Jeon + * + * Implementation of the LZ77 "plain" compression algorithm, as per MS-XCA spec. + */ +#include +#include +#include +#include +#include +#include + +#include "lz77.h" + +/* + * Compression parameters. + * + * LZ77_MATCH_MAX_DIST: Farthest back a match can be from current position (can be 1 - 8K). + * LZ77_HASH_LOG: + * LZ77_HASH_SIZE: ilog2 hash size (recommended to be 13 - 18, default 15 (hash size + * 32k)). + * LZ77_RSTEP_SIZE: Number of bytes to read from input buffer for hashing and initial + * match check (default 4 bytes, this effectivelly makes this the min + * match len). + * LZ77_MSTEP_SIZE: Number of bytes to extend-compare a found match (default 8 bytes). + * LZ77_SKIP_TRIGGER: ilog2 value for adaptive skipping, i.e. to progressively skip input + * bytes when we can't find matches. Default is 4. + * Higher values (>0) will decrease compression time, but will result + * in worse compression ratio. Lower values will give better + * compression ratio (more matches found), but will increase time. + */ +#define LZ77_MATCH_MAX_DIST SZ_8K +#define LZ77_HASH_LOG 15 +#define LZ77_HASH_SIZE BIT(LZ77_HASH_LOG) +#define LZ77_RSTEP_SIZE sizeof(u32) +#define LZ77_MSTEP_SIZE sizeof(u64) +#define LZ77_SKIP_TRIGGER 4 + +#define LZ77_PREFETCH(ptr) __builtin_prefetch((ptr), 0, 3) +#define LZ77_FLAG_MAX 32 + +static __always_inline u8 lz77_read8(const u8 *ptr) +{ + return get_unaligned(ptr); +} + +static __always_inline u32 lz77_read32(const u32 *ptr) +{ + return get_unaligned(ptr); +} + +static __always_inline u64 lz77_read64(const u64 *ptr) +{ + return get_unaligned(ptr); +} + +static __always_inline void lz77_write8(u8 *ptr, u8 v) +{ + put_unaligned(v, ptr); +} + +static __always_inline void lz77_write16(u16 *ptr, u16 v) +{ + put_unaligned_le16(v, ptr); +} + +static __always_inline void lz77_write32(u32 *ptr, u32 v) +{ + put_unaligned_le32(v, ptr); +} + +static __always_inline u32 lz77_match_len(const void *match, const void *cur, const void *end) +{ + const void *start = cur; + + /* Safe for a do/while because otherwise we wouldn't reach here from the main loop. */ + do { + const u64 diff = lz77_read64(cur) ^ lz77_read64(match); + + if (!diff) { + cur += LZ77_MSTEP_SIZE; + match += LZ77_MSTEP_SIZE; + + continue; + } + + /* This computes the number of common bytes in @diff. */ + cur += count_trailing_zeros(diff) >> 3; + + return (cur - start); + } while (likely(cur + LZ77_MSTEP_SIZE <= end)); + + /* Fallback to byte-by-byte comparison for last <8 bytes. */ + while (cur < end && lz77_read8(cur) == lz77_read8(match)) { + cur++; + match++; + } + + return (cur - start); +} + +/** + * lz77_encode_match() - Match encoding. + * @dst: compressed buffer + * @nib: pointer to an address in @dst + * @dist: match distance + * @len: match length + * + * Assumes all args were previously checked. + * + * Return: @dst advanced to new position + * + * Ref: MS-XCA 2.3.4 "Plain LZ77 Compression Algorithm Details" - "Processing" + */ +static __always_inline void *lz77_encode_match(void *dst, void **nib, u16 dist, u32 len) +{ + len -= 3; + dist--; + dist <<= 3; + + if (len < 7) { + lz77_write16(dst, dist + len); + + return dst + sizeof(u16); + } + + dist |= 7; + lz77_write16(dst, dist); + dst += sizeof(u16); + len -= 7; + + if (!*nib) { + lz77_write8(dst, umin(len, 15)); + *nib = dst; + dst++; + } else { + u8 *b = *nib; + + lz77_write8(b, *b | umin(len, 15) << 4); + *nib = NULL; + } + + if (len < 15) + return dst; + + len -= 15; + if (len < 255) { + lz77_write8(dst, len); + + return dst + 1; + } + + lz77_write8(dst, 0xff); + dst++; + len += 7 + 15; + if (len <= 0xffff) { + lz77_write16(dst, len); + + return dst + sizeof(u16); + } + + lz77_write16(dst, 0); + dst += sizeof(u16); + lz77_write32(dst, len); + + return dst + sizeof(u32); +} + +/** + * lz77_encode_literals() - Literals encoding. + * @start: where to start copying literals (uncompressed buffer) + * @end: when to stop copying (uncompressed buffer) + * @dst: compressed buffer + * @f: pointer to current flag value + * @fc: pointer to current flag count + * @fp: pointer to current flag address + * + * Batch copy literals from @start to @dst, updating flag values accordingly. + * Assumes all args were previously checked. + * + * Return: @dst advanced to new position + * + * MS-XCA 2.3.4 "Plain LZ77 Compression Algorithm Details" - "Processing" + */ +static __always_inline void *lz77_encode_literals(const void *start, const void *end, void *dst, + long *f, u32 *fc, void **fp) +{ + if (start >= end) + return dst; + + do { + const u32 len = umin(end - start, LZ77_FLAG_MAX - *fc); + + memcpy(dst, start, len); + + dst += len; + start += len; + + *f <<= len; + *fc += len; + if (*fc == LZ77_FLAG_MAX) { + lz77_write32(*fp, *f); + *fc = 0; + *fp = dst; + dst += sizeof(u32); + } + } while (start < end); + + return dst; +} + +static __always_inline u32 lz77_hash(const u32 v) +{ + return ((v ^ 0x9E3779B9) * 0x85EBCA6B) >> (32 - LZ77_HASH_LOG); +} + +noinline int smb_lz77_compress(const void *src, const u32 slen, + void *dst, u32 *dlen) +{ + const void *srcp, *rlim, *end, *anchor; + u32 *htable, hash, flag_count = 0; + void *dstp, *nib, *flag_pos; + long flag = 0; + + /* This is probably a bug, so throw a warning. */ + if (WARN_ON_ONCE(*dlen < smb_lz77_compressed_alloc_size(slen))) + return -EINVAL; + + srcp = src; + anchor = src; + end = srcp + slen; /* absolute end */ + rlim = end - LZ77_MSTEP_SIZE; /* read limit (for lz77_match_len()) */ + dstp = dst; + flag_pos = dstp; + dstp += sizeof(u32); + nib = NULL; + + htable = kvcalloc(LZ77_HASH_SIZE, sizeof(*htable), GFP_KERNEL); + if (!htable) + return -ENOMEM; + + LZ77_PREFETCH(srcp + LZ77_RSTEP_SIZE); + + /* + * Adjust @srcp so we don't get a false positive match on first iteration. + * Then prepare hash for first loop iteration (don't advance @srcp again). + */ + hash = lz77_hash(lz77_read32(srcp++)); + htable[hash] = 0; + hash = lz77_hash(lz77_read32(srcp)); + + /* + * Main loop. + * + * @dlen is >= smb_lz77_compressed_alloc_size(), so run without + * bound-checking @dstp. + * + * This code was crafted in a way to best utilise fetch-decode-execute CPU flow. + * Any attempt to optimize it, or even organize it, can lead to huge performance loss. + */ + do { + const void *match, *next = srcp; + u32 len, step = 1, skip = 1U << LZ77_SKIP_TRIGGER; + + /* Match finding (hot path -- don't change the read/check/write order). */ + do { + const u32 cur_hash = hash; + + srcp = next; + next += step; + + /* + * Adaptive skipping. + * + * Increment @step every (1 << LZ77_SKIP_TRIGGER, 16 in our case) bytes + * without a match. + * Reset to 1 when a match is found. + */ + step = (skip++ >> LZ77_SKIP_TRIGGER); + if (unlikely(next > rlim)) + goto out; + + hash = lz77_hash(lz77_read32(next)); + match = src + htable[cur_hash]; + htable[cur_hash] = srcp - src; + } while (likely(match + LZ77_MATCH_MAX_DIST < srcp) || + lz77_read32(match) != lz77_read32(srcp)); + + /* + * Match found. Warm/cold path; begin parsing @srcp and writing to @dstp: + * - flush literals + * - compute match length (*) + * - encode match + * + * (*) Current minimum match length is defined by the memory read size above, so + * here we already know that we have 4 matching bytes, but it's just faster to + * redundantly compute it again in lz77_match_len() than to adjust pointers/len. + */ + dstp = lz77_encode_literals(anchor, srcp, dstp, &flag, &flag_count, &flag_pos); + len = lz77_match_len(match, srcp, end); + dstp = lz77_encode_match(dstp, &nib, srcp - match, len); + srcp += len; + anchor = srcp; + + LZ77_PREFETCH(srcp); + + flag = (flag << 1) | 1; + flag_count++; + if (flag_count == LZ77_FLAG_MAX) { + lz77_write32(flag_pos, flag); + flag_count = 0; + flag_pos = dstp; + dstp += sizeof(u32); + } + + if (unlikely(srcp > rlim)) + break; + + /* Prepare for next loop. */ + hash = lz77_hash(lz77_read32(srcp)); + } while (srcp < end); +out: + dstp = lz77_encode_literals(anchor, end, dstp, &flag, &flag_count, &flag_pos); + + flag_count = LZ77_FLAG_MAX - flag_count; + flag <<= flag_count; + flag |= (1UL << flag_count) - 1; + lz77_write32(flag_pos, flag); + + *dlen = dstp - dst; + kvfree(htable); + + if (*dlen < slen) + return 0; + + return -EMSGSIZE; +} +EXPORT_SYMBOL_GPL(smb_lz77_compress); + +static int lz77_decode_match_len(const u8 **src, const u8 *end, u16 token, + u8 *nibble, bool *have_nibble, u32 *len) +{ + u8 extra; + + *len = (token & 0x7) + 3; + if ((token & 0x7) != 0x7) + return 0; + + if (!*have_nibble) { + if (*src >= end) + return -EINVAL; + *nibble = *(*src)++; + extra = *nibble & 0xf; + *have_nibble = true; + } else { + extra = *nibble >> 4; + *have_nibble = false; + } + + *len += extra; + if (extra == 0xf) { + u8 b; + + if (*src >= end) + return -EINVAL; + b = *(*src)++; + if (b != 0xff) { + *len += b; + } else { + u16 w; + + if (end - *src < 2) + return -EINVAL; + w = get_unaligned_le16(*src); + *src += 2; + if (w) { + *len = w + 3; + } else { + u32 long_len; + + if (end - *src < 4) + return -EINVAL; + long_len = get_unaligned_le32(*src); + *src += 4; + if (check_add_overflow(long_len, 3, len)) + return -EINVAL; + } + } + } + + return 0; +} + +int smb_lz77_decompress(const void *src, const u32 slen, void *dst, + const u32 dlen) +{ + const u8 *sp = src, *send = sp + slen; + u8 *dp = dst, *dend = dp + dlen; + u32 flags = 0; + int flag_count = 0; + u8 nibble = 0; + bool have_nibble = false; + + while (dp < dend) { + u32 len, dist; + u16 token; + + if (!flag_count) { + if (send - sp < 4) + return -EINVAL; + flags = get_unaligned_le32(sp); + sp += 4; + flag_count = 32; + } + + if (!(flags & 0x80000000)) { + if (sp >= send) + return -EINVAL; + *dp++ = *sp++; + flags <<= 1; + flag_count--; + continue; + } + + flags <<= 1; + flag_count--; + + if (send - sp < 2) + return -EINVAL; + + token = get_unaligned_le16(sp); + sp += 2; + + dist = (token >> 3) + 1; + if (dist > dp - (u8 *)dst) + return -EINVAL; + + if (lz77_decode_match_len(&sp, send, token, &nibble, + &have_nibble, &len)) + return -EINVAL; + + if (len > dend - dp) + return -EINVAL; + + while (len--) { + *dp = *(dp - dist); + dp++; + } + } + + return 0; +} +EXPORT_SYMBOL_GPL(smb_lz77_decompress); + +MODULE_LICENSE("GPL"); +MODULE_DESCRIPTION("SMB plain LZ77 compression"); diff --git a/fs/smb/common/compress/lz77.h b/fs/smb/common/compress/lz77.h new file mode 100644 index 000000000..e032c0f1b --- /dev/null +++ b/fs/smb/common/compress/lz77.h @@ -0,0 +1,46 @@ +/* SPDX-License-Identifier: GPL-2.0-only */ +/* + * Copyright (C) 2024-2026, SUSE LLC + * + * Authors: Enzo Matsumiya + * + * Implementation of the LZ77 "plain" compression algorithm, as per MS-XCA spec. + */ +#ifndef _SMB_COMPRESS_LZ77_H +#define _SMB_COMPRESS_LZ77_H + +#include + +/** + * smb_lz77_compressed_alloc_size() - Compute compressed buffer size. + * @size: uncompressed (src) size + * + * Compute allocation size for the compressed buffer based on uncompressed size. + * Accounts for metadata and overprovision for the worst case scenario. + * + * LZ77 metadata is a 4-byte flag that is written: + * - on dst begin (pos 0) + * - every 32 literals or matches + * - on end-of-stream (possibly, if last write was another flag) + * + * Worst case scenario is an all-literal compression, which means: + * metadata bytes = 4 + ((@size / 32) * 4) + 4, or, simplified, (@size >> 3) + 8 + * + * The worst case scenario rarely happens, but such overprovisioning also + * allows smb_lz77_compress() main loop to run without ever bound checking dst, + * which is a huge perf improvement, while also being safe when compression goes + * bad. + * + * Return: required (*) allocation size for compressed buffer. + * + * (*) checked once in the beginning of smb_lz77_compress() + */ +static __always_inline u32 smb_lz77_compressed_alloc_size(const u32 size) +{ + return size + (size >> 3) + 8; +} + +int smb_lz77_compress(const void *src, const u32 slen, void *dst, u32 *dlen); +int smb_lz77_decompress(const void *src, const u32 slen, void *dst, + const u32 dlen); +#endif /* _SMB_COMPRESS_LZ77_H */ -- cgit v1.3.1