xref: /linux/fs/erofs/decompressor.c (revision 22c55fb9eb92395d999b8404d73e58540d11bdd8) 
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(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, total, i;
113 	struct page **in;
114 	void *src, *tmp;
115 
116 	if (rq->inplace_io) {
117 		oend = rq->pageofs_out + rq->outputsize;
118 		omargin = PAGE_ALIGN(oend) - oend;
119 		if (rq->partial_decoding || !may_inplace ||
120 		    omargin < LZ4_DECOMPRESS_INPLACE_MARGIN(rq->inputsize))
121 			goto docopy;
122 
123 		for (i = 0; i < rq->inpages; ++i)
124 			if (rq->out[rq->outpages - rq->inpages + i] !=
125 			    rq->in[i])
126 				goto docopy;
127 		kunmap_local(inpage);
128 		*maptype = 3;
129 		return out + ((rq->outpages - rq->inpages) << PAGE_SHIFT);
130 	}
131 
132 	if (rq->inpages <= 1) {
133 		*maptype = 0;
134 		return inpage;
135 	}
136 	kunmap_local(inpage);
137 	src = erofs_vm_map_ram(rq->in, rq->inpages);
138 	if (!src)
139 		return ERR_PTR(-ENOMEM);
140 	*maptype = 1;
141 	return src;
142 
143 docopy:
144 	/* Or copy compressed data which can be overlapped to per-CPU buffer */
145 	in = rq->in;
146 	src = z_erofs_get_gbuf(rq->inpages);
147 	if (!src) {
148 		DBG_BUGON(1);
149 		kunmap_local(inpage);
150 		return ERR_PTR(-EFAULT);
151 	}
152 
153 	tmp = src;
154 	total = rq->inputsize;
155 	while (total) {
156 		unsigned int page_copycnt =
157 			min_t(unsigned int, total, PAGE_SIZE - *inputmargin);
158 
159 		if (!inpage)
160 			inpage = kmap_local_page(*in);
161 		memcpy(tmp, inpage + *inputmargin, page_copycnt);
162 		kunmap_local(inpage);
163 		inpage = NULL;
164 		tmp += page_copycnt;
165 		total -= page_copycnt;
166 		++in;
167 		*inputmargin = 0;
168 	}
169 	*maptype = 2;
170 	return src;
171 }
172 
173 /*
174  * Get the exact inputsize with zero_padding feature.
175  *  - For LZ4, it should work if zero_padding feature is on (5.3+);
176  *  - For MicroLZMA, it'd be enabled all the time.
177  */
178 int z_erofs_fixup_insize(struct z_erofs_decompress_req *rq, const char *padbuf,
179 			 unsigned int padbufsize)
180 {
181 	const char *padend;
182 
183 	padend = memchr_inv(padbuf, 0, padbufsize);
184 	if (!padend)
185 		return -EFSCORRUPTED;
186 	rq->inputsize -= padend - padbuf;
187 	rq->pageofs_in += padend - padbuf;
188 	return 0;
189 }
190 
191 static int z_erofs_lz4_decompress_mem(struct z_erofs_decompress_req *rq, u8 *dst)
192 {
193 	bool support_0padding = false, may_inplace = false;
194 	unsigned int inputmargin;
195 	u8 *out, *headpage, *src;
196 	int ret, maptype;
197 
198 	DBG_BUGON(*rq->in == NULL);
199 	headpage = kmap_local_page(*rq->in);
200 
201 	/* LZ4 decompression inplace is only safe if zero_padding is enabled */
202 	if (erofs_sb_has_zero_padding(EROFS_SB(rq->sb))) {
203 		support_0padding = true;
204 		ret = z_erofs_fixup_insize(rq, headpage + rq->pageofs_in,
205 				min_t(unsigned int, rq->inputsize,
206 				      rq->sb->s_blocksize - rq->pageofs_in));
207 		if (ret) {
208 			kunmap_local(headpage);
209 			return ret;
210 		}
211 		may_inplace = !((rq->pageofs_in + rq->inputsize) &
212 				(rq->sb->s_blocksize - 1));
213 	}
214 
215 	inputmargin = rq->pageofs_in;
216 	src = z_erofs_lz4_handle_overlap(rq, headpage, dst, &inputmargin,
217 					 &maptype, may_inplace);
218 	if (IS_ERR(src))
219 		return PTR_ERR(src);
220 
221 	out = dst + rq->pageofs_out;
222 	/* legacy format could compress extra data in a pcluster. */
223 	if (rq->partial_decoding || !support_0padding)
224 		ret = LZ4_decompress_safe_partial(src + inputmargin, out,
225 				rq->inputsize, rq->outputsize, rq->outputsize);
226 	else
227 		ret = LZ4_decompress_safe(src + inputmargin, out,
228 					  rq->inputsize, rq->outputsize);
229 
230 	if (ret != rq->outputsize) {
231 		erofs_err(rq->sb, "failed to decompress %d in[%u, %u] out[%u]",
232 			  ret, rq->inputsize, inputmargin, rq->outputsize);
233 		if (ret >= 0)
234 			memset(out + ret, 0, rq->outputsize - ret);
235 		ret = -EFSCORRUPTED;
236 	} else {
237 		ret = 0;
238 	}
239 
240 	if (maptype == 0) {
241 		kunmap_local(headpage);
242 	} else if (maptype == 1) {
243 		vm_unmap_ram(src, rq->inpages);
244 	} else if (maptype == 2) {
245 		z_erofs_put_gbuf(src);
246 	} else if (maptype != 3) {
247 		DBG_BUGON(1);
248 		return -EFAULT;
249 	}
250 	return ret;
251 }
252 
253 static int z_erofs_lz4_decompress(struct z_erofs_decompress_req *rq,
254 				  struct page **pagepool)
255 {
256 	unsigned int dst_maptype;
257 	void *dst;
258 	int ret;
259 
260 	/* one optimized fast path only for non bigpcluster cases yet */
261 	if (rq->inpages == 1 && rq->outpages == 1 && !rq->inplace_io) {
262 		DBG_BUGON(!*rq->out);
263 		dst = kmap_local_page(*rq->out);
264 		dst_maptype = 0;
265 	} else {
266 		/* general decoding path which can be used for all cases */
267 		ret = z_erofs_lz4_prepare_dstpages(rq, pagepool);
268 		if (ret < 0)
269 			return ret;
270 		if (ret > 0) {
271 			dst = page_address(*rq->out);
272 			dst_maptype = 1;
273 		} else {
274 			dst = erofs_vm_map_ram(rq->out, rq->outpages);
275 			if (!dst)
276 				return -ENOMEM;
277 			dst_maptype = 2;
278 		}
279 	}
280 	ret = z_erofs_lz4_decompress_mem(rq, dst);
281 	if (!dst_maptype)
282 		kunmap_local(dst);
283 	else if (dst_maptype == 2)
284 		vm_unmap_ram(dst, rq->outpages);
285 	return ret;
286 }
287 
288 static int z_erofs_transform_plain(struct z_erofs_decompress_req *rq,
289 				   struct page **pagepool)
290 {
291 	const unsigned int nrpages_in = rq->inpages, nrpages_out = rq->outpages;
292 	const unsigned int bs = rq->sb->s_blocksize;
293 	unsigned int cur = 0, ni = 0, no, pi, po, insz, cnt;
294 	u8 *kin;
295 
296 	if (rq->outputsize > rq->inputsize)
297 		return -EOPNOTSUPP;
298 	if (rq->alg == Z_EROFS_COMPRESSION_INTERLACED) {
299 		cur = bs - (rq->pageofs_out & (bs - 1));
300 		pi = (rq->pageofs_in + rq->inputsize - cur) & ~PAGE_MASK;
301 		cur = min(cur, rq->outputsize);
302 		if (cur && rq->out[0]) {
303 			kin = kmap_local_page(rq->in[nrpages_in - 1]);
304 			if (rq->out[0] == rq->in[nrpages_in - 1])
305 				memmove(kin + rq->pageofs_out, kin + pi, cur);
306 			else
307 				memcpy_to_page(rq->out[0], rq->pageofs_out,
308 					       kin + pi, cur);
309 			kunmap_local(kin);
310 		}
311 		rq->outputsize -= cur;
312 	}
313 
314 	for (; rq->outputsize; rq->pageofs_in = 0, cur += insz, ni++) {
315 		insz = min(PAGE_SIZE - rq->pageofs_in, rq->outputsize);
316 		rq->outputsize -= insz;
317 		if (!rq->in[ni])
318 			continue;
319 		kin = kmap_local_page(rq->in[ni]);
320 		pi = 0;
321 		do {
322 			no = (rq->pageofs_out + cur + pi) >> PAGE_SHIFT;
323 			po = (rq->pageofs_out + cur + pi) & ~PAGE_MASK;
324 			DBG_BUGON(no >= nrpages_out);
325 			cnt = min(insz - pi, PAGE_SIZE - po);
326 			if (rq->out[no] == rq->in[ni])
327 				memmove(kin + po,
328 					kin + rq->pageofs_in + pi, cnt);
329 			else if (rq->out[no])
330 				memcpy_to_page(rq->out[no], po,
331 					       kin + rq->pageofs_in + pi, cnt);
332 			pi += cnt;
333 		} while (pi < insz);
334 		kunmap_local(kin);
335 	}
336 	DBG_BUGON(ni > nrpages_in);
337 	return 0;
338 }
339 
340 int z_erofs_stream_switch_bufs(struct z_erofs_stream_dctx *dctx, void **dst,
341 			       void **src, struct page **pgpl)
342 {
343 	struct z_erofs_decompress_req *rq = dctx->rq;
344 	struct super_block *sb = rq->sb;
345 	struct page **pgo, *tmppage;
346 	unsigned int j;
347 
348 	if (!dctx->avail_out) {
349 		if (++dctx->no >= rq->outpages || !rq->outputsize) {
350 			erofs_err(sb, "insufficient space for decompressed data");
351 			return -EFSCORRUPTED;
352 		}
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 -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 			erofs_err(sb, "invalid compressed data");
379 			return -EFSCORRUPTED;
380 		}
381 		if (dctx->kout) /* unlike kmap(), take care of the orders */
382 			kunmap_local(dctx->kout);
383 		kunmap_local(dctx->kin);
384 
385 		dctx->inbuf_sz = min_t(u32, rq->inputsize, PAGE_SIZE);
386 		rq->inputsize -= dctx->inbuf_sz;
387 		dctx->kin = kmap_local_page(rq->in[dctx->ni]);
388 		*src = dctx->kin;
389 		dctx->bounced = false;
390 		if (dctx->kout) {
391 			j = (u8 *)*dst - dctx->kout;
392 			dctx->kout = kmap_local_page(rq->out[dctx->no]);
393 			*dst = dctx->kout + j;
394 		}
395 		dctx->inbuf_pos = 0;
396 	}
397 
398 	/*
399 	 * Handle overlapping: Use the given bounce buffer if the input data is
400 	 * under processing; Or utilize short-lived pages from the on-stack page
401 	 * pool, where pages are shared among the same request.  Note that only
402 	 * a few inplace I/O pages need to be doubled.
403 	 */
404 	if (!dctx->bounced && rq->out[dctx->no] == rq->in[dctx->ni]) {
405 		memcpy(dctx->bounce, *src, dctx->inbuf_sz);
406 		*src = dctx->bounce;
407 		dctx->bounced = true;
408 	}
409 
410 	for (j = dctx->ni + 1; j < rq->inpages; ++j) {
411 		if (rq->out[dctx->no] != rq->in[j])
412 			continue;
413 		tmppage = erofs_allocpage(pgpl, rq->gfp);
414 		if (!tmppage)
415 			return -ENOMEM;
416 		set_page_private(tmppage, Z_EROFS_SHORTLIVED_PAGE);
417 		copy_highpage(tmppage, rq->in[j]);
418 		rq->in[j] = tmppage;
419 	}
420 	return 0;
421 }
422 
423 const struct z_erofs_decompressor *z_erofs_decomp[] = {
424 	[Z_EROFS_COMPRESSION_SHIFTED] = &(const struct z_erofs_decompressor) {
425 		.decompress = z_erofs_transform_plain,
426 		.name = "shifted"
427 	},
428 	[Z_EROFS_COMPRESSION_INTERLACED] = &(const struct z_erofs_decompressor) {
429 		.decompress = z_erofs_transform_plain,
430 		.name = "interlaced"
431 	},
432 	[Z_EROFS_COMPRESSION_LZ4] = &(const struct z_erofs_decompressor) {
433 		.config = z_erofs_load_lz4_config,
434 		.decompress = z_erofs_lz4_decompress,
435 		.init = z_erofs_gbuf_init,
436 		.exit = z_erofs_gbuf_exit,
437 		.name = "lz4"
438 	},
439 #ifdef CONFIG_EROFS_FS_ZIP_LZMA
440 	[Z_EROFS_COMPRESSION_LZMA] = &z_erofs_lzma_decomp,
441 #endif
442 #ifdef CONFIG_EROFS_FS_ZIP_DEFLATE
443 	[Z_EROFS_COMPRESSION_DEFLATE] = &z_erofs_deflate_decomp,
444 #endif
445 #ifdef CONFIG_EROFS_FS_ZIP_ZSTD
446 	[Z_EROFS_COMPRESSION_ZSTD] = &z_erofs_zstd_decomp,
447 #endif
448 };
449 
450 int z_erofs_parse_cfgs(struct super_block *sb, struct erofs_super_block *dsb)
451 {
452 	struct erofs_sb_info *sbi = EROFS_SB(sb);
453 	struct erofs_buf buf = __EROFS_BUF_INITIALIZER;
454 	unsigned int algs, alg;
455 	erofs_off_t offset;
456 	int size, ret = 0;
457 
458 	if (!erofs_sb_has_compr_cfgs(sbi)) {
459 		sbi->available_compr_algs = 1 << Z_EROFS_COMPRESSION_LZ4;
460 		return z_erofs_load_lz4_config(sb, dsb, NULL, 0);
461 	}
462 
463 	sbi->available_compr_algs = le16_to_cpu(dsb->u1.available_compr_algs);
464 	if (sbi->available_compr_algs & ~Z_EROFS_ALL_COMPR_ALGS) {
465 		erofs_err(sb, "unidentified algorithms %x, please upgrade kernel",
466 			  sbi->available_compr_algs & ~Z_EROFS_ALL_COMPR_ALGS);
467 		return -EOPNOTSUPP;
468 	}
469 
470 	(void)erofs_init_metabuf(&buf, sb, false);
471 	offset = EROFS_SUPER_OFFSET + sbi->sb_size;
472 	alg = 0;
473 	for (algs = sbi->available_compr_algs; algs; algs >>= 1, ++alg) {
474 		const struct z_erofs_decompressor *dec = z_erofs_decomp[alg];
475 		void *data;
476 
477 		if (!(algs & 1))
478 			continue;
479 
480 		data = erofs_read_metadata(sb, &buf, &offset, &size);
481 		if (IS_ERR(data)) {
482 			ret = PTR_ERR(data);
483 			break;
484 		}
485 
486 		if (alg < Z_EROFS_COMPRESSION_MAX && dec && dec->config) {
487 			ret = dec->config(sb, dsb, data, size);
488 		} else {
489 			erofs_err(sb, "algorithm %d isn't enabled on this kernel",
490 				  alg);
491 			ret = -EOPNOTSUPP;
492 		}
493 		kfree(data);
494 		if (ret)
495 			break;
496 	}
497 	erofs_put_metabuf(&buf);
498 	return ret;
499 }
500 
501 int __init z_erofs_init_decompressor(void)
502 {
503 	int i, err;
504 
505 	for (i = 0; i < Z_EROFS_COMPRESSION_MAX; ++i) {
506 		err = z_erofs_decomp[i] ? z_erofs_decomp[i]->init() : 0;
507 		if (err) {
508 			while (i--)
509 				if (z_erofs_decomp[i])
510 					z_erofs_decomp[i]->exit();
511 			return err;
512 		}
513 	}
514 	return 0;
515 }
516 
517 void z_erofs_exit_decompressor(void)
518 {
519 	int i;
520 
521 	for (i = 0; i < Z_EROFS_COMPRESSION_MAX; ++i)
522 		if (z_erofs_decomp[i])
523 			z_erofs_decomp[i]->exit();
524 }
525