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-io-tree.h"
  18 #include "extent_map.h"
  19 #include "ctree.h"
  20 #include "btrfs_inode.h"
  21 #include "volumes.h"
  22 #include "check-integrity.h"
  23 #include "locking.h"
  24 #include "rcu-string.h"
  25 #include "backref.h"
  26 #include "disk-io.h"
  27
  28 static struct kmem_cache *extent_state_cache;
  29 static struct kmem_cache *extent_buffer_cache;
  30 static struct bio_set btrfs_bioset;
  31
  32 static inline bool extent_state_in_tree(const struct extent_state *state)
  33 {
  34         return !RB_EMPTY_NODE(&state->rb_node);
  35 }
  36
  37 #ifdef CONFIG_BTRFS_DEBUG
  38 static LIST_HEAD(states);
  39 static DEFINE_SPINLOCK(leak_lock);
  40
  41 static inline void btrfs_leak_debug_add(spinlock_t *lock,
  42                                         struct list_head *new,
  43                                         struct list_head *head)
  44 {
  45         unsigned long flags;
  46
  47         spin_lock_irqsave(lock, flags);
  48         list_add(new, head);
  49         spin_unlock_irqrestore(lock, flags);
  50 }
  51
  52 static inline void btrfs_leak_debug_del(spinlock_t *lock,
  53                                         struct list_head *entry)
  54 {
  55         unsigned long flags;
  56
  57         spin_lock_irqsave(lock, flags);
  58         list_del(entry);
  59         spin_unlock_irqrestore(lock, flags);
  60 }
  61
  62 void btrfs_extent_buffer_leak_debug_check(struct btrfs_fs_info *fs_info)
  63 {
  64         struct extent_buffer *eb;
  65         unsigned long flags;
  66
  67         /*
  68          * If we didn't get into open_ctree our allocated_ebs will not be
  69          * initialized, so just skip this.
  70          */
  71         if (!fs_info->allocated_ebs.next)
  72                 return;
  73
  74         spin_lock_irqsave(&fs_info->eb_leak_lock, flags);
  75         while (!list_empty(&fs_info->allocated_ebs)) {
  76                 eb = list_first_entry(&fs_info->allocated_ebs,
  77                                       struct extent_buffer, leak_list);
  78                 pr_err(
  79         "BTRFS: buffer leak start %llu len %lu refs %d bflags %lu owner %llu\n",
  80                        eb->start, eb->len, atomic_read(&eb->refs), eb->bflags,
  81                        btrfs_header_owner(eb));
  82                 list_del(&eb->leak_list);
  83                 kmem_cache_free(extent_buffer_cache, eb);
  84         }
  85         spin_unlock_irqrestore(&fs_info->eb_leak_lock, flags);
  86 }
  87
  88 static inline void btrfs_extent_state_leak_debug_check(void)
  89 {
  90         struct extent_state *state;
  91
  92         while (!list_empty(&states)) {
  93                 state = list_entry(states.next, struct extent_state, leak_list);
  94                 pr_err("BTRFS: state leak: start %llu end %llu state %u in tree %d refs %d\n",
  95                        state->start, state->end, state->state,
  96                        extent_state_in_tree(state),
  97                        refcount_read(&state->refs));
  98                 list_del(&state->leak_list);
  99                 kmem_cache_free(extent_state_cache, state);
 100         }
 101 }
 102
 103 #define btrfs_debug_check_extent_io_range(tree, start, end)             \
 104         __btrfs_debug_check_extent_io_range(__func__, (tree), (start), (end))
 105 static inline void __btrfs_debug_check_extent_io_range(const char *caller,
 106                 struct extent_io_tree *tree, u64 start, u64 end)
 107 {
 108         struct inode *inode = tree->private_data;
 109         u64 isize;
 110
 111         if (!inode || !is_data_inode(inode))
 112                 return;
 113
 114         isize = i_size_read(inode);
 115         if (end >= PAGE_SIZE && (end % 2) == 0 && end != isize - 1) {
 116                 btrfs_debug_rl(BTRFS_I(inode)->root->fs_info,
 117                     "%s: ino %llu isize %llu odd range [%llu,%llu]",
 118                         caller, btrfs_ino(BTRFS_I(inode)), isize, start, end);
 119         }
 120 }
 121 #else
 122 #define btrfs_leak_debug_add(lock, new, head)   do {} while (0)
 123 #define btrfs_leak_debug_del(lock, entry)       do {} while (0)
 124 #define btrfs_extent_state_leak_debug_check()   do {} while (0)
 125 #define btrfs_debug_check_extent_io_range(c, s, e)      do {} while (0)
 126 #endif
 127
 128 struct tree_entry {
 129         u64 start;
 130         u64 end;
 131         struct rb_node rb_node;
 132 };
 133
 134 struct extent_page_data {
 135         struct bio *bio;
 136         /* tells writepage not to lock the state bits for this range
 137          * it still does the unlocking
 138          */
 139         unsigned int extent_locked:1;
 140
 141         /* tells the submit_bio code to use REQ_SYNC */
 142         unsigned int sync_io:1;
 143 };
 144
 145 static int add_extent_changeset(struct extent_state *state, u32 bits,
 146                                  struct extent_changeset *changeset,
 147                                  int set)
 148 {
 149         int ret;
 150
 151         if (!changeset)
 152                 return 0;
 153         if (set && (state->state & bits) == bits)
 154                 return 0;
 155         if (!set && (state->state & bits) == 0)
 156                 return 0;
 157         changeset->bytes_changed += state->end - state->start + 1;
 158         ret = ulist_add(&changeset->range_changed, state->start, state->end,
 159                         GFP_ATOMIC);
 160         return ret;
 161 }
 162
 163 int __must_check submit_one_bio(struct bio *bio, int mirror_num,
 164                                 unsigned long bio_flags)
 165 {
 166         blk_status_t ret = 0;
 167         struct extent_io_tree *tree = bio->bi_private;
 168
 169         bio->bi_private = NULL;
 170
 171         if (is_data_inode(tree->private_data))
 172                 ret = btrfs_submit_data_bio(tree->private_data, bio, mirror_num,
 173                                             bio_flags);
 174         else
 175                 ret = btrfs_submit_metadata_bio(tree->private_data, bio,
 176                                                 mirror_num, bio_flags);
 177
 178         return blk_status_to_errno(ret);
 179 }
 180
 181 /* Cleanup unsubmitted bios */
 182 static void end_write_bio(struct extent_page_data *epd, int ret)
 183 {
 184         if (epd->bio) {
 185                 epd->bio->bi_status = errno_to_blk_status(ret);
 186                 bio_endio(epd->bio);
 187                 epd->bio = NULL;
 188         }
 189 }
 190
 191 /*
 192  * Submit bio from extent page data via submit_one_bio
 193  *
 194  * Return 0 if everything is OK.
 195  * Return <0 for error.
 196  */
 197 static int __must_check flush_write_bio(struct extent_page_data *epd)
 198 {
 199         int ret = 0;
 200
 201         if (epd->bio) {
 202                 ret = submit_one_bio(epd->bio, 0, 0);
 203                 /*
 204                  * Clean up of epd->bio is handled by its endio function.
 205                  * And endio is either triggered by successful bio execution
 206                  * or the error handler of submit bio hook.
 207                  * So at this point, no matter what happened, we don't need
 208                  * to clean up epd->bio.
 209                  */
 210                 epd->bio = NULL;
 211         }
 212         return ret;
 213 }
 214
 215 int __init extent_state_cache_init(void)
 216 {
 217         extent_state_cache = kmem_cache_create("btrfs_extent_state",
 218                         sizeof(struct extent_state), 0,
 219                         SLAB_MEM_SPREAD, NULL);
 220         if (!extent_state_cache)
 221                 return -ENOMEM;
 222         return 0;
 223 }
 224
 225 int __init extent_io_init(void)
 226 {
 227         extent_buffer_cache = kmem_cache_create("btrfs_extent_buffer",
 228                         sizeof(struct extent_buffer), 0,
 229                         SLAB_MEM_SPREAD, NULL);
 230         if (!extent_buffer_cache)
 231                 return -ENOMEM;
 232
 233         if (bioset_init(&btrfs_bioset, BIO_POOL_SIZE,
 234                         offsetof(struct btrfs_io_bio, bio),
 235                         BIOSET_NEED_BVECS))
 236                 goto free_buffer_cache;
 237
 238         if (bioset_integrity_create(&btrfs_bioset, BIO_POOL_SIZE))
 239                 goto free_bioset;
 240
 241         return 0;
 242
 243 free_bioset:
 244         bioset_exit(&btrfs_bioset);
 245
 246 free_buffer_cache:
 247         kmem_cache_destroy(extent_buffer_cache);
 248         extent_buffer_cache = NULL;
 249         return -ENOMEM;
 250 }
 251
 252 void __cold extent_state_cache_exit(void)
 253 {
 254         btrfs_extent_state_leak_debug_check();
 255         kmem_cache_destroy(extent_state_cache);
 256 }
 257
 258 void __cold extent_io_exit(void)
 259 {
 260         /*
 261          * Make sure all delayed rcu free are flushed before we
 262          * destroy caches.
 263          */
 264         rcu_barrier();
 265         kmem_cache_destroy(extent_buffer_cache);
 266         bioset_exit(&btrfs_bioset);
 267 }
 268
 269 /*
 270  * For the file_extent_tree, we want to hold the inode lock when we lookup and
 271  * update the disk_i_size, but lockdep will complain because our io_tree we hold
 272  * the tree lock and get the inode lock when setting delalloc.  These two things
 273  * are unrelated, so make a class for the file_extent_tree so we don't get the
 274  * two locking patterns mixed up.
 275  */
 276 static struct lock_class_key file_extent_tree_class;
 277
 278 void extent_io_tree_init(struct btrfs_fs_info *fs_info,
 279                          struct extent_io_tree *tree, unsigned int owner,
 280                          void *private_data)
 281 {
 282         tree->fs_info = fs_info;
 283         tree->state = RB_ROOT;
 284         tree->dirty_bytes = 0;
 285         spin_lock_init(&tree->lock);
 286         tree->private_data = private_data;
 287         tree->owner = owner;
 288         if (owner == IO_TREE_INODE_FILE_EXTENT)
 289                 lockdep_set_class(&tree->lock, &file_extent_tree_class);
 290 }
 291
 292 void extent_io_tree_release(struct extent_io_tree *tree)
 293 {
 294         spin_lock(&tree->lock);
 295         /*
 296          * Do a single barrier for the waitqueue_active check here, the state
 297          * of the waitqueue should not change once extent_io_tree_release is
 298          * called.
 299          */
 300         smp_mb();
 301         while (!RB_EMPTY_ROOT(&tree->state)) {
 302                 struct rb_node *node;
 303                 struct extent_state *state;
 304
 305                 node = rb_first(&tree->state);
 306                 state = rb_entry(node, struct extent_state, rb_node);
 307                 rb_erase(&state->rb_node, &tree->state);
 308                 RB_CLEAR_NODE(&state->rb_node);
 309                 /*
 310                  * btree io trees aren't supposed to have tasks waiting for
 311                  * changes in the flags of extent states ever.
 312                  */
 313                 ASSERT(!waitqueue_active(&state->wq));
 314                 free_extent_state(state);
 315
 316                 cond_resched_lock(&tree->lock);
 317         }
 318         spin_unlock(&tree->lock);
 319 }
 320
 321 static struct extent_state *alloc_extent_state(gfp_t mask)
 322 {
 323         struct extent_state *state;
 324
 325         /*
 326          * The given mask might be not appropriate for the slab allocator,
 327          * drop the unsupported bits
 328          */
 329         mask &= ~(__GFP_DMA32|__GFP_HIGHMEM);
 330         state = kmem_cache_alloc(extent_state_cache, mask);
 331         if (!state)
 332                 return state;
 333         state->state = 0;
 334         state->failrec = NULL;
 335         RB_CLEAR_NODE(&state->rb_node);
 336         btrfs_leak_debug_add(&leak_lock, &state->leak_list, &states);
 337         refcount_set(&state->refs, 1);
 338         init_waitqueue_head(&state->wq);
 339         trace_alloc_extent_state(state, mask, _RET_IP_);
 340         return state;
 341 }
 342
 343 void free_extent_state(struct extent_state *state)
 344 {
 345         if (!state)
 346                 return;
 347         if (refcount_dec_and_test(&state->refs)) {
 348                 WARN_ON(extent_state_in_tree(state));
 349                 btrfs_leak_debug_del(&leak_lock, &state->leak_list);
 350                 trace_free_extent_state(state, _RET_IP_);
 351                 kmem_cache_free(extent_state_cache, state);
 352         }
 353 }
 354
 355 static struct rb_node *tree_insert(struct rb_root *root,
 356                                    struct rb_node *search_start,
 357                                    u64 offset,
 358                                    struct rb_node *node,
 359                                    struct rb_node ***p_in,
 360                                    struct rb_node **parent_in)
 361 {
 362         struct rb_node **p;
 363         struct rb_node *parent = NULL;
 364         struct tree_entry *entry;
 365
 366         if (p_in && parent_in) {
 367                 p = *p_in;
 368                 parent = *parent_in;
 369                 goto do_insert;
 370         }
 371
 372         p = search_start ? &search_start : &root->rb_node;
 373         while (*p) {
 374                 parent = *p;
 375                 entry = rb_entry(parent, struct tree_entry, rb_node);
 376
 377                 if (offset < entry->start)
 378                         p = &(*p)->rb_left;
 379                 else if (offset > entry->end)
 380                         p = &(*p)->rb_right;
 381                 else
 382                         return parent;
 383         }
 384
 385 do_insert:
 386         rb_link_node(node, parent, p);
 387         rb_insert_color(node, root);
 388         return NULL;
 389 }
 390
 391 /**
 392  * __etree_search - searche @tree for an entry that contains @offset. Such
 393  * entry would have entry->start <= offset && entry->end >= offset.
 394  *
 395  * @tree - the tree to search
 396  * @offset - offset that should fall within an entry in @tree
 397  * @next_ret - pointer to the first entry whose range ends after @offset
 398  * @prev - pointer to the first entry whose range begins before @offset
 399  * @p_ret - pointer where new node should be anchored (used when inserting an
 400  *          entry in the tree)
 401  * @parent_ret - points to entry which would have been the parent of the entry,
 402  *               containing @offset
 403  *
 404  * This function returns a pointer to the entry that contains @offset byte
 405  * address. If no such entry exists, then NULL is returned and the other
 406  * pointer arguments to the function are filled, otherwise the found entry is
 407  * returned and other pointers are left untouched.
 408  */
 409 static struct rb_node *__etree_search(struct extent_io_tree *tree, u64 offset,
 410                                       struct rb_node **next_ret,
 411                                       struct rb_node **prev_ret,
 412                                       struct rb_node ***p_ret,
 413                                       struct rb_node **parent_ret)
 414 {
 415         struct rb_root *root = &tree->state;
 416         struct rb_node **n = &root->rb_node;
 417         struct rb_node *prev = NULL;
 418         struct rb_node *orig_prev = NULL;
 419         struct tree_entry *entry;
 420         struct tree_entry *prev_entry = NULL;
 421
 422         while (*n) {
 423                 prev = *n;
 424                 entry = rb_entry(prev, struct tree_entry, rb_node);
 425                 prev_entry = entry;
 426
 427                 if (offset < entry->start)
 428                         n = &(*n)->rb_left;
 429                 else if (offset > entry->end)
 430                         n = &(*n)->rb_right;
 431                 else
 432                         return *n;
 433         }
 434
 435         if (p_ret)
 436                 *p_ret = n;
 437         if (parent_ret)
 438                 *parent_ret = prev;
 439
 440         if (next_ret) {
 441                 orig_prev = prev;
 442                 while (prev && offset > prev_entry->end) {
 443                         prev = rb_next(prev);
 444                         prev_entry = rb_entry(prev, struct tree_entry, rb_node);
 445                 }
 446                 *next_ret = prev;
 447                 prev = orig_prev;
 448         }
 449
 450         if (prev_ret) {
 451                 prev_entry = rb_entry(prev, struct tree_entry, rb_node);
 452                 while (prev && offset < prev_entry->start) {
 453                         prev = rb_prev(prev);
 454                         prev_entry = rb_entry(prev, struct tree_entry, rb_node);
 455                 }
 456                 *prev_ret = prev;
 457         }
 458         return NULL;
 459 }
 460
 461 static inline struct rb_node *
 462 tree_search_for_insert(struct extent_io_tree *tree,
 463                        u64 offset,
 464                        struct rb_node ***p_ret,
 465                        struct rb_node **parent_ret)
 466 {
 467         struct rb_node *next= NULL;
 468         struct rb_node *ret;
 469
 470         ret = __etree_search(tree, offset, &next, NULL, p_ret, parent_ret);
 471         if (!ret)
 472                 return next;
 473         return ret;
 474 }
 475
 476 static inline struct rb_node *tree_search(struct extent_io_tree *tree,
 477                                           u64 offset)
 478 {
 479         return tree_search_for_insert(tree, offset, NULL, NULL);
 480 }
 481
 482 /*
 483  * utility function to look for merge candidates inside a given range.
 484  * Any extents with matching state are merged together into a single
 485  * extent in the tree.  Extents with EXTENT_IO in their state field
 486  * are not merged because the end_io handlers need to be able to do
 487  * operations on them without sleeping (or doing allocations/splits).
 488  *
 489  * This should be called with the tree lock held.
 490  */
 491 static void merge_state(struct extent_io_tree *tree,
 492                         struct extent_state *state)
 493 {
 494         struct extent_state *other;
 495         struct rb_node *other_node;
 496
 497         if (state->state & (EXTENT_LOCKED | EXTENT_BOUNDARY))
 498                 return;
 499
 500         other_node = rb_prev(&state->rb_node);
 501         if (other_node) {
 502                 other = rb_entry(other_node, struct extent_state, rb_node);
 503                 if (other->end == state->start - 1 &&
 504                     other->state == state->state) {
 505                         if (tree->private_data &&
 506                             is_data_inode(tree->private_data))
 507                                 btrfs_merge_delalloc_extent(tree->private_data,
 508                                                             state, other);
 509                         state->start = other->start;
 510                         rb_erase(&other->rb_node, &tree->state);
 511                         RB_CLEAR_NODE(&other->rb_node);
 512                         free_extent_state(other);
 513                 }
 514         }
 515         other_node = rb_next(&state->rb_node);
 516         if (other_node) {
 517                 other = rb_entry(other_node, struct extent_state, rb_node);
 518                 if (other->start == state->end + 1 &&
 519                     other->state == state->state) {
 520                         if (tree->private_data &&
 521                             is_data_inode(tree->private_data))
 522                                 btrfs_merge_delalloc_extent(tree->private_data,
 523                                                             state, other);
 524                         state->end = other->end;
 525                         rb_erase(&other->rb_node, &tree->state);
 526                         RB_CLEAR_NODE(&other->rb_node);
 527                         free_extent_state(other);
 528                 }
 529         }
 530 }
 531
 532 static void set_state_bits(struct extent_io_tree *tree,
 533                            struct extent_state *state, u32 *bits,
 534                            struct extent_changeset *changeset);
 535
 536 /*
 537  * insert an extent_state struct into the tree.  'bits' are set on the
 538  * struct before it is inserted.
 539  *
 540  * This may return -EEXIST if the extent is already there, in which case the
 541  * state struct is freed.
 542  *
 543  * The tree lock is not taken internally.  This is a utility function and
 544  * probably isn't what you want to call (see set/clear_extent_bit).
 545  */
 546 static int insert_state(struct extent_io_tree *tree,
 547                         struct extent_state *state, u64 start, u64 end,
 548                         struct rb_node ***p,
 549                         struct rb_node **parent,
 550                         u32 *bits, struct extent_changeset *changeset)
 551 {
 552         struct rb_node *node;
 553
 554         if (end < start) {
 555                 btrfs_err(tree->fs_info,
 556                         "insert state: end < start %llu %llu", end, start);
 557                 WARN_ON(1);
 558         }
 559         state->start = start;
 560         state->end = end;
 561
 562         set_state_bits(tree, state, bits, changeset);
 563
 564         node = tree_insert(&tree->state, NULL, end, &state->rb_node, p, parent);
 565         if (node) {
 566                 struct extent_state *found;
 567                 found = rb_entry(node, struct extent_state, rb_node);
 568                 btrfs_err(tree->fs_info,
 569                        "found node %llu %llu on insert of %llu %llu",
 570                        found->start, found->end, start, end);
 571                 return -EEXIST;
 572         }
 573         merge_state(tree, state);
 574         return 0;
 575 }
 576
 577 /*
 578  * split a given extent state struct in two, inserting the preallocated
 579  * struct 'prealloc' as the newly created second half.  'split' indicates an
 580  * offset inside 'orig' where it should be split.
 581  *
 582  * Before calling,
 583  * the tree has 'orig' at [orig->start, orig->end].  After calling, there
 584  * are two extent state structs in the tree:
 585  * prealloc: [orig->start, split - 1]
 586  * orig: [ split, orig->end ]
 587  *
 588  * The tree locks are not taken by this function. They need to be held
 589  * by the caller.
 590  */
 591 static int split_state(struct extent_io_tree *tree, struct extent_state *orig,
 592                        struct extent_state *prealloc, u64 split)
 593 {
 594         struct rb_node *node;
 595
 596         if (tree->private_data && is_data_inode(tree->private_data))
 597                 btrfs_split_delalloc_extent(tree->private_data, orig, split);
 598
 599         prealloc->start = orig->start;
 600         prealloc->end = split - 1;
 601         prealloc->state = orig->state;
 602         orig->start = split;
 603
 604         node = tree_insert(&tree->state, &orig->rb_node, prealloc->end,
 605                            &prealloc->rb_node, NULL, NULL);
 606         if (node) {
 607                 free_extent_state(prealloc);
 608                 return -EEXIST;
 609         }
 610         return 0;
 611 }
 612
 613 static struct extent_state *next_state(struct extent_state *state)
 614 {
 615         struct rb_node *next = rb_next(&state->rb_node);
 616         if (next)
 617                 return rb_entry(next, struct extent_state, rb_node);
 618         else
 619                 return NULL;
 620 }
 621
 622 /*
 623  * utility function to clear some bits in an extent state struct.
 624  * it will optionally wake up anyone waiting on this state (wake == 1).
 625  *
 626  * If no bits are set on the state struct after clearing things, the
 627  * struct is freed and removed from the tree
 628  */
 629 static struct extent_state *clear_state_bit(struct extent_io_tree *tree,
 630                                             struct extent_state *state,
 631                                             u32 *bits, int wake,
 632                                             struct extent_changeset *changeset)
 633 {
 634         struct extent_state *next;
 635         u32 bits_to_clear = *bits & ~EXTENT_CTLBITS;
 636         int ret;
 637
 638         if ((bits_to_clear & EXTENT_DIRTY) && (state->state & EXTENT_DIRTY)) {
 639                 u64 range = state->end - state->start + 1;
 640                 WARN_ON(range > tree->dirty_bytes);
 641                 tree->dirty_bytes -= range;
 642         }
 643
 644         if (tree->private_data && is_data_inode(tree->private_data))
 645                 btrfs_clear_delalloc_extent(tree->private_data, state, bits);
 646
 647         ret = add_extent_changeset(state, bits_to_clear, changeset, 0);
 648         BUG_ON(ret < 0);
 649         state->state &= ~bits_to_clear;
 650         if (wake)
 651                 wake_up(&state->wq);
 652         if (state->state == 0) {
 653                 next = next_state(state);
 654                 if (extent_state_in_tree(state)) {
 655                         rb_erase(&state->rb_node, &tree->state);
 656                         RB_CLEAR_NODE(&state->rb_node);
 657                         free_extent_state(state);
 658                 } else {
 659                         WARN_ON(1);
 660                 }
 661         } else {
 662                 merge_state(tree, state);
 663                 next = next_state(state);
 664         }
 665         return next;
 666 }
 667
 668 static struct extent_state *
 669 alloc_extent_state_atomic(struct extent_state *prealloc)
 670 {
 671         if (!prealloc)
 672                 prealloc = alloc_extent_state(GFP_ATOMIC);
 673
 674         return prealloc;
 675 }
 676
 677 static void extent_io_tree_panic(struct extent_io_tree *tree, int err)
 678 {
 679         btrfs_panic(tree->fs_info, err,
 680         "locking error: extent tree was modified by another thread while locked");
 681 }
 682
 683 /*
 684  * clear some bits on a range in the tree.  This may require splitting
 685  * or inserting elements in the tree, so the gfp mask is used to
 686  * indicate which allocations or sleeping are allowed.
 687  *
 688  * pass 'wake' == 1 to kick any sleepers, and 'delete' == 1 to remove
 689  * the given range from the tree regardless of state (ie for truncate).
 690  *
 691  * the range [start, end] is inclusive.
 692  *
 693  * This takes the tree lock, and returns 0 on success and < 0 on error.
 694  */
 695 int __clear_extent_bit(struct extent_io_tree *tree, u64 start, u64 end,
 696                        u32 bits, int wake, int delete,
 697                        struct extent_state **cached_state,
 698                        gfp_t mask, struct extent_changeset *changeset)
 699 {
 700         struct extent_state *state;
 701         struct extent_state *cached;
 702         struct extent_state *prealloc = NULL;
 703         struct rb_node *node;
 704         u64 last_end;
 705         int err;
 706         int clear = 0;
 707
 708         btrfs_debug_check_extent_io_range(tree, start, end);
 709         trace_btrfs_clear_extent_bit(tree, start, end - start + 1, bits);
 710
 711         if (bits & EXTENT_DELALLOC)
 712                 bits |= EXTENT_NORESERVE;
 713
 714         if (delete)
 715                 bits |= ~EXTENT_CTLBITS;
 716
 717         if (bits & (EXTENT_LOCKED | EXTENT_BOUNDARY))
 718                 clear = 1;
 719 again:
 720         if (!prealloc && gfpflags_allow_blocking(mask)) {
 721                 /*
 722                  * Don't care for allocation failure here because we might end
 723                  * up not needing the pre-allocated extent state at all, which
 724                  * is the case if we only have in the tree extent states that
 725                  * cover our input range and don't cover too any other range.
 726                  * If we end up needing a new extent state we allocate it later.
 727                  */
 728                 prealloc = alloc_extent_state(mask);
 729         }
 730
 731         spin_lock(&tree->lock);
 732         if (cached_state) {
 733                 cached = *cached_state;
 734
 735                 if (clear) {
 736                         *cached_state = NULL;
 737                         cached_state = NULL;
 738                 }
 739
 740                 if (cached && extent_state_in_tree(cached) &&
 741                     cached->start <= start && cached->end > start) {
 742                         if (clear)
 743                                 refcount_dec(&cached->refs);
 744                         state = cached;
 745                         goto hit_next;
 746                 }
 747                 if (clear)
 748                         free_extent_state(cached);
 749         }
 750         /*
 751          * this search will find the extents that end after
 752          * our range starts
 753          */
 754         node = tree_search(tree, start);
 755         if (!node)
 756                 goto out;
 757         state = rb_entry(node, struct extent_state, rb_node);
 758 hit_next:
 759         if (state->start > end)
 760                 goto out;
 761         WARN_ON(state->end < start);
 762         last_end = state->end;
 763
 764         /* the state doesn't have the wanted bits, go ahead */
 765         if (!(state->state & bits)) {
 766                 state = next_state(state);
 767                 goto next;
 768         }
 769
 770         /*
 771          *     | ---- desired range ---- |
 772          *  | state | or
 773          *  | ------------- state -------------- |
 774          *
 775          * We need to split the extent we found, and may flip
 776          * bits on second half.
 777          *
 778          * If the extent we found extends past our range, we
 779          * just split and search again.  It'll get split again
 780          * the next time though.
 781          *
 782          * If the extent we found is inside our range, we clear
 783          * the desired bit on it.
 784          */
 785
 786         if (state->start < start) {
 787                 prealloc = alloc_extent_state_atomic(prealloc);
 788                 BUG_ON(!prealloc);
 789                 err = split_state(tree, state, prealloc, start);
 790                 if (err)
 791                         extent_io_tree_panic(tree, err);
 792
 793                 prealloc = NULL;
 794                 if (err)
 795                         goto out;
 796                 if (state->end <= end) {
 797                         state = clear_state_bit(tree, state, &bits, wake,
 798                                                 changeset);
 799                         goto next;
 800                 }
 801                 goto search_again;
 802         }
 803         /*
 804          * | ---- desired range ---- |
 805          *                        | state |
 806          * We need to split the extent, and clear the bit
 807          * on the first half
 808          */
 809         if (state->start <= end && state->end > end) {
 810                 prealloc = alloc_extent_state_atomic(prealloc);
 811                 BUG_ON(!prealloc);
 812                 err = split_state(tree, state, prealloc, end + 1);
 813                 if (err)
 814                         extent_io_tree_panic(tree, err);
 815
 816                 if (wake)
 817                         wake_up(&state->wq);
 818
 819                 clear_state_bit(tree, prealloc, &bits, wake, changeset);
 820
 821                 prealloc = NULL;
 822                 goto out;
 823         }
 824
 825         state = clear_state_bit(tree, state, &bits, wake, changeset);
 826 next:
 827         if (last_end == (u64)-1)
 828                 goto out;
 829         start = last_end + 1;
 830         if (start <= end && state && !need_resched())
 831                 goto hit_next;
 832
 833 search_again:
 834         if (start > end)
 835                 goto out;
 836         spin_unlock(&tree->lock);
 837         if (gfpflags_allow_blocking(mask))
 838                 cond_resched();
 839         goto again;
 840
 841 out:
 842         spin_unlock(&tree->lock);
 843         if (prealloc)
 844                 free_extent_state(prealloc);
 845
 846         return 0;
 847
 848 }
 849
 850 static void wait_on_state(struct extent_io_tree *tree,
 851                           struct extent_state *state)
 852                 __releases(tree->lock)
 853                 __acquires(tree->lock)
 854 {
 855         DEFINE_WAIT(wait);
 856         prepare_to_wait(&state->wq, &wait, TASK_UNINTERRUPTIBLE);
 857         spin_unlock(&tree->lock);
 858         schedule();
 859         spin_lock(&tree->lock);
 860         finish_wait(&state->wq, &wait);
 861 }
 862
 863 /*
 864  * waits for one or more bits to clear on a range in the state tree.
 865  * The range [start, end] is inclusive.
 866  * The tree lock is taken by this function
 867  */
 868 static void wait_extent_bit(struct extent_io_tree *tree, u64 start, u64 end,
 869                             u32 bits)
 870 {
 871         struct extent_state *state;
 872         struct rb_node *node;
 873
 874         btrfs_debug_check_extent_io_range(tree, start, end);
 875
 876         spin_lock(&tree->lock);
 877 again:
 878         while (1) {
 879                 /*
 880                  * this search will find all the extents that end after
 881                  * our range starts
 882                  */
 883                 node = tree_search(tree, start);
 884 process_node:
 885                 if (!node)
 886                         break;
 887
 888                 state = rb_entry(node, struct extent_state, rb_node);
 889
 890                 if (state->start > end)
 891                         goto out;
 892
 893                 if (state->state & bits) {
 894                         start = state->start;
 895                         refcount_inc(&state->refs);
 896                         wait_on_state(tree, state);
 897                         free_extent_state(state);
 898                         goto again;
 899                 }
 900                 start = state->end + 1;
 901
 902                 if (start > end)
 903                         break;
 904
 905                 if (!cond_resched_lock(&tree->lock)) {
 906                         node = rb_next(node);
 907                         goto process_node;
 908                 }
 909         }
 910 out:
 911         spin_unlock(&tree->lock);
 912 }
 913
 914 static void set_state_bits(struct extent_io_tree *tree,
 915                            struct extent_state *state,
 916                            u32 *bits, struct extent_changeset *changeset)
 917 {
 918         u32 bits_to_set = *bits & ~EXTENT_CTLBITS;
 919         int ret;
 920
 921         if (tree->private_data && is_data_inode(tree->private_data))
 922                 btrfs_set_delalloc_extent(tree->private_data, state, bits);
 923
 924         if ((bits_to_set & EXTENT_DIRTY) && !(state->state & EXTENT_DIRTY)) {
 925                 u64 range = state->end - state->start + 1;
 926                 tree->dirty_bytes += range;
 927         }
 928         ret = add_extent_changeset(state, bits_to_set, changeset, 1);
 929         BUG_ON(ret < 0);
 930         state->state |= bits_to_set;
 931 }
 932
 933 static void cache_state_if_flags(struct extent_state *state,
 934                                  struct extent_state **cached_ptr,
 935                                  unsigned flags)
 936 {
 937         if (cached_ptr && !(*cached_ptr)) {
 938                 if (!flags || (state->state & flags)) {
 939                         *cached_ptr = state;
 940                         refcount_inc(&state->refs);
 941                 }
 942         }
 943 }
 944
 945 static void cache_state(struct extent_state *state,
 946                         struct extent_state **cached_ptr)
 947 {
 948         return cache_state_if_flags(state, cached_ptr,
 949                                     EXTENT_LOCKED | EXTENT_BOUNDARY);
 950 }
 951
 952 /*
 953  * set some bits on a range in the tree.  This may require allocations or
 954  * sleeping, so the gfp mask is used to indicate what is allowed.
 955  *
 956  * If any of the exclusive bits are set, this will fail with -EEXIST if some
 957  * part of the range already has the desired bits set.  The start of the
 958  * existing range is returned in failed_start in this case.
 959  *
 960  * [start, end] is inclusive This takes the tree lock.
 961  */
 962 int set_extent_bit(struct extent_io_tree *tree, u64 start, u64 end, u32 bits,
 963                    u32 exclusive_bits, u64 *failed_start,
 964                    struct extent_state **cached_state, gfp_t mask,
 965                    struct extent_changeset *changeset)
 966 {
 967         struct extent_state *state;
 968         struct extent_state *prealloc = NULL;
 969         struct rb_node *node;
 970         struct rb_node **p;
 971         struct rb_node *parent;
 972         int err = 0;
 973         u64 last_start;
 974         u64 last_end;
 975
 976         btrfs_debug_check_extent_io_range(tree, start, end);
 977         trace_btrfs_set_extent_bit(tree, start, end - start + 1, bits);
 978
 979         if (exclusive_bits)
 980                 ASSERT(failed_start);
 981         else
 982                 ASSERT(failed_start == NULL);
 983 again:
 984         if (!prealloc && gfpflags_allow_blocking(mask)) {
 985                 /*
 986                  * Don't care for allocation failure here because we might end
 987                  * up not needing the pre-allocated extent state at all, which
 988                  * is the case if we only have in the tree extent states that
 989                  * cover our input range and don't cover too any other range.
 990                  * If we end up needing a new extent state we allocate it later.
 991                  */
 992                 prealloc = alloc_extent_state(mask);
 993         }
 994
 995         spin_lock(&tree->lock);
 996         if (cached_state && *cached_state) {
 997                 state = *cached_state;
 998                 if (state->start <= start && state->end > start &&
 999                     extent_state_in_tree(state)) {
1000                         node = &state->rb_node;
1001                         goto hit_next;
1002                 }
1003         }
1004         /*
1005          * this search will find all the extents that end after
1006          * our range starts.
1007          */
1008         node = tree_search_for_insert(tree, start, &p, &parent);
1009         if (!node) {
1010                 prealloc = alloc_extent_state_atomic(prealloc);
1011                 BUG_ON(!prealloc);
1012                 err = insert_state(tree, prealloc, start, end,
1013                                    &p, &parent, &bits, changeset);
1014                 if (err)
1015                         extent_io_tree_panic(tree, err);
1016
1017                 cache_state(prealloc, cached_state);
1018                 prealloc = NULL;
1019                 goto out;
1020         }
1021         state = rb_entry(node, struct extent_state, rb_node);
1022 hit_next:
1023         last_start = state->start;
1024         last_end = state->end;
1025
1026         /*
1027          * | ---- desired range ---- |
1028          * | state |
1029          *
1030          * Just lock what we found and keep going
1031          */
1032         if (state->start == start && state->end <= end) {
1033                 if (state->state & exclusive_bits) {
1034                         *failed_start = state->start;
1035                         err = -EEXIST;
1036                         goto out;
1037                 }
1038
1039                 set_state_bits(tree, state, &bits, changeset);
1040                 cache_state(state, cached_state);
1041                 merge_state(tree, state);
1042                 if (last_end == (u64)-1)
1043                         goto out;
1044                 start = last_end + 1;
1045                 state = next_state(state);
1046                 if (start < end && state && state->start == start &&
1047                     !need_resched())
1048                         goto hit_next;
1049                 goto search_again;
1050         }
1051
1052         /*
1053          *     | ---- desired range ---- |
1054          * | state |
1055          *   or
1056          * | ------------- state -------------- |
1057          *
1058          * We need to split the extent we found, and may flip bits on
1059          * second half.
1060          *
1061          * If the extent we found extends past our
1062          * range, we just split and search again.  It'll get split
1063          * again the next time though.
1064          *
1065          * If the extent we found is inside our range, we set the
1066          * desired bit on it.
1067          */
1068         if (state->start < start) {
1069                 if (state->state & exclusive_bits) {
1070                         *failed_start = start;
1071                         err = -EEXIST;
1072                         goto out;
1073                 }
1074
1075                 /*
1076                  * If this extent already has all the bits we want set, then
1077                  * skip it, not necessary to split it or do anything with it.
1078                  */
1079                 if ((state->state & bits) == bits) {
1080                         start = state->end + 1;
1081                         cache_state(state, cached_state);
1082                         goto search_again;
1083                 }
1084
1085                 prealloc = alloc_extent_state_atomic(prealloc);
1086                 BUG_ON(!prealloc);
1087                 err = split_state(tree, state, prealloc, start);
1088                 if (err)
1089                         extent_io_tree_panic(tree, err);
1090
1091                 prealloc = NULL;
1092                 if (err)
1093                         goto out;
1094                 if (state->end <= end) {
1095                         set_state_bits(tree, state, &bits, changeset);
1096                         cache_state(state, cached_state);
1097                         merge_state(tree, state);
1098                         if (last_end == (u64)-1)
1099                                 goto out;
1100                         start = last_end + 1;
1101                         state = next_state(state);
1102                         if (start < end && state && state->start == start &&
1103                             !need_resched())
1104                                 goto hit_next;
1105                 }
1106                 goto search_again;
1107         }
1108         /*
1109          * | ---- desired range ---- |
1110          *     | state | or               | state |
1111          *
1112          * There's a hole, we need to insert something in it and
1113          * ignore the extent we found.
1114          */
1115         if (state->start > start) {
1116                 u64 this_end;
1117                 if (end < last_start)
1118                         this_end = end;
1119                 else
1120                         this_end = last_start - 1;
1121
1122                 prealloc = alloc_extent_state_atomic(prealloc);
1123                 BUG_ON(!prealloc);
1124
1125                 /*
1126                  * Avoid to free 'prealloc' if it can be merged with
1127                  * the later extent.
1128                  */
1129                 err = insert_state(tree, prealloc, start, this_end,
1130                                    NULL, NULL, &bits, changeset);
1131                 if (err)
1132                         extent_io_tree_panic(tree, err);
1133
1134                 cache_state(prealloc, cached_state);
1135                 prealloc = NULL;
1136                 start = this_end + 1;
1137                 goto search_again;
1138         }
1139         /*
1140          * | ---- desired range ---- |
1141          *                        | state |
1142          * We need to split the extent, and set the bit
1143          * on the first half
1144          */
1145         if (state->start <= end && state->end > end) {
1146                 if (state->state & exclusive_bits) {
1147                         *failed_start = start;
1148                         err = -EEXIST;
1149                         goto out;
1150                 }
1151
1152                 prealloc = alloc_extent_state_atomic(prealloc);
1153                 BUG_ON(!prealloc);
1154                 err = split_state(tree, state, prealloc, end + 1);
1155                 if (err)
1156                         extent_io_tree_panic(tree, err);
1157
1158                 set_state_bits(tree, prealloc, &bits, changeset);
1159                 cache_state(prealloc, cached_state);
1160                 merge_state(tree, prealloc);
1161                 prealloc = NULL;
1162                 goto out;
1163         }
1164
1165 search_again:
1166         if (start > end)
1167                 goto out;
1168         spin_unlock(&tree->lock);
1169         if (gfpflags_allow_blocking(mask))
1170                 cond_resched();
1171         goto again;
1172
1173 out:
1174         spin_unlock(&tree->lock);
1175         if (prealloc)
1176                 free_extent_state(prealloc);
1177
1178         return err;
1179
1180 }
1181
1182 /**
1183  * convert_extent_bit - convert all bits in a given range from one bit to
1184  *                      another
1185  * @tree:       the io tree to search
1186  * @start:      the start offset in bytes
1187  * @end:        the end offset in bytes (inclusive)
1188  * @bits:       the bits to set in this range
1189  * @clear_bits: the bits to clear in this range
1190  * @cached_state:       state that we're going to cache
1191  *
1192  * This will go through and set bits for the given range.  If any states exist
1193  * already in this range they are set with the given bit and cleared of the
1194  * clear_bits.  This is only meant to be used by things that are mergeable, ie
1195  * converting from say DELALLOC to DIRTY.  This is not meant to be used with
1196  * boundary bits like LOCK.
1197  *
1198  * All allocations are done with GFP_NOFS.
1199  */
1200 int convert_extent_bit(struct extent_io_tree *tree, u64 start, u64 end,
1201                        u32 bits, u32 clear_bits,
1202                        struct extent_state **cached_state)
1203 {
1204         struct extent_state *state;
1205         struct extent_state *prealloc = NULL;
1206         struct rb_node *node;
1207         struct rb_node **p;
1208         struct rb_node *parent;
1209         int err = 0;
1210         u64 last_start;
1211         u64 last_end;
1212         bool first_iteration = true;
1213
1214         btrfs_debug_check_extent_io_range(tree, start, end);
1215         trace_btrfs_convert_extent_bit(tree, start, end - start + 1, bits,
1216                                        clear_bits);
1217
1218 again:
1219         if (!prealloc) {
1220                 /*
1221                  * Best effort, don't worry if extent state allocation fails
1222                  * here for the first iteration. We might have a cached state
1223                  * that matches exactly the target range, in which case no
1224                  * extent state allocations are needed. We'll only know this
1225                  * after locking the tree.
1226                  */
1227                 prealloc = alloc_extent_state(GFP_NOFS);
1228                 if (!prealloc && !first_iteration)
1229                         return -ENOMEM;
1230         }
1231
1232         spin_lock(&tree->lock);
1233         if (cached_state && *cached_state) {
1234                 state = *cached_state;
1235                 if (state->start <= start && state->end > start &&
1236                     extent_state_in_tree(state)) {
1237                         node = &state->rb_node;
1238                         goto hit_next;
1239                 }
1240         }
1241
1242         /*
1243          * this search will find all the extents that end after
1244          * our range starts.
1245          */
1246         node = tree_search_for_insert(tree, start, &p, &parent);
1247         if (!node) {
1248                 prealloc = alloc_extent_state_atomic(prealloc);
1249                 if (!prealloc) {
1250                         err = -ENOMEM;
1251                         goto out;
1252                 }
1253                 err = insert_state(tree, prealloc, start, end,
1254                                    &p, &parent, &bits, NULL);
1255                 if (err)
1256                         extent_io_tree_panic(tree, err);
1257                 cache_state(prealloc, cached_state);
1258                 prealloc = NULL;
1259                 goto out;
1260         }
1261         state = rb_entry(node, struct extent_state, rb_node);
1262 hit_next:
1263         last_start = state->start;
1264         last_end = state->end;
1265
1266         /*
1267          * | ---- desired range ---- |
1268          * | state |
1269          *
1270          * Just lock what we found and keep going
1271          */
1272         if (state->start == start && state->end <= end) {
1273                 set_state_bits(tree, state, &bits, NULL);
1274                 cache_state(state, cached_state);
1275                 state = clear_state_bit(tree, state, &clear_bits, 0, NULL);
1276                 if (last_end == (u64)-1)
1277                         goto out;
1278                 start = last_end + 1;
1279                 if (start < end && state && state->start == start &&
1280                     !need_resched())
1281                         goto hit_next;
1282                 goto search_again;
1283         }
1284
1285         /*
1286          *     | ---- desired range ---- |
1287          * | state |
1288          *   or
1289          * | ------------- state -------------- |
1290          *
1291          * We need to split the extent we found, and may flip bits on
1292          * second half.
1293          *
1294          * If the extent we found extends past our
1295          * range, we just split and search again.  It'll get split
1296          * again the next time though.
1297          *
1298          * If the extent we found is inside our range, we set the
1299          * desired bit on it.
1300          */
1301         if (state->start < start) {
1302                 prealloc = alloc_extent_state_atomic(prealloc);
1303                 if (!prealloc) {
1304                         err = -ENOMEM;
1305                         goto out;
1306                 }
1307                 err = split_state(tree, state, prealloc, start);
1308                 if (err)
1309                         extent_io_tree_panic(tree, err);
1310                 prealloc = NULL;
1311                 if (err)
1312                         goto out;
1313                 if (state->end <= end) {
1314                         set_state_bits(tree, state, &bits, NULL);
1315                         cache_state(state, cached_state);
1316                         state = clear_state_bit(tree, state, &clear_bits, 0,
1317                                                 NULL);
1318                         if (last_end == (u64)-1)
1319                                 goto out;
1320                         start = last_end + 1;
1321                         if (start < end && state && state->start == start &&
1322                             !need_resched())
1323                                 goto hit_next;
1324                 }
1325                 goto search_again;
1326         }
1327         /*
1328          * | ---- desired range ---- |
1329          *     | state | or               | state |
1330          *
1331          * There's a hole, we need to insert something in it and
1332          * ignore the extent we found.
1333          */
1334         if (state->start > start) {
1335                 u64 this_end;
1336                 if (end < last_start)
1337                         this_end = end;
1338                 else
1339                         this_end = last_start - 1;
1340
1341                 prealloc = alloc_extent_state_atomic(prealloc);
1342                 if (!prealloc) {
1343                         err = -ENOMEM;
1344                         goto out;
1345                 }
1346
1347                 /*
1348                  * Avoid to free 'prealloc' if it can be merged with
1349                  * the later extent.
1350                  */
1351                 err = insert_state(tree, prealloc, start, this_end,
1352                                    NULL, NULL, &bits, NULL);
1353                 if (err)
1354                         extent_io_tree_panic(tree, err);
1355                 cache_state(prealloc, cached_state);
1356                 prealloc = NULL;
1357                 start = this_end + 1;
1358                 goto search_again;
1359         }
1360         /*
1361          * | ---- desired range ---- |
1362          *                        | state |
1363          * We need to split the extent, and set the bit
1364          * on the first half
1365          */
1366         if (state->start <= end && state->end > end) {
1367                 prealloc = alloc_extent_state_atomic(prealloc);
1368                 if (!prealloc) {
1369                         err = -ENOMEM;
1370                         goto out;
1371                 }
1372
1373                 err = split_state(tree, state, prealloc, end + 1);
1374                 if (err)
1375                         extent_io_tree_panic(tree, err);
1376
1377                 set_state_bits(tree, prealloc, &bits, NULL);
1378                 cache_state(prealloc, cached_state);
1379                 clear_state_bit(tree, prealloc, &clear_bits, 0, NULL);
1380                 prealloc = NULL;
1381                 goto out;
1382         }
1383
1384 search_again:
1385         if (start > end)
1386                 goto out;
1387         spin_unlock(&tree->lock);
1388         cond_resched();
1389         first_iteration = false;
1390         goto again;
1391
1392 out:
1393         spin_unlock(&tree->lock);
1394         if (prealloc)
1395                 free_extent_state(prealloc);
1396
1397         return err;
1398 }
1399
1400 /* wrappers around set/clear extent bit */
1401 int set_record_extent_bits(struct extent_io_tree *tree, u64 start, u64 end,
1402                            u32 bits, struct extent_changeset *changeset)
1403 {
1404         /*
1405          * We don't support EXTENT_LOCKED yet, as current changeset will
1406          * record any bits changed, so for EXTENT_LOCKED case, it will
1407          * either fail with -EEXIST or changeset will record the whole
1408          * range.
1409          */
1410         BUG_ON(bits & EXTENT_LOCKED);
1411
1412         return set_extent_bit(tree, start, end, bits, 0, NULL, NULL, GFP_NOFS,
1413                               changeset);
1414 }
1415
1416 int set_extent_bits_nowait(struct extent_io_tree *tree, u64 start, u64 end,
1417                            u32 bits)
1418 {
1419         return set_extent_bit(tree, start, end, bits, 0, NULL, NULL,
1420                               GFP_NOWAIT, NULL);
1421 }
1422
1423 int clear_extent_bit(struct extent_io_tree *tree, u64 start, u64 end,
1424                      u32 bits, int wake, int delete,
1425                      struct extent_state **cached)
1426 {
1427         return __clear_extent_bit(tree, start, end, bits, wake, delete,
1428                                   cached, GFP_NOFS, NULL);
1429 }
1430
1431 int clear_record_extent_bits(struct extent_io_tree *tree, u64 start, u64 end,
1432                 u32 bits, struct extent_changeset *changeset)
1433 {
1434         /*
1435          * Don't support EXTENT_LOCKED case, same reason as
1436          * set_record_extent_bits().
1437          */
1438         BUG_ON(bits & EXTENT_LOCKED);
1439
1440         return __clear_extent_bit(tree, start, end, bits, 0, 0, NULL, GFP_NOFS,
1441                                   changeset);
1442 }
1443
1444 /*
1445  * either insert or lock state struct between start and end use mask to tell
1446  * us if waiting is desired.
1447  */
1448 int lock_extent_bits(struct extent_io_tree *tree, u64 start, u64 end,
1449                      struct extent_state **cached_state)
1450 {
1451         int err;
1452         u64 failed_start;
1453
1454         while (1) {
1455                 err = set_extent_bit(tree, start, end, EXTENT_LOCKED,
1456                                      EXTENT_LOCKED, &failed_start,
1457                                      cached_state, GFP_NOFS, NULL);
1458                 if (err == -EEXIST) {
1459                         wait_extent_bit(tree, failed_start, end, EXTENT_LOCKED);
1460                         start = failed_start;
1461                 } else
1462                         break;
1463                 WARN_ON(start > end);
1464         }
1465         return err;
1466 }
1467
1468 int try_lock_extent(struct extent_io_tree *tree, u64 start, u64 end)
1469 {
1470         int err;
1471         u64 failed_start;
1472
1473         err = set_extent_bit(tree, start, end, EXTENT_LOCKED, EXTENT_LOCKED,
1474                              &failed_start, NULL, GFP_NOFS, NULL);
1475         if (err == -EEXIST) {
1476                 if (failed_start > start)
1477                         clear_extent_bit(tree, start, failed_start - 1,
1478                                          EXTENT_LOCKED, 1, 0, NULL);
1479                 return 0;
1480         }
1481         return 1;
1482 }
1483
1484 void extent_range_clear_dirty_for_io(struct inode *inode, u64 start, u64 end)
1485 {
1486         unsigned long index = start >> PAGE_SHIFT;
1487         unsigned long end_index = end >> PAGE_SHIFT;
1488         struct page *page;
1489
1490         while (index <= end_index) {
1491                 page = find_get_page(inode->i_mapping, index);
1492                 BUG_ON(!page); /* Pages should be in the extent_io_tree */
1493                 clear_page_dirty_for_io(page);
1494                 put_page(page);
1495                 index++;
1496         }
1497 }
1498
1499 void extent_range_redirty_for_io(struct inode *inode, u64 start, u64 end)
1500 {
1501         unsigned long index = start >> PAGE_SHIFT;
1502         unsigned long end_index = end >> PAGE_SHIFT;
1503         struct page *page;
1504
1505         while (index <= end_index) {
1506                 page = find_get_page(inode->i_mapping, index);
1507                 BUG_ON(!page); /* Pages should be in the extent_io_tree */
1508                 __set_page_dirty_nobuffers(page);
1509                 account_page_redirty(page);
1510                 put_page(page);
1511                 index++;
1512         }
1513 }
1514
1515 /* find the first state struct with 'bits' set after 'start', and
1516  * return it.  tree->lock must be held.  NULL will returned if
1517  * nothing was found after 'start'
1518  */
1519 static struct extent_state *
1520 find_first_extent_bit_state(struct extent_io_tree *tree, u64 start, u32 bits)
1521 {
1522         struct rb_node *node;
1523         struct extent_state *state;
1524
1525         /*
1526          * this search will find all the extents that end after
1527          * our range starts.
1528          */
1529         node = tree_search(tree, start);
1530         if (!node)
1531                 goto out;
1532
1533         while (1) {
1534                 state = rb_entry(node, struct extent_state, rb_node);
1535                 if (state->end >= start && (state->state & bits))
1536                         return state;
1537
1538                 node = rb_next(node);
1539                 if (!node)
1540                         break;
1541         }
1542 out:
1543         return NULL;
1544 }
1545
1546 /*
1547  * Find the first offset in the io tree with one or more @bits set.
1548  *
1549  * Note: If there are multiple bits set in @bits, any of them will match.
1550  *
1551  * Return 0 if we find something, and update @start_ret and @end_ret.
1552  * Return 1 if we found nothing.
1553  */
1554 int find_first_extent_bit(struct extent_io_tree *tree, u64 start,
1555                           u64 *start_ret, u64 *end_ret, u32 bits,
1556                           struct extent_state **cached_state)
1557 {
1558         struct extent_state *state;
1559         int ret = 1;
1560
1561         spin_lock(&tree->lock);
1562         if (cached_state && *cached_state) {
1563                 state = *cached_state;
1564                 if (state->end == start - 1 && extent_state_in_tree(state)) {
1565                         while ((state = next_state(state)) != NULL) {
1566                                 if (state->state & bits)
1567                                         goto got_it;
1568                         }
1569                         free_extent_state(*cached_state);
1570                         *cached_state = NULL;
1571                         goto out;
1572                 }
1573                 free_extent_state(*cached_state);
1574                 *cached_state = NULL;
1575         }
1576
1577         state = find_first_extent_bit_state(tree, start, bits);
1578 got_it:
1579         if (state) {
1580                 cache_state_if_flags(state, cached_state, 0);
1581                 *start_ret = state->start;
1582                 *end_ret = state->end;
1583                 ret = 0;
1584         }
1585 out:
1586         spin_unlock(&tree->lock);
1587         return ret;
1588 }
1589
1590 /**
1591  * find_contiguous_extent_bit: find a contiguous area of bits
1592  * @tree - io tree to check
1593  * @start - offset to start the search from
1594  * @start_ret - the first offset we found with the bits set
1595  * @end_ret - the final contiguous range of the bits that were set
1596  * @bits - bits to look for
1597  *
1598  * set_extent_bit and clear_extent_bit can temporarily split contiguous ranges
1599  * to set bits appropriately, and then merge them again.  During this time it
1600  * will drop the tree->lock, so use this helper if you want to find the actual
1601  * contiguous area for given bits.  We will search to the first bit we find, and
1602  * then walk down the tree until we find a non-contiguous area.  The area
1603  * returned will be the full contiguous area with the bits set.
1604  */
1605 int find_contiguous_extent_bit(struct extent_io_tree *tree, u64 start,
1606                                u64 *start_ret, u64 *end_ret, u32 bits)
1607 {
1608         struct extent_state *state;
1609         int ret = 1;
1610
1611         spin_lock(&tree->lock);
1612         state = find_first_extent_bit_state(tree, start, bits);
1613         if (state) {
1614                 *start_ret = state->start;
1615                 *end_ret = state->end;
1616                 while ((state = next_state(state)) != NULL) {
1617                         if (state->start > (*end_ret + 1))
1618                                 break;
1619                         *end_ret = state->end;
1620                 }
1621                 ret = 0;
1622         }
1623         spin_unlock(&tree->lock);
1624         return ret;
1625 }
1626
1627 /**
1628  * find_first_clear_extent_bit - find the first range that has @bits not set.
1629  * This range could start before @start.
1630  *
1631  * @tree - the tree to search
1632  * @start - the offset at/after which the found extent should start
1633  * @start_ret - records the beginning of the range
1634  * @end_ret - records the end of the range (inclusive)
1635  * @bits - the set of bits which must be unset
1636  *
1637  * Since unallocated range is also considered one which doesn't have the bits
1638  * set it's possible that @end_ret contains -1, this happens in case the range
1639  * spans (last_range_end, end of device]. In this case it's up to the caller to
1640  * trim @end_ret to the appropriate size.
1641  */
1642 void find_first_clear_extent_bit(struct extent_io_tree *tree, u64 start,
1643                                  u64 *start_ret, u64 *end_ret, u32 bits)
1644 {
1645         struct extent_state *state;
1646         struct rb_node *node, *prev = NULL, *next;
1647
1648         spin_lock(&tree->lock);
1649
1650         /* Find first extent with bits cleared */
1651         while (1) {
1652                 node = __etree_search(tree, start, &next, &prev, NULL, NULL);
1653                 if (!node && !next && !prev) {
1654                         /*
1655                          * Tree is completely empty, send full range and let
1656                          * caller deal with it
1657                          */
1658                         *start_ret = 0;
1659                         *end_ret = -1;
1660                         goto out;
1661                 } else if (!node && !next) {
1662                         /*
1663                          * We are past the last allocated chunk, set start at
1664                          * the end of the last extent.
1665                          */
1666                         state = rb_entry(prev, struct extent_state, rb_node);
1667                         *start_ret = state->end + 1;
1668                         *end_ret = -1;
1669                         goto out;
1670                 } else if (!node) {
1671                         node = next;
1672                 }
1673                 /*
1674                  * At this point 'node' either contains 'start' or start is
1675                  * before 'node'
1676                  */
1677                 state = rb_entry(node, struct extent_state, rb_node);
1678
1679                 if (in_range(start, state->start, state->end - state->start + 1)) {
1680                         if (state->state & bits) {
1681                                 /*
1682                                  * |--range with bits sets--|
1683                                  *    |
1684                                  *    start
1685                                  */
1686                                 start = state->end + 1;
1687                         } else {
1688                                 /*
1689                                  * 'start' falls within a range that doesn't
1690                                  * have the bits set, so take its start as
1691                                  * the beginning of the desired range
1692                                  *
1693                                  * |--range with bits cleared----|
1694                                  *      |
1695                                  *      start
1696                                  */
1697                                 *start_ret = state->start;
1698                                 break;
1699                         }
1700                 } else {
1701                         /*
1702                          * |---prev range---|---hole/unset---|---node range---|
1703                          *                          |
1704                          *                        start
1705                          *
1706                          *                        or
1707                          *
1708                          * |---hole/unset--||--first node--|
1709                          * 0   |
1710                          *    start
1711                          */
1712                         if (prev) {
1713                                 state = rb_entry(prev, struct extent_state,
1714                                                  rb_node);
1715                                 *start_ret = state->end + 1;
1716                         } else {
1717                                 *start_ret = 0;
1718                         }
1719                         break;
1720                 }
1721         }
1722
1723         /*
1724          * Find the longest stretch from start until an entry which has the
1725          * bits set
1726          */
1727         while (1) {
1728                 state = rb_entry(node, struct extent_state, rb_node);
1729                 if (state->end >= start && !(state->state & bits)) {
1730                         *end_ret = state->end;
1731                 } else {
1732                         *end_ret = state->start - 1;
1733                         break;
1734                 }
1735
1736                 node = rb_next(node);
1737                 if (!node)
1738                         break;
1739         }
1740 out:
1741         spin_unlock(&tree->lock);
1742 }
1743
1744 /*
1745  * find a contiguous range of bytes in the file marked as delalloc, not
1746  * more than 'max_bytes'.  start and end are used to return the range,
1747  *
1748  * true is returned if we find something, false if nothing was in the tree
1749  */
1750 bool btrfs_find_delalloc_range(struct extent_io_tree *tree, u64 *start,
1751                                u64 *end, u64 max_bytes,
1752                                struct extent_state **cached_state)
1753 {
1754         struct rb_node *node;
1755         struct extent_state *state;
1756         u64 cur_start = *start;
1757         bool found = false;
1758         u64 total_bytes = 0;
1759
1760         spin_lock(&tree->lock);
1761
1762         /*
1763          * this search will find all the extents that end after
1764          * our range starts.
1765          */
1766         node = tree_search(tree, cur_start);
1767         if (!node) {
1768                 *end = (u64)-1;
1769                 goto out;
1770         }
1771
1772         while (1) {
1773                 state = rb_entry(node, struct extent_state, rb_node);
1774                 if (found && (state->start != cur_start ||
1775                               (state->state & EXTENT_BOUNDARY))) {
1776                         goto out;
1777                 }
1778                 if (!(state->state & EXTENT_DELALLOC)) {
1779                         if (!found)
1780                                 *end = state->end;
1781                         goto out;
1782                 }
1783                 if (!found) {
1784                         *start = state->start;
1785                         *cached_state = state;
1786                         refcount_inc(&state->refs);
1787                 }
1788                 found = true;
1789                 *end = state->end;
1790                 cur_start = state->end + 1;
1791                 node = rb_next(node);
1792                 total_bytes += state->end - state->start + 1;
1793                 if (total_bytes >= max_bytes)
1794                         break;
1795                 if (!node)
1796                         break;
1797         }
1798 out:
1799         spin_unlock(&tree->lock);
1800         return found;
1801 }
1802
1803 static int __process_pages_contig(struct address_space *mapping,
1804                                   struct page *locked_page,
1805                                   pgoff_t start_index, pgoff_t end_index,
1806                                   unsigned long page_ops, pgoff_t *index_ret);
1807
1808 static noinline void __unlock_for_delalloc(struct inode *inode,
1809                                            struct page *locked_page,
1810                                            u64 start, u64 end)
1811 {
1812         unsigned long index = start >> PAGE_SHIFT;
1813         unsigned long end_index = end >> PAGE_SHIFT;
1814
1815         ASSERT(locked_page);
1816         if (index == locked_page->index && end_index == index)
1817                 return;
1818
1819         __process_pages_contig(inode->i_mapping, locked_page, index, end_index,
1820                                PAGE_UNLOCK, NULL);
1821 }
1822
1823 static noinline int lock_delalloc_pages(struct inode *inode,
1824                                         struct page *locked_page,
1825                                         u64 delalloc_start,
1826                                         u64 delalloc_end)
1827 {
1828         unsigned long index = delalloc_start >> PAGE_SHIFT;
1829         unsigned long index_ret = index;
1830         unsigned long end_index = delalloc_end >> PAGE_SHIFT;
1831         int ret;
1832
1833         ASSERT(locked_page);
1834         if (index == locked_page->index && index == end_index)
1835                 return 0;
1836
1837         ret = __process_pages_contig(inode->i_mapping, locked_page, index,
1838                                      end_index, PAGE_LOCK, &index_ret);
1839         if (ret == -EAGAIN)
1840                 __unlock_for_delalloc(inode, locked_page, delalloc_start,
1841                                       (u64)index_ret << PAGE_SHIFT);
1842         return ret;
1843 }
1844
1845 /*
1846  * Find and lock a contiguous range of bytes in the file marked as delalloc, no
1847  * more than @max_bytes.  @Start and @end are used to return the range,
1848  *
1849  * Return: true if we find something
1850  *         false if nothing was in the tree
1851  */
1852 EXPORT_FOR_TESTS
1853 noinline_for_stack bool find_lock_delalloc_range(struct inode *inode,
1854                                     struct page *locked_page, u64 *start,
1855                                     u64 *end)
1856 {
1857         struct extent_io_tree *tree = &BTRFS_I(inode)->io_tree;
1858         u64 max_bytes = BTRFS_MAX_EXTENT_SIZE;
1859         u64 delalloc_start;
1860         u64 delalloc_end;
1861         bool found;
1862         struct extent_state *cached_state = NULL;
1863         int ret;
1864         int loops = 0;
1865
1866 again:
1867         /* step one, find a bunch of delalloc bytes starting at start */
1868         delalloc_start = *start;
1869         delalloc_end = 0;
1870         found = btrfs_find_delalloc_range(tree, &delalloc_start, &delalloc_end,
1871                                           max_bytes, &cached_state);
1872         if (!found || delalloc_end <= *start) {
1873                 *start = delalloc_start;
1874                 *end = delalloc_end;
1875                 free_extent_state(cached_state);
1876                 return false;
1877         }
1878
1879         /*
1880          * start comes from the offset of locked_page.  We have to lock
1881          * pages in order, so we can't process delalloc bytes before
1882          * locked_page
1883          */
1884         if (delalloc_start < *start)
1885                 delalloc_start = *start;
1886
1887         /*
1888          * make sure to limit the number of pages we try to lock down
1889          */
1890         if (delalloc_end + 1 - delalloc_start > max_bytes)
1891                 delalloc_end = delalloc_start + max_bytes - 1;
1892
1893         /* step two, lock all the pages after the page that has start */
1894         ret = lock_delalloc_pages(inode, locked_page,
1895                                   delalloc_start, delalloc_end);
1896         ASSERT(!ret || ret == -EAGAIN);
1897         if (ret == -EAGAIN) {
1898                 /* some of the pages are gone, lets avoid looping by
1899                  * shortening the size of the delalloc range we're searching
1900                  */
1901                 free_extent_state(cached_state);
1902                 cached_state = NULL;
1903                 if (!loops) {
1904                         max_bytes = PAGE_SIZE;
1905                         loops = 1;
1906                         goto again;
1907                 } else {
1908                         found = false;
1909                         goto out_failed;
1910                 }
1911         }
1912
1913         /* step three, lock the state bits for the whole range */
1914         lock_extent_bits(tree, delalloc_start, delalloc_end, &cached_state);
1915
1916         /* then test to make sure it is all still delalloc */
1917         ret = test_range_bit(tree, delalloc_start, delalloc_end,
1918                              EXTENT_DELALLOC, 1, cached_state);
1919         if (!ret) {
1920                 unlock_extent_cached(tree, delalloc_start, delalloc_end,
1921                                      &cached_state);
1922                 __unlock_for_delalloc(inode, locked_page,
1923                               delalloc_start, delalloc_end);
1924                 cond_resched();
1925                 goto again;
1926         }
1927         free_extent_state(cached_state);
1928         *start = delalloc_start;
1929         *end = delalloc_end;
1930 out_failed:
1931         return found;
1932 }
1933
1934 static int __process_pages_contig(struct address_space *mapping,
1935                                   struct page *locked_page,
1936                                   pgoff_t start_index, pgoff_t end_index,
1937                                   unsigned long page_ops, pgoff_t *index_ret)
1938 {
1939         unsigned long nr_pages = end_index - start_index + 1;
1940         unsigned long pages_processed = 0;
1941         pgoff_t index = start_index;
1942         struct page *pages[16];
1943         unsigned ret;
1944         int err = 0;
1945         int i;
1946
1947         if (page_ops & PAGE_LOCK) {
1948                 ASSERT(page_ops == PAGE_LOCK);
1949                 ASSERT(index_ret && *index_ret == start_index);
1950         }
1951
1952         if ((page_ops & PAGE_SET_ERROR) && nr_pages > 0)
1953                 mapping_set_error(mapping, -EIO);
1954
1955         while (nr_pages > 0) {
1956                 ret = find_get_pages_contig(mapping, index,
1957                                      min_t(unsigned long,
1958                                      nr_pages, ARRAY_SIZE(pages)), pages);
1959                 if (ret == 0) {
1960                         /*
1961                          * Only if we're going to lock these pages,
1962                          * can we find nothing at @index.
1963                          */
1964                         ASSERT(page_ops & PAGE_LOCK);
1965                         err = -EAGAIN;
1966                         goto out;
1967                 }
1968
1969                 for (i = 0; i < ret; i++) {
1970                         if (page_ops & PAGE_SET_PRIVATE2)
1971                                 SetPagePrivate2(pages[i]);
1972
1973                         if (locked_page && pages[i] == locked_page) {
1974                                 put_page(pages[i]);
1975                                 pages_processed++;
1976                                 continue;
1977                         }
1978                         if (page_ops & PAGE_CLEAR_DIRTY)
1979                                 clear_page_dirty_for_io(pages[i]);
1980                         if (page_ops & PAGE_SET_WRITEBACK)
1981                                 set_page_writeback(pages[i]);
1982                         if (page_ops & PAGE_SET_ERROR)
1983                                 SetPageError(pages[i]);
1984                         if (page_ops & PAGE_END_WRITEBACK)
1985                                 end_page_writeback(pages[i]);
1986                         if (page_ops & PAGE_UNLOCK)
1987                                 unlock_page(pages[i]);
1988                         if (page_ops & PAGE_LOCK) {
1989                                 lock_page(pages[i]);
1990                                 if (!PageDirty(pages[i]) ||
1991                                     pages[i]->mapping != mapping) {
1992                                         unlock_page(pages[i]);
1993                                         for (; i < ret; i++)
1994                                                 put_page(pages[i]);
1995                                         err = -EAGAIN;
1996                                         goto out;
1997                                 }
1998                         }
1999                         put_page(pages[i]);
2000                         pages_processed++;
2001                 }
2002                 nr_pages -= ret;
2003                 index += ret;
2004                 cond_resched();
2005         }
2006 out:
2007         if (err && index_ret)
2008                 *index_ret = start_index + pages_processed - 1;
2009         return err;
2010 }
2011
2012 void extent_clear_unlock_delalloc(struct btrfs_inode *inode, u64 start, u64 end,
2013                                   struct page *locked_page,
2014                                   u32 clear_bits, unsigned long page_ops)
2015 {
2016         clear_extent_bit(&inode->io_tree, start, end, clear_bits, 1, 0, NULL);
2017
2018         __process_pages_contig(inode->vfs_inode.i_mapping, locked_page,
2019                                start >> PAGE_SHIFT, end >> PAGE_SHIFT,
2020                                page_ops, NULL);
2021 }
2022
2023 /*
2024  * count the number of bytes in the tree that have a given bit(s)
2025  * set.  This can be fairly slow, except for EXTENT_DIRTY which is
2026  * cached.  The total number found is returned.
2027  */
2028 u64 count_range_bits(struct extent_io_tree *tree,
2029                      u64 *start, u64 search_end, u64 max_bytes,
2030                      u32 bits, int contig)
2031 {
2032         struct rb_node *node;
2033         struct extent_state *state;
2034         u64 cur_start = *start;
2035         u64 total_bytes = 0;
2036         u64 last = 0;
2037         int found = 0;
2038
2039         if (WARN_ON(search_end <= cur_start))
2040                 return 0;
2041
2042         spin_lock(&tree->lock);
2043         if (cur_start == 0 && bits == EXTENT_DIRTY) {
2044                 total_bytes = tree->dirty_bytes;
2045                 goto out;
2046         }
2047         /*
2048          * this search will find all the extents that end after
2049          * our range starts.
2050          */
2051         node = tree_search(tree, cur_start);
2052         if (!node)
2053                 goto out;
2054
2055         while (1) {
2056                 state = rb_entry(node, struct extent_state, rb_node);
2057                 if (state->start > search_end)
2058                         break;
2059                 if (contig && found && state->start > last + 1)
2060                         break;
2061                 if (state->end >= cur_start && (state->state & bits) == bits) {
2062                         total_bytes += min(search_end, state->end) + 1 -
2063                                        max(cur_start, state->start);
2064                         if (total_bytes >= max_bytes)
2065                                 break;
2066                         if (!found) {
2067                                 *start = max(cur_start, state->start);
2068                                 found = 1;
2069                         }
2070                         last = state->end;
2071                 } else if (contig && found) {
2072                         break;
2073                 }
2074                 node = rb_next(node);
2075                 if (!node)
2076                         break;
2077         }
2078 out:
2079         spin_unlock(&tree->lock);
2080         return total_bytes;
2081 }
2082
2083 /*
2084  * set the private field for a given byte offset in the tree.  If there isn't
2085  * an extent_state there already, this does nothing.
2086  */
2087 int set_state_failrec(struct extent_io_tree *tree, u64 start,
2088                       struct io_failure_record *failrec)
2089 {
2090         struct rb_node *node;
2091         struct extent_state *state;
2092         int ret = 0;
2093
2094         spin_lock(&tree->lock);
2095         /*
2096          * this search will find all the extents that end after
2097          * our range starts.
2098          */
2099         node = tree_search(tree, start);
2100         if (!node) {
2101                 ret = -ENOENT;
2102                 goto out;
2103         }
2104         state = rb_entry(node, struct extent_state, rb_node);
2105         if (state->start != start) {
2106                 ret = -ENOENT;
2107                 goto out;
2108         }
2109         state->failrec = failrec;
2110 out:
2111         spin_unlock(&tree->lock);
2112         return ret;
2113 }
2114
2115 struct io_failure_record *get_state_failrec(struct extent_io_tree *tree, u64 start)
2116 {
2117         struct rb_node *node;
2118         struct extent_state *state;
2119         struct io_failure_record *failrec;
2120
2121         spin_lock(&tree->lock);
2122         /*
2123          * this search will find all the extents that end after
2124          * our range starts.
2125          */
2126         node = tree_search(tree, start);
2127         if (!node) {
2128                 failrec = ERR_PTR(-ENOENT);
2129                 goto out;
2130         }
2131         state = rb_entry(node, struct extent_state, rb_node);
2132         if (state->start != start) {
2133                 failrec = ERR_PTR(-ENOENT);
2134                 goto out;
2135         }
2136
2137         failrec = state->failrec;
2138 out:
2139         spin_unlock(&tree->lock);
2140         return failrec;
2141 }
2142
2143 /*
2144  * searches a range in the state tree for a given mask.
2145  * If 'filled' == 1, this returns 1 only if every extent in the tree
2146  * has the bits set.  Otherwise, 1 is returned if any bit in the
2147  * range is found set.
2148  */
2149 int test_range_bit(struct extent_io_tree *tree, u64 start, u64 end,
2150                    u32 bits, int filled, struct extent_state *cached)
2151 {
2152         struct extent_state *state = NULL;
2153         struct rb_node *node;
2154         int bitset = 0;
2155
2156         spin_lock(&tree->lock);
2157         if (cached && extent_state_in_tree(cached) && cached->start <= start &&
2158             cached->end > start)
2159                 node = &cached->rb_node;
2160         else
2161                 node = tree_search(tree, start);
2162         while (node && start <= end) {
2163                 state = rb_entry(node, struct extent_state, rb_node);
2164
2165                 if (filled && state->start > start) {
2166                         bitset = 0;
2167                         break;
2168                 }
2169
2170                 if (state->start > end)
2171                         break;
2172
2173                 if (state->state & bits) {
2174                         bitset = 1;
2175                         if (!filled)
2176                                 break;
2177                 } else if (filled) {
2178                         bitset = 0;
2179                         break;
2180                 }
2181
2182                 if (state->end == (u64)-1)
2183                         break;
2184
2185                 start = state->end + 1;
2186                 if (start > end)
2187                         break;
2188                 node = rb_next(node);
2189                 if (!node) {
2190                         if (filled)
2191                                 bitset = 0;
2192                         break;
2193                 }
2194         }
2195         spin_unlock(&tree->lock);
2196         return bitset;
2197 }
2198
2199 /*
2200  * helper function to set a given page up to date if all the
2201  * extents in the tree for that page are up to date
2202  */
2203 static void check_page_uptodate(struct extent_io_tree *tree, struct page *page)
2204 {
2205         u64 start = page_offset(page);
2206         u64 end = start + PAGE_SIZE - 1;
2207         if (test_range_bit(tree, start, end, EXTENT_UPTODATE, 1, NULL))
2208                 SetPageUptodate(page);
2209 }
2210
2211 int free_io_failure(struct extent_io_tree *failure_tree,
2212                     struct extent_io_tree *io_tree,
2213                     struct io_failure_record *rec)
2214 {
2215         int ret;
2216         int err = 0;
2217
2218         set_state_failrec(failure_tree, rec->start, NULL);
2219         ret = clear_extent_bits(failure_tree, rec->start,
2220                                 rec->start + rec->len - 1,
2221                                 EXTENT_LOCKED | EXTENT_DIRTY);
2222         if (ret)
2223                 err = ret;
2224
2225         ret = clear_extent_bits(io_tree, rec->start,
2226                                 rec->start + rec->len - 1,
2227                                 EXTENT_DAMAGED);
2228         if (ret && !err)
2229                 err = ret;
2230
2231         kfree(rec);
2232         return err;
2233 }
2234
2235 /*
2236  * this bypasses the standard btrfs submit functions deliberately, as
2237  * the standard behavior is to write all copies in a raid setup. here we only
2238  * want to write the one bad copy. so we do the mapping for ourselves and issue
2239  * submit_bio directly.
2240  * to avoid any synchronization issues, wait for the data after writing, which
2241  * actually prevents the read that triggered the error from finishing.
2242  * currently, there can be no more than two copies of every data bit. thus,
2243  * exactly one rewrite is required.
2244  */
2245 int repair_io_failure(struct btrfs_fs_info *fs_info, u64 ino, u64 start,
2246                       u64 length, u64 logical, struct page *page,
2247                       unsigned int pg_offset, int mirror_num)
2248 {
2249         struct bio *bio;
2250         struct btrfs_device *dev;
2251         u64 map_length = 0;
2252         u64 sector;
2253         struct btrfs_bio *bbio = NULL;
2254         int ret;
2255
2256         ASSERT(!(fs_info->sb->s_flags & SB_RDONLY));
2257         BUG_ON(!mirror_num);
2258
2259         bio = btrfs_io_bio_alloc(1);
2260         bio->bi_iter.bi_size = 0;
2261         map_length = length;
2262
2263         /*
2264          * Avoid races with device replace and make sure our bbio has devices
2265          * associated to its stripes that don't go away while we are doing the
2266          * read repair operation.
2267          */
2268         btrfs_bio_counter_inc_blocked(fs_info);
2269         if (btrfs_is_parity_mirror(fs_info, logical, length)) {
2270                 /*
2271                  * Note that we don't use BTRFS_MAP_WRITE because it's supposed
2272                  * to update all raid stripes, but here we just want to correct
2273                  * bad stripe, thus BTRFS_MAP_READ is abused to only get the bad
2274                  * stripe's dev and sector.
2275                  */
2276                 ret = btrfs_map_block(fs_info, BTRFS_MAP_READ, logical,
2277                                       &map_length, &bbio, 0);
2278                 if (ret) {
2279                         btrfs_bio_counter_dec(fs_info);
2280                         bio_put(bio);
2281                         return -EIO;
2282                 }
2283                 ASSERT(bbio->mirror_num == 1);
2284         } else {
2285                 ret = btrfs_map_block(fs_info, BTRFS_MAP_WRITE, logical,
2286                                       &map_length, &bbio, mirror_num);
2287                 if (ret) {
2288                         btrfs_bio_counter_dec(fs_info);
2289                         bio_put(bio);
2290                         return -EIO;
2291                 }
2292                 BUG_ON(mirror_num != bbio->mirror_num);
2293         }
2294
2295         sector = bbio->stripes[bbio->mirror_num - 1].physical >> 9;
2296         bio->bi_iter.bi_sector = sector;
2297         dev = bbio->stripes[bbio->mirror_num - 1].dev;
2298         btrfs_put_bbio(bbio);
2299         if (!dev || !dev->bdev ||
2300             !test_bit(BTRFS_DEV_STATE_WRITEABLE, &dev->dev_state)) {
2301                 btrfs_bio_counter_dec(fs_info);
2302                 bio_put(bio);
2303                 return -EIO;
2304         }
2305         bio_set_dev(bio, dev->bdev);
2306         bio->bi_opf = REQ_OP_WRITE | REQ_SYNC;
2307         bio_add_page(bio, page, length, pg_offset);
2308
2309         if (btrfsic_submit_bio_wait(bio)) {
2310                 /* try to remap that extent elsewhere? */
2311                 btrfs_bio_counter_dec(fs_info);
2312                 bio_put(bio);
2313                 btrfs_dev_stat_inc_and_print(dev, BTRFS_DEV_STAT_WRITE_ERRS);
2314                 return -EIO;
2315         }
2316
2317         btrfs_info_rl_in_rcu(fs_info,
2318                 "read error corrected: ino %llu off %llu (dev %s sector %llu)",
2319                                   ino, start,
2320                                   rcu_str_deref(dev->name), sector);
2321         btrfs_bio_counter_dec(fs_info);
2322         bio_put(bio);
2323         return 0;
2324 }
2325
2326 int btrfs_repair_eb_io_failure(const struct extent_buffer *eb, int mirror_num)
2327 {
2328         struct btrfs_fs_info *fs_info = eb->fs_info;
2329         u64 start = eb->start;
2330         int i, num_pages = num_extent_pages(eb);
2331         int ret = 0;
2332
2333         if (sb_rdonly(fs_info->sb))
2334                 return -EROFS;
2335
2336         for (i = 0; i < num_pages; i++) {
2337                 struct page *p = eb->pages[i];
2338
2339                 ret = repair_io_failure(fs_info, 0, start, PAGE_SIZE, start, p,
2340                                         start - page_offset(p), mirror_num);
2341                 if (ret)
2342                         break;
2343                 start += PAGE_SIZE;
2344         }
2345
2346         return ret;
2347 }
2348
2349 /*
2350  * each time an IO finishes, we do a fast check in the IO failure tree
2351  * to see if we need to process or clean up an io_failure_record
2352  */
2353 int clean_io_failure(struct btrfs_fs_info *fs_info,
2354                      struct extent_io_tree *failure_tree,
2355                      struct extent_io_tree *io_tree, u64 start,
2356                      struct page *page, u64 ino, unsigned int pg_offset)
2357 {
2358         u64 private;
2359         struct io_failure_record *failrec;
2360         struct extent_state *state;
2361         int num_copies;
2362         int ret;
2363
2364         private = 0;
2365         ret = count_range_bits(failure_tree, &private, (u64)-1, 1,
2366                                EXTENT_DIRTY, 0);
2367         if (!ret)
2368                 return 0;
2369
2370         failrec = get_state_failrec(failure_tree, start);
2371         if (IS_ERR(failrec))
2372                 return 0;
2373
2374         BUG_ON(!failrec->this_mirror);
2375
2376         if (failrec->in_validation) {
2377                 /* there was no real error, just free the record */
2378                 btrfs_debug(fs_info,
2379                         "clean_io_failure: freeing dummy error at %llu",
2380                         failrec->start);
2381                 goto out;
2382         }
2383         if (sb_rdonly(fs_info->sb))
2384                 goto out;
2385
2386         spin_lock(&io_tree->lock);
2387         state = find_first_extent_bit_state(io_tree,
2388                                             failrec->start,
2389                                             EXTENT_LOCKED);
2390         spin_unlock(&io_tree->lock);
2391
2392         if (state && state->start <= failrec->start &&
2393             state->end >= failrec->start + failrec->len - 1) {
2394                 num_copies = btrfs_num_copies(fs_info, failrec->logical,
2395                                               failrec->len);
2396                 if (num_copies > 1)  {
2397                         repair_io_failure(fs_info, ino, start, failrec->len,
2398                                           failrec->logical, page, pg_offset,
2399                                           failrec->failed_mirror);
2400                 }
2401         }
2402
2403 out:
2404         free_io_failure(failure_tree, io_tree, failrec);
2405
2406         return 0;
2407 }
2408
2409 /*
2410  * Can be called when
2411  * - hold extent lock
2412  * - under ordered extent
2413  * - the inode is freeing
2414  */
2415 void btrfs_free_io_failure_record(struct btrfs_inode *inode, u64 start, u64 end)
2416 {
2417         struct extent_io_tree *failure_tree = &inode->io_failure_tree;
2418         struct io_failure_record *failrec;
2419         struct extent_state *state, *next;
2420
2421         if (RB_EMPTY_ROOT(&failure_tree->state))
2422                 return;
2423
2424         spin_lock(&failure_tree->lock);
2425         state = find_first_extent_bit_state(failure_tree, start, EXTENT_DIRTY);
2426         while (state) {
2427                 if (state->start > end)
2428                         break;
2429
2430                 ASSERT(state->end <= end);
2431
2432                 next = next_state(state);
2433
2434                 failrec = state->failrec;
2435                 free_extent_state(state);
2436                 kfree(failrec);
2437
2438                 state = next;
2439         }
2440         spin_unlock(&failure_tree->lock);
2441 }
2442
2443 static struct io_failure_record *btrfs_get_io_failure_record(struct inode *inode,
2444                                                              u64 start, u64 end)
2445 {
2446         struct btrfs_fs_info *fs_info = btrfs_sb(inode->i_sb);
2447         struct io_failure_record *failrec;
2448         struct extent_map *em;
2449         struct extent_io_tree *failure_tree = &BTRFS_I(inode)->io_failure_tree;
2450         struct extent_io_tree *tree = &BTRFS_I(inode)->io_tree;
2451         struct extent_map_tree *em_tree = &BTRFS_I(inode)->extent_tree;
2452         int ret;
2453         u64 logical;
2454
2455         failrec = get_state_failrec(failure_tree, start);
2456         if (!IS_ERR(failrec)) {
2457                 btrfs_debug(fs_info,
2458                         "Get IO Failure Record: (found) logical=%llu, start=%llu, len=%llu, validation=%d",
2459                         failrec->logical, failrec->start, failrec->len,
2460                         failrec->in_validation);
2461                 /*
2462                  * when data can be on disk more than twice, add to failrec here
2463                  * (e.g. with a list for failed_mirror) to make
2464                  * clean_io_failure() clean all those errors at once.
2465                  */
2466
2467                 return failrec;
2468         }
2469
2470         failrec = kzalloc(sizeof(*failrec), GFP_NOFS);
2471         if (!failrec)
2472                 return ERR_PTR(-ENOMEM);
2473
2474         failrec->start = start;
2475         failrec->len = end - start + 1;
2476         failrec->this_mirror = 0;
2477         failrec->bio_flags = 0;
2478         failrec->in_validation = 0;
2479
2480         read_lock(&em_tree->lock);
2481         em = lookup_extent_mapping(em_tree, start, failrec->len);
2482         if (!em) {
2483                 read_unlock(&em_tree->lock);
2484                 kfree(failrec);
2485                 return ERR_PTR(-EIO);
2486         }
2487
2488         if (em->start > start || em->start + em->len <= start) {
2489                 free_extent_map(em);
2490                 em = NULL;
2491         }
2492         read_unlock(&em_tree->lock);
2493         if (!em) {
2494                 kfree(failrec);
2495                 return ERR_PTR(-EIO);
2496         }
2497
2498         logical = start - em->start;
2499         logical = em->block_start + logical;
2500         if (test_bit(EXTENT_FLAG_COMPRESSED, &em->flags)) {
2501                 logical = em->block_start;
2502                 failrec->bio_flags = EXTENT_BIO_COMPRESSED;
2503                 extent_set_compress_type(&failrec->bio_flags, em->compress_type);
2504         }
2505
2506         btrfs_debug(fs_info,
2507                     "Get IO Failure Record: (new) logical=%llu, start=%llu, len=%llu",
2508                     logical, start, failrec->len);
2509
2510         failrec->logical = logical;
2511         free_extent_map(em);
2512
2513         /* Set the bits in the private failure tree */
2514         ret = set_extent_bits(failure_tree, start, end,
2515                               EXTENT_LOCKED | EXTENT_DIRTY);
2516         if (ret >= 0) {
2517                 ret = set_state_failrec(failure_tree, start, failrec);
2518                 /* Set the bits in the inode's tree */
2519                 ret = set_extent_bits(tree, start, end, EXTENT_DAMAGED);
2520         } else if (ret < 0) {
2521                 kfree(failrec);
2522                 return ERR_PTR(ret);
2523         }
2524
2525         return failrec;
2526 }
2527
2528 static bool btrfs_check_repairable(struct inode *inode, bool needs_validation,
2529                                    struct io_failure_record *failrec,
2530                                    int failed_mirror)
2531 {
2532         struct btrfs_fs_info *fs_info = btrfs_sb(inode->i_sb);
2533         int num_copies;
2534
2535         num_copies = btrfs_num_copies(fs_info, failrec->logical, failrec->len);
2536         if (num_copies == 1) {
2537                 /*
2538                  * we only have a single copy of the data, so don't bother with
2539                  * all the retry and error correction code that follows. no
2540                  * matter what the error is, it is very likely to persist.
2541                  */
2542                 btrfs_debug(fs_info,
2543                         "Check Repairable: cannot repair, num_copies=%d, next_mirror %d, failed_mirror %d",
2544                         num_copies, failrec->this_mirror, failed_mirror);
2545                 return false;
2546         }
2547
2548         /*
2549          * there are two premises:
2550          *      a) deliver good data to the caller
2551          *      b) correct the bad sectors on disk
2552          */
2553         if (needs_validation) {
2554                 /*
2555                  * to fulfill b), we need to know the exact failing sectors, as
2556                  * we don't want to rewrite any more than the failed ones. thus,
2557                  * we need separate read requests for the failed bio
2558                  *
2559                  * if the following BUG_ON triggers, our validation request got
2560                  * merged. we need separate requests for our algorithm to work.
2561                  */
2562                 BUG_ON(failrec->in_validation);
2563                 failrec->in_validation = 1;
2564                 failrec->this_mirror = failed_mirror;
2565         } else {
2566                 /*
2567                  * we're ready to fulfill a) and b) alongside. get a good copy
2568                  * of the failed sector and if we succeed, we have setup
2569                  * everything for repair_io_failure to do the rest for us.
2570                  */
2571                 if (failrec->in_validation) {
2572                         BUG_ON(failrec->this_mirror != failed_mirror);
2573                         failrec->in_validation = 0;
2574                         failrec->this_mirror = 0;
2575                 }
2576                 failrec->failed_mirror = failed_mirror;
2577                 failrec->this_mirror++;
2578                 if (failrec->this_mirror == failed_mirror)
2579                         failrec->this_mirror++;
2580         }
2581
2582         if (failrec->this_mirror > num_copies) {
2583                 btrfs_debug(fs_info,
2584                         "Check Repairable: (fail) num_copies=%d, next_mirror %d, failed_mirror %d",
2585                         num_copies, failrec->this_mirror, failed_mirror);
2586                 return false;
2587         }
2588
2589         return true;
2590 }
2591
2592 static bool btrfs_io_needs_validation(struct inode *inode, struct bio *bio)
2593 {
2594         u64 len = 0;
2595         const u32 blocksize = inode->i_sb->s_blocksize;
2596
2597         /*
2598          * If bi_status is BLK_STS_OK, then this was a checksum error, not an
2599          * I/O error. In this case, we already know exactly which sector was
2600          * bad, so we don't need to validate.
2601          */
2602         if (bio->bi_status == BLK_STS_OK)
2603                 return false;
2604
2605         /*
2606          * We need to validate each sector individually if the failed I/O was
2607          * for multiple sectors.
2608          *
2609          * There are a few possible bios that can end up here:
2610          * 1. A buffered read bio, which is not cloned.
2611          * 2. A direct I/O read bio, which is cloned.
2612          * 3. A (buffered or direct) repair bio, which is not cloned.
2613          *
2614          * For cloned bios (case 2), we can get the size from
2615          * btrfs_io_bio->iter; for non-cloned bios (cases 1 and 3), we can get
2616          * it from the bvecs.
2617          */
2618         if (bio_flagged(bio, BIO_CLONED)) {
2619                 if (btrfs_io_bio(bio)->iter.bi_size > blocksize)
2620                         return true;
2621         } else {
2622                 struct bio_vec *bvec;
2623                 int i;
2624
2625                 bio_for_each_bvec_all(bvec, bio, i) {
2626                         len += bvec->bv_len;
2627                         if (len > blocksize)
2628                                 return true;
2629                 }
2630         }
2631         return false;
2632 }
2633
2634 blk_status_t btrfs_submit_read_repair(struct inode *inode,
2635                                       struct bio *failed_bio, u32 bio_offset,
2636                                       struct page *page, unsigned int pgoff,
2637                                       u64 start, u64 end, int failed_mirror,
2638                                       submit_bio_hook_t *submit_bio_hook)
2639 {
2640         struct io_failure_record *failrec;
2641         struct btrfs_fs_info *fs_info = btrfs_sb(inode->i_sb);
2642         struct extent_io_tree *tree = &BTRFS_I(inode)->io_tree;
2643         struct extent_io_tree *failure_tree = &BTRFS_I(inode)->io_failure_tree;
2644         struct btrfs_io_bio *failed_io_bio = btrfs_io_bio(failed_bio);
2645         const int icsum = bio_offset >> fs_info->sectorsize_bits;
2646         bool need_validation;
2647         struct bio *repair_bio;
2648         struct btrfs_io_bio *repair_io_bio;
2649         blk_status_t status;
2650
2651         btrfs_debug(fs_info,
2652                    "repair read error: read error at %llu", start);
2653
2654         BUG_ON(bio_op(failed_bio) == REQ_OP_WRITE);
2655
2656         failrec = btrfs_get_io_failure_record(inode, start, end);
2657         if (IS_ERR(failrec))
2658                 return errno_to_blk_status(PTR_ERR(failrec));
2659
2660         need_validation = btrfs_io_needs_validation(inode, failed_bio);
2661
2662         if (!btrfs_check_repairable(inode, need_validation, failrec,
2663                                     failed_mirror)) {
2664                 free_io_failure(failure_tree, tree, failrec);
2665                 return BLK_STS_IOERR;
2666         }
2667
2668         repair_bio = btrfs_io_bio_alloc(1);
2669         repair_io_bio = btrfs_io_bio(repair_bio);
2670         repair_bio->bi_opf = REQ_OP_READ;
2671         if (need_validation)
2672                 repair_bio->bi_opf |= REQ_FAILFAST_DEV;
2673         repair_bio->bi_end_io = failed_bio->bi_end_io;
2674         repair_bio->bi_iter.bi_sector = failrec->logical >> 9;
2675         repair_bio->bi_private = failed_bio->bi_private;
2676
2677         if (failed_io_bio->csum) {
2678                 const u32 csum_size = fs_info->csum_size;
2679
2680                 repair_io_bio->csum = repair_io_bio->csum_inline;
2681                 memcpy(repair_io_bio->csum,
2682                        failed_io_bio->csum + csum_size * icsum, csum_size);
2683         }
2684
2685         bio_add_page(repair_bio, page, failrec->len, pgoff);
2686         repair_io_bio->logical = failrec->start;
2687         repair_io_bio->iter = repair_bio->bi_iter;
2688
2689         btrfs_debug(btrfs_sb(inode->i_sb),
2690 "repair read error: submitting new read to mirror %d, in_validation=%d",
2691                     failrec->this_mirror, failrec->in_validation);
2692
2693         status = submit_bio_hook(inode, repair_bio, failrec->this_mirror,
2694                                  failrec->bio_flags);
2695         if (status) {
2696                 free_io_failure(failure_tree, tree, failrec);
2697                 bio_put(repair_bio);
2698         }
2699         return status;
2700 }
2701
2702 /* lots and lots of room for performance fixes in the end_bio funcs */
2703
2704 void end_extent_writepage(struct page *page, int err, u64 start, u64 end)
2705 {
2706         int uptodate = (err == 0);
2707         int ret = 0;
2708
2709         btrfs_writepage_endio_finish_ordered(page, start, end, uptodate);
2710
2711         if (!uptodate) {
2712                 ClearPageUptodate(page);
2713                 SetPageError(page);
2714                 ret = err < 0 ? err : -EIO;
2715                 mapping_set_error(page->mapping, ret);
2716         }
2717 }
2718
2719 /*
2720  * after a writepage IO is done, we need to:
2721  * clear the uptodate bits on error
2722  * clear the writeback bits in the extent tree for this IO
2723  * end_page_writeback if the page has no more pending IO
2724  *
2725  * Scheduling is not allowed, so the extent state tree is expected
2726  * to have one and only one object corresponding to this IO.
2727  */
2728 static void end_bio_extent_writepage(struct bio *bio)
2729 {
2730         int error = blk_status_to_errno(bio->bi_status);
2731         struct bio_vec *bvec;
2732         u64 start;
2733         u64 end;
2734         struct bvec_iter_all iter_all;
2735
2736         ASSERT(!bio_flagged(bio, BIO_CLONED));
2737         bio_for_each_segment_all(bvec, bio, iter_all) {
2738                 struct page *page = bvec->bv_page;
2739                 struct inode *inode = page->mapping->host;
2740                 struct btrfs_fs_info *fs_info = btrfs_sb(inode->i_sb);
2741
2742                 /* We always issue full-page reads, but if some block
2743                  * in a page fails to read, blk_update_request() will
2744                  * advance bv_offset and adjust bv_len to compensate.
2745                  * Print a warning for nonzero offsets, and an error
2746                  * if they don't add up to a full page.  */
2747                 if (bvec->bv_offset || bvec->bv_len != PAGE_SIZE) {
2748                         if (bvec->bv_offset + bvec->bv_len != PAGE_SIZE)
2749                                 btrfs_err(fs_info,
2750                                    "partial page write in btrfs with offset %u and length %u",
2751                                         bvec->bv_offset, bvec->bv_len);
2752                         else
2753                                 btrfs_info(fs_info,
2754                                    "incomplete page write in btrfs with offset %u and length %u",
2755                                         bvec->bv_offset, bvec->bv_len);
2756                 }
2757
2758                 start = page_offset(page);
2759                 end = start + bvec->bv_offset + bvec->bv_len - 1;
2760
2761                 end_extent_writepage(page, error, start, end);
2762                 end_page_writeback(page);
2763         }
2764
2765         bio_put(bio);
2766 }
2767
2768 /*
2769  * Record previously processed extent range
2770  *
2771  * For endio_readpage_release_extent() to handle a full extent range, reducing
2772  * the extent io operations.
2773  */
2774 struct processed_extent {
2775         struct btrfs_inode *inode;
2776         /* Start of the range in @inode */
2777         u64 start;
2778         /* End of the range in in @inode */
2779         u64 end;
2780         bool uptodate;
2781 };
2782
2783 /*
2784  * Try to release processed extent range
2785  *
2786  * May not release the extent range right now if the current range is
2787  * contiguous to processed extent.
2788  *
2789  * Will release processed extent when any of @inode, @uptodate, the range is
2790  * no longer contiguous to the processed range.
2791  *
2792  * Passing @inode == NULL will force processed extent to be released.
2793  */
2794 static void endio_readpage_release_extent(struct processed_extent *processed,
2795                               struct btrfs_inode *inode, u64 start, u64 end,
2796                               bool uptodate)
2797 {
2798         struct extent_state *cached = NULL;
2799         struct extent_io_tree *tree;
2800
2801         /* The first extent, initialize @processed */
2802         if (!processed->inode)
2803                 goto update;
2804
2805         /*
2806          * Contiguous to processed extent, just uptodate the end.
2807          *
2808          * Several things to notice:
2809          *
2810          * - bio can be merged as long as on-disk bytenr is contiguous
2811          *   This means we can have page belonging to other inodes, thus need to
2812          *   check if the inode still matches.
2813          * - bvec can contain range beyond current page for multi-page bvec
2814          *   Thus we need to do processed->end + 1 >= start check
2815          */
2816         if (processed->inode == inode && processed->uptodate == uptodate &&
2817             processed->end + 1 >= start && end >= processed->end) {
2818                 processed->end = end;
2819                 return;
2820         }
2821
2822         tree = &processed->inode->io_tree;
2823         /*
2824          * Now we don't have range contiguous to the processed range, release
2825          * the processed range now.
2826          */
2827         if (processed->uptodate && tree->track_uptodate)
2828                 set_extent_uptodate(tree, processed->start, processed->end,
2829                                     &cached, GFP_ATOMIC);
2830         unlock_extent_cached_atomic(tree, processed->start, processed->end,
2831                                     &cached);
2832
2833 update:
2834         /* Update processed to current range */
2835         processed->inode = inode;
2836         processed->start = start;
2837         processed->end = end;
2838         processed->uptodate = uptodate;
2839 }
2840
2841 static void endio_readpage_update_page_status(struct page *page, bool uptodate)
2842 {
2843         if (uptodate) {
2844                 SetPageUptodate(page);
2845         } else {
2846                 ClearPageUptodate(page);
2847                 SetPageError(page);
2848         }
2849         unlock_page(page);
2850 }
2851
2852 /*
2853  * after a readpage IO is done, we need to:
2854  * clear the uptodate bits on error
2855  * set the uptodate bits if things worked
2856  * set the page up to date if all extents in the tree are uptodate
2857  * clear the lock bit in the extent tree
2858  * unlock the page if there are no other extents locked for it
2859  *
2860  * Scheduling is not allowed, so the extent state tree is expected
2861  * to have one and only one object corresponding to this IO.
2862  */
2863 static void end_bio_extent_readpage(struct bio *bio)
2864 {
2865         struct bio_vec *bvec;
2866         int uptodate = !bio->bi_status;
2867         struct btrfs_io_bio *io_bio = btrfs_io_bio(bio);
2868         struct extent_io_tree *tree, *failure_tree;
2869         struct processed_extent processed = { 0 };
2870         /*
2871          * The offset to the beginning of a bio, since one bio can never be
2872          * larger than UINT_MAX, u32 here is enough.
2873          */
2874         u32 bio_offset = 0;
2875         int mirror;
2876         int ret;
2877         struct bvec_iter_all iter_all;
2878
2879         ASSERT(!bio_flagged(bio, BIO_CLONED));
2880         bio_for_each_segment_all(bvec, bio, iter_all) {
2881                 struct page *page = bvec->bv_page;
2882                 struct inode *inode = page->mapping->host;
2883                 struct btrfs_fs_info *fs_info = btrfs_sb(inode->i_sb);
2884                 const u32 sectorsize = fs_info->sectorsize;
2885                 u64 start;
2886                 u64 end;
2887                 u32 len;
2888
2889                 btrfs_debug(fs_info,
2890                         "end_bio_extent_readpage: bi_sector=%llu, err=%d, mirror=%u",
2891                         bio->bi_iter.bi_sector, bio->bi_status,
2892                         io_bio->mirror_num);
2893                 tree = &BTRFS_I(inode)->io_tree;
2894                 failure_tree = &BTRFS_I(inode)->io_failure_tree;
2895
2896                 /*
2897                  * We always issue full-sector reads, but if some block in a
2898                  * page fails to read, blk_update_request() will advance
2899                  * bv_offset and adjust bv_len to compensate.  Print a warning
2900                  * for unaligned offsets, and an error if they don't add up to
2901                  * a full sector.
2902                  */
2903                 if (!IS_ALIGNED(bvec->bv_offset, sectorsize))
2904                         btrfs_err(fs_info,
2905                 "partial page read in btrfs with offset %u and length %u",
2906                                   bvec->bv_offset, bvec->bv_len);
2907                 else if (!IS_ALIGNED(bvec->bv_offset + bvec->bv_len,
2908                                      sectorsize))
2909                         btrfs_info(fs_info,
2910                 "incomplete page read with offset %u and length %u",
2911                                    bvec->bv_offset, bvec->bv_len);
2912
2913                 start = page_offset(page) + bvec->bv_offset;
2914                 end = start + bvec->bv_len - 1;
2915                 len = bvec->bv_len;
2916
2917                 mirror = io_bio->mirror_num;
2918                 if (likely(uptodate)) {
2919                         if (is_data_inode(inode))
2920                                 ret = btrfs_verify_data_csum(io_bio,
2921                                                 bio_offset, page, start, end,
2922                                                 mirror);
2923                         else
2924                                 ret = btrfs_validate_metadata_buffer(io_bio,
2925                                         page, start, end, mirror);
2926                         if (ret)
2927                                 uptodate = 0;
2928                         else
2929                                 clean_io_failure(BTRFS_I(inode)->root->fs_info,
2930                                                  failure_tree, tree, start,
2931                                                  page,
2932                                                  btrfs_ino(BTRFS_I(inode)), 0);
2933                 }
2934
2935                 if (likely(uptodate))
2936                         goto readpage_ok;
2937
2938                 if (is_data_inode(inode)) {
2939
2940                         /*
2941                          * The generic bio_readpage_error handles errors the
2942                          * following way: If possible, new read requests are
2943                          * created and submitted and will end up in
2944                          * end_bio_extent_readpage as well (if we're lucky,
2945                          * not in the !uptodate case). In that case it returns
2946                          * 0 and we just go on with the next page in our bio.
2947                          * If it can't handle the error it will return -EIO and
2948                          * we remain responsible for that page.
2949                          */
2950                         if (!btrfs_submit_read_repair(inode, bio, bio_offset,
2951                                                 page,
2952                                                 start - page_offset(page),
2953                                                 start, end, mirror,
2954                                                 btrfs_submit_data_bio)) {
2955                                 uptodate = !bio->bi_status;
2956                                 ASSERT(bio_offset + len > bio_offset);
2957                                 bio_offset += len;
2958                                 continue;
2959                         }
2960                 } else {
2961                         struct extent_buffer *eb;
2962
2963                         eb = (struct extent_buffer *)page->private;
2964                         set_bit(EXTENT_BUFFER_READ_ERR, &eb->bflags);
2965                         eb->read_mirror = mirror;
2966                         atomic_dec(&eb->io_pages);
2967                         if (test_and_clear_bit(EXTENT_BUFFER_READAHEAD,
2968                                                &eb->bflags))
2969                                 btree_readahead_hook(eb, -EIO);
2970                 }
2971 readpage_ok:
2972                 if (likely(uptodate)) {
2973                         loff_t i_size = i_size_read(inode);
2974                         pgoff_t end_index = i_size >> PAGE_SHIFT;
2975                         unsigned off;
2976
2977                         /* Zero out the end if this page straddles i_size */
2978                         off = offset_in_page(i_size);
2979                         if (page->index == end_index && off)
2980                                 zero_user_segment(page, off, PAGE_SIZE);
2981                 }
2982                 ASSERT(bio_offset + len > bio_offset);
2983                 bio_offset += len;
2984
2985                 /* Update page status and unlock */
2986                 endio_readpage_update_page_status(page, uptodate);
2987                 endio_readpage_release_extent(&processed, BTRFS_I(inode),
2988                                               start, end, uptodate);
2989         }
2990         /* Release the last extent */
2991         endio_readpage_release_extent(&processed, NULL, 0, 0, false);
2992         btrfs_io_bio_free_csum(io_bio);
2993         bio_put(bio);
2994 }
2995
2996 /*
2997  * Initialize the members up to but not including 'bio'. Use after allocating a
2998  * new bio by bio_alloc_bioset as it does not initialize the bytes outside of
2999  * 'bio' because use of __GFP_ZERO is not supported.
3000  */
3001 static inline void btrfs_io_bio_init(struct btrfs_io_bio *btrfs_bio)
3002 {
3003         memset(btrfs_bio, 0, offsetof(struct btrfs_io_bio, bio));
3004 }
3005
3006 /*
3007  * The following helpers allocate a bio. As it's backed by a bioset, it'll
3008  * never fail.  We're returning a bio right now but you can call btrfs_io_bio
3009  * for the appropriate container_of magic
3010  */
3011 struct bio *btrfs_bio_alloc(u64 first_byte)
3012 {
3013         struct bio *bio;
3014
3015         bio = bio_alloc_bioset(GFP_NOFS, BIO_MAX_PAGES, &btrfs_bioset);
3016         bio->bi_iter.bi_sector = first_byte >> 9;
3017         btrfs_io_bio_init(btrfs_io_bio(bio));
3018         return bio;
3019 }
3020
3021 struct bio *btrfs_bio_clone(struct bio *bio)
3022 {
3023         struct btrfs_io_bio *btrfs_bio;
3024         struct bio *new;
3025
3026         /* Bio allocation backed by a bioset does not fail */
3027         new = bio_clone_fast(bio, GFP_NOFS, &btrfs_bioset);
3028         btrfs_bio = btrfs_io_bio(new);
3029         btrfs_io_bio_init(btrfs_bio);
3030         btrfs_bio->iter = bio->bi_iter;
3031         return new;
3032 }
3033
3034 struct bio *btrfs_io_bio_alloc(unsigned int nr_iovecs)
3035 {
3036         struct bio *bio;
3037
3038         /* Bio allocation backed by a bioset does not fail */
3039         bio = bio_alloc_bioset(GFP_NOFS, nr_iovecs, &btrfs_bioset);
3040         btrfs_io_bio_init(btrfs_io_bio(bio));
3041         return bio;
3042 }
3043
3044 struct bio *btrfs_bio_clone_partial(struct bio *orig, int offset, int size)
3045 {
3046         struct bio *bio;
3047         struct btrfs_io_bio *btrfs_bio;
3048
3049         /* this will never fail when it's backed by a bioset */
3050         bio = bio_clone_fast(orig, GFP_NOFS, &btrfs_bioset);
3051         ASSERT(bio);
3052
3053         btrfs_bio = btrfs_io_bio(bio);
3054         btrfs_io_bio_init(btrfs_bio);
3055
3056         bio_trim(bio, offset >> 9, size >> 9);
3057         btrfs_bio->iter = bio->bi_iter;
3058         return bio;
3059 }
3060
3061 /*
3062  * @opf:        bio REQ_OP_* and REQ_* flags as one value
3063  * @wbc:        optional writeback control for io accounting
3064  * @page:       page to add to the bio
3065  * @disk_bytenr: logical bytenr where the write will be
3066  * @size:       portion of page that we want to write to
3067  * @pg_offset:  offset of the new bio or to check whether we are adding
3068  *              a contiguous page to the previous one
3069  * @bio_ret:    must be valid pointer, newly allocated bio will be stored there
3070  * @end_io_func:     end_io callback for new bio
3071  * @mirror_num:      desired mirror to read/write
3072  * @prev_bio_flags:  flags of previous bio to see if we can merge the current one
3073  * @bio_flags:  flags of the current bio to see if we can merge them
3074  */
3075 static int submit_extent_page(unsigned int opf,
3076                               struct writeback_control *wbc,
3077                               struct page *page, u64 disk_bytenr,
3078                               size_t size, unsigned long pg_offset,
3079                               struct bio **bio_ret,
3080                               bio_end_io_t end_io_func,
3081                               int mirror_num,
3082                               unsigned long prev_bio_flags,
3083                               unsigned long bio_flags,
3084                               bool force_bio_submit)
3085 {
3086         int ret = 0;
3087         struct bio *bio;
3088         size_t io_size = min_t(size_t, size, PAGE_SIZE);
3089         sector_t sector = disk_bytenr >> 9;
3090         struct extent_io_tree *tree = &BTRFS_I(page->mapping->host)->io_tree;
3091
3092         ASSERT(bio_ret);
3093
3094         if (*bio_ret) {
3095                 bool contig;
3096                 bool can_merge = true;
3097
3098                 bio = *bio_ret;
3099                 if (prev_bio_flags & EXTENT_BIO_COMPRESSED)
3100                         contig = bio->bi_iter.bi_sector == sector;
3101                 else
3102                         contig = bio_end_sector(bio) == sector;
3103
3104                 if (btrfs_bio_fits_in_stripe(page, io_size, bio, bio_flags))
3105                         can_merge = false;
3106
3107                 if (prev_bio_flags != bio_flags || !contig || !can_merge ||
3108                     force_bio_submit ||
3109                     bio_add_page(bio, page, io_size, pg_offset) < io_size) {
3110                         ret = submit_one_bio(bio, mirror_num, prev_bio_flags);
3111                         if (ret < 0) {
3112                                 *bio_ret = NULL;
3113                                 return ret;
3114                         }
3115                         bio = NULL;
3116                 } else {
3117                         if (wbc)
3118                                 wbc_account_cgroup_owner(wbc, page, io_size);
3119                         return 0;
3120                 }
3121         }
3122
3123         bio = btrfs_bio_alloc(disk_bytenr);
3124         bio_add_page(bio, page, io_size, pg_offset);
3125         bio->bi_end_io = end_io_func;
3126         bio->bi_private = tree;
3127         bio->bi_write_hint = page->mapping->host->i_write_hint;
3128         bio->bi_opf = opf;
3129         if (wbc) {
3130                 struct block_device *bdev;
3131
3132                 bdev = BTRFS_I(page->mapping->host)->root->fs_info->fs_devices->latest_bdev;
3133                 bio_set_dev(bio, bdev);
3134                 wbc_init_bio(wbc, bio);
3135                 wbc_account_cgroup_owner(wbc, page, io_size);
3136         }
3137
3138         *bio_ret = bio;
3139
3140         return ret;
3141 }
3142
3143 static void attach_extent_buffer_page(struct extent_buffer *eb,
3144                                       struct page *page)
3145 {
3146         /*
3147          * If the page is mapped to btree inode, we should hold the private
3148          * lock to prevent race.
3149          * For cloned or dummy extent buffers, their pages are not mapped and
3150          * will not race with any other ebs.
3151          */
3152         if (page->mapping)
3153                 lockdep_assert_held(&page->mapping->private_lock);
3154
3155         if (!PagePrivate(page))
3156                 attach_page_private(page, eb);
3157         else
3158                 WARN_ON(page->private != (unsigned long)eb);
3159 }
3160
3161 void set_page_extent_mapped(struct page *page)
3162 {
3163         if (!PagePrivate(page))
3164                 attach_page_private(page, (void *)EXTENT_PAGE_PRIVATE);
3165 }
3166
3167 static struct extent_map *
3168 __get_extent_map(struct inode *inode, struct page *page, size_t pg_offset,
3169                  u64 start, u64 len, struct extent_map **em_cached)
3170 {
3171         struct extent_map *em;
3172
3173         if (em_cached && *em_cached) {
3174                 em = *em_cached;
3175                 if (extent_map_in_tree(em) && start >= em->start &&
3176                     start < extent_map_end(em)) {
3177                         refcount_inc(&em->refs);
3178                         return em;
3179                 }
3180
3181                 free_extent_map(em);
3182                 *em_cached = NULL;
3183         }
3184
3185         em = btrfs_get_extent(BTRFS_I(inode), page, pg_offset, start, len);
3186         if (em_cached && !IS_ERR_OR_NULL(em)) {
3187                 BUG_ON(*em_cached);
3188                 refcount_inc(&em->refs);
3189                 *em_cached = em;
3190         }
3191         return em;
3192 }
3193 /*
3194  * basic readpage implementation.  Locked extent state structs are inserted
3195  * into the tree that are removed when the IO is done (by the end_io
3196  * handlers)
3197  * XXX JDM: This needs looking at to ensure proper page locking
3198  * return 0 on success, otherwise return error
3199  */
3200 int btrfs_do_readpage(struct page *page, struct extent_map **em_cached,
3201                       struct bio **bio, unsigned long *bio_flags,
3202                       unsigned int read_flags, u64 *prev_em_start)
3203 {
3204         struct inode *inode = page->mapping->host;
3205         u64 start = page_offset(page);
3206         const u64 end = start + PAGE_SIZE - 1;
3207         u64 cur = start;
3208         u64 extent_offset;
3209         u64 last_byte = i_size_read(inode);
3210         u64 block_start;
3211         u64 cur_end;
3212         struct extent_map *em;
3213         int ret = 0;
3214         int nr = 0;
3215         size_t pg_offset = 0;
3216         size_t iosize;
3217         size_t blocksize = inode->i_sb->s_blocksize;
3218         unsigned long this_bio_flag = 0;
3219         struct extent_io_tree *tree = &BTRFS_I(inode)->io_tree;
3220
3221         set_page_extent_mapped(page);
3222
3223         if (!PageUptodate(page)) {
3224                 if (cleancache_get_page(page) == 0) {
3225                         BUG_ON(blocksize != PAGE_SIZE);
3226                         unlock_extent(tree, start, end);
3227                         goto out;
3228                 }
3229         }
3230
3231         if (page->index == last_byte >> PAGE_SHIFT) {
3232                 char *userpage;
3233                 size_t zero_offset = offset_in_page(last_byte);
3234
3235                 if (zero_offset) {
3236                         iosize = PAGE_SIZE - zero_offset;
3237                         userpage = kmap_atomic(page);
3238                         memset(userpage + zero_offset, 0, iosize);
3239                         flush_dcache_page(page);
3240                         kunmap_atomic(userpage);
3241                 }
3242         }
3243         while (cur <= end) {
3244                 bool force_bio_submit = false;
3245                 u64 disk_bytenr;
3246
3247                 if (cur >= last_byte) {
3248                         char *userpage;
3249                         struct extent_state *cached = NULL;
3250
3251                         iosize = PAGE_SIZE - pg_offset;
3252                         userpage = kmap_atomic(page);
3253                         memset(userpage + pg_offset, 0, iosize);
3254                         flush_dcache_page(page);
3255                         kunmap_atomic(userpage);
3256                         set_extent_uptodate(tree, cur, cur + iosize - 1,
3257                                             &cached, GFP_NOFS);
3258                         unlock_extent_cached(tree, cur,
3259                                              cur + iosize - 1, &cached);
3260                         break;
3261                 }
3262                 em = __get_extent_map(inode, page, pg_offset, cur,
3263                                       end - cur + 1, em_cached);
3264                 if (IS_ERR_OR_NULL(em)) {
3265                         SetPageError(page);
3266                         unlock_extent(tree, cur, end);
3267                         break;
3268                 }
3269                 extent_offset = cur - em->start;
3270                 BUG_ON(extent_map_end(em) <= cur);
3271                 BUG_ON(end < cur);
3272
3273                 if (test_bit(EXTENT_FLAG_COMPRESSED, &em->flags)) {
3274                         this_bio_flag |= EXTENT_BIO_COMPRESSED;
3275                         extent_set_compress_type(&this_bio_flag,
3276                                                  em->compress_type);
3277                 }
3278
3279                 iosize = min(extent_map_end(em) - cur, end - cur + 1);
3280                 cur_end = min(extent_map_end(em) - 1, end);
3281                 iosize = ALIGN(iosize, blocksize);
3282                 if (this_bio_flag & EXTENT_BIO_COMPRESSED)
3283                         disk_bytenr = em->block_start;
3284                 else
3285                         disk_bytenr = em->block_start + extent_offset;
3286                 block_start = em->block_start;
3287                 if (test_bit(EXTENT_FLAG_PREALLOC, &em->flags))
3288                         block_start = EXTENT_MAP_HOLE;
3289
3290                 /*
3291                  * If we have a file range that points to a compressed extent
3292                  * and it's followed by a consecutive file range that points
3293                  * to the same compressed extent (possibly with a different
3294                  * offset and/or length, so it either points to the whole extent
3295                  * or only part of it), we must make sure we do not submit a
3296                  * single bio to populate the pages for the 2 ranges because
3297                  * this makes the compressed extent read zero out the pages
3298                  * belonging to the 2nd range. Imagine the following scenario:
3299                  *
3300                  *  File layout
3301                  *  [0 - 8K]                     [8K - 24K]
3302                  *    |                               |
3303                  *    |                               |
3304                  * points to extent X,         points to extent X,
3305                  * offset 4K, length of 8K     offset 0, length 16K
3306                  *
3307                  * [extent X, compressed length = 4K uncompressed length = 16K]
3308                  *
3309                  * If the bio to read the compressed extent covers both ranges,
3310                  * it will decompress extent X into the pages belonging to the
3311                  * first range and then it will stop, zeroing out the remaining
3312                  * pages that belong to the other range that points to extent X.
3313                  * So here we make sure we submit 2 bios, one for the first
3314                  * range and another one for the third range. Both will target
3315                  * the same physical extent from disk, but we can't currently
3316                  * make the compressed bio endio callback populate the pages
3317                  * for both ranges because each compressed bio is tightly
3318                  * coupled with a single extent map, and each range can have
3319                  * an extent map with a different offset value relative to the
3320                  * uncompressed data of our extent and different lengths. This
3321                  * is a corner case so we prioritize correctness over
3322                  * non-optimal behavior (submitting 2 bios for the same extent).
3323                  */
3324                 if (test_bit(EXTENT_FLAG_COMPRESSED, &em->flags) &&
3325                     prev_em_start && *prev_em_start != (u64)-1 &&
3326                     *prev_em_start != em->start)
3327                         force_bio_submit = true;
3328
3329                 if (prev_em_start)
3330                         *prev_em_start = em->start;
3331
3332                 free_extent_map(em);
3333                 em = NULL;
3334
3335                 /* we've found a hole, just zero and go on */
3336                 if (block_start == EXTENT_MAP_HOLE) {
3337                         char *userpage;
3338                         struct extent_state *cached = NULL;
3339
3340                         userpage = kmap_atomic(page);
3341                         memset(userpage + pg_offset, 0, iosize);
3342                         flush_dcache_page(page);
3343                         kunmap_atomic(userpage);
3344
3345                         set_extent_uptodate(tree, cur, cur + iosize - 1,
3346                                             &cached, GFP_NOFS);
3347                         unlock_extent_cached(tree, cur,
3348                                              cur + iosize - 1, &cached);
3349                         cur = cur + iosize;
3350                         pg_offset += iosize;
3351                         continue;
3352                 }
3353                 /* the get_extent function already copied into the page */
3354                 if (test_range_bit(tree, cur, cur_end,
3355                                    EXTENT_UPTODATE, 1, NULL)) {
3356                         check_page_uptodate(tree, page);
3357                         unlock_extent(tree, cur, cur + iosize - 1);
3358                         cur = cur + iosize;
3359                         pg_offset += iosize;
3360                         continue;
3361                 }
3362                 /* we have an inline extent but it didn't get marked up
3363                  * to date.  Error out
3364                  */
3365                 if (block_start == EXTENT_MAP_INLINE) {
3366                         SetPageError(page);
3367                         unlock_extent(tree, cur, cur + iosize - 1);
3368                         cur = cur + iosize;
3369                         pg_offset += iosize;
3370                         continue;
3371                 }
3372
3373                 ret = submit_extent_page(REQ_OP_READ | read_flags, NULL,
3374                                          page, disk_bytenr, iosize,
3375                                          pg_offset, bio,
3376                                          end_bio_extent_readpage, 0,
3377                                          *bio_flags,
3378                                          this_bio_flag,
3379                                          force_bio_submit);
3380                 if (!ret) {
3381                         nr++;
3382                         *bio_flags = this_bio_flag;
3383                 } else {
3384                         SetPageError(page);
3385                         unlock_extent(tree, cur, cur + iosize - 1);
3386                         goto out;
3387                 }
3388                 cur = cur + iosize;
3389                 pg_offset += iosize;
3390         }
3391 out:
3392         if (!nr) {
3393                 if (!PageError(page))
3394                         SetPageUptodate(page);
3395                 unlock_page(page);
3396         }
3397         return ret;
3398 }
3399
3400 static inline void contiguous_readpages(struct page *pages[], int nr_pages,
3401                                              u64 start, u64 end,
3402                                              struct extent_map **em_cached,
3403                                              struct bio **bio,
3404                                              unsigned long *bio_flags,
3405                                              u64 *prev_em_start)
3406 {
3407         struct btrfs_inode *inode = BTRFS_I(pages[0]->mapping->host);
3408         int index;
3409
3410         btrfs_lock_and_flush_ordered_range(inode, start, end, NULL);
3411
3412         for (index = 0; index < nr_pages; index++) {
3413                 btrfs_do_readpage(pages[index], em_cached, bio, bio_flags,
3414                                   REQ_RAHEAD, prev_em_start);
3415                 put_page(pages[index]);
3416         }
3417 }
3418
3419 static void update_nr_written(struct writeback_control *wbc,
3420                               unsigned long nr_written)
3421 {
3422         wbc->nr_to_write -= nr_written;
3423 }
3424
3425 /*
3426  * helper for __extent_writepage, doing all of the delayed allocation setup.
3427  *
3428  * This returns 1 if btrfs_run_delalloc_range function did all the work required
3429  * to write the page (copy into inline extent).  In this case the IO has
3430  * been started and the page is already unlocked.
3431  *
3432  * This returns 0 if all went well (page still locked)
3433  * This returns < 0 if there were errors (page still locked)
3434  */
3435 static noinline_for_stack int writepage_delalloc(struct btrfs_inode *inode,
3436                 struct page *page, struct writeback_control *wbc,
3437                 u64 delalloc_start, unsigned long *nr_written)
3438 {
3439         u64 page_end = delalloc_start + PAGE_SIZE - 1;
3440         bool found;
3441         u64 delalloc_to_write = 0;
3442         u64 delalloc_end = 0;
3443         int ret;
3444         int page_started = 0;
3445
3446
3447         while (delalloc_end < page_end) {
3448                 found = find_lock_delalloc_range(&inode->vfs_inode, page,
3449                                                &delalloc_start,
3450                                                &delalloc_end);
3451                 if (!found) {
3452                         delalloc_start = delalloc_end + 1;
3453                         continue;
3454                 }
3455                 ret = btrfs_run_delalloc_range(inode, page, delalloc_start,
3456                                 delalloc_end, &page_started, nr_written, wbc);
3457                 if (ret) {
3458                         SetPageError(page);
3459                         /*
3460                          * btrfs_run_delalloc_range should return < 0 for error
3461                          * but just in case, we use > 0 here meaning the IO is
3462                          * started, so we don't want to return > 0 unless
3463                          * things are going well.
3464                          */
3465                         return ret < 0 ? ret : -EIO;
3466                 }
3467                 /*
3468                  * delalloc_end is already one less than the total length, so
3469                  * we don't subtract one from PAGE_SIZE
3470                  */
3471                 delalloc_to_write += (delalloc_end - delalloc_start +
3472                                       PAGE_SIZE) >> PAGE_SHIFT;
3473                 delalloc_start = delalloc_end + 1;
3474         }
3475         if (wbc->nr_to_write < delalloc_to_write) {
3476                 int thresh = 8192;
3477
3478                 if (delalloc_to_write < thresh * 2)
3479                         thresh = delalloc_to_write;
3480                 wbc->nr_to_write = min_t(u64, delalloc_to_write,
3481                                          thresh);
3482         }
3483
3484         /* did the fill delalloc function already unlock and start
3485          * the IO?
3486          */
3487         if (page_started) {
3488                 /*
3489                  * we've unlocked the page, so we can't update
3490                  * the mapping's writeback index, just update
3491                  * nr_to_write.
3492                  */
3493                 wbc->nr_to_write -= *nr_written;
3494                 return 1;
3495         }
3496
3497         return 0;
3498 }
3499
3500 /*
3501  * helper for __extent_writepage.  This calls the writepage start hooks,
3502  * and does the loop to map the page into extents and bios.
3503  *
3504  * We return 1 if the IO is started and the page is unlocked,
3505  * 0 if all went well (page still locked)
3506  * < 0 if there were errors (page still locked)
3507  */
3508 static noinline_for_stack int __extent_writepage_io(struct btrfs_inode *inode,
3509                                  struct page *page,
3510                                  struct writeback_control *wbc,
3511                                  struct extent_page_data *epd,
3512                                  loff_t i_size,
3513                                  unsigned long nr_written,
3514                                  int *nr_ret)
3515 {
3516         struct btrfs_fs_info *fs_info = inode->root->fs_info;
3517         struct extent_io_tree *tree = &inode->io_tree;
3518         u64 start = page_offset(page);
3519         u64 end = start + PAGE_SIZE - 1;
3520         u64 cur = start;
3521         u64 extent_offset;
3522         u64 block_start;
3523         struct extent_map *em;
3524         int ret = 0;
3525         int nr = 0;
3526         const unsigned int write_flags = wbc_to_write_flags(wbc);
3527         bool compressed;
3528
3529         ret = btrfs_writepage_cow_fixup(page, start, end);
3530         if (ret) {
3531                 /* Fixup worker will requeue */
3532                 redirty_page_for_writepage(wbc, page);
3533                 update_nr_written(wbc, nr_written);
3534                 unlock_page(page);
3535                 return 1;
3536         }
3537
3538         /*
3539          * we don't want to touch the inode after unlocking the page,
3540          * so we update the mapping writeback index now
3541          */
3542         update_nr_written(wbc, nr_written + 1);
3543
3544         while (cur <= end) {
3545                 u64 disk_bytenr;
3546                 u64 em_end;
3547                 u32 iosize;
3548
3549                 if (cur >= i_size) {
3550                         btrfs_writepage_endio_finish_ordered(page, cur, end, 1);
3551                         break;
3552                 }
3553                 em = btrfs_get_extent(inode, NULL, 0, cur, end - cur + 1);
3554                 if (IS_ERR_OR_NULL(em)) {
3555                         SetPageError(page);
3556                         ret = PTR_ERR_OR_ZERO(em);
3557                         break;
3558                 }
3559
3560                 extent_offset = cur - em->start;
3561                 em_end = extent_map_end(em);
3562                 ASSERT(cur <= em_end);
3563                 ASSERT(cur < end);
3564                 ASSERT(IS_ALIGNED(em->start, fs_info->sectorsize));
3565                 ASSERT(IS_ALIGNED(em->len, fs_info->sectorsize));
3566                 block_start = em->block_start;
3567                 compressed = test_bit(EXTENT_FLAG_COMPRESSED, &em->flags);
3568                 disk_bytenr = em->block_start + extent_offset;
3569
3570                 /* Note that em_end from extent_map_end() is exclusive */
3571                 iosize = min(em_end, end + 1) - cur;
3572                 free_extent_map(em);
3573                 em = NULL;
3574
3575                 /*
3576                  * compressed and inline extents are written through other
3577                  * paths in the FS
3578                  */
3579                 if (compressed || block_start == EXTENT_MAP_HOLE ||
3580                     block_start == EXTENT_MAP_INLINE) {
3581                         if (compressed)
3582                                 nr++;
3583                         else
3584                                 btrfs_writepage_endio_finish_ordered(page, cur,
3585                                                         cur + iosize - 1, 1);
3586                         cur += iosize;
3587                         continue;
3588                 }
3589
3590                 btrfs_set_range_writeback(tree, cur, cur + iosize - 1);
3591                 if (!PageWriteback(page)) {
3592                         btrfs_err(inode->root->fs_info,
3593                                    "page %lu not writeback, cur %llu end %llu",
3594                                page->index, cur, end);
3595                 }
3596
3597                 ret = submit_extent_page(REQ_OP_WRITE | write_flags, wbc,
3598                                          page, disk_bytenr, iosize,
3599                                          cur - page_offset(page), &epd->bio,
3600                                          end_bio_extent_writepage,
3601                                          0, 0, 0, false);
3602                 if (ret) {
3603                         SetPageError(page);
3604                         if (PageWriteback(page))
3605                                 end_page_writeback(page);
3606                 }
3607
3608                 cur += iosize;
3609                 nr++;
3610         }
3611         *nr_ret = nr;
3612         return ret;
3613 }
3614
3615 /*
3616  * the writepage semantics are similar to regular writepage.  extent
3617  * records are inserted to lock ranges in the tree, and as dirty areas
3618  * are found, they are marked writeback.  Then the lock bits are removed
3619  * and the end_io handler clears the writeback ranges
3620  *
3621  * Return 0 if everything goes well.
3622  * Return <0 for error.
3623  */
3624 static int __extent_writepage(struct page *page, struct writeback_control *wbc,
3625                               struct extent_page_data *epd)
3626 {
3627         struct inode *inode = page->mapping->host;
3628         u64 start = page_offset(page);
3629         u64 page_end = start + PAGE_SIZE - 1;
3630         int ret;
3631         int nr = 0;
3632         size_t pg_offset;
3633         loff_t i_size = i_size_read(inode);
3634         unsigned long end_index = i_size >> PAGE_SHIFT;
3635         unsigned long nr_written = 0;
3636
3637         trace___extent_writepage(page, inode, wbc);
3638
3639         WARN_ON(!PageLocked(page));
3640
3641         ClearPageError(page);
3642
3643         pg_offset = offset_in_page(i_size);
3644         if (page->index > end_index ||
3645            (page->index == end_index && !pg_offset)) {
3646                 page->mapping->a_ops->invalidatepage(page, 0, PAGE_SIZE);
3647                 unlock_page(page);
3648                 return 0;
3649         }
3650
3651         if (page->index == end_index) {
3652                 char *userpage;
3653
3654                 userpage = kmap_atomic(page);
3655                 memset(userpage + pg_offset, 0,
3656                        PAGE_SIZE - pg_offset);
3657                 kunmap_atomic(userpage);
3658                 flush_dcache_page(page);
3659         }
3660
3661         set_page_extent_mapped(page);
3662
3663         if (!epd->extent_locked) {
3664                 ret = writepage_delalloc(BTRFS_I(inode), page, wbc, start,
3665                                          &nr_written);
3666                 if (ret == 1)
3667                         return 0;
3668                 if (ret)
3669                         goto done;
3670         }
3671
3672         ret = __extent_writepage_io(BTRFS_I(inode), page, wbc, epd, i_size,
3673                                     nr_written, &nr);
3674         if (ret == 1)
3675                 return 0;
3676
3677 done:
3678         if (nr == 0) {
3679                 /* make sure the mapping tag for page dirty gets cleared */
3680                 set_page_writeback(page);
3681                 end_page_writeback(page);
3682         }
3683         if (PageError(page)) {
3684                 ret = ret < 0 ? ret : -EIO;
3685                 end_extent_writepage(page, ret, start, page_end);
3686         }
3687         unlock_page(page);
3688         ASSERT(ret <= 0);
3689         return ret;
3690 }
3691
3692 void wait_on_extent_buffer_writeback(struct extent_buffer *eb)
3693 {
3694         wait_on_bit_io(&eb->bflags, EXTENT_BUFFER_WRITEBACK,
3695                        TASK_UNINTERRUPTIBLE);
3696 }
3697
3698 static void end_extent_buffer_writeback(struct extent_buffer *eb)
3699 {
3700         clear_bit(EXTENT_BUFFER_WRITEBACK, &eb->bflags);
3701         smp_mb__after_atomic();
3702         wake_up_bit(&eb->bflags, EXTENT_BUFFER_WRITEBACK);
3703 }
3704
3705 /*
3706  * Lock extent buffer status and pages for writeback.
3707  *
3708  * May try to flush write bio if we can't get the lock.
3709  *
3710  * Return  0 if the extent buffer doesn't need to be submitted.
3711  *           (E.g. the extent buffer is not dirty)
3712  * Return >0 is the extent buffer is submitted to bio.
3713  * Return <0 if something went wrong, no page is locked.
3714  */
3715 static noinline_for_stack int lock_extent_buffer_for_io(struct extent_buffer *eb,
3716                           struct extent_page_data *epd)
3717 {
3718         struct btrfs_fs_info *fs_info = eb->fs_info;
3719         int i, num_pages, failed_page_nr;
3720         int flush = 0;
3721         int ret = 0;
3722
3723         if (!btrfs_try_tree_write_lock(eb)) {
3724                 ret = flush_write_bio(epd);
3725                 if (ret < 0)
3726                         return ret;
3727                 flush = 1;
3728                 btrfs_tree_lock(eb);
3729         }
3730
3731         if (test_bit(EXTENT_BUFFER_WRITEBACK, &eb->bflags)) {
3732                 btrfs_tree_unlock(eb);
3733                 if (!epd->sync_io)
3734                         return 0;
3735                 if (!flush) {
3736                         ret = flush_write_bio(epd);
3737                         if (ret < 0)
3738                                 return ret;
3739                         flush = 1;
3740                 }
3741                 while (1) {
3742                         wait_on_extent_buffer_writeback(eb);
3743                         btrfs_tree_lock(eb);
3744                         if (!test_bit(EXTENT_BUFFER_WRITEBACK, &eb->bflags))
3745                                 break;
3746                         btrfs_tree_unlock(eb);
3747                 }
3748         }
3749
3750         /*
3751          * We need to do this to prevent races in people who check if the eb is
3752          * under IO since we can end up having no IO bits set for a short period
3753          * of time.
3754          */
3755         spin_lock(&eb->refs_lock);
3756         if (test_and_clear_bit(EXTENT_BUFFER_DIRTY, &eb->bflags)) {
3757                 set_bit(EXTENT_BUFFER_WRITEBACK, &eb->bflags);
3758                 spin_unlock(&eb->refs_lock);
3759                 btrfs_set_header_flag(eb, BTRFS_HEADER_FLAG_WRITTEN);
3760                 percpu_counter_add_batch(&fs_info->dirty_metadata_bytes,
3761                                          -eb->len,
3762                                          fs_info->dirty_metadata_batch);
3763                 ret = 1;
3764         } else {
3765                 spin_unlock(&eb->refs_lock);
3766         }
3767
3768         btrfs_tree_unlock(eb);
3769
3770         if (!ret)
3771                 return ret;
3772
3773         num_pages = num_extent_pages(eb);
3774         for (i = 0; i < num_pages; i++) {
3775                 struct page *p = eb->pages[i];
3776
3777                 if (!trylock_page(p)) {
3778                         if (!flush) {
3779                                 int err;
3780
3781                                 err = flush_write_bio(epd);
3782                                 if (err < 0) {
3783                                         ret = err;
3784                                         failed_page_nr = i;
3785                                         goto err_unlock;
3786                                 }
3787                                 flush = 1;
3788                         }
3789                         lock_page(p);
3790                 }
3791         }
3792
3793         return ret;
3794 err_unlock:
3795         /* Unlock already locked pages */
3796         for (i = 0; i < failed_page_nr; i++)
3797                 unlock_page(eb->pages[i]);
3798         /*
3799          * Clear EXTENT_BUFFER_WRITEBACK and wake up anyone waiting on it.
3800          * Also set back EXTENT_BUFFER_DIRTY so future attempts to this eb can
3801          * be made and undo everything done before.
3802          */
3803         btrfs_tree_lock(eb);
3804         spin_lock(&eb->refs_lock);
3805         set_bit(EXTENT_BUFFER_DIRTY, &eb->bflags);
3806         end_extent_buffer_writeback(eb);
3807         spin_unlock(&eb->refs_lock);
3808         percpu_counter_add_batch(&fs_info->dirty_metadata_bytes, eb->len,
3809                                  fs_info->dirty_metadata_batch);
3810         btrfs_clear_header_flag(eb, BTRFS_HEADER_FLAG_WRITTEN);
3811         btrfs_tree_unlock(eb);
3812         return ret;
3813 }
3814
3815 static void set_btree_ioerr(struct page *page)
3816 {
3817         struct extent_buffer *eb = (struct extent_buffer *)page->private;
3818         struct btrfs_fs_info *fs_info;
3819
3820         SetPageError(page);
3821         if (test_and_set_bit(EXTENT_BUFFER_WRITE_ERR, &eb->bflags))
3822                 return;
3823
3824         /*
3825          * If we error out, we should add back the dirty_metadata_bytes
3826          * to make it consistent.
3827          */
3828         fs_info = eb->fs_info;
3829         percpu_counter_add_batch(&fs_info->dirty_metadata_bytes,
3830                                  eb->len, fs_info->dirty_metadata_batch);
3831
3832         /*
3833          * If writeback for a btree extent that doesn't belong to a log tree
3834          * failed, increment the counter transaction->eb_write_errors.
3835          * We do this because while the transaction is running and before it's
3836          * committing (when we call filemap_fdata[write|wait]_range against
3837          * the btree inode), we might have
3838          * btree_inode->i_mapping->a_ops->writepages() called by the VM - if it
3839          * returns an error or an error happens during writeback, when we're
3840          * committing the transaction we wouldn't know about it, since the pages
3841          * can be no longer dirty nor marked anymore for writeback (if a
3842          * subsequent modification to the extent buffer didn't happen before the
3843          * transaction commit), which makes filemap_fdata[write|wait]_range not
3844          * able to find the pages tagged with SetPageError at transaction
3845          * commit time. So if this happens we must abort the transaction,
3846          * otherwise we commit a super block with btree roots that point to
3847          * btree nodes/leafs whose content on disk is invalid - either garbage
3848          * or the content of some node/leaf from a past generation that got
3849          * cowed or deleted and is no longer valid.
3850          *
3851          * Note: setting AS_EIO/AS_ENOSPC in the btree inode's i_mapping would
3852          * not be enough - we need to distinguish between log tree extents vs
3853          * non-log tree extents, and the next filemap_fdatawait_range() call
3854          * will catch and clear such errors in the mapping - and that call might
3855          * be from a log sync and not from a transaction commit. Also, checking
3856          * for the eb flag EXTENT_BUFFER_WRITE_ERR at transaction commit time is
3857          * not done and would not be reliable - the eb might have been released
3858          * from memory and reading it back again means that flag would not be
3859          * set (since it's a runtime flag, not persisted on disk).
3860          *
3861          * Using the flags below in the btree inode also makes us achieve the
3862          * goal of AS_EIO/AS_ENOSPC when writepages() returns success, started
3863          * writeback for all dirty pages and before filemap_fdatawait_range()
3864          * is called, the writeback for all dirty pages had already finished
3865          * with errors - because we were not using AS_EIO/AS_ENOSPC,
3866          * filemap_fdatawait_range() would return success, as it could not know
3867          * that writeback errors happened (the pages were no longer tagged for
3868          * writeback).
3869          */
3870         switch (eb->log_index) {
3871         case -1:
3872                 set_bit(BTRFS_FS_BTREE_ERR, &eb->fs_info->flags);
3873                 break;
3874         case 0:
3875                 set_bit(BTRFS_FS_LOG1_ERR, &eb->fs_info->flags);
3876                 break;
3877         case 1:
3878                 set_bit(BTRFS_FS_LOG2_ERR, &eb->fs_info->flags);
3879                 break;
3880         default:
3881                 BUG(); /* unexpected, logic error */
3882         }
3883 }
3884
3885 static void end_bio_extent_buffer_writepage(struct bio *bio)
3886 {
3887         struct bio_vec *bvec;
3888         struct extent_buffer *eb;
3889         int done;
3890         struct bvec_iter_all iter_all;
3891
3892         ASSERT(!bio_flagged(bio, BIO_CLONED));
3893         bio_for_each_segment_all(bvec, bio, iter_all) {
3894                 struct page *page = bvec->bv_page;
3895
3896                 eb = (struct extent_buffer *)page->private;
3897                 BUG_ON(!eb);
3898                 done = atomic_dec_and_test(&eb->io_pages);
3899
3900                 if (bio->bi_status ||
3901                     test_bit(EXTENT_BUFFER_WRITE_ERR, &eb->bflags)) {
3902                         ClearPageUptodate(page);
3903                         set_btree_ioerr(page);
3904                 }
3905
3906                 end_page_writeback(page);
3907
3908                 if (!done)
3909                         continue;
3910
3911                 end_extent_buffer_writeback(eb);
3912         }
3913
3914         bio_put(bio);
3915 }
3916
3917 static noinline_for_stack int write_one_eb(struct extent_buffer *eb,
3918                         struct writeback_control *wbc,
3919                         struct extent_page_data *epd)
3920 {
3921         u64 disk_bytenr = eb->start;
3922         u32 nritems;
3923         int i, num_pages;
3924         unsigned long start, end;
3925         unsigned int write_flags = wbc_to_write_flags(wbc) | REQ_META;
3926         int ret = 0;
3927
3928         clear_bit(EXTENT_BUFFER_WRITE_ERR, &eb->bflags);
3929         num_pages = num_extent_pages(eb);
3930         atomic_set(&eb->io_pages, num_pages);
3931
3932         /* set btree blocks beyond nritems with 0 to avoid stale content. */
3933         nritems = btrfs_header_nritems(eb);
3934         if (btrfs_header_level(eb) > 0) {
3935                 end = btrfs_node_key_ptr_offset(nritems);
3936
3937                 memzero_extent_buffer(eb, end, eb->len - end);
3938         } else {
3939                 /*
3940                  * leaf:
3941                  * header 0 1 2 .. N ... data_N .. data_2 data_1 data_0
3942                  */
3943                 start = btrfs_item_nr_offset(nritems);
3944                 end = BTRFS_LEAF_DATA_OFFSET + leaf_data_end(eb);
3945                 memzero_extent_buffer(eb, start, end - start);
3946         }
3947
3948         for (i = 0; i < num_pages; i++) {
3949                 struct page *p = eb->pages[i];
3950
3951                 clear_page_dirty_for_io(p);
3952                 set_page_writeback(p);
3953                 ret = submit_extent_page(REQ_OP_WRITE | write_flags, wbc,
3954                                          p, disk_bytenr, PAGE_SIZE, 0,
3955                                          &epd->bio,
3956                                          end_bio_extent_buffer_writepage,
3957                                          0, 0, 0, false);
3958                 if (ret) {
3959                         set_btree_ioerr(p);
3960                         if (PageWriteback(p))
3961                                 end_page_writeback(p);
3962                         if (atomic_sub_and_test(num_pages - i, &eb->io_pages))
3963                                 end_extent_buffer_writeback(eb);
3964                         ret = -EIO;
3965                         break;
3966                 }
3967                 disk_bytenr += PAGE_SIZE;
3968                 update_nr_written(wbc, 1);
3969                 unlock_page(p);
3970         }
3971
3972         if (unlikely(ret)) {
3973                 for (; i < num_pages; i++) {
3974                         struct page *p = eb->pages[i];
3975                         clear_page_dirty_for_io(p);
3976                         unlock_page(p);
3977                 }
3978         }
3979
3980         return ret;
3981 }
3982
3983 /*
3984  * Submit all page(s) of one extent buffer.
3985  *
3986  * @page:       the page of one extent buffer
3987  * @eb_context: to determine if we need to submit this page, if current page
3988  *              belongs to this eb, we don't need to submit
3989  *
3990  * The caller should pass each page in their bytenr order, and here we use
3991  * @eb_context to determine if we have submitted pages of one extent buffer.
3992  *
3993  * If we have, we just skip until we hit a new page that doesn't belong to
3994  * current @eb_context.
3995  *
3996  * If not, we submit all the page(s) of the extent buffer.
3997  *
3998  * Return >0 if we have submitted the extent buffer successfully.
3999  * Return 0 if we don't need to submit the page, as it's already submitted by
4000  * previous call.
4001  * Return <0 for fatal error.
4002  */
4003 static int submit_eb_page(struct page *page, struct writeback_control *wbc,
4004                           struct extent_page_data *epd,
4005                           struct extent_buffer **eb_context)
4006 {
4007         struct address_space *mapping = page->mapping;
4008         struct extent_buffer *eb;
4009         int ret;
4010
4011         if (!PagePrivate(page))
4012                 return 0;
4013
4014         spin_lock(&mapping->private_lock);
4015         if (!PagePrivate(page)) {
4016                 spin_unlock(&mapping->private_lock);
4017                 return 0;
4018         }
4019
4020         eb = (struct extent_buffer *)page->private;
4021
4022         /*
4023          * Shouldn't happen and normally this would be a BUG_ON but no point
4024          * crashing the machine for something we can survive anyway.
4025          */
4026         if (WARN_ON(!eb)) {
4027                 spin_unlock(&mapping->private_lock);
4028                 return 0;
4029         }
4030
4031         if (eb == *eb_context) {
4032                 spin_unlock(&mapping->private_lock);
4033                 return 0;
4034         }
4035         ret = atomic_inc_not_zero(&eb->refs);
4036         spin_unlock(&mapping->private_lock);
4037         if (!ret)
4038                 return 0;
4039
4040         *eb_context = eb;
4041
4042         ret = lock_extent_buffer_for_io(eb, epd);
4043         if (ret <= 0) {
4044                 free_extent_buffer(eb);
4045                 return ret;
4046         }
4047         ret = write_one_eb(eb, wbc, epd);
4048         free_extent_buffer(eb);
4049         if (ret < 0)
4050                 return ret;
4051         return 1;
4052 }
4053
4054 int btree_write_cache_pages(struct address_space *mapping,
4055                                    struct writeback_control *wbc)
4056 {
4057         struct extent_buffer *eb_context = NULL;
4058         struct extent_page_data epd = {
4059                 .bio = NULL,
4060                 .extent_locked = 0,
4061                 .sync_io = wbc->sync_mode == WB_SYNC_ALL,
4062         };
4063         struct btrfs_fs_info *fs_info = BTRFS_I(mapping->host)->root->fs_info;
4064         int ret = 0;
4065         int done = 0;
4066         int nr_to_write_done = 0;
4067         struct pagevec pvec;
4068         int nr_pages;
4069         pgoff_t index;
4070         pgoff_t end;            /* Inclusive */
4071         int scanned = 0;
4072         xa_mark_t tag;
4073
4074         pagevec_init(&pvec);
4075         if (wbc->range_cyclic) {
4076                 index = mapping->writeback_index; /* Start from prev offset */
4077                 end = -1;
4078                 /*
4079                  * Start from the beginning does not need to cycle over the
4080                  * range, mark it as scanned.
4081                  */
4082                 scanned = (index == 0);
4083         } else {
4084                 index = wbc->range_start >> PAGE_SHIFT;
4085                 end = wbc->range_end >> PAGE_SHIFT;
4086                 scanned = 1;
4087         }
4088         if (wbc->sync_mode == WB_SYNC_ALL)
4089                 tag = PAGECACHE_TAG_TOWRITE;
4090         else
4091                 tag = PAGECACHE_TAG_DIRTY;
4092 retry:
4093         if (wbc->sync_mode == WB_SYNC_ALL)
4094                 tag_pages_for_writeback(mapping, index, end);
4095         while (!done && !nr_to_write_done && (index <= end) &&
4096                (nr_pages = pagevec_lookup_range_tag(&pvec, mapping, &index, end,
4097                         tag))) {
4098                 unsigned i;
4099
4100                 for (i = 0; i < nr_pages; i++) {
4101                         struct page *page = pvec.pages[i];
4102
4103                         ret = submit_eb_page(page, wbc, &epd, &eb_context);
4104                         if (ret == 0)
4105                                 continue;
4106                         if (ret < 0) {
4107                                 done = 1;
4108                                 break;
4109                         }
4110
4111                         /*
4112                          * the filesystem may choose to bump up nr_to_write.
4113                          * We have to make sure to honor the new nr_to_write
4114                          * at any time
4115                          */
4116                         nr_to_write_done = wbc->nr_to_write <= 0;
4117                 }
4118                 pagevec_release(&pvec);
4119                 cond_resched();
4120         }
4121         if (!scanned && !done) {
4122                 /*
4123                  * We hit the last page and there is more work to be done: wrap
4124                  * back to the start of the file
4125                  */
4126                 scanned = 1;
4127                 index = 0;
4128                 goto retry;
4129         }
4130         if (ret < 0) {
4131                 end_write_bio(&epd, ret);
4132                 return ret;
4133         }
4134         /*
4135          * If something went wrong, don't allow any metadata write bio to be
4136          * submitted.
4137          *
4138          * This would prevent use-after-free if we had dirty pages not
4139          * cleaned up, which can still happen by fuzzed images.
4140          *
4141          * - Bad extent tree
4142          *   Allowing existing tree block to be allocated for other trees.
4143          *
4144          * - Log tree operations
4145          *   Exiting tree blocks get allocated to log tree, bumps its
4146          *   generation, then get cleaned in tree re-balance.
4147          *   Such tree block will not be written back, since it's clean,
4148          *   thus no WRITTEN flag set.
4149          *   And after log writes back, this tree block is not traced by
4150          *   any dirty extent_io_tree.
4151          *
4152          * - Offending tree block gets re-dirtied from its original owner
4153          *   Since it has bumped generation, no WRITTEN flag, it can be
4154          *   reused without COWing. This tree block will not be traced
4155          *   by btrfs_transaction::dirty_pages.
4156          *
4157          *   Now such dirty tree block will not be cleaned by any dirty
4158          *   extent io tree. Thus we don't want to submit such wild eb
4159          *   if the fs already has error.
4160          */
4161         if (!test_bit(BTRFS_FS_STATE_ERROR, &fs_info->fs_state)) {
4162                 ret = flush_write_bio(&epd);
4163         } else {
4164                 ret = -EROFS;
4165                 end_write_bio(&epd, ret);
4166         }
4167         return ret;
4168 }
4169
4170 /**
4171  * write_cache_pages - walk the list of dirty pages of the given address space and write all of them.
4172  * @mapping: address space structure to write
4173  * @wbc: subtract the number of written pages from *@wbc->nr_to_write
4174  * @data: data passed to __extent_writepage function
4175  *
4176  * If a page is already under I/O, write_cache_pages() skips it, even
4177  * if it's dirty.  This is desirable behaviour for memory-cleaning writeback,
4178  * but it is INCORRECT for data-integrity system calls such as fsync().  fsync()
4179  * and msync() need to guarantee that all the data which was dirty at the time
4180  * the call was made get new I/O started against them.  If wbc->sync_mode is
4181  * WB_SYNC_ALL then we were called for data integrity and we must wait for
4182  * existing IO to complete.
4183  */
4184 static int extent_write_cache_pages(struct address_space *mapping,
4185                              struct writeback_control *wbc,
4186                              struct extent_page_data *epd)
4187 {
4188         struct inode *inode = mapping->host;
4189         int ret = 0;
4190         int done = 0;
4191         int nr_to_write_done = 0;
4192         struct pagevec pvec;
4193         int nr_pages;
4194         pgoff_t index;
4195         pgoff_t end;            /* Inclusive */
4196         pgoff_t done_index;
4197         int range_whole = 0;
4198         int scanned = 0;
4199         xa_mark_t tag;
4200
4201         /*
4202          * We have to hold onto the inode so that ordered extents can do their
4203          * work when the IO finishes.  The alternative to this is failing to add
4204          * an ordered extent if the igrab() fails there and that is a huge pain
4205          * to deal with, so instead just hold onto the inode throughout the
4206          * writepages operation.  If it fails here we are freeing up the inode
4207          * anyway and we'd rather not waste our time writing out stuff that is
4208          * going to be truncated anyway.
4209          */
4210         if (!igrab(inode))
4211                 return 0;
4212
4213         pagevec_init(&pvec);
4214         if (wbc->range_cyclic) {
4215                 index = mapping->writeback_index; /* Start from prev offset */
4216                 end = -1;
4217                 /*
4218                  * Start from the beginning does not need to cycle over the
4219                  * range, mark it as scanned.
4220                  */
4221                 scanned = (index == 0);
4222         } else {
4223                 index = wbc->range_start >> PAGE_SHIFT;
4224                 end = wbc->range_end >> PAGE_SHIFT;
4225                 if (wbc->range_start == 0 && wbc->range_end == LLONG_MAX)
4226                         range_whole = 1;
4227                 scanned = 1;
4228         }
4229
4230         /*
4231          * We do the tagged writepage as long as the snapshot flush bit is set
4232          * and we are the first one who do the filemap_flush() on this inode.
4233          *
4234          * The nr_to_write == LONG_MAX is needed to make sure other flushers do
4235          * not race in and drop the bit.
4236          */
4237         if (range_whole && wbc->nr_to_write == LONG_MAX &&
4238             test_and_clear_bit(BTRFS_INODE_SNAPSHOT_FLUSH,
4239                                &BTRFS_I(inode)->runtime_flags))
4240                 wbc->tagged_writepages = 1;
4241
4242         if (wbc->sync_mode == WB_SYNC_ALL || wbc->tagged_writepages)
4243                 tag = PAGECACHE_TAG_TOWRITE;
4244         else
4245                 tag = PAGECACHE_TAG_DIRTY;
4246 retry:
4247         if (wbc->sync_mode == WB_SYNC_ALL || wbc->tagged_writepages)
4248                 tag_pages_for_writeback(mapping, index, end);
4249         done_index = index;
4250         while (!done && !nr_to_write_done && (index <= end) &&
4251                         (nr_pages = pagevec_lookup_range_tag(&pvec, mapping,
4252                                                 &index, end, tag))) {
4253                 unsigned i;
4254
4255                 for (i = 0; i < nr_pages; i++) {
4256                         struct page *page = pvec.pages[i];
4257
4258                         done_index = page->index + 1;
4259                         /*
4260                          * At this point we hold neither the i_pages lock nor
4261                          * the page lock: the page may be truncated or
4262                          * invalidated (changing page->mapping to NULL),
4263                          * or even swizzled back from swapper_space to
4264                          * tmpfs file mapping
4265                          */
4266                         if (!trylock_page(page)) {
4267                                 ret = flush_write_bio(epd);
4268                                 BUG_ON(ret < 0);
4269                                 lock_page(page);
4270                         }
4271
4272                         if (unlikely(page->mapping != mapping)) {
4273                                 unlock_page(page);
4274                                 continue;
4275                         }
4276
4277                         if (wbc->sync_mode != WB_SYNC_NONE) {
4278                                 if (PageWriteback(page)) {
4279                                         ret = flush_write_bio(epd);
4280                                         BUG_ON(ret < 0);
4281                                 }
4282                                 wait_on_page_writeback(page);
4283                         }
4284
4285                         if (PageWriteback(page) ||
4286                             !clear_page_dirty_for_io(page)) {
4287                                 unlock_page(page);
4288                                 continue;
4289                         }
4290
4291                         ret = __extent_writepage(page, wbc, epd);
4292                         if (ret < 0) {
4293                                 done = 1;
4294                                 break;
4295                         }
4296
4297                         /*
4298                          * the filesystem may choose to bump up nr_to_write.
4299                          * We have to make sure to honor the new nr_to_write
4300                          * at any time
4301                          */
4302                         nr_to_write_done = wbc->nr_to_write <= 0;
4303                 }
4304                 pagevec_release(&pvec);
4305                 cond_resched();
4306         }
4307         if (!scanned && !done) {
4308                 /*
4309                  * We hit the last page and there is more work to be done: wrap
4310                  * back to the start of the file
4311                  */
4312                 scanned = 1;
4313                 index = 0;
4314
4315                 /*
4316                  * If we're looping we could run into a page that is locked by a
4317                  * writer and that writer could be waiting on writeback for a
4318                  * page in our current bio, and thus deadlock, so flush the
4319                  * write bio here.
4320                  */
4321                 ret = flush_write_bio(epd);
4322                 if (!ret)
4323                         goto retry;
4324         }
4325
4326         if (wbc->range_cyclic || (wbc->nr_to_write > 0 && range_whole))
4327                 mapping->writeback_index = done_index;
4328
4329         btrfs_add_delayed_iput(inode);
4330         return ret;
4331 }
4332
4333 int extent_write_full_page(struct page *page, struct writeback_control *wbc)
4334 {
4335         int ret;
4336         struct extent_page_data epd = {
4337                 .bio = NULL,
4338                 .extent_locked = 0,
4339                 .sync_io = wbc->sync_mode == WB_SYNC_ALL,
4340         };
4341
4342         ret = __extent_writepage(page, wbc, &epd);
4343         ASSERT(ret <= 0);
4344         if (ret < 0) {
4345                 end_write_bio(&epd, ret);
4346                 return ret;
4347         }
4348
4349         ret = flush_write_bio(&epd);
4350         ASSERT(ret <= 0);
4351         return ret;
4352 }
4353
4354 int extent_write_locked_range(struct inode *inode, u64 start, u64 end,
4355                               int mode)
4356 {
4357         int ret = 0;
4358         struct address_space *mapping = inode->i_mapping;
4359         struct page *page;
4360         unsigned long nr_pages = (end - start + PAGE_SIZE) >>
4361                 PAGE_SHIFT;
4362
4363         struct extent_page_data epd = {
4364                 .bio = NULL,
4365                 .extent_locked = 1,
4366                 .sync_io = mode == WB_SYNC_ALL,
4367         };
4368         struct writeback_control wbc_writepages = {
4369                 .sync_mode      = mode,
4370                 .nr_to_write    = nr_pages * 2,
4371                 .range_start    = start,
4372                 .range_end      = end + 1,
4373                 /* We're called from an async helper function */
4374                 .punt_to_cgroup = 1,
4375                 .no_cgroup_owner = 1,
4376         };
4377
4378         wbc_attach_fdatawrite_inode(&wbc_writepages, inode);
4379         while (start <= end) {
4380                 page = find_get_page(mapping, start >> PAGE_SHIFT);
4381                 if (clear_page_dirty_for_io(page))
4382                         ret = __extent_writepage(page, &wbc_writepages, &epd);
4383                 else {
4384                         btrfs_writepage_endio_finish_ordered(page, start,
4385                                                     start + PAGE_SIZE - 1, 1);
4386                         unlock_page(page);
4387                 }
4388                 put_page(page);
4389                 start += PAGE_SIZE;
4390         }
4391
4392         ASSERT(ret <= 0);
4393         if (ret == 0)
4394                 ret = flush_write_bio(&epd);
4395         else
4396                 end_write_bio(&epd, ret);
4397
4398         wbc_detach_inode(&wbc_writepages);
4399         return ret;
4400 }
4401
4402 int extent_writepages(struct address_space *mapping,
4403                       struct writeback_control *wbc)
4404 {
4405         int ret = 0;
4406         struct extent_page_data epd = {
4407                 .bio = NULL,
4408                 .extent_locked = 0,
4409                 .sync_io = wbc->sync_mode == WB_SYNC_ALL,
4410         };
4411
4412         ret = extent_write_cache_pages(mapping, wbc, &epd);
4413         ASSERT(ret <= 0);
4414         if (ret < 0) {
4415                 end_write_bio(&epd, ret);
4416                 return ret;
4417         }
4418         ret = flush_write_bio(&epd);
4419         return ret;
4420 }
4421
4422 void extent_readahead(struct readahead_control *rac)
4423 {
4424         struct bio *bio = NULL;
4425         unsigned long bio_flags = 0;
4426         struct page *pagepool[16];
4427         struct extent_map *em_cached = NULL;
4428         u64 prev_em_start = (u64)-1;
4429         int nr;
4430
4431         while ((nr = readahead_page_batch(rac, pagepool))) {
4432                 u64 contig_start = page_offset(pagepool[0]);
4433                 u64 contig_end = page_offset(pagepool[nr - 1]) + PAGE_SIZE - 1;
4434
4435                 ASSERT(contig_start + nr * PAGE_SIZE - 1 == contig_end);
4436
4437                 contiguous_readpages(pagepool, nr, contig_start, contig_end,
4438                                 &em_cached, &bio, &bio_flags, &prev_em_start);
4439         }
4440
4441         if (em_cached)
4442                 free_extent_map(em_cached);
4443
4444         if (bio) {
4445                 if (submit_one_bio(bio, 0, bio_flags))
4446                         return;
4447         }
4448 }
4449
4450 /*
4451  * basic invalidatepage code, this waits on any locked or writeback
4452  * ranges corresponding to the page, and then deletes any extent state
4453  * records from the tree
4454  */
4455 int extent_invalidatepage(struct extent_io_tree *tree,
4456                           struct page *page, unsigned long offset)
4457 {
4458         struct extent_state *cached_state = NULL;
4459         u64 start = page_offset(page);
4460         u64 end = start + PAGE_SIZE - 1;
4461         size_t blocksize = page->mapping->host->i_sb->s_blocksize;
4462
4463         /* This function is only called for the btree inode */
4464         ASSERT(tree->owner == IO_TREE_BTREE_INODE_IO);
4465
4466         start += ALIGN(offset, blocksize);
4467         if (start > end)
4468                 return 0;
4469
4470         lock_extent_bits(tree, start, end, &cached_state);
4471         wait_on_page_writeback(page);
4472
4473         /*
4474          * Currently for btree io tree, only EXTENT_LOCKED is utilized,
4475          * so here we only need to unlock the extent range to free any
4476          * existing extent state.
4477          */
4478         unlock_extent_cached(tree, start, end, &cached_state);
4479         return 0;
4480 }
4481
4482 /*
4483  * a helper for releasepage, this tests for areas of the page that
4484  * are locked or under IO and drops the related state bits if it is safe
4485  * to drop the page.
4486  */
4487 static int try_release_extent_state(struct extent_io_tree *tree,
4488                                     struct page *page, gfp_t mask)
4489 {
4490         u64 start = page_offset(page);
4491         u64 end = start + PAGE_SIZE - 1;
4492         int ret = 1;
4493
4494         if (test_range_bit(tree, start, end, EXTENT_LOCKED, 0, NULL)) {
4495                 ret = 0;
4496         } else {
4497                 /*
4498                  * At this point we can safely clear everything except the
4499                  * locked bit, the nodatasum bit and the delalloc new bit.
4500                  * The delalloc new bit will be cleared by ordered extent
4501                  * completion.
4502                  */
4503                 ret = __clear_extent_bit(tree, start, end,
4504                          ~(EXTENT_LOCKED | EXTENT_NODATASUM | EXTENT_DELALLOC_NEW),
4505                          0, 0, NULL, mask, NULL);
4506
4507                 /* if clear_extent_bit failed for enomem reasons,
4508                  * we can't allow the release to continue.
4509                  */
4510                 if (ret < 0)
4511                         ret = 0;
4512                 else
4513                         ret = 1;
4514         }
4515         return ret;
4516 }
4517
4518 /*
4519  * a helper for releasepage.  As long as there are no locked extents
4520  * in the range corresponding to the page, both state records and extent
4521  * map records are removed
4522  */
4523 int try_release_extent_mapping(struct page *page, gfp_t mask)
4524 {
4525         struct extent_map *em;
4526         u64 start = page_offset(page);
4527         u64 end = start + PAGE_SIZE - 1;
4528         struct btrfs_inode *btrfs_inode = BTRFS_I(page->mapping->host);
4529         struct extent_io_tree *tree = &btrfs_inode->io_tree;
4530         struct extent_map_tree *map = &btrfs_inode->extent_tree;
4531
4532         if (gfpflags_allow_blocking(mask) &&
4533             page->mapping->host->i_size > SZ_16M) {
4534                 u64 len;
4535                 while (start <= end) {
4536                         struct btrfs_fs_info *fs_info;
4537                         u64 cur_gen;
4538
4539                         len = end - start + 1;
4540                         write_lock(&map->lock);
4541                         em = lookup_extent_mapping(map, start, len);
4542                         if (!em) {
4543                                 write_unlock(&map->lock);
4544                                 break;
4545                         }
4546                         if (test_bit(EXTENT_FLAG_PINNED, &em->flags) ||
4547                             em->start != start) {
4548                                 write_unlock(&map->lock);
4549                                 free_extent_map(em);
4550                                 break;
4551                         }
4552                         if (test_range_bit(tree, em->start,
4553                                            extent_map_end(em) - 1,
4554                                            EXTENT_LOCKED, 0, NULL))
4555                                 goto next;
4556                         /*
4557                          * If it's not in the list of modified extents, used
4558                          * by a fast fsync, we can remove it. If it's being
4559                          * logged we can safely remove it since fsync took an
4560                          * extra reference on the em.
4561                          */
4562                         if (list_empty(&em->list) ||
4563                             test_bit(EXTENT_FLAG_LOGGING, &em->flags))
4564                                 goto remove_em;
4565                         /*
4566                          * If it's in the list of modified extents, remove it
4567                          * only if its generation is older then the current one,
4568                          * in which case we don't need it for a fast fsync.
4569                          * Otherwise don't remove it, we could be racing with an
4570                          * ongoing fast fsync that could miss the new extent.
4571                          */
4572                         fs_info = btrfs_inode->root->fs_info;
4573                         spin_lock(&fs_info->trans_lock);
4574                         cur_gen = fs_info->generation;
4575                         spin_unlock(&fs_info->trans_lock);
4576                         if (em->generation >= cur_gen)
4577                                 goto next;
4578 remove_em:
4579                         /*
4580                          * We only remove extent maps that are not in the list of
4581                          * modified extents or that are in the list but with a
4582                          * generation lower then the current generation, so there
4583                          * is no need to set the full fsync flag on the inode (it
4584                          * hurts the fsync performance for workloads with a data
4585                          * size that exceeds or is close to the system's memory).
4586                          */
4587                         remove_extent_mapping(map, em);
4588                         /* once for the rb tree */
4589                         free_extent_map(em);
4590 next:
4591                         start = extent_map_end(em);
4592                         write_unlock(&map->lock);
4593
4594                         /* once for us */
4595                         free_extent_map(em);
4596
4597                         cond_resched(); /* Allow large-extent preemption. */
4598                 }
4599         }
4600         return try_release_extent_state(tree, page, mask);
4601 }
4602
4603 /*
4604  * helper function for fiemap, which doesn't want to see any holes.
4605  * This maps until we find something past 'last'
4606  */
4607 static struct extent_map *get_extent_skip_holes(struct btrfs_inode *inode,
4608                                                 u64 offset, u64 last)
4609 {
4610         u64 sectorsize = btrfs_inode_sectorsize(inode);
4611         struct extent_map *em;
4612         u64 len;
4613
4614         if (offset >= last)
4615                 return NULL;
4616
4617         while (1) {
4618                 len = last - offset;
4619                 if (len == 0)
4620                         break;
4621                 len = ALIGN(len, sectorsize);
4622                 em = btrfs_get_extent_fiemap(inode, offset, len);
4623                 if (IS_ERR_OR_NULL(em))
4624                         return em;
4625
4626                 /* if this isn't a hole return it */
4627                 if (em->block_start != EXTENT_MAP_HOLE)
4628                         return em;
4629
4630                 /* this is a hole, advance to the next extent */
4631                 offset = extent_map_end(em);
4632                 free_extent_map(em);
4633                 if (offset >= last)
4634                         break;
4635         }
4636         return NULL;
4637 }
4638
4639 /*
4640  * To cache previous fiemap extent
4641  *
4642  * Will be used for merging fiemap extent
4643  */
4644 struct fiemap_cache {
4645         u64 offset;
4646         u64 phys;
4647         u64 len;
4648         u32 flags;
4649         bool cached;
4650 };
4651
4652 /*
4653  * Helper to submit fiemap extent.
4654  *
4655  * Will try to merge current fiemap extent specified by @offset, @phys,
4656  * @len and @flags with cached one.
4657  * And only when we fails to merge, cached one will be submitted as
4658  * fiemap extent.
4659  *
4660  * Return value is the same as fiemap_fill_next_extent().
4661  */
4662 static int emit_fiemap_extent(struct fiemap_extent_info *fieinfo,
4663                                 struct fiemap_cache *cache,
4664                                 u64 offset, u64 phys, u64 len, u32 flags)
4665 {
4666         int ret = 0;
4667
4668         if (!cache->cached)
4669                 goto assign;
4670
4671         /*
4672          * Sanity check, extent_fiemap() should have ensured that new
4673          * fiemap extent won't overlap with cached one.
4674          * Not recoverable.
4675          *
4676          * NOTE: Physical address can overlap, due to compression
4677          */
4678         if (cache->offset + cache->len > offset) {
4679                 WARN_ON(1);
4680                 return -EINVAL;
4681         }
4682
4683         /*
4684          * Only merges fiemap extents if
4685          * 1) Their logical addresses are continuous
4686          *
4687          * 2) Their physical addresses are continuous
4688          *    So truly compressed (physical size smaller than logical size)
4689          *    extents won't get merged with each other
4690          *
4691          * 3) Share same flags except FIEMAP_EXTENT_LAST
4692          *    So regular extent won't get merged with prealloc extent
4693          */
4694         if (cache->offset + cache->len  == offset &&
4695             cache->phys + cache->len == phys  &&
4696             (cache->flags & ~FIEMAP_EXTENT_LAST) ==
4697                         (flags & ~FIEMAP_EXTENT_LAST)) {
4698                 cache->len += len;
4699                 cache->flags |= flags;
4700                 goto try_submit_last;
4701         }
4702
4703         /* Not mergeable, need to submit cached one */
4704         ret = fiemap_fill_next_extent(fieinfo, cache->offset, cache->phys,
4705                                       cache->len, cache->flags);
4706         cache->cached = false;
4707         if (ret)
4708                 return ret;
4709 assign:
4710         cache->cached = true;
4711         cache->offset = offset;
4712         cache->phys = phys;
4713         cache->len = len;
4714         cache->flags = flags;
4715 try_submit_last:
4716         if (cache->flags & FIEMAP_EXTENT_LAST) {
4717                 ret = fiemap_fill_next_extent(fieinfo, cache->offset,
4718                                 cache->phys, cache->len, cache->flags);
4719                 cache->cached = false;
4720         }
4721         return ret;
4722 }
4723
4724 /*
4725  * Emit last fiemap cache
4726  *
4727  * The last fiemap cache may still be cached in the following case:
4728  * 0                  4k                    8k
4729  * |<- Fiemap range ->|
4730  * |<------------  First extent ----------->|
4731  *
4732  * In this case, the first extent range will be cached but not emitted.
4733  * So we must emit it before ending extent_fiemap().
4734  */
4735 static int emit_last_fiemap_cache(struct fiemap_extent_info *fieinfo,
4736                                   struct fiemap_cache *cache)
4737 {
4738         int ret;
4739
4740         if (!cache->cached)
4741                 return 0;
4742
4743         ret = fiemap_fill_next_extent(fieinfo, cache->offset, cache->phys,
4744                                       cache->len, cache->flags);
4745         cache->cached = false;
4746         if (ret > 0)
4747                 ret = 0;
4748         return ret;
4749 }
4750
4751 int extent_fiemap(struct btrfs_inode *inode, struct fiemap_extent_info *fieinfo,
4752                   u64 start, u64 len)
4753 {
4754         int ret = 0;
4755         u64 off = start;
4756         u64 max = start + len;
4757         u32 flags = 0;
4758         u32 found_type;
4759         u64 last;
4760         u64 last_for_get_extent = 0;
4761         u64 disko = 0;
4762         u64 isize = i_size_read(&inode->vfs_inode);
4763         struct btrfs_key found_key;
4764         struct extent_map *em = NULL;
4765         struct extent_state *cached_state = NULL;
4766         struct btrfs_path *path;
4767         struct btrfs_root *root = inode->root;
4768         struct fiemap_cache cache = { 0 };
4769         struct ulist *roots;
4770         struct ulist *tmp_ulist;
4771         int end = 0;
4772         u64 em_start = 0;
4773         u64 em_len = 0;
4774         u64 em_end = 0;
4775
4776         if (len == 0)
4777                 return -EINVAL;
4778
4779         path = btrfs_alloc_path();
4780         if (!path)
4781                 return -ENOMEM;
4782
4783         roots = ulist_alloc(GFP_KERNEL);
4784         tmp_ulist = ulist_alloc(GFP_KERNEL);
4785         if (!roots || !tmp_ulist) {
4786                 ret = -ENOMEM;
4787                 goto out_free_ulist;
4788         }
4789
4790         start = round_down(start, btrfs_inode_sectorsize(inode));
4791         len = round_up(max, btrfs_inode_sectorsize(inode)) - start;
4792
4793         /*
4794          * lookup the last file extent.  We're not using i_size here
4795          * because there might be preallocation past i_size
4796          */
4797         ret = btrfs_lookup_file_extent(NULL, root, path, btrfs_ino(inode), -1,
4798                                        0);
4799         if (ret < 0) {
4800                 goto out_free_ulist;
4801         } else {
4802                 WARN_ON(!ret);
4803                 if (ret == 1)
4804                         ret = 0;
4805         }
4806
4807         path->slots[0]--;
4808         btrfs_item_key_to_cpu(path->nodes[0], &found_key, path->slots[0]);
4809         found_type = found_key.type;
4810
4811         /* No extents, but there might be delalloc bits */
4812         if (found_key.objectid != btrfs_ino(inode) ||
4813             found_type != BTRFS_EXTENT_DATA_KEY) {
4814                 /* have to trust i_size as the end */
4815                 last = (u64)-1;
4816                 last_for_get_extent = isize;
4817         } else {
4818                 /*
4819                  * remember the start of the last extent.  There are a
4820                  * bunch of different factors that go into the length of the
4821                  * extent, so its much less complex to remember where it started
4822                  */
4823                 last = found_key.offset;
4824                 last_for_get_extent = last + 1;
4825         }
4826         btrfs_release_path(path);
4827
4828         /*
4829          * we might have some extents allocated but more delalloc past those
4830          * extents.  so, we trust isize unless the start of the last extent is
4831          * beyond isize
4832          */
4833         if (last < isize) {
4834                 last = (u64)-1;
4835                 last_for_get_extent = isize;
4836         }
4837
4838         lock_extent_bits(&inode->io_tree, start, start + len - 1,
4839                          &cached_state);
4840
4841         em = get_extent_skip_holes(inode, start, last_for_get_extent);
4842         if (!em)
4843                 goto out;
4844         if (IS_ERR(em)) {
4845                 ret = PTR_ERR(em);
4846                 goto out;
4847         }
4848
4849         while (!end) {
4850                 u64 offset_in_extent = 0;
4851
4852                 /* break if the extent we found is outside the range */
4853                 if (em->start >= max || extent_map_end(em) < off)
4854                         break;
4855
4856                 /*
4857                  * get_extent may return an extent that starts before our
4858                  * requested range.  We have to make sure the ranges
4859                  * we return to fiemap always move forward and don't
4860                  * overlap, so adjust the offsets here
4861                  */
4862                 em_start = max(em->start, off);
4863
4864                 /*
4865                  * record the offset from the start of the extent
4866                  * for adjusting the disk offset below.  Only do this if the
4867                  * extent isn't compressed since our in ram offset may be past
4868                  * what we have actually allocated on disk.
4869                  */
4870                 if (!test_bit(EXTENT_FLAG_COMPRESSED, &em->flags))
4871                         offset_in_extent = em_start - em->start;
4872                 em_end = extent_map_end(em);
4873                 em_len = em_end - em_start;
4874                 flags = 0;
4875                 if (em->block_start < EXTENT_MAP_LAST_BYTE)
4876                         disko = em->block_start + offset_in_extent;
4877                 else
4878                         disko = 0;
4879
4880                 /*
4881                  * bump off for our next call to get_extent
4882                  */
4883                 off = extent_map_end(em);
4884                 if (off >= max)
4885                         end = 1;
4886
4887                 if (em->block_start == EXTENT_MAP_LAST_BYTE) {
4888                         end = 1;
4889                         flags |= FIEMAP_EXTENT_LAST;
4890                 } else if (em->block_start == EXTENT_MAP_INLINE) {
4891                         flags |= (FIEMAP_EXTENT_DATA_INLINE |
4892                                   FIEMAP_EXTENT_NOT_ALIGNED);
4893                 } else if (em->block_start == EXTENT_MAP_DELALLOC) {
4894                         flags |= (FIEMAP_EXTENT_DELALLOC |
4895                                   FIEMAP_EXTENT_UNKNOWN);
4896                 } else if (fieinfo->fi_extents_max) {
4897                         u64 bytenr = em->block_start -
4898                                 (em->start - em->orig_start);
4899
4900                         /*
4901                          * As btrfs supports shared space, this information
4902                          * can be exported to userspace tools via
4903                          * flag FIEMAP_EXTENT_SHARED.  If fi_extents_max == 0
4904                          * then we're just getting a count and we can skip the
4905                          * lookup stuff.
4906                          */
4907                         ret = btrfs_check_shared(root, btrfs_ino(inode),
4908                                                  bytenr, roots, tmp_ulist);
4909                         if (ret < 0)
4910                                 goto out_free;
4911                         if (ret)
4912                                 flags |= FIEMAP_EXTENT_SHARED;
4913                         ret = 0;
4914                 }
4915                 if (test_bit(EXTENT_FLAG_COMPRESSED, &em->flags))
4916                         flags |= FIEMAP_EXTENT_ENCODED;
4917                 if (test_bit(EXTENT_FLAG_PREALLOC, &em->flags))
4918                         flags |= FIEMAP_EXTENT_UNWRITTEN;
4919
4920                 free_extent_map(em);
4921                 em = NULL;
4922                 if ((em_start >= last) || em_len == (u64)-1 ||
4923                    (last == (u64)-1 && isize <= em_end)) {
4924                         flags |= FIEMAP_EXTENT_LAST;
4925                         end = 1;
4926                 }
4927
4928                 /* now scan forward to see if this is really the last extent. */
4929                 em = get_extent_skip_holes(inode, off, last_for_get_extent);
4930                 if (IS_ERR(em)) {
4931                         ret = PTR_ERR(em);
4932                         goto out;
4933                 }
4934                 if (!em) {
4935                         flags |= FIEMAP_EXTENT_LAST;
4936                         end = 1;
4937                 }
4938                 ret = emit_fiemap_extent(fieinfo, &cache, em_start, disko,
4939                                            em_len, flags);
4940                 if (ret) {
4941                         if (ret == 1)
4942                                 ret = 0;
4943                         goto out_free;
4944                 }
4945         }
4946 out_free:
4947         if (!ret)
4948                 ret = emit_last_fiemap_cache(fieinfo, &cache);
4949         free_extent_map(em);
4950 out:
4951         unlock_extent_cached(&inode->io_tree, start, start + len - 1,
4952                              &cached_state);
4953
4954 out_free_ulist:
4955         btrfs_free_path(path);
4956         ulist_free(roots);
4957         ulist_free(tmp_ulist);
4958         return ret;
4959 }
4960
4961 static void __free_extent_buffer(struct extent_buffer *eb)
4962 {
4963         kmem_cache_free(extent_buffer_cache, eb);
4964 }
4965
4966 int extent_buffer_under_io(const struct extent_buffer *eb)
4967 {
4968         return (atomic_read(&eb->io_pages) ||
4969                 test_bit(EXTENT_BUFFER_WRITEBACK, &eb->bflags) ||
4970                 test_bit(EXTENT_BUFFER_DIRTY, &eb->bflags));
4971 }
4972
4973 /*
4974  * Release all pages attached to the extent buffer.
4975  */
4976 static void btrfs_release_extent_buffer_pages(struct extent_buffer *eb)
4977 {
4978         int i;
4979         int num_pages;
4980         int mapped = !test_bit(EXTENT_BUFFER_UNMAPPED, &eb->bflags);
4981
4982         BUG_ON(extent_buffer_under_io(eb));
4983
4984         num_pages = num_extent_pages(eb);
4985         for (i = 0; i < num_pages; i++) {
4986                 struct page *page = eb->pages[i];
4987
4988                 if (!page)
4989                         continue;
4990                 if (mapped)
4991                         spin_lock(&page->mapping->private_lock);
4992                 /*
4993                  * We do this since we'll remove the pages after we've
4994                  * removed the eb from the radix tree, so we could race
4995                  * and have this page now attached to the new eb.  So
4996                  * only clear page_private if it's still connected to
4997                  * this eb.
4998                  */
4999                 if (PagePrivate(page) &&
5000                     page->private == (unsigned long)eb) {
5001                         BUG_ON(test_bit(EXTENT_BUFFER_DIRTY, &eb->bflags));
5002                         BUG_ON(PageDirty(page));
5003                         BUG_ON(PageWriteback(page));
5004                         /*
5005                          * We need to make sure we haven't be attached
5006                          * to a new eb.
5007                          */
5008                         detach_page_private(page);
5009                 }
5010
5011                 if (mapped)
5012                         spin_unlock(&page->mapping->private_lock);
5013
5014                 /* One for when we allocated the page */
5015                 put_page(page);
5016         }
5017 }
5018
5019 /*
5020  * Helper for releasing the extent buffer.
5021  */
5022 static inline void btrfs_release_extent_buffer(struct extent_buffer *eb)
5023 {
5024         btrfs_release_extent_buffer_pages(eb);
5025         btrfs_leak_debug_del(&eb->fs_info->eb_leak_lock, &eb->leak_list);
5026         __free_extent_buffer(eb);
5027 }
5028
5029 static struct extent_buffer *
5030 __alloc_extent_buffer(struct btrfs_fs_info *fs_info, u64 start,
5031                       unsigned long len)
5032 {
5033         struct extent_buffer *eb = NULL;
5034
5035         eb = kmem_cache_zalloc(extent_buffer_cache, GFP_NOFS|__GFP_NOFAIL);
5036         eb->start = start;
5037         eb->len = len;
5038         eb->fs_info = fs_info;
5039         eb->bflags = 0;
5040         init_rwsem(&eb->lock);
5041
5042         btrfs_leak_debug_add(&fs_info->eb_leak_lock, &eb->leak_list,
5043                              &fs_info->allocated_ebs);
5044
5045         spin_lock_init(&eb->refs_lock);
5046         atomic_set(&eb->refs, 1);
5047         atomic_set(&eb->io_pages, 0);
5048
5049         ASSERT(len <= BTRFS_MAX_METADATA_BLOCKSIZE);
5050
5051         return eb;
5052 }
5053
5054 struct extent_buffer *btrfs_clone_extent_buffer(const struct extent_buffer *src)
5055 {
5056         int i;
5057         struct page *p;
5058         struct extent_buffer *new;
5059         int num_pages = num_extent_pages(src);
5060
5061         new = __alloc_extent_buffer(src->fs_info, src->start, src->len);
5062         if (new == NULL)
5063                 return NULL;
5064
5065         for (i = 0; i < num_pages; i++) {
5066                 p = alloc_page(GFP_NOFS);
5067                 if (!p) {
5068                         btrfs_release_extent_buffer(new);
5069                         return NULL;
5070                 }
5071                 attach_extent_buffer_page(new, p);
5072                 WARN_ON(PageDirty(p));
5073                 SetPageUptodate(p);
5074                 new->pages[i] = p;
5075                 copy_page(page_address(p), page_address(src->pages[i]));
5076         }
5077
5078         set_bit(EXTENT_BUFFER_UPTODATE, &new->bflags);
5079         set_bit(EXTENT_BUFFER_UNMAPPED, &new->bflags);
5080
5081         return new;
5082 }
5083
5084 struct extent_buffer *__alloc_dummy_extent_buffer(struct btrfs_fs_info *fs_info,
5085                                                   u64 start, unsigned long len)
5086 {
5087         struct extent_buffer *eb;
5088         int num_pages;
5089         int i;
5090
5091         eb = __alloc_extent_buffer(fs_info, start, len);
5092         if (!eb)
5093                 return NULL;
5094
5095         num_pages = num_extent_pages(eb);
5096         for (i = 0; i < num_pages; i++) {
5097                 eb->pages[i] = alloc_page(GFP_NOFS);
5098                 if (!eb->pages[i])
5099                         goto err;
5100         }
5101         set_extent_buffer_uptodate(eb);
5102         btrfs_set_header_nritems(eb, 0);
5103         set_bit(EXTENT_BUFFER_UNMAPPED, &eb->bflags);
5104
5105         return eb;
5106 err:
5107         for (; i > 0; i--)
5108                 __free_page(eb->pages[i - 1]);
5109         __free_extent_buffer(eb);
5110         return NULL;
5111 }
5112
5113 struct extent_buffer *alloc_dummy_extent_buffer(struct btrfs_fs_info *fs_info,
5114                                                 u64 start)
5115 {
5116         return __alloc_dummy_extent_buffer(fs_info, start, fs_info->nodesize);
5117 }
5118
5119 static void check_buffer_tree_ref(struct extent_buffer *eb)
5120 {
5121         int refs;
5122         /*
5123          * The TREE_REF bit is first set when the extent_buffer is added
5124          * to the radix tree. It is also reset, if unset, when a new reference
5125          * is created by find_extent_buffer.
5126          *
5127          * It is only cleared in two cases: freeing the last non-tree
5128          * reference to the extent_buffer when its STALE bit is set or
5129          * calling releasepage when the tree reference is the only reference.
5130          *
5131          * In both cases, care is taken to ensure that the extent_buffer's
5132          * pages are not under io. However, releasepage can be concurrently
5133          * called with creating new references, which is prone to race
5134          * conditions between the calls to check_buffer_tree_ref in those
5135          * codepaths and clearing TREE_REF in try_release_extent_buffer.
5136          *
5137          * The actual lifetime of the extent_buffer in the radix tree is
5138          * adequately protected by the refcount, but the TREE_REF bit and
5139          * its corresponding reference are not. To protect against this
5140          * class of races, we call check_buffer_tree_ref from the codepaths
5141          * which trigger io after they set eb->io_pages. Note that once io is
5142          * initiated, TREE_REF can no longer be cleared, so that is the
5143          * moment at which any such race is best fixed.
5144          */
5145         refs = atomic_read(&eb->refs);
5146         if (refs >= 2 && test_bit(EXTENT_BUFFER_TREE_REF, &eb->bflags))
5147                 return;
5148
5149         spin_lock(&eb->refs_lock);
5150         if (!test_and_set_bit(EXTENT_BUFFER_TREE_REF, &eb->bflags))
5151                 atomic_inc(&eb->refs);
5152         spin_unlock(&eb->refs_lock);
5153 }
5154
5155 static void mark_extent_buffer_accessed(struct extent_buffer *eb,
5156                 struct page *accessed)
5157 {
5158         int num_pages, i;
5159
5160         check_buffer_tree_ref(eb);
5161
5162         num_pages = num_extent_pages(eb);
5163         for (i = 0; i < num_pages; i++) {
5164                 struct page *p = eb->pages[i];
5165
5166                 if (p != accessed)
5167                         mark_page_accessed(p);
5168         }
5169 }
5170
5171 struct extent_buffer *find_extent_buffer(struct btrfs_fs_info *fs_info,
5172                                          u64 start)
5173 {
5174         struct extent_buffer *eb;
5175
5176         rcu_read_lock();
5177         eb = radix_tree_lookup(&fs_info->buffer_radix,
5178                                start >> fs_info->sectorsize_bits);
5179         if (eb && atomic_inc_not_zero(&eb->refs)) {
5180                 rcu_read_unlock();
5181                 /*
5182                  * Lock our eb's refs_lock to avoid races with
5183                  * free_extent_buffer. When we get our eb it might be flagged
5184                  * with EXTENT_BUFFER_STALE and another task running
5185                  * free_extent_buffer might have seen that flag set,
5186                  * eb->refs == 2, that the buffer isn't under IO (dirty and
5187                  * writeback flags not set) and it's still in the tree (flag
5188                  * EXTENT_BUFFER_TREE_REF set), therefore being in the process
5189                  * of decrementing the extent buffer's reference count twice.
5190                  * So here we could race and increment the eb's reference count,
5191                  * clear its stale flag, mark it as dirty and drop our reference
5192                  * before the other task finishes executing free_extent_buffer,
5193                  * which would later result in an attempt to free an extent
5194                  * buffer that is dirty.
5195                  */
5196                 if (test_bit(EXTENT_BUFFER_STALE, &eb->bflags)) {
5197                         spin_lock(&eb->refs_lock);
5198                         spin_unlock(&eb->refs_lock);
5199                 }
5200                 mark_extent_buffer_accessed(eb, NULL);
5201                 return eb;
5202         }
5203         rcu_read_unlock();
5204
5205         return NULL;
5206 }
5207
5208 #ifdef CONFIG_BTRFS_FS_RUN_SANITY_TESTS
5209 struct extent_buffer *alloc_test_extent_buffer(struct btrfs_fs_info *fs_info,
5210                                         u64 start)
5211 {
5212         struct extent_buffer *eb, *exists = NULL;
5213         int ret;
5214
5215         eb = find_extent_buffer(fs_info, start);
5216         if (eb)
5217                 return eb;
5218         eb = alloc_dummy_extent_buffer(fs_info, start);
5219         if (!eb)
5220                 return ERR_PTR(-ENOMEM);
5221         eb->fs_info = fs_info;
5222 again:
5223         ret = radix_tree_preload(GFP_NOFS);
5224         if (ret) {
5225                 exists = ERR_PTR(ret);
5226                 goto free_eb;
5227         }
5228         spin_lock(&fs_info->buffer_lock);
5229         ret = radix_tree_insert(&fs_info->buffer_radix,
5230                                 start >> fs_info->sectorsize_bits, eb);
5231         spin_unlock(&fs_info->buffer_lock);
5232         radix_tree_preload_end();
5233         if (ret == -EEXIST) {
5234                 exists = find_extent_buffer(fs_info, start);
5235                 if (exists)
5236                         goto free_eb;
5237                 else
5238                         goto again;
5239         }
5240         check_buffer_tree_ref(eb);
5241         set_bit(EXTENT_BUFFER_IN_TREE, &eb->bflags);
5242
5243         return eb;
5244 free_eb:
5245         btrfs_release_extent_buffer(eb);
5246         return exists;
5247 }
5248 #endif
5249
5250 struct extent_buffer *alloc_extent_buffer(struct btrfs_fs_info *fs_info,
5251                                           u64 start, u64 owner_root, int level)
5252 {
5253         unsigned long len = fs_info->nodesize;
5254         int num_pages;
5255         int i;
5256         unsigned long index = start >> PAGE_SHIFT;
5257         struct extent_buffer *eb;
5258         struct extent_buffer *exists = NULL;
5259         struct page *p;
5260         struct address_space *mapping = fs_info->btree_inode->i_mapping;
5261         int uptodate = 1;
5262         int ret;
5263
5264         if (!IS_ALIGNED(start, fs_info->sectorsize)) {
5265                 btrfs_err(fs_info, "bad tree block start %llu", start);
5266                 return ERR_PTR(-EINVAL);
5267         }
5268
5269         if (fs_info->sectorsize < PAGE_SIZE &&
5270             offset_in_page(start) + len > PAGE_SIZE) {
5271                 btrfs_err(fs_info,
5272                 "tree block crosses page boundary, start %llu nodesize %lu",
5273                           start, len);
5274                 return ERR_PTR(-EINVAL);
5275         }
5276
5277         eb = find_extent_buffer(fs_info, start);
5278         if (eb)
5279                 return eb;
5280
5281         eb = __alloc_extent_buffer(fs_info, start, len);
5282         if (!eb)
5283                 return ERR_PTR(-ENOMEM);
5284         btrfs_set_buffer_lockdep_class(owner_root, eb, level);
5285
5286         num_pages = num_extent_pages(eb);
5287         for (i = 0; i < num_pages; i++, index++) {
5288                 p = find_or_create_page(mapping, index, GFP_NOFS|__GFP_NOFAIL);
5289                 if (!p) {
5290                         exists = ERR_PTR(-ENOMEM);
5291                         goto free_eb;
5292                 }
5293
5294                 spin_lock(&mapping->private_lock);
5295                 if (PagePrivate(p)) {
5296                         /*
5297                          * We could have already allocated an eb for this page
5298                          * and attached one so lets see if we can get a ref on
5299                          * the existing eb, and if we can we know it's good and
5300                          * we can just return that one, else we know we can just
5301                          * overwrite page->private.
5302                          */
5303                         exists = (struct extent_buffer *)p->private;
5304                         if (atomic_inc_not_zero(&exists->refs)) {
5305                                 spin_unlock(&mapping->private_lock);
5306                                 unlock_page(p);
5307                                 put_page(p);
5308                                 mark_extent_buffer_accessed(exists, p);
5309                                 goto free_eb;
5310                         }
5311                         exists = NULL;
5312
5313                         WARN_ON(PageDirty(p));
5314                         detach_page_private(p);
5315                 }
5316                 attach_extent_buffer_page(eb, p);
5317                 spin_unlock(&mapping->private_lock);
5318                 WARN_ON(PageDirty(p));
5319                 eb->pages[i] = p;
5320                 if (!PageUptodate(p))
5321                         uptodate = 0;
5322
5323                 /*
5324                  * We can't unlock the pages just yet since the extent buffer
5325                  * hasn't been properly inserted in the radix tree, this
5326                  * opens a race with btree_releasepage which can free a page
5327                  * while we are still filling in all pages for the buffer and
5328                  * we could crash.
5329                  */
5330         }
5331         if (uptodate)
5332                 set_bit(EXTENT_BUFFER_UPTODATE, &eb->bflags);
5333 again:
5334         ret = radix_tree_preload(GFP_NOFS);
5335         if (ret) {
5336                 exists = ERR_PTR(ret);
5337                 goto free_eb;
5338         }
5339
5340         spin_lock(&fs_info->buffer_lock);
5341         ret = radix_tree_insert(&fs_info->buffer_radix,
5342                                 start >> fs_info->sectorsize_bits, eb);
5343         spin_unlock(&fs_info->buffer_lock);
5344         radix_tree_preload_end();
5345         if (ret == -EEXIST) {
5346                 exists = find_extent_buffer(fs_info, start);
5347                 if (exists)
5348                         goto free_eb;
5349                 else
5350                         goto again;
5351         }
5352         /* add one reference for the tree */
5353         check_buffer_tree_ref(eb);
5354         set_bit(EXTENT_BUFFER_IN_TREE, &eb->bflags);
5355
5356         /*
5357          * Now it's safe to unlock the pages because any calls to
5358          * btree_releasepage will correctly detect that a page belongs to a
5359          * live buffer and won't free them prematurely.
5360          */
5361         for (i = 0; i < num_pages; i++)
5362                 unlock_page(eb->pages[i]);
5363         return eb;
5364
5365 free_eb:
5366         WARN_ON(!atomic_dec_and_test(&eb->refs));
5367         for (i = 0; i < num_pages; i++) {
5368                 if (eb->pages[i])
5369                         unlock_page(eb->pages[i]);
5370         }
5371
5372         btrfs_release_extent_buffer(eb);
5373         return exists;
5374 }
5375
5376 static inline void btrfs_release_extent_buffer_rcu(struct rcu_head *head)
5377 {
5378         struct extent_buffer *eb =
5379                         container_of(head, struct extent_buffer, rcu_head);
5380
5381         __free_extent_buffer(eb);
5382 }
5383
5384 static int release_extent_buffer(struct extent_buffer *eb)
5385         __releases(&eb->refs_lock)
5386 {
5387         lockdep_assert_held(&eb->refs_lock);
5388
5389         WARN_ON(atomic_read(&eb->refs) == 0);
5390         if (atomic_dec_and_test(&eb->refs)) {
5391                 if (test_and_clear_bit(EXTENT_BUFFER_IN_TREE, &eb->bflags)) {
5392                         struct btrfs_fs_info *fs_info = eb->fs_info;
5393
5394                         spin_unlock(&eb->refs_lock);
5395
5396                         spin_lock(&fs_info->buffer_lock);
5397                         radix_tree_delete(&fs_info->buffer_radix,
5398                                           eb->start >> fs_info->sectorsize_bits);
5399                         spin_unlock(&fs_info->buffer_lock);
5400                 } else {
5401                         spin_unlock(&eb->refs_lock);
5402                 }
5403
5404                 btrfs_leak_debug_del(&eb->fs_info->eb_leak_lock, &eb->leak_list);
5405                 /* Should be safe to release our pages at this point */
5406                 btrfs_release_extent_buffer_pages(eb);
5407 #ifdef CONFIG_BTRFS_FS_RUN_SANITY_TESTS
5408                 if (unlikely(test_bit(EXTENT_BUFFER_UNMAPPED, &eb->bflags))) {
5409                         __free_extent_buffer(eb);
5410                         return 1;
5411                 }
5412 #endif
5413                 call_rcu(&eb->rcu_head, btrfs_release_extent_buffer_rcu);
5414                 return 1;
5415         }
5416         spin_unlock(&eb->refs_lock);
5417
5418         return 0;
5419 }
5420
5421 void free_extent_buffer(struct extent_buffer *eb)
5422 {
5423         int refs;
5424         int old;
5425         if (!eb)
5426                 return;
5427
5428         while (1) {
5429                 refs = atomic_read(&eb->refs);
5430                 if ((!test_bit(EXTENT_BUFFER_UNMAPPED, &eb->bflags) && refs <= 3)
5431                     || (test_bit(EXTENT_BUFFER_UNMAPPED, &eb->bflags) &&
5432                         refs == 1))
5433                         break;
5434                 old = atomic_cmpxchg(&eb->refs, refs, refs - 1);
5435                 if (old == refs)
5436                         return;
5437         }
5438
5439         spin_lock(&eb->refs_lock);
5440         if (atomic_read(&eb->refs) == 2 &&
5441             test_bit(EXTENT_BUFFER_STALE, &eb->bflags) &&
5442             !extent_buffer_under_io(eb) &&
5443             test_and_clear_bit(EXTENT_BUFFER_TREE_REF, &eb->bflags))
5444                 atomic_dec(&eb->refs);
5445
5446         /*
5447          * I know this is terrible, but it's temporary until we stop tracking
5448          * the uptodate bits and such for the extent buffers.
5449          */
5450         release_extent_buffer(eb);
5451 }
5452
5453 void free_extent_buffer_stale(struct extent_buffer *eb)
5454 {
5455         if (!eb)
5456                 return;
5457
5458         spin_lock(&eb->refs_lock);
5459         set_bit(EXTENT_BUFFER_STALE, &eb->bflags);
5460
5461         if (atomic_read(&eb->refs) == 2 && !extent_buffer_under_io(eb) &&
5462             test_and_clear_bit(EXTENT_BUFFER_TREE_REF, &eb->bflags))
5463                 atomic_dec(&eb->refs);
5464         release_extent_buffer(eb);
5465 }
5466
5467 void clear_extent_buffer_dirty(const struct extent_buffer *eb)
5468 {
5469         int i;
5470         int num_pages;
5471         struct page *page;
5472
5473         num_pages = num_extent_pages(eb);
5474
5475         for (i = 0; i < num_pages; i++) {
5476                 page = eb->pages[i];
5477                 if (!PageDirty(page))
5478                         continue;
5479
5480                 lock_page(page);
5481                 WARN_ON(!PagePrivate(page));
5482
5483                 clear_page_dirty_for_io(page);
5484                 xa_lock_irq(&page->mapping->i_pages);
5485                 if (!PageDirty(page))
5486                         __xa_clear_mark(&page->mapping->i_pages,
5487                                         page_index(page), PAGECACHE_TAG_DIRTY);
5488                 xa_unlock_irq(&page->mapping->i_pages);
5489                 ClearPageError(page);
5490                 unlock_page(page);
5491         }
5492         WARN_ON(atomic_read(&eb->refs) == 0);
5493 }
5494
5495 bool set_extent_buffer_dirty(struct extent_buffer *eb)
5496 {
5497         int i;
5498         int num_pages;
5499         bool was_dirty;
5500
5501         check_buffer_tree_ref(eb);
5502
5503         was_dirty = test_and_set_bit(EXTENT_BUFFER_DIRTY, &eb->bflags);
5504
5505         num_pages = num_extent_pages(eb);
5506         WARN_ON(atomic_read(&eb->refs) == 0);
5507         WARN_ON(!test_bit(EXTENT_BUFFER_TREE_REF, &eb->bflags));
5508
5509         if (!was_dirty)
5510                 for (i = 0; i < num_pages; i++)
5511                         set_page_dirty(eb->pages[i]);
5512
5513 #ifdef CONFIG_BTRFS_DEBUG
5514         for (i = 0; i < num_pages; i++)
5515                 ASSERT(PageDirty(eb->pages[i]));
5516 #endif
5517
5518         return was_dirty;
5519 }
5520
5521 void clear_extent_buffer_uptodate(struct extent_buffer *eb)
5522 {
5523         int i;
5524         struct page *page;
5525         int num_pages;
5526
5527         clear_bit(EXTENT_BUFFER_UPTODATE, &eb->bflags);
5528         num_pages = num_extent_pages(eb);
5529         for (i = 0; i < num_pages; i++) {
5530                 page = eb->pages[i];
5531                 if (page)
5532                         ClearPageUptodate(page);
5533         }
5534 }
5535
5536 void set_extent_buffer_uptodate(struct extent_buffer *eb)
5537 {
5538         int i;
5539         struct page *page;
5540         int num_pages;
5541
5542         set_bit(EXTENT_BUFFER_UPTODATE, &eb->bflags);
5543         num_pages = num_extent_pages(eb);
5544         for (i = 0; i < num_pages; i++) {
5545                 page = eb->pages[i];
5546                 SetPageUptodate(page);
5547         }
5548 }
5549
5550 int read_extent_buffer_pages(struct extent_buffer *eb, int wait, int mirror_num)
5551 {
5552         int i;
5553         struct page *page;
5554         int err;
5555         int ret = 0;
5556         int locked_pages = 0;
5557         int all_uptodate = 1;
5558         int num_pages;
5559         unsigned long num_reads = 0;
5560         struct bio *bio = NULL;
5561         unsigned long bio_flags = 0;
5562
5563         if (test_bit(EXTENT_BUFFER_UPTODATE, &eb->bflags))
5564                 return 0;
5565
5566         num_pages = num_extent_pages(eb);
5567         for (i = 0; i < num_pages; i++) {
5568                 page = eb->pages[i];
5569                 if (wait == WAIT_NONE) {
5570                         if (!trylock_page(page))
5571                                 goto unlock_exit;
5572                 } else {
5573                         lock_page(page);
5574                 }
5575                 locked_pages++;
5576         }
5577         /*
5578          * We need to firstly lock all pages to make sure that
5579          * the uptodate bit of our pages won't be affected by
5580          * clear_extent_buffer_uptodate().
5581          */
5582         for (i = 0; i < num_pages; i++) {
5583                 page = eb->pages[i];
5584                 if (!PageUptodate(page)) {
5585                         num_reads++;
5586                         all_uptodate = 0;
5587                 }
5588         }
5589
5590         if (all_uptodate) {
5591                 set_bit(EXTENT_BUFFER_UPTODATE, &eb->bflags);
5592                 goto unlock_exit;
5593         }
5594
5595         clear_bit(EXTENT_BUFFER_READ_ERR, &eb->bflags);
5596         eb->read_mirror = 0;
5597         atomic_set(&eb->io_pages, num_reads);
5598         /*
5599          * It is possible for releasepage to clear the TREE_REF bit before we
5600          * set io_pages. See check_buffer_tree_ref for a more detailed comment.
5601          */
5602         check_buffer_tree_ref(eb);
5603         for (i = 0; i < num_pages; i++) {
5604                 page = eb->pages[i];
5605
5606                 if (!PageUptodate(page)) {
5607                         if (ret) {
5608                                 atomic_dec(&eb->io_pages);
5609                                 unlock_page(page);
5610                                 continue;
5611                         }
5612
5613                         ClearPageError(page);
5614                         err = submit_extent_page(REQ_OP_READ | REQ_META, NULL,
5615                                          page, page_offset(page), PAGE_SIZE, 0,
5616                                          &bio, end_bio_extent_readpage,
5617                                          mirror_num, 0, 0, false);
5618                         if (err) {
5619                                 /*
5620                                  * We failed to submit the bio so it's the
5621                                  * caller's responsibility to perform cleanup
5622                                  * i.e unlock page/set error bit.
5623                                  */
5624                                 ret = err;
5625                                 SetPageError(page);
5626                                 unlock_page(page);
5627                                 atomic_dec(&eb->io_pages);
5628                         }
5629                 } else {
5630                         unlock_page(page);
5631                 }
5632         }
5633
5634         if (bio) {
5635                 err = submit_one_bio(bio, mirror_num, bio_flags);
5636                 if (err)
5637                         return err;
5638         }
5639
5640         if (ret || wait != WAIT_COMPLETE)
5641                 return ret;
5642
5643         for (i = 0; i < num_pages; i++) {
5644                 page = eb->pages[i];
5645                 wait_on_page_locked(page);
5646                 if (!PageUptodate(page))
5647                         ret = -EIO;
5648         }
5649
5650         return ret;
5651
5652 unlock_exit:
5653         while (locked_pages > 0) {
5654                 locked_pages--;
5655                 page = eb->pages[locked_pages];
5656                 unlock_page(page);
5657         }
5658         return ret;
5659 }
5660
5661 static bool report_eb_range(const struct extent_buffer *eb, unsigned long start,
5662                             unsigned long len)
5663 {
5664         btrfs_warn(eb->fs_info,
5665                 "access to eb bytenr %llu len %lu out of range start %lu len %lu",
5666                 eb->start, eb->len, start, len);
5667         WARN_ON(IS_ENABLED(CONFIG_BTRFS_DEBUG));
5668
5669         return true;
5670 }
5671
5672 /*
5673  * Check if the [start, start + len) range is valid before reading/writing
5674  * the eb.
5675  * NOTE: @start and @len are offset inside the eb, not logical address.
5676  *
5677  * Caller should not touch the dst/src memory if this function returns error.
5678  */
5679 static inline int check_eb_range(const struct extent_buffer *eb,
5680                                  unsigned long start, unsigned long len)
5681 {
5682         unsigned long offset;
5683
5684         /* start, start + len should not go beyond eb->len nor overflow */
5685         if (unlikely(check_add_overflow(start, len, &offset) || offset > eb->len))
5686                 return report_eb_range(eb, start, len);
5687
5688         return false;
5689 }
5690
5691 void read_extent_buffer(const struct extent_buffer *eb, void *dstv,
5692                         unsigned long start, unsigned long len)
5693 {
5694         size_t cur;
5695         size_t offset;
5696         struct page *page;
5697         char *kaddr;
5698         char *dst = (char *)dstv;
5699         unsigned long i = get_eb_page_index(start);
5700
5701         if (check_eb_range(eb, start, len))
5702                 return;
5703
5704         offset = get_eb_offset_in_page(eb, start);
5705
5706         while (len > 0) {
5707                 page = eb->pages[i];
5708
5709                 cur = min(len, (PAGE_SIZE - offset));
5710                 kaddr = page_address(page);
5711                 memcpy(dst, kaddr + offset, cur);
5712
5713                 dst += cur;
5714                 len -= cur;
5715                 offset = 0;
5716                 i++;
5717         }
5718 }
5719
5720 int read_extent_buffer_to_user_nofault(const struct extent_buffer *eb,
5721                                        void __user *dstv,
5722                                        unsigned long start, unsigned long len)
5723 {
5724         size_t cur;
5725         size_t offset;
5726         struct page *page;
5727         char *kaddr;
5728         char __user *dst = (char __user *)dstv;
5729         unsigned long i = get_eb_page_index(start);
5730         int ret = 0;
5731
5732         WARN_ON(start > eb->len);
5733         WARN_ON(start + len > eb->start + eb->len);
5734
5735         offset = get_eb_offset_in_page(eb, start);
5736
5737         while (len > 0) {
5738                 page = eb->pages[i];
5739
5740                 cur = min(len, (PAGE_SIZE - offset));
5741                 kaddr = page_address(page);
5742                 if (copy_to_user_nofault(dst, kaddr + offset, cur)) {
5743                         ret = -EFAULT;
5744                         break;
5745                 }
5746
5747                 dst += cur;
5748                 len -= cur;
5749                 offset = 0;
5750                 i++;
5751         }
5752
5753         return ret;
5754 }
5755
5756 int memcmp_extent_buffer(const struct extent_buffer *eb, const void *ptrv,
5757                          unsigned long start, unsigned long len)
5758 {
5759         size_t cur;
5760         size_t offset;
5761         struct page *page;
5762         char *kaddr;
5763         char *ptr = (char *)ptrv;
5764         unsigned long i = get_eb_page_index(start);
5765         int ret = 0;
5766
5767         if (check_eb_range(eb, start, len))
5768                 return -EINVAL;
5769
5770         offset = get_eb_offset_in_page(eb, start);
5771
5772         while (len > 0) {
5773                 page = eb->pages[i];
5774
5775                 cur = min(len, (PAGE_SIZE - offset));
5776
5777                 kaddr = page_address(page);
5778                 ret = memcmp(ptr, kaddr + offset, cur);
5779                 if (ret)
5780                         break;
5781
5782                 ptr += cur;
5783                 len -= cur;
5784                 offset = 0;
5785                 i++;
5786         }
5787         return ret;
5788 }
5789
5790 void write_extent_buffer_chunk_tree_uuid(const struct extent_buffer *eb,
5791                 const void *srcv)
5792 {
5793         char *kaddr;
5794
5795         WARN_ON(!PageUptodate(eb->pages[0]));
5796         kaddr = page_address(eb->pages[0]) + get_eb_offset_in_page(eb, 0);
5797         memcpy(kaddr + offsetof(struct btrfs_header, chunk_tree_uuid), srcv,
5798                         BTRFS_FSID_SIZE);
5799 }
5800
5801 void write_extent_buffer_fsid(const struct extent_buffer *eb, const void *srcv)
5802 {
5803         char *kaddr;
5804
5805         WARN_ON(!PageUptodate(eb->pages[0]));
5806         kaddr = page_address(eb->pages[0]) + get_eb_offset_in_page(eb, 0);
5807         memcpy(kaddr + offsetof(struct btrfs_header, fsid), srcv,
5808                         BTRFS_FSID_SIZE);
5809 }
5810
5811 void write_extent_buffer(const struct extent_buffer *eb, const void *srcv,
5812                          unsigned long start, unsigned long len)
5813 {
5814         size_t cur;
5815         size_t offset;
5816         struct page *page;
5817         char *kaddr;
5818         char *src = (char *)srcv;
5819         unsigned long i = get_eb_page_index(start);
5820
5821         if (check_eb_range(eb, start, len))
5822                 return;
5823
5824         offset = get_eb_offset_in_page(eb, start);
5825
5826         while (len > 0) {
5827                 page = eb->pages[i];
5828                 WARN_ON(!PageUptodate(page));
5829
5830                 cur = min(len, PAGE_SIZE - offset);
5831                 kaddr = page_address(page);
5832                 memcpy(kaddr + offset, src, cur);
5833
5834                 src += cur;
5835                 len -= cur;
5836                 offset = 0;
5837                 i++;
5838         }
5839 }
5840
5841 void memzero_extent_buffer(const struct extent_buffer *eb, unsigned long start,
5842                 unsigned long len)
5843 {
5844         size_t cur;
5845         size_t offset;
5846         struct page *page;
5847         char *kaddr;
5848         unsigned long i = get_eb_page_index(start);
5849
5850         if (check_eb_range(eb, start, len))
5851                 return;
5852
5853         offset = get_eb_offset_in_page(eb, start);
5854
5855         while (len > 0) {
5856                 page = eb->pages[i];
5857                 WARN_ON(!PageUptodate(page));
5858
5859                 cur = min(len, PAGE_SIZE - offset);
5860                 kaddr = page_address(page);
5861                 memset(kaddr + offset, 0, cur);
5862
5863                 len -= cur;
5864                 offset = 0;
5865                 i++;
5866         }
5867 }
5868
5869 void copy_extent_buffer_full(const struct extent_buffer *dst,
5870                              const struct extent_buffer *src)
5871 {
5872         int i;
5873         int num_pages;
5874
5875         ASSERT(dst->len == src->len);
5876
5877         if (dst->fs_info->sectorsize == PAGE_SIZE) {
5878                 num_pages = num_extent_pages(dst);
5879                 for (i = 0; i < num_pages; i++)
5880                         copy_page(page_address(dst->pages[i]),
5881                                   page_address(src->pages[i]));
5882         } else {
5883                 size_t src_offset = get_eb_offset_in_page(src, 0);
5884                 size_t dst_offset = get_eb_offset_in_page(dst, 0);
5885
5886                 ASSERT(src->fs_info->sectorsize < PAGE_SIZE);
5887                 memcpy(page_address(dst->pages[0]) + dst_offset,
5888                        page_address(src->pages[0]) + src_offset,
5889                        src->len);
5890         }
5891 }
5892
5893 void copy_extent_buffer(const struct extent_buffer *dst,
5894                         const struct extent_buffer *src,
5895                         unsigned long dst_offset, unsigned long src_offset,
5896                         unsigned long len)
5897 {
5898         u64 dst_len = dst->len;
5899         size_t cur;
5900         size_t offset;
5901         struct page *page;
5902         char *kaddr;
5903         unsigned long i = get_eb_page_index(dst_offset);
5904
5905         if (check_eb_range(dst, dst_offset, len) ||
5906             check_eb_range(src, src_offset, len))
5907                 return;
5908
5909         WARN_ON(src->len != dst_len);
5910
5911         offset = get_eb_offset_in_page(dst, dst_offset);
5912
5913         while (len > 0) {
5914                 page = dst->pages[i];
5915                 WARN_ON(!PageUptodate(page));
5916
5917                 cur = min(len, (unsigned long)(PAGE_SIZE - offset));
5918
5919                 kaddr = page_address(page);
5920                 read_extent_buffer(src, kaddr + offset, src_offset, cur);
5921
5922                 src_offset += cur;
5923                 len -= cur;
5924                 offset = 0;
5925                 i++;
5926         }
5927 }
5928
5929 /*
5930  * eb_bitmap_offset() - calculate the page and offset of the byte containing the
5931  * given bit number
5932  * @eb: the extent buffer
5933  * @start: offset of the bitmap item in the extent buffer
5934  * @nr: bit number
5935  * @page_index: return index of the page in the extent buffer that contains the
5936  * given bit number
5937  * @page_offset: return offset into the page given by page_index
5938  *
5939  * This helper hides the ugliness of finding the byte in an extent buffer which
5940  * contains a given bit.
5941  */
5942 static inline void eb_bitmap_offset(const struct extent_buffer *eb,
5943                                     unsigned long start, unsigned long nr,
5944                                     unsigned long *page_index,
5945                                     size_t *page_offset)
5946 {
5947         size_t byte_offset = BIT_BYTE(nr);
5948         size_t offset;
5949
5950         /*
5951          * The byte we want is the offset of the extent buffer + the offset of
5952          * the bitmap item in the extent buffer + the offset of the byte in the
5953          * bitmap item.
5954          */
5955         offset = start + offset_in_page(eb->start) + byte_offset;
5956
5957         *page_index = offset >> PAGE_SHIFT;
5958         *page_offset = offset_in_page(offset);
5959 }
5960
5961 /**
5962  * extent_buffer_test_bit - determine whether a bit in a bitmap item is set
5963  * @eb: the extent buffer
5964  * @start: offset of the bitmap item in the extent buffer
5965  * @nr: bit number to test
5966  */
5967 int extent_buffer_test_bit(const struct extent_buffer *eb, unsigned long start,
5968                            unsigned long nr)
5969 {
5970         u8 *kaddr;
5971         struct page *page;
5972         unsigned long i;
5973         size_t offset;
5974
5975         eb_bitmap_offset(eb, start, nr, &i, &offset);
5976         page = eb->pages[i];
5977         WARN_ON(!PageUptodate(page));
5978         kaddr = page_address(page);
5979         return 1U & (kaddr[offset] >> (nr & (BITS_PER_BYTE - 1)));
5980 }
5981
5982 /**
5983  * extent_buffer_bitmap_set - set an area of a bitmap
5984  * @eb: the extent buffer
5985  * @start: offset of the bitmap item in the extent buffer
5986  * @pos: bit number of the first bit
5987  * @len: number of bits to set
5988  */
5989 void extent_buffer_bitmap_set(const struct extent_buffer *eb, unsigned long start,
5990                               unsigned long pos, unsigned long len)
5991 {
5992         u8 *kaddr;
5993         struct page *page;
5994         unsigned long i;
5995         size_t offset;
5996         const unsigned int size = pos + len;
5997         int bits_to_set = BITS_PER_BYTE - (pos % BITS_PER_BYTE);
5998         u8 mask_to_set = BITMAP_FIRST_BYTE_MASK(pos);
5999
6000         eb_bitmap_offset(eb, start, pos, &i, &offset);
6001         page = eb->pages[i];
6002         WARN_ON(!PageUptodate(page));
6003         kaddr = page_address(page);
6004
6005         while (len >= bits_to_set) {
6006                 kaddr[offset] |= mask_to_set;
6007                 len -= bits_to_set;
6008                 bits_to_set = BITS_PER_BYTE;
6009                 mask_to_set = ~0;
6010                 if (++offset >= PAGE_SIZE && len > 0) {
6011                         offset = 0;
6012                         page = eb->pages[++i];
6013                         WARN_ON(!PageUptodate(page));
6014                         kaddr = page_address(page);
6015                 }
6016         }
6017         if (len) {
6018                 mask_to_set &= BITMAP_LAST_BYTE_MASK(size);
6019                 kaddr[offset] |= mask_to_set;
6020         }
6021 }
6022
6023
6024 /**
6025  * extent_buffer_bitmap_clear - clear an area of a bitmap
6026  * @eb: the extent buffer
6027  * @start: offset of the bitmap item in the extent buffer
6028  * @pos: bit number of the first bit
6029  * @len: number of bits to clear
6030  */
6031 void extent_buffer_bitmap_clear(const struct extent_buffer *eb,
6032                                 unsigned long start, unsigned long pos,
6033                                 unsigned long len)
6034 {
6035         u8 *kaddr;
6036         struct page *page;
6037         unsigned long i;
6038         size_t offset;
6039         const unsigned int size = pos + len;
6040         int bits_to_clear = BITS_PER_BYTE - (pos % BITS_PER_BYTE);
6041         u8 mask_to_clear = BITMAP_FIRST_BYTE_MASK(pos);
6042
6043         eb_bitmap_offset(eb, start, pos, &i, &offset);
6044         page = eb->pages[i];
6045         WARN_ON(!PageUptodate(page));
6046         kaddr = page_address(page);
6047
6048         while (len >= bits_to_clear) {
6049                 kaddr[offset] &= ~mask_to_clear;
6050                 len -= bits_to_clear;
6051                 bits_to_clear = BITS_PER_BYTE;
6052                 mask_to_clear = ~0;
6053                 if (++offset >= PAGE_SIZE && len > 0) {
6054                         offset = 0;
6055                         page = eb->pages[++i];
6056                         WARN_ON(!PageUptodate(page));
6057                         kaddr = page_address(page);
6058                 }
6059         }
6060         if (len) {
6061                 mask_to_clear &= BITMAP_LAST_BYTE_MASK(size);
6062                 kaddr[offset] &= ~mask_to_clear;
6063         }
6064 }
6065
6066 static inline bool areas_overlap(unsigned long src, unsigned long dst, unsigned long len)
6067 {
6068         unsigned long distance = (src > dst) ? src - dst : dst - src;
6069         return distance < len;
6070 }
6071
6072 static void copy_pages(struct page *dst_page, struct page *src_page,
6073                        unsigned long dst_off, unsigned long src_off,
6074                        unsigned long len)
6075 {
6076         char *dst_kaddr = page_address(dst_page);
6077         char *src_kaddr;
6078         int must_memmove = 0;
6079
6080         if (dst_page != src_page) {
6081                 src_kaddr = page_address(src_page);
6082         } else {
6083                 src_kaddr = dst_kaddr;
6084                 if (areas_overlap(src_off, dst_off, len))
6085                         must_memmove = 1;
6086         }
6087
6088         if (must_memmove)
6089                 memmove(dst_kaddr + dst_off, src_kaddr + src_off, len);
6090         else
6091                 memcpy(dst_kaddr + dst_off, src_kaddr + src_off, len);
6092 }
6093
6094 void memcpy_extent_buffer(const struct extent_buffer *dst,
6095                           unsigned long dst_offset, unsigned long src_offset,
6096                           unsigned long len)
6097 {
6098         size_t cur;
6099         size_t dst_off_in_page;
6100         size_t src_off_in_page;
6101         unsigned long dst_i;
6102         unsigned long src_i;
6103
6104         if (check_eb_range(dst, dst_offset, len) ||
6105             check_eb_range(dst, src_offset, len))
6106                 return;
6107
6108         while (len > 0) {
6109                 dst_off_in_page = get_eb_offset_in_page(dst, dst_offset);
6110                 src_off_in_page = get_eb_offset_in_page(dst, src_offset);
6111
6112                 dst_i = get_eb_page_index(dst_offset);
6113                 src_i = get_eb_page_index(src_offset);
6114
6115                 cur = min(len, (unsigned long)(PAGE_SIZE -
6116                                                src_off_in_page));
6117                 cur = min_t(unsigned long, cur,
6118                         (unsigned long)(PAGE_SIZE - dst_off_in_page));
6119
6120                 copy_pages(dst->pages[dst_i], dst->pages[src_i],
6121                            dst_off_in_page, src_off_in_page, cur);
6122
6123                 src_offset += cur;
6124                 dst_offset += cur;
6125                 len -= cur;
6126         }
6127 }
6128
6129 void memmove_extent_buffer(const struct extent_buffer *dst,
6130                            unsigned long dst_offset, unsigned long src_offset,
6131                            unsigned long len)
6132 {
6133         size_t cur;
6134         size_t dst_off_in_page;
6135         size_t src_off_in_page;
6136         unsigned long dst_end = dst_offset + len - 1;
6137         unsigned long src_end = src_offset + len - 1;
6138         unsigned long dst_i;
6139         unsigned long src_i;
6140
6141         if (check_eb_range(dst, dst_offset, len) ||
6142             check_eb_range(dst, src_offset, len))
6143                 return;
6144         if (dst_offset < src_offset) {
6145                 memcpy_extent_buffer(dst, dst_offset, src_offset, len);
6146                 return;
6147         }
6148         while (len > 0) {
6149                 dst_i = get_eb_page_index(dst_end);
6150                 src_i = get_eb_page_index(src_end);
6151
6152                 dst_off_in_page = get_eb_offset_in_page(dst, dst_end);
6153                 src_off_in_page = get_eb_offset_in_page(dst, src_end);
6154
6155                 cur = min_t(unsigned long, len, src_off_in_page + 1);
6156                 cur = min(cur, dst_off_in_page + 1);
6157                 copy_pages(dst->pages[dst_i], dst->pages[src_i],
6158                            dst_off_in_page - cur + 1,
6159                            src_off_in_page - cur + 1, cur);
6160
6161                 dst_end -= cur;
6162                 src_end -= cur;
6163                 len -= cur;
6164         }
6165 }
6166
6167 int try_release_extent_buffer(struct page *page)
6168 {
6169         struct extent_buffer *eb;
6170
6171         /*
6172          * We need to make sure nobody is attaching this page to an eb right
6173          * now.
6174          */
6175         spin_lock(&page->mapping->private_lock);
6176         if (!PagePrivate(page)) {
6177                 spin_unlock(&page->mapping->private_lock);
6178                 return 1;
6179         }
6180
6181         eb = (struct extent_buffer *)page->private;
6182         BUG_ON(!eb);
6183
6184         /*
6185          * This is a little awful but should be ok, we need to make sure that
6186          * the eb doesn't disappear out from under us while we're looking at
6187          * this page.
6188          */
6189         spin_lock(&eb->refs_lock);
6190         if (atomic_read(&eb->refs) != 1 || extent_buffer_under_io(eb)) {
6191                 spin_unlock(&eb->refs_lock);
6192                 spin_unlock(&page->mapping->private_lock);
6193                 return 0;
6194         }
6195         spin_unlock(&page->mapping->private_lock);
6196
6197         /*
6198          * If tree ref isn't set then we know the ref on this eb is a real ref,
6199          * so just return, this page will likely be freed soon anyway.
6200          */
6201         if (!test_and_clear_bit(EXTENT_BUFFER_TREE_REF, &eb->bflags)) {
6202                 spin_unlock(&eb->refs_lock);
6203                 return 0;
6204         }
6205
6206         return release_extent_buffer(eb);
6207 }
6208
6209 /*
6210  * btrfs_readahead_tree_block - attempt to readahead a child block
6211  * @fs_info:    the fs_info
6212  * @bytenr:     bytenr to read
6213  * @owner_root: objectid of the root that owns this eb
6214  * @gen:        generation for the uptodate check, can be 0
6215  * @level:      level for the eb
6216  *
6217  * Attempt to readahead a tree block at @bytenr.  If @gen is 0 then we do a
6218  * normal uptodate check of the eb, without checking the generation.  If we have
6219  * to read the block we will not block on anything.
6220  */
6221 void btrfs_readahead_tree_block(struct btrfs_fs_info *fs_info,
6222                                 u64 bytenr, u64 owner_root, u64 gen, int level)
6223 {
6224         struct extent_buffer *eb;
6225         int ret;
6226
6227         eb = btrfs_find_create_tree_block(fs_info, bytenr, owner_root, level);
6228         if (IS_ERR(eb))
6229                 return;
6230
6231         if (btrfs_buffer_uptodate(eb, gen, 1)) {
6232                 free_extent_buffer(eb);
6233                 return;
6234         }
6235
6236         ret = read_extent_buffer_pages(eb, WAIT_NONE, 0);
6237         if (ret < 0)
6238                 free_extent_buffer_stale(eb);
6239         else
6240                 free_extent_buffer(eb);
6241 }
6242
6243 /*
6244  * btrfs_readahead_node_child - readahead a node's child block
6245  * @node:       parent node we're reading from
6246  * @slot:       slot in the parent node for the child we want to read
6247  *
6248  * A helper for btrfs_readahead_tree_block, we simply read the bytenr pointed at
6249  * the slot in the node provided.
6250  */
6251 void btrfs_readahead_node_child(struct extent_buffer *node, int slot)
6252 {
6253         btrfs_readahead_tree_block(node->fs_info,
6254                                    btrfs_node_blockptr(node, slot),
6255                                    btrfs_header_owner(node),
6256                                    btrfs_node_ptr_generation(node, slot),
6257                                    btrfs_header_level(node) - 1);
6258 }