fs/btrfs/extent_io.c

   1 // SPDX-License-Identifier: GPL-2.0
   2
   3 #include <linux/bitops.h>
   4 #include <linux/slab.h>
   5 #include <linux/bio.h>
   6 #include <linux/mm.h>
   7 #include <linux/pagemap.h>
   8 #include <linux/page-flags.h>
   9 #include <linux/spinlock.h>
  10 #include <linux/blkdev.h>
  11 #include <linux/swap.h>
  12 #include <linux/writeback.h>
  13 #include <linux/pagevec.h>
  14 #include <linux/prefetch.h>
  15 #include <linux/cleancache.h>
  16 #include "extent_io.h"
  17 #include "extent_map.h"
  18 #include "ctree.h"
  19 #include "btrfs_inode.h"
  20 #include "volumes.h"
  21 #include "check-integrity.h"
  22 #include "locking.h"
  23 #include "rcu-string.h"
  24 #include "backref.h"
  25 #include "disk-io.h"
  26
  27 static struct kmem_cache *extent_state_cache;
  28 static struct kmem_cache *extent_buffer_cache;
  29 static struct bio_set btrfs_bioset;
  30
  31 static inline bool extent_state_in_tree(const struct extent_state *state)
  32 {
  33         return !RB_EMPTY_NODE(&state->rb_node);
  34 }
  35
  36 #ifdef CONFIG_BTRFS_DEBUG
  37 static LIST_HEAD(buffers);
  38 static LIST_HEAD(states);
  39
  40 static DEFINE_SPINLOCK(leak_lock);
  41
  42 static inline
  43 void btrfs_leak_debug_add(struct list_head *new, struct list_head *head)
  44 {
  45         unsigned long flags;
  46
  47         spin_lock_irqsave(&leak_lock, flags);
  48         list_add(new, head);
  49         spin_unlock_irqrestore(&leak_lock, flags);
  50 }
  51
  52 static inline
  53 void btrfs_leak_debug_del(struct list_head *entry)
  54 {
  55         unsigned long flags;
  56
  57         spin_lock_irqsave(&leak_lock, flags);
  58         list_del(entry);
  59         spin_unlock_irqrestore(&leak_lock, flags);
  60 }
  61
  62 static inline
  63 void btrfs_leak_debug_check(void)
  64 {
  65         struct extent_state *state;
  66         struct extent_buffer *eb;
  67
  68         while (!list_empty(&states)) {
  69                 state = list_entry(states.next, struct extent_state, leak_list);
  70                 pr_err("BTRFS: state leak: start %llu end %llu state %u in tree %d refs %d\n",
  71                        state->start, state->end, state->state,
  72                        extent_state_in_tree(state),
  73                        refcount_read(&state->refs));
  74                 list_del(&state->leak_list);
  75                 kmem_cache_free(extent_state_cache, state);
  76         }
  77
  78         while (!list_empty(&buffers)) {
  79                 eb = list_entry(buffers.next, struct extent_buffer, leak_list);
  80                 pr_err("BTRFS: buffer leak start %llu len %lu refs %d bflags %lu\n",
  81                        eb->start, eb->len, atomic_read(&eb->refs), eb->bflags);
  82                 list_del(&eb->leak_list);
  83                 kmem_cache_free(extent_buffer_cache, eb);
  84         }
  85 }
  86
  87 #define btrfs_debug_check_extent_io_range(tree, start, end)             \
  88         __btrfs_debug_check_extent_io_range(__func__, (tree), (start), (end))
  89 static inline void __btrfs_debug_check_extent_io_range(const char *caller,
  90                 struct extent_io_tree *tree, u64 start, u64 end)
  91 {
  92         struct inode *inode = tree->private_data;
  93         u64 isize;
  94
  95         if (!inode || !is_data_inode(inode))
  96                 return;
  97
  98         isize = i_size_read(inode);
  99         if (end >= PAGE_SIZE && (end % 2) == 0 && end != isize - 1) {
 100                 btrfs_debug_rl(BTRFS_I(inode)->root->fs_info,
 101                     "%s: ino %llu isize %llu odd range [%llu,%llu]",
 102                         caller, btrfs_ino(BTRFS_I(inode)), isize, start, end);
 103         }
 104 }
 105 #else
 106 #define btrfs_leak_debug_add(new, head) do {} while (0)
 107 #define btrfs_leak_debug_del(entry)     do {} while (0)
 108 #define btrfs_leak_debug_check()        do {} while (0)
 109 #define btrfs_debug_check_extent_io_range(c, s, e)      do {} while (0)
 110 #endif
 111
 112 #define BUFFER_LRU_MAX 64
 113
 114 struct tree_entry {
 115         u64 start;
 116         u64 end;
 117         struct rb_node rb_node;
 118 };
 119
 120 struct extent_page_data {
 121         struct bio *bio;
 122         struct extent_io_tree *tree;
 123         /* tells writepage not to lock the state bits for this range
 124          * it still does the unlocking
 125          */
 126         unsigned int extent_locked:1;
 127
 128         /* tells the submit_bio code to use REQ_SYNC */
 129         unsigned int sync_io:1;
 130 };
 131
 132 static int add_extent_changeset(struct extent_state *state, unsigned bits,
 133                                  struct extent_changeset *changeset,
 134                                  int set)
 135 {
 136         int ret;
 137
 138         if (!changeset)
 139                 return 0;
 140         if (set && (state->state & bits) == bits)
 141                 return 0;
 142         if (!set && (state->state & bits) == 0)
 143                 return 0;
 144         changeset->bytes_changed += state->end - state->start + 1;
 145         ret = ulist_add(&changeset->range_changed, state->start, state->end,
 146                         GFP_ATOMIC);
 147         return ret;
 148 }
 149
 150 static int __must_check submit_one_bio(struct bio *bio, int mirror_num,
 151                                        unsigned long bio_flags)
 152 {
 153         blk_status_t ret = 0;
 154         struct bio_vec *bvec = bio_last_bvec_all(bio);
 155         struct page *page = bvec->bv_page;
 156         struct extent_io_tree *tree = bio->bi_private;
 157         u64 start;
 158
 159         start = page_offset(page) + bvec->bv_offset;
 160
 161         bio->bi_private = NULL;
 162
 163         if (tree->ops)
 164                 ret = tree->ops->submit_bio_hook(tree->private_data, bio,
 165                                            mirror_num, bio_flags, start);
 166         else
 167                 btrfsic_submit_bio(bio);
 168
 169         return blk_status_to_errno(ret);
 170 }
 171
 172 static void flush_write_bio(struct extent_page_data *epd)
 173 {
 174         if (epd->bio) {
 175                 int ret;
 176
 177                 ret = submit_one_bio(epd->bio, 0, 0);
 178                 BUG_ON(ret < 0); /* -ENOMEM */
 179                 epd->bio = NULL;
 180         }
 181 }
 182
 183 int __init extent_io_init(void)
 184 {
 185         extent_state_cache = kmem_cache_create("btrfs_extent_state",
 186                         sizeof(struct extent_state), 0,
 187                         SLAB_MEM_SPREAD, NULL);
 188         if (!extent_state_cache)
 189                 return -ENOMEM;
 190
 191         extent_buffer_cache = kmem_cache_create("btrfs_extent_buffer",
 192                         sizeof(struct extent_buffer), 0,
 193                         SLAB_MEM_SPREAD, NULL);
 194         if (!extent_buffer_cache)
 195                 goto free_state_cache;
 196
 197         if (bioset_init(&btrfs_bioset, BIO_POOL_SIZE,
 198                         offsetof(struct btrfs_io_bio, bio),
 199                         BIOSET_NEED_BVECS))
 200                 goto free_buffer_cache;
 201
 202         if (bioset_integrity_create(&btrfs_bioset, BIO_POOL_SIZE))
 203                 goto free_bioset;
 204
 205         return 0;
 206
 207 free_bioset:
 208         bioset_exit(&btrfs_bioset);
 209
 210 free_buffer_cache:
 211         kmem_cache_destroy(extent_buffer_cache);
 212         extent_buffer_cache = NULL;
 213
 214 free_state_cache:
 215         kmem_cache_destroy(extent_state_cache);
 216         extent_state_cache = NULL;
 217         return -ENOMEM;
 218 }
 219
 220 void __cold extent_io_exit(void)
 221 {
 222         btrfs_leak_debug_check();
 223
 224         /*
 225          * Make sure all delayed rcu free are flushed before we
 226          * destroy caches.
 227          */
 228         rcu_barrier();
 229         kmem_cache_destroy(extent_state_cache);
 230         kmem_cache_destroy(extent_buffer_cache);
 231         bioset_exit(&btrfs_bioset);
 232 }
 233
 234 void extent_io_tree_init(struct extent_io_tree *tree,
 235                          void *private_data)
 236 {
 237         tree->state = RB_ROOT;
 238         tree->ops = NULL;
 239         tree->dirty_bytes = 0;
 240         spin_lock_init(&tree->lock);
 241         tree->private_data = private_data;
 242 }
 243
 244 static struct extent_state *alloc_extent_state(gfp_t mask)
 245 {
 246         struct extent_state *state;
 247
 248         /*
 249          * The given mask might be not appropriate for the slab allocator,
 250          * drop the unsupported bits
 251          */
 252         mask &= ~(__GFP_DMA32|__GFP_HIGHMEM);
 253         state = kmem_cache_alloc(extent_state_cache, mask);
 254         if (!state)
 255                 return state;
 256         state->state = 0;
 257         state->failrec = NULL;
 258         RB_CLEAR_NODE(&state->rb_node);
 259         btrfs_leak_debug_add(&state->leak_list, &states);
 260         refcount_set(&state->refs, 1);
 261         init_waitqueue_head(&state->wq);
 262         trace_alloc_extent_state(state, mask, _RET_IP_);
 263         return state;
 264 }
 265
 266 void free_extent_state(struct extent_state *state)
 267 {
 268         if (!state)
 269                 return;
 270         if (refcount_dec_and_test(&state->refs)) {
 271                 WARN_ON(extent_state_in_tree(state));
 272                 btrfs_leak_debug_del(&state->leak_list);
 273                 trace_free_extent_state(state, _RET_IP_);
 274                 kmem_cache_free(extent_state_cache, state);
 275         }
 276 }
 277
 278 static struct rb_node *tree_insert(struct rb_root *root,
 279                                    struct rb_node *search_start,
 280                                    u64 offset,
 281                                    struct rb_node *node,
 282                                    struct rb_node ***p_in,
 283                                    struct rb_node **parent_in)
 284 {
 285         struct rb_node **p;
 286         struct rb_node *parent = NULL;
 287         struct tree_entry *entry;
 288
 289         if (p_in && parent_in) {
 290                 p = *p_in;
 291                 parent = *parent_in;
 292                 goto do_insert;
 293         }
 294
 295         p = search_start ? &search_start : &root->rb_node;
 296         while (*p) {
 297                 parent = *p;
 298                 entry = rb_entry(parent, struct tree_entry, rb_node);
 299
 300                 if (offset < entry->start)
 301                         p = &(*p)->rb_left;
 302                 else if (offset > entry->end)
 303                         p = &(*p)->rb_right;
 304                 else
 305                         return parent;
 306         }
 307
 308 do_insert:
 309         rb_link_node(node, parent, p);
 310         rb_insert_color(node, root);
 311         return NULL;
 312 }
 313
 314 static struct rb_node *__etree_search(struct extent_io_tree *tree, u64 offset,
 315                                       struct rb_node **next_ret,
 316                                       struct rb_node **prev_ret,
 317                                       struct rb_node ***p_ret,
 318                                       struct rb_node **parent_ret)
 319 {
 320         struct rb_root *root = &tree->state;
 321         struct rb_node **n = &root->rb_node;
 322         struct rb_node *prev = NULL;
 323         struct rb_node *orig_prev = NULL;
 324         struct tree_entry *entry;
 325         struct tree_entry *prev_entry = NULL;
 326
 327         while (*n) {
 328                 prev = *n;
 329                 entry = rb_entry(prev, struct tree_entry, rb_node);
 330                 prev_entry = entry;
 331
 332                 if (offset < entry->start)
 333                         n = &(*n)->rb_left;
 334                 else if (offset > entry->end)
 335                         n = &(*n)->rb_right;
 336                 else
 337                         return *n;
 338         }
 339
 340         if (p_ret)
 341                 *p_ret = n;
 342         if (parent_ret)
 343                 *parent_ret = prev;
 344
 345         if (next_ret) {
 346                 orig_prev = prev;
 347                 while (prev && offset > prev_entry->end) {
 348                         prev = rb_next(prev);
 349                         prev_entry = rb_entry(prev, struct tree_entry, rb_node);
 350                 }
 351                 *next_ret = prev;
 352                 prev = orig_prev;
 353         }
 354
 355         if (prev_ret) {
 356                 prev_entry = rb_entry(prev, struct tree_entry, rb_node);
 357                 while (prev && offset < prev_entry->start) {
 358                         prev = rb_prev(prev);
 359                         prev_entry = rb_entry(prev, struct tree_entry, rb_node);
 360                 }
 361                 *prev_ret = prev;
 362         }
 363         return NULL;
 364 }
 365
 366 static inline struct rb_node *
 367 tree_search_for_insert(struct extent_io_tree *tree,
 368                        u64 offset,
 369                        struct rb_node ***p_ret,
 370                        struct rb_node **parent_ret)
 371 {
 372         struct rb_node *next= NULL;
 373         struct rb_node *ret;
 374
 375         ret = __etree_search(tree, offset, &next, NULL, p_ret, parent_ret);
 376         if (!ret)
 377                 return next;
 378         return ret;
 379 }
 380
 381 static inline struct rb_node *tree_search(struct extent_io_tree *tree,
 382                                           u64 offset)
 383 {
 384         return tree_search_for_insert(tree, offset, NULL, NULL);
 385 }
 386
 387 /*
 388  * utility function to look for merge candidates inside a given range.
 389  * Any extents with matching state are merged together into a single
 390  * extent in the tree.  Extents with EXTENT_IO in their state field
 391  * are not merged because the end_io handlers need to be able to do
 392  * operations on them without sleeping (or doing allocations/splits).
 393  *
 394  * This should be called with the tree lock held.
 395  */
 396 static void merge_state(struct extent_io_tree *tree,
 397                         struct extent_state *state)
 398 {
 399         struct extent_state *other;
 400         struct rb_node *other_node;
 401
 402         if (state->state & (EXTENT_IOBITS | EXTENT_BOUNDARY))
 403                 return;
 404
 405         other_node = rb_prev(&state->rb_node);
 406         if (other_node) {
 407                 other = rb_entry(other_node, struct extent_state, rb_node);
 408                 if (other->end == state->start - 1 &&
 409                     other->state == state->state) {
 410                         if (tree->private_data &&
 411                             is_data_inode(tree->private_data))
 412                                 btrfs_merge_delalloc_extent(tree->private_data,
 413                                                             state, other);
 414                         state->start = other->start;
 415                         rb_erase(&other->rb_node, &tree->state);
 416                         RB_CLEAR_NODE(&other->rb_node);
 417                         free_extent_state(other);
 418                 }
 419         }
 420         other_node = rb_next(&state->rb_node);
 421         if (other_node) {
 422                 other = rb_entry(other_node, struct extent_state, rb_node);
 423                 if (other->start == state->end + 1 &&
 424                     other->state == state->state) {
 425                         if (tree->private_data &&
 426                             is_data_inode(tree->private_data))
 427                                 btrfs_merge_delalloc_extent(tree->private_data,
 428                                                             state, other);
 429                         state->end = other->end;
 430                         rb_erase(&other->rb_node, &tree->state);
 431                         RB_CLEAR_NODE(&other->rb_node);
 432                         free_extent_state(other);
 433                 }
 434         }
 435 }
 436
 437 static void set_state_bits(struct extent_io_tree *tree,
 438                            struct extent_state *state, unsigned *bits,
 439                            struct extent_changeset *changeset);
 440
 441 /*
 442  * insert an extent_state struct into the tree.  'bits' are set on the
 443  * struct before it is inserted.
 444  *
 445  * This may return -EEXIST if the extent is already there, in which case the
 446  * state struct is freed.
 447  *
 448  * The tree lock is not taken internally.  This is a utility function and
 449  * probably isn't what you want to call (see set/clear_extent_bit).
 450  */
 451 static int insert_state(struct extent_io_tree *tree,
 452                         struct extent_state *state, u64 start, u64 end,
 453                         struct rb_node ***p,
 454                         struct rb_node **parent,
 455                         unsigned *bits, struct extent_changeset *changeset)
 456 {
 457         struct rb_node *node;
 458
 459         if (end < start)
 460                 WARN(1, KERN_ERR "BTRFS: end < start %llu %llu\n",
 461                        end, start);
 462         state->start = start;
 463         state->end = end;
 464
 465         set_state_bits(tree, state, bits, changeset);
 466
 467         node = tree_insert(&tree->state, NULL, end, &state->rb_node, p, parent);
 468         if (node) {
 469                 struct extent_state *found;
 470                 found = rb_entry(node, struct extent_state, rb_node);
 471                 pr_err("BTRFS: found node %llu %llu on insert of %llu %llu\n",
 472                        found->start, found->end, start, end);
 473                 return -EEXIST;
 474         }
 475         merge_state(tree, state);
 476         return 0;
 477 }
 478
 479 /*
 480  * split a given extent state struct in two, inserting the preallocated
 481  * struct 'prealloc' as the newly created second half.  'split' indicates an
 482  * offset inside 'orig' where it should be split.
 483  *
 484  * Before calling,
 485  * the tree has 'orig' at [orig->start, orig->end].  After calling, there
 486  * are two extent state structs in the tree:
 487  * prealloc: [orig->start, split - 1]
 488  * orig: [ split, orig->end ]
 489  *
 490  * The tree locks are not taken by this function. They need to be held
 491  * by the caller.
 492  */
 493 static int split_state(struct extent_io_tree *tree, struct extent_state *orig,
 494                        struct extent_state *prealloc, u64 split)
 495 {
 496         struct rb_node *node;
 497
 498         if (tree->private_data && is_data_inode(tree->private_data))
 499                 btrfs_split_delalloc_extent(tree->private_data, orig, split);
 500
 501         prealloc->start = orig->start;
 502         prealloc->end = split - 1;
 503         prealloc->state = orig->state;
 504         orig->start = split;
 505
 506         node = tree_insert(&tree->state, &orig->rb_node, prealloc->end,
 507                            &prealloc->rb_node, NULL, NULL);
 508         if (node) {
 509                 free_extent_state(prealloc);
 510                 return -EEXIST;
 511         }
 512         return 0;
 513 }
 514
 515 static struct extent_state *next_state(struct extent_state *state)
 516 {
 517         struct rb_node *next = rb_next(&state->rb_node);
 518         if (next)
 519                 return rb_entry(next, struct extent_state, rb_node);
 520         else
 521                 return NULL;
 522 }
 523
 524 /*
 525  * utility function to clear some bits in an extent state struct.
 526  * it will optionally wake up anyone waiting on this state (wake == 1).
 527  *
 528  * If no bits are set on the state struct after clearing things, the
 529  * struct is freed and removed from the tree
 530  */
 531 static struct extent_state *clear_state_bit(struct extent_io_tree *tree,
 532                                             struct extent_state *state,
 533                                             unsigned *bits, int wake,
 534                                             struct extent_changeset *changeset)
 535 {
 536         struct extent_state *next;
 537         unsigned bits_to_clear = *bits & ~EXTENT_CTLBITS;
 538         int ret;
 539
 540         if ((bits_to_clear & EXTENT_DIRTY) && (state->state & EXTENT_DIRTY)) {
 541                 u64 range = state->end - state->start + 1;
 542                 WARN_ON(range > tree->dirty_bytes);
 543                 tree->dirty_bytes -= range;
 544         }
 545
 546         if (tree->private_data && is_data_inode(tree->private_data))
 547                 btrfs_clear_delalloc_extent(tree->private_data, state, bits);
 548
 549         ret = add_extent_changeset(state, bits_to_clear, changeset, 0);
 550         BUG_ON(ret < 0);
 551         state->state &= ~bits_to_clear;
 552         if (wake)
 553                 wake_up(&state->wq);
 554         if (state->state == 0) {
 555                 next = next_state(state);
 556                 if (extent_state_in_tree(state)) {
 557                         rb_erase(&state->rb_node, &tree->state);
 558                         RB_CLEAR_NODE(&state->rb_node);
 559                         free_extent_state(state);
 560                 } else {
 561                         WARN_ON(1);
 562                 }
 563         } else {
 564                 merge_state(tree, state);
 565                 next = next_state(state);
 566         }
 567         return next;
 568 }
 569
 570 static struct extent_state *
 571 alloc_extent_state_atomic(struct extent_state *prealloc)
 572 {
 573         if (!prealloc)
 574                 prealloc = alloc_extent_state(GFP_ATOMIC);
 575
 576         return prealloc;
 577 }
 578
 579 static void extent_io_tree_panic(struct extent_io_tree *tree, int err)
 580 {
 581         struct inode *inode = tree->private_data;
 582
 583         btrfs_panic(btrfs_sb(inode->i_sb), err,
 584         "locking error: extent tree was modified by another thread while locked");
 585 }
 586
 587 /*
 588  * clear some bits on a range in the tree.  This may require splitting
 589  * or inserting elements in the tree, so the gfp mask is used to
 590  * indicate which allocations or sleeping are allowed.
 591  *
 592  * pass 'wake' == 1 to kick any sleepers, and 'delete' == 1 to remove
 593  * the given range from the tree regardless of state (ie for truncate).
 594  *
 595  * the range [start, end] is inclusive.
 596  *
 597  * This takes the tree lock, and returns 0 on success and < 0 on error.
 598  */
 599 int __clear_extent_bit(struct extent_io_tree *tree, u64 start, u64 end,
 600                               unsigned bits, int wake, int delete,
 601                               struct extent_state **cached_state,
 602                               gfp_t mask, struct extent_changeset *changeset)
 603 {
 604         struct extent_state *state;
 605         struct extent_state *cached;
 606         struct extent_state *prealloc = NULL;
 607         struct rb_node *node;
 608         u64 last_end;
 609         int err;
 610         int clear = 0;
 611
 612         btrfs_debug_check_extent_io_range(tree, start, end);
 613
 614         if (bits & EXTENT_DELALLOC)
 615                 bits |= EXTENT_NORESERVE;
 616
 617         if (delete)
 618                 bits |= ~EXTENT_CTLBITS;
 619
 620         if (bits & (EXTENT_IOBITS | EXTENT_BOUNDARY))
 621                 clear = 1;
 622 again:
 623         if (!prealloc && gfpflags_allow_blocking(mask)) {
 624                 /*
 625                  * Don't care for allocation failure here because we might end
 626                  * up not needing the pre-allocated extent state at all, which
 627                  * is the case if we only have in the tree extent states that
 628                  * cover our input range and don't cover too any other range.
 629                  * If we end up needing a new extent state we allocate it later.
 630                  */
 631                 prealloc = alloc_extent_state(mask);
 632         }
 633
 634         spin_lock(&tree->lock);
 635         if (cached_state) {
 636                 cached = *cached_state;
 637
 638                 if (clear) {
 639                         *cached_state = NULL;
 640                         cached_state = NULL;
 641                 }
 642
 643                 if (cached && extent_state_in_tree(cached) &&
 644                     cached->start <= start && cached->end > start) {
 645                         if (clear)
 646                                 refcount_dec(&cached->refs);
 647                         state = cached;
 648                         goto hit_next;
 649                 }
 650                 if (clear)
 651                         free_extent_state(cached);
 652         }
 653         /*
 654          * this search will find the extents that end after
 655          * our range starts
 656          */
 657         node = tree_search(tree, start);
 658         if (!node)
 659                 goto out;
 660         state = rb_entry(node, struct extent_state, rb_node);
 661 hit_next:
 662         if (state->start > end)
 663                 goto out;
 664         WARN_ON(state->end < start);
 665         last_end = state->end;
 666
 667         /* the state doesn't have the wanted bits, go ahead */
 668         if (!(state->state & bits)) {
 669                 state = next_state(state);
 670                 goto next;
 671         }
 672
 673         /*
 674          *     | ---- desired range ---- |
 675          *  | state | or
 676          *  | ------------- state -------------- |
 677          *
 678          * We need to split the extent we found, and may flip
 679          * bits on second half.
 680          *
 681          * If the extent we found extends past our range, we
 682          * just split and search again.  It'll get split again
 683          * the next time though.
 684          *
 685          * If the extent we found is inside our range, we clear
 686          * the desired bit on it.
 687          */
 688
 689         if (state->start < start) {
 690                 prealloc = alloc_extent_state_atomic(prealloc);
 691                 BUG_ON(!prealloc);
 692                 err = split_state(tree, state, prealloc, start);
 693                 if (err)
 694                         extent_io_tree_panic(tree, err);
 695
 696                 prealloc = NULL;
 697                 if (err)
 698                         goto out;
 699                 if (state->end <= end) {
 700                         state = clear_state_bit(tree, state, &bits, wake,
 701                                                 changeset);
 702                         goto next;
 703                 }
 704                 goto search_again;
 705         }
 706         /*
 707          * | ---- desired range ---- |
 708          *                        | state |
 709          * We need to split the extent, and clear the bit
 710          * on the first half
 711          */
 712         if (state->start <= end && state->end > end) {
 713                 prealloc = alloc_extent_state_atomic(prealloc);
 714                 BUG_ON(!prealloc);
 715                 err = split_state(tree, state, prealloc, end + 1);
 716                 if (err)
 717                         extent_io_tree_panic(tree, err);
 718
 719                 if (wake)
 720                         wake_up(&state->wq);
 721
 722                 clear_state_bit(tree, prealloc, &bits, wake, changeset);
 723
 724                 prealloc = NULL;
 725                 goto out;
 726         }
 727
 728         state = clear_state_bit(tree, state, &bits, wake, changeset);
 729 next:
 730         if (last_end == (u64)-1)
 731                 goto out;
 732         start = last_end + 1;
 733         if (start <= end && state && !need_resched())
 734                 goto hit_next;
 735
 736 search_again:
 737         if (start > end)
 738                 goto out;
 739         spin_unlock(&tree->lock);
 740         if (gfpflags_allow_blocking(mask))
 741                 cond_resched();
 742         goto again;
 743
 744 out:
 745         spin_unlock(&tree->lock);
 746         if (prealloc)
 747                 free_extent_state(prealloc);
 748
 749         return 0;
 750
 751 }
 752
 753 static void wait_on_state(struct extent_io_tree *tree,
 754                           struct extent_state *state)
 755                 __releases(tree->lock)
 756                 __acquires(tree->lock)
 757 {
 758         DEFINE_WAIT(wait);
 759         prepare_to_wait(&state->wq, &wait, TASK_UNINTERRUPTIBLE);
 760         spin_unlock(&tree->lock);
 761         schedule();
 762         spin_lock(&tree->lock);
 763         finish_wait(&state->wq, &wait);
 764 }
 765
 766 /*
 767  * waits for one or more bits to clear on a range in the state tree.
 768  * The range [start, end] is inclusive.
 769  * The tree lock is taken by this function
 770  */
 771 static void wait_extent_bit(struct extent_io_tree *tree, u64 start, u64 end,
 772                             unsigned long bits)
 773 {
 774         struct extent_state *state;
 775         struct rb_node *node;
 776
 777         btrfs_debug_check_extent_io_range(tree, start, end);
 778
 779         spin_lock(&tree->lock);
 780 again:
 781         while (1) {
 782                 /*
 783                  * this search will find all the extents that end after
 784                  * our range starts
 785                  */
 786                 node = tree_search(tree, start);
 787 process_node:
 788                 if (!node)
 789                         break;
 790
 791                 state = rb_entry(node, struct extent_state, rb_node);
 792
 793                 if (state->start > end)
 794                         goto out;
 795
 796                 if (state->state & bits) {
 797                         start = state->start;
 798                         refcount_inc(&state->refs);
 799                         wait_on_state(tree, state);
 800                         free_extent_state(state);
 801                         goto again;
 802                 }
 803                 start = state->end + 1;
 804
 805                 if (start > end)
 806                         break;
 807
 808                 if (!cond_resched_lock(&tree->lock)) {
 809                         node = rb_next(node);
 810                         goto process_node;
 811                 }
 812         }
 813 out:
 814         spin_unlock(&tree->lock);
 815 }
 816
 817 static void set_state_bits(struct extent_io_tree *tree,
 818                            struct extent_state *state,
 819                            unsigned *bits, struct extent_changeset *changeset)
 820 {
 821         unsigned bits_to_set = *bits & ~EXTENT_CTLBITS;
 822         int ret;
 823
 824         if (tree->private_data && is_data_inode(tree->private_data))
 825                 btrfs_set_delalloc_extent(tree->private_data, state, bits);
 826
 827         if ((bits_to_set & EXTENT_DIRTY) && !(state->state & EXTENT_DIRTY)) {
 828                 u64 range = state->end - state->start + 1;
 829                 tree->dirty_bytes += range;
 830         }
 831         ret = add_extent_changeset(state, bits_to_set, changeset, 1);
 832         BUG_ON(ret < 0);
 833         state->state |= bits_to_set;
 834 }
 835
 836 static void cache_state_if_flags(struct extent_state *state,
 837                                  struct extent_state **cached_ptr,
 838                                  unsigned flags)
 839 {
 840         if (cached_ptr && !(*cached_ptr)) {
 841                 if (!flags || (state->state & flags)) {
 842                         *cached_ptr = state;
 843                         refcount_inc(&state->refs);
 844                 }
 845         }
 846 }
 847
 848 static void cache_state(struct extent_state *state,
 849                         struct extent_state **cached_ptr)
 850 {
 851         return cache_state_if_flags(state, cached_ptr,
 852                                     EXTENT_IOBITS | EXTENT_BOUNDARY);
 853 }
 854
 855 /*
 856  * set some bits on a range in the tree.  This may require allocations or
 857  * sleeping, so the gfp mask is used to indicate what is allowed.
 858  *
 859  * If any of the exclusive bits are set, this will fail with -EEXIST if some
 860  * part of the range already has the desired bits set.  The start of the
 861  * existing range is returned in failed_start in this case.
 862  *
 863  * [start, end] is inclusive This takes the tree lock.
 864  */
 865
 866 static int __must_check
 867 __set_extent_bit(struct extent_io_tree *tree, u64 start, u64 end,
 868                  unsigned bits, unsigned exclusive_bits,
 869                  u64 *failed_start, struct extent_state **cached_state,
 870                  gfp_t mask, struct extent_changeset *changeset)
 871 {
 872         struct extent_state *state;
 873         struct extent_state *prealloc = NULL;
 874         struct rb_node *node;
 875         struct rb_node **p;
 876         struct rb_node *parent;
 877         int err = 0;
 878         u64 last_start;
 879         u64 last_end;
 880
 881         btrfs_debug_check_extent_io_range(tree, start, end);
 882
 883 again:
 884         if (!prealloc && gfpflags_allow_blocking(mask)) {
 885                 /*
 886                  * Don't care for allocation failure here because we might end
 887                  * up not needing the pre-allocated extent state at all, which
 888                  * is the case if we only have in the tree extent states that
 889                  * cover our input range and don't cover too any other range.
 890                  * If we end up needing a new extent state we allocate it later.
 891                  */
 892                 prealloc = alloc_extent_state(mask);
 893         }
 894
 895         spin_lock(&tree->lock);
 896         if (cached_state && *cached_state) {
 897                 state = *cached_state;
 898                 if (state->start <= start && state->end > start &&
 899                     extent_state_in_tree(state)) {
 900                         node = &state->rb_node;
 901                         goto hit_next;
 902                 }
 903         }
 904         /*
 905          * this search will find all the extents that end after
 906          * our range starts.
 907          */
 908         node = tree_search_for_insert(tree, start, &p, &parent);
 909         if (!node) {
 910                 prealloc = alloc_extent_state_atomic(prealloc);
 911                 BUG_ON(!prealloc);
 912                 err = insert_state(tree, prealloc, start, end,
 913                                    &p, &parent, &bits, changeset);
 914                 if (err)
 915                         extent_io_tree_panic(tree, err);
 916
 917                 cache_state(prealloc, cached_state);
 918                 prealloc = NULL;
 919                 goto out;
 920         }
 921         state = rb_entry(node, struct extent_state, rb_node);
 922 hit_next:
 923         last_start = state->start;
 924         last_end = state->end;
 925
 926         /*
 927          * | ---- desired range ---- |
 928          * | state |
 929          *
 930          * Just lock what we found and keep going
 931          */
 932         if (state->start == start && state->end <= end) {
 933                 if (state->state & exclusive_bits) {
 934                         *failed_start = state->start;
 935                         err = -EEXIST;
 936                         goto out;
 937                 }
 938
 939                 set_state_bits(tree, state, &bits, changeset);
 940                 cache_state(state, cached_state);
 941                 merge_state(tree, state);
 942                 if (last_end == (u64)-1)
 943                         goto out;
 944                 start = last_end + 1;
 945                 state = next_state(state);
 946                 if (start < end && state && state->start == start &&
 947                     !need_resched())
 948                         goto hit_next;
 949                 goto search_again;
 950         }
 951
 952         /*
 953          *     | ---- desired range ---- |
 954          * | state |
 955          *   or
 956          * | ------------- state -------------- |
 957          *
 958          * We need to split the extent we found, and may flip bits on
 959          * second half.
 960          *
 961          * If the extent we found extends past our
 962          * range, we just split and search again.  It'll get split
 963          * again the next time though.
 964          *
 965          * If the extent we found is inside our range, we set the
 966          * desired bit on it.
 967          */
 968         if (state->start < start) {
 969                 if (state->state & exclusive_bits) {
 970                         *failed_start = start;
 971                         err = -EEXIST;
 972                         goto out;
 973                 }
 974
 975                 prealloc = alloc_extent_state_atomic(prealloc);
 976                 BUG_ON(!prealloc);
 977                 err = split_state(tree, state, prealloc, start);
 978                 if (err)
 979                         extent_io_tree_panic(tree, err);
 980
 981                 prealloc = NULL;
 982                 if (err)
 983                         goto out;
 984                 if (state->end <= end) {
 985                         set_state_bits(tree, state, &bits, changeset);
 986                         cache_state(state, cached_state);
 987                         merge_state(tree, state);
 988                         if (last_end == (u64)-1)
 989                                 goto out;
 990                         start = last_end + 1;
 991                         state = next_state(state);
 992                         if (start < end && state && state->start == start &&
 993                             !need_resched())
 994                                 goto hit_next;
 995                 }
 996                 goto search_again;
 997         }
 998         /*
 999          * | ---- desired range ---- |
1000          *     | state | or               | state |
1001          *
1002          * There's a hole, we need to insert something in it and
1003          * ignore the extent we found.
1004          */
1005         if (state->start > start) {
1006                 u64 this_end;
1007                 if (end < last_start)
1008                         this_end = end;
1009                 else
1010                         this_end = last_start - 1;
1011
1012                 prealloc = alloc_extent_state_atomic(prealloc);
1013                 BUG_ON(!prealloc);
1014
1015                 /*
1016                  * Avoid to free 'prealloc' if it can be merged with
1017                  * the later extent.
1018                  */
1019                 err = insert_state(tree, prealloc, start, this_end,
1020                                    NULL, NULL, &bits, changeset);
1021                 if (err)
1022                         extent_io_tree_panic(tree, err);
1023
1024                 cache_state(prealloc, cached_state);
1025                 prealloc = NULL;
1026                 start = this_end + 1;
1027                 goto search_again;
1028         }
1029         /*
1030          * | ---- desired range ---- |
1031          *                        | state |
1032          * We need to split the extent, and set the bit
1033          * on the first half
1034          */
1035         if (state->start <= end && state->end > end) {
1036                 if (state->state & exclusive_bits) {
1037                         *failed_start = start;
1038                         err = -EEXIST;
1039                         goto out;
1040                 }
1041
1042                 prealloc = alloc_extent_state_atomic(prealloc);
1043                 BUG_ON(!prealloc);
1044                 err = split_state(tree, state, prealloc, end + 1);
1045                 if (err)
1046                         extent_io_tree_panic(tree, err);
1047
1048                 set_state_bits(tree, prealloc, &bits, changeset);
1049                 cache_state(prealloc, cached_state);
1050                 merge_state(tree, prealloc);
1051                 prealloc = NULL;
1052                 goto out;
1053         }
1054
1055 search_again:
1056         if (start > end)
1057                 goto out;
1058         spin_unlock(&tree->lock);
1059         if (gfpflags_allow_blocking(mask))
1060                 cond_resched();
1061         goto again;
1062
1063 out:
1064         spin_unlock(&tree->lock);
1065         if (prealloc)
1066                 free_extent_state(prealloc);
1067
1068         return err;
1069
1070 }
1071
1072 int set_extent_bit(struct extent_io_tree *tree, u64 start, u64 end,
1073                    unsigned bits, u64 * failed_start,
1074                    struct extent_state **cached_state, gfp_t mask)
1075 {
1076         return __set_extent_bit(tree, start, end, bits, 0, failed_start,
1077                                 cached_state, mask, NULL);
1078 }
1079
1080
1081 /**
1082  * convert_extent_bit - convert all bits in a given range from one bit to
1083  *                      another
1084  * @tree:       the io tree to search
1085  * @start:      the start offset in bytes
1086  * @end:        the end offset in bytes (inclusive)
1087  * @bits:       the bits to set in this range
1088  * @clear_bits: the bits to clear in this range
1089  * @cached_state:       state that we're going to cache
1090  *
1091  * This will go through and set bits for the given range.  If any states exist
1092  * already in this range they are set with the given bit and cleared of the
1093  * clear_bits.  This is only meant to be used by things that are mergeable, ie
1094  * converting from say DELALLOC to DIRTY.  This is not meant to be used with
1095  * boundary bits like LOCK.
1096  *
1097  * All allocations are done with GFP_NOFS.
1098  */
1099 int convert_extent_bit(struct extent_io_tree *tree, u64 start, u64 end,
1100                        unsigned bits, unsigned clear_bits,
1101                        struct extent_state **cached_state)
1102 {
1103         struct extent_state *state;
1104         struct extent_state *prealloc = NULL;
1105         struct rb_node *node;
1106         struct rb_node **p;
1107         struct rb_node *parent;
1108         int err = 0;
1109         u64 last_start;
1110         u64 last_end;
1111         bool first_iteration = true;
1112
1113         btrfs_debug_check_extent_io_range(tree, start, end);
1114
1115 again:
1116         if (!prealloc) {
1117                 /*
1118                  * Best effort, don't worry if extent state allocation fails
1119                  * here for the first iteration. We might have a cached state
1120                  * that matches exactly the target range, in which case no
1121                  * extent state allocations are needed. We'll only know this
1122                  * after locking the tree.
1123                  */
1124                 prealloc = alloc_extent_state(GFP_NOFS);
1125                 if (!prealloc && !first_iteration)
1126                         return -ENOMEM;
1127         }
1128
1129         spin_lock(&tree->lock);
1130         if (cached_state && *cached_state) {
1131                 state = *cached_state;
1132                 if (state->start <= start && state->end > start &&
1133                     extent_state_in_tree(state)) {
1134                         node = &state->rb_node;
1135                         goto hit_next;
1136                 }
1137         }
1138
1139         /*
1140          * this search will find all the extents that end after
1141          * our range starts.
1142          */
1143         node = tree_search_for_insert(tree, start, &p, &parent);
1144         if (!node) {
1145                 prealloc = alloc_extent_state_atomic(prealloc);
1146                 if (!prealloc) {
1147                         err = -ENOMEM;
1148                         goto out;
1149                 }
1150                 err = insert_state(tree, prealloc, start, end,
1151                                    &p, &parent, &bits, NULL);
1152                 if (err)
1153                         extent_io_tree_panic(tree, err);
1154                 cache_state(prealloc, cached_state);
1155                 prealloc = NULL;
1156                 goto out;
1157         }
1158         state = rb_entry(node, struct extent_state, rb_node);
1159 hit_next:
1160         last_start = state->start;
1161         last_end = state->end;
1162
1163         /*
1164          * | ---- desired range ---- |
1165          * | state |
1166          *
1167          * Just lock what we found and keep going
1168          */
1169         if (state->start == start && state->end <= end) {
1170                 set_state_bits(tree, state, &bits, NULL);
1171                 cache_state(state, cached_state);
1172                 state = clear_state_bit(tree, state, &clear_bits, 0, NULL);
1173                 if (last_end == (u64)-1)
1174                         goto out;
1175                 start = last_end + 1;
1176                 if (start < end && state && state->start == start &&
1177                     !need_resched())
1178                         goto hit_next;
1179                 goto search_again;
1180         }
1181
1182         /*
1183          *     | ---- desired range ---- |
1184          * | state |
1185          *   or
1186          * | ------------- state -------------- |
1187          *
1188          * We need to split the extent we found, and may flip bits on
1189          * second half.
1190          *
1191          * If the extent we found extends past our
1192          * range, we just split and search again.  It'll get split
1193          * again the next time though.
1194          *
1195          * If the extent we found is inside our range, we set the
1196          * desired bit on it.
1197          */
1198         if (state->start < start) {
1199                 prealloc = alloc_extent_state_atomic(prealloc);
1200                 if (!prealloc) {
1201                         err = -ENOMEM;
1202                         goto out;
1203                 }
1204                 err = split_state(tree, state, prealloc, start);
1205                 if (err)
1206                         extent_io_tree_panic(tree, err);
1207                 prealloc = NULL;
1208                 if (err)
1209                         goto out;
1210                 if (state->end <= end) {
1211                         set_state_bits(tree, state, &bits, NULL);
1212                         cache_state(state, cached_state);
1213                         state = clear_state_bit(tree, state, &clear_bits, 0,
1214                                                 NULL);
1215                         if (last_end == (u64)-1)
1216                                 goto out;
1217                         start = last_end + 1;
1218                         if (start < end && state && state->start == start &&
1219                             !need_resched())
1220                                 goto hit_next;
1221                 }
1222                 goto search_again;
1223         }
1224         /*
1225          * | ---- desired range ---- |
1226          *     | state | or               | state |
1227          *
1228          * There's a hole, we need to insert something in it and
1229          * ignore the extent we found.
1230          */
1231         if (state->start > start) {
1232                 u64 this_end;
1233                 if (end < last_start)
1234                         this_end = end;
1235                 else
1236                         this_end = last_start - 1;
1237
1238                 prealloc = alloc_extent_state_atomic(prealloc);
1239                 if (!prealloc) {
1240                         err = -ENOMEM;
1241                         goto out;
1242                 }
1243
1244                 /*
1245                  * Avoid to free 'prealloc' if it can be merged with
1246                  * the later extent.
1247                  */
1248                 err = insert_state(tree, prealloc, start, this_end,
1249                                    NULL, NULL, &bits, NULL);
1250                 if (err)
1251                         extent_io_tree_panic(tree, err);
1252                 cache_state(prealloc, cached_state);
1253                 prealloc = NULL;
1254                 start = this_end + 1;
1255                 goto search_again;
1256         }
1257         /*
1258          * | ---- desired range ---- |
1259          *                        | state |
1260          * We need to split the extent, and set the bit
1261          * on the first half
1262          */
1263         if (state->start <= end && state->end > end) {
1264                 prealloc = alloc_extent_state_atomic(prealloc);
1265                 if (!prealloc) {
1266                         err = -ENOMEM;
1267                         goto out;
1268                 }
1269
1270                 err = split_state(tree, state, prealloc, end + 1);
1271                 if (err)
1272                         extent_io_tree_panic(tree, err);
1273
1274                 set_state_bits(tree, prealloc, &bits, NULL);
1275                 cache_state(prealloc, cached_state);
1276                 clear_state_bit(tree, prealloc, &clear_bits, 0, NULL);
1277                 prealloc = NULL;
1278                 goto out;
1279         }
1280
1281 search_again:
1282         if (start > end)
1283                 goto out;
1284         spin_unlock(&tree->lock);
1285         cond_resched();
1286         first_iteration = false;
1287         goto again;
1288
1289 out:
1290         spin_unlock(&tree->lock);
1291         if (prealloc)
1292                 free_extent_state(prealloc);
1293
1294         return err;
1295 }
1296
1297 /* wrappers around set/clear extent bit */
1298 int set_record_extent_bits(struct extent_io_tree *tree, u64 start, u64 end,
1299                            unsigned bits, struct extent_changeset *changeset)
1300 {
1301         /*
1302          * We don't support EXTENT_LOCKED yet, as current changeset will
1303          * record any bits changed, so for EXTENT_LOCKED case, it will
1304          * either fail with -EEXIST or changeset will record the whole
1305          * range.
1306          */
1307         BUG_ON(bits & EXTENT_LOCKED);
1308
1309         return __set_extent_bit(tree, start, end, bits, 0, NULL, NULL, GFP_NOFS,
1310                                 changeset);
1311 }
1312
1313 int clear_extent_bit(struct extent_io_tree *tree, u64 start, u64 end,
1314                      unsigned bits, int wake, int delete,
1315                      struct extent_state **cached)
1316 {
1317         return __clear_extent_bit(tree, start, end, bits, wake, delete,
1318                                   cached, GFP_NOFS, NULL);
1319 }
1320
1321 int clear_record_extent_bits(struct extent_io_tree *tree, u64 start, u64 end,
1322                 unsigned bits, struct extent_changeset *changeset)
1323 {
1324         /*
1325          * Don't support EXTENT_LOCKED case, same reason as
1326          * set_record_extent_bits().
1327          */
1328         BUG_ON(bits & EXTENT_LOCKED);
1329
1330         return __clear_extent_bit(tree, start, end, bits, 0, 0, NULL, GFP_NOFS,
1331                                   changeset);
1332 }
1333
1334 /*
1335  * either insert or lock state struct between start and end use mask to tell
1336  * us if waiting is desired.
1337  */
1338 int lock_extent_bits(struct extent_io_tree *tree, u64 start, u64 end,
1339                      struct extent_state **cached_state)
1340 {
1341         int err;
1342         u64 failed_start;
1343
1344         while (1) {
1345                 err = __set_extent_bit(tree, start, end, EXTENT_LOCKED,
1346                                        EXTENT_LOCKED, &failed_start,
1347                                        cached_state, GFP_NOFS, NULL);
1348                 if (err == -EEXIST) {
1349                         wait_extent_bit(tree, failed_start, end, EXTENT_LOCKED);
1350                         start = failed_start;
1351                 } else
1352                         break;
1353                 WARN_ON(start > end);
1354         }
1355         return err;
1356 }
1357
1358 int try_lock_extent(struct extent_io_tree *tree, u64 start, u64 end)
1359 {
1360         int err;
1361         u64 failed_start;
1362
1363         err = __set_extent_bit(tree, start, end, EXTENT_LOCKED, EXTENT_LOCKED,
1364                                &failed_start, NULL, GFP_NOFS, NULL);
1365         if (err == -EEXIST) {
1366                 if (failed_start > start)
1367                         clear_extent_bit(tree, start, failed_start - 1,
1368                                          EXTENT_LOCKED, 1, 0, NULL);
1369                 return 0;
1370         }
1371         return 1;
1372 }
1373
1374 void extent_range_clear_dirty_for_io(struct inode *inode, u64 start, u64 end)
1375 {
1376         unsigned long index = start >> PAGE_SHIFT;
1377         unsigned long end_index = end >> PAGE_SHIFT;
1378         struct page *page;
1379
1380         while (index <= end_index) {
1381                 page = find_get_page(inode->i_mapping, index);
1382                 BUG_ON(!page); /* Pages should be in the extent_io_tree */
1383                 clear_page_dirty_for_io(page);
1384                 put_page(page);
1385                 index++;
1386         }
1387 }
1388
1389 void extent_range_redirty_for_io(struct inode *inode, u64 start, u64 end)
1390 {
1391         unsigned long index = start >> PAGE_SHIFT;
1392         unsigned long end_index = end >> PAGE_SHIFT;
1393         struct page *page;
1394
1395         while (index <= end_index) {
1396                 page = find_get_page(inode->i_mapping, index);
1397                 BUG_ON(!page); /* Pages should be in the extent_io_tree */
1398                 __set_page_dirty_nobuffers(page);
1399                 account_page_redirty(page);
1400                 put_page(page);
1401                 index++;
1402         }
1403 }
1404
1405 /* find the first state struct with 'bits' set after 'start', and
1406  * return it.  tree->lock must be held.  NULL will returned if
1407  * nothing was found after 'start'
1408  */
1409 static struct extent_state *
1410 find_first_extent_bit_state(struct extent_io_tree *tree,
1411                             u64 start, unsigned bits)
1412 {
1413         struct rb_node *node;
1414         struct extent_state *state;
1415
1416         /*
1417          * this search will find all the extents that end after
1418          * our range starts.
1419          */
1420         node = tree_search(tree, start);
1421         if (!node)
1422                 goto out;
1423
1424         while (1) {
1425                 state = rb_entry(node, struct extent_state, rb_node);
1426                 if (state->end >= start && (state->state & bits))
1427                         return state;
1428
1429                 node = rb_next(node);
1430                 if (!node)
1431                         break;
1432         }
1433 out:
1434         return NULL;
1435 }
1436
1437 /*
1438  * find the first offset in the io tree with 'bits' set. zero is
1439  * returned if we find something, and *start_ret and *end_ret are
1440  * set to reflect the state struct that was found.
1441  *
1442  * If nothing was found, 1 is returned. If found something, return 0.
1443  */
1444 int find_first_extent_bit(struct extent_io_tree *tree, u64 start,
1445                           u64 *start_ret, u64 *end_ret, unsigned bits,
1446                           struct extent_state **cached_state)
1447 {
1448         struct extent_state *state;
1449         int ret = 1;
1450
1451         spin_lock(&tree->lock);
1452         if (cached_state && *cached_state) {
1453                 state = *cached_state;
1454                 if (state->end == start - 1 && extent_state_in_tree(state)) {
1455                         while ((state = next_state(state)) != NULL) {
1456                                 if (state->state & bits)
1457                                         goto got_it;
1458                         }
1459                         free_extent_state(*cached_state);
1460                         *cached_state = NULL;
1461                         goto out;
1462                 }
1463                 free_extent_state(*cached_state);
1464                 *cached_state = NULL;
1465         }
1466
1467         state = find_first_extent_bit_state(tree, start, bits);
1468 got_it:
1469         if (state) {
1470                 cache_state_if_flags(state, cached_state, 0);
1471                 *start_ret = state->start;
1472                 *end_ret = state->end;
1473                 ret = 0;
1474         }
1475 out:
1476         spin_unlock(&tree->lock);
1477         return ret;
1478 }
1479
1480 /*
1481  * find a contiguous range of bytes in the file marked as delalloc, not
1482  * more than 'max_bytes'.  start and end are used to return the range,
1483  *
1484  * true is returned if we find something, false if nothing was in the tree
1485  */
1486 static noinline bool find_delalloc_range(struct extent_io_tree *tree,
1487                                         u64 *start, u64 *end, u64 max_bytes,
1488                                         struct extent_state **cached_state)
1489 {
1490         struct rb_node *node;
1491         struct extent_state *state;
1492         u64 cur_start = *start;
1493         bool found = false;
1494         u64 total_bytes = 0;
1495
1496         spin_lock(&tree->lock);
1497
1498         /*
1499          * this search will find all the extents that end after
1500          * our range starts.
1501          */
1502         node = tree_search(tree, cur_start);
1503         if (!node) {
1504                 *end = (u64)-1;
1505                 goto out;
1506         }
1507
1508         while (1) {
1509                 state = rb_entry(node, struct extent_state, rb_node);
1510                 if (found && (state->start != cur_start ||
1511                               (state->state & EXTENT_BOUNDARY))) {
1512                         goto out;
1513                 }
1514                 if (!(state->state & EXTENT_DELALLOC)) {
1515                         if (!found)
1516                                 *end = state->end;
1517                         goto out;
1518                 }
1519                 if (!found) {
1520                         *start = state->start;
1521                         *cached_state = state;
1522                         refcount_inc(&state->refs);
1523                 }
1524                 found = true;
1525                 *end = state->end;
1526                 cur_start = state->end + 1;
1527                 node = rb_next(node);
1528                 total_bytes += state->end - state->start + 1;
1529                 if (total_bytes >= max_bytes)
1530                         break;
1531                 if (!node)
1532                         break;
1533         }
1534 out:
1535         spin_unlock(&tree->lock);
1536         return found;
1537 }
1538
1539 static int __process_pages_contig(struct address_space *mapping,
1540                                   struct page *locked_page,
1541                                   pgoff_t start_index, pgoff_t end_index,
1542                                   unsigned long page_ops, pgoff_t *index_ret);
1543
1544 static noinline void __unlock_for_delalloc(struct inode *inode,
1545                                            struct page *locked_page,
1546                                            u64 start, u64 end)
1547 {
1548         unsigned long index = start >> PAGE_SHIFT;
1549         unsigned long end_index = end >> PAGE_SHIFT;
1550
1551         ASSERT(locked_page);
1552         if (index == locked_page->index && end_index == index)
1553                 return;
1554
1555         __process_pages_contig(inode->i_mapping, locked_page, index, end_index,
1556                                PAGE_UNLOCK, NULL);
1557 }
1558
1559 static noinline int lock_delalloc_pages(struct inode *inode,
1560                                         struct page *locked_page,
1561                                         u64 delalloc_start,
1562                                         u64 delalloc_end)
1563 {
1564         unsigned long index = delalloc_start >> PAGE_SHIFT;
1565         unsigned long index_ret = index;
1566         unsigned long end_index = delalloc_end >> PAGE_SHIFT;
1567         int ret;
1568
1569         ASSERT(locked_page);
1570         if (index == locked_page->index && index == end_index)
1571                 return 0;
1572
1573         ret = __process_pages_contig(inode->i_mapping, locked_page, index,
1574                                      end_index, PAGE_LOCK, &index_ret);
1575         if (ret == -EAGAIN)
1576                 __unlock_for_delalloc(inode, locked_page, delalloc_start,
1577                                       (u64)index_ret << PAGE_SHIFT);
1578         return ret;
1579 }
1580
1581 /*
1582  * Find and lock a contiguous range of bytes in the file marked as delalloc, no
1583  * more than @max_bytes.  @Start and @end are used to return the range,
1584  *
1585  * Return: true if we find something
1586  *         false if nothing was in the tree
1587  */
1588 EXPORT_FOR_TESTS
1589 noinline_for_stack bool find_lock_delalloc_range(struct inode *inode,
1590                                     struct extent_io_tree *tree,
1591                                     struct page *locked_page, u64 *start,
1592                                     u64 *end)
1593 {
1594         u64 max_bytes = BTRFS_MAX_EXTENT_SIZE;
1595         u64 delalloc_start;
1596         u64 delalloc_end;
1597         bool found;
1598         struct extent_state *cached_state = NULL;
1599         int ret;
1600         int loops = 0;
1601
1602 again:
1603         /* step one, find a bunch of delalloc bytes starting at start */
1604         delalloc_start = *start;
1605         delalloc_end = 0;
1606         found = find_delalloc_range(tree, &delalloc_start, &delalloc_end,
1607                                     max_bytes, &cached_state);
1608         if (!found || delalloc_end <= *start) {
1609                 *start = delalloc_start;
1610                 *end = delalloc_end;
1611                 free_extent_state(cached_state);
1612                 return false;
1613         }
1614
1615         /*
1616          * start comes from the offset of locked_page.  We have to lock
1617          * pages in order, so we can't process delalloc bytes before
1618          * locked_page
1619          */
1620         if (delalloc_start < *start)
1621                 delalloc_start = *start;
1622
1623         /*
1624          * make sure to limit the number of pages we try to lock down
1625          */
1626         if (delalloc_end + 1 - delalloc_start > max_bytes)
1627                 delalloc_end = delalloc_start + max_bytes - 1;
1628
1629         /* step two, lock all the pages after the page that has start */
1630         ret = lock_delalloc_pages(inode, locked_page,
1631                                   delalloc_start, delalloc_end);
1632         ASSERT(!ret || ret == -EAGAIN);
1633         if (ret == -EAGAIN) {
1634                 /* some of the pages are gone, lets avoid looping by
1635                  * shortening the size of the delalloc range we're searching
1636                  */
1637                 free_extent_state(cached_state);
1638                 cached_state = NULL;
1639                 if (!loops) {
1640                         max_bytes = PAGE_SIZE;
1641                         loops = 1;
1642                         goto again;
1643                 } else {
1644                         found = false;
1645                         goto out_failed;
1646                 }
1647         }
1648
1649         /* step three, lock the state bits for the whole range */
1650         lock_extent_bits(tree, delalloc_start, delalloc_end, &cached_state);
1651
1652         /* then test to make sure it is all still delalloc */
1653         ret = test_range_bit(tree, delalloc_start, delalloc_end,
1654                              EXTENT_DELALLOC, 1, cached_state);
1655         if (!ret) {
1656                 unlock_extent_cached(tree, delalloc_start, delalloc_end,
1657                                      &cached_state);
1658                 __unlock_for_delalloc(inode, locked_page,
1659                               delalloc_start, delalloc_end);
1660                 cond_resched();
1661                 goto again;
1662         }
1663         free_extent_state(cached_state);
1664         *start = delalloc_start;
1665         *end = delalloc_end;
1666 out_failed:
1667         return found;
1668 }
1669
1670 static int __process_pages_contig(struct address_space *mapping,
1671                                   struct page *locked_page,
1672                                   pgoff_t start_index, pgoff_t end_index,
1673                                   unsigned long page_ops, pgoff_t *index_ret)
1674 {
1675         unsigned long nr_pages = end_index - start_index + 1;
1676         unsigned long pages_locked = 0;
1677         pgoff_t index = start_index;
1678         struct page *pages[16];
1679         unsigned ret;
1680         int err = 0;
1681         int i;
1682
1683         if (page_ops & PAGE_LOCK) {
1684                 ASSERT(page_ops == PAGE_LOCK);
1685                 ASSERT(index_ret && *index_ret == start_index);
1686         }
1687
1688         if ((page_ops & PAGE_SET_ERROR) && nr_pages > 0)
1689                 mapping_set_error(mapping, -EIO);
1690
1691         while (nr_pages > 0) {
1692                 ret = find_get_pages_contig(mapping, index,
1693                                      min_t(unsigned long,
1694                                      nr_pages, ARRAY_SIZE(pages)), pages);
1695                 if (ret == 0) {
1696                         /*
1697                          * Only if we're going to lock these pages,
1698                          * can we find nothing at @index.
1699                          */
1700                         ASSERT(page_ops & PAGE_LOCK);
1701                         err = -EAGAIN;
1702                         goto out;
1703                 }
1704
1705                 for (i = 0; i < ret; i++) {
1706                         if (page_ops & PAGE_SET_PRIVATE2)
1707                                 SetPagePrivate2(pages[i]);
1708
1709                         if (pages[i] == locked_page) {
1710                                 put_page(pages[i]);
1711                                 pages_locked++;
1712                                 continue;
1713                         }
1714                         if (page_ops & PAGE_CLEAR_DIRTY)
1715                                 clear_page_dirty_for_io(pages[i]);
1716                         if (page_ops & PAGE_SET_WRITEBACK)
1717                                 set_page_writeback(pages[i]);
1718                         if (page_ops & PAGE_SET_ERROR)
1719                                 SetPageError(pages[i]);
1720                         if (page_ops & PAGE_END_WRITEBACK)
1721                                 end_page_writeback(pages[i]);
1722                         if (page_ops & PAGE_UNLOCK)
1723                                 unlock_page(pages[i]);
1724                         if (page_ops & PAGE_LOCK) {
1725                                 lock_page(pages[i]);
1726                                 if (!PageDirty(pages[i]) ||
1727                                     pages[i]->mapping != mapping) {
1728                                         unlock_page(pages[i]);
1729                                         put_page(pages[i]);
1730                                         err = -EAGAIN;
1731                                         goto out;
1732                                 }
1733                         }
1734                         put_page(pages[i]);
1735                         pages_locked++;
1736                 }
1737                 nr_pages -= ret;
1738                 index += ret;
1739                 cond_resched();
1740         }
1741 out:
1742         if (err && index_ret)
1743                 *index_ret = start_index + pages_locked - 1;
1744         return err;
1745 }
1746
1747 void extent_clear_unlock_delalloc(struct inode *inode, u64 start, u64 end,
1748                                  u64 delalloc_end, struct page *locked_page,
1749                                  unsigned clear_bits,
1750                                  unsigned long page_ops)
1751 {
1752         clear_extent_bit(&BTRFS_I(inode)->io_tree, start, end, clear_bits, 1, 0,
1753                          NULL);
1754
1755         __process_pages_contig(inode->i_mapping, locked_page,
1756                                start >> PAGE_SHIFT, end >> PAGE_SHIFT,
1757                                page_ops, NULL);
1758 }
1759
1760 /*
1761  * count the number of bytes in the tree that have a given bit(s)
1762  * set.  This can be fairly slow, except for EXTENT_DIRTY which is
1763  * cached.  The total number found is returned.
1764  */
1765 u64 count_range_bits(struct extent_io_tree *tree,
1766                      u64 *start, u64 search_end, u64 max_bytes,
1767                      unsigned bits, int contig)
1768 {
1769         struct rb_node *node;
1770         struct extent_state *state;
1771         u64 cur_start = *start;
1772         u64 total_bytes = 0;
1773         u64 last = 0;
1774         int found = 0;
1775
1776         if (WARN_ON(search_end <= cur_start))
1777                 return 0;
1778
1779         spin_lock(&tree->lock);
1780         if (cur_start == 0 && bits == EXTENT_DIRTY) {
1781                 total_bytes = tree->dirty_bytes;
1782                 goto out;
1783         }
1784         /*
1785          * this search will find all the extents that end after
1786          * our range starts.
1787          */
1788         node = tree_search(tree, cur_start);
1789         if (!node)
1790                 goto out;
1791
1792         while (1) {
1793                 state = rb_entry(node, struct extent_state, rb_node);
1794                 if (state->start > search_end)
1795                         break;
1796                 if (contig && found && state->start > last + 1)
1797                         break;
1798                 if (state->end >= cur_start && (state->state & bits) == bits) {
1799                         total_bytes += min(search_end, state->end) + 1 -
1800                                        max(cur_start, state->start);
1801                         if (total_bytes >= max_bytes)
1802                                 break;
1803                         if (!found) {
1804                                 *start = max(cur_start, state->start);
1805                                 found = 1;
1806                         }
1807                         last = state->end;
1808                 } else if (contig && found) {
1809                         break;
1810                 }
1811                 node = rb_next(node);
1812                 if (!node)
1813                         break;
1814         }
1815 out:
1816         spin_unlock(&tree->lock);
1817         return total_bytes;
1818 }
1819
1820 /*
1821  * set the private field for a given byte offset in the tree.  If there isn't
1822  * an extent_state there already, this does nothing.
1823  */
1824 static noinline int set_state_failrec(struct extent_io_tree *tree, u64 start,
1825                 struct io_failure_record *failrec)
1826 {
1827         struct rb_node *node;
1828         struct extent_state *state;
1829         int ret = 0;
1830
1831         spin_lock(&tree->lock);
1832         /*
1833          * this search will find all the extents that end after
1834          * our range starts.
1835          */
1836         node = tree_search(tree, start);
1837         if (!node) {
1838                 ret = -ENOENT;
1839                 goto out;
1840         }
1841         state = rb_entry(node, struct extent_state, rb_node);
1842         if (state->start != start) {
1843                 ret = -ENOENT;
1844                 goto out;
1845         }
1846         state->failrec = failrec;
1847 out:
1848         spin_unlock(&tree->lock);
1849         return ret;
1850 }
1851
1852 static noinline int get_state_failrec(struct extent_io_tree *tree, u64 start,
1853                 struct io_failure_record **failrec)
1854 {
1855         struct rb_node *node;
1856         struct extent_state *state;
1857         int ret = 0;
1858
1859         spin_lock(&tree->lock);
1860         /*
1861          * this search will find all the extents that end after
1862          * our range starts.
1863          */
1864         node = tree_search(tree, start);
1865         if (!node) {
1866                 ret = -ENOENT;
1867                 goto out;
1868         }
1869         state = rb_entry(node, struct extent_state, rb_node);
1870         if (state->start != start) {
1871                 ret = -ENOENT;
1872                 goto out;
1873         }
1874         *failrec = state->failrec;
1875 out:
1876         spin_unlock(&tree->lock);
1877         return ret;
1878 }
1879
1880 /*
1881  * searches a range in the state tree for a given mask.
1882  * If 'filled' == 1, this returns 1 only if every extent in the tree
1883  * has the bits set.  Otherwise, 1 is returned if any bit in the
1884  * range is found set.
1885  */
1886 int test_range_bit(struct extent_io_tree *tree, u64 start, u64 end,
1887                    unsigned bits, int filled, struct extent_state *cached)
1888 {
1889         struct extent_state *state = NULL;
1890         struct rb_node *node;
1891         int bitset = 0;
1892
1893         spin_lock(&tree->lock);
1894         if (cached && extent_state_in_tree(cached) && cached->start <= start &&
1895             cached->end > start)
1896                 node = &cached->rb_node;
1897         else
1898                 node = tree_search(tree, start);
1899         while (node && start <= end) {
1900                 state = rb_entry(node, struct extent_state, rb_node);
1901
1902                 if (filled && state->start > start) {
1903                         bitset = 0;
1904                         break;
1905                 }
1906
1907                 if (state->start > end)
1908                         break;
1909
1910                 if (state->state & bits) {
1911                         bitset = 1;
1912                         if (!filled)
1913                                 break;
1914                 } else if (filled) {
1915                         bitset = 0;
1916                         break;
1917                 }
1918
1919                 if (state->end == (u64)-1)
1920                         break;
1921
1922                 start = state->end + 1;
1923                 if (start > end)
1924                         break;
1925                 node = rb_next(node);
1926                 if (!node) {
1927                         if (filled)
1928                                 bitset = 0;
1929                         break;
1930                 }
1931         }
1932         spin_unlock(&tree->lock);
1933         return bitset;
1934 }
1935
1936 /*
1937  * helper function to set a given page up to date if all the
1938  * extents in the tree for that page are up to date
1939  */
1940 static void check_page_uptodate(struct extent_io_tree *tree, struct page *page)
1941 {
1942         u64 start = page_offset(page);
1943         u64 end = start + PAGE_SIZE - 1;
1944         if (test_range_bit(tree, start, end, EXTENT_UPTODATE, 1, NULL))
1945                 SetPageUptodate(page);
1946 }
1947
1948 int free_io_failure(struct extent_io_tree *failure_tree,
1949                     struct extent_io_tree *io_tree,
1950                     struct io_failure_record *rec)
1951 {
1952         int ret;
1953         int err = 0;
1954
1955         set_state_failrec(failure_tree, rec->start, NULL);
1956         ret = clear_extent_bits(failure_tree, rec->start,
1957                                 rec->start + rec->len - 1,
1958                                 EXTENT_LOCKED | EXTENT_DIRTY);
1959         if (ret)
1960                 err = ret;
1961
1962         ret = clear_extent_bits(io_tree, rec->start,
1963                                 rec->start + rec->len - 1,
1964                                 EXTENT_DAMAGED);
1965         if (ret && !err)
1966                 err = ret;
1967
1968         kfree(rec);
1969         return err;
1970 }
1971
1972 /*
1973  * this bypasses the standard btrfs submit functions deliberately, as
1974  * the standard behavior is to write all copies in a raid setup. here we only
1975  * want to write the one bad copy. so we do the mapping for ourselves and issue
1976  * submit_bio directly.
1977  * to avoid any synchronization issues, wait for the data after writing, which
1978  * actually prevents the read that triggered the error from finishing.
1979  * currently, there can be no more than two copies of every data bit. thus,
1980  * exactly one rewrite is required.
1981  */
1982 int repair_io_failure(struct btrfs_fs_info *fs_info, u64 ino, u64 start,
1983                       u64 length, u64 logical, struct page *page,
1984                       unsigned int pg_offset, int mirror_num)
1985 {
1986         struct bio *bio;
1987         struct btrfs_device *dev;
1988         u64 map_length = 0;
1989         u64 sector;
1990         struct btrfs_bio *bbio = NULL;
1991         int ret;
1992
1993         ASSERT(!(fs_info->sb->s_flags & SB_RDONLY));
1994         BUG_ON(!mirror_num);
1995
1996         bio = btrfs_io_bio_alloc(1);
1997         bio->bi_iter.bi_size = 0;
1998         map_length = length;
1999
2000         /*
2001          * Avoid races with device replace and make sure our bbio has devices
2002          * associated to its stripes that don't go away while we are doing the
2003          * read repair operation.
2004          */
2005         btrfs_bio_counter_inc_blocked(fs_info);
2006         if (btrfs_is_parity_mirror(fs_info, logical, length)) {
2007                 /*
2008                  * Note that we don't use BTRFS_MAP_WRITE because it's supposed
2009                  * to update all raid stripes, but here we just want to correct
2010                  * bad stripe, thus BTRFS_MAP_READ is abused to only get the bad
2011                  * stripe's dev and sector.
2012                  */
2013                 ret = btrfs_map_block(fs_info, BTRFS_MAP_READ, logical,
2014                                       &map_length, &bbio, 0);
2015                 if (ret) {
2016                         btrfs_bio_counter_dec(fs_info);
2017                         bio_put(bio);
2018                         return -EIO;
2019                 }
2020                 ASSERT(bbio->mirror_num == 1);
2021         } else {
2022                 ret = btrfs_map_block(fs_info, BTRFS_MAP_WRITE, logical,
2023                                       &map_length, &bbio, mirror_num);
2024                 if (ret) {
2025                         btrfs_bio_counter_dec(fs_info);
2026                         bio_put(bio);
2027                         return -EIO;
2028                 }
2029                 BUG_ON(mirror_num != bbio->mirror_num);
2030         }
2031
2032         sector = bbio->stripes[bbio->mirror_num - 1].physical >> 9;
2033         bio->bi_iter.bi_sector = sector;
2034         dev = bbio->stripes[bbio->mirror_num - 1].dev;
2035         btrfs_put_bbio(bbio);
2036         if (!dev || !dev->bdev ||
2037             !test_bit(BTRFS_DEV_STATE_WRITEABLE, &dev->dev_state)) {
2038                 btrfs_bio_counter_dec(fs_info);
2039                 bio_put(bio);
2040                 return -EIO;
2041         }
2042         bio_set_dev(bio, dev->bdev);
2043         bio->bi_opf = REQ_OP_WRITE | REQ_SYNC;
2044         bio_add_page(bio, page, length, pg_offset);
2045
2046         if (btrfsic_submit_bio_wait(bio)) {
2047                 /* try to remap that extent elsewhere? */
2048                 btrfs_bio_counter_dec(fs_info);
2049                 bio_put(bio);
2050                 btrfs_dev_stat_inc_and_print(dev, BTRFS_DEV_STAT_WRITE_ERRS);
2051                 return -EIO;
2052         }
2053
2054         btrfs_info_rl_in_rcu(fs_info,
2055                 "read error corrected: ino %llu off %llu (dev %s sector %llu)",
2056                                   ino, start,
2057                                   rcu_str_deref(dev->name), sector);
2058         btrfs_bio_counter_dec(fs_info);
2059         bio_put(bio);
2060         return 0;
2061 }
2062
2063 int repair_eb_io_failure(struct btrfs_fs_info *fs_info,
2064                          struct extent_buffer *eb, int mirror_num)
2065 {
2066         u64 start = eb->start;
2067         int i, num_pages = num_extent_pages(eb);
2068         int ret = 0;
2069
2070         if (sb_rdonly(fs_info->sb))
2071                 return -EROFS;
2072
2073         for (i = 0; i < num_pages; i++) {
2074                 struct page *p = eb->pages[i];
2075
2076                 ret = repair_io_failure(fs_info, 0, start, PAGE_SIZE, start, p,
2077                                         start - page_offset(p), mirror_num);
2078                 if (ret)
2079                         break;
2080                 start += PAGE_SIZE;
2081         }
2082
2083         return ret;
2084 }
2085
2086 /*
2087  * each time an IO finishes, we do a fast check in the IO failure tree
2088  * to see if we need to process or clean up an io_failure_record
2089  */
2090 int clean_io_failure(struct btrfs_fs_info *fs_info,
2091                      struct extent_io_tree *failure_tree,
2092                      struct extent_io_tree *io_tree, u64 start,
2093                      struct page *page, u64 ino, unsigned int pg_offset)
2094 {
2095         u64 private;
2096         struct io_failure_record *failrec;
2097         struct extent_state *state;
2098         int num_copies;
2099         int ret;
2100
2101         private = 0;
2102         ret = count_range_bits(failure_tree, &private, (u64)-1, 1,
2103                                EXTENT_DIRTY, 0);
2104         if (!ret)
2105                 return 0;
2106
2107         ret = get_state_failrec(failure_tree, start, &failrec);
2108         if (ret)
2109                 return 0;
2110
2111         BUG_ON(!failrec->this_mirror);
2112
2113         if (failrec->in_validation) {
2114                 /* there was no real error, just free the record */
2115                 btrfs_debug(fs_info,
2116                         "clean_io_failure: freeing dummy error at %llu",
2117                         failrec->start);
2118                 goto out;
2119         }
2120         if (sb_rdonly(fs_info->sb))
2121                 goto out;
2122
2123         spin_lock(&io_tree->lock);
2124         state = find_first_extent_bit_state(io_tree,
2125                                             failrec->start,
2126                                             EXTENT_LOCKED);
2127         spin_unlock(&io_tree->lock);
2128
2129         if (state && state->start <= failrec->start &&
2130             state->end >= failrec->start + failrec->len - 1) {
2131                 num_copies = btrfs_num_copies(fs_info, failrec->logical,
2132                                               failrec->len);
2133                 if (num_copies > 1)  {
2134                         repair_io_failure(fs_info, ino, start, failrec->len,
2135                                           failrec->logical, page, pg_offset,
2136                                           failrec->failed_mirror);
2137                 }
2138         }
2139
2140 out:
2141         free_io_failure(failure_tree, io_tree, failrec);
2142
2143         return 0;
2144 }
2145
2146 /*
2147  * Can be called when
2148  * - hold extent lock
2149  * - under ordered extent
2150  * - the inode is freeing
2151  */
2152 void btrfs_free_io_failure_record(struct btrfs_inode *inode, u64 start, u64 end)
2153 {
2154         struct extent_io_tree *failure_tree = &inode->io_failure_tree;
2155         struct io_failure_record *failrec;
2156         struct extent_state *state, *next;
2157
2158         if (RB_EMPTY_ROOT(&failure_tree->state))
2159                 return;
2160
2161         spin_lock(&failure_tree->lock);
2162         state = find_first_extent_bit_state(failure_tree, start, EXTENT_DIRTY);
2163         while (state) {
2164                 if (state->start > end)
2165                         break;
2166
2167                 ASSERT(state->end <= end);
2168
2169                 next = next_state(state);
2170
2171                 failrec = state->failrec;
2172                 free_extent_state(state);
2173                 kfree(failrec);
2174
2175                 state = next;
2176         }
2177         spin_unlock(&failure_tree->lock);
2178 }
2179
2180 int btrfs_get_io_failure_record(struct inode *inode, u64 start, u64 end,
2181                 struct io_failure_record **failrec_ret)
2182 {
2183         struct btrfs_fs_info *fs_info = btrfs_sb(inode->i_sb);
2184         struct io_failure_record *failrec;
2185         struct extent_map *em;
2186         struct extent_io_tree *failure_tree = &BTRFS_I(inode)->io_failure_tree;
2187         struct extent_io_tree *tree = &BTRFS_I(inode)->io_tree;
2188         struct extent_map_tree *em_tree = &BTRFS_I(inode)->extent_tree;
2189         int ret;
2190         u64 logical;
2191
2192         ret = get_state_failrec(failure_tree, start, &failrec);
2193         if (ret) {
2194                 failrec = kzalloc(sizeof(*failrec), GFP_NOFS);
2195                 if (!failrec)
2196                         return -ENOMEM;
2197
2198                 failrec->start = start;
2199                 failrec->len = end - start + 1;
2200                 failrec->this_mirror = 0;
2201                 failrec->bio_flags = 0;
2202                 failrec->in_validation = 0;
2203
2204                 read_lock(&em_tree->lock);
2205                 em = lookup_extent_mapping(em_tree, start, failrec->len);
2206                 if (!em) {
2207                         read_unlock(&em_tree->lock);
2208                         kfree(failrec);
2209                         return -EIO;
2210                 }
2211
2212                 if (em->start > start || em->start + em->len <= start) {
2213                         free_extent_map(em);
2214                         em = NULL;
2215                 }
2216                 read_unlock(&em_tree->lock);
2217                 if (!em) {
2218                         kfree(failrec);
2219                         return -EIO;
2220                 }
2221
2222                 logical = start - em->start;
2223                 logical = em->block_start + logical;
2224                 if (test_bit(EXTENT_FLAG_COMPRESSED, &em->flags)) {
2225                         logical = em->block_start;
2226                         failrec->bio_flags = EXTENT_BIO_COMPRESSED;
2227                         extent_set_compress_type(&failrec->bio_flags,
2228                                                  em->compress_type);
2229                 }
2230
2231                 btrfs_debug(fs_info,
2232                         "Get IO Failure Record: (new) logical=%llu, start=%llu, len=%llu",
2233                         logical, start, failrec->len);
2234
2235                 failrec->logical = logical;
2236                 free_extent_map(em);
2237
2238                 /* set the bits in the private failure tree */
2239                 ret = set_extent_bits(failure_tree, start, end,
2240                                         EXTENT_LOCKED | EXTENT_DIRTY);
2241                 if (ret >= 0)
2242                         ret = set_state_failrec(failure_tree, start, failrec);
2243                 /* set the bits in the inode's tree */
2244                 if (ret >= 0)
2245                         ret = set_extent_bits(tree, start, end, EXTENT_DAMAGED);
2246                 if (ret < 0) {
2247                         kfree(failrec);
2248                         return ret;
2249                 }
2250         } else {
2251                 btrfs_debug(fs_info,
2252                         "Get IO Failure Record: (found) logical=%llu, start=%llu, len=%llu, validation=%d",
2253                         failrec->logical, failrec->start, failrec->len,
2254                         failrec->in_validation);
2255                 /*
2256                  * when data can be on disk more than twice, add to failrec here
2257                  * (e.g. with a list for failed_mirror) to make
2258                  * clean_io_failure() clean all those errors at once.
2259                  */
2260         }
2261
2262         *failrec_ret = failrec;
2263
2264         return 0;
2265 }
2266
2267 bool btrfs_check_repairable(struct inode *inode, unsigned failed_bio_pages,
2268                            struct io_failure_record *failrec, int failed_mirror)
2269 {
2270         struct btrfs_fs_info *fs_info = btrfs_sb(inode->i_sb);
2271         int num_copies;
2272
2273         num_copies = btrfs_num_copies(fs_info, failrec->logical, failrec->len);
2274         if (num_copies == 1) {
2275                 /*
2276                  * we only have a single copy of the data, so don't bother with
2277                  * all the retry and error correction code that follows. no
2278                  * matter what the error is, it is very likely to persist.
2279                  */
2280                 btrfs_debug(fs_info,
2281                         "Check Repairable: cannot repair, num_copies=%d, next_mirror %d, failed_mirror %d",
2282                         num_copies, failrec->this_mirror, failed_mirror);
2283                 return false;
2284         }
2285
2286         /*
2287          * there are two premises:
2288          *      a) deliver good data to the caller
2289          *      b) correct the bad sectors on disk
2290          */
2291         if (failed_bio_pages > 1) {
2292                 /*
2293                  * to fulfill b), we need to know the exact failing sectors, as
2294                  * we don't want to rewrite any more than the failed ones. thus,
2295                  * we need separate read requests for the failed bio
2296                  *
2297                  * if the following BUG_ON triggers, our validation request got
2298                  * merged. we need separate requests for our algorithm to work.
2299                  */
2300                 BUG_ON(failrec->in_validation);
2301                 failrec->in_validation = 1;
2302                 failrec->this_mirror = failed_mirror;
2303         } else {
2304                 /*
2305                  * we're ready to fulfill a) and b) alongside. get a good copy
2306                  * of the failed sector and if we succeed, we have setup
2307                  * everything for repair_io_failure to do the rest for us.
2308                  */
2309                 if (failrec->in_validation) {
2310                         BUG_ON(failrec->this_mirror != failed_mirror);
2311                         failrec->in_validation = 0;
2312                         failrec->this_mirror = 0;
2313                 }
2314                 failrec->failed_mirror = failed_mirror;
2315                 failrec->this_mirror++;
2316                 if (failrec->this_mirror == failed_mirror)
2317                         failrec->this_mirror++;
2318         }
2319
2320         if (failrec->this_mirror > num_copies) {
2321                 btrfs_debug(fs_info,
2322                         "Check Repairable: (fail) num_copies=%d, next_mirror %d, failed_mirror %d",
2323                         num_copies, failrec->this_mirror, failed_mirror);
2324                 return false;
2325         }
2326
2327         return true;
2328 }
2329
2330
2331 struct bio *btrfs_create_repair_bio(struct inode *inode, struct bio *failed_bio,
2332                                     struct io_failure_record *failrec,
2333                                     struct page *page, int pg_offset, int icsum,
2334                                     bio_end_io_t *endio_func, void *data)
2335 {
2336         struct btrfs_fs_info *fs_info = btrfs_sb(inode->i_sb);
2337         struct bio *bio;
2338         struct btrfs_io_bio *btrfs_failed_bio;
2339         struct btrfs_io_bio *btrfs_bio;
2340
2341         bio = btrfs_io_bio_alloc(1);
2342         bio->bi_end_io = endio_func;
2343         bio->bi_iter.bi_sector = failrec->logical >> 9;
2344         bio_set_dev(bio, fs_info->fs_devices->latest_bdev);
2345         bio->bi_iter.bi_size = 0;
2346         bio->bi_private = data;
2347
2348         btrfs_failed_bio = btrfs_io_bio(failed_bio);
2349         if (btrfs_failed_bio->csum) {
2350                 u16 csum_size = btrfs_super_csum_size(fs_info->super_copy);
2351
2352                 btrfs_bio = btrfs_io_bio(bio);
2353                 btrfs_bio->csum = btrfs_bio->csum_inline;
2354                 icsum *= csum_size;
2355                 memcpy(btrfs_bio->csum, btrfs_failed_bio->csum + icsum,
2356                        csum_size);
2357         }
2358
2359         bio_add_page(bio, page, failrec->len, pg_offset);
2360
2361         return bio;
2362 }
2363
2364 /*
2365  * This is a generic handler for readpage errors. If other copies exist, read
2366  * those and write back good data to the failed position. Does not investigate
2367  * in remapping the failed extent elsewhere, hoping the device will be smart
2368  * enough to do this as needed
2369  */
2370 static int bio_readpage_error(struct bio *failed_bio, u64 phy_offset,
2371                               struct page *page, u64 start, u64 end,
2372                               int failed_mirror)
2373 {
2374         struct io_failure_record *failrec;
2375         struct inode *inode = page->mapping->host;
2376         struct extent_io_tree *tree = &BTRFS_I(inode)->io_tree;
2377         struct extent_io_tree *failure_tree = &BTRFS_I(inode)->io_failure_tree;
2378         struct bio *bio;
2379         int read_mode = 0;
2380         blk_status_t status;
2381         int ret;
2382         unsigned failed_bio_pages = bio_pages_all(failed_bio);
2383
2384         BUG_ON(bio_op(failed_bio) == REQ_OP_WRITE);
2385
2386         ret = btrfs_get_io_failure_record(inode, start, end, &failrec);
2387         if (ret)
2388                 return ret;
2389
2390         if (!btrfs_check_repairable(inode, failed_bio_pages, failrec,
2391                                     failed_mirror)) {
2392                 free_io_failure(failure_tree, tree, failrec);
2393                 return -EIO;
2394         }
2395
2396         if (failed_bio_pages > 1)
2397                 read_mode |= REQ_FAILFAST_DEV;
2398
2399         phy_offset >>= inode->i_sb->s_blocksize_bits;
2400         bio = btrfs_create_repair_bio(inode, failed_bio, failrec, page,
2401                                       start - page_offset(page),
2402                                       (int)phy_offset, failed_bio->bi_end_io,
2403                                       NULL);
2404         bio->bi_opf = REQ_OP_READ | read_mode;
2405
2406         btrfs_debug(btrfs_sb(inode->i_sb),
2407                 "Repair Read Error: submitting new read[%#x] to this_mirror=%d, in_validation=%d",
2408                 read_mode, failrec->this_mirror, failrec->in_validation);
2409
2410         status = tree->ops->submit_bio_hook(tree->private_data, bio, failrec->this_mirror,
2411                                          failrec->bio_flags, 0);
2412         if (status) {
2413                 free_io_failure(failure_tree, tree, failrec);
2414                 bio_put(bio);
2415                 ret = blk_status_to_errno(status);
2416         }
2417
2418         return ret;
2419 }
2420
2421 /* lots and lots of room for performance fixes in the end_bio funcs */
2422
2423 void end_extent_writepage(struct page *page, int err, u64 start, u64 end)
2424 {
2425         int uptodate = (err == 0);
2426         int ret = 0;
2427
2428         btrfs_writepage_endio_finish_ordered(page, start, end, uptodate);
2429
2430         if (!uptodate) {
2431                 ClearPageUptodate(page);
2432                 SetPageError(page);
2433                 ret = err < 0 ? err : -EIO;
2434                 mapping_set_error(page->mapping, ret);
2435         }
2436 }
2437
2438 /*
2439  * after a writepage IO is done, we need to:
2440  * clear the uptodate bits on error
2441  * clear the writeback bits in the extent tree for this IO
2442  * end_page_writeback if the page has no more pending IO
2443  *
2444  * Scheduling is not allowed, so the extent state tree is expected
2445  * to have one and only one object corresponding to this IO.
2446  */
2447 static void end_bio_extent_writepage(struct bio *bio)
2448 {
2449         int error = blk_status_to_errno(bio->bi_status);
2450         struct bio_vec *bvec;
2451         u64 start;
2452         u64 end;
2453         int i;
2454
2455         ASSERT(!bio_flagged(bio, BIO_CLONED));
2456         bio_for_each_segment_all(bvec, bio, i) {
2457                 struct page *page = bvec->bv_page;
2458                 struct inode *inode = page->mapping->host;
2459                 struct btrfs_fs_info *fs_info = btrfs_sb(inode->i_sb);
2460
2461                 /* We always issue full-page reads, but if some block
2462                  * in a page fails to read, blk_update_request() will
2463                  * advance bv_offset and adjust bv_len to compensate.
2464                  * Print a warning for nonzero offsets, and an error
2465                  * if they don't add up to a full page.  */
2466                 if (bvec->bv_offset || bvec->bv_len != PAGE_SIZE) {
2467                         if (bvec->bv_offset + bvec->bv_len != PAGE_SIZE)
2468                                 btrfs_err(fs_info,
2469                                    "partial page write in btrfs with offset %u and length %u",
2470                                         bvec->bv_offset, bvec->bv_len);
2471                         else
2472                                 btrfs_info(fs_info,
2473                                    "incomplete page write in btrfs with offset %u and length %u",
2474                                         bvec->bv_offset, bvec->bv_len);
2475                 }
2476
2477                 start = page_offset(page);
2478                 end = start + bvec->bv_offset + bvec->bv_len - 1;
2479
2480                 end_extent_writepage(page, error, start, end);
2481                 end_page_writeback(page);
2482         }
2483
2484         bio_put(bio);
2485 }
2486
2487 static void
2488 endio_readpage_release_extent(struct extent_io_tree *tree, u64 start, u64 len,
2489                               int uptodate)
2490 {
2491         struct extent_state *cached = NULL;
2492         u64 end = start + len - 1;
2493
2494         if (uptodate && tree->track_uptodate)
2495                 set_extent_uptodate(tree, start, end, &cached, GFP_ATOMIC);
2496         unlock_extent_cached_atomic(tree, start, end, &cached);
2497 }
2498
2499 /*
2500  * after a readpage IO is done, we need to:
2501  * clear the uptodate bits on error
2502  * set the uptodate bits if things worked
2503  * set the page up to date if all extents in the tree are uptodate
2504  * clear the lock bit in the extent tree
2505  * unlock the page if there are no other extents locked for it
2506  *
2507  * Scheduling is not allowed, so the extent state tree is expected
2508  * to have one and only one object corresponding to this IO.
2509  */
2510 static void end_bio_extent_readpage(struct bio *bio)
2511 {
2512         struct bio_vec *bvec;
2513         int uptodate = !bio->bi_status;
2514         struct btrfs_io_bio *io_bio = btrfs_io_bio(bio);
2515         struct extent_io_tree *tree, *failure_tree;
2516         u64 offset = 0;
2517         u64 start;
2518         u64 end;
2519         u64 len;
2520         u64 extent_start = 0;
2521         u64 extent_len = 0;
2522         int mirror;
2523         int ret;
2524         int i;
2525
2526         ASSERT(!bio_flagged(bio, BIO_CLONED));
2527         bio_for_each_segment_all(bvec, bio, i) {
2528                 struct page *page = bvec->bv_page;
2529                 struct inode *inode = page->mapping->host;
2530                 struct btrfs_fs_info *fs_info = btrfs_sb(inode->i_sb);
2531                 bool data_inode = btrfs_ino(BTRFS_I(inode))
2532                         != BTRFS_BTREE_INODE_OBJECTID;
2533
2534                 btrfs_debug(fs_info,
2535                         "end_bio_extent_readpage: bi_sector=%llu, err=%d, mirror=%u",
2536                         (u64)bio->bi_iter.bi_sector, bio->bi_status,
2537                         io_bio->mirror_num);
2538                 tree = &BTRFS_I(inode)->io_tree;
2539                 failure_tree = &BTRFS_I(inode)->io_failure_tree;
2540
2541                 /* We always issue full-page reads, but if some block
2542                  * in a page fails to read, blk_update_request() will
2543                  * advance bv_offset and adjust bv_len to compensate.
2544                  * Print a warning for nonzero offsets, and an error
2545                  * if they don't add up to a full page.  */
2546                 if (bvec->bv_offset || bvec->bv_len != PAGE_SIZE) {
2547                         if (bvec->bv_offset + bvec->bv_len != PAGE_SIZE)
2548                                 btrfs_err(fs_info,
2549                                         "partial page read in btrfs with offset %u and length %u",
2550                                         bvec->bv_offset, bvec->bv_len);
2551                         else
2552                                 btrfs_info(fs_info,
2553                                         "incomplete page read in btrfs with offset %u and length %u",
2554                                         bvec->bv_offset, bvec->bv_len);
2555                 }
2556
2557                 start = page_offset(page);
2558                 end = start + bvec->bv_offset + bvec->bv_len - 1;
2559                 len = bvec->bv_len;
2560
2561                 mirror = io_bio->mirror_num;
2562                 if (likely(uptodate)) {
2563                         ret = tree->ops->readpage_end_io_hook(io_bio, offset,
2564                                                               page, start, end,
2565                                                               mirror);
2566                         if (ret)
2567                                 uptodate = 0;
2568                         else
2569                                 clean_io_failure(BTRFS_I(inode)->root->fs_info,
2570                                                  failure_tree, tree, start,
2571                                                  page,
2572                                                  btrfs_ino(BTRFS_I(inode)), 0);
2573                 }
2574
2575                 if (likely(uptodate))
2576                         goto readpage_ok;
2577
2578                 if (data_inode) {
2579
2580                         /*
2581                          * The generic bio_readpage_error handles errors the
2582                          * following way: If possible, new read requests are
2583                          * created and submitted and will end up in
2584                          * end_bio_extent_readpage as well (if we're lucky,
2585                          * not in the !uptodate case). In that case it returns
2586                          * 0 and we just go on with the next page in our bio.
2587                          * If it can't handle the error it will return -EIO and
2588                          * we remain responsible for that page.
2589                          */
2590                         ret = bio_readpage_error(bio, offset, page, start, end,
2591                                                  mirror);
2592                         if (ret == 0) {
2593                                 uptodate = !bio->bi_status;
2594                                 offset += len;
2595                                 continue;
2596                         }
2597                 } else {
2598                         struct extent_buffer *eb;
2599
2600                         eb = (struct extent_buffer *)page->private;
2601                         set_bit(EXTENT_BUFFER_READ_ERR, &eb->bflags);
2602                         eb->read_mirror = mirror;
2603                         atomic_dec(&eb->io_pages);
2604                         if (test_and_clear_bit(EXTENT_BUFFER_READAHEAD,
2605                                                &eb->bflags))
2606                                 btree_readahead_hook(eb, -EIO);
2607
2608                         ret = -EIO;
2609                 }
2610 readpage_ok:
2611                 if (likely(uptodate)) {
2612                         loff_t i_size = i_size_read(inode);
2613                         pgoff_t end_index = i_size >> PAGE_SHIFT;
2614                         unsigned off;
2615
2616                         /* Zero out the end if this page straddles i_size */
2617                         off = offset_in_page(i_size);
2618                         if (page->index == end_index && off)
2619                                 zero_user_segment(page, off, PAGE_SIZE);
2620                         SetPageUptodate(page);
2621                 } else {
2622                         ClearPageUptodate(page);
2623                         SetPageError(page);
2624                 }
2625                 unlock_page(page);
2626                 offset += len;
2627
2628                 if (unlikely(!uptodate)) {
2629                         if (extent_len) {
2630                                 endio_readpage_release_extent(tree,
2631                                                               extent_start,
2632                                                               extent_len, 1);
2633                                 extent_start = 0;
2634                                 extent_len = 0;
2635                         }
2636                         endio_readpage_release_extent(tree, start,
2637                                                       end - start + 1, 0);
2638                 } else if (!extent_len) {
2639                         extent_start = start;
2640                         extent_len = end + 1 - start;
2641                 } else if (extent_start + extent_len == start) {
2642                         extent_len += end + 1 - start;
2643                 } else {
2644                         endio_readpage_release_extent(tree, extent_start,
2645                                                       extent_len, uptodate);
2646                         extent_start = start;
2647                         extent_len = end + 1 - start;
2648                 }
2649         }
2650
2651         if (extent_len)
2652                 endio_readpage_release_extent(tree, extent_start, extent_len,
2653                                               uptodate);
2654         btrfs_io_bio_free_csum(io_bio);
2655         bio_put(bio);
2656 }
2657
2658 /*
2659  * Initialize the members up to but not including 'bio'. Use after allocating a
2660  * new bio by bio_alloc_bioset as it does not initialize the bytes outside of
2661  * 'bio' because use of __GFP_ZERO is not supported.
2662  */
2663 static inline void btrfs_io_bio_init(struct btrfs_io_bio *btrfs_bio)
2664 {
2665         memset(btrfs_bio, 0, offsetof(struct btrfs_io_bio, bio));
2666 }
2667
2668 /*
2669  * The following helpers allocate a bio. As it's backed by a bioset, it'll
2670  * never fail.  We're returning a bio right now but you can call btrfs_io_bio
2671  * for the appropriate container_of magic
2672  */
2673 struct bio *btrfs_bio_alloc(struct block_device *bdev, u64 first_byte)
2674 {
2675         struct bio *bio;
2676
2677         bio = bio_alloc_bioset(GFP_NOFS, BIO_MAX_PAGES, &btrfs_bioset);
2678         bio_set_dev(bio, bdev);
2679         bio->bi_iter.bi_sector = first_byte >> 9;
2680         btrfs_io_bio_init(btrfs_io_bio(bio));
2681         return bio;
2682 }
2683
2684 struct bio *btrfs_bio_clone(struct bio *bio)
2685 {
2686         struct btrfs_io_bio *btrfs_bio;
2687         struct bio *new;
2688
2689         /* Bio allocation backed by a bioset does not fail */
2690         new = bio_clone_fast(bio, GFP_NOFS, &btrfs_bioset);
2691         btrfs_bio = btrfs_io_bio(new);
2692         btrfs_io_bio_init(btrfs_bio);
2693         btrfs_bio->iter = bio->bi_iter;
2694         return new;
2695 }
2696
2697 struct bio *btrfs_io_bio_alloc(unsigned int nr_iovecs)
2698 {
2699         struct bio *bio;
2700
2701         /* Bio allocation backed by a bioset does not fail */
2702         bio = bio_alloc_bioset(GFP_NOFS, nr_iovecs, &btrfs_bioset);
2703         btrfs_io_bio_init(btrfs_io_bio(bio));
2704         return bio;
2705 }
2706
2707 struct bio *btrfs_bio_clone_partial(struct bio *orig, int offset, int size)
2708 {
2709         struct bio *bio;
2710         struct btrfs_io_bio *btrfs_bio;
2711
2712         /* this will never fail when it's backed by a bioset */
2713         bio = bio_clone_fast(orig, GFP_NOFS, &btrfs_bioset);
2714         ASSERT(bio);
2715
2716         btrfs_bio = btrfs_io_bio(bio);
2717         btrfs_io_bio_init(btrfs_bio);
2718
2719         bio_trim(bio, offset >> 9, size >> 9);
2720         btrfs_bio->iter = bio->bi_iter;
2721         return bio;
2722 }
2723
2724 /*
2725  * @opf:        bio REQ_OP_* and REQ_* flags as one value
2726  * @tree:       tree so we can call our merge_bio hook
2727  * @wbc:        optional writeback control for io accounting
2728  * @page:       page to add to the bio
2729  * @pg_offset:  offset of the new bio or to check whether we are adding
2730  *              a contiguous page to the previous one
2731  * @size:       portion of page that we want to write
2732  * @offset:     starting offset in the page
2733  * @bdev:       attach newly created bios to this bdev
2734  * @bio_ret:    must be valid pointer, newly allocated bio will be stored there
2735  * @end_io_func:     end_io callback for new bio
2736  * @mirror_num:      desired mirror to read/write
2737  * @prev_bio_flags:  flags of previous bio to see if we can merge the current one
2738  * @bio_flags:  flags of the current bio to see if we can merge them
2739  */
2740 static int submit_extent_page(unsigned int opf, struct extent_io_tree *tree,
2741                               struct writeback_control *wbc,
2742                               struct page *page, u64 offset,
2743                               size_t size, unsigned long pg_offset,
2744                               struct block_device *bdev,
2745                               struct bio **bio_ret,
2746                               bio_end_io_t end_io_func,
2747                               int mirror_num,
2748                               unsigned long prev_bio_flags,
2749                               unsigned long bio_flags,
2750                               bool force_bio_submit)
2751 {
2752         int ret = 0;
2753         struct bio *bio;
2754         size_t page_size = min_t(size_t, size, PAGE_SIZE);
2755         sector_t sector = offset >> 9;
2756
2757         ASSERT(bio_ret);
2758
2759         if (*bio_ret) {
2760                 bool contig;
2761                 bool can_merge = true;
2762
2763                 bio = *bio_ret;
2764                 if (prev_bio_flags & EXTENT_BIO_COMPRESSED)
2765                         contig = bio->bi_iter.bi_sector == sector;
2766                 else
2767                         contig = bio_end_sector(bio) == sector;
2768
2769                 ASSERT(tree->ops);
2770                 if (btrfs_bio_fits_in_stripe(page, page_size, bio, bio_flags))
2771                         can_merge = false;
2772
2773                 if (prev_bio_flags != bio_flags || !contig || !can_merge ||
2774                     force_bio_submit ||
2775                     bio_add_page(bio, page, page_size, pg_offset) < page_size) {
2776                         ret = submit_one_bio(bio, mirror_num, prev_bio_flags);
2777                         if (ret < 0) {
2778                                 *bio_ret = NULL;
2779                                 return ret;
2780                         }
2781                         bio = NULL;
2782                 } else {
2783                         if (wbc)
2784                                 wbc_account_io(wbc, page, page_size);
2785                         return 0;
2786                 }
2787         }
2788
2789         bio = btrfs_bio_alloc(bdev, offset);
2790         bio_add_page(bio, page, page_size, pg_offset);
2791         bio->bi_end_io = end_io_func;
2792         bio->bi_private = tree;
2793         bio->bi_write_hint = page->mapping->host->i_write_hint;
2794         bio->bi_opf = opf;
2795         if (wbc) {
2796                 wbc_init_bio(wbc, bio);
2797                 wbc_account_io(wbc, page, page_size);
2798         }
2799
2800         *bio_ret = bio;
2801
2802         return ret;
2803 }
2804
2805 static void attach_extent_buffer_page(struct extent_buffer *eb,
2806                                       struct page *page)
2807 {
2808         if (!PagePrivate(page)) {
2809                 SetPagePrivate(page);
2810                 get_page(page);
2811                 set_page_private(page, (unsigned long)eb);
2812         } else {
2813                 WARN_ON(page->private != (unsigned long)eb);
2814         }
2815 }
2816
2817 void set_page_extent_mapped(struct page *page)
2818 {
2819         if (!PagePrivate(page)) {
2820                 SetPagePrivate(page);
2821                 get_page(page);
2822                 set_page_private(page, EXTENT_PAGE_PRIVATE);
2823         }
2824 }
2825
2826 static struct extent_map *
2827 __get_extent_map(struct inode *inode, struct page *page, size_t pg_offset,
2828                  u64 start, u64 len, get_extent_t *get_extent,
2829                  struct extent_map **em_cached)
2830 {
2831         struct extent_map *em;
2832
2833         if (em_cached && *em_cached) {
2834                 em = *em_cached;
2835                 if (extent_map_in_tree(em) && start >= em->start &&
2836                     start < extent_map_end(em)) {
2837                         refcount_inc(&em->refs);
2838                         return em;
2839                 }
2840
2841                 free_extent_map(em);
2842                 *em_cached = NULL;
2843         }
2844
2845         em = get_extent(BTRFS_I(inode), page, pg_offset, start, len, 0);
2846         if (em_cached && !IS_ERR_OR_NULL(em)) {
2847                 BUG_ON(*em_cached);
2848                 refcount_inc(&em->refs);
2849                 *em_cached = em;
2850         }
2851         return em;
2852 }
2853 /*
2854  * basic readpage implementation.  Locked extent state structs are inserted
2855  * into the tree that are removed when the IO is done (by the end_io
2856  * handlers)
2857  * XXX JDM: This needs looking at to ensure proper page locking
2858  * return 0 on success, otherwise return error
2859  */
2860 static int __do_readpage(struct extent_io_tree *tree,
2861                          struct page *page,
2862                          get_extent_t *get_extent,
2863                          struct extent_map **em_cached,
2864                          struct bio **bio, int mirror_num,
2865                          unsigned long *bio_flags, unsigned int read_flags,
2866                          u64 *prev_em_start)
2867 {
2868         struct inode *inode = page->mapping->host;
2869         u64 start = page_offset(page);
2870         const u64 end = start + PAGE_SIZE - 1;
2871         u64 cur = start;
2872         u64 extent_offset;
2873         u64 last_byte = i_size_read(inode);
2874         u64 block_start;
2875         u64 cur_end;
2876         struct extent_map *em;
2877         struct block_device *bdev;
2878         int ret = 0;
2879         int nr = 0;
2880         size_t pg_offset = 0;
2881         size_t iosize;
2882         size_t disk_io_size;
2883         size_t blocksize = inode->i_sb->s_blocksize;
2884         unsigned long this_bio_flag = 0;
2885
2886         set_page_extent_mapped(page);
2887
2888         if (!PageUptodate(page)) {
2889                 if (cleancache_get_page(page) == 0) {
2890                         BUG_ON(blocksize != PAGE_SIZE);
2891                         unlock_extent(tree, start, end);
2892                         goto out;
2893                 }
2894         }
2895
2896         if (page->index == last_byte >> PAGE_SHIFT) {
2897                 char *userpage;
2898                 size_t zero_offset = offset_in_page(last_byte);
2899
2900                 if (zero_offset) {
2901                         iosize = PAGE_SIZE - zero_offset;
2902                         userpage = kmap_atomic(page);
2903                         memset(userpage + zero_offset, 0, iosize);
2904                         flush_dcache_page(page);
2905                         kunmap_atomic(userpage);
2906                 }
2907         }
2908         while (cur <= end) {
2909                 bool force_bio_submit = false;
2910                 u64 offset;
2911
2912                 if (cur >= last_byte) {
2913                         char *userpage;
2914                         struct extent_state *cached = NULL;
2915
2916                         iosize = PAGE_SIZE - pg_offset;
2917                         userpage = kmap_atomic(page);
2918                         memset(userpage + pg_offset, 0, iosize);
2919                         flush_dcache_page(page);
2920                         kunmap_atomic(userpage);
2921                         set_extent_uptodate(tree, cur, cur + iosize - 1,
2922                                             &cached, GFP_NOFS);
2923                         unlock_extent_cached(tree, cur,
2924                                              cur + iosize - 1, &cached);
2925                         break;
2926                 }
2927                 em = __get_extent_map(inode, page, pg_offset, cur,
2928                                       end - cur + 1, get_extent, em_cached);
2929                 if (IS_ERR_OR_NULL(em)) {
2930                         SetPageError(page);
2931                         unlock_extent(tree, cur, end);
2932                         break;
2933                 }
2934                 extent_offset = cur - em->start;
2935                 BUG_ON(extent_map_end(em) <= cur);
2936                 BUG_ON(end < cur);
2937
2938                 if (test_bit(EXTENT_FLAG_COMPRESSED, &em->flags)) {
2939                         this_bio_flag |= EXTENT_BIO_COMPRESSED;
2940                         extent_set_compress_type(&this_bio_flag,
2941                                                  em->compress_type);
2942                 }
2943
2944                 iosize = min(extent_map_end(em) - cur, end - cur + 1);
2945                 cur_end = min(extent_map_end(em) - 1, end);
2946                 iosize = ALIGN(iosize, blocksize);
2947                 if (this_bio_flag & EXTENT_BIO_COMPRESSED) {
2948                         disk_io_size = em->block_len;
2949                         offset = em->block_start;
2950                 } else {
2951                         offset = em->block_start + extent_offset;
2952                         disk_io_size = iosize;
2953                 }
2954                 bdev = em->bdev;
2955                 block_start = em->block_start;
2956                 if (test_bit(EXTENT_FLAG_PREALLOC, &em->flags))
2957                         block_start = EXTENT_MAP_HOLE;
2958
2959                 /*
2960                  * If we have a file range that points to a compressed extent
2961                  * and it's followed by a consecutive file range that points to
2962                  * to the same compressed extent (possibly with a different
2963                  * offset and/or length, so it either points to the whole extent
2964                  * or only part of it), we must make sure we do not submit a
2965                  * single bio to populate the pages for the 2 ranges because
2966                  * this makes the compressed extent read zero out the pages
2967                  * belonging to the 2nd range. Imagine the following scenario:
2968                  *
2969                  *  File layout
2970                  *  [0 - 8K]                     [8K - 24K]
2971                  *    |                               |
2972                  *    |                               |
2973                  * points to extent X,         points to extent X,
2974                  * offset 4K, length of 8K     offset 0, length 16K
2975                  *
2976                  * [extent X, compressed length = 4K uncompressed length = 16K]
2977                  *
2978                  * If the bio to read the compressed extent covers both ranges,
2979                  * it will decompress extent X into the pages belonging to the
2980                  * first range and then it will stop, zeroing out the remaining
2981                  * pages that belong to the other range that points to extent X.
2982                  * So here we make sure we submit 2 bios, one for the first
2983                  * range and another one for the third range. Both will target
2984                  * the same physical extent from disk, but we can't currently
2985                  * make the compressed bio endio callback populate the pages
2986                  * for both ranges because each compressed bio is tightly
2987                  * coupled with a single extent map, and each range can have
2988                  * an extent map with a different offset value relative to the
2989                  * uncompressed data of our extent and different lengths. This
2990                  * is a corner case so we prioritize correctness over
2991                  * non-optimal behavior (submitting 2 bios for the same extent).
2992                  */
2993                 if (test_bit(EXTENT_FLAG_COMPRESSED, &em->flags) &&
2994                     prev_em_start && *prev_em_start != (u64)-1 &&
2995                     *prev_em_start != em->start)
2996                         force_bio_submit = true;
2997
2998                 if (prev_em_start)
2999                         *prev_em_start = em->start;
3000
3001                 free_extent_map(em);
3002                 em = NULL;
3003
3004                 /* we've found a hole, just zero and go on */
3005                 if (block_start == EXTENT_MAP_HOLE) {
3006                         char *userpage;
3007                         struct extent_state *cached = NULL;
3008
3009                         userpage = kmap_atomic(page);
3010                         memset(userpage + pg_offset, 0, iosize);
3011                         flush_dcache_page(page);
3012                         kunmap_atomic(userpage);
3013
3014                         set_extent_uptodate(tree, cur, cur + iosize - 1,
3015                                             &cached, GFP_NOFS);
3016                         unlock_extent_cached(tree, cur,
3017                                              cur + iosize - 1, &cached);
3018                         cur = cur + iosize;
3019                         pg_offset += iosize;
3020                         continue;
3021                 }
3022                 /* the get_extent function already copied into the page */
3023                 if (test_range_bit(tree, cur, cur_end,
3024                                    EXTENT_UPTODATE, 1, NULL)) {
3025                         check_page_uptodate(tree, page);
3026                         unlock_extent(tree, cur, cur + iosize - 1);
3027                         cur = cur + iosize;
3028                         pg_offset += iosize;
3029                         continue;
3030                 }
3031                 /* we have an inline extent but it didn't get marked up
3032                  * to date.  Error out
3033                  */
3034                 if (block_start == EXTENT_MAP_INLINE) {
3035                         SetPageError(page);
3036                         unlock_extent(tree, cur, cur + iosize - 1);
3037                         cur = cur + iosize;
3038                         pg_offset += iosize;
3039                         continue;
3040                 }
3041
3042                 ret = submit_extent_page(REQ_OP_READ | read_flags, tree, NULL,
3043                                          page, offset, disk_io_size,
3044                                          pg_offset, bdev, bio,
3045                                          end_bio_extent_readpage, mirror_num,
3046                                          *bio_flags,
3047                                          this_bio_flag,
3048                                          force_bio_submit);
3049                 if (!ret) {
3050                         nr++;
3051                         *bio_flags = this_bio_flag;
3052                 } else {
3053                         SetPageError(page);
3054                         unlock_extent(tree, cur, cur + iosize - 1);
3055                         goto out;
3056                 }
3057                 cur = cur + iosize;
3058                 pg_offset += iosize;
3059         }
3060 out:
3061         if (!nr) {
3062                 if (!PageError(page))
3063                         SetPageUptodate(page);
3064                 unlock_page(page);
3065         }
3066         return ret;
3067 }
3068
3069 static inline void __do_contiguous_readpages(struct extent_io_tree *tree,
3070                                              struct page *pages[], int nr_pages,
3071                                              u64 start, u64 end,
3072                                              struct extent_map **em_cached,
3073                                              struct bio **bio,
3074                                              unsigned long *bio_flags,
3075                                              u64 *prev_em_start)
3076 {
3077         struct inode *inode;
3078         struct btrfs_ordered_extent *ordered;
3079         int index;
3080
3081         inode = pages[0]->mapping->host;
3082         while (1) {
3083                 lock_extent(tree, start, end);
3084                 ordered = btrfs_lookup_ordered_range(BTRFS_I(inode), start,
3085                                                      end - start + 1);
3086                 if (!ordered)
3087                         break;
3088                 unlock_extent(tree, start, end);
3089                 btrfs_start_ordered_extent(inode, ordered, 1);
3090                 btrfs_put_ordered_extent(ordered);
3091         }
3092
3093         for (index = 0; index < nr_pages; index++) {
3094                 __do_readpage(tree, pages[index], btrfs_get_extent, em_cached,
3095                                 bio, 0, bio_flags, REQ_RAHEAD, prev_em_start);
3096                 put_page(pages[index]);
3097         }
3098 }
3099
3100 static void __extent_readpages(struct extent_io_tree *tree,
3101                                struct page *pages[],
3102                                int nr_pages,
3103                                struct extent_map **em_cached,
3104                                struct bio **bio, unsigned long *bio_flags,
3105                                u64 *prev_em_start)
3106 {
3107         u64 start = 0;
3108         u64 end = 0;
3109         u64 page_start;
3110         int index;
3111         int first_index = 0;
3112
3113         for (index = 0; index < nr_pages; index++) {
3114                 page_start = page_offset(pages[index]);
3115                 if (!end) {
3116                         start = page_start;
3117                         end = start + PAGE_SIZE - 1;
3118                         first_index = index;
3119                 } else if (end + 1 == page_start) {
3120                         end += PAGE_SIZE;
3121                 } else {
3122                         __do_contiguous_readpages(tree, &pages[first_index],
3123                                                   index - first_index, start,
3124                                                   end, em_cached,