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