fs/btrfs/compression.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/bio.h>
   8 #include <linux/file.h>
   9 #include <linux/fs.h>
  10 #include <linux/pagemap.h>
  11 #include <linux/highmem.h>
  12 #include <linux/time.h>
  13 #include <linux/init.h>
  14 #include <linux/string.h>
  15 #include <linux/backing-dev.h>
  16 #include <linux/writeback.h>
  17 #include <linux/slab.h>
  18 #include <linux/sched/mm.h>
  19 #include <linux/log2.h>
  20 #include <crypto/hash.h>
  21 #include "misc.h"
  22 #include "ctree.h"
  23 #include "disk-io.h"
  24 #include "transaction.h"
  25 #include "btrfs_inode.h"
  26 #include "volumes.h"
  27 #include "ordered-data.h"
  28 #include "compression.h"
  29 #include "extent_io.h"
  30 #include "extent_map.h"
  31 #include "subpage.h"
  32 #include "zoned.h"
  33
  34 static const char* const btrfs_compress_types[] = { "", "zlib", "lzo", "zstd" };
  35
  36 const char* btrfs_compress_type2str(enum btrfs_compression_type type)
  37 {
  38         switch (type) {
  39         case BTRFS_COMPRESS_ZLIB:
  40         case BTRFS_COMPRESS_LZO:
  41         case BTRFS_COMPRESS_ZSTD:
  42         case BTRFS_COMPRESS_NONE:
  43                 return btrfs_compress_types[type];
  44         default:
  45                 break;
  46         }
  47
  48         return NULL;
  49 }
  50
  51 bool btrfs_compress_is_valid_type(const char *str, size_t len)
  52 {
  53         int i;
  54
  55         for (i = 1; i < ARRAY_SIZE(btrfs_compress_types); i++) {
  56                 size_t comp_len = strlen(btrfs_compress_types[i]);
  57
  58                 if (len < comp_len)
  59                         continue;
  60
  61                 if (!strncmp(btrfs_compress_types[i], str, comp_len))
  62                         return true;
  63         }
  64         return false;
  65 }
  66
  67 static int compression_compress_pages(int type, struct list_head *ws,
  68                struct address_space *mapping, u64 start, struct page **pages,
  69                unsigned long *out_pages, unsigned long *total_in,
  70                unsigned long *total_out)
  71 {
  72         switch (type) {
  73         case BTRFS_COMPRESS_ZLIB:
  74                 return zlib_compress_pages(ws, mapping, start, pages,
  75                                 out_pages, total_in, total_out);
  76         case BTRFS_COMPRESS_LZO:
  77                 return lzo_compress_pages(ws, mapping, start, pages,
  78                                 out_pages, total_in, total_out);
  79         case BTRFS_COMPRESS_ZSTD:
  80                 return zstd_compress_pages(ws, mapping, start, pages,
  81                                 out_pages, total_in, total_out);
  82         case BTRFS_COMPRESS_NONE:
  83         default:
  84                 /*
  85                  * This can happen when compression races with remount setting
  86                  * it to 'no compress', while caller doesn't call
  87                  * inode_need_compress() to check if we really need to
  88                  * compress.
  89                  *
  90                  * Not a big deal, just need to inform caller that we
  91                  * haven't allocated any pages yet.
  92                  */
  93                 *out_pages = 0;
  94                 return -E2BIG;
  95         }
  96 }
  97
  98 static int compression_decompress_bio(int type, struct list_head *ws,
  99                 struct compressed_bio *cb)
 100 {
 101         switch (type) {
 102         case BTRFS_COMPRESS_ZLIB: return zlib_decompress_bio(ws, cb);
 103         case BTRFS_COMPRESS_LZO:  return lzo_decompress_bio(ws, cb);
 104         case BTRFS_COMPRESS_ZSTD: return zstd_decompress_bio(ws, cb);
 105         case BTRFS_COMPRESS_NONE:
 106         default:
 107                 /*
 108                  * This can't happen, the type is validated several times
 109                  * before we get here.
 110                  */
 111                 BUG();
 112         }
 113 }
 114
 115 static int compression_decompress(int type, struct list_head *ws,
 116                unsigned char *data_in, struct page *dest_page,
 117                unsigned long start_byte, size_t srclen, size_t destlen)
 118 {
 119         switch (type) {
 120         case BTRFS_COMPRESS_ZLIB: return zlib_decompress(ws, data_in, dest_page,
 121                                                 start_byte, srclen, destlen);
 122         case BTRFS_COMPRESS_LZO:  return lzo_decompress(ws, data_in, dest_page,
 123                                                 start_byte, srclen, destlen);
 124         case BTRFS_COMPRESS_ZSTD: return zstd_decompress(ws, data_in, dest_page,
 125                                                 start_byte, srclen, destlen);
 126         case BTRFS_COMPRESS_NONE:
 127         default:
 128                 /*
 129                  * This can't happen, the type is validated several times
 130                  * before we get here.
 131                  */
 132                 BUG();
 133         }
 134 }
 135
 136 static int btrfs_decompress_bio(struct compressed_bio *cb);
 137
 138 static inline int compressed_bio_size(struct btrfs_fs_info *fs_info,
 139                                       unsigned long disk_size)
 140 {
 141         return sizeof(struct compressed_bio) +
 142                 (DIV_ROUND_UP(disk_size, fs_info->sectorsize)) * fs_info->csum_size;
 143 }
 144
 145 static int check_compressed_csum(struct btrfs_inode *inode, struct bio *bio,
 146                                  u64 disk_start)
 147 {
 148         struct btrfs_fs_info *fs_info = inode->root->fs_info;
 149         SHASH_DESC_ON_STACK(shash, fs_info->csum_shash);
 150         const u32 csum_size = fs_info->csum_size;
 151         const u32 sectorsize = fs_info->sectorsize;
 152         struct page *page;
 153         unsigned int i;
 154         char *kaddr;
 155         u8 csum[BTRFS_CSUM_SIZE];
 156         struct compressed_bio *cb = bio->bi_private;
 157         u8 *cb_sum = cb->sums;
 158
 159         if (!fs_info->csum_root || (inode->flags & BTRFS_INODE_NODATASUM))
 160                 return 0;
 161
 162         shash->tfm = fs_info->csum_shash;
 163
 164         for (i = 0; i < cb->nr_pages; i++) {
 165                 u32 pg_offset;
 166                 u32 bytes_left = PAGE_SIZE;
 167                 page = cb->compressed_pages[i];
 168
 169                 /* Determine the remaining bytes inside the page first */
 170                 if (i == cb->nr_pages - 1)
 171                         bytes_left = cb->compressed_len - i * PAGE_SIZE;
 172
 173                 /* Hash through the page sector by sector */
 174                 for (pg_offset = 0; pg_offset < bytes_left;
 175                      pg_offset += sectorsize) {
 176                         kaddr = page_address(page);
 177                         crypto_shash_digest(shash, kaddr + pg_offset,
 178                                             sectorsize, csum);
 179
 180                         if (memcmp(&csum, cb_sum, csum_size) != 0) {
 181                                 btrfs_print_data_csum_error(inode, disk_start,
 182                                                 csum, cb_sum, cb->mirror_num);
 183                                 if (btrfs_bio(bio)->device)
 184                                         btrfs_dev_stat_inc_and_print(
 185                                                 btrfs_bio(bio)->device,
 186                                                 BTRFS_DEV_STAT_CORRUPTION_ERRS);
 187                                 return -EIO;
 188                         }
 189                         cb_sum += csum_size;
 190                         disk_start += sectorsize;
 191                 }
 192         }
 193         return 0;
 194 }
 195
 196 /* when we finish reading compressed pages from the disk, we
 197  * decompress them and then run the bio end_io routines on the
 198  * decompressed pages (in the inode address space).
 199  *
 200  * This allows the checksumming and other IO error handling routines
 201  * to work normally
 202  *
 203  * The compressed pages are freed here, and it must be run
 204  * in process context
 205  */
 206 static void end_compressed_bio_read(struct bio *bio)
 207 {
 208         struct compressed_bio *cb = bio->bi_private;
 209         struct inode *inode;
 210         struct page *page;
 211         unsigned int index;
 212         unsigned int mirror = btrfs_bio(bio)->mirror_num;
 213         int ret = 0;
 214
 215         if (bio->bi_status)
 216                 cb->errors = 1;
 217
 218         /* if there are more bios still pending for this compressed
 219          * extent, just exit
 220          */
 221         if (!refcount_dec_and_test(&cb->pending_bios))
 222                 goto out;
 223
 224         /*
 225          * Record the correct mirror_num in cb->orig_bio so that
 226          * read-repair can work properly.
 227          */
 228         btrfs_bio(cb->orig_bio)->mirror_num = mirror;
 229         cb->mirror_num = mirror;
 230
 231         /*
 232          * Some IO in this cb have failed, just skip checksum as there
 233          * is no way it could be correct.
 234          */
 235         if (cb->errors == 1)
 236                 goto csum_failed;
 237
 238         inode = cb->inode;
 239         ret = check_compressed_csum(BTRFS_I(inode), bio,
 240                                     bio->bi_iter.bi_sector << 9);
 241         if (ret)
 242                 goto csum_failed;
 243
 244         /* ok, we're the last bio for this extent, lets start
 245          * the decompression.
 246          */
 247         ret = btrfs_decompress_bio(cb);
 248
 249 csum_failed:
 250         if (ret)
 251                 cb->errors = 1;
 252
 253         /* release the compressed pages */
 254         index = 0;
 255         for (index = 0; index < cb->nr_pages; index++) {
 256                 page = cb->compressed_pages[index];
 257                 page->mapping = NULL;
 258                 put_page(page);
 259         }
 260
 261         /* do io completion on the original bio */
 262         if (cb->errors) {
 263                 bio_io_error(cb->orig_bio);
 264         } else {
 265                 struct bio_vec *bvec;
 266                 struct bvec_iter_all iter_all;
 267
 268                 /*
 269                  * we have verified the checksum already, set page
 270                  * checked so the end_io handlers know about it
 271                  */
 272                 ASSERT(!bio_flagged(bio, BIO_CLONED));
 273                 bio_for_each_segment_all(bvec, cb->orig_bio, iter_all)
 274                         SetPageChecked(bvec->bv_page);
 275
 276                 bio_endio(cb->orig_bio);
 277         }
 278
 279         /* finally free the cb struct */
 280         kfree(cb->compressed_pages);
 281         kfree(cb);
 282 out:
 283         bio_put(bio);
 284 }
 285
 286 /*
 287  * Clear the writeback bits on all of the file
 288  * pages for a compressed write
 289  */
 290 static noinline void end_compressed_writeback(struct inode *inode,
 291                                               const struct compressed_bio *cb)
 292 {
 293         unsigned long index = cb->start >> PAGE_SHIFT;
 294         unsigned long end_index = (cb->start + cb->len - 1) >> PAGE_SHIFT;
 295         struct page *pages[16];
 296         unsigned long nr_pages = end_index - index + 1;
 297         int i;
 298         int ret;
 299
 300         if (cb->errors)
 301                 mapping_set_error(inode->i_mapping, -EIO);
 302
 303         while (nr_pages > 0) {
 304                 ret = find_get_pages_contig(inode->i_mapping, index,
 305                                      min_t(unsigned long,
 306                                      nr_pages, ARRAY_SIZE(pages)), pages);
 307                 if (ret == 0) {
 308                         nr_pages -= 1;
 309                         index += 1;
 310                         continue;
 311                 }
 312                 for (i = 0; i < ret; i++) {
 313                         if (cb->errors)
 314                                 SetPageError(pages[i]);
 315                         end_page_writeback(pages[i]);
 316                         put_page(pages[i]);
 317                 }
 318                 nr_pages -= ret;
 319                 index += ret;
 320         }
 321         /* the inode may be gone now */
 322 }
 323
 324 /*
 325  * do the cleanup once all the compressed pages hit the disk.
 326  * This will clear writeback on the file pages and free the compressed
 327  * pages.
 328  *
 329  * This also calls the writeback end hooks for the file pages so that
 330  * metadata and checksums can be updated in the file.
 331  */
 332 static void end_compressed_bio_write(struct bio *bio)
 333 {
 334         struct compressed_bio *cb = bio->bi_private;
 335         struct inode *inode;
 336         struct page *page;
 337         unsigned int index;
 338
 339         if (bio->bi_status)
 340                 cb->errors = 1;
 341
 342         /* if there are more bios still pending for this compressed
 343          * extent, just exit
 344          */
 345         if (!refcount_dec_and_test(&cb->pending_bios))
 346                 goto out;
 347
 348         /* ok, we're the last bio for this extent, step one is to
 349          * call back into the FS and do all the end_io operations
 350          */
 351         inode = cb->inode;
 352         btrfs_record_physical_zoned(inode, cb->start, bio);
 353         btrfs_writepage_endio_finish_ordered(BTRFS_I(inode), NULL,
 354                         cb->start, cb->start + cb->len - 1,
 355                         !cb->errors);
 356
 357         end_compressed_writeback(inode, cb);
 358         /* note, our inode could be gone now */
 359
 360         /*
 361          * release the compressed pages, these came from alloc_page and
 362          * are not attached to the inode at all
 363          */
 364         index = 0;
 365         for (index = 0; index < cb->nr_pages; index++) {
 366                 page = cb->compressed_pages[index];
 367                 page->mapping = NULL;
 368                 put_page(page);
 369         }
 370
 371         /* finally free the cb struct */
 372         kfree(cb->compressed_pages);
 373         kfree(cb);
 374 out:
 375         bio_put(bio);
 376 }
 377
 378 /*
 379  * worker function to build and submit bios for previously compressed pages.
 380  * The corresponding pages in the inode should be marked for writeback
 381  * and the compressed pages should have a reference on them for dropping
 382  * when the IO is complete.
 383  *
 384  * This also checksums the file bytes and gets things ready for
 385  * the end io hooks.
 386  */
 387 blk_status_t btrfs_submit_compressed_write(struct btrfs_inode *inode, u64 start,
 388                                  unsigned int len, u64 disk_start,
 389                                  unsigned int compressed_len,
 390                                  struct page **compressed_pages,
 391                                  unsigned int nr_pages,
 392                                  unsigned int write_flags,
 393                                  struct cgroup_subsys_state *blkcg_css)
 394 {
 395         struct btrfs_fs_info *fs_info = inode->root->fs_info;
 396         struct bio *bio = NULL;
 397         struct compressed_bio *cb;
 398         unsigned long bytes_left;
 399         int pg_index = 0;
 400         struct page *page;
 401         u64 first_byte = disk_start;
 402         blk_status_t ret;
 403         int skip_sum = inode->flags & BTRFS_INODE_NODATASUM;
 404         const bool use_append = btrfs_use_zone_append(inode, disk_start);
 405         const unsigned int bio_op = use_append ? REQ_OP_ZONE_APPEND : REQ_OP_WRITE;
 406
 407         WARN_ON(!PAGE_ALIGNED(start));
 408         cb = kmalloc(compressed_bio_size(fs_info, compressed_len), GFP_NOFS);
 409         if (!cb)
 410                 return BLK_STS_RESOURCE;
 411         refcount_set(&cb->pending_bios, 0);
 412         cb->errors = 0;
 413         cb->inode = &inode->vfs_inode;
 414         cb->start = start;
 415         cb->len = len;
 416         cb->mirror_num = 0;
 417         cb->compressed_pages = compressed_pages;
 418         cb->compressed_len = compressed_len;
 419         cb->orig_bio = NULL;
 420         cb->nr_pages = nr_pages;
 421
 422         bio = btrfs_bio_alloc(BIO_MAX_VECS);
 423         bio->bi_iter.bi_sector = first_byte >> SECTOR_SHIFT;
 424         bio->bi_opf = bio_op | write_flags;
 425         bio->bi_private = cb;
 426         bio->bi_end_io = end_compressed_bio_write;
 427
 428         if (use_append) {
 429                 struct btrfs_device *device;
 430
 431                 device = btrfs_zoned_get_device(fs_info, disk_start, PAGE_SIZE);
 432                 if (IS_ERR(device)) {
 433                         kfree(cb);
 434                         bio_put(bio);
 435                         return BLK_STS_NOTSUPP;
 436                 }
 437
 438                 bio_set_dev(bio, device->bdev);
 439         }
 440
 441         if (blkcg_css) {
 442                 bio->bi_opf |= REQ_CGROUP_PUNT;
 443                 kthread_associate_blkcg(blkcg_css);
 444         }
 445         refcount_set(&cb->pending_bios, 1);
 446
 447         /* create and submit bios for the compressed pages */
 448         bytes_left = compressed_len;
 449         for (pg_index = 0; pg_index < cb->nr_pages; pg_index++) {
 450                 int submit = 0;
 451                 int len = 0;
 452
 453                 page = compressed_pages[pg_index];
 454                 page->mapping = inode->vfs_inode.i_mapping;
 455                 if (bio->bi_iter.bi_size)
 456                         submit = btrfs_bio_fits_in_stripe(page, PAGE_SIZE, bio,
 457                                                           0);
 458
 459                 /*
 460                  * Page can only be added to bio if the current bio fits in
 461                  * stripe.
 462                  */
 463                 if (!submit) {
 464                         if (pg_index == 0 && use_append)
 465                                 len = bio_add_zone_append_page(bio, page,
 466                                                                PAGE_SIZE, 0);
 467                         else
 468                                 len = bio_add_page(bio, page, PAGE_SIZE, 0);
 469                 }
 470
 471                 page->mapping = NULL;
 472                 if (submit || len < PAGE_SIZE) {
 473                         /*
 474                          * inc the count before we submit the bio so
 475                          * we know the end IO handler won't happen before
 476                          * we inc the count.  Otherwise, the cb might get
 477                          * freed before we're done setting it up
 478                          */
 479                         refcount_inc(&cb->pending_bios);
 480                         ret = btrfs_bio_wq_end_io(fs_info, bio,
 481                                                   BTRFS_WQ_ENDIO_DATA);
 482                         BUG_ON(ret); /* -ENOMEM */
 483
 484                         if (!skip_sum) {
 485                                 ret = btrfs_csum_one_bio(inode, bio, start, 1);
 486                                 BUG_ON(ret); /* -ENOMEM */
 487                         }
 488
 489                         ret = btrfs_map_bio(fs_info, bio, 0);
 490                         if (ret) {
 491                                 bio->bi_status = ret;
 492                                 bio_endio(bio);
 493                         }
 494
 495                         bio = btrfs_bio_alloc(BIO_MAX_VECS);
 496                         bio->bi_iter.bi_sector = first_byte >> SECTOR_SHIFT;
 497                         bio->bi_opf = bio_op | write_flags;
 498                         bio->bi_private = cb;
 499                         bio->bi_end_io = end_compressed_bio_write;
 500                         if (blkcg_css)
 501                                 bio->bi_opf |= REQ_CGROUP_PUNT;
 502                         /*
 503                          * Use bio_add_page() to ensure the bio has at least one
 504                          * page.
 505                          */
 506                         bio_add_page(bio, page, PAGE_SIZE, 0);
 507                 }
 508                 if (bytes_left < PAGE_SIZE) {
 509                         btrfs_info(fs_info,
 510                                         "bytes left %lu compress len %u nr %u",
 511                                bytes_left, cb->compressed_len, cb->nr_pages);
 512                 }
 513                 bytes_left -= PAGE_SIZE;
 514                 first_byte += PAGE_SIZE;
 515                 cond_resched();
 516         }
 517
 518         ret = btrfs_bio_wq_end_io(fs_info, bio, BTRFS_WQ_ENDIO_DATA);
 519         BUG_ON(ret); /* -ENOMEM */
 520
 521         if (!skip_sum) {
 522                 ret = btrfs_csum_one_bio(inode, bio, start, 1);
 523                 BUG_ON(ret); /* -ENOMEM */
 524         }
 525
 526         ret = btrfs_map_bio(fs_info, bio, 0);
 527         if (ret) {
 528                 bio->bi_status = ret;
 529                 bio_endio(bio);
 530         }
 531
 532         if (blkcg_css)
 533                 kthread_associate_blkcg(NULL);
 534
 535         return 0;
 536 }
 537
 538 static u64 bio_end_offset(struct bio *bio)
 539 {
 540         struct bio_vec *last = bio_last_bvec_all(bio);
 541
 542         return page_offset(last->bv_page) + last->bv_len + last->bv_offset;
 543 }
 544
 545 /*
 546  * Add extra pages in the same compressed file extent so that we don't need to
 547  * re-read the same extent again and again.
 548  *
 549  * NOTE: this won't work well for subpage, as for subpage read, we lock the
 550  * full page then submit bio for each compressed/regular extents.
 551  *
 552  * This means, if we have several sectors in the same page points to the same
 553  * on-disk compressed data, we will re-read the same extent many times and
 554  * this function can only help for the next page.
 555  */
 556 static noinline int add_ra_bio_pages(struct inode *inode,
 557                                      u64 compressed_end,
 558                                      struct compressed_bio *cb)
 559 {
 560         struct btrfs_fs_info *fs_info = btrfs_sb(inode->i_sb);
 561         unsigned long end_index;
 562         u64 cur = bio_end_offset(cb->orig_bio);
 563         u64 isize = i_size_read(inode);
 564         int ret;
 565         struct page *page;
 566         struct extent_map *em;
 567         struct address_space *mapping = inode->i_mapping;
 568         struct extent_map_tree *em_tree;
 569         struct extent_io_tree *tree;
 570         int sectors_missed = 0;
 571
 572         em_tree = &BTRFS_I(inode)->extent_tree;
 573         tree = &BTRFS_I(inode)->io_tree;
 574
 575         if (isize == 0)
 576                 return 0;
 577
 578         /*
 579          * For current subpage support, we only support 64K page size,
 580          * which means maximum compressed extent size (128K) is just 2x page
 581          * size.
 582          * This makes readahead less effective, so here disable readahead for
 583          * subpage for now, until full compressed write is supported.
 584          */
 585         if (btrfs_sb(inode->i_sb)->sectorsize < PAGE_SIZE)
 586                 return 0;
 587
 588         end_index = (i_size_read(inode) - 1) >> PAGE_SHIFT;
 589
 590         while (cur < compressed_end) {
 591                 u64 page_end;
 592                 u64 pg_index = cur >> PAGE_SHIFT;
 593                 u32 add_size;
 594
 595                 if (pg_index > end_index)
 596                         break;
 597
 598                 page = xa_load(&mapping->i_pages, pg_index);
 599                 if (page && !xa_is_value(page)) {
 600                         sectors_missed += (PAGE_SIZE - offset_in_page(cur)) >>
 601                                           fs_info->sectorsize_bits;
 602
 603                         /* Beyond threshold, no need to continue */
 604                         if (sectors_missed > 4)
 605                                 break;
 606
 607                         /*
 608                          * Jump to next page start as we already have page for
 609                          * current offset.
 610                          */
 611                         cur = (pg_index << PAGE_SHIFT) + PAGE_SIZE;
 612                         continue;
 613                 }
 614
 615                 page = __page_cache_alloc(mapping_gfp_constraint(mapping,
 616                                                                  ~__GFP_FS));
 617                 if (!page)
 618                         break;
 619
 620                 if (add_to_page_cache_lru(page, mapping, pg_index, GFP_NOFS)) {
 621                         put_page(page);
 622                         /* There is already a page, skip to page end */
 623                         cur = (pg_index << PAGE_SHIFT) + PAGE_SIZE;
 624                         continue;
 625                 }
 626
 627                 ret = set_page_extent_mapped(page);
 628                 if (ret < 0) {
 629                         unlock_page(page);
 630                         put_page(page);
 631                         break;
 632                 }
 633
 634                 page_end = (pg_index << PAGE_SHIFT) + PAGE_SIZE - 1;
 635                 lock_extent(tree, cur, page_end);
 636                 read_lock(&em_tree->lock);
 637                 em = lookup_extent_mapping(em_tree, cur, page_end + 1 - cur);
 638                 read_unlock(&em_tree->lock);
 639
 640                 /*
 641                  * At this point, we have a locked page in the page cache for
 642                  * these bytes in the file.  But, we have to make sure they map
 643                  * to this compressed extent on disk.
 644                  */
 645                 if (!em || cur < em->start ||
 646                     (cur + fs_info->sectorsize > extent_map_end(em)) ||
 647                     (em->block_start >> 9) != cb->orig_bio->bi_iter.bi_sector) {
 648                         free_extent_map(em);
 649                         unlock_extent(tree, cur, page_end);
 650                         unlock_page(page);
 651                         put_page(page);
 652                         break;
 653                 }
 654                 free_extent_map(em);
 655
 656                 if (page->index == end_index) {
 657                         size_t zero_offset = offset_in_page(isize);
 658
 659                         if (zero_offset) {
 660                                 int zeros;
 661                                 zeros = PAGE_SIZE - zero_offset;
 662                                 memzero_page(page, zero_offset, zeros);
 663                                 flush_dcache_page(page);
 664                         }
 665                 }
 666
 667                 add_size = min(em->start + em->len, page_end + 1) - cur;
 668                 ret = bio_add_page(cb->orig_bio, page, add_size, offset_in_page(cur));
 669                 if (ret != add_size) {
 670                         unlock_extent(tree, cur, page_end);
 671                         unlock_page(page);
 672                         put_page(page);
 673                         break;
 674                 }
 675                 /*
 676                  * If it's subpage, we also need to increase its
 677                  * subpage::readers number, as at endio we will decrease
 678                  * subpage::readers and to unlock the page.
 679                  */
 680                 if (fs_info->sectorsize < PAGE_SIZE)
 681                         btrfs_subpage_start_reader(fs_info, page, cur, add_size);
 682                 put_page(page);
 683                 cur += add_size;
 684         }
 685         return 0;
 686 }
 687
 688 /*
 689  * for a compressed read, the bio we get passed has all the inode pages
 690  * in it.  We don't actually do IO on those pages but allocate new ones
 691  * to hold the compressed pages on disk.
 692  *
 693  * bio->bi_iter.bi_sector points to the compressed extent on disk
 694  * bio->bi_io_vec points to all of the inode pages
 695  *
 696  * After the compressed pages are read, we copy the bytes into the
 697  * bio we were passed and then call the bio end_io calls
 698  */
 699 blk_status_t btrfs_submit_compressed_read(struct inode *inode, struct bio *bio,
 700                                  int mirror_num, unsigned long bio_flags)
 701 {
 702         struct btrfs_fs_info *fs_info = btrfs_sb(inode->i_sb);
 703         struct extent_map_tree *em_tree;
 704         struct compressed_bio *cb;
 705         unsigned int compressed_len;
 706         unsigned int nr_pages;
 707         unsigned int pg_index;
 708         struct page *page;
 709         struct bio *comp_bio;
 710         u64 cur_disk_byte = bio->bi_iter.bi_sector << 9;
 711         u64 file_offset;
 712         u64 em_len;
 713         u64 em_start;
 714         struct extent_map *em;
 715         blk_status_t ret = BLK_STS_RESOURCE;
 716         int faili = 0;
 717         u8 *sums;
 718
 719         em_tree = &BTRFS_I(inode)->extent_tree;
 720
 721         file_offset = bio_first_bvec_all(bio)->bv_offset +
 722                       page_offset(bio_first_page_all(bio));
 723
 724         /* we need the actual starting offset of this extent in the file */
 725         read_lock(&em_tree->lock);
 726         em = lookup_extent_mapping(em_tree, file_offset, fs_info->sectorsize);
 727         read_unlock(&em_tree->lock);
 728         if (!em)
 729                 return BLK_STS_IOERR;
 730
 731         ASSERT(em->compress_type != BTRFS_COMPRESS_NONE);
 732         compressed_len = em->block_len;
 733         cb = kmalloc(compressed_bio_size(fs_info, compressed_len), GFP_NOFS);
 734         if (!cb)
 735                 goto out;
 736
 737         refcount_set(&cb->pending_bios, 0);
 738         cb->errors = 0;
 739         cb->inode = inode;
 740         cb->mirror_num = mirror_num;
 741         sums = cb->sums;
 742
 743         cb->start = em->orig_start;
 744         em_len = em->len;
 745         em_start = em->start;
 746
 747         free_extent_map(em);
 748         em = NULL;
 749
 750         cb->len = bio->bi_iter.bi_size;
 751         cb->compressed_len = compressed_len;
 752         cb->compress_type = extent_compress_type(bio_flags);
 753         cb->orig_bio = bio;
 754
 755         nr_pages = DIV_ROUND_UP(compressed_len, PAGE_SIZE);
 756         cb->compressed_pages = kcalloc(nr_pages, sizeof(struct page *),
 757                                        GFP_NOFS);
 758         if (!cb->compressed_pages)
 759                 goto fail1;
 760
 761         for (pg_index = 0; pg_index < nr_pages; pg_index++) {
 762                 cb->compressed_pages[pg_index] = alloc_page(GFP_NOFS);
 763                 if (!cb->compressed_pages[pg_index]) {
 764                         faili = pg_index - 1;
 765                         ret = BLK_STS_RESOURCE;
 766                         goto fail2;
 767                 }
 768         }
 769         faili = nr_pages - 1;
 770         cb->nr_pages = nr_pages;
 771
 772         add_ra_bio_pages(inode, em_start + em_len, cb);
 773
 774         /* include any pages we added in add_ra-bio_pages */
 775         cb->len = bio->bi_iter.bi_size;
 776
 777         comp_bio = btrfs_bio_alloc(BIO_MAX_VECS);
 778         comp_bio->bi_iter.bi_sector = cur_disk_byte >> SECTOR_SHIFT;
 779         comp_bio->bi_opf = REQ_OP_READ;
 780         comp_bio->bi_private = cb;
 781         comp_bio->bi_end_io = end_compressed_bio_read;
 782         refcount_set(&cb->pending_bios, 1);
 783
 784         for (pg_index = 0; pg_index < nr_pages; pg_index++) {
 785                 u32 pg_len = PAGE_SIZE;
 786                 int submit = 0;
 787
 788                 /*
 789                  * To handle subpage case, we need to make sure the bio only
 790                  * covers the range we need.
 791                  *
 792                  * If we're at the last page, truncate the length to only cover
 793                  * the remaining part.
 794                  */
 795                 if (pg_index == nr_pages - 1)
 796                         pg_len = min_t(u32, PAGE_SIZE,
 797                                         compressed_len - pg_index * PAGE_SIZE);
 798
 799                 page = cb->compressed_pages[pg_index];
 800                 page->mapping = inode->i_mapping;
 801                 page->index = em_start >> PAGE_SHIFT;
 802
 803                 if (comp_bio->bi_iter.bi_size)
 804                         submit = btrfs_bio_fits_in_stripe(page, pg_len,
 805                                                           comp_bio, 0);
 806
 807                 page->mapping = NULL;
 808                 if (submit || bio_add_page(comp_bio, page, pg_len, 0) < pg_len) {
 809                         unsigned int nr_sectors;
 810
 811                         ret = btrfs_bio_wq_end_io(fs_info, comp_bio,
 812                                                   BTRFS_WQ_ENDIO_DATA);
 813                         BUG_ON(ret); /* -ENOMEM */
 814
 815                         /*
 816                          * inc the count before we submit the bio so
 817                          * we know the end IO handler won't happen before
 818                          * we inc the count.  Otherwise, the cb might get
 819                          * freed before we're done setting it up
 820                          */
 821                         refcount_inc(&cb->pending_bios);
 822
 823                         ret = btrfs_lookup_bio_sums(inode, comp_bio, sums);
 824                         BUG_ON(ret); /* -ENOMEM */
 825
 826                         nr_sectors = DIV_ROUND_UP(comp_bio->bi_iter.bi_size,
 827                                                   fs_info->sectorsize);
 828                         sums += fs_info->csum_size * nr_sectors;
 829
 830                         ret = btrfs_map_bio(fs_info, comp_bio, mirror_num);
 831                         if (ret) {
 832                                 comp_bio->bi_status = ret;
 833                                 bio_endio(comp_bio);
 834                         }
 835
 836                         comp_bio = btrfs_bio_alloc(BIO_MAX_VECS);
 837                         comp_bio->bi_iter.bi_sector = cur_disk_byte >> SECTOR_SHIFT;
 838                         comp_bio->bi_opf = REQ_OP_READ;
 839                         comp_bio->bi_private = cb;
 840                         comp_bio->bi_end_io = end_compressed_bio_read;
 841
 842                         bio_add_page(comp_bio, page, pg_len, 0);
 843                 }
 844                 cur_disk_byte += pg_len;
 845         }
 846
 847         ret = btrfs_bio_wq_end_io(fs_info, comp_bio, BTRFS_WQ_ENDIO_DATA);
 848         BUG_ON(ret); /* -ENOMEM */
 849
 850         ret = btrfs_lookup_bio_sums(inode, comp_bio, sums);
 851         BUG_ON(ret); /* -ENOMEM */
 852
 853         ret = btrfs_map_bio(fs_info, comp_bio, mirror_num);
 854         if (ret) {
 855                 comp_bio->bi_status = ret;
 856                 bio_endio(comp_bio);
 857         }
 858
 859         return 0;
 860
 861 fail2:
 862         while (faili >= 0) {
 863                 __free_page(cb->compressed_pages[faili]);
 864                 faili--;
 865         }
 866
 867         kfree(cb->compressed_pages);
 868 fail1:
 869         kfree(cb);
 870 out:
 871         free_extent_map(em);
 872         return ret;
 873 }
 874
 875 /*
 876  * Heuristic uses systematic sampling to collect data from the input data
 877  * range, the logic can be tuned by the following constants:
 878  *
 879  * @SAMPLING_READ_SIZE - how many bytes will be copied from for each sample
 880  * @SAMPLING_INTERVAL  - range from which the sampled data can be collected
 881  */
 882 #define SAMPLING_READ_SIZE      (16)
 883 #define SAMPLING_INTERVAL       (256)
 884
 885 /*
 886  * For statistical analysis of the input data we consider bytes that form a
 887  * Galois Field of 256 objects. Each object has an attribute count, ie. how
 888  * many times the object appeared in the sample.
 889  */
 890 #define BUCKET_SIZE             (256)
 891
 892 /*
 893  * The size of the sample is based on a statistical sampling rule of thumb.
 894  * The common way is to perform sampling tests as long as the number of
 895  * elements in each cell is at least 5.
 896  *
 897  * Instead of 5, we choose 32 to obtain more accurate results.
 898  * If the data contain the maximum number of symbols, which is 256, we obtain a
 899  * sample size bound by 8192.
 900  *
 901  * For a sample of at most 8KB of data per data range: 16 consecutive bytes
 902  * from up to 512 locations.
 903  */
 904 #define MAX_SAMPLE_SIZE         (BTRFS_MAX_UNCOMPRESSED *               \
 905                                  SAMPLING_READ_SIZE / SAMPLING_INTERVAL)
 906
 907 struct bucket_item {
 908         u32 count;
 909 };
 910
 911 struct heuristic_ws {
 912         /* Partial copy of input data */
 913         u8 *sample;
 914         u32 sample_size;
 915         /* Buckets store counters for each byte value */
 916         struct bucket_item *bucket;
 917         /* Sorting buffer */
 918         struct bucket_item *bucket_b;
 919         struct list_head list;
 920 };
 921
 922 static struct workspace_manager heuristic_wsm;
 923
 924 static void free_heuristic_ws(struct list_head *ws)
 925 {
 926         struct heuristic_ws *workspace;
 927
 928         workspace = list_entry(ws, struct heuristic_ws, list);
 929
 930         kvfree(workspace->sample);
 931         kfree(workspace->bucket);
 932         kfree(workspace->bucket_b);
 933         kfree(workspace);
 934 }
 935
 936 static struct list_head *alloc_heuristic_ws(unsigned int level)
 937 {
 938         struct heuristic_ws *ws;
 939
 940         ws = kzalloc(sizeof(*ws), GFP_KERNEL);
 941         if (!ws)
 942                 return ERR_PTR(-ENOMEM);
 943
 944         ws->sample = kvmalloc(MAX_SAMPLE_SIZE, GFP_KERNEL);
 945         if (!ws->sample)
 946                 goto fail;
 947
 948         ws->bucket = kcalloc(BUCKET_SIZE, sizeof(*ws->bucket), GFP_KERNEL);
 949         if (!ws->bucket)
 950                 goto fail;
 951
 952         ws->bucket_b = kcalloc(BUCKET_SIZE, sizeof(*ws->bucket_b), GFP_KERNEL);
 953         if (!ws->bucket_b)
 954                 goto fail;
 955
 956         INIT_LIST_HEAD(&ws->list);
 957         return &ws->list;
 958 fail:
 959         free_heuristic_ws(&ws->list);
 960         return ERR_PTR(-ENOMEM);
 961 }
 962
 963 const struct btrfs_compress_op btrfs_heuristic_compress = {
 964         .workspace_manager = &heuristic_wsm,
 965 };
 966
 967 static const struct btrfs_compress_op * const btrfs_compress_op[] = {
 968         /* The heuristic is represented as compression type 0 */
 969         &btrfs_heuristic_compress,
 970         &btrfs_zlib_compress,
 971         &btrfs_lzo_compress,
 972         &btrfs_zstd_compress,
 973 };
 974
 975 static struct list_head *alloc_workspace(int type, unsigned int level)
 976 {
 977         switch (type) {
 978         case BTRFS_COMPRESS_NONE: return alloc_heuristic_ws(level);
 979         case BTRFS_COMPRESS_ZLIB: return zlib_alloc_workspace(level);
 980         case BTRFS_COMPRESS_LZO:  return lzo_alloc_workspace(level);
 981         case BTRFS_COMPRESS_ZSTD: return zstd_alloc_workspace(level);
 982         default:
 983                 /*
 984                  * This can't happen, the type is validated several times
 985                  * before we get here.
 986                  */
 987                 BUG();
 988         }
 989 }
 990
 991 static void free_workspace(int type, struct list_head *ws)
 992 {
 993         switch (type) {
 994         case BTRFS_COMPRESS_NONE: return free_heuristic_ws(ws);
 995         case BTRFS_COMPRESS_ZLIB: return zlib_free_workspace(ws);
 996         case BTRFS_COMPRESS_LZO:  return lzo_free_workspace(ws);
 997         case BTRFS_COMPRESS_ZSTD: return zstd_free_workspace(ws);
 998         default:
 999                 /*
1000                  * This can't happen, the type is validated several times
1001                  * before we get here.
1002                  */
1003                 BUG();
1004         }
1005 }
1006
1007 static void btrfs_init_workspace_manager(int type)
1008 {
1009         struct workspace_manager *wsm;
1010         struct list_head *workspace;
1011
1012         wsm = btrfs_compress_op[type]->workspace_manager;
1013         INIT_LIST_HEAD(&wsm->idle_ws);
1014         spin_lock_init(&wsm->ws_lock);
1015         atomic_set(&wsm->total_ws, 0);
1016         init_waitqueue_head(&wsm->ws_wait);
1017
1018         /*
1019          * Preallocate one workspace for each compression type so we can
1020          * guarantee forward progress in the worst case
1021          */
1022         workspace = alloc_workspace(type, 0);
1023         if (IS_ERR(workspace)) {
1024                 pr_warn(
1025         "BTRFS: cannot preallocate compression workspace, will try later\n");
1026         } else {
1027                 atomic_set(&wsm->total_ws, 1);
1028                 wsm->free_ws = 1;
1029                 list_add(workspace, &wsm->idle_ws);
1030         }
1031 }
1032
1033 static void btrfs_cleanup_workspace_manager(int type)
1034 {
1035         struct workspace_manager *wsman;
1036         struct list_head *ws;
1037
1038         wsman = btrfs_compress_op[type]->workspace_manager;
1039         while (!list_empty(&wsman->idle_ws)) {
1040                 ws = wsman->idle_ws.next;
1041                 list_del(ws);
1042                 free_workspace(type, ws);
1043                 atomic_dec(&wsman->total_ws);
1044         }
1045 }
1046
1047 /*
1048  * This finds an available workspace or allocates a new one.
1049  * If it's not possible to allocate a new one, waits until there's one.
1050  * Preallocation makes a forward progress guarantees and we do not return
1051  * errors.
1052  */
1053 struct list_head *btrfs_get_workspace(int type, unsigned int level)
1054 {
1055         struct workspace_manager *wsm;
1056         struct list_head *workspace;
1057         int cpus = num_online_cpus();
1058         unsigned nofs_flag;
1059         struct list_head *idle_ws;
1060         spinlock_t *ws_lock;
1061         atomic_t *total_ws;
1062         wait_queue_head_t *ws_wait;
1063         int *free_ws;
1064
1065         wsm = btrfs_compress_op[type]->workspace_manager;
1066         idle_ws  = &wsm->idle_ws;
1067         ws_lock  = &wsm->ws_lock;
1068         total_ws = &wsm->total_ws;
1069         ws_wait  = &wsm->ws_wait;
1070         free_ws  = &wsm->free_ws;
1071
1072 again:
1073         spin_lock(ws_lock);
1074         if (!list_empty(idle_ws)) {
1075                 workspace = idle_ws->next;
1076                 list_del(workspace);
1077                 (*free_ws)--;
1078                 spin_unlock(ws_lock);
1079                 return workspace;
1080
1081         }
1082         if (atomic_read(total_ws) > cpus) {
1083                 DEFINE_WAIT(wait);
1084
1085                 spin_unlock(ws_lock);
1086                 prepare_to_wait(ws_wait, &wait, TASK_UNINTERRUPTIBLE);
1087                 if (atomic_read(total_ws) > cpus && !*free_ws)
1088                         schedule();
1089                 finish_wait(ws_wait, &wait);
1090                 goto again;
1091         }
1092         atomic_inc(total_ws);
1093         spin_unlock(ws_lock);
1094
1095         /*
1096          * Allocation helpers call vmalloc that can't use GFP_NOFS, so we have
1097          * to turn it off here because we might get called from the restricted
1098          * context of btrfs_compress_bio/btrfs_compress_pages
1099          */
1100         nofs_flag = memalloc_nofs_save();
1101         workspace = alloc_workspace(type, level);
1102         memalloc_nofs_restore(nofs_flag);
1103
1104         if (IS_ERR(workspace)) {
1105                 atomic_dec(total_ws);
1106                 wake_up(ws_wait);
1107
1108                 /*
1109                  * Do not return the error but go back to waiting. There's a
1110                  * workspace preallocated for each type and the compression
1111                  * time is bounded so we get to a workspace eventually. This
1112                  * makes our caller's life easier.
1113                  *
1114                  * To prevent silent and low-probability deadlocks (when the
1115                  * initial preallocation fails), check if there are any
1116                  * workspaces at all.
1117                  */
1118                 if (atomic_read(total_ws) == 0) {
1119                         static DEFINE_RATELIMIT_STATE(_rs,
1120                                         /* once per minute */ 60 * HZ,
1121                                         /* no burst */ 1);
1122
1123                         if (__ratelimit(&_rs)) {
1124                                 pr_warn("BTRFS: no compression workspaces, low memory, retrying\n");
1125                         }
1126                 }
1127                 goto again;
1128         }
1129         return workspace;
1130 }
1131
1132 static struct list_head *get_workspace(int type, int level)
1133 {
1134         switch (type) {
1135         case BTRFS_COMPRESS_NONE: return btrfs_get_workspace(type, level);
1136         case BTRFS_COMPRESS_ZLIB: return zlib_get_workspace(level);
1137         case BTRFS_COMPRESS_LZO:  return btrfs_get_workspace(type, level);
1138         case BTRFS_COMPRESS_ZSTD: return zstd_get_workspace(level);
1139         default:
1140                 /*
1141                  * This can't happen, the type is validated several times
1142                  * before we get here.
1143                  */
1144                 BUG();
1145         }
1146 }
1147
1148 /*
1149  * put a workspace struct back on the list or free it if we have enough
1150  * idle ones sitting around
1151  */
1152 void btrfs_put_workspace(int type, struct list_head *ws)
1153 {
1154         struct workspace_manager *wsm;
1155         struct list_head *idle_ws;
1156         spinlock_t *ws_lock;
1157         atomic_t *total_ws;
1158         wait_queue_head_t *ws_wait;
1159         int *free_ws;
1160
1161         wsm = btrfs_compress_op[type]->workspace_manager;
1162         idle_ws  = &wsm->idle_ws;
1163         ws_lock  = &wsm->ws_lock;
1164         total_ws = &wsm->total_ws;
1165         ws_wait  = &wsm->ws_wait;
1166         free_ws  = &wsm->free_ws;
1167
1168         spin_lock(ws_lock);
1169         if (*free_ws <= num_online_cpus()) {
1170                 list_add(ws, idle_ws);
1171                 (*free_ws)++;
1172                 spin_unlock(ws_lock);
1173                 goto wake;
1174         }
1175         spin_unlock(ws_lock);
1176
1177         free_workspace(type, ws);
1178         atomic_dec(total_ws);
1179 wake:
1180         cond_wake_up(ws_wait);
1181 }
1182
1183 static void put_workspace(int type, struct list_head *ws)
1184 {
1185         switch (type) {
1186         case BTRFS_COMPRESS_NONE: return btrfs_put_workspace(type, ws);
1187         case BTRFS_COMPRESS_ZLIB: return btrfs_put_workspace(type, ws);
1188         case BTRFS_COMPRESS_LZO:  return btrfs_put_workspace(type, ws);
1189         case BTRFS_COMPRESS_ZSTD: return zstd_put_workspace(ws);
1190         default:
1191                 /*
1192                  * This can't happen, the type is validated several times
1193                  * before we get here.
1194                  */
1195                 BUG();
1196         }
1197 }
1198
1199 /*
1200  * Adjust @level according to the limits of the compression algorithm or
1201  * fallback to default
1202  */
1203 static unsigned int btrfs_compress_set_level(int type, unsigned level)
1204 {
1205         const struct btrfs_compress_op *ops = btrfs_compress_op[type];
1206
1207         if (level == 0)
1208                 level = ops->default_level;
1209         else
1210                 level = min(level, ops->max_level);
1211
1212         return level;
1213 }
1214
1215 /*
1216  * Given an address space and start and length, compress the bytes into @pages
1217  * that are allocated on demand.
1218  *
1219  * @type_level is encoded algorithm and level, where level 0 means whatever
1220  * default the algorithm chooses and is opaque here;
1221  * - compression algo are 0-3
1222  * - the level are bits 4-7
1223  *
1224  * @out_pages is an in/out parameter, holds maximum number of pages to allocate
1225  * and returns number of actually allocated pages
1226  *
1227  * @total_in is used to return the number of bytes actually read.  It
1228  * may be smaller than the input length if we had to exit early because we
1229  * ran out of room in the pages array or because we cross the
1230  * max_out threshold.
1231  *
1232  * @total_out is an in/out parameter, must be set to the input length and will
1233  * be also used to return the total number of compressed bytes
1234  */
1235 int btrfs_compress_pages(unsigned int type_level, struct address_space *mapping,
1236                          u64 start, struct page **pages,
1237                          unsigned long *out_pages,
1238                          unsigned long *total_in,
1239                          unsigned long *total_out)
1240 {
1241         int type = btrfs_compress_type(type_level);
1242         int level = btrfs_compress_level(type_level);
1243         struct list_head *workspace;
1244         int ret;
1245
1246         level = btrfs_compress_set_level(type, level);
1247         workspace = get_workspace(type, level);
1248         ret = compression_compress_pages(type, workspace, mapping, start, pages,
1249                                          out_pages, total_in, total_out);
1250         put_workspace(type, workspace);
1251         return ret;
1252 }
1253
1254 static int btrfs_decompress_bio(struct compressed_bio *cb)
1255 {
1256         struct list_head *workspace;
1257         int ret;
1258         int type = cb->compress_type;
1259
1260         workspace = get_workspace(type, 0);
1261         ret = compression_decompress_bio(type, workspace, cb);
1262         put_workspace(type, workspace);
1263
1264         return ret;
1265 }
1266
1267 /*
1268  * a less complex decompression routine.  Our compressed data fits in a
1269  * single page, and we want to read a single page out of it.
1270  * start_byte tells us the offset into the compressed data we're interested in
1271  */
1272 int btrfs_decompress(int type, unsigned char *data_in, struct page *dest_page,
1273                      unsigned long start_byte, size_t srclen, size_t destlen)
1274 {
1275         struct list_head *workspace;
1276         int ret;
1277
1278         workspace = get_workspace(type, 0);
1279         ret = compression_decompress(type, workspace, data_in, dest_page,
1280                                      start_byte, srclen, destlen);
1281         put_workspace(type, workspace);
1282
1283         return ret;
1284 }
1285
1286 void __init btrfs_init_compress(void)
1287 {
1288         btrfs_init_workspace_manager(BTRFS_COMPRESS_NONE);
1289         btrfs_init_workspace_manager(BTRFS_COMPRESS_ZLIB);
1290         btrfs_init_workspace_manager(BTRFS_COMPRESS_LZO);
1291         zstd_init_workspace_manager();
1292 }
1293
1294 void __cold btrfs_exit_compress(void)
1295 {
1296         btrfs_cleanup_workspace_manager(BTRFS_COMPRESS_NONE);
1297         btrfs_cleanup_workspace_manager(BTRFS_COMPRESS_ZLIB);
1298         btrfs_cleanup_workspace_manager(BTRFS_COMPRESS_LZO);
1299         zstd_cleanup_workspace_manager();
1300 }
1301
1302 /*
1303  * Copy decompressed data from working buffer to pages.
1304  *
1305  * @buf:                The decompressed data buffer
1306  * @buf_len:            The decompressed data length
1307  * @decompressed:       Number of bytes that are already decompressed inside the
1308  *                      compressed extent
1309  * @cb:                 The compressed extent descriptor
1310  * @orig_bio:           The original bio that the caller wants to read for
1311  *
1312  * An easier to understand graph is like below:
1313  *
1314  *              |<- orig_bio ->|     |<- orig_bio->|
1315  *      |<-------      full decompressed extent      ----->|
1316  *      |<-----------    @cb range   ---->|
1317  *      |                       |<-- @buf_len -->|
1318  *      |<--- @decompressed --->|
1319  *
1320  * Note that, @cb can be a subpage of the full decompressed extent, but
1321  * @cb->start always has the same as the orig_file_offset value of the full
1322  * decompressed extent.
1323  *
1324  * When reading compressed extent, we have to read the full compressed extent,
1325  * while @orig_bio may only want part of the range.
1326  * Thus this function will ensure only data covered by @orig_bio will be copied
1327  * to.
1328  *
1329  * Return 0 if we have copied all needed contents for @orig_bio.
1330  * Return >0 if we need continue decompress.
1331  */
1332 int btrfs_decompress_buf2page(const char *buf, u32 buf_len,
1333                               struct compressed_bio *cb, u32 decompressed)
1334 {
1335         struct bio *orig_bio = cb->orig_bio;
1336         /* Offset inside the full decompressed extent */
1337         u32 cur_offset;
1338
1339         cur_offset = decompressed;
1340         /* The main loop to do the copy */
1341         while (cur_offset < decompressed + buf_len) {
1342                 struct bio_vec bvec;
1343                 size_t copy_len;
1344                 u32 copy_start;
1345                 /* Offset inside the full decompressed extent */
1346                 u32 bvec_offset;
1347
1348                 bvec = bio_iter_iovec(orig_bio, orig_bio->bi_iter);
1349                 /*
1350                  * cb->start may underflow, but subtracting that value can still
1351                  * give us correct offset inside the full decompressed extent.
1352                  */
1353                 bvec_offset = page_offset(bvec.bv_page) + bvec.bv_offset - cb->start;
1354
1355                 /* Haven't reached the bvec range, exit */
1356                 if (decompressed + buf_len <= bvec_offset)
1357                         return 1;
1358
1359                 copy_start = max(cur_offset, bvec_offset);
1360                 copy_len = min(bvec_offset + bvec.bv_len,
1361                                decompressed + buf_len) - copy_start;
1362                 ASSERT(copy_len);
1363
1364                 /*
1365                  * Extra range check to ensure we didn't go beyond
1366                  * @buf + @buf_len.
1367                  */
1368                 ASSERT(copy_start - decompressed < buf_len);
1369                 memcpy_to_page(bvec.bv_page, bvec.bv_offset,
1370                                buf + copy_start - decompressed, copy_len);
1371                 flush_dcache_page(bvec.bv_page);
1372                 cur_offset += copy_len;
1373
1374                 bio_advance(orig_bio, copy_len);
1375                 /* Finished the bio */
1376                 if (!orig_bio->bi_iter.bi_size)
1377                         return 0;
1378         }
1379         return 1;
1380 }
1381
1382 /*
1383  * Shannon Entropy calculation
1384  *
1385  * Pure byte distribution analysis fails to determine compressibility of data.
1386  * Try calculating entropy to estimate the average minimum number of bits
1387  * needed to encode the sampled data.
1388  *
1389  * For convenience, return the percentage of needed bits, instead of amount of
1390  * bits directly.
1391  *
1392  * @ENTROPY_LVL_ACEPTABLE - below that threshold, sample has low byte entropy
1393  *                          and can be compressible with high probability
1394  *
1395  * @ENTROPY_LVL_HIGH - data are not compressible with high probability
1396  *
1397  * Use of ilog2() decreases precision, we lower the LVL to 5 to compensate.
1398  */
1399 #define ENTROPY_LVL_ACEPTABLE           (65)
1400 #define ENTROPY_LVL_HIGH                (80)
1401
1402 /*
1403  * For increasead precision in shannon_entropy calculation,
1404  * let's do pow(n, M) to save more digits after comma:
1405  *
1406  * - maximum int bit length is 64
1407  * - ilog2(MAX_SAMPLE_SIZE)     -> 13
1408  * - 13 * 4 = 52 < 64           -> M = 4
1409  *
1410  * So use pow(n, 4).
1411  */
1412 static inline u32 ilog2_w(u64 n)
1413 {
1414         return ilog2(n * n * n * n);
1415 }
1416
1417 static u32 shannon_entropy(struct heuristic_ws *ws)
1418 {
1419         const u32 entropy_max = 8 * ilog2_w(2);
1420         u32 entropy_sum = 0;
1421         u32 p, p_base, sz_base;
1422         u32 i;
1423
1424         sz_base = ilog2_w(ws->sample_size);
1425         for (i = 0; i < BUCKET_SIZE && ws->bucket[i].count > 0; i++) {
1426                 p = ws->bucket[i].count;
1427                 p_base = ilog2_w(p);
1428                 entropy_sum += p * (sz_base - p_base);
1429         }
1430
1431         entropy_sum /= ws->sample_size;
1432         return entropy_sum * 100 / entropy_max;
1433 }
1434
1435 #define RADIX_BASE              4U
1436 #define COUNTERS_SIZE           (1U << RADIX_BASE)
1437
1438 static u8 get4bits(u64 num, int shift) {
1439         u8 low4bits;
1440
1441         num >>= shift;
1442         /* Reverse order */
1443         low4bits = (COUNTERS_SIZE - 1) - (num % COUNTERS_SIZE);
1444         return low4bits;
1445 }
1446
1447 /*
1448  * Use 4 bits as radix base
1449  * Use 16 u32 counters for calculating new position in buf array
1450  *
1451  * @array     - array that will be sorted
1452  * @array_buf - buffer array to store sorting results
1453  *              must be equal in size to @array
1454  * @num       - array size
1455  */
1456 static void radix_sort(struct bucket_item *array, struct bucket_item *array_buf,
1457                        int num)
1458 {
1459         u64 max_num;
1460         u64 buf_num;
1461         u32 counters[COUNTERS_SIZE];
1462         u32 new_addr;
1463         u32 addr;
1464         int bitlen;
1465         int shift;
1466         int i;
1467
1468         /*
1469          * Try avoid useless loop iterations for small numbers stored in big
1470          * counters.  Example: 48 33 4 ... in 64bit array
1471          */
1472         max_num = array[0].count;
1473         for (i = 1; i < num; i++) {
1474                 buf_num = array[i].count;
1475                 if (buf_num > max_num)
1476                         max_num = buf_num;
1477         }
1478
1479         buf_num = ilog2(max_num);
1480         bitlen = ALIGN(buf_num, RADIX_BASE * 2);
1481
1482         shift = 0;
1483         while (shift < bitlen) {
1484                 memset(counters, 0, sizeof(counters));
1485
1486                 for (i = 0; i < num; i++) {
1487                         buf_num = array[i].count;
1488                         addr = get4bits(buf_num, shift);
1489                         counters[addr]++;
1490                 }
1491
1492                 for (i = 1; i < COUNTERS_SIZE; i++)
1493                         counters[i] += counters[i - 1];
1494
1495                 for (i = num - 1; i >= 0; i--) {
1496                         buf_num = array[i].count;
1497                         addr = get4bits(buf_num, shift);
1498                         counters[addr]--;
1499                         new_addr = counters[addr];
1500                         array_buf[new_addr] = array[i];
1501                 }
1502
1503                 shift += RADIX_BASE;
1504
1505                 /*
1506                  * Normal radix expects to move data from a temporary array, to
1507                  * the main one.  But that requires some CPU time. Avoid that
1508                  * by doing another sort iteration to original array instead of
1509                  * memcpy()
1510                  */
1511                 memset(counters, 0, sizeof(counters));
1512
1513                 for (i = 0; i < num; i ++) {
1514                         buf_num = array_buf[i].count;
1515                         addr = get4bits(buf_num, shift);
1516                         counters[addr]++;
1517                 }
1518
1519                 for (i = 1; i < COUNTERS_SIZE; i++)
1520                         counters[i] += counters[i - 1];
1521
1522                 for (i = num - 1; i >= 0; i--) {
1523                         buf_num = array_buf[i].count;
1524                         addr = get4bits(buf_num, shift);
1525                         counters[addr]--;
1526                         new_addr = counters[addr];
1527                         array[new_addr] = array_buf[i];
1528                 }
1529
1530                 shift += RADIX_BASE;
1531         }
1532 }
1533
1534 /*
1535  * Size of the core byte set - how many bytes cover 90% of the sample
1536  *
1537  * There are several types of structured binary data that use nearly all byte
1538  * values. The distribution can be uniform and counts in all buckets will be
1539  * nearly the same (eg. encrypted data). Unlikely to be compressible.
1540  *
1541  * Other possibility is normal (Gaussian) distribution, where the data could
1542  * be potentially compressible, but we have to take a few more steps to decide
1543  * how much.
1544  *
1545  * @BYTE_CORE_SET_LOW  - main part of byte values repeated frequently,
1546  *                       compression algo can easy fix that
1547  * @BYTE_CORE_SET_HIGH - data have uniform distribution and with high
1548  *                       probability is not compressible
1549  */
1550 #define BYTE_CORE_SET_LOW               (64)
1551 #define BYTE_CORE_SET_HIGH              (200)
1552
1553 static int byte_core_set_size(struct heuristic_ws *ws)
1554 {
1555         u32 i;
1556         u32 coreset_sum = 0;
1557         const u32 core_set_threshold = ws->sample_size * 90 / 100;
1558         struct bucket_item *bucket = ws->bucket;
1559
1560         /* Sort in reverse order */
1561         radix_sort(ws->bucket, ws->bucket_b, BUCKET_SIZE);
1562
1563         for (i = 0; i < BYTE_CORE_SET_LOW; i++)
1564                 coreset_sum += bucket[i].count;
1565
1566         if (coreset_sum > core_set_threshold)
1567                 return i;
1568
1569         for (; i < BYTE_CORE_SET_HIGH && bucket[i].count > 0; i++) {
1570                 coreset_sum += bucket[i].count;
1571                 if (coreset_sum > core_set_threshold)
1572                         break;
1573         }
1574
1575         return i;
1576 }
1577
1578 /*
1579  * Count byte values in buckets.
1580  * This heuristic can detect textual data (configs, xml, json, html, etc).
1581  * Because in most text-like data byte set is restricted to limited number of
1582  * possible characters, and that restriction in most cases makes data easy to
1583  * compress.
1584  *
1585  * @BYTE_SET_THRESHOLD - consider all data within this byte set size:
1586  *      less - compressible
1587  *      more - need additional analysis
1588  */
1589 #define BYTE_SET_THRESHOLD              (64)
1590
1591 static u32 byte_set_size(const struct heuristic_ws *ws)
1592 {
1593         u32 i;
1594         u32 byte_set_size = 0;
1595
1596         for (i = 0; i < BYTE_SET_THRESHOLD; i++) {
1597                 if (ws->bucket[i].count > 0)
1598                         byte_set_size++;
1599         }
1600
1601         /*
1602          * Continue collecting count of byte values in buckets.  If the byte
1603          * set size is bigger then the threshold, it's pointless to continue,
1604          * the detection technique would fail for this type of data.
1605          */
1606         for (; i < BUCKET_SIZE; i++) {
1607                 if (ws->bucket[i].count > 0) {
1608                         byte_set_size++;
1609                         if (byte_set_size > BYTE_SET_THRESHOLD)
1610                                 return byte_set_size;
1611                 }
1612         }
1613
1614         return byte_set_size;
1615 }
1616
1617 static bool sample_repeated_patterns(struct heuristic_ws *ws)
1618 {
1619         const u32 half_of_sample = ws->sample_size / 2;
1620         const u8 *data = ws->sample;
1621
1622         return memcmp(&data[0], &data[half_of_sample], half_of_sample) == 0;
1623 }
1624
1625 static void heuristic_collect_sample(struct inode *inode, u64 start, u64 end,
1626                                      struct heuristic_ws *ws)
1627 {
1628         struct page *page;
1629         u64 index, index_end;
1630         u32 i, curr_sample_pos;
1631         u8 *in_data;
1632
1633         /*
1634          * Compression handles the input data by chunks of 128KiB
1635          * (defined by BTRFS_MAX_UNCOMPRESSED)
1636          *
1637          * We do the same for the heuristic and loop over the whole range.
1638          *
1639          * MAX_SAMPLE_SIZE - calculated under assumption that heuristic will
1640          * process no more than BTRFS_MAX_UNCOMPRESSED at a time.
1641          */
1642         if (end - start > BTRFS_MAX_UNCOMPRESSED)
1643                 end = start + BTRFS_MAX_UNCOMPRESSED;
1644
1645         index = start >> PAGE_SHIFT;
1646         index_end = end >> PAGE_SHIFT;
1647
1648         /* Don't miss unaligned end */
1649         if (!IS_ALIGNED(end, PAGE_SIZE))
1650                 index_end++;
1651
1652         curr_sample_pos = 0;
1653         while (index < index_end) {
1654                 page = find_get_page(inode->i_mapping, index);
1655                 in_data = kmap_local_page(page);
1656                 /* Handle case where the start is not aligned to PAGE_SIZE */
1657                 i = start % PAGE_SIZE;
1658                 while (i < PAGE_SIZE - SAMPLING_READ_SIZE) {
1659                         /* Don't sample any garbage from the last page */
1660                         if (start > end - SAMPLING_READ_SIZE)
1661                                 break;
1662                         memcpy(&ws->sample[curr_sample_pos], &in_data[i],
1663                                         SAMPLING_READ_SIZE);
1664                         i += SAMPLING_INTERVAL;
1665                         start += SAMPLING_INTERVAL;
1666                         curr_sample_pos += SAMPLING_READ_SIZE;
1667                 }
1668                 kunmap_local(in_data);
1669                 put_page(page);
1670
1671                 index++;
1672         }
1673
1674         ws->sample_size = curr_sample_pos;
1675 }
1676
1677 /*
1678  * Compression heuristic.
1679  *
1680  * For now is's a naive and optimistic 'return true', we'll extend the logic to
1681  * quickly (compared to direct compression) detect data characteristics
1682  * (compressible/uncompressible) to avoid wasting CPU time on uncompressible
1683  * data.
1684  *
1685  * The following types of analysis can be performed:
1686  * - detect mostly zero data
1687  * - detect data with low "byte set" size (text, etc)
1688  * - detect data with low/high "core byte" set
1689  *
1690  * Return non-zero if the compression should be done, 0 otherwise.
1691  */
1692 int btrfs_compress_heuristic(struct inode *inode, u64 start, u64 end)
1693 {
1694         struct list_head *ws_list = get_workspace(0, 0);
1695         struct heuristic_ws *ws;
1696         u32 i;
1697         u8 byte;
1698         int ret = 0;
1699
1700         ws = list_entry(ws_list, struct heuristic_ws, list);
1701
1702         heuristic_collect_sample(inode, start, end, ws);
1703
1704         if (sample_repeated_patterns(ws)) {
1705                 ret = 1;
1706                 goto out;
1707         }
1708
1709         memset(ws->bucket, 0, sizeof(*ws->bucket)*BUCKET_SIZE);
1710
1711         for (i = 0; i < ws->sample_size; i++) {
1712                 byte = ws->sample[i];
1713                 ws->bucket[byte].count++;
1714         }
1715
1716         i = byte_set_size(ws);
1717         if (i < BYTE_SET_THRESHOLD) {
1718                 ret = 2;
1719                 goto out;
1720         }
1721
1722         i = byte_core_set_size(ws);
1723         if (i <= BYTE_CORE_SET_LOW) {
1724                 ret = 3;
1725                 goto out;
1726         }
1727
1728         if (i >= BYTE_CORE_SET_HIGH) {
1729                 ret = 0;
1730                 goto out;
1731         }
1732
1733         i = shannon_entropy(ws);
1734         if (i <= ENTROPY_LVL_ACEPTABLE) {
1735                 ret = 4;
1736                 goto out;
1737         }
1738
1739         /*
1740          * For the levels below ENTROPY_LVL_HIGH, additional analysis would be
1741          * needed to give green light to compression.
1742          *
1743          * For now just assume that compression at that level is not worth the
1744          * resources because:
1745          *
1746          * 1. it is possible to defrag the data later
1747          *
1748          * 2. the data would turn out to be hardly compressible, eg. 150 byte
1749          * values, every bucket has counter at level ~54. The heuristic would
1750          * be confused. This can happen when data have some internal repeated
1751          * patterns like "abbacbbc...". This can be detected by analyzing
1752          * pairs of bytes, which is too costly.
1753          */
1754         if (i < ENTROPY_LVL_HIGH) {
1755                 ret = 5;
1756                 goto out;
1757         } else {
1758                 ret = 0;
1759                 goto out;
1760         }
1761
1762 out:
1763         put_workspace(0, ws_list);
1764         return ret;
1765 }
1766
1767 /*
1768  * Convert the compression suffix (eg. after "zlib" starting with ":") to
1769  * level, unrecognized string will set the default level
1770  */
1771 unsigned int btrfs_compress_str2level(unsigned int type, const char *str)
1772 {
1773         unsigned int level = 0;
1774         int ret;
1775
1776         if (!type)
1777                 return 0;
1778
1779         if (str[0] == ':') {
1780                 ret = kstrtouint(str + 1, 10, &level);
1781                 if (ret)
1782                         level = 0;
1783         }
1784
1785         level = btrfs_compress_set_level(type, level);
1786
1787         return level;
1788 }