summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorChris Mason <chris.mason@oracle.com>2009-05-29 16:35:30 -0400
committerChris Mason <chris.mason@oracle.com>2009-06-08 13:30:36 -0400
commit95d3f20b51e9b2ee21822313ad4f31279396407b (patch)
treeb120e33ca9ad3f04a0a32b62451e6ba5926b2ca0
parent2d39a83829bfc26f0c79b33fca64540c634f7f18 (diff)
downloadbtrfs-progs-95d3f20b51e9b2ee21822313ad4f31279396407b.tar.gz
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
Diffstat
-rw-r--r--Makefile6
-rw-r--r--btrfs-image.c72
-rw-r--r--btrfsck.c725
-rw-r--r--crc32c.h1
-rw-r--r--ctree.c609
-rw-r--r--ctree.h221
-rw-r--r--debug-tree.c4
-rw-r--r--disk-io.c170
-rw-r--r--disk-io.h2
-rw-r--r--extent-tree.c1920
-rw-r--r--extent_io.c16
-rw-r--r--kerncompat.h1
-rw-r--r--mkfs.c7
-rw-r--r--print-tree.c159
-rw-r--r--utils.c25
15 files changed, 2725 insertions, 1213 deletions
diff --git a/Makefile b/Makefile
index e6a332c9..8097b5ae 100644
--- a/Makefile
+++ b/Makefile
@@ -1,10 +1,11 @@
CC=gcc
-AM_CFLAGS = -Wall -fno-strict-aliasing -D_FILE_OFFSET_BITS=64 -D_FORTIFY_SOURCE=2
+AM_CFLAGS = -Wall -D_FILE_OFFSET_BITS=64 -D_FORTIFY_SOURCE=2
CFLAGS = -g -Werror -Os
objects = ctree.o disk-io.o radix-tree.o extent-tree.o print-tree.o \
root-tree.o dir-item.o file-item.o inode-item.o \
inode-map.o crc32c.o rbtree.o extent-cache.o extent_io.o \
volumes.o utils.o
+
#
CHECKFLAGS=-D__linux__ -Dlinux -D__STDC__ -Dunix -D__unix__ -Wbitwise \
-Wuninitialized -Wshadow -Wundef
@@ -15,8 +16,7 @@ prefix ?= /usr/local
bindir = $(prefix)/bin
LIBS=-luuid
-progs = btrfsctl btrfsck mkfs.btrfs btrfs-debug-tree btrfs-show btrfs-vol \
- btrfstune btrfs-image
+progs = btrfsctl mkfs.btrfs btrfs-debug-tree btrfs-show btrfs-vol btrfsck
# make C=1 to enable sparse
ifdef C
diff --git a/btrfs-image.c b/btrfs-image.c
index 62b3dd80..f2bbcc83 100644
--- a/btrfs-image.c
+++ b/btrfs-image.c
@@ -440,6 +440,42 @@ static int add_metadata(u64 start, u64 size, struct metadump_struct *md)
return 0;
}
+#ifdef BTRFS_COMPAT_EXTENT_TREE_V0
+static int is_tree_block(struct btrfs_root *extent_root,
+ struct btrfs_path *path, u64 bytenr)
+{
+ struct extent_buffer *leaf;
+ struct btrfs_key key;
+ u64 ref_objectid;
+ int ret;
+
+ leaf = path->nodes[0];
+ while (1) {
+ struct btrfs_extent_ref_v0 *ref_item;
+ path->slots[0]++;
+ if (path->slots[0] >= btrfs_header_nritems(leaf)) {
+ ret = btrfs_next_leaf(extent_root, path);
+ BUG_ON(ret < 0);
+ if (ret > 0)
+ break;
+ leaf = path->nodes[0];
+ }
+ btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);
+ if (key.objectid != bytenr)
+ break;
+ if (key.type != BTRFS_EXTENT_REF_V0_KEY)
+ continue;
+ ref_item = btrfs_item_ptr(leaf, path->slots[0],
+ struct btrfs_extent_ref_v0);
+ ref_objectid = btrfs_ref_objectid_v0(leaf, ref_item);
+ if (ref_objectid < BTRFS_FIRST_FREE_OBJECTID)
+ return 1;
+ break;
+ }
+ return 0;
+}
+#endif
+
static int create_metadump(const char *input, FILE *out, int num_threads,
int compress_level)
{
@@ -447,12 +483,11 @@ static int create_metadump(const char *input, FILE *out, int num_threads,
struct btrfs_root *extent_root;
struct btrfs_path *path;
struct extent_buffer *leaf;
- struct btrfs_extent_ref *ref_item;
+ struct btrfs_extent_item *ei;
struct btrfs_key key;
struct metadump_struct metadump;
u64 bytenr;
u64 num_bytes;
- u64 ref_objectid;
int ret;
root = open_ctree(input, 0, 0);
@@ -495,29 +530,26 @@ static int create_metadump(const char *input, FILE *out, int num_threads,
bytenr = key.objectid;
num_bytes = key.offset;
- while (1) {
- path->slots[0]++;
- if (path->slots[0] >= btrfs_header_nritems(leaf)) {
- ret = btrfs_next_leaf(extent_root, path);
- BUG_ON(ret < 0);
- if (ret > 0)
- break;
- leaf = path->nodes[0];
+
+ if (btrfs_item_size_nr(leaf, path->slots[0]) > sizeof(*ei)) {
+ ei = btrfs_item_ptr(leaf, path->slots[0],
+ struct btrfs_extent_item);
+ if (btrfs_extent_flags(leaf, ei) &
+ BTRFS_EXTENT_FLAG_TREE_BLOCK) {
+ ret = add_metadata(bytenr, num_bytes,
+ &metadump);
+ BUG_ON(ret);
}
- btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);
- if (key.objectid != bytenr)
- break;
- if (key.type != BTRFS_EXTENT_REF_KEY)
- continue;
- ref_item = btrfs_item_ptr(leaf, path->slots[0],
- struct btrfs_extent_ref);
- ref_objectid = btrfs_ref_objectid(leaf, ref_item);
- if (ref_objectid < BTRFS_FIRST_FREE_OBJECTID) {
+ } else {
+#ifdef BTRFS_COMPAT_EXTENT_TREE_V0
+ if (is_tree_block(extent_root, path, bytenr)) {
ret = add_metadata(bytenr, num_bytes,
&metadump);
BUG_ON(ret);
- break;
}
+#else
+ BUG_ON(1);
+#endif
}
bytenr += num_bytes;
}
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",
diff --git a/crc32c.h b/crc32c.h
index 6d20a953..72f15120 100644
--- a/crc32c.h
+++ b/crc32c.h
@@ -24,4 +24,5 @@
u32 crc32c_le(u32 seed, unsigned char const *data, size_t length);
#define crc32c(seed, data, length) crc32c_le(seed, (unsigned char const *)data, length)
+#define btrfs_crc32c crc32c
#endif
diff --git a/ctree.c b/ctree.c
index 0c029a8c..2756dbf3 100644
--- a/ctree.c
+++ b/ctree.c
@@ -85,6 +85,7 @@ int btrfs_copy_root(struct btrfs_trans_handle *trans,
int ret = 0;
int level;
struct btrfs_root *new_root;
+ struct btrfs_disk_key disk_key;
new_root = kmalloc(sizeof(*new_root), GFP_NOFS);
if (!new_root)
@@ -98,8 +99,12 @@ int btrfs_copy_root(struct btrfs_trans_handle *trans,
WARN_ON(root->ref_cows && trans->transid != root->last_trans);
level = btrfs_header_level(buf);
- cow = btrfs_alloc_free_block(trans, new_root, buf->len, 0,
- new_root_objectid, trans->transid,
+ if (level == 0)
+ btrfs_item_key(buf, &disk_key, 0);
+ else
+ btrfs_node_key(buf, &disk_key, 0);
+ cow = btrfs_alloc_free_block(trans, new_root, buf->len,
+ new_root_objectid, &disk_key,
level, buf->start, 0);
if (IS_ERR(cow)) {
kfree(new_root);
@@ -109,15 +114,20 @@ int btrfs_copy_root(struct btrfs_trans_handle *trans,
copy_extent_buffer(cow, buf, 0, 0, cow->len);
btrfs_set_header_bytenr(cow, cow->start);
btrfs_set_header_generation(cow, trans->transid);
- btrfs_set_header_owner(cow, new_root_objectid);
- btrfs_clear_header_flag(cow, BTRFS_HEADER_FLAG_WRITTEN);
+ btrfs_set_header_backref_rev(cow, BTRFS_MIXED_BACKREF_REV);
+ btrfs_clear_header_flag(cow, BTRFS_HEADER_FLAG_WRITTEN |
+ BTRFS_HEADER_FLAG_RELOC);
+ if (new_root_objectid == BTRFS_TREE_RELOC_OBJECTID)
+ btrfs_set_header_flag(cow, BTRFS_HEADER_FLAG_RELOC);
+ else
+ btrfs_set_header_owner(cow, new_root_objectid);
write_extent_buffer(cow, root->fs_info->fsid,
(unsigned long)btrfs_header_fsid(cow),
BTRFS_FSID_SIZE);
WARN_ON(btrfs_header_generation(buf) > trans->transid);
- ret = btrfs_inc_ref(trans, new_root, buf, cow, NULL);
+ ret = btrfs_inc_ref(trans, new_root, cow, 0);
kfree(new_root);
if (ret)
@@ -128,6 +138,123 @@ int btrfs_copy_root(struct btrfs_trans_handle *trans,
return 0;
}
+/*
+ * check if the tree block can be shared by multiple trees
+ */
+int btrfs_block_can_be_shared(struct btrfs_root *root,
+ struct extent_buffer *buf)
+{
+ /*
+ * Tree blocks not in refernece counted trees and tree roots
+ * are never shared. If a block was allocated after the last
+ * snapshot and the block was not allocated by tree relocation,
+ * we know the block is not shared.
+ */
+ if (root->ref_cows &&
+ buf != root->node && buf != root->commit_root &&
+ (btrfs_header_generation(buf) <=
+ btrfs_root_last_snapshot(&root->root_item) ||
+ btrfs_header_flag(buf, BTRFS_HEADER_FLAG_RELOC)))
+ return 1;
+#ifdef BTRFS_COMPAT_EXTENT_TREE_V0
+ if (root->ref_cows &&
+ btrfs_header_backref_rev(buf) < BTRFS_MIXED_BACKREF_REV)
+ return 1;
+#endif
+ return 0;
+}
+
+static noinline int update_ref_for_cow(struct btrfs_trans_handle *trans,
+ struct btrfs_root *root,
+ struct extent_buffer *buf,
+ struct extent_buffer *cow)
+{
+ u64 refs;
+ u64 owner;
+ u64 flags;
+ u64 new_flags = 0;
+ int ret;
+
+ /*
+ * Backrefs update rules:
+ *
+ * Always use full backrefs for extent pointers in tree block
+ * allocated by tree relocation.
+ *
+ * If a shared tree block is no longer referenced by its owner
+ * tree (btrfs_header_owner(buf) == root->root_key.objectid),
+ * use full backrefs for extent pointers in tree block.
+ *
+ * If a tree block is been relocating
+ * (root->root_key.objectid == BTRFS_TREE_RELOC_OBJECTID),
+ * use full backrefs for extent pointers in tree block.
+ * The reason for this is some operations (such as drop tree)
+ * are only allowed for blocks use full backrefs.
+ */
+
+ if (btrfs_block_can_be_shared(root, buf)) {
+ ret = btrfs_lookup_extent_info(trans, root, buf->start,
+ buf->len, &refs, &flags);
+ BUG_ON(ret);
+ BUG_ON(refs == 0);
+ } else {
+ refs = 1;
+ if (root->root_key.objectid == BTRFS_TREE_RELOC_OBJECTID ||
+ btrfs_header_backref_rev(buf) < BTRFS_MIXED_BACKREF_REV)
+ flags = BTRFS_BLOCK_FLAG_FULL_BACKREF;
+ else
+ flags = 0;
+ }
+
+ owner = btrfs_header_owner(buf);
+ BUG_ON(!(flags & BTRFS_BLOCK_FLAG_FULL_BACKREF) &&
+ owner == BTRFS_TREE_RELOC_OBJECTID);
+
+ if (refs > 1) {
+ if ((owner == root->root_key.objectid ||
+ root->root_key.objectid == BTRFS_TREE_RELOC_OBJECTID) &&
+ !(flags & BTRFS_BLOCK_FLAG_FULL_BACKREF)) {
+ ret = btrfs_inc_ref(trans, root, buf, 1);
+ BUG_ON(ret);
+
+ if (root->root_key.objectid ==
+ BTRFS_TREE_RELOC_OBJECTID) {
+ ret = btrfs_dec_ref(trans, root, buf, 0);
+ BUG_ON(ret);
+ ret = btrfs_inc_ref(trans, root, cow, 1);
+ BUG_ON(ret);
+ }
+ new_flags |= BTRFS_BLOCK_FLAG_FULL_BACKREF;
+ } else {
+
+ if (root->root_key.objectid ==
+ BTRFS_TREE_RELOC_OBJECTID)
+ ret = btrfs_inc_ref(trans, root, cow, 1);
+ else
+ ret = btrfs_inc_ref(trans, root, cow, 0);
+ BUG_ON(ret);
+ }
+ if (new_flags != 0) {
+ ret = btrfs_set_block_flags(trans, root, buf->start,
+ buf->len, new_flags);
+ BUG_ON(ret);
+ }
+ } else {
+ if (flags & BTRFS_BLOCK_FLAG_FULL_BACKREF) {
+ if (root->root_key.objectid ==
+ BTRFS_TREE_RELOC_OBJECTID)
+ ret = btrfs_inc_ref(trans, root, cow, 1);
+ else
+ ret = btrfs_inc_ref(trans, root, cow, 0);
+ BUG_ON(ret);
+ ret = btrfs_dec_ref(trans, root, buf, 1);
+ BUG_ON(ret);
+ }
+ clean_tree_block(trans, root, buf);
+ }
+ return 0;
+}
+
int __btrfs_cow_block(struct btrfs_trans_handle *trans,
struct btrfs_root *root,
struct extent_buffer *buf,
@@ -135,26 +262,25 @@ int __btrfs_cow_block(struct btrfs_trans_handle *trans,
struct extent_buffer **cow_ret,
u64 search_start, u64 empty_size)
{
- u64 parent_start;
+ u64 generation;
struct extent_buffer *cow;
- u32 nritems;
- int ret = 0;
- int different_trans = 0;
+ struct btrfs_disk_key disk_key;
int level;
WARN_ON(root->ref_cows && trans->transid !=
root->fs_info->running_transaction->transid);
WARN_ON(root->ref_cows && trans->transid != root->last_trans);
- if (parent)
- parent_start = parent->start;
+ level = btrfs_header_level(buf);
+ generation = btrfs_header_generation(buf);
+
+ if (level == 0)
+ btrfs_item_key(buf, &disk_key, 0);
else
- parent_start = 0;
+ btrfs_node_key(buf, &disk_key, 0);
- level = btrfs_header_level(buf);
- nritems = btrfs_header_nritems(buf);
- cow = btrfs_alloc_free_block(trans, root, buf->len, parent_start,
- root->root_key.objectid, trans->transid,
+ cow = btrfs_alloc_free_block(trans, root, buf->len,
+ root->root_key.objectid, &disk_key,
level, search_start, empty_size);
if (IS_ERR(cow))
return PTR_ERR(cow);
@@ -162,36 +288,28 @@ int __btrfs_cow_block(struct btrfs_trans_handle *trans,
copy_extent_buffer(cow, buf, 0, 0, cow->len);
btrfs_set_header_bytenr(cow, cow->start);
btrfs_set_header_generation(cow, trans->transid);
- btrfs_set_header_owner(cow, root->root_key.objectid);
- btrfs_clear_header_flag(cow, BTRFS_HEADER_FLAG_WRITTEN);
+ btrfs_set_header_backref_rev(cow, BTRFS_MIXED_BACKREF_REV);
+ btrfs_clear_header_flag(cow, BTRFS_HEADER_FLAG_WRITTEN |
+ BTRFS_HEADER_FLAG_RELOC);
+ if (root->root_key.objectid == BTRFS_TREE_RELOC_OBJECTID)
+ btrfs_set_header_flag(cow, BTRFS_HEADER_FLAG_RELOC);
+ else
+ btrfs_set_header_owner(cow, root->root_key.objectid);
write_extent_buffer(cow, root->fs_info->fsid,
(unsigned long)btrfs_header_fsid(cow),
BTRFS_FSID_SIZE);
WARN_ON(btrfs_header_generation(buf) > trans->transid);
- if (btrfs_header_generation(buf) != trans->transid) {
- different_trans = 1;
- ret = btrfs_inc_ref(trans, root, buf, cow, NULL);
- if (ret)
- return ret;
- } else {
- ret = btrfs_update_ref(trans, root, buf, cow, 0, nritems);
- if (ret)
- return ret;
- clean_tree_block(trans, root, buf);
- }
+
+ update_ref_for_cow(trans, root, buf, cow);
if (buf == root->node) {
root->node = cow;
extent_buffer_get(cow);
- if (buf != root->commit_root) {
- btrfs_free_extent(trans, root, buf->start,
- buf->len, buf->start,
- root->root_key.objectid,
- btrfs_header_generation(buf),
- level, 1);
- }
+
+ btrfs_free_extent(trans, root, buf->start, buf->len,
+ 0, root->root_key.objectid, level, 0);
free_extent_buffer(buf);
add_root_to_dirty_list(root);
} else {
@@ -202,9 +320,9 @@ 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,
- parent_start, btrfs_header_owner(parent),
- btrfs_header_generation(parent), level, 1);
+ 0, root->root_key.objectid, level, 1);
}
free_extent_buffer(buf);
btrfs_mark_buffer_dirty(cow);
@@ -212,6 +330,18 @@ int __btrfs_cow_block(struct btrfs_trans_handle *trans,
return 0;
}
+static inline int should_cow_block(struct btrfs_trans_handle *trans,
+ struct btrfs_root *root,
+ struct extent_buffer *buf)
+{
+ if (btrfs_header_generation(buf) == trans->transid &&
+ !btrfs_header_flag(buf, BTRFS_HEADER_FLAG_WRITTEN) &&
+ !(root->root_key.objectid != BTRFS_TREE_RELOC_OBJECTID &&
+ btrfs_header_flag(buf, BTRFS_HEADER_FLAG_RELOC)))
+ return 0;
+ return 1;
+}
+
int btrfs_cow_block(struct btrfs_trans_handle *trans,
struct btrfs_root *root, struct extent_buffer *buf,
struct extent_buffer *parent, int parent_slot,
@@ -232,8 +362,7 @@ int btrfs_cow_block(struct btrfs_trans_handle *trans,
(unsigned long long)root->fs_info->generation);
WARN_ON(1);
}
- if (btrfs_header_generation(buf) == trans->transid &&
- !btrfs_header_flag(buf, BTRFS_HEADER_FLAG_WRITTEN)) {
+ if (!should_cow_block(trans, root, buf)) {
*cow_ret = buf;
return 0;
}
@@ -698,22 +827,15 @@ static int balance_level(struct btrfs_trans_handle *trans,
BUG_ON(ret);
root->node = child;
-
- ret = btrfs_update_extent_ref(trans, root, child->start,
- mid->start, child->start,
- root->root_key.objectid,
- trans->transid, level - 1);
- BUG_ON(ret);
-
add_root_to_dirty_list(root);
path->nodes[level] = NULL;
clean_tree_block(trans, root, mid);
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,
- mid->start, root->root_key.objectid,
- btrfs_header_generation(mid),
+ 0, root->root_key.objectid,
level, 1);
/* once for the root ptr */
free_extent_buffer(mid);
@@ -764,7 +886,6 @@ static int balance_level(struct btrfs_trans_handle *trans,
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);
@@ -776,9 +897,9 @@ static int balance_level(struct btrfs_trans_handle *trans,
if (wret)
ret = wret;
wret = btrfs_free_extent(trans, root, bytenr,
- blocksize, parent->start,
- btrfs_header_owner(parent),
- generation, level, 1);
+ blocksize, 0,
+ root->root_key.objectid,
+ level, 0);
if (wret)
ret = wret;
} else {
@@ -813,7 +934,6 @@ static int balance_level(struct btrfs_trans_handle *trans,
}
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);
@@ -824,9 +944,8 @@ static int balance_level(struct btrfs_trans_handle *trans,
if (wret)
ret = wret;
wret = btrfs_free_extent(trans, root, bytenr, blocksize,
- parent->start,
- btrfs_header_owner(parent),
- root_gen, level, 1);
+ 0, root->root_key.objectid,
+ level, 0);
if (wret)
ret = wret;
} else {
@@ -1287,8 +1406,6 @@ static int push_node_left(struct btrfs_trans_handle *trans,
btrfs_mark_buffer_dirty(src);
btrfs_mark_buffer_dirty(dst);
- ret = btrfs_update_ref(trans, root, src, dst, dst_nritems, push_items);
- BUG_ON(ret);
return ret;
}
@@ -1351,8 +1468,6 @@ static int balance_node_right(struct btrfs_trans_handle *trans,
btrfs_mark_buffer_dirty(src);
btrfs_mark_buffer_dirty(dst);
- ret = btrfs_update_ref(trans, root, src, dst, 0, push_items);
- BUG_ON(ret);
return ret;
}
@@ -1372,7 +1487,6 @@ static int noinline insert_new_root(struct btrfs_trans_handle *trans,
struct extent_buffer *c;
struct extent_buffer *old;
struct btrfs_disk_key lower_key;
- int ret;
BUG_ON(path->nodes[level]);
BUG_ON(path->nodes[level-1] != root->node);
@@ -1383,18 +1497,19 @@ static int noinline insert_new_root(struct btrfs_trans_handle *trans,
else
btrfs_node_key(lower, &lower_key, 0);
- c = btrfs_alloc_free_block(trans, root, root->nodesize, 0,
- root->root_key.objectid,
- trans->transid, level,
- root->node->start, 0);
+ c = btrfs_alloc_free_block(trans, root, root->nodesize,
+ root->root_key.objectid, &lower_key,
+ level, root->node->start, 0);
+
if (IS_ERR(c))
return PTR_ERR(c);
- memset_extent_buffer(c, 0, 0, root->nodesize);
+ memset_extent_buffer(c, 0, 0, sizeof(struct btrfs_header));
btrfs_set_header_nritems(c, 1);
btrfs_set_header_level(c, level);
btrfs_set_header_bytenr(c, c->start);
btrfs_set_header_generation(c, trans->transid);
+ btrfs_set_header_backref_rev(c, BTRFS_MIXED_BACKREF_REV);
btrfs_set_header_owner(c, root->root_key.objectid);
write_extent_buffer(c, root->fs_info->fsid,
@@ -1417,12 +1532,6 @@ static int noinline insert_new_root(struct btrfs_trans_handle *trans,
old = root->node;
root->node = c;
- ret = btrfs_update_extent_ref(trans, root, lower->start,
- lower->start, c->start,
- root->root_key.objectid,
- trans->transid, level - 1);
- BUG_ON(ret);
-
/* the super has an extra ref to root->node */
free_extent_buffer(old);
@@ -1509,21 +1618,21 @@ static int split_node(struct btrfs_trans_handle *trans, struct btrfs_root
}
c_nritems = btrfs_header_nritems(c);
+ mid = (c_nritems + 1) / 2;
+ btrfs_node_key(c, &disk_key, mid);
- btrfs_node_key(c, &disk_key, 0);
split = btrfs_alloc_free_block(trans, root, root->nodesize,
- path->nodes[level + 1]->start,
- root->root_key.objectid,
- trans->transid, level, c->start, 0);
+ root->root_key.objectid,
+ &disk_key, level, c->start, 0);
if (IS_ERR(split))
return PTR_ERR(split);
- btrfs_set_header_flags(split, btrfs_header_flags(c));
+ memset_extent_buffer(split, 0, 0, sizeof(struct btrfs_header));
btrfs_set_header_level(split, btrfs_header_level(c));
btrfs_set_header_bytenr(split, split->start);
btrfs_set_header_generation(split, trans->transid);
+ btrfs_set_header_backref_rev(split, BTRFS_MIXED_BACKREF_REV);
btrfs_set_header_owner(split, root->root_key.objectid);
- btrfs_set_header_flags(split, 0);
write_extent_buffer(split, root->fs_info->fsid,
(unsigned long)btrfs_header_fsid(split),
BTRFS_FSID_SIZE);
@@ -1531,7 +1640,6 @@ static int split_node(struct btrfs_trans_handle *trans, struct btrfs_root
(unsigned long)btrfs_header_chunk_tree_uuid(split),
BTRFS_UUID_SIZE);
- mid = (c_nritems + 1) / 2;
copy_extent_buffer(split, c,
btrfs_node_key_ptr_offset(0),
@@ -1544,16 +1652,12 @@ static int split_node(struct btrfs_trans_handle *trans, struct btrfs_root
btrfs_mark_buffer_dirty(c);
btrfs_mark_buffer_dirty(split);
- btrfs_node_key(split, &disk_key, 0);
wret = insert_ptr(trans, root, path, &disk_key, split->start,
path->slots[level + 1] + 1,
level + 1);
if (wret)
ret = wret;
- ret = btrfs_update_ref(trans, root, c, split, 0, c_nritems - mid);
- BUG_ON(ret);
-
if (path->slots[level] >= mid) {
path->slots[level] -= mid;
free_extent_buffer(c);
@@ -1744,9 +1848,6 @@ static int push_leaf_right(struct btrfs_trans_handle *trans, struct btrfs_root
btrfs_set_node_key(upper, &disk_key, slot + 1);
btrfs_mark_buffer_dirty(upper);
- ret = btrfs_update_ref(trans, root, left, right, 0, push_items);
- BUG_ON(ret);
-
/* then fixup the leaf pointer in the path */
if (path->slots[0] >= left_nritems) {
path->slots[0] -= left_nritems;
@@ -1907,10 +2008,6 @@ static int push_leaf_left(struct btrfs_trans_handle *trans, struct btrfs_root
if (wret)
ret = wret;
- ret = btrfs_update_ref(trans, root, right, left,
- old_left_nritems, push_items);
- BUG_ON(ret);
-
/* then fixup the leaf pointer in the path */
if (path->slots[0] < push_items) {
path->slots[0] += old_left_nritems;
@@ -1931,34 +2028,96 @@ static int push_leaf_left(struct btrfs_trans_handle *trans, struct btrfs_root
*
* returns 0 if all went well and < 0 on failure.
*/
-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)
+static noinline int copy_for_split(struct btrfs_trans_handle *trans,
+ struct btrfs_root *root,
+ struct btrfs_path *path,
+ struct extent_buffer *l,
+ struct extent_buffer *right,
+ int slot, int mid, int nritems)
{
+ int data_copy_size;
+ int rt_data_off;
+ int i;
+ int ret = 0;
+ int wret;
+ struct btrfs_disk_key disk_key;
+
+ nritems = nritems - mid;
+ btrfs_set_header_nritems(right, nritems);
+ data_copy_size = btrfs_item_end_nr(l, mid) - leaf_data_end(root, l);
+
+ copy_extent_buffer(right, l, btrfs_item_nr_offset(0),
+ btrfs_item_nr_offset(mid),
+ nritems * sizeof(struct btrfs_item));
+
+ copy_extent_buffer(right, l,
+ btrfs_leaf_data(right) + BTRFS_LEAF_DATA_SIZE(root) -
+ data_copy_size, btrfs_leaf_data(l) +
+ leaf_data_end(root, l), data_copy_size);
+
+ rt_data_off = BTRFS_LEAF_DATA_SIZE(root) -
+ btrfs_item_end_nr(l, mid);
+
+ for (i = 0; i < nritems; i++) {
+ struct btrfs_item *item = btrfs_item_nr(right, i);
+ u32 ioff = btrfs_item_offset(right, item);
+ btrfs_set_item_offset(right, item, ioff + rt_data_off);
+ }
+
+ btrfs_set_header_nritems(l, mid);
+ ret = 0;
+ btrfs_item_key(right, &disk_key, 0);
+ wret = insert_ptr(trans, root, path, &disk_key, right->start,
+ path->slots[1] + 1, 1);
+ if (wret)
+ ret = wret;
+
+ btrfs_mark_buffer_dirty(right);
+ btrfs_mark_buffer_dirty(l);
+ BUG_ON(path->slots[0] != slot);
+
+ if (mid <= slot) {
+ free_extent_buffer(path->nodes[0]);
+ path->nodes[0] = right;
+ path->slots[0] -= mid;
+ path->slots[1] += 1;
+ } else {
+ free_extent_buffer(right);
+ }
+
+ BUG_ON(path->slots[0] < 0);
+
+ return ret;
+}
+
+/*
+ * split the path's leaf in two, making sure there is at least data_size
+ * available for the resulting leaf level of the path.
+ *
+ * returns 0 if all went well and < 0 on failure.
+ */
+static noinline 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)
+{
+ struct btrfs_disk_key disk_key;
struct extent_buffer *l;
u32 nritems;
int mid;
int slot;
struct extent_buffer *right;
- int space_needed = data_size + sizeof(struct btrfs_item);
- int data_copy_size;
- int rt_data_off;
- int i;
int ret = 0;
int wret;
- int double_split;
+ int split;
int num_doubles = 0;
- struct btrfs_disk_key disk_key;
-
- if (extend && data_size)
- space_needed = data_size;
/* first try to make some room by pushing left and right */
if (data_size && ins_key->type != BTRFS_DIR_ITEM_KEY) {
wret = push_leaf_right(trans, root, path, data_size, 0);
- if (wret < 0) {
+ if (wret < 0)
return wret;
- }
if (wret) {
wret = push_leaf_left(trans, root, path, data_size, 0);
if (wret < 0)
@@ -1967,7 +2126,7 @@ static int split_leaf(struct btrfs_trans_handle *trans, struct btrfs_root
l = path->nodes[0];
/* did the pushes work? */
- if (btrfs_leaf_free_space(root, l) >= space_needed)
+ if (btrfs_leaf_free_space(root, l) >= data_size)
return 0;
}
@@ -1977,144 +2136,116 @@ static int split_leaf(struct btrfs_trans_handle *trans, struct btrfs_root
return ret;
}
again:
- double_split = 0;
+ split = 1;
l = path->nodes[0];
slot = path->slots[0];
nritems = btrfs_header_nritems(l);
- mid = (nritems + 1)/ 2;
+ mid = (nritems + 1) / 2;
- right = btrfs_alloc_free_block(trans, root, root->leafsize,
- path->nodes[1]->start,
- root->root_key.objectid,
- trans->transid, 0, l->start, 0);
- if (IS_ERR(right)) {
- BUG_ON(1);
- return PTR_ERR(right);
- }
-
- memset_extent_buffer(right, 0, 0, sizeof(struct btrfs_header));
- btrfs_set_header_bytenr(right, right->start);
- btrfs_set_header_generation(right, trans->transid);
- btrfs_set_header_owner(right, root->root_key.objectid);
- btrfs_set_header_level(right, 0);
- write_extent_buffer(right, root->fs_info->fsid,
- (unsigned long)btrfs_header_fsid(right),
- BTRFS_FSID_SIZE);
-
- write_extent_buffer(right, root->fs_info->chunk_tree_uuid,
- (unsigned long)btrfs_header_chunk_tree_uuid(right),
- BTRFS_UUID_SIZE);
if (mid <= slot) {
if (nritems == 1 ||
- leaf_space_used(l, mid, nritems - mid) + space_needed >
+ leaf_space_used(l, mid, nritems - mid) + data_size >
BTRFS_LEAF_DATA_SIZE(root)) {
if (slot >= nritems) {
- btrfs_cpu_key_to_disk(&disk_key, ins_key);
- btrfs_set_header_nritems(right, 0);
- wret = insert_ptr(trans, root, path,
- &disk_key, right->start,
- path->slots[1] + 1, 1);
- if (wret)
- ret = wret;
- free_extent_buffer(path->nodes[0]);
- path->nodes[0] = right;
- path->slots[0] = 0;
- path->slots[1] += 1;
- return ret;
- }
- mid = slot;
- if (mid != nritems &&
- leaf_space_used(l, mid, nritems - mid) +
- space_needed > BTRFS_LEAF_DATA_SIZE(root)) {
- double_split = 1;
+ split = 0;
+ } else {
+ mid = slot;
+ if (mid != nritems &&
+ leaf_space_used(l, mid, nritems - mid) +
+ data_size > BTRFS_LEAF_DATA_SIZE(root)) {
+ split = 2;
+ }
}
}
} else {
- if (leaf_space_used(l, 0, mid + 1) + space_needed >
+ if (leaf_space_used(l, 0, mid) + data_size >
BTRFS_LEAF_DATA_SIZE(root)) {
if (!extend && data_size && slot == 0) {
- btrfs_cpu_key_to_disk(&disk_key, ins_key);
- btrfs_set_header_nritems(right, 0);
- wret = insert_ptr(trans, root, path,
- &disk_key,
- right->start,
- path->slots[1], 1);
- if (wret)
- ret = wret;
- free_extent_buffer(path->nodes[0]);
- path->nodes[0] = right;
- path->slots[0] = 0;
- if (path->slots[1] == 0) {
- wret = fixup_low_keys(trans, root,
- path, &disk_key, 1);
- if (wret)
- ret = wret;
- }
- return ret;
+ split = 0;
} else if ((extend || !data_size) && slot == 0) {
mid = 1;
} else {
mid = slot;
if (mid != nritems &&
leaf_space_used(l, mid, nritems - mid) +
- space_needed > BTRFS_LEAF_DATA_SIZE(root)) {
- double_split = 1;
+ data_size > BTRFS_LEAF_DATA_SIZE(root)) {
+ split = 2 ;
}
}
}
}
- nritems = nritems - mid;
- btrfs_set_header_nritems(right, nritems);
- data_copy_size = btrfs_item_end_nr(l, mid) - leaf_data_end(root, l);
-
- copy_extent_buffer(right, l, btrfs_item_nr_offset(0),
- btrfs_item_nr_offset(mid),
- nritems * sizeof(struct btrfs_item));
-
- copy_extent_buffer(right, l,
- btrfs_leaf_data(right) + BTRFS_LEAF_DATA_SIZE(root) -
- data_copy_size, btrfs_leaf_data(l) +
- leaf_data_end(root, l), data_copy_size);
-
- rt_data_off = BTRFS_LEAF_DATA_SIZE(root) -
- btrfs_item_end_nr(l, mid);
+
+ if (split == 0)
+ btrfs_cpu_key_to_disk(&disk_key, ins_key);
+ else
+ btrfs_item_key(l, &disk_key, mid);
- for (i = 0; i < nritems; i++) {
- struct btrfs_item *item = btrfs_item_nr(right, i);
- u32 ioff = btrfs_item_offset(right, item);
- btrfs_set_item_offset(right, item, ioff + rt_data_off);
+ right = btrfs_alloc_free_block(trans, root, root->leafsize,
+ root->root_key.objectid,
+ &disk_key, 0, l->start, 0);
+ if (IS_ERR(right)) {
+ BUG_ON(1);
+ return PTR_ERR(right);
}
- btrfs_set_header_nritems(l, mid);
- ret = 0;
- btrfs_item_key(right, &disk_key, 0);
- wret = insert_ptr(trans, root, path, &disk_key, right->start,
- path->slots[1] + 1, 1);
- if (wret)
- ret = wret;
+ memset_extent_buffer(right, 0, 0, sizeof(struct btrfs_header));
+ btrfs_set_header_bytenr(right, right->start);
+ btrfs_set_header_generation(right, trans->transid);
+ btrfs_set_header_backref_rev(right, BTRFS_MIXED_BACKREF_REV);
+ btrfs_set_header_owner(right, root->root_key.objectid);
+ btrfs_set_header_level(right, 0);
+ write_extent_buffer(right, root->fs_info->fsid,
+ (unsigned long)btrfs_header_fsid(right),
+ BTRFS_FSID_SIZE);
- btrfs_mark_buffer_dirty(right);
- btrfs_mark_buffer_dirty(l);
- BUG_ON(path->slots[0] != slot);
+ write_extent_buffer(right, root->fs_info->chunk_tree_uuid,
+ (unsigned long)btrfs_header_chunk_tree_uuid(right),
+ BTRFS_UUID_SIZE);
- ret = btrfs_update_ref(trans, root, l, right, 0, nritems);
- BUG_ON(ret);
+ if (split == 0) {
+ if (mid <= slot) {
+ btrfs_set_header_nritems(right, 0);
+ wret = insert_ptr(trans, root, path,
+ &disk_key, right->start,
+ path->slots[1] + 1, 1);
+ if (wret)
+ ret = wret;
- if (mid <= slot) {
- free_extent_buffer(path->nodes[0]);
- path->nodes[0] = right;
- path->slots[0] -= mid;
- path->slots[1] += 1;
- } else
- free_extent_buffer(right);
+ free_extent_buffer(path->nodes[0]);
+ path->nodes[0] = right;
+ path->slots[0] = 0;
+ path->slots[1] += 1;
+ } else {
+ btrfs_set_header_nritems(right, 0);
+ wret = insert_ptr(trans, root, path,
+ &disk_key,
+ right->start,
+ path->slots[1], 1);
+ if (wret)
+ ret = wret;
+ free_extent_buffer(path->nodes[0]);
+ path->nodes[0] = right;
+ path->slots[0] = 0;
+ if (path->slots[1] == 0) {
+ wret = fixup_low_keys(trans, root,
+ path, &disk_key, 1);
+ if (wret)
+ ret = wret;
+ }
+ }
+ btrfs_mark_buffer_dirty(right);
+ return ret;
+ }
- BUG_ON(path->slots[0] < 0);
+ ret = copy_for_split(trans, root, path, l, right, slot, mid, nritems);
+ BUG_ON(ret);
- if (double_split) {
+ if (split == 2) {
BUG_ON(num_doubles != 0);
num_doubles++;
goto again;
}
+
return ret;
}
@@ -2580,6 +2711,33 @@ static int del_ptr(struct btrfs_trans_handle *trans, struct btrfs_root *root,
}
/*
+ * a helper function to delete the leaf pointed to by path->slots[1] and
+ * path->nodes[1].
+ *
+ * This deletes the pointer in path->nodes[1] and frees the leaf
+ * block extent. zero is returned if it all worked out, < 0 otherwise.
+ *
+ * The path must have already been setup for deleting the leaf, including
+ * all the proper balancing. path->nodes[1] must be locked.
+ */
+static noinline int btrfs_del_leaf(struct btrfs_trans_handle *trans,
+ struct btrfs_root *root,
+ struct btrfs_path *path,
+ struct extent_buffer *leaf)
+{
+ int ret;
+
+ WARN_ON(btrfs_header_generation(leaf) != trans->transid);
+ ret = del_ptr(trans, root, path, 1, path->slots[1]);
+ if (ret)
+ return ret;
+
+ ret = btrfs_free_extent(trans, root, leaf->start, leaf->len,
+ 0, root->root_key.objectid, 0, 0);
+ return ret;
+}
+
+/*
* delete the item at the leaf level in path. If that empties
* the leaf, remove it from the tree
*/
@@ -2633,17 +2791,11 @@ int btrfs_del_items(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,
- path->nodes[1]->start,
- btrfs_header_owner(path->nodes[1]),
- root_gen, 0, 1);
+
+ wret = btrfs_del_leaf(trans, root, path, leaf);
+ BUG_ON(ret);
if (wret)
ret = wret;
}
@@ -2680,27 +2832,14 @@ int btrfs_del_items(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);
- wret = del_ptr(trans, root, path, 1, slot);
- if (wret)
- ret = wret;
-
+ path->slots[1] = slot;
+ ret = btrfs_del_leaf(trans, root, path, leaf);
+ BUG_ON(ret);
free_extent_buffer(leaf);
- wret = btrfs_free_extent(trans, root, bytenr,
- blocksize, path->nodes[1]->start,
- btrfs_header_owner(path->nodes[1]),
- root_gen, 0, 1);
- if (wret)
- ret = wret;
+
} else {
btrfs_mark_buffer_dirty(leaf);
free_extent_buffer(leaf);
diff --git a/ctree.h b/ctree.h
index 8e7f8845..a9062ea8 100644
--- a/ctree.h
+++ b/ctree.h
@@ -31,6 +31,8 @@ struct btrfs_trans_handle;
#define BTRFS_MAX_LEVEL 8
+#define BTRFS_COMPAT_EXTENT_TREE_V0
+
/* holds pointers to all of the tree roots */
#define BTRFS_ROOT_TREE_OBJECTID 1ULL
@@ -249,7 +251,18 @@ static inline unsigned long btrfs_chunk_item_size(int num_stripes)
}
#define BTRFS_FSID_SIZE 16
-#define BTRFS_HEADER_FLAG_WRITTEN (1 << 0)
+#define BTRFS_HEADER_FLAG_WRITTEN (1ULL << 0)
+#define BTRFS_HEADER_FLAG_RELOC (1ULL << 1)
+#define BTRFS_SUPER_FLAG_SEEDING (1ULL << 32)
+#define BTRFS_SUPER_FLAG_METADUMP (1ULL << 33)
+
+#define BTRFS_BACKREF_REV_MAX 256
+#define BTRFS_BACKREF_REV_SHIFT 56
+#define BTRFS_BACKREF_REV_MASK (((u64)BTRFS_BACKREF_REV_MAX - 1) << \
+ BTRFS_BACKREF_REV_SHIFT)
+
+#define BTRFS_OLD_BACKREF_REV 0
+#define BTRFS_MIXED_BACKREF_REV 1
/*
* every tree block (leaf or node) starts with this header.
@@ -278,8 +291,6 @@ struct btrfs_header {
sizeof(struct btrfs_item) - \
sizeof(struct btrfs_file_extent_item))
-#define BTRFS_SUPER_FLAG_SEEDING (1ULL << 32)
-#define BTRFS_SUPER_FLAG_METADUMP (1ULL << 33)
/*
* this is a very generous portion of the super block, giving us
@@ -338,9 +349,12 @@ struct btrfs_super_block {
* Compat flags that we support. If any incompat flags are set other than the
* ones specified below then we will fail to mount
*/
-#define BTRFS_FEATURE_COMPAT_SUPP 0x0
-#define BTRFS_FEATURE_COMPAT_RO_SUPP 0x0
-#define BTRFS_FEATURE_INCOMPAT_SUPP 0x0
+#define BTRFS_FEATURE_INCOMPAT_MIXED_BACKREF (1ULL << 0)
+
+#define BTRFS_FEATURE_COMPAT_SUPP 0ULL
+#define BTRFS_FEATURE_COMPAT_RO_SUPP 0ULL
+#define BTRFS_FEATURE_INCOMPAT_SUPP \
+ BTRFS_FEATURE_INCOMPAT_MIXED_BACKREF
/*
* A leaf is full of items. offset and size tell us where to find
@@ -387,32 +401,78 @@ struct btrfs_node {
* The slots array records the index of the item or block pointer
* used while walking the tree.
*/
+
struct btrfs_path {
struct extent_buffer *nodes[BTRFS_MAX_LEVEL];
int slots[BTRFS_MAX_LEVEL];
+ /* if there is real range locking, this locks field will change */
+ int locks[BTRFS_MAX_LEVEL];
int reada;
+ /* keep some upper locks as we walk down */
int lowest_level;
/*
* set by btrfs_split_item, tells search_slot to keep all locks
* and to force calls to keep space in the nodes
*/
- int search_for_split;
+ unsigned int search_for_split:1;
+ unsigned int keep_locks:1;
+ unsigned int skip_locking:1;
+ unsigned int leave_spinning:1;
};
/*
* items in the extent btree are used to record the objectid of the
* owner of the block and the number of references
*/
+
struct btrfs_extent_item {
+ __le64 refs;
+ __le64 generation;
+ __le64 flags;
+} __attribute__ ((__packed__));
+
+struct btrfs_extent_item_v0 {
__le32 refs;
} __attribute__ ((__packed__));
-struct btrfs_extent_ref {
+#define BTRFS_MAX_EXTENT_ITEM_SIZE(r) ((BTRFS_LEAF_DATA_SIZE(r) >> 4) - \
+ sizeof(struct btrfs_item))
+
+#define BTRFS_EXTENT_FLAG_DATA (1ULL << 0)
+#define BTRFS_EXTENT_FLAG_TREE_BLOCK (1ULL << 1)
+
+/* following flags only apply to tree blocks */
+
+/* use full backrefs for extent pointers in the block*/
+#define BTRFS_BLOCK_FLAG_FULL_BACKREF (1ULL << 8)
+
+struct btrfs_tree_block_info {
+ struct btrfs_disk_key key;
+ u8 level;
+} __attribute__ ((__packed__));
+
+struct btrfs_extent_data_ref {
+ __le64 root;
+ __le64 objectid;
+ __le64 offset;
+ __le32 count;
+} __attribute__ ((__packed__));
+
+struct btrfs_shared_data_ref {
+ __le32 count;
+} __attribute__ ((__packed__));
+
+struct btrfs_extent_inline_ref {
+ u8 type;
+ u64 offset;
+} __attribute__ ((__packed__));
+
+struct btrfs_extent_ref_v0 {
__le64 root;
__le64 generation;
__le64 objectid;
- __le32 num_refs;
+ __le32 count;
} __attribute__ ((__packed__));
/* dev extents record free space on individual devices. The owner
@@ -626,6 +686,8 @@ struct btrfs_fs_info {
struct btrfs_root *dev_root;
struct btrfs_root *csum_root;
+ struct cache_tree fs_root_cache;
+
/* the log root tree is a directory of all the other log roots */
struct btrfs_root *log_root_tree;
@@ -701,6 +763,7 @@ struct btrfs_root {
/* the dirty list is only used by non-reference counted roots */
struct list_head dirty_list;
+ struct cache_extent cache;
};
/*
@@ -761,7 +824,18 @@ struct btrfs_root {
* are used, and how many references there are to each block
*/
#define BTRFS_EXTENT_ITEM_KEY 168
-#define BTRFS_EXTENT_REF_KEY 180
+
+#define BTRFS_TREE_BLOCK_REF_KEY 176
+
+#define BTRFS_EXTENT_DATA_REF_KEY 178
+
+/* old style extent backrefs */
+#define BTRFS_EXTENT_REF_V0_KEY 180
+
+#define BTRFS_SHARED_BLOCK_REF_KEY 182
+
+#define BTRFS_SHARED_DATA_REF_KEY 184
+
/*
* block groups give us hints into the extent allocation trees. Which
@@ -1066,24 +1140,68 @@ static inline u8 *btrfs_dev_extent_chunk_tree_uuid(struct btrfs_dev_extent *dev)
return (u8 *)((unsigned long)dev + ptr);
}
-/* struct btrfs_extent_ref */
-BTRFS_SETGET_FUNCS(ref_root, struct btrfs_extent_ref, root, 64);
-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_num_refs, struct btrfs_extent_ref, num_refs, 32);
-
-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(stack_ref_objectid, struct btrfs_extent_ref,
- objectid, 64);
-BTRFS_SETGET_STACK_FUNCS(stack_ref_num_refs, struct btrfs_extent_ref,
- num_refs, 32);
/* struct btrfs_extent_item */
-BTRFS_SETGET_FUNCS(extent_refs, struct btrfs_extent_item, refs, 32);
-BTRFS_SETGET_STACK_FUNCS(stack_extent_refs, struct btrfs_extent_item,
- refs, 32);
+BTRFS_SETGET_FUNCS(extent_refs, struct btrfs_extent_item, refs, 64);
+BTRFS_SETGET_FUNCS(extent_generation, struct btrfs_extent_item,
+ generation, 64);
+BTRFS_SETGET_FUNCS(extent_flags, struct btrfs_extent_item, flags, 64);
+
+BTRFS_SETGET_FUNCS(extent_refs_v0, struct btrfs_extent_item_v0, refs, 32);
+
+BTRFS_SETGET_FUNCS(tree_block_level, struct btrfs_tree_block_info, level, 8);
+
+static inline void btrfs_tree_block_key(struct extent_buffer *eb,
+ struct btrfs_tree_block_info *item,
+ struct btrfs_disk_key *key)
+{
+ read_eb_member(eb, item, struct btrfs_tree_block_info, key, key);
+}
+
+static inline void btrfs_set_tree_block_key(struct extent_buffer *eb,
+ struct btrfs_tree_block_info *item,
+ struct btrfs_disk_key *key)
+{
+ write_eb_member(eb, item, struct btrfs_tree_block_info, key, key);
+}
+
+BTRFS_SETGET_FUNCS(extent_data_ref_root, struct btrfs_extent_data_ref,
+ root, 64);
+BTRFS_SETGET_FUNCS(extent_data_ref_objectid, struct btrfs_extent_data_ref,
+ objectid, 64);
+BTRFS_SETGET_FUNCS(extent_data_ref_offset, struct btrfs_extent_data_ref,
+ offset, 64);
+BTRFS_SETGET_FUNCS(extent_data_ref_count, struct btrfs_extent_data_ref,
+ count, 32);
+
+BTRFS_SETGET_FUNCS(shared_data_ref_count, struct btrfs_shared_data_ref,
+ count, 32);
+
+BTRFS_SETGET_FUNCS(extent_inline_ref_type, struct btrfs_extent_inline_ref,
+ type, 8);
+BTRFS_SETGET_FUNCS(extent_inline_ref_offset, struct btrfs_extent_inline_ref,
+ offset, 64);
+
+static inline u32 btrfs_extent_inline_ref_size(int type)
+{
+ if (type == BTRFS_TREE_BLOCK_REF_KEY ||
+ type == BTRFS_SHARED_BLOCK_REF_KEY)
+ return sizeof(struct btrfs_extent_inline_ref);
+ if (type == BTRFS_SHARED_DATA_REF_KEY)
+ return sizeof(struct btrfs_shared_data_ref) +
+ sizeof(struct btrfs_extent_inline_ref);
+ if (type == BTRFS_EXTENT_DATA_REF_KEY)
+ return sizeof(struct btrfs_extent_data_ref) +
+ offsetof(struct btrfs_extent_inline_ref, offset);
+ BUG();
+ return 0;
+}
+
+BTRFS_SETGET_FUNCS(ref_root_v0, struct btrfs_extent_ref_v0, root, 64);
+BTRFS_SETGET_FUNCS(ref_generation_v0, struct btrfs_extent_ref_v0,
+ generation, 64);
+BTRFS_SETGET_FUNCS(ref_objectid_v0, struct btrfs_extent_ref_v0, objectid, 64);
+BTRFS_SETGET_FUNCS(ref_count_v0, struct btrfs_extent_ref_v0, count, 32);
/* struct btrfs_node */
BTRFS_SETGET_FUNCS(key_blockptr, struct btrfs_key_ptr, blockptr, 64);
@@ -1313,6 +1431,21 @@ static inline int btrfs_clear_header_flag(struct extent_buffer *eb, u64 flag)
return (flags & flag) == flag;
}
+static inline int btrfs_header_backref_rev(struct extent_buffer *eb)
+{
+ u64 flags = btrfs_header_flags(eb);
+ return flags >> BTRFS_BACKREF_REV_SHIFT;
+}
+
+static inline void btrfs_set_header_backref_rev(struct extent_buffer *eb,
+ int rev)
+{
+ u64 flags = btrfs_header_flags(eb);
+ flags &= ~BTRFS_BACKREF_REV_MASK;
+ flags |= (u64)rev << BTRFS_BACKREF_REV_SHIFT;
+ btrfs_set_header_flags(eb, flags);
+}
+
static inline u8 *btrfs_header_fsid(struct extent_buffer *eb)
{
unsigned long ptr = offsetof(struct btrfs_header, fsid);
@@ -1521,32 +1654,30 @@ struct btrfs_block_group_cache *btrfs_find_block_group(struct btrfs_root *root,
*hint, u64 search_start,
int data, int owner);
struct extent_buffer *btrfs_alloc_free_block(struct btrfs_trans_handle *trans,
- struct btrfs_root *root,
- u32 blocksize, u64 parent,
- u64 root_objectid,
- u64 ref_generation,
- int level,
- u64 hint,
- u64 empty_size);
+ struct btrfs_root *root,
+ u32 blocksize, u64 root_objectid,
+ struct btrfs_disk_key *key, int level,
+ u64 hint, u64 empty_size);
int btrfs_alloc_extent(struct btrfs_trans_handle *trans,
struct btrfs_root *root,
u64 num_bytes, u64 parent,
u64 root_objectid, u64 ref_generation,
u64 owner, u64 empty_size, u64 hint_byte,
u64 search_end, struct btrfs_key *ins, int data);
-int btrfs_lookup_extent_ref(struct btrfs_trans_handle *trans,
- struct btrfs_root *root, u64 bytenr,
- u64 num_bytes, u32 *refs);
+int btrfs_lookup_extent_info(struct btrfs_trans_handle *trans,
+ struct btrfs_root *root, u64 bytenr,
+ u64 num_bytes, u64 *refs, u64 *flags);
+int btrfs_set_block_flags(struct btrfs_trans_handle *trans,
+ struct btrfs_root *root,
+ u64 bytenr, u64 num_bytes, u64 flags);
int btrfs_inc_ref(struct btrfs_trans_handle *trans, struct btrfs_root *root,
- struct extent_buffer *orig_buf, struct extent_buffer *buf,
- u32 *nr_extents);
-int btrfs_update_ref(struct btrfs_trans_handle *trans,
- struct btrfs_root *root, struct extent_buffer *orig_buf,
- struct extent_buffer *buf, int start_slot, int nr);
-int btrfs_free_extent(struct btrfs_trans_handle *trans, struct btrfs_root
- *root, u64 bytenr, u64 num_bytes, u64 parent,
- u64 root_objectid, u64 ref_generation,
- u64 owner_objectid, int pin);
+ struct extent_buffer *buf, int record_parent);
+int btrfs_dec_ref(struct btrfs_trans_handle *trans, struct btrfs_root *root,
+ struct extent_buffer *buf, int record_parent);
+int btrfs_free_extent(struct btrfs_trans_handle *trans,
+ struct btrfs_root *root,
+ u64 bytenr, u64 num_bytes, u64 parent,
+ u64 root_objectid, u64 owner, u64 offset);
int btrfs_finish_extent_commit(struct btrfs_trans_handle *trans,
struct btrfs_root *root,
struct extent_io_tree *unpin);
diff --git a/debug-tree.c b/debug-tree.c
index e22d3f5b..1d475190 100644
--- a/debug-tree.c
+++ b/debug-tree.c
@@ -39,7 +39,7 @@ static void print_extent_leaf(struct btrfs_root *root, struct extent_buffer *l)
{
int i;
struct btrfs_item *item;
- struct btrfs_extent_ref *ref;
+// struct btrfs_extent_ref *ref;
struct btrfs_key key;
static u64 last = 0;
static u64 last_len = 0;
@@ -55,6 +55,7 @@ static void print_extent_leaf(struct btrfs_root *root, struct extent_buffer *l)
last_len = key.offset;
last = key.objectid;
break;
+#if 0
case BTRFS_EXTENT_REF_KEY:
ref = btrfs_item_ptr(l, i, struct btrfs_extent_ref);
printf("%llu %llu extent back ref root %llu gen %llu "
@@ -66,6 +67,7 @@ static void print_extent_leaf(struct btrfs_root *root, struct extent_buffer *l)
(unsigned long long)btrfs_ref_objectid(l, ref),
(unsigned long)btrfs_ref_num_refs(l, ref));
break;
+#endif
};
fflush(stdout);
}
diff --git a/disk-io.c b/disk-io.c
index 82e24e6d..2b5771cb 100644
--- a/disk-io.c
+++ b/disk-io.c
@@ -365,46 +365,19 @@ int btrfs_commit_transaction(struct btrfs_trans_handle *trans,
struct btrfs_root *root)
{
int ret = 0;
- struct btrfs_root *new_root = NULL;
struct btrfs_fs_info *fs_info = root->fs_info;
if (root->commit_root == root->node)
goto commit_tree;
- new_root = malloc(sizeof(*new_root));
- if (!new_root)
- return -ENOMEM;
- memcpy(new_root, root, sizeof(*new_root));
- new_root->node = root->commit_root;
+ free_extent_buffer(root->commit_root);
root->commit_root = NULL;
- root->root_key.offset = trans->transid;
btrfs_set_root_bytenr(&root->root_item, root->node->start);
- btrfs_set_root_generation(&root->root_item, root->root_key.offset);
+ btrfs_set_root_generation(&root->root_item, trans->transid);
root->root_item.level = btrfs_header_level(root->node);
- ret = btrfs_insert_root(trans, fs_info->tree_root,
- &root->root_key, &root->root_item);
- BUG_ON(ret);
-
- btrfs_set_root_refs(&new_root->root_item, 0);
ret = btrfs_update_root(trans, root->fs_info->tree_root,
- &new_root->root_key, &new_root->root_item);
- BUG_ON(ret);
-
- ret = commit_tree_roots(trans, fs_info);
- BUG_ON(ret);
- ret = __commit_transaction(trans, root);
- BUG_ON(ret);
- write_ctree_super(trans, root);
- btrfs_finish_extent_commit(trans, fs_info->extent_root,
- &fs_info->pinned_extents);
- btrfs_free_transaction(root, trans);
- fs_info->running_transaction = NULL;
-
- trans = btrfs_start_transaction(root, 1);
- ret = btrfs_drop_snapshot(trans, new_root);
- BUG_ON(ret);
- ret = btrfs_del_root(trans, fs_info->tree_root, &new_root->root_key);
+ &root->root_key, &root->root_item);
BUG_ON(ret);
commit_tree:
ret = commit_tree_roots(trans, fs_info);
@@ -418,10 +391,6 @@ commit_tree:
free_extent_buffer(root->commit_root);
root->commit_root = NULL;
fs_info->running_transaction = NULL;
- if (new_root) {
- free_extent_buffer(new_root->node);
- free(new_root);
- }
return 0;
}
@@ -475,19 +444,36 @@ static int find_and_setup_log_root(struct btrfs_root *tree_root,
return 0;
}
-int btrfs_free_fs_root(struct btrfs_fs_info *fs_info, struct btrfs_root *root)
+
+int btrfs_free_fs_root(struct btrfs_fs_info *fs_info,
+ struct btrfs_root *root)
{
if (root->node)
free_extent_buffer(root->node);
if (root->commit_root)
free_extent_buffer(root->commit_root);
+ kfree(root);
+ return 0;
+}
- free(root);
+static int free_fs_roots(struct btrfs_fs_info *fs_info)
+{
+ struct cache_extent *cache;
+ struct btrfs_root *root;
+
+ while (1) {
+ cache = find_first_cache_extent(&fs_info->fs_root_cache, 0);
+ if (!cache)
+ break;
+ root = container_of(cache, struct btrfs_root, cache);
+ remove_cache_extent(&fs_info->fs_root_cache, cache);
+ btrfs_free_fs_root(fs_info, root);
+ }
return 0;
}
-struct btrfs_root *btrfs_read_fs_root(struct btrfs_fs_info *fs_info,
- struct btrfs_key *location)
+struct btrfs_root *btrfs_read_fs_root_no_cache(struct btrfs_fs_info *fs_info,
+ struct btrfs_key *location)
{
struct btrfs_root *root;
struct btrfs_root *tree_root = fs_info->tree_root;
@@ -546,6 +532,44 @@ insert:
return root;
}
+struct btrfs_root *btrfs_read_fs_root(struct btrfs_fs_info *fs_info,
+ struct btrfs_key *location)
+{
+ struct btrfs_root *root;
+ struct cache_extent *cache;
+ int ret;
+
+ if (location->objectid == BTRFS_ROOT_TREE_OBJECTID)
+ return fs_info->tree_root;
+ if (location->objectid == BTRFS_EXTENT_TREE_OBJECTID)
+ return fs_info->extent_root;
+ if (location->objectid == BTRFS_CHUNK_TREE_OBJECTID)
+ return fs_info->chunk_root;
+ if (location->objectid == BTRFS_DEV_TREE_OBJECTID)
+ return fs_info->dev_root;
+ if (location->objectid == BTRFS_CSUM_TREE_OBJECTID)
+ return fs_info->csum_root;
+
+ BUG_ON(location->objectid == BTRFS_TREE_RELOC_OBJECTID ||
+ location->offset != (u64)-1);
+
+ cache = find_cache_extent(&fs_info->fs_root_cache,
+ location->objectid, 1);
+ if (cache)
+ return container_of(cache, struct btrfs_root, cache);
+
+ root = btrfs_read_fs_root_no_cache(fs_info, location);
+ if (IS_ERR(root))
+ return root;
+
+ root->cache.start = location->objectid;
+ root->cache.size = 1;
+ ret = insert_existing_cache_extent(&fs_info->fs_root_cache,
+ &root->cache);
+ BUG_ON(ret);
+ return root;
+}
+
struct btrfs_root *open_ctree(const char *filename, u64 sb_bytenr, int writes)
{
int fp;
@@ -575,7 +599,7 @@ struct btrfs_root *open_ctree_fd(int fp, const char *path, u64 sb_bytenr,
u32 blocksize;
u32 stripesize;
u64 generation;
- struct btrfs_root *root = malloc(sizeof(struct btrfs_root));
+ struct btrfs_key key;
struct btrfs_root *tree_root = malloc(sizeof(struct btrfs_root));
struct btrfs_root *extent_root = malloc(sizeof(struct btrfs_root));
struct btrfs_root *chunk_root = malloc(sizeof(struct btrfs_root));
@@ -586,6 +610,7 @@ struct btrfs_root *open_ctree_fd(int fp, const char *path, u64 sb_bytenr,
struct btrfs_super_block *disk_super;
struct btrfs_fs_devices *fs_devices = NULL;
u64 total_devs;
+ u64 features;
if (sb_bytenr == 0)
sb_bytenr = BTRFS_SUPER_INFO_OFFSET;
@@ -604,7 +629,6 @@ struct btrfs_root *open_ctree_fd(int fp, const char *path, u64 sb_bytenr,
}
memset(fs_info, 0, sizeof(*fs_info));
- fs_info->fs_root = root;
fs_info->tree_root = tree_root;
fs_info->extent_root = extent_root;
fs_info->chunk_root = chunk_root;
@@ -620,6 +644,7 @@ struct btrfs_root *open_ctree_fd(int fp, const char *path, u64 sb_bytenr,
extent_io_tree_init(&fs_info->pinned_extents);
extent_io_tree_init(&fs_info->pending_del);
extent_io_tree_init(&fs_info->extent_ins);
+ cache_tree_init(&fs_info->fs_root_cache);
cache_tree_init(&fs_info->mapping_tree.cache_tree);
@@ -648,6 +673,29 @@ struct btrfs_root *open_ctree_fd(int fp, const char *path, u64 sb_bytenr,
memcpy(fs_info->fsid, &disk_super->fsid, BTRFS_FSID_SIZE);
+
+ features = btrfs_super_incompat_flags(disk_super) &
+ ~BTRFS_FEATURE_INCOMPAT_SUPP;
+ if (features) {
+ printk("couldn't open because of unsupported "
+ "option features (%Lx).\n", features);
+ BUG_ON(1);
+ }
+
+ features = btrfs_super_incompat_flags(disk_super);
+ if (!(features & BTRFS_FEATURE_INCOMPAT_MIXED_BACKREF)) {
+ features |= BTRFS_FEATURE_INCOMPAT_MIXED_BACKREF;
+ btrfs_set_super_incompat_flags(disk_super, features);
+ }
+
+ features = btrfs_super_compat_ro_flags(disk_super) &
+ ~BTRFS_FEATURE_COMPAT_RO_SUPP;
+ if (writes && features) {
+ printk("couldn't open RDWR because of unsupported "
+ "option features (%Lx).\n", features);
+ BUG_ON(1);
+ }
+
nodesize = btrfs_super_nodesize(disk_super);
leafsize = btrfs_super_leafsize(disk_super);
sectorsize = btrfs_super_sectorsize(disk_super);
@@ -704,19 +752,21 @@ struct btrfs_root *open_ctree_fd(int fp, const char *path, u64 sb_bytenr,
BUG_ON(ret);
csum_root->track_dirty = 1;
- ret = find_and_setup_root(tree_root, fs_info,
- BTRFS_FS_TREE_OBJECTID, root);
BUG_ON(ret);
- root->ref_cows = 1;
find_and_setup_log_root(tree_root, fs_info, disk_super);
- btrfs_read_block_groups(root);
+ btrfs_read_block_groups(fs_info->tree_root);
+
+ key.objectid = BTRFS_FS_TREE_OBJECTID;
+ key.type = BTRFS_ROOT_ITEM_KEY;
+ key.offset = (u64)-1;
+ fs_info->fs_root = btrfs_read_fs_root(fs_info, &key);
fs_info->data_alloc_profile = (u64)-1;
fs_info->metadata_alloc_profile = (u64)-1;
fs_info->system_alloc_profile = fs_info->metadata_alloc_profile;
- return root;
+ return fs_info->fs_root;
}
int btrfs_read_dev_super(int fd, struct btrfs_super_block *sb, u64 sb_bytenr)
@@ -891,27 +941,26 @@ int close_ctree(struct btrfs_root *root)
trans = btrfs_start_transaction(root, 1);
btrfs_commit_transaction(trans, root);
trans = btrfs_start_transaction(root, 1);
- ret = commit_tree_roots(trans, root->fs_info);
+ ret = commit_tree_roots(trans, fs_info);
BUG_ON(ret);
ret = __commit_transaction(trans, root);
BUG_ON(ret);
write_ctree_super(trans, root);
btrfs_free_transaction(root, trans);
- btrfs_free_block_groups(root->fs_info);
- if (root->node)
- free_extent_buffer(root->node);
- if (root->fs_info->extent_root->node)
- free_extent_buffer(root->fs_info->extent_root->node);
- if (root->fs_info->tree_root->node)
- free_extent_buffer(root->fs_info->tree_root->node);
- free_extent_buffer(root->commit_root);
+ btrfs_free_block_groups(fs_info);
+
+ free_fs_roots(fs_info);
- if (root->fs_info->chunk_root->node)
- free_extent_buffer(root->fs_info->chunk_root->node);
- if (root->fs_info->dev_root->node)
- free_extent_buffer(root->fs_info->dev_root->node);
- if (root->fs_info->csum_root->node)
- free_extent_buffer(root->fs_info->csum_root->node);
+ if (fs_info->extent_root->node)
+ free_extent_buffer(fs_info->extent_root->node);
+ if (fs_info->tree_root->node)
+ free_extent_buffer(fs_info->tree_root->node);
+ if (fs_info->chunk_root->node)
+ free_extent_buffer(fs_info->chunk_root->node);
+ if (fs_info->dev_root->node)
+ free_extent_buffer(fs_info->dev_root->node);
+ if (fs_info->csum_root->node)
+ free_extent_buffer(fs_info->csum_root->node);
if (root->fs_info->log_root_tree) {
if (root->fs_info->log_root_tree->node)
@@ -929,7 +978,6 @@ int close_ctree(struct btrfs_root *root)
free(fs_info->tree_root);
free(fs_info->extent_root);
- free(fs_info->fs_root);
free(fs_info->chunk_root);
free(fs_info->dev_root);
free(fs_info->csum_root);
diff --git a/disk-io.h b/disk-io.h
index d9a35afd..49e5692c 100644
--- a/disk-io.h
+++ b/disk-io.h
@@ -56,6 +56,8 @@ struct extent_buffer *btrfs_find_tree_block(struct btrfs_root *root,
u64 bytenr, u32 blocksize);
struct btrfs_root *btrfs_read_fs_root(struct btrfs_fs_info *fs_info,
struct btrfs_key *location);
+struct btrfs_root *btrfs_read_fs_root_no_cache(struct btrfs_fs_info *fs_info,
+ struct btrfs_key *location);
int btrfs_free_fs_root(struct btrfs_fs_info *fs_info, struct btrfs_root *root);
void btrfs_mark_buffer_dirty(struct extent_buffer *buf);
int btrfs_buffer_uptodate(struct extent_buffer *buf, u64 parent_transid);
diff --git a/extent-tree.c b/extent-tree.c
index d0ad017c..bc2fd616 100644
--- a/extent-tree.c
+++ b/extent-tree.c
@@ -41,26 +41,26 @@ struct pending_extent_op {
int type;
u64 bytenr;
u64 num_bytes;
- u64 parent;
- u64 orig_parent;
- u64 generation;
- u64 orig_generation;
+ u64 flags;
+ struct btrfs_disk_key key;
int level;
};
+static int alloc_reserved_tree_block(struct btrfs_trans_handle *trans,
+ struct btrfs_root *root,
+ u64 root_objectid, u64 generation,
+ u64 flags, struct btrfs_disk_key *key,
+ int level, struct btrfs_key *ins);
+static int __free_extent(struct btrfs_trans_handle *trans,
+ struct btrfs_root *root,
+ u64 bytenr, u64 num_bytes, u64 parent,
+ u64 root_objectid, u64 owner_objectid,
+ u64 owner_offset, int refs_to_drop);
static int finish_current_insert(struct btrfs_trans_handle *trans, struct
btrfs_root *extent_root);
static int del_pending_extents(struct btrfs_trans_handle *trans, struct
btrfs_root *extent_root);
-void maybe_lock_mutex(struct btrfs_root *root)
-{
-}
-
-void maybe_unlock_mutex(struct btrfs_root *root)
-{
-}
-
static int remove_sb_from_cache(struct btrfs_root *root,
struct btrfs_block_group_cache *cache)
{
@@ -435,362 +435,990 @@ found:
* maintenance. This is actually the same as #2, but with a slightly
* different use case.
*
+ * There are two kinds of back refs. The implicit back refs is optimized
+ * for pointers in non-shared tree blocks. For a given pointer in a block,
+ * back refs of this kind provide information about the block's owner tree
+ * and the pointer's key. These information allow us to find the block by
+ * b-tree searching. The full back refs is for pointers in tree blocks not
+ * referenced by their owner trees. The location of tree block is recorded
+ * in the back refs. Actually the full back refs is generic, and can be
+ * used in all cases the implicit back refs is used. The major shortcoming
+ * of the full back refs is its overhead. Every time a tree block gets
+ * COWed, we have to update back refs entry for all pointers in it.
+ *
+ * For a newly allocated tree block, we use implicit back refs for
+ * pointers in it. This means most tree related operations only involve
+ * implicit back refs. For a tree block created in old transaction, the
+ * only way to drop a reference to it is COW it. So we can detect the
+ * event that tree block loses its owner tree's reference and do the
+ * back refs conversion.
+ *
+ * When a tree block is COW'd through a tree, there are four cases:
+ *
+ * The reference count of the block is one and the tree is the block's
+ * owner tree. Nothing to do in this case.
+ *
+ * The reference count of the block is one and the tree is not the
+ * block's owner tree. In this case, full back refs is used for pointers
+ * in the block. Remove these full back refs, add implicit back refs for
+ * every pointers in the new block.
+ *
+ * The reference count of the block is greater than one and the tree is
+ * the block's owner tree. In this case, implicit back refs is used for
+ * pointers in the block. Add full back refs for every pointers in the
+ * block, increase lower level extents' reference counts. The original
+ * implicit back refs are entailed to the new block.
+ *
+ * The reference count of the block is greater than one and the tree is
+ * not the block's owner tree. Add implicit back refs for every pointer in
+ * the new block, increase lower level extents' reference count.
+ *
+ * Back Reference Key composing:
+ *
+ * The key objectid corresponds to the first byte in the extent,
+ * The key type is used to differentiate between types of back refs.
+ * There are different meanings of the key offset for different types
+ * of back refs.
+ *
* File extents can be referenced by:
*
* - multiple snapshots, subvolumes, or different generations in one subvol
* - different files inside a single subvolume
* - different offsets inside a file (bookend extents in file.c)
*
- * The extent ref structure has fields for:
+ * The extent ref structure for the implicit back refs has fields for:
*
* - Objectid of the subvolume root
- * - Generation number of the tree holding the reference
* - objectid of the file holding the reference
- * - offset in the file corresponding to the key holding the reference
- * - number of references holding by parent node (alway 1 for tree blocks)
+ * - original offset in the file
+ * - how many bookend extents
*
- * Btree leaf may hold multiple references to a file extent. In most cases,
- * these references are from same file and the corresponding offsets inside
- * the file are close together. So inode objectid and offset in file are
- * just hints, they provide hints about where in the btree the references
- * can be found and when we can stop searching.
+ * The key offset for the implicit back refs is hash of the first
+ * three fields.
*
- * When a file extent is allocated the fields are filled in:
- * (root_key.objectid, trans->transid, inode objectid, offset in file, 1)
+ * The extent ref structure for the full back refs has field for:
*
- * When a leaf is cow'd new references are added for every file extent found
- * in the leaf. It looks similar to the create case, but trans->transid will
- * be different when the block is cow'd.
+ * - number of pointers in the tree leaf
*
- * (root_key.objectid, trans->transid, inode objectid, offset in file,
- * number of references in the leaf)
+ * The key offset for the implicit back refs is the first byte of
+ * the tree leaf
*
- * Because inode objectid and offset in file are just hints, they are not
- * used when backrefs are deleted. When a file extent is removed either
- * during snapshot deletion or file truncation, we find the corresponding
- * back back reference and check the following fields.
+ * When a file extent is allocated, The implicit back refs is used.
+ * the fields are filled in:
*
- * (btrfs_header_owner(leaf), btrfs_header_generation(leaf))
+ * (root_key.objectid, inode objectid, offset in file, 1)
*
- * Btree extents can be referenced by:
- *
- * - Different subvolumes
- * - Different generations of the same subvolume
+ * When a file extent is removed file truncation, we find the
+ * corresponding implicit back refs and check the following fields:
*
- * When a tree block is created, back references are inserted:
+ * (btrfs_header_owner(leaf), inode objectid, offset in file)
*
- * (root->root_key.objectid, trans->transid, level, 0, 1)
- *
- * When a tree block is cow'd, new back references are added for all the
- * blocks it points to. If the tree block isn't in reference counted root,
- * the old back references are removed. These new back references are of
- * the form (trans->transid will have increased since creation):
- *
- * (root->root_key.objectid, trans->transid, level, 0, 1)
- *
- * When a backref is in deleting, the following fields are checked:
+ * Btree extents can be referenced by:
*
- * if backref was for a tree root:
- * (btrfs_header_owner(itself), btrfs_header_generation(itself))
- * else
- * (btrfs_header_owner(parent), btrfs_header_generation(parent))
+ * - Different subvolumes
*
- * Back Reference Key composing:
+ * Both the implicit back refs and the full back refs for tree blocks
+ * only consist of key. The key offset for the implicit back refs is
+ * objectid of block's owner tree. The key offset for the full back refs
+ * is the first byte of parent block.
*
- * The key objectid corresponds to the first byte in the extent, the key
- * type is set to BTRFS_EXTENT_REF_KEY, and the key offset is the first
- * byte of parent extent. If a extent is tree root, the key offset is set
- * to the key objectid.
+ * When implicit back refs is used, information about the lowest key and
+ * level of the tree block are required. These information are stored in
+ * tree block info structure.
*/
-static int noinline lookup_extent_backref(struct btrfs_trans_handle *trans,
- struct btrfs_root *root,
- struct btrfs_path *path,
- u64 bytenr, u64 parent,
- u64 ref_root, u64 ref_generation,
- u64 owner_objectid, int del)
+#ifdef BTRFS_COMPAT_EXTENT_TREE_V0
+static int convert_extent_item_v0(struct btrfs_trans_handle *trans,
+ struct btrfs_root *root,
+ struct btrfs_path *path,
+ u64 owner, u32 extra_size)
{
+ struct btrfs_extent_item *item;
+ struct btrfs_extent_item_v0 *ei0;
+ struct btrfs_extent_ref_v0 *ref0;
+ struct btrfs_tree_block_info *bi;
+ struct extent_buffer *leaf;
struct btrfs_key key;
- struct btrfs_extent_ref *ref;
+ struct btrfs_key found_key;
+ u32 new_size = sizeof(*item);
+ u64 refs;
+ int ret;
+
+ leaf = path->nodes[0];
+ BUG_ON(btrfs_item_size_nr(leaf, path->slots[0]) != sizeof(*ei0));
+
+ btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);
+ ei0 = btrfs_item_ptr(leaf, path->slots[0],
+ struct btrfs_extent_item_v0);
+ refs = btrfs_extent_refs_v0(leaf, ei0);
+
+ if (owner == (u64)-1) {
+ while (1) {
+ if (path->slots[0] >= btrfs_header_nritems(leaf)) {
+ ret = btrfs_next_leaf(root, path);
+ if (ret < 0)
+ return ret;
+ BUG_ON(ret > 0);
+ leaf = path->nodes[0];
+ }
+ btrfs_item_key_to_cpu(leaf, &found_key,
+ path->slots[0]);
+ BUG_ON(key.objectid != found_key.objectid);
+ if (found_key.type != BTRFS_EXTENT_REF_V0_KEY) {
+ path->slots[0]++;
+ continue;
+ }
+ ref0 = btrfs_item_ptr(leaf, path->slots[0],
+ struct btrfs_extent_ref_v0);
+ owner = btrfs_ref_objectid_v0(leaf, ref0);
+ break;
+ }
+ }
+ btrfs_release_path(root, path);
+
+ if (owner < BTRFS_FIRST_FREE_OBJECTID)
+ new_size += sizeof(*bi);
+
+ new_size -= sizeof(*ei0);
+ ret = btrfs_search_slot(trans, root, &key, path, new_size, 1);
+ if (ret < 0)
+ return ret;
+ BUG_ON(ret);
+
+ ret = btrfs_extend_item(trans, root, path, new_size);
+ BUG_ON(ret);
+
+ leaf = path->nodes[0];
+ item = btrfs_item_ptr(leaf, path->slots[0], struct btrfs_extent_item);
+ btrfs_set_extent_refs(leaf, item, refs);
+ /* FIXME: get real generation */
+ btrfs_set_extent_generation(leaf, item, 0);
+ if (owner < BTRFS_FIRST_FREE_OBJECTID) {
+ btrfs_set_extent_flags(leaf, item,
+ BTRFS_EXTENT_FLAG_TREE_BLOCK |
+ BTRFS_BLOCK_FLAG_FULL_BACKREF);
+ bi = (struct btrfs_tree_block_info *)(item + 1);
+ /* FIXME: get first key of the block */
+ memset_extent_buffer(leaf, 0, (unsigned long)bi, sizeof(*bi));
+ btrfs_set_tree_block_level(leaf, bi, (int)owner);
+ } else {
+ btrfs_set_extent_flags(leaf, item, BTRFS_EXTENT_FLAG_DATA);
+ }
+ btrfs_mark_buffer_dirty(leaf);
+ return 0;
+}
+#endif
+
+static u64 hash_extent_data_ref(u64 root_objectid, u64 owner, u64 offset)
+{
+ u32 high_crc = ~(u32)0;
+ u32 low_crc = ~(u32)0;
+ __le64 lenum;
+
+ lenum = cpu_to_le64(root_objectid);
+ high_crc = btrfs_crc32c(high_crc, &lenum, sizeof(lenum));
+ lenum = cpu_to_le64(owner);
+ low_crc = btrfs_crc32c(low_crc, &lenum, sizeof(lenum));
+ lenum = cpu_to_le64(offset);
+ low_crc = btrfs_crc32c(low_crc, &lenum, sizeof(lenum));
+
+ return ((u64)high_crc << 31) ^ (u64)low_crc;
+}
+
+static u64 hash_extent_data_ref_item(struct extent_buffer *leaf,
+ struct btrfs_extent_data_ref *ref)
+{
+ return hash_extent_data_ref(btrfs_extent_data_ref_root(leaf, ref),
+ btrfs_extent_data_ref_objectid(leaf, ref),
+ btrfs_extent_data_ref_offset(leaf, ref));
+}
+
+static int match_extent_data_ref(struct extent_buffer *leaf,
+ struct btrfs_extent_data_ref *ref,
+ u64 root_objectid, u64 owner, u64 offset)
+{
+ if (btrfs_extent_data_ref_root(leaf, ref) != root_objectid ||
+ btrfs_extent_data_ref_objectid(leaf, ref) != owner ||
+ btrfs_extent_data_ref_offset(leaf, ref) != offset)
+ return 0;
+ return 1;
+}
+
+static noinline int lookup_extent_data_ref(struct btrfs_trans_handle *trans,
+ struct btrfs_root *root,
+ struct btrfs_path *path,
+ u64 bytenr, u64 parent,
+ u64 root_objectid,
+ u64 owner, u64 offset)
+{
+ struct btrfs_key key;
+ struct btrfs_extent_data_ref *ref;
struct extent_buffer *leaf;
- u64 ref_objectid;
+ u32 nritems;
int ret;
+ int recow;
+ int err = -ENOENT;
key.objectid = bytenr;
- key.type = BTRFS_EXTENT_REF_KEY;
- key.offset = parent;
+ if (parent) {
+ key.type = BTRFS_SHARED_DATA_REF_KEY;
+ key.offset = parent;
+ } else {
+ key.type = BTRFS_EXTENT_DATA_REF_KEY;
+ key.offset = hash_extent_data_ref(root_objectid,
+ owner, offset);
+ }
+again:
+ recow = 0;
+ ret = btrfs_search_slot(trans, root, &key, path, -1, 1);
+ if (ret < 0) {
+ err = ret;
+ goto fail;
+ }
- ret = btrfs_search_slot(trans, root, &key, path, del ? -1 : 0, 1);
- if (ret < 0)
- goto out;
- if (ret > 0) {
- ret = -ENOENT;
- goto out;
+ if (parent) {
+ if (!ret)
+ return 0;
+#ifdef BTRFS_COMPAT_EXTENT_TREE_V0
+ key.type = BTRFS_EXTENT_REF_V0_KEY;
+ btrfs_release_path(root, path);
+ ret = btrfs_search_slot(trans, root, &key, path, -1, 1);
+ if (ret < 0) {
+ err = ret;
+ goto fail;
+ }
+ if (!ret)
+ return 0;
+#endif
+ goto fail;
}
leaf = path->nodes[0];
- ref = btrfs_item_ptr(leaf, path->slots[0], struct btrfs_extent_ref);
- ref_objectid = btrfs_ref_objectid(leaf, ref);
- if (btrfs_ref_root(leaf, ref) != ref_root ||
- btrfs_ref_generation(leaf, ref) != ref_generation ||
- (ref_objectid != owner_objectid &&
- ref_objectid != BTRFS_MULTIPLE_OBJECTIDS)) {
- ret = -EIO;
- WARN_ON(1);
- goto out;
+ nritems = btrfs_header_nritems(leaf);
+ while (1) {
+ if (path->slots[0] >= nritems) {
+ ret = btrfs_next_leaf(root, path);
+ if (ret < 0)
+ err = ret;
+ if (ret)
+ goto fail;
+
+ leaf = path->nodes[0];
+ nritems = btrfs_header_nritems(leaf);
+ recow = 1;
+ }
+
+ btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);
+ if (key.objectid != bytenr ||
+ key.type != BTRFS_EXTENT_DATA_REF_KEY)
+ goto fail;
+
+ ref = btrfs_item_ptr(leaf, path->slots[0],
+ struct btrfs_extent_data_ref);
+
+ if (match_extent_data_ref(leaf, ref, root_objectid,
+ owner, offset)) {
+ if (recow) {
+ btrfs_release_path(root, path);
+ goto again;
+ }
+ err = 0;
+ break;
+ }
+ path->slots[0]++;
}
- ret = 0;
-out:
- return ret;
+fail:
+ return err;
}
-static int noinline insert_extent_backref(struct btrfs_trans_handle *trans,
- struct btrfs_root *root,
- struct btrfs_path *path,
- u64 bytenr, u64 parent,
- u64 ref_root, u64 ref_generation,
- u64 owner_objectid)
+static noinline int insert_extent_data_ref(struct btrfs_trans_handle *trans,
+ struct btrfs_root *root,
+ struct btrfs_path *path,
+ u64 bytenr, u64 parent,
+ u64 root_objectid, u64 owner,
+ u64 offset, int refs_to_add)
{
struct btrfs_key key;
struct extent_buffer *leaf;
- struct btrfs_extent_ref *ref;
+ u32 size;
u32 num_refs;
int ret;
key.objectid = bytenr;
- key.type = BTRFS_EXTENT_REF_KEY;
- key.offset = parent;
+ if (parent) {
+ key.type = BTRFS_SHARED_DATA_REF_KEY;
+ key.offset = parent;
+ size = sizeof(struct btrfs_shared_data_ref);
+ } else {
+ key.type = BTRFS_EXTENT_DATA_REF_KEY;
+ key.offset = hash_extent_data_ref(root_objectid,
+ owner, offset);
+ size = sizeof(struct btrfs_extent_data_ref);
+ }
- ret = btrfs_insert_empty_item(trans, root, path, &key, sizeof(*ref));
- if (ret == 0) {
- leaf = path->nodes[0];
- ref = btrfs_item_ptr(leaf, path->slots[0],
- struct btrfs_extent_ref);
- btrfs_set_ref_root(leaf, ref, ref_root);
- btrfs_set_ref_generation(leaf, ref, ref_generation);
- btrfs_set_ref_objectid(leaf, ref, owner_objectid);
- btrfs_set_ref_num_refs(leaf, ref, 1);
- } else if (ret == -EEXIST) {
- u64 existing_owner;
- BUG_ON(owner_objectid < BTRFS_FIRST_FREE_OBJECTID);
- leaf = path->nodes[0];
+ ret = btrfs_insert_empty_item(trans, root, path, &key, size);
+ if (ret && ret != -EEXIST)
+ goto fail;
+
+ leaf = path->nodes[0];
+ if (parent) {
+ struct btrfs_shared_data_ref *ref;
ref = btrfs_item_ptr(leaf, path->slots[0],
- struct btrfs_extent_ref);
- if (btrfs_ref_root(leaf, ref) != ref_root ||
- btrfs_ref_generation(leaf, ref) != ref_generation) {
- ret = -EIO;
- WARN_ON(1);
- goto out;
+ struct btrfs_shared_data_ref);
+ if (ret == 0) {
+ btrfs_set_shared_data_ref_count(leaf, ref, refs_to_add);
+ } else {
+ num_refs = btrfs_shared_data_ref_count(leaf, ref);
+ num_refs += refs_to_add;
+ btrfs_set_shared_data_ref_count(leaf, ref, num_refs);
}
+ } else {
+ struct btrfs_extent_data_ref *ref;
+ while (ret == -EEXIST) {
+ ref = btrfs_item_ptr(leaf, path->slots[0],
+ struct btrfs_extent_data_ref);
+ if (match_extent_data_ref(leaf, ref, root_objectid,
+ owner, offset))
+ break;
+ btrfs_release_path(root, path);
- num_refs = btrfs_ref_num_refs(leaf, ref);
- BUG_ON(num_refs == 0);
- btrfs_set_ref_num_refs(leaf, ref, num_refs + 1);
+ key.offset++;
+ ret = btrfs_insert_empty_item(trans, root, path, &key,
+ size);
+ if (ret && ret != -EEXIST)
+ goto fail;
- existing_owner = btrfs_ref_objectid(leaf, ref);
- if (existing_owner != owner_objectid &&
- existing_owner != BTRFS_MULTIPLE_OBJECTIDS) {
- btrfs_set_ref_objectid(leaf, ref,
- BTRFS_MULTIPLE_OBJECTIDS);
+ leaf = path->nodes[0];
+ }
+ ref = btrfs_item_ptr(leaf, path->slots[0],
+ struct btrfs_extent_data_ref);
+ if (ret == 0) {
+ btrfs_set_extent_data_ref_root(leaf, ref,
+ root_objectid);
+ btrfs_set_extent_data_ref_objectid(leaf, ref, owner);
+ btrfs_set_extent_data_ref_offset(leaf, ref, offset);
+ btrfs_set_extent_data_ref_count(leaf, ref, refs_to_add);
+ } else {
+ num_refs = btrfs_extent_data_ref_count(leaf, ref);
+ num_refs += refs_to_add;
+ btrfs_set_extent_data_ref_count(leaf, ref, num_refs);
}
- ret = 0;
- } else {
- goto out;
}
- btrfs_mark_buffer_dirty(path->nodes[0]);
-out:
+ btrfs_mark_buffer_dirty(leaf);
+ ret = 0;
+fail:
btrfs_release_path(root, path);
return ret;
}
-static int noinline remove_extent_backref(struct btrfs_trans_handle *trans,
- struct btrfs_root *root,
- struct btrfs_path *path)
+static noinline int remove_extent_data_ref(struct btrfs_trans_handle *trans,
+ struct btrfs_root *root,
+ struct btrfs_path *path,
+ int refs_to_drop)
{
+ struct btrfs_key key;
+ struct btrfs_extent_data_ref *ref1 = NULL;
+ struct btrfs_shared_data_ref *ref2 = NULL;
struct extent_buffer *leaf;
- struct btrfs_extent_ref *ref;
- u32 num_refs;
+ u32 num_refs = 0;
int ret = 0;
leaf = path->nodes[0];
- ref = btrfs_item_ptr(leaf, path->slots[0], struct btrfs_extent_ref);
- num_refs = btrfs_ref_num_refs(leaf, ref);
- BUG_ON(num_refs == 0);
- num_refs -= 1;
+ btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);
+
+ if (key.type == BTRFS_EXTENT_DATA_REF_KEY) {
+ ref1 = btrfs_item_ptr(leaf, path->slots[0],
+ struct btrfs_extent_data_ref);
+ num_refs = btrfs_extent_data_ref_count(leaf, ref1);
+ } else if (key.type == BTRFS_SHARED_DATA_REF_KEY) {
+ ref2 = btrfs_item_ptr(leaf, path->slots[0],
+ struct btrfs_shared_data_ref);
+ num_refs = btrfs_shared_data_ref_count(leaf, ref2);
+#ifdef BTRFS_COMPAT_EXTENT_TREE_V0
+ } else if (key.type == BTRFS_EXTENT_REF_V0_KEY) {
+ struct btrfs_extent_ref_v0 *ref0;
+ ref0 = btrfs_item_ptr(leaf, path->slots[0],
+ struct btrfs_extent_ref_v0);
+ num_refs = btrfs_ref_count_v0(leaf, ref0);
+#endif
+ } else {
+ BUG();
+ }
+
+ BUG_ON(num_refs < refs_to_drop);
+ num_refs -= refs_to_drop;
+
if (num_refs == 0) {
ret = btrfs_del_item(trans, root, path);
} else {
- btrfs_set_ref_num_refs(leaf, ref, num_refs);
+ if (key.type == BTRFS_EXTENT_DATA_REF_KEY)
+ btrfs_set_extent_data_ref_count(leaf, ref1, num_refs);
+ else if (key.type == BTRFS_SHARED_DATA_REF_KEY)
+ btrfs_set_shared_data_ref_count(leaf, ref2, num_refs);
+#ifdef BTRFS_COMPAT_EXTENT_TREE_V0
+ else {
+ struct btrfs_extent_ref_v0 *ref0;
+ ref0 = btrfs_item_ptr(leaf, path->slots[0],
+ struct btrfs_extent_ref_v0);
+ btrfs_set_ref_count_v0(leaf, ref0, num_refs);
+ }
+#endif
btrfs_mark_buffer_dirty(leaf);
}
- btrfs_release_path(root, path);
return ret;
}
-static int __btrfs_update_extent_ref(struct btrfs_trans_handle *trans,
- struct btrfs_root *root, u64 bytenr,
- u64 orig_parent, u64 parent,
- u64 orig_root, u64 ref_root,
- u64 orig_generation, u64 ref_generation,
- u64 owner_objectid)
+static noinline u32 extent_data_ref_count(struct btrfs_root *root,
+ struct btrfs_path *path,
+ struct btrfs_extent_inline_ref *iref)
{
- int ret;
- struct btrfs_root *extent_root = root->fs_info->extent_root;
- struct btrfs_path *path;
+ struct btrfs_key key;
+ struct extent_buffer *leaf;
+ struct btrfs_extent_data_ref *ref1;
+ struct btrfs_shared_data_ref *ref2;
+ u32 num_refs = 0;
- if (root == root->fs_info->extent_root) {
- struct pending_extent_op *extent_op;
- u64 num_bytes;
-
- BUG_ON(owner_objectid >= BTRFS_MAX_LEVEL);
- num_bytes = btrfs_level_size(root, (int)owner_objectid);
- if (test_range_bit(&root->fs_info->extent_ins, bytenr,
- bytenr + num_bytes - 1, EXTENT_LOCKED, 0)) {
- u64 priv;
- ret = get_state_private(&root->fs_info->extent_ins,
- bytenr, &priv);
- BUG_ON(ret);
- extent_op = (struct pending_extent_op *)
- (unsigned long)priv;
- BUG_ON(extent_op->parent != orig_parent);
- BUG_ON(extent_op->generation != orig_generation);
- extent_op->parent = parent;
- extent_op->generation = ref_generation;
+ leaf = path->nodes[0];
+ btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);
+ if (iref) {
+ if (btrfs_extent_inline_ref_type(leaf, iref) ==
+ BTRFS_EXTENT_DATA_REF_KEY) {
+ ref1 = (struct btrfs_extent_data_ref *)(&iref->offset);
+ num_refs = btrfs_extent_data_ref_count(leaf, ref1);
} else {
- extent_op = kmalloc(sizeof(*extent_op), GFP_NOFS);
- BUG_ON(!extent_op);
-
- extent_op->type = PENDING_BACKREF_UPDATE;
- extent_op->bytenr = bytenr;
- extent_op->num_bytes = num_bytes;
- extent_op->parent = parent;
- extent_op->orig_parent = orig_parent;
- extent_op->generation = ref_generation;
- extent_op->orig_generation = orig_generation;
- extent_op->level = (int)owner_objectid;
-
- set_extent_bits(&root->fs_info->extent_ins,
- bytenr, bytenr + num_bytes - 1,
- EXTENT_LOCKED, GFP_NOFS);
- set_state_private(&root->fs_info->extent_ins,
- bytenr, (unsigned long)extent_op);
+ ref2 = (struct btrfs_shared_data_ref *)(iref + 1);
+ num_refs = btrfs_shared_data_ref_count(leaf, ref2);
}
+ } else if (key.type == BTRFS_EXTENT_DATA_REF_KEY) {
+ ref1 = btrfs_item_ptr(leaf, path->slots[0],
+ struct btrfs_extent_data_ref);
+ num_refs = btrfs_extent_data_ref_count(leaf, ref1);
+ } else if (key.type == BTRFS_SHARED_DATA_REF_KEY) {
+ ref2 = btrfs_item_ptr(leaf, path->slots[0],
+ struct btrfs_shared_data_ref);
+ num_refs = btrfs_shared_data_ref_count(leaf, ref2);
+#ifdef BTRFS_COMPAT_EXTENT_TREE_V0
+ } else if (key.type == BTRFS_EXTENT_REF_V0_KEY) {
+ struct btrfs_extent_ref_v0 *ref0;
+ ref0 = btrfs_item_ptr(leaf, path->slots[0],
+ struct btrfs_extent_ref_v0);
+ num_refs = btrfs_ref_count_v0(leaf, ref0);
+#endif
+ } else {
+ BUG();
+ }
+ return num_refs;
+}
+
+static noinline int lookup_tree_block_ref(struct btrfs_trans_handle *trans,
+ struct btrfs_root *root,
+ struct btrfs_path *path,
+ u64 bytenr, u64 parent,
+ u64 root_objectid)
+{
+ struct btrfs_key key;
+ int ret;
+
+ key.objectid = bytenr;
+ if (parent) {
+ key.type = BTRFS_SHARED_BLOCK_REF_KEY;
+ key.offset = parent;
+ } else {
+ key.type = BTRFS_TREE_BLOCK_REF_KEY;
+ key.offset = root_objectid;
+ }
+
+ ret = btrfs_search_slot(trans, root, &key, path, -1, 1);
+ if (ret > 0)
+ ret = -ENOENT;
+#ifdef BTRFS_COMPAT_EXTENT_TREE_V0
+ if (ret == -ENOENT && parent) {
+ btrfs_release_path(root, path);
+ key.type = BTRFS_EXTENT_REF_V0_KEY;
+ ret = btrfs_search_slot(trans, root, &key, path, -1, 1);
+ if (ret > 0)
+ ret = -ENOENT;
+ }
+#endif
+ return ret;
+}
+
+static noinline int insert_tree_block_ref(struct btrfs_trans_handle *trans,
+ struct btrfs_root *root,
+ struct btrfs_path *path,
+ u64 bytenr, u64 parent,
+ u64 root_objectid)
+{
+ struct btrfs_key key;
+ int ret;
+
+ key.objectid = bytenr;
+ if (parent) {
+ key.type = BTRFS_SHARED_BLOCK_REF_KEY;
+ key.offset = parent;
+ } else {
+ key.type = BTRFS_TREE_BLOCK_REF_KEY;
+ key.offset = root_objectid;
+ }
+
+ ret = btrfs_insert_empty_item(trans, root, path, &key, 0);
+
+ btrfs_release_path(root, path);
+ return ret;
+}
+
+static inline int extent_ref_type(u64 parent, u64 owner)
+{
+ if (owner < BTRFS_FIRST_FREE_OBJECTID) {
+ if (parent > 0)
+ return BTRFS_SHARED_BLOCK_REF_KEY;
+ else
+ return BTRFS_TREE_BLOCK_REF_KEY;
+ } else {
+ if (parent > 0)
+ return BTRFS_SHARED_DATA_REF_KEY;
+ else
+ return BTRFS_EXTENT_DATA_REF_KEY;
+ }
+}
+
+static int find_next_key(struct btrfs_path *path, struct btrfs_key *key)
+
+{
+ int level;
+ for (level = 0; level < BTRFS_MAX_LEVEL; level++) {
+ if (!path->nodes[level])
+ break;
+ if (path->slots[level] + 1 >=
+ btrfs_header_nritems(path->nodes[level]))
+ continue;
+ if (level == 0)
+ btrfs_item_key_to_cpu(path->nodes[level], key,
+ path->slots[level] + 1);
+ else
+ btrfs_node_key_to_cpu(path->nodes[level], key,
+ path->slots[level] + 1);
return 0;
}
+ return 1;
+}
- path = btrfs_alloc_path();
- if (!path)
- return -ENOMEM;
- ret = lookup_extent_backref(trans, extent_root, path,
- bytenr, orig_parent, orig_root,
- orig_generation, owner_objectid, 1);
- if (ret)
- goto out;
- ret = remove_extent_backref(trans, extent_root, path);
- if (ret)
+static int lookup_inline_extent_backref(struct btrfs_trans_handle *trans,
+ struct btrfs_root *root,
+ struct btrfs_path *path,
+ struct btrfs_extent_inline_ref **ref_ret,
+ u64 bytenr, u64 num_bytes,
+ u64 parent, u64 root_objectid,
+ u64 owner, u64 offset, int insert)
+{
+ struct btrfs_key key;
+ struct extent_buffer *leaf;
+ struct btrfs_extent_item *ei;
+ struct btrfs_extent_inline_ref *iref;
+ u64 flags;
+ u32 item_size;
+ unsigned long ptr;
+ unsigned long end;
+ int extra_size;
+ int type;
+ int want;
+ int ret;
+ int err = 0;
+
+ key.objectid = bytenr;
+ key.type = BTRFS_EXTENT_ITEM_KEY;
+ key.offset = num_bytes;
+
+ want = extent_ref_type(parent, owner);
+ if (insert)
+ extra_size = btrfs_extent_inline_ref_size(want);
+ else
+ extra_size = -1;
+ ret = btrfs_search_slot(trans, root, &key, path, extra_size, 1);
+ if (ret < 0) {
+ err = ret;
goto out;
- ret = insert_extent_backref(trans, extent_root, path, bytenr,
- parent, ref_root, ref_generation,
- owner_objectid);
+ }
BUG_ON(ret);
- finish_current_insert(trans, extent_root);
- del_pending_extents(trans, extent_root);
+
+ leaf = path->nodes[0];
+ item_size = btrfs_item_size_nr(leaf, path->slots[0]);
+#ifdef BTRFS_COMPAT_EXTENT_TREE_V0
+ if (item_size < sizeof(*ei)) {
+ if (!insert) {
+ err = -ENOENT;
+ goto out;
+ }
+ ret = convert_extent_item_v0(trans, root, path, owner,
+ extra_size);
+ if (ret < 0) {
+ err = ret;
+ goto out;
+ }
+ leaf = path->nodes[0];
+ item_size = btrfs_item_size_nr(leaf, path->slots[0]);
+ }
+#endif
+ BUG_ON(item_size < sizeof(*ei));
+
+ if (owner < BTRFS_FIRST_FREE_OBJECTID && insert &&
+ item_size + extra_size >= BTRFS_MAX_EXTENT_ITEM_SIZE(root)) {
+ err = -EAGAIN;
+ goto out;
+ }
+
+ ei = btrfs_item_ptr(leaf, path->slots[0], struct btrfs_extent_item);
+ flags = btrfs_extent_flags(leaf, ei);
+
+ ptr = (unsigned long)(ei + 1);
+ end = (unsigned long)ei + item_size;
+
+ if (flags & BTRFS_EXTENT_FLAG_TREE_BLOCK) {
+ ptr += sizeof(struct btrfs_tree_block_info);
+ BUG_ON(ptr > end);
+ } else {
+ BUG_ON(!(flags & BTRFS_EXTENT_FLAG_DATA));
+ }
+
+ err = -ENOENT;
+ while (1) {
+ if (ptr >= end) {
+ WARN_ON(ptr > end);
+ break;
+ }
+ iref = (struct btrfs_extent_inline_ref *)ptr;
+ type = btrfs_extent_inline_ref_type(leaf, iref);
+ if (want < type)
+ break;
+ if (want > type) {
+ ptr += btrfs_extent_inline_ref_size(type);
+ continue;
+ }
+
+ if (type == BTRFS_EXTENT_DATA_REF_KEY) {
+ struct btrfs_extent_data_ref *dref;
+ dref = (struct btrfs_extent_data_ref *)(&iref->offset);
+ if (match_extent_data_ref(leaf, dref, root_objectid,
+ owner, offset)) {
+ err = 0;
+ break;
+ }
+ if (hash_extent_data_ref_item(leaf, dref) <
+ hash_extent_data_ref(root_objectid, owner, offset))
+ break;
+ } else {
+ u64 ref_offset;
+ ref_offset = btrfs_extent_inline_ref_offset(leaf, iref);
+ if (parent > 0) {
+ if (parent == ref_offset) {
+ err = 0;
+ break;
+ }
+ if (ref_offset < parent)
+ break;
+ } else {
+ if (root_objectid == ref_offset) {
+ err = 0;
+ break;
+ }
+ if (ref_offset < root_objectid)
+ break;
+ }
+ }
+ ptr += btrfs_extent_inline_ref_size(type);
+ }
+ if (err == -ENOENT && insert) {
+ if (item_size + extra_size >=
+ BTRFS_MAX_EXTENT_ITEM_SIZE(root)) {
+ err = -EAGAIN;
+ goto out;
+ }
+ /*
+ * To add new inline back ref, we have to make sure
+ * there is no corresponding back ref item.
+ * For simplicity, we just do not add new inline back
+ * ref if there is any back ref item.
+ */
+ if (owner >= BTRFS_FIRST_FREE_OBJECTID &&
+ find_next_key(path, &key) == 0 && key.objectid == bytenr) {
+ err = -EAGAIN;
+ goto out;
+ }
+ }
+ *ref_ret = (struct btrfs_extent_inline_ref *)ptr;
out:
- btrfs_free_path(path);
+ return err;
+}
+
+static int setup_inline_extent_backref(struct btrfs_trans_handle *trans,
+ struct btrfs_root *root,
+ struct btrfs_path *path,
+ struct btrfs_extent_inline_ref *iref,
+ u64 parent, u64 root_objectid,
+ u64 owner, u64 offset, int refs_to_add)
+{
+ struct extent_buffer *leaf;
+ struct btrfs_extent_item *ei;
+ unsigned long ptr;
+ unsigned long end;
+ unsigned long item_offset;
+ u64 refs;
+ int size;
+ int type;
+ int ret;
+
+ leaf = path->nodes[0];
+ ei = btrfs_item_ptr(leaf, path->slots[0], struct btrfs_extent_item);
+ item_offset = (unsigned long)iref - (unsigned long)ei;
+
+ type = extent_ref_type(parent, owner);
+ size = btrfs_extent_inline_ref_size(type);
+
+ ret = btrfs_extend_item(trans, root, path, size);
+ BUG_ON(ret);
+
+ ei = btrfs_item_ptr(leaf, path->slots[0], struct btrfs_extent_item);
+ refs = btrfs_extent_refs(leaf, ei);
+ refs += refs_to_add;
+ btrfs_set_extent_refs(leaf, ei, refs);
+
+ ptr = (unsigned long)ei + item_offset;
+ end = (unsigned long)ei + btrfs_item_size_nr(leaf, path->slots[0]);
+ if (ptr < end - size)
+ memmove_extent_buffer(leaf, ptr + size, ptr,
+ end - size - ptr);
+
+ iref = (struct btrfs_extent_inline_ref *)ptr;
+ btrfs_set_extent_inline_ref_type(leaf, iref, type);
+ if (type == BTRFS_EXTENT_DATA_REF_KEY) {
+ struct btrfs_extent_data_ref *dref;
+ dref = (struct btrfs_extent_data_ref *)(&iref->offset);
+ btrfs_set_extent_data_ref_root(leaf, dref, root_objectid);
+ btrfs_set_extent_data_ref_objectid(leaf, dref, owner);
+ btrfs_set_extent_data_ref_offset(leaf, dref, offset);
+ btrfs_set_extent_data_ref_count(leaf, dref, refs_to_add);
+ } else if (type == BTRFS_SHARED_DATA_REF_KEY) {
+ struct btrfs_shared_data_ref *sref;
+ sref = (struct btrfs_shared_data_ref *)(iref + 1);
+ btrfs_set_shared_data_ref_count(leaf, sref, refs_to_add);
+ btrfs_set_extent_inline_ref_offset(leaf, iref, parent);
+ } else if (type == BTRFS_SHARED_BLOCK_REF_KEY) {
+ btrfs_set_extent_inline_ref_offset(leaf, iref, parent);
+ } else {
+ btrfs_set_extent_inline_ref_offset(leaf, iref, root_objectid);
+ }
+ btrfs_mark_buffer_dirty(leaf);
+ return 0;
+}
+
+static int lookup_extent_backref(struct btrfs_trans_handle *trans,
+ struct btrfs_root *root,
+ struct btrfs_path *path,
+ struct btrfs_extent_inline_ref **ref_ret,
+ u64 bytenr, u64 num_bytes, u64 parent,
+ u64 root_objectid, u64 owner, u64 offset)
+{
+ int ret;
+
+ ret = lookup_inline_extent_backref(trans, root, path, ref_ret,
+ bytenr, num_bytes, parent,
+ root_objectid, owner, offset, 0);
+ if (ret != -ENOENT)
+ return ret;
+
+ btrfs_release_path(root, path);
+ *ref_ret = NULL;
+
+ if (owner < BTRFS_FIRST_FREE_OBJECTID) {
+ ret = lookup_tree_block_ref(trans, root, path, bytenr, parent,
+ root_objectid);
+ } else {
+ ret = lookup_extent_data_ref(trans, root, path, bytenr, parent,
+ root_objectid, owner, offset);
+ }
return ret;
}
-int btrfs_update_extent_ref(struct btrfs_trans_handle *trans,
- struct btrfs_root *root, u64 bytenr,
- u64 orig_parent, u64 parent,
- u64 ref_root, u64 ref_generation,
- u64 owner_objectid)
+static int update_inline_extent_backref(struct btrfs_trans_handle *trans,
+ struct btrfs_root *root,
+ struct btrfs_path *path,
+ struct btrfs_extent_inline_ref *iref,
+ int refs_to_mod)
{
+ struct extent_buffer *leaf;
+ struct btrfs_extent_item *ei;
+ struct btrfs_extent_data_ref *dref = NULL;
+ struct btrfs_shared_data_ref *sref = NULL;
+ unsigned long ptr;
+ unsigned long end;
+ u32 item_size;
+ int size;
+ int type;
int ret;
- if (ref_root == BTRFS_TREE_LOG_OBJECTID &&
- owner_objectid < BTRFS_FIRST_FREE_OBJECTID)
- return 0;
- maybe_lock_mutex(root);
- ret = __btrfs_update_extent_ref(trans, root, bytenr, orig_parent,
- parent, ref_root, ref_root,
- ref_generation, ref_generation,
- owner_objectid);
- maybe_unlock_mutex(root);
+ u64 refs;
+
+ leaf = path->nodes[0];
+ ei = btrfs_item_ptr(leaf, path->slots[0], struct btrfs_extent_item);
+ refs = btrfs_extent_refs(leaf, ei);
+ WARN_ON(refs_to_mod < 0 && refs + refs_to_mod <= 0);
+ refs += refs_to_mod;
+ btrfs_set_extent_refs(leaf, ei, refs);
+
+ type = btrfs_extent_inline_ref_type(leaf, iref);
+
+ if (type == BTRFS_EXTENT_DATA_REF_KEY) {
+ dref = (struct btrfs_extent_data_ref *)(&iref->offset);
+ refs = btrfs_extent_data_ref_count(leaf, dref);
+ } else if (type == BTRFS_SHARED_DATA_REF_KEY) {
+ sref = (struct btrfs_shared_data_ref *)(iref + 1);
+ refs = btrfs_shared_data_ref_count(leaf, sref);
+ } else {
+ refs = 1;
+ BUG_ON(refs_to_mod != -1);
+ }
+
+ BUG_ON(refs_to_mod < 0 && refs < -refs_to_mod);
+ refs += refs_to_mod;
+
+ if (refs > 0) {
+ if (type == BTRFS_EXTENT_DATA_REF_KEY)
+ btrfs_set_extent_data_ref_count(leaf, dref, refs);
+ else
+ btrfs_set_shared_data_ref_count(leaf, sref, refs);
+ } else {
+ size = btrfs_extent_inline_ref_size(type);
+ item_size = btrfs_item_size_nr(leaf, path->slots[0]);
+ ptr = (unsigned long)iref;
+ end = (unsigned long)ei + item_size;
+ if (ptr + size < end)
+ memmove_extent_buffer(leaf, ptr, ptr + size,
+ end - ptr - size);
+ item_size -= size;
+ ret = btrfs_truncate_item(trans, root, path, item_size, 1);
+ BUG_ON(ret);
+ }
+ btrfs_mark_buffer_dirty(leaf);
+ return 0;
+}
+
+static int insert_inline_extent_backref(struct btrfs_trans_handle *trans,
+ struct btrfs_root *root,
+ struct btrfs_path *path,
+ u64 bytenr, u64 num_bytes, u64 parent,
+ u64 root_objectid, u64 owner,
+ u64 offset, int refs_to_add)
+{
+ struct btrfs_extent_inline_ref *iref;
+ int ret;
+
+ ret = lookup_inline_extent_backref(trans, root, path, &iref,
+ bytenr, num_bytes, parent,
+ root_objectid, owner, offset, 1);
+ if (ret == 0) {
+ BUG_ON(owner < BTRFS_FIRST_FREE_OBJECTID);
+ ret = update_inline_extent_backref(trans, root, path, iref,
+ refs_to_add);
+ } else if (ret == -ENOENT) {
+ ret = setup_inline_extent_backref(trans, root, path, iref,
+ parent, root_objectid,
+ owner, offset, refs_to_add);
+ }
return ret;
}
-static int __btrfs_inc_extent_ref(struct btrfs_trans_handle *trans,
- struct btrfs_root *root, u64 bytenr,
- u64 orig_parent, u64 parent,
- u64 orig_root, u64 ref_root,
- u64 orig_generation, u64 ref_generation,
- u64 owner_objectid)
+static int insert_extent_backref(struct btrfs_trans_handle *trans,
+ struct btrfs_root *root,
+ struct btrfs_path *path,
+ u64 bytenr, u64 parent, u64 root_objectid,
+ u64 owner, u64 offset, int refs_to_add)
{
- struct btrfs_path *path;
int ret;
- struct btrfs_key key;
- struct extent_buffer *l;
+
+ if (owner >= BTRFS_FIRST_FREE_OBJECTID) {
+ ret = insert_extent_data_ref(trans, root, path, bytenr,
+ parent, root_objectid,
+ owner, offset, refs_to_add);
+ } else {
+ BUG_ON(refs_to_add != 1);
+ ret = insert_tree_block_ref(trans, root, path, bytenr,
+ parent, root_objectid);
+ }
+ return ret;
+}
+
+static int remove_extent_backref(struct btrfs_trans_handle *trans,
+ struct btrfs_root *root,
+ struct btrfs_path *path,
+ struct btrfs_extent_inline_ref *iref,
+ int refs_to_drop, int is_data)
+{
+ int ret;
+
+ BUG_ON(!is_data && refs_to_drop != 1);
+ if (iref) {
+ ret = update_inline_extent_backref(trans, root, path, iref,
+ -refs_to_drop);
+ } else if (is_data) {
+ ret = remove_extent_data_ref(trans, root, path, refs_to_drop);
+ } else {
+ ret = btrfs_del_item(trans, root, path);
+ }
+ return ret;
+}
+
+int btrfs_inc_extent_ref(struct btrfs_trans_handle *trans,
+ struct btrfs_root *root,
+ u64 bytenr, u64 num_bytes, u64 parent,
+ u64 root_objectid, u64 owner, u64 offset)
+{
+ struct btrfs_path *path;
+ struct extent_buffer *leaf;
struct btrfs_extent_item *item;
- u32 refs;
+ u64 refs;
+ int ret;
+ int err = 0;
path = btrfs_alloc_path();
if (!path)
return -ENOMEM;
path->reada = 1;
- key.objectid = bytenr;
- key.type = BTRFS_EXTENT_ITEM_KEY;
- key.offset = (u64)-1;
+ path->leave_spinning = 1;
- ret = btrfs_search_slot(trans, root->fs_info->extent_root, &key, path,
- 0, 1);
- if (ret < 0)
- return ret;
- BUG_ON(ret == 0 || path->slots[0] == 0);
-
- path->slots[0]--;
- l = path->nodes[0];
-
- btrfs_item_key_to_cpu(l, &key, path->slots[0]);
- BUG_ON(key.objectid != bytenr);
- BUG_ON(key.type != BTRFS_EXTENT_ITEM_KEY);
+ ret = insert_inline_extent_backref(trans, root->fs_info->extent_root,
+ path, bytenr, num_bytes, parent,
+ root_objectid, owner, offset, 1);
+ if (ret == 0)
+ goto out;
- item = btrfs_item_ptr(l, path->slots[0], struct btrfs_extent_item);
- refs = btrfs_extent_refs(l, item);
- btrfs_set_extent_refs(l, item, refs + 1);
- btrfs_mark_buffer_dirty(path->nodes[0]);
+ if (ret != -EAGAIN) {
+ err = ret;
+ goto out;
+ }
+
+ leaf = path->nodes[0];
+ item = btrfs_item_ptr(leaf, path->slots[0], struct btrfs_extent_item);
+ refs = btrfs_extent_refs(leaf, item);
+ btrfs_set_extent_refs(leaf, item, refs + 1);
+ btrfs_mark_buffer_dirty(leaf);
btrfs_release_path(root->fs_info->extent_root, path);
path->reada = 1;
+ path->leave_spinning = 1;
+
+ /* now insert the actual backref */
ret = insert_extent_backref(trans, root->fs_info->extent_root,
- path, bytenr, parent,
- ref_root, ref_generation,
- owner_objectid);
- BUG_ON(ret);
+ path, bytenr, parent, root_objectid,
+ owner, offset, 1);
+ if (ret)
+ err = ret;
+out:
+ btrfs_free_path(path);
finish_current_insert(trans, root->fs_info->extent_root);
del_pending_extents(trans, root->fs_info->extent_root);
-
- btrfs_free_path(path);
- return 0;
-}
-
-int btrfs_inc_extent_ref(struct btrfs_trans_handle *trans,
- struct btrfs_root *root,
- u64 bytenr, u64 num_bytes, u64 parent,
- u64 ref_root, u64 ref_generation,
- u64 owner_objectid)
-{
- int ret;
- if (ref_root == BTRFS_TREE_LOG_OBJECTID &&
- owner_objectid < BTRFS_FIRST_FREE_OBJECTID)
- return 0;
- maybe_lock_mutex(root);
- ret = __btrfs_inc_extent_ref(trans, root, bytenr, 0, parent,
- 0, ref_root, 0, ref_generation,
- owner_objectid);
- maybe_unlock_mutex(root);
- return ret;
+ BUG_ON(err);
+ return err;
}
int btrfs_extent_post_op(struct btrfs_trans_handle *trans,
@@ -801,15 +1429,76 @@ int btrfs_extent_post_op(struct btrfs_trans_handle *trans,
return 0;
}
-int btrfs_lookup_extent_ref(struct btrfs_trans_handle *trans,
- struct btrfs_root *root, u64 bytenr,
- u64 num_bytes, u32 *refs)
+int btrfs_lookup_extent_info(struct btrfs_trans_handle *trans,
+ struct btrfs_root *root, u64 bytenr,
+ u64 num_bytes, u64 *refs, u64 *flags)
+{
+ struct btrfs_path *path;
+ int ret;
+ struct btrfs_key key;
+ struct extent_buffer *l;
+ struct btrfs_extent_item *item;
+ u32 item_size;
+ u64 num_refs;
+ u64 extent_flags;
+
+ WARN_ON(num_bytes < root->sectorsize);
+ path = btrfs_alloc_path();
+ path->reada = 1;
+ key.objectid = bytenr;
+ key.offset = num_bytes;
+ btrfs_set_key_type(&key, BTRFS_EXTENT_ITEM_KEY);
+ ret = btrfs_search_slot(trans, root->fs_info->extent_root, &key, path,
+ 0, 0);
+ if (ret < 0)
+ goto out;
+ if (ret != 0) {
+ btrfs_print_leaf(root, path->nodes[0]);
+ printk("failed to find block number %Lu\n", bytenr);
+ BUG();
+ }
+
+ l = path->nodes[0];
+ item_size = btrfs_item_size_nr(l, path->slots[0]);
+ if (item_size >= sizeof(*item)) {
+ item = btrfs_item_ptr(l, path->slots[0],
+ struct btrfs_extent_item);
+ num_refs = btrfs_extent_refs(l, item);
+ extent_flags = btrfs_extent_flags(l, item);
+ } else {
+#ifdef BTRFS_COMPAT_EXTENT_TREE_V0
+ struct btrfs_extent_item_v0 *ei0;
+ BUG_ON(item_size != sizeof(*ei0));
+ ei0 = btrfs_item_ptr(l, path->slots[0],
+ struct btrfs_extent_item_v0);
+ num_refs = btrfs_extent_refs_v0(l, ei0);
+ /* FIXME: this isn't correct for data */
+ extent_flags = BTRFS_BLOCK_FLAG_FULL_BACKREF;
+#else
+ BUG();
+#endif
+ }
+ BUG_ON(num_refs == 0);
+ item = btrfs_item_ptr(l, path->slots[0], struct btrfs_extent_item);
+ if (refs)
+ *refs = num_refs;
+ if (flags)
+ *flags = extent_flags;
+out:
+ btrfs_free_path(path);
+ return 0;
+}
+
+int btrfs_set_block_flags(struct btrfs_trans_handle *trans,
+ struct btrfs_root *root,
+ u64 bytenr, u64 num_bytes, u64 flags)
{
struct btrfs_path *path;
int ret;
struct btrfs_key key;
struct extent_buffer *l;
struct btrfs_extent_item *item;
+ u32 item_size;
WARN_ON(num_bytes < root->sectorsize);
path = btrfs_alloc_path();
@@ -828,49 +1517,65 @@ int btrfs_lookup_extent_ref(struct btrfs_trans_handle *trans,
BUG();
}
l = path->nodes[0];
+ item_size = btrfs_item_size_nr(l, path->slots[0]);
+#ifdef BTRFS_COMPAT_EXTENT_TREE_V0
+ if (item_size < sizeof(*item)) {
+ ret = convert_extent_item_v0(trans, root->fs_info->extent_root,
+ path, (u64)-1, 0);
+ if (ret < 0)
+ goto out;
+
+ l = path->nodes[0];
+ item_size = btrfs_item_size_nr(l, path->slots[0]);
+ }
+#endif
+ BUG_ON(item_size < sizeof(*item));
item = btrfs_item_ptr(l, path->slots[0], struct btrfs_extent_item);
- *refs = btrfs_extent_refs(l, item);
+ flags |= btrfs_extent_flags(l, item);
+ btrfs_set_extent_flags(l, item, flags);
out:
btrfs_free_path(path);
- return 0;
+ finish_current_insert(trans, root->fs_info->extent_root);
+ del_pending_extents(trans, root->fs_info->extent_root);
+ return ret;
}
-int btrfs_inc_ref(struct btrfs_trans_handle *trans, struct btrfs_root *root,
- struct extent_buffer *orig_buf, struct extent_buffer *buf,
- u32 *nr_extents)
+static int __btrfs_mod_ref(struct btrfs_trans_handle *trans,
+ struct btrfs_root *root,
+ struct extent_buffer *buf,
+ int record_parent, int inc)
{
u64 bytenr;
+ u64 num_bytes;
+ u64 parent;
u64 ref_root;
- u64 orig_root;
- u64 ref_generation;
- u64 orig_generation;
u32 nritems;
- u32 nr_file_extents = 0;
struct btrfs_key key;
struct btrfs_file_extent_item *fi;
int i;
int level;
int ret = 0;
int faili = 0;
- int (*process_func)(struct btrfs_trans_handle *, struct btrfs_root *,
- u64, u64, u64, u64, u64, u64, u64, u64);
+ int (*process_func)(struct btrfs_trans_handle *trans,
+ struct btrfs_root *root,
+ u64, u64, u64, u64, u64, u64);
ref_root = btrfs_header_owner(buf);
- ref_generation = btrfs_header_generation(buf);
- orig_root = btrfs_header_owner(orig_buf);
- orig_generation = btrfs_header_generation(orig_buf);
-
nritems = btrfs_header_nritems(buf);
level = btrfs_header_level(buf);
- if (root->ref_cows) {
- process_func = __btrfs_inc_extent_ref;
- } else {
- if (level == 0 &&
- root->root_key.objectid != BTRFS_TREE_LOG_OBJECTID)
- goto out;
- process_func = __btrfs_update_extent_ref;
- }
+ if (!root->ref_cows && level == 0)
+ return 0;
+
+ if (inc)
+ process_func = btrfs_inc_extent_ref;
+ else
+ process_func = btrfs_free_extent;
+
+ if (record_parent)
+ parent = buf->start;
+ else
+ parent = 0;
for (i = 0; i < nritems; i++) {
cond_resched();
@@ -886,17 +1591,12 @@ int btrfs_inc_ref(struct btrfs_trans_handle *trans, struct btrfs_root *root,
bytenr = btrfs_file_extent_disk_bytenr(buf, fi);
if (bytenr == 0)
continue;
-
- nr_file_extents++;
-
- maybe_lock_mutex(root);
- ret = process_func(trans, root, bytenr,
- orig_buf->start, buf->start,
- orig_root, ref_root,
- orig_generation, ref_generation,
- key.objectid);
- maybe_unlock_mutex(root);
-
+
+ num_bytes = btrfs_file_extent_disk_num_bytes(buf, fi);
+ key.offset -= btrfs_file_extent_offset(buf, fi);
+ ret = process_func(trans, root, bytenr, num_bytes,
+ parent, ref_root, key.objectid,
+ key.offset);
if (ret) {
faili = i;
WARN_ON(1);
@@ -904,13 +1604,9 @@ int btrfs_inc_ref(struct btrfs_trans_handle *trans, struct btrfs_root *root,
}
} else {
bytenr = btrfs_node_blockptr(buf, i);
- maybe_lock_mutex(root);
- ret = process_func(trans, root, bytenr,
- orig_buf->start, buf->start,
- orig_root, ref_root,
- orig_generation, ref_generation,
- level - 1);
- maybe_unlock_mutex(root);
+ num_bytes = btrfs_level_size(root, level - 1);
+ ret = process_func(trans, root, bytenr, num_bytes,
+ parent, ref_root, level - 1, 0);
if (ret) {
faili = i;
WARN_ON(1);
@@ -918,13 +1614,6 @@ int btrfs_inc_ref(struct btrfs_trans_handle *trans, struct btrfs_root *root,
}
}
}
-out:
- if (nr_extents) {
- if (level == 0)
- *nr_extents = nr_file_extents;
- else
- *nr_extents = nritems;
- }
return 0;
fail:
WARN_ON(1);
@@ -958,79 +1647,16 @@ fail:
return ret;
}
-int btrfs_update_ref(struct btrfs_trans_handle *trans,
- struct btrfs_root *root, struct extent_buffer *orig_buf,
- struct extent_buffer *buf, int start_slot, int nr)
-
+int btrfs_inc_ref(struct btrfs_trans_handle *trans, struct btrfs_root *root,
+ struct extent_buffer *buf, int record_parent)
{
- u64 bytenr;
- u64 ref_root;
- u64 orig_root;
- u64 ref_generation;
- u64 orig_generation;
- struct btrfs_key key;
- struct btrfs_file_extent_item *fi;
- int i;
- int ret;
- int slot;
- int level;
-
- BUG_ON(start_slot < 0);
- BUG_ON(start_slot + nr > btrfs_header_nritems(buf));
-
- ref_root = btrfs_header_owner(buf);
- ref_generation = btrfs_header_generation(buf);
- orig_root = btrfs_header_owner(orig_buf);
- orig_generation = btrfs_header_generation(orig_buf);
- level = btrfs_header_level(buf);
-
- if (!root->ref_cows) {
- if (level == 0 &&
- root->root_key.objectid != BTRFS_TREE_LOG_OBJECTID)
- return 0;
- }
-
- for (i = 0, slot = start_slot; i < nr; i++, slot++) {
- cond_resched();
- if (level == 0) {
- btrfs_item_key_to_cpu(buf, &key, slot);
- if (btrfs_key_type(&key) != BTRFS_EXTENT_DATA_KEY)
- continue;
- fi = btrfs_item_ptr(buf, slot,
- struct btrfs_file_extent_item);
- if (btrfs_file_extent_type(buf, fi) ==
- BTRFS_FILE_EXTENT_INLINE)
- continue;
- bytenr = btrfs_file_extent_disk_bytenr(buf, fi);
- if (bytenr == 0)
- continue;
+ return __btrfs_mod_ref(trans, root, buf, record_parent, 1);
+}
- maybe_lock_mutex(root);
- ret = __btrfs_update_extent_ref(trans, root, bytenr,
- orig_buf->start, buf->start,
- orig_root, ref_root,
- orig_generation, ref_generation,
- key.objectid);
- maybe_unlock_mutex(root);
- if (ret)
- goto fail;
- } else {
- bytenr = btrfs_node_blockptr(buf, slot);
- maybe_lock_mutex(root);
- ret = __btrfs_update_extent_ref(trans, root, bytenr,
- orig_buf->start, buf->start,
- orig_root, ref_root,
- orig_generation, ref_generation,
- level - 1);
- maybe_unlock_mutex(root);
- if (ret)
- goto fail;
- }
- }
- return 0;
-fail:
- WARN_ON(1);
- return -1;
+int btrfs_dec_ref(struct btrfs_trans_handle *trans, struct btrfs_root *root,
+ struct extent_buffer *buf, int record_parent)
+{
+ return __btrfs_mod_ref(trans, root, buf, record_parent, 0);
}
static int write_one_cache_group(struct btrfs_trans_handle *trans,
@@ -1225,6 +1851,22 @@ static int update_block_group(struct btrfs_trans_handle *trans,
u64 start;
u64 end;
+ /* block accounting for super block */
+ old_val = btrfs_super_bytes_used(&info->super_copy);
+ if (alloc)
+ old_val += num_bytes;
+ else
+ old_val -= num_bytes;
+ btrfs_set_super_bytes_used(&info->super_copy, old_val);
+
+ /* block accounting for root item */
+ old_val = btrfs_root_used(&root->root_item);
+ if (alloc)
+ old_val += num_bytes;
+ else
+ old_val -= num_bytes;
+ btrfs_set_root_used(&root->root_item, old_val);
+
while(total) {
cache = btrfs_lookup_block_group(info, bytenr);
if (!cache) {
@@ -1341,14 +1983,10 @@ static int finish_current_insert(struct btrfs_trans_handle *trans,
u64 priv;
struct btrfs_fs_info *info = extent_root->fs_info;
struct btrfs_path *path;
- struct btrfs_extent_ref *ref;
struct pending_extent_op *extent_op;
struct btrfs_key key;
- struct btrfs_extent_item extent_item;
int ret;
- int err = 0;
- btrfs_set_stack_extent_refs(&extent_item, 1);
path = btrfs_alloc_path();
while(1) {
@@ -1365,45 +2003,18 @@ static int finish_current_insert(struct btrfs_trans_handle *trans,
key.objectid = start;
key.offset = end + 1 - start;
key.type = BTRFS_EXTENT_ITEM_KEY;
- err = btrfs_insert_item(trans, extent_root, &key,
- &extent_item, sizeof(extent_item));
- BUG_ON(err);
-
- clear_extent_bits(&info->extent_ins, start, end,
- EXTENT_LOCKED, GFP_NOFS);
-
- err = insert_extent_backref(trans, extent_root, path,
- start, extent_op->parent,
- extent_root->root_key.objectid,
- extent_op->generation,
- extent_op->level);
- BUG_ON(err);
- } else if (extent_op->type == PENDING_BACKREF_UPDATE) {
- err = lookup_extent_backref(trans, extent_root, path,
- start, extent_op->orig_parent,
+ ret = alloc_reserved_tree_block(trans, extent_root,
extent_root->root_key.objectid,
- extent_op->orig_generation,
- extent_op->level, 0);
- BUG_ON(err);
-
- clear_extent_bits(&info->extent_ins, start, end,
- EXTENT_LOCKED, GFP_NOFS);
-
- key.objectid = start;
- key.offset = extent_op->parent;
- key.type = BTRFS_EXTENT_REF_KEY;
- err = btrfs_set_item_key_safe(trans, extent_root, path,
- &key);
- BUG_ON(err);
- ref = btrfs_item_ptr(path->nodes[0], path->slots[0],
- struct btrfs_extent_ref);
- btrfs_set_ref_generation(path->nodes[0], ref,
- extent_op->generation);
- btrfs_mark_buffer_dirty(path->nodes[0]);
- btrfs_release_path(extent_root, path);
+ trans->transid,
+ extent_op->flags,
+ &extent_op->key,
+ extent_op->level, &key);
} else {
BUG_ON(1);
}
+
+ clear_extent_bits(&info->extent_ins, start, end, EXTENT_LOCKED,
+ GFP_NOFS);
kfree(extent_op);
}
btrfs_free_path(path);
@@ -1433,7 +2044,6 @@ static int pin_down_bytes(struct btrfs_trans_handle *trans,
u64 header_owner = btrfs_header_owner(buf);
u64 header_transid = btrfs_header_generation(buf);
if (header_owner != BTRFS_TREE_LOG_OBJECTID &&
- header_owner != BTRFS_TREE_RELOC_OBJECTID &&
header_transid == trans->transid &&
!btrfs_header_flag(buf, BTRFS_HEADER_FLAG_WRITTEN)) {
clean_tree_block(NULL, root, buf);
@@ -1452,143 +2062,186 @@ pinit:
/*
* 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, u64 parent,
- u64 root_objectid, u64 ref_generation,
- u64 owner_objectid, int pin, int mark_free)
+static int __free_extent(struct btrfs_trans_handle *trans,
+ struct btrfs_root *root,
+ u64 bytenr, u64 num_bytes, u64 parent,
+ u64 root_objectid, u64 owner_objectid,
+ u64 owner_offset, int refs_to_drop)
{
- struct btrfs_path *path;
+
struct btrfs_key key;
+ struct btrfs_path *path;
struct btrfs_fs_info *info = root->fs_info;
- struct btrfs_extent_ops *ops = info->extent_ops;
struct btrfs_root *extent_root = info->extent_root;
struct extent_buffer *leaf;
+ struct btrfs_extent_item *ei;
+ struct btrfs_extent_inline_ref *iref;
int ret;
+ int is_data;
int extent_slot = 0;
int found_extent = 0;
int num_to_del = 1;
- struct btrfs_extent_item *ei;
- u32 refs;
-
- key.objectid = bytenr;
- btrfs_set_key_type(&key, BTRFS_EXTENT_ITEM_KEY);
- key.offset = num_bytes;
+ u32 item_size;
+ u64 refs;
path = btrfs_alloc_path();
if (!path)
return -ENOMEM;
- ret = lookup_extent_backref(trans, extent_root, path,
- bytenr, parent, root_objectid,
- ref_generation, owner_objectid, 1);
+ path->reada = 1;
+ path->leave_spinning = 1;
+
+ is_data = owner_objectid >= BTRFS_FIRST_FREE_OBJECTID;
+ BUG_ON(!is_data && refs_to_drop != 1);
+
+ ret = lookup_extent_backref(trans, extent_root, path, &iref,
+ bytenr, num_bytes, parent,
+ root_objectid, owner_objectid,
+ owner_offset);
if (ret == 0) {
- struct btrfs_key found_key;
extent_slot = path->slots[0];
- while(extent_slot > 0) {
- extent_slot--;
- btrfs_item_key_to_cpu(path->nodes[0], &found_key,
+ while (extent_slot >= 0) {
+ btrfs_item_key_to_cpu(path->nodes[0], &key,
extent_slot);
- if (found_key.objectid != bytenr)
+ if (key.objectid != bytenr)
break;
- if (found_key.type == BTRFS_EXTENT_ITEM_KEY &&
- found_key.offset == num_bytes) {
+ if (key.type == BTRFS_EXTENT_ITEM_KEY &&
+ key.offset == num_bytes) {
found_extent = 1;
break;
}
if (path->slots[0] - extent_slot > 5)
break;
+ extent_slot--;
}
+#ifdef BTRFS_COMPAT_EXTENT_TREE_V0
+ item_size = btrfs_item_size_nr(path->nodes[0], extent_slot);
+ if (found_extent && item_size < sizeof(*ei))
+ found_extent = 0;
+#endif
if (!found_extent) {
- ret = remove_extent_backref(trans, extent_root, path);
+ BUG_ON(iref);
+ ret = remove_extent_backref(trans, extent_root, path,
+ NULL, refs_to_drop,
+ is_data);
BUG_ON(ret);
btrfs_release_path(extent_root, path);
+ path->leave_spinning = 1;
+
+ key.objectid = bytenr;
+ key.type = BTRFS_EXTENT_ITEM_KEY;
+ key.offset = num_bytes;
+
ret = btrfs_search_slot(trans, extent_root,
&key, path, -1, 1);
+ if (ret) {
+ printk(KERN_ERR "umm, got %d back from search"
+ ", was looking for %llu\n", ret,
+ (unsigned long long)bytenr);
+ btrfs_print_leaf(extent_root, path->nodes[0]);
+ }
BUG_ON(ret);
extent_slot = path->slots[0];
}
} else {
btrfs_print_leaf(extent_root, path->nodes[0]);
- printk("Unable to find ref byte nr %llu root %llu "
- " gen %llu owner %llu\n",
+ WARN_ON(1);
+ printk(KERN_ERR "btrfs unable to find ref byte nr %llu "
+ "parent %llu root %llu owner %llu offset %llu\n",
(unsigned long long)bytenr,
+ (unsigned long long)parent,
(unsigned long long)root_objectid,
- (unsigned long long)ref_generation,
- (unsigned long long)owner_objectid);
- BUG_ON(1);
+ (unsigned long long)owner_objectid,
+ (unsigned long long)owner_offset);
}
leaf = path->nodes[0];
+ item_size = btrfs_item_size_nr(leaf, extent_slot);
+#ifdef BTRFS_COMPAT_EXTENT_TREE_V0
+ if (item_size < sizeof(*ei)) {
+ BUG_ON(found_extent || extent_slot != path->slots[0]);
+ ret = convert_extent_item_v0(trans, extent_root, path,
+ owner_objectid, 0);
+ BUG_ON(ret < 0);
+
+ btrfs_release_path(extent_root, path);
+ path->leave_spinning = 1;
+
+ key.objectid = bytenr;
+ key.type = BTRFS_EXTENT_ITEM_KEY;
+ key.offset = num_bytes;
+
+ ret = btrfs_search_slot(trans, extent_root, &key, path,
+ -1, 1);
+ if (ret) {
+ printk(KERN_ERR "umm, got %d back from search"
+ ", was looking for %llu\n", ret,
+ (unsigned long long)bytenr);
+ btrfs_print_leaf(extent_root, path->nodes[0]);
+ }
+ BUG_ON(ret);
+ extent_slot = path->slots[0];
+ leaf = path->nodes[0];
+ item_size = btrfs_item_size_nr(leaf, extent_slot);
+ }
+#endif
+ BUG_ON(item_size < sizeof(*ei));
ei = btrfs_item_ptr(leaf, extent_slot,
struct btrfs_extent_item);
- refs = btrfs_extent_refs(leaf, ei);
- BUG_ON(refs == 0);
- refs -= 1;
- btrfs_set_extent_refs(leaf, ei, refs);
+ if (owner_objectid < BTRFS_FIRST_FREE_OBJECTID) {
+ struct btrfs_tree_block_info *bi;
+ BUG_ON(item_size < sizeof(*ei) + sizeof(*bi));
+ bi = (struct btrfs_tree_block_info *)(ei + 1);
+ WARN_ON(owner_objectid != btrfs_tree_block_level(leaf, bi));
+ }
- btrfs_mark_buffer_dirty(leaf);
+ refs = btrfs_extent_refs(leaf, ei);
+ BUG_ON(refs < refs_to_drop);
+ refs -= refs_to_drop;
- if (refs == 0 && found_extent && path->slots[0] == extent_slot + 1) {
- struct btrfs_extent_ref *ref;
- ref = btrfs_item_ptr(leaf, path->slots[0],
- struct btrfs_extent_ref);
- BUG_ON(btrfs_ref_num_refs(leaf, ref) != 1);
- /* if the back ref and the extent are next to each other
- * they get deleted below in one shot
+ if (refs > 0) {
+ /*
+ * In the case of inline back ref, reference count will
+ * be updated by remove_extent_backref
*/
- path->slots[0] = extent_slot;
- num_to_del = 2;
- } else if (found_extent) {
- /* otherwise delete the extent back ref */
- ret = remove_extent_backref(trans, extent_root, path);
- BUG_ON(ret);
- /* if refs are 0, we need to setup the path for deletion */
- if (refs == 0) {
- btrfs_release_path(extent_root, path);
- ret = btrfs_search_slot(trans, extent_root, &key, path,
- -1, 1);
- if (ret < 0)
- return ret;
+ if (iref) {
+ BUG_ON(!found_extent);
+ } else {
+ btrfs_set_extent_refs(leaf, ei, refs);
+ btrfs_mark_buffer_dirty(leaf);
+ }
+ if (found_extent) {
+ ret = remove_extent_backref(trans, extent_root, path,
+ iref, refs_to_drop,
+ is_data);
BUG_ON(ret);
}
- }
-
- if (refs == 0) {
- u64 super_used;
- u64 root_used;
-
+ } else {
+ int mark_free = 0;
+ if (found_extent) {
+ BUG_ON(is_data && refs_to_drop !=
+ extent_data_ref_count(root, path, iref));
+ if (iref) {
+ BUG_ON(path->slots[0] != extent_slot);
+ } else {
+ BUG_ON(path->slots[0] != extent_slot + 1);
+ path->slots[0] = extent_slot;
+ num_to_del = 2;
+ }
+ }
- /* block accounting for super block */
- super_used = btrfs_super_bytes_used(&info->super_copy);
- btrfs_set_super_bytes_used(&info->super_copy,
- super_used - num_bytes);
+ ret = pin_down_bytes(trans, root, bytenr, num_bytes, is_data);
+ if (ret > 0)
+ mark_free = 1;
+ BUG_ON(ret < 0);
- /* block accounting for root item */
- root_used = btrfs_root_used(&root->root_item);
- btrfs_set_root_used(&root->root_item,
- root_used - num_bytes);
ret = btrfs_del_items(trans, extent_root, path, path->slots[0],
num_to_del);
- if (ret)
- return ret;
-
- if (ops && ops->free_extent) {
- ret = ops->free_extent(root, bytenr, num_bytes);
- if (ret > 0) {
- pin = 0;
- mark_free = 0;
- }
- }
-
- if (pin) {
- ret = pin_down_bytes(trans, root, bytenr, num_bytes, 0);
- if (ret > 0)
- mark_free = 1;
- BUG_ON(ret < 0);
- }
+ BUG_ON(ret);
+ btrfs_release_path(extent_root, path);
- if (owner_objectid >= BTRFS_FIRST_FREE_OBJECTID) {
+ if (is_data) {
ret = btrfs_del_csums(trans, root, bytenr, num_bytes);
BUG_ON(ret);
}
@@ -1611,7 +2264,6 @@ static int del_pending_extents(struct btrfs_trans_handle *trans, struct
{
int ret;
int err = 0;
- int mark_free = 0;
u64 start;
u64 end;
u64 priv;
@@ -1635,18 +2287,12 @@ static int del_pending_extents(struct btrfs_trans_handle *trans, struct
clear_extent_bits(pending_del, start, end, EXTENT_LOCKED,
GFP_NOFS);
- ret = pin_down_bytes(trans, extent_root, start,
- end + 1 - start, 0);
- mark_free = ret > 0;
if (!test_range_bit(extent_ins, start, end,
EXTENT_LOCKED, 0)) {
-free_extent:
ret = __free_extent(trans, extent_root,
- start, end + 1 - start,
- extent_op->orig_parent,
+ start, end + 1 - start, 0,
extent_root->root_key.objectid,
- extent_op->orig_generation,
- extent_op->level, 0, mark_free);
+ extent_op->level, 0, 1);
kfree(extent_op);
} else {
kfree(extent_op);
@@ -1659,11 +2305,8 @@ free_extent:
EXTENT_LOCKED, GFP_NOFS);
if (extent_op->type == PENDING_BACKREF_UPDATE)
- goto free_extent;
+ BUG_ON(1);
- ret = update_block_group(trans, extent_root, start,
- end + 1 - start, 0, mark_free);
- BUG_ON(ret);
kfree(extent_op);
}
if (ret)
@@ -1675,10 +2318,11 @@ free_extent:
/*
* 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, u64 parent,
- u64 root_objectid, u64 ref_generation,
- u64 owner_objectid, int pin)
+
+int btrfs_free_extent(struct btrfs_trans_handle *trans,
+ struct btrfs_root *root,
+ u64 bytenr, u64 num_bytes, u64 parent,
+ u64 root_objectid, u64 owner, u64 offset)
{
struct btrfs_root *extent_root = root->fs_info->extent_root;
int pending_ret;
@@ -1694,11 +2338,7 @@ int btrfs_free_extent(struct btrfs_trans_handle *trans, struct btrfs_root
extent_op->type = PENDING_EXTENT_DELETE;
extent_op->bytenr = bytenr;
extent_op->num_bytes = num_bytes;
- extent_op->parent = parent;
- extent_op->orig_parent = parent;
- extent_op->generation = ref_generation;
- extent_op->orig_generation = ref_generation;
- extent_op->level = (int)owner_objectid;
+ extent_op->level = (int)owner;
set_extent_bits(&root->fs_info->pending_del,
bytenr, bytenr + num_bytes - 1,
@@ -1708,8 +2348,7 @@ int btrfs_free_extent(struct btrfs_trans_handle *trans, struct btrfs_root
return 0;
}
ret = __free_extent(trans, root, bytenr, num_bytes, parent,
- root_objectid, ref_generation,
- owner_objectid, pin, pin == 0);
+ root_objectid, owner, offset, 1);
pending_ret = del_pending_extents(trans, root->fs_info->extent_root);
return ret ? ret : pending_ret;
}
@@ -1836,32 +2475,17 @@ new_group:
error:
return ret;
}
-/*
- * finds a free extent and does all the dirty work required for allocation
- * returns the key for the extent through ins, and a tree buffer for
- * the first block of the extent through buf.
- *
- * returns 0 if everything worked, non-zero otherwise.
- */
-int btrfs_alloc_extent(struct btrfs_trans_handle *trans,
- struct btrfs_root *root,
- u64 num_bytes, u64 parent,
- u64 root_objectid, u64 ref_generation,
- u64 owner, u64 empty_size, u64 hint_byte,
- u64 search_end, struct btrfs_key *ins, int data)
+
+static int btrfs_reserve_extent(struct btrfs_trans_handle *trans,
+ struct btrfs_root *root,
+ u64 num_bytes, u64 empty_size,
+ u64 hint_byte, u64 search_end,
+ struct btrfs_key *ins, int data)
{
int ret;
- int pending_ret;
- u64 super_used, root_used;
u64 search_start = 0;
u64 alloc_profile;
- u32 sizes[2];
struct btrfs_fs_info *info = root->fs_info;
- struct btrfs_root *extent_root = info->extent_root;
- struct btrfs_path *path;
- struct btrfs_extent_item *extent_item;
- struct btrfs_extent_ref *ref;
- struct btrfs_key keys[2];
if (info->extent_ops) {
struct btrfs_extent_ops *ops = info->extent_ops;
@@ -1904,25 +2528,78 @@ int btrfs_alloc_extent(struct btrfs_trans_handle *trans,
trans->alloc_exclude_nr, data);
BUG_ON(ret);
found:
- if (ret)
- return ret;
+ clear_extent_dirty(&root->fs_info->free_space_cache,
+ ins->objectid, ins->objectid + ins->offset - 1,
+ GFP_NOFS);
+ return ret;
+}
+
+static int alloc_reserved_tree_block(struct btrfs_trans_handle *trans,
+ struct btrfs_root *root,
+ u64 root_objectid, u64 generation,
+ u64 flags, struct btrfs_disk_key *key,
+ int level, struct btrfs_key *ins)
+{
+ int ret;
+ struct btrfs_fs_info *fs_info = root->fs_info;
+ struct btrfs_extent_item *extent_item;
+ struct btrfs_tree_block_info *block_info;
+ struct btrfs_extent_inline_ref *iref;
+ struct btrfs_path *path;
+ struct extent_buffer *leaf;
+ u32 size = sizeof(*extent_item) + sizeof(*block_info) + sizeof(*iref);
- if (parent == 0)
- parent = ins->objectid;
+ path = btrfs_alloc_path();
+ BUG_ON(!path);
- /* block accounting for super block */
- super_used = btrfs_super_bytes_used(&info->super_copy);
- btrfs_set_super_bytes_used(&info->super_copy, super_used + num_bytes);
+ path->leave_spinning = 1;
+ ret = btrfs_insert_empty_item(trans, fs_info->extent_root, path,
+ ins, size);
+ BUG_ON(ret);
- /* block accounting for root item */
- root_used = btrfs_root_used(&root->root_item);
- btrfs_set_root_used(&root->root_item, root_used + num_bytes);
+ leaf = path->nodes[0];
+ extent_item = btrfs_item_ptr(leaf, path->slots[0],
+ struct btrfs_extent_item);
+ btrfs_set_extent_refs(leaf, extent_item, 1);
+ btrfs_set_extent_generation(leaf, extent_item, generation);
+ btrfs_set_extent_flags(leaf, extent_item,
+ flags | BTRFS_EXTENT_FLAG_TREE_BLOCK);
+ block_info = (struct btrfs_tree_block_info *)(extent_item + 1);
- clear_extent_dirty(&root->fs_info->free_space_cache,
- ins->objectid, ins->objectid + ins->offset - 1,
- GFP_NOFS);
+ btrfs_set_tree_block_key(leaf, block_info, key);
+ btrfs_set_tree_block_level(leaf, block_info, level);
- if (root == extent_root) {
+ iref = (struct btrfs_extent_inline_ref *)(block_info + 1);
+ btrfs_set_extent_inline_ref_type(leaf, iref, BTRFS_TREE_BLOCK_REF_KEY);
+ btrfs_set_extent_inline_ref_offset(leaf, iref, root_objectid);
+
+ btrfs_mark_buffer_dirty(leaf);
+ btrfs_free_path(path);
+
+ ret = update_block_group(trans, root, ins->objectid, ins->offset,
+ 1, 0);
+ if (ret) {
+ printk(KERN_ERR "btrfs update block group failed for %llu "
+ "%llu\n", (unsigned long long)ins->objectid,
+ (unsigned long long)ins->offset);
+ BUG();
+ }
+ return ret;
+}
+
+static int alloc_tree_block(struct btrfs_trans_handle *trans,
+ struct btrfs_root *root, u64 num_bytes,
+ u64 root_objectid, u64 generation,
+ u64 flags, struct btrfs_disk_key *key,
+ int level, u64 empty_size, u64 hint_byte,
+ u64 search_end, struct btrfs_key *ins)
+{
+ int ret;
+ ret = btrfs_reserve_extent(trans, root, num_bytes, empty_size,
+ hint_byte, search_end, ins, 0);
+ BUG_ON(ret);
+
+ if (root_objectid == BTRFS_EXTENT_TREE_OBJECTID) {
struct pending_extent_op *extent_op;
extent_op = kmalloc(sizeof(*extent_op), GFP_NOFS);
@@ -1931,73 +2608,23 @@ found:
extent_op->type = PENDING_EXTENT_INSERT;
extent_op->bytenr = ins->objectid;
extent_op->num_bytes = ins->offset;
- extent_op->parent = parent;
- extent_op->orig_parent = 0;
- extent_op->generation = ref_generation;
- extent_op->orig_generation = 0;
- extent_op->level = (int)owner;
+ extent_op->level = level;
+ extent_op->flags = flags;
+ memcpy(&extent_op->key, key, sizeof(*key));
set_extent_bits(&root->fs_info->extent_ins, ins->objectid,
ins->objectid + ins->offset - 1,
EXTENT_LOCKED, GFP_NOFS);
set_state_private(&root->fs_info->extent_ins,
ins->objectid, (unsigned long)extent_op);
- goto update_block;
- }
-
- WARN_ON(trans->alloc_exclude_nr);
- trans->alloc_exclude_start = ins->objectid;
- trans->alloc_exclude_nr = ins->offset;
-
- memcpy(&keys[0], ins, sizeof(*ins));
- keys[1].objectid = ins->objectid;
- keys[1].type = BTRFS_EXTENT_REF_KEY;
- keys[1].offset = parent;
- sizes[0] = sizeof(*extent_item);
- sizes[1] = sizeof(*ref);
-
- path = btrfs_alloc_path();
- BUG_ON(!path);
-
- ret = btrfs_insert_empty_items(trans, extent_root, path, keys,
- sizes, 2);
-
- BUG_ON(ret);
- extent_item = btrfs_item_ptr(path->nodes[0], path->slots[0],
- struct btrfs_extent_item);
- btrfs_set_extent_refs(path->nodes[0], extent_item, 1);
- ref = btrfs_item_ptr(path->nodes[0], path->slots[0] + 1,
- struct btrfs_extent_ref);
-
- btrfs_set_ref_root(path->nodes[0], ref, root_objectid);
- btrfs_set_ref_generation(path->nodes[0], ref, ref_generation);
- btrfs_set_ref_objectid(path->nodes[0], ref, owner);
- btrfs_set_ref_num_refs(path->nodes[0], ref, 1);
-
- btrfs_mark_buffer_dirty(path->nodes[0]);
-
- trans->alloc_exclude_start = 0;
- trans->alloc_exclude_nr = 0;
- btrfs_free_path(path);
- finish_current_insert(trans, extent_root);
- pending_ret = del_pending_extents(trans, extent_root);
-
- if (ret) {
- return ret;
- }
- if (pending_ret) {
- return pending_ret;
- }
-
-update_block:
- ret = update_block_group(trans, root, ins->objectid, ins->offset, 1, 0);
- if (ret) {
- printk("update block group failed for %llu %llu\n",
- (unsigned long long)ins->objectid,
- (unsigned long long)ins->offset);
- BUG();
+ } else {
+ ret = alloc_reserved_tree_block(trans, root, root_objectid,
+ generation, flags,
+ key, level, ins);
+ finish_current_insert(trans, root->fs_info->extent_root);
+ del_pending_extents(trans, root->fs_info->extent_root);
}
- return 0;
+ return ret;
}
/*
@@ -2005,41 +2632,38 @@ update_block:
* returns the tree buffer or NULL.
*/
struct extent_buffer *btrfs_alloc_free_block(struct btrfs_trans_handle *trans,
- struct btrfs_root *root,
- u32 blocksize, u64 parent,
- u64 root_objectid,
- u64 ref_generation,
- int level,
- u64 hint,
- u64 empty_size)
+ struct btrfs_root *root,
+ u32 blocksize, u64 root_objectid,
+ struct btrfs_disk_key *key, int level,
+ u64 hint, u64 empty_size)
{
struct btrfs_key ins;
int ret;
struct extent_buffer *buf;
- ret = btrfs_alloc_extent(trans, root, blocksize, parent,
- root_objectid, ref_generation,
- level, empty_size, hint,
- (u64)-1, &ins, 0);
+ ret = alloc_tree_block(trans, root, blocksize, root_objectid,
+ trans->transid, 0, key, level,
+ empty_size, hint, (u64)-1, &ins);
if (ret) {
BUG_ON(ret > 0);
return ERR_PTR(ret);
}
+
buf = btrfs_find_create_tree_block(root, ins.objectid, blocksize);
if (!buf) {
- if (parent == 0)
- parent = ins.objectid;
- btrfs_free_extent(trans, root, ins.objectid, blocksize,
- parent, root->root_key.objectid,
- ref_generation, level, 0);
+ btrfs_free_extent(trans, root, ins.objectid, ins.offset,
+ 0, root->root_key.objectid, level, 0);
BUG_ON(1);
return ERR_PTR(-ENOMEM);
}
btrfs_set_buffer_uptodate(buf);
trans->blocks_used++;
+
return buf;
}
+#if 0
+
static int noinline drop_leaf_ref(struct btrfs_trans_handle *trans,
struct btrfs_root *root,
struct extent_buffer *leaf)
@@ -2357,6 +2981,8 @@ out:
return ret;
}
+#endif
+
int btrfs_free_block_groups(struct btrfs_fs_info *info)
{
u64 start;
diff --git a/extent_io.c b/extent_io.c
index 4920b291..069c199c 100644
--- a/extent_io.c
+++ b/extent_io.c
@@ -202,6 +202,7 @@ int clear_extent_bits(struct extent_io_tree *tree, u64 start,
struct extent_state *state;
struct extent_state *prealloc = NULL;
struct cache_extent *node;
+ u64 last_end;
int err;
int set = 0;
@@ -220,6 +221,7 @@ again:
state = container_of(node, struct extent_state, cache_node);
if (state->start > end)
goto out;
+ last_end = state->end;
/*
* | ---- desired range ---- |
@@ -243,8 +245,10 @@ again:
if (err)
goto out;
if (state->end <= end) {
- start = state->end + 1;
set |= clear_state_bit(tree, state, bits);
+ if (last_end == (u64)-1)
+ goto out;
+ start = last_end + 1;
} else {
start = state->start;
}
@@ -267,6 +271,9 @@ again:
start = state->end + 1;
set |= clear_state_bit(tree, state, bits);
+ if (last_end == (u64)-1)
+ goto out;
+ start = last_end + 1;
goto search_again;
out:
if (prealloc)
@@ -322,8 +329,10 @@ again:
if (state->start == start && state->end <= end) {
set = state->state & bits;
state->state |= bits;
- start = state->end + 1;
merge_state(tree, state);
+ if (last_end == (u64)-1)
+ goto out;
+ start = last_end + 1;
goto search_again;
}
/*
@@ -353,6 +362,9 @@ again:
state->state |= bits;
start = state->end + 1;
merge_state(tree, state);
+ if (last_end == (u64)-1)
+ goto out;
+ start = last_end + 1;
} else {
start = state->start;
}
diff --git a/kerncompat.h b/kerncompat.h
index aed4b556..e4c8ce0c 100644
--- a/kerncompat.h
+++ b/kerncompat.h
@@ -191,6 +191,7 @@ static inline long IS_ERR(const void *ptr)
*/
#define printk(fmt, args...) fprintf(stderr, fmt, ##args)
#define KERN_CRIT ""
+#define KERN_ERR ""
/*
* kmalloc/kfree
diff --git a/mkfs.c b/mkfs.c
index 4f959f74..2e99b952 100644
--- a/mkfs.c
+++ b/mkfs.c
@@ -173,6 +173,11 @@ static int recow_roots(struct btrfs_trans_handle *trans,
BUG_ON(ret);
free_extent_buffer(tmp);
+ ret = __btrfs_cow_block(trans, info->csum_root, info->csum_root->node,
+ NULL, 0, &tmp, 0, 0);
+ BUG_ON(ret);
+ free_extent_buffer(tmp);
+
return 0;
}
@@ -252,7 +257,7 @@ static int create_data_reloc_tree(struct btrfs_trans_handle *trans,
location.objectid = objectid;
location.type = BTRFS_ROOT_ITEM_KEY;
- location.offset = trans->transid;
+ location.offset = 0;
ret = btrfs_insert_root(trans, root->fs_info->tree_root,
&location, &root_item);
BUG_ON(ret);
diff --git a/print-tree.c b/print-tree.c
index 86033cf3..59f43588 100644
--- a/print-tree.c
+++ b/print-tree.c
@@ -159,6 +159,107 @@ static void print_file_extent_item(struct extent_buffer *eb,
btrfs_file_extent_compression(eb, fi));
}
+static void print_extent_item(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_disk_key key;
+ unsigned long end;
+ unsigned long ptr;
+ int type;
+ u32 item_size = btrfs_item_size_nr(eb, slot);
+ u64 flags;
+ u64 offset;
+
+ 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);
+ printf("\t\textent refs %u\n",
+ btrfs_extent_refs_v0(eb, ei0));
+ return;
+#else
+ BUG();
+#endif
+ }
+
+ ei = btrfs_item_ptr(eb, slot, struct btrfs_extent_item);
+ flags = btrfs_extent_flags(eb, ei);
+
+ printf("\t\textent refs %llu gen %llu flags %llu\n",
+ (unsigned long long)btrfs_extent_refs(eb, ei),
+ (unsigned long long)btrfs_extent_generation(eb, ei),
+ (unsigned long long)flags);
+
+ if (flags & BTRFS_EXTENT_FLAG_TREE_BLOCK) {
+ struct btrfs_tree_block_info *info;
+ info = (struct btrfs_tree_block_info *)(ei + 1);
+ btrfs_tree_block_key(eb, info, &key);
+ printf("\t\ttree block key (%llu %x %llu) level %d\n",
+ (unsigned long long)btrfs_disk_key_objectid(&key),
+ key.type,
+ (unsigned long long)btrfs_disk_key_offset(&key),
+ btrfs_tree_block_level(eb, info));
+ iref = (struct btrfs_extent_inline_ref *)(info + 1);
+ } else {
+ iref = (struct btrfs_extent_inline_ref *)(ei + 1);
+ }
+
+ ptr = (unsigned long)iref;
+ 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:
+ printf("\t\ttree block backref root %llu\n",
+ (unsigned long long)offset);
+ break;
+ case BTRFS_SHARED_BLOCK_REF_KEY:
+ printf("\t\tshared block backref parent %llu\n",
+ (unsigned long long)offset);
+ break;
+ case BTRFS_EXTENT_DATA_REF_KEY:
+ dref = (struct btrfs_extent_data_ref *)(&iref->offset);
+ printf("\t\textent data backref root %llu "
+ "objectid %llu offset %llu count %u\n",
+ (unsigned long long)btrfs_extent_data_ref_root(eb, dref),
+ (unsigned long long)btrfs_extent_data_ref_objectid(eb, dref),
+ (unsigned long long)btrfs_extent_data_ref_offset(eb, dref),
+ btrfs_extent_data_ref_count(eb, dref));
+ break;
+ case BTRFS_SHARED_DATA_REF_KEY:
+ sref = (struct btrfs_shared_data_ref *)(iref + 1);
+ printf("\t\tshared data backref parent %llu count %u\n",
+ (unsigned long long)offset,
+ btrfs_shared_data_ref_count(eb, sref));
+ break;
+ default:
+ BUG();
+ }
+ ptr += btrfs_extent_inline_ref_size(type);
+ }
+ WARN_ON(ptr > end);
+}
+
+#ifdef BTRFS_COMPAT_EXTENT_TREE_V0
+static void print_extent_ref_v0(struct extent_buffer *eb, int slot)
+{
+ struct btrfs_extent_ref_v0 *ref0;
+
+ ref0 = btrfs_item_ptr(eb, slot, struct btrfs_extent_ref_v0);
+ printf("\t\textent back ref root %llu gen %llu "
+ "owner %llu num_refs %lu\n",
+ (unsigned long long)btrfs_ref_root_v0(eb, ref0),
+ (unsigned long long)btrfs_ref_generation_v0(eb, ref0),
+ (unsigned long long)btrfs_ref_objectid_v0(eb, ref0),
+ (unsigned long)btrfs_ref_count_v0(eb, ref0));
+}
+#endif
static void print_root_ref(struct extent_buffer *leaf, int slot, char *tag)
{
@@ -214,8 +315,20 @@ static void print_key_type(u8 type)
case BTRFS_EXTENT_ITEM_KEY:
printf("EXTENT_ITEM");
break;
- case BTRFS_EXTENT_REF_KEY:
- printf("EXTENT_REF");
+ case BTRFS_TREE_BLOCK_REF_KEY:
+ printf("TREE_BLOCK_REF");
+ break;
+ case BTRFS_SHARED_BLOCK_REF_KEY:
+ printf("SHARED_BLOCK_REF");
+ break;
+ case BTRFS_EXTENT_DATA_REF_KEY:
+ printf("EXTENT_DATA_REF");
+ break;
+ case BTRFS_SHARED_DATA_REF_KEY:
+ printf("SHARED_DATA_REF");
+ break;
+ case BTRFS_EXTENT_REF_V0_KEY:
+ printf("EXTENT_REF_V0");
break;
case BTRFS_CSUM_ITEM_KEY:
printf("CSUM_ITEM");
@@ -324,14 +437,14 @@ void btrfs_print_leaf(struct btrfs_root *root, struct extent_buffer *l)
int i;
char *str;
struct btrfs_item *item;
- struct btrfs_extent_item *ei;
struct btrfs_root_item *ri;
struct btrfs_dir_item *di;
struct btrfs_inode_item *ii;
struct btrfs_file_extent_item *fi;
struct btrfs_csum_item *ci;
struct btrfs_block_group_item *bi;
- struct btrfs_extent_ref *ref;
+ struct btrfs_extent_data_ref *dref;
+ struct btrfs_shared_data_ref *sref;
struct btrfs_inode_ref *iref;
struct btrfs_dev_extent *dev_extent;
struct btrfs_disk_key disk_key;
@@ -410,18 +523,34 @@ void btrfs_print_leaf(struct btrfs_root *root, struct extent_buffer *l)
print_root_ref(l, i, "backref");
break;
case BTRFS_EXTENT_ITEM_KEY:
- ei = btrfs_item_ptr(l, i, struct btrfs_extent_item);
- printf("\t\textent data refs %u\n",
- btrfs_extent_refs(l, ei));
+ print_extent_item(l, i);
+ break;
+ case BTRFS_TREE_BLOCK_REF_KEY:
+ printf("\t\ttree block backref\n");
break;
- case BTRFS_EXTENT_REF_KEY:
- ref = btrfs_item_ptr(l, i, struct btrfs_extent_ref);
- printf("\t\textent back ref root %llu gen %llu "
- "owner %llu num_refs %lu\n",
- (unsigned long long)btrfs_ref_root(l, ref),
- (unsigned long long)btrfs_ref_generation(l, ref),
- (unsigned long long)btrfs_ref_objectid(l, ref),
- (unsigned long)btrfs_ref_num_refs(l, ref));
+ case BTRFS_SHARED_BLOCK_REF_KEY:
+ printf("\t\tshared block backref\n");
+ break;
+ case BTRFS_EXTENT_DATA_REF_KEY:
+ dref = btrfs_item_ptr(l, i, struct btrfs_extent_data_ref);
+ printf("\t\textent data backref root %llu "
+ "objectid %llu offset %llu count %u\n",
+ (unsigned long long)btrfs_extent_data_ref_root(l, dref),
+ (unsigned long long)btrfs_extent_data_ref_objectid(l, dref),
+ (unsigned long long)btrfs_extent_data_ref_offset(l, dref),
+ btrfs_extent_data_ref_count(l, dref));
+ break;
+ case BTRFS_SHARED_DATA_REF_KEY:
+ sref = btrfs_item_ptr(l, i, struct btrfs_shared_data_ref);
+ printf("\t\tshared data backref count %u\n",
+ btrfs_shared_data_ref_count(l, sref));
+ break;
+ case BTRFS_EXTENT_REF_V0_KEY:
+#ifdef BTRFS_COMPAT_EXTENT_TREE_V0
+ print_extent_ref_v0(l, i);
+#else
+ BUG();
+#endif
break;
case BTRFS_CSUM_ITEM_KEY:
ci = btrfs_item_ptr(l, i, struct btrfs_csum_item);
diff --git a/utils.c b/utils.c
index a87c5a86..2f4c6e14 100644
--- a/utils.c
+++ b/utils.c
@@ -63,7 +63,6 @@ int make_btrfs(int fd, const char *device, const char *label,
struct extent_buffer *buf;
struct btrfs_root_item root_item;
struct btrfs_disk_key disk_key;
- struct btrfs_extent_ref *extent_ref;
struct btrfs_extent_item *extent_item;
struct btrfs_inode_item *inode_item;
struct btrfs_chunk *chunk;
@@ -115,6 +114,7 @@ int make_btrfs(int fd, const char *device, const char *label,
btrfs_set_header_bytenr(buf, blocks[1]);
btrfs_set_header_nritems(buf, 4);
btrfs_set_header_generation(buf, 1);
+ btrfs_set_header_backref_rev(buf, BTRFS_MIXED_BACKREF_REV);
btrfs_set_header_owner(buf, BTRFS_ROOT_TREE_OBJECTID);
write_extent_buffer(buf, super.fsid, (unsigned long)
btrfs_header_fsid(buf), BTRFS_FSID_SIZE);
@@ -200,7 +200,8 @@ int make_btrfs(int fd, const char *device, const char *label,
BUG_ON(blocks[i] < blocks[i - 1]);
/* create extent item */
- itemoff = itemoff - sizeof(struct btrfs_extent_item);
+ itemoff -= sizeof(struct btrfs_extent_item) +
+ sizeof(struct btrfs_tree_block_info);
btrfs_set_disk_key_objectid(&disk_key, blocks[i]);
btrfs_set_disk_key_offset(&disk_key, leafsize);
btrfs_set_disk_key_type(&disk_key, BTRFS_EXTENT_ITEM_KEY);
@@ -208,29 +209,25 @@ int make_btrfs(int fd, const char *device, const char *label,
btrfs_set_item_offset(buf, btrfs_item_nr(buf, nritems),
itemoff);
btrfs_set_item_size(buf, btrfs_item_nr(buf, nritems),
- sizeof(struct btrfs_extent_item));
+ sizeof(struct btrfs_extent_item) +
+ sizeof(struct btrfs_tree_block_info));
extent_item = btrfs_item_ptr(buf, nritems,
struct btrfs_extent_item);
btrfs_set_extent_refs(buf, extent_item, 1);
+ btrfs_set_extent_generation(buf, extent_item, 1);
+ btrfs_set_extent_flags(buf, extent_item,
+ BTRFS_EXTENT_FLAG_TREE_BLOCK);
nritems++;
/* create extent ref */
ref_root = reference_root_table[i];
- itemoff = itemoff - sizeof(struct btrfs_extent_ref);
btrfs_set_disk_key_objectid(&disk_key, blocks[i]);
- btrfs_set_disk_key_offset(&disk_key, blocks[i]);
- btrfs_set_disk_key_type(&disk_key, BTRFS_EXTENT_REF_KEY);
+ btrfs_set_disk_key_offset(&disk_key, ref_root);
+ btrfs_set_disk_key_type(&disk_key, BTRFS_TREE_BLOCK_REF_KEY);
btrfs_set_item_key(buf, &disk_key, nritems);
btrfs_set_item_offset(buf, btrfs_item_nr(buf, nritems),
itemoff);
- btrfs_set_item_size(buf, btrfs_item_nr(buf, nritems),
- sizeof(struct btrfs_extent_ref));
- extent_ref = btrfs_item_ptr(buf, nritems,
- struct btrfs_extent_ref);
- btrfs_set_ref_root(buf, extent_ref, ref_root);
- btrfs_set_ref_generation(buf, extent_ref, 1);
- btrfs_set_ref_objectid(buf, extent_ref, 0);
- btrfs_set_ref_num_refs(buf, extent_ref, 1);
+ btrfs_set_item_size(buf, btrfs_item_nr(buf, nritems), 0);
nritems++;
}
btrfs_set_header_bytenr(buf, blocks[2]);
generated by cgit 1.2.3-korg (git 2.39.0) at 2024-05-22 04:36:29 +0000