]>
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 | ||
a6fa6fae LZ |
58 | struct workspace { |
59 | void *mem; | |
3fb40375 JL |
60 | void *buf; /* where decompressed data goes */ |
61 | void *cbuf; /* where compressed data goes */ | |
a6fa6fae LZ |
62 | struct list_head list; |
63 | }; | |
64 | ||
92ee5530 DZ |
65 | static struct workspace_manager wsm; |
66 | ||
d20f395f | 67 | void lzo_free_workspace(struct list_head *ws) |
a6fa6fae LZ |
68 | { |
69 | struct workspace *workspace = list_entry(ws, struct workspace, list); | |
70 | ||
6acafd1e DS |
71 | kvfree(workspace->buf); |
72 | kvfree(workspace->cbuf); | |
73 | kvfree(workspace->mem); | |
a6fa6fae LZ |
74 | kfree(workspace); |
75 | } | |
76 | ||
d20f395f | 77 | struct list_head *lzo_alloc_workspace(unsigned int level) |
a6fa6fae LZ |
78 | { |
79 | struct workspace *workspace; | |
80 | ||
389a6cfc | 81 | workspace = kzalloc(sizeof(*workspace), GFP_KERNEL); |
a6fa6fae LZ |
82 | if (!workspace) |
83 | return ERR_PTR(-ENOMEM); | |
84 | ||
6acafd1e DS |
85 | workspace->mem = kvmalloc(LZO1X_MEM_COMPRESS, GFP_KERNEL); |
86 | workspace->buf = kvmalloc(lzo1x_worst_compress(PAGE_SIZE), GFP_KERNEL); | |
87 | workspace->cbuf = kvmalloc(lzo1x_worst_compress(PAGE_SIZE), GFP_KERNEL); | |
a6fa6fae LZ |
88 | if (!workspace->mem || !workspace->buf || !workspace->cbuf) |
89 | goto fail; | |
90 | ||
91 | INIT_LIST_HEAD(&workspace->list); | |
92 | ||
93 | return &workspace->list; | |
94 | fail: | |
95 | lzo_free_workspace(&workspace->list); | |
96 | return ERR_PTR(-ENOMEM); | |
97 | } | |
98 | ||
99 | static inline void write_compress_length(char *buf, size_t len) | |
100 | { | |
101 | __le32 dlen; | |
102 | ||
103 | dlen = cpu_to_le32(len); | |
104 | memcpy(buf, &dlen, LZO_LEN); | |
105 | } | |
106 | ||
14a3357b | 107 | static inline size_t read_compress_length(const char *buf) |
a6fa6fae LZ |
108 | { |
109 | __le32 dlen; | |
110 | ||
111 | memcpy(&dlen, buf, LZO_LEN); | |
112 | return le32_to_cpu(dlen); | |
113 | } | |
114 | ||
d4088803 QW |
115 | /* |
116 | * Will do: | |
117 | * | |
118 | * - Write a segment header into the destination | |
119 | * - Copy the compressed buffer into the destination | |
120 | * - Make sure we have enough space in the last sector to fit a segment header | |
121 | * If not, we will pad at most (LZO_LEN (4)) - 1 bytes of zeros. | |
122 | * | |
123 | * Will allocate new pages when needed. | |
124 | */ | |
125 | static int copy_compressed_data_to_page(char *compressed_data, | |
126 | size_t compressed_size, | |
127 | struct page **out_pages, | |
6f019c0e | 128 | unsigned long max_nr_page, |
d4088803 QW |
129 | u32 *cur_out, |
130 | const u32 sectorsize) | |
131 | { | |
132 | u32 sector_bytes_left; | |
133 | u32 orig_out; | |
134 | struct page *cur_page; | |
135 | ||
6f019c0e QW |
136 | if ((*cur_out / PAGE_SIZE) >= max_nr_page) |
137 | return -E2BIG; | |
138 | ||
d4088803 QW |
139 | /* |
140 | * We never allow a segment header crossing sector boundary, previous | |
141 | * run should ensure we have enough space left inside the sector. | |
142 | */ | |
143 | ASSERT((*cur_out / sectorsize) == (*cur_out + LZO_LEN - 1) / sectorsize); | |
144 | ||
145 | cur_page = out_pages[*cur_out / PAGE_SIZE]; | |
146 | /* Allocate a new page */ | |
147 | if (!cur_page) { | |
148 | cur_page = alloc_page(GFP_NOFS); | |
149 | if (!cur_page) | |
150 | return -ENOMEM; | |
151 | out_pages[*cur_out / PAGE_SIZE] = cur_page; | |
152 | } | |
153 | ||
154 | write_compress_length(page_address(cur_page) + offset_in_page(*cur_out), | |
155 | compressed_size); | |
156 | *cur_out += LZO_LEN; | |
157 | ||
158 | orig_out = *cur_out; | |
159 | ||
160 | /* Copy compressed data */ | |
161 | while (*cur_out - orig_out < compressed_size) { | |
162 | u32 copy_len = min_t(u32, sectorsize - *cur_out % sectorsize, | |
163 | orig_out + compressed_size - *cur_out); | |
164 | ||
6f019c0e QW |
165 | if ((*cur_out / PAGE_SIZE) >= max_nr_page) |
166 | return -E2BIG; | |
167 | ||
d4088803 QW |
168 | cur_page = out_pages[*cur_out / PAGE_SIZE]; |
169 | /* Allocate a new page */ | |
170 | if (!cur_page) { | |
171 | cur_page = alloc_page(GFP_NOFS); | |
172 | if (!cur_page) | |
173 | return -ENOMEM; | |
174 | out_pages[*cur_out / PAGE_SIZE] = cur_page; | |
175 | } | |
176 | ||
177 | memcpy(page_address(cur_page) + offset_in_page(*cur_out), | |
178 | compressed_data + *cur_out - orig_out, copy_len); | |
179 | ||
180 | *cur_out += copy_len; | |
181 | } | |
182 | ||
183 | /* | |
184 | * Check if we can fit the next segment header into the remaining space | |
185 | * of the sector. | |
186 | */ | |
187 | sector_bytes_left = round_up(*cur_out, sectorsize) - *cur_out; | |
188 | if (sector_bytes_left >= LZO_LEN || sector_bytes_left == 0) | |
189 | return 0; | |
190 | ||
191 | /* The remaining size is not enough, pad it with zeros */ | |
192 | memset(page_address(cur_page) + offset_in_page(*cur_out), 0, | |
193 | sector_bytes_left); | |
194 | *cur_out += sector_bytes_left; | |
195 | return 0; | |
196 | } | |
197 | ||
c4bf665a DS |
198 | int lzo_compress_pages(struct list_head *ws, struct address_space *mapping, |
199 | u64 start, struct page **pages, unsigned long *out_pages, | |
200 | unsigned long *total_in, unsigned long *total_out) | |
a6fa6fae LZ |
201 | { |
202 | struct workspace *workspace = list_entry(ws, struct workspace, list); | |
d4088803 QW |
203 | const u32 sectorsize = btrfs_sb(mapping->host->i_sb)->sectorsize; |
204 | struct page *page_in = NULL; | |
6f019c0e | 205 | const unsigned long max_nr_page = *out_pages; |
a6fa6fae | 206 | int ret = 0; |
d4088803 QW |
207 | /* Points to the file offset of input data */ |
208 | u64 cur_in = start; | |
209 | /* Points to the current output byte */ | |
210 | u32 cur_out = 0; | |
211 | u32 len = *total_out; | |
a6fa6fae | 212 | |
6f019c0e | 213 | ASSERT(max_nr_page > 0); |
a6fa6fae LZ |
214 | *out_pages = 0; |
215 | *total_out = 0; | |
216 | *total_in = 0; | |
217 | ||
a6fa6fae | 218 | /* |
d4088803 QW |
219 | * Skip the header for now, we will later come back and write the total |
220 | * compressed size | |
a6fa6fae | 221 | */ |
d4088803 QW |
222 | cur_out += LZO_LEN; |
223 | while (cur_in < start + len) { | |
224 | const u32 sectorsize_mask = sectorsize - 1; | |
225 | u32 sector_off = (cur_in - start) & sectorsize_mask; | |
226 | u32 in_len; | |
227 | size_t out_len; | |
228 | ||
229 | /* Get the input page first */ | |
230 | if (!page_in) { | |
231 | page_in = find_get_page(mapping, cur_in >> PAGE_SHIFT); | |
232 | ASSERT(page_in); | |
233 | } | |
234 | ||
235 | /* Compress at most one sector of data each time */ | |
236 | in_len = min_t(u32, start + len - cur_in, sectorsize - sector_off); | |
237 | ASSERT(in_len); | |
238 | ret = lzo1x_1_compress(page_address(page_in) + | |
239 | offset_in_page(cur_in), in_len, | |
240 | workspace->cbuf, &out_len, | |
241 | workspace->mem); | |
242 | if (ret < 0) { | |
243 | pr_debug("BTRFS: lzo in loop returned %d\n", ret); | |
60e1975a | 244 | ret = -EIO; |
a6fa6fae LZ |
245 | goto out; |
246 | } | |
247 | ||
d4088803 | 248 | ret = copy_compressed_data_to_page(workspace->cbuf, out_len, |
6f019c0e QW |
249 | pages, max_nr_page, |
250 | &cur_out, sectorsize); | |
d4088803 QW |
251 | if (ret < 0) |
252 | goto out; | |
a6fa6fae | 253 | |
d4088803 QW |
254 | cur_in += in_len; |
255 | ||
256 | /* | |
257 | * Check if we're making it bigger after two sectors. And if | |
258 | * it is so, give up. | |
259 | */ | |
260 | if (cur_in - start > sectorsize * 2 && cur_in - start < cur_out) { | |
60e1975a | 261 | ret = -E2BIG; |
a6fa6fae | 262 | goto out; |
59516f60 | 263 | } |
a6fa6fae | 264 | |
d4088803 QW |
265 | /* Check if we have reached page boundary */ |
266 | if (IS_ALIGNED(cur_in, PAGE_SIZE)) { | |
267 | put_page(page_in); | |
268 | page_in = NULL; | |
269 | } | |
1e9d7291 | 270 | } |
a6fa6fae | 271 | |
d4088803 QW |
272 | /* Store the size of all chunks of compressed data */ |
273 | write_compress_length(page_address(pages[0]), cur_out); | |
a6fa6fae LZ |
274 | |
275 | ret = 0; | |
d4088803 QW |
276 | *total_out = cur_out; |
277 | *total_in = cur_in - start; | |
a6fa6fae | 278 | out: |
d4088803 | 279 | *out_pages = DIV_ROUND_UP(cur_out, PAGE_SIZE); |
a6fa6fae LZ |
280 | return ret; |
281 | } | |
282 | ||
a6e66e6f QW |
283 | /* |
284 | * Copy the compressed segment payload into @dest. | |
285 | * | |
286 | * For the payload there will be no padding, just need to do page switching. | |
287 | */ | |
288 | static void copy_compressed_segment(struct compressed_bio *cb, | |
289 | char *dest, u32 len, u32 *cur_in) | |
290 | { | |
291 | u32 orig_in = *cur_in; | |
292 | ||
293 | while (*cur_in < orig_in + len) { | |
294 | struct page *cur_page; | |
295 | u32 copy_len = min_t(u32, PAGE_SIZE - offset_in_page(*cur_in), | |
296 | orig_in + len - *cur_in); | |
297 | ||
298 | ASSERT(copy_len); | |
299 | cur_page = cb->compressed_pages[*cur_in / PAGE_SIZE]; | |
300 | ||
301 | memcpy(dest + *cur_in - orig_in, | |
302 | page_address(cur_page) + offset_in_page(*cur_in), | |
303 | copy_len); | |
304 | ||
305 | *cur_in += copy_len; | |
306 | } | |
307 | } | |
308 | ||
c4bf665a | 309 | int lzo_decompress_bio(struct list_head *ws, struct compressed_bio *cb) |
a6fa6fae LZ |
310 | { |
311 | struct workspace *workspace = list_entry(ws, struct workspace, list); | |
a6e66e6f QW |
312 | const struct btrfs_fs_info *fs_info = btrfs_sb(cb->inode->i_sb); |
313 | const u32 sectorsize = fs_info->sectorsize; | |
314 | int ret; | |
315 | /* Compressed data length, can be unaligned */ | |
316 | u32 len_in; | |
317 | /* Offset inside the compressed data */ | |
318 | u32 cur_in = 0; | |
319 | /* Bytes decompressed so far */ | |
320 | u32 cur_out = 0; | |
321 | ||
322 | len_in = read_compress_length(page_address(cb->compressed_pages[0])); | |
323 | cur_in += LZO_LEN; | |
a6fa6fae | 324 | |
314bfa47 | 325 | /* |
a6e66e6f | 326 | * LZO header length check |
314bfa47 | 327 | * |
a6e66e6f QW |
328 | * The total length should not exceed the maximum extent length, |
329 | * and all sectors should be used. | |
330 | * If this happens, it means the compressed extent is corrupted. | |
314bfa47 | 331 | */ |
a6e66e6f QW |
332 | if (len_in > min_t(size_t, BTRFS_MAX_COMPRESSED, cb->compressed_len) || |
333 | round_up(len_in, sectorsize) < cb->compressed_len) { | |
334 | btrfs_err(fs_info, | |
335 | "invalid lzo header, lzo len %u compressed len %u", | |
336 | len_in, cb->compressed_len); | |
337 | return -EUCLEAN; | |
314bfa47 | 338 | } |
a6fa6fae | 339 | |
a6e66e6f QW |
340 | /* Go through each lzo segment */ |
341 | while (cur_in < len_in) { | |
342 | struct page *cur_page; | |
343 | /* Length of the compressed segment */ | |
344 | u32 seg_len; | |
345 | u32 sector_bytes_left; | |
346 | size_t out_len = lzo1x_worst_compress(sectorsize); | |
a6fa6fae | 347 | |
314bfa47 | 348 | /* |
a6e66e6f QW |
349 | * We should always have enough space for one segment header |
350 | * inside current sector. | |
314bfa47 | 351 | */ |
a6e66e6f QW |
352 | ASSERT(cur_in / sectorsize == |
353 | (cur_in + LZO_LEN - 1) / sectorsize); | |
354 | cur_page = cb->compressed_pages[cur_in / PAGE_SIZE]; | |
355 | ASSERT(cur_page); | |
356 | seg_len = read_compress_length(page_address(cur_page) + | |
357 | offset_in_page(cur_in)); | |
358 | cur_in += LZO_LEN; | |
359 | ||
360 | /* Copy the compressed segment payload into workspace */ | |
361 | copy_compressed_segment(cb, workspace->cbuf, seg_len, &cur_in); | |
362 | ||
363 | /* Decompress the data */ | |
364 | ret = lzo1x_decompress_safe(workspace->cbuf, seg_len, | |
365 | workspace->buf, &out_len); | |
a6fa6fae | 366 | if (ret != LZO_E_OK) { |
a6e66e6f | 367 | btrfs_err(fs_info, "failed to decompress"); |
60e1975a | 368 | ret = -EIO; |
a6e66e6f | 369 | goto out; |
a6fa6fae LZ |
370 | } |
371 | ||
a6e66e6f QW |
372 | /* Copy the data into inode pages */ |
373 | ret = btrfs_decompress_buf2page(workspace->buf, out_len, cb, cur_out); | |
374 | cur_out += out_len; | |
a6fa6fae | 375 | |
a6e66e6f QW |
376 | /* All data read, exit */ |
377 | if (ret == 0) | |
378 | goto out; | |
379 | ret = 0; | |
380 | ||
381 | /* Check if the sector has enough space for a segment header */ | |
382 | sector_bytes_left = sectorsize - (cur_in % sectorsize); | |
383 | if (sector_bytes_left >= LZO_LEN) | |
384 | continue; | |
385 | ||
386 | /* Skip the padding zeros */ | |
387 | cur_in += sector_bytes_left; | |
a6fa6fae | 388 | } |
a6e66e6f | 389 | out: |
2f19cad9 | 390 | if (!ret) |
1c3dc173 | 391 | zero_fill_bio(cb->orig_bio); |
a6fa6fae LZ |
392 | return ret; |
393 | } | |
394 | ||
c4bf665a DS |
395 | int lzo_decompress(struct list_head *ws, unsigned char *data_in, |
396 | struct page *dest_page, unsigned long start_byte, size_t srclen, | |
397 | size_t destlen) | |
a6fa6fae LZ |
398 | { |
399 | struct workspace *workspace = list_entry(ws, struct workspace, list); | |
400 | size_t in_len; | |
401 | size_t out_len; | |
de885e3e | 402 | size_t max_segment_len = lzo1x_worst_compress(PAGE_SIZE); |
a6fa6fae LZ |
403 | int ret = 0; |
404 | char *kaddr; | |
405 | unsigned long bytes; | |
406 | ||
de885e3e QW |
407 | if (srclen < LZO_LEN || srclen > max_segment_len + LZO_LEN * 2) |
408 | return -EUCLEAN; | |
a6fa6fae | 409 | |
de885e3e QW |
410 | in_len = read_compress_length(data_in); |
411 | if (in_len != srclen) | |
412 | return -EUCLEAN; | |
a6fa6fae LZ |
413 | data_in += LZO_LEN; |
414 | ||
415 | in_len = read_compress_length(data_in); | |
de885e3e QW |
416 | if (in_len != srclen - LZO_LEN * 2) { |
417 | ret = -EUCLEAN; | |
418 | goto out; | |
419 | } | |
a6fa6fae LZ |
420 | data_in += LZO_LEN; |
421 | ||
09cbfeaf | 422 | out_len = PAGE_SIZE; |
a6fa6fae LZ |
423 | ret = lzo1x_decompress_safe(data_in, in_len, workspace->buf, &out_len); |
424 | if (ret != LZO_E_OK) { | |
62e85577 | 425 | pr_warn("BTRFS: decompress failed!\n"); |
60e1975a | 426 | ret = -EIO; |
a6fa6fae LZ |
427 | goto out; |
428 | } | |
429 | ||
430 | if (out_len < start_byte) { | |
60e1975a | 431 | ret = -EIO; |
a6fa6fae LZ |
432 | goto out; |
433 | } | |
434 | ||
2f19cad9 CM |
435 | /* |
436 | * the caller is already checking against PAGE_SIZE, but lets | |
437 | * move this check closer to the memcpy/memset | |
438 | */ | |
439 | destlen = min_t(unsigned long, destlen, PAGE_SIZE); | |
a6fa6fae LZ |
440 | bytes = min_t(unsigned long, destlen, out_len - start_byte); |
441 | ||
8c945d32 | 442 | kaddr = page_address(dest_page); |
a6fa6fae | 443 | memcpy(kaddr, workspace->buf + start_byte, bytes); |
2f19cad9 CM |
444 | |
445 | /* | |
446 | * btrfs_getblock is doing a zero on the tail of the page too, | |
447 | * but this will cover anything missing from the decompressed | |
448 | * data. | |
449 | */ | |
450 | if (bytes < destlen) | |
451 | memset(kaddr+bytes, 0, destlen-bytes); | |
a6fa6fae LZ |
452 | out: |
453 | return ret; | |
454 | } | |
455 | ||
e8c9f186 | 456 | const struct btrfs_compress_op btrfs_lzo_compress = { |
be951045 | 457 | .workspace_manager = &wsm, |
e18333a7 DS |
458 | .max_level = 1, |
459 | .default_level = 1, | |
a6fa6fae | 460 | }; |