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 "compression.h"
  17 #include "ctree.h"
  18
  19 #define LZO_LEN 4
  20
  21 /*
  22  * Btrfs LZO compression format
  23  *
  24  * Regular and inlined LZO compressed data extents consist of:
  25  *
  26  * 1.  Header
  27  *     Fixed size. LZO_LEN (4) bytes long, LE32.
  28  *     Records the total size (including the header) of compressed data.
  29  *
  30  * 2.  Segment(s)
  31  *     Variable size. Each segment includes one segment header, followed by data
  32  *     payload.
  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 sector of uncompressed data.
  36  *
  37  * 2.1 Segment header
  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 sector boundary, thus it's possible to
  41  *     have at most 3 padding zeros at the end of the sector.
  42  *
  43  * 2.2 Data Payload
  44  *     Variable size. Size up limit should be lzo1x_worst_compress(sectorsize)
  45  *     which is 4419 for a 4KiB sectorsize.
  46  *
  47  * Example with 4K sectorsize:
  48  * Page 1:
  49  *          0     0x2   0x4   0x6   0x8   0xa   0xc   0xe     0x10
  50  * 0x0000   |  Header   | SegHdr 01 | Data payload 01 ...     |
  51  * ...
  52  * 0x0ff0   | SegHdr  N | Data payload  N     ...          |00|
  53  *                                                          ^^ padding zeros
  54  * Page 2:
  55  * 0x1000   | SegHdr N+1| Data payload N+1 ...                |
  56  */
  57
  58 #define WORKSPACE_BUF_LENGTH    (lzo1x_worst_compress(PAGE_SIZE))
  59 #define WORKSPACE_CBUF_LENGTH   (lzo1x_worst_compress(PAGE_SIZE))
  60
  61 struct workspace {
  62         void *mem;
  63         void *buf;      /* where decompressed data goes */
  64         void *cbuf;     /* where compressed data goes */
  65         struct list_head list;
  66 };
  67
  68 static struct workspace_manager wsm;
  69
  70 void lzo_free_workspace(struct list_head *ws)
  71 {
  72         struct workspace *workspace = list_entry(ws, struct workspace, list);
  73
  74         kvfree(workspace->buf);
  75         kvfree(workspace->cbuf);
  76         kvfree(workspace->mem);
  77         kfree(workspace);
  78 }
  79
  80 struct list_head *lzo_alloc_workspace(unsigned int level)
  81 {
  82         struct workspace *workspace;
  83
  84         workspace = kzalloc(sizeof(*workspace), GFP_KERNEL);
  85         if (!workspace)
  86                 return ERR_PTR(-ENOMEM);
  87
  88         workspace->mem = kvmalloc(LZO1X_MEM_COMPRESS, GFP_KERNEL);
  89         workspace->buf = kvmalloc(WORKSPACE_BUF_LENGTH, GFP_KERNEL);
  90         workspace->cbuf = kvmalloc(WORKSPACE_CBUF_LENGTH, GFP_KERNEL);
  91         if (!workspace->mem || !workspace->buf || !workspace->cbuf)
  92                 goto fail;
  93
  94         INIT_LIST_HEAD(&workspace->list);
  95
  96         return &workspace->list;
  97 fail:
  98         lzo_free_workspace(&workspace->list);
  99         return ERR_PTR(-ENOMEM);
 100 }
 101
 102 static inline void write_compress_length(char *buf, size_t len)
 103 {
 104         __le32 dlen;
 105
 106         dlen = cpu_to_le32(len);
 107         memcpy(buf, &dlen, LZO_LEN);
 108 }
 109
 110 static inline size_t read_compress_length(const char *buf)
 111 {
 112         __le32 dlen;
 113
 114         memcpy(&dlen, buf, LZO_LEN);
 115         return le32_to_cpu(dlen);
 116 }
 117
 118 /*
 119  * Will do:
 120  *
 121  * - Write a segment header into the destination
 122  * - Copy the compressed buffer into the destination
 123  * - Make sure we have enough space in the last sector to fit a segment header
 124  *   If not, we will pad at most (LZO_LEN (4)) - 1 bytes of zeros.
 125  *
 126  * Will allocate new pages when needed.
 127  */
 128 static int copy_compressed_data_to_page(char *compressed_data,
 129                                         size_t compressed_size,
 130                                         struct page **out_pages,
 131                                         unsigned long max_nr_page,
 132                                         u32 *cur_out,
 133                                         const u32 sectorsize)
 134 {
 135         u32 sector_bytes_left;
 136         u32 orig_out;
 137         struct page *cur_page;
 138         char *kaddr;
 139
 140         if ((*cur_out / PAGE_SIZE) >= max_nr_page)
 141                 return -E2BIG;
 142
 143         /*
 144          * We never allow a segment header crossing sector boundary, previous
 145          * run should ensure we have enough space left inside the sector.
 146          */
 147         ASSERT((*cur_out / sectorsize) == (*cur_out + LZO_LEN - 1) / sectorsize);
 148
 149         cur_page = out_pages[*cur_out / PAGE_SIZE];
 150         /* Allocate a new page */
 151         if (!cur_page) {
 152                 cur_page = alloc_page(GFP_NOFS);
 153                 if (!cur_page)
 154                         return -ENOMEM;
 155                 out_pages[*cur_out / PAGE_SIZE] = cur_page;
 156         }
 157
 158         kaddr = kmap_local_page(cur_page);
 159         write_compress_length(kaddr + offset_in_page(*cur_out),
 160                               compressed_size);
 161         *cur_out += LZO_LEN;
 162
 163         orig_out = *cur_out;
 164
 165         /* Copy compressed data */
 166         while (*cur_out - orig_out < compressed_size) {
 167                 u32 copy_len = min_t(u32, sectorsize - *cur_out % sectorsize,
 168                                      orig_out + compressed_size - *cur_out);
 169
 170                 kunmap_local(kaddr);
 171
 172                 if ((*cur_out / PAGE_SIZE) >= max_nr_page)
 173                         return -E2BIG;
 174
 175                 cur_page = out_pages[*cur_out / PAGE_SIZE];
 176                 /* Allocate a new page */
 177                 if (!cur_page) {
 178                         cur_page = alloc_page(GFP_NOFS);
 179                         if (!cur_page)
 180                                 return -ENOMEM;
 181                         out_pages[*cur_out / PAGE_SIZE] = cur_page;
 182                 }
 183                 kaddr = kmap_local_page(cur_page);
 184
 185                 memcpy(kaddr + offset_in_page(*cur_out),
 186                        compressed_data + *cur_out - orig_out, copy_len);
 187
 188                 *cur_out += copy_len;
 189         }
 190
 191         /*
 192          * Check if we can fit the next segment header into the remaining space
 193          * of the sector.
 194          */
 195         sector_bytes_left = round_up(*cur_out, sectorsize) - *cur_out;
 196         if (sector_bytes_left >= LZO_LEN || sector_bytes_left == 0)
 197                 goto out;
 198
 199         /* The remaining size is not enough, pad it with zeros */
 200         memset(kaddr + offset_in_page(*cur_out), 0,
 201                sector_bytes_left);
 202         *cur_out += sector_bytes_left;
 203
 204 out:
 205         kunmap_local(kaddr);
 206         return 0;
 207 }
 208
 209 int lzo_compress_pages(struct list_head *ws, struct address_space *mapping,
 210                 u64 start, struct page **pages, unsigned long *out_pages,
 211                 unsigned long *total_in, unsigned long *total_out)
 212 {
 213         struct workspace *workspace = list_entry(ws, struct workspace, list);
 214         const u32 sectorsize = btrfs_sb(mapping->host->i_sb)->sectorsize;
 215         struct page *page_in = NULL;
 216         char *sizes_ptr;
 217         const unsigned long max_nr_page = *out_pages;
 218         int ret = 0;
 219         /* Points to the file offset of input data */
 220         u64 cur_in = start;
 221         /* Points to the current output byte */
 222         u32 cur_out = 0;
 223         u32 len = *total_out;
 224
 225         ASSERT(max_nr_page > 0);
 226         *out_pages = 0;
 227         *total_out = 0;
 228         *total_in = 0;
 229
 230         /*
 231          * Skip the header for now, we will later come back and write the total
 232          * compressed size
 233          */
 234         cur_out += LZO_LEN;
 235         while (cur_in < start + len) {
 236                 char *data_in;
 237                 const u32 sectorsize_mask = sectorsize - 1;
 238                 u32 sector_off = (cur_in - start) & sectorsize_mask;
 239                 u32 in_len;
 240                 size_t out_len;
 241
 242                 /* Get the input page first */
 243                 if (!page_in) {
 244                         page_in = find_get_page(mapping, cur_in >> PAGE_SHIFT);
 245                         ASSERT(page_in);
 246                 }
 247
 248                 /* Compress at most one sector of data each time */
 249                 in_len = min_t(u32, start + len - cur_in, sectorsize - sector_off);
 250                 ASSERT(in_len);
 251                 data_in = kmap_local_page(page_in);
 252                 ret = lzo1x_1_compress(data_in +
 253                                        offset_in_page(cur_in), in_len,
 254                                        workspace->cbuf, &out_len,
 255                                        workspace->mem);
 256                 kunmap_local(data_in);
 257                 if (ret < 0) {
 258                         pr_debug("BTRFS: lzo in loop returned %d\n", ret);
 259                         ret = -EIO;
 260                         goto out;
 261                 }
 262
 263                 ret = copy_compressed_data_to_page(workspace->cbuf, out_len,
 264                                                    pages, max_nr_page,
 265                                                    &cur_out, sectorsize);
 266                 if (ret < 0)
 267                         goto out;
 268
 269                 cur_in += in_len;
 270
 271                 /*
 272                  * Check if we're making it bigger after two sectors.  And if
 273                  * it is so, give up.
 274                  */
 275                 if (cur_in - start > sectorsize * 2 && cur_in - start < cur_out) {
 276                         ret = -E2BIG;
 277                         goto out;
 278                 }
 279
 280                 /* Check if we have reached page boundary */
 281                 if (IS_ALIGNED(cur_in, PAGE_SIZE)) {
 282                         put_page(page_in);
 283                         page_in = NULL;
 284                 }
 285         }
 286
 287         /* Store the size of all chunks of compressed data */
 288         sizes_ptr = kmap_local_page(pages[0]);
 289         write_compress_length(sizes_ptr, cur_out);
 290         kunmap_local(sizes_ptr);
 291
 292         ret = 0;
 293         *total_out = cur_out;
 294         *total_in = cur_in - start;
 295 out:
 296         if (page_in)
 297                 put_page(page_in);
 298         *out_pages = DIV_ROUND_UP(cur_out, PAGE_SIZE);
 299         return ret;
 300 }
 301
 302 /*
 303  * Copy the compressed segment payload into @dest.
 304  *
 305  * For the payload there will be no padding, just need to do page switching.
 306  */
 307 static void copy_compressed_segment(struct compressed_bio *cb,
 308                                     char *dest, u32 len, u32 *cur_in)
 309 {
 310         u32 orig_in = *cur_in;
 311
 312         while (*cur_in < orig_in + len) {
 313                 struct page *cur_page;
 314                 u32 copy_len = min_t(u32, PAGE_SIZE - offset_in_page(*cur_in),
 315                                           orig_in + len - *cur_in);
 316
 317                 ASSERT(copy_len);
 318                 cur_page = cb->compressed_pages[*cur_in / PAGE_SIZE];
 319
 320                 memcpy_from_page(dest + *cur_in - orig_in, cur_page,
 321                                  offset_in_page(*cur_in), copy_len);
 322
 323                 *cur_in += copy_len;
 324         }
 325 }
 326
 327 int lzo_decompress_bio(struct list_head *ws, struct compressed_bio *cb)
 328 {
 329         struct workspace *workspace = list_entry(ws, struct workspace, list);
 330         const struct btrfs_fs_info *fs_info = btrfs_sb(cb->inode->i_sb);
 331         const u32 sectorsize = fs_info->sectorsize;
 332         char *kaddr;
 333         int ret;
 334         /* Compressed data length, can be unaligned */
 335         u32 len_in;
 336         /* Offset inside the compressed data */
 337         u32 cur_in = 0;
 338         /* Bytes decompressed so far */
 339         u32 cur_out = 0;
 340
 341         kaddr = kmap_local_page(cb->compressed_pages[0]);
 342         len_in = read_compress_length(kaddr);
 343         kunmap_local(kaddr);
 344         cur_in += LZO_LEN;
 345
 346         /*
 347          * LZO header length check
 348          *
 349          * The total length should not exceed the maximum extent length,
 350          * and all sectors should be used.
 351          * If this happens, it means the compressed extent is corrupted.
 352          */
 353         if (len_in > min_t(size_t, BTRFS_MAX_COMPRESSED, cb->compressed_len) ||
 354             round_up(len_in, sectorsize) < cb->compressed_len) {
 355                 btrfs_err(fs_info,
 356                         "invalid lzo header, lzo len %u compressed len %u",
 357                         len_in, cb->compressed_len);
 358                 return -EUCLEAN;
 359         }
 360
 361         /* Go through each lzo segment */
 362         while (cur_in < len_in) {
 363                 struct page *cur_page;
 364                 /* Length of the compressed segment */
 365                 u32 seg_len;
 366                 u32 sector_bytes_left;
 367                 size_t out_len = lzo1x_worst_compress(sectorsize);
 368
 369                 /*
 370                  * We should always have enough space for one segment header
 371                  * inside current sector.
 372                  */
 373                 ASSERT(cur_in / sectorsize ==
 374                        (cur_in + LZO_LEN - 1) / sectorsize);
 375                 cur_page = cb->compressed_pages[cur_in / PAGE_SIZE];
 376                 ASSERT(cur_page);
 377                 kaddr = kmap_local_page(cur_page);
 378                 seg_len = read_compress_length(kaddr + offset_in_page(cur_in));
 379                 kunmap_local(kaddr);
 380                 cur_in += LZO_LEN;
 381
 382                 if (seg_len > WORKSPACE_CBUF_LENGTH) {
 383                         /*
 384                          * seg_len shouldn't be larger than we have allocated
 385                          * for workspace->cbuf
 386                          */
 387                         btrfs_err(fs_info, "unexpectedly large lzo segment len %u",
 388                                         seg_len);
 389                         ret = -EIO;
 390                         goto out;
 391                 }
 392
 393                 /* Copy the compressed segment payload into workspace */
 394                 copy_compressed_segment(cb, workspace->cbuf, seg_len, &cur_in);
 395
 396                 /* Decompress the data */
 397                 ret = lzo1x_decompress_safe(workspace->cbuf, seg_len,
 398                                             workspace->buf, &out_len);
 399                 if (ret != LZO_E_OK) {
 400                         btrfs_err(fs_info, "failed to decompress");
 401                         ret = -EIO;
 402                         goto out;
 403                 }
 404
 405                 /* Copy the data into inode pages */
 406                 ret = btrfs_decompress_buf2page(workspace->buf, out_len, cb, cur_out);
 407                 cur_out += out_len;
 408
 409                 /* All data read, exit */
 410                 if (ret == 0)
 411                         goto out;
 412                 ret = 0;
 413
 414                 /* Check if the sector has enough space for a segment header */
 415                 sector_bytes_left = sectorsize - (cur_in % sectorsize);
 416                 if (sector_bytes_left >= LZO_LEN)
 417                         continue;
 418
 419                 /* Skip the padding zeros */
 420                 cur_in += sector_bytes_left;
 421         }
 422 out:
 423         if (!ret)
 424                 zero_fill_bio(cb->orig_bio);
 425         return ret;
 426 }
 427
 428 int lzo_decompress(struct list_head *ws, unsigned char *data_in,
 429                 struct page *dest_page, unsigned long start_byte, size_t srclen,
 430                 size_t destlen)
 431 {
 432         struct workspace *workspace = list_entry(ws, struct workspace, list);
 433         size_t in_len;
 434         size_t out_len;
 435         size_t max_segment_len = WORKSPACE_BUF_LENGTH;
 436         int ret = 0;
 437         char *kaddr;
 438         unsigned long bytes;
 439
 440         if (srclen < LZO_LEN || srclen > max_segment_len + LZO_LEN * 2)
 441                 return -EUCLEAN;
 442
 443         in_len = read_compress_length(data_in);
 444         if (in_len != srclen)
 445                 return -EUCLEAN;
 446         data_in += LZO_LEN;
 447
 448         in_len = read_compress_length(data_in);
 449         if (in_len != srclen - LZO_LEN * 2) {
 450                 ret = -EUCLEAN;
 451                 goto out;
 452         }
 453         data_in += LZO_LEN;
 454
 455         out_len = PAGE_SIZE;
 456         ret = lzo1x_decompress_safe(data_in, in_len, workspace->buf, &out_len);
 457         if (ret != LZO_E_OK) {
 458                 pr_warn("BTRFS: decompress failed!\n");
 459                 ret = -EIO;
 460                 goto out;
 461         }
 462
 463         if (out_len < start_byte) {
 464                 ret = -EIO;
 465                 goto out;
 466         }
 467
 468         /*
 469          * the caller is already checking against PAGE_SIZE, but lets
 470          * move this check closer to the memcpy/memset
 471          */
 472         destlen = min_t(unsigned long, destlen, PAGE_SIZE);
 473         bytes = min_t(unsigned long, destlen, out_len - start_byte);
 474
 475         kaddr = kmap_local_page(dest_page);
 476         memcpy(kaddr, workspace->buf + start_byte, bytes);
 477
 478         /*
 479          * btrfs_getblock is doing a zero on the tail of the page too,
 480          * but this will cover anything missing from the decompressed
 481          * data.
 482          */
 483         if (bytes < destlen)
 484                 memset(kaddr+bytes, 0, destlen-bytes);
 485         kunmap_local(kaddr);
 486 out:
 487         return ret;
 488 }
 489
 490 const struct btrfs_compress_op btrfs_lzo_compress = {
 491         .workspace_manager      = &wsm,
 492         .max_level              = 1,
 493         .default_level          = 1,
 494 };