387 lines · c
1// SPDX-License-Identifier: GPL-2.0-only2/*3 * Copyright (C) 2024, SUSE LLC4 *5 * Authors: Enzo Matsumiya <ematsumiya@suse.de>6 *7 * This file implements I/O compression support for SMB2 messages (SMB 3.1.1 only).8 * See compress/ for implementation details of each algorithm.9 *10 * References:11 * MS-SMB2 "3.1.4.4 Compressing the Message"12 * MS-SMB2 "3.1.5.3 Decompressing the Chained Message"13 * MS-XCA - for details of the supported algorithms14 */15#include <linux/slab.h>16#include <linux/kernel.h>17#include <linux/uio.h>18#include <linux/sort.h>19 20#include "cifsglob.h"21#include "../common/smb2pdu.h"22#include "cifsproto.h"23#include "smb2proto.h"24 25#include "compress/lz77.h"26#include "compress.h"27 28/*29 * The heuristic_*() functions below try to determine data compressibility.30 *31 * Derived from fs/btrfs/compression.c, changing coding style, some parameters, and removing32 * unused parts.33 *34 * Read that file for better and more detailed explanation of the calculations.35 *36 * The algorithms are ran in a collected sample of the input (uncompressed) data.37 * The sample is formed of 2K reads in PAGE_SIZE intervals, with a maximum size of 4M.38 *39 * Parsing the sample goes from "low-hanging fruits" (fastest algorithms, likely compressible)40 * to "need more analysis" (likely uncompressible).41 */42 43struct bucket {44 unsigned int count;45};46 47/**48 * has_low_entropy() - Compute Shannon entropy of the sampled data.49 * @bkt: Bytes counts of the sample.50 * @slen: Size of the sample.51 *52 * Return: true if the level (percentage of number of bits that would be required to53 * compress the data) is below the minimum threshold.54 *55 * Note:56 * There _is_ an entropy level here that's > 65 (minimum threshold) that would indicate a57 * possibility of compression, but compressing, or even further analysing, it would waste so much58 * resources that it's simply not worth it.59 *60 * Also Shannon entropy is the last computed heuristic; if we got this far and ended up61 * with uncertainty, just stay on the safe side and call it uncompressible.62 */63static bool has_low_entropy(struct bucket *bkt, size_t slen)64{65 const size_t threshold = 65, max_entropy = 8 * ilog2(16);66 size_t i, p, p2, len, sum = 0;67 68#define pow4(n) (n * n * n * n)69 len = ilog2(pow4(slen));70 71 for (i = 0; i < 256 && bkt[i].count > 0; i++) {72 p = bkt[i].count;73 p2 = ilog2(pow4(p));74 sum += p * (len - p2);75 }76 77 sum /= slen;78 79 return ((sum * 100 / max_entropy) <= threshold);80}81 82#define BYTE_DIST_BAD 083#define BYTE_DIST_GOOD 184#define BYTE_DIST_MAYBE 285/**86 * calc_byte_distribution() - Compute byte distribution on the sampled data.87 * @bkt: Byte counts of the sample.88 * @slen: Size of the sample.89 *90 * Return:91 * BYTE_DIST_BAD: A "hard no" for compression -- a computed uniform distribution of92 * the bytes (e.g. random or encrypted data).93 * BYTE_DIST_GOOD: High probability (normal (Gaussian) distribution) of the data being94 * compressible.95 * BYTE_DIST_MAYBE: When computed byte distribution resulted in "low > n < high"96 * grounds. has_low_entropy() should be used for a final decision.97 */98static int calc_byte_distribution(struct bucket *bkt, size_t slen)99{100 const size_t low = 64, high = 200, threshold = slen * 90 / 100;101 size_t sum = 0;102 int i;103 104 for (i = 0; i < low; i++)105 sum += bkt[i].count;106 107 if (sum > threshold)108 return BYTE_DIST_BAD;109 110 for (; i < high && bkt[i].count > 0; i++) {111 sum += bkt[i].count;112 if (sum > threshold)113 break;114 }115 116 if (i <= low)117 return BYTE_DIST_GOOD;118 119 if (i >= high)120 return BYTE_DIST_BAD;121 122 return BYTE_DIST_MAYBE;123}124 125static bool is_mostly_ascii(const struct bucket *bkt)126{127 size_t count = 0;128 int i;129 130 for (i = 0; i < 256; i++)131 if (bkt[i].count > 0)132 /* Too many non-ASCII (0-63) bytes. */133 if (++count > 64)134 return false;135 136 return true;137}138 139static bool has_repeated_data(const u8 *sample, size_t len)140{141 size_t s = len / 2;142 143 return (!memcmp(&sample[0], &sample[s], s));144}145 146static int cmp_bkt(const void *_a, const void *_b)147{148 const struct bucket *a = _a, *b = _b;149 150 /* Reverse sort. */151 if (a->count > b->count)152 return -1;153 154 return 1;155}156 157/*158 * TODO:159 * Support other iter types, if required.160 * Only ITER_XARRAY is supported for now.161 */162static int collect_sample(const struct iov_iter *iter, ssize_t max, u8 *sample)163{164 struct folio *folios[16], *folio;165 unsigned int nr, i, j, npages;166 loff_t start = iter->xarray_start + iter->iov_offset;167 pgoff_t last, index = start / PAGE_SIZE;168 size_t len, off, foff;169 void *p;170 int s = 0;171 172 last = (start + max - 1) / PAGE_SIZE;173 do {174 nr = xa_extract(iter->xarray, (void **)folios, index, last, ARRAY_SIZE(folios),175 XA_PRESENT);176 if (nr == 0)177 return -EIO;178 179 for (i = 0; i < nr; i++) {180 folio = folios[i];181 npages = folio_nr_pages(folio);182 foff = start - folio_pos(folio);183 off = foff % PAGE_SIZE;184 185 for (j = foff / PAGE_SIZE; j < npages; j++) {186 size_t len2;187 188 len = min_t(size_t, max, PAGE_SIZE - off);189 len2 = min_t(size_t, len, SZ_2K);190 191 p = kmap_local_page(folio_page(folio, j));192 memcpy(&sample[s], p, len2);193 kunmap_local(p);194 195 s += len2;196 197 if (len2 < SZ_2K || s >= max - SZ_2K)198 return s;199 200 max -= len;201 if (max <= 0)202 return s;203 204 start += len;205 off = 0;206 index++;207 }208 }209 } while (nr == ARRAY_SIZE(folios));210 211 return s;212}213 214/**215 * is_compressible() - Determines if a chunk of data is compressible.216 * @data: Iterator containing uncompressed data.217 *218 * Return: true if @data is compressible, false otherwise.219 *220 * Tests shows that this function is quite reliable in predicting data compressibility,221 * matching close to 1:1 with the behaviour of LZ77 compression success and failures.222 */223static bool is_compressible(const struct iov_iter *data)224{225 const size_t read_size = SZ_2K, bkt_size = 256, max = SZ_4M;226 struct bucket *bkt = NULL;227 size_t len;228 u8 *sample;229 bool ret = false;230 int i;231 232 /* Preventive double check -- already checked in should_compress(). */233 len = iov_iter_count(data);234 if (unlikely(len < read_size))235 return ret;236 237 if (len - read_size > max)238 len = max;239 240 sample = kvzalloc(len, GFP_KERNEL);241 if (!sample) {242 WARN_ON_ONCE(1);243 244 return ret;245 }246 247 /* Sample 2K bytes per page of the uncompressed data. */248 i = collect_sample(data, len, sample);249 if (i <= 0) {250 WARN_ON_ONCE(1);251 252 goto out;253 }254 255 len = i;256 ret = true;257 258 if (has_repeated_data(sample, len))259 goto out;260 261 bkt = kcalloc(bkt_size, sizeof(*bkt), GFP_KERNEL);262 if (!bkt) {263 WARN_ON_ONCE(1);264 ret = false;265 266 goto out;267 }268 269 for (i = 0; i < len; i++)270 bkt[sample[i]].count++;271 272 if (is_mostly_ascii(bkt))273 goto out;274 275 /* Sort in descending order */276 sort(bkt, bkt_size, sizeof(*bkt), cmp_bkt, NULL);277 278 i = calc_byte_distribution(bkt, len);279 if (i != BYTE_DIST_MAYBE) {280 ret = !!i;281 282 goto out;283 }284 285 ret = has_low_entropy(bkt, len);286out:287 kvfree(sample);288 kfree(bkt);289 290 return ret;291}292 293bool should_compress(const struct cifs_tcon *tcon, const struct smb_rqst *rq)294{295 const struct smb2_hdr *shdr = rq->rq_iov->iov_base;296 297 if (unlikely(!tcon || !tcon->ses || !tcon->ses->server))298 return false;299 300 if (!tcon->ses->server->compression.enabled)301 return false;302 303 if (!(tcon->share_flags & SMB2_SHAREFLAG_COMPRESS_DATA))304 return false;305 306 if (shdr->Command == SMB2_WRITE) {307 const struct smb2_write_req *wreq = rq->rq_iov->iov_base;308 309 if (le32_to_cpu(wreq->Length) < SMB_COMPRESS_MIN_LEN)310 return false;311 312 return is_compressible(&rq->rq_iter);313 }314 315 return (shdr->Command == SMB2_READ);316}317 318int smb_compress(struct TCP_Server_Info *server, struct smb_rqst *rq, compress_send_fn send_fn)319{320 struct iov_iter iter;321 u32 slen, dlen;322 void *src, *dst = NULL;323 int ret;324 325 if (!server || !rq || !rq->rq_iov || !rq->rq_iov->iov_base)326 return -EINVAL;327 328 if (rq->rq_iov->iov_len != sizeof(struct smb2_write_req))329 return -EINVAL;330 331 slen = iov_iter_count(&rq->rq_iter);332 src = kvzalloc(slen, GFP_KERNEL);333 if (!src) {334 ret = -ENOMEM;335 goto err_free;336 }337 338 /* Keep the original iter intact. */339 iter = rq->rq_iter;340 341 if (!copy_from_iter_full(src, slen, &iter)) {342 ret = -EIO;343 goto err_free;344 }345 346 /*347 * This is just overprovisioning, as the algorithm will error out if @dst reaches 7/8348 * of @slen.349 */350 dlen = slen;351 dst = kvzalloc(dlen, GFP_KERNEL);352 if (!dst) {353 ret = -ENOMEM;354 goto err_free;355 }356 357 ret = lz77_compress(src, slen, dst, &dlen);358 if (!ret) {359 struct smb2_compression_hdr hdr = { 0 };360 struct smb_rqst comp_rq = { .rq_nvec = 3, };361 struct kvec iov[3];362 363 hdr.ProtocolId = SMB2_COMPRESSION_TRANSFORM_ID;364 hdr.OriginalCompressedSegmentSize = cpu_to_le32(slen);365 hdr.CompressionAlgorithm = SMB3_COMPRESS_LZ77;366 hdr.Flags = SMB2_COMPRESSION_FLAG_NONE;367 hdr.Offset = cpu_to_le32(rq->rq_iov[0].iov_len);368 369 iov[0].iov_base = &hdr;370 iov[0].iov_len = sizeof(hdr);371 iov[1] = rq->rq_iov[0];372 iov[2].iov_base = dst;373 iov[2].iov_len = dlen;374 375 comp_rq.rq_iov = iov;376 377 ret = send_fn(server, 1, &comp_rq);378 } else if (ret == -EMSGSIZE || dlen >= slen) {379 ret = send_fn(server, 1, rq);380 }381err_free:382 kvfree(dst);383 kvfree(src);384 385 return ret;386}387