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