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