a42419c276e21686dfd9949497541d4936b17b44
[linux-2.6.git] / fs / btrfs / extent-tree.c
1 /*
2  * Copyright (C) 2007 Oracle.  All rights reserved.
3  *
4  * This program is free software; you can redistribute it and/or
5  * modify it under the terms of the GNU General Public
6  * License v2 as published by the Free Software Foundation.
7  *
8  * This program is distributed in the hope that it will be useful,
9  * but WITHOUT ANY WARRANTY; without even the implied warranty of
10  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
11  * General Public License for more details.
12  *
13  * You should have received a copy of the GNU General Public
14  * License along with this program; if not, write to the
15  * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
16  * Boston, MA 021110-1307, USA.
17  */
18 #include <linux/sched.h>
19 #include <linux/pagemap.h>
20 #include <linux/writeback.h>
21 #include <linux/blkdev.h>
22 #include <linux/sort.h>
23 #include <linux/rcupdate.h>
24 #include "compat.h"
25 #include "hash.h"
26 #include "crc32c.h"
27 #include "ctree.h"
28 #include "disk-io.h"
29 #include "print-tree.h"
30 #include "transaction.h"
31 #include "volumes.h"
32 #include "locking.h"
33 #include "free-space-cache.h"
34
35 static int update_reserved_extents(struct btrfs_root *root,
36                                    u64 bytenr, u64 num, int reserve);
37 static int update_block_group(struct btrfs_trans_handle *trans,
38                               struct btrfs_root *root,
39                               u64 bytenr, u64 num_bytes, int alloc,
40                               int mark_free);
41 static int __btrfs_free_extent(struct btrfs_trans_handle *trans,
42                                 struct btrfs_root *root,
43                                 u64 bytenr, u64 num_bytes, u64 parent,
44                                 u64 root_objectid, u64 owner_objectid,
45                                 u64 owner_offset, int refs_to_drop,
46                                 struct btrfs_delayed_extent_op *extra_op);
47 static void __run_delayed_extent_op(struct btrfs_delayed_extent_op *extent_op,
48                                     struct extent_buffer *leaf,
49                                     struct btrfs_extent_item *ei);
50 static int alloc_reserved_file_extent(struct btrfs_trans_handle *trans,
51                                       struct btrfs_root *root,
52                                       u64 parent, u64 root_objectid,
53                                       u64 flags, u64 owner, u64 offset,
54                                       struct btrfs_key *ins, int ref_mod);
55 static int alloc_reserved_tree_block(struct btrfs_trans_handle *trans,
56                                      struct btrfs_root *root,
57                                      u64 parent, u64 root_objectid,
58                                      u64 flags, struct btrfs_disk_key *key,
59                                      int level, struct btrfs_key *ins);
60
61 static int do_chunk_alloc(struct btrfs_trans_handle *trans,
62                           struct btrfs_root *extent_root, u64 alloc_bytes,
63                           u64 flags, int force);
64
65 static int block_group_bits(struct btrfs_block_group_cache *cache, u64 bits)
66 {
67         return (cache->flags & bits) == bits;
68 }
69
70 /*
71  * this adds the block group to the fs_info rb tree for the block group
72  * cache
73  */
74 static int btrfs_add_block_group_cache(struct btrfs_fs_info *info,
75                                 struct btrfs_block_group_cache *block_group)
76 {
77         struct rb_node **p;
78         struct rb_node *parent = NULL;
79         struct btrfs_block_group_cache *cache;
80
81         spin_lock(&info->block_group_cache_lock);
82         p = &info->block_group_cache_tree.rb_node;
83
84         while (*p) {
85                 parent = *p;
86                 cache = rb_entry(parent, struct btrfs_block_group_cache,
87                                  cache_node);
88                 if (block_group->key.objectid < cache->key.objectid) {
89                         p = &(*p)->rb_left;
90                 } else if (block_group->key.objectid > cache->key.objectid) {
91                         p = &(*p)->rb_right;
92                 } else {
93                         spin_unlock(&info->block_group_cache_lock);
94                         return -EEXIST;
95                 }
96         }
97
98         rb_link_node(&block_group->cache_node, parent, p);
99         rb_insert_color(&block_group->cache_node,
100                         &info->block_group_cache_tree);
101         spin_unlock(&info->block_group_cache_lock);
102
103         return 0;
104 }
105
106 /*
107  * This will return the block group at or after bytenr if contains is 0, else
108  * it will return the block group that contains the bytenr
109  */
110 static struct btrfs_block_group_cache *
111 block_group_cache_tree_search(struct btrfs_fs_info *info, u64 bytenr,
112                               int contains)
113 {
114         struct btrfs_block_group_cache *cache, *ret = NULL;
115         struct rb_node *n;
116         u64 end, start;
117
118         spin_lock(&info->block_group_cache_lock);
119         n = info->block_group_cache_tree.rb_node;
120
121         while (n) {
122                 cache = rb_entry(n, struct btrfs_block_group_cache,
123                                  cache_node);
124                 end = cache->key.objectid + cache->key.offset - 1;
125                 start = cache->key.objectid;
126
127                 if (bytenr < start) {
128                         if (!contains && (!ret || start < ret->key.objectid))
129                                 ret = cache;
130                         n = n->rb_left;
131                 } else if (bytenr > start) {
132                         if (contains && bytenr <= end) {
133                                 ret = cache;
134                                 break;
135                         }
136                         n = n->rb_right;
137                 } else {
138                         ret = cache;
139                         break;
140                 }
141         }
142         if (ret)
143                 atomic_inc(&ret->count);
144         spin_unlock(&info->block_group_cache_lock);
145
146         return ret;
147 }
148
149 /*
150  * this is only called by cache_block_group, since we could have freed extents
151  * we need to check the pinned_extents for any extents that can't be used yet
152  * since their free space will be released as soon as the transaction commits.
153  */
154 static int add_new_free_space(struct btrfs_block_group_cache *block_group,
155                               struct btrfs_fs_info *info, u64 start, u64 end)
156 {
157         u64 extent_start, extent_end, size;
158         int ret;
159
160         while (start < end) {
161                 ret = find_first_extent_bit(&info->pinned_extents, start,
162                                             &extent_start, &extent_end,
163                                             EXTENT_DIRTY);
164                 if (ret)
165                         break;
166
167                 if (extent_start == start) {
168                         start = extent_end + 1;
169                 } else if (extent_start > start && extent_start < end) {
170                         size = extent_start - start;
171                         ret = btrfs_add_free_space(block_group, start,
172                                                    size);
173                         BUG_ON(ret);
174                         start = extent_end + 1;
175                 } else {
176                         break;
177                 }
178         }
179
180         if (start < end) {
181                 size = end - start;
182                 ret = btrfs_add_free_space(block_group, start, size);
183                 BUG_ON(ret);
184         }
185
186         return 0;
187 }
188
189 static int remove_sb_from_cache(struct btrfs_root *root,
190                                 struct btrfs_block_group_cache *cache)
191 {
192         u64 bytenr;
193         u64 *logical;
194         int stripe_len;
195         int i, nr, ret;
196
197         for (i = 0; i < BTRFS_SUPER_MIRROR_MAX; i++) {
198                 bytenr = btrfs_sb_offset(i);
199                 ret = btrfs_rmap_block(&root->fs_info->mapping_tree,
200                                        cache->key.objectid, bytenr, 0,
201                                        &logical, &nr, &stripe_len);
202                 BUG_ON(ret);
203                 while (nr--) {
204                         btrfs_remove_free_space(cache, logical[nr],
205                                                 stripe_len);
206                 }
207                 kfree(logical);
208         }
209         return 0;
210 }
211
212 static int cache_block_group(struct btrfs_root *root,
213                              struct btrfs_block_group_cache *block_group)
214 {
215         struct btrfs_path *path;
216         int ret = 0;
217         struct btrfs_key key;
218         struct extent_buffer *leaf;
219         int slot;
220         u64 last;
221
222         if (!block_group)
223                 return 0;
224
225         root = root->fs_info->extent_root;
226
227         if (block_group->cached)
228                 return 0;
229
230         path = btrfs_alloc_path();
231         if (!path)
232                 return -ENOMEM;
233
234         path->reada = 2;
235         /*
236          * we get into deadlocks with paths held by callers of this function.
237          * since the alloc_mutex is protecting things right now, just
238          * skip the locking here
239          */
240         path->skip_locking = 1;
241         last = max_t(u64, block_group->key.objectid, BTRFS_SUPER_INFO_OFFSET);
242         key.objectid = last;
243         key.offset = 0;
244         btrfs_set_key_type(&key, BTRFS_EXTENT_ITEM_KEY);
245         ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
246         if (ret < 0)
247                 goto err;
248
249         while (1) {
250                 leaf = path->nodes[0];
251                 slot = path->slots[0];
252                 if (slot >= btrfs_header_nritems(leaf)) {
253                         ret = btrfs_next_leaf(root, path);
254                         if (ret < 0)
255                                 goto err;
256                         if (ret == 0)
257                                 continue;
258                         else
259                                 break;
260                 }
261                 btrfs_item_key_to_cpu(leaf, &key, slot);
262                 if (key.objectid < block_group->key.objectid)
263                         goto next;
264
265                 if (key.objectid >= block_group->key.objectid +
266                     block_group->key.offset)
267                         break;
268
269                 if (btrfs_key_type(&key) == BTRFS_EXTENT_ITEM_KEY) {
270                         add_new_free_space(block_group, root->fs_info, last,
271                                            key.objectid);
272
273                         last = key.objectid + key.offset;
274                 }
275 next:
276                 path->slots[0]++;
277         }
278
279         add_new_free_space(block_group, root->fs_info, last,
280                            block_group->key.objectid +
281                            block_group->key.offset);
282
283         block_group->cached = 1;
284         remove_sb_from_cache(root, block_group);
285         ret = 0;
286 err:
287         btrfs_free_path(path);
288         return ret;
289 }
290
291 /*
292  * return the block group that starts at or after bytenr
293  */
294 static struct btrfs_block_group_cache *
295 btrfs_lookup_first_block_group(struct btrfs_fs_info *info, u64 bytenr)
296 {
297         struct btrfs_block_group_cache *cache;
298
299         cache = block_group_cache_tree_search(info, bytenr, 0);
300
301         return cache;
302 }
303
304 /*
305  * return the block group that contains the given bytenr
306  */
307 struct btrfs_block_group_cache *btrfs_lookup_block_group(
308                                                  struct btrfs_fs_info *info,
309                                                  u64 bytenr)
310 {
311         struct btrfs_block_group_cache *cache;
312
313         cache = block_group_cache_tree_search(info, bytenr, 1);
314
315         return cache;
316 }
317
318 void btrfs_put_block_group(struct btrfs_block_group_cache *cache)
319 {
320         if (atomic_dec_and_test(&cache->count))
321                 kfree(cache);
322 }
323
324 static struct btrfs_space_info *__find_space_info(struct btrfs_fs_info *info,
325                                                   u64 flags)
326 {
327         struct list_head *head = &info->space_info;
328         struct btrfs_space_info *found;
329
330         rcu_read_lock();
331         list_for_each_entry_rcu(found, head, list) {
332                 if (found->flags == flags) {
333                         rcu_read_unlock();
334                         return found;
335                 }
336         }
337         rcu_read_unlock();
338         return NULL;
339 }
340
341 /*
342  * after adding space to the filesystem, we need to clear the full flags
343  * on all the space infos.
344  */
345 void btrfs_clear_space_info_full(struct btrfs_fs_info *info)
346 {
347         struct list_head *head = &info->space_info;
348         struct btrfs_space_info *found;
349
350         rcu_read_lock();
351         list_for_each_entry_rcu(found, head, list)
352                 found->full = 0;
353         rcu_read_unlock();
354 }
355
356 static u64 div_factor(u64 num, int factor)
357 {
358         if (factor == 10)
359                 return num;
360         num *= factor;
361         do_div(num, 10);
362         return num;
363 }
364
365 u64 btrfs_find_block_group(struct btrfs_root *root,
366                            u64 search_start, u64 search_hint, int owner)
367 {
368         struct btrfs_block_group_cache *cache;
369         u64 used;
370         u64 last = max(search_hint, search_start);
371         u64 group_start = 0;
372         int full_search = 0;
373         int factor = 9;
374         int wrapped = 0;
375 again:
376         while (1) {
377                 cache = btrfs_lookup_first_block_group(root->fs_info, last);
378                 if (!cache)
379                         break;
380
381                 spin_lock(&cache->lock);
382                 last = cache->key.objectid + cache->key.offset;
383                 used = btrfs_block_group_used(&cache->item);
384
385                 if ((full_search || !cache->ro) &&
386                     block_group_bits(cache, BTRFS_BLOCK_GROUP_METADATA)) {
387                         if (used + cache->pinned + cache->reserved <
388                             div_factor(cache->key.offset, factor)) {
389                                 group_start = cache->key.objectid;
390                                 spin_unlock(&cache->lock);
391                                 btrfs_put_block_group(cache);
392                                 goto found;
393                         }
394                 }
395                 spin_unlock(&cache->lock);
396                 btrfs_put_block_group(cache);
397                 cond_resched();
398         }
399         if (!wrapped) {
400                 last = search_start;
401                 wrapped = 1;
402                 goto again;
403         }
404         if (!full_search && factor < 10) {
405                 last = search_start;
406                 full_search = 1;
407                 factor = 10;
408                 goto again;
409         }
410 found:
411         return group_start;
412 }
413
414 /* simple helper to search for an existing extent at a given offset */
415 int btrfs_lookup_extent(struct btrfs_root *root, u64 start, u64 len)
416 {
417         int ret;
418         struct btrfs_key key;
419         struct btrfs_path *path;
420
421         path = btrfs_alloc_path();
422         BUG_ON(!path);
423         key.objectid = start;
424         key.offset = len;
425         btrfs_set_key_type(&key, BTRFS_EXTENT_ITEM_KEY);
426         ret = btrfs_search_slot(NULL, root->fs_info->extent_root, &key, path,
427                                 0, 0);
428         btrfs_free_path(path);
429         return ret;
430 }
431
432 /*
433  * Back reference rules.  Back refs have three main goals:
434  *
435  * 1) differentiate between all holders of references to an extent so that
436  *    when a reference is dropped we can make sure it was a valid reference
437  *    before freeing the extent.
438  *
439  * 2) Provide enough information to quickly find the holders of an extent
440  *    if we notice a given block is corrupted or bad.
441  *
442  * 3) Make it easy to migrate blocks for FS shrinking or storage pool
443  *    maintenance.  This is actually the same as #2, but with a slightly
444  *    different use case.
445  *
446  * There are two kinds of back refs. The implicit back refs is optimized
447  * for pointers in non-shared tree blocks. For a given pointer in a block,
448  * back refs of this kind provide information about the block's owner tree
449  * and the pointer's key. These information allow us to find the block by
450  * b-tree searching. The full back refs is for pointers in tree blocks not
451  * referenced by their owner trees. The location of tree block is recorded
452  * in the back refs. Actually the full back refs is generic, and can be
453  * used in all cases the implicit back refs is used. The major shortcoming
454  * of the full back refs is its overhead. Every time a tree block gets
455  * COWed, we have to update back refs entry for all pointers in it.
456  *
457  * For a newly allocated tree block, we use implicit back refs for
458  * pointers in it. This means most tree related operations only involve
459  * implicit back refs. For a tree block created in old transaction, the
460  * only way to drop a reference to it is COW it. So we can detect the
461  * event that tree block loses its owner tree's reference and do the
462  * back refs conversion.
463  *
464  * When a tree block is COW'd through a tree, there are four cases:
465  *
466  * The reference count of the block is one and the tree is the block's
467  * owner tree. Nothing to do in this case.
468  *
469  * The reference count of the block is one and the tree is not the
470  * block's owner tree. In this case, full back refs is used for pointers
471  * in the block. Remove these full back refs, add implicit back refs for
472  * every pointers in the new block.
473  *
474  * The reference count of the block is greater than one and the tree is
475  * the block's owner tree. In this case, implicit back refs is used for
476  * pointers in the block. Add full back refs for every pointers in the
477  * block, increase lower level extents' reference counts. The original
478  * implicit back refs are entailed to the new block.
479  *
480  * The reference count of the block is greater than one and the tree is
481  * not the block's owner tree. Add implicit back refs for every pointer in
482  * the new block, increase lower level extents' reference count.
483  *
484  * Back Reference Key composing:
485  *
486  * The key objectid corresponds to the first byte in the extent,
487  * The key type is used to differentiate between types of back refs.
488  * There are different meanings of the key offset for different types
489  * of back refs.
490  *
491  * File extents can be referenced by:
492  *
493  * - multiple snapshots, subvolumes, or different generations in one subvol
494  * - different files inside a single subvolume
495  * - different offsets inside a file (bookend extents in file.c)
496  *
497  * The extent ref structure for the implicit back refs has fields for:
498  *
499  * - Objectid of the subvolume root
500  * - objectid of the file holding the reference
501  * - original offset in the file
502  * - how many bookend extents
503  *
504  * The key offset for the implicit back refs is hash of the first
505  * three fields.
506  *
507  * The extent ref structure for the full back refs has field for:
508  *
509  * - number of pointers in the tree leaf
510  *
511  * The key offset for the implicit back refs is the first byte of
512  * the tree leaf
513  *
514  * When a file extent is allocated, The implicit back refs is used.
515  * the fields are filled in:
516  *
517  *     (root_key.objectid, inode objectid, offset in file, 1)
518  *
519  * When a file extent is removed file truncation, we find the
520  * corresponding implicit back refs and check the following fields:
521  *
522  *     (btrfs_header_owner(leaf), inode objectid, offset in file)
523  *
524  * Btree extents can be referenced by:
525  *
526  * - Different subvolumes
527  *
528  * Both the implicit back refs and the full back refs for tree blocks
529  * only consist of key. The key offset for the implicit back refs is
530  * objectid of block's owner tree. The key offset for the full back refs
531  * is the first byte of parent block.
532  *
533  * When implicit back refs is used, information about the lowest key and
534  * level of the tree block are required. These information are stored in
535  * tree block info structure.
536  */
537
538 #ifdef BTRFS_COMPAT_EXTENT_TREE_V0
539 static int convert_extent_item_v0(struct btrfs_trans_handle *trans,
540                                   struct btrfs_root *root,
541                                   struct btrfs_path *path,
542                                   u64 owner, u32 extra_size)
543 {
544         struct btrfs_extent_item *item;
545         struct btrfs_extent_item_v0 *ei0;
546         struct btrfs_extent_ref_v0 *ref0;
547         struct btrfs_tree_block_info *bi;
548         struct extent_buffer *leaf;
549         struct btrfs_key key;
550         struct btrfs_key found_key;
551         u32 new_size = sizeof(*item);
552         u64 refs;
553         int ret;
554
555         leaf = path->nodes[0];
556         BUG_ON(btrfs_item_size_nr(leaf, path->slots[0]) != sizeof(*ei0));
557
558         btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);
559         ei0 = btrfs_item_ptr(leaf, path->slots[0],
560                              struct btrfs_extent_item_v0);
561         refs = btrfs_extent_refs_v0(leaf, ei0);
562
563         if (owner == (u64)-1) {
564                 while (1) {
565                         if (path->slots[0] >= btrfs_header_nritems(leaf)) {
566                                 ret = btrfs_next_leaf(root, path);
567                                 if (ret < 0)
568                                         return ret;
569                                 BUG_ON(ret > 0);
570                                 leaf = path->nodes[0];
571                         }
572                         btrfs_item_key_to_cpu(leaf, &found_key,
573                                               path->slots[0]);
574                         BUG_ON(key.objectid != found_key.objectid);
575                         if (found_key.type != BTRFS_EXTENT_REF_V0_KEY) {
576                                 path->slots[0]++;
577                                 continue;
578                         }
579                         ref0 = btrfs_item_ptr(leaf, path->slots[0],
580                                               struct btrfs_extent_ref_v0);
581                         owner = btrfs_ref_objectid_v0(leaf, ref0);
582                         break;
583                 }
584         }
585         btrfs_release_path(root, path);
586
587         if (owner < BTRFS_FIRST_FREE_OBJECTID)
588                 new_size += sizeof(*bi);
589
590         new_size -= sizeof(*ei0);
591         ret = btrfs_search_slot(trans, root, &key, path,
592                                 new_size + extra_size, 1);
593         if (ret < 0)
594                 return ret;
595         BUG_ON(ret);
596
597         ret = btrfs_extend_item(trans, root, path, new_size);
598         BUG_ON(ret);
599
600         leaf = path->nodes[0];
601         item = btrfs_item_ptr(leaf, path->slots[0], struct btrfs_extent_item);
602         btrfs_set_extent_refs(leaf, item, refs);
603         /* FIXME: get real generation */
604         btrfs_set_extent_generation(leaf, item, 0);
605         if (owner < BTRFS_FIRST_FREE_OBJECTID) {
606                 btrfs_set_extent_flags(leaf, item,
607                                        BTRFS_EXTENT_FLAG_TREE_BLOCK |
608                                        BTRFS_BLOCK_FLAG_FULL_BACKREF);
609                 bi = (struct btrfs_tree_block_info *)(item + 1);
610                 /* FIXME: get first key of the block */
611                 memset_extent_buffer(leaf, 0, (unsigned long)bi, sizeof(*bi));
612                 btrfs_set_tree_block_level(leaf, bi, (int)owner);
613         } else {
614                 btrfs_set_extent_flags(leaf, item, BTRFS_EXTENT_FLAG_DATA);
615         }
616         btrfs_mark_buffer_dirty(leaf);
617         return 0;
618 }
619 #endif
620
621 static u64 hash_extent_data_ref(u64 root_objectid, u64 owner, u64 offset)
622 {
623         u32 high_crc = ~(u32)0;
624         u32 low_crc = ~(u32)0;
625         __le64 lenum;
626
627         lenum = cpu_to_le64(root_objectid);
628         high_crc = btrfs_crc32c(high_crc, &lenum, sizeof(lenum));
629         lenum = cpu_to_le64(owner);
630         low_crc = btrfs_crc32c(low_crc, &lenum, sizeof(lenum));
631         lenum = cpu_to_le64(offset);
632         low_crc = btrfs_crc32c(low_crc, &lenum, sizeof(lenum));
633
634         return ((u64)high_crc << 31) ^ (u64)low_crc;
635 }
636
637 static u64 hash_extent_data_ref_item(struct extent_buffer *leaf,
638                                      struct btrfs_extent_data_ref *ref)
639 {
640         return hash_extent_data_ref(btrfs_extent_data_ref_root(leaf, ref),
641                                     btrfs_extent_data_ref_objectid(leaf, ref),
642                                     btrfs_extent_data_ref_offset(leaf, ref));
643 }
644
645 static int match_extent_data_ref(struct extent_buffer *leaf,
646                                  struct btrfs_extent_data_ref *ref,
647                                  u64 root_objectid, u64 owner, u64 offset)
648 {
649         if (btrfs_extent_data_ref_root(leaf, ref) != root_objectid ||
650             btrfs_extent_data_ref_objectid(leaf, ref) != owner ||
651             btrfs_extent_data_ref_offset(leaf, ref) != offset)
652                 return 0;
653         return 1;
654 }
655
656 static noinline int lookup_extent_data_ref(struct btrfs_trans_handle *trans,
657                                            struct btrfs_root *root,
658                                            struct btrfs_path *path,
659                                            u64 bytenr, u64 parent,
660                                            u64 root_objectid,
661                                            u64 owner, u64 offset)
662 {
663         struct btrfs_key key;
664         struct btrfs_extent_data_ref *ref;
665         struct extent_buffer *leaf;
666         u32 nritems;
667         int ret;
668         int recow;
669         int err = -ENOENT;
670
671         key.objectid = bytenr;
672         if (parent) {
673                 key.type = BTRFS_SHARED_DATA_REF_KEY;
674                 key.offset = parent;
675         } else {
676                 key.type = BTRFS_EXTENT_DATA_REF_KEY;
677                 key.offset = hash_extent_data_ref(root_objectid,
678                                                   owner, offset);
679         }
680 again:
681         recow = 0;
682         ret = btrfs_search_slot(trans, root, &key, path, -1, 1);
683         if (ret < 0) {
684                 err = ret;
685                 goto fail;
686         }
687
688         if (parent) {
689                 if (!ret)
690                         return 0;
691 #ifdef BTRFS_COMPAT_EXTENT_TREE_V0
692                 key.type = BTRFS_EXTENT_REF_V0_KEY;
693                 btrfs_release_path(root, path);
694                 ret = btrfs_search_slot(trans, root, &key, path, -1, 1);
695                 if (ret < 0) {
696                         err = ret;
697                         goto fail;
698                 }
699                 if (!ret)
700                         return 0;
701 #endif
702                 goto fail;
703         }
704
705         leaf = path->nodes[0];
706         nritems = btrfs_header_nritems(leaf);
707         while (1) {
708                 if (path->slots[0] >= nritems) {
709                         ret = btrfs_next_leaf(root, path);
710                         if (ret < 0)
711                                 err = ret;
712                         if (ret)
713                                 goto fail;
714
715                         leaf = path->nodes[0];
716                         nritems = btrfs_header_nritems(leaf);
717                         recow = 1;
718                 }
719
720                 btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);
721                 if (key.objectid != bytenr ||
722                     key.type != BTRFS_EXTENT_DATA_REF_KEY)
723                         goto fail;
724
725                 ref = btrfs_item_ptr(leaf, path->slots[0],
726                                      struct btrfs_extent_data_ref);
727
728                 if (match_extent_data_ref(leaf, ref, root_objectid,
729                                           owner, offset)) {
730                         if (recow) {
731                                 btrfs_release_path(root, path);
732                                 goto again;
733                         }
734                         err = 0;
735                         break;
736                 }
737                 path->slots[0]++;
738         }
739 fail:
740         return err;
741 }
742
743 static noinline int insert_extent_data_ref(struct btrfs_trans_handle *trans,
744                                            struct btrfs_root *root,
745                                            struct btrfs_path *path,
746                                            u64 bytenr, u64 parent,
747                                            u64 root_objectid, u64 owner,
748                                            u64 offset, int refs_to_add)
749 {
750         struct btrfs_key key;
751         struct extent_buffer *leaf;
752         u32 size;
753         u32 num_refs;
754         int ret;
755
756         key.objectid = bytenr;
757         if (parent) {
758                 key.type = BTRFS_SHARED_DATA_REF_KEY;
759                 key.offset = parent;
760                 size = sizeof(struct btrfs_shared_data_ref);
761         } else {
762                 key.type = BTRFS_EXTENT_DATA_REF_KEY;
763                 key.offset = hash_extent_data_ref(root_objectid,
764                                                   owner, offset);
765                 size = sizeof(struct btrfs_extent_data_ref);
766         }
767
768         ret = btrfs_insert_empty_item(trans, root, path, &key, size);
769         if (ret && ret != -EEXIST)
770                 goto fail;
771
772         leaf = path->nodes[0];
773         if (parent) {
774                 struct btrfs_shared_data_ref *ref;
775                 ref = btrfs_item_ptr(leaf, path->slots[0],
776                                      struct btrfs_shared_data_ref);
777                 if (ret == 0) {
778                         btrfs_set_shared_data_ref_count(leaf, ref, refs_to_add);
779                 } else {
780                         num_refs = btrfs_shared_data_ref_count(leaf, ref);
781                         num_refs += refs_to_add;
782                         btrfs_set_shared_data_ref_count(leaf, ref, num_refs);
783                 }
784         } else {
785                 struct btrfs_extent_data_ref *ref;
786                 while (ret == -EEXIST) {
787                         ref = btrfs_item_ptr(leaf, path->slots[0],
788                                              struct btrfs_extent_data_ref);
789                         if (match_extent_data_ref(leaf, ref, root_objectid,
790                                                   owner, offset))
791                                 break;
792                         btrfs_release_path(root, path);
793                         key.offset++;
794                         ret = btrfs_insert_empty_item(trans, root, path, &key,
795                                                       size);
796                         if (ret && ret != -EEXIST)
797                                 goto fail;
798
799                         leaf = path->nodes[0];
800                 }
801                 ref = btrfs_item_ptr(leaf, path->slots[0],
802                                      struct btrfs_extent_data_ref);
803                 if (ret == 0) {
804                         btrfs_set_extent_data_ref_root(leaf, ref,
805                                                        root_objectid);
806                         btrfs_set_extent_data_ref_objectid(leaf, ref, owner);
807                         btrfs_set_extent_data_ref_offset(leaf, ref, offset);
808                         btrfs_set_extent_data_ref_count(leaf, ref, refs_to_add);
809                 } else {
810                         num_refs = btrfs_extent_data_ref_count(leaf, ref);
811                         num_refs += refs_to_add;
812                         btrfs_set_extent_data_ref_count(leaf, ref, num_refs);
813                 }
814         }
815         btrfs_mark_buffer_dirty(leaf);
816         ret = 0;
817 fail:
818         btrfs_release_path(root, path);
819         return ret;
820 }
821
822 static noinline int remove_extent_data_ref(struct btrfs_trans_handle *trans,
823                                            struct btrfs_root *root,
824                                            struct btrfs_path *path,
825                                            int refs_to_drop)
826 {
827         struct btrfs_key key;
828         struct btrfs_extent_data_ref *ref1 = NULL;
829         struct btrfs_shared_data_ref *ref2 = NULL;
830         struct extent_buffer *leaf;
831         u32 num_refs = 0;
832         int ret = 0;
833
834         leaf = path->nodes[0];
835         btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);
836
837         if (key.type == BTRFS_EXTENT_DATA_REF_KEY) {
838                 ref1 = btrfs_item_ptr(leaf, path->slots[0],
839                                       struct btrfs_extent_data_ref);
840                 num_refs = btrfs_extent_data_ref_count(leaf, ref1);
841         } else if (key.type == BTRFS_SHARED_DATA_REF_KEY) {
842                 ref2 = btrfs_item_ptr(leaf, path->slots[0],
843                                       struct btrfs_shared_data_ref);
844                 num_refs = btrfs_shared_data_ref_count(leaf, ref2);
845 #ifdef BTRFS_COMPAT_EXTENT_TREE_V0
846         } else if (key.type == BTRFS_EXTENT_REF_V0_KEY) {
847                 struct btrfs_extent_ref_v0 *ref0;
848                 ref0 = btrfs_item_ptr(leaf, path->slots[0],
849                                       struct btrfs_extent_ref_v0);
850                 num_refs = btrfs_ref_count_v0(leaf, ref0);
851 #endif
852         } else {
853                 BUG();
854         }
855
856         BUG_ON(num_refs < refs_to_drop);
857         num_refs -= refs_to_drop;
858
859         if (num_refs == 0) {
860                 ret = btrfs_del_item(trans, root, path);
861         } else {
862                 if (key.type == BTRFS_EXTENT_DATA_REF_KEY)
863                         btrfs_set_extent_data_ref_count(leaf, ref1, num_refs);
864                 else if (key.type == BTRFS_SHARED_DATA_REF_KEY)
865                         btrfs_set_shared_data_ref_count(leaf, ref2, num_refs);
866 #ifdef BTRFS_COMPAT_EXTENT_TREE_V0
867                 else {
868                         struct btrfs_extent_ref_v0 *ref0;
869                         ref0 = btrfs_item_ptr(leaf, path->slots[0],
870                                         struct btrfs_extent_ref_v0);
871                         btrfs_set_ref_count_v0(leaf, ref0, num_refs);
872                 }
873 #endif
874                 btrfs_mark_buffer_dirty(leaf);
875         }
876         return ret;
877 }
878
879 static noinline u32 extent_data_ref_count(struct btrfs_root *root,
880                                           struct btrfs_path *path,
881                                           struct btrfs_extent_inline_ref *iref)
882 {
883         struct btrfs_key key;
884         struct extent_buffer *leaf;
885         struct btrfs_extent_data_ref *ref1;
886         struct btrfs_shared_data_ref *ref2;
887         u32 num_refs = 0;
888
889         leaf = path->nodes[0];
890         btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);
891         if (iref) {
892                 if (btrfs_extent_inline_ref_type(leaf, iref) ==
893                     BTRFS_EXTENT_DATA_REF_KEY) {
894                         ref1 = (struct btrfs_extent_data_ref *)(&iref->offset);
895                         num_refs = btrfs_extent_data_ref_count(leaf, ref1);
896                 } else {
897                         ref2 = (struct btrfs_shared_data_ref *)(iref + 1);
898                         num_refs = btrfs_shared_data_ref_count(leaf, ref2);
899                 }
900         } else if (key.type == BTRFS_EXTENT_DATA_REF_KEY) {
901                 ref1 = btrfs_item_ptr(leaf, path->slots[0],
902                                       struct btrfs_extent_data_ref);
903                 num_refs = btrfs_extent_data_ref_count(leaf, ref1);
904         } else if (key.type == BTRFS_SHARED_DATA_REF_KEY) {
905                 ref2 = btrfs_item_ptr(leaf, path->slots[0],
906                                       struct btrfs_shared_data_ref);
907                 num_refs = btrfs_shared_data_ref_count(leaf, ref2);
908 #ifdef BTRFS_COMPAT_EXTENT_TREE_V0
909         } else if (key.type == BTRFS_EXTENT_REF_V0_KEY) {
910                 struct btrfs_extent_ref_v0 *ref0;
911                 ref0 = btrfs_item_ptr(leaf, path->slots[0],
912                                       struct btrfs_extent_ref_v0);
913                 num_refs = btrfs_ref_count_v0(leaf, ref0);
914 #endif
915         } else {
916                 WARN_ON(1);
917         }
918         return num_refs;
919 }
920
921 static noinline int lookup_tree_block_ref(struct btrfs_trans_handle *trans,
922                                           struct btrfs_root *root,
923                                           struct btrfs_path *path,
924                                           u64 bytenr, u64 parent,
925                                           u64 root_objectid)
926 {
927         struct btrfs_key key;
928         int ret;
929
930         key.objectid = bytenr;
931         if (parent) {
932                 key.type = BTRFS_SHARED_BLOCK_REF_KEY;
933                 key.offset = parent;
934         } else {
935                 key.type = BTRFS_TREE_BLOCK_REF_KEY;
936                 key.offset = root_objectid;
937         }
938
939         ret = btrfs_search_slot(trans, root, &key, path, -1, 1);
940         if (ret > 0)
941                 ret = -ENOENT;
942 #ifdef BTRFS_COMPAT_EXTENT_TREE_V0
943         if (ret == -ENOENT && parent) {
944                 btrfs_release_path(root, path);
945                 key.type = BTRFS_EXTENT_REF_V0_KEY;
946                 ret = btrfs_search_slot(trans, root, &key, path, -1, 1);
947                 if (ret > 0)
948                         ret = -ENOENT;
949         }
950 #endif
951         return ret;
952 }
953
954 static noinline int insert_tree_block_ref(struct btrfs_trans_handle *trans,
955                                           struct btrfs_root *root,
956                                           struct btrfs_path *path,
957                                           u64 bytenr, u64 parent,
958                                           u64 root_objectid)
959 {
960         struct btrfs_key key;
961         int ret;
962
963         key.objectid = bytenr;
964         if (parent) {
965                 key.type = BTRFS_SHARED_BLOCK_REF_KEY;
966                 key.offset = parent;
967         } else {
968                 key.type = BTRFS_TREE_BLOCK_REF_KEY;
969                 key.offset = root_objectid;
970         }
971
972         ret = btrfs_insert_empty_item(trans, root, path, &key, 0);
973         btrfs_release_path(root, path);
974         return ret;
975 }
976
977 static inline int extent_ref_type(u64 parent, u64 owner)
978 {
979         int type;
980         if (owner < BTRFS_FIRST_FREE_OBJECTID) {
981                 if (parent > 0)
982                         type = BTRFS_SHARED_BLOCK_REF_KEY;
983                 else
984                         type = BTRFS_TREE_BLOCK_REF_KEY;
985         } else {
986                 if (parent > 0)
987                         type = BTRFS_SHARED_DATA_REF_KEY;
988                 else
989                         type = BTRFS_EXTENT_DATA_REF_KEY;
990         }
991         return type;
992 }
993
994 static int find_next_key(struct btrfs_path *path, struct btrfs_key *key)
995
996 {
997         int level;
998         BUG_ON(!path->keep_locks);
999         for (level = 0; level < BTRFS_MAX_LEVEL; level++) {
1000                 if (!path->nodes[level])
1001                         break;
1002                 btrfs_assert_tree_locked(path->nodes[level]);
1003                 if (path->slots[level] + 1 >=
1004                     btrfs_header_nritems(path->nodes[level]))
1005                         continue;
1006                 if (level == 0)
1007                         btrfs_item_key_to_cpu(path->nodes[level], key,
1008                                               path->slots[level] + 1);
1009                 else
1010                         btrfs_node_key_to_cpu(path->nodes[level], key,
1011                                               path->slots[level] + 1);
1012                 return 0;
1013         }
1014         return 1;
1015 }
1016
1017 /*
1018  * look for inline back ref. if back ref is found, *ref_ret is set
1019  * to the address of inline back ref, and 0 is returned.
1020  *
1021  * if back ref isn't found, *ref_ret is set to the address where it
1022  * should be inserted, and -ENOENT is returned.
1023  *
1024  * if insert is true and there are too many inline back refs, the path
1025  * points to the extent item, and -EAGAIN is returned.
1026  *
1027  * NOTE: inline back refs are ordered in the same way that back ref
1028  *       items in the tree are ordered.
1029  */
1030 static noinline_for_stack
1031 int lookup_inline_extent_backref(struct btrfs_trans_handle *trans,
1032                                  struct btrfs_root *root,
1033                                  struct btrfs_path *path,
1034                                  struct btrfs_extent_inline_ref **ref_ret,
1035                                  u64 bytenr, u64 num_bytes,
1036                                  u64 parent, u64 root_objectid,
1037                                  u64 owner, u64 offset, int insert)
1038 {
1039         struct btrfs_key key;
1040         struct extent_buffer *leaf;
1041         struct btrfs_extent_item *ei;
1042         struct btrfs_extent_inline_ref *iref;
1043         u64 flags;
1044         u64 item_size;
1045         unsigned long ptr;
1046         unsigned long end;
1047         int extra_size;
1048         int type;
1049         int want;
1050         int ret;
1051         int err = 0;
1052
1053         key.objectid = bytenr;
1054         key.type = BTRFS_EXTENT_ITEM_KEY;
1055         key.offset = num_bytes;
1056
1057         want = extent_ref_type(parent, owner);
1058         if (insert) {
1059                 extra_size = btrfs_extent_inline_ref_size(want);
1060                 if (owner >= BTRFS_FIRST_FREE_OBJECTID)
1061                         path->keep_locks = 1;
1062         } else
1063                 extra_size = -1;
1064         ret = btrfs_search_slot(trans, root, &key, path, extra_size, 1);
1065         if (ret < 0) {
1066                 err = ret;
1067                 goto out;
1068         }
1069         BUG_ON(ret);
1070
1071         leaf = path->nodes[0];
1072         item_size = btrfs_item_size_nr(leaf, path->slots[0]);
1073 #ifdef BTRFS_COMPAT_EXTENT_TREE_V0
1074         if (item_size < sizeof(*ei)) {
1075                 if (!insert) {
1076                         err = -ENOENT;
1077                         goto out;
1078                 }
1079                 ret = convert_extent_item_v0(trans, root, path, owner,
1080                                              extra_size);
1081                 if (ret < 0) {
1082                         err = ret;
1083                         goto out;
1084                 }
1085                 leaf = path->nodes[0];
1086                 item_size = btrfs_item_size_nr(leaf, path->slots[0]);
1087         }
1088 #endif
1089         BUG_ON(item_size < sizeof(*ei));
1090
1091         if (owner < BTRFS_FIRST_FREE_OBJECTID && insert &&
1092             item_size + extra_size >= BTRFS_MAX_EXTENT_ITEM_SIZE(root)) {
1093                 err = -EAGAIN;
1094                 goto out;
1095         }
1096
1097         ei = btrfs_item_ptr(leaf, path->slots[0], struct btrfs_extent_item);
1098         flags = btrfs_extent_flags(leaf, ei);
1099
1100         ptr = (unsigned long)(ei + 1);
1101         end = (unsigned long)ei + item_size;
1102
1103         if (flags & BTRFS_EXTENT_FLAG_TREE_BLOCK) {
1104                 ptr += sizeof(struct btrfs_tree_block_info);
1105                 BUG_ON(ptr > end);
1106         } else {
1107                 BUG_ON(!(flags & BTRFS_EXTENT_FLAG_DATA));
1108         }
1109
1110         err = -ENOENT;
1111         while (1) {
1112                 if (ptr >= end) {
1113                         WARN_ON(ptr > end);
1114                         break;
1115                 }
1116                 iref = (struct btrfs_extent_inline_ref *)ptr;
1117                 type = btrfs_extent_inline_ref_type(leaf, iref);
1118                 if (want < type)
1119                         break;
1120                 if (want > type) {
1121                         ptr += btrfs_extent_inline_ref_size(type);
1122                         continue;
1123                 }
1124
1125                 if (type == BTRFS_EXTENT_DATA_REF_KEY) {
1126                         struct btrfs_extent_data_ref *dref;
1127                         dref = (struct btrfs_extent_data_ref *)(&iref->offset);
1128                         if (match_extent_data_ref(leaf, dref, root_objectid,
1129                                                   owner, offset)) {
1130                                 err = 0;
1131                                 break;
1132                         }
1133                         if (hash_extent_data_ref_item(leaf, dref) <
1134                             hash_extent_data_ref(root_objectid, owner, offset))
1135                                 break;
1136                 } else {
1137                         u64 ref_offset;
1138                         ref_offset = btrfs_extent_inline_ref_offset(leaf, iref);
1139                         if (parent > 0) {
1140                                 if (parent == ref_offset) {
1141                                         err = 0;
1142                                         break;
1143                                 }
1144                                 if (ref_offset < parent)
1145                                         break;
1146                         } else {
1147                                 if (root_objectid == ref_offset) {
1148                                         err = 0;
1149                                         break;
1150                                 }
1151                                 if (ref_offset < root_objectid)
1152                                         break;
1153                         }
1154                 }
1155                 ptr += btrfs_extent_inline_ref_size(type);
1156         }
1157         if (err == -ENOENT && insert) {
1158                 if (item_size + extra_size >=
1159                     BTRFS_MAX_EXTENT_ITEM_SIZE(root)) {
1160                         err = -EAGAIN;
1161                         goto out;
1162                 }
1163                 /*
1164                  * To add new inline back ref, we have to make sure
1165                  * there is no corresponding back ref item.
1166                  * For simplicity, we just do not add new inline back
1167                  * ref if there is any kind of item for this block
1168                  */
1169                 if (owner >= BTRFS_FIRST_FREE_OBJECTID &&
1170                     find_next_key(path, &key) == 0 && key.objectid == bytenr) {
1171                         err = -EAGAIN;
1172                         goto out;
1173                 }
1174         }
1175         *ref_ret = (struct btrfs_extent_inline_ref *)ptr;
1176 out:
1177         if (insert && owner >= BTRFS_FIRST_FREE_OBJECTID) {
1178                 path->keep_locks = 0;
1179                 btrfs_unlock_up_safe(path, 1);
1180         }
1181         return err;
1182 }
1183
1184 /*
1185  * helper to add new inline back ref
1186  */
1187 static noinline_for_stack
1188 int setup_inline_extent_backref(struct btrfs_trans_handle *trans,
1189                                 struct btrfs_root *root,
1190                                 struct btrfs_path *path,
1191                                 struct btrfs_extent_inline_ref *iref,
1192                                 u64 parent, u64 root_objectid,
1193                                 u64 owner, u64 offset, int refs_to_add,
1194                                 struct btrfs_delayed_extent_op *extent_op)
1195 {
1196         struct extent_buffer *leaf;
1197         struct btrfs_extent_item *ei;
1198         unsigned long ptr;
1199         unsigned long end;
1200         unsigned long item_offset;
1201         u64 refs;
1202         int size;
1203         int type;
1204         int ret;
1205
1206         leaf = path->nodes[0];
1207         ei = btrfs_item_ptr(leaf, path->slots[0], struct btrfs_extent_item);
1208         item_offset = (unsigned long)iref - (unsigned long)ei;
1209
1210         type = extent_ref_type(parent, owner);
1211         size = btrfs_extent_inline_ref_size(type);
1212
1213         ret = btrfs_extend_item(trans, root, path, size);
1214         BUG_ON(ret);
1215
1216         ei = btrfs_item_ptr(leaf, path->slots[0], struct btrfs_extent_item);
1217         refs = btrfs_extent_refs(leaf, ei);
1218         refs += refs_to_add;
1219         btrfs_set_extent_refs(leaf, ei, refs);
1220         if (extent_op)
1221                 __run_delayed_extent_op(extent_op, leaf, ei);
1222
1223         ptr = (unsigned long)ei + item_offset;
1224         end = (unsigned long)ei + btrfs_item_size_nr(leaf, path->slots[0]);
1225         if (ptr < end - size)
1226                 memmove_extent_buffer(leaf, ptr + size, ptr,
1227                                       end - size - ptr);
1228
1229         iref = (struct btrfs_extent_inline_ref *)ptr;
1230         btrfs_set_extent_inline_ref_type(leaf, iref, type);
1231         if (type == BTRFS_EXTENT_DATA_REF_KEY) {
1232                 struct btrfs_extent_data_ref *dref;
1233                 dref = (struct btrfs_extent_data_ref *)(&iref->offset);
1234                 btrfs_set_extent_data_ref_root(leaf, dref, root_objectid);
1235                 btrfs_set_extent_data_ref_objectid(leaf, dref, owner);
1236                 btrfs_set_extent_data_ref_offset(leaf, dref, offset);
1237                 btrfs_set_extent_data_ref_count(leaf, dref, refs_to_add);
1238         } else if (type == BTRFS_SHARED_DATA_REF_KEY) {
1239                 struct btrfs_shared_data_ref *sref;
1240                 sref = (struct btrfs_shared_data_ref *)(iref + 1);
1241                 btrfs_set_shared_data_ref_count(leaf, sref, refs_to_add);
1242                 btrfs_set_extent_inline_ref_offset(leaf, iref, parent);
1243         } else if (type == BTRFS_SHARED_BLOCK_REF_KEY) {
1244                 btrfs_set_extent_inline_ref_offset(leaf, iref, parent);
1245         } else {
1246                 btrfs_set_extent_inline_ref_offset(leaf, iref, root_objectid);
1247         }
1248         btrfs_mark_buffer_dirty(leaf);
1249         return 0;
1250 }
1251
1252 static int lookup_extent_backref(struct btrfs_trans_handle *trans,
1253                                  struct btrfs_root *root,
1254                                  struct btrfs_path *path,
1255                                  struct btrfs_extent_inline_ref **ref_ret,
1256                                  u64 bytenr, u64 num_bytes, u64 parent,
1257                                  u64 root_objectid, u64 owner, u64 offset)
1258 {
1259         int ret;
1260
1261         ret = lookup_inline_extent_backref(trans, root, path, ref_ret,
1262                                            bytenr, num_bytes, parent,
1263                                            root_objectid, owner, offset, 0);
1264         if (ret != -ENOENT)
1265                 return ret;
1266
1267         btrfs_release_path(root, path);
1268         *ref_ret = NULL;
1269
1270         if (owner < BTRFS_FIRST_FREE_OBJECTID) {
1271                 ret = lookup_tree_block_ref(trans, root, path, bytenr, parent,
1272                                             root_objectid);
1273         } else {
1274                 ret = lookup_extent_data_ref(trans, root, path, bytenr, parent,
1275                                              root_objectid, owner, offset);
1276         }
1277         return ret;
1278 }
1279
1280 /*
1281  * helper to update/remove inline back ref
1282  */
1283 static noinline_for_stack
1284 int update_inline_extent_backref(struct btrfs_trans_handle *trans,
1285                                  struct btrfs_root *root,
1286                                  struct btrfs_path *path,
1287                                  struct btrfs_extent_inline_ref *iref,
1288                                  int refs_to_mod,
1289                                  struct btrfs_delayed_extent_op *extent_op)
1290 {
1291         struct extent_buffer *leaf;
1292         struct btrfs_extent_item *ei;
1293         struct btrfs_extent_data_ref *dref = NULL;
1294         struct btrfs_shared_data_ref *sref = NULL;
1295         unsigned long ptr;
1296         unsigned long end;
1297         u32 item_size;
1298         int size;
1299         int type;
1300         int ret;
1301         u64 refs;
1302
1303         leaf = path->nodes[0];
1304         ei = btrfs_item_ptr(leaf, path->slots[0], struct btrfs_extent_item);
1305         refs = btrfs_extent_refs(leaf, ei);
1306         WARN_ON(refs_to_mod < 0 && refs + refs_to_mod <= 0);
1307         refs += refs_to_mod;
1308         btrfs_set_extent_refs(leaf, ei, refs);
1309         if (extent_op)
1310                 __run_delayed_extent_op(extent_op, leaf, ei);
1311
1312         type = btrfs_extent_inline_ref_type(leaf, iref);
1313
1314         if (type == BTRFS_EXTENT_DATA_REF_KEY) {
1315                 dref = (struct btrfs_extent_data_ref *)(&iref->offset);
1316                 refs = btrfs_extent_data_ref_count(leaf, dref);
1317         } else if (type == BTRFS_SHARED_DATA_REF_KEY) {
1318                 sref = (struct btrfs_shared_data_ref *)(iref + 1);
1319                 refs = btrfs_shared_data_ref_count(leaf, sref);
1320         } else {
1321                 refs = 1;
1322                 BUG_ON(refs_to_mod != -1);
1323         }
1324
1325         BUG_ON(refs_to_mod < 0 && refs < -refs_to_mod);
1326         refs += refs_to_mod;
1327
1328         if (refs > 0) {
1329                 if (type == BTRFS_EXTENT_DATA_REF_KEY)
1330                         btrfs_set_extent_data_ref_count(leaf, dref, refs);
1331                 else
1332                         btrfs_set_shared_data_ref_count(leaf, sref, refs);
1333         } else {
1334                 size =  btrfs_extent_inline_ref_size(type);
1335                 item_size = btrfs_item_size_nr(leaf, path->slots[0]);
1336                 ptr = (unsigned long)iref;
1337                 end = (unsigned long)ei + item_size;
1338                 if (ptr + size < end)
1339                         memmove_extent_buffer(leaf, ptr, ptr + size,
1340                                               end - ptr - size);
1341                 item_size -= size;
1342                 ret = btrfs_truncate_item(trans, root, path, item_size, 1);
1343                 BUG_ON(ret);
1344         }
1345         btrfs_mark_buffer_dirty(leaf);
1346         return 0;
1347 }
1348
1349 static noinline_for_stack
1350 int insert_inline_extent_backref(struct btrfs_trans_handle *trans,
1351                                  struct btrfs_root *root,
1352                                  struct btrfs_path *path,
1353                                  u64 bytenr, u64 num_bytes, u64 parent,
1354                                  u64 root_objectid, u64 owner,
1355                                  u64 offset, int refs_to_add,
1356                                  struct btrfs_delayed_extent_op *extent_op)
1357 {
1358         struct btrfs_extent_inline_ref *iref;
1359         int ret;
1360
1361         ret = lookup_inline_extent_backref(trans, root, path, &iref,
1362                                            bytenr, num_bytes, parent,
1363                                            root_objectid, owner, offset, 1);
1364         if (ret == 0) {
1365                 BUG_ON(owner < BTRFS_FIRST_FREE_OBJECTID);
1366                 ret = update_inline_extent_backref(trans, root, path, iref,
1367                                                    refs_to_add, extent_op);
1368         } else if (ret == -ENOENT) {
1369                 ret = setup_inline_extent_backref(trans, root, path, iref,
1370                                                   parent, root_objectid,
1371                                                   owner, offset, refs_to_add,
1372                                                   extent_op);
1373         }
1374         return ret;
1375 }
1376
1377 static int insert_extent_backref(struct btrfs_trans_handle *trans,
1378                                  struct btrfs_root *root,
1379                                  struct btrfs_path *path,
1380                                  u64 bytenr, u64 parent, u64 root_objectid,
1381                                  u64 owner, u64 offset, int refs_to_add)
1382 {
1383         int ret;
1384         if (owner < BTRFS_FIRST_FREE_OBJECTID) {
1385                 BUG_ON(refs_to_add != 1);
1386                 ret = insert_tree_block_ref(trans, root, path, bytenr,
1387                                             parent, root_objectid);
1388         } else {
1389                 ret = insert_extent_data_ref(trans, root, path, bytenr,
1390                                              parent, root_objectid,
1391                                              owner, offset, refs_to_add);
1392         }
1393         return ret;
1394 }
1395
1396 static int remove_extent_backref(struct btrfs_trans_handle *trans,
1397                                  struct btrfs_root *root,
1398                                  struct btrfs_path *path,
1399                                  struct btrfs_extent_inline_ref *iref,
1400                                  int refs_to_drop, int is_data)
1401 {
1402         int ret;
1403
1404         BUG_ON(!is_data && refs_to_drop != 1);
1405         if (iref) {
1406                 ret = update_inline_extent_backref(trans, root, path, iref,
1407                                                    -refs_to_drop, NULL);
1408         } else if (is_data) {
1409                 ret = remove_extent_data_ref(trans, root, path, refs_to_drop);
1410         } else {
1411                 ret = btrfs_del_item(trans, root, path);
1412         }
1413         return ret;
1414 }
1415
1416 #ifdef BIO_RW_DISCARD
1417 static void btrfs_issue_discard(struct block_device *bdev,
1418                                 u64 start, u64 len)
1419 {
1420         blkdev_issue_discard(bdev, start >> 9, len >> 9, GFP_KERNEL);
1421 }
1422 #endif
1423
1424 static int btrfs_discard_extent(struct btrfs_root *root, u64 bytenr,
1425                                 u64 num_bytes)
1426 {
1427 #ifdef BIO_RW_DISCARD
1428         int ret;
1429         u64 map_length = num_bytes;
1430         struct btrfs_multi_bio *multi = NULL;
1431
1432         /* Tell the block device(s) that the sectors can be discarded */
1433         ret = btrfs_map_block(&root->fs_info->mapping_tree, READ,
1434                               bytenr, &map_length, &multi, 0);
1435         if (!ret) {
1436                 struct btrfs_bio_stripe *stripe = multi->stripes;
1437                 int i;
1438
1439                 if (map_length > num_bytes)
1440                         map_length = num_bytes;
1441
1442                 for (i = 0; i < multi->num_stripes; i++, stripe++) {
1443                         btrfs_issue_discard(stripe->dev->bdev,
1444                                             stripe->physical,
1445                                             map_length);
1446                 }
1447                 kfree(multi);
1448         }
1449
1450         return ret;
1451 #else
1452         return 0;
1453 #endif
1454 }
1455
1456 int btrfs_inc_extent_ref(struct btrfs_trans_handle *trans,
1457                          struct btrfs_root *root,
1458                          u64 bytenr, u64 num_bytes, u64 parent,
1459                          u64 root_objectid, u64 owner, u64 offset)
1460 {
1461         int ret;
1462         BUG_ON(owner < BTRFS_FIRST_FREE_OBJECTID &&
1463                root_objectid == BTRFS_TREE_LOG_OBJECTID);
1464
1465         if (owner < BTRFS_FIRST_FREE_OBJECTID) {
1466                 ret = btrfs_add_delayed_tree_ref(trans, bytenr, num_bytes,
1467                                         parent, root_objectid, (int)owner,
1468                                         BTRFS_ADD_DELAYED_REF, NULL);
1469         } else {
1470                 ret = btrfs_add_delayed_data_ref(trans, bytenr, num_bytes,
1471                                         parent, root_objectid, owner, offset,
1472                                         BTRFS_ADD_DELAYED_REF, NULL);
1473         }
1474         return ret;
1475 }
1476
1477 static int __btrfs_inc_extent_ref(struct btrfs_trans_handle *trans,
1478                                   struct btrfs_root *root,
1479                                   u64 bytenr, u64 num_bytes,
1480                                   u64 parent, u64 root_objectid,
1481                                   u64 owner, u64 offset, int refs_to_add,
1482                                   struct btrfs_delayed_extent_op *extent_op)
1483 {
1484         struct btrfs_path *path;
1485         struct extent_buffer *leaf;
1486         struct btrfs_extent_item *item;
1487         u64 refs;
1488         int ret;
1489         int err = 0;
1490
1491         path = btrfs_alloc_path();
1492         if (!path)
1493                 return -ENOMEM;
1494
1495         path->reada = 1;
1496         path->leave_spinning = 1;
1497         /* this will setup the path even if it fails to insert the back ref */
1498         ret = insert_inline_extent_backref(trans, root->fs_info->extent_root,
1499                                            path, bytenr, num_bytes, parent,
1500                                            root_objectid, owner, offset,
1501                                            refs_to_add, extent_op);
1502         if (ret == 0)
1503                 goto out;
1504
1505         if (ret != -EAGAIN) {
1506                 err = ret;
1507                 goto out;
1508         }
1509
1510         leaf = path->nodes[0];
1511         item = btrfs_item_ptr(leaf, path->slots[0], struct btrfs_extent_item);
1512         refs = btrfs_extent_refs(leaf, item);
1513         btrfs_set_extent_refs(leaf, item, refs + refs_to_add);
1514         if (extent_op)
1515                 __run_delayed_extent_op(extent_op, leaf, item);
1516
1517         btrfs_mark_buffer_dirty(leaf);
1518         btrfs_release_path(root->fs_info->extent_root, path);
1519
1520         path->reada = 1;
1521         path->leave_spinning = 1;
1522
1523         /* now insert the actual backref */
1524         ret = insert_extent_backref(trans, root->fs_info->extent_root,
1525                                     path, bytenr, parent, root_objectid,
1526                                     owner, offset, refs_to_add);
1527         BUG_ON(ret);
1528 out:
1529         btrfs_free_path(path);
1530         return err;
1531 }
1532
1533 static int run_delayed_data_ref(struct btrfs_trans_handle *trans,
1534                                 struct btrfs_root *root,
1535                                 struct btrfs_delayed_ref_node *node,
1536                                 struct btrfs_delayed_extent_op *extent_op,
1537                                 int insert_reserved)
1538 {
1539         int ret = 0;
1540         struct btrfs_delayed_data_ref *ref;
1541         struct btrfs_key ins;
1542         u64 parent = 0;
1543         u64 ref_root = 0;
1544         u64 flags = 0;
1545
1546         ins.objectid = node->bytenr;
1547         ins.offset = node->num_bytes;
1548         ins.type = BTRFS_EXTENT_ITEM_KEY;
1549
1550         ref = btrfs_delayed_node_to_data_ref(node);
1551         if (node->type == BTRFS_SHARED_DATA_REF_KEY)
1552                 parent = ref->parent;
1553         else
1554                 ref_root = ref->root;
1555
1556         if (node->action == BTRFS_ADD_DELAYED_REF && insert_reserved) {
1557                 if (extent_op) {
1558                         BUG_ON(extent_op->update_key);
1559                         flags |= extent_op->flags_to_set;
1560                 }
1561                 ret = alloc_reserved_file_extent(trans, root,
1562                                                  parent, ref_root, flags,
1563                                                  ref->objectid, ref->offset,
1564                                                  &ins, node->ref_mod);
1565                 update_reserved_extents(root, ins.objectid, ins.offset, 0);
1566         } else if (node->action == BTRFS_ADD_DELAYED_REF) {
1567                 ret = __btrfs_inc_extent_ref(trans, root, node->bytenr,
1568                                              node->num_bytes, parent,
1569                                              ref_root, ref->objectid,
1570                                              ref->offset, node->ref_mod,
1571                                              extent_op);
1572         } else if (node->action == BTRFS_DROP_DELAYED_REF) {
1573                 ret = __btrfs_free_extent(trans, root, node->bytenr,
1574                                           node->num_bytes, parent,
1575                                           ref_root, ref->objectid,
1576                                           ref->offset, node->ref_mod,
1577                                           extent_op);
1578         } else {
1579                 BUG();
1580         }
1581         return ret;
1582 }
1583
1584 static void __run_delayed_extent_op(struct btrfs_delayed_extent_op *extent_op,
1585                                     struct extent_buffer *leaf,
1586                                     struct btrfs_extent_item *ei)
1587 {
1588         u64 flags = btrfs_extent_flags(leaf, ei);
1589         if (extent_op->update_flags) {
1590                 flags |= extent_op->flags_to_set;
1591                 btrfs_set_extent_flags(leaf, ei, flags);
1592         }
1593
1594         if (extent_op->update_key) {
1595                 struct btrfs_tree_block_info *bi;
1596                 BUG_ON(!(flags & BTRFS_EXTENT_FLAG_TREE_BLOCK));
1597                 bi = (struct btrfs_tree_block_info *)(ei + 1);
1598                 btrfs_set_tree_block_key(leaf, bi, &extent_op->key);
1599         }
1600 }
1601
1602 static int run_delayed_extent_op(struct btrfs_trans_handle *trans,
1603                                  struct btrfs_root *root,
1604                                  struct btrfs_delayed_ref_node *node,
1605                                  struct btrfs_delayed_extent_op *extent_op)
1606 {
1607         struct btrfs_key key;
1608         struct btrfs_path *path;
1609         struct btrfs_extent_item *ei;
1610         struct extent_buffer *leaf;
1611         u32 item_size;
1612         int ret;
1613         int err = 0;
1614
1615         path = btrfs_alloc_path();
1616         if (!path)
1617                 return -ENOMEM;
1618
1619         key.objectid = node->bytenr;
1620         key.type = BTRFS_EXTENT_ITEM_KEY;
1621         key.offset = node->num_bytes;
1622
1623         path->reada = 1;
1624         path->leave_spinning = 1;
1625         ret = btrfs_search_slot(trans, root->fs_info->extent_root, &key,
1626                                 path, 0, 1);
1627         if (ret < 0) {
1628                 err = ret;
1629                 goto out;
1630         }
1631         if (ret > 0) {
1632                 err = -EIO;
1633                 goto out;
1634         }
1635
1636         leaf = path->nodes[0];
1637         item_size = btrfs_item_size_nr(leaf, path->slots[0]);
1638 #ifdef BTRFS_COMPAT_EXTENT_TREE_V0
1639         if (item_size < sizeof(*ei)) {
1640                 ret = convert_extent_item_v0(trans, root->fs_info->extent_root,
1641                                              path, (u64)-1, 0);
1642                 if (ret < 0) {
1643                         err = ret;
1644                         goto out;
1645                 }
1646                 leaf = path->nodes[0];
1647                 item_size = btrfs_item_size_nr(leaf, path->slots[0]);
1648         }
1649 #endif
1650         BUG_ON(item_size < sizeof(*ei));
1651         ei = btrfs_item_ptr(leaf, path->slots[0], struct btrfs_extent_item);
1652         __run_delayed_extent_op(extent_op, leaf, ei);
1653
1654         btrfs_mark_buffer_dirty(leaf);
1655 out:
1656         btrfs_free_path(path);
1657         return err;
1658 }
1659
1660 static int run_delayed_tree_ref(struct btrfs_trans_handle *trans,
1661                                 struct btrfs_root *root,
1662                                 struct btrfs_delayed_ref_node *node,
1663                                 struct btrfs_delayed_extent_op *extent_op,
1664                                 int insert_reserved)
1665 {
1666         int ret = 0;
1667         struct btrfs_delayed_tree_ref *ref;
1668         struct btrfs_key ins;
1669         u64 parent = 0;
1670         u64 ref_root = 0;
1671
1672         ins.objectid = node->bytenr;
1673         ins.offset = node->num_bytes;
1674         ins.type = BTRFS_EXTENT_ITEM_KEY;
1675
1676         ref = btrfs_delayed_node_to_tree_ref(node);
1677         if (node->type == BTRFS_SHARED_BLOCK_REF_KEY)
1678                 parent = ref->parent;
1679         else
1680                 ref_root = ref->root;
1681
1682         BUG_ON(node->ref_mod != 1);
1683         if (node->action == BTRFS_ADD_DELAYED_REF && insert_reserved) {
1684                 BUG_ON(!extent_op || !extent_op->update_flags ||
1685                        !extent_op->update_key);
1686                 ret = alloc_reserved_tree_block(trans, root,
1687                                                 parent, ref_root,
1688                                                 extent_op->flags_to_set,
1689                                                 &extent_op->key,
1690                                                 ref->level, &ins);
1691                 update_reserved_extents(root, ins.objectid, ins.offset, 0);
1692         } else if (node->action == BTRFS_ADD_DELAYED_REF) {
1693                 ret = __btrfs_inc_extent_ref(trans, root, node->bytenr,
1694                                              node->num_bytes, parent, ref_root,
1695                                              ref->level, 0, 1, extent_op);
1696         } else if (node->action == BTRFS_DROP_DELAYED_REF) {
1697                 ret = __btrfs_free_extent(trans, root, node->bytenr,
1698                                           node->num_bytes, parent, ref_root,
1699                                           ref->level, 0, 1, extent_op);
1700         } else {
1701                 BUG();
1702         }
1703         return ret;
1704 }
1705
1706
1707 /* helper function to actually process a single delayed ref entry */
1708 static int run_one_delayed_ref(struct btrfs_trans_handle *trans,
1709                                struct btrfs_root *root,
1710                                struct btrfs_delayed_ref_node *node,
1711                                struct btrfs_delayed_extent_op *extent_op,
1712                                int insert_reserved)
1713 {
1714         int ret;
1715         if (btrfs_delayed_ref_is_head(node)) {
1716                 struct btrfs_delayed_ref_head *head;
1717                 /*
1718                  * we've hit the end of the chain and we were supposed
1719                  * to insert this extent into the tree.  But, it got
1720                  * deleted before we ever needed to insert it, so all
1721                  * we have to do is clean up the accounting
1722                  */
1723                 BUG_ON(extent_op);
1724                 head = btrfs_delayed_node_to_head(node);
1725                 if (insert_reserved) {
1726                         if (head->is_data) {
1727                                 ret = btrfs_del_csums(trans, root,
1728                                                       node->bytenr,
1729                                                       node->num_bytes);
1730                                 BUG_ON(ret);
1731                         }
1732                         btrfs_update_pinned_extents(root, node->bytenr,
1733                                                     node->num_bytes, 1);
1734                         update_reserved_extents(root, node->bytenr,
1735                                                 node->num_bytes, 0);
1736                 }
1737                 mutex_unlock(&head->mutex);
1738                 return 0;
1739         }
1740
1741         if (node->type == BTRFS_TREE_BLOCK_REF_KEY ||
1742             node->type == BTRFS_SHARED_BLOCK_REF_KEY)
1743                 ret = run_delayed_tree_ref(trans, root, node, extent_op,
1744                                            insert_reserved);
1745         else if (node->type == BTRFS_EXTENT_DATA_REF_KEY ||
1746                  node->type == BTRFS_SHARED_DATA_REF_KEY)
1747                 ret = run_delayed_data_ref(trans, root, node, extent_op,
1748                                            insert_reserved);
1749         else
1750                 BUG();
1751         return ret;
1752 }
1753
1754 static noinline struct btrfs_delayed_ref_node *
1755 select_delayed_ref(struct btrfs_delayed_ref_head *head)
1756 {
1757         struct rb_node *node;
1758         struct btrfs_delayed_ref_node *ref;
1759         int action = BTRFS_ADD_DELAYED_REF;
1760 again:
1761         /*
1762          * select delayed ref of type BTRFS_ADD_DELAYED_REF first.
1763          * this prevents ref count from going down to zero when
1764          * there still are pending delayed ref.
1765          */
1766         node = rb_prev(&head->node.rb_node);
1767         while (1) {
1768                 if (!node)
1769                         break;
1770                 ref = rb_entry(node, struct btrfs_delayed_ref_node,
1771                                 rb_node);
1772                 if (ref->bytenr != head->node.bytenr)
1773                         break;
1774                 if (ref->action == action)
1775                         return ref;
1776                 node = rb_prev(node);
1777         }
1778         if (action == BTRFS_ADD_DELAYED_REF) {
1779                 action = BTRFS_DROP_DELAYED_REF;
1780                 goto again;
1781         }
1782         return NULL;
1783 }
1784
1785 static noinline int run_clustered_refs(struct btrfs_trans_handle *trans,
1786                                        struct btrfs_root *root,
1787                                        struct list_head *cluster)
1788 {
1789         struct btrfs_delayed_ref_root *delayed_refs;
1790         struct btrfs_delayed_ref_node *ref;
1791         struct btrfs_delayed_ref_head *locked_ref = NULL;
1792         struct btrfs_delayed_extent_op *extent_op;
1793         int ret;
1794         int count = 0;
1795         int must_insert_reserved = 0;
1796
1797         delayed_refs = &trans->transaction->delayed_refs;
1798         while (1) {
1799                 if (!locked_ref) {
1800                         /* pick a new head ref from the cluster list */
1801                         if (list_empty(cluster))
1802                                 break;
1803
1804                         locked_ref = list_entry(cluster->next,
1805                                      struct btrfs_delayed_ref_head, cluster);
1806
1807                         /* grab the lock that says we are going to process
1808                          * all the refs for this head */
1809                         ret = btrfs_delayed_ref_lock(trans, locked_ref);
1810
1811                         /*
1812                          * we may have dropped the spin lock to get the head
1813                          * mutex lock, and that might have given someone else
1814                          * time to free the head.  If that's true, it has been
1815                          * removed from our list and we can move on.
1816                          */
1817                         if (ret == -EAGAIN) {
1818                                 locked_ref = NULL;
1819                                 count++;
1820                                 continue;
1821                         }
1822                 }
1823
1824                 /*
1825                  * record the must insert reserved flag before we
1826                  * drop the spin lock.
1827                  */
1828                 must_insert_reserved = locked_ref->must_insert_reserved;
1829                 locked_ref->must_insert_reserved = 0;
1830
1831                 extent_op = locked_ref->extent_op;
1832                 locked_ref->extent_op = NULL;
1833
1834                 /*
1835                  * locked_ref is the head node, so we have to go one
1836                  * node back for any delayed ref updates
1837                  */
1838                 ref = select_delayed_ref(locked_ref);
1839                 if (!ref) {
1840                         /* All delayed refs have been processed, Go ahead
1841                          * and send the head node to run_one_delayed_ref,
1842                          * so that any accounting fixes can happen
1843                          */
1844                         ref = &locked_ref->node;
1845
1846                         if (extent_op && must_insert_reserved) {
1847                                 kfree(extent_op);
1848                                 extent_op = NULL;
1849                         }
1850
1851                         if (extent_op) {
1852                                 spin_unlock(&delayed_refs->lock);
1853
1854                                 ret = run_delayed_extent_op(trans, root,
1855                                                             ref, extent_op);
1856                                 BUG_ON(ret);
1857                                 kfree(extent_op);
1858
1859                                 cond_resched();
1860                                 spin_lock(&delayed_refs->lock);
1861                                 continue;
1862                         }
1863
1864                         list_del_init(&locked_ref->cluster);
1865                         locked_ref = NULL;
1866                 }
1867
1868                 ref->in_tree = 0;
1869                 rb_erase(&ref->rb_node, &delayed_refs->root);
1870                 delayed_refs->num_entries--;
1871
1872                 spin_unlock(&delayed_refs->lock);
1873
1874                 ret = run_one_delayed_ref(trans, root, ref, extent_op,
1875                                           must_insert_reserved);
1876                 BUG_ON(ret);
1877
1878                 btrfs_put_delayed_ref(ref);
1879                 kfree(extent_op);
1880                 count++;
1881
1882                 cond_resched();
1883                 spin_lock(&delayed_refs->lock);
1884         }
1885         return count;
1886 }
1887
1888 /*
1889  * this starts processing the delayed reference count updates and
1890  * extent insertions we have queued up so far.  count can be
1891  * 0, which means to process everything in the tree at the start
1892  * of the run (but not newly added entries), or it can be some target
1893  * number you'd like to process.
1894  */
1895 int btrfs_run_delayed_refs(struct btrfs_trans_handle *trans,
1896                            struct btrfs_root *root, unsigned long count)
1897 {
1898         struct rb_node *node;
1899         struct btrfs_delayed_ref_root *delayed_refs;
1900         struct btrfs_delayed_ref_node *ref;
1901         struct list_head cluster;
1902         int ret;
1903         int run_all = count == (unsigned long)-1;
1904         int run_most = 0;
1905
1906         if (root == root->fs_info->extent_root)
1907                 root = root->fs_info->tree_root;
1908
1909         delayed_refs = &trans->transaction->delayed_refs;
1910         INIT_LIST_HEAD(&cluster);
1911 again:
1912         spin_lock(&delayed_refs->lock);
1913         if (count == 0) {
1914                 count = delayed_refs->num_entries * 2;
1915                 run_most = 1;
1916         }
1917         while (1) {
1918                 if (!(run_all || run_most) &&
1919                     delayed_refs->num_heads_ready < 64)
1920                         break;
1921
1922                 /*
1923                  * go find something we can process in the rbtree.  We start at
1924                  * the beginning of the tree, and then build a cluster
1925                  * of refs to process starting at the first one we are able to
1926                  * lock
1927                  */
1928                 ret = btrfs_find_ref_cluster(trans, &cluster,
1929                                              delayed_refs->run_delayed_start);
1930                 if (ret)
1931                         break;
1932
1933                 ret = run_clustered_refs(trans, root, &cluster);
1934                 BUG_ON(ret < 0);
1935
1936                 count -= min_t(unsigned long, ret, count);
1937
1938                 if (count == 0)
1939                         break;
1940         }
1941
1942         if (run_all) {
1943                 node = rb_first(&delayed_refs->root);
1944                 if (!node)
1945                         goto out;
1946                 count = (unsigned long)-1;
1947
1948                 while (node) {
1949                         ref = rb_entry(node, struct btrfs_delayed_ref_node,
1950                                        rb_node);
1951                         if (btrfs_delayed_ref_is_head(ref)) {
1952                                 struct btrfs_delayed_ref_head *head;
1953
1954                                 head = btrfs_delayed_node_to_head(ref);
1955                                 atomic_inc(&ref->refs);
1956
1957                                 spin_unlock(&delayed_refs->lock);
1958                                 mutex_lock(&head->mutex);
1959                                 mutex_unlock(&head->mutex);
1960
1961                                 btrfs_put_delayed_ref(ref);
1962                                 cond_resched();
1963                                 goto again;
1964                         }
1965                         node = rb_next(node);
1966                 }
1967                 spin_unlock(&delayed_refs->lock);
1968                 schedule_timeout(1);
1969                 goto again;
1970         }
1971 out:
1972         spin_unlock(&delayed_refs->lock);
1973         return 0;
1974 }
1975
1976 int btrfs_set_disk_extent_flags(struct btrfs_trans_handle *trans,
1977                                 struct btrfs_root *root,
1978                                 u64 bytenr, u64 num_bytes, u64 flags,
1979                                 int is_data)
1980 {
1981         struct btrfs_delayed_extent_op *extent_op;
1982         int ret;
1983
1984         extent_op = kmalloc(sizeof(*extent_op), GFP_NOFS);
1985         if (!extent_op)
1986                 return -ENOMEM;
1987
1988         extent_op->flags_to_set = flags;
1989         extent_op->update_flags = 1;
1990         extent_op->update_key = 0;
1991         extent_op->is_data = is_data ? 1 : 0;
1992
1993         ret = btrfs_add_delayed_extent_op(trans, bytenr, num_bytes, extent_op);
1994         if (ret)
1995                 kfree(extent_op);
1996         return ret;
1997 }
1998
1999 static noinline int check_delayed_ref(struct btrfs_trans_handle *trans,
2000                                       struct btrfs_root *root,
2001                                       struct btrfs_path *path,
2002                                       u64 objectid, u64 offset, u64 bytenr)
2003 {
2004         struct btrfs_delayed_ref_head *head;
2005         struct btrfs_delayed_ref_node *ref;
2006         struct btrfs_delayed_data_ref *data_ref;
2007         struct btrfs_delayed_ref_root *delayed_refs;
2008         struct rb_node *node;
2009         int ret = 0;
2010
2011         ret = -ENOENT;
2012         delayed_refs = &trans->transaction->delayed_refs;
2013         spin_lock(&delayed_refs->lock);
2014         head = btrfs_find_delayed_ref_head(trans, bytenr);
2015         if (!head)
2016                 goto out;
2017
2018         if (!mutex_trylock(&head->mutex)) {
2019                 atomic_inc(&head->node.refs);
2020                 spin_unlock(&delayed_refs->lock);
2021
2022                 btrfs_release_path(root->fs_info->extent_root, path);
2023
2024                 mutex_lock(&head->mutex);
2025                 mutex_unlock(&head->mutex);
2026                 btrfs_put_delayed_ref(&head->node);
2027                 return -EAGAIN;
2028         }
2029
2030         node = rb_prev(&head->node.rb_node);
2031         if (!node)
2032                 goto out_unlock;
2033
2034         ref = rb_entry(node, struct btrfs_delayed_ref_node, rb_node);
2035
2036         if (ref->bytenr != bytenr)
2037                 goto out_unlock;
2038
2039         ret = 1;
2040         if (ref->type != BTRFS_EXTENT_DATA_REF_KEY)
2041                 goto out_unlock;
2042
2043         data_ref = btrfs_delayed_node_to_data_ref(ref);
2044
2045         node = rb_prev(node);
2046         if (node) {
2047                 ref = rb_entry(node, struct btrfs_delayed_ref_node, rb_node);
2048                 if (ref->bytenr == bytenr)
2049                         goto out_unlock;
2050         }
2051
2052         if (data_ref->root != root->root_key.objectid ||
2053             data_ref->objectid != objectid || data_ref->offset != offset)
2054                 goto out_unlock;
2055
2056         ret = 0;
2057 out_unlock:
2058         mutex_unlock(&head->mutex);
2059 out:
2060         spin_unlock(&delayed_refs->lock);
2061         return ret;
2062 }
2063
2064 static noinline int check_committed_ref(struct btrfs_trans_handle *trans,
2065                                         struct btrfs_root *root,
2066                                         struct btrfs_path *path,
2067                                         u64 objectid, u64 offset, u64 bytenr)
2068 {
2069         struct btrfs_root *extent_root = root->fs_info->extent_root;
2070         struct extent_buffer *leaf;
2071         struct btrfs_extent_data_ref *ref;
2072         struct btrfs_extent_inline_ref *iref;
2073         struct btrfs_extent_item *ei;
2074         struct btrfs_key key;
2075         u32 item_size;
2076         int ret;
2077
2078         key.objectid = bytenr;
2079         key.offset = (u64)-1;
2080         key.type = BTRFS_EXTENT_ITEM_KEY;
2081
2082         ret = btrfs_search_slot(NULL, extent_root, &key, path, 0, 0);
2083         if (ret < 0)
2084                 goto out;
2085         BUG_ON(ret == 0);
2086
2087         ret = -ENOENT;
2088         if (path->slots[0] == 0)
2089                 goto out;
2090
2091         path->slots[0]--;
2092         leaf = path->nodes[0];
2093         btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);
2094
2095         if (key.objectid != bytenr || key.type != BTRFS_EXTENT_ITEM_KEY)
2096                 goto out;
2097
2098         ret = 1;
2099         item_size = btrfs_item_size_nr(leaf, path->slots[0]);
2100 #ifdef BTRFS_COMPAT_EXTENT_TREE_V0
2101         if (item_size < sizeof(*ei)) {
2102                 WARN_ON(item_size != sizeof(struct btrfs_extent_item_v0));
2103                 goto out;
2104         }
2105 #endif
2106         ei = btrfs_item_ptr(leaf, path->slots[0], struct btrfs_extent_item);
2107
2108         if (item_size != sizeof(*ei) +
2109             btrfs_extent_inline_ref_size(BTRFS_EXTENT_DATA_REF_KEY))
2110                 goto out;
2111
2112         if (btrfs_extent_generation(leaf, ei) <=
2113             btrfs_root_last_snapshot(&root->root_item))
2114                 goto out;
2115
2116         iref = (struct btrfs_extent_inline_ref *)(ei + 1);
2117         if (btrfs_extent_inline_ref_type(leaf, iref) !=
2118             BTRFS_EXTENT_DATA_REF_KEY)
2119                 goto out;
2120
2121         ref = (struct btrfs_extent_data_ref *)(&iref->offset);
2122         if (btrfs_extent_refs(leaf, ei) !=
2123             btrfs_extent_data_ref_count(leaf, ref) ||
2124             btrfs_extent_data_ref_root(leaf, ref) !=
2125             root->root_key.objectid ||
2126             btrfs_extent_data_ref_objectid(leaf, ref) != objectid ||
2127             btrfs_extent_data_ref_offset(leaf, ref) != offset)
2128                 goto out;
2129
2130         ret = 0;
2131 out:
2132         return ret;
2133 }
2134
2135 int btrfs_cross_ref_exist(struct btrfs_trans_handle *trans,
2136                           struct btrfs_root *root,
2137                           u64 objectid, u64 offset, u64 bytenr)
2138 {
2139         struct btrfs_path *path;
2140         int ret;
2141         int ret2;
2142
2143         path = btrfs_alloc_path();
2144         if (!path)
2145                 return -ENOENT;
2146
2147         do {
2148                 ret = check_committed_ref(trans, root, path, objectid,
2149                                           offset, bytenr);
2150                 if (ret && ret != -ENOENT)
2151                         goto out;
2152
2153                 ret2 = check_delayed_ref(trans, root, path, objectid,
2154                                          offset, bytenr);
2155         } while (ret2 == -EAGAIN);
2156
2157         if (ret2 && ret2 != -ENOENT) {
2158                 ret = ret2;
2159                 goto out;
2160         }
2161
2162         if (ret != -ENOENT || ret2 != -ENOENT)
2163                 ret = 0;
2164 out:
2165         btrfs_free_path(path);
2166         return ret;
2167 }
2168
2169 #if 0
2170 int btrfs_cache_ref(struct btrfs_trans_handle *trans, struct btrfs_root *root,
2171                     struct extent_buffer *buf, u32 nr_extents)
2172 {
2173         struct btrfs_key key;
2174         struct btrfs_file_extent_item *fi;
2175         u64 root_gen;
2176         u32 nritems;
2177         int i;
2178         int level;
2179         int ret = 0;
2180         int shared = 0;
2181
2182         if (!root->ref_cows)
2183                 return 0;
2184
2185         if (root->root_key.objectid != BTRFS_TREE_RELOC_OBJECTID) {
2186                 shared = 0;
2187                 root_gen = root->root_key.offset;
2188         } else {
2189                 shared = 1;
2190                 root_gen = trans->transid - 1;
2191         }
2192
2193         level = btrfs_header_level(buf);
2194         nritems = btrfs_header_nritems(buf);
2195
2196         if (level == 0) {
2197                 struct btrfs_leaf_ref *ref;
2198                 struct btrfs_extent_info *info;
2199
2200                 ref = btrfs_alloc_leaf_ref(root, nr_extents);
2201                 if (!ref) {
2202                         ret = -ENOMEM;
2203                         goto out;
2204                 }
2205
2206                 ref->root_gen = root_gen;
2207                 ref->bytenr = buf->start;
2208                 ref->owner = btrfs_header_owner(buf);
2209                 ref->generation = btrfs_header_generation(buf);
2210                 ref->nritems = nr_extents;
2211                 info = ref->extents;
2212
2213                 for (i = 0; nr_extents > 0 && i < nritems; i++) {
2214                         u64 disk_bytenr;
2215                         btrfs_item_key_to_cpu(buf, &key, i);
2216                         if (btrfs_key_type(&key) != BTRFS_EXTENT_DATA_KEY)
2217                                 continue;
2218                         fi = btrfs_item_ptr(buf, i,
2219                                             struct btrfs_file_extent_item);
2220                         if (btrfs_file_extent_type(buf, fi) ==
2221                             BTRFS_FILE_EXTENT_INLINE)
2222                                 continue;
2223                         disk_bytenr = btrfs_file_extent_disk_bytenr(buf, fi);
2224                         if (disk_bytenr == 0)
2225                                 continue;
2226
2227                         info->bytenr = disk_bytenr;
2228                         info->num_bytes =
2229                                 btrfs_file_extent_disk_num_bytes(buf, fi);
2230                         info->objectid = key.objectid;
2231                         info->offset = key.offset;
2232                         info++;
2233                 }
2234
2235                 ret = btrfs_add_leaf_ref(root, ref, shared);
2236                 if (ret == -EEXIST && shared) {
2237                         struct btrfs_leaf_ref *old;
2238                         old = btrfs_lookup_leaf_ref(root, ref->bytenr);
2239                         BUG_ON(!old);
2240                         btrfs_remove_leaf_ref(root, old);
2241                         btrfs_free_leaf_ref(root, old);
2242                         ret = btrfs_add_leaf_ref(root, ref, shared);
2243                 }
2244                 WARN_ON(ret);
2245                 btrfs_free_leaf_ref(root, ref);
2246         }
2247 out:
2248         return ret;
2249 }
2250
2251 /* when a block goes through cow, we update the reference counts of
2252  * everything that block points to.  The internal pointers of the block
2253  * can be in just about any order, and it is likely to have clusters of
2254  * things that are close together and clusters of things that are not.
2255  *
2256  * To help reduce the seeks that come with updating all of these reference
2257  * counts, sort them by byte number before actual updates are done.
2258  *
2259  * struct refsort is used to match byte number to slot in the btree block.
2260  * we sort based on the byte number and then use the slot to actually
2261  * find the item.
2262  *
2263  * struct refsort is smaller than strcut btrfs_item and smaller than
2264  * struct btrfs_key_ptr.  Since we're currently limited to the page size
2265  * for a btree block, there's no way for a kmalloc of refsorts for a
2266  * single node to be bigger than a page.
2267  */
2268 struct refsort {
2269         u64 bytenr;
2270         u32 slot;
2271 };
2272
2273 /*
2274  * for passing into sort()
2275  */
2276 static int refsort_cmp(const void *a_void, const void *b_void)
2277 {
2278         const struct refsort *a = a_void;
2279         const struct refsort *b = b_void;
2280
2281         if (a->bytenr < b->bytenr)
2282                 return -1;
2283         if (a->bytenr > b->bytenr)
2284                 return 1;
2285         return 0;
2286 }
2287 #endif
2288
2289 static int __btrfs_mod_ref(struct btrfs_trans_handle *trans,
2290                            struct btrfs_root *root,
2291                            struct extent_buffer *buf,
2292                            int full_backref, int inc)
2293 {
2294         u64 bytenr;
2295         u64 num_bytes;
2296         u64 parent;
2297         u64 ref_root;
2298         u32 nritems;
2299         struct btrfs_key key;
2300         struct btrfs_file_extent_item *fi;
2301         int i;
2302         int level;
2303         int ret = 0;
2304         int (*process_func)(struct btrfs_trans_handle *, struct btrfs_root *,
2305                             u64, u64, u64, u64, u64, u64);
2306
2307         ref_root = btrfs_header_owner(buf);
2308         nritems = btrfs_header_nritems(buf);
2309         level = btrfs_header_level(buf);
2310
2311         if (!root->ref_cows && level == 0)
2312                 return 0;
2313
2314         if (inc)
2315                 process_func = btrfs_inc_extent_ref;
2316         else
2317                 process_func = btrfs_free_extent;
2318
2319         if (full_backref)
2320                 parent = buf->start;
2321         else
2322                 parent = 0;
2323
2324         for (i = 0; i < nritems; i++) {
2325                 if (level == 0) {
2326                         btrfs_item_key_to_cpu(buf, &key, i);
2327                         if (btrfs_key_type(&key) != BTRFS_EXTENT_DATA_KEY)
2328                                 continue;
2329                         fi = btrfs_item_ptr(buf, i,
2330                                             struct btrfs_file_extent_item);
2331                         if (btrfs_file_extent_type(buf, fi) ==
2332                             BTRFS_FILE_EXTENT_INLINE)
2333                                 continue;
2334                         bytenr = btrfs_file_extent_disk_bytenr(buf, fi);
2335                         if (bytenr == 0)
2336                                 continue;
2337
2338                         num_bytes = btrfs_file_extent_disk_num_bytes(buf, fi);
2339                         key.offset -= btrfs_file_extent_offset(buf, fi);
2340                         ret = process_func(trans, root, bytenr, num_bytes,
2341                                            parent, ref_root, key.objectid,
2342                                            key.offset);
2343                         if (ret)
2344                                 goto fail;
2345                 } else {
2346                         bytenr = btrfs_node_blockptr(buf, i);
2347                         num_bytes = btrfs_level_size(root, level - 1);
2348                         ret = process_func(trans, root, bytenr, num_bytes,
2349                                            parent, ref_root, level - 1, 0);
2350                         if (ret)
2351                                 goto fail;
2352                 }
2353         }
2354         return 0;
2355 fail:
2356         BUG();
2357         return ret;
2358 }
2359
2360 int btrfs_inc_ref(struct btrfs_trans_handle *trans, struct btrfs_root *root,
2361                   struct extent_buffer *buf, int full_backref)
2362 {
2363         return __btrfs_mod_ref(trans, root, buf, full_backref, 1);
2364 }
2365
2366 int btrfs_dec_ref(struct btrfs_trans_handle *trans, struct btrfs_root *root,
2367                   struct extent_buffer *buf, int full_backref)
2368 {
2369         return __btrfs_mod_ref(trans, root, buf, full_backref, 0);
2370 }
2371
2372 static int write_one_cache_group(struct btrfs_trans_handle *trans,
2373                                  struct btrfs_root *root,
2374                                  struct btrfs_path *path,
2375                                  struct btrfs_block_group_cache *cache)
2376 {
2377         int ret;
2378         struct btrfs_root *extent_root = root->fs_info->extent_root;
2379         unsigned long bi;
2380         struct extent_buffer *leaf;
2381
2382         ret = btrfs_search_slot(trans, extent_root, &cache->key, path, 0, 1);
2383         if (ret < 0)
2384                 goto fail;
2385         BUG_ON(ret);
2386
2387         leaf = path->nodes[0];
2388         bi = btrfs_item_ptr_offset(leaf, path->slots[0]);
2389         write_extent_buffer(leaf, &cache->item, bi, sizeof(cache->item));
2390         btrfs_mark_buffer_dirty(leaf);
2391         btrfs_release_path(extent_root, path);
2392 fail:
2393         if (ret)
2394                 return ret;
2395         return 0;
2396
2397 }
2398
2399 int btrfs_write_dirty_block_groups(struct btrfs_trans_handle *trans,
2400                                    struct btrfs_root *root)
2401 {
2402         struct btrfs_block_group_cache *cache, *entry;
2403         struct rb_node *n;
2404         int err = 0;
2405         int werr = 0;
2406         struct btrfs_path *path;
2407         u64 last = 0;
2408
2409         path = btrfs_alloc_path();
2410         if (!path)
2411                 return -ENOMEM;
2412
2413         while (1) {
2414                 cache = NULL;
2415                 spin_lock(&root->fs_info->block_group_cache_lock);
2416                 for (n = rb_first(&root->fs_info->block_group_cache_tree);
2417                      n; n = rb_next(n)) {
2418                         entry = rb_entry(n, struct btrfs_block_group_cache,
2419                                          cache_node);
2420                         if (entry->dirty) {
2421                                 cache = entry;
2422                                 break;
2423                         }
2424                 }
2425                 spin_unlock(&root->fs_info->block_group_cache_lock);
2426
2427                 if (!cache)
2428                         break;
2429
2430                 cache->dirty = 0;
2431                 last += cache->key.offset;
2432
2433                 err = write_one_cache_group(trans, root,
2434                                             path, cache);
2435                 /*
2436                  * if we fail to write the cache group, we want
2437                  * to keep it marked dirty in hopes that a later
2438                  * write will work
2439                  */
2440                 if (err) {
2441                         werr = err;
2442                         continue;
2443                 }
2444         }
2445         btrfs_free_path(path);
2446         return werr;
2447 }
2448
2449 int btrfs_extent_readonly(struct btrfs_root *root, u64 bytenr)
2450 {
2451         struct btrfs_block_group_cache *block_group;
2452         int readonly = 0;
2453
2454         block_group = btrfs_lookup_block_group(root->fs_info, bytenr);
2455         if (!block_group || block_group->ro)
2456                 readonly = 1;
2457         if (block_group)
2458                 btrfs_put_block_group(block_group);
2459         return readonly;
2460 }
2461
2462 static int update_space_info(struct btrfs_fs_info *info, u64 flags,
2463                              u64 total_bytes, u64 bytes_used,
2464                              struct btrfs_space_info **space_info)
2465 {
2466         struct btrfs_space_info *found;
2467
2468         found = __find_space_info(info, flags);
2469         if (found) {
2470                 spin_lock(&found->lock);
2471                 found->total_bytes += total_bytes;
2472                 found->bytes_used += bytes_used;
2473                 found->full = 0;
2474                 spin_unlock(&found->lock);
2475                 *space_info = found;
2476                 return 0;
2477         }
2478         found = kzalloc(sizeof(*found), GFP_NOFS);
2479         if (!found)
2480                 return -ENOMEM;
2481
2482         INIT_LIST_HEAD(&found->block_groups);
2483         init_rwsem(&found->groups_sem);
2484         spin_lock_init(&found->lock);
2485         found->flags = flags;
2486         found->total_bytes = total_bytes;
2487         found->bytes_used = bytes_used;
2488         found->bytes_pinned = 0;
2489         found->bytes_reserved = 0;
2490         found->bytes_readonly = 0;
2491         found->bytes_delalloc = 0;
2492         found->full = 0;
2493         found->force_alloc = 0;
2494         *space_info = found;
2495         list_add_rcu(&found->list, &info->space_info);
2496         return 0;
2497 }
2498
2499 static void set_avail_alloc_bits(struct btrfs_fs_info *fs_info, u64 flags)
2500 {
2501         u64 extra_flags = flags & (BTRFS_BLOCK_GROUP_RAID0 |
2502                                    BTRFS_BLOCK_GROUP_RAID1 |
2503                                    BTRFS_BLOCK_GROUP_RAID10 |
2504                                    BTRFS_BLOCK_GROUP_DUP);
2505         if (extra_flags) {
2506                 if (flags & BTRFS_BLOCK_GROUP_DATA)
2507                         fs_info->avail_data_alloc_bits |= extra_flags;
2508                 if (flags & BTRFS_BLOCK_GROUP_METADATA)
2509                         fs_info->avail_metadata_alloc_bits |= extra_flags;
2510                 if (flags & BTRFS_BLOCK_GROUP_SYSTEM)
2511                         fs_info->avail_system_alloc_bits |= extra_flags;
2512         }
2513 }
2514
2515 static void set_block_group_readonly(struct btrfs_block_group_cache *cache)
2516 {
2517         spin_lock(&cache->space_info->lock);
2518         spin_lock(&cache->lock);
2519         if (!cache->ro) {
2520                 cache->space_info->bytes_readonly += cache->key.offset -
2521                                         btrfs_block_group_used(&cache->item);
2522                 cache->ro = 1;
2523         }
2524         spin_unlock(&cache->lock);
2525         spin_unlock(&cache->space_info->lock);
2526 }
2527
2528 u64 btrfs_reduce_alloc_profile(struct btrfs_root *root, u64 flags)
2529 {
2530         u64 num_devices = root->fs_info->fs_devices->rw_devices;
2531
2532         if (num_devices == 1)
2533                 flags &= ~(BTRFS_BLOCK_GROUP_RAID1 | BTRFS_BLOCK_GROUP_RAID0);
2534         if (num_devices < 4)
2535                 flags &= ~BTRFS_BLOCK_GROUP_RAID10;
2536
2537         if ((flags & BTRFS_BLOCK_GROUP_DUP) &&
2538             (flags & (BTRFS_BLOCK_GROUP_RAID1 |
2539                       BTRFS_BLOCK_GROUP_RAID10))) {
2540                 flags &= ~BTRFS_BLOCK_GROUP_DUP;
2541         }
2542
2543         if ((flags & BTRFS_BLOCK_GROUP_RAID1) &&
2544             (flags & BTRFS_BLOCK_GROUP_RAID10)) {
2545                 flags &= ~BTRFS_BLOCK_GROUP_RAID1;
2546         }
2547
2548         if ((flags & BTRFS_BLOCK_GROUP_RAID0) &&
2549             ((flags & BTRFS_BLOCK_GROUP_RAID1) |
2550              (flags & BTRFS_BLOCK_GROUP_RAID10) |
2551              (flags & BTRFS_BLOCK_GROUP_DUP)))
2552                 flags &= ~BTRFS_BLOCK_GROUP_RAID0;
2553         return flags;
2554 }
2555
2556 static u64 btrfs_get_alloc_profile(struct btrfs_root *root, u64 data)
2557 {
2558         struct btrfs_fs_info *info = root->fs_info;
2559         u64 alloc_profile;
2560
2561         if (data) {
2562                 alloc_profile = info->avail_data_alloc_bits &
2563                         info->data_alloc_profile;
2564                 data = BTRFS_BLOCK_GROUP_DATA | alloc_profile;
2565         } else if (root == root->fs_info->chunk_root) {
2566                 alloc_profile = info->avail_system_alloc_bits &
2567                         info->system_alloc_profile;
2568                 data = BTRFS_BLOCK_GROUP_SYSTEM | alloc_profile;
2569         } else {
2570                 alloc_profile = info->avail_metadata_alloc_bits &
2571                         info->metadata_alloc_profile;
2572                 data = BTRFS_BLOCK_GROUP_METADATA | alloc_profile;
2573         }
2574
2575         return btrfs_reduce_alloc_profile(root, data);
2576 }
2577
2578 void btrfs_set_inode_space_info(struct btrfs_root *root, struct inode *inode)
2579 {
2580         u64 alloc_target;
2581
2582         alloc_target = btrfs_get_alloc_profile(root, 1);
2583         BTRFS_I(inode)->space_info = __find_space_info(root->fs_info,
2584                                                        alloc_target);
2585 }
2586
2587 /*
2588  * for now this just makes sure we have at least 5% of our metadata space free
2589  * for use.
2590  */
2591 int btrfs_check_metadata_free_space(struct btrfs_root *root)
2592 {
2593         struct btrfs_fs_info *info = root->fs_info;
2594         struct btrfs_space_info *meta_sinfo;
2595         u64 alloc_target, thresh;
2596         int committed = 0, ret;
2597
2598         /* get the space info for where the metadata will live */
2599         alloc_target = btrfs_get_alloc_profile(root, 0);
2600         meta_sinfo = __find_space_info(info, alloc_target);
2601
2602 again:
2603         spin_lock(&meta_sinfo->lock);
2604         if (!meta_sinfo->full)
2605                 thresh = meta_sinfo->total_bytes * 80;
2606         else
2607                 thresh = meta_sinfo->total_bytes * 95;
2608
2609         do_div(thresh, 100);
2610
2611         if (meta_sinfo->bytes_used + meta_sinfo->bytes_reserved +
2612             meta_sinfo->bytes_pinned + meta_sinfo->bytes_readonly > thresh) {
2613                 struct btrfs_trans_handle *trans;
2614                 if (!meta_sinfo->full) {
2615                         meta_sinfo->force_alloc = 1;
2616                         spin_unlock(&meta_sinfo->lock);
2617
2618                         trans = btrfs_start_transaction(root, 1);
2619                         if (!trans)
2620                                 return -ENOMEM;
2621
2622                         ret = do_chunk_alloc(trans, root->fs_info->extent_root,
2623                                              2 * 1024 * 1024, alloc_target, 0);
2624                         btrfs_end_transaction(trans, root);
2625                         goto again;
2626                 }
2627                 spin_unlock(&meta_sinfo->lock);
2628
2629                 if (!committed) {
2630                         committed = 1;
2631                         trans = btrfs_join_transaction(root, 1);
2632                         if (!trans)
2633                                 return -ENOMEM;
2634                         ret = btrfs_commit_transaction(trans, root);
2635                         if (ret)
2636                                 return ret;
2637                         goto again;
2638                 }
2639                 return -ENOSPC;
2640         }
2641         spin_unlock(&meta_sinfo->lock);
2642
2643         return 0;
2644 }
2645
2646 /*
2647  * This will check the space that the inode allocates from to make sure we have
2648  * enough space for bytes.
2649  */
2650 int btrfs_check_data_free_space(struct btrfs_root *root, struct inode *inode,
2651                                 u64 bytes)
2652 {
2653         struct btrfs_space_info *data_sinfo;
2654         int ret = 0, committed = 0;
2655
2656         /* make sure bytes are sectorsize aligned */
2657         bytes = (bytes + root->sectorsize - 1) & ~((u64)root->sectorsize - 1);
2658
2659         data_sinfo = BTRFS_I(inode)->space_info;
2660 again:
2661         /* make sure we have enough space to handle the data first */
2662         spin_lock(&data_sinfo->lock);
2663         if (data_sinfo->total_bytes - data_sinfo->bytes_used -
2664             data_sinfo->bytes_delalloc - data_sinfo->bytes_reserved -
2665             data_sinfo->bytes_pinned - data_sinfo->bytes_readonly -
2666             data_sinfo->bytes_may_use < bytes) {
2667                 struct btrfs_trans_handle *trans;
2668
2669                 /*
2670                  * if we don't have enough free bytes in this space then we need
2671                  * to alloc a new chunk.
2672                  */
2673                 if (!data_sinfo->full) {
2674                         u64 alloc_target;
2675
2676                         data_sinfo->force_alloc = 1;
2677                         spin_unlock(&data_sinfo->lock);
2678
2679                         alloc_target = btrfs_get_alloc_profile(root, 1);
2680                         trans = btrfs_start_transaction(root, 1);
2681                         if (!trans)
2682                                 return -ENOMEM;
2683
2684                         ret = do_chunk_alloc(trans, root->fs_info->extent_root,
2685                                              bytes + 2 * 1024 * 1024,
2686                                              alloc_target, 0);
2687                         btrfs_end_transaction(trans, root);
2688                         if (ret)
2689                                 return ret;
2690                         goto again;
2691                 }
2692                 spin_unlock(&data_sinfo->lock);
2693
2694                 /* commit the current transaction and try again */
2695                 if (!committed) {
2696                         committed = 1;
2697                         trans = btrfs_join_transaction(root, 1);
2698                         if (!trans)
2699                                 return -ENOMEM;
2700                         ret = btrfs_commit_transaction(trans, root);
2701                         if (ret)
2702                                 return ret;
2703                         goto again;
2704                 }
2705
2706                 printk(KERN_ERR "no space left, need %llu, %llu delalloc bytes"
2707                        ", %llu bytes_used, %llu bytes_reserved, "
2708                        "%llu bytes_pinned, %llu bytes_readonly, %llu may use"
2709                        "%llu total\n", (unsigned long long)bytes,
2710                        (unsigned long long)data_sinfo->bytes_delalloc,
2711                        (unsigned long long)data_sinfo->bytes_used,
2712                        (unsigned long long)data_sinfo->bytes_reserved,
2713                        (unsigned long long)data_sinfo->bytes_pinned,
2714                        (unsigned long long)data_sinfo->bytes_readonly,
2715                        (unsigned long long)data_sinfo->bytes_may_use,
2716                        (unsigned long long)data_sinfo->total_bytes);
2717                 return -ENOSPC;
2718         }
2719         data_sinfo->bytes_may_use += bytes;
2720         BTRFS_I(inode)->reserved_bytes += bytes;
2721         spin_unlock(&data_sinfo->lock);
2722
2723         return btrfs_check_metadata_free_space(root);
2724 }
2725
2726 /*
2727  * if there was an error for whatever reason after calling
2728  * btrfs_check_data_free_space, call this so we can cleanup the counters.
2729  */
2730 void btrfs_free_reserved_data_space(struct btrfs_root *root,
2731                                     struct inode *inode, u64 bytes)
2732 {
2733         struct btrfs_space_info *data_sinfo;
2734
2735         /* make sure bytes are sectorsize aligned */
2736         bytes = (bytes + root->sectorsize - 1) & ~((u64)root->sectorsize - 1);
2737
2738         data_sinfo = BTRFS_I(inode)->space_info;
2739         spin_lock(&data_sinfo->lock);
2740         data_sinfo->bytes_may_use -= bytes;
2741         BTRFS_I(inode)->reserved_bytes -= bytes;
2742         spin_unlock(&data_sinfo->lock);
2743 }
2744
2745 /* called when we are adding a delalloc extent to the inode's io_tree */
2746 void btrfs_delalloc_reserve_space(struct btrfs_root *root, struct inode *inode,
2747                                   u64 bytes)
2748 {
2749         struct btrfs_space_info *data_sinfo;
2750
2751         /* get the space info for where this inode will be storing its data */
2752         data_sinfo = BTRFS_I(inode)->space_info;
2753
2754         /* make sure we have enough space to handle the data first */
2755         spin_lock(&data_sinfo->lock);
2756         data_sinfo->bytes_delalloc += bytes;
2757
2758         /*
2759          * we are adding a delalloc extent without calling
2760          * btrfs_check_data_free_space first.  This happens on a weird
2761          * writepage condition, but shouldn't hurt our accounting
2762          */
2763         if (unlikely(bytes > BTRFS_I(inode)->reserved_bytes)) {
2764                 data_sinfo->bytes_may_use -= BTRFS_I(inode)->reserved_bytes;
2765                 BTRFS_I(inode)->reserved_bytes = 0;
2766         } else {
2767                 data_sinfo->bytes_may_use -= bytes;
2768                 BTRFS_I(inode)->reserved_bytes -= bytes;
2769         }
2770
2771         spin_unlock(&data_sinfo->lock);
2772 }
2773
2774 /* called when we are clearing an delalloc extent from the inode's io_tree */
2775 void btrfs_delalloc_free_space(struct btrfs_root *root, struct inode *inode,
2776                               u64 bytes)
2777 {
2778         struct btrfs_space_info *info;
2779
2780         info = BTRFS_I(inode)->space_info;
2781
2782         spin_lock(&info->lock);
2783         info->bytes_delalloc -= bytes;
2784         spin_unlock(&info->lock);
2785 }
2786
2787 static void force_metadata_allocation(struct btrfs_fs_info *info)
2788 {
2789         struct list_head *head = &info->space_info;
2790         struct btrfs_space_info *found;
2791
2792         rcu_read_lock();
2793         list_for_each_entry_rcu(found, head, list) {
2794                 if (found->flags & BTRFS_BLOCK_GROUP_METADATA)
2795                         found->force_alloc = 1;
2796         }
2797         rcu_read_unlock();
2798 }
2799
2800 static int do_chunk_alloc(struct btrfs_trans_handle *trans,
2801                           struct btrfs_root *extent_root, u64 alloc_bytes,
2802                           u64 flags, int force)
2803 {
2804         struct btrfs_space_info *space_info;
2805         struct btrfs_fs_info *fs_info = extent_root->fs_info;
2806         u64 thresh;
2807         int ret = 0;
2808
2809         mutex_lock(&fs_info->chunk_mutex);
2810
2811         flags = btrfs_reduce_alloc_profile(extent_root, flags);
2812
2813         space_info = __find_space_info(extent_root->fs_info, flags);
2814         if (!space_info) {
2815                 ret = update_space_info(extent_root->fs_info, flags,
2816                                         0, 0, &space_info);
2817                 BUG_ON(ret);
2818         }
2819         BUG_ON(!space_info);
2820
2821         spin_lock(&space_info->lock);
2822         if (space_info->force_alloc) {
2823                 force = 1;
2824                 space_info->force_alloc = 0;
2825         }
2826         if (space_info->full) {
2827                 spin_unlock(&space_info->lock);
2828                 goto out;
2829         }
2830
2831         thresh = space_info->total_bytes - space_info->bytes_readonly;
2832         thresh = div_factor(thresh, 6);
2833         if (!force &&
2834            (space_info->bytes_used + space_info->bytes_pinned +
2835             space_info->bytes_reserved + alloc_bytes) < thresh) {
2836                 spin_unlock(&space_info->lock);
2837                 goto out;
2838         }
2839         spin_unlock(&space_info->lock);
2840
2841         /*
2842          * if we're doing a data chunk, go ahead and make sure that
2843          * we keep a reasonable number of metadata chunks allocated in the
2844          * FS as well.
2845          */
2846         if (flags & BTRFS_BLOCK_GROUP_DATA) {
2847                 fs_info->data_chunk_allocations++;
2848                 if (!(fs_info->data_chunk_allocations %
2849                       fs_info->metadata_ratio))
2850                         force_metadata_allocation(fs_info);
2851         }
2852
2853         ret = btrfs_alloc_chunk(trans, extent_root, flags);
2854         if (ret)
2855                 space_info->full = 1;
2856 out:
2857         mutex_unlock(&extent_root->fs_info->chunk_mutex);
2858         return ret;
2859 }
2860
2861 static int update_block_group(struct btrfs_trans_handle *trans,
2862                               struct btrfs_root *root,
2863                               u64 bytenr, u64 num_bytes, int alloc,
2864                               int mark_free)
2865 {
2866         struct btrfs_block_group_cache *cache;
2867         struct btrfs_fs_info *info = root->fs_info;
2868         u64 total = num_bytes;
2869         u64 old_val;
2870         u64 byte_in_group;
2871
2872         /* block accounting for super block */
2873         spin_lock(&info->delalloc_lock);
2874         old_val = btrfs_super_bytes_used(&info->super_copy);
2875         if (alloc)
2876                 old_val += num_bytes;
2877         else
2878                 old_val -= num_bytes;
2879         btrfs_set_super_bytes_used(&info->super_copy, old_val);
2880
2881         /* block accounting for root item */
2882         old_val = btrfs_root_used(&root->root_item);
2883         if (alloc)
2884                 old_val += num_bytes;
2885         else
2886                 old_val -= num_bytes;
2887         btrfs_set_root_used(&root->root_item, old_val);
2888         spin_unlock(&info->delalloc_lock);
2889
2890         while (total) {
2891                 cache = btrfs_lookup_block_group(info, bytenr);
2892                 if (!cache)
2893                         return -1;
2894                 byte_in_group = bytenr - cache->key.objectid;
2895                 WARN_ON(byte_in_group > cache->key.offset);
2896
2897                 spin_lock(&cache->space_info->lock);
2898                 spin_lock(&cache->lock);
2899                 cache->dirty = 1;
2900                 old_val = btrfs_block_group_used(&cache->item);
2901                 num_bytes = min(total, cache->key.offset - byte_in_group);
2902                 if (alloc) {
2903                         old_val += num_bytes;
2904                         cache->space_info->bytes_used += num_bytes;
2905                         if (cache->ro)
2906                                 cache->space_info->bytes_readonly -= num_bytes;
2907                         btrfs_set_block_group_used(&cache->item, old_val);
2908                         spin_unlock(&cache->lock);
2909                         spin_unlock(&cache->space_info->lock);
2910                 } else {
2911                         old_val -= num_bytes;
2912                         cache->space_info->bytes_used -= num_bytes;
2913                         if (cache->ro)
2914                                 cache->space_info->bytes_readonly += num_bytes;
2915                         btrfs_set_block_group_used(&cache->item, old_val);
2916                         spin_unlock(&cache->lock);
2917                         spin_unlock(&cache->space_info->lock);
2918                         if (mark_free) {
2919                                 int ret;
2920
2921                                 ret = btrfs_discard_extent(root, bytenr,
2922                                                            num_bytes);
2923                                 WARN_ON(ret);
2924
2925                                 ret = btrfs_add_free_space(cache, bytenr,
2926                                                            num_bytes);
2927                                 WARN_ON(ret);
2928                         }
2929                 }
2930                 btrfs_put_block_group(cache);
2931                 total -= num_bytes;
2932                 bytenr += num_bytes;
2933         }
2934         return 0;
2935 }
2936
2937 static u64 first_logical_byte(struct btrfs_root *root, u64 search_start)
2938 {
2939         struct btrfs_block_group_cache *cache;
2940         u64 bytenr;
2941
2942         cache = btrfs_lookup_first_block_group(root->fs_info, search_start);
2943         if (!cache)
2944                 return 0;
2945
2946         bytenr = cache->key.objectid;
2947         btrfs_put_block_group(cache);
2948
2949         return bytenr;
2950 }
2951
2952 int btrfs_update_pinned_extents(struct btrfs_root *root,
2953                                 u64 bytenr, u64 num, int pin)
2954 {
2955         u64 len;
2956         struct btrfs_block_group_cache *cache;
2957         struct btrfs_fs_info *fs_info = root->fs_info;
2958
2959         if (pin) {
2960                 set_extent_dirty(&fs_info->pinned_extents,
2961                                 bytenr, bytenr + num - 1, GFP_NOFS);
2962         } else {
2963                 clear_extent_dirty(&fs_info->pinned_extents,
2964                                 bytenr, bytenr + num - 1, GFP_NOFS);
2965         }
2966
2967         while (num > 0) {
2968                 cache = btrfs_lookup_block_group(fs_info, bytenr);
2969                 BUG_ON(!cache);
2970                 len = min(num, cache->key.offset -
2971                           (bytenr - cache->key.objectid));
2972                 if (pin) {
2973                         spin_lock(&cache->space_info->lock);
2974                         spin_lock(&cache->lock);
2975                         cache->pinned += len;
2976                         cache->space_info->bytes_pinned += len;
2977                         spin_unlock(&cache->lock);
2978                         spin_unlock(&cache->space_info->lock);
2979                         fs_info->total_pinned += len;
2980                 } else {
2981                         spin_lock(&cache->space_info->lock);
2982                         spin_lock(&cache->lock);
2983                         cache->pinned -= len;
2984                         cache->space_info->bytes_pinned -= len;
2985                         spin_unlock(&cache->lock);
2986                         spin_unlock(&cache->space_info->lock);
2987                         fs_info->total_pinned -= len;
2988                         if (cache->cached)
2989                                 btrfs_add_free_space(cache, bytenr, len);
2990                 }
2991                 btrfs_put_block_group(cache);
2992                 bytenr += len;
2993                 num -= len;
2994         }
2995         return 0;
2996 }
2997
2998 static int update_reserved_extents(struct btrfs_root *root,
2999                                    u64 bytenr, u64 num, int reserve)
3000 {
3001         u64 len;
3002         struct btrfs_block_group_cache *cache;
3003         struct btrfs_fs_info *fs_info = root->fs_info;
3004
3005         while (num > 0) {
3006                 cache = btrfs_lookup_block_group(fs_info, bytenr);
3007                 BUG_ON(!cache);
3008                 len = min(num, cache->key.offset -
3009                           (bytenr - cache->key.objectid));
3010
3011                 spin_lock(&cache->space_info->lock);
3012                 spin_lock(&cache->lock);
3013                 if (reserve) {
3014                         cache->reserved += len;
3015                         cache->space_info->bytes_reserved += len;
3016                 } else {
3017                         cache->reserved -= len;
3018                         cache->space_info->bytes_reserved -= len;
3019                 }
3020                 spin_unlock(&cache->lock);
3021                 spin_unlock(&cache->space_info->lock);
3022                 btrfs_put_block_group(cache);
3023                 bytenr += len;
3024                 num -= len;
3025         }
3026         return 0;
3027 }
3028
3029 int btrfs_copy_pinned(struct btrfs_root *root, struct extent_io_tree *copy)
3030 {
3031         u64 last = 0;
3032         u64 start;
3033         u64 end;
3034         struct extent_io_tree *pinned_extents = &root->fs_info->pinned_extents;
3035         int ret;
3036
3037         while (1) {
3038                 ret = find_first_extent_bit(pinned_extents, last,
3039                                             &start, &end, EXTENT_DIRTY);
3040                 if (ret)
3041                         break;
3042                 set_extent_dirty(copy, start, end, GFP_NOFS);
3043                 last = end + 1;
3044         }
3045         return 0;
3046 }
3047
3048 int btrfs_finish_extent_commit(struct btrfs_trans_handle *trans,
3049                                struct btrfs_root *root,
3050                                struct extent_io_tree *unpin)
3051 {
3052         u64 start;
3053         u64 end;
3054         int ret;
3055
3056         while (1) {
3057                 ret = find_first_extent_bit(unpin, 0, &start, &end,
3058                                             EXTENT_DIRTY);
3059                 if (ret)
3060                         break;
3061
3062                 ret = btrfs_discard_extent(root, start, end + 1 - start);
3063
3064                 /* unlocks the pinned mutex */
3065                 btrfs_update_pinned_extents(root, start, end + 1 - start, 0);
3066                 clear_extent_dirty(unpin, start, end, GFP_NOFS);
3067
3068                 cond_resched();
3069         }
3070         return ret;
3071 }
3072
3073 static int pin_down_bytes(struct btrfs_trans_handle *trans,
3074                           struct btrfs_root *root,
3075                           struct btrfs_path *path,
3076                           u64 bytenr, u64 num_bytes, int is_data,
3077                           struct extent_buffer **must_clean)
3078 {
3079         int err = 0;
3080         struct extent_buffer *buf;
3081
3082         if (is_data)
3083                 goto pinit;
3084
3085         buf = btrfs_find_tree_block(root, bytenr, num_bytes);
3086         if (!buf)
3087                 goto pinit;
3088
3089         /* we can reuse a block if it hasn't been written
3090          * and it is from this transaction.  We can't
3091          * reuse anything from the tree log root because
3092          * it has tiny sub-transactions.
3093          */
3094         if (btrfs_buffer_uptodate(buf, 0) &&
3095             btrfs_try_tree_lock(buf)) {
3096                 u64 header_owner = btrfs_header_owner(buf);
3097                 u64 header_transid = btrfs_header_generation(buf);
3098                 if (header_owner != BTRFS_TREE_LOG_OBJECTID &&
3099                     header_transid == trans->transid &&
3100                     !btrfs_header_flag(buf, BTRFS_HEADER_FLAG_WRITTEN)) {
3101                         *must_clean = buf;
3102                         return 1;
3103                 }
3104                 btrfs_tree_unlock(buf);
3105         }
3106         free_extent_buffer(buf);
3107 pinit:
3108         btrfs_set_path_blocking(path);
3109         /* unlocks the pinned mutex */
3110         btrfs_update_pinned_extents(root, bytenr, num_bytes, 1);
3111
3112         BUG_ON(err < 0);
3113         return 0;
3114 }
3115
3116
3117 static int __btrfs_free_extent(struct btrfs_trans_handle *trans,
3118                                 struct btrfs_root *root,
3119                                 u64 bytenr, u64 num_bytes, u64 parent,
3120                                 u64 root_objectid, u64 owner_objectid,
3121                                 u64 owner_offset, int refs_to_drop,
3122                                 struct btrfs_delayed_extent_op *extent_op)
3123 {
3124         struct btrfs_key key;
3125         struct btrfs_path *path;
3126         struct btrfs_fs_info *info = root->fs_info;
3127         struct btrfs_root *extent_root = info->extent_root;
3128         struct extent_buffer *leaf;
3129         struct btrfs_extent_item *ei;
3130         struct btrfs_extent_inline_ref *iref;
3131         int ret;
3132         int is_data;
3133         int extent_slot = 0;
3134         int found_extent = 0;
3135         int num_to_del = 1;
3136         u32 item_size;
3137         u64 refs;
3138
3139         path = btrfs_alloc_path();
3140         if (!path)
3141                 return -ENOMEM;
3142
3143         path->reada = 1;
3144         path->leave_spinning = 1;
3145
3146         is_data = owner_objectid >= BTRFS_FIRST_FREE_OBJECTID;
3147         BUG_ON(!is_data && refs_to_drop != 1);
3148
3149         ret = lookup_extent_backref(trans, extent_root, path, &iref,
3150                                     bytenr, num_bytes, parent,
3151                                     root_objectid, owner_objectid,
3152                                     owner_offset);
3153         if (ret == 0) {
3154                 extent_slot = path->slots[0];
3155                 while (extent_slot >= 0) {
3156                         btrfs_item_key_to_cpu(path->nodes[0], &key,
3157                                               extent_slot);
3158                         if (key.objectid != bytenr)
3159                                 break;
3160                         if (key.type == BTRFS_EXTENT_ITEM_KEY &&
3161                             key.offset == num_bytes) {
3162                                 found_extent = 1;
3163                                 break;
3164                         }
3165                         if (path->slots[0] - extent_slot > 5)
3166                                 break;
3167                         extent_slot--;
3168                 }
3169 #ifdef BTRFS_COMPAT_EXTENT_TREE_V0
3170                 item_size = btrfs_item_size_nr(path->nodes[0], extent_slot);
3171                 if (found_extent && item_size < sizeof(*ei))
3172                         found_extent = 0;
3173 #endif
3174                 if (!found_extent) {
3175                         BUG_ON(iref);
3176                         ret = remove_extent_backref(trans, extent_root, path,
3177                                                     NULL, refs_to_drop,
3178                                                     is_data);
3179                         BUG_ON(ret);
3180                         btrfs_release_path(extent_root, path);
3181                         path->leave_spinning = 1;
3182
3183                         key.objectid = bytenr;
3184                         key.type = BTRFS_EXTENT_ITEM_KEY;
3185                         key.offset = num_bytes;
3186
3187                         ret = btrfs_search_slot(trans, extent_root,
3188                                                 &key, path, -1, 1);
3189                         if (ret) {
3190                                 printk(KERN_ERR "umm, got %d back from search"
3191                                        ", was looking for %llu\n", ret,
3192                                        (unsigned long long)bytenr);
3193                                 btrfs_print_leaf(extent_root, path->nodes[0]);
3194                         }
3195                         BUG_ON(ret);
3196                         extent_slot = path->slots[0];
3197                 }
3198         } else {
3199                 btrfs_print_leaf(extent_root, path->nodes[0]);
3200                 WARN_ON(1);
3201                 printk(KERN_ERR "btrfs unable to find ref byte nr %llu "
3202                        "parent %llu root %llu  owner %llu offset %llu\n",
3203                        (unsigned long long)bytenr,
3204                        (unsigned long long)parent,
3205                        (unsigned long long)root_objectid,
3206                        (unsigned long long)owner_objectid,
3207                        (unsigned long long)owner_offset);
3208         }
3209
3210         leaf = path->nodes[0];
3211         item_size = btrfs_item_size_nr(leaf, extent_slot);
3212 #ifdef BTRFS_COMPAT_EXTENT_TREE_V0
3213         if (item_size < sizeof(*ei)) {
3214                 BUG_ON(found_extent || extent_slot != path->slots[0]);
3215                 ret = convert_extent_item_v0(trans, extent_root, path,
3216                                              owner_objectid, 0);
3217                 BUG_ON(ret < 0);
3218
3219                 btrfs_release_path(extent_root, path);
3220                 path->leave_spinning = 1;
3221
3222                 key.objectid = bytenr;
3223                 key.type = BTRFS_EXTENT_ITEM_KEY;
3224                 key.offset = num_bytes;
3225
3226                 ret = btrfs_search_slot(trans, extent_root, &key, path,
3227                                         -1, 1);
3228                 if (ret) {
3229                         printk(KERN_ERR "umm, got %d back from search"
3230                                ", was looking for %llu\n", ret,
3231                                (unsigned long long)bytenr);
3232                         btrfs_print_leaf(extent_root, path->nodes[0]);
3233                 }
3234                 BUG_ON(ret);
3235                 extent_slot = path->slots[0];
3236                 leaf = path->nodes[0];
3237                 item_size = btrfs_item_size_nr(leaf, extent_slot);
3238         }
3239 #endif
3240         BUG_ON(item_size < sizeof(*ei));
3241         ei = btrfs_item_ptr(leaf, extent_slot,
3242                             struct btrfs_extent_item);
3243         if (owner_objectid < BTRFS_FIRST_FREE_OBJECTID) {
3244                 struct btrfs_tree_block_info *bi;
3245                 BUG_ON(item_size < sizeof(*ei) + sizeof(*bi));
3246                 bi = (struct btrfs_tree_block_info *)(ei + 1);
3247                 WARN_ON(owner_objectid != btrfs_tree_block_level(leaf, bi));
3248         }
3249
3250         refs = btrfs_extent_refs(leaf, ei);
3251         BUG_ON(refs < refs_to_drop);
3252         refs -= refs_to_drop;
3253
3254         if (refs > 0) {
3255                 if (extent_op)
3256                         __run_delayed_extent_op(extent_op, leaf, ei);
3257                 /*
3258                  * In the case of inline back ref, reference count will
3259                  * be updated by remove_extent_backref
3260                  */
3261                 if (iref) {
3262                         BUG_ON(!found_extent);
3263                 } else {
3264                         btrfs_set_extent_refs(leaf, ei, refs);
3265                         btrfs_mark_buffer_dirty(leaf);
3266                 }
3267                 if (found_extent) {
3268                         ret = remove_extent_backref(trans, extent_root, path,
3269                                                     iref, refs_to_drop,
3270                                                     is_data);
3271                         BUG_ON(ret);
3272                 }
3273         } else {
3274                 int mark_free = 0;
3275                 struct extent_buffer *must_clean = NULL;
3276
3277                 if (found_extent) {
3278                         BUG_ON(is_data && refs_to_drop !=
3279                                extent_data_ref_count(root, path, iref));
3280                         if (iref) {
3281                                 BUG_ON(path->slots[0] != extent_slot);
3282                         } else {
3283                                 BUG_ON(path->slots[0] != extent_slot + 1);
3284                                 path->slots[0] = extent_slot;
3285                                 num_to_del = 2;
3286                         }
3287                 }
3288
3289                 ret = pin_down_bytes(trans, root, path, bytenr,
3290                                      num_bytes, is_data, &must_clean);
3291                 if (ret > 0)
3292                         mark_free = 1;
3293                 BUG_ON(ret < 0);
3294                 /*
3295                  * it is going to be very rare for someone to be waiting
3296                  * on the block we're freeing.  del_items might need to
3297                  * schedule, so rather than get fancy, just force it
3298                  * to blocking here
3299                  */
3300                 if (must_clean)
3301                         btrfs_set_lock_blocking(must_clean);
3302
3303                 ret = btrfs_del_items(trans, extent_root, path, path->slots[0],
3304                                       num_to_del);
3305                 BUG_ON(ret);
3306                 btrfs_release_path(extent_root, path);
3307
3308                 if (must_clean) {
3309                         clean_tree_block(NULL, root, must_clean);
3310                         btrfs_tree_unlock(must_clean);
3311                         free_extent_buffer(must_clean);
3312                 }
3313
3314                 if (is_data) {
3315                         ret = btrfs_del_csums(trans, root, bytenr, num_bytes);
3316                         BUG_ON(ret);
3317                 } else {
3318                         invalidate_mapping_pages(info->btree_inode->i_mapping,
3319                              bytenr >> PAGE_CACHE_SHIFT,
3320                              (bytenr + num_bytes - 1) >> PAGE_CACHE_SHIFT);
3321                 }
3322
3323                 ret = update_block_group(trans, root, bytenr, num_bytes, 0,
3324                                          mark_free);
3325                 BUG_ON(ret);
3326         }
3327         btrfs_free_path(path);
3328         return ret;
3329 }
3330
3331 /*
3332  * when we free an extent, it is possible (and likely) that we free the last
3333  * delayed ref for that extent as well.  This searches the delayed ref tree for
3334  * a given extent, and if there are no other delayed refs to be processed, it
3335  * removes it from the tree.
3336  */
3337 static noinline int check_ref_cleanup(struct btrfs_trans_handle *trans,
3338                                       struct btrfs_root *root, u64 bytenr)
3339 {
3340         struct btrfs_delayed_ref_head *head;
3341         struct btrfs_delayed_ref_root *delayed_refs;
3342         struct btrfs_delayed_ref_node *ref;
3343         struct rb_node *node;
3344         int ret;
3345
3346         delayed_refs = &trans->transaction->delayed_refs;
3347         spin_lock(&delayed_refs->lock);
3348         head = btrfs_find_delayed_ref_head(trans, bytenr);
3349         if (!head)
3350                 goto out;
3351
3352         node = rb_prev(&head->node.rb_node);
3353         if (!node)
3354                 goto out;
3355
3356         ref = rb_entry(node, struct btrfs_delayed_ref_node, rb_node);
3357
3358         /* there are still entries for this ref, we can't drop it */
3359         if (ref->bytenr == bytenr)
3360                 goto out;
3361
3362         if (head->extent_op) {
3363                 if (!head->must_insert_reserved)
3364                         goto out;
3365                 kfree(head->extent_op);
3366                 head->extent_op = NULL;
3367         }
3368
3369         /*
3370          * waiting for the lock here would deadlock.  If someone else has it
3371          * locked they are already in the process of dropping it anyway
3372          */
3373         if (!mutex_trylock(&head->mutex))
3374                 goto out;
3375
3376         /*
3377          * at this point we have a head with no other entries.  Go
3378          * ahead and process it.
3379          */
3380         head->node.in_tree = 0;
3381         rb_erase(&head->node.rb_node, &delayed_refs->root);
3382
3383         delayed_refs->num_entries--;
3384
3385         /*
3386          * we don't take a ref on the node because we're removing it from the
3387          * tree, so we just steal the ref the tree was holding.
3388          */
3389         delayed_refs->num_heads--;
3390         if (list_empty(&head->cluster))
3391                 delayed_refs->num_heads_ready--;
3392
3393         list_del_init(&head->cluster);
3394         spin_unlock(&delayed_refs->lock);
3395
3396         ret = run_one_delayed_ref(trans, root->fs_info->tree_root,
3397                                   &head->node, head->extent_op,
3398                                   head->must_insert_reserved);
3399         BUG_ON(ret);
3400         btrfs_put_delayed_ref(&head->node);
3401         return 0;
3402 out:
3403         spin_unlock(&delayed_refs->lock);
3404         return 0;
3405 }
3406
3407 int btrfs_free_extent(struct btrfs_trans_handle *trans,
3408                       struct btrfs_root *root,
3409                       u64 bytenr, u64 num_bytes, u64 parent,
3410                       u64 root_objectid, u64 owner, u64 offset)
3411 {
3412         int ret;
3413
3414         /*
3415          * tree log blocks never actually go into the extent allocation
3416          * tree, just update pinning info and exit early.
3417          */
3418         if (root_objectid == BTRFS_TREE_LOG_OBJECTID) {
3419                 WARN_ON(owner >= BTRFS_FIRST_FREE_OBJECTID);
3420                 /* unlocks the pinned mutex */
3421                 btrfs_update_pinned_extents(root, bytenr, num_bytes, 1);
3422                 update_reserved_extents(root, bytenr, num_bytes, 0);
3423                 ret = 0;
3424         } else if (owner < BTRFS_FIRST_FREE_OBJECTID) {
3425                 ret = btrfs_add_delayed_tree_ref(trans, bytenr, num_bytes,
3426                                         parent, root_objectid, (int)owner,
3427                                         BTRFS_DROP_DELAYED_REF, NULL);
3428                 BUG_ON(ret);
3429                 ret = check_ref_cleanup(trans, root, bytenr);
3430                 BUG_ON(ret);
3431         } else {
3432                 ret = btrfs_add_delayed_data_ref(trans, bytenr, num_bytes,
3433                                         parent, root_objectid, owner,
3434                                         offset, BTRFS_DROP_DELAYED_REF, NULL);
3435                 BUG_ON(ret);
3436         }
3437         return ret;
3438 }
3439
3440 static u64 stripe_align(struct btrfs_root *root, u64 val)
3441 {
3442         u64 mask = ((u64)root->stripesize - 1);
3443         u64 ret = (val + mask) & ~mask;
3444         return ret;
3445 }
3446
3447 /*
3448  * walks the btree of allocated extents and find a hole of a given size.
3449  * The key ins is changed to record the hole:
3450  * ins->objectid == block start
3451  * ins->flags = BTRFS_EXTENT_ITEM_KEY
3452  * ins->offset == number of blocks
3453  * Any available blocks before search_start are skipped.
3454  */
3455 static noinline int find_free_extent(struct btrfs_trans_handle *trans,
3456                                      struct btrfs_root *orig_root,
3457                                      u64 num_bytes, u64 empty_size,
3458                                      u64 search_start, u64 search_end,
3459                                      u64 hint_byte, struct btrfs_key *ins,
3460                                      u64 exclude_start, u64 exclude_nr,
3461                                      int data)
3462 {
3463         int ret = 0;
3464         struct btrfs_root *root = orig_root->fs_info->extent_root;
3465         struct btrfs_free_cluster *last_ptr = NULL;
3466         struct btrfs_block_group_cache *block_group = NULL;
3467         int empty_cluster = 2 * 1024 * 1024;
3468         int allowed_chunk_alloc = 0;
3469         struct btrfs_space_info *space_info;
3470         int last_ptr_loop = 0;
3471         int loop = 0;
3472
3473         WARN_ON(num_bytes < root->sectorsize);
3474         btrfs_set_key_type(ins, BTRFS_EXTENT_ITEM_KEY);
3475         ins->objectid = 0;
3476         ins->offset = 0;
3477
3478         space_info = __find_space_info(root->fs_info, data);
3479
3480         if (orig_root->ref_cows || empty_size)
3481                 allowed_chunk_alloc = 1;
3482
3483         if (data & BTRFS_BLOCK_GROUP_METADATA) {
3484                 last_ptr = &root->fs_info->meta_alloc_cluster;
3485                 if (!btrfs_test_opt(root, SSD))
3486                         empty_cluster = 64 * 1024;
3487         }
3488
3489         if ((data & BTRFS_BLOCK_GROUP_DATA) && btrfs_test_opt(root, SSD)) {
3490                 last_ptr = &root->fs_info->data_alloc_cluster;
3491         }
3492
3493         if (last_ptr) {
3494                 spin_lock(&last_ptr->lock);
3495                 if (last_ptr->block_group)
3496                         hint_byte = last_ptr->window_start;
3497                 spin_unlock(&last_ptr->lock);
3498         }
3499
3500         search_start = max(search_start, first_logical_byte(root, 0));
3501         search_start = max(search_start, hint_byte);
3502
3503         if (!last_ptr) {
3504                 empty_cluster = 0;
3505                 loop = 1;
3506         }
3507
3508         if (search_start == hint_byte) {
3509                 block_group = btrfs_lookup_block_group(root->fs_info,
3510                                                        search_start);
3511                 if (block_group && block_group_bits(block_group, data)) {
3512                         down_read(&space_info->groups_sem);
3513                         if (list_empty(&block_group->list) ||
3514                             block_group->ro) {
3515                                 /*
3516                                  * someone is removing this block group,
3517                                  * we can't jump into the have_block_group
3518                                  * target because our list pointers are not
3519                                  * valid
3520                                  */
3521                                 btrfs_put_block_group(block_group);
3522                                 up_read(&space_info->groups_sem);
3523                         } else
3524                                 goto have_block_group;
3525                 } else if (block_group) {
3526                         btrfs_put_block_group(block_group);
3527                 }
3528         }
3529
3530 search:
3531         down_read(&space_info->groups_sem);
3532         list_for_each_entry(block_group, &space_info->block_groups, list) {
3533                 u64 offset;
3534
3535                 atomic_inc(&block_group->count);
3536                 search_start = block_group->key.objectid;
3537
3538 have_block_group:
3539                 if (unlikely(!block_group->cached)) {
3540                         mutex_lock(&block_group->cache_mutex);
3541                         ret = cache_block_group(root, block_group);
3542                         mutex_unlock(&block_group->cache_mutex);
3543                         if (ret) {
3544                                 btrfs_put_block_group(block_group);
3545                                 break;
3546                         }
3547                 }
3548
3549                 if (unlikely(block_group->ro))
3550                         goto loop;
3551
3552                 if (last_ptr) {
3553                         /*
3554                          * the refill lock keeps out other
3555                          * people trying to start a new cluster
3556                          */
3557                         spin_lock(&last_ptr->refill_lock);
3558                         if (last_ptr->block_group &&
3559                             (last_ptr->block_group->ro ||
3560                             !block_group_bits(last_ptr->block_group, data))) {
3561                                 offset = 0;
3562                                 goto refill_cluster;
3563                         }
3564
3565                         offset = btrfs_alloc_from_cluster(block_group, last_ptr,
3566                                                  num_bytes, search_start);
3567                         if (offset) {
3568                                 /* we have a block, we're done */
3569                                 spin_unlock(&last_ptr->refill_lock);
3570                                 goto checks;
3571                         }
3572
3573                         spin_lock(&last_ptr->lock);
3574                         /*
3575                          * whoops, this cluster doesn't actually point to
3576                          * this block group.  Get a ref on the block
3577                          * group is does point to and try again
3578                          */
3579                         if (!last_ptr_loop && last_ptr->block_group &&
3580                             last_ptr->block_group != block_group) {
3581
3582                                 btrfs_put_block_group(block_group);
3583                                 block_group = last_ptr->block_group;
3584                                 atomic_inc(&block_group->count);
3585                                 spin_unlock(&last_ptr->lock);
3586                                 spin_unlock(&last_ptr->refill_lock);
3587
3588                                 last_ptr_loop = 1;
3589                                 search_start = block_group->key.objectid;
3590                                 /*
3591                                  * we know this block group is properly
3592                                  * in the list because
3593                                  * btrfs_remove_block_group, drops the
3594                                  * cluster before it removes the block
3595                                  * group from the list
3596                                  */
3597                                 goto have_block_group;
3598                         }
3599                         spin_unlock(&last_ptr->lock);
3600 refill_cluster:
3601                         /*
3602                          * this cluster didn't work out, free it and
3603                          * start over
3604                          */
3605                         btrfs_return_cluster_to_free_space(NULL, last_ptr);
3606
3607                         last_ptr_loop = 0;
3608
3609                         /* allocate a cluster in this block group */
3610                         ret = btrfs_find_space_cluster(trans,
3611                                                block_group, last_ptr,
3612                                                offset, num_bytes,
3613                                                empty_cluster + empty_size);
3614                         if (ret == 0) {
3615                                 /*
3616                                  * now pull our allocation out of this
3617                                  * cluster
3618                                  */
3619                                 offset = btrfs_alloc_from_cluster(block_group,
3620                                                   last_ptr, num_bytes,
3621                                                   search_start);
3622                                 if (offset) {
3623                                         /* we found one, proceed */
3624                                         spin_unlock(&last_ptr->refill_lock);
3625                                         goto checks;
3626                                 }
3627                         }
3628                         /*
3629                          * at this point we either didn't find a cluster
3630                          * or we weren't able to allocate a block from our
3631                          * cluster.  Free the cluster we've been trying
3632                          * to use, and go to the next block group
3633                          */
3634                         if (loop < 2) {
3635                                 btrfs_return_cluster_to_free_space(NULL,
3636                                                                    last_ptr);
3637                                 spin_unlock(&last_ptr->refill_lock);
3638                                 goto loop;
3639                         }
3640                         spin_unlock(&last_ptr->refill_lock);
3641                 }
3642
3643                 offset = btrfs_find_space_for_alloc(block_group, search_start,
3644                                                     num_bytes, empty_size);
3645                 if (!offset)
3646                         goto loop;
3647 checks:
3648                 search_start = stripe_align(root, offset);
3649
3650                 /* move on to the next group */
3651                 if (search_start + num_bytes >= search_end) {
3652                         btrfs_add_free_space(block_group, offset, num_bytes);
3653                         goto loop;
3654                 }
3655
3656                 /* move on to the next group */
3657                 if (search_start + num_bytes >
3658                     block_group->key.objectid + block_group->key.offset) {
3659                         btrfs_add_free_space(block_group, offset, num_bytes);
3660                         goto loop;
3661                 }
3662
3663                 if (exclude_nr > 0 &&
3664                     (search_start + num_bytes > exclude_start &&
3665                      search_start < exclude_start + exclude_nr)) {
3666                         search_start = exclude_start + exclude_nr;
3667
3668                         btrfs_add_free_space(block_group, offset, num_bytes);
3669                         /*
3670                          * if search_start is still in this block group
3671                          * then we just re-search this block group
3672                          */
3673                         if (search_start >= block_group->key.objectid &&
3674                             search_start < (block_group->key.objectid +
3675                                             block_group->key.offset))
3676                                 goto have_block_group;
3677                         goto loop;
3678                 }
3679
3680                 ins->objectid = search_start;
3681                 ins->offset = num_bytes;
3682
3683                 if (offset < search_start)
3684                         btrfs_add_free_space(block_group, offset,
3685                                              search_start - offset);
3686                 BUG_ON(offset > search_start);
3687
3688                 /* we are all good, lets return */
3689                 break;
3690 loop:
3691                 btrfs_put_block_group(block_group);
3692         }
3693         up_read(&space_info->groups_sem);
3694
3695         /* loop == 0, try to find a clustered alloc in every block group
3696          * loop == 1, try again after forcing a chunk allocation
3697          * loop == 2, set empty_size and empty_cluster to 0 and try again
3698          */
3699         if (!ins->objectid && loop < 3 &&
3700             (empty_size || empty_cluster || allowed_chunk_alloc)) {
3701                 if (loop >= 2) {
3702                         empty_size = 0;
3703                         empty_cluster = 0;
3704                 }
3705
3706                 if (allowed_chunk_alloc) {
3707                         ret = do_chunk_alloc(trans, root, num_bytes +
3708                                              2 * 1024 * 1024, data, 1);
3709                         allowed_chunk_alloc = 0;
3710                 } else {
3711                         space_info->force_alloc = 1;
3712                 }
3713
3714                 if (loop < 3) {
3715                         loop++;
3716                         goto search;
3717                 }
3718                 ret = -ENOSPC;
3719         } else if (!ins->objectid) {
3720                 ret = -ENOSPC;
3721         }
3722
3723         /* we found what we needed */
3724         if (ins->objectid) {
3725                 if (!(data & BTRFS_BLOCK_GROUP_DATA))
3726                         trans->block_group = block_group->key.objectid;
3727
3728                 btrfs_put_block_group(block_group);
3729                 ret = 0;
3730         }
3731
3732         return ret;
3733 }
3734
3735 static void dump_space_info(struct btrfs_space_info *info, u64 bytes)
3736 {
3737         struct btrfs_block_group_cache *cache;
3738
3739         printk(KERN_INFO "space_info has %llu free, is %sfull\n",
3740                (unsigned long long)(info->total_bytes - info->bytes_used -
3741                                     info->bytes_pinned - info->bytes_reserved),
3742                (info->full) ? "" : "not ");
3743         printk(KERN_INFO "space_info total=%llu, pinned=%llu, delalloc=%llu,"
3744                " may_use=%llu, used=%llu\n",
3745                (unsigned long long)info->total_bytes,
3746                (unsigned long long)info->bytes_pinned,
3747                (unsigned long long)info->bytes_delalloc,
3748                (unsigned long long)info->bytes_may_use,
3749                (unsigned long long)info->bytes_used);
3750
3751         down_read(&info->groups_sem);
3752         list_for_each_entry(cache, &info->block_groups, list) {
3753                 spin_lock(&cache->lock);
3754                 printk(KERN_INFO "block group %llu has %llu bytes, %llu used "
3755                        "%llu pinned %llu reserved\n",
3756                        (unsigned long long)cache->key.objectid,
3757                        (unsigned long long)cache->key.offset,
3758                        (unsigned long long)btrfs_block_group_used(&cache->item),
3759                        (unsigned long long)cache->pinned,
3760                        (unsigned long long)cache->reserved);
3761                 btrfs_dump_free_space(cache, bytes);
3762                 spin_unlock(&cache->lock);
3763         }
3764         up_read(&info->groups_sem);
3765 }
3766
3767 static int __btrfs_reserve_extent(struct btrfs_trans_handle *trans,
3768                                   struct btrfs_root *root,
3769                                   u64 num_bytes, u64 min_alloc_size,
3770                                   u64 empty_size, u64 hint_byte,
3771                                   u64 search_end, struct btrfs_key *ins,
3772                                   u64 data)
3773 {
3774         int ret;
3775         u64 search_start = 0;
3776         struct btrfs_fs_info *info = root->fs_info;
3777
3778         data = btrfs_get_alloc_profile(root, data);
3779 again:
3780         /*
3781          * the only place that sets empty_size is btrfs_realloc_node, which
3782          * is not called recursively on allocations
3783          */
3784         if (empty_size || root->ref_cows) {
3785                 if (!(data & BTRFS_BLOCK_GROUP_METADATA)) {
3786                         ret = do_chunk_alloc(trans, root->fs_info->extent_root,
3787                                      2 * 1024 * 1024,
3788                                      BTRFS_BLOCK_GROUP_METADATA |
3789                                      (info->metadata_alloc_profile &
3790                                       info->avail_metadata_alloc_bits), 0);
3791                 }
3792                 ret = do_chunk_alloc(trans, root->fs_info->extent_root,
3793                                      num_bytes + 2 * 1024 * 1024, data, 0);
3794         }
3795
3796         WARN_ON(num_bytes < root->sectorsize);
3797         ret = find_free_extent(trans, root, num_bytes, empty_size,
3798                                search_start, search_end, hint_byte, ins,
3799                                trans->alloc_exclude_start,
3800                                trans->alloc_exclude_nr, data);
3801
3802         if (ret == -ENOSPC && num_bytes > min_alloc_size) {
3803                 num_bytes = num_bytes >> 1;
3804                 num_bytes = num_bytes & ~(root->sectorsize - 1);
3805                 num_bytes = max(num_bytes, min_alloc_size);
3806                 do_chunk_alloc(trans, root->fs_info->extent_root,
3807                                num_bytes, data, 1);
3808                 goto again;
3809         }
3810         if (ret) {
3811                 struct btrfs_space_info *sinfo;
3812
3813                 sinfo = __find_space_info(root->fs_info, data);
3814                 printk(KERN_ERR "btrfs allocation failed flags %llu, "
3815                        "wanted %llu\n", (unsigned long long)data,
3816                        (unsigned long long)num_bytes);
3817                 dump_space_info(sinfo, num_bytes);
3818                 BUG();
3819         }
3820
3821         return ret;
3822 }
3823
3824 int btrfs_free_reserved_extent(struct btrfs_root *root, u64 start, u64 len)
3825 {
3826         struct btrfs_block_group_cache *cache;
3827         int ret = 0;
3828
3829         cache = btrfs_lookup_block_group(root->fs_info, start);
3830         if (!cache) {
3831                 printk(KERN_ERR "Unable to find block group for %llu\n",
3832                        (unsigned long long)start);
3833                 return -ENOSPC;
3834         }
3835
3836         ret = btrfs_discard_extent(root, start, len);
3837
3838         btrfs_add_free_space(cache, start, len);
3839         btrfs_put_block_group(cache);
3840         update_reserved_extents(root, start, len, 0);
3841
3842         return ret;
3843 }
3844
3845 int btrfs_reserve_extent(struct btrfs_trans_handle *trans,
3846                                   struct btrfs_root *root,
3847                                   u64 num_bytes, u64 min_alloc_size,
3848                                   u64 empty_size, u64 hint_byte,
3849                                   u64 search_end, struct btrfs_key *ins,
3850                                   u64 data)
3851 {
3852         int ret;
3853         ret = __btrfs_reserve_extent(trans, root, num_bytes, min_alloc_size,
3854                                      empty_size, hint_byte, search_end, ins,
3855                                      data);
3856         update_reserved_extents(root, ins->objectid, ins->offset, 1);
3857         return ret;
3858 }
3859
3860 static int alloc_reserved_file_extent(struct btrfs_trans_handle *trans,
3861                                       struct btrfs_root *root,
3862                                       u64 parent, u64 root_objectid,
3863                                       u64 flags, u64 owner, u64 offset,
3864                                       struct btrfs_key *ins, int ref_mod)
3865 {
3866         int ret;
3867         struct btrfs_fs_info *fs_info = root->fs_info;
3868         struct btrfs_extent_item *extent_item;
3869         struct btrfs_extent_inline_ref *iref;
3870         struct btrfs_path *path;
3871         struct extent_buffer *leaf;
3872         int type;
3873         u32 size;
3874
3875         if (parent > 0)
3876                 type = BTRFS_SHARED_DATA_REF_KEY;
3877         else
3878                 type = BTRFS_EXTENT_DATA_REF_KEY;
3879
3880         size = sizeof(*extent_item) + btrfs_extent_inline_ref_size(type);
3881
3882         path = btrfs_alloc_path();
3883         BUG_ON(!path);
3884
3885         path->leave_spinning = 1;
3886         ret = btrfs_insert_empty_item(trans, fs_info->extent_root, path,
3887                                       ins, size);
3888         BUG_ON(ret);
3889
3890         leaf = path->nodes[0];
3891         extent_item = btrfs_item_ptr(leaf, path->slots[0],
3892                                      struct btrfs_extent_item);
3893         btrfs_set_extent_refs(leaf, extent_item, ref_mod);
3894         btrfs_set_extent_generation(leaf, extent_item, trans->transid);
3895         btrfs_set_extent_flags(leaf, extent_item,
3896                                flags | BTRFS_EXTENT_FLAG_DATA);
3897
3898         iref = (struct btrfs_extent_inline_ref *)(extent_item + 1);
3899         btrfs_set_extent_inline_ref_type(leaf, iref, type);
3900         if (parent > 0) {
3901                 struct btrfs_shared_data_ref *ref;
3902                 ref = (struct btrfs_shared_data_ref *)(iref + 1);
3903                 btrfs_set_extent_inline_ref_offset(leaf, iref, parent);
3904                 btrfs_set_shared_data_ref_count(leaf, ref, ref_mod);
3905         } else {
3906                 struct btrfs_extent_data_ref *ref;
3907                 ref = (struct btrfs_extent_data_ref *)(&iref->offset);
3908                 btrfs_set_extent_data_ref_root(leaf, ref, root_objectid);
3909                 btrfs_set_extent_data_ref_objectid(leaf, ref, owner);
3910                 btrfs_set_extent_data_ref_offset(leaf, ref, offset);
3911                 btrfs_set_extent_data_ref_count(leaf, ref, ref_mod);
3912         }
3913
3914         btrfs_mark_buffer_dirty(path->nodes[0]);
3915         btrfs_free_path(path);
3916
3917         ret = update_block_group(trans, root, ins->objectid, ins->offset,
3918                                  1, 0);
3919         if (ret) {
3920                 printk(KERN_ERR "btrfs update block group failed for %llu "
3921                        "%llu\n", (unsigned long long)ins->objectid,
3922                        (unsigned long long)ins->offset);
3923                 BUG();
3924         }
3925         return ret;
3926 }
3927
3928 static int alloc_reserved_tree_block(struct btrfs_trans_handle *trans,
3929                                      struct btrfs_root *root,
3930                                      u64 parent, u64 root_objectid,
3931                                      u64 flags, struct btrfs_disk_key *key,
3932                                      int level, struct btrfs_key *ins)
3933 {
3934         int ret;
3935         struct btrfs_fs_info *fs_info = root->fs_info;
3936         struct btrfs_extent_item *extent_item;
3937         struct btrfs_tree_block_info *block_info;
3938         struct btrfs_extent_inline_ref *iref;
3939         struct btrfs_path *path;
3940         struct extent_buffer *leaf;
3941         u32 size = sizeof(*extent_item) + sizeof(*block_info) + sizeof(*iref);
3942
3943         path = btrfs_alloc_path();
3944         BUG_ON(!path);
3945
3946         path->leave_spinning = 1;
3947         ret = btrfs_insert_empty_item(trans, fs_info->extent_root, path,
3948                                       ins, size);
3949         BUG_ON(ret);
3950
3951         leaf = path->nodes[0];
3952         extent_item = btrfs_item_ptr(leaf, path->slots[0],
3953                                      struct btrfs_extent_item);
3954         btrfs_set_extent_refs(leaf, extent_item, 1);
3955         btrfs_set_extent_generation(leaf, extent_item, trans->transid);
3956         btrfs_set_extent_flags(leaf, extent_item,
3957                                flags | BTRFS_EXTENT_FLAG_TREE_BLOCK);
3958         block_info = (struct btrfs_tree_block_info *)(extent_item + 1);
3959
3960         btrfs_set_tree_block_key(leaf, block_info, key);
3961         btrfs_set_tree_block_level(leaf, block_info, level);
3962
3963         iref = (struct btrfs_extent_inline_ref *)(block_info + 1);
3964         if (parent > 0) {
3965                 BUG_ON(!(flags & BTRFS_BLOCK_FLAG_FULL_BACKREF));
3966                 btrfs_set_extent_inline_ref_type(leaf, iref,
3967                                                  BTRFS_SHARED_BLOCK_REF_KEY);
3968                 btrfs_set_extent_inline_ref_offset(leaf, iref, parent);
3969         } else {
3970                 btrfs_set_extent_inline_ref_type(leaf, iref,
3971                                                  BTRFS_TREE_BLOCK_REF_KEY);
3972                 btrfs_set_extent_inline_ref_offset(leaf, iref, root_objectid);
3973         }
3974
3975         btrfs_mark_buffer_dirty(leaf);
3976         btrfs_free_path(path);
3977
3978         ret = update_block_group(trans, root, ins->objectid, ins->offset,
3979                                  1, 0);
3980         if (ret) {
3981                 printk(KERN_ERR "btrfs update block group failed for %llu "
3982                        "%llu\n", (unsigned long long)ins->objectid,
3983                        (unsigned long long)ins->offset);
3984                 BUG();
3985         }
3986         return ret;
3987 }
3988
3989 int btrfs_alloc_reserved_file_extent(struct btrfs_trans_handle *trans,
3990                                      struct btrfs_root *root,
3991                                      u64 root_objectid, u64 owner,
3992                                      u64 offset, struct btrfs_key *ins)
3993 {
3994         int ret;
3995
3996         BUG_ON(root_objectid == BTRFS_TREE_LOG_OBJECTID);
3997
3998         ret = btrfs_add_delayed_data_ref(trans, ins->objectid, ins->offset,
3999                                          0, root_objectid, owner, offset,
4000                                          BTRFS_ADD_DELAYED_EXTENT, NULL);
4001         return ret;
4002 }
4003
4004 /*
4005  * this is used by the tree logging recovery code.  It records that
4006  * an extent has been allocated and makes sure to clear the free
4007  * space cache bits as well
4008  */
4009 int btrfs_alloc_logged_file_extent(struct btrfs_trans_handle *trans,
4010                                    struct btrfs_root *root,
4011                                    u64 root_objectid, u64 owner, u64 offset,
4012                                    struct btrfs_key *ins)
4013 {
4014         int ret;
4015         struct btrfs_block_group_cache *block_group;
4016
4017         block_group = btrfs_lookup_block_group(root->fs_info, ins->objectid);
4018         mutex_lock(&block_group->cache_mutex);
4019         cache_block_group(root, block_group);
4020         mutex_unlock(&block_group->cache_mutex);
4021
4022         ret = btrfs_remove_free_space(block_group, ins->objectid,
4023                                       ins->offset);
4024         BUG_ON(ret);
4025         btrfs_put_block_group(block_group);
4026         ret = alloc_reserved_file_extent(trans, root, 0, root_objectid,
4027                                          0, owner, offset, ins, 1);
4028         return ret;
4029 }
4030
4031 /*
4032  * finds a free extent and does all the dirty work required for allocation
4033  * returns the key for the extent through ins, and a tree buffer for
4034  * the first block of the extent through buf.
4035  *
4036  * returns 0 if everything worked, non-zero otherwise.
4037  */
4038 static int alloc_tree_block(struct btrfs_trans_handle *trans,
4039                             struct btrfs_root *root,
4040                             u64 num_bytes, u64 parent, u64 root_objectid,
4041                             struct btrfs_disk_key *key, int level,
4042                             u64 empty_size, u64 hint_byte, u64 search_end,
4043                             struct btrfs_key *ins)
4044 {
4045         int ret;
4046         u64 flags = 0;
4047
4048         ret = __btrfs_reserve_extent(trans, root, num_bytes, num_bytes,
4049                                      empty_size, hint_byte, search_end,
4050                                      ins, 0);
4051         BUG_ON(ret);
4052
4053         if (root_objectid == BTRFS_TREE_RELOC_OBJECTID) {
4054                 if (parent == 0)
4055                         parent = ins->objectid;
4056                 flags |= BTRFS_BLOCK_FLAG_FULL_BACKREF;
4057         } else
4058                 BUG_ON(parent > 0);
4059
4060         update_reserved_extents(root, ins->objectid, ins->offset, 1);
4061         if (root_objectid != BTRFS_TREE_LOG_OBJECTID) {
4062                 struct btrfs_delayed_extent_op *extent_op;
4063                 extent_op = kmalloc(sizeof(*extent_op), GFP_NOFS);
4064                 BUG_ON(!extent_op);
4065                 if (key)
4066                         memcpy(&extent_op->key, key, sizeof(extent_op->key));
4067                 else
4068                         memset(&extent_op->key, 0, sizeof(extent_op->key));
4069                 extent_op->flags_to_set = flags;
4070                 extent_op->update_key = 1;
4071                 extent_op->update_flags = 1;
4072                 extent_op->is_data = 0;
4073
4074                 ret = btrfs_add_delayed_tree_ref(trans, ins->objectid,
4075                                         ins->offset, parent, root_objectid,
4076                                         level, BTRFS_ADD_DELAYED_EXTENT,
4077                                         extent_op);
4078                 BUG_ON(ret);
4079         }
4080         return ret;
4081 }
4082
4083 struct extent_buffer *btrfs_init_new_buffer(struct btrfs_trans_handle *trans,
4084                                             struct btrfs_root *root,
4085                                             u64 bytenr, u32 blocksize,
4086                                             int level)
4087 {
4088         struct extent_buffer *buf;
4089
4090         buf = btrfs_find_create_tree_block(root, bytenr, blocksize);
4091         if (!buf)
4092                 return ERR_PTR(-ENOMEM);
4093         btrfs_set_header_generation(buf, trans->transid);
4094         btrfs_set_buffer_lockdep_class(buf, level);
4095         btrfs_tree_lock(buf);
4096         clean_tree_block(trans, root, buf);
4097
4098         btrfs_set_lock_blocking(buf);
4099         btrfs_set_buffer_uptodate(buf);
4100
4101         if (root->root_key.objectid == BTRFS_TREE_LOG_OBJECTID) {
4102                 set_extent_dirty(&root->dirty_log_pages, buf->start,
4103                          buf->start + buf->len - 1, GFP_NOFS);
4104         } else {
4105                 set_extent_dirty(&trans->transaction->dirty_pages, buf->start,
4106                          buf->start + buf->len - 1, GFP_NOFS);
4107         }
4108         trans->blocks_used++;
4109         /* this returns a buffer locked for blocking */
4110         return buf;
4111 }
4112
4113 /*
4114  * helper function to allocate a block for a given tree
4115  * returns the tree buffer or NULL.
4116  */
4117 struct extent_buffer *btrfs_alloc_free_block(struct btrfs_trans_handle *trans,
4118                                         struct btrfs_root *root, u32 blocksize,
4119                                         u64 parent, u64 root_objectid,
4120                                         struct btrfs_disk_key *key, int level,
4121                                         u64 hint, u64 empty_size)
4122 {
4123         struct btrfs_key ins;
4124         int ret;
4125         struct extent_buffer *buf;
4126
4127         ret = alloc_tree_block(trans, root, blocksize, parent, root_objectid,
4128                                key, level, empty_size, hint, (u64)-1, &ins);
4129         if (ret) {
4130                 BUG_ON(ret > 0);
4131                 return ERR_PTR(ret);
4132         }
4133
4134         buf = btrfs_init_new_buffer(trans, root, ins.objectid,
4135                                     blocksize, level);
4136         return buf;
4137 }
4138
4139 int btrfs_drop_leaf_ref(struct btrfs_trans_handle *trans,
4140                         struct btrfs_root *root, struct extent_buffer *leaf)
4141 {
4142         u64 disk_bytenr;
4143         u64 num_bytes;
4144         struct btrfs_key key;
4145         struct btrfs_file_extent_item *fi;
4146         u32 nritems;
4147         int i;
4148         int ret;
4149
4150         BUG_ON(!btrfs_is_leaf(leaf));
4151         nritems = btrfs_header_nritems(leaf);
4152
4153         for (i = 0; i < nritems; i++) {
4154                 cond_resched();
4155                 btrfs_item_key_to_cpu(leaf, &key, i);
4156
4157                 /* only extents have references, skip everything else */
4158                 if (btrfs_key_type(&key) != BTRFS_EXTENT_DATA_KEY)
4159                         continue;
4160
4161                 fi = btrfs_item_ptr(leaf, i, struct btrfs_file_extent_item);
4162
4163                 /* inline extents live in the btree, they don't have refs */
4164                 if (btrfs_file_extent_type(leaf, fi) ==
4165                     BTRFS_FILE_EXTENT_INLINE)
4166                         continue;
4167
4168                 disk_bytenr = btrfs_file_extent_disk_bytenr(leaf, fi);
4169
4170                 /* holes don't have refs */
4171                 if (disk_bytenr == 0)
4172                         continue;
4173
4174                 num_bytes = btrfs_file_extent_disk_num_bytes(leaf, fi);
4175                 ret = btrfs_free_extent(trans, root, disk_bytenr, num_bytes,
4176                                         leaf->start, 0, key.objectid, 0);
4177                 BUG_ON(ret);
4178         }
4179         return 0;
4180 }
4181
4182 #if 0
4183
4184 static noinline int cache_drop_leaf_ref(struct btrfs_trans_handle *trans,
4185                                         struct btrfs_root *root,
4186                                         struct btrfs_leaf_ref *ref)
4187 {
4188         int i;
4189         int ret;
4190         struct btrfs_extent_info *info;
4191         struct refsort *sorted;
4192
4193         if (ref->nritems == 0)
4194                 return 0;
4195
4196         sorted = kmalloc(sizeof(*sorted) * ref->nritems, GFP_NOFS);
4197         for (i = 0; i < ref->nritems; i++) {
4198                 sorted[i].bytenr = ref->extents[i].bytenr;
4199                 sorted[i].slot = i;
4200         }
4201         sort(sorted, ref->nritems, sizeof(struct refsort), refsort_cmp, NULL);
4202
4203         /*
4204          * the items in the ref were sorted when the ref was inserted
4205          * into the ref cache, so this is already in order
4206          */
4207         for (i = 0; i < ref->nritems; i++) {
4208                 info = ref->extents + sorted[i].slot;
4209                 ret = btrfs_free_extent(trans, root, info->bytenr,
4210                                           info->num_bytes, ref->bytenr,
4211                                           ref->owner, ref->generation,
4212                                           info->objectid, 0);
4213
4214                 atomic_inc(&root->fs_info->throttle_gen);
4215                 wake_up(&root->fs_info->transaction_throttle);
4216                 cond_resched();
4217
4218                 BUG_ON(ret);
4219                 info++;
4220         }
4221
4222         kfree(sorted);
4223         return 0;
4224 }
4225
4226
4227 static int drop_snap_lookup_refcount(struct btrfs_trans_handle *trans,
4228                                      struct btrfs_root *root, u64 start,
4229                                      u64 len, u32 *refs)
4230 {
4231         int ret;
4232
4233         ret = btrfs_lookup_extent_refs(trans, root, start, len, refs);
4234         BUG_ON(ret);
4235
4236 #if 0 /* some debugging code in case we see problems here */
4237         /* if the refs count is one, it won't get increased again.  But
4238          * if the ref count is > 1, someone may be decreasing it at
4239          * the same time we are.
4240          */
4241         if (*refs != 1) {
4242                 struct extent_buffer *eb = NULL;
4243                 eb = btrfs_find_create_tree_block(root, start, len);
4244                 if (eb)
4245                         btrfs_tree_lock(eb);
4246
4247                 mutex_lock(&root->fs_info->alloc_mutex);
4248                 ret = lookup_extent_ref(NULL, root, start, len, refs);
4249                 BUG_ON(ret);
4250                 mutex_unlock(&root->fs_info->alloc_mutex);
4251
4252                 if (eb) {
4253                         btrfs_tree_unlock(eb);
4254                         free_extent_buffer(eb);
4255                 }
4256                 if (*refs == 1) {
4257                         printk(KERN_ERR "btrfs block %llu went down to one "
4258                                "during drop_snap\n", (unsigned long long)start);
4259                 }
4260
4261         }
4262 #endif
4263
4264         cond_resched();
4265         return ret;
4266 }
4267
4268
4269 /*
4270  * this is used while deleting old snapshots, and it drops the refs
4271  * on a whole subtree starting from a level 1 node.
4272  *
4273  * The idea is to sort all the leaf pointers, and then drop the
4274  * ref on all the leaves in order.  Most of the time the leaves
4275  * will have ref cache entries, so no leaf IOs will be required to
4276  * find the extents they have references on.
4277  *
4278  * For each leaf, any references it has are also dropped in order
4279  *
4280  * This ends up dropping the references in something close to optimal
4281  * order for reading and modifying the extent allocation tree.
4282  */
4283 static noinline int drop_level_one_refs(struct btrfs_trans_handle *trans,
4284                                         struct btrfs_root *root,
4285                                         struct btrfs_path *path)
4286 {
4287         u64 bytenr;
4288         u64 root_owner;
4289         u64 root_gen;
4290         struct extent_buffer *eb = path->nodes[1];
4291         struct extent_buffer *leaf;
4292         struct btrfs_leaf_ref *ref;
4293         struct refsort *sorted = NULL;
4294         int nritems = btrfs_header_nritems(eb);
4295         int ret;
4296         int i;
4297         int refi = 0;
4298         int slot = path->slots[1];
4299         u32 blocksize = btrfs_level_size(root, 0);
4300         u32 refs;
4301
4302         if (nritems == 0)
4303                 goto out;
4304
4305         root_owner = btrfs_header_owner(eb);
4306         root_gen = btrfs_header_generation(eb);
4307         sorted = kmalloc(sizeof(*sorted) * nritems, GFP_NOFS);
4308
4309         /*
4310          * step one, sort all the leaf pointers so we don't scribble
4311          * randomly into the extent allocation tree
4312          */
4313         for (i = slot; i < nritems; i++) {
4314                 sorted[refi].bytenr = btrfs_node_blockptr(eb, i);
4315                 sorted[refi].slot = i;
4316                 refi++;
4317         }
4318
4319         /*
4320          * nritems won't be zero, but if we're picking up drop_snapshot
4321          * after a crash, slot might be > 0, so double check things
4322          * just in case.
4323          */
4324         if (refi == 0)
4325                 goto out;
4326
4327         sort(sorted, refi, sizeof(struct refsort), refsort_cmp, NULL);
4328
4329         /*
4330          * the first loop frees everything the leaves point to
4331          */
4332         for (i = 0; i < refi; i++) {
4333                 u64 ptr_gen;
4334
4335                 bytenr = sorted[i].bytenr;
4336
4337                 /*
4338                  * check the reference count on this leaf.  If it is > 1
4339                  * we just decrement it below and don't update any
4340                  * of the refs the leaf points to.
4341                  */
4342                 ret = drop_snap_lookup_refcount(trans, root, bytenr,
4343                                                 blocksize, &refs);
4344                 BUG_ON(ret);
4345                 if (refs != 1)
4346                         continue;
4347
4348                 ptr_gen = btrfs_node_ptr_generation(eb, sorted[i].slot);
4349
4350                 /*
4351                  * the leaf only had one reference, which means the
4352                  * only thing pointing to this leaf is the snapshot
4353                  * we're deleting.  It isn't possible for the reference
4354                  * count to increase again later
4355                  *
4356                  * The reference cache is checked for the leaf,
4357                  * and if found we'll be able to drop any refs held by
4358                  * the leaf without needing to read it in.
4359                  */
4360                 ref = btrfs_lookup_leaf_ref(root, bytenr);
4361                 if (ref && ref->generation != ptr_gen) {
4362                         btrfs_free_leaf_ref(root, ref);
4363                         ref = NULL;
4364                 }
4365                 if (ref) {
4366                         ret = cache_drop_leaf_ref(trans, root, ref);
4367                         BUG_ON(ret);
4368                         btrfs_remove_leaf_ref(root, ref);
4369                         btrfs_free_leaf_ref(root, ref);
4370                 } else {
4371                         /*
4372                          * the leaf wasn't in the reference cache, so
4373                          * we have to read it.
4374                          */
4375                         leaf = read_tree_block(root, bytenr, blocksize,
4376                                                ptr_gen);
4377                         ret = btrfs_drop_leaf_ref(trans, root, leaf);
4378                         BUG_ON(ret);
4379                         free_extent_buffer(leaf);
4380                 }
4381                 atomic_inc(&root->fs_info->throttle_gen);
4382                 wake_up(&root->fs_info->transaction_throttle);
4383                 cond_resched();
4384         }
4385
4386         /*
4387          * run through the loop again to free the refs on the leaves.
4388          * This is faster than doing it in the loop above because
4389          * the leaves are likely to be clustered together.  We end up
4390          * working in nice chunks on the extent allocation tree.
4391          */
4392         for (i = 0; i < refi; i++) {
4393                 bytenr = sorted[i].bytenr;
4394                 ret = btrfs_free_extent(trans, root, bytenr,
4395                                         blocksize, eb->start,
4396                                         root_owner, root_gen, 0, 1);
4397                 BUG_ON(ret);
4398
4399                 atomic_inc(&root->fs_info->throttle_gen);
4400                 wake_up(&root->fs_info->transaction_throttle);
4401                 cond_resched();
4402         }
4403 out:
4404         kfree(sorted);
4405
4406         /*
4407          * update the path to show we've processed the entire level 1
4408          * node.  This will get saved into the root's drop_snapshot_progress
4409          * field so these drops are not repeated again if this transaction
4410          * commits.
4411          */
4412         path->slots[1] = nritems;
4413         return 0;
4414 }
4415
4416 /*
4417  * helper function for drop_snapshot, this walks down the tree dropping ref
4418  * counts as it goes.
4419  */
4420 static noinline int walk_down_tree(struct btrfs_trans_handle *trans,
4421                                    struct btrfs_root *root,
4422                                    struct btrfs_path *path, int *level)
4423 {
4424         u64 root_owner;
4425         u64 root_gen;
4426         u64 bytenr;
4427         u64 ptr_gen;
4428         struct extent_buffer *next;
4429         struct extent_buffer *cur;
4430         struct extent_buffer *parent;
4431         u32 blocksize;
4432         int ret;
4433         u32 refs;
4434
4435         WARN_ON(*level < 0);
4436         WARN_ON(*level >= BTRFS_MAX_LEVEL);
4437         ret = drop_snap_lookup_refcount(trans, root, path->nodes[*level]->start,
4438                                 path->nodes[*level]->len, &refs);
4439         BUG_ON(ret);
4440         if (refs > 1)
4441                 goto out;
4442
4443         /*
4444          * walk down to the last node level and free all the leaves
4445          */
4446         while (*level >= 0) {
4447                 WARN_ON(*level < 0);
4448                 WARN_ON(*level >= BTRFS_MAX_LEVEL);
4449                 cur = path->nodes[*level];
4450
4451                 if (btrfs_header_level(cur) != *level)
4452                         WARN_ON(1);
4453
4454                 if (path->slots[*level] >=
4455                     btrfs_header_nritems(cur))
4456                         break;
4457
4458                 /* the new code goes down to level 1 and does all the
4459                  * leaves pointed to that node in bulk.  So, this check
4460                  * for level 0 will always be false.
4461                  *
4462                  * But, the disk format allows the drop_snapshot_progress
4463                  * field in the root to leave things in a state where
4464                  * a leaf will need cleaning up here.  If someone crashes
4465                  * with the old code and then boots with the new code,
4466                  * we might find a leaf here.
4467                  */
4468                 if (*level == 0) {
4469                         ret = btrfs_drop_leaf_ref(trans, root, cur);
4470                         BUG_ON(ret);
4471                         break;
4472                 }
4473
4474                 /*
4475                  * once we get to level one, process the whole node
4476                  * at once, including everything below it.
4477                  */
4478                 if (*level == 1) {
4479                         ret = drop_level_one_refs(trans, root, path);
4480                         BUG_ON(ret);
4481                         break;
4482                 }
4483
4484                 bytenr = btrfs_node_blockptr(cur, path->slots[*level]);
4485                 ptr_gen = btrfs_node_ptr_generation(cur, path->slots[*level]);
4486                 blocksize = btrfs_level_size(root, *level - 1);
4487
4488                 ret = drop_snap_lookup_refcount(trans, root, bytenr,
4489                                                 blocksize, &refs);
4490                 BUG_ON(ret);
4491
4492                 /*
4493                  * if there is more than one reference, we don't need
4494                  * to read that node to drop any references it has.  We
4495                  * just drop the ref we hold on that node and move on to the
4496                  * next slot in this level.
4497                  */
4498                 if (refs != 1) {
4499                         parent = path->nodes[*level];
4500                         root_owner = btrfs_header_owner(parent);
4501                         root_gen = btrfs_header_generation(parent);
4502                         path->slots[*level]++;
4503
4504                         ret = btrfs_free_extent(trans, root, bytenr,
4505                                                 blocksize, parent->start,
4506                                                 root_owner, root_gen,
4507                                                 *level - 1, 1);
4508                         BUG_ON(ret);
4509
4510                         atomic_inc(&root->fs_info->throttle_gen);
4511                         wake_up(&root->fs_info->transaction_throttle);
4512                         cond_resched();
4513
4514                         continue;
4515                 }
4516
4517                 /*
4518                  * we need to keep freeing things in the next level down.
4519                  * read the block and loop around to process it
4520                  */
4521                 next = read_tree_block(root, bytenr, blocksize, ptr_gen);
4522                 WARN_ON(*level <= 0);
4523                 if (path->nodes[*level-1])
4524                         free_extent_buffer(path->nodes[*level-1]);
4525                 path->nodes[*level-1] = next;
4526                 *level = btrfs_header_level(next);
4527                 path->slots[*level] = 0;
4528                 cond_resched();
4529         }
4530 out:
4531         WARN_ON(*level < 0);
4532         WARN_ON(*level >= BTRFS_MAX_LEVEL);
4533
4534         if (path->nodes[*level] == root->node) {
4535                 parent = path->nodes[*level];
4536                 bytenr = path->nodes[*level]->start;
4537         } else {
4538                 parent = path->nodes[*level + 1];
4539                 bytenr = btrfs_node_blockptr(parent, path->slots[*level + 1]);
4540         }
4541
4542         blocksize = btrfs_level_size(root, *level);
4543         root_owner = btrfs_header_owner(parent);
4544         root_gen = btrfs_header_generation(parent);
4545
4546         /*
4547          * cleanup and free the reference on the last node
4548          * we processed
4549          */
4550         ret = btrfs_free_extent(trans, root, bytenr, blocksize,
4551                                   parent->start, root_owner, root_gen,
4552                                   *level, 1);
4553         free_extent_buffer(path->nodes[*level]);
4554         path->nodes[*level] = NULL;
4555
4556         *level += 1;
4557         BUG_ON(ret);
4558
4559         cond_resched();
4560         return 0;
4561 }
4562 #endif
4563
4564 /*
4565  * helper function for drop_subtree, this function is similar to
4566  * walk_down_tree. The main difference is that it checks reference
4567  * counts while tree blocks are locked.
4568  */
4569 static noinline int walk_down_tree(struct btrfs_trans_handle *trans,
4570                                    struct btrfs_root *root,
4571                                    struct btrfs_path *path, int *level)
4572 {
4573         struct extent_buffer *next;
4574         struct extent_buffer *cur;
4575         struct extent_buffer *parent;
4576         u64 bytenr;
4577         u64 ptr_gen;
4578         u64 refs;
4579         u64 flags;
4580         u32 blocksize;
4581         int ret;
4582
4583         cur = path->nodes[*level];
4584         ret = btrfs_lookup_extent_info(trans, root, cur->start, cur->len,
4585                                        &refs, &flags);
4586         BUG_ON(ret);
4587         if (refs > 1)
4588                 goto out;
4589
4590         BUG_ON(!(flags & BTRFS_BLOCK_FLAG_FULL_BACKREF));
4591
4592         while (*level >= 0) {
4593                 cur = path->nodes[*level];
4594                 if (*level == 0) {
4595                         ret = btrfs_drop_leaf_ref(trans, root, cur);
4596                         BUG_ON(ret);
4597                         clean_tree_block(trans, root, cur);
4598                         break;
4599                 }
4600                 if (path->slots[*level] >= btrfs_header_nritems(cur)) {
4601                         clean_tree_block(trans, root, cur);
4602                         break;
4603                 }
4604
4605                 bytenr = btrfs_node_blockptr(cur, path->slots[*level]);
4606                 blocksize = btrfs_level_size(root, *level - 1);
4607                 ptr_gen = btrfs_node_ptr_generation(cur, path->slots[*level]);
4608
4609                 next = read_tree_block(root, bytenr, blocksize, ptr_gen);
4610                 btrfs_tree_lock(next);
4611                 btrfs_set_lock_blocking(next);
4612
4613                 ret = btrfs_lookup_extent_info(trans, root, bytenr, blocksize,
4614                                                &refs, &flags);
4615                 BUG_ON(ret);
4616                 if (refs > 1) {
4617                         parent = path->nodes[*level];
4618                         ret = btrfs_free_extent(trans, root, bytenr,
4619                                                 blocksize, parent->start,
4620                                                 btrfs_header_owner(parent),
4621                                                 *level - 1, 0);
4622                         BUG_ON(ret);
4623                         path->slots[*level]++;
4624                         btrfs_tree_unlock(next);
4625                         free_extent_buffer(next);
4626                         continue;
4627                 }
4628
4629                 BUG_ON(!(flags & BTRFS_BLOCK_FLAG_FULL_BACKREF));
4630
4631                 *level = btrfs_header_level(next);
4632                 path->nodes[*level] = next;
4633                 path->slots[*level] = 0;
4634                 path->locks[*level] = 1;
4635                 cond_resched();
4636         }
4637 out:
4638         if (path->nodes[*level] == root->node)
4639                 parent = path->nodes[*level];
4640         else
4641                 parent = path->nodes[*level + 1];
4642         bytenr = path->nodes[*level]->start;
4643         blocksize = path->nodes[*level]->len;
4644
4645         ret = btrfs_free_extent(trans, root, bytenr, blocksize, parent->start,
4646                                 btrfs_header_owner(parent), *level, 0);
4647         BUG_ON(ret);
4648
4649         if (path->locks[*level]) {
4650                 btrfs_tree_unlock(path->nodes[*level]);
4651                 path->locks[*level] = 0;
4652         }
4653         free_extent_buffer(path->nodes[*level]);
4654         path->nodes[*level] = NULL;
4655         *level += 1;
4656         cond_resched();
4657         return 0;
4658 }
4659
4660 /*
4661  * helper for dropping snapshots.  This walks back up the tree in the path
4662  * to find the first node higher up where we haven't yet gone through
4663  * all the slots
4664  */
4665 static noinline int walk_up_tree(struct btrfs_trans_handle *trans,
4666                                  struct btrfs_root *root,
4667                                  struct btrfs_path *path,
4668                                  int *level, int max_level)
4669 {
4670         struct btrfs_root_item *root_item = &root->root_item;
4671         int i;
4672         int slot;
4673         int ret;
4674
4675         for (i = *level; i < max_level && path->nodes[i]; i++) {
4676                 slot = path->slots[i];
4677                 if (slot + 1 < btrfs_header_nritems(path->nodes[i])) {
4678                         /*
4679                          * there is more work to do in this level.
4680                          * Update the drop_progress marker to reflect
4681                          * the work we've done so far, and then bump
4682                          * the slot number
4683                          */
4684                         path->slots[i]++;
4685                         WARN_ON(*level == 0);
4686                         if (max_level == BTRFS_MAX_LEVEL) {
4687                                 btrfs_node_key(path->nodes[i],
4688                                                &root_item->drop_progress,
4689                                                path->slots[i]);
4690                                 root_item->drop_level = i;
4691                         }
4692                         *level = i;
4693                         return 0;
4694                 } else {
4695                         struct extent_buffer *parent;
4696
4697                         /*
4698                          * this whole node is done, free our reference
4699                          * on it and go up one level
4700                          */
4701                         if (path->nodes[*level] == root->node)
4702                                 parent = path->nodes[*level];
4703                         else
4704                                 parent = path->nodes[*level + 1];
4705
4706                         clean_tree_block(trans, root, path->nodes[i]);
4707                         ret = btrfs_free_extent(trans, root,
4708                                                 path->nodes[i]->start,
4709                                                 path->nodes[i]->len,
4710                                                 parent->start,
4711                                                 btrfs_header_owner(parent),
4712                                                 *level, 0);
4713                         BUG_ON(ret);
4714                         if (path->locks[*level]) {
4715                                 btrfs_tree_unlock(path->nodes[i]);
4716                                 path->locks[i] = 0;
4717                         }
4718                         free_extent_buffer(path->nodes[i]);
4719                         path->nodes[i] = NULL;
4720                         *level = i + 1;
4721                 }
4722         }
4723         return 1;
4724 }
4725
4726 /*
4727  * drop the reference count on the tree rooted at 'snap'.  This traverses
4728  * the tree freeing any blocks that have a ref count of zero after being
4729  * decremented.
4730  */
4731 int btrfs_drop_snapshot(struct btrfs_trans_handle *trans, struct btrfs_root
4732                         *root)
4733 {
4734         int ret = 0;
4735         int wret;
4736         int level;
4737         struct btrfs_path *path;
4738         int update_count;
4739         struct btrfs_root_item *root_item = &root->root_item;
4740
4741         path = btrfs_alloc_path();
4742         BUG_ON(!path);
4743
4744         level = btrfs_header_level(root->node);
4745         if (btrfs_disk_key_objectid(&root_item->drop_progress) == 0) {
4746                 path->nodes[level] = btrfs_lock_root_node(root);
4747                 btrfs_set_lock_blocking(path->nodes[level]);
4748                 path->slots[level] = 0;
4749                 path->locks[level] = 1;
4750         } else {
4751                 struct btrfs_key key;
4752                 struct btrfs_disk_key found_key;
4753                 struct extent_buffer *node;
4754
4755                 btrfs_disk_key_to_cpu(&key, &root_item->drop_progress);
4756                 level = root_item->drop_level;
4757                 path->lowest_level = level;
4758                 wret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
4759                 if (wret < 0) {
4760                         ret = wret;
4761                         goto out;
4762                 }
4763                 node = path->nodes[level];
4764                 btrfs_node_key(node, &found_key, path->slots[level]);
4765                 WARN_ON(memcmp(&found_key, &root_item->drop_progress,
4766                                sizeof(found_key)));
4767                 /*
4768                  * unlock our path, this is safe because only this
4769                  * function is allowed to delete this snapshot
4770                  */
4771                 btrfs_unlock_up_safe(path, 0);
4772         }
4773         while (1) {
4774                 unsigned long update;
4775                 wret = walk_down_tree(trans, root, path, &level);
4776                 if (wret > 0)
4777                         break;
4778                 if (wret < 0)
4779                         ret = wret;
4780
4781                 wret = walk_up_tree(trans, root, path, &level,
4782                                     BTRFS_MAX_LEVEL);
4783                 if (wret > 0)
4784                         break;
4785                 if (wret < 0)
4786                         ret = wret;
4787                 if (trans->transaction->in_commit ||
4788                     trans->transaction->delayed_refs.flushing) {
4789                         ret = -EAGAIN;
4790                         break;
4791                 }
4792                 for (update_count = 0; update_count < 16; update_count++) {
4793                         update = trans->delayed_ref_updates;
4794                         trans->delayed_ref_updates = 0;
4795                         if (update)
4796                                 btrfs_run_delayed_refs(trans, root, update);
4797                         else
4798                                 break;
4799                 }
4800         }
4801 out:
4802         btrfs_free_path(path);
4803         return ret;
4804 }
4805
4806 int btrfs_drop_subtree(struct btrfs_trans_handle *trans,
4807                         struct btrfs_root *root,
4808                         struct extent_buffer *node,
4809                         struct extent_buffer *parent)
4810 {
4811         struct btrfs_path *path;
4812         int level;
4813         int parent_level;
4814         int ret = 0;
4815         int wret;
4816
4817         path = btrfs_alloc_path();
4818         BUG_ON(!path);
4819
4820         btrfs_assert_tree_locked(parent);
4821         parent_level = btrfs_header_level(parent);
4822         extent_buffer_get(parent);
4823         path->nodes[parent_level] = parent;
4824         path->slots[parent_level] = btrfs_header_nritems(parent);
4825
4826         btrfs_assert_tree_locked(node);
4827         level = btrfs_header_level(node);
4828         extent_buffer_get(node);
4829         path->nodes[level] = node;
4830         path->slots[level] = 0;
4831
4832         while (1) {
4833                 wret = walk_down_tree(trans, root, path, &level);
4834                 if (wret < 0)
4835                         ret = wret;
4836                 if (wret != 0)
4837                         break;
4838
4839                 wret = walk_up_tree(trans, root, path, &level, parent_level);
4840                 if (wret < 0)
4841                         ret = wret;
4842                 if (wret != 0)
4843                         break;
4844         }
4845
4846         btrfs_free_path(path);
4847         return ret;
4848 }
4849
4850 #if 0
4851 static unsigned long calc_ra(unsigned long start, unsigned long last,
4852                              unsigned long nr)
4853 {
4854         return min(last, start + nr - 1);
4855 }
4856
4857 static noinline int relocate_inode_pages(struct inode *inode, u64 start,
4858                                          u64 len)
4859 {
4860         u64 page_start;
4861         u64 page_end;
4862         unsigned long first_index;
4863         unsigned long last_index;
4864         unsigned long i;
4865         struct page *page;
4866         struct extent_io_tree *io_tree = &BTRFS_I(inode)->io_tree;
4867         struct file_ra_state *ra;
4868         struct btrfs_ordered_extent *ordered;
4869         unsigned int total_read = 0;
4870         unsigned int total_dirty = 0;
4871         int ret = 0;
4872
4873         ra = kzalloc(sizeof(*ra), GFP_NOFS);
4874
4875         mutex_lock(&inode->i_mutex);
4876         first_index = start >> PAGE_CACHE_SHIFT;
4877         last_index = (start + len - 1) >> PAGE_CACHE_SHIFT;
4878
4879         /* make sure the dirty trick played by the caller work */
4880         ret = invalidate_inode_pages2_range(inode->i_mapping,
4881                                             first_index, last_index);
4882         if (ret)
4883                 goto out_unlock;
4884
4885         file_ra_state_init(ra, inode->i_mapping);
4886
4887         for (i = first_index ; i <= last_index; i++) {
4888                 if (total_read % ra->ra_pages == 0) {
4889                         btrfs_force_ra(inode->i_mapping, ra, NULL, i,
4890                                        calc_ra(i, last_index, ra->ra_pages));
4891                 }
4892                 total_read++;
4893 again:
4894                 if (((u64)i << PAGE_CACHE_SHIFT) > i_size_read(inode))
4895                         BUG_ON(1);
4896                 page = grab_cache_page(inode->i_mapping, i);
4897                 if (!page) {
4898                         ret = -ENOMEM;
4899                         goto out_unlock;
4900                 }
4901                 if (!PageUptodate(page)) {
4902                         btrfs_readpage(NULL, page);
4903                         lock_page(page);
4904                         if (!PageUptodate(page)) {
4905                                 unlock_page(page);
4906                                 page_cache_release(page);
4907                                 ret = -EIO;
4908                                 goto out_unlock;
4909                         }
4910                 }
4911                 wait_on_page_writeback(page);
4912
4913                 page_start = (u64)page->index << PAGE_CACHE_SHIFT;
4914                 page_end = page_start + PAGE_CACHE_SIZE - 1;
4915                 lock_extent(io_tree, page_start, page_end, GFP_NOFS);
4916
4917                 ordered = btrfs_lookup_ordered_extent(inode, page_start);
4918                 if (ordered) {
4919                         unlock_extent(io_tree, page_start, page_end, GFP_NOFS);
4920                         unlock_page(page);
4921                         page_cache_release(page);
4922                         btrfs_start_ordered_extent(inode, ordered, 1);
4923                         btrfs_put_ordered_extent(ordered);
4924                         goto again;
4925                 }
4926                 set_page_extent_mapped(page);
4927
4928                 if (i == first_index)
4929                         set_extent_bits(io_tree, page_start, page_end,
4930                                         EXTENT_BOUNDARY, GFP_NOFS);
4931                 btrfs_set_extent_delalloc(inode, page_start, page_end);
4932
4933                 set_page_dirty(page);
4934                 total_dirty++;
4935
4936                 unlock_extent(io_tree, page_start, page_end, GFP_NOFS);
4937                 unlock_page(page);
4938                 page_cache_release(page);
4939         }
4940
4941 out_unlock:
4942         kfree(ra);
4943         mutex_unlock(&inode->i_mutex);
4944         balance_dirty_pages_ratelimited_nr(inode->i_mapping, total_dirty);
4945         return ret;
4946 }
4947
4948 static noinline int relocate_data_extent(struct inode *reloc_inode,
4949                                          struct btrfs_key *extent_key,
4950                                          u64 offset)
4951 {
4952         struct btrfs_root *root = BTRFS_I(reloc_inode)->root;
4953         struct extent_map_tree *em_tree = &BTRFS_I(reloc_inode)->extent_tree;
4954         struct extent_map *em;
4955         u64 start = extent_key->objectid - offset;
4956         u64 end = start + extent_key->offset - 1;
4957
4958         em = alloc_extent_map(GFP_NOFS);
4959         BUG_ON(!em || IS_ERR(em));
4960
4961         em->start = start;
4962         em->len = extent_key->offset;
4963         em->block_len = extent_key->offset;
4964         em->block_start = extent_key->objectid;
4965         em->bdev = root->fs_info->fs_devices->latest_bdev;
4966         set_bit(EXTENT_FLAG_PINNED, &em->flags);
4967
4968         /* setup extent map to cheat btrfs_readpage */
4969         lock_extent(&BTRFS_I(reloc_inode)->io_tree, start, end, GFP_NOFS);
4970         while (1) {
4971                 int ret;
4972                 spin_lock(&em_tree->lock);
4973                 ret = add_extent_mapping(em_tree, em);
4974                 spin_unlock(&em_tree->lock);
4975                 if (ret != -EEXIST) {
4976                         free_extent_map(em);
4977                         break;
4978                 }
4979                 btrfs_drop_extent_cache(reloc_inode, start, end, 0);
4980         }
4981         unlock_extent(&BTRFS_I(reloc_inode)->io_tree, start, end, GFP_NOFS);
4982
4983         return relocate_inode_pages(reloc_inode, start, extent_key->offset);
4984 }
4985
4986 struct btrfs_ref_path {
4987         u64 extent_start;
4988         u64 nodes[BTRFS_MAX_LEVEL];
4989         u64 root_objectid;
4990         u64 root_generation;
4991         u64 owner_objectid;
4992         u32 num_refs;
4993         int lowest_level;
4994         int current_level;
4995         int shared_level;
4996
4997         struct btrfs_key node_keys[BTRFS_MAX_LEVEL];
4998         u64 new_nodes[BTRFS_MAX_LEVEL];
4999 };
5000
5001 struct disk_extent {
5002         u64 ram_bytes;
5003         u64 disk_bytenr;
5004         u64 disk_num_bytes;
5005         u64 offset;
5006         u64 num_bytes;
5007         u8 compression;
5008         u8 encryption;
5009         u16 other_encoding;
5010 };
5011
5012 static int is_cowonly_root(u64 root_objectid)
5013 {
5014         if (root_objectid == BTRFS_ROOT_TREE_OBJECTID ||
5015             root_objectid == BTRFS_EXTENT_TREE_OBJECTID ||
5016             root_objectid == BTRFS_CHUNK_TREE_OBJECTID ||
5017             root_objectid == BTRFS_DEV_TREE_OBJECTID ||
5018             root_objectid == BTRFS_TREE_LOG_OBJECTID ||
5019             root_objectid == BTRFS_CSUM_TREE_OBJECTID)
5020                 return 1;
5021         return 0;
5022 }
5023
5024 static noinline int __next_ref_path(struct btrfs_trans_handle *trans,
5025                                     struct btrfs_root *extent_root,
5026                                     struct btrfs_ref_path *ref_path,
5027                                     int first_time)
5028 {
5029         struct extent_buffer *leaf;
5030         struct btrfs_path *path;
5031         struct btrfs_extent_ref *ref;
5032         struct btrfs_key key;
5033         struct btrfs_key found_key;
5034         u64 bytenr;
5035         u32 nritems;
5036         int level;
5037         int ret = 1;
5038
5039         path = btrfs_alloc_path();
5040         if (!path)
5041                 return -ENOMEM;
5042
5043         if (first_time) {
5044                 ref_path->lowest_level = -1;
5045                 ref_path->current_level = -1;
5046                 ref_path->shared_level = -1;
5047                 goto walk_up;
5048         }
5049 walk_down:
5050         level = ref_path->current_level - 1;
5051         while (level >= -1) {
5052                 u64 parent;
5053                 if (level < ref_path->lowest_level)
5054                         break;
5055
5056                 if (level >= 0)
5057                         bytenr = ref_path->nodes[level];
5058                 else
5059                         bytenr = ref_path->extent_start;
5060                 BUG_ON(bytenr == 0);
5061
5062                 parent = ref_path->nodes[level + 1];
5063                 ref_path->nodes[level + 1] = 0;
5064                 ref_path->current_level = level;
5065                 BUG_ON(parent == 0);
5066
5067                 key.objectid = bytenr;
5068                 key.offset = parent + 1;
5069                 key.type = BTRFS_EXTENT_REF_KEY;
5070
5071                 ret = btrfs_search_slot(trans, extent_root, &key, path, 0, 0);
5072                 if (ret < 0)
5073                         goto out;
5074                 BUG_ON(ret == 0);
5075
5076                 leaf = path->nodes[0];
5077                 nritems = btrfs_header_nritems(leaf);
5078                 if (path->slots[0] >= nritems) {
5079                         ret = btrfs_next_leaf(extent_root, path);
5080                         if (ret < 0)
5081                                 goto out;
5082                         if (ret > 0)
5083                                 goto next;
5084                         leaf = path->nodes[0];
5085                 }
5086
5087                 btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
5088                 if (found_key.objectid == bytenr &&
5089                     found_key.type == BTRFS_EXTENT_REF_KEY) {
5090                         if (level < ref_path->shared_level)
5091                                 ref_path->shared_level = level;
5092                         goto found;
5093                 }
5094 next:
5095                 level--;
5096                 btrfs_release_path(extent_root, path);
5097                 cond_resched();
5098         }
5099         /* reached lowest level */
5100         ret = 1;
5101         goto out;
5102 walk_up:
5103         level = ref_path->current_level;
5104         while (level < BTRFS_MAX_LEVEL - 1) {
5105                 u64 ref_objectid;
5106
5107                 if (level >= 0)
5108                         bytenr = ref_path->nodes[level];
5109                 else
5110                         bytenr = ref_path->extent_start;
5111
5112                 BUG_ON(bytenr == 0);
5113
5114                 key.objectid = bytenr;
5115                 key.offset = 0;
5116                 key.type = BTRFS_EXTENT_REF_KEY;
5117
5118                 ret = btrfs_search_slot(trans, extent_root, &key, path, 0, 0);
5119                 if (ret < 0)
5120                         goto out;
5121
5122                 leaf = path->nodes[0];
5123                 nritems = btrfs_header_nritems(leaf);
5124                 if (path->slots[0] >= nritems) {
5125                         ret = btrfs_next_leaf(extent_root, path);
5126                         if (ret < 0)
5127                                 goto out;
5128                         if (ret > 0) {
5129                                 /* the extent was freed by someone */
5130                                 if (ref_path->lowest_level == level)
5131                                         goto out;
5132                                 btrfs_release_path(extent_root, path);
5133                                 goto walk_down;
5134                         }
5135                         leaf = path->nodes[0];
5136                 }
5137
5138                 btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
5139                 if (found_key.objectid != bytenr ||
5140                                 found_key.type != BTRFS_EXTENT_REF_KEY) {
5141                         /* the extent was freed by someone */
5142                         if (ref_path->lowest_level == level) {
5143                                 ret = 1;
5144                                 goto out;
5145                         }
5146                         btrfs_release_path(extent_root, path);
5147                         goto walk_down;
5148                 }
5149 found:
5150                 ref = btrfs_item_ptr(leaf, path->slots[0],
5151                                 struct btrfs_extent_ref);
5152                 ref_objectid = btrfs_ref_objectid(leaf, ref);
5153                 if (ref_objectid < BTRFS_FIRST_FREE_OBJECTID) {
5154                         if (first_time) {
5155                                 level = (int)ref_objectid;
5156                                 BUG_ON(level >= BTRFS_MAX_LEVEL);
5157                                 ref_path->lowest_level = level;
5158                                 ref_path->current_level = level;
5159                                 ref_path->nodes[level] = bytenr;
5160                         } else {
5161                                 WARN_ON(ref_objectid != level);
5162                         }
5163                 } else {
5164                         WARN_ON(level != -1);
5165                 }
5166                 first_time = 0;
5167
5168                 if (ref_path->lowest_level == level) {
5169                         ref_path->owner_objectid = ref_objectid;
5170                         ref_path->num_refs = btrfs_ref_num_refs(leaf, ref);
5171                 }
5172
5173                 /*
5174                  * the block is tree root or the block isn't in reference
5175                  * counted tree.
5176                  */
5177                 if (found_key.objectid == found_key.offset ||
5178                     is_cowonly_root(btrfs_ref_root(leaf, ref))) {
5179                         ref_path->root_objectid = btrfs_ref_root(leaf, ref);
5180                         ref_path->root_generation =
5181                                 btrfs_ref_generation(leaf, ref);
5182                         if (level < 0) {
5183                                 /* special reference from the tree log */
5184                                 ref_path->nodes[0] = found_key.offset;
5185                                 ref_path->current_level = 0;
5186                         }
5187                         ret = 0;
5188                         goto out;
5189                 }
5190
5191                 level++;
5192                 BUG_ON(ref_path->nodes[level] != 0);
5193                 ref_path->nodes[level] = found_key.offset;
5194                 ref_path->current_level = level;
5195
5196                 /*
5197                  * the reference was created in the running transaction,
5198                  * no need to continue walking up.
5199                  */
5200                 if (btrfs_ref_generation(leaf, ref) == trans->transid) {
5201                         ref_path->root_objectid = btrfs_ref_root(leaf, ref);
5202                         ref_path->root_generation =
5203                                 btrfs_ref_generation(leaf, ref);
5204                         ret = 0;
5205                         goto out;
5206                 }
5207
5208                 btrfs_release_path(extent_root, path);
5209                 cond_resched();
5210         }
5211         /* reached max tree level, but no tree root found. */
5212         BUG();
5213 out:
5214         btrfs_free_path(path);
5215         return ret;
5216 }
5217
5218 static int btrfs_first_ref_path(struct btrfs_trans_handle *trans,
5219                                 struct btrfs_root *extent_root,
5220                                 struct btrfs_ref_path *ref_path,
5221                                 u64 extent_start)
5222 {
5223         memset(ref_path, 0, sizeof(*ref_path));
5224         ref_path->extent_start = extent_start;
5225
5226         return __next_ref_path(trans, extent_root, ref_path, 1);
5227 }
5228
5229 static int btrfs_next_ref_path(struct btrfs_trans_handle *trans,
5230                                struct btrfs_root *extent_root,
5231                                struct btrfs_ref_path *ref_path)
5232 {
5233         return __next_ref_path(trans, extent_root, ref_path, 0);
5234 }
5235
5236 static noinline int get_new_locations(struct inode *reloc_inode,
5237                                       struct btrfs_key *extent_key,
5238                                       u64 offset, int no_fragment,
5239                                       struct disk_extent **extents,
5240                                       int *nr_extents)
5241 {
5242         struct btrfs_root *root = BTRFS_I(reloc_inode)->root;
5243         struct btrfs_path *path;
5244         struct btrfs_file_extent_item *fi;
5245         struct extent_buffer *leaf;
5246         struct disk_extent *exts = *extents;
5247         struct btrfs_key found_key;
5248         u64 cur_pos;
5249         u64 last_byte;
5250         u32 nritems;
5251         int nr = 0;
5252         int max = *nr_extents;
5253         int ret;
5254
5255         WARN_ON(!no_fragment && *extents);
5256         if (!exts) {
5257                 max = 1;
5258                 exts = kmalloc(sizeof(*exts) * max, GFP_NOFS);
5259                 if (!exts)
5260                         return -ENOMEM;
5261         }
5262
5263         path = btrfs_alloc_path();
5264         BUG_ON(!path);
5265
5266         cur_pos = extent_key->objectid - offset;
5267         last_byte = extent_key->objectid + extent_key->offset;
5268         ret = btrfs_lookup_file_extent(NULL, root, path, reloc_inode->i_ino,
5269                                        cur_pos, 0);
5270         if (ret < 0)
5271                 goto out;
5272         if (ret > 0) {
5273                 ret = -ENOENT;
5274                 goto out;
5275         }
5276
5277         while (1) {
5278                 leaf = path->nodes[0];
5279                 nritems = btrfs_header_nritems(leaf);
5280                 if (path->slots[0] >= nritems) {
5281                         ret = btrfs_next_leaf(root, path);
5282                         if (ret < 0)
5283                                 goto out;
5284                         if (ret > 0)
5285                                 break;
5286                         leaf = path->nodes[0];
5287                 }
5288
5289                 btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
5290                 if (found_key.offset != cur_pos ||
5291                     found_key.type != BTRFS_EXTENT_DATA_KEY ||
5292                     found_key.objectid != reloc_inode->i_ino)
5293                         break;
5294
5295                 fi = btrfs_item_ptr(leaf, path->slots[0],
5296                                     struct btrfs_file_extent_item);
5297                 if (btrfs_file_extent_type(leaf, fi) !=
5298                     BTRFS_FILE_EXTENT_REG ||
5299                     btrfs_file_extent_disk_bytenr(leaf, fi) == 0)
5300                         break;
5301
5302                 if (nr == max) {
5303                         struct disk_extent *old = exts;
5304                         max *= 2;
5305                         exts = kzalloc(sizeof(*exts) * max, GFP_NOFS);
5306                         memcpy(exts, old, sizeof(*exts) * nr);
5307                         if (old != *extents)
5308                                 kfree(old);
5309                 }
5310
5311                 exts[nr].disk_bytenr =
5312                         btrfs_file_extent_disk_bytenr(leaf, fi);
5313                 exts[nr].disk_num_bytes =
5314                         btrfs_file_extent_disk_num_bytes(leaf, fi);
5315                 exts[nr].offset = btrfs_file_extent_offset(leaf, fi);
5316                 exts[nr].num_bytes = btrfs_file_extent_num_bytes(leaf, fi);
5317                 exts[nr].ram_bytes = btrfs_file_extent_ram_bytes(leaf, fi);
5318                 exts[nr].compression = btrfs_file_extent_compression(leaf, fi);
5319                 exts[nr].encryption = btrfs_file_extent_encryption(leaf, fi);
5320                 exts[nr].other_encoding = btrfs_file_extent_other_encoding(leaf,
5321                                                                            fi);
5322                 BUG_ON(exts[nr].offset > 0);
5323                 BUG_ON(exts[nr].compression || exts[nr].encryption);
5324                 BUG_ON(exts[nr].num_bytes != exts[nr].disk_num_bytes);
5325
5326                 cur_pos += exts[nr].num_bytes;
5327                 nr++;
5328
5329                 if (cur_pos + offset >= last_byte)
5330                         break;
5331
5332                 if (no_fragment) {
5333                         ret = 1;
5334                         goto out;
5335                 }
5336                 path->slots[0]++;
5337         }
5338
5339         BUG_ON(cur_pos + offset > last_byte);
5340         if (cur_pos + offset < last_byte) {
5341                 ret = -ENOENT;
5342                 goto out;
5343         }
5344         ret = 0;
5345 out:
5346         btrfs_free_path(path);
5347         if (ret) {
5348                 if (exts != *extents)
5349                         kfree(exts);
5350         } else {
5351                 *extents = exts;
5352                 *nr_extents = nr;
5353         }
5354         return ret;
5355 }
5356
5357 static noinline int replace_one_extent(struct btrfs_trans_handle *trans,
5358                                         struct btrfs_root *root,
5359                                         struct btrfs_path *path,
5360                                         struct btrfs_key *extent_key,
5361                                         struct btrfs_key *leaf_key,
5362                                         struct btrfs_ref_path *ref_path,
5363                                         struct disk_extent *new_extents,
5364                                         int nr_extents)
5365 {
5366         struct extent_buffer *leaf;
5367         struct btrfs_file_extent_item *fi;
5368         struct inode *inode = NULL;
5369         struct btrfs_key key;
5370         u64 lock_start = 0;
5371         u64 lock_end = 0;
5372         u64 num_bytes;
5373         u64 ext_offset;
5374         u64 search_end = (u64)-1;
5375         u32 nritems;
5376         int nr_scaned = 0;
5377         int extent_locked = 0;
5378         int extent_type;
5379         int ret;
5380
5381         memcpy(&key, leaf_key, sizeof(key));
5382         if (ref_path->owner_objectid != BTRFS_MULTIPLE_OBJECTIDS) {
5383                 if (key.objectid < ref_path->owner_objectid ||
5384                     (key.objectid == ref_path->owner_objectid &&
5385                      key.type < BTRFS_EXTENT_DATA_KEY)) {
5386                         key.objectid = ref_path->owner_objectid;
5387                         key.type = BTRFS_EXTENT_DATA_KEY;
5388                         key.offset = 0;
5389                 }
5390         }
5391
5392         while (1) {
5393                 ret = btrfs_search_slot(trans, root, &key, path, 0, 1);
5394                 if (ret < 0)
5395                         goto out;
5396
5397                 leaf = path->nodes[0];
5398                 nritems = btrfs_header_nritems(leaf);
5399 next:
5400                 if (extent_locked && ret > 0) {
5401                         /*
5402                          * the file extent item was modified by someone
5403                          * before the extent got locked.
5404                          */
5405                         unlock_extent(&BTRFS_I(inode)->io_tree, lock_start,
5406                                       lock_end, GFP_NOFS);
5407                         extent_locked = 0;
5408                 }
5409
5410                 if (path->slots[0] >= nritems) {
5411                         if (++nr_scaned > 2)
5412                                 break;
5413
5414                         BUG_ON(extent_locked);
5415                         ret = btrfs_next_leaf(root, path);
5416                         if (ret < 0)
5417                                 goto out;
5418                         if (ret > 0)
5419                                 break;
5420                         leaf = path->nodes[0];
5421                         nritems = btrfs_header_nritems(leaf);
5422                 }
5423
5424                 btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);
5425
5426                 if (ref_path->owner_objectid != BTRFS_MULTIPLE_OBJECTIDS) {
5427                         if ((key.objectid > ref_path->owner_objectid) ||
5428                             (key.objectid == ref_path->owner_objectid &&
5429                              key.type > BTRFS_EXTENT_DATA_KEY) ||
5430                             key.offset >= search_end)
5431                                 break;
5432                 }
5433
5434                 if (inode && key.objectid != inode->i_ino) {
5435                         BUG_ON(extent_locked);
5436                         btrfs_release_path(root, path);
5437                         mutex_unlock(&inode->i_mutex);
5438                         iput(inode);
5439                         inode = NULL;
5440                         continue;
5441                 }
5442
5443                 if (key.type != BTRFS_EXTENT_DATA_KEY) {
5444                         path->slots[0]++;
5445                         ret = 1;
5446                         goto next;
5447                 }
5448                 fi = btrfs_item_ptr(leaf, path->slots[0],
5449                                     struct btrfs_file_extent_item);
5450                 extent_type = btrfs_file_extent_type(leaf, fi);
5451                 if ((extent_type != BTRFS_FILE_EXTENT_REG &&
5452                      extent_type != BTRFS_FILE_EXTENT_PREALLOC) ||
5453                     (btrfs_file_extent_disk_bytenr(leaf, fi) !=
5454                      extent_key->objectid)) {
5455                         path->slots[0]++;
5456                         ret = 1;
5457                         goto next;
5458                 }
5459
5460                 num_bytes = btrfs_file_extent_num_bytes(leaf, fi);
5461                 ext_offset = btrfs_file_extent_offset(leaf, fi);
5462
5463                 if (search_end == (u64)-1) {
5464                         search_end = key.offset - ext_offset +
5465                                 btrfs_file_extent_ram_bytes(leaf, fi);
5466                 }
5467
5468                 if (!extent_locked) {
5469                         lock_start = key.offset;
5470                         lock_end = lock_start + num_bytes - 1;
5471                 } else {
5472                         if (lock_start > key.offset ||
5473                             lock_end + 1 < key.offset + num_bytes) {
5474                                 unlock_extent(&BTRFS_I(inode)->io_tree,
5475