]>
Commit | Line | Data |
---|---|---|
c1d7c514 | 1 | // SPDX-License-Identifier: GPL-2.0 |
a6fa6fae LZ |
2 | /* |
3 | * Copyright (C) 2008 Oracle. All rights reserved. | |
a6fa6fae LZ |
4 | */ |
5 | ||
6 | #include <linux/kernel.h> | |
7 | #include <linux/slab.h> | |
6acafd1e | 8 | #include <linux/mm.h> |
a6fa6fae LZ |
9 | #include <linux/init.h> |
10 | #include <linux/err.h> | |
11 | #include <linux/sched.h> | |
12 | #include <linux/pagemap.h> | |
13 | #include <linux/bio.h> | |
14 | #include <linux/lzo.h> | |
e1ddce71 | 15 | #include <linux/refcount.h> |
a6fa6fae | 16 | #include "compression.h" |
a6e66e6f | 17 | #include "ctree.h" |
a6fa6fae LZ |
18 | |
19 | #define LZO_LEN 4 | |
20 | ||
2a1f7c0c QW |
21 | /* |
22 | * Btrfs LZO compression format | |
23 | * | |
24 | * Regular and inlined LZO compressed data extents consist of: | |
25 | * | |
26 | * 1. Header | |
27 | * Fixed size. LZO_LEN (4) bytes long, LE32. | |
28 | * Records the total size (including the header) of compressed data. | |
29 | * | |
30 | * 2. Segment(s) | |
52042d8e | 31 | * Variable size. Each segment includes one segment header, followed by data |
2a1f7c0c QW |
32 | * payload. |
33 | * One regular LZO compressed extent can have one or more segments. | |
34 | * For inlined LZO compressed extent, only one segment is allowed. | |
d4088803 | 35 | * One segment represents at most one sector of uncompressed data. |
2a1f7c0c QW |
36 | * |
37 | * 2.1 Segment header | |
38 | * Fixed size. LZO_LEN (4) bytes long, LE32. | |
39 | * Records the total size of the segment (not including the header). | |
d4088803 QW |
40 | * Segment header never crosses sector boundary, thus it's possible to |
41 | * have at most 3 padding zeros at the end of the sector. | |
2a1f7c0c QW |
42 | * |
43 | * 2.2 Data Payload | |
d4088803 QW |
44 | * Variable size. Size up limit should be lzo1x_worst_compress(sectorsize) |
45 | * which is 4419 for a 4KiB sectorsize. | |
2a1f7c0c | 46 | * |
d4088803 | 47 | * Example with 4K sectorsize: |
2a1f7c0c QW |
48 | * Page 1: |
49 | * 0 0x2 0x4 0x6 0x8 0xa 0xc 0xe 0x10 | |
50 | * 0x0000 | Header | SegHdr 01 | Data payload 01 ... | | |
51 | * ... | |
52 | * 0x0ff0 | SegHdr N | Data payload N ... |00| | |
53 | * ^^ padding zeros | |
54 | * Page 2: | |
55 | * 0x1000 | SegHdr N+1| Data payload N+1 ... | | |
56 | */ | |
57 | ||
dc4a4bdb DM |
58 | #define WORKSPACE_BUF_LENGTH (lzo1x_worst_compress(PAGE_SIZE)) |
59 | #define WORKSPACE_CBUF_LENGTH (lzo1x_worst_compress(PAGE_SIZE)) | |
60 | ||
a6fa6fae LZ |
61 | struct workspace { |
62 | void *mem; | |
3fb40375 JL |
63 | void *buf; /* where decompressed data goes */ |
64 | void *cbuf; /* where compressed data goes */ | |
a6fa6fae LZ |
65 | struct list_head list; |
66 | }; | |
67 | ||
92ee5530 DZ |
68 | static struct workspace_manager wsm; |
69 | ||
d20f395f | 70 | void lzo_free_workspace(struct list_head *ws) |
a6fa6fae LZ |
71 | { |
72 | struct workspace *workspace = list_entry(ws, struct workspace, list); | |
73 | ||
6acafd1e DS |
74 | kvfree(workspace->buf); |
75 | kvfree(workspace->cbuf); | |
76 | kvfree(workspace->mem); | |
a6fa6fae LZ |
77 | kfree(workspace); |
78 | } | |
79 | ||
d20f395f | 80 | struct list_head *lzo_alloc_workspace(unsigned int level) |
a6fa6fae LZ |
81 | { |
82 | struct workspace *workspace; | |
83 | ||
389a6cfc | 84 | workspace = kzalloc(sizeof(*workspace), GFP_KERNEL); |
a6fa6fae LZ |
85 | if (!workspace) |
86 | return ERR_PTR(-ENOMEM); | |
87 | ||
6acafd1e | 88 | workspace->mem = kvmalloc(LZO1X_MEM_COMPRESS, GFP_KERNEL); |
dc4a4bdb DM |
89 | workspace->buf = kvmalloc(WORKSPACE_BUF_LENGTH, GFP_KERNEL); |
90 | workspace->cbuf = kvmalloc(WORKSPACE_CBUF_LENGTH, GFP_KERNEL); | |
a6fa6fae LZ |
91 | if (!workspace->mem || !workspace->buf || !workspace->cbuf) |
92 | goto fail; | |
93 | ||
94 | INIT_LIST_HEAD(&workspace->list); | |
95 | ||
96 | return &workspace->list; | |
97 | fail: | |
98 | lzo_free_workspace(&workspace->list); | |
99 | return ERR_PTR(-ENOMEM); | |
100 | } | |
101 | ||
102 | static inline void write_compress_length(char *buf, size_t len) | |
103 | { | |
104 | __le32 dlen; | |
105 | ||
106 | dlen = cpu_to_le32(len); | |
107 | memcpy(buf, &dlen, LZO_LEN); | |
108 | } | |
109 | ||
14a3357b | 110 | static inline size_t read_compress_length(const char *buf) |
a6fa6fae LZ |
111 | { |
112 | __le32 dlen; | |
113 | ||
114 | memcpy(&dlen, buf, LZO_LEN); | |
115 | return le32_to_cpu(dlen); | |
116 | } | |
117 | ||
d4088803 QW |
118 | /* |
119 | * Will do: | |
120 | * | |
121 | * - Write a segment header into the destination | |
122 | * - Copy the compressed buffer into the destination | |
123 | * - Make sure we have enough space in the last sector to fit a segment header | |
124 | * If not, we will pad at most (LZO_LEN (4)) - 1 bytes of zeros. | |
125 | * | |
126 | * Will allocate new pages when needed. | |
127 | */ | |
128 | static int copy_compressed_data_to_page(char *compressed_data, | |
129 | size_t compressed_size, | |
130 | struct page **out_pages, | |
6f019c0e | 131 | unsigned long max_nr_page, |
d4088803 QW |
132 | u32 *cur_out, |
133 | const u32 sectorsize) | |
134 | { | |
135 | u32 sector_bytes_left; | |
136 | u32 orig_out; | |
137 | struct page *cur_page; | |
037c50bf | 138 | char *kaddr; |
d4088803 | 139 | |
6f019c0e QW |
140 | if ((*cur_out / PAGE_SIZE) >= max_nr_page) |
141 | return -E2BIG; | |
142 | ||
d4088803 QW |
143 | /* |
144 | * We never allow a segment header crossing sector boundary, previous | |
145 | * run should ensure we have enough space left inside the sector. | |
146 | */ | |
147 | ASSERT((*cur_out / sectorsize) == (*cur_out + LZO_LEN - 1) / sectorsize); | |
148 | ||
149 | cur_page = out_pages[*cur_out / PAGE_SIZE]; | |
150 | /* Allocate a new page */ | |
151 | if (!cur_page) { | |
152 | cur_page = alloc_page(GFP_NOFS); | |
153 | if (!cur_page) | |
154 | return -ENOMEM; | |
155 | out_pages[*cur_out / PAGE_SIZE] = cur_page; | |
156 | } | |
157 | ||
51c0674a | 158 | kaddr = kmap_local_page(cur_page); |
037c50bf | 159 | write_compress_length(kaddr + offset_in_page(*cur_out), |
d4088803 QW |
160 | compressed_size); |
161 | *cur_out += LZO_LEN; | |
162 | ||
163 | orig_out = *cur_out; | |
164 | ||
165 | /* Copy compressed data */ | |
166 | while (*cur_out - orig_out < compressed_size) { | |
167 | u32 copy_len = min_t(u32, sectorsize - *cur_out % sectorsize, | |
168 | orig_out + compressed_size - *cur_out); | |
169 | ||
51c0674a | 170 | kunmap_local(kaddr); |
6fdf8864 | 171 | |
6f019c0e QW |
172 | if ((*cur_out / PAGE_SIZE) >= max_nr_page) |
173 | return -E2BIG; | |
174 | ||
d4088803 QW |
175 | cur_page = out_pages[*cur_out / PAGE_SIZE]; |
176 | /* Allocate a new page */ | |
177 | if (!cur_page) { | |
178 | cur_page = alloc_page(GFP_NOFS); | |
179 | if (!cur_page) | |
180 | return -ENOMEM; | |
181 | out_pages[*cur_out / PAGE_SIZE] = cur_page; | |
182 | } | |
51c0674a | 183 | kaddr = kmap_local_page(cur_page); |
d4088803 | 184 | |
037c50bf | 185 | memcpy(kaddr + offset_in_page(*cur_out), |
d4088803 QW |
186 | compressed_data + *cur_out - orig_out, copy_len); |
187 | ||
188 | *cur_out += copy_len; | |
189 | } | |
190 | ||
191 | /* | |
192 | * Check if we can fit the next segment header into the remaining space | |
193 | * of the sector. | |
194 | */ | |
195 | sector_bytes_left = round_up(*cur_out, sectorsize) - *cur_out; | |
196 | if (sector_bytes_left >= LZO_LEN || sector_bytes_left == 0) | |
037c50bf | 197 | goto out; |
d4088803 QW |
198 | |
199 | /* The remaining size is not enough, pad it with zeros */ | |
037c50bf | 200 | memset(kaddr + offset_in_page(*cur_out), 0, |
d4088803 QW |
201 | sector_bytes_left); |
202 | *cur_out += sector_bytes_left; | |
037c50bf LT |
203 | |
204 | out: | |
51c0674a | 205 | kunmap_local(kaddr); |
d4088803 QW |
206 | return 0; |
207 | } | |
208 | ||
c4bf665a DS |
209 | int lzo_compress_pages(struct list_head *ws, struct address_space *mapping, |
210 | u64 start, struct page **pages, unsigned long *out_pages, | |
211 | unsigned long *total_in, unsigned long *total_out) | |
a6fa6fae LZ |
212 | { |
213 | struct workspace *workspace = list_entry(ws, struct workspace, list); | |
d4088803 QW |
214 | const u32 sectorsize = btrfs_sb(mapping->host->i_sb)->sectorsize; |
215 | struct page *page_in = NULL; | |
037c50bf | 216 | char *sizes_ptr; |
6f019c0e | 217 | const unsigned long max_nr_page = *out_pages; |
a6fa6fae | 218 | int ret = 0; |
d4088803 QW |
219 | /* Points to the file offset of input data */ |
220 | u64 cur_in = start; | |
221 | /* Points to the current output byte */ | |
222 | u32 cur_out = 0; | |
223 | u32 len = *total_out; | |
a6fa6fae | 224 | |
6f019c0e | 225 | ASSERT(max_nr_page > 0); |
a6fa6fae LZ |
226 | *out_pages = 0; |
227 | *total_out = 0; | |
228 | *total_in = 0; | |
229 | ||
a6fa6fae | 230 | /* |
d4088803 QW |
231 | * Skip the header for now, we will later come back and write the total |
232 | * compressed size | |
a6fa6fae | 233 | */ |
d4088803 QW |
234 | cur_out += LZO_LEN; |
235 | while (cur_in < start + len) { | |
037c50bf | 236 | char *data_in; |
d4088803 QW |
237 | const u32 sectorsize_mask = sectorsize - 1; |
238 | u32 sector_off = (cur_in - start) & sectorsize_mask; | |
239 | u32 in_len; | |
240 | size_t out_len; | |
241 | ||
242 | /* Get the input page first */ | |
243 | if (!page_in) { | |
244 | page_in = find_get_page(mapping, cur_in >> PAGE_SHIFT); | |
245 | ASSERT(page_in); | |
246 | } | |
247 | ||
248 | /* Compress at most one sector of data each time */ | |
249 | in_len = min_t(u32, start + len - cur_in, sectorsize - sector_off); | |
250 | ASSERT(in_len); | |
51c0674a | 251 | data_in = kmap_local_page(page_in); |
037c50bf | 252 | ret = lzo1x_1_compress(data_in + |
d4088803 QW |
253 | offset_in_page(cur_in), in_len, |
254 | workspace->cbuf, &out_len, | |
255 | workspace->mem); | |
51c0674a | 256 | kunmap_local(data_in); |
d4088803 QW |
257 | if (ret < 0) { |
258 | pr_debug("BTRFS: lzo in loop returned %d\n", ret); | |
60e1975a | 259 | ret = -EIO; |
a6fa6fae LZ |
260 | goto out; |
261 | } | |
262 | ||
d4088803 | 263 | ret = copy_compressed_data_to_page(workspace->cbuf, out_len, |
6f019c0e QW |
264 | pages, max_nr_page, |
265 | &cur_out, sectorsize); | |
d4088803 QW |
266 | if (ret < 0) |
267 | goto out; | |
a6fa6fae | 268 | |
d4088803 QW |
269 | cur_in += in_len; |
270 | ||
271 | /* | |
272 | * Check if we're making it bigger after two sectors. And if | |
273 | * it is so, give up. | |
274 | */ | |
275 | if (cur_in - start > sectorsize * 2 && cur_in - start < cur_out) { | |
60e1975a | 276 | ret = -E2BIG; |
a6fa6fae | 277 | goto out; |
59516f60 | 278 | } |
a6fa6fae | 279 | |
d4088803 QW |
280 | /* Check if we have reached page boundary */ |
281 | if (IS_ALIGNED(cur_in, PAGE_SIZE)) { | |
282 | put_page(page_in); | |
283 | page_in = NULL; | |
284 | } | |
1e9d7291 | 285 | } |
a6fa6fae | 286 | |
d4088803 | 287 | /* Store the size of all chunks of compressed data */ |
ccaa66c8 | 288 | sizes_ptr = kmap_local_page(pages[0]); |
037c50bf | 289 | write_compress_length(sizes_ptr, cur_out); |
ccaa66c8 | 290 | kunmap_local(sizes_ptr); |
a6fa6fae LZ |
291 | |
292 | ret = 0; | |
d4088803 QW |
293 | *total_out = cur_out; |
294 | *total_in = cur_in - start; | |
a6fa6fae | 295 | out: |
daf87e95 QW |
296 | if (page_in) |
297 | put_page(page_in); | |
d4088803 | 298 | *out_pages = DIV_ROUND_UP(cur_out, PAGE_SIZE); |
a6fa6fae LZ |
299 | return ret; |
300 | } | |
301 | ||
a6e66e6f QW |
302 | /* |
303 | * Copy the compressed segment payload into @dest. | |
304 | * | |
305 | * For the payload there will be no padding, just need to do page switching. | |
306 | */ | |
307 | static void copy_compressed_segment(struct compressed_bio *cb, | |
308 | char *dest, u32 len, u32 *cur_in) | |
309 | { | |
310 | u32 orig_in = *cur_in; | |
311 | ||
312 | while (*cur_in < orig_in + len) { | |
313 | struct page *cur_page; | |
314 | u32 copy_len = min_t(u32, PAGE_SIZE - offset_in_page(*cur_in), | |
315 | orig_in + len - *cur_in); | |
316 | ||
317 | ASSERT(copy_len); | |
318 | cur_page = cb->compressed_pages[*cur_in / PAGE_SIZE]; | |
319 | ||
51c0674a FDF |
320 | memcpy_from_page(dest + *cur_in - orig_in, cur_page, |
321 | offset_in_page(*cur_in), copy_len); | |
a6e66e6f QW |
322 | |
323 | *cur_in += copy_len; | |
324 | } | |
325 | } | |
326 | ||
c4bf665a | 327 | int lzo_decompress_bio(struct list_head *ws, struct compressed_bio *cb) |
a6fa6fae LZ |
328 | { |
329 | struct workspace *workspace = list_entry(ws, struct workspace, list); | |
a6e66e6f QW |
330 | const struct btrfs_fs_info *fs_info = btrfs_sb(cb->inode->i_sb); |
331 | const u32 sectorsize = fs_info->sectorsize; | |
ccaa66c8 | 332 | char *kaddr; |
a6e66e6f QW |
333 | int ret; |
334 | /* Compressed data length, can be unaligned */ | |
335 | u32 len_in; | |
336 | /* Offset inside the compressed data */ | |
337 | u32 cur_in = 0; | |
338 | /* Bytes decompressed so far */ | |
339 | u32 cur_out = 0; | |
340 | ||
51c0674a | 341 | kaddr = kmap_local_page(cb->compressed_pages[0]); |
ccaa66c8 | 342 | len_in = read_compress_length(kaddr); |
51c0674a | 343 | kunmap_local(kaddr); |
a6e66e6f | 344 | cur_in += LZO_LEN; |
a6fa6fae | 345 | |
314bfa47 | 346 | /* |
a6e66e6f | 347 | * LZO header length check |
314bfa47 | 348 | * |
a6e66e6f QW |
349 | * The total length should not exceed the maximum extent length, |
350 | * and all sectors should be used. | |
351 | * If this happens, it means the compressed extent is corrupted. | |
314bfa47 | 352 | */ |
a6e66e6f QW |
353 | if (len_in > min_t(size_t, BTRFS_MAX_COMPRESSED, cb->compressed_len) || |
354 | round_up(len_in, sectorsize) < cb->compressed_len) { | |
355 | btrfs_err(fs_info, | |
356 | "invalid lzo header, lzo len %u compressed len %u", | |
357 | len_in, cb->compressed_len); | |
358 | return -EUCLEAN; | |
314bfa47 | 359 | } |
a6fa6fae | 360 | |
a6e66e6f QW |
361 | /* Go through each lzo segment */ |
362 | while (cur_in < len_in) { | |
363 | struct page *cur_page; | |
364 | /* Length of the compressed segment */ | |
365 | u32 seg_len; | |
366 | u32 sector_bytes_left; | |
367 | size_t out_len = lzo1x_worst_compress(sectorsize); | |
a6fa6fae | 368 | |
314bfa47 | 369 | /* |
a6e66e6f QW |
370 | * We should always have enough space for one segment header |
371 | * inside current sector. | |
314bfa47 | 372 | */ |
a6e66e6f QW |
373 | ASSERT(cur_in / sectorsize == |
374 | (cur_in + LZO_LEN - 1) / sectorsize); | |
375 | cur_page = cb->compressed_pages[cur_in / PAGE_SIZE]; | |
376 | ASSERT(cur_page); | |
51c0674a | 377 | kaddr = kmap_local_page(cur_page); |
ccaa66c8 | 378 | seg_len = read_compress_length(kaddr + offset_in_page(cur_in)); |
51c0674a | 379 | kunmap_local(kaddr); |
a6e66e6f QW |
380 | cur_in += LZO_LEN; |
381 | ||
dc4a4bdb | 382 | if (seg_len > WORKSPACE_CBUF_LENGTH) { |
741b23a9 DM |
383 | /* |
384 | * seg_len shouldn't be larger than we have allocated | |
385 | * for workspace->cbuf | |
386 | */ | |
387 | btrfs_err(fs_info, "unexpectedly large lzo segment len %u", | |
388 | seg_len); | |
389 | ret = -EIO; | |
390 | goto out; | |
391 | } | |
392 | ||
a6e66e6f QW |
393 | /* Copy the compressed segment payload into workspace */ |
394 | copy_compressed_segment(cb, workspace->cbuf, seg_len, &cur_in); | |
395 | ||
396 | /* Decompress the data */ | |
397 | ret = lzo1x_decompress_safe(workspace->cbuf, seg_len, | |
398 | workspace->buf, &out_len); | |
a6fa6fae | 399 | if (ret != LZO_E_OK) { |
a6e66e6f | 400 | btrfs_err(fs_info, "failed to decompress"); |
60e1975a | 401 | ret = -EIO; |
a6e66e6f | 402 | goto out; |
a6fa6fae LZ |
403 | } |
404 | ||
a6e66e6f QW |
405 | /* Copy the data into inode pages */ |
406 | ret = btrfs_decompress_buf2page(workspace->buf, out_len, cb, cur_out); | |
407 | cur_out += out_len; | |
a6fa6fae | 408 | |
a6e66e6f QW |
409 | /* All data read, exit */ |
410 | if (ret == 0) | |
411 | goto out; | |
412 | ret = 0; | |
413 | ||
414 | /* Check if the sector has enough space for a segment header */ | |
415 | sector_bytes_left = sectorsize - (cur_in % sectorsize); | |
416 | if (sector_bytes_left >= LZO_LEN) | |
417 | continue; | |
418 | ||
419 | /* Skip the padding zeros */ | |
420 | cur_in += sector_bytes_left; | |
a6fa6fae | 421 | } |
a6e66e6f | 422 | out: |
2f19cad9 | 423 | if (!ret) |
1c3dc173 | 424 | zero_fill_bio(cb->orig_bio); |
a6fa6fae LZ |
425 | return ret; |
426 | } | |
427 | ||
c4bf665a DS |
428 | int lzo_decompress(struct list_head *ws, unsigned char *data_in, |
429 | struct page *dest_page, unsigned long start_byte, size_t srclen, | |
430 | size_t destlen) | |
a6fa6fae LZ |
431 | { |
432 | struct workspace *workspace = list_entry(ws, struct workspace, list); | |
433 | size_t in_len; | |
434 | size_t out_len; | |
dc4a4bdb | 435 | size_t max_segment_len = WORKSPACE_BUF_LENGTH; |
a6fa6fae LZ |
436 | int ret = 0; |
437 | char *kaddr; | |
438 | unsigned long bytes; | |
439 | ||
de885e3e QW |
440 | if (srclen < LZO_LEN || srclen > max_segment_len + LZO_LEN * 2) |
441 | return -EUCLEAN; | |
a6fa6fae | 442 | |
de885e3e QW |
443 | in_len = read_compress_length(data_in); |
444 | if (in_len != srclen) | |
445 | return -EUCLEAN; | |
a6fa6fae LZ |
446 | data_in += LZO_LEN; |
447 | ||
448 | in_len = read_compress_length(data_in); | |
de885e3e QW |
449 | if (in_len != srclen - LZO_LEN * 2) { |
450 | ret = -EUCLEAN; | |
451 | goto out; | |
452 | } | |
a6fa6fae LZ |
453 | data_in += LZO_LEN; |
454 | ||
09cbfeaf | 455 | out_len = PAGE_SIZE; |
a6fa6fae LZ |
456 | ret = lzo1x_decompress_safe(data_in, in_len, workspace->buf, &out_len); |
457 | if (ret != LZO_E_OK) { | |
62e85577 | 458 | pr_warn("BTRFS: decompress failed!\n"); |
60e1975a | 459 | ret = -EIO; |
a6fa6fae LZ |
460 | goto out; |
461 | } | |
462 | ||
463 | if (out_len < start_byte) { | |
60e1975a | 464 | ret = -EIO; |
a6fa6fae LZ |
465 | goto out; |
466 | } | |
467 | ||
2f19cad9 CM |
468 | /* |
469 | * the caller is already checking against PAGE_SIZE, but lets | |
470 | * move this check closer to the memcpy/memset | |
471 | */ | |
472 | destlen = min_t(unsigned long, destlen, PAGE_SIZE); | |
a6fa6fae LZ |
473 | bytes = min_t(unsigned long, destlen, out_len - start_byte); |
474 | ||
ccaa66c8 | 475 | kaddr = kmap_local_page(dest_page); |
a6fa6fae | 476 | memcpy(kaddr, workspace->buf + start_byte, bytes); |
2f19cad9 CM |
477 | |
478 | /* | |
479 | * btrfs_getblock is doing a zero on the tail of the page too, | |
480 | * but this will cover anything missing from the decompressed | |
481 | * data. | |
482 | */ | |
483 | if (bytes < destlen) | |
484 | memset(kaddr+bytes, 0, destlen-bytes); | |
ccaa66c8 | 485 | kunmap_local(kaddr); |
a6fa6fae LZ |
486 | out: |
487 | return ret; | |
488 | } | |
489 | ||
e8c9f186 | 490 | const struct btrfs_compress_op btrfs_lzo_compress = { |
be951045 | 491 | .workspace_manager = &wsm, |
e18333a7 DS |
492 | .max_level = 1, |
493 | .default_level = 1, | |
a6fa6fae | 494 | }; |