fs/btrfs/extent_io.c

   1 #include <linux/bitops.h>
   2 #include <linux/slab.h>
   3 #include <linux/bio.h>
   4 #include <linux/mm.h>
   5 #include <linux/pagemap.h>
   6 #include <linux/page-flags.h>
   7 #include <linux/module.h>
   8 #include <linux/spinlock.h>
   9 #include <linux/blkdev.h>
  10 #include <linux/swap.h>
  11 #include <linux/writeback.h>
  12 #include <linux/pagevec.h>
  13 #include <linux/prefetch.h>
  14 #include <linux/cleancache.h>
  15 #include "extent_io.h"
  16 #include "extent_map.h"
  17 #include "compat.h"
  18 #include "ctree.h"
  19 #include "btrfs_inode.h"
  20
  21 static struct kmem_cache *extent_state_cache;
  22 static struct kmem_cache *extent_buffer_cache;
  23
  24 static LIST_HEAD(buffers);
  25 static LIST_HEAD(states);
  26
  27 #define LEAK_DEBUG 0
  28 #if LEAK_DEBUG
  29 static DEFINE_SPINLOCK(leak_lock);
  30 #endif
  31
  32 #define BUFFER_LRU_MAX 64
  33
  34 struct tree_entry {
  35         u64 start;
  36         u64 end;
  37         struct rb_node rb_node;
  38 };
  39
  40 struct extent_page_data {
  41         struct bio *bio;
  42         struct extent_io_tree *tree;
  43         get_extent_t *get_extent;
  44
  45         /* tells writepage not to lock the state bits for this range
  46          * it still does the unlocking
  47          */
  48         unsigned int extent_locked:1;
  49
  50         /* tells the submit_bio code to use a WRITE_SYNC */
  51         unsigned int sync_io:1;
  52 };
  53
  54 int __init extent_io_init(void)
  55 {
  56         extent_state_cache = kmem_cache_create("extent_state",
  57                         sizeof(struct extent_state), 0,
  58                         SLAB_RECLAIM_ACCOUNT | SLAB_MEM_SPREAD, NULL);
  59         if (!extent_state_cache)
  60                 return -ENOMEM;
  61
  62         extent_buffer_cache = kmem_cache_create("extent_buffers",
  63                         sizeof(struct extent_buffer), 0,
  64                         SLAB_RECLAIM_ACCOUNT | SLAB_MEM_SPREAD, NULL);
  65         if (!extent_buffer_cache)
  66                 goto free_state_cache;
  67         return 0;
  68
  69 free_state_cache:
  70         kmem_cache_destroy(extent_state_cache);
  71         return -ENOMEM;
  72 }
  73
  74 void extent_io_exit(void)
  75 {
  76         struct extent_state *state;
  77         struct extent_buffer *eb;
  78
  79         while (!list_empty(&states)) {
  80                 state = list_entry(states.next, struct extent_state, leak_list);
  81                 printk(KERN_ERR "btrfs state leak: start %llu end %llu "
  82                        "state %lu in tree %p refs %d\n",
  83                        (unsigned long long)state->start,
  84                        (unsigned long long)state->end,
  85                        state->state, state->tree, atomic_read(&state->refs));
  86                 list_del(&state->leak_list);
  87                 kmem_cache_free(extent_state_cache, state);
  88
  89         }
  90
  91         while (!list_empty(&buffers)) {
  92                 eb = list_entry(buffers.next, struct extent_buffer, leak_list);
  93                 printk(KERN_ERR "btrfs buffer leak start %llu len %lu "
  94                        "refs %d\n", (unsigned long long)eb->start,
  95                        eb->len, atomic_read(&eb->refs));
  96                 list_del(&eb->leak_list);
  97                 kmem_cache_free(extent_buffer_cache, eb);
  98         }
  99         if (extent_state_cache)
 100                 kmem_cache_destroy(extent_state_cache);
 101         if (extent_buffer_cache)
 102                 kmem_cache_destroy(extent_buffer_cache);
 103 }
 104
 105 void extent_io_tree_init(struct extent_io_tree *tree,
 106                          struct address_space *mapping)
 107 {
 108         tree->state = RB_ROOT;
 109         INIT_RADIX_TREE(&tree->buffer, GFP_ATOMIC);
 110         tree->ops = NULL;
 111         tree->dirty_bytes = 0;
 112         spin_lock_init(&tree->lock);
 113         spin_lock_init(&tree->buffer_lock);
 114         tree->mapping = mapping;
 115 }
 116
 117 static struct extent_state *alloc_extent_state(gfp_t mask)
 118 {
 119         struct extent_state *state;
 120 #if LEAK_DEBUG
 121         unsigned long flags;
 122 #endif
 123
 124         state = kmem_cache_alloc(extent_state_cache, mask);
 125         if (!state)
 126                 return state;
 127         state->state = 0;
 128         state->private = 0;
 129         state->tree = NULL;
 130 #if LEAK_DEBUG
 131         spin_lock_irqsave(&leak_lock, flags);
 132         list_add(&state->leak_list, &states);
 133         spin_unlock_irqrestore(&leak_lock, flags);
 134 #endif
 135         atomic_set(&state->refs, 1);
 136         init_waitqueue_head(&state->wq);
 137         return state;
 138 }
 139
 140 void free_extent_state(struct extent_state *state)
 141 {
 142         if (!state)
 143                 return;
 144         if (atomic_dec_and_test(&state->refs)) {
 145 #if LEAK_DEBUG
 146                 unsigned long flags;
 147 #endif
 148                 WARN_ON(state->tree);
 149 #if LEAK_DEBUG
 150                 spin_lock_irqsave(&leak_lock, flags);
 151                 list_del(&state->leak_list);
 152                 spin_unlock_irqrestore(&leak_lock, flags);
 153 #endif
 154                 kmem_cache_free(extent_state_cache, state);
 155         }
 156 }
 157
 158 static struct rb_node *tree_insert(struct rb_root *root, u64 offset,
 159                                    struct rb_node *node)
 160 {
 161         struct rb_node **p = &root->rb_node;
 162         struct rb_node *parent = NULL;
 163         struct tree_entry *entry;
 164
 165         while (*p) {
 166                 parent = *p;
 167                 entry = rb_entry(parent, struct tree_entry, rb_node);
 168
 169                 if (offset < entry->start)
 170                         p = &(*p)->rb_left;
 171                 else if (offset > entry->end)
 172                         p = &(*p)->rb_right;
 173                 else
 174                         return parent;
 175         }
 176
 177         entry = rb_entry(node, struct tree_entry, rb_node);
 178         rb_link_node(node, parent, p);
 179         rb_insert_color(node, root);
 180         return NULL;
 181 }
 182
 183 static struct rb_node *__etree_search(struct extent_io_tree *tree, u64 offset,
 184                                      struct rb_node **prev_ret,
 185                                      struct rb_node **next_ret)
 186 {
 187         struct rb_root *root = &tree->state;
 188         struct rb_node *n = root->rb_node;
 189         struct rb_node *prev = NULL;
 190         struct rb_node *orig_prev = NULL;
 191         struct tree_entry *entry;
 192         struct tree_entry *prev_entry = NULL;
 193
 194         while (n) {
 195                 entry = rb_entry(n, struct tree_entry, rb_node);
 196                 prev = n;
 197                 prev_entry = entry;
 198
 199                 if (offset < entry->start)
 200                         n = n->rb_left;
 201                 else if (offset > entry->end)
 202                         n = n->rb_right;
 203                 else
 204                         return n;
 205         }
 206
 207         if (prev_ret) {
 208                 orig_prev = prev;
 209                 while (prev && offset > prev_entry->end) {
 210                         prev = rb_next(prev);
 211                         prev_entry = rb_entry(prev, struct tree_entry, rb_node);
 212                 }
 213                 *prev_ret = prev;
 214                 prev = orig_prev;
 215         }
 216
 217         if (next_ret) {
 218                 prev_entry = rb_entry(prev, struct tree_entry, rb_node);
 219                 while (prev && offset < prev_entry->start) {
 220                         prev = rb_prev(prev);
 221                         prev_entry = rb_entry(prev, struct tree_entry, rb_node);
 222                 }
 223                 *next_ret = prev;
 224         }
 225         return NULL;
 226 }
 227
 228 static inline struct rb_node *tree_search(struct extent_io_tree *tree,
 229                                           u64 offset)
 230 {
 231         struct rb_node *prev = NULL;
 232         struct rb_node *ret;
 233
 234         ret = __etree_search(tree, offset, &prev, NULL);
 235         if (!ret)
 236                 return prev;
 237         return ret;
 238 }
 239
 240 static void merge_cb(struct extent_io_tree *tree, struct extent_state *new,
 241                      struct extent_state *other)
 242 {
 243         if (tree->ops && tree->ops->merge_extent_hook)
 244                 tree->ops->merge_extent_hook(tree->mapping->host, new,
 245                                              other);
 246 }
 247
 248 /*
 249  * utility function to look for merge candidates inside a given range.
 250  * Any extents with matching state are merged together into a single
 251  * extent in the tree.  Extents with EXTENT_IO in their state field
 252  * are not merged because the end_io handlers need to be able to do
 253  * operations on them without sleeping (or doing allocations/splits).
 254  *
 255  * This should be called with the tree lock held.
 256  */
 257 static void merge_state(struct extent_io_tree *tree,
 258                         struct extent_state *state)
 259 {
 260         struct extent_state *other;
 261         struct rb_node *other_node;
 262
 263         if (state->state & (EXTENT_IOBITS | EXTENT_BOUNDARY))
 264                 return;
 265
 266         other_node = rb_prev(&state->rb_node);
 267         if (other_node) {
 268                 other = rb_entry(other_node, struct extent_state, rb_node);
 269                 if (other->end == state->start - 1 &&
 270                     other->state == state->state) {
 271                         merge_cb(tree, state, other);
 272                         state->start = other->start;
 273                         other->tree = NULL;
 274                         rb_erase(&other->rb_node, &tree->state);
 275                         free_extent_state(other);
 276                 }
 277         }
 278         other_node = rb_next(&state->rb_node);
 279         if (other_node) {
 280                 other = rb_entry(other_node, struct extent_state, rb_node);
 281                 if (other->start == state->end + 1 &&
 282                     other->state == state->state) {
 283                         merge_cb(tree, state, other);
 284                         state->end = other->end;
 285                         other->tree = NULL;
 286                         rb_erase(&other->rb_node, &tree->state);
 287                         free_extent_state(other);
 288                 }
 289         }
 290 }
 291
 292 static void set_state_cb(struct extent_io_tree *tree,
 293                          struct extent_state *state, int *bits)
 294 {
 295         if (tree->ops && tree->ops->set_bit_hook)
 296                 tree->ops->set_bit_hook(tree->mapping->host, state, bits);
 297 }
 298
 299 static void clear_state_cb(struct extent_io_tree *tree,
 300                            struct extent_state *state, int *bits)
 301 {
 302         if (tree->ops && tree->ops->clear_bit_hook)
 303                 tree->ops->clear_bit_hook(tree->mapping->host, state, bits);
 304 }
 305
 306 static void set_state_bits(struct extent_io_tree *tree,
 307                            struct extent_state *state, int *bits);
 308
 309 /*
 310  * insert an extent_state struct into the tree.  'bits' are set on the
 311  * struct before it is inserted.
 312  *
 313  * This may return -EEXIST if the extent is already there, in which case the
 314  * state struct is freed.
 315  *
 316  * The tree lock is not taken internally.  This is a utility function and
 317  * probably isn't what you want to call (see set/clear_extent_bit).
 318  */
 319 static int insert_state(struct extent_io_tree *tree,
 320                         struct extent_state *state, u64 start, u64 end,
 321                         int *bits)
 322 {
 323         struct rb_node *node;
 324
 325         if (end < start) {
 326                 printk(KERN_ERR "btrfs end < start %llu %llu\n",
 327                        (unsigned long long)end,
 328                        (unsigned long long)start);
 329                 WARN_ON(1);
 330         }
 331         state->start = start;
 332         state->end = end;
 333
 334         set_state_bits(tree, state, bits);
 335
 336         node = tree_insert(&tree->state, end, &state->rb_node);
 337         if (node) {
 338                 struct extent_state *found;
 339                 found = rb_entry(node, struct extent_state, rb_node);
 340                 printk(KERN_ERR "btrfs found node %llu %llu on insert of "
 341                        "%llu %llu\n", (unsigned long long)found->start,
 342                        (unsigned long long)found->end,
 343                        (unsigned long long)start, (unsigned long long)end);
 344                 return -EEXIST;
 345         }
 346         state->tree = tree;
 347         merge_state(tree, state);
 348         return 0;
 349 }
 350
 351 static void split_cb(struct extent_io_tree *tree, struct extent_state *orig,
 352                      u64 split)
 353 {
 354         if (tree->ops && tree->ops->split_extent_hook)
 355                 tree->ops->split_extent_hook(tree->mapping->host, orig, split);
 356 }
 357
 358 /*
 359  * split a given extent state struct in two, inserting the preallocated
 360  * struct 'prealloc' as the newly created second half.  'split' indicates an
 361  * offset inside 'orig' where it should be split.
 362  *
 363  * Before calling,
 364  * the tree has 'orig' at [orig->start, orig->end].  After calling, there
 365  * are two extent state structs in the tree:
 366  * prealloc: [orig->start, split - 1]
 367  * orig: [ split, orig->end ]
 368  *
 369  * The tree locks are not taken by this function. They need to be held
 370  * by the caller.
 371  */
 372 static int split_state(struct extent_io_tree *tree, struct extent_state *orig,
 373                        struct extent_state *prealloc, u64 split)
 374 {
 375         struct rb_node *node;
 376
 377         split_cb(tree, orig, split);
 378
 379         prealloc->start = orig->start;
 380         prealloc->end = split - 1;
 381         prealloc->state = orig->state;
 382         orig->start = split;
 383
 384         node = tree_insert(&tree->state, prealloc->end, &prealloc->rb_node);
 385         if (node) {
 386                 free_extent_state(prealloc);
 387                 return -EEXIST;
 388         }
 389         prealloc->tree = tree;
 390         return 0;
 391 }
 392
 393 /*
 394  * utility function to clear some bits in an extent state struct.
 395  * it will optionally wake up any one waiting on this state (wake == 1), or
 396  * forcibly remove the state from the tree (delete == 1).
 397  *
 398  * If no bits are set on the state struct after clearing things, the
 399  * struct is freed and removed from the tree
 400  */
 401 static int clear_state_bit(struct extent_io_tree *tree,
 402                             struct extent_state *state,
 403                             int *bits, int wake)
 404 {
 405         int bits_to_clear = *bits & ~EXTENT_CTLBITS;
 406         int ret = state->state & bits_to_clear;
 407
 408         if ((bits_to_clear & EXTENT_DIRTY) && (state->state & EXTENT_DIRTY)) {
 409                 u64 range = state->end - state->start + 1;
 410                 WARN_ON(range > tree->dirty_bytes);
 411                 tree->dirty_bytes -= range;
 412         }
 413         clear_state_cb(tree, state, bits);
 414         state->state &= ~bits_to_clear;
 415         if (wake)
 416                 wake_up(&state->wq);
 417         if (state->state == 0) {
 418                 if (state->tree) {
 419                         rb_erase(&state->rb_node, &tree->state);
 420                         state->tree = NULL;
 421                         free_extent_state(state);
 422                 } else {
 423                         WARN_ON(1);
 424                 }
 425         } else {
 426                 merge_state(tree, state);
 427         }
 428         return ret;
 429 }
 430
 431 static struct extent_state *
 432 alloc_extent_state_atomic(struct extent_state *prealloc)
 433 {
 434         if (!prealloc)
 435                 prealloc = alloc_extent_state(GFP_ATOMIC);
 436
 437         return prealloc;
 438 }
 439
 440 /*
 441  * clear some bits on a range in the tree.  This may require splitting
 442  * or inserting elements in the tree, so the gfp mask is used to
 443  * indicate which allocations or sleeping are allowed.
 444  *
 445  * pass 'wake' == 1 to kick any sleepers, and 'delete' == 1 to remove
 446  * the given range from the tree regardless of state (ie for truncate).
 447  *
 448  * the range [start, end] is inclusive.
 449  *
 450  * This takes the tree lock, and returns < 0 on error, > 0 if any of the
 451  * bits were already set, or zero if none of the bits were already set.
 452  */
 453 int clear_extent_bit(struct extent_io_tree *tree, u64 start, u64 end,
 454                      int bits, int wake, int delete,
 455                      struct extent_state **cached_state,
 456                      gfp_t mask)
 457 {
 458         struct extent_state *state;
 459         struct extent_state *cached;
 460         struct extent_state *prealloc = NULL;
 461         struct rb_node *next_node;
 462         struct rb_node *node;
 463         u64 last_end;
 464         int err;
 465         int set = 0;
 466         int clear = 0;
 467
 468         if (delete)
 469                 bits |= ~EXTENT_CTLBITS;
 470         bits |= EXTENT_FIRST_DELALLOC;
 471
 472         if (bits & (EXTENT_IOBITS | EXTENT_BOUNDARY))
 473                 clear = 1;
 474 again:
 475         if (!prealloc && (mask & __GFP_WAIT)) {
 476                 prealloc = alloc_extent_state(mask);
 477                 if (!prealloc)
 478                         return -ENOMEM;
 479         }
 480
 481         spin_lock(&tree->lock);
 482         if (cached_state) {
 483                 cached = *cached_state;
 484
 485                 if (clear) {
 486                         *cached_state = NULL;
 487                         cached_state = NULL;
 488                 }
 489
 490                 if (cached && cached->tree && cached->start <= start &&
 491                     cached->end > start) {
 492                         if (clear)
 493                                 atomic_dec(&cached->refs);
 494                         state = cached;
 495                         goto hit_next;
 496                 }
 497                 if (clear)
 498                         free_extent_state(cached);
 499         }
 500         /*
 501          * this search will find the extents that end after
 502          * our range starts
 503          */
 504         node = tree_search(tree, start);
 505         if (!node)
 506                 goto out;
 507         state = rb_entry(node, struct extent_state, rb_node);
 508 hit_next:
 509         if (state->start > end)
 510                 goto out;
 511         WARN_ON(state->end < start);
 512         last_end = state->end;
 513
 514         /*
 515          *     | ---- desired range ---- |
 516          *  | state | or
 517          *  | ------------- state -------------- |
 518          *
 519          * We need to split the extent we found, and may flip
 520          * bits on second half.
 521          *
 522          * If the extent we found extends past our range, we
 523          * just split and search again.  It'll get split again
 524          * the next time though.
 525          *
 526          * If the extent we found is inside our range, we clear
 527          * the desired bit on it.
 528          */
 529
 530         if (state->start < start) {
 531                 prealloc = alloc_extent_state_atomic(prealloc);
 532                 BUG_ON(!prealloc);
 533                 err = split_state(tree, state, prealloc, start);
 534                 BUG_ON(err == -EEXIST);
 535                 prealloc = NULL;
 536                 if (err)
 537                         goto out;
 538                 if (state->end <= end) {
 539                         set |= clear_state_bit(tree, state, &bits, wake);
 540                         if (last_end == (u64)-1)
 541                                 goto out;
 542                         start = last_end + 1;
 543                 }
 544                 goto search_again;
 545         }
 546         /*
 547          * | ---- desired range ---- |
 548          *                        | state |
 549          * We need to split the extent, and clear the bit
 550          * on the first half
 551          */
 552         if (state->start <= end && state->end > end) {
 553                 prealloc = alloc_extent_state_atomic(prealloc);
 554                 BUG_ON(!prealloc);
 555                 err = split_state(tree, state, prealloc, end + 1);
 556                 BUG_ON(err == -EEXIST);
 557                 if (wake)
 558                         wake_up(&state->wq);
 559
 560                 set |= clear_state_bit(tree, prealloc, &bits, wake);
 561
 562                 prealloc = NULL;
 563                 goto out;
 564         }
 565
 566         if (state->end < end && prealloc && !need_resched())
 567                 next_node = rb_next(&state->rb_node);
 568         else
 569                 next_node = NULL;
 570
 571         set |= clear_state_bit(tree, state, &bits, wake);
 572         if (last_end == (u64)-1)
 573                 goto out;
 574         start = last_end + 1;
 575         if (start <= end && next_node) {
 576                 state = rb_entry(next_node, struct extent_state,
 577                                  rb_node);
 578                 if (state->start == start)
 579                         goto hit_next;
 580         }
 581         goto search_again;
 582
 583 out:
 584         spin_unlock(&tree->lock);
 585         if (prealloc)
 586                 free_extent_state(prealloc);
 587
 588         return set;
 589
 590 search_again:
 591         if (start > end)
 592                 goto out;
 593         spin_unlock(&tree->lock);
 594         if (mask & __GFP_WAIT)
 595                 cond_resched();
 596         goto again;
 597 }
 598
 599 static int wait_on_state(struct extent_io_tree *tree,
 600                          struct extent_state *state)
 601                 __releases(tree->lock)
 602                 __acquires(tree->lock)
 603 {
 604         DEFINE_WAIT(wait);
 605         prepare_to_wait(&state->wq, &wait, TASK_UNINTERRUPTIBLE);
 606         spin_unlock(&tree->lock);
 607         schedule();
 608         spin_lock(&tree->lock);
 609         finish_wait(&state->wq, &wait);
 610         return 0;
 611 }
 612
 613 /*
 614  * waits for one or more bits to clear on a range in the state tree.
 615  * The range [start, end] is inclusive.
 616  * The tree lock is taken by this function
 617  */
 618 int wait_extent_bit(struct extent_io_tree *tree, u64 start, u64 end, int bits)
 619 {
 620         struct extent_state *state;
 621         struct rb_node *node;
 622
 623         spin_lock(&tree->lock);
 624 again:
 625         while (1) {
 626                 /*
 627                  * this search will find all the extents that end after
 628                  * our range starts
 629                  */
 630                 node = tree_search(tree, start);
 631                 if (!node)
 632                         break;
 633
 634                 state = rb_entry(node, struct extent_state, rb_node);
 635
 636                 if (state->start > end)
 637                         goto out;
 638
 639                 if (state->state & bits) {
 640                         start = state->start;
 641                         atomic_inc(&state->refs);
 642                         wait_on_state(tree, state);
 643                         free_extent_state(state);
 644                         goto again;
 645                 }
 646                 start = state->end + 1;
 647
 648                 if (start > end)
 649                         break;
 650
 651                 cond_resched_lock(&tree->lock);
 652         }
 653 out:
 654         spin_unlock(&tree->lock);
 655         return 0;
 656 }
 657
 658 static void set_state_bits(struct extent_io_tree *tree,
 659                            struct extent_state *state,
 660                            int *bits)
 661 {
 662         int bits_to_set = *bits & ~EXTENT_CTLBITS;
 663
 664         set_state_cb(tree, state, bits);
 665         if ((bits_to_set & EXTENT_DIRTY) && !(state->state & EXTENT_DIRTY)) {
 666                 u64 range = state->end - state->start + 1;
 667                 tree->dirty_bytes += range;
 668         }
 669         state->state |= bits_to_set;
 670 }
 671
 672 static void cache_state(struct extent_state *state,
 673                         struct extent_state **cached_ptr)
 674 {
 675         if (cached_ptr && !(*cached_ptr)) {
 676                 if (state->state & (EXTENT_IOBITS | EXTENT_BOUNDARY)) {
 677                         *cached_ptr = state;
 678                         atomic_inc(&state->refs);
 679                 }
 680         }
 681 }
 682
 683 static void uncache_state(struct extent_state **cached_ptr)
 684 {
 685         if (cached_ptr && (*cached_ptr)) {
 686                 struct extent_state *state = *cached_ptr;
 687                 *cached_ptr = NULL;
 688                 free_extent_state(state);
 689         }
 690 }
 691
 692 /*
 693  * set some bits on a range in the tree.  This may require allocations or
 694  * sleeping, so the gfp mask is used to indicate what is allowed.
 695  *
 696  * If any of the exclusive bits are set, this will fail with -EEXIST if some
 697  * part of the range already has the desired bits set.  The start of the
 698  * existing range is returned in failed_start in this case.
 699  *
 700  * [start, end] is inclusive This takes the tree lock.
 701  */
 702
 703 int set_extent_bit(struct extent_io_tree *tree, u64 start, u64 end,
 704                    int bits, int exclusive_bits, u64 *failed_start,
 705                    struct extent_state **cached_state, gfp_t mask)
 706 {
 707         struct extent_state *state;
 708         struct extent_state *prealloc = NULL;
 709         struct rb_node *node;
 710         int err = 0;
 711         u64 last_start;
 712         u64 last_end;
 713
 714         bits |= EXTENT_FIRST_DELALLOC;
 715 again:
 716         if (!prealloc && (mask & __GFP_WAIT)) {
 717                 prealloc = alloc_extent_state(mask);
 718                 BUG_ON(!prealloc);
 719         }
 720
 721         spin_lock(&tree->lock);
 722         if (cached_state && *cached_state) {
 723                 state = *cached_state;
 724                 if (state->start <= start && state->end > start &&
 725                     state->tree) {
 726                         node = &state->rb_node;
 727                         goto hit_next;
 728                 }
 729         }
 730         /*
 731          * this search will find all the extents that end after
 732          * our range starts.
 733          */
 734         node = tree_search(tree, start);
 735         if (!node) {
 736                 prealloc = alloc_extent_state_atomic(prealloc);
 737                 BUG_ON(!prealloc);
 738                 err = insert_state(tree, prealloc, start, end, &bits);
 739                 prealloc = NULL;
 740                 BUG_ON(err == -EEXIST);
 741                 goto out;
 742         }
 743         state = rb_entry(node, struct extent_state, rb_node);
 744 hit_next:
 745         last_start = state->start;
 746         last_end = state->end;
 747
 748         /*
 749          * | ---- desired range ---- |
 750          * | state |
 751          *
 752          * Just lock what we found and keep going
 753          */
 754         if (state->start == start && state->end <= end) {
 755                 struct rb_node *next_node;
 756                 if (state->state & exclusive_bits) {
 757                         *failed_start = state->start;
 758                         err = -EEXIST;
 759                         goto out;
 760                 }
 761
 762                 set_state_bits(tree, state, &bits);
 763
 764                 cache_state(state, cached_state);
 765                 merge_state(tree, state);
 766                 if (last_end == (u64)-1)
 767                         goto out;
 768
 769                 start = last_end + 1;
 770                 next_node = rb_next(&state->rb_node);
 771                 if (next_node && start < end && prealloc && !need_resched()) {
 772                         state = rb_entry(next_node, struct extent_state,
 773                                          rb_node);
 774                         if (state->start == start)
 775                                 goto hit_next;
 776                 }
 777                 goto search_again;
 778         }
 779
 780         /*
 781          *     | ---- desired range ---- |
 782          * | state |
 783          *   or
 784          * | ------------- state -------------- |
 785          *
 786          * We need to split the extent we found, and may flip bits on
 787          * second half.
 788          *
 789          * If the extent we found extends past our
 790          * range, we just split and search again.  It'll get split
 791          * again the next time though.
 792          *
 793          * If the extent we found is inside our range, we set the
 794          * desired bit on it.
 795          */
 796         if (state->start < start) {
 797                 if (state->state & exclusive_bits) {
 798                         *failed_start = start;
 799                         err = -EEXIST;
 800                         goto out;
 801                 }
 802
 803                 prealloc = alloc_extent_state_atomic(prealloc);
 804                 BUG_ON(!prealloc);
 805                 err = split_state(tree, state, prealloc, start);
 806                 BUG_ON(err == -EEXIST);
 807                 prealloc = NULL;
 808                 if (err)
 809                         goto out;
 810                 if (state->end <= end) {
 811                         set_state_bits(tree, state, &bits);
 812                         cache_state(state, cached_state);
 813                         merge_state(tree, state);
 814                         if (last_end == (u64)-1)
 815                                 goto out;
 816                         start = last_end + 1;
 817                 }
 818                 goto search_again;
 819         }
 820         /*
 821          * | ---- desired range ---- |
 822          *     | state | or               | state |
 823          *
 824          * There's a hole, we need to insert something in it and
 825          * ignore the extent we found.
 826          */
 827         if (state->start > start) {
 828                 u64 this_end;
 829                 if (end < last_start)
 830                         this_end = end;
 831                 else
 832                         this_end = last_start - 1;
 833
 834                 prealloc = alloc_extent_state_atomic(prealloc);
 835                 BUG_ON(!prealloc);
 836
 837                 /*
 838                  * Avoid to free 'prealloc' if it can be merged with
 839                  * the later extent.
 840                  */
 841                 err = insert_state(tree, prealloc, start, this_end,
 842                                    &bits);
 843                 BUG_ON(err == -EEXIST);
 844                 if (err) {
 845                         free_extent_state(prealloc);
 846                         prealloc = NULL;
 847                         goto out;
 848                 }
 849                 cache_state(prealloc, cached_state);
 850                 prealloc = NULL;
 851                 start = this_end + 1;
 852                 goto search_again;
 853         }
 854         /*
 855          * | ---- desired range ---- |
 856          *                        | state |
 857          * We need to split the extent, and set the bit
 858          * on the first half
 859          */
 860         if (state->start <= end && state->end > end) {
 861                 if (state->state & exclusive_bits) {
 862                         *failed_start = start;
 863                         err = -EEXIST;
 864                         goto out;
 865                 }
 866
 867                 prealloc = alloc_extent_state_atomic(prealloc);
 868                 BUG_ON(!prealloc);
 869                 err = split_state(tree, state, prealloc, end + 1);
 870                 BUG_ON(err == -EEXIST);
 871
 872                 set_state_bits(tree, prealloc, &bits);
 873                 cache_state(prealloc, cached_state);
 874                 merge_state(tree, prealloc);
 875                 prealloc = NULL;
 876                 goto out;
 877         }
 878
 879         goto search_again;
 880
 881 out:
 882         spin_unlock(&tree->lock);
 883         if (prealloc)
 884                 free_extent_state(prealloc);
 885
 886         return err;
 887
 888 search_again:
 889         if (start > end)
 890                 goto out;
 891         spin_unlock(&tree->lock);
 892         if (mask & __GFP_WAIT)
 893                 cond_resched();
 894         goto again;
 895 }
 896
 897 /**
 898  * convert_extent - convert all bits in a given range from one bit to another
 899  * @tree:       the io tree to search
 900  * @start:      the start offset in bytes
 901  * @end:        the end offset in bytes (inclusive)
 902  * @bits:       the bits to set in this range
 903  * @clear_bits: the bits to clear in this range
 904  * @mask:       the allocation mask
 905  *
 906  * This will go through and set bits for the given range.  If any states exist
 907  * already in this range they are set with the given bit and cleared of the
 908  * clear_bits.  This is only meant to be used by things that are mergeable, ie
 909  * converting from say DELALLOC to DIRTY.  This is not meant to be used with
 910  * boundary bits like LOCK.
 911  */
 912 int convert_extent_bit(struct extent_io_tree *tree, u64 start, u64 end,
 913                        int bits, int clear_bits, gfp_t mask)
 914 {
 915         struct extent_state *state;
 916         struct extent_state *prealloc = NULL;
 917         struct rb_node *node;
 918         int err = 0;
 919         u64 last_start;
 920         u64 last_end;
 921
 922 again:
 923         if (!prealloc && (mask & __GFP_WAIT)) {
 924                 prealloc = alloc_extent_state(mask);
 925                 if (!prealloc)
 926                         return -ENOMEM;
 927         }
 928
 929         spin_lock(&tree->lock);
 930         /*
 931          * this search will find all the extents that end after
 932          * our range starts.
 933          */
 934         node = tree_search(tree, start);
 935         if (!node) {
 936                 prealloc = alloc_extent_state_atomic(prealloc);
 937                 if (!prealloc)
 938                         return -ENOMEM;
 939                 err = insert_state(tree, prealloc, start, end, &bits);
 940                 prealloc = NULL;
 941                 BUG_ON(err == -EEXIST);
 942                 goto out;
 943         }
 944         state = rb_entry(node, struct extent_state, rb_node);
 945 hit_next:
 946         last_start = state->start;
 947         last_end = state->end;
 948
 949         /*
 950          * | ---- desired range ---- |
 951          * | state |
 952          *
 953          * Just lock what we found and keep going
 954          */
 955         if (state->start == start && state->end <= end) {
 956                 struct rb_node *next_node;
 957
 958                 set_state_bits(tree, state, &bits);
 959                 clear_state_bit(tree, state, &clear_bits, 0);
 960
 961                 merge_state(tree, state);
 962                 if (last_end == (u64)-1)
 963                         goto out;
 964
 965                 start = last_end + 1;
 966                 next_node = rb_next(&state->rb_node);
 967                 if (next_node && start < end && prealloc && !need_resched()) {
 968                         state = rb_entry(next_node, struct extent_state,
 969                                          rb_node);
 970                         if (state->start == start)
 971                                 goto hit_next;
 972                 }
 973                 goto search_again;
 974         }
 975
 976         /*
 977          *     | ---- desired range ---- |
 978          * | state |
 979          *   or
 980          * | ------------- state -------------- |
 981          *
 982          * We need to split the extent we found, and may flip bits on
 983          * second half.
 984          *
 985          * If the extent we found extends past our
 986          * range, we just split and search again.  It'll get split
 987          * again the next time though.
 988          *
 989          * If the extent we found is inside our range, we set the
 990          * desired bit on it.
 991          */
 992         if (state->start < start) {
 993                 prealloc = alloc_extent_state_atomic(prealloc);
 994                 if (!prealloc)
 995                         return -ENOMEM;
 996                 err = split_state(tree, state, prealloc, start);
 997                 BUG_ON(err == -EEXIST);
 998                 prealloc = NULL;
 999                 if (err)
1000                         goto out;
1001                 if (state->end <= end) {
1002                         set_state_bits(tree, state, &bits);
1003                         clear_state_bit(tree, state, &clear_bits, 0);
1004                         merge_state(tree, state);
1005                         if (last_end == (u64)-1)
1006                                 goto out;
1007                         start = last_end + 1;
1008                 }
1009                 goto search_again;
1010         }
1011         /*
1012          * | ---- desired range ---- |
1013          *     | state | or               | state |
1014          *
1015          * There's a hole, we need to insert something in it and
1016          * ignore the extent we found.
1017          */
1018         if (state->start > start) {
1019                 u64 this_end;
1020                 if (end < last_start)
1021                         this_end = end;
1022                 else
1023                         this_end = last_start - 1;
1024
1025                 prealloc = alloc_extent_state_atomic(prealloc);
1026                 if (!prealloc)
1027                         return -ENOMEM;
1028
1029                 /*
1030                  * Avoid to free 'prealloc' if it can be merged with
1031                  * the later extent.
1032                  */
1033                 err = insert_state(tree, prealloc, start, this_end,
1034                                    &bits);
1035                 BUG_ON(err == -EEXIST);
1036                 if (err) {
1037                         free_extent_state(prealloc);
1038                         prealloc = NULL;
1039                         goto out;
1040                 }
1041                 prealloc = NULL;
1042                 start = this_end + 1;
1043                 goto search_again;
1044         }
1045         /*
1046          * | ---- desired range ---- |
1047          *                        | state |
1048          * We need to split the extent, and set the bit
1049          * on the first half
1050          */
1051         if (state->start <= end && state->end > end) {
1052                 prealloc = alloc_extent_state_atomic(prealloc);
1053                 if (!prealloc)
1054                         return -ENOMEM;
1055
1056                 err = split_state(tree, state, prealloc, end + 1);
1057                 BUG_ON(err == -EEXIST);
1058
1059                 set_state_bits(tree, prealloc, &bits);
1060                 clear_state_bit(tree, prealloc, &clear_bits, 0);
1061
1062                 merge_state(tree, prealloc);
1063                 prealloc = NULL;
1064                 goto out;
1065         }
1066
1067         goto search_again;
1068
1069 out:
1070         spin_unlock(&tree->lock);
1071         if (prealloc)
1072                 free_extent_state(prealloc);
1073
1074         return err;
1075
1076 search_again:
1077         if (start > end)
1078                 goto out;
1079         spin_unlock(&tree->lock);
1080         if (mask & __GFP_WAIT)
1081                 cond_resched();
1082         goto again;
1083 }
1084
1085 /* wrappers around set/clear extent bit */
1086 int set_extent_dirty(struct extent_io_tree *tree, u64 start, u64 end,
1087                      gfp_t mask)
1088 {
1089         return set_extent_bit(tree, start, end, EXTENT_DIRTY, 0, NULL,
1090                               NULL, mask);
1091 }
1092
1093 int set_extent_bits(struct extent_io_tree *tree, u64 start, u64 end,
1094                     int bits, gfp_t mask)
1095 {
1096         return set_extent_bit(tree, start, end, bits, 0, NULL,
1097                               NULL, mask);
1098 }
1099
1100 int clear_extent_bits(struct extent_io_tree *tree, u64 start, u64 end,
1101                       int bits, gfp_t mask)
1102 {
1103         return clear_extent_bit(tree, start, end, bits, 0, 0, NULL, mask);
1104 }
1105
1106 int set_extent_delalloc(struct extent_io_tree *tree, u64 start, u64 end,
1107                         struct extent_state **cached_state, gfp_t mask)
1108 {
1109         return set_extent_bit(tree, start, end,
1110                               EXTENT_DELALLOC | EXTENT_UPTODATE,
1111                               0, NULL, cached_state, mask);
1112 }
1113
1114 int clear_extent_dirty(struct extent_io_tree *tree, u64 start, u64 end,
1115                        gfp_t mask)
1116 {
1117         return clear_extent_bit(tree, start, end,
1118                                 EXTENT_DIRTY | EXTENT_DELALLOC |
1119                                 EXTENT_DO_ACCOUNTING, 0, 0, NULL, mask);
1120 }
1121
1122 int set_extent_new(struct extent_io_tree *tree, u64 start, u64 end,
1123                      gfp_t mask)
1124 {
1125         return set_extent_bit(tree, start, end, EXTENT_NEW, 0, NULL,
1126                               NULL, mask);
1127 }
1128
1129 int set_extent_uptodate(struct extent_io_tree *tree, u64 start, u64 end,
1130                         struct extent_state **cached_state, gfp_t mask)
1131 {
1132         return set_extent_bit(tree, start, end, EXTENT_UPTODATE, 0,
1133                               NULL, cached_state, mask);
1134 }
1135
1136 static int clear_extent_uptodate(struct extent_io_tree *tree, u64 start,
1137                                  u64 end, struct extent_state **cached_state,
1138                                  gfp_t mask)
1139 {
1140         return clear_extent_bit(tree, start, end, EXTENT_UPTODATE, 0, 0,
1141                                 cached_state, mask);
1142 }
1143
1144 /*
1145  * either insert or lock state struct between start and end use mask to tell
1146  * us if waiting is desired.
1147  */
1148 int lock_extent_bits(struct extent_io_tree *tree, u64 start, u64 end,
1149                      int bits, struct extent_state **cached_state, gfp_t mask)
1150 {
1151         int err;
1152         u64 failed_start;
1153         while (1) {
1154                 err = set_extent_bit(tree, start, end, EXTENT_LOCKED | bits,
1155                                      EXTENT_LOCKED, &failed_start,
1156                                      cached_state, mask);
1157                 if (err == -EEXIST && (mask & __GFP_WAIT)) {
1158                         wait_extent_bit(tree, failed_start, end, EXTENT_LOCKED);
1159                         start = failed_start;
1160                 } else {
1161                         break;
1162                 }
1163                 WARN_ON(start > end);
1164         }
1165         return err;
1166 }
1167
1168 int lock_extent(struct extent_io_tree *tree, u64 start, u64 end, gfp_t mask)
1169 {
1170         return lock_extent_bits(tree, start, end, 0, NULL, mask);
1171 }
1172
1173 int try_lock_extent(struct extent_io_tree *tree, u64 start, u64 end,
1174                     gfp_t mask)
1175 {
1176         int err;
1177         u64 failed_start;
1178
1179         err = set_extent_bit(tree, start, end, EXTENT_LOCKED, EXTENT_LOCKED,
1180                              &failed_start, NULL, mask);
1181         if (err == -EEXIST) {
1182                 if (failed_start > start)
1183                         clear_extent_bit(tree, start, failed_start - 1,
1184                                          EXTENT_LOCKED, 1, 0, NULL, mask);
1185                 return 0;
1186         }
1187         return 1;
1188 }
1189
1190 int unlock_extent_cached(struct extent_io_tree *tree, u64 start, u64 end,
1191                          struct extent_state **cached, gfp_t mask)
1192 {
1193         return clear_extent_bit(tree, start, end, EXTENT_LOCKED, 1, 0, cached,
1194                                 mask);
1195 }
1196
1197 int unlock_extent(struct extent_io_tree *tree, u64 start, u64 end, gfp_t mask)
1198 {
1199         return clear_extent_bit(tree, start, end, EXTENT_LOCKED, 1, 0, NULL,
1200                                 mask);
1201 }
1202
1203 /*
1204  * helper function to set both pages and extents in the tree writeback
1205  */
1206 static int set_range_writeback(struct extent_io_tree *tree, u64 start, u64 end)
1207 {
1208         unsigned long index = start >> PAGE_CACHE_SHIFT;
1209         unsigned long end_index = end >> PAGE_CACHE_SHIFT;
1210         struct page *page;
1211
1212         while (index <= end_index) {
1213                 page = find_get_page(tree->mapping, index);
1214                 BUG_ON(!page);
1215                 set_page_writeback(page);
1216                 page_cache_release(page);
1217                 index++;
1218         }
1219         return 0;
1220 }
1221
1222 /* find the first state struct with 'bits' set after 'start', and
1223  * return it.  tree->lock must be held.  NULL will returned if
1224  * nothing was found after 'start'
1225  */
1226 struct extent_state *find_first_extent_bit_state(struct extent_io_tree *tree,
1227                                                  u64 start, int bits)
1228 {
1229         struct rb_node *node;
1230         struct extent_state *state;
1231
1232         /*
1233          * this search will find all the extents that end after
1234          * our range starts.
1235          */
1236         node = tree_search(tree, start);
1237         if (!node)
1238                 goto out;
1239
1240         while (1) {
1241                 state = rb_entry(node, struct extent_state, rb_node);
1242                 if (state->end >= start && (state->state & bits))
1243                         return state;
1244
1245                 node = rb_next(node);
1246                 if (!node)
1247                         break;
1248         }
1249 out:
1250         return NULL;
1251 }
1252
1253 /*
1254  * find the first offset in the io tree with 'bits' set. zero is
1255  * returned if we find something, and *start_ret and *end_ret are
1256  * set to reflect the state struct that was found.
1257  *
1258  * If nothing was found, 1 is returned, < 0 on error
1259  */
1260 int find_first_extent_bit(struct extent_io_tree *tree, u64 start,
1261                           u64 *start_ret, u64 *end_ret, int bits)
1262 {
1263         struct extent_state *state;
1264         int ret = 1;
1265
1266         spin_lock(&tree->lock);
1267         state = find_first_extent_bit_state(tree, start, bits);
1268         if (state) {
1269                 *start_ret = state->start;
1270                 *end_ret = state->end;
1271                 ret = 0;
1272         }
1273         spin_unlock(&tree->lock);
1274         return ret;
1275 }
1276
1277 /*
1278  * find a contiguous range of bytes in the file marked as delalloc, not
1279  * more than 'max_bytes'.  start and end are used to return the range,
1280  *
1281  * 1 is returned if we find something, 0 if nothing was in the tree
1282  */
1283 static noinline u64 find_delalloc_range(struct extent_io_tree *tree,
1284                                         u64 *start, u64 *end, u64 max_bytes,
1285                                         struct extent_state **cached_state)
1286 {
1287         struct rb_node *node;
1288         struct extent_state *state;
1289         u64 cur_start = *start;
1290         u64 found = 0;
1291         u64 total_bytes = 0;
1292
1293         spin_lock(&tree->lock);
1294
1295         /*
1296          * this search will find all the extents that end after
1297          * our range starts.
1298          */
1299         node = tree_search(tree, cur_start);
1300         if (!node) {
1301                 if (!found)
1302                         *end = (u64)-1;
1303                 goto out;
1304         }
1305
1306         while (1) {
1307                 state = rb_entry(node, struct extent_state, rb_node);
1308                 if (found && (state->start != cur_start ||
1309                               (state->state & EXTENT_BOUNDARY))) {
1310                         goto out;
1311                 }
1312                 if (!(state->state & EXTENT_DELALLOC)) {
1313                         if (!found)
1314                                 *end = state->end;
1315                         goto out;
1316                 }
1317                 if (!found) {
1318                         *start = state->start;
1319                         *cached_state = state;
1320                         atomic_inc(&state->refs);
1321                 }
1322                 found++;
1323                 *end = state->end;
1324                 cur_start = state->end + 1;
1325                 node = rb_next(node);
1326                 if (!node)
1327                         break;
1328                 total_bytes += state->end - state->start + 1;
1329                 if (total_bytes >= max_bytes)
1330                         break;
1331         }
1332 out:
1333         spin_unlock(&tree->lock);
1334         return found;
1335 }
1336
1337 static noinline int __unlock_for_delalloc(struct inode *inode,
1338                                           struct page *locked_page,
1339                                           u64 start, u64 end)
1340 {
1341         int ret;
1342         struct page *pages[16];
1343         unsigned long index = start >> PAGE_CACHE_SHIFT;
1344         unsigned long end_index = end >> PAGE_CACHE_SHIFT;
1345         unsigned long nr_pages = end_index - index + 1;
1346         int i;
1347
1348         if (index == locked_page->index && end_index == index)
1349                 return 0;
1350
1351         while (nr_pages > 0) {
1352                 ret = find_get_pages_contig(inode->i_mapping, index,
1353                                      min_t(unsigned long, nr_pages,
1354                                      ARRAY_SIZE(pages)), pages);
1355                 for (i = 0; i < ret; i++) {
1356                         if (pages[i] != locked_page)
1357                                 unlock_page(pages[i]);
1358                         page_cache_release(pages[i]);
1359                 }
1360                 nr_pages -= ret;
1361                 index += ret;
1362                 cond_resched();
1363         }
1364         return 0;
1365 }
1366
1367 static noinline int lock_delalloc_pages(struct inode *inode,
1368                                         struct page *locked_page,
1369                                         u64 delalloc_start,
1370                                         u64 delalloc_end)
1371 {
1372         unsigned long index = delalloc_start >> PAGE_CACHE_SHIFT;
1373         unsigned long start_index = index;
1374         unsigned long end_index = delalloc_end >> PAGE_CACHE_SHIFT;
1375         unsigned long pages_locked = 0;
1376         struct page *pages[16];
1377         unsigned long nrpages;
1378         int ret;
1379         int i;
1380
1381         /* the caller is responsible for locking the start index */
1382         if (index == locked_page->index && index == end_index)
1383                 return 0;
1384
1385         /* skip the page at the start index */
1386         nrpages = end_index - index + 1;
1387         while (nrpages > 0) {
1388                 ret = find_get_pages_contig(inode->i_mapping, index,
1389                                      min_t(unsigned long,
1390                                      nrpages, ARRAY_SIZE(pages)), pages);
1391                 if (ret == 0) {
1392                         ret = -EAGAIN;
1393                         goto done;
1394                 }
1395                 /* now we have an array of pages, lock them all */
1396                 for (i = 0; i < ret; i++) {
1397                         /*
1398                          * the caller is taking responsibility for
1399                          * locked_page
1400                          */
1401                         if (pages[i] != locked_page) {
1402                                 lock_page(pages[i]);
1403                                 if (!PageDirty(pages[i]) ||
1404                                     pages[i]->mapping != inode->i_mapping) {
1405                                         ret = -EAGAIN;
1406                                         unlock_page(pages[i]);
1407                                         page_cache_release(pages[i]);
1408                                         goto done;
1409                                 }
1410                         }
1411                         page_cache_release(pages[i]);
1412                         pages_locked++;
1413                 }
1414                 nrpages -= ret;
1415                 index += ret;
1416                 cond_resched();
1417         }
1418         ret = 0;
1419 done:
1420         if (ret && pages_locked) {
1421                 __unlock_for_delalloc(inode, locked_page,
1422                               delalloc_start,
1423                               ((u64)(start_index + pages_locked - 1)) <<
1424                               PAGE_CACHE_SHIFT);
1425         }
1426         return ret;
1427 }
1428
1429 /*
1430  * find a contiguous range of bytes in the file marked as delalloc, not
1431  * more than 'max_bytes'.  start and end are used to return the range,
1432  *
1433  * 1 is returned if we find something, 0 if nothing was in the tree
1434  */
1435 static noinline u64 find_lock_delalloc_range(struct inode *inode,
1436                                              struct extent_io_tree *tree,
1437                                              struct page *locked_page,
1438                                              u64 *start, u64 *end,
1439                                              u64 max_bytes)
1440 {
1441         u64 delalloc_start;
1442         u64 delalloc_end;
1443         u64 found;
1444         struct extent_state *cached_state = NULL;
1445         int ret;
1446         int loops = 0;
1447
1448 again:
1449         /* step one, find a bunch of delalloc bytes starting at start */
1450         delalloc_start = *start;
1451         delalloc_end = 0;
1452         found = find_delalloc_range(tree, &delalloc_start, &delalloc_end,
1453                                     max_bytes, &cached_state);
1454         if (!found || delalloc_end <= *start) {
1455                 *start = delalloc_start;
1456                 *end = delalloc_end;
1457                 free_extent_state(cached_state);
1458                 return found;
1459         }
1460
1461         /*
1462          * start comes from the offset of locked_page.  We have to lock
1463          * pages in order, so we can't process delalloc bytes before
1464          * locked_page
1465          */
1466         if (delalloc_start < *start)
1467                 delalloc_start = *start;
1468
1469         /*
1470          * make sure to limit the number of pages we try to lock down
1471          * if we're looping.
1472          */
1473         if (delalloc_end + 1 - delalloc_start > max_bytes && loops)
1474                 delalloc_end = delalloc_start + PAGE_CACHE_SIZE - 1;
1475
1476         /* step two, lock all the pages after the page that has start */
1477         ret = lock_delalloc_pages(inode, locked_page,
1478                                   delalloc_start, delalloc_end);
1479         if (ret == -EAGAIN) {
1480                 /* some of the pages are gone, lets avoid looping by
1481                  * shortening the size of the delalloc range we're searching
1482                  */
1483                 free_extent_state(cached_state);
1484                 if (!loops) {
1485                         unsigned long offset = (*start) & (PAGE_CACHE_SIZE - 1);
1486                         max_bytes = PAGE_CACHE_SIZE - offset;
1487                         loops = 1;
1488                         goto again;
1489                 } else {
1490                         found = 0;
1491                         goto out_failed;
1492                 }
1493         }
1494         BUG_ON(ret);
1495
1496         /* step three, lock the state bits for the whole range */
1497         lock_extent_bits(tree, delalloc_start, delalloc_end,
1498                          0, &cached_state, GFP_NOFS);
1499
1500         /* then test to make sure it is all still delalloc */
1501         ret = test_range_bit(tree, delalloc_start, delalloc_end,
1502                              EXTENT_DELALLOC, 1, cached_state);
1503         if (!ret) {
1504                 unlock_extent_cached(tree, delalloc_start, delalloc_end,
1505                                      &cached_state, GFP_NOFS);
1506                 __unlock_for_delalloc(inode, locked_page,
1507                               delalloc_start, delalloc_end);
1508                 cond_resched();
1509                 goto again;
1510         }
1511         free_extent_state(cached_state);
1512         *start = delalloc_start;
1513         *end = delalloc_end;
1514 out_failed:
1515         return found;
1516 }
1517
1518 int extent_clear_unlock_delalloc(struct inode *inode,
1519                                 struct extent_io_tree *tree,
1520                                 u64 start, u64 end, struct page *locked_page,
1521                                 unsigned long op)
1522 {
1523         int ret;
1524         struct page *pages[16];
1525         unsigned long index = start >> PAGE_CACHE_SHIFT;
1526         unsigned long end_index = end >> PAGE_CACHE_SHIFT;
1527         unsigned long nr_pages = end_index - index + 1;
1528         int i;
1529         int clear_bits = 0;
1530
1531         if (op & EXTENT_CLEAR_UNLOCK)
1532                 clear_bits |= EXTENT_LOCKED;
1533         if (op & EXTENT_CLEAR_DIRTY)
1534                 clear_bits |= EXTENT_DIRTY;
1535
1536         if (op & EXTENT_CLEAR_DELALLOC)
1537                 clear_bits |= EXTENT_DELALLOC;
1538
1539         clear_extent_bit(tree, start, end, clear_bits, 1, 0, NULL, GFP_NOFS);
1540         if (!(op & (EXTENT_CLEAR_UNLOCK_PAGE | EXTENT_CLEAR_DIRTY |
1541                     EXTENT_SET_WRITEBACK | EXTENT_END_WRITEBACK |
1542                     EXTENT_SET_PRIVATE2)))
1543                 return 0;
1544
1545         while (nr_pages > 0) {
1546                 ret = find_get_pages_contig(inode->i_mapping, index,
1547                                      min_t(unsigned long,
1548                                      nr_pages, ARRAY_SIZE(pages)), pages);
1549                 for (i = 0; i < ret; i++) {
1550
1551                         if (op & EXTENT_SET_PRIVATE2)
1552                                 SetPagePrivate2(pages[i]);
1553
1554                         if (pages[i] == locked_page) {
1555                                 page_cache_release(pages[i]);
1556                                 continue;
1557                         }
1558                         if (op & EXTENT_CLEAR_DIRTY)
1559                                 clear_page_dirty_for_io(pages[i]);
1560                         if (op & EXTENT_SET_WRITEBACK)
1561                                 set_page_writeback(pages[i]);
1562                         if (op & EXTENT_END_WRITEBACK)
1563                                 end_page_writeback(pages[i]);
1564                         if (op & EXTENT_CLEAR_UNLOCK_PAGE)
1565                                 unlock_page(pages[i]);
1566                         page_cache_release(pages[i]);
1567                 }
1568                 nr_pages -= ret;
1569                 index += ret;
1570                 cond_resched();
1571         }
1572         return 0;
1573 }
1574
1575 /*
1576  * count the number of bytes in the tree that have a given bit(s)
1577  * set.  This can be fairly slow, except for EXTENT_DIRTY which is
1578  * cached.  The total number found is returned.
1579  */
1580 u64 count_range_bits(struct extent_io_tree *tree,
1581                      u64 *start, u64 search_end, u64 max_bytes,
1582                      unsigned long bits, int contig)
1583 {
1584         struct rb_node *node;
1585         struct extent_state *state;
1586         u64 cur_start = *start;
1587         u64 total_bytes = 0;
1588         u64 last = 0;
1589         int found = 0;
1590
1591         if (search_end <= cur_start) {
1592                 WARN_ON(1);
1593                 return 0;
1594         }
1595
1596         spin_lock(&tree->lock);
1597         if (cur_start == 0 && bits == EXTENT_DIRTY) {
1598                 total_bytes = tree->dirty_bytes;
1599                 goto out;
1600         }
1601         /*
1602          * this search will find all the extents that end after
1603          * our range starts.
1604          */
1605         node = tree_search(tree, cur_start);
1606         if (!node)
1607                 goto out;
1608
1609         while (1) {
1610                 state = rb_entry(node, struct extent_state, rb_node);
1611                 if (state->start > search_end)
1612                         break;
1613                 if (contig && found && state->start > last + 1)
1614                         break;
1615                 if (state->end >= cur_start && (state->state & bits) == bits) {
1616                         total_bytes += min(search_end, state->end) + 1 -
1617                                        max(cur_start, state->start);
1618                         if (total_bytes >= max_bytes)
1619                                 break;
1620                         if (!found) {
1621                                 *start = max(cur_start, state->start);
1622                                 found = 1;
1623                         }
1624                         last = state->end;
1625                 } else if (contig && found) {
1626                         break;
1627                 }
1628                 node = rb_next(node);
1629                 if (!node)
1630                         break;
1631         }
1632 out:
1633         spin_unlock(&tree->lock);
1634         return total_bytes;
1635 }
1636
1637 /*
1638  * set the private field for a given byte offset in the tree.  If there isn't
1639  * an extent_state there already, this does nothing.
1640  */
1641 int set_state_private(struct extent_io_tree *tree, u64 start, u64 private)
1642 {
1643         struct rb_node *node;
1644         struct extent_state *state;
1645         int ret = 0;
1646
1647         spin_lock(&tree->lock);
1648         /*
1649          * this search will find all the extents that end after
1650          * our range starts.
1651          */
1652         node = tree_search(tree, start);
1653         if (!node) {
1654                 ret = -ENOENT;
1655                 goto out;
1656         }
1657         state = rb_entry(node, struct extent_state, rb_node);
1658         if (state->start != start) {
1659                 ret = -ENOENT;
1660                 goto out;
1661         }
1662         state->private = private;
1663 out:
1664         spin_unlock(&tree->lock);
1665         return ret;
1666 }
1667
1668 int get_state_private(struct extent_io_tree *tree, u64 start, u64 *private)
1669 {
1670         struct rb_node *node;
1671         struct extent_state *state;
1672         int ret = 0;
1673
1674         spin_lock(&tree->lock);
1675         /*
1676          * this search will find all the extents that end after
1677          * our range starts.
1678          */
1679         node = tree_search(tree, start);
1680         if (!node) {
1681                 ret = -ENOENT;
1682                 goto out;
1683         }
1684         state = rb_entry(node, struct extent_state, rb_node);
1685         if (state->start != start) {
1686                 ret = -ENOENT;
1687                 goto out;
1688         }
1689         *private = state->private;
1690 out:
1691         spin_unlock(&tree->lock);
1692         return ret;
1693 }
1694
1695 /*
1696  * searches a range in the state tree for a given mask.
1697  * If 'filled' == 1, this returns 1 only if every extent in the tree
1698  * has the bits set.  Otherwise, 1 is returned if any bit in the
1699  * range is found set.
1700  */
1701 int test_range_bit(struct extent_io_tree *tree, u64 start, u64 end,
1702                    int bits, int filled, struct extent_state *cached)
1703 {
1704         struct extent_state *state = NULL;
1705         struct rb_node *node;
1706         int bitset = 0;
1707
1708         spin_lock(&tree->lock);
1709         if (cached && cached->tree && cached->start <= start &&
1710             cached->end > start)
1711                 node = &cached->rb_node;
1712         else
1713                 node = tree_search(tree, start);
1714         while (node && start <= end) {
1715                 state = rb_entry(node, struct extent_state, rb_node);
1716
1717                 if (filled && state->start > start) {
1718                         bitset = 0;
1719                         break;
1720                 }
1721
1722                 if (state->start > end)
1723                         break;
1724
1725                 if (state->state & bits) {
1726                         bitset = 1;
1727                         if (!filled)
1728                                 break;
1729                 } else if (filled) {
1730                         bitset = 0;
1731                         break;
1732                 }
1733
1734                 if (state->end == (u64)-1)
1735                         break;
1736
1737                 start = state->end + 1;
1738                 if (start > end)
1739                         break;
1740                 node = rb_next(node);
1741                 if (!node) {
1742                         if (filled)
1743                                 bitset = 0;
1744                         break;
1745                 }
1746         }
1747         spin_unlock(&tree->lock);
1748         return bitset;
1749 }
1750
1751 /*
1752  * helper function to set a given page up to date if all the
1753  * extents in the tree for that page are up to date
1754  */
1755 static int check_page_uptodate(struct extent_io_tree *tree,
1756                                struct page *page)
1757 {
1758         u64 start = (u64)page->index << PAGE_CACHE_SHIFT;
1759         u64 end = start + PAGE_CACHE_SIZE - 1;
1760         if (test_range_bit(tree, start, end, EXTENT_UPTODATE, 1, NULL))
1761                 SetPageUptodate(page);
1762         return 0;
1763 }
1764
1765 /*
1766  * helper function to unlock a page if all the extents in the tree
1767  * for that page are unlocked
1768  */
1769 static int check_page_locked(struct extent_io_tree *tree,
1770                              struct page *page)
1771 {
1772         u64 start = (u64)page->index << PAGE_CACHE_SHIFT;
1773         u64 end = start + PAGE_CACHE_SIZE - 1;
1774         if (!test_range_bit(tree, start, end, EXTENT_LOCKED, 0, NULL))
1775                 unlock_page(page);
1776         return 0;
1777 }
1778
1779 /*
1780  * helper function to end page writeback if all the extents
1781  * in the tree for that page are done with writeback
1782  */
1783 static int check_page_writeback(struct extent_io_tree *tree,
1784                              struct page *page)
1785 {
1786         end_page_writeback(page);
1787         return 0;
1788 }
1789
1790 /* lots and lots of room for performance fixes in the end_bio funcs */
1791
1792 /*
1793  * after a writepage IO is done, we need to:
1794  * clear the uptodate bits on error
1795  * clear the writeback bits in the extent tree for this IO
1796  * end_page_writeback if the page has no more pending IO
1797  *
1798  * Scheduling is not allowed, so the extent state tree is expected
1799  * to have one and only one object corresponding to this IO.
1800  */
1801 static void end_bio_extent_writepage(struct bio *bio, int err)
1802 {
1803         int uptodate = err == 0;
1804         struct bio_vec *bvec = bio->bi_io_vec + bio->bi_vcnt - 1;
1805         struct extent_io_tree *tree;
1806         u64 start;
1807         u64 end;
1808         int whole_page;
1809         int ret;
1810
1811         do {
1812                 struct page *page = bvec->bv_page;
1813                 tree = &BTRFS_I(page->mapping->host)->io_tree;
1814
1815                 start = ((u64)page->index << PAGE_CACHE_SHIFT) +
1816                          bvec->bv_offset;
1817                 end = start + bvec->bv_len - 1;
1818
1819                 if (bvec->bv_offset == 0 && bvec->bv_len == PAGE_CACHE_SIZE)
1820                         whole_page = 1;
1821                 else
1822                         whole_page = 0;
1823
1824                 if (--bvec >= bio->bi_io_vec)
1825                         prefetchw(&bvec->bv_page->flags);
1826                 if (tree->ops && tree->ops->writepage_end_io_hook) {
1827                         ret = tree->ops->writepage_end_io_hook(page, start,
1828                                                        end, NULL, uptodate);
1829                         if (ret)
1830                                 uptodate = 0;
1831                 }
1832
1833                 if (!uptodate && tree->ops &&
1834                     tree->ops->writepage_io_failed_hook) {
1835                         ret = tree->ops->writepage_io_failed_hook(bio, page,
1836                                                          start, end, NULL);
1837                         if (ret == 0) {
1838                                 uptodate = (err == 0);
1839                                 continue;
1840                         }
1841                 }
1842
1843                 if (!uptodate) {
1844                         clear_extent_uptodate(tree, start, end, NULL, GFP_NOFS);
1845                         ClearPageUptodate(page);
1846                         SetPageError(page);
1847                 }
1848
1849                 if (whole_page)
1850                         end_page_writeback(page);
1851                 else
1852                         check_page_writeback(tree, page);
1853         } while (bvec >= bio->bi_io_vec);
1854
1855         bio_put(bio);
1856 }
1857
1858 /*
1859  * after a readpage IO is done, we need to:
1860  * clear the uptodate bits on error
1861  * set the uptodate bits if things worked
1862  * set the page up to date if all extents in the tree are uptodate
1863  * clear the lock bit in the extent tree
1864  * unlock the page if there are no other extents locked for it
1865  *
1866  * Scheduling is not allowed, so the extent state tree is expected
1867  * to have one and only one object corresponding to this IO.
1868  */
1869 static void end_bio_extent_readpage(struct bio *bio, int err)
1870 {
1871         int uptodate = test_bit(BIO_UPTODATE, &bio->bi_flags);
1872         struct bio_vec *bvec_end = bio->bi_io_vec + bio->bi_vcnt - 1;
1873         struct bio_vec *bvec = bio->bi_io_vec;
1874         struct extent_io_tree *tree;
1875         u64 start;
1876         u64 end;
1877         int whole_page;
1878         int ret;
1879
1880         if (err)
1881                 uptodate = 0;
1882
1883         do {
1884                 struct page *page = bvec->bv_page;
1885                 struct extent_state *cached = NULL;
1886                 struct extent_state *state;
1887
1888                 tree = &BTRFS_I(page->mapping->host)->io_tree;
1889
1890                 start = ((u64)page->index << PAGE_CACHE_SHIFT) +
1891                         bvec->bv_offset;
1892                 end = start + bvec->bv_len - 1;
1893
1894                 if (bvec->bv_offset == 0 && bvec->bv_len == PAGE_CACHE_SIZE)
1895                         whole_page = 1;
1896                 else
1897                         whole_page = 0;
1898
1899                 if (++bvec <= bvec_end)
1900                         prefetchw(&bvec->bv_page->flags);
1901
1902                 spin_lock(&tree->lock);
1903                 state = find_first_extent_bit_state(tree, start, EXTENT_LOCKED);
1904                 if (state && state->start == start) {
1905                         /*
1906                          * take a reference on the state, unlock will drop
1907                          * the ref
1908                          */
1909                         cache_state(state, &cached);
1910                 }
1911                 spin_unlock(&tree->lock);
1912
1913                 if (uptodate && tree->ops && tree->ops->readpage_end_io_hook) {
1914                         ret = tree->ops->readpage_end_io_hook(page, start, end,
1915                                                               state);
1916                         if (ret)
1917                                 uptodate = 0;
1918                 }
1919                 if (!uptodate && tree->ops &&
1920                     tree->ops->readpage_io_failed_hook) {
1921                         ret = tree->ops->readpage_io_failed_hook(bio, page,
1922                                                          start, end, NULL);
1923                         if (ret == 0) {
1924                                 uptodate =
1925                                         test_bit(BIO_UPTODATE, &bio->bi_flags);
1926                                 if (err)
1927                                         uptodate = 0;
1928                                 uncache_state(&cached);
1929                                 continue;
1930                         }
1931                 }
1932
1933                 if (uptodate) {
1934                         set_extent_uptodate(tree, start, end, &cached,
1935                                             GFP_ATOMIC);
1936                 }
1937                 unlock_extent_cached(tree, start, end, &cached, GFP_ATOMIC);
1938
1939                 if (whole_page) {
1940                         if (uptodate) {
1941                                 SetPageUptodate(page);
1942                         } else {
1943                                 ClearPageUptodate(page);
1944                                 SetPageError(page);
1945                         }
1946                         unlock_page(page);
1947                 } else {
1948                         if (uptodate) {
1949                                 check_page_uptodate(tree, page);
1950                         } else {
1951                                 ClearPageUptodate(page);
1952                                 SetPageError(page);
1953                         }
1954                         check_page_locked(tree, page);
1955                 }
1956         } while (bvec <= bvec_end);
1957
1958         bio_put(bio);
1959 }
1960
1961 struct bio *
1962 btrfs_bio_alloc(struct block_device *bdev, u64 first_sector, int nr_vecs,
1963                 gfp_t gfp_flags)
1964 {
1965         struct bio *bio;
1966
1967         bio = bio_alloc(gfp_flags, nr_vecs);
1968
1969         if (bio == NULL && (current->flags & PF_MEMALLOC)) {
1970                 while (!bio && (nr_vecs /= 2))
1971                         bio = bio_alloc(gfp_flags, nr_vecs);
1972         }
1973
1974         if (bio) {
1975                 bio->bi_size = 0;
1976                 bio->bi_bdev = bdev;
1977                 bio->bi_sector = first_sector;
1978         }
1979         return bio;
1980 }
1981
1982 static int submit_one_bio(int rw, struct bio *bio, int mirror_num,
1983                           unsigned long bio_flags)
1984 {
1985         int ret = 0;
1986         struct bio_vec *bvec = bio->bi_io_vec + bio->bi_vcnt - 1;
1987         struct page *page = bvec->bv_page;
1988         struct extent_io_tree *tree = bio->bi_private;
1989         u64 start;
1990
1991         start = ((u64)page->index << PAGE_CACHE_SHIFT) + bvec->bv_offset;
1992
1993         bio->bi_private = NULL;
1994
1995         bio_get(bio);
1996
1997         if (tree->ops && tree->ops->submit_bio_hook)
1998                 ret = tree->ops->submit_bio_hook(page->mapping->host, rw, bio,
1999                                            mirror_num, bio_flags, start);
2000         else
2001                 submit_bio(rw, bio);
2002         if (bio_flagged(bio, BIO_EOPNOTSUPP))
2003                 ret = -EOPNOTSUPP;
2004         bio_put(bio);
2005         return ret;
2006 }
2007
2008 static int submit_extent_page(int rw, struct extent_io_tree *tree,
2009                               struct page *page, sector_t sector,
2010                               size_t size, unsigned long offset,
2011                               struct block_device *bdev,
2012                               struct bio **bio_ret,
2013                               unsigned long max_pages,
2014                               bio_end_io_t end_io_func,
2015                               int mirror_num,
2016                               unsigned long prev_bio_flags,
2017                               unsigned long bio_flags)
2018 {
2019         int ret = 0;
2020         struct bio *bio;
2021         int nr;
2022         int contig = 0;
2023         int this_compressed = bio_flags & EXTENT_BIO_COMPRESSED;
2024         int old_compressed = prev_bio_flags & EXTENT_BIO_COMPRESSED;
2025         size_t page_size = min_t(size_t, size, PAGE_CACHE_SIZE);
2026
2027         if (bio_ret && *bio_ret) {
2028                 bio = *bio_ret;
2029                 if (old_compressed)
2030                         contig = bio->bi_sector == sector;
2031                 else
2032                         contig = bio->bi_sector + (bio->bi_size >> 9) ==
2033                                 sector;
2034
2035                 if (prev_bio_flags != bio_flags || !contig ||
2036                     (tree->ops && tree->ops->merge_bio_hook &&
2037                      tree->ops->merge_bio_hook(page, offset, page_size, bio,
2038                                                bio_flags)) ||
2039                     bio_add_page(bio, page, page_size, offset) < page_size) {
2040                         ret = submit_one_bio(rw, bio, mirror_num,
2041                                              prev_bio_flags);
2042                         bio = NULL;
2043                 } else {
2044                         return 0;
2045                 }
2046         }
2047         if (this_compressed)
2048                 nr = BIO_MAX_PAGES;
2049         else
2050                 nr = bio_get_nr_vecs(bdev);
2051
2052         bio = btrfs_bio_alloc(bdev, sector, nr, GFP_NOFS | __GFP_HIGH);
2053         if (!bio)
2054                 return -ENOMEM;
2055
2056         bio_add_page(bio, page, page_size, offset);
2057         bio->bi_end_io = end_io_func;
2058         bio->bi_private = tree;
2059
2060         if (bio_ret)
2061                 *bio_ret = bio;
2062         else
2063                 ret = submit_one_bio(rw, bio, mirror_num, bio_flags);
2064
2065         return ret;
2066 }
2067
2068 void set_page_extent_mapped(struct page *page)
2069 {
2070         if (!PagePrivate(page)) {
2071                 SetPagePrivate(page);
2072                 page_cache_get(page);
2073                 set_page_private(page, EXTENT_PAGE_PRIVATE);
2074         }
2075 }
2076
2077 static void set_page_extent_head(struct page *page, unsigned long len)
2078 {
2079         WARN_ON(!PagePrivate(page));
2080         set_page_private(page, EXTENT_PAGE_PRIVATE_FIRST_PAGE | len << 2);
2081 }
2082
2083 /*
2084  * basic readpage implementation.  Locked extent state structs are inserted
2085  * into the tree that are removed when the IO is done (by the end_io
2086  * handlers)
2087  */
2088 static int __extent_read_full_page(struct extent_io_tree *tree,
2089                                    struct page *page,
2090                                    get_extent_t *get_extent,
2091                                    struct bio **bio, int mirror_num,
2092                                    unsigned long *bio_flags)
2093 {
2094         struct inode *inode = page->mapping->host;
2095         u64 start = (u64)page->index << PAGE_CACHE_SHIFT;
2096         u64 page_end = start + PAGE_CACHE_SIZE - 1;
2097         u64 end;
2098         u64 cur = start;
2099         u64 extent_offset;
2100         u64 last_byte = i_size_read(inode);
2101         u64 block_start;
2102         u64 cur_end;
2103         sector_t sector;
2104         struct extent_map *em;
2105         struct block_device *bdev;
2106         struct btrfs_ordered_extent *ordered;
2107         int ret;
2108         int nr = 0;
2109         size_t pg_offset = 0;
2110         size_t iosize;
2111         size_t disk_io_size;
2112         size_t blocksize = inode->i_sb->s_blocksize;
2113         unsigned long this_bio_flag = 0;
2114
2115         set_page_extent_mapped(page);
2116
2117         if (!PageUptodate(page)) {
2118                 if (cleancache_get_page(page) == 0) {
2119                         BUG_ON(blocksize != PAGE_SIZE);
2120                         goto out;
2121                 }
2122         }
2123
2124         end = page_end;
2125         while (1) {
2126                 lock_extent(tree, start, end, GFP_NOFS);
2127                 ordered = btrfs_lookup_ordered_extent(inode, start);
2128                 if (!ordered)
2129                         break;
2130                 unlock_extent(tree, start, end, GFP_NOFS);
2131                 btrfs_start_ordered_extent(inode, ordered, 1);
2132                 btrfs_put_ordered_extent(ordered);
2133         }
2134
2135         if (page->index == last_byte >> PAGE_CACHE_SHIFT) {
2136                 char *userpage;
2137                 size_t zero_offset = last_byte & (PAGE_CACHE_SIZE - 1);
2138
2139                 if (zero_offset) {
2140                         iosize = PAGE_CACHE_SIZE - zero_offset;
2141                         userpage = kmap_atomic(page, KM_USER0);
2142                         memset(userpage + zero_offset, 0, iosize);
2143                         flush_dcache_page(page);
2144                         kunmap_atomic(userpage, KM_USER0);
2145                 }
2146         }
2147         while (cur <= end) {
2148                 if (cur >= last_byte) {
2149                         char *userpage;
2150                         struct extent_state *cached = NULL;
2151
2152                         iosize = PAGE_CACHE_SIZE - pg_offset;
2153                         userpage = kmap_atomic(page, KM_USER0);
2154                         memset(userpage + pg_offset, 0, iosize);
2155                         flush_dcache_page(page);
2156                         kunmap_atomic(userpage, KM_USER0);
2157                         set_extent_uptodate(tree, cur, cur + iosize - 1,
2158                                             &cached, GFP_NOFS);
2159                         unlock_extent_cached(tree, cur, cur + iosize - 1,
2160                                              &cached, GFP_NOFS);
2161                         break;
2162                 }
2163                 em = get_extent(inode, page, pg_offset, cur,
2164                                 end - cur + 1, 0);
2165                 if (IS_ERR_OR_NULL(em)) {
2166                         SetPageError(page);
2167                         unlock_extent(tree, cur, end, GFP_NOFS);
2168                         break;
2169                 }
2170                 extent_offset = cur - em->start;
2171                 BUG_ON(extent_map_end(em) <= cur);
2172                 BUG_ON(end < cur);
2173
2174                 if (test_bit(EXTENT_FLAG_COMPRESSED, &em->flags)) {
2175                         this_bio_flag = EXTENT_BIO_COMPRESSED;
2176                         extent_set_compress_type(&this_bio_flag,
2177                                                  em->compress_type);
2178                 }
2179
2180                 iosize = min(extent_map_end(em) - cur, end - cur + 1);
2181                 cur_end = min(extent_map_end(em) - 1, end);
2182                 iosize = (iosize + blocksize - 1) & ~((u64)blocksize - 1);
2183                 if (this_bio_flag & EXTENT_BIO_COMPRESSED) {
2184                         disk_io_size = em->block_len;
2185                         sector = em->block_start >> 9;
2186                 } else {
2187                         sector = (em->block_start + extent_offset) >> 9;
2188                         disk_io_size = iosize;
2189                 }
2190                 bdev = em->bdev;
2191                 block_start = em->block_start;
2192                 if (test_bit(EXTENT_FLAG_PREALLOC, &em->flags))
2193                         block_start = EXTENT_MAP_HOLE;
2194                 free_extent_map(em);
2195                 em = NULL;
2196
2197                 /* we've found a hole, just zero and go on */
2198                 if (block_start == EXTENT_MAP_HOLE) {
2199                         char *userpage;
2200                         struct extent_state *cached = NULL;
2201
2202                         userpage = kmap_atomic(page, KM_USER0);
2203                         memset(userpage + pg_offset, 0, iosize);
2204                         flush_dcache_page(page);
2205                         kunmap_atomic(userpage, KM_USER0);
2206
2207                         set_extent_uptodate(tree, cur, cur + iosize - 1,
2208                                             &cached, GFP_NOFS);
2209                         unlock_extent_cached(tree, cur, cur + iosize - 1,
2210                                              &cached, GFP_NOFS);
2211                         cur = cur + iosize;
2212                         pg_offset += iosize;
2213                         continue;
2214                 }
2215                 /* the get_extent function already copied into the page */
2216                 if (test_range_bit(tree, cur, cur_end,
2217                                    EXTENT_UPTODATE, 1, NULL)) {
2218                         check_page_uptodate(tree, page);
2219                         unlock_extent(tree, cur, cur + iosize - 1, GFP_NOFS);
2220                         cur = cur + iosize;
2221                         pg_offset += iosize;
2222                         continue;
2223                 }
2224                 /* we have an inline extent but it didn't get marked up
2225                  * to date.  Error out
2226                  */
2227                 if (block_start == EXTENT_MAP_INLINE) {
2228                         SetPageError(page);
2229                         unlock_extent(tree, cur, cur + iosize - 1, GFP_NOFS);
2230                         cur = cur + iosize;
2231                         pg_offset += iosize;
2232                         continue;
2233                 }
2234
2235                 ret = 0;
2236                 if (tree->ops && tree->ops->readpage_io_hook) {
2237                         ret = tree->ops->readpage_io_hook(page, cur,
2238                                                           cur + iosize - 1);
2239                 }
2240                 if (!ret) {
2241                         unsigned long pnr = (last_byte >> PAGE_CACHE_SHIFT) + 1;
2242                         pnr -= page->index;
2243                         ret = submit_extent_page(READ, tree, page,
2244                                          sector, disk_io_size, pg_offset,
2245                                          bdev, bio, pnr,
2246                                          end_bio_extent_readpage, mirror_num,
2247                                          *bio_flags,
2248                                          this_bio_flag);
2249                         nr++;
2250                         *bio_flags = this_bio_flag;
2251                 }
2252                 if (ret)
2253                         SetPageError(page);
2254                 cur = cur + iosize;
2255                 pg_offset += iosize;
2256         }
2257 out:
2258         if (!nr) {
2259                 if (!PageError(page))
2260                         SetPageUptodate(page);
2261                 unlock_page(page);
2262         }
2263         return 0;
2264 }
2265
2266 int extent_read_full_page(struct extent_io_tree *tree, struct page *page,
2267                             get_extent_t *get_extent)
2268 {
2269         struct bio *bio = NULL;
2270         unsigned long bio_flags = 0;
2271         int ret;
2272
2273         ret = __extent_read_full_page(tree, page, get_extent, &bio, 0,
2274                                       &bio_flags);
2275         if (bio)
2276                 ret = submit_one_bio(READ, bio, 0, bio_flags);
2277         return ret;
2278 }
2279
2280 static noinline void update_nr_written(struct page *page,
2281                                       struct writeback_control *wbc,
2282                                       unsigned long nr_written)
2283 {
2284         wbc->nr_to_write -= nr_written;
2285         if (wbc->range_cyclic || (wbc->nr_to_write > 0 &&
2286             wbc->range_start == 0 && wbc->range_end == LLONG_MAX))
2287                 page->mapping->writeback_index = page->index + nr_written;
2288 }
2289
2290 /*
2291  * the writepage semantics are similar to regular writepage.  extent
2292  * records are inserted to lock ranges in the tree, and as dirty areas
2293  * are found, they are marked writeback.  Then the lock bits are removed
2294  * and the end_io handler clears the writeback ranges
2295  */
2296 static int __extent_writepage(struct page *page, struct writeback_control *wbc,
2297                               void *data)
2298 {
2299         struct inode *inode = page->mapping->host;
2300         struct extent_page_data *epd = data;
2301         struct extent_io_tree *tree = epd->tree;
2302         u64 start = (u64)page->index << PAGE_CACHE_SHIFT;
2303         u64 delalloc_start;
2304         u64 page_end = start + PAGE_CACHE_SIZE - 1;
2305         u64 end;
2306         u64 cur = start;
2307         u64 extent_offset;
2308         u64 last_byte = i_size_read(inode);
2309         u64 block_start;
2310         u64 iosize;
2311         sector_t sector;
2312         struct extent_state *cached_state = NULL;
2313         struct extent_map *em;
2314         struct block_device *bdev;
2315         int ret;
2316         int nr = 0;
2317         size_t pg_offset = 0;
2318         size_t blocksize;
2319         loff_t i_size = i_size_read(inode);
2320         unsigned long end_index = i_size >> PAGE_CACHE_SHIFT;
2321         u64 nr_delalloc;
2322         u64 delalloc_end;
2323         int page_started;
2324         int compressed;
2325         int write_flags;
2326         unsigned long nr_written = 0;
2327         bool fill_delalloc = true;
2328
2329         if (wbc->sync_mode == WB_SYNC_ALL)
2330                 write_flags = WRITE_SYNC;
2331         else
2332                 write_flags = WRITE;
2333
2334         trace___extent_writepage(page, inode, wbc);
2335
2336         WARN_ON(!PageLocked(page));
2337
2338         ClearPageError(page);
2339
2340         pg_offset = i_size & (PAGE_CACHE_SIZE - 1);
2341         if (page->index > end_index ||
2342            (page->index == end_index && !pg_offset)) {
2343                 page->mapping->a_ops->invalidatepage(page, 0);
2344                 unlock_page(page);
2345                 return 0;
2346         }
2347
2348         if (page->index == end_index) {
2349                 char *userpage;
2350
2351                 userpage = kmap_atomic(page, KM_USER0);
2352                 memset(userpage + pg_offset, 0,
2353                        PAGE_CACHE_SIZE - pg_offset);
2354                 kunmap_atomic(userpage, KM_USER0);
2355                 flush_dcache_page(page);
2356         }
2357         pg_offset = 0;
2358
2359         set_page_extent_mapped(page);
2360
2361         if (!tree->ops || !tree->ops->fill_delalloc)
2362                 fill_delalloc = false;
2363
2364         delalloc_start = start;
2365         delalloc_end = 0;
2366         page_started = 0;
2367         if (!epd->extent_locked && fill_delalloc) {
2368                 u64 delalloc_to_write = 0;
2369                 /*
2370                  * make sure the wbc mapping index is at least updated
2371                  * to this page.
2372                  */
2373                 update_nr_written(page, wbc, 0);
2374
2375                 while (delalloc_end < page_end) {
2376                         nr_delalloc = find_lock_delalloc_range(inode, tree,
2377                                                        page,
2378                                                        &delalloc_start,
2379                                                        &delalloc_end,
2380                                                        128 * 1024 * 1024);
2381                         if (nr_delalloc == 0) {
2382                                 delalloc_start = delalloc_end + 1;
2383                                 continue;
2384                         }
2385                         tree->ops->fill_delalloc(inode, page, delalloc_start,
2386                                                  delalloc_end, &page_started,
2387                                                  &nr_written);
2388                         /*
2389                          * delalloc_end is already one less than the total
2390                          * length, so we don't subtract one from
2391                          * PAGE_CACHE_SIZE
2392                          */
2393                         delalloc_to_write += (delalloc_end - delalloc_start +
2394                                               PAGE_CACHE_SIZE) >>
2395                                               PAGE_CACHE_SHIFT;
2396                         delalloc_start = delalloc_end + 1;
2397                 }
2398                 if (wbc->nr_to_write < delalloc_to_write) {
2399                         int thresh = 8192;
2400
2401                         if (delalloc_to_write < thresh * 2)
2402                                 thresh = delalloc_to_write;
2403                         wbc->nr_to_write = min_t(u64, delalloc_to_write,
2404                                                  thresh);
2405                 }
2406
2407                 /* did the fill delalloc function already unlock and start
2408                  * the IO?
2409                  */
2410                 if (page_started) {
2411                         ret = 0;
2412                         /*
2413                          * we've unlocked the page, so we can't update
2414                          * the mapping's writeback index, just update
2415                          * nr_to_write.
2416                          */
2417                         wbc->nr_to_write -= nr_written;
2418                         goto done_unlocked;
2419                 }
2420         }
2421         if (tree->ops && tree->ops->writepage_start_hook) {
2422                 ret = tree->ops->writepage_start_hook(page, start,
2423                                                       page_end);
2424                 if (ret == -EAGAIN) {
2425                         redirty_page_for_writepage(wbc, page);
2426                         update_nr_written(page, wbc, nr_written);
2427                         unlock_page(page);
2428                         ret = 0;
2429                         goto done_unlocked;
2430                 }
2431         }
2432
2433         /*
2434          * we don't want to touch the inode after unlocking the page,
2435          * so we update the mapping writeback index now
2436          */
2437         update_nr_written(page, wbc, nr_written + 1);
2438
2439         end = page_end;
2440         if (last_byte <= start) {
2441                 if (tree->ops && tree->ops->writepage_end_io_hook)
2442                         tree->ops->writepage_end_io_hook(page, start,
2443                                                          page_end, NULL, 1);
2444                 goto done;
2445         }
2446
2447         blocksize = inode->i_sb->s_blocksize;
2448
2449         while (cur <= end) {
2450                 if (cur >= last_byte) {
2451                         if (tree->ops && tree->ops->writepage_end_io_hook)
2452                                 tree->ops->writepage_end_io_hook(page, cur,
2453                                                          page_end, NULL, 1);
2454                         break;
2455                 }
2456                 em = epd->get_extent(inode, page, pg_offset, cur,
2457                                      end - cur + 1, 1);
2458                 if (IS_ERR_OR_NULL(em)) {
2459                         SetPageError(page);
2460                         break;
2461                 }
2462
2463                 extent_offset = cur - em->start;
2464                 BUG_ON(extent_map_end(em) <= cur);
2465                 BUG_ON(end < cur);
2466                 iosize = min(extent_map_end(em) - cur, end - cur + 1);
2467                 iosize = (iosize + blocksize - 1) & ~((u64)blocksize - 1);
2468                 sector = (em->block_start + extent_offset) >> 9;
2469                 bdev = em->bdev;
2470                 block_start = em->block_start;
2471                 compressed = test_bit(EXTENT_FLAG_COMPRESSED, &em->flags);
2472                 free_extent_map(em);
2473                 em = NULL;
2474
2475                 /*
2476                  * compressed and inline extents are written through other
2477                  * paths in the FS
2478                  */
2479                 if (compressed || block_start == EXTENT_MAP_HOLE ||
2480                     block_start == EXTENT_MAP_INLINE) {
2481                         /*
2482                          * end_io notification does not happen here for
2483                          * compressed extents
2484                          */
2485                         if (!compressed && tree->ops &&
2486                             tree->ops->writepage_end_io_hook)
2487                                 tree->ops->writepage_end_io_hook(page, cur,
2488                                                          cur + iosize - 1,
2489                                                          NULL, 1);
2490                         else if (compressed) {
2491                                 /* we don't want to end_page_writeback on
2492                                  * a compressed extent.  this happens
2493                                  * elsewhere
2494                                  */
2495                                 nr++;
2496                         }
2497
2498                         cur += iosize;
2499                         pg_offset += iosize;
2500                         continue;
2501                 }
2502                 /* leave this out until we have a page_mkwrite call */
2503                 if (0 && !test_range_bit(tree, cur, cur + iosize - 1,
2504                                    EXTENT_DIRTY, 0, NULL)) {
2505                         cur = cur + iosize;
2506                         pg_offset += iosize;
2507                         continue;
2508                 }
2509
2510                 if (tree->ops && tree->ops->writepage_io_hook) {
2511                         ret = tree->ops->writepage_io_hook(page, cur,
2512                                                 cur + iosize - 1);
2513                 } else {
2514                         ret = 0;
2515                 }
2516                 if (ret) {
2517                         SetPageError(page);
2518                 } else {
2519                         unsigned long max_nr = end_index + 1;
2520
2521                         set_range_writeback(tree, cur, cur + iosize - 1);
2522                         if (!PageWriteback(page)) {
2523                                 printk(KERN_ERR "btrfs warning page %lu not "
2524                                        "writeback, cur %llu end %llu\n",
2525                                        page->index, (unsigned long long)cur,
2526                                        (unsigned long long)end);
2527                         }
2528
2529                         ret = submit_extent_page(write_flags, tree, page,
2530                                                  sector, iosize, pg_offset,
2531                                                  bdev, &epd->bio, max_nr,
2532                                                  end_bio_extent_writepage,
2533                                                  0, 0, 0);
2534                         if (ret)
2535                                 SetPageError(page);
2536                 }
2537                 cur = cur + iosize;
2538                 pg_offset += iosize;
2539                 nr++;
2540         }
2541 done:
2542         if (nr == 0) {
2543                 /* make sure the mapping tag for page dirty gets cleared */
2544                 set_page_writeback(page);
2545                 end_page_writeback(page);
2546         }
2547         unlock_page(page);
2548
2549 done_unlocked:
2550
2551         /* drop our reference on any cached states */
2552         free_extent_state(cached_state);
2553         return 0;
2554 }
2555
2556 /**
2557  * write_cache_pages - walk the list of dirty pages of the given address space and write all of them.
2558  * @mapping: address space structure to write
2559  * @wbc: subtract the number of written pages from *@wbc->nr_to_write
2560  * @writepage: function called for each page
2561  * @data: data passed to writepage function
2562  *
2563  * If a page is already under I/O, write_cache_pages() skips it, even
2564  * if it's dirty.  This is desirable behaviour for memory-cleaning writeback,
2565  * but it is INCORRECT for data-integrity system calls such as fsync().  fsync()
2566  * and msync() need to guarantee that all the data which was dirty at the time
2567  * the call was made get new I/O started against them.  If wbc->sync_mode is
2568  * WB_SYNC_ALL then we were called for data integrity and we must wait for
2569  * existing IO to complete.
2570  */
2571 static int extent_write_cache_pages(struct extent_io_tree *tree,
2572                              struct address_space *mapping,
2573                              struct writeback_control *wbc,
2574                              writepage_t writepage, void *data,
2575                              void (*flush_fn)(void *))
2576 {
2577         int ret = 0;
2578         int done = 0;
2579         int nr_to_write_done = 0;
2580         struct pagevec pvec;
2581         int nr_pages;
2582         pgoff_t index;
2583         pgoff_t end;            /* Inclusive */
2584         int scanned = 0;
2585         int tag;
2586
2587         pagevec_init(&pvec, 0);
2588         if (wbc->range_cyclic) {
2589                 index = mapping->writeback_index; /* Start from prev offset */
2590                 end = -1;
2591         } else {
2592                 index = wbc->range_start >> PAGE_CACHE_SHIFT;
2593                 end = wbc->range_end >> PAGE_CACHE_SHIFT;
2594                 scanned = 1;
2595         }
2596         if (wbc->sync_mode == WB_SYNC_ALL)
2597                 tag = PAGECACHE_TAG_TOWRITE;
2598         else
2599                 tag = PAGECACHE_TAG_DIRTY;
2600 retry:
2601         if (wbc->sync_mode == WB_SYNC_ALL)
2602                 tag_pages_for_writeback(mapping, index, end);
2603         while (!done && !nr_to_write_done && (index <= end) &&
2604                (nr_pages = pagevec_lookup_tag(&pvec, mapping, &index, tag,
2605                         min(end - index, (pgoff_t)PAGEVEC_SIZE-1) + 1))) {
2606                 unsigned i;
2607
2608                 scanned = 1;
2609                 for (i = 0; i < nr_pages; i++) {
2610                         struct page *page = pvec.pages[i];
2611
2612                         /*
2613                          * At this point we hold neither mapping->tree_lock nor
2614                          * lock on the page itself: the page may be truncated or
2615                          * invalidated (changing page->mapping to NULL), or even
2616                          * swizzled back from swapper_space to tmpfs file
2617                          * mapping
2618                          */
2619                         if (tree->ops &&
2620                             tree->ops->write_cache_pages_lock_hook) {
2621                                 tree->ops->write_cache_pages_lock_hook(page,
2622                                                                data, flush_fn);
2623                         } else {
2624                                 if (!trylock_page(page)) {
2625                                         flush_fn(data);
2626                                         lock_page(page);
2627                                 }
2628                         }
2629
2630                         if (unlikely(page->mapping != mapping)) {
2631                                 unlock_page(page);
2632                                 continue;
2633                         }
2634
2635                         if (!wbc->range_cyclic && page->index > end) {
2636                                 done = 1;
2637                                 unlock_page(page);
2638                                 continue;
2639                         }
2640
2641                         if (wbc->sync_mode != WB_SYNC_NONE) {
2642                                 if (PageWriteback(page))
2643                                         flush_fn(data);
2644                                 wait_on_page_writeback(page);
2645                         }
2646
2647                         if (PageWriteback(page) ||
2648                             !clear_page_dirty_for_io(page)) {
2649                                 unlock_page(page);
2650                                 continue;
2651                         }
2652
2653                         ret = (*writepage)(page, wbc, data);
2654
2655                         if (unlikely(ret == AOP_WRITEPAGE_ACTIVATE)) {
2656                                 unlock_page(page);
2657                                 ret = 0;
2658                         }
2659                         if (ret)
2660                                 done = 1;
2661
2662                         /*
2663                          * the filesystem may choose to bump up nr_to_write.
2664                          * We have to make sure to honor the new nr_to_write
2665                          * at any time
2666                          */
2667                         nr_to_write_done = wbc->nr_to_write <= 0;
2668                 }
2669                 pagevec_release(&pvec);
2670                 cond_resched();
2671         }
2672         if (!scanned && !done) {
2673                 /*
2674                  * We hit the last page and there is more work to be done: wrap
2675                  * back to the start of the file
2676                  */
2677                 scanned = 1;
2678                 index = 0;
2679                 goto retry;
2680         }
2681         return ret;
2682 }
2683
2684 static void flush_epd_write_bio(struct extent_page_data *epd)
2685 {
2686         if (epd->bio) {
2687                 if (epd->sync_io)
2688                         submit_one_bio(WRITE_SYNC, epd->bio, 0, 0);
2689                 else
2690                         submit_one_bio(WRITE, epd->bio, 0, 0);
2691                 epd->bio = NULL;
2692         }
2693 }
2694
2695 static noinline void flush_write_bio(void *data)
2696 {
2697         struct extent_page_data *epd = data;
2698         flush_epd_write_bio(epd);
2699 }
2700
2701 int extent_write_full_page(struct extent_io_tree *tree, struct page *page,
2702                           get_extent_t *get_extent,
2703                           struct writeback_control *wbc)
2704 {
2705         int ret;
2706         struct extent_page_data epd = {
2707                 .bio = NULL,
2708                 .tree = tree,
2709                 .get_extent = get_extent,
2710                 .extent_locked = 0,
2711                 .sync_io = wbc->sync_mode == WB_SYNC_ALL,
2712         };
2713
2714         ret = __extent_writepage(page, wbc, &epd);
2715
2716         flush_epd_write_bio(&epd);
2717         return ret;
2718 }
2719
2720 int extent_write_locked_range(struct extent_io_tree *tree, struct inode *inode,
2721                               u64 start, u64 end, get_extent_t *get_extent,
2722                               int mode)
2723 {
2724         int ret = 0;
2725         struct address_space *mapping = inode->i_mapping;
2726         struct page *page;
2727         unsigned long nr_pages = (end - start + PAGE_CACHE_SIZE) >>
2728                 PAGE_CACHE_SHIFT;
2729
2730         struct extent_page_data epd = {
2731                 .bio = NULL,
2732                 .tree = tree,
2733                 .get_extent = get_extent,
2734                 .extent_locked = 1,
2735                 .sync_io = mode == WB_SYNC_ALL,
2736         };
2737         struct writeback_control wbc_writepages = {
2738                 .sync_mode      = mode,
2739                 .nr_to_write    = nr_pages * 2,
2740                 .range_start    = start,
2741                 .range_end      = end + 1,
2742         };
2743
2744         while (start <= end) {
2745                 page = find_get_page(mapping, start >> PAGE_CACHE_SHIFT);
2746                 if (clear_page_dirty_for_io(page))
2747                         ret = __extent_writepage(page, &wbc_writepages, &epd);
2748                 else {
2749                         if (tree->ops && tree->ops->writepage_end_io_hook)
2750                                 tree->ops->writepage_end_io_hook(page, start,
2751                                                  start + PAGE_CACHE_SIZE - 1,
2752                                                  NULL, 1);
2753                         unlock_page(page);
2754                 }
2755                 page_cache_release(page);
2756                 start += PAGE_CACHE_SIZE;
2757         }
2758
2759         flush_epd_write_bio(&epd);
2760         return ret;
2761 }
2762
2763 int extent_writepages(struct extent_io_tree *tree,
2764                       struct address_space *mapping,
2765                       get_extent_t *get_extent,
2766                       struct writeback_control *wbc)
2767 {
2768         int ret = 0;
2769         struct extent_page_data epd = {
2770                 .bio = NULL,
2771                 .tree = tree,
2772                 .get_extent = get_extent,
2773                 .extent_locked = 0,
2774                 .sync_io = wbc->sync_mode == WB_SYNC_ALL,
2775         };
2776
2777         ret = extent_write_cache_pages(tree, mapping, wbc,
2778                                        __extent_writepage, &epd,
2779                                        flush_write_bio);
2780         flush_epd_write_bio(&epd);
2781         return ret;
2782 }
2783
2784 int extent_readpages(struct extent_io_tree *tree,
2785                      struct address_space *mapping,
2786                      struct list_head *pages, unsigned nr_pages,
2787                      get_extent_t get_extent)
2788 {
2789         struct bio *bio = NULL;
2790         unsigned page_idx;
2791         unsigned long bio_flags = 0;
2792
2793         for (page_idx = 0; page_idx < nr_pages; page_idx++) {
2794                 struct page *page = list_entry(pages->prev, struct page, lru);
2795
2796                 prefetchw(&page->flags);
2797                 list_del(&page->lru);
2798                 if (!add_to_page_cache_lru(page, mapping,
2799                                         page->index, GFP_NOFS)) {
2800                         __extent_read_full_page(tree, page, get_extent,
2801                                                 &bio, 0, &bio_flags);
2802                 }
2803                 page_cache_release(page);
2804         }
2805         BUG_ON(!list_empty(pages));
2806         if (bio)
2807                 submit_one_bio(READ, bio, 0, bio_flags);
2808         return 0;
2809 }
2810
2811 /*
2812  * basic invalidatepage code, this waits on any locked or writeback
2813  * ranges corresponding to the page, and then deletes any extent state
2814  * records from the tree
2815  */
2816 int extent_invalidatepage(struct extent_io_tree *tree,
2817                           struct page *page, unsigned long offset)
2818 {
2819         struct extent_state *cached_state = NULL;
2820         u64 start = ((u64)page->index << PAGE_CACHE_SHIFT);
2821         u64 end = start + PAGE_CACHE_SIZE - 1;
2822         size_t blocksize = page->mapping->host->i_sb->s_blocksize;
2823
2824         start += (offset + blocksize - 1) & ~(blocksize - 1);
2825         if (start > end)
2826                 return 0;
2827
2828         lock_extent_bits(tree, start, end, 0, &cached_state, GFP_NOFS);
2829         wait_on_page_writeback(page);
2830         clear_extent_bit(tree, start, end,
2831                          EXTENT_LOCKED | EXTENT_DIRTY | EXTENT_DELALLOC |
2832                          EXTENT_DO_ACCOUNTING,
2833                          1, 1, &cached_state, GFP_NOFS);
2834         return 0;
2835 }
2836
2837 /*
2838  * a helper for releasepage, this tests for areas of the page that
2839  * are locked or under IO and drops the related state bits if it is safe
2840  * to drop the page.
2841  */
2842 int try_release_extent_state(struct extent_map_tree *map,
2843                              struct extent_io_tree *tree, struct page *page,
2844                              gfp_t mask)
2845 {
2846         u64 start = (u64)page->index << PAGE_CACHE_SHIFT;
2847         u64 end = start + PAGE_CACHE_SIZE - 1;
2848         int ret = 1;
2849
2850         if (test_range_bit(tree, start, end,
2851                            EXTENT_IOBITS, 0, NULL))
2852                 ret = 0;
2853         else {
2854                 if ((mask & GFP_NOFS) == GFP_NOFS)
2855                         mask = GFP_NOFS;
2856                 /*
2857                  * at this point we can safely clear everything except the
2858                  * locked bit and the nodatasum bit
2859                  */
2860                 ret = clear_extent_bit(tree, start, end,
2861                                  ~(EXTENT_LOCKED | EXTENT_NODATASUM),
2862                                  0, 0, NULL, mask);
2863
2864                 /* if clear_extent_bit failed for enomem reasons,
2865                  * we can't allow the release to continue.
2866                  */
2867                 if (ret < 0)
2868                         ret = 0;
2869                 else
2870                         ret = 1;
2871         }
2872         return ret;
2873 }
2874
2875 /*
2876  * a helper for releasepage.  As long as there are no locked extents
2877  * in the range corresponding to the page, both state records and extent
2878  * map records are removed
2879  */
2880 int try_release_extent_mapping(struct extent_map_tree *map,
2881                                struct extent_io_tree *tree, struct page *page,
2882                                gfp_t mask)
2883 {
2884         struct extent_map *em;
2885         u64 start = (u64)page->index << PAGE_CACHE_SHIFT;
2886         u64 end = start + PAGE_CACHE_SIZE - 1;
2887
2888         if ((mask & __GFP_WAIT) &&
2889             page->mapping->host->i_size > 16 * 1024 * 1024) {
2890                 u64 len;
2891                 while (start <= end) {
2892                         len = end - start + 1;
2893                         write_lock(&map->lock);
2894                         em = lookup_extent_mapping(map, start, len);
2895                         if (IS_ERR_OR_NULL(em)) {
2896                                 write_unlock(&map->lock);
2897                                 break;
2898                         }
2899                         if (test_bit(EXTENT_FLAG_PINNED, &em->flags) ||
2900                             em->start != start) {
2901                                 write_unlock(&map->lock);
2902                                 free_extent_map(em);
2903                                 break;
2904                         }
2905                         if (!test_range_bit(tree, em->start,
2906                                             extent_map_end(em) - 1,
2907                                             EXTENT_LOCKED | EXTENT_WRITEBACK,
2908                                             0, NULL)) {
2909                                 remove_extent_mapping(map, em);
2910                                 /* once for the rb tree */
2911                                 free_extent_map(em);
2912                         }
2913                         start = extent_map_end(em);
2914                         write_unlock(&map->lock);
2915
2916                         /* once for us */
2917                         free_extent_map(em);
2918                 }
2919         }
2920         return try_release_extent_state(map, tree, page, mask);
2921 }
2922
2923 /*
2924  * helper function for fiemap, which doesn't want to see any holes.
2925  * This maps until we find something past 'last'
2926  */
2927 static struct extent_map *get_extent_skip_holes(struct inode *inode,
2928                                                 u64 offset,
2929                                                 u64 last,
2930                                                 get_extent_t *get_extent)
2931 {
2932         u64 sectorsize = BTRFS_I(inode)->root->sectorsize;
2933         struct extent_map *em;
2934         u64 len;
2935
2936         if (offset >= last)
2937                 return NULL;
2938
2939         while(1) {
2940                 len = last - offset;
2941                 if (len == 0)
2942                         break;
2943                 len = (len + sectorsize - 1) & ~(sectorsize - 1);
2944                 em = get_extent(inode, NULL, 0, offset, len, 0);
2945                 if (IS_ERR_OR_NULL(em))
2946                         return em;
2947
2948                 /* if this isn't a hole return it */
2949                 if (!test_bit(EXTENT_FLAG_VACANCY, &em->flags) &&
2950                     em->block_start != EXTENT_MAP_HOLE) {
2951                         return em;
2952                 }
2953
2954                 /* this is a hole, advance to the next extent */
2955                 offset = extent_map_end(em);
2956                 free_extent_map(em);
2957                 if (offset >= last)
2958                         break;
2959         }
2960         return NULL;
2961 }
2962
2963 int extent_fiemap(struct inode *inode, struct fiemap_extent_info *fieinfo,
2964                 __u64 start, __u64 len, get_extent_t *get_extent)
2965 {
2966         int ret = 0;
2967         u64 off = start;
2968         u64 max = start + len;
2969         u32 flags = 0;
2970         u32 found_type;
2971         u64 last;
2972         u64 last_for_get_extent = 0;
2973         u64 disko = 0;
2974         u64 isize = i_size_read(inode);
2975         struct btrfs_key found_key;
2976         struct extent_map *em = NULL;
2977         struct extent_state *cached_state = NULL;
2978         struct btrfs_path *path;
2979         struct btrfs_file_extent_item *item;
2980         int end = 0;
2981         u64 em_start = 0;
2982         u64 em_len = 0;
2983         u64 em_end = 0;
2984         unsigned long emflags;
2985
2986         if (len == 0)
2987                 return -EINVAL;
2988
2989         path = btrfs_alloc_path();
2990         if (!path)
2991                 return -ENOMEM;
2992         path->leave_spinning = 1;
2993
2994         /*
2995          * lookup the last file extent.  We're not using i_size here
2996          * because there might be preallocation past i_size
2997          */
2998         ret = btrfs_lookup_file_extent(NULL, BTRFS_I(inode)->root,
2999                                        path, btrfs_ino(inode), -1, 0);
3000         if (ret < 0) {
3001                 btrfs_free_path(path);
3002                 return ret;
3003         }
3004         WARN_ON(!ret);
3005         path->slots[0]--;
3006         item = btrfs_item_ptr(path->nodes[0], path->slots[0],
3007                               struct btrfs_file_extent_item);
3008         btrfs_item_key_to_cpu(path->nodes[0], &found_key, path->slots[0]);
3009         found_type = btrfs_key_type(&found_key);
3010
3011         /* No extents, but there might be delalloc bits */
3012         if (found_key.objectid != btrfs_ino(inode) ||
3013             found_type != BTRFS_EXTENT_DATA_KEY) {
3014                 /* have to trust i_size as the end */
3015                 last = (u64)-1;
3016                 last_for_get_extent = isize;
3017         } else {
3018                 /*
3019                  * remember the start of the last extent.  There are a
3020                  * bunch of different factors that go into the length of the
3021                  * extent, so its much less complex to remember where it started
3022                  */
3023                 last = found_key.offset;
3024                 last_for_get_extent = last + 1;
3025         }
3026         btrfs_free_path(path);
3027
3028         /*
3029          * we might have some extents allocated but more delalloc past those
3030          * extents.  so, we trust isize unless the start of the last extent is
3031          * beyond isize
3032          */
3033         if (last < isize) {
3034                 last = (u64)-1;
3035                 last_for_get_extent = isize;
3036         }
3037
3038         lock_extent_bits(&BTRFS_I(inode)->io_tree, start, start + len, 0,
3039                          &cached_state, GFP_NOFS);
3040
3041         em = get_extent_skip_holes(inode, off, last_for_get_extent,
3042                                    get_extent);
3043         if (!em)
3044                 goto out;
3045         if (IS_ERR(em)) {
3046                 ret = PTR_ERR(em);
3047                 goto out;
3048         }
3049
3050         while (!end) {
3051                 u64 offset_in_extent;
3052
3053                 /* break if the extent we found is outside the range */
3054                 if (em->start >= max || extent_map_end(em) < off)
3055                         break;
3056
3057                 /*
3058                  * get_extent may return an extent that starts before our
3059                  * requested range.  We have to make sure the ranges
3060                  * we return to fiemap always move forward and don't
3061                  * overlap, so adjust the offsets here
3062                  */
3063                 em_start = max(em->start, off);
3064
3065                 /*
3066                  * record the offset from the start of the extent
3067                  * for adjusting the disk offset below
3068                  */
3069                 offset_in_extent = em_start - em->start;
3070                 em_end = extent_map_end(em);
3071                 em_len = em_end - em_start;
3072                 emflags = em->flags;
3073                 disko = 0;
3074                 flags = 0;
3075
3076                 /*
3077                  * bump off for our next call to get_extent
3078                  */
3079                 off = extent_map_end(em);
3080                 if (off >= max)
3081                         end = 1;
3082
3083                 if (em->block_start == EXTENT_MAP_LAST_BYTE) {
3084                         end = 1;
3085                         flags |= FIEMAP_EXTENT_LAST;
3086                 } else if (em->block_start == EXTENT_MAP_INLINE) {
3087                         flags |= (FIEMAP_EXTENT_DATA_INLINE |
3088                                   FIEMAP_EXTENT_NOT_ALIGNED);
3089                 } else if (em->block_start == EXTENT_MAP_DELALLOC) {
3090                         flags |= (FIEMAP_EXTENT_DELALLOC |
3091                                   FIEMAP_EXTENT_UNKNOWN);
3092                 } else {
3093                         disko = em->block_start + offset_in_extent;
3094                 }
3095                 if (test_bit(EXTENT_FLAG_COMPRESSED, &em->flags))
3096                         flags |= FIEMAP_EXTENT_ENCODED;
3097
3098                 free_extent_map(em);
3099                 em = NULL;
3100                 if ((em_start >= last) || em_len == (u64)-1 ||
3101                    (last == (u64)-1 && isize <= em_end)) {
3102                         flags |= FIEMAP_EXTENT_LAST;
3103                         end = 1;
3104                 }
3105
3106                 /* now scan forward to see if this is really the last extent. */
3107                 em = get_extent_skip_holes(inode, off, last_for_get_extent,
3108                                            get_extent);
3109                 if (IS_ERR(em)) {
3110                         ret = PTR_ERR(em);
3111                         goto out;
3112                 }
3113                 if (!em) {
3114                         flags |= FIEMAP_EXTENT_LAST;
3115                         end = 1;
3116                 }
3117                 ret = fiemap_fill_next_extent(fieinfo, em_start, disko,
3118                                               em_len, flags);
3119                 if (ret)
3120                         goto out_free;
3121         }
3122 out_free:
3123         free_extent_map(em);
3124 out:
3125         unlock_extent_cached(&BTRFS_I(inode)->io_tree, start, start + len,
3126                              &cached_state, GFP_NOFS);
3127         return ret;
3128 }
3129
3130 static inline struct page *extent_buffer_page(struct extent_buffer *eb,
3131                                               unsigned long i)
3132 {
3133         struct page *p;
3134         struct address_space *mapping;
3135
3136         if (i == 0)
3137                 return eb->first_page;
3138         i += eb->start >> PAGE_CACHE_SHIFT;
3139         mapping = eb->first_page->mapping;
3140         if (!mapping)
3141                 return NULL;
3142
3143         /*
3144          * extent_buffer_page is only called after pinning the page
3145          * by increasing the reference count.  So we know the page must
3146          * be in the radix tree.
3147          */
3148         rcu_read_lock();
3149         p = radix_tree_lookup(&mapping->page_tree, i);
3150         rcu_read_unlock();
3151
3152         return p;
3153 }
3154
3155 static inline unsigned long num_extent_pages(u64 start, u64 len)
3156 {
3157         return ((start + len + PAGE_CACHE_SIZE - 1) >> PAGE_CACHE_SHIFT) -
3158                 (start >> PAGE_CACHE_SHIFT);
3159 }
3160
3161 static struct extent_buffer *__alloc_extent_buffer(struct extent_io_tree *tree,
3162                                                    u64 start,
3163                                                    unsigned long len,
3164                                                    gfp_t mask)
3165 {
3166         struct extent_buffer *eb = NULL;
3167 #if LEAK_DEBUG
3168         unsigned long flags;
3169 #endif
3170
3171         eb = kmem_cache_zalloc(extent_buffer_cache, mask);
3172         if (eb == NULL)
3173                 return NULL;
3174         eb->start = start;
3175         eb->len = len;
3176         rwlock_init(&eb->lock);
3177         atomic_set(&eb->write_locks, 0);
3178         atomic_set(&eb->read_locks, 0);
3179         atomic_set(&eb->blocking_readers, 0);
3180         atomic_set(&eb->blocking_writers, 0);
3181         atomic_set(&eb->spinning_readers, 0);
3182         atomic_set(&eb->spinning_writers, 0);
3183         init_waitqueue_head(&eb->write_lock_wq);
3184         init_waitqueue_head(&eb->read_lock_wq);
3185
3186 #if LEAK_DEBUG
3187         spin_lock_irqsave(&leak_lock, flags);
3188         list_add(&eb->leak_list, &buffers);
3189         spin_unlock_irqrestore(&leak_lock, flags);
3190 #endif
3191         atomic_set(&eb->refs, 1);
3192
3193         return eb;
3194 }
3195
3196 static void __free_extent_buffer(struct extent_buffer *eb)
3197 {
3198 #if LEAK_DEBUG
3199         unsigned long flags;
3200         spin_lock_irqsave(&leak_lock, flags);
3201         list_del(&eb->leak_list);
3202         spin_unlock_irqrestore(&leak_lock, flags);
3203 #endif
3204         kmem_cache_free(extent_buffer_cache, eb);
3205 }
3206
3207 /*
3208  * Helper for releasing extent buffer page.
3209  */
3210 static void btrfs_release_extent_buffer_page(struct extent_buffer *eb,
3211                                                 unsigned long start_idx)
3212 {
3213         unsigned long index;
3214         struct page *page;
3215
3216         if (!eb->first_page)
3217                 return;
3218
3219         index = num_extent_pages(eb->start, eb->len);
3220         if (start_idx >= index)
3221                 return;
3222
3223         do {
3224                 index--;
3225                 page = extent_buffer_page(eb, index);
3226                 if (page)
3227                         page_cache_release(page);
3228         } while (index != start_idx);
3229 }
3230
3231 /*
3232  * Helper for releasing the extent buffer.
3233  */
3234 static inline void btrfs_release_extent_buffer(struct extent_buffer *eb)
3235 {
3236         btrfs_release_extent_buffer_page(eb, 0);
3237         __free_extent_buffer(eb);
3238 }
3239
3240 struct extent_buffer *alloc_extent_buffer(struct extent_io_tree *tree,
3241                                           u64 start, unsigned long len,
3242                                           struct page *page0)
3243 {
3244         unsigned long num_pages = num_extent_pages(start, len);
3245         unsigned long i;
3246         unsigned long index = start >> PAGE_CACHE_SHIFT;
3247         struct extent_buffer *eb;
3248         struct extent_buffer *exists = NULL;
3249         struct page *p;
3250         struct address_space *mapping = tree->mapping;
3251         int uptodate = 1;
3252         int ret;
3253
3254         rcu_read_lock();
3255         eb = radix_tree_lookup(&tree->buffer, start >> PAGE_CACHE_SHIFT);
3256         if (eb && atomic_inc_not_zero(&eb->refs)) {
3257                 rcu_read_unlock();
3258                 mark_page_accessed(eb->first_page);
3259                 return eb;
3260         }
3261         rcu_read_unlock();
3262
3263         eb = __alloc_extent_buffer(tree, start, len, GFP_NOFS);
3264         if (!eb)
3265                 return NULL;
3266
3267         if (page0) {
3268                 eb->first_page = page0;
3269                 i = 1;
3270                 index++;
3271                 page_cache_get(page0);
3272                 mark_page_accessed(page0);
3273                 set_page_extent_mapped(page0);
3274                 set_page_extent_head(page0, len);
3275                 uptodate = PageUptodate(page0);
3276         } else {
3277                 i = 0;
3278         }
3279         for (; i < num_pages; i++, index++) {
3280                 p = find_or_create_page(mapping, index, GFP_NOFS);
3281                 if (!p) {
3282                         WARN_ON(1);
3283                         goto free_eb;
3284                 }
3285                 set_page_extent_mapped(p);
3286                 mark_page_accessed(p);
3287                 if (i == 0) {
3288                         eb->first_page = p;
3289                         set_page_extent_head(p, len);
3290                 } else {
3291                         set_page_private(p, EXTENT_PAGE_PRIVATE);
3292                 }
3293                 if (!PageUptodate(p))
3294                         uptodate = 0;
3295
3296                 /*
3297                  * see below about how we avoid a nasty race with release page
3298                  * and why we unlock later
3299                  */
3300                 if (i != 0)
3301                         unlock_page(p);
3302         }
3303         if (uptodate)
3304                 set_bit(EXTENT_BUFFER_UPTODATE, &eb->bflags);
3305
3306         ret = radix_tree_preload(GFP_NOFS & ~__GFP_HIGHMEM);
3307         if (ret)
3308                 goto free_eb;
3309
3310         spin_lock(&tree->buffer_lock);
3311         ret = radix_tree_insert(&tree->buffer, start >> PAGE_CACHE_SHIFT, eb);
3312         if (ret == -EEXIST) {
3313                 exists = radix_tree_lookup(&tree->buffer,
3314                                                 start >> PAGE_CACHE_SHIFT);
3315                 /* add one reference for the caller */
3316                 atomic_inc(&exists->refs);
3317                 spin_unlock(&tree->buffer_lock);
3318                 radix_tree_preload_end();
3319                 goto free_eb;
3320         }
3321         /* add one reference for the tree */
3322         atomic_inc(&eb->refs);
3323         spin_unlock(&tree->buffer_lock);
3324         radix_tree_preload_end();
3325
3326         /*
3327          * there is a race where release page may have
3328          * tried to find this extent buffer in the radix
3329          * but failed.  It will tell the VM it is safe to
3330          * reclaim the, and it will clear the page private bit.
3331          * We must make sure to set the page private bit properly
3332          * after the extent buffer is in the radix tree so
3333          * it doesn't get lost
3334          */
3335         set_page_extent_mapped(eb->first_page);
3336         set_page_extent_head(eb->first_page, eb->len);
3337         if (!page0)
3338                 unlock_page(eb->first_page);
3339         return eb;
3340
3341 free_eb:
3342         if (eb->first_page && !page0)
3343                 unlock_page(eb->first_page);
3344
3345         if (!atomic_dec_and_test(&eb->refs))
3346                 return exists;
3347         btrfs_release_extent_buffer(eb);
3348         return exists;
3349 }
3350
3351 struct extent_buffer *find_extent_buffer(struct extent_io_tree *tree,
3352                                          u64 start, unsigned long len)
3353 {
3354         struct extent_buffer *eb;
3355
3356         rcu_read_lock();
3357         eb = radix_tree_lookup(&tree->buffer, start >> PAGE_CACHE_SHIFT);
3358         if (eb && atomic_inc_not_zero(&eb->refs)) {
3359                 rcu_read_unlock();
3360                 mark_page_accessed(eb->first_page);
3361                 return eb;
3362         }
3363         rcu_read_unlock();
3364
3365         return NULL;
3366 }
3367
3368 void free_extent_buffer(struct extent_buffer *eb)
3369 {
3370         if (!eb)
3371                 return;
3372
3373         if (!atomic_dec_and_test(&eb->refs))
3374                 return;
3375
3376         WARN_ON(1);
3377 }
3378
3379 int clear_extent_buffer_dirty(struct extent_io_tree *tree,
3380                               struct extent_buffer *eb)
3381 {
3382         unsigned long i;
3383         unsigned long num_pages;
3384         struct page *page;
3385
3386         num_pages = num_extent_pages(eb->start, eb->len);
3387
3388         for (i = 0; i < num_pages; i++) {
3389                 page = extent_buffer_page(eb, i);
3390                 if (!PageDirty(page))
3391                         continue;
3392
3393                 lock_page(page);
3394                 WARN_ON(!PagePrivate(page));
3395
3396                 set_page_extent_mapped(page);
3397                 if (i == 0)
3398                         set_page_extent_head(page, eb->len);
3399
3400                 clear_page_dirty_for_io(page);
3401                 spin_lock_irq(&page->mapping->tree_lock);
3402                 if (!PageDirty(page)) {
3403                         radix_tree_tag_clear(&page->mapping->page_tree,
3404                                                 page_index(page),
3405                                                 PAGECACHE_TAG_DIRTY);
3406                 }
3407                 spin_unlock_irq(&page->mapping->tree_lock);
3408                 ClearPageError(page);
3409                 unlock_page(page);
3410         }
3411         return 0;
3412 }
3413
3414 int set_extent_buffer_dirty(struct extent_io_tree *tree,
3415                              struct extent_buffer *eb)
3416 {
3417         unsigned long i;
3418         unsigned long num_pages;
3419         int was_dirty = 0;
3420
3421         was_dirty = test_and_set_bit(EXTENT_BUFFER_DIRTY, &eb->bflags);
3422         num_pages = num_extent_pages(eb->start, eb->len);
3423         for (i = 0; i < num_pages; i++)
3424                 __set_page_dirty_nobuffers(extent_buffer_page(eb, i));
3425         return was_dirty;
3426 }
3427
3428 static int __eb_straddles_pages(u64 start, u64 len)
3429 {
3430         if (len < PAGE_CACHE_SIZE)
3431                 return 1;
3432         if (start & (PAGE_CACHE_SIZE - 1))
3433                 return 1;
3434         if ((start + len) & (PAGE_CACHE_SIZE - 1))
3435                 return 1;
3436         return 0;
3437 }
3438
3439 static int eb_straddles_pages(struct extent_buffer *eb)
3440 {
3441         return __eb_straddles_pages(eb->start, eb->len);
3442 }
3443
3444 int clear_extent_buffer_uptodate(struct extent_io_tree *tree,
3445                                 struct extent_buffer *eb,
3446                                 struct extent_state **cached_state)
3447 {
3448         unsigned long i;
3449         struct page *page;
3450         unsigned long num_pages;
3451
3452         num_pages = num_extent_pages(eb->start, eb->len);
3453         clear_bit(EXTENT_BUFFER_UPTODATE, &eb->bflags);
3454
3455         if (eb_straddles_pages(eb)) {
3456                 clear_extent_uptodate(tree, eb->start, eb->start + eb->len - 1,
3457                                       cached_state, GFP_NOFS);
3458         }
3459         for (i = 0; i < num_pages; i++) {
3460                 page = extent_buffer_page(eb, i);
3461                 if (page)
3462                         ClearPageUptodate(page);
3463         }
3464         return 0;
3465 }
3466
3467 int set_extent_buffer_uptodate(struct extent_io_tree *tree,
3468                                 struct extent_buffer *eb)
3469 {
3470         unsigned long i;
3471         struct page *page;
3472         unsigned long num_pages;
3473
3474         num_pages = num_extent_pages(eb->start, eb->len);
3475
3476         if (eb_straddles_pages(eb)) {
3477                 set_extent_uptodate(tree, eb->start, eb->start + eb->len - 1,
3478                                     NULL, GFP_NOFS);
3479         }
3480         for (i = 0; i < num_pages; i++) {
3481                 page = extent_buffer_page(eb, i);
3482                 if ((i == 0 && (eb->start & (PAGE_CACHE_SIZE - 1))) ||
3483                     ((i == num_pages - 1) &&
3484                      ((eb->start + eb->len) & (PAGE_CACHE_SIZE - 1)))) {
3485                         check_page_uptodate(tree, page);
3486                         continue;
3487                 }
3488                 SetPageUptodate(page);
3489         }
3490         return 0;
3491 }
3492
3493 int extent_range_uptodate(struct extent_io_tree *tree,
3494                           u64 start, u64 end)
3495 {
3496         struct page *page;
3497         int ret;
3498         int pg_uptodate = 1;
3499         int uptodate;
3500         unsigned long index;
3501
3502         if (__eb_straddles_pages(start, end - start + 1)) {
3503                 ret = test_range_bit(tree, start, end,
3504                                      EXTENT_UPTODATE, 1, NULL);
3505                 if (ret)
3506                         return 1;
3507         }
3508         while (start <= end) {
3509                 index = start >> PAGE_CACHE_SHIFT;
3510                 page = find_get_page(tree->mapping, index);
3511                 uptodate = PageUptodate(page);
3512                 page_cache_release(page);
3513                 if (!uptodate) {
3514                         pg_uptodate = 0;
3515                         break;
3516                 }
3517                 start += PAGE_CACHE_SIZE;
3518         }
3519         return pg_uptodate;
3520 }
3521
3522 int extent_buffer_uptodate(struct extent_io_tree *tree,
3523                            struct extent_buffer *eb,
3524                            struct extent_state *cached_state)
3525 {
3526         int ret = 0;
3527         unsigned long num_pages;
3528         unsigned long i;
3529         struct page *page;
3530         int pg_uptodate = 1;
3531
3532         if (test_bit(EXTENT_BUFFER_UPTODATE, &eb->bflags))
3533                 return 1;
3534
3535         if (eb_straddles_pages(eb)) {
3536                 ret = test_range_bit(tree, eb->start, eb->start + eb->len - 1,
3537                                    EXTENT_UPTODATE, 1, cached_state);
3538                 if (ret)
3539                         return ret;
3540         }
3541
3542         num_pages = num_extent_pages(eb->start, eb->len);
3543         for (i = 0; i < num_pages; i++) {
3544                 page = extent_buffer_page(eb, i);
3545                 if (!PageUptodate(page)) {
3546                         pg_uptodate = 0;
3547                         break;
3548                 }
3549         }
3550         return pg_uptodate;
3551 }
3552
3553 int read_extent_buffer_pages(struct extent_io_tree *tree,
3554                              struct extent_buffer *eb,
3555                              u64 start, int wait,
3556                              get_extent_t *get_extent, int mirror_num)
3557 {
3558         unsigned long i;
3559         unsigned long start_i;
3560         struct page *page;
3561         int err;
3562         int ret = 0;
3563         int locked_pages = 0;
3564         int all_uptodate = 1;
3565         int inc_all_pages = 0;
3566         unsigned long num_pages;
3567         struct bio *bio = NULL;
3568         unsigned long bio_flags = 0;
3569
3570         if (test_bit(EXTENT_BUFFER_UPTODATE, &eb->bflags))
3571                 return 0;
3572
3573         if (eb_straddles_pages(eb)) {
3574                 if (test_range_bit(tree, eb->start, eb->start + eb->len - 1,
3575                                    EXTENT_UPTODATE, 1, NULL)) {
3576                         return 0;
3577                 }
3578         }
3579
3580         if (start) {
3581                 WARN_ON(start < eb->start);
3582                 start_i = (start >> PAGE_CACHE_SHIFT) -
3583                         (eb->start >> PAGE_CACHE_SHIFT);
3584         } else {
3585                 start_i = 0;
3586         }
3587
3588         num_pages = num_extent_pages(eb->start, eb->len);
3589         for (i = start_i; i < num_pages; i++) {
3590                 page = extent_buffer_page(eb, i);
3591                 if (!wait) {
3592                         if (!trylock_page(page))
3593                                 goto unlock_exit;
3594                 } else {
3595                         lock_page(page);
3596                 }
3597                 locked_pages++;
3598                 if (!PageUptodate(page))
3599                         all_uptodate = 0;
3600         }
3601         if (all_uptodate) {
3602                 if (start_i == 0)
3603                         set_bit(EXTENT_BUFFER_UPTODATE, &eb->bflags);
3604                 goto unlock_exit;
3605         }
3606
3607         for (i = start_i; i < num_pages; i++) {
3608                 page = extent_buffer_page(eb, i);
3609
3610                 WARN_ON(!PagePrivate(page));
3611
3612                 set_page_extent_mapped(page);
3613                 if (i == 0)
3614                         set_page_extent_head(page, eb->len);
3615
3616                 if (inc_all_pages)
3617                         page_cache_get(page);
3618                 if (!PageUptodate(page)) {
3619                         if (start_i == 0)
3620                                 inc_all_pages = 1;
3621                         ClearPageError(page);
3622                         err = __extent_read_full_page(tree, page,
3623                                                       get_extent, &bio,
3624                                                       mirror_num, &bio_flags);
3625                         if (err)
3626                                 ret = err;
3627                 } else {
3628                         unlock_page(page);
3629                 }
3630         }
3631
3632         if (bio)
3633                 submit_one_bio(READ, bio, mirror_num, bio_flags);
3634
3635         if (ret || !wait)
3636                 return ret;
3637
3638         for (i = start_i; i < num_pages; i++) {
3639                 page = extent_buffer_page(eb, i);
3640                 wait_on_page_locked(page);
3641                 if (!PageUptodate(page))
3642                         ret = -EIO;
3643         }
3644
3645         if (!ret)
3646                 set_bit(EXTENT_BUFFER_UPTODATE, &eb->bflags);
3647         return ret;
3648
3649 unlock_exit:
3650         i = start_i;
3651         while (locked_pages > 0) {
3652                 page = extent_buffer_page(eb, i);
3653                 i++;
3654                 unlock_page(page);
3655                 locked_pages--;
3656         }
3657         return ret;
3658 }
3659
3660 void read_extent_buffer(struct extent_buffer *eb, void *dstv,
3661                         unsigned long start,
3662                         unsigned long len)
3663 {
3664         size_t cur;
3665         size_t offset;
3666         struct page *page;
3667         char *kaddr;
3668         char *dst = (char *)dstv;
3669         size_t start_offset = eb->start & ((u64)PAGE_CACHE_SIZE - 1);
3670         unsigned long i = (start_offset + start) >> PAGE_CACHE_SHIFT;
3671
3672         WARN_ON(start > eb->len);
3673         WARN_ON(start + len > eb->start + eb->len);
3674
3675         offset = (start_offset + start) & ((unsigned long)PAGE_CACHE_SIZE - 1);
3676
3677         while (len > 0) {
3678                 page = extent_buffer_page(eb, i);
3679
3680                 cur = min(len, (PAGE_CACHE_SIZE - offset));
3681                 kaddr = page_address(page);
3682                 memcpy(dst, kaddr + offset, cur);
3683
3684                 dst += cur;
3685                 len -= cur;
3686                 offset = 0;
3687                 i++;
3688         }
3689 }
3690
3691 int map_private_extent_buffer(struct extent_buffer *eb, unsigned long start,
3692                                unsigned long min_len, char **map,
3693                                unsigned long *map_start,
3694                                unsigned long *map_len)
3695 {
3696         size_t offset = start & (PAGE_CACHE_SIZE - 1);
3697         char *kaddr;
3698         struct page *p;
3699         size_t start_offset = eb->start & ((u64)PAGE_CACHE_SIZE - 1);
3700         unsigned long i = (start_offset + start) >> PAGE_CACHE_SHIFT;
3701         unsigned long end_i = (start_offset + start + min_len - 1) >>
3702                 PAGE_CACHE_SHIFT;
3703
3704         if (i != end_i)
3705                 return -EINVAL;
3706
3707         if (i == 0) {
3708                 offset = start_offset;
3709                 *map_start = 0;
3710         } else {
3711                 offset = 0;
3712                 *map_start = ((u64)i << PAGE_CACHE_SHIFT) - start_offset;
3713         }
3714
3715         if (start + min_len > eb->len) {
3716                 printk(KERN_ERR "btrfs bad mapping eb start %llu len %lu, "
3717                        "wanted %lu %lu\n", (unsigned long long)eb->start,
3718                        eb->len, start, min_len);
3719                 WARN_ON(1);
3720                 return -EINVAL;
3721         }
3722
3723         p = extent_buffer_page(eb, i);
3724         kaddr = page_address(p);
3725         *map = kaddr + offset;
3726         *map_len = PAGE_CACHE_SIZE - offset;
3727         return 0;
3728 }
3729
3730 int memcmp_extent_buffer(struct extent_buffer *eb, const void *ptrv,
3731                           unsigned long start,
3732                           unsigned long len)
3733 {
3734         size_t cur;
3735         size_t offset;
3736         struct page *page;
3737         char *kaddr;
3738         char *ptr = (char *)ptrv;
3739         size_t start_offset = eb->start & ((u64)PAGE_CACHE_SIZE - 1);
3740         unsigned long i = (start_offset + start) >> PAGE_CACHE_SHIFT;
3741         int ret = 0;
3742
3743         WARN_ON(start > eb->len);
3744         WARN_ON(start + len > eb->start + eb->len);
3745
3746         offset = (start_offset + start) & ((unsigned long)PAGE_CACHE_SIZE - 1);
3747
3748         while (len > 0) {
3749                 page = extent_buffer_page(eb, i);
3750
3751                 cur = min(len, (PAGE_CACHE_SIZE - offset));
3752
3753                 kaddr = page_address(page);
3754                 ret = memcmp(ptr, kaddr + offset, cur);
3755                 if (ret)
3756                         break;
3757
3758                 ptr += cur;
3759                 len -= cur;
3760                 offset = 0;
3761                 i++;
3762         }
3763         return ret;
3764 }
3765
3766 void write_extent_buffer(struct extent_buffer *eb, const void *srcv,
3767                          unsigned long start, unsigned long len)
3768 {
3769         size_t cur;
3770         size_t offset;
3771         struct page *page;
3772         char *kaddr;
3773         char *src = (char *)srcv;
3774         size_t start_offset = eb->start & ((u64)PAGE_CACHE_SIZE - 1);
3775         unsigned long i = (start_offset + start) >> PAGE_CACHE_SHIFT;
3776
3777         WARN_ON(start > eb->len);
3778         WARN_ON(start + len > eb->start + eb->len);
3779
3780         offset = (start_offset + start) & ((unsigned long)PAGE_CACHE_SIZE - 1);
3781
3782         while (len > 0) {
3783                 page = extent_buffer_page(eb, i);
3784                 WARN_ON(!PageUptodate(page));
3785
3786                 cur = min(len, PAGE_CACHE_SIZE - offset);
3787                 kaddr = page_address(page);
3788                 memcpy(kaddr + offset, src, cur);
3789
3790                 src += cur;
3791                 len -= cur;
3792                 offset = 0;
3793                 i++;
3794         }
3795 }
3796
3797 void memset_extent_buffer(struct extent_buffer *eb, char c,
3798                           unsigned long start, unsigned long len)
3799 {
3800         size_t cur;
3801         size_t offset;
3802         struct page *page;
3803         char *kaddr;
3804         size_t start_offset = eb->start & ((u64)PAGE_CACHE_SIZE - 1);
3805         unsigned long i = (start_offset + start) >> PAGE_CACHE_SHIFT;
3806
3807         WARN_ON(start > eb->len);
3808         WARN_ON(start + len > eb->start + eb->len);
3809
3810         offset = (start_offset + start) & ((unsigned long)PAGE_CACHE_SIZE - 1);
3811
3812         while (len > 0) {
3813                 page = extent_buffer_page(eb, i);
3814                 WARN_ON(!PageUptodate(page));
3815
3816                 cur = min(len, PAGE_CACHE_SIZE - offset);
3817                 kaddr = page_address(page);
3818                 memset(kaddr + offset, c, cur);
3819
3820                 len -= cur;
3821                 offset = 0;
3822                 i++;
3823         }
3824 }
3825
3826 void copy_extent_buffer(struct extent_buffer *dst, struct extent_buffer *src,
3827                         unsigned long dst_offset, unsigned long src_offset,
3828                         unsigned long len)
3829 {
3830         u64 dst_len = dst->len;
3831         size_t cur;
3832         size_t offset;
3833         struct page *page;
3834         char *kaddr;
3835         size_t start_offset = dst->start & ((u64)PAGE_CACHE_SIZE - 1);
3836         unsigned long i = (start_offset + dst_offset) >> PAGE_CACHE_SHIFT;
3837
3838         WARN_ON(src->len != dst_len);
3839
3840         offset = (start_offset + dst_offset) &
3841                 ((unsigned long)PAGE_CACHE_SIZE - 1);
3842
3843         while (len > 0) {
3844                 page = extent_buffer_page(dst, i);
3845                 WARN_ON(!PageUptodate(page));
3846
3847                 cur = min(len, (unsigned long)(PAGE_CACHE_SIZE - offset));
3848
3849                 kaddr = page_address(page);
3850                 read_extent_buffer(src, kaddr + offset, src_offset, cur);
3851
3852                 src_offset += cur;
3853                 len -= cur;
3854                 offset = 0;
3855                 i++;
3856         }
3857 }
3858
3859 static void move_pages(struct page *dst_page, struct page *src_page,
3860                        unsigned long dst_off, unsigned long src_off,
3861                        unsigned long len)
3862 {
3863         char *dst_kaddr = page_address(dst_page);
3864         if (dst_page == src_page) {
3865                 memmove(dst_kaddr + dst_off, dst_kaddr + src_off, len);
3866         } else {
3867                 char *src_kaddr = page_address(src_page);
3868                 char *p = dst_kaddr + dst_off + len;
3869                 char *s = src_kaddr + src_off + len;
3870
3871                 while (len--)
3872                         *--p = *--s;
3873         }
3874 }
3875
3876 static inline bool areas_overlap(unsigned long src, unsigned long dst, unsigned long len)
3877 {
3878         unsigned long distance = (src > dst) ? src - dst : dst - src;
3879         return distance < len;
3880 }
3881
3882 static void copy_pages(struct page *dst_page, struct page *src_page,
3883                        unsigned long dst_off, unsigned long src_off,
3884                        unsigned long len)
3885 {
3886         char *dst_kaddr = page_address(dst_page);
3887         char *src_kaddr;
3888
3889         if (dst_page != src_page) {
3890                 src_kaddr = page_address(src_page);
3891         } else {
3892                 src_kaddr = dst_kaddr;
3893                 BUG_ON(areas_overlap(src_off, dst_off, len));
3894         }
3895
3896         memcpy(dst_kaddr + dst_off, src_kaddr + src_off, len);
3897 }
3898
3899 void memcpy_extent_buffer(struct extent_buffer *dst, unsigned long dst_offset,
3900                            unsigned long src_offset, unsigned long len)
3901 {
3902         size_t cur;
3903         size_t dst_off_in_page;
3904         size_t src_off_in_page;
3905         size_t start_offset = dst->start & ((u64)PAGE_CACHE_SIZE - 1);
3906         unsigned long dst_i;
3907         unsigned long src_i;
3908
3909         if (src_offset + len > dst->len) {
3910                 printk(KERN_ERR "btrfs memmove bogus src_offset %lu move "
3911                        "len %lu dst len %lu\n", src_offset, len, dst->len);
3912                 BUG_ON(1);
3913         }
3914         if (dst_offset + len > dst->len) {
3915                 printk(KERN_ERR "btrfs memmove bogus dst_offset %lu move "
3916                        "len %lu dst len %lu\n", dst_offset, len, dst->len);
3917                 BUG_ON(1);
3918         }
3919
3920         while (len > 0) {
3921                 dst_off_in_page = (start_offset + dst_offset) &
3922                         ((unsigned long)PAGE_CACHE_SIZE - 1);
3923                 src_off_in_page = (start_offset + src_offset) &
3924                         ((unsigned long)PAGE_CACHE_SIZE - 1);
3925
3926                 dst_i = (start_offset + dst_offset) >> PAGE_CACHE_SHIFT;
3927                 src_i = (start_offset + src_offset) >> PAGE_CACHE_SHIFT;
3928
3929                 cur = min(len, (unsigned long)(PAGE_CACHE_SIZE -
3930                                                src_off_in_page));
3931                 cur = min_t(unsigned long, cur,
3932                         (unsigned long)(PAGE_CACHE_SIZE - dst_off_in_page));
3933
3934                 copy_pages(extent_buffer_page(dst, dst_i),
3935                            extent_buffer_page(dst, src_i),
3936                            dst_off_in_page, src_off_in_page, cur);
3937
3938                 src_offset += cur;
3939                 dst_offset += cur;
3940                 len -= cur;
3941         }
3942 }
3943
3944 void memmove_extent_buffer(struct extent_buffer *dst, unsigned long dst_offset,
3945                            unsigned long src_offset, unsigned long len)
3946 {
3947         size_t cur;
3948         size_t dst_off_in_page;
3949         size_t src_off_in_page;
3950         unsigned long dst_end = dst_offset + len - 1;
3951         unsigned long src_end = src_offset + len - 1;
3952         size_t start_offset = dst->start & ((u64)PAGE_CACHE_SIZE - 1);
3953         unsigned long dst_i;
3954         unsigned long src_i;
3955
3956         if (src_offset + len > dst->len) {
3957                 printk(KERN_ERR "btrfs memmove bogus src_offset %lu move "
3958                        "len %lu len %lu\n", src_offset, len, dst->len);
3959                 BUG_ON(1);
3960         }
3961         if (dst_offset + len > dst->len) {
3962                 printk(KERN_ERR "btrfs memmove bogus dst_offset %lu move "
3963                        "len %lu len %lu\n", dst_offset, len, dst->len);
3964                 BUG_ON(1);
3965         }
3966         if (!areas_overlap(src_offset, dst_offset, len)) {
3967                 memcpy_extent_buffer(dst, dst_offset, src_offset, len);
3968                 return;
3969         }
3970         while (len > 0) {
3971                 dst_i = (start_offset + dst_end) >> PAGE_CACHE_SHIFT;
3972                 src_i = (start_offset + src_end) >> PAGE_CACHE_SHIFT;
3973
3974                 dst_off_in_page = (start_offset + dst_end) &
3975                         ((unsigned long)PAGE_CACHE_SIZE - 1);
3976                 src_off_in_page = (start_offset + src_end) &
3977                         ((unsigned long)PAGE_CACHE_SIZE - 1);
3978
3979                 cur = min_t(unsigned long, len, src_off_in_page + 1);
3980                 cur = min(cur, dst_off_in_page + 1);
3981                 move_pages(extent_buffer_page(dst, dst_i),
3982                            extent_buffer_page(dst, src_i),
3983                            dst_off_in_page - cur + 1,
3984                            src_off_in_page - cur + 1, cur);
3985
3986                 dst_end -= cur;
3987                 src_end -= cur;
3988                 len -= cur;
3989         }
3990 }
3991
3992 static inline void btrfs_release_extent_buffer_rcu(struct rcu_head *head)
3993 {
3994         struct extent_buffer *eb =
3995                         container_of(head, struct extent_buffer, rcu_head);
3996
3997         btrfs_release_extent_buffer(eb);
3998 }
3999
4000 int try_release_extent_buffer(struct extent_io_tree *tree, struct page *page)
4001 {
4002         u64 start = page_offset(page);
4003         struct extent_buffer *eb;
4004         int ret = 1;
4005
4006         spin_lock(&tree->buffer_lock);
4007         eb = radix_tree_lookup(&tree->buffer, start >> PAGE_CACHE_SHIFT);
4008         if (!eb) {
4009                 spin_unlock(&tree->buffer_lock);
4010                 return ret;
4011         }
4012
4013         if (test_bit(EXTENT_BUFFER_DIRTY, &eb->bflags)) {
4014                 ret = 0;
4015                 goto out;
4016         }
4017
4018         /*
4019          * set @eb->refs to 0 if it is already 1, and then release the @eb.
4020          * Or go back.
4021          */
4022         if (atomic_cmpxchg(&eb->refs, 1, 0) != 1) {
4023                 ret = 0;
4024                 goto out;
4025         }
4026
4027         radix_tree_delete(&tree->buffer, start >> PAGE_CACHE_SHIFT);
4028 out:
4029         spin_unlock(&tree->buffer_lock);
4030
4031         /* at this point we can safely release the extent buffer */
4032         if (atomic_read(&eb->refs) == 0)
4033                 call_rcu(&eb->rcu_head, btrfs_release_extent_buffer_rcu);
4034         return ret;
4035 }