1 | // SPDX-License-Identifier: GPL-2.0 |
2 | /* |
3 | * Copyright (C) 2008 Oracle. All rights reserved. |
4 | */ |
5 | |
6 | #include <linux/kernel.h> |
7 | #include <linux/slab.h> |
8 | #include <linux/mm.h> |
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> |
15 | #include <linux/refcount.h> |
16 | #include "messages.h" |
17 | #include "compression.h" |
18 | #include "ctree.h" |
19 | #include "super.h" |
20 | #include "btrfs_inode.h" |
21 | |
22 | #define LZO_LEN 4 |
23 | |
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) |
34 | * Variable size. Each segment includes one segment header, followed by data |
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. |
38 | * One segment represents at most one sector of uncompressed data. |
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). |
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. |
45 | * |
46 | * 2.2 Data Payload |
47 | * Variable size. Size up limit should be lzo1x_worst_compress(sectorsize) |
48 | * which is 4419 for a 4KiB sectorsize. |
49 | * |
50 | * Example with 4K sectorsize: |
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 | |
61 | #define WORKSPACE_BUF_LENGTH (lzo1x_worst_compress(PAGE_SIZE)) |
62 | #define WORKSPACE_CBUF_LENGTH (lzo1x_worst_compress(PAGE_SIZE)) |
63 | |
64 | struct workspace { |
65 | void *mem; |
66 | void *buf; /* where decompressed data goes */ |
67 | void *cbuf; /* where compressed data goes */ |
68 | struct list_head list; |
69 | }; |
70 | |
71 | static struct workspace_manager wsm; |
72 | |
73 | void lzo_free_workspace(struct list_head *ws) |
74 | { |
75 | struct workspace *workspace = list_entry(ws, struct workspace, list); |
76 | |
77 | kvfree(addr: workspace->buf); |
78 | kvfree(addr: workspace->cbuf); |
79 | kvfree(addr: workspace->mem); |
80 | kfree(objp: workspace); |
81 | } |
82 | |
83 | struct list_head *lzo_alloc_workspace(unsigned int level) |
84 | { |
85 | struct workspace *workspace; |
86 | |
87 | workspace = kzalloc(size: sizeof(*workspace), GFP_KERNEL); |
88 | if (!workspace) |
89 | return ERR_PTR(error: -ENOMEM); |
90 | |
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); |
94 | if (!workspace->mem || !workspace->buf || !workspace->cbuf) |
95 | goto fail; |
96 | |
97 | INIT_LIST_HEAD(list: &workspace->list); |
98 | |
99 | return &workspace->list; |
100 | fail: |
101 | lzo_free_workspace(ws: &workspace->list); |
102 | return ERR_PTR(error: -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 | |
113 | static inline size_t read_compress_length(const char *buf) |
114 | { |
115 | __le32 dlen; |
116 | |
117 | memcpy(&dlen, buf, LZO_LEN); |
118 | return le32_to_cpu(dlen); |
119 | } |
120 | |
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, |
133 | struct page **out_pages, |
134 | unsigned long max_nr_page, |
135 | u32 *cur_out, |
136 | const u32 sectorsize) |
137 | { |
138 | u32 sector_bytes_left; |
139 | u32 orig_out; |
140 | struct page *cur_page; |
141 | char *kaddr; |
142 | |
143 | if ((*cur_out / PAGE_SIZE) >= max_nr_page) |
144 | return -E2BIG; |
145 | |
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 | |
152 | cur_page = out_pages[*cur_out / PAGE_SIZE]; |
153 | /* Allocate a new page */ |
154 | if (!cur_page) { |
155 | cur_page = alloc_page(GFP_NOFS); |
156 | if (!cur_page) |
157 | return -ENOMEM; |
158 | out_pages[*cur_out / PAGE_SIZE] = cur_page; |
159 | } |
160 | |
161 | kaddr = kmap_local_page(page: cur_page); |
162 | write_compress_length(buf: kaddr + offset_in_page(*cur_out), |
163 | len: 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 | |
173 | kunmap_local(kaddr); |
174 | |
175 | if ((*cur_out / PAGE_SIZE) >= max_nr_page) |
176 | return -E2BIG; |
177 | |
178 | cur_page = out_pages[*cur_out / PAGE_SIZE]; |
179 | /* Allocate a new page */ |
180 | if (!cur_page) { |
181 | cur_page = alloc_page(GFP_NOFS); |
182 | if (!cur_page) |
183 | return -ENOMEM; |
184 | out_pages[*cur_out / PAGE_SIZE] = cur_page; |
185 | } |
186 | kaddr = kmap_local_page(page: cur_page); |
187 | |
188 | memcpy(kaddr + offset_in_page(*cur_out), |
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) |
200 | goto out; |
201 | |
202 | /* The remaining size is not enough, pad it with zeros */ |
203 | memset(kaddr + offset_in_page(*cur_out), 0, |
204 | sector_bytes_left); |
205 | *cur_out += sector_bytes_left; |
206 | |
207 | out: |
208 | kunmap_local(kaddr); |
209 | return 0; |
210 | } |
211 | |
212 | int lzo_compress_pages(struct list_head *ws, struct address_space *mapping, |
213 | u64 start, struct page **pages, unsigned long *out_pages, |
214 | unsigned long *total_in, unsigned long *total_out) |
215 | { |
216 | struct workspace *workspace = list_entry(ws, struct workspace, list); |
217 | const u32 sectorsize = btrfs_sb(sb: mapping->host->i_sb)->sectorsize; |
218 | struct page *page_in = NULL; |
219 | char *sizes_ptr; |
220 | const unsigned long max_nr_page = *out_pages; |
221 | int ret = 0; |
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; |
227 | |
228 | ASSERT(max_nr_page > 0); |
229 | *out_pages = 0; |
230 | *total_out = 0; |
231 | *total_in = 0; |
232 | |
233 | /* |
234 | * Skip the header for now, we will later come back and write the total |
235 | * compressed size |
236 | */ |
237 | cur_out += LZO_LEN; |
238 | while (cur_in < start + len) { |
239 | char *data_in; |
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 */ |
246 | if (!page_in) { |
247 | page_in = find_get_page(mapping, offset: cur_in >> PAGE_SHIFT); |
248 | ASSERT(page_in); |
249 | } |
250 | |
251 | /* Compress at most one sector of data each time */ |
252 | in_len = min_t(u32, start + len - cur_in, sectorsize - sector_off); |
253 | ASSERT(in_len); |
254 | data_in = kmap_local_page(page: page_in); |
255 | ret = lzo1x_1_compress(src: data_in + |
256 | offset_in_page(cur_in), src_len: in_len, |
257 | dst: workspace->cbuf, dst_len: &out_len, |
258 | wrkmem: workspace->mem); |
259 | kunmap_local(data_in); |
260 | if (ret < 0) { |
261 | pr_debug("BTRFS: lzo in loop returned %d\n" , ret); |
262 | ret = -EIO; |
263 | goto out; |
264 | } |
265 | |
266 | ret = copy_compressed_data_to_page(compressed_data: workspace->cbuf, compressed_size: out_len, |
267 | out_pages: pages, max_nr_page, |
268 | cur_out: &cur_out, sectorsize); |
269 | if (ret < 0) |
270 | goto out; |
271 | |
272 | cur_in += in_len; |
273 | |
274 | /* |
275 | * Check if we're making it bigger after two sectors. And if |
276 | * it is so, give up. |
277 | */ |
278 | if (cur_in - start > sectorsize * 2 && cur_in - start < cur_out) { |
279 | ret = -E2BIG; |
280 | goto out; |
281 | } |
282 | |
283 | /* Check if we have reached page boundary */ |
284 | if (PAGE_ALIGNED(cur_in)) { |
285 | put_page(page: page_in); |
286 | page_in = NULL; |
287 | } |
288 | } |
289 | |
290 | /* Store the size of all chunks of compressed data */ |
291 | sizes_ptr = kmap_local_page(page: pages[0]); |
292 | write_compress_length(buf: sizes_ptr, len: cur_out); |
293 | kunmap_local(sizes_ptr); |
294 | |
295 | ret = 0; |
296 | *total_out = cur_out; |
297 | *total_in = cur_in - start; |
298 | out: |
299 | if (page_in) |
300 | put_page(page: page_in); |
301 | *out_pages = DIV_ROUND_UP(cur_out, PAGE_SIZE); |
302 | return ret; |
303 | } |
304 | |
305 | /* |
306 | * Copy the compressed segment payload into @dest. |
307 | * |
308 | * For the payload there will be no padding, just need to do page switching. |
309 | */ |
310 | static void copy_compressed_segment(struct compressed_bio *cb, |
311 | char *dest, u32 len, u32 *cur_in) |
312 | { |
313 | u32 orig_in = *cur_in; |
314 | |
315 | while (*cur_in < orig_in + len) { |
316 | struct page *cur_page; |
317 | u32 copy_len = min_t(u32, PAGE_SIZE - offset_in_page(*cur_in), |
318 | orig_in + len - *cur_in); |
319 | |
320 | ASSERT(copy_len); |
321 | cur_page = cb->compressed_pages[*cur_in / PAGE_SIZE]; |
322 | |
323 | memcpy_from_page(to: dest + *cur_in - orig_in, page: cur_page, |
324 | offset_in_page(*cur_in), len: copy_len); |
325 | |
326 | *cur_in += copy_len; |
327 | } |
328 | } |
329 | |
330 | int lzo_decompress_bio(struct list_head *ws, struct compressed_bio *cb) |
331 | { |
332 | struct workspace *workspace = list_entry(ws, struct workspace, list); |
333 | const struct btrfs_fs_info *fs_info = cb->bbio.inode->root->fs_info; |
334 | const u32 sectorsize = fs_info->sectorsize; |
335 | char *kaddr; |
336 | int ret; |
337 | /* Compressed data length, can be unaligned */ |
338 | u32 len_in; |
339 | /* Offset inside the compressed data */ |
340 | u32 cur_in = 0; |
341 | /* Bytes decompressed so far */ |
342 | u32 cur_out = 0; |
343 | |
344 | kaddr = kmap_local_page(page: cb->compressed_pages[0]); |
345 | len_in = read_compress_length(buf: kaddr); |
346 | kunmap_local(kaddr); |
347 | cur_in += LZO_LEN; |
348 | |
349 | /* |
350 | * LZO header length check |
351 | * |
352 | * The total length should not exceed the maximum extent length, |
353 | * and all sectors should be used. |
354 | * If this happens, it means the compressed extent is corrupted. |
355 | */ |
356 | if (len_in > min_t(size_t, BTRFS_MAX_COMPRESSED, cb->compressed_len) || |
357 | round_up(len_in, sectorsize) < cb->compressed_len) { |
358 | btrfs_err(fs_info, |
359 | "invalid lzo header, lzo len %u compressed len %u" , |
360 | len_in, cb->compressed_len); |
361 | return -EUCLEAN; |
362 | } |
363 | |
364 | /* Go through each lzo segment */ |
365 | while (cur_in < len_in) { |
366 | struct page *cur_page; |
367 | /* Length of the compressed segment */ |
368 | u32 seg_len; |
369 | u32 sector_bytes_left; |
370 | size_t out_len = lzo1x_worst_compress(sectorsize); |
371 | |
372 | /* |
373 | * We should always have enough space for one segment header |
374 | * inside current sector. |
375 | */ |
376 | ASSERT(cur_in / sectorsize == |
377 | (cur_in + LZO_LEN - 1) / sectorsize); |
378 | cur_page = cb->compressed_pages[cur_in / PAGE_SIZE]; |
379 | ASSERT(cur_page); |
380 | kaddr = kmap_local_page(page: cur_page); |
381 | seg_len = read_compress_length(buf: kaddr + offset_in_page(cur_in)); |
382 | kunmap_local(kaddr); |
383 | cur_in += LZO_LEN; |
384 | |
385 | if (seg_len > WORKSPACE_CBUF_LENGTH) { |
386 | /* |
387 | * seg_len shouldn't be larger than we have allocated |
388 | * for workspace->cbuf |
389 | */ |
390 | btrfs_err(fs_info, "unexpectedly large lzo segment len %u" , |
391 | seg_len); |
392 | return -EIO; |
393 | } |
394 | |
395 | /* Copy the compressed segment payload into workspace */ |
396 | copy_compressed_segment(cb, dest: workspace->cbuf, len: seg_len, cur_in: &cur_in); |
397 | |
398 | /* Decompress the data */ |
399 | ret = lzo1x_decompress_safe(src: workspace->cbuf, src_len: seg_len, |
400 | dst: workspace->buf, dst_len: &out_len); |
401 | if (ret != LZO_E_OK) { |
402 | btrfs_err(fs_info, "failed to decompress" ); |
403 | return -EIO; |
404 | } |
405 | |
406 | /* Copy the data into inode pages */ |
407 | ret = btrfs_decompress_buf2page(buf: workspace->buf, buf_len: out_len, cb, decompressed: cur_out); |
408 | cur_out += out_len; |
409 | |
410 | /* All data read, exit */ |
411 | if (ret == 0) |
412 | return 0; |
413 | ret = 0; |
414 | |
415 | /* Check if the sector has enough space for a segment header */ |
416 | sector_bytes_left = sectorsize - (cur_in % sectorsize); |
417 | if (sector_bytes_left >= LZO_LEN) |
418 | continue; |
419 | |
420 | /* Skip the padding zeros */ |
421 | cur_in += sector_bytes_left; |
422 | } |
423 | |
424 | return 0; |
425 | } |
426 | |
427 | int lzo_decompress(struct list_head *ws, const u8 *data_in, |
428 | struct page *dest_page, unsigned long start_byte, size_t srclen, |
429 | size_t destlen) |
430 | { |
431 | struct workspace *workspace = list_entry(ws, struct workspace, list); |
432 | size_t in_len; |
433 | size_t out_len; |
434 | size_t max_segment_len = WORKSPACE_BUF_LENGTH; |
435 | int ret = 0; |
436 | char *kaddr; |
437 | unsigned long bytes; |
438 | |
439 | if (srclen < LZO_LEN || srclen > max_segment_len + LZO_LEN * 2) |
440 | return -EUCLEAN; |
441 | |
442 | in_len = read_compress_length(buf: data_in); |
443 | if (in_len != srclen) |
444 | return -EUCLEAN; |
445 | data_in += LZO_LEN; |
446 | |
447 | in_len = read_compress_length(buf: data_in); |
448 | if (in_len != srclen - LZO_LEN * 2) { |
449 | ret = -EUCLEAN; |
450 | goto out; |
451 | } |
452 | data_in += LZO_LEN; |
453 | |
454 | out_len = PAGE_SIZE; |
455 | ret = lzo1x_decompress_safe(src: data_in, src_len: in_len, dst: workspace->buf, dst_len: &out_len); |
456 | if (ret != LZO_E_OK) { |
457 | pr_warn("BTRFS: decompress failed!\n" ); |
458 | ret = -EIO; |
459 | goto out; |
460 | } |
461 | |
462 | if (out_len < start_byte) { |
463 | ret = -EIO; |
464 | goto out; |
465 | } |
466 | |
467 | /* |
468 | * the caller is already checking against PAGE_SIZE, but lets |
469 | * move this check closer to the memcpy/memset |
470 | */ |
471 | destlen = min_t(unsigned long, destlen, PAGE_SIZE); |
472 | bytes = min_t(unsigned long, destlen, out_len - start_byte); |
473 | |
474 | kaddr = kmap_local_page(page: dest_page); |
475 | memcpy(kaddr, workspace->buf + start_byte, bytes); |
476 | |
477 | /* |
478 | * btrfs_getblock is doing a zero on the tail of the page too, |
479 | * but this will cover anything missing from the decompressed |
480 | * data. |
481 | */ |
482 | if (bytes < destlen) |
483 | memset(kaddr+bytes, 0, destlen-bytes); |
484 | kunmap_local(kaddr); |
485 | out: |
486 | return ret; |
487 | } |
488 | |
489 | const struct btrfs_compress_op btrfs_lzo_compress = { |
490 | .workspace_manager = &wsm, |
491 | .max_level = 1, |
492 | .default_level = 1, |
493 | }; |
494 | |