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
z_erofs_lz4_prepare_destpages(struct z_erofs_decompress_req * rq,struct list_head * pagepool)31 static 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
generic_copy_inplace_data(struct z_erofs_decompress_req * rq,u8 * src,unsigned int pageofs_in)90 static 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
z_erofs_lz4_decompress(struct z_erofs_decompress_req * rq,u8 * out)117 static 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
194 static 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
copy_from_pcpubuf(struct page ** out,const char * dst,unsigned short pageofs_out,unsigned int outputsize)205 static 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
z_erofs_decompress_generic(struct z_erofs_decompress_req * rq,struct list_head * pagepool)232 static 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
293 dstmap_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
z_erofs_shifted_transform(const struct z_erofs_decompress_req * rq,struct list_head * pagepool)303 static 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
z_erofs_decompress(struct z_erofs_decompress_req * rq,struct list_head * pagepool)342 int 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