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
z_erofs_load_lz4_config(struct super_block * sb,struct erofs_super_block * dsb,void * data,int size)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 */
z_erofs_lz4_prepare_dstpages(struct z_erofs_decompress_req * rq,struct page ** pagepool)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
z_erofs_lz4_handle_overlap(const struct z_erofs_decompress_req * rq,void * inpage,void * out,unsigned int * inputmargin,int * maptype,bool may_inplace)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 */
z_erofs_fixup_insize(struct z_erofs_decompress_req * rq,const char * padbuf,unsigned int padbufsize)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
__z_erofs_lz4_decompress(struct z_erofs_decompress_req * rq,u8 * dst)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
z_erofs_lz4_decompress(struct z_erofs_decompress_req * rq,struct page ** pagepool)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
z_erofs_transform_plain(struct z_erofs_decompress_req * rq,struct page ** pagepool)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
z_erofs_stream_switch_bufs(struct z_erofs_stream_dctx * dctx,void ** dst,void ** src,struct page ** pgpl)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
z_erofs_parse_cfgs(struct super_block * sb,struct erofs_super_block * dsb)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
z_erofs_init_decompressor(void)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
z_erofs_exit_decompressor(void)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