1 // SPDX-License-Identifier: GPL-2.0-only 2 /* 3 * Copyright (C) 2019 HUAWEI, Inc. 4 * https://www.huawei.com/ 5 */ 6 #include "compress.h" 7 #include <linux/lz4.h> 8 9 #ifndef LZ4_DISTANCE_MAX /* history window size */ 10 #define LZ4_DISTANCE_MAX 65535 /* set to maximum value by default */ 11 #endif 12 13 #define LZ4_MAX_DISTANCE_PAGES (DIV_ROUND_UP(LZ4_DISTANCE_MAX, PAGE_SIZE) + 1) 14 #ifndef LZ4_DECOMPRESS_INPLACE_MARGIN 15 #define LZ4_DECOMPRESS_INPLACE_MARGIN(srcsize) (((srcsize) >> 8) + 32) 16 #endif 17 18 struct z_erofs_lz4_decompress_ctx { 19 struct z_erofs_decompress_req *rq; 20 /* # of encoded, decoded pages */ 21 unsigned int inpages, outpages; 22 /* decoded block total length (used for in-place decompression) */ 23 unsigned int oend; 24 }; 25 26 static int z_erofs_load_lz4_config(struct super_block *sb, 27 struct erofs_super_block *dsb, void *data, int size) 28 { 29 struct erofs_sb_info *sbi = EROFS_SB(sb); 30 struct z_erofs_lz4_cfgs *lz4 = data; 31 u16 distance; 32 33 if (lz4) { 34 if (size < sizeof(struct z_erofs_lz4_cfgs)) { 35 erofs_err(sb, "invalid lz4 cfgs, size=%u", size); 36 return -EINVAL; 37 } 38 distance = le16_to_cpu(lz4->max_distance); 39 40 sbi->lz4.max_pclusterblks = le16_to_cpu(lz4->max_pclusterblks); 41 if (!sbi->lz4.max_pclusterblks) { 42 sbi->lz4.max_pclusterblks = 1; /* reserved case */ 43 } else if (sbi->lz4.max_pclusterblks > 44 erofs_blknr(sb, Z_EROFS_PCLUSTER_MAX_SIZE)) { 45 erofs_err(sb, "too large lz4 pclusterblks %u", 46 sbi->lz4.max_pclusterblks); 47 return -EINVAL; 48 } 49 } else { 50 distance = le16_to_cpu(dsb->u1.lz4_max_distance); 51 sbi->lz4.max_pclusterblks = 1; 52 } 53 54 sbi->lz4.max_distance_pages = distance ? 55 DIV_ROUND_UP(distance, PAGE_SIZE) + 1 : 56 LZ4_MAX_DISTANCE_PAGES; 57 return erofs_pcpubuf_growsize(sbi->lz4.max_pclusterblks); 58 } 59 60 /* 61 * Fill all gaps with bounce pages if it's a sparse page list. Also check if 62 * all physical pages are consecutive, which can be seen for moderate CR. 63 */ 64 static int z_erofs_lz4_prepare_dstpages(struct z_erofs_lz4_decompress_ctx *ctx, 65 struct page **pagepool) 66 { 67 struct z_erofs_decompress_req *rq = ctx->rq; 68 struct page *availables[LZ4_MAX_DISTANCE_PAGES] = { NULL }; 69 unsigned long bounced[DIV_ROUND_UP(LZ4_MAX_DISTANCE_PAGES, 70 BITS_PER_LONG)] = { 0 }; 71 unsigned int lz4_max_distance_pages = 72 EROFS_SB(rq->sb)->lz4.max_distance_pages; 73 void *kaddr = NULL; 74 unsigned int i, j, top; 75 76 top = 0; 77 for (i = j = 0; i < ctx->outpages; ++i, ++j) { 78 struct page *const page = rq->out[i]; 79 struct page *victim; 80 81 if (j >= lz4_max_distance_pages) 82 j = 0; 83 84 /* 'valid' bounced can only be tested after a complete round */ 85 if (!rq->fillgaps && test_bit(j, bounced)) { 86 DBG_BUGON(i < lz4_max_distance_pages); 87 DBG_BUGON(top >= lz4_max_distance_pages); 88 availables[top++] = rq->out[i - lz4_max_distance_pages]; 89 } 90 91 if (page) { 92 __clear_bit(j, bounced); 93 if (!PageHighMem(page)) { 94 if (!i) { 95 kaddr = page_address(page); 96 continue; 97 } 98 if (kaddr && 99 kaddr + PAGE_SIZE == page_address(page)) { 100 kaddr += PAGE_SIZE; 101 continue; 102 } 103 } 104 kaddr = NULL; 105 continue; 106 } 107 kaddr = NULL; 108 __set_bit(j, bounced); 109 110 if (top) { 111 victim = availables[--top]; 112 get_page(victim); 113 } else { 114 victim = erofs_allocpage(pagepool, 115 GFP_KERNEL | __GFP_NOFAIL); 116 set_page_private(victim, Z_EROFS_SHORTLIVED_PAGE); 117 } 118 rq->out[i] = victim; 119 } 120 return kaddr ? 1 : 0; 121 } 122 123 static void *z_erofs_lz4_handle_overlap(struct z_erofs_lz4_decompress_ctx *ctx, 124 void *inpage, void *out, unsigned int *inputmargin, 125 int *maptype, bool may_inplace) 126 { 127 struct z_erofs_decompress_req *rq = ctx->rq; 128 unsigned int omargin, total, i; 129 struct page **in; 130 void *src, *tmp; 131 132 if (rq->inplace_io) { 133 omargin = PAGE_ALIGN(ctx->oend) - ctx->oend; 134 if (rq->partial_decoding || !may_inplace || 135 omargin < LZ4_DECOMPRESS_INPLACE_MARGIN(rq->inputsize)) 136 goto docopy; 137 138 for (i = 0; i < ctx->inpages; ++i) 139 if (rq->out[ctx->outpages - ctx->inpages + i] != 140 rq->in[i]) 141 goto docopy; 142 kunmap_local(inpage); 143 *maptype = 3; 144 return out + ((ctx->outpages - ctx->inpages) << PAGE_SHIFT); 145 } 146 147 if (ctx->inpages <= 1) { 148 *maptype = 0; 149 return inpage; 150 } 151 kunmap_local(inpage); 152 src = erofs_vm_map_ram(rq->in, ctx->inpages); 153 if (!src) 154 return ERR_PTR(-ENOMEM); 155 *maptype = 1; 156 return src; 157 158 docopy: 159 /* Or copy compressed data which can be overlapped to per-CPU buffer */ 160 in = rq->in; 161 src = erofs_get_pcpubuf(ctx->inpages); 162 if (!src) { 163 DBG_BUGON(1); 164 kunmap_local(inpage); 165 return ERR_PTR(-EFAULT); 166 } 167 168 tmp = src; 169 total = rq->inputsize; 170 while (total) { 171 unsigned int page_copycnt = 172 min_t(unsigned int, total, PAGE_SIZE - *inputmargin); 173 174 if (!inpage) 175 inpage = kmap_local_page(*in); 176 memcpy(tmp, inpage + *inputmargin, page_copycnt); 177 kunmap_local(inpage); 178 inpage = NULL; 179 tmp += page_copycnt; 180 total -= page_copycnt; 181 ++in; 182 *inputmargin = 0; 183 } 184 *maptype = 2; 185 return src; 186 } 187 188 /* 189 * Get the exact inputsize with zero_padding feature. 190 * - For LZ4, it should work if zero_padding feature is on (5.3+); 191 * - For MicroLZMA, it'd be enabled all the time. 192 */ 193 int z_erofs_fixup_insize(struct z_erofs_decompress_req *rq, const char *padbuf, 194 unsigned int padbufsize) 195 { 196 const char *padend; 197 198 padend = memchr_inv(padbuf, 0, padbufsize); 199 if (!padend) 200 return -EFSCORRUPTED; 201 rq->inputsize -= padend - padbuf; 202 rq->pageofs_in += padend - padbuf; 203 return 0; 204 } 205 206 static int z_erofs_lz4_decompress_mem(struct z_erofs_lz4_decompress_ctx *ctx, 207 u8 *dst) 208 { 209 struct z_erofs_decompress_req *rq = ctx->rq; 210 bool support_0padding = false, may_inplace = false; 211 unsigned int inputmargin; 212 u8 *out, *headpage, *src; 213 int ret, maptype; 214 215 DBG_BUGON(*rq->in == NULL); 216 headpage = kmap_local_page(*rq->in); 217 218 /* LZ4 decompression inplace is only safe if zero_padding is enabled */ 219 if (erofs_sb_has_zero_padding(EROFS_SB(rq->sb))) { 220 support_0padding = true; 221 ret = z_erofs_fixup_insize(rq, headpage + rq->pageofs_in, 222 min_t(unsigned int, rq->inputsize, 223 rq->sb->s_blocksize - rq->pageofs_in)); 224 if (ret) { 225 kunmap_local(headpage); 226 return ret; 227 } 228 may_inplace = !((rq->pageofs_in + rq->inputsize) & 229 (rq->sb->s_blocksize - 1)); 230 } 231 232 inputmargin = rq->pageofs_in; 233 src = z_erofs_lz4_handle_overlap(ctx, headpage, dst, &inputmargin, 234 &maptype, may_inplace); 235 if (IS_ERR(src)) 236 return PTR_ERR(src); 237 238 out = dst + rq->pageofs_out; 239 /* legacy format could compress extra data in a pcluster. */ 240 if (rq->partial_decoding || !support_0padding) 241 ret = LZ4_decompress_safe_partial(src + inputmargin, out, 242 rq->inputsize, rq->outputsize, rq->outputsize); 243 else 244 ret = LZ4_decompress_safe(src + inputmargin, out, 245 rq->inputsize, rq->outputsize); 246 247 if (ret != rq->outputsize) { 248 erofs_err(rq->sb, "failed to decompress %d in[%u, %u] out[%u]", 249 ret, rq->inputsize, inputmargin, rq->outputsize); 250 if (ret >= 0) 251 memset(out + ret, 0, rq->outputsize - ret); 252 ret = -EFSCORRUPTED; 253 } else { 254 ret = 0; 255 } 256 257 if (maptype == 0) { 258 kunmap_local(headpage); 259 } else if (maptype == 1) { 260 vm_unmap_ram(src, ctx->inpages); 261 } else if (maptype == 2) { 262 erofs_put_pcpubuf(src); 263 } else if (maptype != 3) { 264 DBG_BUGON(1); 265 return -EFAULT; 266 } 267 return ret; 268 } 269 270 static int z_erofs_lz4_decompress(struct z_erofs_decompress_req *rq, 271 struct page **pagepool) 272 { 273 struct z_erofs_lz4_decompress_ctx ctx; 274 unsigned int dst_maptype; 275 void *dst; 276 int ret; 277 278 ctx.rq = rq; 279 ctx.oend = rq->pageofs_out + rq->outputsize; 280 ctx.outpages = PAGE_ALIGN(ctx.oend) >> PAGE_SHIFT; 281 ctx.inpages = PAGE_ALIGN(rq->inputsize) >> PAGE_SHIFT; 282 283 /* one optimized fast path only for non bigpcluster cases yet */ 284 if (ctx.inpages == 1 && ctx.outpages == 1 && !rq->inplace_io) { 285 DBG_BUGON(!*rq->out); 286 dst = kmap_local_page(*rq->out); 287 dst_maptype = 0; 288 goto dstmap_out; 289 } 290 291 /* general decoding path which can be used for all cases */ 292 ret = z_erofs_lz4_prepare_dstpages(&ctx, pagepool); 293 if (ret < 0) { 294 return ret; 295 } else if (ret > 0) { 296 dst = page_address(*rq->out); 297 dst_maptype = 1; 298 } else { 299 dst = erofs_vm_map_ram(rq->out, ctx.outpages); 300 if (!dst) 301 return -ENOMEM; 302 dst_maptype = 2; 303 } 304 305 dstmap_out: 306 ret = z_erofs_lz4_decompress_mem(&ctx, dst); 307 if (!dst_maptype) 308 kunmap_local(dst); 309 else if (dst_maptype == 2) 310 vm_unmap_ram(dst, ctx.outpages); 311 return ret; 312 } 313 314 static int z_erofs_transform_plain(struct z_erofs_decompress_req *rq, 315 struct page **pagepool) 316 { 317 const unsigned int nrpages_in = 318 PAGE_ALIGN(rq->pageofs_in + rq->inputsize) >> PAGE_SHIFT; 319 const unsigned int nrpages_out = 320 PAGE_ALIGN(rq->pageofs_out + rq->outputsize) >> PAGE_SHIFT; 321 const unsigned int bs = rq->sb->s_blocksize; 322 unsigned int cur = 0, ni = 0, no, pi, po, insz, cnt; 323 u8 *kin; 324 325 DBG_BUGON(rq->outputsize > rq->inputsize); 326 if (rq->alg == Z_EROFS_COMPRESSION_INTERLACED) { 327 cur = bs - (rq->pageofs_out & (bs - 1)); 328 pi = (rq->pageofs_in + rq->inputsize - cur) & ~PAGE_MASK; 329 cur = min(cur, rq->outputsize); 330 if (cur && rq->out[0]) { 331 kin = kmap_local_page(rq->in[nrpages_in - 1]); 332 if (rq->out[0] == rq->in[nrpages_in - 1]) { 333 memmove(kin + rq->pageofs_out, kin + pi, cur); 334 flush_dcache_page(rq->out[0]); 335 } else { 336 memcpy_to_page(rq->out[0], rq->pageofs_out, 337 kin + pi, cur); 338 } 339 kunmap_local(kin); 340 } 341 rq->outputsize -= cur; 342 } 343 344 for (; rq->outputsize; rq->pageofs_in = 0, cur += PAGE_SIZE, ni++) { 345 insz = min(PAGE_SIZE - rq->pageofs_in, rq->outputsize); 346 rq->outputsize -= insz; 347 if (!rq->in[ni]) 348 continue; 349 kin = kmap_local_page(rq->in[ni]); 350 pi = 0; 351 do { 352 no = (rq->pageofs_out + cur + pi) >> PAGE_SHIFT; 353 po = (rq->pageofs_out + cur + pi) & ~PAGE_MASK; 354 DBG_BUGON(no >= nrpages_out); 355 cnt = min(insz - pi, PAGE_SIZE - po); 356 if (rq->out[no] == rq->in[ni]) { 357 memmove(kin + po, 358 kin + rq->pageofs_in + pi, cnt); 359 flush_dcache_page(rq->out[no]); 360 } else if (rq->out[no]) { 361 memcpy_to_page(rq->out[no], po, 362 kin + rq->pageofs_in + pi, cnt); 363 } 364 pi += cnt; 365 } while (pi < insz); 366 kunmap_local(kin); 367 } 368 DBG_BUGON(ni > nrpages_in); 369 return 0; 370 } 371 372 const struct z_erofs_decompressor erofs_decompressors[] = { 373 [Z_EROFS_COMPRESSION_SHIFTED] = { 374 .decompress = z_erofs_transform_plain, 375 .name = "shifted" 376 }, 377 [Z_EROFS_COMPRESSION_INTERLACED] = { 378 .decompress = z_erofs_transform_plain, 379 .name = "interlaced" 380 }, 381 [Z_EROFS_COMPRESSION_LZ4] = { 382 .config = z_erofs_load_lz4_config, 383 .decompress = z_erofs_lz4_decompress, 384 .name = "lz4" 385 }, 386 #ifdef CONFIG_EROFS_FS_ZIP_LZMA 387 [Z_EROFS_COMPRESSION_LZMA] = { 388 .config = z_erofs_load_lzma_config, 389 .decompress = z_erofs_lzma_decompress, 390 .name = "lzma" 391 }, 392 #endif 393 #ifdef CONFIG_EROFS_FS_ZIP_DEFLATE 394 [Z_EROFS_COMPRESSION_DEFLATE] = { 395 .config = z_erofs_load_deflate_config, 396 .decompress = z_erofs_deflate_decompress, 397 .name = "deflate" 398 }, 399 #endif 400 }; 401 402 int z_erofs_parse_cfgs(struct super_block *sb, struct erofs_super_block *dsb) 403 { 404 struct erofs_sb_info *sbi = EROFS_SB(sb); 405 struct erofs_buf buf = __EROFS_BUF_INITIALIZER; 406 unsigned int algs, alg; 407 erofs_off_t offset; 408 int size, ret = 0; 409 410 if (!erofs_sb_has_compr_cfgs(sbi)) { 411 sbi->available_compr_algs = Z_EROFS_COMPRESSION_LZ4; 412 return z_erofs_load_lz4_config(sb, dsb, NULL, 0); 413 } 414 415 sbi->available_compr_algs = le16_to_cpu(dsb->u1.available_compr_algs); 416 if (sbi->available_compr_algs & ~Z_EROFS_ALL_COMPR_ALGS) { 417 erofs_err(sb, "unidentified algorithms %x, please upgrade kernel", 418 sbi->available_compr_algs & ~Z_EROFS_ALL_COMPR_ALGS); 419 return -EOPNOTSUPP; 420 } 421 422 erofs_init_metabuf(&buf, sb); 423 offset = EROFS_SUPER_OFFSET + sbi->sb_size; 424 alg = 0; 425 for (algs = sbi->available_compr_algs; algs; algs >>= 1, ++alg) { 426 void *data; 427 428 if (!(algs & 1)) 429 continue; 430 431 data = erofs_read_metadata(sb, &buf, &offset, &size); 432 if (IS_ERR(data)) { 433 ret = PTR_ERR(data); 434 break; 435 } 436 437 if (alg >= ARRAY_SIZE(erofs_decompressors) || 438 !erofs_decompressors[alg].config) { 439 erofs_err(sb, "algorithm %d isn't enabled on this kernel", 440 alg); 441 ret = -EOPNOTSUPP; 442 } else { 443 ret = erofs_decompressors[alg].config(sb, 444 dsb, data, size); 445 } 446 447 kfree(data); 448 if (ret) 449 break; 450 } 451 erofs_put_metabuf(&buf); 452 return ret; 453 } 454