1 // SPDX-License-Identifier: GPL-2.0-only 2 /* 3 * Copyright (C) 2019 HUAWEI, Inc. 4 * https://www.huawei.com/ 5 * Copyright (C) 2024 Alibaba Cloud 6 */ 7 #include "compress.h" 8 #include <linux/lz4.h> 9 10 #define LZ4_MAX_DISTANCE_PAGES (DIV_ROUND_UP(LZ4_DISTANCE_MAX, PAGE_SIZE) + 1) 11 12 static int z_erofs_load_lz4_config(struct super_block *sb, 13 struct erofs_super_block *dsb, void *data, int size) 14 { 15 struct erofs_sb_info *sbi = EROFS_SB(sb); 16 struct z_erofs_lz4_cfgs *lz4 = data; 17 u16 distance; 18 19 if (lz4) { 20 if (size < sizeof(struct z_erofs_lz4_cfgs)) { 21 erofs_err(sb, "invalid lz4 cfgs, size=%u", size); 22 return -EINVAL; 23 } 24 distance = le16_to_cpu(lz4->max_distance); 25 26 sbi->lz4.max_pclusterblks = le16_to_cpu(lz4->max_pclusterblks); 27 if (!sbi->lz4.max_pclusterblks) { 28 sbi->lz4.max_pclusterblks = 1; /* reserved case */ 29 } else if (sbi->lz4.max_pclusterblks > 30 erofs_blknr(sb, Z_EROFS_PCLUSTER_MAX_SIZE)) { 31 erofs_err(sb, "too large lz4 pclusterblks %u", 32 sbi->lz4.max_pclusterblks); 33 return -EINVAL; 34 } 35 } else { 36 distance = le16_to_cpu(dsb->u1.lz4_max_distance); 37 if (!distance && !erofs_sb_has_lz4_0padding(sbi)) 38 return 0; 39 sbi->lz4.max_pclusterblks = 1; 40 sbi->available_compr_algs = 1 << Z_EROFS_COMPRESSION_LZ4; 41 } 42 43 sbi->lz4.max_distance_pages = distance ? 44 DIV_ROUND_UP(distance, PAGE_SIZE) + 1 : 45 LZ4_MAX_DISTANCE_PAGES; 46 return z_erofs_gbuf_growsize(sbi->lz4.max_pclusterblks); 47 } 48 49 /* 50 * Fill all gaps with bounce pages if it's a sparse page list. Also check if 51 * all physical pages are consecutive, which can be seen for moderate CR. 52 */ 53 static int z_erofs_lz4_prepare_dstpages(struct z_erofs_decompress_req *rq, 54 struct page **pagepool) 55 { 56 struct page *availables[LZ4_MAX_DISTANCE_PAGES] = { NULL }; 57 unsigned long bounced[DIV_ROUND_UP(LZ4_MAX_DISTANCE_PAGES, 58 BITS_PER_LONG)] = { 0 }; 59 unsigned int lz4_max_distance_pages = 60 EROFS_SB(rq->sb)->lz4.max_distance_pages; 61 void *kaddr = NULL; 62 unsigned int i, j, top; 63 64 top = 0; 65 for (i = j = 0; i < rq->outpages; ++i, ++j) { 66 struct page *const page = rq->out[i]; 67 struct page *victim; 68 69 if (j >= lz4_max_distance_pages) 70 j = 0; 71 72 /* 'valid' bounced can only be tested after a complete round */ 73 if (!rq->fillgaps && test_bit(j, bounced)) { 74 DBG_BUGON(i < lz4_max_distance_pages); 75 DBG_BUGON(top >= lz4_max_distance_pages); 76 availables[top++] = rq->out[i - lz4_max_distance_pages]; 77 } 78 79 if (page) { 80 __clear_bit(j, bounced); 81 if (!PageHighMem(page)) { 82 if (!i) { 83 kaddr = page_address(page); 84 continue; 85 } 86 if (kaddr && 87 kaddr + PAGE_SIZE == page_address(page)) { 88 kaddr += PAGE_SIZE; 89 continue; 90 } 91 } 92 kaddr = NULL; 93 continue; 94 } 95 kaddr = NULL; 96 __set_bit(j, bounced); 97 98 if (top) { 99 victim = availables[--top]; 100 } else { 101 victim = __erofs_allocpage(pagepool, rq->gfp, true); 102 if (!victim) 103 return -ENOMEM; 104 set_page_private(victim, Z_EROFS_SHORTLIVED_PAGE); 105 } 106 rq->out[i] = victim; 107 } 108 return kaddr ? 1 : 0; 109 } 110 111 static void *z_erofs_lz4_handle_overlap(const struct z_erofs_decompress_req *rq, 112 void *inpage, void *out, unsigned int *inputmargin, 113 int *maptype, bool may_inplace) 114 { 115 unsigned int oend, omargin, cnt, i; 116 struct page **in; 117 void *src; 118 119 /* 120 * If in-place I/O isn't used, for example, the bounce compressed cache 121 * can hold data for incomplete read requests. Just map the compressed 122 * buffer as well and decompress directly. 123 */ 124 if (!rq->inplace_io) { 125 if (rq->inpages <= 1) { 126 *maptype = 0; 127 return inpage; 128 } 129 kunmap_local(inpage); 130 src = erofs_vm_map_ram(rq->in, rq->inpages); 131 if (!src) 132 return ERR_PTR(-ENOMEM); 133 *maptype = 1; 134 return src; 135 } 136 /* 137 * Then, deal with in-place I/Os. The reasons why in-place I/O is useful 138 * are: (1) It minimizes memory footprint during the I/O submission, 139 * which is useful for slow storage (including network devices and 140 * low-end HDDs/eMMCs) but with a lot inflight I/Os; (2) If in-place 141 * decompression can also be applied, it will reuse the unique buffer so 142 * that no extra CPU D-cache is polluted with temporary compressed data 143 * for extreme performance. 144 */ 145 oend = rq->pageofs_out + rq->outputsize; 146 omargin = PAGE_ALIGN(oend) - oend; 147 if (!rq->partial_decoding && may_inplace && 148 omargin >= LZ4_DECOMPRESS_INPLACE_MARGIN(rq->inputsize)) { 149 for (i = 0; i < rq->inpages; ++i) 150 if (rq->out[rq->outpages - rq->inpages + i] != 151 rq->in[i]) 152 break; 153 if (i >= rq->inpages) { 154 kunmap_local(inpage); 155 *maptype = 3; 156 return out + ((rq->outpages - rq->inpages) << PAGE_SHIFT); 157 } 158 } 159 /* 160 * If in-place decompression can't be applied, copy compressed data that 161 * may potentially overlap during decompression to a per-CPU buffer. 162 */ 163 src = z_erofs_get_gbuf(rq->inpages); 164 if (!src) { 165 DBG_BUGON(1); 166 kunmap_local(inpage); 167 return ERR_PTR(-EFAULT); 168 } 169 170 for (i = 0, in = rq->in; i < rq->inputsize; i += cnt, ++in) { 171 cnt = min_t(u32, rq->inputsize - i, PAGE_SIZE - *inputmargin); 172 if (!inpage) 173 inpage = kmap_local_page(*in); 174 memcpy(src + i, inpage + *inputmargin, cnt); 175 kunmap_local(inpage); 176 inpage = NULL; 177 *inputmargin = 0; 178 } 179 *maptype = 2; 180 return src; 181 } 182 183 /* 184 * Get the exact on-disk size of the compressed data: 185 * - For LZ4, it should apply if the zero_padding feature is on (5.3+); 186 * - For others, zero_padding is enabled all the time. 187 */ 188 const char *z_erofs_fixup_insize(struct z_erofs_decompress_req *rq, 189 const char *padbuf, unsigned int padbufsize) 190 { 191 const char *padend; 192 193 padend = memchr_inv(padbuf, 0, padbufsize); 194 if (!padend) 195 return "compressed data start not found"; 196 rq->inputsize -= padend - padbuf; 197 rq->pageofs_in += padend - padbuf; 198 return NULL; 199 } 200 201 static const char *__z_erofs_lz4_decompress(struct z_erofs_decompress_req *rq, 202 u8 *dst) 203 { 204 bool may_inplace = false; 205 unsigned int inputmargin; 206 u8 *out, *headpage, *src; 207 const char *reason; 208 int ret, maptype; 209 210 headpage = kmap_local_page(*rq->in); 211 reason = z_erofs_fixup_insize(rq, headpage + rq->pageofs_in, 212 min_t(unsigned int, rq->inputsize, 213 rq->sb->s_blocksize - rq->pageofs_in)); 214 if (reason) { 215 kunmap_local(headpage); 216 return reason; 217 } 218 may_inplace = !((rq->pageofs_in + rq->inputsize) & 219 (rq->sb->s_blocksize - 1)); 220 221 inputmargin = rq->pageofs_in; 222 src = z_erofs_lz4_handle_overlap(rq, headpage, dst, &inputmargin, 223 &maptype, may_inplace); 224 if (IS_ERR(src)) 225 return ERR_CAST(src); 226 227 out = dst + rq->pageofs_out; 228 if (rq->partial_decoding) 229 ret = LZ4_decompress_safe_partial(src + inputmargin, out, 230 rq->inputsize, rq->outputsize, rq->outputsize); 231 else 232 ret = LZ4_decompress_safe(src + inputmargin, out, 233 rq->inputsize, rq->outputsize); 234 if (ret == rq->outputsize) 235 reason = NULL; 236 else if (ret < 0) 237 reason = "corrupted compressed data"; 238 else 239 reason = "unexpected end of stream"; 240 241 if (!maptype) { 242 kunmap_local(headpage); 243 } else if (maptype == 1) { 244 vm_unmap_ram(src, rq->inpages); 245 } else if (maptype == 2) { 246 z_erofs_put_gbuf(src); 247 } else if (maptype != 3) { 248 DBG_BUGON(1); 249 return ERR_PTR(-EFAULT); 250 } 251 return reason; 252 } 253 254 static const char *z_erofs_lz4_decompress(struct z_erofs_decompress_req *rq, 255 struct page **pagepool) 256 { 257 unsigned int dst_maptype; 258 const char *reason; 259 void *dst; 260 int ret; 261 262 /* one optimized fast path only for non bigpcluster cases yet */ 263 if (rq->inpages == 1 && rq->outpages == 1 && !rq->inplace_io) { 264 DBG_BUGON(!*rq->out); 265 dst = kmap_local_page(*rq->out); 266 dst_maptype = 0; 267 } else { 268 /* general decoding path which can be used for all cases */ 269 ret = z_erofs_lz4_prepare_dstpages(rq, pagepool); 270 if (ret < 0) 271 return ERR_PTR(ret); 272 if (ret > 0) { 273 dst = page_address(*rq->out); 274 dst_maptype = 1; 275 } else { 276 dst = erofs_vm_map_ram(rq->out, rq->outpages); 277 if (!dst) 278 return ERR_PTR(-ENOMEM); 279 dst_maptype = 2; 280 } 281 } 282 reason = __z_erofs_lz4_decompress(rq, dst); 283 if (!dst_maptype) 284 kunmap_local(dst); 285 else if (dst_maptype == 2) 286 vm_unmap_ram(dst, rq->outpages); 287 return reason; 288 } 289 290 static const char *z_erofs_transform_plain(struct z_erofs_decompress_req *rq, 291 struct page **pagepool) 292 { 293 const unsigned int nrpages_in = rq->inpages, nrpages_out = rq->outpages; 294 const unsigned int bs = rq->sb->s_blocksize; 295 unsigned int cur = 0, ni = 0, no, pi, po, insz, cnt; 296 u8 *kin; 297 298 if (rq->outputsize > rq->inputsize) 299 return ERR_PTR(-EOPNOTSUPP); 300 if (rq->alg == Z_EROFS_COMPRESSION_INTERLACED) { 301 cur = bs - (rq->pageofs_out & (bs - 1)); 302 DBG_BUGON(rq->pageofs_in & (bs - 1)); 303 pi = (rq->pageofs_in + rq->inputsize - cur) & ~PAGE_MASK; 304 cur = min(cur, rq->outputsize); 305 if (cur && rq->out[0]) { 306 kin = kmap_local_page(rq->in[nrpages_in - 1]); 307 if (rq->out[0] == rq->in[nrpages_in - 1]) 308 memmove(kin + rq->pageofs_out, kin + pi, cur); 309 else 310 memcpy_to_page(rq->out[0], rq->pageofs_out, 311 kin + pi, cur); 312 kunmap_local(kin); 313 } 314 rq->outputsize -= cur; 315 } 316 317 for (; rq->outputsize; rq->pageofs_in = 0, cur += insz, ni++) { 318 insz = min(PAGE_SIZE - rq->pageofs_in, rq->outputsize); 319 rq->outputsize -= insz; 320 if (!rq->in[ni]) 321 continue; 322 kin = kmap_local_page(rq->in[ni]); 323 pi = 0; 324 do { 325 no = (rq->pageofs_out + cur + pi) >> PAGE_SHIFT; 326 po = (rq->pageofs_out + cur + pi) & ~PAGE_MASK; 327 DBG_BUGON(no >= nrpages_out); 328 cnt = min(insz - pi, PAGE_SIZE - po); 329 if (rq->out[no] == rq->in[ni]) 330 memmove(kin + po, 331 kin + rq->pageofs_in + pi, cnt); 332 else if (rq->out[no]) 333 memcpy_to_page(rq->out[no], po, 334 kin + rq->pageofs_in + pi, cnt); 335 pi += cnt; 336 } while (pi < insz); 337 kunmap_local(kin); 338 } 339 DBG_BUGON(ni > nrpages_in); 340 return NULL; 341 } 342 343 const char *z_erofs_stream_switch_bufs(struct z_erofs_stream_dctx *dctx, 344 void **dst, void **src, struct page **pgpl) 345 { 346 struct z_erofs_decompress_req *rq = dctx->rq; 347 struct page **pgo, *tmppage; 348 unsigned int j; 349 350 if (!dctx->avail_out) { 351 if (++dctx->no >= rq->outpages || !rq->outputsize) 352 return "insufficient space for decompressed data"; 353 354 if (dctx->kout) 355 kunmap_local(dctx->kout); 356 dctx->avail_out = min(rq->outputsize, PAGE_SIZE - rq->pageofs_out); 357 rq->outputsize -= dctx->avail_out; 358 pgo = &rq->out[dctx->no]; 359 if (!*pgo && rq->fillgaps) { /* deduped */ 360 *pgo = erofs_allocpage(pgpl, rq->gfp); 361 if (!*pgo) { 362 dctx->kout = NULL; 363 return ERR_PTR(-ENOMEM); 364 } 365 set_page_private(*pgo, Z_EROFS_SHORTLIVED_PAGE); 366 } 367 if (*pgo) { 368 dctx->kout = kmap_local_page(*pgo); 369 *dst = dctx->kout + rq->pageofs_out; 370 } else { 371 *dst = dctx->kout = NULL; 372 } 373 rq->pageofs_out = 0; 374 } 375 376 if (dctx->inbuf_pos == dctx->inbuf_sz && rq->inputsize) { 377 if (++dctx->ni >= rq->inpages) 378 return "invalid compressed data"; 379 if (dctx->kout) /* unlike kmap(), take care of the orders */ 380 kunmap_local(dctx->kout); 381 kunmap_local(dctx->kin); 382 383 dctx->inbuf_sz = min_t(u32, rq->inputsize, PAGE_SIZE); 384 rq->inputsize -= dctx->inbuf_sz; 385 dctx->kin = kmap_local_page(rq->in[dctx->ni]); 386 *src = dctx->kin; 387 dctx->bounced = false; 388 if (dctx->kout) { 389 j = (u8 *)*dst - dctx->kout; 390 dctx->kout = kmap_local_page(rq->out[dctx->no]); 391 *dst = dctx->kout + j; 392 } 393 dctx->inbuf_pos = 0; 394 } 395 396 /* 397 * Handle overlapping: Use the given bounce buffer if the input data is 398 * under processing; Or utilize short-lived pages from the on-stack page 399 * pool, where pages are shared among the same request. Note that only 400 * a few inplace I/O pages need to be doubled. 401 */ 402 if (!dctx->bounced && rq->out[dctx->no] == rq->in[dctx->ni]) { 403 memcpy(dctx->bounce, *src, dctx->inbuf_sz); 404 *src = dctx->bounce; 405 dctx->bounced = true; 406 } 407 408 for (j = dctx->ni + 1; j < rq->inpages; ++j) { 409 if (rq->out[dctx->no] != rq->in[j]) 410 continue; 411 tmppage = erofs_allocpage(pgpl, rq->gfp); 412 if (!tmppage) 413 return ERR_PTR(-ENOMEM); 414 set_page_private(tmppage, Z_EROFS_SHORTLIVED_PAGE); 415 copy_highpage(tmppage, rq->in[j]); 416 rq->in[j] = tmppage; 417 } 418 return NULL; 419 } 420 421 const struct z_erofs_decompressor *z_erofs_decomp[] = { 422 [Z_EROFS_COMPRESSION_SHIFTED] = &(const struct z_erofs_decompressor) { 423 .decompress = z_erofs_transform_plain, 424 .name = "shifted" 425 }, 426 [Z_EROFS_COMPRESSION_INTERLACED] = &(const struct z_erofs_decompressor) { 427 .decompress = z_erofs_transform_plain, 428 .name = "interlaced" 429 }, 430 [Z_EROFS_COMPRESSION_LZ4] = &(const struct z_erofs_decompressor) { 431 .config = z_erofs_load_lz4_config, 432 .decompress = z_erofs_lz4_decompress, 433 .init = z_erofs_gbuf_init, 434 .exit = z_erofs_gbuf_exit, 435 .name = "lz4" 436 }, 437 #ifdef CONFIG_EROFS_FS_ZIP_LZMA 438 [Z_EROFS_COMPRESSION_LZMA] = &z_erofs_lzma_decomp, 439 #endif 440 #ifdef CONFIG_EROFS_FS_ZIP_DEFLATE 441 [Z_EROFS_COMPRESSION_DEFLATE] = &z_erofs_deflate_decomp, 442 #endif 443 #ifdef CONFIG_EROFS_FS_ZIP_ZSTD 444 [Z_EROFS_COMPRESSION_ZSTD] = &z_erofs_zstd_decomp, 445 #endif 446 }; 447 448 int z_erofs_parse_cfgs(struct super_block *sb, struct erofs_super_block *dsb) 449 { 450 struct erofs_sb_info *sbi = EROFS_SB(sb); 451 struct erofs_buf buf = __EROFS_BUF_INITIALIZER; 452 unsigned long algs, alg; 453 erofs_off_t offset; 454 int size, ret = 0; 455 456 if (!erofs_sb_has_compr_cfgs(sbi)) 457 return z_erofs_load_lz4_config(sb, dsb, NULL, 0); 458 459 algs = le16_to_cpu(dsb->u1.available_compr_algs); 460 sbi->available_compr_algs = algs; 461 if (algs & ~Z_EROFS_ALL_COMPR_ALGS) { 462 erofs_err(sb, "unidentified algorithms %lx, please upgrade kernel", 463 algs & ~Z_EROFS_ALL_COMPR_ALGS); 464 return -EOPNOTSUPP; 465 } 466 467 (void)erofs_init_metabuf(&buf, sb, false); 468 offset = EROFS_SUPER_OFFSET + sbi->sb_size; 469 for_each_set_bit(alg, &algs, Z_EROFS_COMPRESSION_MAX) { 470 const struct z_erofs_decompressor *dec = z_erofs_decomp[alg]; 471 void *data; 472 473 data = erofs_read_metadata(sb, &buf, &offset, &size); 474 if (IS_ERR(data)) { 475 ret = PTR_ERR(data); 476 break; 477 } 478 479 if (dec && dec->config) { 480 ret = dec->config(sb, dsb, data, size); 481 } else { 482 erofs_err(sb, "algorithm %ld isn't enabled on this kernel", 483 alg); 484 ret = -EOPNOTSUPP; 485 } 486 kfree(data); 487 if (ret) 488 break; 489 } 490 erofs_put_metabuf(&buf); 491 return ret; 492 } 493 494 int __init z_erofs_init_decompressor(void) 495 { 496 int i, err; 497 498 for (i = 0; i < Z_EROFS_COMPRESSION_MAX; ++i) { 499 err = z_erofs_decomp[i] ? z_erofs_decomp[i]->init() : 0; 500 if (err) { 501 while (i--) 502 if (z_erofs_decomp[i]) 503 z_erofs_decomp[i]->exit(); 504 return err; 505 } 506 } 507 return 0; 508 } 509 510 void z_erofs_exit_decompressor(void) 511 { 512 int i; 513 514 for (i = 0; i < Z_EROFS_COMPRESSION_MAX; ++i) 515 if (z_erofs_decomp[i]) 516 z_erofs_decomp[i]->exit(); 517 } 518