1 // SPDX-License-Identifier: GPL-2.0-only 2 /* 3 * Copyright (C) 2024, SUSE LLC 4 * 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 algorithms 14 */ 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 removing 32 * 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 43 struct 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 to 53 * 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 a 57 * possibility of compression, but compressing, or even further analysing, it would waste so much 58 * 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 up 61 * with uncertainty, just stay on the safe side and call it uncompressible. 62 */ 63 static 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 0 83 #define BYTE_DIST_GOOD 1 84 #define BYTE_DIST_MAYBE 2 85 /** 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 of 92 * the bytes (e.g. random or encrypted data). 93 * BYTE_DIST_GOOD: High probability (normal (Gaussian) distribution) of the data being 94 * 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 */ 98 static 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 125 static 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 139 static 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 146 static 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 */ 162 static 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 */ 223 static 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); 286 out: 287 kvfree(sample); 288 kfree(bkt); 289 290 return ret; 291 } 292 293 bool 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 318 int 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/8 348 * 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 } 381 err_free: 382 kvfree(dst); 383 kvfree(src); 384 385 return ret; 386 } 387