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 "compression.h" 17 18 #define LZO_LEN 4 19 20 /* 21 * Btrfs LZO compression format 22 * 23 * Regular and inlined LZO compressed data extents consist of: 24 * 25 * 1. Header 26 * Fixed size. LZO_LEN (4) bytes long, LE32. 27 * Records the total size (including the header) of compressed data. 28 * 29 * 2. Segment(s) 30 * Variable size. Each segment includes one segment header, followd by data 31 * payload. 32 * One regular LZO compressed extent can have one or more segments. 33 * For inlined LZO compressed extent, only one segment is allowed. 34 * One segment represents at most one page of uncompressed data. 35 * 36 * 2.1 Segment header 37 * Fixed size. LZO_LEN (4) bytes long, LE32. 38 * Records the total size of the segment (not including the header). 39 * Segment header never crosses page boundary, thus it's possible to 40 * have at most 3 padding zeros at the end of the page. 41 * 42 * 2.2 Data Payload 43 * Variable size. Size up limit should be lzo1x_worst_compress(PAGE_SIZE) 44 * which is 4419 for a 4KiB page. 45 * 46 * Example: 47 * Page 1: 48 * 0 0x2 0x4 0x6 0x8 0xa 0xc 0xe 0x10 49 * 0x0000 | Header | SegHdr 01 | Data payload 01 ... | 50 * ... 51 * 0x0ff0 | SegHdr N | Data payload N ... |00| 52 * ^^ padding zeros 53 * Page 2: 54 * 0x1000 | SegHdr N+1| Data payload N+1 ... | 55 */ 56 57 struct workspace { 58 void *mem; 59 void *buf; /* where decompressed data goes */ 60 void *cbuf; /* where compressed data goes */ 61 struct list_head list; 62 }; 63 64 static void lzo_free_workspace(struct list_head *ws) 65 { 66 struct workspace *workspace = list_entry(ws, struct workspace, list); 67 68 kvfree(workspace->buf); 69 kvfree(workspace->cbuf); 70 kvfree(workspace->mem); 71 kfree(workspace); 72 } 73 74 static struct list_head *lzo_alloc_workspace(void) 75 { 76 struct workspace *workspace; 77 78 workspace = kzalloc(sizeof(*workspace), GFP_KERNEL); 79 if (!workspace) 80 return ERR_PTR(-ENOMEM); 81 82 workspace->mem = kvmalloc(LZO1X_MEM_COMPRESS, GFP_KERNEL); 83 workspace->buf = kvmalloc(lzo1x_worst_compress(PAGE_SIZE), GFP_KERNEL); 84 workspace->cbuf = kvmalloc(lzo1x_worst_compress(PAGE_SIZE), GFP_KERNEL); 85 if (!workspace->mem || !workspace->buf || !workspace->cbuf) 86 goto fail; 87 88 INIT_LIST_HEAD(&workspace->list); 89 90 return &workspace->list; 91 fail: 92 lzo_free_workspace(&workspace->list); 93 return ERR_PTR(-ENOMEM); 94 } 95 96 static inline void write_compress_length(char *buf, size_t len) 97 { 98 __le32 dlen; 99 100 dlen = cpu_to_le32(len); 101 memcpy(buf, &dlen, LZO_LEN); 102 } 103 104 static inline size_t read_compress_length(const char *buf) 105 { 106 __le32 dlen; 107 108 memcpy(&dlen, buf, LZO_LEN); 109 return le32_to_cpu(dlen); 110 } 111 112 static int lzo_compress_pages(struct list_head *ws, 113 struct address_space *mapping, 114 u64 start, 115 struct page **pages, 116 unsigned long *out_pages, 117 unsigned long *total_in, 118 unsigned long *total_out) 119 { 120 struct workspace *workspace = list_entry(ws, struct workspace, list); 121 int ret = 0; 122 char *data_in; 123 char *cpage_out; 124 int nr_pages = 0; 125 struct page *in_page = NULL; 126 struct page *out_page = NULL; 127 unsigned long bytes_left; 128 unsigned long len = *total_out; 129 unsigned long nr_dest_pages = *out_pages; 130 const unsigned long max_out = nr_dest_pages * PAGE_SIZE; 131 size_t in_len; 132 size_t out_len; 133 char *buf; 134 unsigned long tot_in = 0; 135 unsigned long tot_out = 0; 136 unsigned long pg_bytes_left; 137 unsigned long out_offset; 138 unsigned long bytes; 139 140 *out_pages = 0; 141 *total_out = 0; 142 *total_in = 0; 143 144 in_page = find_get_page(mapping, start >> PAGE_SHIFT); 145 data_in = kmap(in_page); 146 147 /* 148 * store the size of all chunks of compressed data in 149 * the first 4 bytes 150 */ 151 out_page = alloc_page(GFP_NOFS | __GFP_HIGHMEM); 152 if (out_page == NULL) { 153 ret = -ENOMEM; 154 goto out; 155 } 156 cpage_out = kmap(out_page); 157 out_offset = LZO_LEN; 158 tot_out = LZO_LEN; 159 pages[0] = out_page; 160 nr_pages = 1; 161 pg_bytes_left = PAGE_SIZE - LZO_LEN; 162 163 /* compress at most one page of data each time */ 164 in_len = min(len, PAGE_SIZE); 165 while (tot_in < len) { 166 ret = lzo1x_1_compress(data_in, in_len, workspace->cbuf, 167 &out_len, workspace->mem); 168 if (ret != LZO_E_OK) { 169 pr_debug("BTRFS: lzo in loop returned %d\n", 170 ret); 171 ret = -EIO; 172 goto out; 173 } 174 175 /* store the size of this chunk of compressed data */ 176 write_compress_length(cpage_out + out_offset, out_len); 177 tot_out += LZO_LEN; 178 out_offset += LZO_LEN; 179 pg_bytes_left -= LZO_LEN; 180 181 tot_in += in_len; 182 tot_out += out_len; 183 184 /* copy bytes from the working buffer into the pages */ 185 buf = workspace->cbuf; 186 while (out_len) { 187 bytes = min_t(unsigned long, pg_bytes_left, out_len); 188 189 memcpy(cpage_out + out_offset, buf, bytes); 190 191 out_len -= bytes; 192 pg_bytes_left -= bytes; 193 buf += bytes; 194 out_offset += bytes; 195 196 /* 197 * we need another page for writing out. 198 * 199 * Note if there's less than 4 bytes left, we just 200 * skip to a new page. 201 */ 202 if ((out_len == 0 && pg_bytes_left < LZO_LEN) || 203 pg_bytes_left == 0) { 204 if (pg_bytes_left) { 205 memset(cpage_out + out_offset, 0, 206 pg_bytes_left); 207 tot_out += pg_bytes_left; 208 } 209 210 /* we're done, don't allocate new page */ 211 if (out_len == 0 && tot_in >= len) 212 break; 213 214 kunmap(out_page); 215 if (nr_pages == nr_dest_pages) { 216 out_page = NULL; 217 ret = -E2BIG; 218 goto out; 219 } 220 221 out_page = alloc_page(GFP_NOFS | __GFP_HIGHMEM); 222 if (out_page == NULL) { 223 ret = -ENOMEM; 224 goto out; 225 } 226 cpage_out = kmap(out_page); 227 pages[nr_pages++] = out_page; 228 229 pg_bytes_left = PAGE_SIZE; 230 out_offset = 0; 231 } 232 } 233 234 /* we're making it bigger, give up */ 235 if (tot_in > 8192 && tot_in < tot_out) { 236 ret = -E2BIG; 237 goto out; 238 } 239 240 /* we're all done */ 241 if (tot_in >= len) 242 break; 243 244 if (tot_out > max_out) 245 break; 246 247 bytes_left = len - tot_in; 248 kunmap(in_page); 249 put_page(in_page); 250 251 start += PAGE_SIZE; 252 in_page = find_get_page(mapping, start >> PAGE_SHIFT); 253 data_in = kmap(in_page); 254 in_len = min(bytes_left, PAGE_SIZE); 255 } 256 257 if (tot_out >= tot_in) { 258 ret = -E2BIG; 259 goto out; 260 } 261 262 /* store the size of all chunks of compressed data */ 263 cpage_out = kmap(pages[0]); 264 write_compress_length(cpage_out, tot_out); 265 266 kunmap(pages[0]); 267 268 ret = 0; 269 *total_out = tot_out; 270 *total_in = tot_in; 271 out: 272 *out_pages = nr_pages; 273 if (out_page) 274 kunmap(out_page); 275 276 if (in_page) { 277 kunmap(in_page); 278 put_page(in_page); 279 } 280 281 return ret; 282 } 283 284 static int lzo_decompress_bio(struct list_head *ws, struct compressed_bio *cb) 285 { 286 struct workspace *workspace = list_entry(ws, struct workspace, list); 287 int ret = 0, ret2; 288 char *data_in; 289 unsigned long page_in_index = 0; 290 size_t srclen = cb->compressed_len; 291 unsigned long total_pages_in = DIV_ROUND_UP(srclen, PAGE_SIZE); 292 unsigned long buf_start; 293 unsigned long buf_offset = 0; 294 unsigned long bytes; 295 unsigned long working_bytes; 296 size_t in_len; 297 size_t out_len; 298 const size_t max_segment_len = lzo1x_worst_compress(PAGE_SIZE); 299 unsigned long in_offset; 300 unsigned long in_page_bytes_left; 301 unsigned long tot_in; 302 unsigned long tot_out; 303 unsigned long tot_len; 304 char *buf; 305 bool may_late_unmap, need_unmap; 306 struct page **pages_in = cb->compressed_pages; 307 u64 disk_start = cb->start; 308 struct bio *orig_bio = cb->orig_bio; 309 310 data_in = kmap(pages_in[0]); 311 tot_len = read_compress_length(data_in); 312 /* 313 * Compressed data header check. 314 * 315 * The real compressed size can't exceed the maximum extent length, and 316 * all pages should be used (whole unused page with just the segment 317 * header is not possible). If this happens it means the compressed 318 * extent is corrupted. 319 */ 320 if (tot_len > min_t(size_t, BTRFS_MAX_COMPRESSED, srclen) || 321 tot_len < srclen - PAGE_SIZE) { 322 ret = -EUCLEAN; 323 goto done; 324 } 325 326 tot_in = LZO_LEN; 327 in_offset = LZO_LEN; 328 in_page_bytes_left = PAGE_SIZE - LZO_LEN; 329 330 tot_out = 0; 331 332 while (tot_in < tot_len) { 333 in_len = read_compress_length(data_in + in_offset); 334 in_page_bytes_left -= LZO_LEN; 335 in_offset += LZO_LEN; 336 tot_in += LZO_LEN; 337 338 /* 339 * Segment header check. 340 * 341 * The segment length must not exceed the maximum LZO 342 * compression size, nor the total compressed size. 343 */ 344 if (in_len > max_segment_len || tot_in + in_len > tot_len) { 345 ret = -EUCLEAN; 346 goto done; 347 } 348 349 tot_in += in_len; 350 working_bytes = in_len; 351 may_late_unmap = need_unmap = false; 352 353 /* fast path: avoid using the working buffer */ 354 if (in_page_bytes_left >= in_len) { 355 buf = data_in + in_offset; 356 bytes = in_len; 357 may_late_unmap = true; 358 goto cont; 359 } 360 361 /* copy bytes from the pages into the working buffer */ 362 buf = workspace->cbuf; 363 buf_offset = 0; 364 while (working_bytes) { 365 bytes = min(working_bytes, in_page_bytes_left); 366 367 memcpy(buf + buf_offset, data_in + in_offset, bytes); 368 buf_offset += bytes; 369 cont: 370 working_bytes -= bytes; 371 in_page_bytes_left -= bytes; 372 in_offset += bytes; 373 374 /* check if we need to pick another page */ 375 if ((working_bytes == 0 && in_page_bytes_left < LZO_LEN) 376 || in_page_bytes_left == 0) { 377 tot_in += in_page_bytes_left; 378 379 if (working_bytes == 0 && tot_in >= tot_len) 380 break; 381 382 if (page_in_index + 1 >= total_pages_in) { 383 ret = -EIO; 384 goto done; 385 } 386 387 if (may_late_unmap) 388 need_unmap = true; 389 else 390 kunmap(pages_in[page_in_index]); 391 392 data_in = kmap(pages_in[++page_in_index]); 393 394 in_page_bytes_left = PAGE_SIZE; 395 in_offset = 0; 396 } 397 } 398 399 out_len = max_segment_len; 400 ret = lzo1x_decompress_safe(buf, in_len, workspace->buf, 401 &out_len); 402 if (need_unmap) 403 kunmap(pages_in[page_in_index - 1]); 404 if (ret != LZO_E_OK) { 405 pr_warn("BTRFS: decompress failed\n"); 406 ret = -EIO; 407 break; 408 } 409 410 buf_start = tot_out; 411 tot_out += out_len; 412 413 ret2 = btrfs_decompress_buf2page(workspace->buf, buf_start, 414 tot_out, disk_start, orig_bio); 415 if (ret2 == 0) 416 break; 417 } 418 done: 419 kunmap(pages_in[page_in_index]); 420 if (!ret) 421 zero_fill_bio(orig_bio); 422 return ret; 423 } 424 425 static int lzo_decompress(struct list_head *ws, unsigned char *data_in, 426 struct page *dest_page, 427 unsigned long start_byte, 428 size_t srclen, size_t destlen) 429 { 430 struct workspace *workspace = list_entry(ws, struct workspace, list); 431 size_t in_len; 432 size_t out_len; 433 size_t max_segment_len = lzo1x_worst_compress(PAGE_SIZE); 434 int ret = 0; 435 char *kaddr; 436 unsigned long bytes; 437 438 if (srclen < LZO_LEN || srclen > max_segment_len + LZO_LEN * 2) 439 return -EUCLEAN; 440 441 in_len = read_compress_length(data_in); 442 if (in_len != srclen) 443 return -EUCLEAN; 444 data_in += LZO_LEN; 445 446 in_len = read_compress_length(data_in); 447 if (in_len != srclen - LZO_LEN * 2) { 448 ret = -EUCLEAN; 449 goto out; 450 } 451 data_in += LZO_LEN; 452 453 out_len = PAGE_SIZE; 454 ret = lzo1x_decompress_safe(data_in, in_len, workspace->buf, &out_len); 455 if (ret != LZO_E_OK) { 456 pr_warn("BTRFS: decompress failed!\n"); 457 ret = -EIO; 458 goto out; 459 } 460 461 if (out_len < start_byte) { 462 ret = -EIO; 463 goto out; 464 } 465 466 /* 467 * the caller is already checking against PAGE_SIZE, but lets 468 * move this check closer to the memcpy/memset 469 */ 470 destlen = min_t(unsigned long, destlen, PAGE_SIZE); 471 bytes = min_t(unsigned long, destlen, out_len - start_byte); 472 473 kaddr = kmap_atomic(dest_page); 474 memcpy(kaddr, workspace->buf + start_byte, bytes); 475 476 /* 477 * btrfs_getblock is doing a zero on the tail of the page too, 478 * but this will cover anything missing from the decompressed 479 * data. 480 */ 481 if (bytes < destlen) 482 memset(kaddr+bytes, 0, destlen-bytes); 483 kunmap_atomic(kaddr); 484 out: 485 return ret; 486 } 487 488 static void lzo_set_level(struct list_head *ws, unsigned int type) 489 { 490 } 491 492 const struct btrfs_compress_op btrfs_lzo_compress = { 493 .alloc_workspace = lzo_alloc_workspace, 494 .free_workspace = lzo_free_workspace, 495 .compress_pages = lzo_compress_pages, 496 .decompress_bio = lzo_decompress_bio, 497 .decompress = lzo_decompress, 498 .set_level = lzo_set_level, 499 }; 500