Btrfs: Add back pointers from extents to the btree or file referencing them

Signed-off-by: Chris Mason <chris.mason@oracle.com>

8 files changed, 577 insertions, 105 deletions

diff --git a/fs/btrfs/ctree.c b/fs/btrfs/ctree.c
index 5697705f7530..fd8233e05cf4 100644
--- a/fs/btrfs/ctree.c
+++ b/fs/btrfs/ctree.c
@@ -77,13 +77,37 @@ static int __btrfs_cow_block(struct btrfs_trans_handle *trans,
 			     struct extent_buffer **cow_ret,
 			     u64 search_start, u64 empty_size)
 {
+	u64 root_gen;
 	struct extent_buffer *cow;
+	u32 nritems;
 	int ret = 0;
 	int different_trans = 0;
+	int level;
+	struct btrfs_key first_key;
+
+	if (root->ref_cows) {
+		root_gen = trans->transid;
+	} else {
+		root_gen = 0;
+	}
 
+	WARN_ON(root->ref_cows && trans->transid !=
+		root->fs_info->running_transaction->transid);
 	WARN_ON(root->ref_cows && trans->transid != root->last_trans);
 
-	cow = btrfs_alloc_free_block(trans, root, buf->len,
+	level = btrfs_header_level(buf);
+	nritems = btrfs_header_nritems(buf);
+	if (nritems) {
+		if (level == 0)
+			btrfs_item_key_to_cpu(buf, &first_key, 0);
+		else
+			btrfs_node_key_to_cpu(buf, &first_key, 0);
+	} else {
+		first_key.objectid = 0;
+	}
+	cow = __btrfs_alloc_free_block(trans, root, buf->len,
+				     root->root_key.objectid,
+				     root_gen, first_key.objectid, level,
 				     search_start, empty_size);
 	if (IS_ERR(cow))
 		return PTR_ERR(cow);
@@ -104,14 +128,17 @@ static int __btrfs_cow_block(struct btrfs_trans_handle *trans,
 	}
 
 	if (buf == root->node) {
+		root_gen = btrfs_header_generation(buf);
 		root->node = cow;
 		extent_buffer_get(cow);
 		if (buf != root->commit_root) {
 			btrfs_free_extent(trans, root, buf->start,
-					  buf->len, 1);
+					  buf->len, root->root_key.objectid,
+					  root_gen, 0, 0, 1);
 		}
 		free_extent_buffer(buf);
 	} else {
+		root_gen = btrfs_header_generation(parent);
 		btrfs_set_node_blockptr(parent, parent_slot,
 					cow->start);
 		WARN_ON(trans->transid == 0);
@@ -119,7 +146,9 @@ static int __btrfs_cow_block(struct btrfs_trans_handle *trans,
 					      trans->transid);
 		btrfs_mark_buffer_dirty(parent);
 		WARN_ON(btrfs_header_generation(parent) != trans->transid);
-		btrfs_free_extent(trans, root, buf->start, buf->len, 1);
+		btrfs_free_extent(trans, root, buf->start, buf->len,
+				  btrfs_header_owner(parent), root_gen,
+				  0, 0, 1);
 	}
 	free_extent_buffer(buf);
 	btrfs_mark_buffer_dirty(cow);
@@ -606,6 +635,8 @@ static int balance_level(struct btrfs_trans_handle *trans, struct btrfs_root
 		return 0;
 
 	mid = path->nodes[level];
+	WARN_ON(btrfs_header_generation(mid) != trans->transid);
+
 	orig_ptr = btrfs_node_blockptr(mid, orig_slot);
 
 	if (level < BTRFS_MAX_LEVEL - 1)
@@ -631,7 +662,9 @@ static int balance_level(struct btrfs_trans_handle *trans, struct btrfs_root
 		wait_on_tree_block_writeback(root, mid);
 		/* once for the path */
 		free_extent_buffer(mid);
-		ret = btrfs_free_extent(trans, root, mid->start, mid->len, 1);
+		ret = btrfs_free_extent(trans, root, mid->start, mid->len,
+					root->root_key.objectid,
+					btrfs_header_generation(mid), 0, 0, 1);
 		/* once for the root ptr */
 		free_extent_buffer(mid);
 		return ret;
@@ -681,6 +714,7 @@ static int balance_level(struct btrfs_trans_handle *trans, struct btrfs_root
 			ret = wret;
 		if (btrfs_header_nritems(right) == 0) {
 			u64 bytenr = right->start;
+			u64 generation = btrfs_header_generation(parent);
 			u32 blocksize = right->len;
 
 			clean_tree_block(trans, root, right);
@@ -692,7 +726,9 @@ static int balance_level(struct btrfs_trans_handle *trans, struct btrfs_root
 			if (wret)
 				ret = wret;
 			wret = btrfs_free_extent(trans, root, bytenr,
-						 blocksize, 1);
+						 blocksize,
+						 btrfs_header_owner(parent),
+						 generation, 0, 0, 1);
 			if (wret)
 				ret = wret;
 		} else {
@@ -722,6 +758,7 @@ static int balance_level(struct btrfs_trans_handle *trans, struct btrfs_root
 	}
 	if (btrfs_header_nritems(mid) == 0) {
 		/* we've managed to empty the middle node, drop it */
+		u64 root_gen = btrfs_header_generation(parent);
 		u64 bytenr = mid->start;
 		u32 blocksize = mid->len;
 		clean_tree_block(trans, root, mid);
@@ -731,7 +768,9 @@ static int balance_level(struct btrfs_trans_handle *trans, struct btrfs_root
 		wret = del_ptr(trans, root, path, level + 1, pslot);
 		if (wret)
 			ret = wret;
-		wret = btrfs_free_extent(trans, root, bytenr, blocksize, 1);
+		wret = btrfs_free_extent(trans, root, bytenr, blocksize,
+					 btrfs_header_owner(parent),
+					 root_gen, 0, 0, 1);
 		if (wret)
 			ret = wret;
 	} else {
@@ -788,6 +827,7 @@ static int push_nodes_for_insert(struct btrfs_trans_handle *trans,
 		return 1;
 
 	mid = path->nodes[level];
+	WARN_ON(btrfs_header_generation(mid) != trans->transid);
 	orig_ptr = btrfs_node_blockptr(mid, orig_slot);
 
 	if (level < BTRFS_MAX_LEVEL - 1)
@@ -1113,6 +1153,8 @@ static int push_node_left(struct btrfs_trans_handle *trans, struct btrfs_root
 	src_nritems = btrfs_header_nritems(src);
 	dst_nritems = btrfs_header_nritems(dst);
 	push_items = BTRFS_NODEPTRS_PER_BLOCK(root) - dst_nritems;
+	WARN_ON(btrfs_header_generation(src) != trans->transid);
+	WARN_ON(btrfs_header_generation(dst) != trans->transid);
 
 	if (push_items <= 0) {
 		return 1;
@@ -1159,6 +1201,9 @@ static int balance_node_right(struct btrfs_trans_handle *trans,
 	int dst_nritems;
 	int ret = 0;
 
+	WARN_ON(btrfs_header_generation(src) != trans->transid);
+	WARN_ON(btrfs_header_generation(dst) != trans->transid);
+
 	src_nritems = btrfs_header_nritems(src);
 	dst_nritems = btrfs_header_nritems(dst);
 	push_items = BTRFS_NODEPTRS_PER_BLOCK(root) - dst_nritems;
@@ -1202,6 +1247,8 @@ static int insert_new_root(struct btrfs_trans_handle *trans,
 			   struct btrfs_root *root,
 			   struct btrfs_path *path, int level)
 {
+	u64 root_gen;
+	u64 lower_gen;
 	struct extent_buffer *lower;
 	struct extent_buffer *c;
 	struct btrfs_disk_key lower_key;
@@ -1209,7 +1256,20 @@ static int insert_new_root(struct btrfs_trans_handle *trans,
 	BUG_ON(path->nodes[level]);
 	BUG_ON(path->nodes[level-1] != root->node);
 
-	c = btrfs_alloc_free_block(trans, root, root->nodesize,
+	if (root->ref_cows)
+		root_gen = trans->transid;
+	else
+		root_gen = 0;
+
+	lower = path->nodes[level-1];
+	if (level == 1)
+		btrfs_item_key(lower, &lower_key, 0);
+	else
+		btrfs_node_key(lower, &lower_key, 0);
+
+	c = __btrfs_alloc_free_block(trans, root, root->nodesize,
+				   root->root_key.objectid,
+				   root_gen, lower_key.objectid, level,
 				   root->node->start, 0);
 	if (IS_ERR(c))
 		return PTR_ERR(c);
@@ -1219,19 +1279,16 @@ static int insert_new_root(struct btrfs_trans_handle *trans,
 	btrfs_set_header_bytenr(c, c->start);
 	btrfs_set_header_generation(c, trans->transid);
 	btrfs_set_header_owner(c, root->root_key.objectid);
-	lower = path->nodes[level-1];
 
 	write_extent_buffer(c, root->fs_info->fsid,
 			    (unsigned long)btrfs_header_fsid(c),
 			    BTRFS_FSID_SIZE);
-	if (level == 1)
-		btrfs_item_key(lower, &lower_key, 0);
-	else
-		btrfs_node_key(lower, &lower_key, 0);
 	btrfs_set_node_key(c, &lower_key, 0);
 	btrfs_set_node_blockptr(c, 0, lower->start);
-	WARN_ON(btrfs_header_generation(lower) == 0);
-	btrfs_set_node_ptr_generation(c, 0, btrfs_header_generation(lower));
+	lower_gen = btrfs_header_generation(lower);
+	WARN_ON(lower_gen == 0);
+
+	btrfs_set_node_ptr_generation(c, 0, lower_gen);
 
 	btrfs_mark_buffer_dirty(c);
 
@@ -1241,6 +1298,18 @@ static int insert_new_root(struct btrfs_trans_handle *trans,
 	extent_buffer_get(c);
 	path->nodes[level] = c;
 	path->slots[level] = 0;
+
+	if (root->ref_cows && lower_gen != trans->transid) {
+		struct btrfs_path *back_path = btrfs_alloc_path();
+		int ret;
+		ret = btrfs_insert_extent_backref(trans,
+						  root->fs_info->extent_root,
+						  path, lower->start,
+						  root->root_key.objectid,
+						  trans->transid, 0, 0);
+		BUG_ON(ret);
+		btrfs_free_path(back_path);
+	}
 	return 0;
 }
 
@@ -1294,6 +1363,7 @@ static int insert_ptr(struct btrfs_trans_handle *trans, struct btrfs_root
 static int split_node(struct btrfs_trans_handle *trans, struct btrfs_root
 		      *root, struct btrfs_path *path, int level)
 {
+	u64 root_gen;
 	struct extent_buffer *c;
 	struct extent_buffer *split;
 	struct btrfs_disk_key disk_key;
@@ -1303,6 +1373,7 @@ static int split_node(struct btrfs_trans_handle *trans, struct btrfs_root
 	u32 c_nritems;
 
 	c = path->nodes[level];
+	WARN_ON(btrfs_header_generation(c) != trans->transid);
 	if (c == root->node) {
 		/* trying to split the root, lets make a new one */
 		ret = insert_new_root(trans, root, path, level + 1);
@@ -1319,8 +1390,17 @@ static int split_node(struct btrfs_trans_handle *trans, struct btrfs_root
 	}
 
 	c_nritems = btrfs_header_nritems(c);
-	split = btrfs_alloc_free_block(trans, root, root->nodesize,
-				       c->start, 0);
+	if (root->ref_cows)
+		root_gen = trans->transid;
+	else
+		root_gen = 0;
+
+	btrfs_node_key(c, &disk_key, 0);
+	split = __btrfs_alloc_free_block(trans, root, root->nodesize,
+					 root->root_key.objectid,
+					 root_gen,
+					 btrfs_disk_key_objectid(&disk_key),
+					 level, c->start, 0);
 	if (IS_ERR(split))
 		return PTR_ERR(split);
 
@@ -1789,6 +1869,7 @@ static int split_leaf(struct btrfs_trans_handle *trans, struct btrfs_root
 		      *root, struct btrfs_key *ins_key,
 		      struct btrfs_path *path, int data_size, int extend)
 {
+	u64 root_gen;
 	struct extent_buffer *l;
 	u32 nritems;
 	int mid;
@@ -1807,6 +1888,11 @@ static int split_leaf(struct btrfs_trans_handle *trans, struct btrfs_root
 	if (extend)
 		space_needed = data_size;
 
+	if (root->ref_cows)
+		root_gen = trans->transid;
+	else
+		root_gen = 0;
+
 	/* first try to make some room by pushing left and right */
 	if (ins_key->type != BTRFS_DIR_ITEM_KEY) {
 		wret = push_leaf_right(trans, root, path, data_size, 0);
@@ -1837,8 +1923,12 @@ again:
 	nritems = btrfs_header_nritems(l);
 	mid = (nritems + 1)/ 2;
 
-	right = btrfs_alloc_free_block(trans, root, root->leafsize,
-				       l->start, 0);
+	btrfs_item_key(l, &disk_key, 0);
+
+	right = __btrfs_alloc_free_block(trans, root, root->leafsize,
+					 root->root_key.objectid,
+					 root_gen, disk_key.objectid, 0,
+					 l->start, 0);
 	if (IS_ERR(right))
 		return PTR_ERR(right);
 
@@ -2413,13 +2503,16 @@ int btrfs_del_item(struct btrfs_trans_handle *trans, struct btrfs_root *root,
 		if (leaf == root->node) {
 			btrfs_set_header_level(leaf, 0);
 		} else {
+			u64 root_gen = btrfs_header_generation(path->nodes[1]);
 			clean_tree_block(trans, root, leaf);
 			wait_on_tree_block_writeback(root, leaf);
 			wret = del_ptr(trans, root, path, 1, path->slots[1]);
 			if (wret)
 				ret = wret;
 			wret = btrfs_free_extent(trans, root,
-						 leaf->start, leaf->len, 1);
+					 leaf->start, leaf->len,
+					 btrfs_header_owner(path->nodes[1]),
+					 root_gen, 0, 0, 1);
 			if (wret)
 				ret = wret;
 		}
@@ -2456,9 +2549,13 @@ int btrfs_del_item(struct btrfs_trans_handle *trans, struct btrfs_root *root,
 			}
 
 			if (btrfs_header_nritems(leaf) == 0) {
+				u64 root_gen;
 				u64 bytenr = leaf->start;
 				u32 blocksize = leaf->len;
 
+				root_gen = btrfs_header_generation(
+							   path->nodes[1]);
+
 				clean_tree_block(trans, root, leaf);
 				wait_on_tree_block_writeback(root, leaf);
 
@@ -2468,7 +2565,9 @@ int btrfs_del_item(struct btrfs_trans_handle *trans, struct btrfs_root *root,
 
 				free_extent_buffer(leaf);
 				wret = btrfs_free_extent(trans, root, bytenr,
-							 blocksize, 1);
+					     blocksize,
+					     btrfs_header_owner(path->nodes[1]),
+					     root_gen, 0, 0, 1);
 				if (wret)
 					ret = wret;
 			} else {
@@ -2483,6 +2582,61 @@ int btrfs_del_item(struct btrfs_trans_handle *trans, struct btrfs_root *root,
 }
 
 /*
+ * walk up the tree as far as required to find the previous leaf.
+ * returns 0 if it found something or 1 if there are no lesser leaves.
+ * returns < 0 on io errors.
+ */
+int btrfs_prev_leaf(struct btrfs_root *root, struct btrfs_path *path)
+{
+	int slot;
+	int level = 1;
+	u64 bytenr;
+	struct extent_buffer *c;
+	struct extent_buffer *next = NULL;
+
+	while(level < BTRFS_MAX_LEVEL) {
+		if (!path->nodes[level])
+			return 1;
+
+		slot = path->slots[level];
+		c = path->nodes[level];
+		if (slot == 0) {
+			level++;
+			if (level == BTRFS_MAX_LEVEL)
+				return 1;
+			continue;
+		}
+		slot--;
+
+		bytenr = btrfs_node_blockptr(c, slot);
+		if (next)
+			free_extent_buffer(next);
+
+		if (path->reada < 0)
+			reada_for_search(root, path, level, slot);
+
+		next = read_tree_block(root, bytenr,
+				       btrfs_level_size(root, level - 1));
+		break;
+	}
+	path->slots[level] = slot;
+	while(1) {
+		level--;
+		c = path->nodes[level];
+		free_extent_buffer(c);
+		path->nodes[level] = next;
+		path->slots[level] = 0;
+		if (!level)
+			break;
+		if (path->reada)
+			reada_for_search(root, path, level, 0);
+		next = read_tree_block(root, btrfs_node_blockptr(next, 0),
+				       btrfs_level_size(root, level - 1));
+	}
+	return 0;
+}
+
+/*
  * walk up the tree as far as required to find the next leaf.
  * returns 0 if it found something or 1 if there are no greater leaves.
  * returns < 0 on io errors.
@@ -2503,6 +2657,8 @@ int btrfs_next_leaf(struct btrfs_root *root, struct btrfs_path *path)
 		c = path->nodes[level];
 		if (slot >= btrfs_header_nritems(c)) {
 			level++;
+			if (level == BTRFS_MAX_LEVEL)
+				return 1;
 			continue;
 		}
 
diff --git a/fs/btrfs/ctree.h b/fs/btrfs/ctree.h
index fd58dd846e61..cb1b156d954e 100644
--- a/fs/btrfs/ctree.h
+++ b/fs/btrfs/ctree.h
@@ -544,11 +544,12 @@ BTRFS_SETGET_FUNCS(ref_generation, struct btrfs_extent_ref, generation, 64);
 BTRFS_SETGET_FUNCS(ref_objectid, struct btrfs_extent_ref, objectid, 64);
 BTRFS_SETGET_FUNCS(ref_offset, struct btrfs_extent_ref, offset, 64);
 
-BTRFS_SETGET_STACK_FUNCS(ref_root, struct btrfs_extent_ref, root, 64);
-BTRFS_SETGET_STACK_FUNCS(ref_generation, struct btrfs_extent_ref,
+BTRFS_SETGET_STACK_FUNCS(stack_ref_root, struct btrfs_extent_ref, root, 64);
+BTRFS_SETGET_STACK_FUNCS(stack_ref_generation, struct btrfs_extent_ref,
 			 generation, 64);
-BTRFS_SETGET_STACK_FUNCS(ref_objectid, struct btrfs_extent_ref, objectid, 64);
-BTRFS_SETGET_STACK_FUNCS(ref_offset, struct btrfs_extent_ref, offset, 64);
+BTRFS_SETGET_STACK_FUNCS(stack_ref_objectid, struct btrfs_extent_ref,
+			 objectid, 64);
+BTRFS_SETGET_STACK_FUNCS(stack_ref_offset, struct btrfs_extent_ref, offset, 64);
 
 BTRFS_SETGET_STACK_FUNCS(stack_extent_refs, struct btrfs_extent_item,
 			 refs, 32);
@@ -914,24 +915,45 @@ struct btrfs_block_group_cache *btrfs_find_block_group(struct btrfs_root *root,
 						 *hint, u64 search_start,
 						 int data, int owner);
 int btrfs_inc_root_ref(struct btrfs_trans_handle *trans,
-		       struct btrfs_root *root);
+		       struct btrfs_root *root, u64 owner_objectid);
 struct extent_buffer *btrfs_alloc_free_block(struct btrfs_trans_handle *trans,
 					    struct btrfs_root *root, u32 size,
+					    u64 root_objectid,
 					    u64 hint, u64 empty_size);
+struct extent_buffer *__btrfs_alloc_free_block(struct btrfs_trans_handle *trans,
+					     struct btrfs_root *root,
+					     u32 blocksize,
+					     u64 root_objectid,
+					     u64 ref_generation,
+					     u64 first_objectid,
+					     int level,
+					     u64 hint,
+					     u64 empty_size);
+int btrfs_insert_extent_backref(struct btrfs_trans_handle *trans,
+				 struct btrfs_root *root,
+				 struct btrfs_path *path, u64 bytenr,
+				 u64 root_objectid, u64 ref_generation,
+				 u64 owner, u64 owner_offset);
 int btrfs_alloc_extent(struct btrfs_trans_handle *trans,
-		       struct btrfs_root *root, u64 owner,
-		       u64 num_bytes, u64 empty_size, u64 search_start,
+		       struct btrfs_root *root,
+		       u64 num_bytes, u64 root_objectid, u64 ref_generation,
+		       u64 owner, u64 owner_offset,
+		       u64 empty_size, u64 hint_byte,
 		       u64 search_end, struct btrfs_key *ins, int data);
 int btrfs_inc_ref(struct btrfs_trans_handle *trans, struct btrfs_root *root,
 		  struct extent_buffer *buf);
 int btrfs_free_extent(struct btrfs_trans_handle *trans, struct btrfs_root
-		      *root, u64 bytenr, u64 num_bytes, int pin);
+		      *root, u64 bytenr, u64 num_bytes,
+		      u64 root_objectid, u64 ref_generation,
+		      u64 owner_objectid, u64 owner_offset, int pin);
 int btrfs_finish_extent_commit(struct btrfs_trans_handle *trans,
 			       struct btrfs_root *root,
 			       struct extent_map_tree *unpin);
 int btrfs_inc_extent_ref(struct btrfs_trans_handle *trans,
 				struct btrfs_root *root,
-				u64 bytenr, u64 num_bytes);
+				u64 bytenr, u64 num_bytes,
+				u64 root_objectid, u64 ref_generation,
+				u64 owner, u64 owner_offset);
 int btrfs_write_dirty_block_groups(struct btrfs_trans_handle *trans,
 				    struct btrfs_root *root);
 int btrfs_free_block_groups(struct btrfs_fs_info *info);
@@ -966,6 +988,7 @@ int btrfs_insert_empty_item(struct btrfs_trans_handle *trans, struct btrfs_root
 			    *root, struct btrfs_path *path, struct btrfs_key
 			    *cpu_key, u32 data_size);
 int btrfs_next_leaf(struct btrfs_root *root, struct btrfs_path *path);
+int btrfs_prev_leaf(struct btrfs_root *root, struct btrfs_path *path);
 int btrfs_leaf_free_space(struct btrfs_root *root, struct extent_buffer *leaf);
 int btrfs_drop_snapshot(struct btrfs_trans_handle *trans, struct btrfs_root
 			*root);
diff --git a/fs/btrfs/disk-io.c b/fs/btrfs/disk-io.c
index 60a30da6af00..0ac21e3aac87 100644
--- a/fs/btrfs/disk-io.c
+++ b/fs/btrfs/disk-io.c
@@ -210,7 +210,7 @@ static int btree_writepages(struct address_space *mapping,
 {
 	struct extent_map_tree *tree;
 	tree = &BTRFS_I(mapping->host)->extent_tree;
-	if (wbc->sync_mode == WB_SYNC_NONE) {
+	if (0 && wbc->sync_mode == WB_SYNC_NONE) {
 		u64 num_dirty;
 		u64 start = 0;
 		unsigned long thresh = 96 * 1024 * 1024;
diff --git a/fs/btrfs/extent-tree.c b/fs/btrfs/extent-tree.c
index 0f1ebdd4e925..32991f73e9db 100644
--- a/fs/btrfs/extent-tree.c
+++ b/fs/btrfs/extent-tree.c
@@ -17,6 +17,7 @@
  */
 
 #include <linux/sched.h>
+#include <linux/crc32c.h>
 #include "hash.h"
 #include "ctree.h"
 #include "disk-io.h"
@@ -89,7 +90,8 @@ static int cache_block_group(struct btrfs_root *root,
 
 		btrfs_item_key_to_cpu(leaf, &key, slot);
 		if (key.objectid < block_group->key.objectid) {
-			if (key.objectid + key.offset > first_free)
+			if (btrfs_key_type(&key) != BTRFS_EXTENT_REF_KEY &&
+			    key.objectid + key.offset > first_free)
 				first_free = key.objectid + key.offset;
 			goto next;
 		}
@@ -353,7 +355,7 @@ found:
 	return found_group;
 }
 
-static u64 hash_extent_ref(u64 root_objectid, u64 root_generation,
+static u64 hash_extent_ref(u64 root_objectid, u64 ref_generation,
 			   u64 owner, u64 owner_offset)
 {
 	u32 high_crc = ~(u32)0;
@@ -362,53 +364,149 @@ static u64 hash_extent_ref(u64 root_objectid, u64 root_generation,
 
 	lenum = cpu_to_le64(root_objectid);
 	high_crc = crc32c(high_crc, &lenum, sizeof(lenum));
-	lenum = cpu_to_le64(root_generation);
-	high_crc = crc32c(high_crc, &lenum, sizeof(lenum));
+	lenum = cpu_to_le64(ref_generation);
+	low_crc = crc32c(low_crc, &lenum, sizeof(lenum));
 
+#if 0
 	lenum = cpu_to_le64(owner);
 	low_crc = crc32c(low_crc, &lenum, sizeof(lenum));
-
 	lenum = cpu_to_le64(owner_offset);
 	low_crc = crc32c(low_crc, &lenum, sizeof(lenum));
-
+#endif
 	return ((u64)high_crc << 32) | (u64)low_crc;
 }
 
-int insert_extent_ref(struct btrfs_trans_handle *trans,
-				struct btrfs_root *root,
-				struct btrfs_path *path,
-				u64 bytenr,
-				u64 root_objectid, u64 root_generation,
-				u64 owner, u64 owner_offset)
+static int match_extent_ref(struct extent_buffer *leaf,
+			    struct btrfs_extent_ref *disk_ref,
+			    struct btrfs_extent_ref *cpu_ref)
+{
+	int ret;
+	int len;
+
+	if (cpu_ref->objectid)
+		len = sizeof(*cpu_ref);
+	else
+		len = 2 * sizeof(u64);
+	ret = memcmp_extent_buffer(leaf, cpu_ref, (unsigned long)disk_ref,
+				   len);
+	return ret == 0;
+}
+
+static int lookup_extent_backref(struct btrfs_trans_handle *trans,
+				 struct btrfs_root *root,
+				 struct btrfs_path *path, u64 bytenr,
+				 u64 root_objectid, u64 ref_generation,
+				 u64 owner, u64 owner_offset, int del)
 {
 	u64 hash;
 	struct btrfs_key key;
+	struct btrfs_key found_key;
 	struct btrfs_extent_ref ref;
-	struct extent_buffer *l;
-	struct btrfs_extent_item *item;
+	struct extent_buffer *leaf;
+	struct btrfs_extent_ref *disk_ref;
+	int ret;
+	int ret2;
+
+	btrfs_set_stack_ref_root(&ref, root_objectid);
+	btrfs_set_stack_ref_generation(&ref, ref_generation);
+	btrfs_set_stack_ref_objectid(&ref, owner);
+	btrfs_set_stack_ref_offset(&ref, owner_offset);
+
+	hash = hash_extent_ref(root_objectid, ref_generation, owner,
+			       owner_offset);
+	key.offset = hash;
+	key.objectid = bytenr;
+	key.type = BTRFS_EXTENT_REF_KEY;
+
+	while (1) {
+		ret = btrfs_search_slot(trans, root, &key, path,
+					del ? -1 : 0, del);
+		if (ret < 0)
+			goto out;
+		leaf = path->nodes[0];
+		if (ret != 0) {
+			u32 nritems = btrfs_header_nritems(leaf);
+			if (path->slots[0] >= nritems) {
+				ret2 = btrfs_next_leaf(root, path);
+				if (ret2)
+					goto out;
+				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_REF_KEY)
+				goto out;
+			key.offset = found_key.offset;
+			if (del) {
+				btrfs_release_path(root, path);
+				continue;
+			}
+		}
+		disk_ref = btrfs_item_ptr(path->nodes[0],
+					  path->slots[0],
+					  struct btrfs_extent_ref);
+		if (match_extent_ref(path->nodes[0], disk_ref, &ref)) {
+			ret = 0;
+			goto out;
+		}
+		btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
+		key.offset = found_key.offset + 1;
+		btrfs_release_path(root, path);
+	}
+out:
+	return ret;
+}
+
+int btrfs_insert_extent_backref(struct btrfs_trans_handle *trans,
+				 struct btrfs_root *root,
+				 struct btrfs_path *path, u64 bytenr,
+				 u64 root_objectid, u64 ref_generation,
+				 u64 owner, u64 owner_offset)
+{
+	u64 hash;
+	struct btrfs_key key;
+	struct btrfs_extent_ref ref;
+	struct btrfs_extent_ref *disk_ref;
 	int ret;
 
 	btrfs_set_stack_ref_root(&ref, root_objectid);
-	btrfs_set_stack_ref_generation(&ref, root_generation);
+	btrfs_set_stack_ref_generation(&ref, ref_generation);
 	btrfs_set_stack_ref_objectid(&ref, owner);
 	btrfs_set_stack_ref_offset(&ref, owner_offset);
 
-	ret = btrfs_name_hash(&ref, sizeof(ref), &hash);
+	hash = hash_extent_ref(root_objectid, ref_generation, owner,
+			       owner_offset);
 	key.offset = hash;
 	key.objectid = bytenr;
 	key.type = BTRFS_EXTENT_REF_KEY;
 
 	ret = btrfs_insert_empty_item(trans, root, path, &key, sizeof(ref));
 	while (ret == -EEXIST) {
-
+		disk_ref = btrfs_item_ptr(path->nodes[0], path->slots[0],
+					  struct btrfs_extent_ref);
+		if (match_extent_ref(path->nodes[0], disk_ref, &ref))
+			goto out;
+		key.offset++;
+		btrfs_release_path(root, path);
+		ret = btrfs_insert_empty_item(trans, root, path, &key,
+					      sizeof(ref));
 	}
-
+	if (ret)
+		goto out;
+	disk_ref = btrfs_item_ptr(path->nodes[0], path->slots[0],
+				  struct btrfs_extent_ref);
+	write_extent_buffer(path->nodes[0], &ref, (unsigned long)disk_ref,
+			    sizeof(ref));
+	btrfs_mark_buffer_dirty(path->nodes[0]);
+out:
+	btrfs_release_path(root, path);
+	return ret;
 }
 
 int btrfs_inc_extent_ref(struct btrfs_trans_handle *trans,
 				struct btrfs_root *root,
 				u64 bytenr, u64 num_bytes,
-				u64 root_objectid, u64 root_generation,
+				u64 root_objectid, u64 ref_generation,
 				u64 owner, u64 owner_offset)
 {
 	struct btrfs_path *path;
@@ -441,6 +539,11 @@ int btrfs_inc_extent_ref(struct btrfs_trans_handle *trans,
 	btrfs_mark_buffer_dirty(path->nodes[0]);
 
 	btrfs_release_path(root->fs_info->extent_root, path);
+
+	ret = btrfs_insert_extent_backref(trans, root->fs_info->extent_root,
+					  path, bytenr, root_objectid,
+					  ref_generation, owner, owner_offset);
+	BUG_ON(ret);
 	finish_current_insert(trans, root->fs_info->extent_root);
 	del_pending_extents(trans, root->fs_info->extent_root);
 
@@ -489,10 +592,29 @@ out:
 }
 
 int btrfs_inc_root_ref(struct btrfs_trans_handle *trans,
-		       struct btrfs_root *root)
+		       struct btrfs_root *root, u64 owner_objectid)
 {
+	u64 generation;
+	u64 key_objectid;
+	u64 level;
+	u32 nritems;
+	struct btrfs_disk_key disk_key;
+
+	level = btrfs_header_level(root->node);
+	generation = trans->transid;
+	nritems = btrfs_header_nritems(root->node);
+	if (nritems > 0) {
+		if (level == 0)
+			btrfs_item_key(root->node, &disk_key, 0);
+		else
+			btrfs_node_key(root->node, &disk_key, 0);
+		key_objectid = btrfs_disk_key_objectid(&disk_key);
+	} else {
+		key_objectid = 0;
+	}
 	return btrfs_inc_extent_ref(trans, root, root->node->start,
-				    root->node->len);
+				    root->node->len, owner_objectid,
+				    generation, 0, 0);
 }
 
 int btrfs_inc_ref(struct btrfs_trans_handle *trans, struct btrfs_root *root,
@@ -506,7 +628,6 @@ int btrfs_inc_ref(struct btrfs_trans_handle *trans, struct btrfs_root *root,
 	int level;
 	int ret;
 	int faili;
-	int err;
 
 	if (!root->ref_cows)
 		return 0;
@@ -528,7 +649,9 @@ int btrfs_inc_ref(struct btrfs_trans_handle *trans, struct btrfs_root *root,
 			if (disk_bytenr == 0)
 				continue;
 			ret = btrfs_inc_extent_ref(trans, root, disk_bytenr,
-				    btrfs_file_extent_disk_num_bytes(buf, fi));
+				    btrfs_file_extent_disk_num_bytes(buf, fi),
+				    root->root_key.objectid, trans->transid,
+				    key.objectid, key.offset);
 			if (ret) {
 				faili = i;
 				goto fail;
@@ -536,7 +659,9 @@ int btrfs_inc_ref(struct btrfs_trans_handle *trans, struct btrfs_root *root,
 		} else {
 			bytenr = btrfs_node_blockptr(buf, i);
 			ret = btrfs_inc_extent_ref(trans, root, bytenr,
-					   btrfs_level_size(root, level - 1));
+					   btrfs_level_size(root, level - 1),
+					   root->root_key.objectid,
+					   trans->transid, 0, 0);
 			if (ret) {
 				faili = i;
 				goto fail;
@@ -546,6 +671,7 @@ int btrfs_inc_ref(struct btrfs_trans_handle *trans, struct btrfs_root *root,
 	return 0;
 fail:
 	WARN_ON(1);
+#if 0
 	for (i =0; i < faili; i++) {
 		if (level == 0) {
 			u64 disk_bytenr;
@@ -571,6 +697,7 @@ fail:
 			BUG_ON(err);
 		}
 	}
+#endif
 	return ret;
 }
 
@@ -809,18 +936,18 @@ int btrfs_finish_extent_commit(struct btrfs_trans_handle *trans,
 static int finish_current_insert(struct btrfs_trans_handle *trans, struct
 				 btrfs_root *extent_root)
 {
+	u64 start;
+	u64 end;
+	struct btrfs_fs_info *info = extent_root->fs_info;
+	struct btrfs_path *path;
 	struct btrfs_key ins;
 	struct btrfs_extent_item extent_item;
 	int ret;
 	int err = 0;
-	u64 start;
-	u64 end;
-	struct btrfs_fs_info *info = extent_root->fs_info;
 
 	btrfs_set_stack_extent_refs(&extent_item, 1);
 	btrfs_set_key_type(&ins, BTRFS_EXTENT_ITEM_KEY);
-	btrfs_set_stack_extent_owner(&extent_item,
-				     extent_root->root_key.objectid);
+	path = btrfs_alloc_path();
 
 	while(1) {
 		ret = find_first_extent_bit(&info->extent_ins, 0, &start,
@@ -834,7 +961,12 @@ static int finish_current_insert(struct btrfs_trans_handle *trans, struct
 					&extent_item, sizeof(extent_item));
 		clear_extent_bits(&info->extent_ins, start, end, EXTENT_LOCKED,
 				  GFP_NOFS);
+		err = btrfs_insert_extent_backref(trans, extent_root, path,
+					  start, extent_root->root_key.objectid,
+					  0, 0, 0);
+		BUG_ON(err);
 	}
+	btrfs_free_path(path);
 	return 0;
 }
 
@@ -871,7 +1003,9 @@ static int pin_down_bytes(struct btrfs_root *root, u64 bytenr, u32 num_bytes,
  * remove an extent from the root, returns 0 on success
  */
 static int __free_extent(struct btrfs_trans_handle *trans, struct btrfs_root
-			 *root, u64 bytenr, u64 num_bytes, int pin,
+			 *root, u64 bytenr, u64 num_bytes,
+			 u64 root_objectid, u64 ref_generation,
+			 u64 owner_objectid, u64 owner_offset, int pin,
 			 int mark_free)
 {
 	struct btrfs_path *path;
@@ -891,6 +1025,24 @@ static int __free_extent(struct btrfs_trans_handle *trans, struct btrfs_root
 	if (!path)
 		return -ENOMEM;
 
+	if (ref_generation && owner_objectid == 0 && root_objectid == 3) {
+//printk("drop backref root %Lu gen %Lu byte %Lu\n", root_objectid, ref_generation, bytenr );
+	}
+	ret = lookup_extent_backref(trans, extent_root, path,
+				    bytenr, root_objectid,
+				    ref_generation,
+				    owner_objectid, owner_offset, 1);
+	if (ret == 0) {
+		ret = btrfs_del_item(trans, extent_root, path);
+	} else {
+		btrfs_print_leaf(extent_root, path->nodes[0]);
+		WARN_ON(1);
+		printk("Unable to find ref byte nr %Lu root %Lu "
+		       " gen %Lu owner %Lu offset %Lu\n", bytenr,
+		       root_objectid, ref_generation, owner_objectid,
+		       owner_offset);
+	}
+	btrfs_release_path(extent_root, path);
 	ret = btrfs_search_slot(trans, extent_root, &key, path, -1, 1);
 	if (ret < 0)
 		return ret;
@@ -965,7 +1117,9 @@ static int del_pending_extents(struct btrfs_trans_handle *trans, struct
 		clear_extent_bits(pending_del, start, end, EXTENT_LOCKED,
 				  GFP_NOFS);
 		ret = __free_extent(trans, extent_root,
-				     start, end + 1 - start, 0, 0);
+				     start, end + 1 - start,
+				     extent_root->root_key.objectid,
+				     0, 0, 0, 0, 0);
 		if (ret)
 			err = ret;
 	}
@@ -976,18 +1130,25 @@ static int del_pending_extents(struct btrfs_trans_handle *trans, struct
  * remove an extent from the root, returns 0 on success
  */
 int btrfs_free_extent(struct btrfs_trans_handle *trans, struct btrfs_root
-		      *root, u64 bytenr, u64 num_bytes, int pin)
+		      *root, u64 bytenr, u64 num_bytes,
+		      u64 root_objectid, u64 ref_generation,
+		      u64 owner_objectid, u64 owner_offset, int pin)
 {
 	struct btrfs_root *extent_root = root->fs_info->extent_root;
 	int pending_ret;
 	int ret;
 
 	WARN_ON(num_bytes < root->sectorsize);
+	if (!root->ref_cows)
+		ref_generation = 0;
+
 	if (root == extent_root) {
 		pin_down_bytes(root, bytenr, num_bytes, 1);
 		return 0;
 	}
-	ret = __free_extent(trans, root, bytenr, num_bytes, pin, pin == 0);
+	ret = __free_extent(trans, root, bytenr, num_bytes, root_objectid,
+			    ref_generation, owner_objectid, owner_offset,
+			    pin, pin == 0);
 	pending_ret = del_pending_extents(trans, root->fs_info->extent_root);
 	return ret ? ret : pending_ret;
 }
@@ -1080,23 +1241,26 @@ check_failed:
 	btrfs_item_key_to_cpu(l, &key, path->slots[0]);
 
 	/*
-	 * a rare case, go back one key if we hit a block group item
-	 * instead of an extent item
+	 * walk backwards to find the first extent item key
 	 */
-	if (btrfs_key_type(&key) != BTRFS_EXTENT_ITEM_KEY &&
-	    key.objectid + key.offset >= search_start) {
-		ins->objectid = key.objectid;
-		ins->offset = key.offset - 1;
-		btrfs_release_path(root, path);
-		ret = btrfs_search_slot(trans, root, ins, path, 0, 0);
-		if (ret < 0)
-			goto error;
-
-		if (path->slots[0] > 0) {
+	while(btrfs_key_type(&key) != BTRFS_EXTENT_ITEM_KEY) {
+		if (path->slots[0] == 0) {
+			ret = btrfs_prev_leaf(root, path);
+			if (ret != 0) {
+				ret = btrfs_search_slot(trans, root, ins,
+							path, 0, 0);
+				if (ret < 0)
+					goto error;
+				if (path->slots[0] > 0)
+					path->slots[0]--;
+				break;
+			}
+		} else {
 			path->slots[0]--;
 		}
+		l = path->nodes[0];
+		btrfs_item_key_to_cpu(l, &key, path->slots[0]);
 	}
-
 	while (1) {
 		l = path->nodes[0];
 		slot = path->slots[0];
@@ -1146,7 +1310,8 @@ check_failed:
 			}
 		}
 		if (btrfs_key_type(&key) != BTRFS_EXTENT_ITEM_KEY) {
-			if (!start_found) {
+			if (!start_found && btrfs_key_type(&key) ==
+			    BTRFS_BLOCK_GROUP_ITEM_KEY) {
 				last_byte = key.objectid;
 				start_found = 1;
 			}
@@ -1244,8 +1409,10 @@ error:
  * returns 0 if everything worked, non-zero otherwise.
  */
 int btrfs_alloc_extent(struct btrfs_trans_handle *trans,
-		       struct btrfs_root *root, u64 owner,
-		       u64 num_bytes, u64 empty_size, u64 hint_byte,
+		       struct btrfs_root *root,
+		       u64 num_bytes, u64 root_objectid, u64 ref_generation,
+		       u64 owner, u64 owner_offset,
+		       u64 empty_size, u64 hint_byte,
 		       u64 search_end, struct btrfs_key *ins, int data)
 {
 	int ret;
@@ -1255,9 +1422,9 @@ int btrfs_alloc_extent(struct btrfs_trans_handle *trans,
 	struct btrfs_fs_info *info = root->fs_info;
 	struct btrfs_root *extent_root = info->extent_root;
 	struct btrfs_extent_item extent_item;
+	struct btrfs_path *path;
 
 	btrfs_set_stack_extent_refs(&extent_item, 1);
-	btrfs_set_stack_extent_owner(&extent_item, owner);
 
 	WARN_ON(num_bytes < root->sectorsize);
 	ret = find_free_extent(trans, root, num_bytes, empty_size,
@@ -1296,8 +1463,16 @@ int btrfs_alloc_extent(struct btrfs_trans_handle *trans,
 
 	trans->alloc_exclude_start = 0;
 	trans->alloc_exclude_nr = 0;
+	BUG_ON(ret);
+
+	path = btrfs_alloc_path();
+	BUG_ON(!path);
+	ret = btrfs_insert_extent_backref(trans, extent_root, path,
+					  ins->objectid, root_objectid,
+					  ref_generation, owner, owner_offset);
 
 	BUG_ON(ret);
+	btrfs_free_path(path);
 	finish_current_insert(trans, extent_root);
 	pending_ret = del_pending_extents(trans, extent_root);
 
@@ -1321,15 +1496,43 @@ update_block:
  */
 struct extent_buffer *btrfs_alloc_free_block(struct btrfs_trans_handle *trans,
 					     struct btrfs_root *root,
-					     u32 blocksize, u64 hint,
+					     u32 blocksize,
+					     u64 root_objectid, u64 hint,