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 = kmap(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 = kmap(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)
214 if (nr_pages == nr_dest_pages) {
220 out_page = alloc_page(GFP_NOFS);
221 if (out_page == NULL) {
225 cpage_out = kmap(out_page);
226 pages[nr_pages++] = out_page;
228 pg_bytes_left = PAGE_SIZE;
233 /* we're making it bigger, give up */
234 if (tot_in > 8192 && tot_in < tot_out) {
243 if (tot_out > max_out)
246 bytes_left = len - tot_in;
251 in_page = find_get_page(mapping, start >> PAGE_SHIFT);
252 data_in = kmap(in_page);
253 in_len = min(bytes_left, PAGE_SIZE);
256 if (tot_out >= tot_in) {
261 /* store the size of all chunks of compressed data */
262 sizes_ptr = kmap_local_page(pages[0]);
263 write_compress_length(sizes_ptr, tot_out);
264 kunmap_local(sizes_ptr);
267 *total_out = tot_out;
270 *out_pages = nr_pages;
283 * Copy the compressed segment payload into @dest.
285 * For the payload there will be no padding, just need to do page switching.
287 static void copy_compressed_segment(struct compressed_bio *cb,
288 char *dest, u32 len, u32 *cur_in)
290 u32 orig_in = *cur_in;
292 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);
299 cur_page = cb->compressed_pages[*cur_in / PAGE_SIZE];
301 kaddr = kmap(cur_page);
302 memcpy(dest + *cur_in - orig_in,
303 kaddr + offset_in_page(*cur_in),
311 int lzo_decompress_bio(struct list_head *ws, struct compressed_bio *cb)
313 struct workspace *workspace = list_entry(ws, struct workspace, list);
314 const struct btrfs_fs_info *fs_info = btrfs_sb(cb->inode->i_sb);
315 const u32 sectorsize = fs_info->sectorsize;
318 /* Compressed data length, can be unaligned */
320 /* Offset inside the compressed data */
322 /* Bytes decompressed so far */
325 kaddr = kmap(cb->compressed_pages[0]);
326 len_in = read_compress_length(kaddr);
327 kunmap(cb->compressed_pages[0]);
331 * LZO header length check
333 * The total length should not exceed the maximum extent length,
334 * and all sectors should be used.
335 * If this happens, it means the compressed extent is corrupted.
337 if (len_in > min_t(size_t, BTRFS_MAX_COMPRESSED, cb->compressed_len) ||
338 round_up(len_in, sectorsize) < cb->compressed_len) {
340 "invalid lzo header, lzo len %u compressed len %u",
341 len_in, cb->compressed_len);
345 /* Go through each lzo segment */
346 while (cur_in < len_in) {
347 struct page *cur_page;
348 /* Length of the compressed segment */
350 u32 sector_bytes_left;
351 size_t out_len = lzo1x_worst_compress(sectorsize);
354 * We should always have enough space for one segment header
355 * inside current sector.
357 ASSERT(cur_in / sectorsize ==
358 (cur_in + LZO_LEN - 1) / sectorsize);
359 cur_page = cb->compressed_pages[cur_in / PAGE_SIZE];
360 kaddr = kmap(cur_page);
362 seg_len = read_compress_length(kaddr + offset_in_page(cur_in));
365 /* Copy the compressed segment payload into workspace */
366 copy_compressed_segment(cb, workspace->cbuf, seg_len, &cur_in);
368 /* Decompress the data */
369 ret = lzo1x_decompress_safe(workspace->cbuf, seg_len,
370 workspace->buf, &out_len);
371 if (ret != LZO_E_OK) {
372 btrfs_err(fs_info, "failed to decompress");
377 /* Copy the data into inode pages */
378 ret = btrfs_decompress_buf2page(workspace->buf, out_len, cb, cur_out);
381 /* All data read, exit */
386 /* Check if the sector has enough space for a segment header */
387 sector_bytes_left = sectorsize - (cur_in % sectorsize);
388 if (sector_bytes_left >= LZO_LEN)
391 /* Skip the padding zeros */
392 cur_in += sector_bytes_left;
396 zero_fill_bio(cb->orig_bio);
400 int lzo_decompress(struct list_head *ws, unsigned char *data_in,
401 struct page *dest_page, unsigned long start_byte, size_t srclen,
404 struct workspace *workspace = list_entry(ws, struct workspace, list);
407 size_t max_segment_len = lzo1x_worst_compress(PAGE_SIZE);
412 if (srclen < LZO_LEN || srclen > max_segment_len + LZO_LEN * 2)
415 in_len = read_compress_length(data_in);
416 if (in_len != srclen)
420 in_len = read_compress_length(data_in);
421 if (in_len != srclen - LZO_LEN * 2) {
428 ret = lzo1x_decompress_safe(data_in, in_len, workspace->buf, &out_len);
429 if (ret != LZO_E_OK) {
430 pr_warn("BTRFS: decompress failed!\n");
435 if (out_len < start_byte) {
441 * the caller is already checking against PAGE_SIZE, but lets
442 * move this check closer to the memcpy/memset
444 destlen = min_t(unsigned long, destlen, PAGE_SIZE);
445 bytes = min_t(unsigned long, destlen, out_len - start_byte);
447 kaddr = kmap_local_page(dest_page);
448 memcpy(kaddr, workspace->buf + start_byte, bytes);
451 * btrfs_getblock is doing a zero on the tail of the page too,
452 * but this will cover anything missing from the decompressed
456 memset(kaddr+bytes, 0, destlen-bytes);
462 const struct btrfs_compress_op btrfs_lzo_compress = {
463 .workspace_manager = &wsm,