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
20struct 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
31static int z_erofs_lz4_prepare_destpages(struct z_erofs_decompress_req *rq,
32					 struct list_head *pagepool)
33{
34	const unsigned int nr =
35		PAGE_ALIGN(rq->pageofs_out + rq->outputsize) >> PAGE_SHIFT;
36	struct page *availables[LZ4_MAX_DISTANCE_PAGES] = { NULL };
37	unsigned long bounced[DIV_ROUND_UP(LZ4_MAX_DISTANCE_PAGES,
38					   BITS_PER_LONG)] = { 0 };
39	void *kaddr = NULL;
40	unsigned int i, j, top;
41
42	top = 0;
43	for (i = j = 0; i < nr; ++i, ++j) {
44		struct page *const page = rq->out[i];
45		struct page *victim;
46
47		if (j >= LZ4_MAX_DISTANCE_PAGES)
48			j = 0;
49
50		/* 'valid' bounced can only be tested after a complete round */
51		if (test_bit(j, bounced)) {
52			DBG_BUGON(i < LZ4_MAX_DISTANCE_PAGES);
53			DBG_BUGON(top >= LZ4_MAX_DISTANCE_PAGES);
54			availables[top++] = rq->out[i - LZ4_MAX_DISTANCE_PAGES];
55		}
56
57		if (page) {
58			__clear_bit(j, bounced);
59			if (!PageHighMem(page)) {
60				if (!i) {
61					kaddr = page_address(page);
62					continue;
63				}
64				if (kaddr &&
65				    kaddr + PAGE_SIZE == page_address(page)) {
66					kaddr += PAGE_SIZE;
67					continue;
68				}
69			}
70			kaddr = NULL;
71			continue;
72		}
73		kaddr = NULL;
74		__set_bit(j, bounced);
75
76		if (top) {
77			victim = availables[--top];
78			get_page(victim);
79		} else {
80			victim = erofs_allocpage(pagepool, GFP_KERNEL);
81			if (!victim)
82				return -ENOMEM;
83			victim->mapping = Z_EROFS_MAPPING_STAGING;
84		}
85		rq->out[i] = victim;
86	}
87	return kaddr ? 1 : 0;
88}
89
90static void *generic_copy_inplace_data(struct z_erofs_decompress_req *rq,
91				       u8 *src, unsigned int pageofs_in)
92{
93	/*
94	 * if in-place decompression is ongoing, those decompressed
95	 * pages should be copied in order to avoid being overlapped.
96	 */
97	struct page **in = rq->in;
98	u8 *const tmp = erofs_get_pcpubuf(0);
99	u8 *tmpp = tmp;
100	unsigned int inlen = rq->inputsize - pageofs_in;
101	unsigned int count = min_t(uint, inlen, PAGE_SIZE - pageofs_in);
102
103	while (tmpp < tmp + inlen) {
104		if (!src)
105			src = kmap_atomic(*in);
106		memcpy(tmpp, src + pageofs_in, count);
107		kunmap_atomic(src);
108		src = NULL;
109		tmpp += count;
110		pageofs_in = 0;
111		count = PAGE_SIZE;
112		++in;
113	}
114	return tmp;
115}
116
117static int z_erofs_lz4_decompress(struct z_erofs_decompress_req *rq, u8 *out)
118{
119	unsigned int inputmargin, inlen;
120	u8 *src;
121	bool copied, support_0padding;
122	int ret;
123
124	if (rq->inputsize > PAGE_SIZE)
125		return -EOPNOTSUPP;
126
127	src = kmap_atomic(*rq->in);
128	inputmargin = 0;
129	support_0padding = false;
130
131	/* decompression inplace is only safe when 0padding is enabled */
132	if (EROFS_SB(rq->sb)->feature_incompat &
133	    EROFS_FEATURE_INCOMPAT_LZ4_0PADDING) {
134		support_0padding = true;
135
136		while (!src[inputmargin & ~PAGE_MASK])
137			if (!(++inputmargin & ~PAGE_MASK))
138				break;
139
140		if (inputmargin >= rq->inputsize) {
141			kunmap_atomic(src);
142			return -EIO;
143		}
144	}
145
146	copied = false;
147	inlen = rq->inputsize - inputmargin;
148	if (rq->inplace_io) {
149		const uint oend = (rq->pageofs_out +
150				   rq->outputsize) & ~PAGE_MASK;
151		const uint nr = PAGE_ALIGN(rq->pageofs_out +
152					   rq->outputsize) >> PAGE_SHIFT;
153
154		if (rq->partial_decoding || !support_0padding ||
155		    rq->out[nr - 1] != rq->in[0] ||
156		    rq->inputsize - oend <
157		      LZ4_DECOMPRESS_INPLACE_MARGIN(inlen)) {
158			src = generic_copy_inplace_data(rq, src, inputmargin);
159			inputmargin = 0;
160			copied = true;
161		}
162	}
163
164	/* legacy format could compress extra data in a pcluster. */
165	if (rq->partial_decoding || !support_0padding)
166		ret = LZ4_decompress_safe_partial(src + inputmargin, out,
167						  inlen, rq->outputsize,
168						  rq->outputsize);
169	else
170		ret = LZ4_decompress_safe(src + inputmargin, out,
171					  inlen, rq->outputsize);
172
173	if (ret != rq->outputsize) {
174		erofs_err(rq->sb, "failed to decompress %d in[%u, %u] out[%u]",
175			  ret, inlen, inputmargin, rq->outputsize);
176
177		print_hex_dump(KERN_DEBUG, "[ in]: ", DUMP_PREFIX_OFFSET,
178			       16, 1, src + inputmargin, inlen, true);
179		print_hex_dump(KERN_DEBUG, "[out]: ", DUMP_PREFIX_OFFSET,
180			       16, 1, out, rq->outputsize, true);
181
182		if (ret >= 0)
183			memset(out + ret, 0, rq->outputsize - ret);
184		ret = -EIO;
185	}
186
187	if (copied)
188		erofs_put_pcpubuf(src);
189	else
190		kunmap_atomic(src);
191	return ret;
192}
193
194static struct z_erofs_decompressor decompressors[] = {
195	[Z_EROFS_COMPRESSION_SHIFTED] = {
196		.name = "shifted"
197	},
198	[Z_EROFS_COMPRESSION_LZ4] = {
199		.prepare_destpages = z_erofs_lz4_prepare_destpages,
200		.decompress = z_erofs_lz4_decompress,
201		.name = "lz4"
202	},
203};
204
205static void copy_from_pcpubuf(struct page **out, const char *dst,
206			      unsigned short pageofs_out,
207			      unsigned int outputsize)
208{
209	const char *end = dst + outputsize;
210	const unsigned int righthalf = PAGE_SIZE - pageofs_out;
211	const char *cur = dst - pageofs_out;
212
213	while (cur < end) {
214		struct page *const page = *out++;
215
216		if (page) {
217			char *buf = kmap_atomic(page);
218
219			if (cur >= dst) {
220				memcpy(buf, cur, min_t(uint, PAGE_SIZE,
221						       end - cur));
222			} else {
223				memcpy(buf + pageofs_out, cur + pageofs_out,
224				       min_t(uint, righthalf, end - cur));
225			}
226			kunmap_atomic(buf);
227		}
228		cur += PAGE_SIZE;
229	}
230}
231
232static int z_erofs_decompress_generic(struct z_erofs_decompress_req *rq,
233				      struct list_head *pagepool)
234{
235	const unsigned int nrpages_out =
236		PAGE_ALIGN(rq->pageofs_out + rq->outputsize) >> PAGE_SHIFT;
237	const struct z_erofs_decompressor *alg = decompressors + rq->alg;
238	unsigned int dst_maptype;
239	void *dst;
240	int ret, i;
241
242	if (nrpages_out == 1 && !rq->inplace_io) {
243		DBG_BUGON(!*rq->out);
244		dst = kmap_atomic(*rq->out);
245		dst_maptype = 0;
246		goto dstmap_out;
247	}
248
249	/*
250	 * For the case of small output size (especially much less
251	 * than PAGE_SIZE), memcpy the decompressed data rather than
252	 * compressed data is preferred.
253	 */
254	if (rq->outputsize <= PAGE_SIZE * 7 / 8) {
255		dst = erofs_get_pcpubuf(0);
256		if (IS_ERR(dst))
257			return PTR_ERR(dst);
258
259		rq->inplace_io = false;
260		ret = alg->decompress(rq, dst);
261		if (!ret)
262			copy_from_pcpubuf(rq->out, dst, rq->pageofs_out,
263					  rq->outputsize);
264
265		erofs_put_pcpubuf(dst);
266		return ret;
267	}
268
269	ret = alg->prepare_destpages(rq, pagepool);
270	if (ret < 0) {
271		return ret;
272	} else if (ret) {
273		dst = page_address(*rq->out);
274		dst_maptype = 1;
275		goto dstmap_out;
276	}
277
278	i = 0;
279	while (1) {
280		dst = vm_map_ram(rq->out, nrpages_out, -1);
281
282		/* retry two more times (totally 3 times) */
283		if (dst || ++i >= 3)
284			break;
285		vm_unmap_aliases();
286	}
287
288	if (!dst)
289		return -ENOMEM;
290
291	dst_maptype = 2;
292
293dstmap_out:
294	ret = alg->decompress(rq, dst + rq->pageofs_out);
295
296	if (!dst_maptype)
297		kunmap_atomic(dst);
298	else if (dst_maptype == 2)
299		vm_unmap_ram(dst, nrpages_out);
300	return ret;
301}
302
303static int z_erofs_shifted_transform(const struct z_erofs_decompress_req *rq,
304				     struct list_head *pagepool)
305{
306	const unsigned int nrpages_out =
307		PAGE_ALIGN(rq->pageofs_out + rq->outputsize) >> PAGE_SHIFT;
308	const unsigned int righthalf = PAGE_SIZE - rq->pageofs_out;
309	unsigned char *src, *dst;
310
311	if (nrpages_out > 2) {
312		DBG_BUGON(1);
313		return -EIO;
314	}
315
316	if (rq->out[0] == *rq->in) {
317		DBG_BUGON(nrpages_out != 1);
318		return 0;
319	}
320
321	src = kmap_atomic(*rq->in);
322	if (rq->out[0]) {
323		dst = kmap_atomic(rq->out[0]);
324		memcpy(dst + rq->pageofs_out, src, righthalf);
325		kunmap_atomic(dst);
326	}
327
328	if (nrpages_out == 2) {
329		DBG_BUGON(!rq->out[1]);
330		if (rq->out[1] == *rq->in) {
331			memmove(src, src + righthalf, rq->pageofs_out);
332		} else {
333			dst = kmap_atomic(rq->out[1]);
334			memcpy(dst, src + righthalf, rq->pageofs_out);
335			kunmap_atomic(dst);
336		}
337	}
338	kunmap_atomic(src);
339	return 0;
340}
341
342int z_erofs_decompress(struct z_erofs_decompress_req *rq,
343		       struct list_head *pagepool)
344{
345	if (rq->alg == Z_EROFS_COMPRESSION_SHIFTED)
346		return z_erofs_shifted_transform(rq, pagepool);
347	return z_erofs_decompress_generic(rq, pagepool);
348}
349
350