diff options
-rw-r--r-- | Makefile | 6 | ||||
-rw-r--r-- | btrfs-image.c | 72 | ||||
-rw-r--r-- | btrfsck.c | 725 | ||||
-rw-r--r-- | crc32c.h | 1 | ||||
-rw-r--r-- | ctree.c | 609 | ||||
-rw-r--r-- | ctree.h | 221 | ||||
-rw-r--r-- | debug-tree.c | 4 | ||||
-rw-r--r-- | disk-io.c | 170 | ||||
-rw-r--r-- | disk-io.h | 2 | ||||
-rw-r--r-- | extent-tree.c | 1920 | ||||
-rw-r--r-- | extent_io.c | 16 | ||||
-rw-r--r-- | kerncompat.h | 1 | ||||
-rw-r--r-- | mkfs.c | 7 | ||||
-rw-r--r-- | print-tree.c | 159 | ||||
-rw-r--r-- | utils.c | 25 |
15 files changed, 2725 insertions, 1213 deletions
@@ -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; } @@ -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", @@ -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 @@ -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); @@ -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); } @@ -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); @@ -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 @@ -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); @@ -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]); |