xref: /linux/fs/erofs/decompressor.c (revision aaa44952bbd1d4db14a4d676bf9595bb5db7e7b0) 
1 // SPDX-License-Identifier: GPL-2.0-only
2 /*
3  * Copyright (C) 2019 HUAWEI, Inc.
4  *             https://www.huawei.com/
5  * Created by Gao Xiang <gaoxiang25@huawei.com>
6  */
7 #include "compress.h"
8 #include <linux/module.h>
9 #include <linux/lz4.h>
10 
11 #ifndef LZ4_DISTANCE_MAX	/* history window size */
12 #define LZ4_DISTANCE_MAX 65535	/* set to maximum value by default */
13 #endif
14 
15 #define LZ4_MAX_DISTANCE_PAGES	(DIV_ROUND_UP(LZ4_DISTANCE_MAX, PAGE_SIZE) + 1)
16 #ifndef LZ4_DECOMPRESS_INPLACE_MARGIN
17 #define LZ4_DECOMPRESS_INPLACE_MARGIN(srcsize)  (((srcsize) >> 8) + 32)
18 #endif
19 
20 struct z_erofs_decompressor {
21 	/*
22 	 * if destpages have sparsed pages, fill them with bounce pages.
23 	 * it also check whether destpages indicate continuous physical memory.
24 	 */
25 	int (*prepare_destpages)(struct z_erofs_decompress_req *rq,
26 				 struct list_head *pagepool);
27 	int (*decompress)(struct z_erofs_decompress_req *rq, u8 *out);
28 	char *name;
29 };
30 
31 int z_erofs_load_lz4_config(struct super_block *sb,
32 			    struct erofs_super_block *dsb,
33 			    struct z_erofs_lz4_cfgs *lz4, int size)
34 {
35 	struct erofs_sb_info *sbi = EROFS_SB(sb);
36 	u16 distance;
37 
38 	if (lz4) {
39 		if (size < sizeof(struct z_erofs_lz4_cfgs)) {
40 			erofs_err(sb, "invalid lz4 cfgs, size=%u", size);
41 			return -EINVAL;
42 		}
43 		distance = le16_to_cpu(lz4->max_distance);
44 
45 		sbi->lz4.max_pclusterblks = le16_to_cpu(lz4->max_pclusterblks);
46 		if (!sbi->lz4.max_pclusterblks) {
47 			sbi->lz4.max_pclusterblks = 1;	/* reserved case */
48 		} else if (sbi->lz4.max_pclusterblks >
49 			   Z_EROFS_PCLUSTER_MAX_SIZE / EROFS_BLKSIZ) {
50 			erofs_err(sb, "too large lz4 pclusterblks %u",
51 				  sbi->lz4.max_pclusterblks);
52 			return -EINVAL;
53 		} else if (sbi->lz4.max_pclusterblks >= 2) {
54 			erofs_info(sb, "EXPERIMENTAL big pcluster feature in use. Use at your own risk!");
55 		}
56 	} else {
57 		distance = le16_to_cpu(dsb->u1.lz4_max_distance);
58 		sbi->lz4.max_pclusterblks = 1;
59 	}
60 
61 	sbi->lz4.max_distance_pages = distance ?
62 					DIV_ROUND_UP(distance, PAGE_SIZE) + 1 :
63 					LZ4_MAX_DISTANCE_PAGES;
64 	return erofs_pcpubuf_growsize(sbi->lz4.max_pclusterblks);
65 }
66 
67 static int z_erofs_lz4_prepare_destpages(struct z_erofs_decompress_req *rq,
68 					 struct list_head *pagepool)
69 {
70 	const unsigned int nr =
71 		PAGE_ALIGN(rq->pageofs_out + rq->outputsize) >> PAGE_SHIFT;
72 	struct page *availables[LZ4_MAX_DISTANCE_PAGES] = { NULL };
73 	unsigned long bounced[DIV_ROUND_UP(LZ4_MAX_DISTANCE_PAGES,
74 					   BITS_PER_LONG)] = { 0 };
75 	unsigned int lz4_max_distance_pages =
76 				EROFS_SB(rq->sb)->lz4.max_distance_pages;
77 	void *kaddr = NULL;
78 	unsigned int i, j, top;
79 
80 	top = 0;
81 	for (i = j = 0; i < nr; ++i, ++j) {
82 		struct page *const page = rq->out[i];
83 		struct page *victim;
84 
85 		if (j >= lz4_max_distance_pages)
86 			j = 0;
87 
88 		/* 'valid' bounced can only be tested after a complete round */
89 		if (test_bit(j, bounced)) {
90 			DBG_BUGON(i < lz4_max_distance_pages);
91 			DBG_BUGON(top >= lz4_max_distance_pages);
92 			availables[top++] = rq->out[i - lz4_max_distance_pages];
93 		}
94 
95 		if (page) {
96 			__clear_bit(j, bounced);
97 			if (kaddr) {
98 				if (kaddr + PAGE_SIZE == page_address(page))
99 					kaddr += PAGE_SIZE;
100 				else
101 					kaddr = NULL;
102 			} else if (!i) {
103 				kaddr = page_address(page);
104 			}
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_handle_inplace_io(struct z_erofs_decompress_req *rq,
124 			void *inpage, unsigned int *inputmargin, int *maptype,
125 			bool support_0padding)
126 {
127 	unsigned int nrpages_in, nrpages_out;
128 	unsigned int ofull, oend, inputsize, total, i, j;
129 	struct page **in;
130 	void *src, *tmp;
131 
132 	inputsize = rq->inputsize;
133 	nrpages_in = PAGE_ALIGN(inputsize) >> PAGE_SHIFT;
134 	oend = rq->pageofs_out + rq->outputsize;
135 	ofull = PAGE_ALIGN(oend);
136 	nrpages_out = ofull >> PAGE_SHIFT;
137 
138 	if (rq->inplace_io) {
139 		if (rq->partial_decoding || !support_0padding ||
140 		    ofull - oend < LZ4_DECOMPRESS_INPLACE_MARGIN(inputsize))
141 			goto docopy;
142 
143 		for (i = 0; i < nrpages_in; ++i) {
144 			DBG_BUGON(rq->in[i] == NULL);
145 			for (j = 0; j < nrpages_out - nrpages_in + i; ++j)
146 				if (rq->out[j] == rq->in[i])
147 					goto docopy;
148 		}
149 	}
150 
151 	if (nrpages_in <= 1) {
152 		*maptype = 0;
153 		return inpage;
154 	}
155 	kunmap_atomic(inpage);
156 	might_sleep();
157 	src = erofs_vm_map_ram(rq->in, nrpages_in);
158 	if (!src)
159 		return ERR_PTR(-ENOMEM);
160 	*maptype = 1;
161 	return src;
162 
163 docopy:
164 	/* Or copy compressed data which can be overlapped to per-CPU buffer */
165 	in = rq->in;
166 	src = erofs_get_pcpubuf(nrpages_in);
167 	if (!src) {
168 		DBG_BUGON(1);
169 		kunmap_atomic(inpage);
170 		return ERR_PTR(-EFAULT);
171 	}
172 
173 	tmp = src;
174 	total = rq->inputsize;
175 	while (total) {
176 		unsigned int page_copycnt =
177 			min_t(unsigned int, total, PAGE_SIZE - *inputmargin);
178 
179 		if (!inpage)
180 			inpage = kmap_atomic(*in);
181 		memcpy(tmp, inpage + *inputmargin, page_copycnt);
182 		kunmap_atomic(inpage);
183 		inpage = NULL;
184 		tmp += page_copycnt;
185 		total -= page_copycnt;
186 		++in;
187 		*inputmargin = 0;
188 	}
189 	*maptype = 2;
190 	return src;
191 }
192 
193 static int z_erofs_lz4_decompress(struct z_erofs_decompress_req *rq, u8 *out)
194 {
195 	unsigned int inputmargin;
196 	u8 *headpage, *src;
197 	bool support_0padding;
198 	int ret, maptype;
199 
200 	DBG_BUGON(*rq->in == NULL);
201 	headpage = kmap_atomic(*rq->in);
202 	inputmargin = 0;
203 	support_0padding = false;
204 
205 	/* decompression inplace is only safe when 0padding is enabled */
206 	if (erofs_sb_has_lz4_0padding(EROFS_SB(rq->sb))) {
207 		support_0padding = true;
208 
209 		while (!headpage[inputmargin & ~PAGE_MASK])
210 			if (!(++inputmargin & ~PAGE_MASK))
211 				break;
212 
213 		if (inputmargin >= rq->inputsize) {
214 			kunmap_atomic(headpage);
215 			return -EIO;
216 		}
217 	}
218 
219 	rq->inputsize -= inputmargin;
220 	src = z_erofs_handle_inplace_io(rq, headpage, &inputmargin, &maptype,
221 					support_0padding);
222 	if (IS_ERR(src))
223 		return PTR_ERR(src);
224 
225 	/* legacy format could compress extra data in a pcluster. */
226 	if (rq->partial_decoding || !support_0padding)
227 		ret = LZ4_decompress_safe_partial(src + inputmargin, out,
228 				rq->inputsize, rq->outputsize, rq->outputsize);
229 	else
230 		ret = LZ4_decompress_safe(src + inputmargin, out,
231 					  rq->inputsize, rq->outputsize);
232 
233 	if (ret != rq->outputsize) {
234 		erofs_err(rq->sb, "failed to decompress %d in[%u, %u] out[%u]",
235 			  ret, rq->inputsize, inputmargin, rq->outputsize);
236 
237 		WARN_ON(1);
238 		print_hex_dump(KERN_DEBUG, "[ in]: ", DUMP_PREFIX_OFFSET,
239 			       16, 1, src + inputmargin, rq->inputsize, true);
240 		print_hex_dump(KERN_DEBUG, "[out]: ", DUMP_PREFIX_OFFSET,
241 			       16, 1, out, rq->outputsize, true);
242 
243 		if (ret >= 0)
244 			memset(out + ret, 0, rq->outputsize - ret);
245 		ret = -EIO;
246 	}
247 
248 	if (maptype == 0) {
249 		kunmap_atomic(src);
250 	} else if (maptype == 1) {
251 		vm_unmap_ram(src, PAGE_ALIGN(rq->inputsize) >> PAGE_SHIFT);
252 	} else if (maptype == 2) {
253 		erofs_put_pcpubuf(src);
254 	} else {
255 		DBG_BUGON(1);
256 		return -EFAULT;
257 	}
258 	return ret;
259 }
260 
261 static struct z_erofs_decompressor decompressors[] = {
262 	[Z_EROFS_COMPRESSION_SHIFTED] = {
263 		.name = "shifted"
264 	},
265 	[Z_EROFS_COMPRESSION_LZ4] = {
266 		.prepare_destpages = z_erofs_lz4_prepare_destpages,
267 		.decompress = z_erofs_lz4_decompress,
268 		.name = "lz4"
269 	},
270 };
271 
272 static void copy_from_pcpubuf(struct page **out, const char *dst,
273 			      unsigned short pageofs_out,
274 			      unsigned int outputsize)
275 {
276 	const char *end = dst + outputsize;
277 	const unsigned int righthalf = PAGE_SIZE - pageofs_out;
278 	const char *cur = dst - pageofs_out;
279 
280 	while (cur < end) {
281 		struct page *const page = *out++;
282 
283 		if (page) {
284 			char *buf = kmap_atomic(page);
285 
286 			if (cur >= dst) {
287 				memcpy(buf, cur, min_t(uint, PAGE_SIZE,
288 						       end - cur));
289 			} else {
290 				memcpy(buf + pageofs_out, cur + pageofs_out,
291 				       min_t(uint, righthalf, end - cur));
292 			}
293 			kunmap_atomic(buf);
294 		}
295 		cur += PAGE_SIZE;
296 	}
297 }
298 
299 static int z_erofs_decompress_generic(struct z_erofs_decompress_req *rq,
300 				      struct list_head *pagepool)
301 {
302 	const unsigned int nrpages_out =
303 		PAGE_ALIGN(rq->pageofs_out + rq->outputsize) >> PAGE_SHIFT;
304 	const struct z_erofs_decompressor *alg = decompressors + rq->alg;
305 	unsigned int dst_maptype;
306 	void *dst;
307 	int ret;
308 
309 	/* two optimized fast paths only for non bigpcluster cases yet */
310 	if (rq->inputsize <= PAGE_SIZE) {
311 		if (nrpages_out == 1 && !rq->inplace_io) {
312 			DBG_BUGON(!*rq->out);
313 			dst = kmap_atomic(*rq->out);
314 			dst_maptype = 0;
315 			goto dstmap_out;
316 		}
317 
318 		/*
319 		 * For the case of small output size (especially much less
320 		 * than PAGE_SIZE), memcpy the decompressed data rather than
321 		 * compressed data is preferred.
322 		 */
323 		if (rq->outputsize <= PAGE_SIZE * 7 / 8) {
324 			dst = erofs_get_pcpubuf(1);
325 			if (IS_ERR(dst))
326 				return PTR_ERR(dst);
327 
328 			rq->inplace_io = false;
329 			ret = alg->decompress(rq, dst);
330 			if (!ret)
331 				copy_from_pcpubuf(rq->out, dst, rq->pageofs_out,
332 						  rq->outputsize);
333 
334 			erofs_put_pcpubuf(dst);
335 			return ret;
336 		}
337 	}
338 
339 	/* general decoding path which can be used for all cases */
340 	ret = alg->prepare_destpages(rq, pagepool);
341 	if (ret < 0)
342 		return ret;
343 	if (ret) {
344 		dst = page_address(*rq->out);
345 		dst_maptype = 1;
346 		goto dstmap_out;
347 	}
348 
349 	dst = erofs_vm_map_ram(rq->out, nrpages_out);
350 	if (!dst)
351 		return -ENOMEM;
352 	dst_maptype = 2;
353 
354 dstmap_out:
355 	ret = alg->decompress(rq, dst + rq->pageofs_out);
356 
357 	if (!dst_maptype)
358 		kunmap_atomic(dst);
359 	else if (dst_maptype == 2)
360 		vm_unmap_ram(dst, nrpages_out);
361 	return ret;
362 }
363 
364 static int z_erofs_shifted_transform(const struct z_erofs_decompress_req *rq,
365 				     struct list_head *pagepool)
366 {
367 	const unsigned int nrpages_out =
368 		PAGE_ALIGN(rq->pageofs_out + rq->outputsize) >> PAGE_SHIFT;
369 	const unsigned int righthalf = PAGE_SIZE - rq->pageofs_out;
370 	unsigned char *src, *dst;
371 
372 	if (nrpages_out > 2) {
373 		DBG_BUGON(1);
374 		return -EIO;
375 	}
376 
377 	if (rq->out[0] == *rq->in) {
378 		DBG_BUGON(nrpages_out != 1);
379 		return 0;
380 	}
381 
382 	src = kmap_atomic(*rq->in);
383 	if (rq->out[0]) {
384 		dst = kmap_atomic(rq->out[0]);
385 		memcpy(dst + rq->pageofs_out, src, righthalf);
386 		kunmap_atomic(dst);
387 	}
388 
389 	if (nrpages_out == 2) {
390 		DBG_BUGON(!rq->out[1]);
391 		if (rq->out[1] == *rq->in) {
392 			memmove(src, src + righthalf, rq->pageofs_out);
393 		} else {
394 			dst = kmap_atomic(rq->out[1]);
395 			memcpy(dst, src + righthalf, rq->pageofs_out);
396 			kunmap_atomic(dst);
397 		}
398 	}
399 	kunmap_atomic(src);
400 	return 0;
401 }
402 
403 int z_erofs_decompress(struct z_erofs_decompress_req *rq,
404 		       struct list_head *pagepool)
405 {
406 	if (rq->alg == Z_EROFS_COMPRESSION_SHIFTED)
407 		return z_erofs_shifted_transform(rq, pagepool);
408 	return z_erofs_decompress_generic(rq, pagepool);
409 }
410 
411