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->orig_start)
2996                         force_bio_submit = true;
2997
2998                 if (prev_em_start)
2999                         *prev_em_start = em->orig_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,
3125                                                   bio, bio_flags,
3126                                                   prev_em_start);
3127                         start = page_start;
3128                         end = start + PAGE_SIZE - 1;
3129                         first_index = index;
3130                 }
3131         }
3132
3133         if (end)
3134                 __do_contiguous_readpages(tree, &pages[first_index],
3135                                           index - first_index, start,
3136                                           end, em_cached, bio,
3137                                           bio_flags, prev_em_start);
3138 }
3139
3140 static int __extent_read_full_page(struct extent_io_tree *tree,
3141                                    struct page *page,
3142                                    get_extent_t *get_extent,
3143                                    struct bio **bio, int mirror_num,
3144                                    unsigned long *bio_flags,
3145                                    unsigned int read_flags)
3146 {
3147         struct inode *inode = page->mapping->host;
3148         struct btrfs_ordered_extent *ordered;
3149         u64 start = page_offset(page);
3150         u64 end = start + PAGE_SIZE - 1;
3151         int ret;
3152
3153         while (1) {
3154                 lock_extent(tree, start, end);
3155                 ordered = btrfs_lookup_ordered_range(BTRFS_I(inode), start,
3156                                                 PAGE_SIZE);
3157                 if (!ordered)
3158                         break;
3159                 unlock_extent(tree, start, end);
3160                 btrfs_start_ordered_extent(inode, ordered, 1);
3161                 btrfs_put_ordered_extent(ordered);
3162         }
3163
3164         ret = __do_readpage(tree, page, get_extent, NULL, bio, mirror_num,
3165                             bio_flags, read_flags, NULL);
3166         return ret;
3167 }
3168
3169 int extent_read_full_page(struct extent_io_tree *tree, struct page *page,
3170                             get_extent_t *get_extent, int mirror_num)
3171 {
3172         struct bio *bio = NULL;
3173         unsigned long bio_flags = 0;
3174         int ret;
3175
3176         ret = __extent_read_full_page(tree, page, get_extent, &bio, mirror_num,
3177                                       &bio_flags, 0);
3178         if (bio)
3179                 ret = submit_one_bio(bio, mirror_num, bio_flags);
3180         return ret;
3181 }
3182
3183 static void update_nr_written(struct writeback_control *wbc,
3184                               unsigned long nr_written)
3185 {
3186         wbc->nr_to_write -= nr_written;
3187 }
3188
3189 /*
3190  * helper for __extent_writepage, doing all of the delayed allocation setup.
3191  *
3192  * This returns 1 if btrfs_run_delalloc_range function did all the work required
3193  * to write the page (copy into inline extent).  In this case the IO has
3194  * been started and the page is already unlocked.
3195  *
3196  * This returns 0 if all went well (page still locked)
3197  * This returns < 0 if there were errors (page still locked)
3198  */
3199 static noinline_for_stack int writepage_delalloc(struct inode *inode,
3200                 struct page *page, struct writeback_control *wbc,
3201                 u64 delalloc_start, unsigned long *nr_written)
3202 {
3203         struct extent_io_tree *tree = &BTRFS_I(inode)->io_tree;
3204         u64 page_end = delalloc_start + PAGE_SIZE - 1;
3205         bool found;
3206         u64 delalloc_to_write = 0;
3207         u64 delalloc_end = 0;
3208         int ret;
3209         int page_started = 0;
3210
3211
3212         while (delalloc_end < page_end) {
3213                 found = find_lock_delalloc_range(inode, tree,
3214                                                page,
3215                                                &delalloc_start,
3216                                                &delalloc_end);
3217                 if (!found) {
3218                         delalloc_start = delalloc_end + 1;
3219                         continue;
3220                 }
3221                 ret = btrfs_run_delalloc_range(inode, page, delalloc_start,
3222                                 delalloc_end, &page_started, nr_written, wbc);
3223                 /* File system has been set read-only */
3224                 if (ret) {
3225                         SetPageError(page);
3226                         /*
3227                          * btrfs_run_delalloc_range should return < 0 for error
3228                          * but just in case, we use > 0 here meaning the IO is
3229                          * started, so we don't want to return > 0 unless
3230                          * things are going well.
3231                          */
3232                         ret = ret < 0 ? ret : -EIO;
3233                         goto done;
3234                 }
3235                 /*
3236                  * delalloc_end is already one less than the total length, so
3237                  * we don't subtract one from PAGE_SIZE
3238                  */
3239                 delalloc_to_write += (delalloc_end - delalloc_start +
3240                                       PAGE_SIZE) >> PAGE_SHIFT;
3241                 delalloc_start = delalloc_end + 1;
3242         }
3243         if (wbc->nr_to_write < delalloc_to_write) {
3244                 int thresh = 8192;
3245
3246                 if (delalloc_to_write < thresh * 2)
3247                         thresh = delalloc_to_write;
3248                 wbc->nr_to_write = min_t(u64, delalloc_to_write,
3249                                          thresh);
3250         }
3251
3252         /* did the fill delalloc function already unlock and start
3253          * the IO?
3254          */
3255         if (page_started) {
3256                 /*
3257                  * we've unlocked the page, so we can't update
3258                  * the mapping's writeback index, just update
3259                  * nr_to_write.
3260                  */
3261                 wbc->nr_to_write -= *nr_written;
3262                 return 1;
3263         }
3264
3265         ret = 0;
3266
3267 done:
3268         return ret;
3269 }
3270
3271 /*
3272  * helper for __extent_writepage.  This calls the writepage start hooks,
3273  * and does the loop to map the page into extents and bios.
3274  *
3275  * We return 1 if the IO is started and the page is unlocked,
3276  * 0 if all went well (page still locked)
3277  * < 0 if there were errors (page still locked)
3278  */
3279 static noinline_for_stack int __extent_writepage_io(struct inode *inode,
3280                                  struct page *page,
3281                                  struct writeback_control *wbc,
3282                                  struct extent_page_data *epd,
3283                                  loff_t i_size,
3284                                  unsigned long nr_written,
3285                                  unsigned int write_flags, int *nr_ret)
3286 {
3287         struct extent_io_tree *tree = epd->tree;
3288         u64 start = page_offset(page);
3289         u64 page_end = start + PAGE_SIZE - 1;
3290         u64 end;
3291         u64 cur = start;
3292         u64 extent_offset;
3293         u64 block_start;
3294         u64 iosize;
3295         struct extent_map *em;
3296         struct block_device *bdev;
3297         size_t pg_offset = 0;
3298         size_t blocksize;
3299         int ret = 0;
3300         int nr = 0;
3301         bool compressed;
3302
3303         ret = btrfs_writepage_cow_fixup(page, start, page_end);
3304         if (ret) {
3305                 /* Fixup worker will requeue */
3306                 if (ret == -EBUSY)
3307                         wbc->pages_skipped++;
3308                 else
3309                         redirty_page_for_writepage(wbc, page);
3310
3311                 update_nr_written(wbc, nr_written);
3312                 unlock_page(page);
3313                 return 1;
3314         }
3315
3316         /*
3317          * we don't want to touch the inode after unlocking the page,
3318          * so we update the mapping writeback index now
3319          */
3320         update_nr_written(wbc, nr_written + 1);
3321
3322         end = page_end;
3323         if (i_size <= start) {
3324                 btrfs_writepage_endio_finish_ordered(page, start, page_end, 1);
3325                 goto done;
3326         }
3327
3328         blocksize = inode->i_sb->s_blocksize;
3329
3330         while (cur <= end) {
3331                 u64 em_end;
3332                 u64 offset;
3333
3334                 if (cur >= i_size) {
3335                         btrfs_writepage_endio_finish_ordered(page, cur,
3336                                                              page_end, 1);
3337                         break;
3338                 }
3339                 em = btrfs_get_extent(BTRFS_I(inode), page, pg_offset, cur,
3340                                      end - cur + 1, 1);
3341                 if (IS_ERR_OR_NULL(em)) {
3342                         SetPageError(page);
3343                         ret = PTR_ERR_OR_ZERO(em);
3344                         break;
3345                 }
3346
3347                 extent_offset = cur - em->start;
3348                 em_end = extent_map_end(em);
3349                 BUG_ON(em_end <= cur);
3350                 BUG_ON(end < cur);
3351                 iosize = min(em_end - cur, end - cur + 1);
3352                 iosize = ALIGN(iosize, blocksize);
3353                 offset = em->block_start + extent_offset;
3354                 bdev = em->bdev;
3355                 block_start = em->block_start;
3356                 compressed = test_bit(EXTENT_FLAG_COMPRESSED, &em->flags);
3357                 free_extent_map(em);
3358                 em = NULL;
3359
3360                 /*
3361                  * compressed and inline extents are written through other
3362                  * paths in the FS
3363                  */
3364                 if (compressed || block_start == EXTENT_MAP_HOLE ||
3365                     block_start == EXTENT_MAP_INLINE) {
3366                         /*
3367                          * end_io notification does not happen here for
3368                          * compressed extents
3369                          */
3370                         if (!compressed)
3371                                 btrfs_writepage_endio_finish_ordered(page, cur,
3372                                                             cur + iosize - 1,
3373                                                             1);
3374                         else if (compressed) {
3375                                 /* we don't want to end_page_writeback on
3376                                  * a compressed extent.  this happens
3377                                  * elsewhere
3378                                  */
3379                                 nr++;
3380                         }
3381
3382                         cur += iosize;
3383                         pg_offset += iosize;
3384                         continue;
3385                 }
3386
3387                 btrfs_set_range_writeback(tree, cur, cur + iosize - 1);
3388                 if (!PageWriteback(page)) {
3389                         btrfs_err(BTRFS_I(inode)->root->fs_info,
3390                                    "page %lu not writeback, cur %llu end %llu",
3391                                page->index, cur, end);
3392                 }
3393
3394                 ret = submit_extent_page(REQ_OP_WRITE | write_flags, tree, wbc,
3395                                          page, offset, iosize, pg_offset,
3396                                          bdev, &epd->bio,
3397                                          end_bio_extent_writepage,
3398                                          0, 0, 0, false);
3399                 if (ret) {
3400                         SetPageError(page);
3401                         if (PageWriteback(page))
3402                                 end_page_writeback(page);
3403                 }
3404
3405                 cur = cur + iosize;
3406                 pg_offset += iosize;
3407                 nr++;
3408         }
3409 done:
3410         *nr_ret = nr;
3411         return ret;
3412 }
3413
3414 /*
3415  * the writepage semantics are similar to regular writepage.  extent
3416  * records are inserted to lock ranges in the tree, and as dirty areas
3417  * are found, they are marked writeback.  Then the lock bits are removed
3418  * and the end_io handler clears the writeback ranges
3419  */
3420 static int __extent_writepage(struct page *page, struct writeback_control *wbc,
3421                               struct extent_page_data *epd)
3422 {
3423         struct inode *inode = page->mapping->host;
3424         u64 start = page_offset(page);
3425         u64 page_end = start + PAGE_SIZE - 1;
3426         int ret;
3427         int nr = 0;
3428         size_t pg_offset = 0;
3429         loff_t i_size = i_size_read(inode);
3430         unsigned long end_index = i_size >> PAGE_SHIFT;
3431         unsigned int write_flags = 0;
3432         unsigned long nr_written = 0;
3433
3434         write_flags = wbc_to_write_flags(wbc);
3435
3436         trace___extent_writepage(page, inode, wbc);
3437
3438         WARN_ON(!PageLocked(page));
3439
3440         ClearPageError(page);
3441
3442         pg_offset = offset_in_page(i_size);
3443         if (page->index > end_index ||
3444            (page->index == end_index && !pg_offset)) {
3445                 page->mapping->a_ops->invalidatepage(page, 0, PAGE_SIZE);
3446                 unlock_page(page);
3447                 return 0;
3448         }
3449
3450         if (page->index == end_index) {
3451                 char *userpage;
3452
3453                 userpage = kmap_atomic(page);
3454                 memset(userpage + pg_offset, 0,
3455                        PAGE_SIZE - pg_offset);
3456                 kunmap_atomic(userpage);
3457                 flush_dcache_page(page);
3458         }
3459
3460         pg_offset = 0;
3461
3462         set_page_extent_mapped(page);
3463
3464         if (!epd->extent_locked) {
3465                 ret = writepage_delalloc(inode, page, wbc, start, &nr_written);
3466                 if (ret == 1)
3467                         goto done_unlocked;
3468                 if (ret)
3469                         goto done;
3470         }
3471
3472         ret = __extent_writepage_io(inode, page, wbc, epd,
3473                                     i_size, nr_written, write_flags, &nr);
3474         if (ret == 1)
3475                 goto done_unlocked;
3476
3477 done:
3478         if (nr == 0) {
3479                 /* make sure the mapping tag for page dirty gets cleared */
3480                 set_page_writeback(page);
3481                 end_page_writeback(page);
3482         }
3483         if (PageError(page)) {
3484                 ret = ret < 0 ? ret : -EIO;
3485                 end_extent_writepage(page, ret, start, page_end);
3486         }
3487         unlock_page(page);
3488         return ret;
3489
3490 done_unlocked:
3491         return 0;
3492 }
3493
3494 void wait_on_extent_buffer_writeback(struct extent_buffer *eb)
3495 {
3496         wait_on_bit_io(&eb->bflags, EXTENT_BUFFER_WRITEBACK,
3497                        TASK_UNINTERRUPTIBLE);
3498 }
3499
3500 static noinline_for_stack int
3501 lock_extent_buffer_for_io(struct extent_buffer *eb,
3502                           struct btrfs_fs_info *fs_info,
3503                           struct extent_page_data *epd)
3504 {
3505         int i, num_pages;
3506         int flush = 0;
3507         int ret = 0;
3508
3509         if (!btrfs_try_tree_write_lock(eb)) {
3510                 flush = 1;
3511                 flush_write_bio(epd);
3512                 btrfs_tree_lock(eb);
3513         }
3514
3515         if (test_bit(EXTENT_BUFFER_WRITEBACK, &eb->bflags)) {
3516                 btrfs_tree_unlock(eb);
3517                 if (!epd->sync_io)
3518                         return 0;
3519                 if (!flush) {
3520                         flush_write_bio(epd);
3521                         flush = 1;
3522                 }
3523                 while (1) {
3524                         wait_on_extent_buffer_writeback(eb);
3525                         btrfs_tree_lock(eb);
3526                         if (!test_bit(EXTENT_BUFFER_WRITEBACK, &eb->bflags))
3527                                 break;
3528                         btrfs_tree_unlock(eb);
3529                 }
3530         }
3531
3532         /*
3533          * We need to do this to prevent races in people who check if the eb is
3534          * under IO since we can end up having no IO bits set for a short period
3535          * of time.
3536          */
3537         spin_lock(&eb->refs_lock);
3538         if (test_and_clear_bit(EXTENT_BUFFER_DIRTY, &eb->bflags)) {
3539                 set_bit(EXTENT_BUFFER_WRITEBACK, &eb->bflags);
3540                 spin_unlock(&eb->refs_lock);
3541                 btrfs_set_header_flag(eb, BTRFS_HEADER_FLAG_WRITTEN);
3542                 percpu_counter_add_batch(&fs_info->dirty_metadata_bytes,
3543                                          -eb->len,
3544                                          fs_info->dirty_metadata_batch);
3545                 ret = 1;
3546         } else {
3547                 spin_unlock(&eb->refs_lock);
3548         }
3549
3550         btrfs_tree_unlock(eb);
3551
3552         if (!ret)
3553                 return ret;
3554
3555         num_pages = num_extent_pages(eb);
3556         for (i = 0; i < num_pages; i++) {
3557                 struct page *p = eb->pages[i];
3558
3559                 if (!trylock_page(p)) {
3560                         if (!flush) {
3561                                 flush_write_bio(epd);
3562                                 flush = 1;
3563                         }
3564                         lock_page(p);
3565                 }
3566         }
3567
3568         return ret;
3569 }
3570
3571 static void end_extent_buffer_writeback(struct extent_buffer *eb)
3572 {
3573         clear_bit(EXTENT_BUFFER_WRITEBACK, &eb->bflags);
3574         smp_mb__after_atomic();
3575         wake_up_bit(&eb->bflags, EXTENT_BUFFER_WRITEBACK);
3576 }
3577
3578 static void set_btree_ioerr(struct page *page)
3579 {
3580         struct extent_buffer *eb = (struct extent_buffer *)page->private;
3581
3582         SetPageError(page);
3583         if (test_and_set_bit(EXTENT_BUFFER_WRITE_ERR, &eb->bflags))
3584                 return;
3585
3586         /*
3587          * If writeback for a btree extent that doesn't belong to a log tree
3588          * failed, increment the counter transaction->eb_write_errors.
3589          * We do this because while the transaction is running and before it's
3590          * committing (when we call filemap_fdata[write|wait]_range against
3591          * the btree inode), we might have
3592          * btree_inode->i_mapping->a_ops->writepages() called by the VM - if it
3593          * returns an error or an error happens during writeback, when we're
3594          * committing the transaction we wouldn't know about it, since the pages
3595          * can be no longer dirty nor marked anymore for writeback (if a
3596          * subsequent modification to the extent buffer didn't happen before the
3597          * transaction commit), which makes filemap_fdata[write|wait]_range not
3598          * able to find the pages tagged with SetPageError at transaction
3599          * commit time. So if this happens we must abort the transaction,
3600          * otherwise we commit a super block with btree roots that point to
3601          * btree nodes/leafs whose content on disk is invalid - either garbage
3602          * or the content of some node/leaf from a past generation that got
3603          * cowed or deleted and is no longer valid.
3604          *
3605          * Note: setting AS_EIO/AS_ENOSPC in the btree inode's i_mapping would
3606          * not be enough - we need to distinguish between log tree extents vs
3607          * non-log tree extents, and the next filemap_fdatawait_range() call
3608          * will catch and clear such errors in the mapping - and that call might
3609          * be from a log sync and not from a transaction commit. Also, checking
3610          * for the eb flag EXTENT_BUFFER_WRITE_ERR at transaction commit time is
3611          * not done and would not be reliable - the eb might have been released
3612          * from memory and reading it back again means that flag would not be
3613          * set (since it's a runtime flag, not persisted on disk).
3614          *
3615          * Using the flags below in the btree inode also makes us achieve the
3616          * goal of AS_EIO/AS_ENOSPC when writepages() returns success, started
3617          * writeback for all dirty pages and before filemap_fdatawait_range()
3618          * is called, the writeback for all dirty pages had already finished
3619          * with errors - because we were not using AS_EIO/AS_ENOSPC,
3620          * filemap_fdatawait_range() would return success, as it could not know
3621          * that writeback errors happened (the pages were no longer tagged for
3622          * writeback).
3623          */
3624         switch (eb->log_index) {
3625         case -1:
3626                 set_bit(BTRFS_FS_BTREE_ERR, &eb->fs_info->flags);
3627                 break;
3628         case 0:
3629                 set_bit(BTRFS_FS_LOG1_ERR, &eb->fs_info->flags);
3630                 break;
3631         case 1:
3632                 set_bit(BTRFS_FS_LOG2_ERR, &eb->fs_info->flags);
3633                 break;
3634         default:
3635                 BUG(); /* unexpected, logic error */
3636         }
3637 }
3638
3639 static void end_bio_extent_buffer_writepage(struct bio *bio)
3640 {
3641         struct bio_vec *bvec;
3642         struct extent_buffer *eb;
3643         int i, done;
3644
3645         ASSERT(!bio_flagged(bio, BIO_CLONED));
3646         bio_for_each_segment_all(bvec, bio, i) {
3647                 struct page *page = bvec->bv_page;
3648
3649                 eb = (struct extent_buffer *)page->private;
3650                 BUG_ON(!eb);
3651                 done = atomic_dec_and_test(&eb->io_pages);
3652
3653                 if (bio->bi_status ||
3654                     test_bit(EXTENT_BUFFER_WRITE_ERR, &eb->bflags)) {
3655                         ClearPageUptodate(page);
3656                         set_btree_ioerr(page);
3657                 }
3658
3659                 end_page_writeback(page);
3660
3661                 if (!done)
3662                         continue;
3663
3664                 end_extent_buffer_writeback(eb);
3665         }
3666
3667         bio_put(bio);
3668 }
3669
3670 static noinline_for_stack int write_one_eb(struct extent_buffer *eb,
3671                         struct btrfs_fs_info *fs_info,
3672                         struct writeback_control *wbc,
3673                         struct extent_page_data *epd)
3674 {
3675         struct block_device *bdev = fs_info->fs_devices->latest_bdev;
3676         struct extent_io_tree *tree = &BTRFS_I(fs_info->btree_inode)->io_tree;
3677         u64 offset = eb->start;
3678         u32 nritems;
3679         int i, num_pages;
3680         unsigned long start, end;
3681         unsigned int write_flags = wbc_to_write_flags(wbc) | REQ_META;
3682         int ret = 0;
3683
3684         clear_bit(EXTENT_BUFFER_WRITE_ERR, &eb->bflags);
3685         num_pages = num_extent_pages(eb);
3686         atomic_set(&eb->io_pages, num_pages);
3687
3688         /* set btree blocks beyond nritems with 0 to avoid stale content. */
3689         nritems = btrfs_header_nritems(eb);
3690         if (btrfs_header_level(eb) > 0) {
3691                 end = btrfs_node_key_ptr_offset(nritems);
3692
3693                 memzero_extent_buffer(eb, end, eb->len - end);
3694         } else {
3695                 /*
3696                  * leaf:
3697                  * header 0 1 2 .. N ... data_N .. data_2 data_1 data_0
3698                  */
3699                 start = btrfs_item_nr_offset(nritems);
3700                 end = BTRFS_LEAF_DATA_OFFSET + leaf_data_end(fs_info, eb);
3701                 memzero_extent_buffer(eb, start, end - start);
3702         }
3703
3704         for (i = 0; i < num_pages; i++) {
3705                 struct page *p = eb->pages[i];
3706
3707                 clear_page_dirty_for_io(p);
3708                 set_page_writeback(p);
3709                 ret = submit_extent_page(REQ_OP_WRITE | write_flags, tree, wbc,
3710                                          p, offset, PAGE_SIZE, 0, bdev,
3711                                          &epd->bio,
3712                                          end_bio_extent_buffer_writepage,
3713                                          0, 0, 0, false);
3714                 if (ret) {
3715                         set_btree_ioerr(p);
3716                         if (PageWriteback(p))
3717                                 end_page_writeback(p);
3718                         if (atomic_sub_and_test(num_pages - i, &eb->io_pages))
3719                                 end_extent_buffer_writeback(eb);
3720                         ret = -EIO;
3721                         break;
3722                 }
3723                 offset += PAGE_SIZE;
3724                 update_nr_written(wbc, 1);
3725                 unlock_page(p);
3726         }
3727
3728         if (unlikely(ret)) {
3729                 for (; i < num_pages; i++) {
3730                         struct page *p = eb->pages[i];
3731                         clear_page_dirty_for_io(p);
3732                         unlock_page(p);
3733                 }
3734         }
3735
3736         return ret;
3737 }
3738
3739 int btree_write_cache_pages(struct address_space *mapping,
3740                                    struct writeback_control *wbc)
3741 {
3742         struct extent_io_tree *tree = &BTRFS_I(mapping->host)->io_tree;
3743         struct btrfs_fs_info *fs_info = BTRFS_I(mapping->host)->root->fs_info;
3744         struct extent_buffer *eb, *prev_eb = NULL;
3745         struct extent_page_data epd = {
3746                 .bio = NULL,
3747                 .tree = tree,
3748                 .extent_locked = 0,
3749                 .sync_io = wbc->sync_mode == WB_SYNC_ALL,
3750         };
3751         int ret = 0;
3752         int done = 0;
3753         int nr_to_write_done = 0;
3754         struct pagevec pvec;
3755         int nr_pages;
3756         pgoff_t index;
3757         pgoff_t end;            /* Inclusive */
3758         int scanned = 0;
3759         xa_mark_t tag;
3760
3761         pagevec_init(&pvec);
3762         if (wbc->range_cyclic) {
3763                 index = mapping->writeback_index; /* Start from prev offset */
3764                 end = -1;
3765         } else {
3766                 index = wbc->range_start >> PAGE_SHIFT;
3767                 end = wbc->range_end >> PAGE_SHIFT;
3768                 scanned = 1;
3769         }
3770         if (wbc->sync_mode == WB_SYNC_ALL)
3771                 tag = PAGECACHE_TAG_TOWRITE;
3772         else
3773                 tag = PAGECACHE_TAG_DIRTY;
3774 retry:
3775         if (wbc->sync_mode == WB_SYNC_ALL)
3776                 tag_pages_for_writeback(mapping, index, end);
3777         while (!done && !nr_to_write_done && (index <= end) &&
3778                (nr_pages = pagevec_lookup_range_tag(&pvec, mapping, &index, end,
3779                         tag))) {
3780                 unsigned i;
3781
3782                 scanned = 1;
3783                 for (i = 0; i < nr_pages; i++) {
3784                         struct page *page = pvec.pages[i];
3785
3786                         if (!PagePrivate(page))
3787                                 continue;
3788
3789                         spin_lock(&mapping->private_lock);
3790                         if (!PagePrivate(page)) {
3791                                 spin_unlock(&mapping->private_lock);
3792                                 continue;
3793                         }
3794
3795                         eb = (struct extent_buffer *)page->private;
3796
3797                         /*
3798                          * Shouldn't happen and normally this would be a BUG_ON
3799                          * but no sense in crashing the users box for something
3800                          * we can survive anyway.
3801                          */
3802                         if (WARN_ON(!eb)) {
3803                                 spin_unlock(&mapping->private_lock);
3804                                 continue;
3805                         }
3806
3807                         if (eb == prev_eb) {
3808                                 spin_unlock(&mapping->private_lock);
3809                                 continue;
3810                         }
3811
3812                         ret = atomic_inc_not_zero(&eb->refs);
3813                         spin_unlock(&mapping->private_lock);
3814                         if (!ret)
3815                                 continue;
3816
3817                         prev_eb = eb;
3818                         ret = lock_extent_buffer_for_io(eb, fs_info, &epd);
3819                         if (!ret) {
3820                                 free_extent_buffer(eb);
3821                                 continue;
3822                         }
3823
3824                         ret = write_one_eb(eb, fs_info, wbc, &epd);
3825                         if (ret) {
3826                                 done = 1;
3827                                 free_extent_buffer(eb);
3828                                 break;
3829                         }
3830                         free_extent_buffer(eb);
3831
3832                         /*
3833                          * the filesystem may choose to bump up nr_to_write.
3834                          * We have to make sure to honor the new nr_to_write
3835                          * at any time
3836                          */
3837                         nr_to_write_done = wbc->nr_to_write <= 0;
3838                 }
3839                 pagevec_release(&pvec);
3840                 cond_resched();
3841         }
3842         if (!scanned && !done) {
3843                 /*
3844                  * We hit the last page and there is more work to be done: wrap
3845                  * back to the start of the file
3846                  */
3847                 scanned = 1;
3848                 index = 0;
3849                 goto retry;
3850         }
3851         flush_write_bio(&epd);
3852         return ret;
3853 }
3854
3855 /**
3856  * write_cache_pages - walk the list of dirty pages of the given address space and write all of them.
3857  * @mapping: address space structure to write
3858  * @wbc: subtract the number of written pages from *@wbc->nr_to_write
3859  * @data: data passed to __extent_writepage function
3860  *
3861  * If a page is already under I/O, write_cache_pages() skips it, even
3862  * if it's dirty.  This is desirable behaviour for memory-cleaning writeback,
3863  * but it is INCORRECT for data-integrity system calls such as fsync().  fsync()
3864  * and msync() need to guarantee that all the data which was dirty at the time
3865  * the call was made get new I/O started against them.  If wbc->sync_mode is
3866  * WB_SYNC_ALL then we were called for data integrity and we must wait for
3867  * existing IO to complete.
3868  */
3869 static int extent_write_cache_pages(struct address_space *mapping,
3870                              struct writeback_control *wbc,
3871                              struct extent_page_data *epd)
3872 {
3873         struct inode *inode = mapping->host;
3874         int ret = 0;
3875         int done = 0;
3876         int nr_to_write_done = 0;
3877         struct pagevec pvec;
3878         int nr_pages;
3879         pgoff_t index;
3880         pgoff_t end;            /* Inclusive */
3881         pgoff_t done_index;
3882         int range_whole = 0;
3883         int scanned = 0;
3884         xa_mark_t tag;
3885
3886         /*
3887          * We have to hold onto the inode so that ordered extents can do their
3888          * work when the IO finishes.  The alternative to this is failing to add
3889          * an ordered extent if the igrab() fails there and that is a huge pain
3890          * to deal with, so instead just hold onto the inode throughout the
3891          * writepages operation.  If it fails here we are freeing up the inode
3892          * anyway and we'd rather not waste our time writing out stuff that is
3893          * going to be truncated anyway.
3894          */
3895         if (!igrab(inode))
3896                 return 0;
3897
3898         pagevec_init(&pvec);
3899         if (wbc->range_cyclic) {
3900                 index = mapping->writeback_index; /* Start from prev offset */
3901                 end = -1;
3902         } else {
3903                 index = wbc->range_start >> PAGE_SHIFT;
3904                 end = wbc->range_end >> PAGE_SHIFT;
3905                 if (wbc->range_start == 0 && wbc->range_end == LLONG_MAX)
3906                         range_whole = 1;
3907                 scanned = 1;
3908         }
3909
3910         /*
3911          * We do the tagged writepage as long as the snapshot flush bit is set
3912          * and we are the first one who do the filemap_flush() on this inode.
3913          *
3914          * The nr_to_write == LONG_MAX is needed to make sure other flushers do
3915          * not race in and drop the bit.
3916          */
3917         if (range_whole && wbc->nr_to_write == LONG_MAX &&
3918             test_and_clear_bit(BTRFS_INODE_SNAPSHOT_FLUSH,
3919                                &BTRFS_I(inode)->runtime_flags))
3920                 wbc->tagged_writepages = 1;
3921
3922         if (wbc->sync_mode == WB_SYNC_ALL || wbc->tagged_writepages)
3923                 tag = PAGECACHE_TAG_TOWRITE;
3924         else
3925                 tag = PAGECACHE_TAG_DIRTY;
3926 retry:
3927         if (wbc->sync_mode == WB_SYNC_ALL || wbc->tagged_writepages)
3928                 tag_pages_for_writeback(mapping, index, end);
3929         done_index = index;
3930         while (!done && !nr_to_write_done && (index <= end) &&
3931                         (nr_pages = pagevec_lookup_range_tag(&pvec, mapping,
3932                                                 &index, end, tag))) {
3933                 unsigned i;
3934
3935                 scanned = 1;
3936                 for (i = 0; i < nr_pages; i++) {
3937                         struct page *page = pvec.pages[i];
3938
3939                         done_index = page->index;
3940                         /*
3941                          * At this point we hold neither the i_pages lock nor
3942                          * the page lock: the page may be truncated or
3943                          * invalidated (changing page->mapping to NULL),
3944                          * or even swizzled back from swapper_space to
3945                          * tmpfs file mapping
3946                          */
3947                         if (!trylock_page(page)) {
3948                                 flush_write_bio(epd);
3949                                 lock_page(page);
3950                         }
3951
3952                         if (unlikely(page->mapping != mapping)) {
3953                                 unlock_page(page);
3954                                 continue;
3955                         }
3956
3957                         if (wbc->sync_mode != WB_SYNC_NONE) {
3958                                 if (PageWriteback(page))
3959                                         flush_write_bio(epd);
3960                                 wait_on_page_writeback(page);
3961                         }
3962
3963                         if (PageWriteback(page) ||
3964                             !clear_page_dirty_for_io(page)) {
3965                                 unlock_page(page);
3966                                 continue;
3967                         }
3968
3969                         ret = __extent_writepage(page, wbc, epd);
3970
3971                         if (unlikely(ret == AOP_WRITEPAGE_ACTIVATE)) {
3972                                 unlock_page(page);
3973                                 ret = 0;
3974                         }
3975                         if (ret < 0) {
3976                                 /*
3977                                  * done_index is set past this page,
3978                                  * so media errors will not choke
3979                                  * background writeout for the entire
3980                                  * file. This has consequences for
3981                                  * range_cyclic semantics (ie. it may
3982                                  * not be suitable for data integrity
3983                                  * writeout).
3984                                  */
3985                                 done_index = page->index + 1;
3986                                 done = 1;
3987                                 break;
3988                         }
3989
3990                         /*
3991                          * the filesystem may choose to bump up nr_to_write.
3992                          * We have to make sure to honor the new nr_to_write
3993                          * at any time
3994                          */
3995                         nr_to_write_done = wbc->nr_to_write <= 0;
3996                 }
3997                 pagevec_release(&pvec);
3998                 cond_resched();
3999         }
4000         if (!scanned && !done) {
4001                 /*
4002                  * We hit the last page and there is more work to be done: wrap
4003                  * back to the start of the file
4004                  */
4005                 scanned = 1;
4006                 index = 0;
4007                 goto retry;
4008         }
4009
4010         if (wbc->range_cyclic || (wbc->nr_to_write > 0 && range_whole))
4011                 mapping->writeback_index = done_index;
4012
4013         btrfs_add_delayed_iput(inode);
4014         return ret;
4015 }
4016
4017 int extent_write_full_page(struct page *page, struct writeback_control *wbc)
4018 {
4019         int ret;
4020         struct extent_page_data epd = {
4021                 .bio = NULL,
4022                 .tree = &BTRFS_I(page->mapping->host)->io_tree,
4023                 .extent_locked = 0,
4024                 .sync_io = wbc->sync_mode == WB_SYNC_ALL,
4025         };
4026
4027         ret = __extent_writepage(page, wbc, &epd);
4028
4029         flush_write_bio(&epd);
4030         return ret;
4031 }
4032
4033 int extent_write_locked_range(struct inode *inode, u64 start, u64 end,
4034                               int mode)
4035 {
4036         int ret = 0;
4037         struct address_space *mapping = inode->i_mapping;
4038         struct extent_io_tree *tree = &BTRFS_I(inode)->io_tree;
4039         struct page *page;
4040         unsigned long nr_pages = (end - start + PAGE_SIZE) >>
4041                 PAGE_SHIFT;
4042
4043         struct extent_page_data epd = {
4044                 .bio = NULL,
4045                 .tree = tree,
4046                 .extent_locked = 1,
4047                 .sync_io = mode == WB_SYNC_ALL,
4048         };
4049         struct writeback_control wbc_writepages = {
4050                 .sync_mode      = mode,
4051                 .nr_to_write    = nr_pages * 2,
4052                 .range_start    = start,
4053                 .range_end      = end + 1,
4054         };
4055
4056         while (start <= end) {
4057                 page = find_get_page(mapping, start >> PAGE_SHIFT);
4058                 if (clear_page_dirty_for_io(page))
4059                         ret = __extent_writepage(page, &wbc_writepages, &epd);
4060                 else {
4061                         btrfs_writepage_endio_finish_ordered(page, start,
4062                                                     start + PAGE_SIZE - 1, 1);
4063                         unlock_page(page);
4064                 }
4065                 put_page(page);
4066                 start += PAGE_SIZE;
4067         }
4068
4069         flush_write_bio(&epd);
4070         return ret;
4071 }
4072
4073 int extent_writepages(struct address_space *mapping,
4074                       struct writeback_control *wbc)
4075 {
4076         int ret = 0;
4077         struct extent_page_data epd = {
4078                 .bio = NULL,
4079                 .tree = &BTRFS_I(mapping->host)->io_tree,
4080                 .extent_locked = 0,
4081                 .sync_io = wbc->sync_mode == WB_SYNC_ALL,
4082         };
4083
4084         ret = extent_write_cache_pages(mapping, wbc, &epd);
4085         flush_write_bio(&epd);
4086         return ret;
4087 }
4088
4089 int extent_readpages(struct address_space *mapping, struct list_head *pages,
4090                      unsigned nr_pages)
4091 {
4092         struct bio *bio = NULL;
4093         unsigned long bio_flags = 0;
4094         struct page *pagepool[16];
4095         struct extent_map *em_cached = NULL;
4096         struct extent_io_tree *tree = &BTRFS_I(mapping->host)->io_tree;
4097         int nr = 0;
4098         u64 prev_em_start = (u64)-1;
4099
4100         while (!list_empty(pages)) {
4101                 for (nr = 0; nr < ARRAY_SIZE(pagepool) && !list_empty(pages);) {
4102                         struct page *page = lru_to_page(pages);
4103
4104                         prefetchw(&page->flags);
4105                         list_del(&page->lru);
4106                         if (add_to_page_cache_lru(page, mapping, page->index,
4107                                                 readahead_gfp_mask(mapping))) {
4108                                 put_page(page);
4109                                 continue;
4110                         }
4111
4112                         pagepool[nr++] = page;
4113                 }
4114
4115                 __extent_readpages(tree, pagepool, nr, &em_cached, &bio,
4116                                    &bio_flags, &prev_em_start);
4117         }
4118
4119         if (em_cached)
4120                 free_extent_map(em_cached);
4121
4122         if (bio)
4123                 return submit_one_bio(bio, 0, bio_flags);
4124         return 0;
4125 }
4126
4127 /*
4128  * basic invalidatepage code, this waits on any locked or writeback
4129  * ranges corresponding to the page, and then deletes any extent state
4130  * records from the tree
4131  */
4132 int extent_invalidatepage(struct extent_io_tree *tree,
4133                           struct page *page, unsigned long offset)
4134 {
4135         struct extent_state *cached_state = NULL;
4136         u64 start = page_offset(page);
4137         u64 end = start + PAGE_SIZE - 1;
4138         size_t blocksize = page->mapping->host->i_sb->s_blocksize;
4139
4140         start += ALIGN(offset, blocksize);
4141         if (start > end)
4142                 return 0;
4143
4144         lock_extent_bits(tree, start, end, &cached_state);
4145         wait_on_page_writeback(page);
4146         clear_extent_bit(tree, start, end,
4147                          EXTENT_LOCKED | EXTENT_DIRTY | EXTENT_DELALLOC |
4148                          EXTENT_DO_ACCOUNTING,
4149                          1, 1, &cached_state);
4150         return 0;
4151 }
4152
4153 /*
4154  * a helper for releasepage, this tests for areas of the page that
4155  * are locked or under IO and drops the related state bits if it is safe
4156  * to drop the page.
4157  */
4158 static int try_release_extent_state(struct extent_io_tree *tree,
4159                                     struct page *page, gfp_t mask)
4160 {
4161         u64 start = page_offset(page);
4162         u64 end = start + PAGE_SIZE - 1;
4163         int ret = 1;
4164
4165         if (test_range_bit(tree, start, end,
4166                            EXTENT_IOBITS, 0, NULL))
4167                 ret = 0;
4168         else {
4169                 /*
4170                  * at this point we can safely clear everything except the
4171                  * locked bit and the nodatasum bit
4172                  */
4173                 ret = __clear_extent_bit(tree, start, end,
4174                                  ~(EXTENT_LOCKED | EXTENT_NODATASUM),
4175                                  0, 0, NULL, mask, NULL);
4176
4177                 /* if clear_extent_bit failed for enomem reasons,
4178                  * we can't allow the release to continue.
4179                  */
4180                 if (ret < 0)
4181                         ret = 0;
4182                 else
4183                         ret = 1;
4184         }
4185         return ret;
4186 }
4187
4188 /*
4189  * a helper for releasepage.  As long as there are no locked extents
4190  * in the range corresponding to the page, both state records and extent
4191  * map records are removed
4192  */
4193 int try_release_extent_mapping(struct page *page, gfp_t mask)
4194 {
4195         struct extent_map *em;
4196         u64 start = page_offset(page);
4197         u64 end = start + PAGE_SIZE - 1;
4198         struct btrfs_inode *btrfs_inode = BTRFS_I(page->mapping->host);
4199         struct extent_io_tree *tree = &btrfs_inode->io_tree;
4200         struct extent_map_tree *map = &btrfs_inode->extent_tree;
4201
4202         if (gfpflags_allow_blocking(mask) &&
4203             page->mapping->host->i_size > SZ_16M) {
4204                 u64 len;
4205                 while (start <= end) {
4206                         len = end - start + 1;
4207                         write_lock(&map->lock);
4208                         em = lookup_extent_mapping(map, start, len);
4209                         if (!em) {
4210                                 write_unlock(&map->lock);
4211                                 break;
4212                         }
4213                         if (test_bit(EXTENT_FLAG_PINNED, &em->flags) ||
4214                             em->start != start) {
4215                                 write_unlock(&map->lock);
4216                                 free_extent_map(em);
4217                                 break;
4218                         }
4219                         if (!test_range_bit(tree, em->start,
4220                                             extent_map_end(em) - 1,
4221                                             EXTENT_LOCKED | EXTENT_WRITEBACK,
4222                                             0, NULL)) {
4223                                 set_bit(BTRFS_INODE_NEEDS_FULL_SYNC,
4224                                         &btrfs_inode->runtime_flags);
4225                                 remove_extent_mapping(map, em);
4226                                 /* once for the rb tree */
4227                                 free_extent_map(em);
4228                         }
4229                         start = extent_map_end(em);
4230                         write_unlock(&map->lock);
4231
4232                         /* once for us */
4233                         free_extent_map(em);
4234                 }
4235         }
4236         return try_release_extent_state(tree, page, mask);
4237 }
4238
4239 /*
4240  * helper function for fiemap, which doesn't want to see any holes.
4241  * This maps until we find something past 'last'
4242  */
4243 static struct extent_map *get_extent_skip_holes(struct inode *inode,
4244                                                 u64 offset, u64 last)
4245 {
4246         u64 sectorsize = btrfs_inode_sectorsize(inode);
4247         struct extent_map *em;
4248         u64 len;
4249
4250         if (offset >= last)
4251                 return NULL;
4252
4253         while (1) {
4254                 len = last - offset;
4255                 if (len == 0)
4256                         break;
4257                 len = ALIGN(len, sectorsize);
4258                 em = btrfs_get_extent_fiemap(BTRFS_I(inode), offset, len);
4259                 if (IS_ERR_OR_NULL(em))
4260                         return em;
4261
4262                 /* if this isn't a hole return it */
4263                 if (em->block_start != EXTENT_MAP_HOLE)
4264                         return em;
4265
4266                 /* this is a hole, advance to the next extent */
4267                 offset = extent_map_end(em);
4268                 free_extent_map(em);
4269                 if (offset >= last)
4270                         break;
4271         }
4272         return NULL;
4273 }
4274
4275 /*
4276  * To cache previous fiemap extent
4277  *
4278  * Will be used for merging fiemap extent
4279  */
4280 struct fiemap_cache {
4281         u64 offset;
4282         u64 phys;
4283         u64 len;
4284         u32 flags;
4285         bool cached;
4286 };
4287
4288 /*
4289  * Helper to submit fiemap extent.
4290  *
4291  * Will try to merge current fiemap extent specified by @offset, @phys,
4292  * @len and @flags with cached one.
4293  * And only when we fails to merge, cached one will be submitted as
4294  * fiemap extent.
4295  *
4296  * Return value is the same as fiemap_fill_next_extent().
4297  */
4298 static int emit_fiemap_extent(struct fiemap_extent_info *fieinfo,
4299                                 struct fiemap_cache *cache,
4300                                 u64 offset, u64 phys, u64 len, u32 flags)
4301 {
4302         int ret = 0;
4303
4304         if (!cache->cached)
4305                 goto assign;
4306
4307         /*
4308          * Sanity check, extent_fiemap() should have ensured that new
4309          * fiemap extent won't overlap with cached one.
4310          * Not recoverable.
4311          *
4312          * NOTE: Physical address can overlap, due to compression
4313          */
4314         if (cache->offset + cache->len > offset) {
4315                 WARN_ON(1);
4316                 return -EINVAL;
4317         }
4318
4319         /*
4320          * Only merges fiemap extents if
4321          * 1) Their logical addresses are continuous
4322          *
4323          * 2) Their physical addresses are continuous
4324          *    So truly compressed (physical size smaller than logical size)
4325          *    extents won't get merged with each other
4326          *
4327          * 3) Share same flags except FIEMAP_EXTENT_LAST
4328          *    So regular extent won't get merged with prealloc extent
4329          */
4330         if (cache->offset + cache->len  == offset &&
4331             cache->phys + cache->len == phys  &&
4332             (cache->flags & ~FIEMAP_EXTENT_LAST) ==
4333                         (flags & ~FIEMAP_EXTENT_LAST)) {
4334                 cache->len += len;
4335                 cache->flags |= flags;
4336                 goto try_submit_last;
4337         }
4338
4339         /* Not mergeable, need to submit cached one */
4340         ret = fiemap_fill_next_extent(fieinfo, cache->offset, cache->phys,
4341                                       cache->len, cache->flags);
4342         cache->cached = false;
4343         if (ret)
4344                 return ret;
4345 assign:
4346         cache->cached = true;
4347         cache->offset = offset;
4348         cache->phys = phys;
4349         cache->len = len;
4350         cache->flags = flags;
4351 try_submit_last:
4352         if (cache->flags & FIEMAP_EXTENT_LAST) {
4353                 ret = fiemap_fill_next_extent(fieinfo, cache->offset,
4354                                 cache->phys, cache->len, cache->flags);
4355                 cache->cached = false;
4356         }
4357         return ret;
4358 }
4359
4360 /*
4361  * Emit last fiemap cache
4362  *
4363  * The last fiemap cache may still be cached in the following case:
4364  * 0                  4k                    8k
4365  * |<- Fiemap range ->|
4366  * |<------------  First extent ----------->|
4367  *
4368  * In this case, the first extent range will be cached but not emitted.
4369  * So we must emit it before ending extent_fiemap().
4370  */
4371 static int emit_last_fiemap_cache(struct btrfs_fs_info *fs_info,
4372                                   struct fiemap_extent_info *fieinfo,
4373                                   struct fiemap_cache *cache)
4374 {
4375         int ret;
4376
4377         if (!cache->cached)
4378                 return 0;
4379
4380         ret = fiemap_fill_next_extent(fieinfo, cache->offset, cache->phys,
4381                                       cache->len, cache->flags);
4382         cache->cached = false;
4383         if (ret > 0)
4384                 ret = 0;
4385         return ret;
4386 }
4387
4388 int extent_fiemap(struct inode *inode, struct fiemap_extent_info *fieinfo,
4389                 __u64 start, __u64 len)
4390 {
4391         int ret = 0;
4392         u64 off = start;
4393         u64 max = start + len;
4394         u32 flags = 0;
4395         u32 found_type;
4396         u64 last;
4397         u64 last_for_get_extent = 0;
4398         u64 disko = 0;
4399         u64 isize = i_size_read(inode);
4400         struct btrfs_key found_key;
4401         struct extent_map *em = NULL;
4402         struct extent_state *cached_state = NULL;
4403         struct btrfs_path *path;
4404         struct btrfs_root *root = BTRFS_I(inode)->root;
4405         struct fiemap_cache cache = { 0 };
4406         int end = 0;
4407         u64 em_start = 0;
4408         u64 em_len = 0;
4409         u64 em_end = 0;
4410
4411         if (len == 0)
4412                 return -EINVAL;
4413
4414         path = btrfs_alloc_path();
4415         if (!path)
4416                 return -ENOMEM;
4417         path->leave_spinning = 1;
4418
4419         start = round_down(start, btrfs_inode_sectorsize(inode));
4420         len = round_up(max, btrfs_inode_sectorsize(inode)) - start;
4421
4422         /*
4423          * lookup the last file extent.  We're not using i_size here
4424          * because there might be preallocation past i_size
4425          */
4426         ret = btrfs_lookup_file_extent(NULL, root, path,
4427                         btrfs_ino(BTRFS_I(inode)), -1, 0);
4428         if (ret < 0) {
4429                 btrfs_free_path(path);
4430                 return ret;
4431         } else {
4432                 WARN_ON(!ret);
4433                 if (ret == 1)
4434                         ret = 0;
4435         }
4436
4437         path->slots[0]--;
4438         btrfs_item_key_to_cpu(path->nodes[0], &found_key, path->slots[0]);
4439         found_type = found_key.type;
4440
4441         /* No extents, but there might be delalloc bits */
4442         if (found_key.objectid != btrfs_ino(BTRFS_I(inode)) ||
4443             found_type != BTRFS_EXTENT_DATA_KEY) {
4444                 /* have to trust i_size as the end */
4445                 last = (u64)-1;
4446                 last_for_get_extent = isize;
4447         } else {
4448                 /*
4449                  * remember the start of the last extent.  There are a
4450                  * bunch of different factors that go into the length of the
4451                  * extent, so its much less complex to remember where it started
4452                  */
4453                 last = found_key.offset;
4454                 last_for_get_extent = last + 1;
4455         }
4456         btrfs_release_path(path);
4457
4458         /*
4459          * we might have some extents allocated but more delalloc past those
4460          * extents.  so, we trust isize unless the start of the last extent is
4461          * beyond isize
4462          */
4463         if (last < isize) {
4464                 last = (u64)-1;
4465                 last_for_get_extent = isize;
4466         }
4467
4468         lock_extent_bits(&BTRFS_I(inode)->io_tree, start, start + len - 1,
4469                          &cached_state);
4470
4471         em = get_extent_skip_holes(inode, start, last_for_get_extent);
4472         if (!em)
4473                 goto out;
4474         if (IS_ERR(em)) {
4475                 ret = PTR_ERR(em);
4476                 goto out;
4477         }
4478
4479         while (!end) {
4480                 u64 offset_in_extent = 0;
4481
4482                 /* break if the extent we found is outside the range */
4483                 if (em->start >= max || extent_map_end(em) < off)
4484                         break;
4485
4486                 /*
4487                  * get_extent may return an extent that starts before our
4488                  * requested range.  We have to make sure the ranges
4489                  * we return to fiemap always move forward and don't
4490                  * overlap, so adjust the offsets here
4491                  */
4492                 em_start = max(em->start, off);
4493
4494                 /*
4495                  * record the offset from the start of the extent
4496                  * for adjusting the disk offset below.  Only do this if the
4497                  * extent isn't compressed since our in ram offset may be past
4498                  * what we have actually allocated on disk.
4499                  */
4500                 if (!test_bit(EXTENT_FLAG_COMPRESSED, &em->flags))
4501                         offset_in_extent = em_start - em->start;
4502                 em_end = extent_map_end(em);
4503                 em_len = em_end - em_start;
4504                 flags = 0;
4505                 if (em->block_start < EXTENT_MAP_LAST_BYTE)
4506                         disko = em->block_start + offset_in_extent;
4507                 else
4508                         disko = 0;
4509
4510                 /*
4511                  * bump off for our next call to get_extent
4512                  */
4513                 off = extent_map_end(em);
4514                 if (off >= max)
4515                         end = 1;
4516
4517                 if (em->block_start == EXTENT_MAP_LAST_BYTE) {
4518                         end = 1;
4519                         flags |= FIEMAP_EXTENT_LAST;
4520                 } else if (em->block_start == EXTENT_MAP_INLINE) {
4521                         flags |= (FIEMAP_EXTENT_DATA_INLINE |
4522                                   FIEMAP_EXTENT_NOT_ALIGNED);
4523                 } else if (em->block_start == EXTENT_MAP_DELALLOC) {
4524                         flags |= (FIEMAP_EXTENT_DELALLOC |
4525                                   FIEMAP_EXTENT_UNKNOWN);
4526                 } else if (fieinfo->fi_extents_max) {
4527                         u64 bytenr = em->block_start -
4528                                 (em->start - em->orig_start);
4529
4530                         /*
4531                          * As btrfs supports shared space, this information
4532                          * can be exported to userspace tools via
4533                          * flag FIEMAP_EXTENT_SHARED.  If fi_extents_max == 0
4534                          * then we're just getting a count and we can skip the
4535                          * lookup stuff.
4536                          */
4537                         ret = btrfs_check_shared(root,
4538                                                  btrfs_ino(BTRFS_I(inode)),
4539                                                  bytenr);
4540                         if (ret < 0)
4541                                 goto out_free;
4542                         if (ret)
4543                                 flags |= FIEMAP_EXTENT_SHARED;
4544                         ret = 0;
4545                 }
4546                 if (test_bit(EXTENT_FLAG_COMPRESSED, &em->flags))
4547                         flags |= FIEMAP_EXTENT_ENCODED;
4548                 if (test_bit(EXTENT_FLAG_PREALLOC, &em->flags))
4549                         flags |= FIEMAP_EXTENT_UNWRITTEN;
4550
4551                 free_extent_map(em);
4552                 em = NULL;
4553                 if ((em_start >= last) || em_len == (u64)-1 ||
4554                    (last == (u64)-1 && isize <= em_end)) {
4555                         flags |= FIEMAP_EXTENT_LAST;
4556                         end = 1;
4557                 }
4558
4559                 /* now scan forward to see if this is really the last extent. */
4560                 em = get_extent_skip_holes(inode, off, last_for_get_extent);
4561                 if (IS_ERR(em)) {
4562                         ret = PTR_ERR(em);
4563                         goto out;
4564                 }
4565                 if (!em) {
4566                         flags |= FIEMAP_EXTENT_LAST;
4567                         end = 1;
4568                 }
4569                 ret = emit_fiemap_extent(fieinfo, &cache, em_start, disko,
4570                                            em_len, flags);
4571                 if (ret) {
4572                         if (ret == 1)
4573                                 ret = 0;
4574                         goto out_free;
4575                 }
4576         }
4577 out_free:
4578         if (!ret)
4579                 ret = emit_last_fiemap_cache(root->fs_info, fieinfo, &cache);
4580         free_extent_map(em);
4581 out:
4582         btrfs_free_path(path);
4583         unlock_extent_cached(&BTRFS_I(inode)->io_tree, start, start + len - 1,
4584                              &cached_state);
4585         return ret;
4586 }
4587
4588 static void __free_extent_buffer(struct extent_buffer *eb)
4589 {
4590         btrfs_leak_debug_del(&eb->leak_list);
4591         kmem_cache_free(extent_buffer_cache, eb);
4592 }
4593
4594 int extent_buffer_under_io(struct extent_buffer *eb)
4595 {
4596         return (atomic_read(&eb->io_pages) ||
4597                 test_bit(EXTENT_BUFFER_WRITEBACK, &eb->bflags) ||
4598                 test_bit(EXTENT_BUFFER_DIRTY, &eb->bflags));
4599 }
4600
4601 /*
4602  * Release all pages attached to the extent buffer.
4603  */
4604 static void btrfs_release_extent_buffer_pages(struct extent_buffer *eb)
4605 {
4606         int i;
4607         int num_pages;
4608         int mapped = !test_bit(EXTENT_BUFFER_UNMAPPED, &eb->bflags);
4609
4610         BUG_ON(extent_buffer_under_io(eb));
4611
4612         num_pages = num_extent_pages(eb);
4613         for (i = 0; i < num_pages; i++) {
4614                 struct page *page = eb->pages[i];
4615
4616                 if (!page)
4617                         continue;
4618                 if (mapped)
4619                         spin_lock(&page->mapping->private_lock);
4620                 /*
4621                  * We do this since we'll remove the pages after we've
4622                  * removed the eb from the radix tree, so we could race
4623                  * and have this page now attached to the new eb.  So
4624                  * only clear page_private if it's still connected to
4625                  * this eb.
4626                  */
4627                 if (PagePrivate(page) &&
4628                     page->private == (unsigned long)eb) {
4629                         BUG_ON(test_bit(EXTENT_BUFFER_DIRTY, &eb->bflags));
4630                         BUG_ON(PageDirty(page));
4631                         BUG_ON(PageWriteback(page));
4632                         /*
4633                          * We need to make sure we haven't be attached
4634                          * to a new eb.
4635                          */
4636                         ClearPagePrivate(page);
4637                         set_page_private(page, 0);
4638                         /* One for the page private */
4639                         put_page(page);
4640                 }
4641
4642                 if (mapped)
4643                         spin_unlock(&page->mapping->private_lock);
4644
4645                 /* One for when we allocated the page */
4646                 put_page(page);
4647         }
4648 }
4649
4650 /*
4651  * Helper for releasing the extent buffer.
4652  */
4653 static inline void btrfs_release_extent_buffer(struct extent_buffer *eb)
4654 {
4655         btrfs_release_extent_buffer_pages(eb);
4656         __free_extent_buffer(eb);
4657 }
4658
4659 static struct extent_buffer *
4660 __alloc_extent_buffer(struct btrfs_fs_info *fs_info, u64 start,
4661                       unsigned long len)
4662 {
4663         struct extent_buffer *eb = NULL;
4664
4665         eb = kmem_cache_zalloc(extent_buffer_cache, GFP_NOFS|__GFP_NOFAIL);
4666         eb->start = start;
4667         eb->len = len;
4668         eb->fs_info = fs_info;
4669         eb->bflags = 0;
4670         rwlock_init(&eb->lock);
4671         atomic_set(&eb->write_locks, 0);
4672         atomic_set(&eb->read_locks, 0);
4673         atomic_set(&eb->blocking_readers, 0);
4674         atomic_set(&eb->blocking_writers, 0);
4675         atomic_set(&eb->spinning_readers, 0);
4676         atomic_set(&eb->spinning_writers, 0);
4677         eb->lock_nested = 0;
4678         init_waitqueue_head(&eb->write_lock_wq);
4679         init_waitqueue_head(&eb->read_lock_wq);
4680
4681         btrfs_leak_debug_add(&eb->leak_list, &buffers);
4682
4683         spin_lock_init(&eb->refs_lock);
4684         atomic_set(&eb->refs, 1);
4685         atomic_set(&eb->io_pages, 0);
4686
4687         /*
4688          * Sanity checks, currently the maximum is 64k covered by 16x 4k pages
4689          */
4690         BUILD_BUG_ON(BTRFS_MAX_METADATA_BLOCKSIZE
4691                 > MAX_INLINE_EXTENT_BUFFER_SIZE);
4692         BUG_ON(len > MAX_INLINE_EXTENT_BUFFER_SIZE);
4693
4694         return eb;
4695 }
4696
4697 struct extent_buffer *btrfs_clone_extent_buffer(struct extent_buffer *src)
4698 {
4699         int i;
4700         struct page *p;
4701         struct extent_buffer *new;
4702         int num_pages = num_extent_pages(src);
4703
4704         new = __alloc_extent_buffer(src->fs_info, src->start, src->len);
4705         if (new == NULL)
4706                 return NULL;
4707
4708         for (i = 0; i < num_pages; i++) {
4709                 p = alloc_page(GFP_NOFS);
4710                 if (!p) {
4711                         btrfs_release_extent_buffer(new);
4712                         return NULL;
4713                 }
4714                 attach_extent_buffer_page(new, p);
4715                 WARN_ON(PageDirty(p));
4716                 SetPageUptodate(p);
4717                 new->pages[i] = p;
4718                 copy_page(page_address(p), page_address(src->pages[i]));
4719         }
4720
4721         set_bit(EXTENT_BUFFER_UPTODATE, &new->bflags);
4722         set_bit(EXTENT_BUFFER_UNMAPPED, &new->bflags);
4723
4724         return new;
4725 }
4726
4727 struct extent_buffer *__alloc_dummy_extent_buffer(struct btrfs_fs_info *fs_info,
4728                                                   u64 start, unsigned long len)
4729 {
4730         struct extent_buffer *eb;
4731         int num_pages;
4732         int i;
4733
4734         eb = __alloc_extent_buffer(fs_info, start, len);
4735         if (!eb)
4736                 return NULL;
4737
4738         num_pages = num_extent_pages(eb);
4739         for (i = 0; i < num_pages; i++) {
4740                 eb->pages[i] = alloc_page(GFP_NOFS);
4741                 if (!eb->pages[i])
4742                         goto err;
4743         }
4744         set_extent_buffer_uptodate(eb);
4745         btrfs_set_header_nritems(eb, 0);
4746         set_bit(EXTENT_BUFFER_UNMAPPED, &eb->bflags);
4747
4748         return eb;
4749 err:
4750         for (; i > 0; i--)
4751                 __free_page(eb->pages[i - 1]);
4752         __free_extent_buffer(eb);
4753         return NULL;
4754 }
4755
4756 struct extent_buffer *alloc_dummy_extent_buffer(struct btrfs_fs_info *fs_info,
4757                                                 u64 start)
4758 {
4759         return __alloc_dummy_extent_buffer(fs_info, start, fs_info->nodesize);
4760 }
4761
4762 static void check_buffer_tree_ref(struct extent_buffer *eb)
4763 {
4764         int refs;
4765         /* the ref bit is tricky.  We have to make sure it is set
4766          * if we have the buffer dirty.   Otherwise the
4767          * code to free a buffer can end up dropping a dirty
4768          * page
4769          *
4770          * Once the ref bit is set, it won't go away while the
4771          * buffer is dirty or in writeback, and it also won't
4772          * go away while we have the reference count on the
4773          * eb bumped.
4774          *
4775          * We can't just set the ref bit without bumping the
4776          * ref on the eb because free_extent_buffer might
4777          * see the ref bit and try to clear it.  If this happens
4778          * free_extent_buffer might end up dropping our original
4779          * ref by mistake and freeing the page before we are able
4780          * to add one more ref.
4781          *
4782          * So bump the ref count first, then set the bit.  If someone
4783          * beat us to it, drop the ref we added.
4784          */
4785         refs = atomic_read(&eb->refs);
4786         if (refs >= 2 && test_bit(EXTENT_BUFFER_TREE_REF, &eb->bflags))
4787                 return;
4788
4789         spin_lock(&eb->refs_lock);
4790         if (!test_and_set_bit(EXTENT_BUFFER_TREE_REF, &eb->bflags))
4791                 atomic_inc(&eb->refs);
4792         spin_unlock(&eb->refs_lock);
4793 }
4794
4795 static void mark_extent_buffer_accessed(struct extent_buffer *eb,
4796                 struct page *accessed)
4797 {
4798         int num_pages, i;
4799
4800         check_buffer_tree_ref(eb);
4801
4802         num_pages = num_extent_pages(eb);
4803         for (i = 0; i < num_pages; i++) {
4804                 struct page *p = eb->pages[i];
4805
4806                 if (p != accessed)
4807                         mark_page_accessed(p);
4808         }
4809 }
4810
4811 struct extent_buffer *find_extent_buffer(struct btrfs_fs_info *fs_info,
4812                                          u64 start)
4813 {
4814         struct extent_buffer *eb;
4815
4816         rcu_read_lock();
4817         eb = radix_tree_lookup(&fs_info->buffer_radix,
4818                                start >> PAGE_SHIFT);
4819         if (eb && atomic_inc_not_zero(&eb->refs)) {
4820                 rcu_read_unlock();
4821                 /*
4822                  * Lock our eb's refs_lock to avoid races with
4823                  * free_extent_buffer. When we get our eb it might be flagged
4824                  * with EXTENT_BUFFER_STALE and another task running
4825                  * free_extent_buffer might have seen that flag set,
4826                  * eb->refs == 2, that the buffer isn't under IO (dirty and
4827                  * writeback flags not set) and it's still in the tree (flag
4828                  * EXTENT_BUFFER_TREE_REF set), therefore being in the process
4829                  * of decrementing the extent buffer's reference count twice.
4830                  * So here we could race and increment the eb's reference count,
4831                  * clear its stale flag, mark it as dirty and drop our reference
4832                  * before the other task finishes executing free_extent_buffer,
4833                  * which would later result in an attempt to free an extent
4834                  * buffer that is dirty.
4835                  */
4836                 if (test_bit(EXTENT_BUFFER_STALE, &eb->bflags)) {
4837                         spin_lock(&eb->refs_lock);
4838                         spin_unlock(&eb->refs_lock);
4839                 }
4840                 mark_extent_buffer_accessed(eb, NULL);
4841                 return eb;
4842         }
4843         rcu_read_unlock();
4844
4845         return NULL;
4846 }
4847
4848 #ifdef CONFIG_BTRFS_FS_RUN_SANITY_TESTS
4849 struct extent_buffer *alloc_test_extent_buffer(struct btrfs_fs_info *fs_info,
4850                                         u64 start)
4851 {
4852         struct extent_buffer *eb, *exists = NULL;
4853         int ret;
4854
4855         eb = find_extent_buffer(fs_info, start);
4856         if (eb)
4857                 return eb;
4858         eb = alloc_dummy_extent_buffer(fs_info, start);
4859         if (!eb)
4860                 return NULL;
4861         eb->fs_info = fs_info;
4862 again:
4863         ret = radix_tree_preload(GFP_NOFS);
4864         if (ret)
4865                 goto free_eb;
4866         spin_lock(&fs_info->buffer_lock);
4867         ret = radix_tree_insert(&fs_info->buffer_radix,
4868                                 start >> PAGE_SHIFT, eb);
4869         spin_unlock(&fs_info->buffer_lock);
4870         radix_tree_preload_end();
4871         if (ret == -EEXIST) {
4872                 exists = find_extent_buffer(fs_info, start);
4873                 if (exists)
4874                         goto free_eb;
4875                 else
4876                         goto again;
4877         }
4878         check_buffer_tree_ref(eb);
4879         set_bit(EXTENT_BUFFER_IN_TREE, &eb->bflags);
4880
4881         return eb;
4882 free_eb:
4883         btrfs_release_extent_buffer(eb);
4884         return exists;
4885 }
4886 #endif
4887
4888 struct extent_buffer *alloc_extent_buffer(struct btrfs_fs_info *fs_info,
4889                                           u64 start)
4890 {
4891         unsigned long len = fs_info->nodesize;
4892         int num_pages;
4893         int i;
4894         unsigned long index = start >> PAGE_SHIFT;
4895         struct extent_buffer *eb;
4896         struct extent_buffer *exists = NULL;
4897         struct page *p;
4898         struct address_space *mapping = fs_info->btree_inode->i_mapping;
4899         int uptodate = 1;
4900         int ret;
4901
4902         if (!IS_ALIGNED(start, fs_info->sectorsize)) {
4903                 btrfs_err(fs_info, "bad tree block start %llu", start);
4904                 return ERR_PTR(-EINVAL);
4905         }
4906
4907         eb = find_extent_buffer(fs_info, start);
4908         if (eb)
4909                 return eb;
4910
4911         eb = __alloc_extent_buffer(fs_info, start, len);
4912         if (!eb)
4913                 return ERR_PTR(-ENOMEM);
4914
4915         num_pages = num_extent_pages(eb);
4916         for (i = 0; i < num_pages; i++, index++) {
4917                 p = find_or_create_page(mapping, index, GFP_NOFS|__GFP_NOFAIL);
4918                 if (!p) {
4919                         exists = ERR_PTR(-ENOMEM);
4920                         goto free_eb;
4921                 }
4922
4923                 spin_lock(&mapping->private_lock);
4924                 if (PagePrivate(p)) {
4925                         /*
4926                          * We could have already allocated an eb for this page
4927                          * and attached one so lets see if we can get a ref on
4928                          * the existing eb, and if we can we know it's good and
4929                          * we can just return that one, else we know we can just
4930                          * overwrite page->private.
4931                          */
4932                         exists = (struct extent_buffer *)p->private;
4933                         if (atomic_inc_not_zero(&exists->refs)) {
4934                                 spin_unlock(&mapping->private_lock);
4935                                 unlock_page(p);
4936                                 put_page(p);
4937                                 mark_extent_buffer_accessed(exists, p);
4938                                 goto free_eb;
4939                         }
4940                         exists = NULL;
4941
4942                         /*
4943                          * Do this so attach doesn't complain and we need to
4944                          * drop the ref the old guy had.
4945                          */
4946                         ClearPagePrivate(p);
4947                         WARN_ON(PageDirty(p));
4948                         put_page(p);
4949                 }
4950                 attach_extent_buffer_page(eb, p);
4951                 spin_unlock(&mapping->private_lock);
4952                 WARN_ON(PageDirty(p));
4953                 eb->pages[i] = p;
4954                 if (!PageUptodate(p))
4955                         uptodate = 0;
4956
4957                 /*
4958                  * We can't unlock the pages just yet since the extent buffer
4959                  * hasn't been properly inserted in the radix tree, this
4960                  * opens a race with btree_releasepage which can free a page
4961                  * while we are still filling in all pages for the buffer and
4962                  * we could crash.
4963                  */
4964         }
4965         if (uptodate)
4966                 set_bit(EXTENT_BUFFER_UPTODATE, &eb->bflags);
4967 again:
4968         ret = radix_tree_preload(GFP_NOFS);
4969         if (ret) {
4970                 exists = ERR_PTR(ret);
4971                 goto free_eb;
4972         }
4973
4974         spin_lock(&fs_info->buffer_lock);
4975         ret = radix_tree_insert(&fs_info->buffer_radix,
4976                                 start >> PAGE_SHIFT, eb);
4977         spin_unlock(&fs_info->buffer_lock);
4978         radix_tree_preload_end();
4979         if (ret == -EEXIST) {
4980                 exists = find_extent_buffer(fs_info, start);
4981                 if (exists)
4982                         goto free_eb;
4983                 else
4984                         goto again;
4985         }
4986         /* add one reference for the tree */
4987         check_buffer_tree_ref(eb);
4988         set_bit(EXTENT_BUFFER_IN_TREE, &eb->bflags);
4989
4990         /*
4991          * Now it's safe to unlock the pages because any calls to
4992          * btree_releasepage will correctly detect that a page belongs to a
4993          * live buffer and won't free them prematurely.
4994          */
4995         for (i = 0; i < num_pages; i++)
4996                 unlock_page(eb->pages[i]);
4997         return eb;
4998
4999 free_eb:
5000         WARN_ON(!atomic_dec_and_test(&eb->refs));
5001         for (i = 0; i < num_pages; i++) {
5002                 if (eb->pages[i])
5003                         unlock_page(eb->pages[i]);
5004         }
5005
5006         btrfs_release_extent_buffer(eb);
5007         return exists;
5008 }
5009
5010 static inline void btrfs_release_extent_buffer_rcu(struct rcu_head *head)
5011 {
5012         struct extent_buffer *eb =
5013                         container_of(head, struct extent_buffer, rcu_head);
5014
5015         __free_extent_buffer(eb);
5016 }
5017
5018 static int release_extent_buffer(struct extent_buffer *eb)
5019 {
5020         lockdep_assert_held(&eb->refs_lock);
5021
5022         WARN_ON(atomic_read(&eb->refs) == 0);
5023         if (atomic_dec_and_test(&eb->refs)) {
5024                 if (test_and_clear_bit(EXTENT_BUFFER_IN_TREE, &eb->bflags)) {
5025                         struct btrfs_fs_info *fs_info = eb->fs_info;
5026
5027                         spin_unlock(&eb->refs_lock);
5028
5029                         spin_lock(&fs_info->buffer_lock);
5030                         radix_tree_delete(&fs_info->buffer_radix,
5031                                           eb->start >> PAGE_SHIFT);
5032                         spin_unlock(&fs_info->buffer_lock);
5033                 } else {
5034                         spin_unlock(&eb->refs_lock);
5035                 }
5036
5037                 /* Should be safe to release our pages at this point */
5038                 btrfs_release_extent_buffer_pages(eb);
5039 #ifdef CONFIG_BTRFS_FS_RUN_SANITY_TESTS
5040                 if (unlikely(test_bit(EXTENT_BUFFER_UNMAPPED, &eb->bflags))) {
5041                         __free_extent_buffer(eb);
5042                         return 1;
5043                 }
5044 #endif
5045                 call_rcu(&eb->rcu_head, btrfs_release_extent_buffer_rcu);
5046                 return 1;
5047         }
5048         spin_unlock(&eb->refs_lock);
5049
5050         return 0;
5051 }
5052
5053 void free_extent_buffer(struct extent_buffer *eb)
5054 {
5055         int refs;
5056         int old;
5057         if (!eb)
5058                 return;
5059
5060         while (1) {
5061                 refs = atomic_read(&eb->refs);
5062                 if ((!test_bit(EXTENT_BUFFER_UNMAPPED, &eb->bflags) && refs <= 3)
5063                     || (test_bit(EXTENT_BUFFER_UNMAPPED, &eb->bflags) &&
5064                         refs == 1))
5065                         break;
5066                 old = atomic_cmpxchg(&eb->refs, refs, refs - 1);
5067                 if (old == refs)
5068                         return;
5069         }
5070
5071         spin_lock(&eb->refs_lock);
5072         if (atomic_read(&eb->refs) == 2 &&
5073             test_bit(EXTENT_BUFFER_STALE, &eb->bflags) &&
5074             !extent_buffer_under_io(eb) &&
5075             test_and_clear_bit(EXTENT_BUFFER_TREE_REF, &eb->bflags))
5076                 atomic_dec(&eb->refs);
5077
5078         /*
5079          * I know this is terrible, but it's temporary until we stop tracking
5080          * the uptodate bits and such for the extent buffers.
5081          */
5082         release_extent_buffer(eb);
5083 }
5084
5085 void free_extent_buffer_stale(struct extent_buffer *eb)
5086 {
5087         if (!eb)
5088                 return;
5089
5090         spin_lock(&eb->refs_lock);
5091         set_bit(EXTENT_BUFFER_STALE, &eb->bflags);
5092
5093         if (atomic_read(&eb->refs) == 2 && !extent_buffer_under_io(eb) &&
5094             test_and_clear_bit(EXTENT_BUFFER_TREE_REF, &eb->bflags))
5095                 atomic_dec(&eb->refs);
5096         release_extent_buffer(eb);
5097 }
5098
5099 void clear_extent_buffer_dirty(struct extent_buffer *eb)
5100 {
5101         int i;
5102         int num_pages;
5103         struct page *page;
5104
5105         num_pages = num_extent_pages(eb);
5106
5107         for (i = 0; i < num_pages; i++) {
5108                 page = eb->pages[i];
5109                 if (!PageDirty(page))
5110                         continue;
5111
5112                 lock_page(page);
5113                 WARN_ON(!PagePrivate(page));
5114
5115                 clear_page_dirty_for_io(page);
5116                 xa_lock_irq(&page->mapping->i_pages);
5117                 if (!PageDirty(page))
5118                         __xa_clear_mark(&page->mapping->i_pages,
5119                                         page_index(page), PAGECACHE_TAG_DIRTY);
5120                 xa_unlock_irq(&page->mapping->i_pages);
5121                 ClearPageError(page);
5122                 unlock_page(page);
5123         }
5124         WARN_ON(atomic_read(&eb->refs) == 0);
5125 }
5126
5127 bool set_extent_buffer_dirty(struct extent_buffer *eb)
5128 {
5129         int i;
5130         int num_pages;
5131         bool was_dirty;
5132
5133         check_buffer_tree_ref(eb);
5134
5135         was_dirty = test_and_set_bit(EXTENT_BUFFER_DIRTY, &eb->bflags);
5136
5137         num_pages = num_extent_pages(eb);
5138         WARN_ON(atomic_read(&eb->refs) == 0);
5139         WARN_ON(!test_bit(EXTENT_BUFFER_TREE_REF, &eb->bflags));
5140
5141         if (!was_dirty)
5142                 for (i = 0; i < num_pages; i++)
5143                         set_page_dirty(eb->pages[i]);
5144
5145 #ifdef CONFIG_BTRFS_DEBUG
5146         for (i = 0; i < num_pages; i++)
5147                 ASSERT(PageDirty(eb->pages[i]));
5148 #endif
5149
5150         return was_dirty;
5151 }
5152
5153 void clear_extent_buffer_uptodate(struct extent_buffer *eb)
5154 {
5155         int i;
5156         struct page *page;
5157         int num_pages;
5158
5159         clear_bit(EXTENT_BUFFER_UPTODATE, &eb->bflags);
5160         num_pages = num_extent_pages(eb);
5161         for (i = 0; i < num_pages; i++) {
5162                 page = eb->pages[i];
5163                 if (page)
5164                         ClearPageUptodate(page);
5165         }
5166 }
5167
5168 void set_extent_buffer_uptodate(struct extent_buffer *eb)
5169 {
5170         int i;
5171         struct page *page;
5172         int num_pages;
5173
5174         set_bit(EXTENT_BUFFER_UPTODATE, &eb->bflags);
5175         num_pages = num_extent_pages(eb);
5176         for (i = 0; i < num_pages; i++) {
5177                 page = eb->pages[i];
5178                 SetPageUptodate(page);
5179         }
5180 }
5181
5182 int read_extent_buffer_pages(struct extent_io_tree *tree,
5183                              struct extent_buffer *eb, int wait, int mirror_num)
5184 {
5185         int i;
5186         struct page *page;
5187         int err;
5188         int ret = 0;
5189         int locked_pages = 0;
5190         int all_uptodate = 1;
5191         int num_pages;
5192         unsigned long num_reads = 0;
5193         struct bio *bio = NULL;
5194         unsigned long bio_flags = 0;
5195
5196         if (test_bit(EXTENT_BUFFER_UPTODATE, &eb->bflags))
5197                 return 0;
5198
5199         num_pages = num_extent_pages(eb);
5200         for (i = 0; i < num_pages; i++) {
5201                 page = eb->pages[i];
5202                 if (wait == WAIT_NONE) {
5203                         if (!trylock_page(page))
5204                                 goto unlock_exit;
5205                 } else {
5206                         lock_page(page);
5207                 }
5208                 locked_pages++;
5209         }
5210         /*
5211          * We need to firstly lock all pages to make sure that
5212          * the uptodate bit of our pages won't be affected by
5213          * clear_extent_buffer_uptodate().
5214          */
5215         for (i = 0; i < num_pages; i++) {
5216                 page = eb->pages[i];
5217                 if (!PageUptodate(page)) {
5218                         num_reads++;
5219                         all_uptodate = 0;
5220                 }
5221         }
5222
5223         if (all_uptodate) {
5224                 set_bit(EXTENT_BUFFER_UPTODATE, &eb->bflags);
5225                 goto unlock_exit;
5226         }
5227
5228         clear_bit(EXTENT_BUFFER_READ_ERR, &eb->bflags);
5229         eb->read_mirror = 0;
5230         atomic_set(&eb->io_pages, num_reads);
5231         for (i = 0; i < num_pages; i++) {
5232                 page = eb->pages[i];
5233
5234                 if (!PageUptodate(page)) {
5235                         if (ret) {
5236                                 atomic_dec(&eb->io_pages);
5237                                 unlock_page(page);
5238                                 continue;
5239                         }
5240
5241                         ClearPageError(page);
5242                         err = __extent_read_full_page(tree, page,
5243                                                       btree_get_extent, &bio,
5244                                                       mirror_num, &bio_flags,
5245                                                       REQ_META);
5246                         if (err) {
5247                                 ret = err;
5248                                 /*
5249                                  * We use &bio in above __extent_read_full_page,
5250                                  * so we ensure that if it returns error, the
5251                                  * current page fails to add itself to bio and
5252                                  * it's been unlocked.
5253                                  *
5254                                  * We must dec io_pages by ourselves.
5255                                  */
5256                                 atomic_dec(&eb->io_pages);
5257                         }
5258                 } else {
5259                         unlock_page(page);
5260                 }
5261         }
5262
5263         if (bio) {
5264                 err = submit_one_bio(bio, mirror_num, bio_flags);
5265                 if (err)
5266                         return err;
5267         }
5268
5269         if (ret || wait != WAIT_COMPLETE)
5270                 return ret;
5271
5272         for (i = 0; i < num_pages; i++) {
5273                 page = eb->pages[i];
5274                 wait_on_page_locked(page);
5275                 if (!PageUptodate(page))
5276                         ret = -EIO;
5277         }
5278
5279         return ret;
5280
5281 unlock_exit:
5282         while (locked_pages > 0) {
5283                 locked_pages--;
5284                 page = eb->pages[locked_pages];
5285                 unlock_page(page);
5286         }
5287         return ret;
5288 }
5289
5290 void read_extent_buffer(const struct extent_buffer *eb, void *dstv,
5291                         unsigned long start, unsigned long len)
5292 {
5293         size_t cur;
5294         size_t offset;
5295         struct page *page;
5296         char *kaddr;
5297         char *dst = (char *)dstv;
5298         size_t start_offset = offset_in_page(eb->start);
5299         unsigned long i = (start_offset + start) >> PAGE_SHIFT;
5300
5301         if (start + len > eb->len) {
5302                 WARN(1, KERN_ERR "btrfs bad mapping eb start %llu len %lu, wanted %lu %lu\n",
5303                      eb->start, eb->len, start, len);
5304                 memset(dst, 0, len);
5305                 return;
5306         }
5307
5308         offset = offset_in_page(start_offset + start);
5309
5310         while (len > 0) {
5311                 page = eb->pages[i];
5312
5313                 cur = min(len, (PAGE_SIZE - offset));
5314                 kaddr = page_address(page);
5315                 memcpy(dst, kaddr + offset, cur);
5316
5317                 dst += cur;
5318                 len -= cur;
5319                 offset = 0;
5320                 i++;
5321         }
5322 }
5323
5324 int read_extent_buffer_to_user(const struct extent_buffer *eb,
5325                                void __user *dstv,
5326                                unsigned long start, unsigned long len)
5327 {
5328         size_t cur;
5329         size_t offset;
5330         struct page *page;
5331         char *kaddr;
5332         char __user *dst = (char __user *)dstv;
5333         size_t start_offset = offset_in_page(eb->start);
5334         unsigned long i = (start_offset + start) >> PAGE_SHIFT;
5335         int ret = 0;
5336
5337         WARN_ON(start > eb->len);
5338         WARN_ON(start + len > eb->start + eb->len);
5339
5340         offset = offset_in_page(start_offset + start);
5341
5342         while (len > 0) {
5343                 page = eb->pages[i];
5344
5345                 cur = min(len, (PAGE_SIZE - offset));
5346                 kaddr = page_address(page);
5347                 if (copy_to_user(dst, kaddr + offset, cur)) {
5348                         ret = -EFAULT;
5349                         break;
5350                 }
5351
5352                 dst += cur;
5353                 len -= cur;
5354                 offset = 0;
5355                 i++;
5356         }
5357
5358         return ret;
5359 }
5360
5361 /*
5362  * return 0 if the item is found within a page.
5363  * return 1 if the item spans two pages.
5364  * return -EINVAL otherwise.
5365  */
5366 int map_private_extent_buffer(const struct extent_buffer *eb,
5367                               unsigned long start, unsigned long min_len,
5368                               char **map, unsigned long *map_start,
5369                               unsigned long *map_len)
5370 {
5371         size_t offset;
5372         char *kaddr;
5373         struct page *p;
5374         size_t start_offset = offset_in_page(eb->start);
5375         unsigned long i = (start_offset + start) >> PAGE_SHIFT;
5376         unsigned long end_i = (start_offset + start + min_len - 1) >>
5377                 PAGE_SHIFT;
5378
5379         if (start + min_len > eb->len) {
5380                 WARN(1, KERN_ERR "btrfs bad mapping eb start %llu len %lu, wanted %lu %lu\n",
5381                        eb->start, eb->len, start, min_len);
5382                 return -EINVAL;
5383         }
5384
5385         if (i != end_i)
5386                 return 1;
5387
5388         if (i == 0) {
5389                 offset = start_offset;
5390                 *map_start = 0;
5391         } else {
5392                 offset = 0;
5393                 *map_start = ((u64)i << PAGE_SHIFT) - start_offset;
5394         }
5395
5396         p = eb->pages[i];
5397         kaddr = page_address(p);
5398         *map = kaddr + offset;
5399         *map_len = PAGE_SIZE - offset;
5400         return 0;
5401 }
5402
5403 int memcmp_extent_buffer(const struct extent_buffer *eb, const void *ptrv,
5404                          unsigned long start, unsigned long len)
5405 {
5406         size_t cur;
5407         size_t offset;
5408         struct page *page;
5409         char *kaddr;
5410         char *ptr = (char *)ptrv;
5411         size_t start_offset = offset_in_page(eb->start);
5412         unsigned long i = (start_offset + start) >> PAGE_SHIFT;
5413         int ret = 0;
5414
5415         WARN_ON(start > eb->len);
5416         WARN_ON(start + len > eb->start + eb->len);
5417
5418         offset = offset_in_page(start_offset + start);
5419
5420         while (len > 0) {
5421                 page = eb->pages[i];
5422
5423                 cur = min(len, (PAGE_SIZE - offset));
5424
5425                 kaddr = page_address(page);
5426                 ret = memcmp(ptr, kaddr + offset, cur);
5427                 if (ret)
5428                         break;
5429
5430                 ptr += cur;
5431                 len -= cur;
5432                 offset = 0;
5433                 i++;
5434         }
5435         return ret;
5436 }
5437
5438 void write_extent_buffer_chunk_tree_uuid(struct extent_buffer *eb,
5439                 const void *srcv)
5440 {
5441         char *kaddr;
5442
5443         WARN_ON(!PageUptodate(eb->pages[0]));
5444         kaddr = page_address(eb->pages[0]);
5445         memcpy(kaddr + offsetof(struct btrfs_header, chunk_tree_uuid), srcv,
5446                         BTRFS_FSID_SIZE);
5447 }
5448
5449 void write_extent_buffer_fsid(struct extent_buffer *eb, const void *srcv)
5450 {
5451         char *kaddr;
5452
5453         WARN_ON(!PageUptodate(eb->pages[0]));
5454         kaddr = page_address(eb->pages[0]);
5455         memcpy(kaddr + offsetof(struct btrfs_header, fsid), srcv,
5456                         BTRFS_FSID_SIZE);
5457 }
5458
5459 void write_extent_buffer(struct extent_buffer *eb, const void *srcv,
5460                          unsigned long start, unsigned long len)
5461 {
5462         size_t cur;
5463         size_t offset;
5464         struct page *page;
5465         char *kaddr;
5466         char *src = (char *)srcv;
5467         size_t start_offset = offset_in_page(eb->start);
5468         unsigned long i = (start_offset + start) >> PAGE_SHIFT;
5469
5470         WARN_ON(start > eb->len);
5471         WARN_ON(start + len > eb->start + eb->len);
5472
5473         offset = offset_in_page(start_offset + start);
5474
5475         while (len > 0) {
5476                 page = eb->pages[i];
5477                 WARN_ON(!PageUptodate(page));
5478
5479                 cur = min(len, PAGE_SIZE - offset);
5480                 kaddr = page_address(page);
5481                 memcpy(kaddr + offset, src, cur);
5482
5483                 src += cur;
5484                 len -= cur;
5485                 offset = 0;
5486                 i++;
5487         }
5488 }
5489
5490 void memzero_extent_buffer(struct extent_buffer *eb, unsigned long start,
5491                 unsigned long len)
5492 {
5493         size_t cur;
5494         size_t offset;
5495         struct page *page;
5496         char *kaddr;
5497         size_t start_offset = offset_in_page(eb->start);
5498         unsigned long i = (start_offset + start) >> PAGE_SHIFT;
5499
5500         WARN_ON(start > eb->len);
5501         WARN_ON(start + len > eb->start + eb->len);
5502
5503         offset = offset_in_page(start_offset + start);
5504
5505         while (len > 0) {
5506                 page = eb->pages[i];
5507                 WARN_ON(!PageUptodate(page));
5508
5509                 cur = min(len, PAGE_SIZE - offset);
5510                 kaddr = page_address(page);
5511                 memset(kaddr + offset, 0, cur);
5512
5513                 len -= cur;
5514                 offset = 0;
5515                 i++;
5516         }
5517 }
5518
5519 void copy_extent_buffer_full(struct extent_buffer *dst,
5520                              struct extent_buffer *src)
5521 {
5522         int i;
5523         int num_pages;
5524
5525         ASSERT(dst->len == src->len);
5526
5527         num_pages = num_extent_pages(dst);
5528         for (i = 0; i < num_pages; i++)
5529                 copy_page(page_address(dst->pages[i]),
5530                                 page_address(src->pages[i]));
5531 }
5532
5533 void copy_extent_buffer(struct extent_buffer *dst, struct extent_buffer *src,
5534                         unsigned long dst_offset, unsigned long src_offset,
5535                         unsigned long len)
5536 {
5537         u64 dst_len = dst->len;
5538         size_t cur;
5539         size_t offset;
5540         struct page *page;
5541         char *kaddr;
5542         size_t start_offset = offset_in_page(dst->start);
5543         unsigned long i = (start_offset + dst_offset) >> PAGE_SHIFT;
5544
5545         WARN_ON(src->len != dst_len);
5546
5547         offset = offset_in_page(start_offset + dst_offset);
5548
5549         while (len > 0) {
5550                 page = dst->pages[i];
5551                 WARN_ON(!PageUptodate(page));
5552
5553                 cur = min(len, (unsigned long)(PAGE_SIZE - offset));
5554
5555                 kaddr = page_address(page);
5556                 read_extent_buffer(src, kaddr + offset, src_offset, cur);
5557
5558                 src_offset += cur;
5559                 len -= cur;
5560                 offset = 0;
5561                 i++;
5562         }
5563 }
5564
5565 /*
5566  * eb_bitmap_offset() - calculate the page and offset of the byte containing the
5567  * given bit number
5568  * @eb: the extent buffer
5569  * @start: offset of the bitmap item in the extent buffer
5570  * @nr: bit number
5571  * @page_index: return index of the page in the extent buffer that contains the
5572  * given bit number
5573  * @page_offset: return offset into the page given by page_index
5574  *
5575  * This helper hides the ugliness of finding the byte in an extent buffer which
5576  * contains a given bit.
5577  */
5578 static inline void eb_bitmap_offset(struct extent_buffer *eb,
5579                                     unsigned long start, unsigned long nr,
5580                                     unsigned long *page_index,
5581                                     size_t *page_offset)
5582 {
5583         size_t start_offset = offset_in_page(eb->start);
5584         size_t byte_offset = BIT_BYTE(nr);
5585         size_t offset;
5586
5587         /*
5588          * The byte we want is the offset of the extent buffer + the offset of
5589          * the bitmap item in the extent buffer + the offset of the byte in the
5590          * bitmap item.
5591          */
5592         offset = start_offset + start + byte_offset;
5593
5594         *page_index = offset >> PAGE_SHIFT;
5595         *page_offset = offset_in_page(offset);
5596 }
5597
5598 /**
5599  * extent_buffer_test_bit - determine whether a bit in a bitmap item is set
5600  * @eb: the extent buffer
5601  * @start: offset of the bitmap item in the extent buffer
5602  * @nr: bit number to test
5603  */
5604 int extent_buffer_test_bit(struct extent_buffer *eb, unsigned long start,
5605                            unsigned long nr)
5606 {
5607         u8 *kaddr;
5608         struct page *page;
5609         unsigned long i;
5610         size_t offset;
5611
5612         eb_bitmap_offset(eb, start, nr, &i, &offset);
5613         page = eb->pages[i];
5614         WARN_ON(!PageUptodate(page));
5615         kaddr = page_address(page);
5616         return 1U & (kaddr[offset] >> (nr & (BITS_PER_BYTE - 1)));
5617 }
5618
5619 /**
5620  * extent_buffer_bitmap_set - set an area of a bitmap
5621  * @eb: the extent buffer
5622  * @start: offset of the bitmap item in the extent buffer
5623  * @pos: bit number of the first bit
5624  * @len: number of bits to set
5625  */
5626 void extent_buffer_bitmap_set(struct extent_buffer *eb, unsigned long start,
5627                               unsigned long pos, unsigned long len)
5628 {
5629         u8 *kaddr;
5630         struct page *page;
5631         unsigned long i;
5632         size_t offset;
5633         const unsigned int size = pos + len;
5634         int bits_to_set = BITS_PER_BYTE - (pos % BITS_PER_BYTE);
5635         u8 mask_to_set = BITMAP_FIRST_BYTE_MASK(pos);
5636
5637         eb_bitmap_offset(eb, start, pos, &i, &offset);
5638         page = eb->pages[i];
5639         WARN_ON(!PageUptodate(page));
5640         kaddr = page_address(page);
5641
5642         while (len >= bits_to_set) {
5643                 kaddr[offset] |= mask_to_set;
5644                 len -= bits_to_set;
5645                 bits_to_set = BITS_PER_BYTE;
5646                 mask_to_set = ~0;
5647                 if (++offset >= PAGE_SIZE && len > 0) {
5648                         offset = 0;
5649                         page = eb->pages[++i];
5650                         WARN_ON(!PageUptodate(page));
5651                         kaddr = page_address(page);
5652                 }
5653         }
5654         if (len) {
5655                 mask_to_set &= BITMAP_LAST_BYTE_MASK(size);
5656                 kaddr[offset] |= mask_to_set;
5657         }
5658 }
5659
5660
5661 /**
5662  * extent_buffer_bitmap_clear - clear an area of a bitmap
5663  * @eb: the extent buffer
5664  * @start: offset of the bitmap item in the extent buffer
5665  * @pos: bit number of the first bit
5666  * @len: number of bits to clear
5667  */
5668 void extent_buffer_bitmap_clear(struct extent_buffer *eb, unsigned long start,
5669                                 unsigned long pos, unsigned long len)
5670 {
5671         u8 *kaddr;
5672         struct page *page;
5673         unsigned long i;
5674         size_t offset;
5675         const unsigned int size = pos + len;
5676         int bits_to_clear = BITS_PER_BYTE - (pos % BITS_PER_BYTE);
5677         u8 mask_to_clear = BITMAP_FIRST_BYTE_MASK(pos);
5678
5679         eb_bitmap_offset(eb, start, pos, &i, &offset);
5680         page = eb->pages[i];
5681         WARN_ON(!PageUptodate(page));
5682         kaddr = page_address(page);
5683
5684         while (len >= bits_to_clear) {
5685                 kaddr[offset] &= ~mask_to_clear;
5686                 len -= bits_to_clear;
5687                 bits_to_clear = BITS_PER_BYTE;
5688                 mask_to_clear = ~0;
5689                 if (++offset >= PAGE_SIZE && len > 0) {
5690                         offset = 0;
5691                         page = eb->pages[++i];
5692                         WARN_ON(!PageUptodate(page));
5693                         kaddr = page_address(page);
5694                 }
5695         }
5696         if (len) {
5697                 mask_to_clear &= BITMAP_LAST_BYTE_MASK(size);
5698                 kaddr[offset] &= ~mask_to_clear;
5699         }
5700 }
5701
5702 static inline bool areas_overlap(unsigned long src, unsigned long dst, unsigned long len)
5703 {
5704         unsigned long distance = (src > dst) ? src - dst : dst - src;
5705         return distance < len;
5706 }
5707
5708 static void copy_pages(struct page *dst_page, struct page *src_page,
5709                        unsigned long dst_off, unsigned long src_off,
5710                        unsigned long len)
5711 {
5712         char *dst_kaddr = page_address(dst_page);
5713         char *src_kaddr;
5714         int must_memmove = 0;
5715
5716         if (dst_page != src_page) {
5717                 src_kaddr = page_address(src_page);
5718         } else {
5719                 src_kaddr = dst_kaddr;
5720                 if (areas_overlap(src_off, dst_off, len))
5721                         must_memmove = 1;
5722         }
5723
5724         if (must_memmove)
5725                 memmove(dst_kaddr + dst_off, src_kaddr + src_off, len);
5726         else
5727                 memcpy(dst_kaddr + dst_off, src_kaddr + src_off, len);
5728 }
5729
5730 void memcpy_extent_buffer(struct extent_buffer *dst, unsigned long dst_offset,
5731                            unsigned long src_offset, unsigned long len)
5732 {
5733         struct btrfs_fs_info *fs_info = dst->fs_info;
5734         size_t cur;
5735         size_t dst_off_in_page;
5736         size_t src_off_in_page;
5737         size_t start_offset = offset_in_page(dst->start);
5738         unsigned long dst_i;
5739         unsigned long src_i;
5740
5741         if (src_offset + len > dst->len) {
5742                 btrfs_err(fs_info,
5743                         "memmove bogus src_offset %lu move len %lu dst len %lu",
5744                          src_offset, len, dst->len);
5745                 BUG_ON(1);
5746         }
5747         if (dst_offset + len > dst->len) {
5748                 btrfs_err(fs_info,
5749                         "memmove bogus dst_offset %lu move len %lu dst len %lu",
5750                          dst_offset, len, dst->len);
5751                 BUG_ON(1);
5752         }
5753
5754         while (len > 0) {
5755                 dst_off_in_page = offset_in_page(start_offset + dst_offset);
5756                 src_off_in_page = offset_in_page(start_offset + src_offset);
5757
5758                 dst_i = (start_offset + dst_offset) >> PAGE_SHIFT;
5759                 src_i = (start_offset + src_offset) >> PAGE_SHIFT;
5760
5761                 cur = min(len, (unsigned long)(PAGE_SIZE -
5762                                                src_off_in_page));
5763                 cur = min_t(unsigned long, cur,
5764                         (unsigned long)(PAGE_SIZE - dst_off_in_page));
5765
5766                 copy_pages(dst->pages[dst_i], dst->pages[src_i],
5767                            dst_off_in_page, src_off_in_page, cur);
5768
5769                 src_offset += cur;
5770                 dst_offset += cur;
5771                 len -= cur;
5772         }
5773 }
5774
5775 void memmove_extent_buffer(struct extent_buffer *dst, unsigned long dst_offset,
5776                            unsigned long src_offset, unsigned long len)
5777 {
5778         struct btrfs_fs_info *fs_info = dst->fs_info;
5779         size_t cur;
5780         size_t dst_off_in_page;
5781         size_t src_off_in_page;
5782         unsigned long dst_end = dst_offset + len - 1;
5783         unsigned long src_end = src_offset + len - 1;
5784         size_t start_offset = offset_in_page(dst->start);
5785         unsigned long dst_i;
5786         unsigned long src_i;
5787
5788         if (src_offset + len > dst->len) {
5789                 btrfs_err(fs_info,
5790                           "memmove bogus src_offset %lu move len %lu len %lu",
5791                           src_offset, len, dst->len);
5792                 BUG_ON(1);
5793         }
5794         if (dst_offset + len > dst->len) {
5795                 btrfs_err(fs_info,
5796                           "memmove bogus dst_offset %lu move len %lu len %lu",
5797                           dst_offset, len, dst->len);
5798                 BUG_ON(1);
5799         }
5800         if (dst_offset < src_offset) {
5801                 memcpy_extent_buffer(dst, dst_offset, src_offset, len);
5802                 return;
5803         }
5804         while (len > 0) {
5805                 dst_i = (start_offset + dst_end) >> PAGE_SHIFT;
5806                 src_i = (start_offset + src_end) >> PAGE_SHIFT;
5807
5808                 dst_off_in_page = offset_in_page(start_offset + dst_end);
5809                 src_off_in_page = offset_in_page(start_offset + src_end);
5810
5811                 cur = min_t(unsigned long, len, src_off_in_page + 1);
5812                 cur = min(cur, dst_off_in_page + 1);
5813                 copy_pages(dst->pages[dst_i], dst->pages[src_i],
5814                            dst_off_in_page - cur + 1,
5815                            src_off_in_page - cur + 1, cur);
5816
5817                 dst_end -= cur;
5818                 src_end -= cur;
5819                 len -= cur;
5820         }
5821 }
5822
5823 int try_release_extent_buffer(struct page *page)
5824 {
5825         struct extent_buffer *eb;
5826
5827         /*
5828          * We need to make sure nobody is attaching this page to an eb right
5829          * now.
5830          */
5831         spin_lock(&page->mapping->private_lock);
5832         if (!PagePrivate(page)) {
5833                 spin_unlock(&page->mapping->private_lock);
5834                 return 1;
5835         }
5836
5837         eb = (struct extent_buffer *)page->private;
5838         BUG_ON(!eb);
5839
5840         /*
5841          * This is a little awful but should be ok, we need to make sure that
5842          * the eb doesn't disappear out from under us while we're looking at
5843          * this page.
5844          */
5845         spin_lock(&eb->refs_lock);
5846         if (atomic_read(&eb->refs) != 1 || extent_buffer_under_io(eb)) {
5847                 spin_unlock(&eb->refs_lock);
5848                 spin_unlock(&page->mapping->private_lock);
5849                 return 0;
5850         }
5851         spin_unlock(&page->mapping->private_lock);
5852
5853         /*
5854          * If tree ref isn't set then we know the ref on this eb is a real ref,
5855          * so just return, this page will likely be freed soon anyway.
5856          */
5857         if (!test_and_clear_bit(EXTENT_BUFFER_TREE_REF, &eb->bflags)) {
5858                 spin_unlock(&eb->refs_lock);
5859                 return 0;
5860         }
5861
5862         return release_extent_buffer(eb);
5863 }