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