5 files changed, 142 insertions, 96 deletions

diff --git a/fs/btrfs/ctree.h b/fs/btrfs/ctree.h
index 5517dfc6f71c..83422088c629 100644
--- a/fs/btrfs/ctree.h
+++ b/fs/btrfs/ctree.h
@@ -617,7 +617,7 @@ struct btrfs_leaf_ref_tree {
  * in ram representation of the tree.  extent_root is used for all allocations
  * and for the extent tree extent_root root.
  */
-struct dirty_root;
+struct btrfs_dirty_root;
 struct btrfs_root {
 	struct extent_buffer *node;
 
@@ -627,7 +627,7 @@ struct btrfs_root {
 	struct extent_buffer *commit_root;
 	struct btrfs_leaf_ref_tree *ref_tree;
 	struct btrfs_leaf_ref_tree ref_tree_struct;
-	struct dirty_root *dirty_root;
+	struct btrfs_dirty_root *dirty_root;
 
 	struct btrfs_root_item root_item;
 	struct btrfs_key root_key;
@@ -1399,9 +1399,8 @@ static inline struct dentry *fdentry(struct file *file) {
 }
 
 /* extent-tree.c */
-u32 btrfs_count_snapshots_in_path(struct btrfs_root *root,
-				  struct btrfs_path *count_path,
-				  u64 expected_owner, u64 first_extent);
+int btrfs_cross_ref_exists(struct btrfs_root *root,
+			   struct btrfs_key *key, u64 bytenr);
 int btrfs_extent_post_op(struct btrfs_trans_handle *trans,
 			 struct btrfs_root *root);
 int btrfs_copy_pinned(struct btrfs_root *root, struct extent_io_tree *copy);
diff --git a/fs/btrfs/extent-tree.c b/fs/btrfs/extent-tree.c
index 6290cf41d647..fe1ddbd2bfd6 100644
--- a/fs/btrfs/extent-tree.c
+++ b/fs/btrfs/extent-tree.c
@@ -802,70 +802,57 @@ out:
 	return 0;
 }
 
-u32 btrfs_count_snapshots_in_path(struct btrfs_root *root,
-				  struct btrfs_path *count_path,
-				  u64 expected_owner,
-				  u64 first_extent)
+
+static int get_reference_status(struct btrfs_root *root, u64 bytenr,
+				u64 parent_gen, u64 ref_objectid,
+			        u64 *min_generation, u32 *ref_count)
 {
 	struct btrfs_root *extent_root = root->fs_info->extent_root;
 	struct btrfs_path *path;
-	u64 bytenr;
-	u64 found_objectid;
-	u64 found_owner;
+	struct extent_buffer *leaf;
+	struct btrfs_extent_ref *ref_item;
+	struct btrfs_key key;
+	struct btrfs_key found_key;
 	u64 root_objectid = root->root_key.objectid;
-	u32 total_count = 0;
-	u32 extent_refs;
-	u32 cur_count;
+	u64 ref_generation;
 	u32 nritems;
 	int ret;
-	struct btrfs_key key;
-	struct btrfs_key found_key;
-	struct extent_buffer *l;
-	struct btrfs_extent_item *item;
-	struct btrfs_extent_ref *ref_item;
-	int level = -1;
 
-	/* FIXME, needs locking */
-	BUG();
-
-	mutex_lock(&root->fs_info->alloc_mutex);
-	path = btrfs_alloc_path();
-again:
-	if (level == -1)
-		bytenr = first_extent;
-	else
-		bytenr = count_path->nodes[level]->start;
-
-	cur_count = 0;
 	key.objectid = bytenr;
 	key.offset = 0;
+	key.type = BTRFS_EXTENT_ITEM_KEY;
 
-	btrfs_set_key_type(&key, BTRFS_EXTENT_ITEM_KEY);
+	path = btrfs_alloc_path();
+	mutex_lock(&root->fs_info->alloc_mutex);
 	ret = btrfs_search_slot(NULL, extent_root, &key, path, 0, 0);
 	if (ret < 0)
 		goto out;
 	BUG_ON(ret == 0);
 
-	l = path->nodes[0];
-	btrfs_item_key_to_cpu(l, &found_key, path->slots[0]);
+	leaf = path->nodes[0];
+	btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
 
 	if (found_key.objectid != bytenr ||
 	    found_key.type != BTRFS_EXTENT_ITEM_KEY) {
+		ret = 1;
 		goto out;
 	}
 
-	item = btrfs_item_ptr(l, path->slots[0], struct btrfs_extent_item);
-	extent_refs = btrfs_extent_refs(l, item);
+	*ref_count = 0;
+	*min_generation = (u64)-1;
+
 	while (1) {
-		l = path->nodes[0];
-		nritems = btrfs_header_nritems(l);
+		leaf = path->nodes[0];
+		nritems = btrfs_header_nritems(leaf);
 		if (path->slots[0] >= nritems) {
 			ret = btrfs_next_leaf(extent_root, path);
+			if (ret < 0)
+				goto out;
 			if (ret == 0)
 				continue;
 			break;
 		}
-		btrfs_item_key_to_cpu(l, &found_key, path->slots[0]);
+		btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
 		if (found_key.objectid != bytenr)
 			break;
 
@@ -874,57 +861,120 @@ again:
 			continue;
 		}
 
-		cur_count++;
-		ref_item = btrfs_item_ptr(l, path->slots[0],
+		ref_item = btrfs_item_ptr(leaf, path->slots[0],
 					  struct btrfs_extent_ref);
-		found_objectid = btrfs_ref_root(l, ref_item);
-
-		if (found_objectid != root_objectid) {
-			total_count = 2;
-			goto out;
-		}
-		if (level == -1) {
-			found_owner = btrfs_ref_objectid(l, ref_item);
-			if (found_owner != expected_owner) {
-				total_count = 2;
-				goto out;
-			}
-			/*
-			 * nasty.  we don't count a reference held by
-			 * the running transaction.  This allows nodatacow
-			 * to avoid cow most of the time
-			 */
-			if (found_owner >= BTRFS_FIRST_FREE_OBJECTID &&
-			    btrfs_ref_generation(l, ref_item) ==
-			    root->fs_info->generation) {
-				extent_refs--;
-			}
+		ref_generation = btrfs_ref_generation(leaf, ref_item);
+		/*
+		 * For (parent_gen > 0 && parent_gen > ref_gen):
+		 *
+		 * we reach here through the oldest root, therefore 
+		 * all other reference from same snapshot should have 
+		 * a larger generation.
+		 */
+		if ((root_objectid != btrfs_ref_root(leaf, ref_item)) ||
+		    (parent_gen > 0 && parent_gen > ref_generation) ||
+		    (ref_objectid >= BTRFS_FIRST_FREE_OBJECTID &&
+		     ref_objectid != btrfs_ref_objectid(leaf, ref_item))) {
+			if (ref_count)
+				*ref_count = 2;
+			break;
 		}
-		total_count = 1;
+
+		*ref_count = 1;
+		if (*min_generation > ref_generation)
+			*min_generation = ref_generation;
+
 		path->slots[0]++;
 	}
-	/*
-	 * if there is more than one reference against a data extent,
-	 * we have to assume the other ref is another snapshot
-	 */
-	if (level == -1 && extent_refs > 1) {
-		total_count = 2;
+	ret = 0;
+out:
+	mutex_unlock(&root->fs_info->alloc_mutex);
+	btrfs_free_path(path);
+	return ret;
+}
+
+int btrfs_cross_ref_exists(struct btrfs_root *root,
+			   struct btrfs_key *key, u64 bytenr)
+{
+	struct btrfs_trans_handle *trans;
+	struct btrfs_root *old_root;
+	struct btrfs_path *path = NULL;
+	struct extent_buffer *eb;
+	struct btrfs_file_extent_item *item;
+	u64 ref_generation;
+	u64 min_generation;
+	u64 extent_start;
+	u32 ref_count;
+	int level;
+	int ret;
+
+	BUG_ON(key->type != BTRFS_EXTENT_DATA_KEY);
+	ret = get_reference_status(root, bytenr, 0, key->objectid,
+				   &min_generation, &ref_count);
+	if (ret)
+		return ret;
+
+	if (ref_count != 1)
+		return 1;
+
+	trans = btrfs_start_transaction(root, 0);
+	old_root = root->dirty_root->root;
+	ref_generation = old_root->root_key.offset;
+
+	/* all references are created in running transaction */
+	if (min_generation > ref_generation) {
+		ret = 0;
 		goto out;
 	}
-	if (cur_count == 0) {
-		total_count = 0;
+
+	path = btrfs_alloc_path();
+	if (!path) {
+		ret = -ENOMEM;
 		goto out;
 	}
-	if (level >= 0 && root->node == count_path->nodes[level])
+
+	path->skip_locking = 1;
+	/* if no item found, the extent is referenced by other snapshot */
+	ret = btrfs_search_slot(NULL, old_root, key, path, 0, 0);
+	if (ret)
 		goto out;
-	level++;
-	btrfs_release_path(root, path);
-	goto again;
 
+	eb = path->nodes[0];
+	item = btrfs_item_ptr(eb, path->slots[0],
+			      struct btrfs_file_extent_item);
+	if (btrfs_file_extent_type(eb, item) != BTRFS_FILE_EXTENT_REG ||
+	    btrfs_file_extent_disk_bytenr(eb, item) != bytenr) {
+		ret = 1;
+		goto out;
+	}
+
+	for (level = BTRFS_MAX_LEVEL - 1; level >= -1; level--) {
+		if (level >= 0) {
+			eb = path->nodes[level];
+			if (!eb)
+				continue;
+			extent_start = eb->start;
+		} else 
+			extent_start = bytenr;
+
+		ret = get_reference_status(root, extent_start, ref_generation,
+					   0, &min_generation, &ref_count);
+		if (ret)
+			goto out;
+
+		if (ref_count != 1) {
+			ret = 1;
+			goto out;
+		}
+		if (level >= 0)
+			ref_generation = btrfs_header_generation(eb);
+	}
+	ret = 0;
 out:
-	btrfs_free_path(path);
-	mutex_unlock(&root->fs_info->alloc_mutex);
-	return total_count;
+	if (path)
+		btrfs_free_path(path);
+	btrfs_end_transaction(trans, root);
+	return ret;
 }
 
 int btrfs_inc_ref(struct btrfs_trans_handle *trans, struct btrfs_root *root,
diff --git a/fs/btrfs/inode.c b/fs/btrfs/inode.c
index 7c87f863d6f7..3aa82cec6bf7 100644
--- a/fs/btrfs/inode.c
+++ b/fs/btrfs/inode.c
@@ -249,11 +249,8 @@ again:
 		if (bytenr == 0)
 			goto not_found;
 
-		if (btrfs_count_snapshots_in_path(root, path, inode->i_ino,
-						  bytenr) != 1) {
+		if (btrfs_cross_ref_exists(root, &found_key, bytenr))
 			goto not_found;
-		}
-
 		/*
 		 * we may be called by the resizer, make sure we're inside
 		 * the limits of the FS
@@ -277,6 +274,7 @@ loop:
 	goto again;
 
 not_found:
+	btrfs_release_path(root, path);
 	cow_file_range(inode, start, end);
 	start = end + 1;
 	goto loop;
diff --git a/fs/btrfs/transaction.c b/fs/btrfs/transaction.c
index b8be6703189a..216f31571620 100644
--- a/fs/btrfs/transaction.c
+++ b/fs/btrfs/transaction.c
@@ -32,12 +32,6 @@ extern struct kmem_cache *btrfs_transaction_cachep;
 
 #define BTRFS_ROOT_TRANS_TAG 0
 
-struct dirty_root {
-	struct list_head list;
-	struct btrfs_root *root;
-	struct btrfs_root *latest_root;
-};
-
 static noinline void put_transaction(struct btrfs_transaction *transaction)
 {
 	WARN_ON(transaction->use_count == 0);
@@ -91,7 +85,7 @@ static noinline int join_transaction(struct btrfs_root *root)
 
 static noinline int record_root_in_trans(struct btrfs_root *root)
 {
-	struct dirty_root *dirty;
+	struct btrfs_dirty_root *dirty;
 	u64 running_trans_id = root->fs_info->running_transaction->transid;
 	if (root->ref_cows && root->last_trans < running_trans_id) {
 		WARN_ON(root == root->fs_info->extent_root);
@@ -372,7 +366,7 @@ int btrfs_add_dead_root(struct btrfs_root *root,
 			struct btrfs_root *latest,
 			struct list_head *dead_list)
 {
-	struct dirty_root *dirty;
+	struct btrfs_dirty_root *dirty;
 
 	dirty = kmalloc(sizeof(*dirty), GFP_NOFS);
 	if (!dirty)
@@ -387,7 +381,7 @@ static noinline int add_dirty_roots(struct btrfs_trans_handle *trans,
 				    struct radix_tree_root *radix,
 				    struct list_head *list)
 {
-	struct dirty_root *dirty;
+	struct btrfs_dirty_root *dirty;
 	struct btrfs_root *gang[8];
 	struct btrfs_root *root;
 	int i;
@@ -498,7 +492,7 @@ int btrfs_defrag_root(struct btrfs_root *root, int cacheonly)
 static noinline int drop_dirty_roots(struct btrfs_root *tree_root,
 				     struct list_head *list)
 {
-	struct dirty_root *dirty;
+	struct btrfs_dirty_root *dirty;
 	struct btrfs_trans_handle *trans;
 	unsigned long nr;
 	u64 num_bytes;
@@ -509,7 +503,7 @@ static noinline int drop_dirty_roots(struct btrfs_root *tree_root,
 	while(!list_empty(list)) {
 		struct btrfs_root *root;
 
-		dirty = list_entry(list->prev, struct dirty_root, list);
+		dirty = list_entry(list->prev, struct btrfs_dirty_root, list);
 		list_del_init(&dirty->list);
 
 		num_bytes = btrfs_root_used(&dirty->root->root_item);
diff --git a/fs/btrfs/transaction.h b/fs/btrfs/transaction.h
index df2ca2aad1c0..f5adb23151fb 100644
--- a/fs/btrfs/transaction.h
+++ b/fs/btrfs/transaction.h
@@ -52,6 +52,11 @@ struct btrfs_pending_snapshot {
 	struct list_head list;
 };
 
+struct btrfs_dirty_root {
+	struct list_head list;
+	struct btrfs_root *root;
+	struct btrfs_root *latest_root;
+};
 
 static inline void btrfs_set_trans_block_group(struct btrfs_trans_handle *trans,
 					       struct inode *inode)