1 // SPDX-License-Identifier: GPL-2.0
3 * Copyright (C) 2008 Oracle. All rights reserved.
6 #include <linux/kernel.h>
7 #include <linux/slab.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 "compression.h"
22 * Btrfs LZO compression format
24 * Regular and inlined LZO compressed data extents consist of:
27 * Fixed size. LZO_LEN (4) bytes long, LE32.
28 * Records the total size (including the header) of compressed data.
31 * Variable size. Each segment includes one segment header, followed by data
33 * One regular LZO compressed extent can have one or more segments.
34 * For inlined LZO compressed extent, only one segment is allowed.
35 * One segment represents at most one page of uncompressed data.
38 * Fixed size. LZO_LEN (4) bytes long, LE32.
39 * Records the total size of the segment (not including the header).
40 * Segment header never crosses page boundary, thus it's possible to
41 * have at most 3 padding zeros at the end of the page.
44 * Variable size. Size up limit should be lzo1x_worst_compress(PAGE_SIZE)
45 * which is 4419 for a 4KiB page.
49 * 0 0x2 0x4 0x6 0x8 0xa 0xc 0xe 0x10
50 * 0x0000 | Header | SegHdr 01 | Data payload 01 ... |
52 * 0x0ff0 | SegHdr N | Data payload N ... |00|
55 * 0x1000 | SegHdr N+1| Data payload N+1 ... |
60 void *buf; /* where decompressed data goes */
61 void *cbuf; /* where compressed data goes */
62 struct list_head list;
65 static struct workspace_manager wsm;
67 void lzo_free_workspace(struct list_head *ws)
69 struct workspace *workspace = list_entry(ws, struct workspace, list);
71 kvfree(workspace->buf);
72 kvfree(workspace->cbuf);
73 kvfree(workspace->mem);
77 struct list_head *lzo_alloc_workspace(unsigned int level)
79 struct workspace *workspace;
81 workspace = kzalloc(sizeof(*workspace), GFP_KERNEL);
83 return ERR_PTR(-ENOMEM);
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);
88 if (!workspace->mem || !workspace->buf || !workspace->cbuf)
91 INIT_LIST_HEAD(&workspace->list);
93 return &workspace->list;
95 lzo_free_workspace(&workspace->list);
96 return ERR_PTR(-ENOMEM);
99 static inline void write_compress_length(char *buf, size_t len)
103 dlen = cpu_to_le32(len);
104 memcpy(buf, &dlen, LZO_LEN);
107 static inline size_t read_compress_length(const char *buf)
111 memcpy(&dlen, buf, LZO_LEN);
112 return le32_to_cpu(dlen);
115 int lzo_compress_pages(struct list_head *ws, struct address_space *mapping,
116 u64 start, struct page **pages, unsigned long *out_pages,
117 unsigned long *total_in, unsigned long *total_out)
119 struct workspace *workspace = list_entry(ws, struct workspace, list);
122 char *cpage_out, *sizes_ptr;
124 struct page *in_page = NULL;
125 struct page *out_page = NULL;
126 unsigned long bytes_left;
127 unsigned long len = *total_out;
128 unsigned long nr_dest_pages = *out_pages;
129 const unsigned long max_out = nr_dest_pages * PAGE_SIZE;
133 unsigned long tot_in = 0;
134 unsigned long tot_out = 0;
135 unsigned long pg_bytes_left;
136 unsigned long out_offset;
143 in_page = find_get_page(mapping, start >> PAGE_SHIFT);
144 data_in = page_address(in_page);
147 * store the size of all chunks of compressed data in
150 out_page = alloc_page(GFP_NOFS);
151 if (out_page == NULL) {
155 cpage_out = page_address(out_page);
156 out_offset = LZO_LEN;
160 pg_bytes_left = PAGE_SIZE - LZO_LEN;
162 /* compress at most one page of data each time */
163 in_len = min(len, PAGE_SIZE);
164 while (tot_in < len) {
165 ret = lzo1x_1_compress(data_in, in_len, workspace->cbuf,
166 &out_len, workspace->mem);
167 if (ret != LZO_E_OK) {
168 pr_debug("BTRFS: lzo in loop returned %d\n",
174 /* store the size of this chunk of compressed data */
175 write_compress_length(cpage_out + out_offset, out_len);
177 out_offset += LZO_LEN;
178 pg_bytes_left -= LZO_LEN;
183 /* copy bytes from the working buffer into the pages */
184 buf = workspace->cbuf;
186 bytes = min_t(unsigned long, pg_bytes_left, out_len);
188 memcpy(cpage_out + out_offset, buf, bytes);
191 pg_bytes_left -= bytes;
196 * we need another page for writing out.
198 * Note if there's less than 4 bytes left, we just
199 * skip to a new page.
201 if ((out_len == 0 && pg_bytes_left < LZO_LEN) ||
202 pg_bytes_left == 0) {
204 memset(cpage_out + out_offset, 0,
206 tot_out += pg_bytes_left;
209 /* we're done, don't allocate new page */
210 if (out_len == 0 && tot_in >= len)
213 if (nr_pages == nr_dest_pages) {
219 out_page = alloc_page(GFP_NOFS);
220 if (out_page == NULL) {
224 cpage_out = page_address(out_page);
225 pages[nr_pages++] = out_page;
227 pg_bytes_left = PAGE_SIZE;
232 /* we're making it bigger, give up */
233 if (tot_in > 8192 && tot_in < tot_out) {
242 if (tot_out > max_out)
245 bytes_left = len - tot_in;
249 in_page = find_get_page(mapping, start >> PAGE_SHIFT);
250 data_in = page_address(in_page);
251 in_len = min(bytes_left, PAGE_SIZE);
254 if (tot_out >= tot_in) {
259 /* store the size of all chunks of compressed data */
260 sizes_ptr = page_address(pages[0]);
261 write_compress_length(sizes_ptr, tot_out);
264 *total_out = tot_out;
267 *out_pages = nr_pages;
276 * Copy the compressed segment payload into @dest.
278 * For the payload there will be no padding, just need to do page switching.
280 static void copy_compressed_segment(struct compressed_bio *cb,
281 char *dest, u32 len, u32 *cur_in)
283 u32 orig_in = *cur_in;
285 while (*cur_in < orig_in + len) {
286 struct page *cur_page;
287 u32 copy_len = min_t(u32, PAGE_SIZE - offset_in_page(*cur_in),
288 orig_in + len - *cur_in);
291 cur_page = cb->compressed_pages[*cur_in / PAGE_SIZE];
293 memcpy(dest + *cur_in - orig_in,
294 page_address(cur_page) + offset_in_page(*cur_in),
301 int lzo_decompress_bio(struct list_head *ws, struct compressed_bio *cb)
303 struct workspace *workspace = list_entry(ws, struct workspace, list);
304 const struct btrfs_fs_info *fs_info = btrfs_sb(cb->inode->i_sb);
305 const u32 sectorsize = fs_info->sectorsize;
307 /* Compressed data length, can be unaligned */
309 /* Offset inside the compressed data */
311 /* Bytes decompressed so far */
314 len_in = read_compress_length(page_address(cb->compressed_pages[0]));
318 * LZO header length check
320 * The total length should not exceed the maximum extent length,
321 * and all sectors should be used.
322 * If this happens, it means the compressed extent is corrupted.
324 if (len_in > min_t(size_t, BTRFS_MAX_COMPRESSED, cb->compressed_len) ||
325 round_up(len_in, sectorsize) < cb->compressed_len) {
327 "invalid lzo header, lzo len %u compressed len %u",
328 len_in, cb->compressed_len);
332 /* Go through each lzo segment */
333 while (cur_in < len_in) {
334 struct page *cur_page;
335 /* Length of the compressed segment */
337 u32 sector_bytes_left;
338 size_t out_len = lzo1x_worst_compress(sectorsize);
341 * We should always have enough space for one segment header
342 * inside current sector.
344 ASSERT(cur_in / sectorsize ==
345 (cur_in + LZO_LEN - 1) / sectorsize);
346 cur_page = cb->compressed_pages[cur_in / PAGE_SIZE];
348 seg_len = read_compress_length(page_address(cur_page) +
349 offset_in_page(cur_in));
352 /* Copy the compressed segment payload into workspace */
353 copy_compressed_segment(cb, workspace->cbuf, seg_len, &cur_in);
355 /* Decompress the data */
356 ret = lzo1x_decompress_safe(workspace->cbuf, seg_len,
357 workspace->buf, &out_len);
358 if (ret != LZO_E_OK) {
359 btrfs_err(fs_info, "failed to decompress");
364 /* Copy the data into inode pages */
365 ret = btrfs_decompress_buf2page(workspace->buf, out_len, cb, cur_out);
368 /* All data read, exit */
373 /* Check if the sector has enough space for a segment header */
374 sector_bytes_left = sectorsize - (cur_in % sectorsize);
375 if (sector_bytes_left >= LZO_LEN)
378 /* Skip the padding zeros */
379 cur_in += sector_bytes_left;
383 zero_fill_bio(cb->orig_bio);
387 int lzo_decompress(struct list_head *ws, unsigned char *data_in,
388 struct page *dest_page, unsigned long start_byte, size_t srclen,
391 struct workspace *workspace = list_entry(ws, struct workspace, list);
394 size_t max_segment_len = lzo1x_worst_compress(PAGE_SIZE);
399 if (srclen < LZO_LEN || srclen > max_segment_len + LZO_LEN * 2)
402 in_len = read_compress_length(data_in);
403 if (in_len != srclen)
407 in_len = read_compress_length(data_in);
408 if (in_len != srclen - LZO_LEN * 2) {
415 ret = lzo1x_decompress_safe(data_in, in_len, workspace->buf, &out_len);
416 if (ret != LZO_E_OK) {
417 pr_warn("BTRFS: decompress failed!\n");
422 if (out_len < start_byte) {
428 * the caller is already checking against PAGE_SIZE, but lets
429 * move this check closer to the memcpy/memset
431 destlen = min_t(unsigned long, destlen, PAGE_SIZE);
432 bytes = min_t(unsigned long, destlen, out_len - start_byte);
434 kaddr = page_address(dest_page);
435 memcpy(kaddr, workspace->buf + start_byte, bytes);
438 * btrfs_getblock is doing a zero on the tail of the page too,
439 * but this will cover anything missing from the decompressed
443 memset(kaddr+bytes, 0, destlen-bytes);
448 const struct btrfs_compress_op btrfs_lzo_compress = {
449 .workspace_manager = &wsm,