Line data Source code
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 0 : void lzo_free_workspace(struct list_head *ws)
74 : {
75 0 : struct workspace *workspace = list_entry(ws, struct workspace, list);
76 :
77 0 : kvfree(workspace->buf);
78 0 : kvfree(workspace->cbuf);
79 0 : kvfree(workspace->mem);
80 0 : kfree(workspace);
81 0 : }
82 :
83 2 : struct list_head *lzo_alloc_workspace(unsigned int level)
84 : {
85 2 : struct workspace *workspace;
86 :
87 2 : workspace = kzalloc(sizeof(*workspace), GFP_KERNEL);
88 2 : if (!workspace)
89 : return ERR_PTR(-ENOMEM);
90 :
91 2 : workspace->mem = kvmalloc(LZO1X_MEM_COMPRESS, GFP_KERNEL | __GFP_NOWARN);
92 2 : workspace->buf = kvmalloc(WORKSPACE_BUF_LENGTH, GFP_KERNEL | __GFP_NOWARN);
93 2 : workspace->cbuf = kvmalloc(WORKSPACE_CBUF_LENGTH, GFP_KERNEL | __GFP_NOWARN);
94 2 : if (!workspace->mem || !workspace->buf || !workspace->cbuf)
95 0 : goto fail;
96 :
97 2 : INIT_LIST_HEAD(&workspace->list);
98 :
99 2 : return &workspace->list;
100 : fail:
101 0 : lzo_free_workspace(&workspace->list);
102 0 : return ERR_PTR(-ENOMEM);
103 : }
104 :
105 0 : static inline void write_compress_length(char *buf, size_t len)
106 : {
107 0 : __le32 dlen;
108 :
109 0 : dlen = cpu_to_le32(len);
110 0 : memcpy(buf, &dlen, LZO_LEN);
111 0 : }
112 :
113 0 : static inline size_t read_compress_length(const char *buf)
114 : {
115 0 : __le32 dlen;
116 :
117 0 : memcpy(&dlen, buf, LZO_LEN);
118 0 : 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 0 : 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 0 : u32 sector_bytes_left;
139 0 : u32 orig_out;
140 0 : struct page *cur_page;
141 0 : char *kaddr;
142 :
143 0 : 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 0 : ASSERT((*cur_out / sectorsize) == (*cur_out + LZO_LEN - 1) / sectorsize);
151 :
152 0 : cur_page = out_pages[*cur_out / PAGE_SIZE];
153 : /* Allocate a new page */
154 0 : if (!cur_page) {
155 0 : cur_page = alloc_page(GFP_NOFS);
156 0 : if (!cur_page)
157 : return -ENOMEM;
158 0 : out_pages[*cur_out / PAGE_SIZE] = cur_page;
159 : }
160 :
161 0 : kaddr = kmap_local_page(cur_page);
162 0 : write_compress_length(kaddr + offset_in_page(*cur_out),
163 : compressed_size);
164 0 : *cur_out += LZO_LEN;
165 :
166 0 : orig_out = *cur_out;
167 :
168 : /* Copy compressed data */
169 0 : while (*cur_out - orig_out < compressed_size) {
170 0 : u32 copy_len = min_t(u32, sectorsize - *cur_out % sectorsize,
171 : orig_out + compressed_size - *cur_out);
172 :
173 0 : kunmap_local(kaddr);
174 :
175 0 : if ((*cur_out / PAGE_SIZE) >= max_nr_page)
176 : return -E2BIG;
177 :
178 0 : cur_page = out_pages[*cur_out / PAGE_SIZE];
179 : /* Allocate a new page */
180 0 : if (!cur_page) {
181 0 : cur_page = alloc_page(GFP_NOFS);
182 0 : if (!cur_page)
183 : return -ENOMEM;
184 0 : out_pages[*cur_out / PAGE_SIZE] = cur_page;
185 : }
186 0 : kaddr = kmap_local_page(cur_page);
187 :
188 0 : memcpy(kaddr + offset_in_page(*cur_out),
189 : compressed_data + *cur_out - orig_out, copy_len);
190 :
191 0 : *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 0 : sector_bytes_left = round_up(*cur_out, sectorsize) - *cur_out;
199 0 : if (sector_bytes_left >= LZO_LEN || sector_bytes_left == 0)
200 0 : goto out;
201 :
202 : /* The remaining size is not enough, pad it with zeros */
203 0 : memset(kaddr + offset_in_page(*cur_out), 0,
204 : sector_bytes_left);
205 0 : *cur_out += sector_bytes_left;
206 :
207 : out:
208 : kunmap_local(kaddr);
209 : return 0;
210 : }
211 :
212 0 : 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 0 : struct workspace *workspace = list_entry(ws, struct workspace, list);
217 0 : const u32 sectorsize = btrfs_sb(mapping->host->i_sb)->sectorsize;
218 0 : struct page *page_in = NULL;
219 0 : char *sizes_ptr;
220 0 : const unsigned long max_nr_page = *out_pages;
221 0 : int ret = 0;
222 : /* Points to the file offset of input data */
223 0 : u64 cur_in = start;
224 : /* Points to the current output byte */
225 0 : u32 cur_out = 0;
226 0 : u32 len = *total_out;
227 :
228 0 : ASSERT(max_nr_page > 0);
229 0 : *out_pages = 0;
230 0 : *total_out = 0;
231 0 : *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 0 : cur_out += LZO_LEN;
238 0 : while (cur_in < start + len) {
239 0 : char *data_in;
240 0 : const u32 sectorsize_mask = sectorsize - 1;
241 0 : u32 sector_off = (cur_in - start) & sectorsize_mask;
242 0 : u32 in_len;
243 0 : size_t out_len;
244 :
245 : /* Get the input page first */
246 0 : if (!page_in) {
247 0 : page_in = find_get_page(mapping, cur_in >> PAGE_SHIFT);
248 0 : ASSERT(page_in);
249 : }
250 :
251 : /* Compress at most one sector of data each time */
252 0 : in_len = min_t(u32, start + len - cur_in, sectorsize - sector_off);
253 0 : ASSERT(in_len);
254 0 : data_in = kmap_local_page(page_in);
255 0 : ret = lzo1x_1_compress(data_in +
256 0 : offset_in_page(cur_in), in_len,
257 0 : workspace->cbuf, &out_len,
258 : workspace->mem);
259 0 : kunmap_local(data_in);
260 0 : if (ret < 0) {
261 0 : pr_debug("BTRFS: lzo in loop returned %d\n", ret);
262 0 : ret = -EIO;
263 0 : goto out;
264 : }
265 :
266 0 : ret = copy_compressed_data_to_page(workspace->cbuf, out_len,
267 : pages, max_nr_page,
268 : &cur_out, sectorsize);
269 0 : if (ret < 0)
270 0 : goto out;
271 :
272 0 : 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 0 : if (cur_in - start > sectorsize * 2 && cur_in - start < cur_out) {
279 0 : ret = -E2BIG;
280 0 : goto out;
281 : }
282 :
283 : /* Check if we have reached page boundary */
284 0 : if (PAGE_ALIGNED(cur_in)) {
285 0 : put_page(page_in);
286 0 : page_in = NULL;
287 : }
288 : }
289 :
290 : /* Store the size of all chunks of compressed data */
291 0 : sizes_ptr = kmap_local_page(pages[0]);
292 0 : write_compress_length(sizes_ptr, cur_out);
293 0 : kunmap_local(sizes_ptr);
294 :
295 0 : ret = 0;
296 0 : *total_out = cur_out;
297 0 : *total_in = cur_in - start;
298 0 : out:
299 0 : if (page_in)
300 0 : put_page(page_in);
301 0 : *out_pages = DIV_ROUND_UP(cur_out, PAGE_SIZE);
302 0 : 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 0 : static void copy_compressed_segment(struct compressed_bio *cb,
311 : char *dest, u32 len, u32 *cur_in)
312 : {
313 0 : u32 orig_in = *cur_in;
314 :
315 0 : while (*cur_in < orig_in + len) {
316 0 : struct page *cur_page;
317 0 : u32 copy_len = min_t(u32, PAGE_SIZE - offset_in_page(*cur_in),
318 : orig_in + len - *cur_in);
319 :
320 0 : ASSERT(copy_len);
321 0 : cur_page = cb->compressed_pages[*cur_in / PAGE_SIZE];
322 :
323 0 : memcpy_from_page(dest + *cur_in - orig_in, cur_page,
324 : offset_in_page(*cur_in), copy_len);
325 :
326 0 : *cur_in += copy_len;
327 : }
328 0 : }
329 :
330 0 : int lzo_decompress_bio(struct list_head *ws, struct compressed_bio *cb)
331 : {
332 0 : struct workspace *workspace = list_entry(ws, struct workspace, list);
333 0 : const struct btrfs_fs_info *fs_info = cb->bbio.inode->root->fs_info;
334 0 : const u32 sectorsize = fs_info->sectorsize;
335 0 : char *kaddr;
336 0 : int ret;
337 : /* Compressed data length, can be unaligned */
338 0 : u32 len_in;
339 : /* Offset inside the compressed data */
340 0 : u32 cur_in = 0;
341 : /* Bytes decompressed so far */
342 0 : u32 cur_out = 0;
343 :
344 0 : kaddr = kmap_local_page(cb->compressed_pages[0]);
345 0 : len_in = read_compress_length(kaddr);
346 0 : kunmap_local(kaddr);
347 0 : 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 0 : if (len_in > min_t(size_t, BTRFS_MAX_COMPRESSED, cb->compressed_len) ||
357 0 : round_up(len_in, sectorsize) < cb->compressed_len) {
358 0 : btrfs_err(fs_info,
359 : "invalid lzo header, lzo len %u compressed len %u",
360 : len_in, cb->compressed_len);
361 0 : return -EUCLEAN;
362 : }
363 :
364 : /* Go through each lzo segment */
365 0 : while (cur_in < len_in) {
366 0 : struct page *cur_page;
367 : /* Length of the compressed segment */
368 0 : u32 seg_len;
369 0 : u32 sector_bytes_left;
370 0 : 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 0 : ASSERT(cur_in / sectorsize ==
377 : (cur_in + LZO_LEN - 1) / sectorsize);
378 0 : cur_page = cb->compressed_pages[cur_in / PAGE_SIZE];
379 0 : ASSERT(cur_page);
380 0 : kaddr = kmap_local_page(cur_page);
381 0 : seg_len = read_compress_length(kaddr + offset_in_page(cur_in));
382 0 : kunmap_local(kaddr);
383 0 : cur_in += LZO_LEN;
384 :
385 0 : if (seg_len > WORKSPACE_CBUF_LENGTH) {
386 : /*
387 : * seg_len shouldn't be larger than we have allocated
388 : * for workspace->cbuf
389 : */
390 0 : btrfs_err(fs_info, "unexpectedly large lzo segment len %u",
391 : seg_len);
392 0 : return -EIO;
393 : }
394 :
395 : /* Copy the compressed segment payload into workspace */
396 0 : copy_compressed_segment(cb, workspace->cbuf, seg_len, &cur_in);
397 :
398 : /* Decompress the data */
399 0 : ret = lzo1x_decompress_safe(workspace->cbuf, seg_len,
400 0 : workspace->buf, &out_len);
401 0 : if (ret != LZO_E_OK) {
402 0 : btrfs_err(fs_info, "failed to decompress");
403 0 : return -EIO;
404 : }
405 :
406 : /* Copy the data into inode pages */
407 0 : ret = btrfs_decompress_buf2page(workspace->buf, out_len, cb, cur_out);
408 0 : cur_out += out_len;
409 :
410 : /* All data read, exit */
411 0 : if (ret == 0)
412 : return 0;
413 0 : ret = 0;
414 :
415 : /* Check if the sector has enough space for a segment header */
416 0 : sector_bytes_left = sectorsize - (cur_in % sectorsize);
417 0 : if (sector_bytes_left >= LZO_LEN)
418 0 : continue;
419 :
420 : /* Skip the padding zeros */
421 0 : cur_in += sector_bytes_left;
422 : }
423 :
424 : return 0;
425 : }
426 :
427 0 : 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 0 : struct workspace *workspace = list_entry(ws, struct workspace, list);
432 0 : size_t in_len;
433 0 : size_t out_len;
434 0 : size_t max_segment_len = WORKSPACE_BUF_LENGTH;
435 0 : int ret = 0;
436 0 : char *kaddr;
437 0 : unsigned long bytes;
438 :
439 0 : if (srclen < LZO_LEN || srclen > max_segment_len + LZO_LEN * 2)
440 : return -EUCLEAN;
441 :
442 0 : in_len = read_compress_length(data_in);
443 0 : if (in_len != srclen)
444 : return -EUCLEAN;
445 0 : data_in += LZO_LEN;
446 :
447 0 : in_len = read_compress_length(data_in);
448 0 : if (in_len != srclen - LZO_LEN * 2) {
449 0 : ret = -EUCLEAN;
450 0 : goto out;
451 : }
452 0 : data_in += LZO_LEN;
453 :
454 0 : out_len = PAGE_SIZE;
455 0 : ret = lzo1x_decompress_safe(data_in, in_len, workspace->buf, &out_len);
456 0 : if (ret != LZO_E_OK) {
457 0 : pr_warn("BTRFS: decompress failed!\n");
458 0 : ret = -EIO;
459 0 : goto out;
460 : }
461 :
462 0 : if (out_len < start_byte) {
463 0 : ret = -EIO;
464 0 : 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 0 : destlen = min_t(unsigned long, destlen, PAGE_SIZE);
472 0 : bytes = min_t(unsigned long, destlen, out_len - start_byte);
473 :
474 0 : kaddr = kmap_local_page(dest_page);
475 0 : 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 0 : if (bytes < destlen)
483 0 : 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 : };
|
