Mixed back reference (FORWARD ROLLING FORMAT CHANGE)

This commit introduces a new kind of back reference for btrfs metadata.
Once a filesystem has been mounted with this commit, IT WILL NO LONGER
BE MOUNTABLE BY OLDER KERNELS.

The new back ref provides information about pointer's key, level and in which
tree the pointer lives. This information allow us to find the pointer by
searching the tree. The shortcoming of the new back ref is that it only works
for pointers in tree blocks referenced by their owner trees.

This is mostly a problem for snapshots, where resolving one of these fuzzy back
references would be O(number_of_snapshots) and quite slow.  The solution used
here is to use the fuzzy back references in the common case where a given tree
block is only referenced by one root, and use the full back references when
multiple roots have a reference

1 files changed, 556 insertions, 169 deletions

diff --git a/btrfsck.c b/btrfsck.c
index a6d105ec..40c90f81 100644
--- a/btrfsck.c
+++ b/btrfsck.c
@@ -32,19 +32,38 @@
 static u64 bytes_used = 0;
 static u64 total_csum_bytes = 0;
 static u64 total_btree_bytes = 0;
+static u64 total_fs_tree_bytes = 0;
 static u64 btree_space_waste = 0;
 static u64 data_bytes_allocated = 0;
 static u64 data_bytes_referenced = 0;
+int found_old_backref = 0;
 
 struct extent_backref {
 	struct list_head list;
-	u64 parent;
-	u64 root;
-	u64 generation;
+	unsigned int is_data:1;
+	unsigned int found_extent_tree:1;
+	unsigned int full_backref:1;
+	unsigned int found_ref:1;
+};
+
+struct data_backref {
+	struct extent_backref node;
+	union {
+		u64 parent;
+		u64 root;
+	};
 	u64 owner;
+	u64 offset;
 	u32 num_refs;
 	u32 found_ref;
-	int found_extent_tree;
+};
+
+struct tree_backref {
+	struct extent_backref node;
+	union {
+		u64 parent;
+		u64 root;
+	};
 };
 
 struct extent_record {
@@ -53,9 +72,11 @@ struct extent_record {
 	struct btrfs_disk_key parent_key;
 	u64 start;
 	u64 nr;
-	u32 refs;
-	u32 extent_item_refs;
-	int checked;
+	u64 refs;
+	u64 extent_item_refs;
+	unsigned int content_checked:1;
+	unsigned int owner_ref_checked:1;
+	unsigned int is_root:1;
 };
 
 struct inode_backref {
@@ -84,6 +105,7 @@ struct inode_backref {
 struct inode_record {
 	struct list_head backrefs;
 	unsigned int checked:1;
+	unsigned int merging:1;
 	unsigned int found_inode_item:1;
 	unsigned int found_dir_item:1;
 	unsigned int found_file_extent:1;
@@ -120,6 +142,7 @@ struct inode_record {
 #define I_ERR_FILE_NBYTES_WRONG		(1 << 10) // 400
 #define I_ERR_ODD_CSUM_ITEM		(1 << 11)
 #define I_ERR_SOME_CSUM_MISSING		(1 << 12)
+#define I_ERR_LINK_COUNT_WRONG		(1 << 13)
 
 struct ptr_node {
 	struct cache_extent cache;
@@ -258,7 +281,7 @@ static void maybe_free_inode_rec(struct cache_tree *inode_cache,
 		}
 	}
 
-	if (!rec->checked)
+	if (!rec->checked || rec->merging)
 		return;
 
 	if (S_ISDIR(rec->imode)) {
@@ -425,6 +448,7 @@ static int merge_inode_recs(struct inode_record *src, struct inode_record *dst,
 	struct inode_backref *backref;
 	struct cache_tree *dst_cache = &dst_node->inode_cache;
 
+	dst->merging = 1;
 	list_for_each_entry(backref, &src->backrefs, list) {
 		if (backref->found_dir_index) {
 			add_inode_backref(dst_cache, dst->ino, backref->dir,
@@ -492,6 +516,7 @@ static int merge_inode_recs(struct inode_record *src, struct inode_record *dst,
 		if (dst_node->current == dst)
 			dst_node->current = NULL;
 	}
+	dst->merging = 0;
 	maybe_free_inode_rec(dst_cache, dst);
 	return 0;
 }
@@ -1001,13 +1026,13 @@ static int walk_down_tree(struct btrfs_root *root, struct btrfs_path *path,
 	struct extent_buffer *cur;
 	u32 blocksize;
 	int ret;
-	u32 refs;
+	u64 refs;
 
 	WARN_ON(*level < 0);
 	WARN_ON(*level >= BTRFS_MAX_LEVEL);
-	ret = btrfs_lookup_extent_ref(NULL, root,
-				      path->nodes[*level]->start,
-				      path->nodes[*level]->len, &refs);
+	ret = btrfs_lookup_extent_info(NULL, root,
+				       path->nodes[*level]->start,
+				       path->nodes[*level]->len, &refs, NULL);
 	BUG_ON(ret);
 	if (refs > 1) {
 		ret = enter_shared_node(root, path->nodes[*level]->start,
@@ -1033,8 +1058,8 @@ static int walk_down_tree(struct btrfs_root *root, struct btrfs_path *path,
 		bytenr = btrfs_node_blockptr(cur, path->slots[*level]);
 		ptr_gen = btrfs_node_ptr_generation(cur, path->slots[*level]);
 		blocksize = btrfs_level_size(root, *level - 1);
-		ret = btrfs_lookup_extent_ref(NULL, root, bytenr, blocksize,
-					      &refs);
+		ret = btrfs_lookup_extent_info(NULL, root, bytenr, blocksize,
+					       &refs, NULL);
 		BUG_ON(ret);
 
 		if (refs > 1) {
@@ -1072,7 +1097,7 @@ static int walk_up_tree(struct btrfs_root *root, struct btrfs_path *path,
 
 	for (i = *level; i < BTRFS_MAX_LEVEL - 1 && path->nodes[i]; i++) {
 		leaf = path->nodes[i];
-		if (path->slots[i] < btrfs_header_nritems(leaf) - 1) {
+		if (path->slots[i] + 1 < btrfs_header_nritems(leaf)) {
 			path->slots[i]++;
 			*level = i;
 			return 0;
@@ -1161,6 +1186,8 @@ static int check_inode_recs(struct btrfs_root *root,
 		error++;
 		if (!rec->found_inode_item)
 			rec->errors |= I_ERR_NO_INODE_ITEM;
+		if (rec->found_link != rec->nlink)
+			rec->errors |= I_ERR_LINK_COUNT_WRONG;
 		fprintf(stderr, "root %llu inode %llu errors %x\n",
 			(unsigned long long) root->root_key.objectid,
 			(unsigned long long) rec->ino, rec->errors);
@@ -1204,7 +1231,8 @@ static int check_fs_root(struct btrfs_root *root,
 	wc->active_node = level;
 	wc->root_level = level;
 
-	if (btrfs_disk_key_objectid(&root_item->drop_progress) == 0) {
+	if (btrfs_root_refs(root_item) > 0 ||
+	    btrfs_disk_key_objectid(&root_item->drop_progress) == 0) {
 		path.nodes[level] = root->node;
 		extent_buffer_get(root->node);
 		path.slots[level] = 0;
@@ -1289,7 +1317,8 @@ static int check_fs_roots(struct btrfs_root *root)
 		btrfs_item_key_to_cpu(leaf, &key, path.slots[0]);
 		if (key.type == BTRFS_ROOT_ITEM_KEY &&
 		    fs_root_objectid(key.objectid)) {
-			tmp_root = btrfs_read_fs_root(root->fs_info, &key);
+			tmp_root = btrfs_read_fs_root_no_cache(root->fs_info,
+							       &key);
 			ret = check_fs_root(tmp_root, &wc);
 			if (ret)
 				err = 1;
@@ -1389,7 +1418,9 @@ static int all_backpointers_checked(struct extent_record *rec, int print_errs)
 {
 	struct list_head *cur = rec->backrefs.next;
 	struct extent_backref *back;
-	u32 found = 0;
+	struct tree_backref *tback;
+	struct data_backref *dback;
+	u64 found = 0;
 	int err = 0;
 
 	while(cur != &rec->backrefs) {
@@ -1399,50 +1430,77 @@ static int all_backpointers_checked(struct extent_record *rec, int print_errs)
 			err = 1;
 			if (!print_errs)
 				goto out;
-			fprintf(stderr, "Backref %llu parent %llu"
-				" [%llu %llu %llu %lu]"
-				" not found in extent tree\n",
-				(unsigned long long)rec->start,
-				(unsigned long long)back->parent,
-				(unsigned long long)back->root,
-				(unsigned long long)back->generation,
-				(unsigned long long)back->owner,
-				(unsigned long)back->num_refs);
+			if (back->is_data) {
+				dback = (struct data_backref *)back;
+				fprintf(stderr, "Backref %llu %s %llu"
+					" owner %llu offset %llu num_refs %lu"
+					" not found in extent tree\n",
+					(unsigned long long)rec->start,
+					back->full_backref ?
+					"parent" : "root",
+					back->full_backref ?
+					(unsigned long long)dback->parent:
+					(unsigned long long)dback->root,
+					(unsigned long long)dback->owner,
+					(unsigned long long)dback->offset,
+					(unsigned long)dback->num_refs);
+			} else {
+				tback = (struct tree_backref *)back;
+				fprintf(stderr, "Backref %llu parent %llu"
+					" root %llu not found in extent tree\n",
+					(unsigned long long)rec->start,
+					(unsigned long long)tback->parent,
+					(unsigned long long)tback->root);
+			}
 		}
-		if (!back->found_ref) {
+		if (!back->is_data && !back->found_ref) {
 			err = 1;
 			if (!print_errs)
 				goto out;
-			fprintf(stderr, "Backref %llu parent %llu"
-				" [%llu %llu %llu %lu]"
-				" not referenced\n",
+			tback = (struct tree_backref *)back;
+			fprintf(stderr, "Backref %llu %s %llu not referenced\n",
 				(unsigned long long)rec->start,
-				(unsigned long long)back->parent,
-				(unsigned long long)back->root,
-				(unsigned long long)back->generation,
-				(unsigned long long)back->owner,
-				(unsigned long)back->num_refs);
+				back->full_backref ? "parent" : "root",
+				back->full_backref ?
+				(unsigned long long)tback->parent :
+				(unsigned long long)tback->root);
 		}
-		if (back->found_ref != back->num_refs) {
-			err = 1;
-			if (!print_errs)
-				goto out;
-			fprintf(stderr, "Incorrect local backref count "
-				"on %llu parent %llu found %u wanted %u\n",
-				(unsigned long long)rec->start,
-				(unsigned long long)back->parent,
-				back->found_ref, back->num_refs);
+		if (back->is_data) {
+			dback = (struct data_backref *)back;
+			if (dback->found_ref != dback->num_refs) {
+				err = 1;
+				if (!print_errs)
+					goto out;
+				fprintf(stderr, "Incorrect local backref count"
+					" on %llu %s %llu owner %llu"
+					" offset %llu found %u wanted %u\n",
+					(unsigned long long)rec->start,
+					back->full_backref ?
+					"parent" : "root",
+					back->full_backref ? 
+					(unsigned long long)dback->parent:
+					(unsigned long long)dback->root,
+					(unsigned long long)dback->owner,
+					(unsigned long long)dback->offset,
+					dback->found_ref, dback->num_refs);
+			}
+		}
+		if (!back->is_data) {
+			found += 1;
+		} else {
+			dback = (struct data_backref *)back;
+			found += dback->found_ref;
 		}
-		found += back->found_ref;
 	}
 	if (found != rec->refs) {
 		err = 1;
 		if (!print_errs)
 			goto out;
 		fprintf(stderr, "Incorrect global backref count "
-			"on %llu found %u wanted %u\n",
+			"on %llu found %llu wanted %llu\n",
 			(unsigned long long)rec->start,
-			found, rec->refs);
+			(unsigned long long)found,
+			(unsigned long long)rec->refs);
 	}
 out:
 	return err;
@@ -1464,8 +1522,9 @@ static int free_all_extent_backrefs(struct extent_record *rec)
 static int maybe_free_extent_rec(struct cache_tree *extent_cache,
 				 struct extent_record *rec)
 {
-	if (rec->checked && rec->extent_item_refs == rec->refs &&
-	    rec->refs > 0 && !all_backpointers_checked(rec, 0)) {
+	if (rec->content_checked && rec->owner_ref_checked &&
+	    rec->extent_item_refs == rec->refs && rec->refs > 0 &&
+	    !all_backpointers_checked(rec, 0)) {
 		remove_cache_extent(extent_cache, &rec->cache);
 		free_all_extent_backrefs(rec);
 		free(rec);
@@ -1473,9 +1532,61 @@ static int maybe_free_extent_rec(struct cache_tree *extent_cache,
 	return 0;
 }
 
+static int check_owner_ref(struct btrfs_root *root,
+			    struct extent_record *rec,
+			    struct extent_buffer *buf)
+{
+	struct extent_backref *node;
+	struct tree_backref *back;
+	struct btrfs_root *ref_root;
+	struct btrfs_key key;
+	struct btrfs_path path;
+	int ret;
+	int level;
+	int found = 0;
+
+	list_for_each_entry(node, &rec->backrefs, list) {
+		if (node->is_data)
+			continue;
+		if (!node->found_ref)
+			continue;
+		if (node->full_backref)
+			continue;
+		back = (struct tree_backref *)node;
+		if (btrfs_header_owner(buf) == back->root)
+			return 0;
+	}
+	BUG_ON(rec->is_root);
+
+	/* try to find the block by search corresponding fs tree */
+	key.objectid = btrfs_header_owner(buf);
+	key.type = BTRFS_ROOT_ITEM_KEY;
+	key.offset = (u64)-1;
+
+	ref_root = btrfs_read_fs_root(root->fs_info, &key);
+	BUG_ON(IS_ERR(ref_root));
+
+	level = btrfs_header_level(buf);
+	if (level == 0)
+		btrfs_item_key_to_cpu(buf, &key, 0);
+	else
+		btrfs_node_key_to_cpu(buf, &key, 0);
+	
+	btrfs_init_path(&path);
+	path.lowest_level = level + 1;
+	ret = btrfs_search_slot(NULL, ref_root, &key, &path, 0, 0);
+
+	if (buf->start == btrfs_node_blockptr(path.nodes[level + 1],
+					      path.slots[level + 1]))
+		rec->owner_ref_checked = 1;
+
+	btrfs_release_path(ref_root, &path);
+	return found ? 0 : 1;
+}
+
 static int check_block(struct btrfs_root *root,
 		       struct cache_tree *extent_cache,
-		       struct extent_buffer *buf)
+		       struct extent_buffer *buf, u64 flags)
 {
 	struct extent_record *rec;
 	struct cache_extent *cache;
@@ -1490,50 +1601,126 @@ static int check_block(struct btrfs_root *root,
 	} else {
 		ret = check_node(root, &rec->parent_key, buf);
 	}
-	rec->checked = 1;
+	if (ret) {
+		fprintf(stderr, "bad block %llu\n",
+			(unsigned long long)buf->start);
+	} else {
+		rec->content_checked = 1;
+		if (flags & BTRFS_BLOCK_FLAG_FULL_BACKREF)
+			rec->owner_ref_checked = 1;
+		else {
+			ret = check_owner_ref(root, rec, buf);
+			if (!ret)
+				rec->owner_ref_checked = 1;
+		}
+	}
 	if (!ret)
 		maybe_free_extent_rec(extent_cache, rec);
 	return ret;
 }
 
-static struct extent_backref *find_extent_backref(struct extent_record *rec,
-					   u64 parent, u64 root, u64 gen)
+static struct tree_backref *find_tree_backref(struct extent_record *rec,
+						u64 parent, u64 root)
 {
 	struct list_head *cur = rec->backrefs.next;
-	struct extent_backref *back;
+	struct extent_backref *node;
+	struct tree_backref *back;
 
 	while(cur != &rec->backrefs) {
-		back = list_entry(cur, struct extent_backref, list);
+		node = list_entry(cur, struct extent_backref, list);
 		cur = cur->next;
-		if (back->parent != parent)
+		if (node->is_data)
 			continue;
-		if (back->root != root || back->generation != gen)
+		back = (struct tree_backref *)node;
+		if (parent > 0) {
+			if (!node->full_backref)
+				continue;
+			if (parent == back->parent)
+				return back;
+		} else {
+			if (node->full_backref)
+				continue;
+			if (back->root == root)
+				return back;
+		}
+	}
+	return NULL;
+}
+
+static struct tree_backref *alloc_tree_backref(struct extent_record *rec,
+						u64 parent, u64 root)
+{
+	struct tree_backref *ref = malloc(sizeof(*ref));
+	memset(&ref->node, 0, sizeof(ref->node));
+	if (parent > 0) {
+		ref->parent = parent;
+		ref->node.full_backref = 1;
+	} else {
+		ref->root = root;
+		ref->node.full_backref = 0;
+	}
+	list_add_tail(&ref->node.list, &rec->backrefs);
+	return ref;
+}
+
+static struct data_backref *find_data_backref(struct extent_record *rec,
+						u64 parent, u64 root,
+						u64 owner, u64 offset)
+{
+	struct list_head *cur = rec->backrefs.next;
+	struct extent_backref *node;
+	struct data_backref *back;
+
+	while(cur != &rec->backrefs) {
+		node = list_entry(cur, struct extent_backref, list);
+		cur = cur->next;
+		if (!node->is_data)
 			continue;
-		return back;
+		back = (struct data_backref *)node;
+		if (parent > 0) { 
+			if (!node->full_backref)
+				continue;
+			if (parent == back->parent)
+				return back;
+		} else {
+			if (node->full_backref)
+				continue;
+			if (back->root == root && back->owner == owner &&
+			    back->offset == offset)
+				return back;
+		}
 	}
 	return NULL;
 }
 
-static struct extent_backref *alloc_extent_backref(struct extent_record *rec,
-						   u64 parent, u64 root,
-						   u64 gen, u64 owner)
+static struct data_backref *alloc_data_backref(struct extent_record *rec,
+						u64 parent, u64 root,
+						u64 owner, u64 offset)
 {
-	struct extent_backref *ref = malloc(sizeof(*ref));
-	ref->parent = parent;
-	ref->root = root;
-	ref->generation = gen;
-	ref->owner = owner;
-	ref->num_refs = 0;
-	ref->found_extent_tree = 0;
+	struct data_backref *ref = malloc(sizeof(*ref));
+	memset(&ref->node, 0, sizeof(ref->node));
+	ref->node.is_data = 1;
+	if (parent > 0) {
+		ref->parent = parent;
+		ref->owner = 0;
+		ref->offset = 0;
+		ref->node.full_backref = 1;
+	} else {
+		ref->root = root;
+		ref->owner = owner;
+		ref->offset = offset;
+		ref->node.full_backref = 0;
+	}
 	ref->found_ref = 0;
-	list_add_tail(&ref->list, &rec->backrefs);
+	ref->num_refs = 0;
+	list_add_tail(&ref->node.list, &rec->backrefs);
 	return ref;
 }
 
 static int add_extent_rec(struct cache_tree *extent_cache,
-			  struct btrfs_disk_key *parent_key,
-			  u64 ref, u64 start, u64 nr,
-			  u32 extent_item_refs, int inc_ref, int set_checked)
+			  struct btrfs_key *parent_key,
+			  u64 start, u64 nr, u64 extent_item_refs,
+			  int is_root, int inc_ref, int set_checked)
 {
 	struct extent_record *rec;
 	struct cache_extent *cache;
@@ -1556,31 +1743,39 @@ static int add_extent_rec(struct cache_tree *extent_cache,
 		if (extent_item_refs) {
 			if (rec->extent_item_refs) {
 				fprintf(stderr, "block %llu rec "
-					"extent_item_refs %u, passed %u\n",
+					"extent_item_refs %llu, passed %llu\n",
 					(unsigned long long)start,
-					rec->extent_item_refs,
-					extent_item_refs);
+					(unsigned long long)
+							rec->extent_item_refs,
+					(unsigned long long)extent_item_refs);
 			}
 			rec->extent_item_refs = extent_item_refs;
 		}
-		if (set_checked)
-			rec->checked = 1;
+		if (is_root)
+			rec->is_root = 1;
+		if (set_checked) {
+			rec->content_checked = 1;
+			rec->owner_ref_checked = 1;
+		}
 
 		if (parent_key)
-			memcpy(&rec->parent_key, parent_key,
-			       sizeof(*parent_key));
+			btrfs_cpu_key_to_disk(&rec->parent_key, parent_key);
 
 		maybe_free_extent_rec(extent_cache, rec);
 		return ret;
 	}
 	rec = malloc(sizeof(*rec));
-	if (start == 0)
-		extent_item_refs = 0;
 	rec->start = start;
 	rec->nr = nr;
-	rec->checked = 0;
+	rec->content_checked = 0;
+	rec->owner_ref_checked = 0;
 	INIT_LIST_HEAD(&rec->backrefs);
 
+	if (is_root)
+		rec->is_root = 1;
+	else
+		rec->is_root = 0;
+
 	if (inc_ref)
 		rec->refs = 1;
 	else
@@ -1592,7 +1787,7 @@ static int add_extent_rec(struct cache_tree *extent_cache,
 		rec->extent_item_refs = 0;
 
 	if (parent_key)
-		memcpy(&rec->parent_key, parent_key, sizeof(*parent_key));
+		btrfs_cpu_key_to_disk(&rec->parent_key, parent_key);
 	else
 		memset(&rec->parent_key, 0, sizeof(*parent_key));
 
@@ -1601,22 +1796,23 @@ static int add_extent_rec(struct cache_tree *extent_cache,
 	ret = insert_existing_cache_extent(extent_cache, &rec->cache);
 	BUG_ON(ret);
 	bytes_used += nr;
-	if (set_checked)
-		rec->checked = 1;
+	if (set_checked) {
+		rec->content_checked = 1;
+		rec->owner_ref_checked = 1;
+	}
 	return ret;
 }
 
-static int add_extent_backref(struct cache_tree *extent_cache, u64 bytenr,
-			      u64 parent, u64 root, u64 gen, u64 owner,
-			      u32 num_refs, int found_ref)
+static int add_tree_backref(struct cache_tree *extent_cache, u64 bytenr,
+			    u64 parent, u64 root, int found_ref)
 {
 	struct extent_record *rec;
-	struct extent_backref *back;
+	struct tree_backref *back;
 	struct cache_extent *cache;
 
 	cache = find_cache_extent(extent_cache, bytenr, 1);
 	if (!cache) {
-		add_extent_rec(extent_cache, NULL, 0, bytenr, 1, 0, 0, 0);
+		add_extent_rec(extent_cache, NULL, bytenr, 1, 0, 0, 0, 0);
 		cache = find_cache_extent(extent_cache, bytenr, 1);
 		if (!cache)
 			abort();
@@ -1626,39 +1822,75 @@ static int add_extent_backref(struct cache_tree *extent_cache, u64 bytenr,
 	if (rec->start != bytenr) {
 		abort();
 	}
-	back = find_extent_backref(rec, parent, root, gen);
+
+	back = find_tree_backref(rec, parent, root);
 	if (!back)
-		back = alloc_extent_backref(rec, parent, root, gen, owner);
+		back = alloc_tree_backref(rec, parent, root);
 
 	if (found_ref) {
-		if (back->found_ref > 0 &&
-		    back->owner < BTRFS_FIRST_FREE_OBJECTID) {
+		if (back->node.found_ref) {
 			fprintf(stderr, "Extent back ref already exists "
-				"for %llu parent %llu root %llu gen %llu "
-				"owner %llu num_refs %lu\n",
+				"for %llu parent %llu root %llu \n",
+				(unsigned long long)bytenr,
 				(unsigned long long)parent,
+				(unsigned long long)root);
+		}
+		back->node.found_ref = 1;
+	} else {
+		if (back->node.found_extent_tree) {
+			fprintf(stderr, "Extent back ref already exists "
+				"for %llu parent %llu root %llu \n",
 				(unsigned long long)bytenr,
-				(unsigned long long)root,
-				(unsigned long long)gen,
-				(unsigned long long)owner,
-				(unsigned long)num_refs);
+				(unsigned long long)parent,
+				(unsigned long long)root);
 		}
+		back->node.found_extent_tree = 1;
+	}
+	return 0;
+}
+
+static int add_data_backref(struct cache_tree *extent_cache, u64 bytenr,
+			    u64 parent, u64 root, u64 owner, u64 offset,
+			    u32 num_refs, int found_ref)
+{
+	struct extent_record *rec;
+	struct data_backref *back;
+	struct cache_extent *cache;
+
+	cache = find_cache_extent(extent_cache, bytenr, 1);
+	if (!cache) {
+		add_extent_rec(extent_cache, NULL, bytenr, 1, 0, 0, 0, 0);
+		cache = find_cache_extent(extent_cache, bytenr, 1);
+		if (!cache)
+			abort();
+	}
+
+	rec = container_of(cache, struct extent_record, cache);
+	if (rec->start != bytenr) {
+		abort();
+	}
+	back = find_data_backref(rec, parent, root, owner, offset);
+	if (!back)
+		back = alloc_data_backref(rec, parent, root, owner, offset);
+
+	if (found_ref) {
 		BUG_ON(num_refs != 1);
+		back->node.found_ref = 1;
 		back->found_ref += 1;
 	} else {
-		if (back->found_extent_tree) {
+		if (back->node.found_extent_tree) {
 			fprintf(stderr, "Extent back ref already exists "
-				"for %llu parent %llu root %llu gen %llu "
-				"owner %llu num_refs %lu\n",
-				(unsigned long long)parent,
+				"for %llu parent %llu root %llu"
+				"owner %llu offset %llu num_refs %lu\n",
 				(unsigned long long)bytenr,
+				(unsigned long long)parent,
 				(unsigned long long)root,
-				(unsigned long long)gen,
 				(unsigned long long)owner,
+				(unsigned long long)offset,
 				(unsigned long)num_refs);
 		}
 		back->num_refs = num_refs;
-		back->found_extent_tree = 1;
+		back->node.found_extent_tree = 1;
 	}
 	return 0;
 }
@@ -1674,6 +1906,7 @@ static int add_pending(struct cache_tree *pending,
 	insert_cache_extent(pending, bytenr, size);
 	return 0;
 }
+
 static int pick_next_pending(struct cache_tree *pending,
 			struct cache_tree *reada,
 			struct cache_tree *nodes,
@@ -1742,6 +1975,106 @@ static int pick_next_pending(struct cache_tree *pending,
 	return ret;
 }
 
+#ifdef BTRFS_COMPAT_EXTENT_TREE_V0
+static int process_extent_ref_v0(struct cache_tree *extent_cache,
+				 struct extent_buffer *leaf, int slot)
+{
+	struct btrfs_extent_ref_v0 *ref0;
+	struct btrfs_key key;
+
+	btrfs_item_key_to_cpu(leaf, &key, slot);
+	ref0 = btrfs_item_ptr(leaf, slot, struct btrfs_extent_ref_v0);
+	if (btrfs_ref_objectid_v0(leaf, ref0) < BTRFS_FIRST_FREE_OBJECTID) {
+		add_tree_backref(extent_cache, key.objectid, key.offset,
+				 0, 0);
+	} else {
+		add_data_backref(extent_cache, key.objectid, key.offset, 0,
+				 0, 0, btrfs_ref_count_v0(leaf, ref0), 0);
+	}
+	return 0;
+}
+#endif
+
+static int process_extent_item(struct cache_tree *extent_cache,
+			       struct extent_buffer *eb, int slot)
+{
+	struct btrfs_extent_item *ei;
+	struct btrfs_extent_inline_ref *iref;
+	struct btrfs_extent_data_ref *dref;
+	struct btrfs_shared_data_ref *sref;
+	struct btrfs_key key;
+	unsigned long end;
+	unsigned long ptr;
+	int type;
+	u32 item_size = btrfs_item_size_nr(eb, slot);
+	u64 refs = 0;
+	u64 offset;
+
+	btrfs_item_key_to_cpu(eb, &key, slot);
+
+	if (item_size < sizeof(*ei)) {
+#ifdef BTRFS_COMPAT_EXTENT_TREE_V0
+		struct btrfs_extent_item_v0 *ei0;
+		BUG_ON(item_size != sizeof(*ei0));
+		ei0 = btrfs_item_ptr(eb, slot, struct btrfs_extent_item_v0);
+		refs = btrfs_extent_refs_v0(eb, ei0);
+#else
+		BUG();
+#endif
+		return add_extent_rec(extent_cache, NULL, key.objectid,
+				      key.offset, refs, 0, 0, 0);
+	}
+
+	ei = btrfs_item_ptr(eb, slot, struct btrfs_extent_item);
+	refs = btrfs_extent_refs(eb, ei);
+
+	add_extent_rec(extent_cache, NULL, key.objectid, key.offset,
+		       refs, 0, 0, 0);
+
+	ptr = (unsigned long)(ei + 1);
+	if (btrfs_extent_flags(eb, ei) & BTRFS_EXTENT_FLAG_TREE_BLOCK)
+		ptr += sizeof(struct btrfs_tree_block_info);
+
+	end = (unsigned long)ei + item_size;
+	while (ptr < end) {
+		iref = (struct btrfs_extent_inline_ref *)ptr;
+		type = btrfs_extent_inline_ref_type(eb, iref);
+		offset = btrfs_extent_inline_ref_offset(eb, iref);
+		switch (type) {
+		case BTRFS_TREE_BLOCK_REF_KEY:
+			add_tree_backref(extent_cache, key.objectid,
+					 0, offset, 0);
+			break;
+		case BTRFS_SHARED_BLOCK_REF_KEY:
+			add_tree_backref(extent_cache, key.objectid,
+					 offset, 0, 0);
+			break;
+		case BTRFS_EXTENT_DATA_REF_KEY:
+			dref = (struct btrfs_extent_data_ref *)(&iref->offset);
+			add_data_backref(extent_cache, key.objectid, 0,
+					btrfs_extent_data_ref_root(eb, dref),
+					btrfs_extent_data_ref_objectid(eb,
+								       dref),
+					btrfs_extent_data_ref_offset(eb, dref),
+					btrfs_extent_data_ref_count(eb, dref),
+					0);
+			break;
+		case BTRFS_SHARED_DATA_REF_KEY:
+			sref = (struct btrfs_shared_data_ref *)(iref + 1);
+			add_data_backref(extent_cache, key.objectid, offset,
+					0, 0, 0,
+					btrfs_shared_data_ref_count(eb, sref),
+					0);
+			break;
+		default:
+			BUG();
+		}
+		ptr += btrfs_extent_inline_ref_size(type);
+	}
+	WARN_ON(ptr > end);
+	return 0;
+}
+
 static int run_next_block(struct btrfs_root *root,
 			  struct block_info *bits,
 			  int bits_nr,
@@ -1755,11 +2088,13 @@ static int run_next_block(struct btrfs_root *root,
 	struct extent_buffer *buf;
 	u64 bytenr;
 	u32 size;
+	u64 parent;
+	u64 owner;
+	u64 flags;
 	int ret;
 	int i;
 	int nritems;
-	struct btrfs_extent_ref *ref;
-	struct btrfs_disk_key disk_key;
+	struct btrfs_key key;
 	struct cache_extent *cache;
 	int reada_bits;
 
@@ -1801,38 +2136,34 @@ static int run_next_block(struct btrfs_root *root,
 	/* fixme, get the real parent transid */
 	buf = read_tree_block(root, bytenr, size, 0);
 	nritems = btrfs_header_nritems(buf);
-	ret = check_block(root, extent_cache, buf);
-	if (ret) {
-		fprintf(stderr, "bad block %llu\n",
-			(unsigned long long)bytenr);
+
+	ret = btrfs_lookup_extent_info(NULL, root, bytenr, size, NULL, &flags);
+
+	if (flags & BTRFS_BLOCK_FLAG_FULL_BACKREF) {
+		parent = bytenr;
+		owner = 0;
+	} else {
+		parent = 0;
+		owner = btrfs_header_owner(buf);
 	}
+
+	ret = check_block(root, extent_cache, buf, flags);
+
 	if (btrfs_is_leaf(buf)) {
 		btree_space_waste += btrfs_leaf_free_space(root, buf);
 		for (i = 0; i < nritems; i++) {
 			struct btrfs_file_extent_item *fi;
-			btrfs_item_key(buf, &disk_key, i);
-			if (btrfs_disk_key_type(&disk_key) ==
-			    BTRFS_EXTENT_ITEM_KEY) {
-				struct btrfs_key found;
-				struct btrfs_extent_item *ei;
-				btrfs_disk_key_to_cpu(&found, &disk_key);
-				ei = btrfs_item_ptr(buf, i,
-						    struct btrfs_extent_item);
-				add_extent_rec(extent_cache, NULL, 0,
-					       found.objectid,
-					       found.offset,
-					       btrfs_extent_refs(buf, ei),
-					       0, 0);
+			btrfs_item_key_to_cpu(buf, &key, i);
+			if (key.type == BTRFS_EXTENT_ITEM_KEY) {
+				process_extent_item(extent_cache, buf, i);
 				continue;
 			}
-			if (btrfs_disk_key_type(&disk_key) ==
-			    BTRFS_EXTENT_CSUM_KEY) {
+			if (key.type == BTRFS_EXTENT_CSUM_KEY) {
 				total_csum_bytes +=
 					btrfs_item_size_nr(buf, i);
 				continue;
 			}
-			if (btrfs_disk_key_type(&disk_key) ==
-			    BTRFS_BLOCK_GROUP_ITEM_KEY) {
+			if (key.type == BTRFS_BLOCK_GROUP_ITEM_KEY) {
 				struct btrfs_block_group_item *bi;
 				bi = btrfs_item_ptr(buf, i,
 					    struct btrfs_block_group_item);
@@ -1845,21 +2176,50 @@ static int run_next_block(struct btrfs_root *root,
 #endif
 				continue;
 			}
-			if (btrfs_disk_key_type(&disk_key) ==
-			    BTRFS_EXTENT_REF_KEY) {
+			if (key.type == BTRFS_EXTENT_REF_V0_KEY) {
+#ifdef BTRFS_COMPAT_EXTENT_TREE_V0
+				process_extent_ref_v0(extent_cache, buf, i);
+#else
+				BUG();
+#endif
+				continue;
+			}
+
+			if (key.type == BTRFS_TREE_BLOCK_REF_KEY) {
+				add_tree_backref(extent_cache, key.objectid, 0,
+						 key.offset, 0);
+				continue;
+			}
+			if (key.type == BTRFS_SHARED_BLOCK_REF_KEY) {
+				add_tree_backref(extent_cache, key.objectid,
+						 key.offset, 0, 0);
+				continue;
+			}
+			if (key.type == BTRFS_EXTENT_DATA_REF_KEY) {
+				struct btrfs_extent_data_ref *ref;
 				ref = btrfs_item_ptr(buf, i,
-						     struct btrfs_extent_ref);
-				add_extent_backref(extent_cache,
-					btrfs_disk_key_objectid(&disk_key),
-					btrfs_disk_key_offset(&disk_key),
-					btrfs_ref_root(buf, ref),
-					btrfs_ref_generation(buf, ref),
-					btrfs_ref_objectid(buf, ref),
-					btrfs_ref_num_refs(buf, ref), 0);
+						struct btrfs_extent_data_ref);
+				add_data_backref(extent_cache,
+					key.objectid, 0,
+					btrfs_extent_data_ref_root(buf, ref),
+					btrfs_extent_data_ref_objectid(buf,
+								       ref),
+					btrfs_extent_data_ref_offset(buf, ref),
+					btrfs_extent_data_ref_count(buf, ref),
+					0);
 				continue;
 			}
-			if (btrfs_disk_key_type(&disk_key) !=
-			    BTRFS_EXTENT_DATA_KEY)
+			if (key.type == BTRFS_SHARED_DATA_REF_KEY) {
+				struct btrfs_shared_data_ref *ref;
+				ref = btrfs_item_ptr(buf, i,
+						struct btrfs_shared_data_ref);
+				add_data_backref(extent_cache,
+					key.objectid, key.offset, 0, 0, 0, 
+					btrfs_shared_data_ref_count(buf, ref),
+					0);
+				continue;
+			}
+			if (key.type != BTRFS_EXTENT_DATA_KEY)
 				continue;
 			fi = btrfs_item_ptr(buf, i,
 					    struct btrfs_file_extent_item);
@@ -1876,15 +2236,14 @@ static int run_next_block(struct btrfs_root *root,
 			}
 			data_bytes_referenced +=
 				btrfs_file_extent_num_bytes(buf, fi);
-			ret = add_extent_rec(extent_cache, NULL, bytenr,
+			ret = add_extent_rec(extent_cache, NULL,
 				   btrfs_file_extent_disk_bytenr(buf, fi),
 				   btrfs_file_extent_disk_num_bytes(buf, fi),
-				   0, 1, 1);
-			add_extent_backref(extent_cache,
+				   0, 0, 1, 1);
+			add_data_backref(extent_cache,
 				btrfs_file_extent_disk_bytenr(buf, fi),
-				buf->start, btrfs_header_owner(buf),
-				btrfs_header_generation(buf),
-				btrfs_disk_key_objectid(&disk_key), 1, 1);
+				parent, owner, key.objectid, key.offset -
+				btrfs_file_extent_offset(buf, fi), 1, 1);
 			BUG_ON(ret);
 		}
 	} else {
@@ -1893,17 +2252,13 @@ static int run_next_block(struct btrfs_root *root,
 		for (i = 0; i < nritems; i++) {
 			u64 ptr = btrfs_node_blockptr(buf, i);
 			u32 size = btrfs_level_size(root, level - 1);
-			btrfs_node_key(buf, &disk_key, i);
-			ret = add_extent_rec(extent_cache,
-					     &disk_key,
-					     bytenr, ptr, size,
-					     0, 1, 0);
+			btrfs_node_key_to_cpu(buf, &key, i);
+			ret = add_extent_rec(extent_cache, &key,
+					     ptr, size, 0, 0, 1, 0);
 			BUG_ON(ret);
 
-			add_extent_backref(extent_cache, ptr,
-				buf->start, btrfs_header_owner(buf),
-				btrfs_header_generation(buf),
-				level - 1, 1, 1);
+			add_tree_backref(extent_cache, ptr, parent, 
+					 owner, 1);
 
 			if (level > 1) {
 				add_pending(nodes, seen, ptr, size);
@@ -1915,6 +2270,13 @@ static int run_next_block(struct btrfs_root *root,
 				      nritems) * sizeof(struct btrfs_key_ptr);
 	}
 	total_btree_bytes += buf->len;
+	if (fs_root_objectid(btrfs_header_owner(buf)))
+		total_fs_tree_bytes += buf->len;
+	if (!found_old_backref &&
+	    btrfs_header_owner(buf) == BTRFS_TREE_RELOC_OBJECTID &&
+	    btrfs_header_backref_rev(buf) == BTRFS_MIXED_BACKREF_REV &&
+	    !btrfs_header_flag(buf, BTRFS_HEADER_FLAG_RELOC))
+		found_old_backref = 1;
 	free_extent_buffer(buf);
 	return 0;
 }
@@ -1926,18 +2288,22 @@ static int add_root_to_pending(struct extent_buffer *buf,
 			       struct cache_tree *pending,
 			       struct cache_tree *seen,
 			       struct cache_tree *reada,
-			       struct cache_tree *nodes, u64 root_objectid)
+			       struct cache_tree *nodes,
+			       struct btrfs_key *root_key)
 {
 	if (btrfs_header_level(buf) > 0)
 		add_pending(nodes, seen, buf->start, buf->len);
 	else
 		add_pending(pending, seen, buf->start, buf->len);
-	add_extent_rec(extent_cache, NULL, 0, buf->start, buf->len,
-		       0, 1, 0);
+	add_extent_rec(extent_cache, NULL, buf->start, buf->len,
+		       0, 1, 1, 0);
 
-	add_extent_backref(extent_cache, buf->start, buf->start,
-			root_objectid, btrfs_header_generation(buf),
-			btrfs_header_level(buf), 1, 1);
+	if (root_key->objectid == BTRFS_TREE_RELOC_OBJECTID ||
+	    btrfs_header_backref_rev(buf) < BTRFS_MIXED_BACKREF_REV)
+		add_tree_backref(extent_cache, buf->start, buf->start, 0, 1);
+	else
+		add_tree_backref(extent_cache, buf->start, 0,
+				 root_key->objectid, 1);
 	return 0;
 }
 
@@ -1957,9 +2323,9 @@ static int check_extent_refs(struct btrfs_root *root,
 			fprintf(stderr, "ref mismatch on [%llu %llu] ",
 				(unsigned long long)rec->start,
 				(unsigned long long)rec->nr);
-			fprintf(stderr, "extent item %u, found %u\n",
-				rec->extent_item_refs,
-				rec->refs);
+			fprintf(stderr, "extent item %llu, found %llu\n",
+				(unsigned long long)rec->extent_item_refs,
+				(unsigned long long)rec->refs);
 			err = 1;
 		}
 		if (all_backpointers_checked(rec, 1)) {
@@ -1969,6 +2335,13 @@ static int check_extent_refs(struct btrfs_root *root,
 
 			err = 1;
 		}
+		if (!rec->owner_ref_checked) {
+			fprintf(stderr, "owner ref check failed [%llu %llu]\n",
+				(unsigned long long)rec->start,
+				(unsigned long long)rec->nr);
+			err = 1;
+		}
+
 		remove_cache_extent(extent_cache, cache);
 		free_all_extent_backrefs(rec);
 		free(rec);
@@ -2009,11 +2382,11 @@ static int check_extents(struct btrfs_root *root)
 
 	add_root_to_pending(root->fs_info->tree_root->node, bits, bits_nr,
 			    &extent_cache, &pending, &seen, &reada, &nodes,
-			    root->fs_info->tree_root->root_key.objectid);
+			    &root->fs_info->tree_root->root_key);
 
 	add_root_to_pending(root->fs_info->chunk_root->node, bits, bits_nr,
 			    &extent_cache, &pending, &seen, &reada, &nodes,
-			    root->fs_info->chunk_root->root_key.objectid);
+			    &root->fs_info->chunk_root->root_key);
 
 	btrfs_init_path(&path);
 	key.offset = 0;
@@ -2045,7 +2418,7 @@ static int check_extents(struct btrfs_root *root)
 					       btrfs_root_level(&ri)), 0);
 			add_root_to_pending(buf, bits, bits_nr, &extent_cache,
 					    &pending, &seen, &reada, &nodes,
-					    found_key.objectid);
+					    &found_key);
 			free_extent_buffer(buf);
 		}
 		path.slots[0]++;
@@ -2089,11 +2462,25 @@ int main(int ac, char **av)
 
 out:
 	close_ctree(root);
+	if (found_old_backref) {
+		/*
+		 * there was a disk format change when mixed
+		 * backref was in testing tree. The old format
+		 * existed about one week.
+		 */
+		printf("\n * Found old mixed backref format. "
+		       "The old format is not supported! *"
+		       "\n * Please mount the FS in readonly mode, "
+		       "backup data and re-format the FS. *\n\n");
+		ret = 1;
+	}
 	printf("found %llu bytes used err is %d\n",
 	       (unsigned long long)bytes_used, ret);
 	printf("total csum bytes: %llu\n",(unsigned long long)total_csum_bytes);
 	printf("total tree bytes: %llu\n",
 	       (unsigned long long)total_btree_bytes);
+	printf("total fs tree bytes: %llu\n",
+	       (unsigned long long)total_fs_tree_bytes);
 	printf("btree space waste bytes: %llu\n",
 	       (unsigned long long)btree_space_waste);
 	printf("file data blocks allocated: %llu\n referenced %llu\n",