fs/btrfs/lzo.c

   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(workspace->buf);
  78         kvfree(workspace->cbuf);
  79         kvfree(workspace->mem);
  80         kfree(workspace);
  81 }
  82
  83 struct list_head *lzo_alloc_workspace(unsigned int level)
  84 {
  85         struct workspace *workspace;
  86
  87         workspace = kzalloc(sizeof(*workspace), GFP_KERNEL);
  88         if (!workspace)
  89                 return ERR_PTR(-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(&workspace->list);
  98
  99         return &workspace->list;
 100 fail:
 101         lzo_free_workspace(&workspace->list);
 102         return ERR_PTR(-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 = btrfs_alloc_compr_page();
 156                 if (!cur_page)
 157                         return -ENOMEM;
 158                 out_pages[*cur_out / PAGE_SIZE] = cur_page;
 159         }
 160
 161         kaddr = kmap_local_page(cur_page);
 162         write_compress_length(kaddr + offset_in_page(*cur_out),
 163                               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 = btrfs_alloc_compr_page();
 182                         if (!cur_page)
 183                                 return -ENOMEM;
 184                         out_pages[*cur_out / PAGE_SIZE] = cur_page;
 185                 }
 186                 kaddr = kmap_local_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 = inode_to_fs_info(mapping->host)->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, 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_in);
 255                 ret = lzo1x_1_compress(data_in +
 256                                        offset_in_page(cur_in), in_len,
 257                                        workspace->cbuf, &out_len,
 258                                        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(workspace->cbuf, out_len,
 267                                                    pages, max_nr_page,
 268                                                    &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_in);
 286                         page_in = NULL;
 287                 }
 288         }
 289
 290         /* Store the size of all chunks of compressed data */
 291         sizes_ptr = kmap_local_page(pages[0]);
 292         write_compress_length(sizes_ptr, 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_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(dest + *cur_in - orig_in, cur_page,
 324                                  offset_in_page(*cur_in), 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(cb->compressed_pages[0]);
 345         len_in = read_compress_length(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(cur_page);
 381                 seg_len = read_compress_length(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, workspace->cbuf, seg_len, &cur_in);
 397
 398                 /* Decompress the data */
 399                 ret = lzo1x_decompress_safe(workspace->cbuf, seg_len,
 400                                             workspace->buf, &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(workspace->buf, out_len, cb, 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 dest_pgoff, size_t srclen,
 429                 size_t destlen)
 430 {
 431         struct workspace *workspace = list_entry(ws, struct workspace, list);
 432         struct btrfs_fs_info *fs_info = page_to_fs_info(dest_page);
 433         const u32 sectorsize = fs_info->sectorsize;
 434         size_t in_len;
 435         size_t out_len;
 436         size_t max_segment_len = WORKSPACE_BUF_LENGTH;
 437         int ret = 0;
 438
 439         if (srclen < LZO_LEN || srclen > max_segment_len + LZO_LEN * 2)
 440                 return -EUCLEAN;
 441
 442         in_len = read_compress_length(data_in);
 443         if (in_len != srclen)
 444                 return -EUCLEAN;
 445         data_in += LZO_LEN;
 446
 447         in_len = read_compress_length(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 = sectorsize;
 455         ret = lzo1x_decompress_safe(data_in, in_len, workspace->buf, &out_len);
 456         if (ret != LZO_E_OK) {
 457                 pr_warn("BTRFS: decompress failed!\n");
 458                 ret = -EIO;
 459                 goto out;
 460         }
 461
 462         ASSERT(out_len <= sectorsize);
 463         memcpy_to_page(dest_page, dest_pgoff, workspace->buf, out_len);
 464         /* Early end, considered as an error. */
 465         if (unlikely(out_len < destlen)) {
 466                 ret = -EIO;
 467                 memzero_page(dest_page, dest_pgoff + out_len, destlen - out_len);
 468         }
 469 out:
 470         return ret;
 471 }
 472
 473 const struct btrfs_compress_op btrfs_lzo_compress = {
 474         .workspace_manager      = &wsm,
 475         .max_level              = 1,
 476         .default_level          = 1,
 477 };