4f19bdca3214dea23e4a6cbfa7139c918c23d68d
[sfrench/cifs-2.6.git] / fs / btrfs / extent-tree.c
1 // SPDX-License-Identifier: GPL-2.0
2 /*
3  * Copyright (C) 2007 Oracle.  All rights reserved.
4  */
5
6 #include <linux/sched.h>
7 #include <linux/sched/signal.h>
8 #include <linux/pagemap.h>
9 #include <linux/writeback.h>
10 #include <linux/blkdev.h>
11 #include <linux/sort.h>
12 #include <linux/rcupdate.h>
13 #include <linux/kthread.h>
14 #include <linux/slab.h>
15 #include <linux/ratelimit.h>
16 #include <linux/percpu_counter.h>
17 #include <linux/lockdep.h>
18 #include <linux/crc32c.h>
19 #include "tree-log.h"
20 #include "disk-io.h"
21 #include "print-tree.h"
22 #include "volumes.h"
23 #include "raid56.h"
24 #include "locking.h"
25 #include "free-space-cache.h"
26 #include "free-space-tree.h"
27 #include "math.h"
28 #include "sysfs.h"
29 #include "qgroup.h"
30 #include "ref-verify.h"
31
32 #undef SCRAMBLE_DELAYED_REFS
33
34 /*
35  * control flags for do_chunk_alloc's force field
36  * CHUNK_ALLOC_NO_FORCE means to only allocate a chunk
37  * if we really need one.
38  *
39  * CHUNK_ALLOC_LIMITED means to only try and allocate one
40  * if we have very few chunks already allocated.  This is
41  * used as part of the clustering code to help make sure
42  * we have a good pool of storage to cluster in, without
43  * filling the FS with empty chunks
44  *
45  * CHUNK_ALLOC_FORCE means it must try to allocate one
46  *
47  */
48 enum {
49         CHUNK_ALLOC_NO_FORCE = 0,
50         CHUNK_ALLOC_LIMITED = 1,
51         CHUNK_ALLOC_FORCE = 2,
52 };
53
54 static int __btrfs_free_extent(struct btrfs_trans_handle *trans,
55                                struct btrfs_delayed_ref_node *node, u64 parent,
56                                u64 root_objectid, u64 owner_objectid,
57                                u64 owner_offset, int refs_to_drop,
58                                struct btrfs_delayed_extent_op *extra_op);
59 static void __run_delayed_extent_op(struct btrfs_delayed_extent_op *extent_op,
60                                     struct extent_buffer *leaf,
61                                     struct btrfs_extent_item *ei);
62 static int alloc_reserved_file_extent(struct btrfs_trans_handle *trans,
63                                       u64 parent, u64 root_objectid,
64                                       u64 flags, u64 owner, u64 offset,
65                                       struct btrfs_key *ins, int ref_mod);
66 static int alloc_reserved_tree_block(struct btrfs_trans_handle *trans,
67                                      struct btrfs_delayed_ref_node *node,
68                                      struct btrfs_delayed_extent_op *extent_op);
69 static int do_chunk_alloc(struct btrfs_trans_handle *trans, u64 flags,
70                           int force);
71 static int find_next_key(struct btrfs_path *path, int level,
72                          struct btrfs_key *key);
73 static void dump_space_info(struct btrfs_fs_info *fs_info,
74                             struct btrfs_space_info *info, u64 bytes,
75                             int dump_block_groups);
76 static int block_rsv_use_bytes(struct btrfs_block_rsv *block_rsv,
77                                u64 num_bytes);
78 static void space_info_add_new_bytes(struct btrfs_fs_info *fs_info,
79                                      struct btrfs_space_info *space_info,
80                                      u64 num_bytes);
81 static void space_info_add_old_bytes(struct btrfs_fs_info *fs_info,
82                                      struct btrfs_space_info *space_info,
83                                      u64 num_bytes);
84
85 static noinline int
86 block_group_cache_done(struct btrfs_block_group_cache *cache)
87 {
88         smp_mb();
89         return cache->cached == BTRFS_CACHE_FINISHED ||
90                 cache->cached == BTRFS_CACHE_ERROR;
91 }
92
93 static int block_group_bits(struct btrfs_block_group_cache *cache, u64 bits)
94 {
95         return (cache->flags & bits) == bits;
96 }
97
98 void btrfs_get_block_group(struct btrfs_block_group_cache *cache)
99 {
100         atomic_inc(&cache->count);
101 }
102
103 void btrfs_put_block_group(struct btrfs_block_group_cache *cache)
104 {
105         if (atomic_dec_and_test(&cache->count)) {
106                 WARN_ON(cache->pinned > 0);
107                 WARN_ON(cache->reserved > 0);
108
109                 /*
110                  * If not empty, someone is still holding mutex of
111                  * full_stripe_lock, which can only be released by caller.
112                  * And it will definitely cause use-after-free when caller
113                  * tries to release full stripe lock.
114                  *
115                  * No better way to resolve, but only to warn.
116                  */
117                 WARN_ON(!RB_EMPTY_ROOT(&cache->full_stripe_locks_root.root));
118                 kfree(cache->free_space_ctl);
119                 kfree(cache);
120         }
121 }
122
123 /*
124  * this adds the block group to the fs_info rb tree for the block group
125  * cache
126  */
127 static int btrfs_add_block_group_cache(struct btrfs_fs_info *info,
128                                 struct btrfs_block_group_cache *block_group)
129 {
130         struct rb_node **p;
131         struct rb_node *parent = NULL;
132         struct btrfs_block_group_cache *cache;
133
134         spin_lock(&info->block_group_cache_lock);
135         p = &info->block_group_cache_tree.rb_node;
136
137         while (*p) {
138                 parent = *p;
139                 cache = rb_entry(parent, struct btrfs_block_group_cache,
140                                  cache_node);
141                 if (block_group->key.objectid < cache->key.objectid) {
142                         p = &(*p)->rb_left;
143                 } else if (block_group->key.objectid > cache->key.objectid) {
144                         p = &(*p)->rb_right;
145                 } else {
146                         spin_unlock(&info->block_group_cache_lock);
147                         return -EEXIST;
148                 }
149         }
150
151         rb_link_node(&block_group->cache_node, parent, p);
152         rb_insert_color(&block_group->cache_node,
153                         &info->block_group_cache_tree);
154
155         if (info->first_logical_byte > block_group->key.objectid)
156                 info->first_logical_byte = block_group->key.objectid;
157
158         spin_unlock(&info->block_group_cache_lock);
159
160         return 0;
161 }
162
163 /*
164  * This will return the block group at or after bytenr if contains is 0, else
165  * it will return the block group that contains the bytenr
166  */
167 static struct btrfs_block_group_cache *
168 block_group_cache_tree_search(struct btrfs_fs_info *info, u64 bytenr,
169                               int contains)
170 {
171         struct btrfs_block_group_cache *cache, *ret = NULL;
172         struct rb_node *n;
173         u64 end, start;
174
175         spin_lock(&info->block_group_cache_lock);
176         n = info->block_group_cache_tree.rb_node;
177
178         while (n) {
179                 cache = rb_entry(n, struct btrfs_block_group_cache,
180                                  cache_node);
181                 end = cache->key.objectid + cache->key.offset - 1;
182                 start = cache->key.objectid;
183
184                 if (bytenr < start) {
185                         if (!contains && (!ret || start < ret->key.objectid))
186                                 ret = cache;
187                         n = n->rb_left;
188                 } else if (bytenr > start) {
189                         if (contains && bytenr <= end) {
190                                 ret = cache;
191                                 break;
192                         }
193                         n = n->rb_right;
194                 } else {
195                         ret = cache;
196                         break;
197                 }
198         }
199         if (ret) {
200                 btrfs_get_block_group(ret);
201                 if (bytenr == 0 && info->first_logical_byte > ret->key.objectid)
202                         info->first_logical_byte = ret->key.objectid;
203         }
204         spin_unlock(&info->block_group_cache_lock);
205
206         return ret;
207 }
208
209 static int add_excluded_extent(struct btrfs_fs_info *fs_info,
210                                u64 start, u64 num_bytes)
211 {
212         u64 end = start + num_bytes - 1;
213         set_extent_bits(&fs_info->freed_extents[0],
214                         start, end, EXTENT_UPTODATE);
215         set_extent_bits(&fs_info->freed_extents[1],
216                         start, end, EXTENT_UPTODATE);
217         return 0;
218 }
219
220 static void free_excluded_extents(struct btrfs_block_group_cache *cache)
221 {
222         struct btrfs_fs_info *fs_info = cache->fs_info;
223         u64 start, end;
224
225         start = cache->key.objectid;
226         end = start + cache->key.offset - 1;
227
228         clear_extent_bits(&fs_info->freed_extents[0],
229                           start, end, EXTENT_UPTODATE);
230         clear_extent_bits(&fs_info->freed_extents[1],
231                           start, end, EXTENT_UPTODATE);
232 }
233
234 static int exclude_super_stripes(struct btrfs_block_group_cache *cache)
235 {
236         struct btrfs_fs_info *fs_info = cache->fs_info;
237         u64 bytenr;
238         u64 *logical;
239         int stripe_len;
240         int i, nr, ret;
241
242         if (cache->key.objectid < BTRFS_SUPER_INFO_OFFSET) {
243                 stripe_len = BTRFS_SUPER_INFO_OFFSET - cache->key.objectid;
244                 cache->bytes_super += stripe_len;
245                 ret = add_excluded_extent(fs_info, cache->key.objectid,
246                                           stripe_len);
247                 if (ret)
248                         return ret;
249         }
250
251         for (i = 0; i < BTRFS_SUPER_MIRROR_MAX; i++) {
252                 bytenr = btrfs_sb_offset(i);
253                 ret = btrfs_rmap_block(fs_info, cache->key.objectid,
254                                        bytenr, &logical, &nr, &stripe_len);
255                 if (ret)
256                         return ret;
257
258                 while (nr--) {
259                         u64 start, len;
260
261                         if (logical[nr] > cache->key.objectid +
262                             cache->key.offset)
263                                 continue;
264
265                         if (logical[nr] + stripe_len <= cache->key.objectid)
266                                 continue;
267
268                         start = logical[nr];
269                         if (start < cache->key.objectid) {
270                                 start = cache->key.objectid;
271                                 len = (logical[nr] + stripe_len) - start;
272                         } else {
273                                 len = min_t(u64, stripe_len,
274                                             cache->key.objectid +
275                                             cache->key.offset - start);
276                         }
277
278                         cache->bytes_super += len;
279                         ret = add_excluded_extent(fs_info, start, len);
280                         if (ret) {
281                                 kfree(logical);
282                                 return ret;
283                         }
284                 }
285
286                 kfree(logical);
287         }
288         return 0;
289 }
290
291 static struct btrfs_caching_control *
292 get_caching_control(struct btrfs_block_group_cache *cache)
293 {
294         struct btrfs_caching_control *ctl;
295
296         spin_lock(&cache->lock);
297         if (!cache->caching_ctl) {
298                 spin_unlock(&cache->lock);
299                 return NULL;
300         }
301
302         ctl = cache->caching_ctl;
303         refcount_inc(&ctl->count);
304         spin_unlock(&cache->lock);
305         return ctl;
306 }
307
308 static void put_caching_control(struct btrfs_caching_control *ctl)
309 {
310         if (refcount_dec_and_test(&ctl->count))
311                 kfree(ctl);
312 }
313
314 #ifdef CONFIG_BTRFS_DEBUG
315 static void fragment_free_space(struct btrfs_block_group_cache *block_group)
316 {
317         struct btrfs_fs_info *fs_info = block_group->fs_info;
318         u64 start = block_group->key.objectid;
319         u64 len = block_group->key.offset;
320         u64 chunk = block_group->flags & BTRFS_BLOCK_GROUP_METADATA ?
321                 fs_info->nodesize : fs_info->sectorsize;
322         u64 step = chunk << 1;
323
324         while (len > chunk) {
325                 btrfs_remove_free_space(block_group, start, chunk);
326                 start += step;
327                 if (len < step)
328                         len = 0;
329                 else
330                         len -= step;
331         }
332 }
333 #endif
334
335 /*
336  * this is only called by cache_block_group, since we could have freed extents
337  * we need to check the pinned_extents for any extents that can't be used yet
338  * since their free space will be released as soon as the transaction commits.
339  */
340 u64 add_new_free_space(struct btrfs_block_group_cache *block_group,
341                        u64 start, u64 end)
342 {
343         struct btrfs_fs_info *info = block_group->fs_info;
344         u64 extent_start, extent_end, size, total_added = 0;
345         int ret;
346
347         while (start < end) {
348                 ret = find_first_extent_bit(info->pinned_extents, start,
349                                             &extent_start, &extent_end,
350                                             EXTENT_DIRTY | EXTENT_UPTODATE,
351                                             NULL);
352                 if (ret)
353                         break;
354
355                 if (extent_start <= start) {
356                         start = extent_end + 1;
357                 } else if (extent_start > start && extent_start < end) {
358                         size = extent_start - start;
359                         total_added += size;
360                         ret = btrfs_add_free_space(block_group, start,
361                                                    size);
362                         BUG_ON(ret); /* -ENOMEM or logic error */
363                         start = extent_end + 1;
364                 } else {
365                         break;
366                 }
367         }
368
369         if (start < end) {
370                 size = end - start;
371                 total_added += size;
372                 ret = btrfs_add_free_space(block_group, start, size);
373                 BUG_ON(ret); /* -ENOMEM or logic error */
374         }
375
376         return total_added;
377 }
378
379 static int load_extent_tree_free(struct btrfs_caching_control *caching_ctl)
380 {
381         struct btrfs_block_group_cache *block_group = caching_ctl->block_group;
382         struct btrfs_fs_info *fs_info = block_group->fs_info;
383         struct btrfs_root *extent_root = fs_info->extent_root;
384         struct btrfs_path *path;
385         struct extent_buffer *leaf;
386         struct btrfs_key key;
387         u64 total_found = 0;
388         u64 last = 0;
389         u32 nritems;
390         int ret;
391         bool wakeup = true;
392
393         path = btrfs_alloc_path();
394         if (!path)
395                 return -ENOMEM;
396
397         last = max_t(u64, block_group->key.objectid, BTRFS_SUPER_INFO_OFFSET);
398
399 #ifdef CONFIG_BTRFS_DEBUG
400         /*
401          * If we're fragmenting we don't want to make anybody think we can
402          * allocate from this block group until we've had a chance to fragment
403          * the free space.
404          */
405         if (btrfs_should_fragment_free_space(block_group))
406                 wakeup = false;
407 #endif
408         /*
409          * We don't want to deadlock with somebody trying to allocate a new
410          * extent for the extent root while also trying to search the extent
411          * root to add free space.  So we skip locking and search the commit
412          * root, since its read-only
413          */
414         path->skip_locking = 1;
415         path->search_commit_root = 1;
416         path->reada = READA_FORWARD;
417
418         key.objectid = last;
419         key.offset = 0;
420         key.type = BTRFS_EXTENT_ITEM_KEY;
421
422 next:
423         ret = btrfs_search_slot(NULL, extent_root, &key, path, 0, 0);
424         if (ret < 0)
425                 goto out;
426
427         leaf = path->nodes[0];
428         nritems = btrfs_header_nritems(leaf);
429
430         while (1) {
431                 if (btrfs_fs_closing(fs_info) > 1) {
432                         last = (u64)-1;
433                         break;
434                 }
435
436                 if (path->slots[0] < nritems) {
437                         btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);
438                 } else {
439                         ret = find_next_key(path, 0, &key);
440                         if (ret)
441                                 break;
442
443                         if (need_resched() ||
444                             rwsem_is_contended(&fs_info->commit_root_sem)) {
445                                 if (wakeup)
446                                         caching_ctl->progress = last;
447                                 btrfs_release_path(path);
448                                 up_read(&fs_info->commit_root_sem);
449                                 mutex_unlock(&caching_ctl->mutex);
450                                 cond_resched();
451                                 mutex_lock(&caching_ctl->mutex);
452                                 down_read(&fs_info->commit_root_sem);
453                                 goto next;
454                         }
455
456                         ret = btrfs_next_leaf(extent_root, path);
457                         if (ret < 0)
458                                 goto out;
459                         if (ret)
460                                 break;
461                         leaf = path->nodes[0];
462                         nritems = btrfs_header_nritems(leaf);
463                         continue;
464                 }
465
466                 if (key.objectid < last) {
467                         key.objectid = last;
468                         key.offset = 0;
469                         key.type = BTRFS_EXTENT_ITEM_KEY;
470
471                         if (wakeup)
472                                 caching_ctl->progress = last;
473                         btrfs_release_path(path);
474                         goto next;
475                 }
476
477                 if (key.objectid < block_group->key.objectid) {
478                         path->slots[0]++;
479                         continue;
480                 }
481
482                 if (key.objectid >= block_group->key.objectid +
483                     block_group->key.offset)
484                         break;
485
486                 if (key.type == BTRFS_EXTENT_ITEM_KEY ||
487                     key.type == BTRFS_METADATA_ITEM_KEY) {
488                         total_found += add_new_free_space(block_group, last,
489                                                           key.objectid);
490                         if (key.type == BTRFS_METADATA_ITEM_KEY)
491                                 last = key.objectid +
492                                         fs_info->nodesize;
493                         else
494                                 last = key.objectid + key.offset;
495
496                         if (total_found > CACHING_CTL_WAKE_UP) {
497                                 total_found = 0;
498                                 if (wakeup)
499                                         wake_up(&caching_ctl->wait);
500                         }
501                 }
502                 path->slots[0]++;
503         }
504         ret = 0;
505
506         total_found += add_new_free_space(block_group, last,
507                                           block_group->key.objectid +
508                                           block_group->key.offset);
509         caching_ctl->progress = (u64)-1;
510
511 out:
512         btrfs_free_path(path);
513         return ret;
514 }
515
516 static noinline void caching_thread(struct btrfs_work *work)
517 {
518         struct btrfs_block_group_cache *block_group;
519         struct btrfs_fs_info *fs_info;
520         struct btrfs_caching_control *caching_ctl;
521         int ret;
522
523         caching_ctl = container_of(work, struct btrfs_caching_control, work);
524         block_group = caching_ctl->block_group;
525         fs_info = block_group->fs_info;
526
527         mutex_lock(&caching_ctl->mutex);
528         down_read(&fs_info->commit_root_sem);
529
530         if (btrfs_fs_compat_ro(fs_info, FREE_SPACE_TREE))
531                 ret = load_free_space_tree(caching_ctl);
532         else
533                 ret = load_extent_tree_free(caching_ctl);
534
535         spin_lock(&block_group->lock);
536         block_group->caching_ctl = NULL;
537         block_group->cached = ret ? BTRFS_CACHE_ERROR : BTRFS_CACHE_FINISHED;
538         spin_unlock(&block_group->lock);
539
540 #ifdef CONFIG_BTRFS_DEBUG
541         if (btrfs_should_fragment_free_space(block_group)) {
542                 u64 bytes_used;
543
544                 spin_lock(&block_group->space_info->lock);
545                 spin_lock(&block_group->lock);
546                 bytes_used = block_group->key.offset -
547                         btrfs_block_group_used(&block_group->item);
548                 block_group->space_info->bytes_used += bytes_used >> 1;
549                 spin_unlock(&block_group->lock);
550                 spin_unlock(&block_group->space_info->lock);
551                 fragment_free_space(block_group);
552         }
553 #endif
554
555         caching_ctl->progress = (u64)-1;
556
557         up_read(&fs_info->commit_root_sem);
558         free_excluded_extents(block_group);
559         mutex_unlock(&caching_ctl->mutex);
560
561         wake_up(&caching_ctl->wait);
562
563         put_caching_control(caching_ctl);
564         btrfs_put_block_group(block_group);
565 }
566
567 static int cache_block_group(struct btrfs_block_group_cache *cache,
568                              int load_cache_only)
569 {
570         DEFINE_WAIT(wait);
571         struct btrfs_fs_info *fs_info = cache->fs_info;
572         struct btrfs_caching_control *caching_ctl;
573         int ret = 0;
574
575         caching_ctl = kzalloc(sizeof(*caching_ctl), GFP_NOFS);
576         if (!caching_ctl)
577                 return -ENOMEM;
578
579         INIT_LIST_HEAD(&caching_ctl->list);
580         mutex_init(&caching_ctl->mutex);
581         init_waitqueue_head(&caching_ctl->wait);
582         caching_ctl->block_group = cache;
583         caching_ctl->progress = cache->key.objectid;
584         refcount_set(&caching_ctl->count, 1);
585         btrfs_init_work(&caching_ctl->work, btrfs_cache_helper,
586                         caching_thread, NULL, NULL);
587
588         spin_lock(&cache->lock);
589         /*
590          * This should be a rare occasion, but this could happen I think in the
591          * case where one thread starts to load the space cache info, and then
592          * some other thread starts a transaction commit which tries to do an
593          * allocation while the other thread is still loading the space cache
594          * info.  The previous loop should have kept us from choosing this block
595          * group, but if we've moved to the state where we will wait on caching
596          * block groups we need to first check if we're doing a fast load here,
597          * so we can wait for it to finish, otherwise we could end up allocating
598          * from a block group who's cache gets evicted for one reason or
599          * another.
600          */
601         while (cache->cached == BTRFS_CACHE_FAST) {
602                 struct btrfs_caching_control *ctl;
603
604                 ctl = cache->caching_ctl;
605                 refcount_inc(&ctl->count);
606                 prepare_to_wait(&ctl->wait, &wait, TASK_UNINTERRUPTIBLE);
607                 spin_unlock(&cache->lock);
608
609                 schedule();
610
611                 finish_wait(&ctl->wait, &wait);
612                 put_caching_control(ctl);
613                 spin_lock(&cache->lock);
614         }
615
616         if (cache->cached != BTRFS_CACHE_NO) {
617                 spin_unlock(&cache->lock);
618                 kfree(caching_ctl);
619                 return 0;
620         }
621         WARN_ON(cache->caching_ctl);
622         cache->caching_ctl = caching_ctl;
623         cache->cached = BTRFS_CACHE_FAST;
624         spin_unlock(&cache->lock);
625
626         if (btrfs_test_opt(fs_info, SPACE_CACHE)) {
627                 mutex_lock(&caching_ctl->mutex);
628                 ret = load_free_space_cache(fs_info, cache);
629
630                 spin_lock(&cache->lock);
631                 if (ret == 1) {
632                         cache->caching_ctl = NULL;
633                         cache->cached = BTRFS_CACHE_FINISHED;
634                         cache->last_byte_to_unpin = (u64)-1;
635                         caching_ctl->progress = (u64)-1;
636                 } else {
637                         if (load_cache_only) {
638                                 cache->caching_ctl = NULL;
639                                 cache->cached = BTRFS_CACHE_NO;
640                         } else {
641                                 cache->cached = BTRFS_CACHE_STARTED;
642                                 cache->has_caching_ctl = 1;
643                         }
644                 }
645                 spin_unlock(&cache->lock);
646 #ifdef CONFIG_BTRFS_DEBUG
647                 if (ret == 1 &&
648                     btrfs_should_fragment_free_space(cache)) {
649                         u64 bytes_used;
650
651                         spin_lock(&cache->space_info->lock);
652                         spin_lock(&cache->lock);
653                         bytes_used = cache->key.offset -
654                                 btrfs_block_group_used(&cache->item);
655                         cache->space_info->bytes_used += bytes_used >> 1;
656                         spin_unlock(&cache->lock);
657                         spin_unlock(&cache->space_info->lock);
658                         fragment_free_space(cache);
659                 }
660 #endif
661                 mutex_unlock(&caching_ctl->mutex);
662
663                 wake_up(&caching_ctl->wait);
664                 if (ret == 1) {
665                         put_caching_control(caching_ctl);
666                         free_excluded_extents(cache);
667                         return 0;
668                 }
669         } else {
670                 /*
671                  * We're either using the free space tree or no caching at all.
672                  * Set cached to the appropriate value and wakeup any waiters.
673                  */
674                 spin_lock(&cache->lock);
675                 if (load_cache_only) {
676                         cache->caching_ctl = NULL;
677                         cache->cached = BTRFS_CACHE_NO;
678                 } else {
679                         cache->cached = BTRFS_CACHE_STARTED;
680                         cache->has_caching_ctl = 1;
681                 }
682                 spin_unlock(&cache->lock);
683                 wake_up(&caching_ctl->wait);
684         }
685
686         if (load_cache_only) {
687                 put_caching_control(caching_ctl);
688                 return 0;
689         }
690
691         down_write(&fs_info->commit_root_sem);
692         refcount_inc(&caching_ctl->count);
693         list_add_tail(&caching_ctl->list, &fs_info->caching_block_groups);
694         up_write(&fs_info->commit_root_sem);
695
696         btrfs_get_block_group(cache);
697
698         btrfs_queue_work(fs_info->caching_workers, &caching_ctl->work);
699
700         return ret;
701 }
702
703 /*
704  * return the block group that starts at or after bytenr
705  */
706 static struct btrfs_block_group_cache *
707 btrfs_lookup_first_block_group(struct btrfs_fs_info *info, u64 bytenr)
708 {
709         return block_group_cache_tree_search(info, bytenr, 0);
710 }
711
712 /*
713  * return the block group that contains the given bytenr
714  */
715 struct btrfs_block_group_cache *btrfs_lookup_block_group(
716                                                  struct btrfs_fs_info *info,
717                                                  u64 bytenr)
718 {
719         return block_group_cache_tree_search(info, bytenr, 1);
720 }
721
722 static struct btrfs_space_info *__find_space_info(struct btrfs_fs_info *info,
723                                                   u64 flags)
724 {
725         struct list_head *head = &info->space_info;
726         struct btrfs_space_info *found;
727
728         flags &= BTRFS_BLOCK_GROUP_TYPE_MASK;
729
730         rcu_read_lock();
731         list_for_each_entry_rcu(found, head, list) {
732                 if (found->flags & flags) {
733                         rcu_read_unlock();
734                         return found;
735                 }
736         }
737         rcu_read_unlock();
738         return NULL;
739 }
740
741 static void add_pinned_bytes(struct btrfs_fs_info *fs_info, s64 num_bytes,
742                              bool metadata, u64 root_objectid)
743 {
744         struct btrfs_space_info *space_info;
745         u64 flags;
746
747         if (metadata) {
748                 if (root_objectid == BTRFS_CHUNK_TREE_OBJECTID)
749                         flags = BTRFS_BLOCK_GROUP_SYSTEM;
750                 else
751                         flags = BTRFS_BLOCK_GROUP_METADATA;
752         } else {
753                 flags = BTRFS_BLOCK_GROUP_DATA;
754         }
755
756         space_info = __find_space_info(fs_info, flags);
757         ASSERT(space_info);
758         percpu_counter_add_batch(&space_info->total_bytes_pinned, num_bytes,
759                     BTRFS_TOTAL_BYTES_PINNED_BATCH);
760 }
761
762 /*
763  * after adding space to the filesystem, we need to clear the full flags
764  * on all the space infos.
765  */
766 void btrfs_clear_space_info_full(struct btrfs_fs_info *info)
767 {
768         struct list_head *head = &info->space_info;
769         struct btrfs_space_info *found;
770
771         rcu_read_lock();
772         list_for_each_entry_rcu(found, head, list)
773                 found->full = 0;
774         rcu_read_unlock();
775 }
776
777 /* simple helper to search for an existing data extent at a given offset */
778 int btrfs_lookup_data_extent(struct btrfs_fs_info *fs_info, u64 start, u64 len)
779 {
780         int ret;
781         struct btrfs_key key;
782         struct btrfs_path *path;
783
784         path = btrfs_alloc_path();
785         if (!path)
786                 return -ENOMEM;
787
788         key.objectid = start;
789         key.offset = len;
790         key.type = BTRFS_EXTENT_ITEM_KEY;
791         ret = btrfs_search_slot(NULL, fs_info->extent_root, &key, path, 0, 0);
792         btrfs_free_path(path);
793         return ret;
794 }
795
796 /*
797  * helper function to lookup reference count and flags of a tree block.
798  *
799  * the head node for delayed ref is used to store the sum of all the
800  * reference count modifications queued up in the rbtree. the head
801  * node may also store the extent flags to set. This way you can check
802  * to see what the reference count and extent flags would be if all of
803  * the delayed refs are not processed.
804  */
805 int btrfs_lookup_extent_info(struct btrfs_trans_handle *trans,
806                              struct btrfs_fs_info *fs_info, u64 bytenr,
807                              u64 offset, int metadata, u64 *refs, u64 *flags)
808 {
809         struct btrfs_delayed_ref_head *head;
810         struct btrfs_delayed_ref_root *delayed_refs;
811         struct btrfs_path *path;
812         struct btrfs_extent_item *ei;
813         struct extent_buffer *leaf;
814         struct btrfs_key key;
815         u32 item_size;
816         u64 num_refs;
817         u64 extent_flags;
818         int ret;
819
820         /*
821          * If we don't have skinny metadata, don't bother doing anything
822          * different
823          */
824         if (metadata && !btrfs_fs_incompat(fs_info, SKINNY_METADATA)) {
825                 offset = fs_info->nodesize;
826                 metadata = 0;
827         }
828
829         path = btrfs_alloc_path();
830         if (!path)
831                 return -ENOMEM;
832
833         if (!trans) {
834                 path->skip_locking = 1;
835                 path->search_commit_root = 1;
836         }
837
838 search_again:
839         key.objectid = bytenr;
840         key.offset = offset;
841         if (metadata)
842                 key.type = BTRFS_METADATA_ITEM_KEY;
843         else
844                 key.type = BTRFS_EXTENT_ITEM_KEY;
845
846         ret = btrfs_search_slot(trans, fs_info->extent_root, &key, path, 0, 0);
847         if (ret < 0)
848                 goto out_free;
849
850         if (ret > 0 && metadata && key.type == BTRFS_METADATA_ITEM_KEY) {
851                 if (path->slots[0]) {
852                         path->slots[0]--;
853                         btrfs_item_key_to_cpu(path->nodes[0], &key,
854                                               path->slots[0]);
855                         if (key.objectid == bytenr &&
856                             key.type == BTRFS_EXTENT_ITEM_KEY &&
857                             key.offset == fs_info->nodesize)
858                                 ret = 0;
859                 }
860         }
861
862         if (ret == 0) {
863                 leaf = path->nodes[0];
864                 item_size = btrfs_item_size_nr(leaf, path->slots[0]);
865                 if (item_size >= sizeof(*ei)) {
866                         ei = btrfs_item_ptr(leaf, path->slots[0],
867                                             struct btrfs_extent_item);
868                         num_refs = btrfs_extent_refs(leaf, ei);
869                         extent_flags = btrfs_extent_flags(leaf, ei);
870                 } else {
871                         ret = -EINVAL;
872                         btrfs_print_v0_err(fs_info);
873                         if (trans)
874                                 btrfs_abort_transaction(trans, ret);
875                         else
876                                 btrfs_handle_fs_error(fs_info, ret, NULL);
877
878                         goto out_free;
879                 }
880
881                 BUG_ON(num_refs == 0);
882         } else {
883                 num_refs = 0;
884                 extent_flags = 0;
885                 ret = 0;
886         }
887
888         if (!trans)
889                 goto out;
890
891         delayed_refs = &trans->transaction->delayed_refs;
892         spin_lock(&delayed_refs->lock);
893         head = btrfs_find_delayed_ref_head(delayed_refs, bytenr);
894         if (head) {
895                 if (!mutex_trylock(&head->mutex)) {
896                         refcount_inc(&head->refs);
897                         spin_unlock(&delayed_refs->lock);
898
899                         btrfs_release_path(path);
900
901                         /*
902                          * Mutex was contended, block until it's released and try
903                          * again
904                          */
905                         mutex_lock(&head->mutex);
906                         mutex_unlock(&head->mutex);
907                         btrfs_put_delayed_ref_head(head);
908                         goto search_again;
909                 }
910                 spin_lock(&head->lock);
911                 if (head->extent_op && head->extent_op->update_flags)
912                         extent_flags |= head->extent_op->flags_to_set;
913                 else
914                         BUG_ON(num_refs == 0);
915
916                 num_refs += head->ref_mod;
917                 spin_unlock(&head->lock);
918                 mutex_unlock(&head->mutex);
919         }
920         spin_unlock(&delayed_refs->lock);
921 out:
922         WARN_ON(num_refs == 0);
923         if (refs)
924                 *refs = num_refs;
925         if (flags)
926                 *flags = extent_flags;
927 out_free:
928         btrfs_free_path(path);
929         return ret;
930 }
931
932 /*
933  * Back reference rules.  Back refs have three main goals:
934  *
935  * 1) differentiate between all holders of references to an extent so that
936  *    when a reference is dropped we can make sure it was a valid reference
937  *    before freeing the extent.
938  *
939  * 2) Provide enough information to quickly find the holders of an extent
940  *    if we notice a given block is corrupted or bad.
941  *
942  * 3) Make it easy to migrate blocks for FS shrinking or storage pool
943  *    maintenance.  This is actually the same as #2, but with a slightly
944  *    different use case.
945  *
946  * There are two kinds of back refs. The implicit back refs is optimized
947  * for pointers in non-shared tree blocks. For a given pointer in a block,
948  * back refs of this kind provide information about the block's owner tree
949  * and the pointer's key. These information allow us to find the block by
950  * b-tree searching. The full back refs is for pointers in tree blocks not
951  * referenced by their owner trees. The location of tree block is recorded
952  * in the back refs. Actually the full back refs is generic, and can be
953  * used in all cases the implicit back refs is used. The major shortcoming
954  * of the full back refs is its overhead. Every time a tree block gets
955  * COWed, we have to update back refs entry for all pointers in it.
956  *
957  * For a newly allocated tree block, we use implicit back refs for
958  * pointers in it. This means most tree related operations only involve
959  * implicit back refs. For a tree block created in old transaction, the
960  * only way to drop a reference to it is COW it. So we can detect the
961  * event that tree block loses its owner tree's reference and do the
962  * back refs conversion.
963  *
964  * When a tree block is COWed through a tree, there are four cases:
965  *
966  * The reference count of the block is one and the tree is the block's
967  * owner tree. Nothing to do in this case.
968  *
969  * The reference count of the block is one and the tree is not the
970  * block's owner tree. In this case, full back refs is used for pointers
971  * in the block. Remove these full back refs, add implicit back refs for
972  * every pointers in the new block.
973  *
974  * The reference count of the block is greater than one and the tree is
975  * the block's owner tree. In this case, implicit back refs is used for
976  * pointers in the block. Add full back refs for every pointers in the
977  * block, increase lower level extents' reference counts. The original
978  * implicit back refs are entailed to the new block.
979  *
980  * The reference count of the block is greater than one and the tree is
981  * not the block's owner tree. Add implicit back refs for every pointer in
982  * the new block, increase lower level extents' reference count.
983  *
984  * Back Reference Key composing:
985  *
986  * The key objectid corresponds to the first byte in the extent,
987  * The key type is used to differentiate between types of back refs.
988  * There are different meanings of the key offset for different types
989  * of back refs.
990  *
991  * File extents can be referenced by:
992  *
993  * - multiple snapshots, subvolumes, or different generations in one subvol
994  * - different files inside a single subvolume
995  * - different offsets inside a file (bookend extents in file.c)
996  *
997  * The extent ref structure for the implicit back refs has fields for:
998  *
999  * - Objectid of the subvolume root
1000  * - objectid of the file holding the reference
1001  * - original offset in the file
1002  * - how many bookend extents
1003  *
1004  * The key offset for the implicit back refs is hash of the first
1005  * three fields.
1006  *
1007  * The extent ref structure for the full back refs has field for:
1008  *
1009  * - number of pointers in the tree leaf
1010  *
1011  * The key offset for the implicit back refs is the first byte of
1012  * the tree leaf
1013  *
1014  * When a file extent is allocated, The implicit back refs is used.
1015  * the fields are filled in:
1016  *
1017  *     (root_key.objectid, inode objectid, offset in file, 1)
1018  *
1019  * When a file extent is removed file truncation, we find the
1020  * corresponding implicit back refs and check the following fields:
1021  *
1022  *     (btrfs_header_owner(leaf), inode objectid, offset in file)
1023  *
1024  * Btree extents can be referenced by:
1025  *
1026  * - Different subvolumes
1027  *
1028  * Both the implicit back refs and the full back refs for tree blocks
1029  * only consist of key. The key offset for the implicit back refs is
1030  * objectid of block's owner tree. The key offset for the full back refs
1031  * is the first byte of parent block.
1032  *
1033  * When implicit back refs is used, information about the lowest key and
1034  * level of the tree block are required. These information are stored in
1035  * tree block info structure.
1036  */
1037
1038 /*
1039  * is_data == BTRFS_REF_TYPE_BLOCK, tree block type is required,
1040  * is_data == BTRFS_REF_TYPE_DATA, data type is requried,
1041  * is_data == BTRFS_REF_TYPE_ANY, either type is OK.
1042  */
1043 int btrfs_get_extent_inline_ref_type(const struct extent_buffer *eb,
1044                                      struct btrfs_extent_inline_ref *iref,
1045                                      enum btrfs_inline_ref_type is_data)
1046 {
1047         int type = btrfs_extent_inline_ref_type(eb, iref);
1048         u64 offset = btrfs_extent_inline_ref_offset(eb, iref);
1049
1050         if (type == BTRFS_TREE_BLOCK_REF_KEY ||
1051             type == BTRFS_SHARED_BLOCK_REF_KEY ||
1052             type == BTRFS_SHARED_DATA_REF_KEY ||
1053             type == BTRFS_EXTENT_DATA_REF_KEY) {
1054                 if (is_data == BTRFS_REF_TYPE_BLOCK) {
1055                         if (type == BTRFS_TREE_BLOCK_REF_KEY)
1056                                 return type;
1057                         if (type == BTRFS_SHARED_BLOCK_REF_KEY) {
1058                                 ASSERT(eb->fs_info);
1059                                 /*
1060                                  * Every shared one has parent tree
1061                                  * block, which must be aligned to
1062                                  * nodesize.
1063                                  */
1064                                 if (offset &&
1065                                     IS_ALIGNED(offset, eb->fs_info->nodesize))
1066                                         return type;
1067                         }
1068                 } else if (is_data == BTRFS_REF_TYPE_DATA) {
1069                         if (type == BTRFS_EXTENT_DATA_REF_KEY)
1070                                 return type;
1071                         if (type == BTRFS_SHARED_DATA_REF_KEY) {
1072                                 ASSERT(eb->fs_info);
1073                                 /*
1074                                  * Every shared one has parent tree
1075                                  * block, which must be aligned to
1076                                  * nodesize.
1077                                  */
1078                                 if (offset &&
1079                                     IS_ALIGNED(offset, eb->fs_info->nodesize))
1080                                         return type;
1081                         }
1082                 } else {
1083                         ASSERT(is_data == BTRFS_REF_TYPE_ANY);
1084                         return type;
1085                 }
1086         }
1087
1088         btrfs_print_leaf((struct extent_buffer *)eb);
1089         btrfs_err(eb->fs_info, "eb %llu invalid extent inline ref type %d",
1090                   eb->start, type);
1091         WARN_ON(1);
1092
1093         return BTRFS_REF_TYPE_INVALID;
1094 }
1095
1096 static u64 hash_extent_data_ref(u64 root_objectid, u64 owner, u64 offset)
1097 {
1098         u32 high_crc = ~(u32)0;
1099         u32 low_crc = ~(u32)0;
1100         __le64 lenum;
1101
1102         lenum = cpu_to_le64(root_objectid);
1103         high_crc = crc32c(high_crc, &lenum, sizeof(lenum));
1104         lenum = cpu_to_le64(owner);
1105         low_crc = crc32c(low_crc, &lenum, sizeof(lenum));
1106         lenum = cpu_to_le64(offset);
1107         low_crc = crc32c(low_crc, &lenum, sizeof(lenum));
1108
1109         return ((u64)high_crc << 31) ^ (u64)low_crc;
1110 }
1111
1112 static u64 hash_extent_data_ref_item(struct extent_buffer *leaf,
1113                                      struct btrfs_extent_data_ref *ref)
1114 {
1115         return hash_extent_data_ref(btrfs_extent_data_ref_root(leaf, ref),
1116                                     btrfs_extent_data_ref_objectid(leaf, ref),
1117                                     btrfs_extent_data_ref_offset(leaf, ref));
1118 }
1119
1120 static int match_extent_data_ref(struct extent_buffer *leaf,
1121                                  struct btrfs_extent_data_ref *ref,
1122                                  u64 root_objectid, u64 owner, u64 offset)
1123 {
1124         if (btrfs_extent_data_ref_root(leaf, ref) != root_objectid ||
1125             btrfs_extent_data_ref_objectid(leaf, ref) != owner ||
1126             btrfs_extent_data_ref_offset(leaf, ref) != offset)
1127                 return 0;
1128         return 1;
1129 }
1130
1131 static noinline int lookup_extent_data_ref(struct btrfs_trans_handle *trans,
1132                                            struct btrfs_path *path,
1133                                            u64 bytenr, u64 parent,
1134                                            u64 root_objectid,
1135                                            u64 owner, u64 offset)
1136 {
1137         struct btrfs_root *root = trans->fs_info->extent_root;
1138         struct btrfs_key key;
1139         struct btrfs_extent_data_ref *ref;
1140         struct extent_buffer *leaf;
1141         u32 nritems;
1142         int ret;
1143         int recow;
1144         int err = -ENOENT;
1145
1146         key.objectid = bytenr;
1147         if (parent) {
1148                 key.type = BTRFS_SHARED_DATA_REF_KEY;
1149                 key.offset = parent;
1150         } else {
1151                 key.type = BTRFS_EXTENT_DATA_REF_KEY;
1152                 key.offset = hash_extent_data_ref(root_objectid,
1153                                                   owner, offset);
1154         }
1155 again:
1156         recow = 0;
1157         ret = btrfs_search_slot(trans, root, &key, path, -1, 1);
1158         if (ret < 0) {
1159                 err = ret;
1160                 goto fail;
1161         }
1162
1163         if (parent) {
1164                 if (!ret)
1165                         return 0;
1166                 goto fail;
1167         }
1168
1169         leaf = path->nodes[0];
1170         nritems = btrfs_header_nritems(leaf);
1171         while (1) {
1172                 if (path->slots[0] >= nritems) {
1173                         ret = btrfs_next_leaf(root, path);
1174                         if (ret < 0)
1175                                 err = ret;
1176                         if (ret)
1177                                 goto fail;
1178
1179                         leaf = path->nodes[0];
1180                         nritems = btrfs_header_nritems(leaf);
1181                         recow = 1;
1182                 }
1183
1184                 btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);
1185                 if (key.objectid != bytenr ||
1186                     key.type != BTRFS_EXTENT_DATA_REF_KEY)
1187                         goto fail;
1188
1189                 ref = btrfs_item_ptr(leaf, path->slots[0],
1190                                      struct btrfs_extent_data_ref);
1191
1192                 if (match_extent_data_ref(leaf, ref, root_objectid,
1193                                           owner, offset)) {
1194                         if (recow) {
1195                                 btrfs_release_path(path);
1196                                 goto again;
1197                         }
1198                         err = 0;
1199                         break;
1200                 }
1201                 path->slots[0]++;
1202         }
1203 fail:
1204         return err;
1205 }
1206
1207 static noinline int insert_extent_data_ref(struct btrfs_trans_handle *trans,
1208                                            struct btrfs_path *path,
1209                                            u64 bytenr, u64 parent,
1210                                            u64 root_objectid, u64 owner,
1211                                            u64 offset, int refs_to_add)
1212 {
1213         struct btrfs_root *root = trans->fs_info->extent_root;
1214         struct btrfs_key key;
1215         struct extent_buffer *leaf;
1216         u32 size;
1217         u32 num_refs;
1218         int ret;
1219
1220         key.objectid = bytenr;
1221         if (parent) {
1222                 key.type = BTRFS_SHARED_DATA_REF_KEY;
1223                 key.offset = parent;
1224                 size = sizeof(struct btrfs_shared_data_ref);
1225         } else {
1226                 key.type = BTRFS_EXTENT_DATA_REF_KEY;
1227                 key.offset = hash_extent_data_ref(root_objectid,
1228                                                   owner, offset);
1229                 size = sizeof(struct btrfs_extent_data_ref);
1230         }
1231
1232         ret = btrfs_insert_empty_item(trans, root, path, &key, size);
1233         if (ret && ret != -EEXIST)
1234                 goto fail;
1235
1236         leaf = path->nodes[0];
1237         if (parent) {
1238                 struct btrfs_shared_data_ref *ref;
1239                 ref = btrfs_item_ptr(leaf, path->slots[0],
1240                                      struct btrfs_shared_data_ref);
1241                 if (ret == 0) {
1242                         btrfs_set_shared_data_ref_count(leaf, ref, refs_to_add);
1243                 } else {
1244                         num_refs = btrfs_shared_data_ref_count(leaf, ref);
1245                         num_refs += refs_to_add;
1246                         btrfs_set_shared_data_ref_count(leaf, ref, num_refs);
1247                 }
1248         } else {
1249                 struct btrfs_extent_data_ref *ref;
1250                 while (ret == -EEXIST) {
1251                         ref = btrfs_item_ptr(leaf, path->slots[0],
1252                                              struct btrfs_extent_data_ref);
1253                         if (match_extent_data_ref(leaf, ref, root_objectid,
1254                                                   owner, offset))
1255                                 break;
1256                         btrfs_release_path(path);
1257                         key.offset++;
1258                         ret = btrfs_insert_empty_item(trans, root, path, &key,
1259                                                       size);
1260                         if (ret && ret != -EEXIST)
1261                                 goto fail;
1262
1263                         leaf = path->nodes[0];
1264                 }
1265                 ref = btrfs_item_ptr(leaf, path->slots[0],
1266                                      struct btrfs_extent_data_ref);
1267                 if (ret == 0) {
1268                         btrfs_set_extent_data_ref_root(leaf, ref,
1269                                                        root_objectid);
1270                         btrfs_set_extent_data_ref_objectid(leaf, ref, owner);
1271                         btrfs_set_extent_data_ref_offset(leaf, ref, offset);
1272                         btrfs_set_extent_data_ref_count(leaf, ref, refs_to_add);
1273                 } else {
1274                         num_refs = btrfs_extent_data_ref_count(leaf, ref);
1275                         num_refs += refs_to_add;
1276                         btrfs_set_extent_data_ref_count(leaf, ref, num_refs);
1277                 }
1278         }
1279         btrfs_mark_buffer_dirty(leaf);
1280         ret = 0;
1281 fail:
1282         btrfs_release_path(path);
1283         return ret;
1284 }
1285
1286 static noinline int remove_extent_data_ref(struct btrfs_trans_handle *trans,
1287                                            struct btrfs_path *path,
1288                                            int refs_to_drop, int *last_ref)
1289 {
1290         struct btrfs_key key;
1291         struct btrfs_extent_data_ref *ref1 = NULL;
1292         struct btrfs_shared_data_ref *ref2 = NULL;
1293         struct extent_buffer *leaf;
1294         u32 num_refs = 0;
1295         int ret = 0;
1296
1297         leaf = path->nodes[0];
1298         btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);
1299
1300         if (key.type == BTRFS_EXTENT_DATA_REF_KEY) {
1301                 ref1 = btrfs_item_ptr(leaf, path->slots[0],
1302                                       struct btrfs_extent_data_ref);
1303                 num_refs = btrfs_extent_data_ref_count(leaf, ref1);
1304         } else if (key.type == BTRFS_SHARED_DATA_REF_KEY) {
1305                 ref2 = btrfs_item_ptr(leaf, path->slots[0],
1306                                       struct btrfs_shared_data_ref);
1307                 num_refs = btrfs_shared_data_ref_count(leaf, ref2);
1308         } else if (unlikely(key.type == BTRFS_EXTENT_REF_V0_KEY)) {
1309                 btrfs_print_v0_err(trans->fs_info);
1310                 btrfs_abort_transaction(trans, -EINVAL);
1311                 return -EINVAL;
1312         } else {
1313                 BUG();
1314         }
1315
1316         BUG_ON(num_refs < refs_to_drop);
1317         num_refs -= refs_to_drop;
1318
1319         if (num_refs == 0) {
1320                 ret = btrfs_del_item(trans, trans->fs_info->extent_root, path);
1321                 *last_ref = 1;
1322         } else {
1323                 if (key.type == BTRFS_EXTENT_DATA_REF_KEY)
1324                         btrfs_set_extent_data_ref_count(leaf, ref1, num_refs);
1325                 else if (key.type == BTRFS_SHARED_DATA_REF_KEY)
1326                         btrfs_set_shared_data_ref_count(leaf, ref2, num_refs);
1327                 btrfs_mark_buffer_dirty(leaf);
1328         }
1329         return ret;
1330 }
1331
1332 static noinline u32 extent_data_ref_count(struct btrfs_path *path,
1333                                           struct btrfs_extent_inline_ref *iref)
1334 {
1335         struct btrfs_key key;
1336         struct extent_buffer *leaf;
1337         struct btrfs_extent_data_ref *ref1;
1338         struct btrfs_shared_data_ref *ref2;
1339         u32 num_refs = 0;
1340         int type;
1341
1342         leaf = path->nodes[0];
1343         btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);
1344
1345         BUG_ON(key.type == BTRFS_EXTENT_REF_V0_KEY);
1346         if (iref) {
1347                 /*
1348                  * If type is invalid, we should have bailed out earlier than
1349                  * this call.
1350                  */
1351                 type = btrfs_get_extent_inline_ref_type(leaf, iref, BTRFS_REF_TYPE_DATA);
1352                 ASSERT(type != BTRFS_REF_TYPE_INVALID);
1353                 if (type == BTRFS_EXTENT_DATA_REF_KEY) {
1354                         ref1 = (struct btrfs_extent_data_ref *)(&iref->offset);
1355                         num_refs = btrfs_extent_data_ref_count(leaf, ref1);
1356                 } else {
1357                         ref2 = (struct btrfs_shared_data_ref *)(iref + 1);
1358                         num_refs = btrfs_shared_data_ref_count(leaf, ref2);
1359                 }
1360         } else if (key.type == BTRFS_EXTENT_DATA_REF_KEY) {
1361                 ref1 = btrfs_item_ptr(leaf, path->slots[0],
1362                                       struct btrfs_extent_data_ref);
1363                 num_refs = btrfs_extent_data_ref_count(leaf, ref1);
1364         } else if (key.type == BTRFS_SHARED_DATA_REF_KEY) {
1365                 ref2 = btrfs_item_ptr(leaf, path->slots[0],
1366                                       struct btrfs_shared_data_ref);
1367                 num_refs = btrfs_shared_data_ref_count(leaf, ref2);
1368         } else {
1369                 WARN_ON(1);
1370         }
1371         return num_refs;
1372 }
1373
1374 static noinline int lookup_tree_block_ref(struct btrfs_trans_handle *trans,
1375                                           struct btrfs_path *path,
1376                                           u64 bytenr, u64 parent,
1377                                           u64 root_objectid)
1378 {
1379         struct btrfs_root *root = trans->fs_info->extent_root;
1380         struct btrfs_key key;
1381         int ret;
1382
1383         key.objectid = bytenr;
1384         if (parent) {
1385                 key.type = BTRFS_SHARED_BLOCK_REF_KEY;
1386                 key.offset = parent;
1387         } else {
1388                 key.type = BTRFS_TREE_BLOCK_REF_KEY;
1389                 key.offset = root_objectid;
1390         }
1391
1392         ret = btrfs_search_slot(trans, root, &key, path, -1, 1);
1393         if (ret > 0)
1394                 ret = -ENOENT;
1395         return ret;
1396 }
1397
1398 static noinline int insert_tree_block_ref(struct btrfs_trans_handle *trans,
1399                                           struct btrfs_path *path,
1400                                           u64 bytenr, u64 parent,
1401                                           u64 root_objectid)
1402 {
1403         struct btrfs_key key;
1404         int ret;
1405
1406         key.objectid = bytenr;
1407         if (parent) {
1408                 key.type = BTRFS_SHARED_BLOCK_REF_KEY;
1409                 key.offset = parent;
1410         } else {
1411                 key.type = BTRFS_TREE_BLOCK_REF_KEY;
1412                 key.offset = root_objectid;
1413         }
1414
1415         ret = btrfs_insert_empty_item(trans, trans->fs_info->extent_root,
1416                                       path, &key, 0);
1417         btrfs_release_path(path);
1418         return ret;
1419 }
1420
1421 static inline int extent_ref_type(u64 parent, u64 owner)
1422 {
1423         int type;
1424         if (owner < BTRFS_FIRST_FREE_OBJECTID) {
1425                 if (parent > 0)
1426                         type = BTRFS_SHARED_BLOCK_REF_KEY;
1427                 else
1428                         type = BTRFS_TREE_BLOCK_REF_KEY;
1429         } else {
1430                 if (parent > 0)
1431                         type = BTRFS_SHARED_DATA_REF_KEY;
1432                 else
1433                         type = BTRFS_EXTENT_DATA_REF_KEY;
1434         }
1435         return type;
1436 }
1437
1438 static int find_next_key(struct btrfs_path *path, int level,
1439                          struct btrfs_key *key)
1440
1441 {
1442         for (; level < BTRFS_MAX_LEVEL; level++) {
1443                 if (!path->nodes[level])
1444                         break;
1445                 if (path->slots[level] + 1 >=
1446                     btrfs_header_nritems(path->nodes[level]))
1447                         continue;
1448                 if (level == 0)
1449                         btrfs_item_key_to_cpu(path->nodes[level], key,
1450                                               path->slots[level] + 1);
1451                 else
1452                         btrfs_node_key_to_cpu(path->nodes[level], key,
1453                                               path->slots[level] + 1);
1454                 return 0;
1455         }
1456         return 1;
1457 }
1458
1459 /*
1460  * look for inline back ref. if back ref is found, *ref_ret is set
1461  * to the address of inline back ref, and 0 is returned.
1462  *
1463  * if back ref isn't found, *ref_ret is set to the address where it
1464  * should be inserted, and -ENOENT is returned.
1465  *
1466  * if insert is true and there are too many inline back refs, the path
1467  * points to the extent item, and -EAGAIN is returned.
1468  *
1469  * NOTE: inline back refs are ordered in the same way that back ref
1470  *       items in the tree are ordered.
1471  */
1472 static noinline_for_stack
1473 int lookup_inline_extent_backref(struct btrfs_trans_handle *trans,
1474                                  struct btrfs_path *path,
1475                                  struct btrfs_extent_inline_ref **ref_ret,
1476                                  u64 bytenr, u64 num_bytes,
1477                                  u64 parent, u64 root_objectid,
1478                                  u64 owner, u64 offset, int insert)
1479 {
1480         struct btrfs_fs_info *fs_info = trans->fs_info;
1481         struct btrfs_root *root = fs_info->extent_root;
1482         struct btrfs_key key;
1483         struct extent_buffer *leaf;
1484         struct btrfs_extent_item *ei;
1485         struct btrfs_extent_inline_ref *iref;
1486         u64 flags;
1487         u64 item_size;
1488         unsigned long ptr;
1489         unsigned long end;
1490         int extra_size;
1491         int type;
1492         int want;
1493         int ret;
1494         int err = 0;
1495         bool skinny_metadata = btrfs_fs_incompat(fs_info, SKINNY_METADATA);
1496         int needed;
1497
1498         key.objectid = bytenr;
1499         key.type = BTRFS_EXTENT_ITEM_KEY;
1500         key.offset = num_bytes;
1501
1502         want = extent_ref_type(parent, owner);
1503         if (insert) {
1504                 extra_size = btrfs_extent_inline_ref_size(want);
1505                 path->keep_locks = 1;
1506         } else
1507                 extra_size = -1;
1508
1509         /*
1510          * Owner is our level, so we can just add one to get the level for the
1511          * block we are interested in.
1512          */
1513         if (skinny_metadata && owner < BTRFS_FIRST_FREE_OBJECTID) {
1514                 key.type = BTRFS_METADATA_ITEM_KEY;
1515                 key.offset = owner;
1516         }
1517
1518 again:
1519         ret = btrfs_search_slot(trans, root, &key, path, extra_size, 1);
1520         if (ret < 0) {
1521                 err = ret;
1522                 goto out;
1523         }
1524
1525         /*
1526          * We may be a newly converted file system which still has the old fat
1527          * extent entries for metadata, so try and see if we have one of those.
1528          */
1529         if (ret > 0 && skinny_metadata) {
1530                 skinny_metadata = false;
1531                 if (path->slots[0]) {
1532                         path->slots[0]--;
1533                         btrfs_item_key_to_cpu(path->nodes[0], &key,
1534                                               path->slots[0]);
1535                         if (key.objectid == bytenr &&
1536                             key.type == BTRFS_EXTENT_ITEM_KEY &&
1537                             key.offset == num_bytes)
1538                                 ret = 0;
1539                 }
1540                 if (ret) {
1541                         key.objectid = bytenr;
1542                         key.type = BTRFS_EXTENT_ITEM_KEY;
1543                         key.offset = num_bytes;
1544                         btrfs_release_path(path);
1545                         goto again;
1546                 }
1547         }
1548
1549         if (ret && !insert) {
1550                 err = -ENOENT;
1551                 goto out;
1552         } else if (WARN_ON(ret)) {
1553                 err = -EIO;
1554                 goto out;
1555         }
1556
1557         leaf = path->nodes[0];
1558         item_size = btrfs_item_size_nr(leaf, path->slots[0]);
1559         if (unlikely(item_size < sizeof(*ei))) {
1560                 err = -EINVAL;
1561                 btrfs_print_v0_err(fs_info);
1562                 btrfs_abort_transaction(trans, err);
1563                 goto out;
1564         }
1565
1566         ei = btrfs_item_ptr(leaf, path->slots[0], struct btrfs_extent_item);
1567         flags = btrfs_extent_flags(leaf, ei);
1568
1569         ptr = (unsigned long)(ei + 1);
1570         end = (unsigned long)ei + item_size;
1571
1572         if (flags & BTRFS_EXTENT_FLAG_TREE_BLOCK && !skinny_metadata) {
1573                 ptr += sizeof(struct btrfs_tree_block_info);
1574                 BUG_ON(ptr > end);
1575         }
1576
1577         if (owner >= BTRFS_FIRST_FREE_OBJECTID)
1578                 needed = BTRFS_REF_TYPE_DATA;
1579         else
1580                 needed = BTRFS_REF_TYPE_BLOCK;
1581
1582         err = -ENOENT;
1583         while (1) {
1584                 if (ptr >= end) {
1585                         WARN_ON(ptr > end);
1586                         break;
1587                 }
1588                 iref = (struct btrfs_extent_inline_ref *)ptr;
1589                 type = btrfs_get_extent_inline_ref_type(leaf, iref, needed);
1590                 if (type == BTRFS_REF_TYPE_INVALID) {
1591                         err = -EUCLEAN;
1592                         goto out;
1593                 }
1594
1595                 if (want < type)
1596                         break;
1597                 if (want > type) {
1598                         ptr += btrfs_extent_inline_ref_size(type);
1599                         continue;
1600                 }
1601
1602                 if (type == BTRFS_EXTENT_DATA_REF_KEY) {
1603                         struct btrfs_extent_data_ref *dref;
1604                         dref = (struct btrfs_extent_data_ref *)(&iref->offset);
1605                         if (match_extent_data_ref(leaf, dref, root_objectid,
1606                                                   owner, offset)) {
1607                                 err = 0;
1608                                 break;
1609                         }
1610                         if (hash_extent_data_ref_item(leaf, dref) <
1611                             hash_extent_data_ref(root_objectid, owner, offset))
1612                                 break;
1613                 } else {
1614                         u64 ref_offset;
1615                         ref_offset = btrfs_extent_inline_ref_offset(leaf, iref);
1616                         if (parent > 0) {
1617                                 if (parent == ref_offset) {
1618                                         err = 0;
1619                                         break;
1620                                 }
1621                                 if (ref_offset < parent)
1622                                         break;
1623                         } else {
1624                                 if (root_objectid == ref_offset) {
1625                                         err = 0;
1626                                         break;
1627                                 }
1628                                 if (ref_offset < root_objectid)
1629                                         break;
1630                         }
1631                 }
1632                 ptr += btrfs_extent_inline_ref_size(type);
1633         }
1634         if (err == -ENOENT && insert) {
1635                 if (item_size + extra_size >=
1636                     BTRFS_MAX_EXTENT_ITEM_SIZE(root)) {
1637                         err = -EAGAIN;
1638                         goto out;
1639                 }
1640                 /*
1641                  * To add new inline back ref, we have to make sure
1642                  * there is no corresponding back ref item.
1643                  * For simplicity, we just do not add new inline back
1644                  * ref if there is any kind of item for this block
1645                  */
1646                 if (find_next_key(path, 0, &key) == 0 &&
1647                     key.objectid == bytenr &&
1648                     key.type < BTRFS_BLOCK_GROUP_ITEM_KEY) {
1649                         err = -EAGAIN;
1650                         goto out;
1651                 }
1652         }
1653         *ref_ret = (struct btrfs_extent_inline_ref *)ptr;
1654 out:
1655         if (insert) {
1656                 path->keep_locks = 0;
1657                 btrfs_unlock_up_safe(path, 1);
1658         }
1659         return err;
1660 }
1661
1662 /*
1663  * helper to add new inline back ref
1664  */
1665 static noinline_for_stack
1666 void setup_inline_extent_backref(struct btrfs_fs_info *fs_info,
1667                                  struct btrfs_path *path,
1668                                  struct btrfs_extent_inline_ref *iref,
1669                                  u64 parent, u64 root_objectid,
1670                                  u64 owner, u64 offset, int refs_to_add,
1671                                  struct btrfs_delayed_extent_op *extent_op)
1672 {
1673         struct extent_buffer *leaf;
1674         struct btrfs_extent_item *ei;
1675         unsigned long ptr;
1676         unsigned long end;
1677         unsigned long item_offset;
1678         u64 refs;
1679         int size;
1680         int type;
1681
1682         leaf = path->nodes[0];
1683         ei = btrfs_item_ptr(leaf, path->slots[0], struct btrfs_extent_item);
1684         item_offset = (unsigned long)iref - (unsigned long)ei;
1685
1686         type = extent_ref_type(parent, owner);
1687         size = btrfs_extent_inline_ref_size(type);
1688
1689         btrfs_extend_item(fs_info, path, size);
1690
1691         ei = btrfs_item_ptr(leaf, path->slots[0], struct btrfs_extent_item);
1692         refs = btrfs_extent_refs(leaf, ei);
1693         refs += refs_to_add;
1694         btrfs_set_extent_refs(leaf, ei, refs);
1695         if (extent_op)
1696                 __run_delayed_extent_op(extent_op, leaf, ei);
1697
1698         ptr = (unsigned long)ei + item_offset;
1699         end = (unsigned long)ei + btrfs_item_size_nr(leaf, path->slots[0]);
1700         if (ptr < end - size)
1701                 memmove_extent_buffer(leaf, ptr + size, ptr,
1702                                       end - size - ptr);
1703
1704         iref = (struct btrfs_extent_inline_ref *)ptr;
1705         btrfs_set_extent_inline_ref_type(leaf, iref, type);
1706         if (type == BTRFS_EXTENT_DATA_REF_KEY) {
1707                 struct btrfs_extent_data_ref *dref;
1708                 dref = (struct btrfs_extent_data_ref *)(&iref->offset);
1709                 btrfs_set_extent_data_ref_root(leaf, dref, root_objectid);
1710                 btrfs_set_extent_data_ref_objectid(leaf, dref, owner);
1711                 btrfs_set_extent_data_ref_offset(leaf, dref, offset);
1712                 btrfs_set_extent_data_ref_count(leaf, dref, refs_to_add);
1713         } else if (type == BTRFS_SHARED_DATA_REF_KEY) {
1714                 struct btrfs_shared_data_ref *sref;
1715                 sref = (struct btrfs_shared_data_ref *)(iref + 1);
1716                 btrfs_set_shared_data_ref_count(leaf, sref, refs_to_add);
1717                 btrfs_set_extent_inline_ref_offset(leaf, iref, parent);
1718         } else if (type == BTRFS_SHARED_BLOCK_REF_KEY) {
1719                 btrfs_set_extent_inline_ref_offset(leaf, iref, parent);
1720         } else {
1721                 btrfs_set_extent_inline_ref_offset(leaf, iref, root_objectid);
1722         }
1723         btrfs_mark_buffer_dirty(leaf);
1724 }
1725
1726 static int lookup_extent_backref(struct btrfs_trans_handle *trans,
1727                                  struct btrfs_path *path,
1728                                  struct btrfs_extent_inline_ref **ref_ret,
1729                                  u64 bytenr, u64 num_bytes, u64 parent,
1730                                  u64 root_objectid, u64 owner, u64 offset)
1731 {
1732         int ret;
1733
1734         ret = lookup_inline_extent_backref(trans, path, ref_ret, bytenr,
1735                                            num_bytes, parent, root_objectid,
1736                                            owner, offset, 0);
1737         if (ret != -ENOENT)
1738                 return ret;
1739
1740         btrfs_release_path(path);
1741         *ref_ret = NULL;
1742
1743         if (owner < BTRFS_FIRST_FREE_OBJECTID) {
1744                 ret = lookup_tree_block_ref(trans, path, bytenr, parent,
1745                                             root_objectid);
1746         } else {
1747                 ret = lookup_extent_data_ref(trans, path, bytenr, parent,
1748                                              root_objectid, owner, offset);
1749         }
1750         return ret;
1751 }
1752
1753 /*
1754  * helper to update/remove inline back ref
1755  */
1756 static noinline_for_stack
1757 void update_inline_extent_backref(struct btrfs_path *path,
1758                                   struct btrfs_extent_inline_ref *iref,
1759                                   int refs_to_mod,
1760                                   struct btrfs_delayed_extent_op *extent_op,
1761                                   int *last_ref)
1762 {
1763         struct extent_buffer *leaf = path->nodes[0];
1764         struct btrfs_fs_info *fs_info = leaf->fs_info;
1765         struct btrfs_extent_item *ei;
1766         struct btrfs_extent_data_ref *dref = NULL;
1767         struct btrfs_shared_data_ref *sref = NULL;
1768         unsigned long ptr;
1769         unsigned long end;
1770         u32 item_size;
1771         int size;
1772         int type;
1773         u64 refs;
1774
1775         ei = btrfs_item_ptr(leaf, path->slots[0], struct btrfs_extent_item);
1776         refs = btrfs_extent_refs(leaf, ei);
1777         WARN_ON(refs_to_mod < 0 && refs + refs_to_mod <= 0);
1778         refs += refs_to_mod;
1779         btrfs_set_extent_refs(leaf, ei, refs);
1780         if (extent_op)
1781                 __run_delayed_extent_op(extent_op, leaf, ei);
1782
1783         /*
1784          * If type is invalid, we should have bailed out after
1785          * lookup_inline_extent_backref().
1786          */
1787         type = btrfs_get_extent_inline_ref_type(leaf, iref, BTRFS_REF_TYPE_ANY);
1788         ASSERT(type != BTRFS_REF_TYPE_INVALID);
1789
1790         if (type == BTRFS_EXTENT_DATA_REF_KEY) {
1791                 dref = (struct btrfs_extent_data_ref *)(&iref->offset);
1792                 refs = btrfs_extent_data_ref_count(leaf, dref);
1793         } else if (type == BTRFS_SHARED_DATA_REF_KEY) {
1794                 sref = (struct btrfs_shared_data_ref *)(iref + 1);
1795                 refs = btrfs_shared_data_ref_count(leaf, sref);
1796         } else {
1797                 refs = 1;
1798                 BUG_ON(refs_to_mod != -1);
1799         }
1800
1801         BUG_ON(refs_to_mod < 0 && refs < -refs_to_mod);
1802         refs += refs_to_mod;
1803
1804         if (refs > 0) {
1805                 if (type == BTRFS_EXTENT_DATA_REF_KEY)
1806                         btrfs_set_extent_data_ref_count(leaf, dref, refs);
1807                 else
1808                         btrfs_set_shared_data_ref_count(leaf, sref, refs);
1809         } else {
1810                 *last_ref = 1;
1811                 size =  btrfs_extent_inline_ref_size(type);
1812                 item_size = btrfs_item_size_nr(leaf, path->slots[0]);
1813                 ptr = (unsigned long)iref;
1814                 end = (unsigned long)ei + item_size;
1815                 if (ptr + size < end)
1816                         memmove_extent_buffer(leaf, ptr, ptr + size,
1817                                               end - ptr - size);
1818                 item_size -= size;
1819                 btrfs_truncate_item(fs_info, path, item_size, 1);
1820         }
1821         btrfs_mark_buffer_dirty(leaf);
1822 }
1823
1824 static noinline_for_stack
1825 int insert_inline_extent_backref(struct btrfs_trans_handle *trans,
1826                                  struct btrfs_path *path,
1827                                  u64 bytenr, u64 num_bytes, u64 parent,
1828                                  u64 root_objectid, u64 owner,
1829                                  u64 offset, int refs_to_add,
1830                                  struct btrfs_delayed_extent_op *extent_op)
1831 {
1832         struct btrfs_extent_inline_ref *iref;
1833         int ret;
1834
1835         ret = lookup_inline_extent_backref(trans, path, &iref, bytenr,
1836                                            num_bytes, parent, root_objectid,
1837                                            owner, offset, 1);
1838         if (ret == 0) {
1839                 BUG_ON(owner < BTRFS_FIRST_FREE_OBJECTID);
1840                 update_inline_extent_backref(path, iref, refs_to_add,
1841                                              extent_op, NULL);
1842         } else if (ret == -ENOENT) {
1843                 setup_inline_extent_backref(trans->fs_info, path, iref, parent,
1844                                             root_objectid, owner, offset,
1845                                             refs_to_add, extent_op);
1846                 ret = 0;
1847         }
1848         return ret;
1849 }
1850
1851 static int insert_extent_backref(struct btrfs_trans_handle *trans,
1852                                  struct btrfs_path *path,
1853                                  u64 bytenr, u64 parent, u64 root_objectid,
1854                                  u64 owner, u64 offset, int refs_to_add)
1855 {
1856         int ret;
1857         if (owner < BTRFS_FIRST_FREE_OBJECTID) {
1858                 BUG_ON(refs_to_add != 1);
1859                 ret = insert_tree_block_ref(trans, path, bytenr, parent,
1860                                             root_objectid);
1861         } else {
1862                 ret = insert_extent_data_ref(trans, path, bytenr, parent,
1863                                              root_objectid, owner, offset,
1864                                              refs_to_add);
1865         }
1866         return ret;
1867 }
1868
1869 static int remove_extent_backref(struct btrfs_trans_handle *trans,
1870                                  struct btrfs_path *path,
1871                                  struct btrfs_extent_inline_ref *iref,
1872                                  int refs_to_drop, int is_data, int *last_ref)
1873 {
1874         int ret = 0;
1875
1876         BUG_ON(!is_data && refs_to_drop != 1);
1877         if (iref) {
1878                 update_inline_extent_backref(path, iref, -refs_to_drop, NULL,
1879                                              last_ref);
1880         } else if (is_data) {
1881                 ret = remove_extent_data_ref(trans, path, refs_to_drop,
1882                                              last_ref);
1883         } else {
1884                 *last_ref = 1;
1885                 ret = btrfs_del_item(trans, trans->fs_info->extent_root, path);
1886         }
1887         return ret;
1888 }
1889
1890 #define in_range(b, first, len)        ((b) >= (first) && (b) < (first) + (len))
1891 static int btrfs_issue_discard(struct block_device *bdev, u64 start, u64 len,
1892                                u64 *discarded_bytes)
1893 {
1894         int j, ret = 0;
1895         u64 bytes_left, end;
1896         u64 aligned_start = ALIGN(start, 1 << 9);
1897
1898         if (WARN_ON(start != aligned_start)) {
1899                 len -= aligned_start - start;
1900                 len = round_down(len, 1 << 9);
1901                 start = aligned_start;
1902         }
1903
1904         *discarded_bytes = 0;
1905
1906         if (!len)
1907                 return 0;
1908
1909         end = start + len;
1910         bytes_left = len;
1911
1912         /* Skip any superblocks on this device. */
1913         for (j = 0; j < BTRFS_SUPER_MIRROR_MAX; j++) {
1914                 u64 sb_start = btrfs_sb_offset(j);
1915                 u64 sb_end = sb_start + BTRFS_SUPER_INFO_SIZE;
1916                 u64 size = sb_start - start;
1917
1918                 if (!in_range(sb_start, start, bytes_left) &&
1919                     !in_range(sb_end, start, bytes_left) &&
1920                     !in_range(start, sb_start, BTRFS_SUPER_INFO_SIZE))
1921                         continue;
1922
1923                 /*
1924                  * Superblock spans beginning of range.  Adjust start and
1925                  * try again.
1926                  */
1927                 if (sb_start <= start) {
1928                         start += sb_end - start;
1929                         if (start > end) {
1930                                 bytes_left = 0;
1931                                 break;
1932                         }
1933                         bytes_left = end - start;
1934                         continue;
1935                 }
1936
1937                 if (size) {
1938                         ret = blkdev_issue_discard(bdev, start >> 9, size >> 9,
1939                                                    GFP_NOFS, 0);
1940                         if (!ret)
1941                                 *discarded_bytes += size;
1942                         else if (ret != -EOPNOTSUPP)
1943                                 return ret;
1944                 }
1945
1946                 start = sb_end;
1947                 if (start > end) {
1948                         bytes_left = 0;
1949                         break;
1950                 }
1951                 bytes_left = end - start;
1952         }
1953
1954         if (bytes_left) {
1955                 ret = blkdev_issue_discard(bdev, start >> 9, bytes_left >> 9,
1956                                            GFP_NOFS, 0);
1957                 if (!ret)
1958                         *discarded_bytes += bytes_left;
1959         }
1960         return ret;
1961 }
1962
1963 int btrfs_discard_extent(struct btrfs_fs_info *fs_info, u64 bytenr,
1964                          u64 num_bytes, u64 *actual_bytes)
1965 {
1966         int ret;
1967         u64 discarded_bytes = 0;
1968         struct btrfs_bio *bbio = NULL;
1969
1970
1971         /*
1972          * Avoid races with device replace and make sure our bbio has devices
1973          * associated to its stripes that don't go away while we are discarding.
1974          */
1975         btrfs_bio_counter_inc_blocked(fs_info);
1976         /* Tell the block device(s) that the sectors can be discarded */
1977         ret = btrfs_map_block(fs_info, BTRFS_MAP_DISCARD, bytenr, &num_bytes,
1978                               &bbio, 0);
1979         /* Error condition is -ENOMEM */
1980         if (!ret) {
1981                 struct btrfs_bio_stripe *stripe = bbio->stripes;
1982                 int i;
1983
1984
1985                 for (i = 0; i < bbio->num_stripes; i++, stripe++) {
1986                         u64 bytes;
1987                         struct request_queue *req_q;
1988
1989                         if (!stripe->dev->bdev) {
1990                                 ASSERT(btrfs_test_opt(fs_info, DEGRADED));
1991                                 continue;
1992                         }
1993                         req_q = bdev_get_queue(stripe->dev->bdev);
1994                         if (!blk_queue_discard(req_q))
1995                                 continue;
1996
1997                         ret = btrfs_issue_discard(stripe->dev->bdev,
1998                                                   stripe->physical,
1999                                                   stripe->length,
2000                                                   &bytes);
2001                         if (!ret)
2002                                 discarded_bytes += bytes;
2003                         else if (ret != -EOPNOTSUPP)
2004                                 break; /* Logic errors or -ENOMEM, or -EIO but I don't know how that could happen JDM */
2005
2006                         /*
2007                          * Just in case we get back EOPNOTSUPP for some reason,
2008                          * just ignore the return value so we don't screw up
2009                          * people calling discard_extent.
2010                          */
2011                         ret = 0;
2012                 }
2013                 btrfs_put_bbio(bbio);
2014         }
2015         btrfs_bio_counter_dec(fs_info);
2016
2017         if (actual_bytes)
2018                 *actual_bytes = discarded_bytes;
2019
2020
2021         if (ret == -EOPNOTSUPP)
2022                 ret = 0;
2023         return ret;
2024 }
2025
2026 /* Can return -ENOMEM */
2027 int btrfs_inc_extent_ref(struct btrfs_trans_handle *trans,
2028                          struct btrfs_root *root,
2029                          u64 bytenr, u64 num_bytes, u64 parent,
2030                          u64 root_objectid, u64 owner, u64 offset)
2031 {
2032         struct btrfs_fs_info *fs_info = root->fs_info;
2033         int old_ref_mod, new_ref_mod;
2034         int ret;
2035
2036         BUG_ON(owner < BTRFS_FIRST_FREE_OBJECTID &&
2037                root_objectid == BTRFS_TREE_LOG_OBJECTID);
2038
2039         btrfs_ref_tree_mod(root, bytenr, num_bytes, parent, root_objectid,
2040                            owner, offset, BTRFS_ADD_DELAYED_REF);
2041
2042         if (owner < BTRFS_FIRST_FREE_OBJECTID) {
2043                 ret = btrfs_add_delayed_tree_ref(trans, bytenr,
2044                                                  num_bytes, parent,
2045                                                  root_objectid, (int)owner,
2046                                                  BTRFS_ADD_DELAYED_REF, NULL,
2047                                                  &old_ref_mod, &new_ref_mod);
2048         } else {
2049                 ret = btrfs_add_delayed_data_ref(trans, bytenr,
2050                                                  num_bytes, parent,
2051                                                  root_objectid, owner, offset,
2052                                                  0, BTRFS_ADD_DELAYED_REF,
2053                                                  &old_ref_mod, &new_ref_mod);
2054         }
2055
2056         if (ret == 0 && old_ref_mod < 0 && new_ref_mod >= 0) {
2057                 bool metadata = owner < BTRFS_FIRST_FREE_OBJECTID;
2058
2059                 add_pinned_bytes(fs_info, -num_bytes, metadata, root_objectid);
2060         }
2061
2062         return ret;
2063 }
2064
2065 /*
2066  * __btrfs_inc_extent_ref - insert backreference for a given extent
2067  *
2068  * @trans:          Handle of transaction
2069  *
2070  * @node:           The delayed ref node used to get the bytenr/length for
2071  *                  extent whose references are incremented.
2072  *
2073  * @parent:         If this is a shared extent (BTRFS_SHARED_DATA_REF_KEY/
2074  *                  BTRFS_SHARED_BLOCK_REF_KEY) then it holds the logical
2075  *                  bytenr of the parent block. Since new extents are always
2076  *                  created with indirect references, this will only be the case
2077  *                  when relocating a shared extent. In that case, root_objectid
2078  *                  will be BTRFS_TREE_RELOC_OBJECTID. Otheriwse, parent must
2079  *                  be 0
2080  *
2081  * @root_objectid:  The id of the root where this modification has originated,
2082  *                  this can be either one of the well-known metadata trees or
2083  *                  the subvolume id which references this extent.
2084  *
2085  * @owner:          For data extents it is the inode number of the owning file.
2086  *                  For metadata extents this parameter holds the level in the
2087  *                  tree of the extent.
2088  *
2089  * @offset:         For metadata extents the offset is ignored and is currently
2090  *                  always passed as 0. For data extents it is the fileoffset
2091  *                  this extent belongs to.
2092  *
2093  * @refs_to_add     Number of references to add
2094  *
2095  * @extent_op       Pointer to a structure, holding information necessary when
2096  *                  updating a tree block's flags
2097  *
2098  */
2099 static int __btrfs_inc_extent_ref(struct btrfs_trans_handle *trans,
2100                                   struct btrfs_delayed_ref_node *node,
2101                                   u64 parent, u64 root_objectid,
2102                                   u64 owner, u64 offset, int refs_to_add,
2103                                   struct btrfs_delayed_extent_op *extent_op)
2104 {
2105         struct btrfs_path *path;
2106         struct extent_buffer *leaf;
2107         struct btrfs_extent_item *item;
2108         struct btrfs_key key;
2109         u64 bytenr = node->bytenr;
2110         u64 num_bytes = node->num_bytes;
2111         u64 refs;
2112         int ret;
2113
2114         path = btrfs_alloc_path();
2115         if (!path)
2116                 return -ENOMEM;
2117
2118         path->reada = READA_FORWARD;
2119         path->leave_spinning = 1;
2120         /* this will setup the path even if it fails to insert the back ref */
2121         ret = insert_inline_extent_backref(trans, path, bytenr, num_bytes,
2122                                            parent, root_objectid, owner,
2123                                            offset, refs_to_add, extent_op);
2124         if ((ret < 0 && ret != -EAGAIN) || !ret)
2125                 goto out;
2126
2127         /*
2128          * Ok we had -EAGAIN which means we didn't have space to insert and
2129          * inline extent ref, so just update the reference count and add a
2130          * normal backref.
2131          */
2132         leaf = path->nodes[0];
2133         btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);
2134         item = btrfs_item_ptr(leaf, path->slots[0], struct btrfs_extent_item);
2135         refs = btrfs_extent_refs(leaf, item);
2136         btrfs_set_extent_refs(leaf, item, refs + refs_to_add);
2137         if (extent_op)
2138                 __run_delayed_extent_op(extent_op, leaf, item);
2139
2140         btrfs_mark_buffer_dirty(leaf);
2141         btrfs_release_path(path);
2142
2143         path->reada = READA_FORWARD;
2144         path->leave_spinning = 1;
2145         /* now insert the actual backref */
2146         ret = insert_extent_backref(trans, path, bytenr, parent, root_objectid,
2147                                     owner, offset, refs_to_add);
2148         if (ret)
2149                 btrfs_abort_transaction(trans, ret);
2150 out:
2151         btrfs_free_path(path);
2152         return ret;
2153 }
2154
2155 static int run_delayed_data_ref(struct btrfs_trans_handle *trans,
2156                                 struct btrfs_delayed_ref_node *node,
2157                                 struct btrfs_delayed_extent_op *extent_op,
2158                                 int insert_reserved)
2159 {
2160         int ret = 0;
2161         struct btrfs_delayed_data_ref *ref;
2162         struct btrfs_key ins;
2163         u64 parent = 0;
2164         u64 ref_root = 0;
2165         u64 flags = 0;
2166
2167         ins.objectid = node->bytenr;
2168         ins.offset = node->num_bytes;
2169         ins.type = BTRFS_EXTENT_ITEM_KEY;
2170
2171         ref = btrfs_delayed_node_to_data_ref(node);
2172         trace_run_delayed_data_ref(trans->fs_info, node, ref, node->action);
2173
2174         if (node->type == BTRFS_SHARED_DATA_REF_KEY)
2175                 parent = ref->parent;
2176         ref_root = ref->root;
2177
2178         if (node->action == BTRFS_ADD_DELAYED_REF && insert_reserved) {
2179                 if (extent_op)
2180                         flags |= extent_op->flags_to_set;
2181                 ret = alloc_reserved_file_extent(trans, parent, ref_root,
2182                                                  flags, ref->objectid,
2183                                                  ref->offset, &ins,
2184                                                  node->ref_mod);
2185         } else if (node->action == BTRFS_ADD_DELAYED_REF) {
2186                 ret = __btrfs_inc_extent_ref(trans, node, parent, ref_root,
2187                                              ref->objectid, ref->offset,
2188                                              node->ref_mod, extent_op);
2189         } else if (node->action == BTRFS_DROP_DELAYED_REF) {
2190                 ret = __btrfs_free_extent(trans, node, parent,
2191                                           ref_root, ref->objectid,
2192                                           ref->offset, node->ref_mod,
2193                                           extent_op);
2194         } else {
2195                 BUG();
2196         }
2197         return ret;
2198 }
2199
2200 static void __run_delayed_extent_op(struct btrfs_delayed_extent_op *extent_op,
2201                                     struct extent_buffer *leaf,
2202                                     struct btrfs_extent_item *ei)
2203 {
2204         u64 flags = btrfs_extent_flags(leaf, ei);
2205         if (extent_op->update_flags) {
2206                 flags |= extent_op->flags_to_set;
2207                 btrfs_set_extent_flags(leaf, ei, flags);
2208         }
2209
2210         if (extent_op->update_key) {
2211                 struct btrfs_tree_block_info *bi;
2212                 BUG_ON(!(flags & BTRFS_EXTENT_FLAG_TREE_BLOCK));
2213                 bi = (struct btrfs_tree_block_info *)(ei + 1);
2214                 btrfs_set_tree_block_key(leaf, bi, &extent_op->key);
2215         }
2216 }
2217
2218 static int run_delayed_extent_op(struct btrfs_trans_handle *trans,
2219                                  struct btrfs_delayed_ref_head *head,
2220                                  struct btrfs_delayed_extent_op *extent_op)
2221 {
2222         struct btrfs_fs_info *fs_info = trans->fs_info;
2223         struct btrfs_key key;
2224         struct btrfs_path *path;
2225         struct btrfs_extent_item *ei;
2226         struct extent_buffer *leaf;
2227         u32 item_size;
2228         int ret;
2229         int err = 0;
2230         int metadata = !extent_op->is_data;
2231
2232         if (trans->aborted)
2233                 return 0;
2234
2235         if (metadata && !btrfs_fs_incompat(fs_info, SKINNY_METADATA))
2236                 metadata = 0;
2237
2238         path = btrfs_alloc_path();
2239         if (!path)
2240                 return -ENOMEM;
2241
2242         key.objectid = head->bytenr;
2243
2244         if (metadata) {
2245                 key.type = BTRFS_METADATA_ITEM_KEY;
2246                 key.offset = extent_op->level;
2247         } else {
2248                 key.type = BTRFS_EXTENT_ITEM_KEY;
2249                 key.offset = head->num_bytes;
2250         }
2251
2252 again:
2253         path->reada = READA_FORWARD;
2254         path->leave_spinning = 1;
2255         ret = btrfs_search_slot(trans, fs_info->extent_root, &key, path, 0, 1);
2256         if (ret < 0) {
2257                 err = ret;
2258                 goto out;
2259         }
2260         if (ret > 0) {
2261                 if (metadata) {
2262                         if (path->slots[0] > 0) {
2263                                 path->slots[0]--;
2264                                 btrfs_item_key_to_cpu(path->nodes[0], &key,
2265                                                       path->slots[0]);
2266                                 if (key.objectid == head->bytenr &&
2267                                     key.type == BTRFS_EXTENT_ITEM_KEY &&
2268                                     key.offset == head->num_bytes)
2269                                         ret = 0;
2270                         }
2271                         if (ret > 0) {
2272                                 btrfs_release_path(path);
2273                                 metadata = 0;
2274
2275                                 key.objectid = head->bytenr;
2276                                 key.offset = head->num_bytes;
2277                                 key.type = BTRFS_EXTENT_ITEM_KEY;
2278                                 goto again;
2279                         }
2280                 } else {
2281                         err = -EIO;
2282                         goto out;
2283                 }
2284         }
2285
2286         leaf = path->nodes[0];
2287         item_size = btrfs_item_size_nr(leaf, path->slots[0]);
2288
2289         if (unlikely(item_size < sizeof(*ei))) {
2290                 err = -EINVAL;
2291                 btrfs_print_v0_err(fs_info);
2292                 btrfs_abort_transaction(trans, err);
2293                 goto out;
2294         }
2295
2296         ei = btrfs_item_ptr(leaf, path->slots[0], struct btrfs_extent_item);
2297         __run_delayed_extent_op(extent_op, leaf, ei);
2298
2299         btrfs_mark_buffer_dirty(leaf);
2300 out:
2301         btrfs_free_path(path);
2302         return err;
2303 }
2304
2305 static int run_delayed_tree_ref(struct btrfs_trans_handle *trans,
2306                                 struct btrfs_delayed_ref_node *node,
2307                                 struct btrfs_delayed_extent_op *extent_op,
2308                                 int insert_reserved)
2309 {
2310         int ret = 0;
2311         struct btrfs_delayed_tree_ref *ref;
2312         u64 parent = 0;
2313         u64 ref_root = 0;
2314
2315         ref = btrfs_delayed_node_to_tree_ref(node);
2316         trace_run_delayed_tree_ref(trans->fs_info, node, ref, node->action);
2317
2318         if (node->type == BTRFS_SHARED_BLOCK_REF_KEY)
2319                 parent = ref->parent;
2320         ref_root = ref->root;
2321
2322         if (node->ref_mod != 1) {
2323                 btrfs_err(trans->fs_info,
2324         "btree block(%llu) has %d references rather than 1: action %d ref_root %llu parent %llu",
2325                           node->bytenr, node->ref_mod, node->action, ref_root,
2326                           parent);
2327                 return -EIO;
2328         }
2329         if (node->action == BTRFS_ADD_DELAYED_REF && insert_reserved) {
2330                 BUG_ON(!extent_op || !extent_op->update_flags);
2331                 ret = alloc_reserved_tree_block(trans, node, extent_op);
2332         } else if (node->action == BTRFS_ADD_DELAYED_REF) {
2333                 ret = __btrfs_inc_extent_ref(trans, node, parent, ref_root,
2334                                              ref->level, 0, 1, extent_op);
2335         } else if (node->action == BTRFS_DROP_DELAYED_REF) {
2336                 ret = __btrfs_free_extent(trans, node, parent, ref_root,
2337                                           ref->level, 0, 1, extent_op);
2338         } else {
2339                 BUG();
2340         }
2341         return ret;
2342 }
2343
2344 /* helper function to actually process a single delayed ref entry */
2345 static int run_one_delayed_ref(struct btrfs_trans_handle *trans,
2346                                struct btrfs_delayed_ref_node *node,
2347                                struct btrfs_delayed_extent_op *extent_op,
2348                                int insert_reserved)
2349 {
2350         int ret = 0;
2351
2352         if (trans->aborted) {
2353                 if (insert_reserved)
2354                         btrfs_pin_extent(trans->fs_info, node->bytenr,
2355                                          node->num_bytes, 1);
2356                 return 0;
2357         }
2358
2359         if (node->type == BTRFS_TREE_BLOCK_REF_KEY ||
2360             node->type == BTRFS_SHARED_BLOCK_REF_KEY)
2361                 ret = run_delayed_tree_ref(trans, node, extent_op,
2362                                            insert_reserved);
2363         else if (node->type == BTRFS_EXTENT_DATA_REF_KEY ||
2364                  node->type == BTRFS_SHARED_DATA_REF_KEY)
2365                 ret = run_delayed_data_ref(trans, node, extent_op,
2366                                            insert_reserved);
2367         else
2368                 BUG();
2369         return ret;
2370 }
2371
2372 static inline struct btrfs_delayed_ref_node *
2373 select_delayed_ref(struct btrfs_delayed_ref_head *head)
2374 {
2375         struct btrfs_delayed_ref_node *ref;
2376
2377         if (RB_EMPTY_ROOT(&head->ref_tree))
2378                 return NULL;
2379
2380         /*
2381          * Select a delayed ref of type BTRFS_ADD_DELAYED_REF first.
2382          * This is to prevent a ref count from going down to zero, which deletes
2383          * the extent item from the extent tree, when there still are references
2384          * to add, which would fail because they would not find the extent item.
2385          */
2386         if (!list_empty(&head->ref_add_list))
2387                 return list_first_entry(&head->ref_add_list,
2388                                 struct btrfs_delayed_ref_node, add_list);
2389
2390         ref = rb_entry(rb_first(&head->ref_tree),
2391                        struct btrfs_delayed_ref_node, ref_node);
2392         ASSERT(list_empty(&ref->add_list));
2393         return ref;
2394 }
2395
2396 static void unselect_delayed_ref_head(struct btrfs_delayed_ref_root *delayed_refs,
2397                                       struct btrfs_delayed_ref_head *head)
2398 {
2399         spin_lock(&delayed_refs->lock);
2400         head->processing = 0;
2401         delayed_refs->num_heads_ready++;
2402         spin_unlock(&delayed_refs->lock);
2403         btrfs_delayed_ref_unlock(head);
2404 }
2405
2406 static int cleanup_extent_op(struct btrfs_trans_handle *trans,
2407                              struct btrfs_delayed_ref_head *head)
2408 {
2409         struct btrfs_delayed_extent_op *extent_op = head->extent_op;
2410         int ret;
2411
2412         if (!extent_op)
2413                 return 0;
2414         head->extent_op = NULL;
2415         if (head->must_insert_reserved) {
2416                 btrfs_free_delayed_extent_op(extent_op);
2417                 return 0;
2418         }
2419         spin_unlock(&head->lock);
2420         ret = run_delayed_extent_op(trans, head, extent_op);
2421         btrfs_free_delayed_extent_op(extent_op);
2422         return ret ? ret : 1;
2423 }
2424
2425 static int cleanup_ref_head(struct btrfs_trans_handle *trans,
2426                             struct btrfs_delayed_ref_head *head)
2427 {
2428
2429         struct btrfs_fs_info *fs_info = trans->fs_info;
2430         struct btrfs_delayed_ref_root *delayed_refs;
2431         int ret;
2432
2433         delayed_refs = &trans->transaction->delayed_refs;
2434
2435         ret = cleanup_extent_op(trans, head);
2436         if (ret < 0) {
2437                 unselect_delayed_ref_head(delayed_refs, head);
2438                 btrfs_debug(fs_info, "run_delayed_extent_op returned %d", ret);
2439                 return ret;
2440         } else if (ret) {
2441                 return ret;
2442         }
2443
2444         /*
2445          * Need to drop our head ref lock and re-acquire the delayed ref lock
2446          * and then re-check to make sure nobody got added.
2447          */
2448         spin_unlock(&head->lock);
2449         spin_lock(&delayed_refs->lock);
2450         spin_lock(&head->lock);
2451         if (!RB_EMPTY_ROOT(&head->ref_tree) || head->extent_op) {
2452                 spin_unlock(&head->lock);
2453                 spin_unlock(&delayed_refs->lock);
2454                 return 1;
2455         }
2456         delayed_refs->num_heads--;
2457         rb_erase(&head->href_node, &delayed_refs->href_root);
2458         RB_CLEAR_NODE(&head->href_node);
2459         spin_unlock(&head->lock);
2460         spin_unlock(&delayed_refs->lock);
2461         atomic_dec(&delayed_refs->num_entries);
2462
2463         trace_run_delayed_ref_head(fs_info, head, 0);
2464
2465         if (head->total_ref_mod < 0) {
2466                 struct btrfs_space_info *space_info;
2467                 u64 flags;
2468
2469                 if (head->is_data)
2470                         flags = BTRFS_BLOCK_GROUP_DATA;
2471                 else if (head->is_system)
2472                         flags = BTRFS_BLOCK_GROUP_SYSTEM;
2473                 else
2474                         flags = BTRFS_BLOCK_GROUP_METADATA;
2475                 space_info = __find_space_info(fs_info, flags);
2476                 ASSERT(space_info);
2477                 percpu_counter_add_batch(&space_info->total_bytes_pinned,
2478                                    -head->num_bytes,
2479                                    BTRFS_TOTAL_BYTES_PINNED_BATCH);
2480
2481                 if (head->is_data) {
2482                         spin_lock(&delayed_refs->lock);
2483                         delayed_refs->pending_csums -= head->num_bytes;
2484                         spin_unlock(&delayed_refs->lock);
2485                 }
2486         }
2487
2488         if (head->must_insert_reserved) {
2489                 btrfs_pin_extent(fs_info, head->bytenr,
2490                                  head->num_bytes, 1);
2491                 if (head->is_data) {
2492                         ret = btrfs_del_csums(trans, fs_info, head->bytenr,
2493                                               head->num_bytes);
2494                 }
2495         }
2496
2497         /* Also free its reserved qgroup space */
2498         btrfs_qgroup_free_delayed_ref(fs_info, head->qgroup_ref_root,
2499                                       head->qgroup_reserved);
2500         btrfs_delayed_ref_unlock(head);
2501         btrfs_put_delayed_ref_head(head);
2502         return 0;
2503 }
2504
2505 /*
2506  * Returns 0 on success or if called with an already aborted transaction.
2507  * Returns -ENOMEM or -EIO on failure and will abort the transaction.
2508  */
2509 static noinline int __btrfs_run_delayed_refs(struct btrfs_trans_handle *trans,
2510                                              unsigned long nr)
2511 {
2512         struct btrfs_fs_info *fs_info = trans->fs_info;
2513         struct btrfs_delayed_ref_root *delayed_refs;
2514         struct btrfs_delayed_ref_node *ref;
2515         struct btrfs_delayed_ref_head *locked_ref = NULL;
2516         struct btrfs_delayed_extent_op *extent_op;
2517         ktime_t start = ktime_get();
2518         int ret;
2519         unsigned long count = 0;
2520         unsigned long actual_count = 0;
2521         int must_insert_reserved = 0;
2522
2523         delayed_refs = &trans->transaction->delayed_refs;
2524         while (1) {
2525                 if (!locked_ref) {
2526                         if (count >= nr)
2527                                 break;
2528
2529                         spin_lock(&delayed_refs->lock);
2530                         locked_ref = btrfs_select_ref_head(trans);
2531                         if (!locked_ref) {
2532                                 spin_unlock(&delayed_refs->lock);
2533                                 break;
2534                         }
2535
2536                         /* grab the lock that says we are going to process
2537                          * all the refs for this head */
2538                         ret = btrfs_delayed_ref_lock(trans, locked_ref);
2539                         spin_unlock(&delayed_refs->lock);
2540                         /*
2541                          * we may have dropped the spin lock to get the head
2542                          * mutex lock, and that might have given someone else
2543                          * time to free the head.  If that's true, it has been
2544                          * removed from our list and we can move on.
2545                          */
2546                         if (ret == -EAGAIN) {
2547                                 locked_ref = NULL;
2548                                 count++;
2549                                 continue;
2550                         }
2551                 }
2552
2553                 /*
2554                  * We need to try and merge add/drops of the same ref since we
2555                  * can run into issues with relocate dropping the implicit ref
2556                  * and then it being added back again before the drop can
2557                  * finish.  If we merged anything we need to re-loop so we can
2558                  * get a good ref.
2559                  * Or we can get node references of the same type that weren't
2560                  * merged when created due to bumps in the tree mod seq, and
2561                  * we need to merge them to prevent adding an inline extent
2562                  * backref before dropping it (triggering a BUG_ON at
2563                  * insert_inline_extent_backref()).
2564                  */
2565                 spin_lock(&locked_ref->lock);
2566                 btrfs_merge_delayed_refs(trans, delayed_refs, locked_ref);
2567
2568                 ref = select_delayed_ref(locked_ref);
2569
2570                 if (ref && ref->seq &&
2571                     btrfs_check_delayed_seq(fs_info, ref->seq)) {
2572                         spin_unlock(&locked_ref->lock);
2573                         unselect_delayed_ref_head(delayed_refs, locked_ref);
2574                         locked_ref = NULL;
2575                         cond_resched();
2576                         count++;
2577                         continue;
2578                 }
2579
2580                 /*
2581                  * We're done processing refs in this ref_head, clean everything
2582                  * up and move on to the next ref_head.
2583                  */
2584                 if (!ref) {
2585                         ret = cleanup_ref_head(trans, locked_ref);
2586                         if (ret > 0 ) {
2587                                 /* We dropped our lock, we need to loop. */
2588                                 ret = 0;
2589                                 continue;
2590                         } else if (ret) {
2591                                 return ret;
2592                         }
2593                         locked_ref = NULL;
2594                         count++;
2595                         continue;
2596                 }
2597
2598                 actual_count++;
2599                 ref->in_tree = 0;
2600                 rb_erase(&ref->ref_node, &locked_ref->ref_tree);
2601                 RB_CLEAR_NODE(&ref->ref_node);
2602                 if (!list_empty(&ref->add_list))
2603                         list_del(&ref->add_list);
2604                 /*
2605                  * When we play the delayed ref, also correct the ref_mod on
2606                  * head
2607                  */
2608                 switch (ref->action) {
2609                 case BTRFS_ADD_DELAYED_REF:
2610                 case BTRFS_ADD_DELAYED_EXTENT:
2611                         locked_ref->ref_mod -= ref->ref_mod;
2612                         break;
2613                 case BTRFS_DROP_DELAYED_REF:
2614                         locked_ref->ref_mod += ref->ref_mod;
2615                         break;
2616                 default:
2617                         WARN_ON(1);
2618                 }
2619                 atomic_dec(&delayed_refs->num_entries);
2620
2621                 /*
2622                  * Record the must-insert_reserved flag before we drop the spin
2623                  * lock.
2624                  */
2625                 must_insert_reserved = locked_ref->must_insert_reserved;
2626                 locked_ref->must_insert_reserved = 0;
2627
2628                 extent_op = locked_ref->extent_op;
2629                 locked_ref->extent_op = NULL;
2630                 spin_unlock(&locked_ref->lock);
2631
2632                 ret = run_one_delayed_ref(trans, ref, extent_op,
2633                                           must_insert_reserved);
2634
2635                 btrfs_free_delayed_extent_op(extent_op);
2636                 if (ret) {
2637                         unselect_delayed_ref_head(delayed_refs, locked_ref);
2638                         btrfs_put_delayed_ref(ref);
2639                         btrfs_debug(fs_info, "run_one_delayed_ref returned %d",
2640                                     ret);
2641                         return ret;
2642                 }
2643
2644                 btrfs_put_delayed_ref(ref);
2645                 count++;
2646                 cond_resched();
2647         }
2648
2649         /*
2650          * We don't want to include ref heads since we can have empty ref heads
2651          * and those will drastically skew our runtime down since we just do
2652          * accounting, no actual extent tree updates.
2653          */
2654         if (actual_count > 0) {
2655                 u64 runtime = ktime_to_ns(ktime_sub(ktime_get(), start));
2656                 u64 avg;
2657
2658                 /*
2659                  * We weigh the current average higher than our current runtime
2660                  * to avoid large swings in the average.
2661                  */
2662                 spin_lock(&delayed_refs->lock);
2663                 avg = fs_info->avg_delayed_ref_runtime * 3 + runtime;
2664                 fs_info->avg_delayed_ref_runtime = avg >> 2;    /* div by 4 */
2665                 spin_unlock(&delayed_refs->lock);
2666         }
2667         return 0;
2668 }
2669
2670 #ifdef SCRAMBLE_DELAYED_REFS
2671 /*
2672  * Normally delayed refs get processed in ascending bytenr order. This
2673  * correlates in most cases to the order added. To expose dependencies on this
2674  * order, we start to process the tree in the middle instead of the beginning
2675  */
2676 static u64 find_middle(struct rb_root *root)
2677 {
2678         struct rb_node *n = root->rb_node;
2679         struct btrfs_delayed_ref_node *entry;
2680         int alt = 1;
2681         u64 middle;
2682         u64 first = 0, last = 0;
2683
2684         n = rb_first(root);
2685         if (n) {
2686                 entry = rb_entry(n, struct btrfs_delayed_ref_node, rb_node);
2687                 first = entry->bytenr;
2688         }
2689         n = rb_last(root);
2690         if (n) {
2691                 entry = rb_entry(n, struct btrfs_delayed_ref_node, rb_node);
2692                 last = entry->bytenr;
2693         }
2694         n = root->rb_node;
2695
2696         while (n) {
2697                 entry = rb_entry(n, struct btrfs_delayed_ref_node, rb_node);
2698                 WARN_ON(!entry->in_tree);
2699
2700                 middle = entry->bytenr;
2701
2702                 if (alt)
2703                         n = n->rb_left;
2704                 else
2705                         n = n->rb_right;
2706
2707                 alt = 1 - alt;
2708         }
2709         return middle;
2710 }
2711 #endif
2712
2713 static inline u64 heads_to_leaves(struct btrfs_fs_info *fs_info, u64 heads)
2714 {
2715         u64 num_bytes;
2716
2717         num_bytes = heads * (sizeof(struct btrfs_extent_item) +
2718                              sizeof(struct btrfs_extent_inline_ref));
2719         if (!btrfs_fs_incompat(fs_info, SKINNY_METADATA))
2720                 num_bytes += heads * sizeof(struct btrfs_tree_block_info);
2721
2722         /*
2723          * We don't ever fill up leaves all the way so multiply by 2 just to be
2724          * closer to what we're really going to want to use.
2725          */
2726         return div_u64(num_bytes, BTRFS_LEAF_DATA_SIZE(fs_info));
2727 }
2728
2729 /*
2730  * Takes the number of bytes to be csumm'ed and figures out how many leaves it
2731  * would require to store the csums for that many bytes.
2732  */
2733 u64 btrfs_csum_bytes_to_leaves(struct btrfs_fs_info *fs_info, u64 csum_bytes)
2734 {
2735         u64 csum_size;
2736         u64 num_csums_per_leaf;
2737         u64 num_csums;
2738
2739         csum_size = BTRFS_MAX_ITEM_SIZE(fs_info);
2740         num_csums_per_leaf = div64_u64(csum_size,
2741                         (u64)btrfs_super_csum_size(fs_info->super_copy));
2742         num_csums = div64_u64(csum_bytes, fs_info->sectorsize);
2743         num_csums += num_csums_per_leaf - 1;
2744         num_csums = div64_u64(num_csums, num_csums_per_leaf);
2745         return num_csums;
2746 }
2747
2748 int btrfs_check_space_for_delayed_refs(struct btrfs_trans_handle *trans,
2749                                        struct btrfs_fs_info *fs_info)
2750 {
2751         struct btrfs_block_rsv *global_rsv;
2752         u64 num_heads = trans->transaction->delayed_refs.num_heads_ready;
2753         u64 csum_bytes = trans->transaction->delayed_refs.pending_csums;
2754         unsigned int num_dirty_bgs = trans->transaction->num_dirty_bgs;
2755         u64 num_bytes, num_dirty_bgs_bytes;
2756         int ret = 0;
2757
2758         num_bytes = btrfs_calc_trans_metadata_size(fs_info, 1);
2759         num_heads = heads_to_leaves(fs_info, num_heads);
2760         if (num_heads > 1)
2761                 num_bytes += (num_heads - 1) * fs_info->nodesize;
2762         num_bytes <<= 1;
2763         num_bytes += btrfs_csum_bytes_to_leaves(fs_info, csum_bytes) *
2764                                                         fs_info->nodesize;
2765         num_dirty_bgs_bytes = btrfs_calc_trans_metadata_size(fs_info,
2766                                                              num_dirty_bgs);
2767         global_rsv = &fs_info->global_block_rsv;
2768
2769         /*
2770          * If we can't allocate any more chunks lets make sure we have _lots_ of
2771          * wiggle room since running delayed refs can create more delayed refs.
2772          */
2773         if (global_rsv->space_info->full) {
2774                 num_dirty_bgs_bytes <<= 1;
2775                 num_bytes <<= 1;
2776         }
2777
2778         spin_lock(&global_rsv->lock);
2779         if (global_rsv->reserved <= num_bytes + num_dirty_bgs_bytes)
2780                 ret = 1;
2781         spin_unlock(&global_rsv->lock);
2782         return ret;
2783 }
2784
2785 int btrfs_should_throttle_delayed_refs(struct btrfs_trans_handle *trans,
2786                                        struct btrfs_fs_info *fs_info)
2787 {
2788         u64 num_entries =
2789                 atomic_read(&trans->transaction->delayed_refs.num_entries);
2790         u64 avg_runtime;
2791         u64 val;
2792
2793         smp_mb();
2794         avg_runtime = fs_info->avg_delayed_ref_runtime;
2795         val = num_entries * avg_runtime;
2796         if (val >= NSEC_PER_SEC)
2797                 return 1;
2798         if (val >= NSEC_PER_SEC / 2)
2799                 return 2;
2800
2801         return btrfs_check_space_for_delayed_refs(trans, fs_info);
2802 }
2803
2804 struct async_delayed_refs {
2805         struct btrfs_root *root;
2806         u64 transid;
2807         int count;
2808         int error;
2809         int sync;
2810         struct completion wait;
2811         struct btrfs_work work;
2812 };
2813
2814 static inline struct async_delayed_refs *
2815 to_async_delayed_refs(struct btrfs_work *work)
2816 {
2817         return container_of(work, struct async_delayed_refs, work);
2818 }
2819
2820 static void delayed_ref_async_start(struct btrfs_work *work)
2821 {
2822         struct async_delayed_refs *async = to_async_delayed_refs(work);
2823         struct btrfs_trans_handle *trans;
2824         struct btrfs_fs_info *fs_info = async->root->fs_info;
2825         int ret;
2826
2827         /* if the commit is already started, we don't need to wait here */
2828         if (btrfs_transaction_blocked(fs_info))
2829                 goto done;
2830
2831         trans = btrfs_join_transaction(async->root);
2832         if (IS_ERR(trans)) {
2833                 async->error = PTR_ERR(trans);
2834                 goto done;
2835         }
2836
2837         /*
2838          * trans->sync means that when we call end_transaction, we won't
2839          * wait on delayed refs
2840          */
2841         trans->sync = true;
2842
2843         /* Don't bother flushing if we got into a different transaction */
2844         if (trans->transid > async->transid)
2845                 goto end;
2846
2847         ret = btrfs_run_delayed_refs(trans, async->count);
2848         if (ret)
2849                 async->error = ret;
2850 end:
2851         ret = btrfs_end_transaction(trans);
2852         if (ret && !async->error)
2853                 async->error = ret;
2854 done:
2855         if (async->sync)
2856                 complete(&async->wait);
2857         else
2858                 kfree(async);
2859 }
2860
2861 int btrfs_async_run_delayed_refs(struct btrfs_fs_info *fs_info,
2862                                  unsigned long count, u64 transid, int wait)
2863 {
2864         struct async_delayed_refs *async;
2865         int ret;
2866
2867         async = kmalloc(sizeof(*async), GFP_NOFS);
2868         if (!async)
2869                 return -ENOMEM;
2870
2871         async->root = fs_info->tree_root;
2872         async->count = count;
2873         async->error = 0;
2874         async->transid = transid;
2875         if (wait)
2876                 async->sync = 1;
2877         else
2878                 async->sync = 0;
2879         init_completion(&async->wait);
2880
2881         btrfs_init_work(&async->work, btrfs_extent_refs_helper,
2882                         delayed_ref_async_start, NULL, NULL);
2883
2884         btrfs_queue_work(fs_info->extent_workers, &async->work);
2885
2886         if (wait) {
2887                 wait_for_completion(&async->wait);
2888                 ret = async->error;
2889                 kfree(async);
2890                 return ret;
2891         }
2892         return 0;
2893 }
2894
2895 /*
2896  * this starts processing the delayed reference count updates and
2897  * extent insertions we have queued up so far.  count can be
2898  * 0, which means to process everything in the tree at the start
2899  * of the run (but not newly added entries), or it can be some target
2900  * number you'd like to process.
2901  *
2902  * Returns 0 on success or if called with an aborted transaction
2903  * Returns <0 on error and aborts the transaction
2904  */
2905 int btrfs_run_delayed_refs(struct btrfs_trans_handle *trans,
2906                            unsigned long count)
2907 {
2908         struct btrfs_fs_info *fs_info = trans->fs_info;
2909         struct rb_node *node;
2910         struct btrfs_delayed_ref_root *delayed_refs;
2911         struct btrfs_delayed_ref_head *head;
2912         int ret;
2913         int run_all = count == (unsigned long)-1;
2914         bool can_flush_pending_bgs = trans->can_flush_pending_bgs;
2915
2916         /* We'll clean this up in btrfs_cleanup_transaction */
2917         if (trans->aborted)
2918                 return 0;
2919
2920         if (test_bit(BTRFS_FS_CREATING_FREE_SPACE_TREE, &fs_info->flags))
2921                 return 0;
2922
2923         delayed_refs = &trans->transaction->delayed_refs;
2924         if (count == 0)
2925                 count = atomic_read(&delayed_refs->num_entries) * 2;
2926
2927 again:
2928 #ifdef SCRAMBLE_DELAYED_REFS
2929         delayed_refs->run_delayed_start = find_middle(&delayed_refs->root);
2930 #endif
2931         trans->can_flush_pending_bgs = false;
2932         ret = __btrfs_run_delayed_refs(trans, count);
2933         if (ret < 0) {
2934                 btrfs_abort_transaction(trans, ret);
2935                 return ret;
2936         }
2937
2938         if (run_all) {
2939                 if (!list_empty(&trans->new_bgs))
2940                         btrfs_create_pending_block_groups(trans);
2941
2942                 spin_lock(&delayed_refs->lock);
2943                 node = rb_first(&delayed_refs->href_root);
2944                 if (!node) {
2945                         spin_unlock(&delayed_refs->lock);
2946                         goto out;
2947                 }
2948                 head = rb_entry(node, struct btrfs_delayed_ref_head,
2949                                 href_node);
2950                 refcount_inc(&head->refs);
2951                 spin_unlock(&delayed_refs->lock);
2952
2953                 /* Mutex was contended, block until it's released and retry. */
2954                 mutex_lock(&head->mutex);
2955                 mutex_unlock(&head->mutex);
2956
2957                 btrfs_put_delayed_ref_head(head);
2958                 cond_resched();
2959                 goto again;
2960         }
2961 out:
2962         trans->can_flush_pending_bgs = can_flush_pending_bgs;
2963         return 0;
2964 }
2965
2966 int btrfs_set_disk_extent_flags(struct btrfs_trans_handle *trans,
2967                                 struct btrfs_fs_info *fs_info,
2968                                 u64 bytenr, u64 num_bytes, u64 flags,
2969                                 int level, int is_data)
2970 {
2971         struct btrfs_delayed_extent_op *extent_op;
2972         int ret;
2973
2974         extent_op = btrfs_alloc_delayed_extent_op();
2975         if (!extent_op)
2976                 return -ENOMEM;
2977
2978         extent_op->flags_to_set = flags;
2979         extent_op->update_flags = true;
2980         extent_op->update_key = false;
2981         extent_op->is_data = is_data ? true : false;
2982         extent_op->level = level;
2983
2984         ret = btrfs_add_delayed_extent_op(fs_info, trans, bytenr,
2985                                           num_bytes, extent_op);
2986         if (ret)
2987                 btrfs_free_delayed_extent_op(extent_op);
2988         return ret;
2989 }
2990
2991 static noinline int check_delayed_ref(struct btrfs_root *root,
2992                                       struct btrfs_path *path,
2993                                       u64 objectid, u64 offset, u64 bytenr)
2994 {
2995         struct btrfs_delayed_ref_head *head;
2996         struct btrfs_delayed_ref_node *ref;
2997         struct btrfs_delayed_data_ref *data_ref;
2998         struct btrfs_delayed_ref_root *delayed_refs;
2999         struct btrfs_transaction *cur_trans;
3000         struct rb_node *node;
3001         int ret = 0;
3002
3003         spin_lock(&root->fs_info->trans_lock);
3004         cur_trans = root->fs_info->running_transaction;
3005         if (cur_trans)
3006                 refcount_inc(&cur_trans->use_count);
3007         spin_unlock(&root->fs_info->trans_lock);
3008         if (!cur_trans)
3009                 return 0;
3010
3011         delayed_refs = &cur_trans->delayed_refs;
3012         spin_lock(&delayed_refs->lock);
3013         head = btrfs_find_delayed_ref_head(delayed_refs, bytenr);
3014         if (!head) {
3015                 spin_unlock(&delayed_refs->lock);
3016                 btrfs_put_transaction(cur_trans);
3017                 return 0;
3018         }
3019
3020         if (!mutex_trylock(&head->mutex)) {
3021                 refcount_inc(&head->refs);
3022                 spin_unlock(&delayed_refs->lock);
3023
3024                 btrfs_release_path(path);
3025
3026                 /*
3027                  * Mutex was contended, block until it's released and let
3028                  * caller try again
3029                  */
3030                 mutex_lock(&head->mutex);
3031                 mutex_unlock(&head->mutex);
3032                 btrfs_put_delayed_ref_head(head);
3033                 btrfs_put_transaction(cur_trans);
3034                 return -EAGAIN;
3035         }
3036         spin_unlock(&delayed_refs->lock);
3037
3038         spin_lock(&head->lock);
3039         /*
3040          * XXX: We should replace this with a proper search function in the
3041          * future.
3042          */
3043         for (node = rb_first(&head->ref_tree); node; node = rb_next(node)) {
3044                 ref = rb_entry(node, struct btrfs_delayed_ref_node, ref_node);
3045                 /* If it's a shared ref we know a cross reference exists */
3046                 if (ref->type != BTRFS_EXTENT_DATA_REF_KEY) {
3047                         ret = 1;
3048                         break;
3049                 }
3050
3051                 data_ref = btrfs_delayed_node_to_data_ref(ref);
3052
3053                 /*
3054                  * If our ref doesn't match the one we're currently looking at
3055                  * then we have a cross reference.
3056                  */
3057                 if (data_ref->root != root->root_key.objectid ||
3058                     data_ref->objectid != objectid ||
3059                     data_ref->offset != offset) {
3060                         ret = 1;
3061                         break;
3062                 }
3063         }
3064         spin_unlock(&head->lock);
3065         mutex_unlock(&head->mutex);
3066         btrfs_put_transaction(cur_trans);
3067         return ret;
3068 }
3069
3070 static noinline int check_committed_ref(struct btrfs_root *root,
3071                                         struct btrfs_path *path,
3072                                         u64 objectid, u64 offset, u64 bytenr)
3073 {
3074         struct btrfs_fs_info *fs_info = root->fs_info;
3075         struct btrfs_root *extent_root = fs_info->extent_root;
3076         struct extent_buffer *leaf;
3077         struct btrfs_extent_data_ref *ref;
3078         struct btrfs_extent_inline_ref *iref;
3079         struct btrfs_extent_item *ei;
3080         struct btrfs_key key;
3081         u32 item_size;
3082         int type;
3083         int ret;
3084
3085         key.objectid = bytenr;
3086         key.offset = (u64)-1;
3087         key.type = BTRFS_EXTENT_ITEM_KEY;
3088
3089         ret = btrfs_search_slot(NULL, extent_root, &key, path, 0, 0);
3090         if (ret < 0)
3091                 goto out;
3092         BUG_ON(ret == 0); /* Corruption */
3093
3094         ret = -ENOENT;
3095         if (path->slots[0] == 0)
3096                 goto out;
3097
3098         path->slots[0]--;
3099         leaf = path->nodes[0];
3100         btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);
3101
3102         if (key.objectid != bytenr || key.type != BTRFS_EXTENT_ITEM_KEY)
3103                 goto out;
3104
3105         ret = 1;
3106         item_size = btrfs_item_size_nr(leaf, path->slots[0]);
3107         ei = btrfs_item_ptr(leaf, path->slots[0], struct btrfs_extent_item);
3108
3109         if (item_size != sizeof(*ei) +
3110             btrfs_extent_inline_ref_size(BTRFS_EXTENT_DATA_REF_KEY))
3111                 goto out;
3112
3113         if (btrfs_extent_generation(leaf, ei) <=
3114             btrfs_root_last_snapshot(&root->root_item))
3115                 goto out;
3116
3117         iref = (struct btrfs_extent_inline_ref *)(ei + 1);
3118
3119         type = btrfs_get_extent_inline_ref_type(leaf, iref, BTRFS_REF_TYPE_DATA);
3120         if (type != BTRFS_EXTENT_DATA_REF_KEY)
3121                 goto out;
3122
3123         ref = (struct btrfs_extent_data_ref *)(&iref->offset);
3124         if (btrfs_extent_refs(leaf, ei) !=
3125             btrfs_extent_data_ref_count(leaf, ref) ||
3126             btrfs_extent_data_ref_root(leaf, ref) !=
3127             root->root_key.objectid ||
3128             btrfs_extent_data_ref_objectid(leaf, ref) != objectid ||
3129             btrfs_extent_data_ref_offset(leaf, ref) != offset)
3130                 goto out;
3131
3132         ret = 0;
3133 out:
3134         return ret;
3135 }
3136
3137 int btrfs_cross_ref_exist(struct btrfs_root *root, u64 objectid, u64 offset,
3138                           u64 bytenr)
3139 {
3140         struct btrfs_path *path;
3141         int ret;
3142         int ret2;
3143
3144         path = btrfs_alloc_path();
3145         if (!path)
3146                 return -ENOMEM;
3147
3148         do {
3149                 ret = check_committed_ref(root, path, objectid,
3150                                           offset, bytenr);
3151                 if (ret && ret != -ENOENT)
3152                         goto out;
3153
3154                 ret2 = check_delayed_ref(root, path, objectid,
3155                                          offset, bytenr);
3156         } while (ret2 == -EAGAIN);
3157
3158         if (ret2 && ret2 != -ENOENT) {
3159                 ret = ret2;
3160                 goto out;
3161         }
3162
3163         if (ret != -ENOENT || ret2 != -ENOENT)
3164                 ret = 0;
3165 out:
3166         btrfs_free_path(path);
3167         if (root->root_key.objectid == BTRFS_DATA_RELOC_TREE_OBJECTID)
3168                 WARN_ON(ret > 0);
3169         return ret;
3170 }
3171
3172 static int __btrfs_mod_ref(struct btrfs_trans_handle *trans,
3173                            struct btrfs_root *root,
3174                            struct extent_buffer *buf,
3175                            int full_backref, int inc)
3176 {
3177         struct btrfs_fs_info *fs_info = root->fs_info;
3178         u64 bytenr;
3179         u64 num_bytes;
3180         u64 parent;
3181         u64 ref_root;
3182         u32 nritems;
3183         struct btrfs_key key;
3184         struct btrfs_file_extent_item *fi;
3185         int i;
3186         int level;
3187         int ret = 0;
3188         int (*process_func)(struct btrfs_trans_handle *,
3189                             struct btrfs_root *,
3190                             u64, u64, u64, u64, u64, u64);
3191
3192
3193         if (btrfs_is_testing(fs_info))
3194                 return 0;
3195
3196         ref_root = btrfs_header_owner(buf);
3197         nritems = btrfs_header_nritems(buf);
3198         level = btrfs_header_level(buf);
3199
3200         if (!test_bit(BTRFS_ROOT_REF_COWS, &root->state) && level == 0)
3201                 return 0;
3202
3203         if (inc)
3204                 process_func = btrfs_inc_extent_ref;
3205         else
3206                 process_func = btrfs_free_extent;
3207
3208         if (full_backref)
3209                 parent = buf->start;
3210         else
3211                 parent = 0;
3212
3213         for (i = 0; i < nritems; i++) {
3214                 if (level == 0) {
3215                         btrfs_item_key_to_cpu(buf, &key, i);
3216                         if (key.type != BTRFS_EXTENT_DATA_KEY)
3217                                 continue;
3218                         fi = btrfs_item_ptr(buf, i,
3219                                             struct btrfs_file_extent_item);
3220                         if (btrfs_file_extent_type(buf, fi) ==
3221                             BTRFS_FILE_EXTENT_INLINE)
3222                                 continue;
3223                         bytenr = btrfs_file_extent_disk_bytenr(buf, fi);
3224                         if (bytenr == 0)
3225                                 continue;
3226
3227                         num_bytes = btrfs_file_extent_disk_num_bytes(buf, fi);
3228                         key.offset -= btrfs_file_extent_offset(buf, fi);
3229                         ret = process_func(trans, root, bytenr, num_bytes,
3230                                            parent, ref_root, key.objectid,
3231                                            key.offset);
3232                         if (ret)
3233                                 goto fail;
3234                 } else {
3235                         bytenr = btrfs_node_blockptr(buf, i);
3236                         num_bytes = fs_info->nodesize;
3237                         ret = process_func(trans, root, bytenr, num_bytes,
3238                                            parent, ref_root, level - 1, 0);
3239                         if (ret)
3240                                 goto fail;
3241                 }
3242         }
3243         return 0;
3244 fail:
3245         return ret;
3246 }
3247
3248 int btrfs_inc_ref(struct btrfs_trans_handle *trans, struct btrfs_root *root,
3249                   struct extent_buffer *buf, int full_backref)
3250 {
3251         return __btrfs_mod_ref(trans, root, buf, full_backref, 1);
3252 }
3253
3254 int btrfs_dec_ref(struct btrfs_trans_handle *trans, struct btrfs_root *root,
3255                   struct extent_buffer *buf, int full_backref)
3256 {
3257         return __btrfs_mod_ref(trans, root, buf, full_backref, 0);
3258 }
3259
3260 static int write_one_cache_group(struct btrfs_trans_handle *trans,
3261                                  struct btrfs_fs_info *fs_info,
3262                                  struct btrfs_path *path,
3263                                  struct btrfs_block_group_cache *cache)
3264 {
3265         int ret;
3266         struct btrfs_root *extent_root = fs_info->extent_root;
3267         unsigned long bi;
3268         struct extent_buffer *leaf;
3269
3270         ret = btrfs_search_slot(trans, extent_root, &cache->key, path, 0, 1);
3271         if (ret) {
3272                 if (ret > 0)
3273                         ret = -ENOENT;
3274                 goto fail;
3275         }
3276
3277         leaf = path->nodes[0];
3278         bi = btrfs_item_ptr_offset(leaf, path->slots[0]);
3279         write_extent_buffer(leaf, &cache->item, bi, sizeof(cache->item));
3280         btrfs_mark_buffer_dirty(leaf);
3281 fail:
3282         btrfs_release_path(path);
3283         return ret;
3284
3285 }
3286
3287 static struct btrfs_block_group_cache *
3288 next_block_group(struct btrfs_fs_info *fs_info,
3289                  struct btrfs_block_group_cache *cache)
3290 {
3291         struct rb_node *node;
3292
3293         spin_lock(&fs_info->block_group_cache_lock);
3294
3295         /* If our block group was removed, we need a full search. */
3296         if (RB_EMPTY_NODE(&cache->cache_node)) {
3297                 const u64 next_bytenr = cache->key.objectid + cache->key.offset;
3298
3299                 spin_unlock(&fs_info->block_group_cache_lock);
3300                 btrfs_put_block_group(cache);
3301                 cache = btrfs_lookup_first_block_group(fs_info, next_bytenr); return cache;
3302         }
3303         node = rb_next(&cache->cache_node);
3304         btrfs_put_block_group(cache);
3305         if (node) {
3306                 cache = rb_entry(node, struct btrfs_block_group_cache,
3307                                  cache_node);
3308                 btrfs_get_block_group(cache);
3309         } else
3310                 cache = NULL;
3311         spin_unlock(&fs_info->block_group_cache_lock);
3312         return cache;
3313 }
3314
3315 static int cache_save_setup(struct btrfs_block_group_cache *block_group,
3316                             struct btrfs_trans_handle *trans,
3317                             struct btrfs_path *path)
3318 {
3319         struct btrfs_fs_info *fs_info = block_group->fs_info;
3320         struct btrfs_root *root = fs_info->tree_root;
3321         struct inode *inode = NULL;
3322         struct extent_changeset *data_reserved = NULL;
3323         u64 alloc_hint = 0;
3324         int dcs = BTRFS_DC_ERROR;
3325         u64 num_pages = 0;
3326         int retries = 0;
3327         int ret = 0;
3328
3329         /*
3330          * If this block group is smaller than 100 megs don't bother caching the
3331          * block group.
3332          */
3333         if (block_group->key.offset < (100 * SZ_1M)) {
3334                 spin_lock(&block_group->lock);
3335                 block_group->disk_cache_state = BTRFS_DC_WRITTEN;
3336                 spin_unlock(&block_group->lock);
3337                 return 0;
3338         }
3339
3340         if (trans->aborted)
3341                 return 0;
3342 again:
3343         inode = lookup_free_space_inode(fs_info, block_group, path);
3344         if (IS_ERR(inode) && PTR_ERR(inode) != -ENOENT) {
3345                 ret = PTR_ERR(inode);
3346                 btrfs_release_path(path);
3347                 goto out;
3348         }
3349
3350         if (IS_ERR(inode)) {
3351                 BUG_ON(retries);
3352                 retries++;
3353
3354                 if (block_group->ro)
3355                         goto out_free;
3356
3357                 ret = create_free_space_inode(fs_info, trans, block_group,
3358                                               path);
3359                 if (ret)
3360                         goto out_free;
3361                 goto again;
3362         }
3363
3364         /*
3365          * We want to set the generation to 0, that way if anything goes wrong
3366          * from here on out we know not to trust this cache when we load up next
3367          * time.
3368          */
3369         BTRFS_I(inode)->generation = 0;
3370         ret = btrfs_update_inode(trans, root, inode);
3371         if (ret) {
3372                 /*
3373                  * So theoretically we could recover from this, simply set the
3374                  * super cache generation to 0 so we know to invalidate the
3375                  * cache, but then we'd have to keep track of the block groups
3376                  * that fail this way so we know we _have_ to reset this cache
3377                  * before the next commit or risk reading stale cache.  So to
3378                  * limit our exposure to horrible edge cases lets just abort the
3379                  * transaction, this only happens in really bad situations
3380                  * anyway.
3381                  */
3382                 btrfs_abort_transaction(trans, ret);
3383                 goto out_put;
3384         }
3385         WARN_ON(ret);
3386
3387         /* We've already setup this transaction, go ahead and exit */
3388         if (block_group->cache_generation == trans->transid &&
3389             i_size_read(inode)) {
3390                 dcs = BTRFS_DC_SETUP;
3391                 goto out_put;
3392         }
3393
3394         if (i_size_read(inode) > 0) {
3395                 ret = btrfs_check_trunc_cache_free_space(fs_info,
3396                                         &fs_info->global_block_rsv);
3397                 if (ret)
3398                         goto out_put;
3399
3400                 ret = btrfs_truncate_free_space_cache(trans, NULL, inode);
3401                 if (ret)
3402                         goto out_put;
3403         }
3404
3405         spin_lock(&block_group->lock);
3406         if (block_group->cached != BTRFS_CACHE_FINISHED ||
3407             !btrfs_test_opt(fs_info, SPACE_CACHE)) {
3408                 /*
3409                  * don't bother trying to write stuff out _if_
3410                  * a) we're not cached,
3411                  * b) we're with nospace_cache mount option,
3412                  * c) we're with v2 space_cache (FREE_SPACE_TREE).
3413                  */
3414                 dcs = BTRFS_DC_WRITTEN;
3415                 spin_unlock(&block_group->lock);
3416                 goto out_put;
3417         }
3418         spin_unlock(&block_group->lock);
3419
3420         /*
3421          * We hit an ENOSPC when setting up the cache in this transaction, just
3422          * skip doing the setup, we've already cleared the cache so we're safe.
3423          */
3424         if (test_bit(BTRFS_TRANS_CACHE_ENOSPC, &trans->transaction->flags)) {
3425                 ret = -ENOSPC;
3426                 goto out_put;
3427         }
3428
3429         /*
3430          * Try to preallocate enough space based on how big the block group is.
3431          * Keep in mind this has to include any pinned space which could end up
3432          * taking up quite a bit since it's not folded into the other space
3433          * cache.
3434          */
3435         num_pages = div_u64(block_group->key.offset, SZ_256M);
3436         if (!num_pages)
3437                 num_pages = 1;
3438
3439         num_pages *= 16;
3440         num_pages *= PAGE_SIZE;
3441
3442         ret = btrfs_check_data_free_space(inode, &data_reserved, 0, num_pages);
3443         if (ret)
3444                 goto out_put;
3445
3446         ret = btrfs_prealloc_file_range_trans(inode, trans, 0, 0, num_pages,
3447                                               num_pages, num_pages,
3448                                               &alloc_hint);
3449         /*
3450          * Our cache requires contiguous chunks so that we don't modify a bunch
3451          * of metadata or split extents when writing the cache out, which means
3452          * we can enospc if we are heavily fragmented in addition to just normal
3453          * out of space conditions.  So if we hit this just skip setting up any
3454          * other block groups for this transaction, maybe we'll unpin enough
3455          * space the next time around.
3456          */
3457         if (!ret)
3458                 dcs = BTRFS_DC_SETUP;
3459         else if (ret == -ENOSPC)
3460                 set_bit(BTRFS_TRANS_CACHE_ENOSPC, &trans->transaction->flags);
3461
3462 out_put:
3463         iput(inode);
3464 out_free:
3465         btrfs_release_path(path);
3466 out:
3467         spin_lock(&block_group->lock);
3468         if (!ret && dcs == BTRFS_DC_SETUP)
3469                 block_group->cache_generation = trans->transid;
3470         block_group->disk_cache_state = dcs;
3471         spin_unlock(&block_group->lock);
3472
3473         extent_changeset_free(data_reserved);
3474         return ret;
3475 }
3476
3477 int btrfs_setup_space_cache(struct btrfs_trans_handle *trans,
3478                             struct btrfs_fs_info *fs_info)
3479 {
3480         struct btrfs_block_group_cache *cache, *tmp;
3481         struct btrfs_transaction *cur_trans = trans->transaction;
3482         struct btrfs_path *path;
3483
3484         if (list_empty(&cur_trans->dirty_bgs) ||
3485             !btrfs_test_opt(fs_info, SPACE_CACHE))
3486                 return 0;
3487
3488         path = btrfs_alloc_path();
3489         if (!path)
3490                 return -ENOMEM;
3491
3492         /* Could add new block groups, use _safe just in case */
3493         list_for_each_entry_safe(cache, tmp, &cur_trans->dirty_bgs,
3494                                  dirty_list) {
3495                 if (cache->disk_cache_state == BTRFS_DC_CLEAR)
3496                         cache_save_setup(cache, trans, path);
3497         }
3498
3499         btrfs_free_path(path);
3500         return 0;
3501 }
3502
3503 /*
3504  * transaction commit does final block group cache writeback during a
3505  * critical section where nothing is allowed to change the FS.  This is
3506  * required in order for the cache to actually match the block group,
3507  * but can introduce a lot of latency into the commit.
3508  *
3509  * So, btrfs_start_dirty_block_groups is here to kick off block group
3510  * cache IO.  There's a chance we'll have to redo some of it if the
3511  * block group changes again during the commit, but it greatly reduces
3512  * the commit latency by getting rid of the easy block groups while
3513  * we're still allowing others to join the commit.
3514  */
3515 int btrfs_start_dirty_block_groups(struct btrfs_trans_handle *trans)
3516 {
3517         struct btrfs_fs_info *fs_info = trans->fs_info;
3518         struct btrfs_block_group_cache *cache;
3519         struct btrfs_transaction *cur_trans = trans->transaction;
3520         int ret = 0;
3521         int should_put;
3522         struct btrfs_path *path = NULL;
3523         LIST_HEAD(dirty);
3524         struct list_head *io = &cur_trans->io_bgs;
3525         int num_started = 0;
3526         int loops = 0;
3527
3528         spin_lock(&cur_trans->dirty_bgs_lock);
3529         if (list_empty(&cur_trans->dirty_bgs)) {
3530                 spin_unlock(&cur_trans->dirty_bgs_lock);
3531                 return 0;
3532         }
3533         list_splice_init(&cur_trans->dirty_bgs, &dirty);
3534         spin_unlock(&cur_trans->dirty_bgs_lock);
3535
3536 again:
3537         /*
3538          * make sure all the block groups on our dirty list actually
3539          * exist
3540          */
3541         btrfs_create_pending_block_groups(trans);
3542
3543         if (!path) {
3544                 path = btrfs_alloc_path();
3545                 if (!path)
3546                         return -ENOMEM;
3547         }
3548
3549         /*
3550          * cache_write_mutex is here only to save us from balance or automatic
3551          * removal of empty block groups deleting this block group while we are
3552          * writing out the cache
3553          */
3554         mutex_lock(&trans->transaction->cache_write_mutex);
3555         while (!list_empty(&dirty)) {
3556                 cache = list_first_entry(&dirty,
3557                                          struct btrfs_block_group_cache,
3558                                          dirty_list);
3559                 /*
3560                  * this can happen if something re-dirties a block
3561                  * group that is already under IO.  Just wait for it to
3562                  * finish and then do it all again
3563                  */
3564                 if (!list_empty(&cache->io_list)) {
3565                         list_del_init(&cache->io_list);
3566                         btrfs_wait_cache_io(trans, cache, path);
3567                         btrfs_put_block_group(cache);
3568      &nbs