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