From 73980becaebfd4dd3c56f2ae64d4081af2a65b27 Mon Sep 17 00:00:00 2001 From: Jeff Mahoney Date: Wed, 28 Jun 2017 21:56:55 -0600 Subject: btrfs: backref, constify some arguments This constifies a few buffers used in the backref code. Signed-off-by: Jeff Mahoney Signed-off-by: David Sterba --- fs/btrfs/backref.c | 29 ++++++++++++++++------------- 1 file changed, 16 insertions(+), 13 deletions(-) (limited to 'fs/btrfs/backref.c') diff --git a/fs/btrfs/backref.c b/fs/btrfs/backref.c index f723c11bb763..9d6474ddf674 100644 --- a/fs/btrfs/backref.c +++ b/fs/btrfs/backref.c @@ -299,10 +299,11 @@ static int ref_tree_add(struct ref_root *ref_tree, u64 root_id, u64 object_id, return 0; } -static int check_extent_in_eb(struct btrfs_key *key, struct extent_buffer *eb, - struct btrfs_file_extent_item *fi, - u64 extent_item_pos, - struct extent_inode_elem **eie) +static int check_extent_in_eb(const struct btrfs_key *key, + const struct extent_buffer *eb, + const struct btrfs_file_extent_item *fi, + u64 extent_item_pos, + struct extent_inode_elem **eie) { u64 offset = 0; struct extent_inode_elem *e; @@ -344,9 +345,9 @@ static void free_inode_elem_list(struct extent_inode_elem *eie) } } -static int find_extent_in_eb(struct extent_buffer *eb, u64 wanted_disk_byte, - u64 extent_item_pos, - struct extent_inode_elem **eie) +static int find_extent_in_eb(const struct extent_buffer *eb, + u64 wanted_disk_byte, u64 extent_item_pos, + struct extent_inode_elem **eie) { u64 disk_byte; struct btrfs_key key; @@ -456,7 +457,7 @@ void btrfs_prelim_ref_exit(void) */ static int __add_prelim_ref(struct list_head *head, u64 root_id, - struct btrfs_key *key, int level, + const struct btrfs_key *key, int level, u64 parent, u64 wanted_disk_byte, int count, gfp_t gfp_mask) { @@ -1649,7 +1650,7 @@ int btrfs_find_one_extref(struct btrfs_root *root, u64 inode_objectid, struct btrfs_key key; struct btrfs_key found_key; struct btrfs_inode_extref *extref; - struct extent_buffer *leaf; + const struct extent_buffer *leaf; unsigned long ptr; key.objectid = inode_objectid; @@ -1806,7 +1807,7 @@ int extent_from_logical(struct btrfs_fs_info *fs_info, u64 logical, u64 flags; u64 size = 0; u32 item_size; - struct extent_buffer *eb; + const struct extent_buffer *eb; struct btrfs_extent_item *ei; struct btrfs_key key; @@ -1874,9 +1875,11 @@ int extent_from_logical(struct btrfs_fs_info *fs_info, u64 logical, * next ref. after the last ref was processed, 1 is returned. * returns <0 on error */ -static int __get_extent_inline_ref(unsigned long *ptr, struct extent_buffer *eb, - struct btrfs_key *key, - struct btrfs_extent_item *ei, u32 item_size, +static int __get_extent_inline_ref(unsigned long *ptr, + const struct extent_buffer *eb, + const struct btrfs_key *key, + const struct btrfs_extent_item *ei, + u32 item_size, struct btrfs_extent_inline_ref **out_eiref, int *out_type) { -- cgit v1.2.3 From 4dae077a83dd8944ed351b09a0651c1283f46185 Mon Sep 17 00:00:00 2001 From: Jeff Mahoney Date: Wed, 28 Jun 2017 21:56:56 -0600 Subject: btrfs: backref, add unode_aux_to_inode_list helper Replacing the double cast and ternary conditional with a helper makes the code easier on the eyes. Signed-off-by: Jeff Mahoney Signed-off-by: David Sterba --- fs/btrfs/backref.c | 16 +++++++++++----- 1 file changed, 11 insertions(+), 5 deletions(-) (limited to 'fs/btrfs/backref.c') diff --git a/fs/btrfs/backref.c b/fs/btrfs/backref.c index 9d6474ddf674..4a7a4b032c2f 100644 --- a/fs/btrfs/backref.c +++ b/fs/btrfs/backref.c @@ -682,6 +682,14 @@ out: return ret; } +static struct extent_inode_elem * +unode_aux_to_inode_list(struct ulist_node *node) +{ + if (!node) + return NULL; + return (struct extent_inode_elem *)(uintptr_t)node->aux; +} + /* * resolve all indirect backrefs from the list */ @@ -736,8 +744,7 @@ static int __resolve_indirect_refs(struct btrfs_fs_info *fs_info, ULIST_ITER_INIT(&uiter); node = ulist_next(parents, &uiter); ref->parent = node ? node->val : 0; - ref->inode_list = node ? - (struct extent_inode_elem *)(uintptr_t)node->aux : NULL; + ref->inode_list = unode_aux_to_inode_list(node); /* additional parents require new refs being added here */ while ((node = ulist_next(parents, &uiter))) { @@ -749,8 +756,7 @@ static int __resolve_indirect_refs(struct btrfs_fs_info *fs_info, } memcpy(new_ref, ref, sizeof(*ref)); new_ref->parent = node->val; - new_ref->inode_list = (struct extent_inode_elem *) - (uintptr_t)node->aux; + new_ref->inode_list = unode_aux_to_inode_list(node); list_add(&new_ref->list, &ref->list); } ulist_reinit(parents); @@ -1476,7 +1482,7 @@ static void free_leaf_list(struct ulist *blocks) while ((node = ulist_next(blocks, &uiter))) { if (!node->aux) continue; - eie = (struct extent_inode_elem *)(uintptr_t)node->aux; + eie = unode_aux_to_inode_list(node); free_inode_elem_list(eie); node->aux = 0; } -- cgit v1.2.3 From e0c476b128e37daa37d630dd68da5681e9c16bab Mon Sep 17 00:00:00 2001 From: Jeff Mahoney Date: Wed, 28 Jun 2017 21:56:57 -0600 Subject: btrfs: backref, cleanup __ namespace abuse We typically use __ to indicate a helper routine that shouldn't be called directly without understanding the proper context required to do so. We use static functions to indicate that a function is private to a particular C file. The backref code uses static function and __ prefixes on nearly everything, which makes the code difficult to read and establishes a pattern for future code that shouldn't be followed. This patch drops all the unnecessary prefixes. Signed-off-by: Jeff Mahoney Signed-off-by: David Sterba --- fs/btrfs/backref.c | 225 ++++++++++++++++++++++++++--------------------------- 1 file changed, 109 insertions(+), 116 deletions(-) (limited to 'fs/btrfs/backref.c') diff --git a/fs/btrfs/backref.c b/fs/btrfs/backref.c index 4a7a4b032c2f..3725277f6e08 100644 --- a/fs/btrfs/backref.c +++ b/fs/btrfs/backref.c @@ -387,7 +387,7 @@ static int find_extent_in_eb(const struct extent_buffer *eb, /* * this structure records all encountered refs on the way up to the root */ -struct __prelim_ref { +struct prelim_ref { struct list_head list; u64 root_id; struct btrfs_key key_for_search; @@ -403,7 +403,7 @@ static struct kmem_cache *btrfs_prelim_ref_cache; int __init btrfs_prelim_ref_init(void) { btrfs_prelim_ref_cache = kmem_cache_create("btrfs_prelim_ref", - sizeof(struct __prelim_ref), + sizeof(struct prelim_ref), 0, SLAB_MEM_SPREAD, NULL); @@ -449,19 +449,17 @@ void btrfs_prelim_ref_exit(void) * * - column 1, 3: we've the parent -> done * - column 2: we take the first key from the block to find the parent - * (see __add_missing_keys) + * (see add_missing_keys) * - column 4: we use the key to find the parent * * additional information that's available but not required to find the parent * block might help in merging entries to gain some speed. */ - -static int __add_prelim_ref(struct list_head *head, u64 root_id, - const struct btrfs_key *key, int level, - u64 parent, u64 wanted_disk_byte, int count, - gfp_t gfp_mask) +static int add_prelim_ref(struct list_head *head, u64 root_id, + const struct btrfs_key *key, int level, u64 parent, + u64 wanted_disk_byte, int count, gfp_t gfp_mask) { - struct __prelim_ref *ref; + struct prelim_ref *ref; if (root_id == BTRFS_DATA_RELOC_TREE_OBJECTID) return 0; @@ -510,7 +508,7 @@ static int __add_prelim_ref(struct list_head *head, u64 root_id, } static int add_all_parents(struct btrfs_root *root, struct btrfs_path *path, - struct ulist *parents, struct __prelim_ref *ref, + struct ulist *parents, struct prelim_ref *ref, int level, u64 time_seq, const u64 *extent_item_pos, u64 total_refs) { @@ -600,11 +598,10 @@ next: * resolve an indirect backref in the form (root_id, key, level) * to a logical address */ -static int __resolve_indirect_ref(struct btrfs_fs_info *fs_info, - struct btrfs_path *path, u64 time_seq, - struct __prelim_ref *ref, - struct ulist *parents, - const u64 *extent_item_pos, u64 total_refs) +static int resolve_indirect_ref(struct btrfs_fs_info *fs_info, + struct btrfs_path *path, u64 time_seq, + struct prelim_ref *ref, struct ulist *parents, + const u64 *extent_item_pos, u64 total_refs) { struct btrfs_root *root; struct btrfs_key root_key; @@ -693,17 +690,17 @@ unode_aux_to_inode_list(struct ulist_node *node) /* * resolve all indirect backrefs from the list */ -static int __resolve_indirect_refs(struct btrfs_fs_info *fs_info, - struct btrfs_path *path, u64 time_seq, - struct list_head *head, - const u64 *extent_item_pos, u64 total_refs, - u64 root_objectid) +static int resolve_indirect_refs(struct btrfs_fs_info *fs_info, + struct btrfs_path *path, u64 time_seq, + struct list_head *head, + const u64 *extent_item_pos, u64 total_refs, + u64 root_objectid) { int err; int ret = 0; - struct __prelim_ref *ref; - struct __prelim_ref *ref_safe; - struct __prelim_ref *new_ref; + struct prelim_ref *ref; + struct prelim_ref *ref_safe; + struct prelim_ref *new_ref; struct ulist *parents; struct ulist_node *node; struct ulist_iterator uiter; @@ -726,9 +723,9 @@ static int __resolve_indirect_refs(struct btrfs_fs_info *fs_info, ret = BACKREF_FOUND_SHARED; goto out; } - err = __resolve_indirect_ref(fs_info, path, time_seq, ref, - parents, extent_item_pos, - total_refs); + err = resolve_indirect_ref(fs_info, path, time_seq, ref, + parents, extent_item_pos, + total_refs); /* * we can only tolerate ENOENT,otherwise,we should catch error * and return directly. @@ -766,8 +763,8 @@ out: return ret; } -static inline int ref_for_same_block(struct __prelim_ref *ref1, - struct __prelim_ref *ref2) +static inline int ref_for_same_block(struct prelim_ref *ref1, + struct prelim_ref *ref2) { if (ref1->level != ref2->level) return 0; @@ -788,10 +785,10 @@ static inline int ref_for_same_block(struct __prelim_ref *ref1, /* * read tree blocks and add keys where required. */ -static int __add_missing_keys(struct btrfs_fs_info *fs_info, - struct list_head *head) +static int add_missing_keys(struct btrfs_fs_info *fs_info, + struct list_head *head) { - struct __prelim_ref *ref; + struct prelim_ref *ref; struct extent_buffer *eb; list_for_each_entry(ref, head, list) { @@ -821,20 +818,20 @@ static int __add_missing_keys(struct btrfs_fs_info *fs_info, /* * merge backrefs and adjust counts accordingly * - * FIXME: For MERGE_IDENTICAL_KEYS, if we add more keys in __add_prelim_ref + * FIXME: For MERGE_IDENTICAL_KEYS, if we add more keys in add_prelim_ref * then we can merge more here. Additionally, we could even add a key * range for the blocks we looked into to merge even more (-> replace * unresolved refs by those having a parent). */ -static void __merge_refs(struct list_head *head, enum merge_mode mode) +static void merge_refs(struct list_head *head, enum merge_mode mode) { - struct __prelim_ref *pos1; + struct prelim_ref *pos1; list_for_each_entry(pos1, head, list) { - struct __prelim_ref *pos2 = pos1, *tmp; + struct prelim_ref *pos2 = pos1, *tmp; list_for_each_entry_safe_continue(pos2, tmp, head, list) { - struct __prelim_ref *ref1 = pos1, *ref2 = pos2; + struct prelim_ref *ref1 = pos1, *ref2 = pos2; struct extent_inode_elem *eie; if (!ref_for_same_block(ref1, ref2)) @@ -868,9 +865,9 @@ static void __merge_refs(struct list_head *head, enum merge_mode mode) * add all currently queued delayed refs from this head whose seq nr is * smaller or equal that seq to the list */ -static int __add_delayed_refs(struct btrfs_delayed_ref_head *head, u64 seq, - struct list_head *prefs, u64 *total_refs, - u64 inum) +static int add_delayed_refs(struct btrfs_delayed_ref_head *head, u64 seq, + struct list_head *prefs, u64 *total_refs, + u64 inum) { struct btrfs_delayed_ref_node *node; struct btrfs_delayed_extent_op *extent_op = head->extent_op; @@ -907,19 +904,18 @@ static int __add_delayed_refs(struct btrfs_delayed_ref_head *head, u64 seq, struct btrfs_delayed_tree_ref *ref; ref = btrfs_delayed_node_to_tree_ref(node); - ret = __add_prelim_ref(prefs, ref->root, &op_key, - ref->level + 1, 0, node->bytenr, - node->ref_mod * sgn, GFP_ATOMIC); + ret = add_prelim_ref(prefs, ref->root, &op_key, + ref->level + 1, 0, node->bytenr, + node->ref_mod * sgn, GFP_ATOMIC); break; } case BTRFS_SHARED_BLOCK_REF_KEY: { struct btrfs_delayed_tree_ref *ref; ref = btrfs_delayed_node_to_tree_ref(node); - ret = __add_prelim_ref(prefs, 0, NULL, - ref->level + 1, ref->parent, - node->bytenr, - node->ref_mod * sgn, GFP_ATOMIC); + ret = add_prelim_ref(prefs, 0, NULL, ref->level + 1, + ref->parent, node->bytenr, + node->ref_mod * sgn, GFP_ATOMIC); break; } case BTRFS_EXTENT_DATA_REF_KEY: { @@ -939,18 +935,18 @@ static int __add_delayed_refs(struct btrfs_delayed_ref_head *head, u64 seq, break; } - ret = __add_prelim_ref(prefs, ref->root, &key, 0, 0, - node->bytenr, - node->ref_mod * sgn, GFP_ATOMIC); + ret = add_prelim_ref(prefs, ref->root, &key, 0, 0, + node->bytenr, node->ref_mod * sgn, + GFP_ATOMIC); break; } case BTRFS_SHARED_DATA_REF_KEY: { struct btrfs_delayed_data_ref *ref; ref = btrfs_delayed_node_to_data_ref(node); - ret = __add_prelim_ref(prefs, 0, NULL, 0, - ref->parent, node->bytenr, - node->ref_mod * sgn, GFP_ATOMIC); + ret = add_prelim_ref(prefs, 0, NULL, 0, ref->parent, + node->bytenr, node->ref_mod * sgn, + GFP_ATOMIC); break; } default: @@ -966,10 +962,10 @@ static int __add_delayed_refs(struct btrfs_delayed_ref_head *head, u64 seq, /* * add all inline backrefs for bytenr to the list */ -static int __add_inline_refs(struct btrfs_path *path, u64 bytenr, - int *info_level, struct list_head *prefs, - struct ref_root *ref_tree, - u64 *total_refs, u64 inum) +static int add_inline_refs(struct btrfs_path *path, u64 bytenr, + int *info_level, struct list_head *prefs, + struct ref_root *ref_tree, + u64 *total_refs, u64 inum) { int ret = 0; int slot; @@ -1024,9 +1020,8 @@ static int __add_inline_refs(struct btrfs_path *path, u64 bytenr, switch (type) { case BTRFS_SHARED_BLOCK_REF_KEY: - ret = __add_prelim_ref(prefs, 0, NULL, - *info_level + 1, offset, - bytenr, 1, GFP_NOFS); + ret = add_prelim_ref(prefs, 0, NULL, *info_level + 1, + offset, bytenr, 1, GFP_NOFS); break; case BTRFS_SHARED_DATA_REF_KEY: { struct btrfs_shared_data_ref *sdref; @@ -1034,8 +1029,8 @@ static int __add_inline_refs(struct btrfs_path *path, u64 bytenr, sdref = (struct btrfs_shared_data_ref *)(iref + 1); count = btrfs_shared_data_ref_count(leaf, sdref); - ret = __add_prelim_ref(prefs, 0, NULL, 0, offset, - bytenr, count, GFP_NOFS); + ret = add_prelim_ref(prefs, 0, NULL, 0, offset, + bytenr, count, GFP_NOFS); if (ref_tree) { if (!ret) ret = ref_tree_add(ref_tree, 0, 0, 0, @@ -1046,9 +1041,9 @@ static int __add_inline_refs(struct btrfs_path *path, u64 bytenr, break; } case BTRFS_TREE_BLOCK_REF_KEY: - ret = __add_prelim_ref(prefs, offset, NULL, - *info_level + 1, 0, - bytenr, 1, GFP_NOFS); + ret = add_prelim_ref(prefs, offset, NULL, + *info_level + 1, 0, + bytenr, 1, GFP_NOFS); break; case BTRFS_EXTENT_DATA_REF_KEY: { struct btrfs_extent_data_ref *dref; @@ -1068,8 +1063,8 @@ static int __add_inline_refs(struct btrfs_path *path, u64 bytenr, } root = btrfs_extent_data_ref_root(leaf, dref); - ret = __add_prelim_ref(prefs, root, &key, 0, 0, - bytenr, count, GFP_NOFS); + ret = add_prelim_ref(prefs, root, &key, 0, 0, + bytenr, count, GFP_NOFS); if (ref_tree) { if (!ret) ret = ref_tree_add(ref_tree, root, @@ -1095,10 +1090,10 @@ static int __add_inline_refs(struct btrfs_path *path, u64 bytenr, /* * add all non-inline backrefs for bytenr to the list */ -static int __add_keyed_refs(struct btrfs_fs_info *fs_info, - struct btrfs_path *path, u64 bytenr, - int info_level, struct list_head *prefs, - struct ref_root *ref_tree, u64 inum) +static int add_keyed_refs(struct btrfs_fs_info *fs_info, + struct btrfs_path *path, u64 bytenr, + int info_level, struct list_head *prefs, + struct ref_root *ref_tree, u64 inum) { struct btrfs_root *extent_root = fs_info->extent_root; int ret; @@ -1128,9 +1123,8 @@ static int __add_keyed_refs(struct btrfs_fs_info *fs_info, switch (key.type) { case BTRFS_SHARED_BLOCK_REF_KEY: - ret = __add_prelim_ref(prefs, 0, NULL, - info_level + 1, key.offset, - bytenr, 1, GFP_NOFS); + ret = add_prelim_ref(prefs, 0, NULL, info_level + 1, + key.offset, bytenr, 1, GFP_NOFS); break; case BTRFS_SHARED_DATA_REF_KEY: { struct btrfs_shared_data_ref *sdref; @@ -1139,8 +1133,8 @@ static int __add_keyed_refs(struct btrfs_fs_info *fs_info, sdref = btrfs_item_ptr(leaf, slot, struct btrfs_shared_data_ref); count = btrfs_shared_data_ref_count(leaf, sdref); - ret = __add_prelim_ref(prefs, 0, NULL, 0, key.offset, - bytenr, count, GFP_NOFS); + ret = add_prelim_ref(prefs, 0, NULL, 0, key.offset, + bytenr, count, GFP_NOFS); if (ref_tree) { if (!ret) ret = ref_tree_add(ref_tree, 0, 0, 0, @@ -1151,9 +1145,9 @@ static int __add_keyed_refs(struct btrfs_fs_info *fs_info, break; } case BTRFS_TREE_BLOCK_REF_KEY: - ret = __add_prelim_ref(prefs, key.offset, NULL, - info_level + 1, 0, - bytenr, 1, GFP_NOFS); + ret = add_prelim_ref(prefs, key.offset, NULL, + info_level + 1, 0, + bytenr, 1, GFP_NOFS); break; case BTRFS_EXTENT_DATA_REF_KEY: { struct btrfs_extent_data_ref *dref; @@ -1174,8 +1168,8 @@ static int __add_keyed_refs(struct btrfs_fs_info *fs_info, } root = btrfs_extent_data_ref_root(leaf, dref); - ret = __add_prelim_ref(prefs, root, &key, 0, 0, - bytenr, count, GFP_NOFS); + ret = add_prelim_ref(prefs, root, &key, 0, 0, + bytenr, count, GFP_NOFS); if (ref_tree) { if (!ret) ret = ref_tree_add(ref_tree, root, @@ -1230,7 +1224,7 @@ static int find_parent_nodes(struct btrfs_trans_handle *trans, int ret; struct list_head prefs_delayed; struct list_head prefs; - struct __prelim_ref *ref; + struct prelim_ref *ref; struct extent_inode_elem *eie = NULL; struct ref_root *ref_tree = NULL; u64 total_refs = 0; @@ -1311,9 +1305,9 @@ again: goto again; } spin_unlock(&delayed_refs->lock); - ret = __add_delayed_refs(head, time_seq, - &prefs_delayed, &total_refs, - inum); + ret = add_delayed_refs(head, time_seq, + &prefs_delayed, &total_refs, + inum); mutex_unlock(&head->mutex); if (ret) goto out; @@ -1363,15 +1357,13 @@ again: if (key.objectid == bytenr && (key.type == BTRFS_EXTENT_ITEM_KEY || key.type == BTRFS_METADATA_ITEM_KEY)) { - ret = __add_inline_refs(path, bytenr, - &info_level, &prefs, - ref_tree, &total_refs, - inum); + ret = add_inline_refs(path, bytenr, &info_level, + &prefs, ref_tree, &total_refs, + inum); if (ret) goto out; - ret = __add_keyed_refs(fs_info, path, bytenr, - info_level, &prefs, - ref_tree, inum); + ret = add_keyed_refs(fs_info, path, bytenr, info_level, + &prefs, ref_tree, inum); if (ret) goto out; } @@ -1380,22 +1372,22 @@ again: list_splice_init(&prefs_delayed, &prefs); - ret = __add_missing_keys(fs_info, &prefs); + ret = add_missing_keys(fs_info, &prefs); if (ret) goto out; - __merge_refs(&prefs, MERGE_IDENTICAL_KEYS); + merge_refs(&prefs, MERGE_IDENTICAL_KEYS); - ret = __resolve_indirect_refs(fs_info, path, time_seq, &prefs, - extent_item_pos, total_refs, - root_objectid); + ret = resolve_indirect_refs(fs_info, path, time_seq, &prefs, + extent_item_pos, total_refs, + root_objectid); if (ret) goto out; - __merge_refs(&prefs, MERGE_IDENTICAL_PARENTS); + merge_refs(&prefs, MERGE_IDENTICAL_PARENTS); while (!list_empty(&prefs)) { - ref = list_first_entry(&prefs, struct __prelim_ref, list); + ref = list_first_entry(&prefs, struct prelim_ref, list); WARN_ON(ref->count < 0); if (roots && ref->count && ref->root_id && ref->parent == 0) { if (root_objectid && ref->root_id != root_objectid) { @@ -1457,12 +1449,12 @@ out: btrfs_free_path(path); ref_root_free(ref_tree); while (!list_empty(&prefs)) { - ref = list_first_entry(&prefs, struct __prelim_ref, list); + ref = list_first_entry(&prefs, struct prelim_ref, list); list_del(&ref->list); kmem_cache_free(btrfs_prelim_ref_cache, ref); } while (!list_empty(&prefs_delayed)) { - ref = list_first_entry(&prefs_delayed, struct __prelim_ref, + ref = list_first_entry(&prefs_delayed, struct prelim_ref, list); list_del(&ref->list); kmem_cache_free(btrfs_prelim_ref_cache, ref); @@ -1532,9 +1524,9 @@ static int btrfs_find_all_leafs(struct btrfs_trans_handle *trans, * * returns 0 on success, < 0 on error. */ -static int __btrfs_find_all_roots(struct btrfs_trans_handle *trans, - struct btrfs_fs_info *fs_info, u64 bytenr, - u64 time_seq, struct ulist **roots) +static int btrfs_find_all_roots_safe(struct btrfs_trans_handle *trans, + struct btrfs_fs_info *fs_info, u64 bytenr, + u64 time_seq, struct ulist **roots) { struct ulist *tmp; struct ulist_node *node = NULL; @@ -1578,7 +1570,8 @@ int btrfs_find_all_roots(struct btrfs_trans_handle *trans, if (!trans) down_read(&fs_info->commit_root_sem); - ret = __btrfs_find_all_roots(trans, fs_info, bytenr, time_seq, roots); + ret = btrfs_find_all_roots_safe(trans, fs_info, bytenr, + time_seq, roots); if (!trans) up_read(&fs_info->commit_root_sem); return ret; @@ -1877,17 +1870,17 @@ int extent_from_logical(struct btrfs_fs_info *fs_info, u64 logical, * helper function to iterate extent inline refs. ptr must point to a 0 value * for the first call and may be modified. it is used to track state. * if more refs exist, 0 is returned and the next call to - * __get_extent_inline_ref must pass the modified ptr parameter to get the + * get_extent_inline_ref must pass the modified ptr parameter to get the * next ref. after the last ref was processed, 1 is returned. * returns <0 on error */ -static int __get_extent_inline_ref(unsigned long *ptr, - const struct extent_buffer *eb, - const struct btrfs_key *key, - const struct btrfs_extent_item *ei, - u32 item_size, - struct btrfs_extent_inline_ref **out_eiref, - int *out_type) +static int get_extent_inline_ref(unsigned long *ptr, + const struct extent_buffer *eb, + const struct btrfs_key *key, + const struct btrfs_extent_item *ei, + u32 item_size, + struct btrfs_extent_inline_ref **out_eiref, + int *out_type) { unsigned long end; u64 flags; @@ -1930,7 +1923,7 @@ static int __get_extent_inline_ref(unsigned long *ptr, /* * reads the tree block backref for an extent. tree level and root are returned * through out_level and out_root. ptr must point to a 0 value for the first - * call and may be modified (see __get_extent_inline_ref comment). + * call and may be modified (see get_extent_inline_ref comment). * returns 0 if data was provided, 1 if there was no more data to provide or * <0 on error. */ @@ -1946,7 +1939,7 @@ int tree_backref_for_extent(unsigned long *ptr, struct extent_buffer *eb, return 1; while (1) { - ret = __get_extent_inline_ref(ptr, eb, key, ei, item_size, + ret = get_extent_inline_ref(ptr, eb, key, ei, item_size, &eiref, &type); if (ret < 0) return ret; @@ -2043,8 +2036,8 @@ int iterate_extent_inodes(struct btrfs_fs_info *fs_info, ULIST_ITER_INIT(&ref_uiter); while (!ret && (ref_node = ulist_next(refs, &ref_uiter))) { - ret = __btrfs_find_all_roots(trans, fs_info, ref_node->val, - tree_mod_seq_elem.seq, &roots); + ret = btrfs_find_all_roots_safe(trans, fs_info, ref_node->val, + tree_mod_seq_elem.seq, &roots); if (ret) break; ULIST_ITER_INIT(&root_uiter); -- cgit v1.2.3 From bb739cf08e8f32ea0b4a6d2ae22466488182c2fe Mon Sep 17 00:00:00 2001 From: Edmund Nadolski Date: Wed, 28 Jun 2017 21:56:58 -0600 Subject: btrfs: btrfs_check_shared should manage its own transaction Commit afce772e87c3 ("btrfs: fix check_shared for fiemap ioctl") added transaction semantics around calls to btrfs_check_shared() in order to provide accurate accounting of delayed refs. The transaction management should be done inside btrfs_check_shared(), so that callers do not need to manage transactions individually. Signed-off-by: Edmund Nadolski Signed-off-by: Jeff Mahoney Reviewed-by: David Sterba Signed-off-by: David Sterba --- fs/btrfs/backref.c | 30 +++++++++++++++++++----------- fs/btrfs/backref.h | 4 +--- fs/btrfs/extent_io.c | 22 +++------------------- 3 files changed, 23 insertions(+), 33 deletions(-) (limited to 'fs/btrfs/backref.c') diff --git a/fs/btrfs/backref.c b/fs/btrfs/backref.c index 3725277f6e08..35cfa388dc0b 100644 --- a/fs/btrfs/backref.c +++ b/fs/btrfs/backref.c @@ -1580,20 +1580,21 @@ int btrfs_find_all_roots(struct btrfs_trans_handle *trans, /** * btrfs_check_shared - tell us whether an extent is shared * - * @trans: optional trans handle - * * btrfs_check_shared uses the backref walking code but will short * circuit as soon as it finds a root or inode that doesn't match the * one passed in. This provides a significant performance benefit for * callers (such as fiemap) which want to know whether the extent is * shared but do not need a ref count. * + * This attempts to allocate a transaction in order to account for + * delayed refs, but continues on even when the alloc fails. + * * Return: 0 if extent is not shared, 1 if it is shared, < 0 on error. */ -int btrfs_check_shared(struct btrfs_trans_handle *trans, - struct btrfs_fs_info *fs_info, u64 root_objectid, - u64 inum, u64 bytenr) +int btrfs_check_shared(struct btrfs_root *root, u64 inum, u64 bytenr) { + struct btrfs_fs_info *fs_info = root->fs_info; + struct btrfs_trans_handle *trans; struct ulist *tmp = NULL; struct ulist *roots = NULL; struct ulist_iterator uiter; @@ -1609,14 +1610,18 @@ int btrfs_check_shared(struct btrfs_trans_handle *trans, return -ENOMEM; } - if (trans) - btrfs_get_tree_mod_seq(fs_info, &elem); - else + trans = btrfs_join_transaction(root); + if (IS_ERR(trans)) { + trans = NULL; down_read(&fs_info->commit_root_sem); + } else { + btrfs_get_tree_mod_seq(fs_info, &elem); + } + ULIST_ITER_INIT(&uiter); while (1) { ret = find_parent_nodes(trans, fs_info, bytenr, elem.seq, tmp, - roots, NULL, root_objectid, inum, 1); + roots, NULL, root->objectid, inum, 1); if (ret == BACKREF_FOUND_SHARED) { /* this is the only condition under which we return 1 */ ret = 1; @@ -1631,10 +1636,13 @@ int btrfs_check_shared(struct btrfs_trans_handle *trans, bytenr = node->val; cond_resched(); } - if (trans) + + if (trans) { btrfs_put_tree_mod_seq(fs_info, &elem); - else + btrfs_end_transaction(trans); + } else { up_read(&fs_info->commit_root_sem); + } ulist_free(tmp); ulist_free(roots); return ret; diff --git a/fs/btrfs/backref.h b/fs/btrfs/backref.h index 9c41fbac3009..f9428aaaa77a 100644 --- a/fs/btrfs/backref.h +++ b/fs/btrfs/backref.h @@ -68,9 +68,7 @@ int btrfs_find_one_extref(struct btrfs_root *root, u64 inode_objectid, u64 start_off, struct btrfs_path *path, struct btrfs_inode_extref **ret_extref, u64 *found_off); -int btrfs_check_shared(struct btrfs_trans_handle *trans, - struct btrfs_fs_info *fs_info, u64 root_objectid, - u64 inum, u64 bytenr); +int btrfs_check_shared(struct btrfs_root *root, u64 inum, u64 bytenr); int __init btrfs_prelim_ref_init(void); void btrfs_prelim_ref_exit(void); diff --git a/fs/btrfs/extent_io.c b/fs/btrfs/extent_io.c index d6f761b4fae0..7dd1b2dc7c68 100644 --- a/fs/btrfs/extent_io.c +++ b/fs/btrfs/extent_io.c @@ -20,7 +20,6 @@ #include "locking.h" #include "rcu-string.h" #include "backref.h" -#include "transaction.h" static struct kmem_cache *extent_state_cache; static struct kmem_cache *extent_buffer_cache; @@ -4606,24 +4605,11 @@ int extent_fiemap(struct inode *inode, struct fiemap_extent_info *fieinfo, flags |= (FIEMAP_EXTENT_DELALLOC | FIEMAP_EXTENT_UNKNOWN); } else if (fieinfo->fi_extents_max) { - struct btrfs_trans_handle *trans; - u64 bytenr = em->block_start - (em->start - em->orig_start); disko = em->block_start + offset_in_extent; - /* - * We need a trans handle to get delayed refs - */ - trans = btrfs_join_transaction(root); - /* - * It's OK if we can't start a trans we can still check - * from commit_root - */ - if (IS_ERR(trans)) - trans = NULL; - /* * As btrfs supports shared space, this information * can be exported to userspace tools via @@ -4631,11 +4617,9 @@ int extent_fiemap(struct inode *inode, struct fiemap_extent_info *fieinfo, * then we're just getting a count and we can skip the * lookup stuff. */ - ret = btrfs_check_shared(trans, root->fs_info, - root->objectid, - btrfs_ino(BTRFS_I(inode)), bytenr); - if (trans) - btrfs_end_transaction(trans); + ret = btrfs_check_shared(root, + btrfs_ino(BTRFS_I(inode)), + bytenr); if (ret < 0) goto out_free; if (ret) -- cgit v1.2.3 From f6954245d9e17902a66a1253d2a3afc05e335172 Mon Sep 17 00:00:00 2001 From: Edmund Nadolski Date: Wed, 28 Jun 2017 21:56:59 -0600 Subject: btrfs: remove ref_tree implementation from backref.c Commit afce772e87c3 ("btrfs: fix check_shared for fiemap ioctl") added the ref_tree code in backref.c to reduce backref searching for shared extents under the FIEMAP ioctl. This code will not be compatible with the upcoming rbtree changes for improved backref searching, so this patch removes the ref_tree code. The rbtree changes will provide the equivalent functionality for FIEMAP. The above commit also introduced transaction semantics around calls to btrfs_check_shared() in order to accurately account for delayed refs. This functionality needs to be retained, so a complete revert of the above commit is not desirable. This patch therefore removes the ref_tree portion of the commit as above, however it does not remove the transaction portion. Signed-off-by: Edmund Nadolski Signed-off-by: Jeff Mahoney Reviewed-by: David Sterba Signed-off-by: David Sterba --- fs/btrfs/backref.c | 355 ++--------------------------------------------------- 1 file changed, 7 insertions(+), 348 deletions(-) (limited to 'fs/btrfs/backref.c') diff --git a/fs/btrfs/backref.c b/fs/btrfs/backref.c index 35cfa388dc0b..6cac5ab8d5e0 100644 --- a/fs/btrfs/backref.c +++ b/fs/btrfs/backref.c @@ -40,265 +40,6 @@ struct extent_inode_elem { struct extent_inode_elem *next; }; -/* - * ref_root is used as the root of the ref tree that hold a collection - * of unique references. - */ -struct ref_root { - struct rb_root rb_root; - - /* - * The unique_refs represents the number of ref_nodes with a positive - * count stored in the tree. Even if a ref_node (the count is greater - * than one) is added, the unique_refs will only increase by one. - */ - unsigned int unique_refs; -}; - -/* ref_node is used to store a unique reference to the ref tree. */ -struct ref_node { - struct rb_node rb_node; - - /* For NORMAL_REF, otherwise all these fields should be set to 0 */ - u64 root_id; - u64 object_id; - u64 offset; - - /* For SHARED_REF, otherwise parent field should be set to 0 */ - u64 parent; - - /* Ref to the ref_mod of btrfs_delayed_ref_node */ - int ref_mod; -}; - -/* Dynamically allocate and initialize a ref_root */ -static struct ref_root *ref_root_alloc(void) -{ - struct ref_root *ref_tree; - - ref_tree = kmalloc(sizeof(*ref_tree), GFP_NOFS); - if (!ref_tree) - return NULL; - - ref_tree->rb_root = RB_ROOT; - ref_tree->unique_refs = 0; - - return ref_tree; -} - -/* Free all nodes in the ref tree, and reinit ref_root */ -static void ref_root_fini(struct ref_root *ref_tree) -{ - struct ref_node *node; - struct rb_node *next; - - while ((next = rb_first(&ref_tree->rb_root)) != NULL) { - node = rb_entry(next, struct ref_node, rb_node); - rb_erase(next, &ref_tree->rb_root); - kfree(node); - } - - ref_tree->rb_root = RB_ROOT; - ref_tree->unique_refs = 0; -} - -static void ref_root_free(struct ref_root *ref_tree) -{ - if (!ref_tree) - return; - - ref_root_fini(ref_tree); - kfree(ref_tree); -} - -/* - * Compare ref_node with (root_id, object_id, offset, parent) - * - * The function compares two ref_node a and b. It returns an integer less - * than, equal to, or greater than zero , respectively, to be less than, to - * equal, or be greater than b. - */ -static int ref_node_cmp(struct ref_node *a, struct ref_node *b) -{ - if (a->root_id < b->root_id) - return -1; - else if (a->root_id > b->root_id) - return 1; - - if (a->object_id < b->object_id) - return -1; - else if (a->object_id > b->object_id) - return 1; - - if (a->offset < b->offset) - return -1; - else if (a->offset > b->offset) - return 1; - - if (a->parent < b->parent) - return -1; - else if (a->parent > b->parent) - return 1; - - return 0; -} - -/* - * Search ref_node with (root_id, object_id, offset, parent) in the tree - * - * if found, the pointer of the ref_node will be returned; - * if not found, NULL will be returned and pos will point to the rb_node for - * insert, pos_parent will point to pos'parent for insert; -*/ -static struct ref_node *__ref_tree_search(struct ref_root *ref_tree, - struct rb_node ***pos, - struct rb_node **pos_parent, - u64 root_id, u64 object_id, - u64 offset, u64 parent) -{ - struct ref_node *cur = NULL; - struct ref_node entry; - int ret; - - entry.root_id = root_id; - entry.object_id = object_id; - entry.offset = offset; - entry.parent = parent; - - *pos = &ref_tree->rb_root.rb_node; - - while (**pos) { - *pos_parent = **pos; - cur = rb_entry(*pos_parent, struct ref_node, rb_node); - - ret = ref_node_cmp(cur, &entry); - if (ret > 0) - *pos = &(**pos)->rb_left; - else if (ret < 0) - *pos = &(**pos)->rb_right; - else - return cur; - } - - return NULL; -} - -/* - * Insert a ref_node to the ref tree - * @pos used for specifiy the position to insert - * @pos_parent for specifiy pos's parent - * - * success, return 0; - * ref_node already exists, return -EEXIST; -*/ -static int ref_tree_insert(struct ref_root *ref_tree, struct rb_node **pos, - struct rb_node *pos_parent, struct ref_node *ins) -{ - struct rb_node **p = NULL; - struct rb_node *parent = NULL; - struct ref_node *cur = NULL; - - if (!pos) { - cur = __ref_tree_search(ref_tree, &p, &parent, ins->root_id, - ins->object_id, ins->offset, - ins->parent); - if (cur) - return -EEXIST; - } else { - p = pos; - parent = pos_parent; - } - - rb_link_node(&ins->rb_node, parent, p); - rb_insert_color(&ins->rb_node, &ref_tree->rb_root); - - return 0; -} - -/* Erase and free ref_node, caller should update ref_root->unique_refs */ -static void ref_tree_remove(struct ref_root *ref_tree, struct ref_node *node) -{ - rb_erase(&node->rb_node, &ref_tree->rb_root); - kfree(node); -} - -/* - * Update ref_root->unique_refs - * - * Call __ref_tree_search - * 1. if ref_node doesn't exist, ref_tree_insert this node, and update - * ref_root->unique_refs: - * if ref_node->ref_mod > 0, ref_root->unique_refs++; - * if ref_node->ref_mod < 0, do noting; - * - * 2. if ref_node is found, then get origin ref_node->ref_mod, and update - * ref_node->ref_mod. - * if ref_node->ref_mod is equal to 0,then call ref_tree_remove - * - * according to origin_mod and new_mod, update ref_root->items - * +----------------+--------------+-------------+ - * | |new_count <= 0|new_count > 0| - * +----------------+--------------+-------------+ - * |origin_count < 0| 0 | 1 | - * +----------------+--------------+-------------+ - * |origin_count > 0| -1 | 0 | - * +----------------+--------------+-------------+ - * - * In case of allocation failure, -ENOMEM is returned and the ref_tree stays - * unaltered. - * Success, return 0 - */ -static int ref_tree_add(struct ref_root *ref_tree, u64 root_id, u64 object_id, - u64 offset, u64 parent, int count) -{ - struct ref_node *node = NULL; - struct rb_node **pos = NULL; - struct rb_node *pos_parent = NULL; - int origin_count; - int ret; - - if (!count) - return 0; - - node = __ref_tree_search(ref_tree, &pos, &pos_parent, root_id, - object_id, offset, parent); - if (node == NULL) { - node = kmalloc(sizeof(*node), GFP_NOFS); - if (!node) - return -ENOMEM; - - node->root_id = root_id; - node->object_id = object_id; - node->offset = offset; - node->parent = parent; - node->ref_mod = count; - - ret = ref_tree_insert(ref_tree, pos, pos_parent, node); - ASSERT(!ret); - if (ret) { - kfree(node); - return ret; - } - - ref_tree->unique_refs += node->ref_mod > 0 ? 1 : 0; - - return 0; - } - - origin_count = node->ref_mod; - node->ref_mod += count; - - if (node->ref_mod > 0) - ref_tree->unique_refs += origin_count > 0 ? 0 : 1; - else if (node->ref_mod <= 0) - ref_tree->unique_refs += origin_count > 0 ? -1 : 0; - - if (!node->ref_mod) - ref_tree_remove(ref_tree, node); - - return 0; -} - static int check_extent_in_eb(const struct btrfs_key *key, const struct extent_buffer *eb, const struct btrfs_file_extent_item *fi, @@ -964,7 +705,6 @@ static int add_delayed_refs(struct btrfs_delayed_ref_head *head, u64 seq, */ static int add_inline_refs(struct btrfs_path *path, u64 bytenr, int *info_level, struct list_head *prefs, - struct ref_root *ref_tree, u64 *total_refs, u64 inum) { int ret = 0; @@ -1031,13 +771,6 @@ static int add_inline_refs(struct btrfs_path *path, u64 bytenr, count = btrfs_shared_data_ref_count(leaf, sdref); ret = add_prelim_ref(prefs, 0, NULL, 0, offset, bytenr, count, GFP_NOFS); - if (ref_tree) { - if (!ret) - ret = ref_tree_add(ref_tree, 0, 0, 0, - bytenr, count); - if (!ret && ref_tree->unique_refs > 1) - ret = BACKREF_FOUND_SHARED; - } break; } case BTRFS_TREE_BLOCK_REF_KEY: @@ -1065,15 +798,6 @@ static int add_inline_refs(struct btrfs_path *path, u64 bytenr, root = btrfs_extent_data_ref_root(leaf, dref); ret = add_prelim_ref(prefs, root, &key, 0, 0, bytenr, count, GFP_NOFS); - if (ref_tree) { - if (!ret) - ret = ref_tree_add(ref_tree, root, - key.objectid, - key.offset, 0, - count); - if (!ret && ref_tree->unique_refs > 1) - ret = BACKREF_FOUND_SHARED; - } break; } default: @@ -1092,8 +816,7 @@ static int add_inline_refs(struct btrfs_path *path, u64 bytenr, */ static int add_keyed_refs(struct btrfs_fs_info *fs_info, struct btrfs_path *path, u64 bytenr, - int info_level, struct list_head *prefs, - struct ref_root *ref_tree, u64 inum) + int info_level, struct list_head *prefs, u64 inum) { struct btrfs_root *extent_root = fs_info->extent_root; int ret; @@ -1135,13 +858,6 @@ static int add_keyed_refs(struct btrfs_fs_info *fs_info, count = btrfs_shared_data_ref_count(leaf, sdref); ret = add_prelim_ref(prefs, 0, NULL, 0, key.offset, bytenr, count, GFP_NOFS); - if (ref_tree) { - if (!ret) - ret = ref_tree_add(ref_tree, 0, 0, 0, - bytenr, count); - if (!ret && ref_tree->unique_refs > 1) - ret = BACKREF_FOUND_SHARED; - } break; } case BTRFS_TREE_BLOCK_REF_KEY: @@ -1170,15 +886,6 @@ static int add_keyed_refs(struct btrfs_fs_info *fs_info, root = btrfs_extent_data_ref_root(leaf, dref); ret = add_prelim_ref(prefs, root, &key, 0, 0, bytenr, count, GFP_NOFS); - if (ref_tree) { - if (!ret) - ret = ref_tree_add(ref_tree, root, - key.objectid, - key.offset, 0, - count); - if (!ret && ref_tree->unique_refs > 1) - ret = BACKREF_FOUND_SHARED; - } break; } default: @@ -1205,16 +912,13 @@ static int add_keyed_refs(struct btrfs_fs_info *fs_info, * commit root. * The special case is for qgroup to search roots in commit_transaction(). * - * If check_shared is set to 1, any extent has more than one ref item, will - * be returned BACKREF_FOUND_SHARED immediately. - * * FIXME some caching might speed things up */ static int find_parent_nodes(struct btrfs_trans_handle *trans, struct btrfs_fs_info *fs_info, u64 bytenr, u64 time_seq, struct ulist *refs, struct ulist *roots, const u64 *extent_item_pos, - u64 root_objectid, u64 inum, int check_shared) + u64 root_objectid, u64 inum) { struct btrfs_key key; struct btrfs_path *path; @@ -1226,7 +930,6 @@ static int find_parent_nodes(struct btrfs_trans_handle *trans, struct list_head prefs; struct prelim_ref *ref; struct extent_inode_elem *eie = NULL; - struct ref_root *ref_tree = NULL; u64 total_refs = 0; INIT_LIST_HEAD(&prefs); @@ -1258,18 +961,6 @@ static int find_parent_nodes(struct btrfs_trans_handle *trans, again: head = NULL; - if (check_shared) { - if (!ref_tree) { - ref_tree = ref_root_alloc(); - if (!ref_tree) { - ret = -ENOMEM; - goto out; - } - } else { - ref_root_fini(ref_tree); - } - } - ret = btrfs_search_slot(trans, fs_info->extent_root, &key, path, 0, 0); if (ret < 0) goto out; @@ -1314,36 +1005,6 @@ again: } else { spin_unlock(&delayed_refs->lock); } - - if (check_shared && !list_empty(&prefs_delayed)) { - /* - * Add all delay_ref to the ref_tree and check if there - * are multiple ref items added. - */ - list_for_each_entry(ref, &prefs_delayed, list) { - if (ref->key_for_search.type) { - ret = ref_tree_add(ref_tree, - ref->root_id, - ref->key_for_search.objectid, - ref->key_for_search.offset, - 0, ref->count); - if (ret) - goto out; - } else { - ret = ref_tree_add(ref_tree, 0, 0, 0, - ref->parent, ref->count); - if (ret) - goto out; - } - - } - - if (ref_tree->unique_refs > 1) { - ret = BACKREF_FOUND_SHARED; - goto out; - } - - } } if (path->slots[0]) { @@ -1358,12 +1019,11 @@ again: (key.type == BTRFS_EXTENT_ITEM_KEY || key.type == BTRFS_METADATA_ITEM_KEY)) { ret = add_inline_refs(path, bytenr, &info_level, - &prefs, ref_tree, &total_refs, - inum); + &prefs, &total_refs, inum); if (ret) goto out; ret = add_keyed_refs(fs_info, path, bytenr, info_level, - &prefs, ref_tree, inum); + &prefs, inum); if (ret) goto out; } @@ -1447,7 +1107,6 @@ again: out: btrfs_free_path(path); - ref_root_free(ref_tree); while (!list_empty(&prefs)) { ref = list_first_entry(&prefs, struct prelim_ref, list); list_del(&ref->list); @@ -1502,7 +1161,7 @@ static int btrfs_find_all_leafs(struct btrfs_trans_handle *trans, return -ENOMEM; ret = find_parent_nodes(trans, fs_info, bytenr, time_seq, - *leafs, NULL, extent_item_pos, 0, 0, 0); + *leafs, NULL, extent_item_pos, 0, 0); if (ret < 0 && ret != -ENOENT) { free_leaf_list(*leafs); return ret; @@ -1545,7 +1204,7 @@ static int btrfs_find_all_roots_safe(struct btrfs_trans_handle *trans, ULIST_ITER_INIT(&uiter); while (1) { ret = find_parent_nodes(trans, fs_info, bytenr, time_seq, - tmp, *roots, NULL, 0, 0, 0); + tmp, *roots, NULL, 0, 0); if (ret < 0 && ret != -ENOENT) { ulist_free(tmp); ulist_free(*roots); @@ -1621,7 +1280,7 @@ int btrfs_check_shared(struct btrfs_root *root, u64 inum, u64 bytenr) ULIST_ITER_INIT(&uiter); while (1) { ret = find_parent_nodes(trans, fs_info, bytenr, elem.seq, tmp, - roots, NULL, root->objectid, inum, 1); + roots, NULL, root->objectid, inum); if (ret == BACKREF_FOUND_SHARED) { /* this is the only condition under which we return 1 */ ret = 1; -- cgit v1.2.3 From 86d5f994425252d8a40e2184c94a2682ae8ecfbf Mon Sep 17 00:00:00 2001 From: Edmund Nadolski Date: Wed, 12 Jul 2017 16:20:06 -0600 Subject: btrfs: convert prelimary reference tracking to use rbtrees It's been known for a while that the use of multiple lists that are periodically merged was an algorithmic problem within btrfs. There are several workloads that don't complete in any reasonable amount of time (e.g. btrfs/130) and others that cause soft lockups. The solution is to use a set of rbtrees that do insertion merging for both indirect and direct refs, with the former converting refs into the latter. The result is a btrfs/130 workload that used to take several hours now takes about half of that. This runtime still isn't acceptable and a future patch will address that by moving the rbtrees higher in the stack so the lookups can be shared across multiple calls to find_parent_nodes. Signed-off-by: Edmund Nadolski Signed-off-by: Jeff Mahoney Reviewed-by: Liu Bo Signed-off-by: David Sterba --- fs/btrfs/backref.c | 442 ++++++++++++++++++++++++++++++++++------------------- 1 file changed, 285 insertions(+), 157 deletions(-) (limited to 'fs/btrfs/backref.c') diff --git a/fs/btrfs/backref.c b/fs/btrfs/backref.c index 6cac5ab8d5e0..baf907adede1 100644 --- a/fs/btrfs/backref.c +++ b/fs/btrfs/backref.c @@ -26,11 +26,6 @@ #include "delayed-ref.h" #include "locking.h" -enum merge_mode { - MERGE_IDENTICAL_KEYS = 1, - MERGE_IDENTICAL_PARENTS, -}; - /* Just an arbitrary number so we can be sure this happened */ #define BACKREF_FOUND_SHARED 6 @@ -129,7 +124,7 @@ static int find_extent_in_eb(const struct extent_buffer *eb, * this structure records all encountered refs on the way up to the root */ struct prelim_ref { - struct list_head list; + struct rb_node rbnode; u64 root_id; struct btrfs_key key_for_search; int level; @@ -139,6 +134,18 @@ struct prelim_ref { u64 wanted_disk_byte; }; +struct preftree { + struct rb_root root; +}; + +#define PREFTREE_INIT { .root = RB_ROOT } + +struct preftrees { + struct preftree direct; /* BTRFS_SHARED_[DATA|BLOCK]_REF_KEY */ + struct preftree indirect; /* BTRFS_[TREE_BLOCK|EXTENT_DATA]_REF_KEY */ + struct preftree indirect_missing_keys; +}; + static struct kmem_cache *btrfs_prelim_ref_cache; int __init btrfs_prelim_ref_init(void) @@ -158,6 +165,108 @@ void btrfs_prelim_ref_exit(void) kmem_cache_destroy(btrfs_prelim_ref_cache); } +static void free_pref(struct prelim_ref *ref) +{ + kmem_cache_free(btrfs_prelim_ref_cache, ref); +} + +/* + * Return 0 when both refs are for the same block (and can be merged). + * A -1 return indicates ref1 is a 'lower' block than ref2, while 1 + * indicates a 'higher' block. + */ +static int prelim_ref_compare(struct prelim_ref *ref1, + struct prelim_ref *ref2) +{ + if (ref1->level < ref2->level) + return -1; + if (ref1->level > ref2->level) + return 1; + if (ref1->root_id < ref2->root_id) + return -1; + if (ref1->root_id > ref2->root_id) + return 1; + if (ref1->key_for_search.type < ref2->key_for_search.type) + return -1; + if (ref1->key_for_search.type > ref2->key_for_search.type) + return 1; + if (ref1->key_for_search.objectid < ref2->key_for_search.objectid) + return -1; + if (ref1->key_for_search.objectid > ref2->key_for_search.objectid) + return 1; + if (ref1->key_for_search.offset < ref2->key_for_search.offset) + return -1; + if (ref1->key_for_search.offset > ref2->key_for_search.offset) + return 1; + if (ref1->parent < ref2->parent) + return -1; + if (ref1->parent > ref2->parent) + return 1; + + return 0; +} + +/* + * Add @newref to the @root rbtree, merging identical refs. + * + * Callers should assumed that newref has been freed after calling. + */ +static void prelim_ref_insert(struct preftree *preftree, + struct prelim_ref *newref) +{ + struct rb_root *root; + struct rb_node **p; + struct rb_node *parent = NULL; + struct prelim_ref *ref; + int result; + + root = &preftree->root; + p = &root->rb_node; + + while (*p) { + parent = *p; + ref = rb_entry(parent, struct prelim_ref, rbnode); + result = prelim_ref_compare(ref, newref); + if (result < 0) { + p = &(*p)->rb_left; + } else if (result > 0) { + p = &(*p)->rb_right; + } else { + /* Identical refs, merge them and free @newref */ + struct extent_inode_elem *eie = ref->inode_list; + + while (eie && eie->next) + eie = eie->next; + + if (!eie) + ref->inode_list = newref->inode_list; + else + eie->next = newref->inode_list; + ref->count += newref->count; + free_pref(newref); + return; + } + } + + rb_link_node(&newref->rbnode, parent, p); + rb_insert_color(&newref->rbnode, root); +} + +/* + * Release the entire tree. We don't care about internal consistency so + * just free everything and then reset the tree root. + */ +static void prelim_release(struct preftree *preftree) +{ + struct prelim_ref *ref, *next_ref; + + rbtree_postorder_for_each_entry_safe(ref, next_ref, &preftree->root, + rbnode) + free_pref(ref); + + preftree->root = RB_ROOT; +} + /* * the rules for all callers of this function are: * - obtaining the parent is the goal @@ -196,7 +305,7 @@ void btrfs_prelim_ref_exit(void) * additional information that's available but not required to find the parent * block might help in merging entries to gain some speed. */ -static int add_prelim_ref(struct list_head *head, u64 root_id, +static int add_prelim_ref(struct preftree *preftree, u64 root_id, const struct btrfs_key *key, int level, u64 parent, u64 wanted_disk_byte, int count, gfp_t gfp_mask) { @@ -243,11 +352,32 @@ static int add_prelim_ref(struct list_head *head, u64 root_id, ref->count = count; ref->parent = parent; ref->wanted_disk_byte = wanted_disk_byte; - list_add_tail(&ref->list, head); + prelim_ref_insert(preftree, ref); return 0; } +/* direct refs use root == 0, key == NULL */ +static int add_direct_ref(struct preftrees *preftrees, int level, u64 parent, + u64 wanted_disk_byte, int count, gfp_t gfp_mask) +{ + return add_prelim_ref(&preftrees->direct, 0, NULL, level, parent, + wanted_disk_byte, count, gfp_mask); +} + +/* indirect refs use parent == 0 */ +static int add_indirect_ref(struct preftrees *preftrees, u64 root_id, + const struct btrfs_key *key, int level, + u64 wanted_disk_byte, int count, gfp_t gfp_mask) +{ + struct preftree *tree = &preftrees->indirect; + + if (!key) + tree = &preftrees->indirect_missing_keys; + return add_prelim_ref(tree, root_id, key, level, 0, + wanted_disk_byte, count, gfp_mask); +} + static int add_all_parents(struct btrfs_root *root, struct btrfs_path *path, struct ulist *parents, struct prelim_ref *ref, int level, u64 time_seq, const u64 *extent_item_pos, @@ -429,38 +559,63 @@ unode_aux_to_inode_list(struct ulist_node *node) } /* - * resolve all indirect backrefs from the list + * We maintain three seperate rbtrees: one for direct refs, one for + * indirect refs which have a key, and one for indirect refs which do not + * have a key. Each tree does merge on insertion. + * + * Once all of the references are located, we iterate over the tree of + * indirect refs with missing keys. An appropriate key is located and + * the ref is moved onto the tree for indirect refs. After all missing + * keys are thus located, we iterate over the indirect ref tree, resolve + * each reference, and then insert the resolved reference onto the + * direct tree (merging there too). + * + * New backrefs (i.e., for parent nodes) are added to the appropriate + * rbtree as they are encountered. The new backrefs are subsequently + * resolved as above. */ static int resolve_indirect_refs(struct btrfs_fs_info *fs_info, struct btrfs_path *path, u64 time_seq, - struct list_head *head, + struct preftrees *preftrees, const u64 *extent_item_pos, u64 total_refs, u64 root_objectid) { int err; int ret = 0; - struct prelim_ref *ref; - struct prelim_ref *ref_safe; - struct prelim_ref *new_ref; struct ulist *parents; struct ulist_node *node; struct ulist_iterator uiter; + struct rb_node *rnode; parents = ulist_alloc(GFP_NOFS); if (!parents) return -ENOMEM; /* - * _safe allows us to insert directly after the current item without - * iterating over the newly inserted items. - * we're also allowed to re-assign ref during iteration. + * We could trade memory usage for performance here by iterating + * the tree, allocating new refs for each insertion, and then + * freeing the entire indirect tree when we're done. In some test + * cases, the tree can grow quite large (~200k objects). */ - list_for_each_entry_safe(ref, ref_safe, head, list) { - if (ref->parent) /* already direct */ - continue; - if (ref->count == 0) + while ((rnode = rb_first(&preftrees->indirect.root))) { + struct prelim_ref *ref; + + ref = rb_entry(rnode, struct prelim_ref, rbnode); + if (WARN(ref->parent, + "BUG: direct ref found in indirect tree")) { + ret = -EINVAL; + goto out; + } + + rb_erase(&ref->rbnode, &preftrees->indirect.root); + + if (ref->count == 0) { + free_pref(ref); continue; + } + if (root_objectid && ref->root_id != root_objectid) { + free_pref(ref); ret = BACKREF_FOUND_SHARED; goto out; } @@ -472,8 +627,10 @@ static int resolve_indirect_refs(struct btrfs_fs_info *fs_info, * and return directly. */ if (err == -ENOENT) { + prelim_ref_insert(&preftrees->direct, ref); continue; } else if (err) { + free_pref(ref); ret = err; goto out; } @@ -484,19 +641,26 @@ static int resolve_indirect_refs(struct btrfs_fs_info *fs_info, ref->parent = node ? node->val : 0; ref->inode_list = unode_aux_to_inode_list(node); - /* additional parents require new refs being added here */ + /* Add a prelim_ref(s) for any other parent(s). */ while ((node = ulist_next(parents, &uiter))) { + struct prelim_ref *new_ref; + new_ref = kmem_cache_alloc(btrfs_prelim_ref_cache, GFP_NOFS); if (!new_ref) { + free_pref(ref); ret = -ENOMEM; goto out; } memcpy(new_ref, ref, sizeof(*ref)); new_ref->parent = node->val; new_ref->inode_list = unode_aux_to_inode_list(node); - list_add(&new_ref->list, &ref->list); + prelim_ref_insert(&preftrees->direct, new_ref); } + + /* Now it's a direct ref, put it in the the direct tree */ + prelim_ref_insert(&preftrees->direct, ref); + ulist_reinit(parents); } out: @@ -504,44 +668,31 @@ out: return ret; } -static inline int ref_for_same_block(struct prelim_ref *ref1, - struct prelim_ref *ref2) -{ - if (ref1->level != ref2->level) - return 0; - if (ref1->root_id != ref2->root_id) - return 0; - if (ref1->key_for_search.type != ref2->key_for_search.type) - return 0; - if (ref1->key_for_search.objectid != ref2->key_for_search.objectid) - return 0; - if (ref1->key_for_search.offset != ref2->key_for_search.offset) - return 0; - if (ref1->parent != ref2->parent) - return 0; - - return 1; -} - /* * read tree blocks and add keys where required. */ static int add_missing_keys(struct btrfs_fs_info *fs_info, - struct list_head *head) + struct preftrees *preftrees) { struct prelim_ref *ref; struct extent_buffer *eb; + struct preftree *tree = &preftrees->indirect_missing_keys; + struct rb_node *node; - list_for_each_entry(ref, head, list) { - if (ref->parent) - continue; - if (ref->key_for_search.type) - continue; + while ((node = rb_first(&tree->root))) { + ref = rb_entry(node, struct prelim_ref, rbnode); + rb_erase(node, &tree->root); + + BUG_ON(ref->parent); /* should not be a direct ref */ + BUG_ON(ref->key_for_search.type); BUG_ON(!ref->wanted_disk_byte); + eb = read_tree_block(fs_info, ref->wanted_disk_byte, 0); if (IS_ERR(eb)) { + free_pref(ref); return PTR_ERR(eb); } else if (!extent_buffer_uptodate(eb)) { + free_pref(ref); free_extent_buffer(eb); return -EIO; } @@ -552,73 +703,31 @@ static int add_missing_keys(struct btrfs_fs_info *fs_info, btrfs_node_key_to_cpu(eb, &ref->key_for_search, 0); btrfs_tree_read_unlock(eb); free_extent_buffer(eb); + prelim_ref_insert(&preftrees->indirect, ref); } return 0; } -/* - * merge backrefs and adjust counts accordingly - * - * FIXME: For MERGE_IDENTICAL_KEYS, if we add more keys in add_prelim_ref - * then we can merge more here. Additionally, we could even add a key - * range for the blocks we looked into to merge even more (-> replace - * unresolved refs by those having a parent). - */ -static void merge_refs(struct list_head *head, enum merge_mode mode) -{ - struct prelim_ref *pos1; - - list_for_each_entry(pos1, head, list) { - struct prelim_ref *pos2 = pos1, *tmp; - - list_for_each_entry_safe_continue(pos2, tmp, head, list) { - struct prelim_ref *ref1 = pos1, *ref2 = pos2; - struct extent_inode_elem *eie; - - if (!ref_for_same_block(ref1, ref2)) - continue; - if (mode == MERGE_IDENTICAL_KEYS) { - if (!ref1->parent && ref2->parent) - swap(ref1, ref2); - } else { - if (ref1->parent != ref2->parent) - continue; - } - - eie = ref1->inode_list; - while (eie && eie->next) - eie = eie->next; - if (eie) - eie->next = ref2->inode_list; - else - ref1->inode_list = ref2->inode_list; - ref1->count += ref2->count; - - list_del(&ref2->list); - kmem_cache_free(btrfs_prelim_ref_cache, ref2); - cond_resched(); - } - - } -} - /* * add all currently queued delayed refs from this head whose seq nr is * smaller or equal that seq to the list */ static int add_delayed_refs(struct btrfs_delayed_ref_head *head, u64 seq, - struct list_head *prefs, u64 *total_refs, + struct preftrees *preftrees, u64 *total_refs, u64 inum) { struct btrfs_delayed_ref_node *node; struct btrfs_delayed_extent_op *extent_op = head->extent_op; struct btrfs_key key; - struct btrfs_key op_key = {0}; + struct btrfs_key tmp_op_key; + struct btrfs_key *op_key = NULL; int sgn; int ret = 0; - if (extent_op && extent_op->update_key) - btrfs_disk_key_to_cpu(&op_key, &extent_op->key); + if (extent_op && extent_op->update_key) { + btrfs_disk_key_to_cpu(&tmp_op_key, &extent_op->key); + op_key = &tmp_op_key; + } spin_lock(&head->lock); list_for_each_entry(node, &head->ref_list, list) { @@ -642,24 +751,30 @@ static int add_delayed_refs(struct btrfs_delayed_ref_head *head, u64 seq, *total_refs += (node->ref_mod * sgn); switch (node->type) { case BTRFS_TREE_BLOCK_REF_KEY: { + /* NORMAL INDIRECT METADATA backref */ struct btrfs_delayed_tree_ref *ref; ref = btrfs_delayed_node_to_tree_ref(node); - ret = add_prelim_ref(prefs, ref->root, &op_key, - ref->level + 1, 0, node->bytenr, - node->ref_mod * sgn, GFP_ATOMIC); + ret = add_indirect_ref(preftrees, ref->root, &tmp_op_key, + ref->level + 1, node->bytenr, + node->ref_mod * sgn, + GFP_ATOMIC); break; } case BTRFS_SHARED_BLOCK_REF_KEY: { + /* SHARED DIRECT METADATA backref */ struct btrfs_delayed_tree_ref *ref; ref = btrfs_delayed_node_to_tree_ref(node); - ret = add_prelim_ref(prefs, 0, NULL, ref->level + 1, + + ret = add_direct_ref(preftrees, ref->level + 1, ref->parent, node->bytenr, - node->ref_mod * sgn, GFP_ATOMIC); + node->ref_mod * sgn, + GFP_ATOMIC); break; } case BTRFS_EXTENT_DATA_REF_KEY: { + /* NORMAL INDIRECT DATA backref */ struct btrfs_delayed_data_ref *ref; ref = btrfs_delayed_node_to_data_ref(node); @@ -676,17 +791,21 @@ static int add_delayed_refs(struct btrfs_delayed_ref_head *head, u64 seq, break; } - ret = add_prelim_ref(prefs, ref->root, &key, 0, 0, - node->bytenr, node->ref_mod * sgn, - GFP_ATOMIC); + ret = add_indirect_ref(preftrees, ref->root, &key, 0, + node->bytenr, + node->ref_mod * sgn, + GFP_ATOMIC); break; } case BTRFS_SHARED_DATA_REF_KEY: { + /* SHARED DIRECT FULL backref */ struct btrfs_delayed_data_ref *ref; ref = btrfs_delayed_node_to_data_ref(node); - ret = add_prelim_ref(prefs, 0, NULL, 0, ref->parent, - node->bytenr, node->ref_mod * sgn, + + ret = add_direct_ref(preftrees, 0, ref->parent, + node->bytenr, + node->ref_mod * sgn, GFP_ATOMIC); break; } @@ -704,7 +823,7 @@ static int add_delayed_refs(struct btrfs_delayed_ref_head *head, u64 seq, * add all inline backrefs for bytenr to the list */ static int add_inline_refs(struct btrfs_path *path, u64 bytenr, - int *info_level, struct list_head *prefs, + int *info_level, struct preftrees *preftrees, u64 *total_refs, u64 inum) { int ret = 0; @@ -760,8 +879,8 @@ static int add_inline_refs(struct btrfs_path *path, u64 bytenr, switch (type) { case BTRFS_SHARED_BLOCK_REF_KEY: - ret = add_prelim_ref(prefs, 0, NULL, *info_level + 1, - offset, bytenr, 1, GFP_NOFS); + ret = add_direct_ref(preftrees, *info_level + 1, offset, + bytenr, 1, GFP_NOFS); break; case BTRFS_SHARED_DATA_REF_KEY: { struct btrfs_shared_data_ref *sdref; @@ -769,14 +888,15 @@ static int add_inline_refs(struct btrfs_path *path, u64 bytenr, sdref = (struct btrfs_shared_data_ref *)(iref + 1); count = btrfs_shared_data_ref_count(leaf, sdref); - ret = add_prelim_ref(prefs, 0, NULL, 0, offset, + + ret = add_direct_ref(preftrees, 0, offset, bytenr, count, GFP_NOFS); break; } case BTRFS_TREE_BLOCK_REF_KEY: - ret = add_prelim_ref(prefs, offset, NULL, - *info_level + 1, 0, - bytenr, 1, GFP_NOFS); + ret = add_indirect_ref(preftrees, offset, NULL, + *info_level + 1, bytenr, 1, + GFP_NOFS); break; case BTRFS_EXTENT_DATA_REF_KEY: { struct btrfs_extent_data_ref *dref; @@ -796,8 +916,9 @@ static int add_inline_refs(struct btrfs_path *path, u64 bytenr, } root = btrfs_extent_data_ref_root(leaf, dref); - ret = add_prelim_ref(prefs, root, &key, 0, 0, - bytenr, count, GFP_NOFS); + + ret = add_indirect_ref(preftrees, root, &key, 0, bytenr, + count, GFP_NOFS); break; } default: @@ -816,7 +937,8 @@ static int add_inline_refs(struct btrfs_path *path, u64 bytenr, */ static int add_keyed_refs(struct btrfs_fs_info *fs_info, struct btrfs_path *path, u64 bytenr, - int info_level, struct list_head *prefs, u64 inum) + int info_level, struct preftrees *preftrees, + u64 inum) { struct btrfs_root *extent_root = fs_info->extent_root; int ret; @@ -846,26 +968,31 @@ static int add_keyed_refs(struct btrfs_fs_info *fs_info, switch (key.type) { case BTRFS_SHARED_BLOCK_REF_KEY: - ret = add_prelim_ref(prefs, 0, NULL, info_level + 1, - key.offset, bytenr, 1, GFP_NOFS); + /* SHARED DIRECT METADATA backref */ + ret = add_direct_ref(preftrees, info_level + 1, + key.offset, bytenr, 1, + GFP_NOFS); break; case BTRFS_SHARED_DATA_REF_KEY: { + /* SHARED DIRECT FULL backref */ struct btrfs_shared_data_ref *sdref; int count; sdref = btrfs_item_ptr(leaf, slot, struct btrfs_shared_data_ref); count = btrfs_shared_data_ref_count(leaf, sdref); - ret = add_prelim_ref(prefs, 0, NULL, 0, key.offset, - bytenr, count, GFP_NOFS); + ret = add_direct_ref(preftrees, 0, key.offset, bytenr, + count, GFP_NOFS); break; } case BTRFS_TREE_BLOCK_REF_KEY: - ret = add_prelim_ref(prefs, key.offset, NULL, - info_level + 1, 0, - bytenr, 1, GFP_NOFS); + /* NORMAL INDIRECT METADATA backref */ + ret = add_indirect_ref(preftrees, key.offset, NULL, + info_level + 1, bytenr, 1, + GFP_NOFS); break; case BTRFS_EXTENT_DATA_REF_KEY: { + /* NORMAL INDIRECT DATA backref */ struct btrfs_extent_data_ref *dref; int count; u64 root; @@ -884,8 +1011,8 @@ static int add_keyed_refs(struct btrfs_fs_info *fs_info, } root = btrfs_extent_data_ref_root(leaf, dref); - ret = add_prelim_ref(prefs, root, &key, 0, 0, - bytenr, count, GFP_NOFS); + ret = add_indirect_ref(preftrees, root, &key, 0, bytenr, + count, GFP_NOFS); break; } default: @@ -926,14 +1053,16 @@ static int find_parent_nodes(struct btrfs_trans_handle *trans, struct btrfs_delayed_ref_head *head; int info_level = 0; int ret; - struct list_head prefs_delayed; - struct list_head prefs; struct prelim_ref *ref; + struct rb_node *node; struct extent_inode_elem *eie = NULL; + /* total of both direct AND indirect refs! */ u64 total_refs = 0; - - INIT_LIST_HEAD(&prefs); - INIT_LIST_HEAD(&prefs_delayed); + struct preftrees preftrees = { + .direct = PREFTREE_INIT, + .indirect = PREFTREE_INIT, + .indirect_missing_keys = PREFTREE_INIT + }; key.objectid = bytenr; key.offset = (u64)-1; @@ -996,9 +1125,8 @@ again: goto again; } spin_unlock(&delayed_refs->lock); - ret = add_delayed_refs(head, time_seq, - &prefs_delayed, &total_refs, - inum); + ret = add_delayed_refs(head, time_seq, &preftrees, + &total_refs, inum); mutex_unlock(&head->mutex); if (ret) goto out; @@ -1019,35 +1147,43 @@ again: (key.type == BTRFS_EXTENT_ITEM_KEY || key.type == BTRFS_METADATA_ITEM_KEY)) { ret = add_inline_refs(path, bytenr, &info_level, - &prefs, &total_refs, inum); + &preftrees, &total_refs, inum); if (ret) goto out; ret = add_keyed_refs(fs_info, path, bytenr, info_level, - &prefs, inum); + &preftrees, inum); if (ret) goto out; } } - btrfs_release_path(path); - list_splice_init(&prefs_delayed, &prefs); + btrfs_release_path(path); - ret = add_missing_keys(fs_info, &prefs); + ret = add_missing_keys(fs_info, &preftrees); if (ret) goto out; - merge_refs(&prefs, MERGE_IDENTICAL_KEYS); + WARN_ON(!RB_EMPTY_ROOT(&preftrees.indirect_missing_keys.root)); - ret = resolve_indirect_refs(fs_info, path, time_seq, &prefs, + ret = resolve_indirect_refs(fs_info, path, time_seq, &preftrees, extent_item_pos, total_refs, root_objectid); if (ret) goto out; - merge_refs(&prefs, MERGE_IDENTICAL_PARENTS); + WARN_ON(!RB_EMPTY_ROOT(&preftrees.indirect.root)); - while (!list_empty(&prefs)) { - ref = list_first_entry(&prefs, struct prelim_ref, list); + /* + * This walks the tree of merged and resolved refs. Tree blocks are + * read in as needed. Unique entries are added to the ulist, and + * the list of found roots is updated. + * + * We release the entire tree in one go before returning. + */ + node = rb_first(&preftrees.direct.root); + while (node) { + ref = rb_entry(node, struct prelim_ref, rbnode); + node = rb_next(&ref->rbnode); WARN_ON(ref->count < 0); if (roots && ref->count && ref->root_id && ref->parent == 0) { if (root_objectid && ref->root_id != root_objectid) { @@ -1101,23 +1237,15 @@ again: } eie = NULL; } - list_del(&ref->list); - kmem_cache_free(btrfs_prelim_ref_cache, ref); } out: btrfs_free_path(path); - while (!list_empty(&prefs)) { - ref = list_first_entry(&prefs, struct prelim_ref, list); - list_del(&ref->list); - kmem_cache_free(btrfs_prelim_ref_cache, ref); - } - while (!list_empty(&prefs_delayed)) { - ref = list_first_entry(&prefs_delayed, struct prelim_ref, - list); - list_del(&ref->list); - kmem_cache_free(btrfs_prelim_ref_cache, ref); - } + + prelim_release(&preftrees.direct); + prelim_release(&preftrees.indirect); + prelim_release(&preftrees.indirect_missing_keys); + if (ret < 0) free_inode_elem_list(eie); return ret; -- cgit v1.2.3 From 6c336b212bef66e507897c78551b3bb4e613a857 Mon Sep 17 00:00:00 2001 From: Jeff Mahoney Date: Wed, 12 Jul 2017 16:20:07 -0600 Subject: btrfs: add a node counter to each of the rbtrees This patch adds counters to each of the rbtrees so that we can tell how large they are growing for a given workload. These counters will be exported by tracepoints in the next patch. Signed-off-by: Jeff Mahoney Reviewed-by: David Sterba Signed-off-by: David Sterba --- fs/btrfs/backref.c | 6 +++++- 1 file changed, 5 insertions(+), 1 deletion(-) (limited to 'fs/btrfs/backref.c') diff --git a/fs/btrfs/backref.c b/fs/btrfs/backref.c index baf907adede1..297f33850425 100644 --- a/fs/btrfs/backref.c +++ b/fs/btrfs/backref.c @@ -136,9 +136,10 @@ struct prelim_ref { struct preftree { struct rb_root root; + unsigned int count; }; -#define PREFTREE_INIT { .root = RB_ROOT } +#define PREFTREE_INIT { .root = RB_ROOT, .count = 0 } struct preftrees { struct preftree direct; /* BTRFS_SHARED_[DATA|BLOCK]_REF_KEY */ @@ -248,6 +249,7 @@ static void prelim_ref_insert(struct preftree *preftree, } } + preftree->count++; rb_link_node(&newref->rbnode, parent, p); rb_insert_color(&newref->rbnode, root); } @@ -265,6 +267,7 @@ static void prelim_release(struct preftree *preftree) free_pref(ref); preftree->root = RB_ROOT; + preftree->count = 0; } /* @@ -608,6 +611,7 @@ static int resolve_indirect_refs(struct btrfs_fs_info *fs_info, } rb_erase(&ref->rbnode, &preftrees->indirect.root); + preftrees->indirect.count--; if (ref->count == 0) { free_pref(ref); -- cgit v1.2.3 From 00142756e1f8015d2f8ce96532d156689db7e448 Mon Sep 17 00:00:00 2001 From: Jeff Mahoney Date: Wed, 12 Jul 2017 16:20:08 -0600 Subject: btrfs: backref, add tracepoints for prelim_ref insertion and merging This patch adds a tracepoint event for prelim_ref insertion and merging. For each, the ref being inserted or merged and the count of tree nodes is issued. Signed-off-by: Jeff Mahoney Reviewed-by: David Sterba Signed-off-by: David Sterba --- fs/btrfs/backref.c | 118 ++++++++++++++++++++++--------------------- fs/btrfs/backref.h | 12 +++++ fs/btrfs/super.c | 1 + include/trace/events/btrfs.h | 58 +++++++++++++++++++++ 4 files changed, 131 insertions(+), 58 deletions(-) (limited to 'fs/btrfs/backref.c') diff --git a/fs/btrfs/backref.c b/fs/btrfs/backref.c index 297f33850425..4cda81964dd4 100644 --- a/fs/btrfs/backref.c +++ b/fs/btrfs/backref.c @@ -18,6 +18,7 @@ #include #include +#include #include "ctree.h" #include "disk-io.h" #include "backref.h" @@ -120,20 +121,6 @@ static int find_extent_in_eb(const struct extent_buffer *eb, return 0; } -/* - * this structure records all encountered refs on the way up to the root - */ -struct prelim_ref { - struct rb_node rbnode; - u64 root_id; - struct btrfs_key key_for_search; - int level; - int count; - struct extent_inode_elem *inode_list; - u64 parent; - u64 wanted_disk_byte; -}; - struct preftree { struct rb_root root; unsigned int count; @@ -212,7 +199,8 @@ static int prelim_ref_compare(struct prelim_ref *ref1, * * Callers should assumed that newref has been freed after calling. */ -static void prelim_ref_insert(struct preftree *preftree, +static void prelim_ref_insert(const struct btrfs_fs_info *fs_info, + struct preftree *preftree, struct prelim_ref *newref) { struct rb_root *root; @@ -243,6 +231,8 @@ static void prelim_ref_insert(struct preftree *preftree, ref->inode_list = newref->inode_list; else eie->next = newref->inode_list; + trace_btrfs_prelim_ref_merge(fs_info, ref, newref, + preftree->count); ref->count += newref->count; free_pref(newref); return; @@ -250,6 +240,7 @@ static void prelim_ref_insert(struct preftree *preftree, } preftree->count++; + trace_btrfs_prelim_ref_insert(fs_info, newref, NULL, preftree->count); rb_link_node(&newref->rbnode, parent, p); rb_insert_color(&newref->rbnode, root); } @@ -308,7 +299,8 @@ static void prelim_release(struct preftree *preftree) * additional information that's available but not required to find the parent * block might help in merging entries to gain some speed. */ -static int add_prelim_ref(struct preftree *preftree, u64 root_id, +static int add_prelim_ref(const struct btrfs_fs_info *fs_info, + struct preftree *preftree, u64 root_id, const struct btrfs_key *key, int level, u64 parent, u64 wanted_disk_byte, int count, gfp_t gfp_mask) { @@ -355,21 +347,23 @@ static int add_prelim_ref(struct preftree *preftree, u64 root_id, ref->count = count; ref->parent = parent; ref->wanted_disk_byte = wanted_disk_byte; - prelim_ref_insert(preftree, ref); + prelim_ref_insert(fs_info, preftree, ref); return 0; } /* direct refs use root == 0, key == NULL */ -static int add_direct_ref(struct preftrees *preftrees, int level, u64 parent, +static int add_direct_ref(const struct btrfs_fs_info *fs_info, + struct preftrees *preftrees, int level, u64 parent, u64 wanted_disk_byte, int count, gfp_t gfp_mask) { - return add_prelim_ref(&preftrees->direct, 0, NULL, level, parent, - wanted_disk_byte, count, gfp_mask); + return add_prelim_ref(fs_info, &preftrees->direct, 0, NULL, level, + parent, wanted_disk_byte, count, gfp_mask); } /* indirect refs use parent == 0 */ -static int add_indirect_ref(struct preftrees *preftrees, u64 root_id, +static int add_indirect_ref(const struct btrfs_fs_info *fs_info, + struct preftrees *preftrees, u64 root_id, const struct btrfs_key *key, int level, u64 wanted_disk_byte, int count, gfp_t gfp_mask) { @@ -377,7 +371,7 @@ static int add_indirect_ref(struct preftrees *preftrees, u64 root_id, if (!key) tree = &preftrees->indirect_missing_keys; - return add_prelim_ref(tree, root_id, key, level, 0, + return add_prelim_ref(fs_info, tree, root_id, key, level, 0, wanted_disk_byte, count, gfp_mask); } @@ -631,7 +625,7 @@ static int resolve_indirect_refs(struct btrfs_fs_info *fs_info, * and return directly. */ if (err == -ENOENT) { - prelim_ref_insert(&preftrees->direct, ref); + prelim_ref_insert(fs_info, &preftrees->direct, ref); continue; } else if (err) { free_pref(ref); @@ -659,11 +653,11 @@ static int resolve_indirect_refs(struct btrfs_fs_info *fs_info, memcpy(new_ref, ref, sizeof(*ref)); new_ref->parent = node->val; new_ref->inode_list = unode_aux_to_inode_list(node); - prelim_ref_insert(&preftrees->direct, new_ref); + prelim_ref_insert(fs_info, &preftrees->direct, new_ref); } /* Now it's a direct ref, put it in the the direct tree */ - prelim_ref_insert(&preftrees->direct, ref); + prelim_ref_insert(fs_info, &preftrees->direct, ref); ulist_reinit(parents); } @@ -707,7 +701,7 @@ static int add_missing_keys(struct btrfs_fs_info *fs_info, btrfs_node_key_to_cpu(eb, &ref->key_for_search, 0); btrfs_tree_read_unlock(eb); free_extent_buffer(eb); - prelim_ref_insert(&preftrees->indirect, ref); + prelim_ref_insert(fs_info, &preftrees->indirect, ref); } return 0; } @@ -716,7 +710,8 @@ static int add_missing_keys(struct btrfs_fs_info *fs_info, * add all currently queued delayed refs from this head whose seq nr is * smaller or equal that seq to the list */ -static int add_delayed_refs(struct btrfs_delayed_ref_head *head, u64 seq, +static int add_delayed_refs(const struct btrfs_fs_info *fs_info, + struct btrfs_delayed_ref_head *head, u64 seq, struct preftrees *preftrees, u64 *total_refs, u64 inum) { @@ -759,8 +754,9 @@ static int add_delayed_refs(struct btrfs_delayed_ref_head *head, u64 seq, struct btrfs_delayed_tree_ref *ref; ref = btrfs_delayed_node_to_tree_ref(node); - ret = add_indirect_ref(preftrees, ref->root, &tmp_op_key, - ref->level + 1, node->bytenr, + ret = add_indirect_ref(fs_info, preftrees, ref->root, + &tmp_op_key, ref->level + 1, + node->bytenr, node->ref_mod * sgn, GFP_ATOMIC); break; @@ -771,9 +767,9 @@ static int add_delayed_refs(struct btrfs_delayed_ref_head *head, u64 seq, ref = btrfs_delayed_node_to_tree_ref(node); - ret = add_direct_ref(preftrees, ref->level + 1, - ref->parent, node->bytenr, - node->ref_mod * sgn, + ret = add_direct_ref(fs_info, preftrees, + ref->level + 1, ref->parent, + node->bytenr, node->ref_mod * sgn, GFP_ATOMIC); break; } @@ -795,8 +791,8 @@ static int add_delayed_refs(struct btrfs_delayed_ref_head *head, u64 seq, break; } - ret = add_indirect_ref(preftrees, ref->root, &key, 0, - node->bytenr, + ret = add_indirect_ref(fs_info, preftrees, ref->root, + &key, 0, node->bytenr, node->ref_mod * sgn, GFP_ATOMIC); break; @@ -807,8 +803,8 @@ static int add_delayed_refs(struct btrfs_delayed_ref_head *head, u64 seq, ref = btrfs_delayed_node_to_data_ref(node); - ret = add_direct_ref(preftrees, 0, ref->parent, - node->bytenr, + ret = add_direct_ref(fs_info, preftrees, 0, + ref->parent, node->bytenr, node->ref_mod * sgn, GFP_ATOMIC); break; @@ -826,7 +822,8 @@ static int add_delayed_refs(struct btrfs_delayed_ref_head *head, u64 seq, /* * add all inline backrefs for bytenr to the list */ -static int add_inline_refs(struct btrfs_path *path, u64 bytenr, +static int add_inline_refs(const struct btrfs_fs_info *fs_info, + struct btrfs_path *path, u64 bytenr, int *info_level, struct preftrees *preftrees, u64 *total_refs, u64 inum) { @@ -883,7 +880,8 @@ static int add_inline_refs(struct btrfs_path *path, u64 bytenr, switch (type) { case BTRFS_SHARED_BLOCK_REF_KEY: - ret = add_direct_ref(preftrees, *info_level + 1, offset, + ret = add_direct_ref(fs_info, preftrees, + *info_level + 1, offset, bytenr, 1, GFP_NOFS); break; case BTRFS_SHARED_DATA_REF_KEY: { @@ -893,14 +891,14 @@ static int add_inline_refs(struct btrfs_path *path, u64 bytenr, sdref = (struct btrfs_shared_data_ref *)(iref + 1); count = btrfs_shared_data_ref_count(leaf, sdref); - ret = add_direct_ref(preftrees, 0, offset, + ret = add_direct_ref(fs_info, preftrees, 0, offset, bytenr, count, GFP_NOFS); break; } case BTRFS_TREE_BLOCK_REF_KEY: - ret = add_indirect_ref(preftrees, offset, NULL, - *info_level + 1, bytenr, 1, - GFP_NOFS); + ret = add_indirect_ref(fs_info, preftrees, offset, + NULL, *info_level + 1, + bytenr, 1, GFP_NOFS); break; case BTRFS_EXTENT_DATA_REF_KEY: { struct btrfs_extent_data_ref *dref; @@ -921,8 +919,9 @@ static int add_inline_refs(struct btrfs_path *path, u64 bytenr, root = btrfs_extent_data_ref_root(leaf, dref); - ret = add_indirect_ref(preftrees, root, &key, 0, bytenr, - count, GFP_NOFS); + ret = add_indirect_ref(fs_info, preftrees, root, + &key, 0, bytenr, count, + GFP_NOFS); break; } default: @@ -973,9 +972,9 @@ static int add_keyed_refs(struct btrfs_fs_info *fs_info, switch (key.type) { case BTRFS_SHARED_BLOCK_REF_KEY: /* SHARED DIRECT METADATA backref */ - ret = add_direct_ref(preftrees, info_level + 1, - key.offset, bytenr, 1, - GFP_NOFS); + ret = add_direct_ref(fs_info, preftrees, + info_level + 1, key.offset, + bytenr, 1, GFP_NOFS); break; case BTRFS_SHARED_DATA_REF_KEY: { /* SHARED DIRECT FULL backref */ @@ -985,15 +984,16 @@ static int add_keyed_refs(struct btrfs_fs_info *fs_info, sdref = btrfs_item_ptr(leaf, slot, struct btrfs_shared_data_ref); count = btrfs_shared_data_ref_count(leaf, sdref); - ret = add_direct_ref(preftrees, 0, key.offset, bytenr, - count, GFP_NOFS); + ret = add_direct_ref(fs_info, preftrees, 0, + key.offset, bytenr, count, + GFP_NOFS); break; } case BTRFS_TREE_BLOCK_REF_KEY: /* NORMAL INDIRECT METADATA backref */ - ret = add_indirect_ref(preftrees, key.offset, NULL, - info_level + 1, bytenr, 1, - GFP_NOFS); + ret = add_indirect_ref(fs_info, preftrees, key.offset, + NULL, info_level + 1, bytenr, + 1, GFP_NOFS); break; case BTRFS_EXTENT_DATA_REF_KEY: { /* NORMAL INDIRECT DATA backref */ @@ -1015,8 +1015,9 @@ static int add_keyed_refs(struct btrfs_fs_info *fs_info, } root = btrfs_extent_data_ref_root(leaf, dref); - ret = add_indirect_ref(preftrees, root, &key, 0, bytenr, - count, GFP_NOFS); + ret = add_indirect_ref(fs_info, preftrees, root, + &key, 0, bytenr, count, + GFP_NOFS); break; } default: @@ -1129,8 +1130,8 @@ again: goto again; } spin_unlock(&delayed_refs->lock); - ret = add_delayed_refs(head, time_seq, &preftrees, - &total_refs, inum); + ret = add_delayed_refs(fs_info, head, time_seq, + &preftrees, &total_refs, inum); mutex_unlock(&head->mutex); if (ret) goto out; @@ -1150,8 +1151,9 @@ again: if (key.objectid == bytenr && (key.type == BTRFS_EXTENT_ITEM_KEY || key.type == BTRFS_METADATA_ITEM_KEY)) { - ret = add_inline_refs(path, bytenr, &info_level, - &preftrees, &total_refs, inum); + ret = add_inline_refs(fs_info, path, bytenr, + &info_level, &preftrees, + &total_refs, inum); if (ret) goto out; ret = add_keyed_refs(fs_info, path, bytenr, info_level, diff --git a/fs/btrfs/backref.h b/fs/btrfs/backref.h index f9428aaaa77a..e410335841aa 100644 --- a/fs/btrfs/backref.h +++ b/fs/btrfs/backref.h @@ -72,4 +72,16 @@ int btrfs_check_shared(struct btrfs_root *root, u64 inum, u64 bytenr); int __init btrfs_prelim_ref_init(void); void btrfs_prelim_ref_exit(void); + +struct prelim_ref { + struct rb_node rbnode; + u64 root_id; + struct btrfs_key key_for_search; + int level; + int count; + struct extent_inode_elem *inode_list; + u64 parent; + u64 wanted_disk_byte; +}; + #endif diff --git a/fs/btrfs/super.c b/fs/btrfs/super.c index 12540b6104b5..58650f2e0f17 100644 --- a/fs/btrfs/super.c +++ b/fs/btrfs/super.c @@ -61,6 +61,7 @@ #include "tests/btrfs-tests.h" #include "qgroup.h" +#include "backref.h" #define CREATE_TRACE_POINTS #include diff --git a/include/trace/events/btrfs.h b/include/trace/events/btrfs.h index 42560feb9920..90d25085762f 100644 --- a/include/trace/events/btrfs.h +++ b/include/trace/events/btrfs.h @@ -26,6 +26,7 @@ struct btrfs_work; struct __btrfs_workqueue; struct btrfs_qgroup_extent_record; struct btrfs_qgroup; +struct prelim_ref; #define show_ref_type(type) \ __print_symbolic(type, \ @@ -1636,6 +1637,63 @@ TRACE_EVENT(qgroup_meta_reserve, show_root_type(__entry->refroot), __entry->diff) ); +DECLARE_EVENT_CLASS(btrfs__prelim_ref, + TP_PROTO(const struct btrfs_fs_info *fs_info, + const struct prelim_ref *oldref, + const struct prelim_ref *newref, u64 tree_size), + TP_ARGS(fs_info, newref, oldref, tree_size), + + TP_STRUCT__entry_btrfs( + __field( u64, root_id ) + __field( u64, objectid ) + __field( u8, type ) + __field( u64, offset ) + __field( int, level ) + __field( int, old_count ) + __field( u64, parent ) + __field( u64, bytenr ) + __field( int, mod_count ) + __field( u64, tree_size ) + ), + + TP_fast_assign_btrfs(fs_info, + __entry->root_id = oldref->root_id; + __entry->objectid = oldref->key_for_search.objectid; + __entry->type = oldref->key_for_search.type; + __entry->offset = oldref->key_for_search.offset; + __entry->level = oldref->level; + __entry->old_count = oldref->count; + __entry->parent = oldref->parent; + __entry->bytenr = oldref->wanted_disk_byte; + __entry->mod_count = newref ? newref->count : 0; + __entry->tree_size = tree_size; + ), + + TP_printk_btrfs("root_id=%llu key=[%llu,%u,%llu] level=%d count=[%d+%d=%d] parent=%llu wanted_disk_byte=%llu nodes=%llu", + (unsigned long long)__entry->root_id, + (unsigned long long)__entry->objectid, __entry->type, + (unsigned long long)__entry->offset, __entry->level, + __entry->old_count, __entry->mod_count, + __entry->old_count + __entry->mod_count, + (unsigned long long)__entry->parent, + (unsigned long long)__entry->bytenr, + (unsigned long long)__entry->tree_size) +); + +DEFINE_EVENT(btrfs__prelim_ref, btrfs_prelim_ref_merge, + TP_PROTO(const struct btrfs_fs_info *fs_info, + const struct prelim_ref *oldref, + const struct prelim_ref *newref, u64 tree_size), + TP_ARGS(fs_info, oldref, newref, tree_size) +); + +DEFINE_EVENT(btrfs__prelim_ref, btrfs_prelim_ref_insert, + TP_PROTO(const struct btrfs_fs_info *fs_info, + const struct prelim_ref *oldref, + const struct prelim_ref *newref, u64 tree_size), + TP_ARGS(fs_info, oldref, newref, tree_size) +); + #endif /* _TRACE_BTRFS_H */ /* This part must be outside protection */ -- cgit v1.2.3 From 9dd14fd6964e6db02346d5f472f915029728b8cf Mon Sep 17 00:00:00 2001 From: Edmund Nadolski Date: Wed, 12 Jul 2017 16:20:09 -0600 Subject: btrfs: add cond_resched() calls when resolving backrefs Since backref resolution is CPU-intensive, the cond_resched calls should help alleviate soft lockup occurences. Signed-off-by: Edmund Nadolski Signed-off-by: Jeff Mahoney Reviewed-by: David Sterba Signed-off-by: David Sterba --- fs/btrfs/backref.c | 3 +++ 1 file changed, 3 insertions(+) (limited to 'fs/btrfs/backref.c') diff --git a/fs/btrfs/backref.c b/fs/btrfs/backref.c index 4cda81964dd4..9593102bdc2c 100644 --- a/fs/btrfs/backref.c +++ b/fs/btrfs/backref.c @@ -660,6 +660,7 @@ static int resolve_indirect_refs(struct btrfs_fs_info *fs_info, prelim_ref_insert(fs_info, &preftrees->direct, ref); ulist_reinit(parents); + cond_resched(); } out: ulist_free(parents); @@ -702,6 +703,7 @@ static int add_missing_keys(struct btrfs_fs_info *fs_info, btrfs_tree_read_unlock(eb); free_extent_buffer(eb); prelim_ref_insert(fs_info, &preftrees->indirect, ref); + cond_resched(); } return 0; } @@ -1243,6 +1245,7 @@ again: } eie = NULL; } + cond_resched(); } out: -- cgit v1.2.3 From 3ec4d3238ab1655ae3f696c412fb3244cd3b58de Mon Sep 17 00:00:00 2001 From: Edmund Nadolski Date: Wed, 12 Jul 2017 16:20:10 -0600 Subject: btrfs: allow backref search checks for shared extents When called with a struct share_check, find_parent_nodes() will detect a shared extent and immediately return with BACKREF_SHARED_FOUND. Signed-off-by: Edmund Nadolski Signed-off-by: Jeff Mahoney Reviewed-by: Liu Bo Signed-off-by: David Sterba --- fs/btrfs/backref.c | 164 +++++++++++++++++++++++++++++++++++++---------------- 1 file changed, 115 insertions(+), 49 deletions(-) (limited to 'fs/btrfs/backref.c') diff --git a/fs/btrfs/backref.c b/fs/btrfs/backref.c index 9593102bdc2c..2a983a640069 100644 --- a/fs/btrfs/backref.c +++ b/fs/btrfs/backref.c @@ -134,6 +134,25 @@ struct preftrees { struct preftree indirect_missing_keys; }; +/* + * Checks for a shared extent during backref search. + * + * The share_count tracks prelim_refs (direct and indirect) having a + * ref->count >0: + * - incremented when a ref->count transitions to >0 + * - decremented when a ref->count transitions to <1 + */ +struct share_check { + u64 root_objectid; + u64 inum; + int share_count; +}; + +static inline int extent_is_shared(struct share_check *sc) +{ + return (sc && sc->share_count > 1) ? BACKREF_FOUND_SHARED : 0; +} + static struct kmem_cache *btrfs_prelim_ref_cache; int __init btrfs_prelim_ref_init(void) @@ -194,14 +213,26 @@ static int prelim_ref_compare(struct prelim_ref *ref1, return 0; } +void update_share_count(struct share_check *sc, int oldcount, int newcount) +{ + if ((!sc) || (oldcount == 0 && newcount < 1)) + return; + + if (oldcount > 0 && newcount < 1) + sc->share_count--; + else if (oldcount < 1 && newcount > 0) + sc->share_count++; +} + /* * Add @newref to the @root rbtree, merging identical refs. * - * Callers should assumed that newref has been freed after calling. + * Callers should assume that newref has been freed after calling. */ static void prelim_ref_insert(const struct btrfs_fs_info *fs_info, struct preftree *preftree, - struct prelim_ref *newref) + struct prelim_ref *newref, + struct share_check *sc) { struct rb_root *root; struct rb_node **p; @@ -233,12 +264,20 @@ static void prelim_ref_insert(const struct btrfs_fs_info *fs_info, eie->next = newref->inode_list; trace_btrfs_prelim_ref_merge(fs_info, ref, newref, preftree->count); + /* + * A delayed ref can have newref->count < 0. + * The ref->count is updated to follow any + * BTRFS_[ADD|DROP]_DELAYED_REF actions. + */ + update_share_count(sc, ref->count, + ref->count + newref->count); ref->count += newref->count; free_pref(newref); return; } } + update_share_count(sc, 0, newref->count); preftree->count++; trace_btrfs_prelim_ref_insert(fs_info, newref, NULL, preftree->count); rb_link_node(&newref->rbnode, parent, p); @@ -302,7 +341,8 @@ static void prelim_release(struct preftree *preftree) static int add_prelim_ref(const struct btrfs_fs_info *fs_info, struct preftree *preftree, u64 root_id, const struct btrfs_key *key, int level, u64 parent, - u64 wanted_disk_byte, int count, gfp_t gfp_mask) + u64 wanted_disk_byte, int count, + struct share_check *sc, gfp_t gfp_mask) { struct prelim_ref *ref; @@ -347,32 +387,33 @@ static int add_prelim_ref(const struct btrfs_fs_info *fs_info, ref->count = count; ref->parent = parent; ref->wanted_disk_byte = wanted_disk_byte; - prelim_ref_insert(fs_info, preftree, ref); - - return 0; + prelim_ref_insert(fs_info, preftree, ref, sc); + return extent_is_shared(sc); } /* direct refs use root == 0, key == NULL */ static int add_direct_ref(const struct btrfs_fs_info *fs_info, struct preftrees *preftrees, int level, u64 parent, - u64 wanted_disk_byte, int count, gfp_t gfp_mask) + u64 wanted_disk_byte, int count, + struct share_check *sc, gfp_t gfp_mask) { return add_prelim_ref(fs_info, &preftrees->direct, 0, NULL, level, - parent, wanted_disk_byte, count, gfp_mask); + parent, wanted_disk_byte, count, sc, gfp_mask); } /* indirect refs use parent == 0 */ static int add_indirect_ref(const struct btrfs_fs_info *fs_info, struct preftrees *preftrees, u64 root_id, const struct btrfs_key *key, int level, - u64 wanted_disk_byte, int count, gfp_t gfp_mask) + u64 wanted_disk_byte, int count, + struct share_check *sc, gfp_t gfp_mask) { struct preftree *tree = &preftrees->indirect; if (!key) tree = &preftrees->indirect_missing_keys; return add_prelim_ref(fs_info, tree, root_id, key, level, 0, - wanted_disk_byte, count, gfp_mask); + wanted_disk_byte, count, sc, gfp_mask); } static int add_all_parents(struct btrfs_root *root, struct btrfs_path *path, @@ -575,7 +616,7 @@ static int resolve_indirect_refs(struct btrfs_fs_info *fs_info, struct btrfs_path *path, u64 time_seq, struct preftrees *preftrees, const u64 *extent_item_pos, u64 total_refs, - u64 root_objectid) + struct share_check *sc) { int err; int ret = 0; @@ -612,7 +653,8 @@ static int resolve_indirect_refs(struct btrfs_fs_info *fs_info, continue; } - if (root_objectid && ref->root_id != root_objectid) { + if (sc && sc->root_objectid && + ref->root_id != sc->root_objectid) { free_pref(ref); ret = BACKREF_FOUND_SHARED; goto out; @@ -625,7 +667,8 @@ static int resolve_indirect_refs(struct btrfs_fs_info *fs_info, * and return directly. */ if (err == -ENOENT) { - prelim_ref_insert(fs_info, &preftrees->direct, ref); + prelim_ref_insert(fs_info, &preftrees->direct, ref, + NULL); continue; } else if (err) { free_pref(ref); @@ -653,11 +696,15 @@ static int resolve_indirect_refs(struct btrfs_fs_info *fs_info, memcpy(new_ref, ref, sizeof(*ref)); new_ref->parent = node->val; new_ref->inode_list = unode_aux_to_inode_list(node); - prelim_ref_insert(fs_info, &preftrees->direct, new_ref); + prelim_ref_insert(fs_info, &preftrees->direct, + new_ref, NULL); } - /* Now it's a direct ref, put it in the the direct tree */ - prelim_ref_insert(fs_info, &preftrees->direct, ref); + /* + * Now it's a direct ref, put it in the the direct tree. We must + * do this last because the ref could be merged/freed here. + */ + prelim_ref_insert(fs_info, &preftrees->direct, ref, NULL); ulist_reinit(parents); cond_resched(); @@ -702,7 +749,7 @@ static int add_missing_keys(struct btrfs_fs_info *fs_info, btrfs_node_key_to_cpu(eb, &ref->key_for_search, 0); btrfs_tree_read_unlock(eb); free_extent_buffer(eb); - prelim_ref_insert(fs_info, &preftrees->indirect, ref); + prelim_ref_insert(fs_info, &preftrees->indirect, ref, NULL); cond_resched(); } return 0; @@ -715,7 +762,7 @@ static int add_missing_keys(struct btrfs_fs_info *fs_info, static int add_delayed_refs(const struct btrfs_fs_info *fs_info, struct btrfs_delayed_ref_head *head, u64 seq, struct preftrees *preftrees, u64 *total_refs, - u64 inum) + struct share_check *sc) { struct btrfs_delayed_ref_node *node; struct btrfs_delayed_extent_op *extent_op = head->extent_op; @@ -760,7 +807,7 @@ static int add_delayed_refs(const struct btrfs_fs_info *fs_info, &tmp_op_key, ref->level + 1, node->bytenr, node->ref_mod * sgn, - GFP_ATOMIC); + sc, GFP_ATOMIC); break; } case BTRFS_SHARED_BLOCK_REF_KEY: { @@ -772,7 +819,7 @@ static int add_delayed_refs(const struct btrfs_fs_info *fs_info, ret = add_direct_ref(fs_info, preftrees, ref->level + 1, ref->parent, node->bytenr, node->ref_mod * sgn, - GFP_ATOMIC); + sc, GFP_ATOMIC); break; } case BTRFS_EXTENT_DATA_REF_KEY: { @@ -788,15 +835,15 @@ static int add_delayed_refs(const struct btrfs_fs_info *fs_info, * Found a inum that doesn't match our known inum, we * know it's shared. */ - if (inum && ref->objectid != inum) { + if (sc && sc->inum && ref->objectid != sc->inum) { ret = BACKREF_FOUND_SHARED; - break; + goto out; } ret = add_indirect_ref(fs_info, preftrees, ref->root, &key, 0, node->bytenr, node->ref_mod * sgn, - GFP_ATOMIC); + sc, GFP_ATOMIC); break; } case BTRFS_SHARED_DATA_REF_KEY: { @@ -808,26 +855,35 @@ static int add_delayed_refs(const struct btrfs_fs_info *fs_info, ret = add_direct_ref(fs_info, preftrees, 0, ref->parent, node->bytenr, node->ref_mod * sgn, - GFP_ATOMIC); + sc, GFP_ATOMIC); break; } default: WARN_ON(1); } - if (ret) + /* + * We must ignore BACKREF_FOUND_SHARED until all delayed + * refs have been checked. + */ + if (ret && (ret != BACKREF_FOUND_SHARED)) break; } + if (!ret) + ret = extent_is_shared(sc); +out: spin_unlock(&head->lock); return ret; } /* * add all inline backrefs for bytenr to the list + * + * Returns 0 on success, <0 on error, or BACKREF_FOUND_SHARED. */ static int add_inline_refs(const struct btrfs_fs_info *fs_info, struct btrfs_path *path, u64 bytenr, int *info_level, struct preftrees *preftrees, - u64 *total_refs, u64 inum) + u64 *total_refs, struct share_check *sc) { int ret = 0; int slot; @@ -884,7 +940,7 @@ static int add_inline_refs(const struct btrfs_fs_info *fs_info, case BTRFS_SHARED_BLOCK_REF_KEY: ret = add_direct_ref(fs_info, preftrees, *info_level + 1, offset, - bytenr, 1, GFP_NOFS); + bytenr, 1, NULL, GFP_NOFS); break; case BTRFS_SHARED_DATA_REF_KEY: { struct btrfs_shared_data_ref *sdref; @@ -894,13 +950,13 @@ static int add_inline_refs(const struct btrfs_fs_info *fs_info, count = btrfs_shared_data_ref_count(leaf, sdref); ret = add_direct_ref(fs_info, preftrees, 0, offset, - bytenr, count, GFP_NOFS); + bytenr, count, sc, GFP_NOFS); break; } case BTRFS_TREE_BLOCK_REF_KEY: ret = add_indirect_ref(fs_info, preftrees, offset, NULL, *info_level + 1, - bytenr, 1, GFP_NOFS); + bytenr, 1, NULL, GFP_NOFS); break; case BTRFS_EXTENT_DATA_REF_KEY: { struct btrfs_extent_data_ref *dref; @@ -914,7 +970,7 @@ static int add_inline_refs(const struct btrfs_fs_info *fs_info, key.type = BTRFS_EXTENT_DATA_KEY; key.offset = btrfs_extent_data_ref_offset(leaf, dref); - if (inum && key.objectid != inum) { + if (sc && sc->inum && key.objectid != sc->inum) { ret = BACKREF_FOUND_SHARED; break; } @@ -923,7 +979,7 @@ static int add_inline_refs(const struct btrfs_fs_info *fs_info, ret = add_indirect_ref(fs_info, preftrees, root, &key, 0, bytenr, count, - GFP_NOFS); + sc, GFP_NOFS); break; } default: @@ -939,11 +995,13 @@ static int add_inline_refs(const struct btrfs_fs_info *fs_info, /* * add all non-inline backrefs for bytenr to the list + * + * Returns 0 on success, <0 on error, or BACKREF_FOUND_SHARED. */ static int add_keyed_refs(struct btrfs_fs_info *fs_info, struct btrfs_path *path, u64 bytenr, int info_level, struct preftrees *preftrees, - u64 inum) + struct share_check *sc) { struct btrfs_root *extent_root = fs_info->extent_root; int ret; @@ -976,7 +1034,7 @@ static int add_keyed_refs(struct btrfs_fs_info *fs_info, /* SHARED DIRECT METADATA backref */ ret = add_direct_ref(fs_info, preftrees, info_level + 1, key.offset, - bytenr, 1, GFP_NOFS); + bytenr, 1, NULL, GFP_NOFS); break; case BTRFS_SHARED_DATA_REF_KEY: { /* SHARED DIRECT FULL backref */ @@ -988,14 +1046,14 @@ static int add_keyed_refs(struct btrfs_fs_info *fs_info, count = btrfs_shared_data_ref_count(leaf, sdref); ret = add_direct_ref(fs_info, preftrees, 0, key.offset, bytenr, count, - GFP_NOFS); + sc, GFP_NOFS); break; } case BTRFS_TREE_BLOCK_REF_KEY: /* NORMAL INDIRECT METADATA backref */ ret = add_indirect_ref(fs_info, preftrees, key.offset, NULL, info_level + 1, bytenr, - 1, GFP_NOFS); + 1, NULL, GFP_NOFS); break; case BTRFS_EXTENT_DATA_REF_KEY: { /* NORMAL INDIRECT DATA backref */ @@ -1011,7 +1069,7 @@ static int add_keyed_refs(struct btrfs_fs_info *fs_info, key.type = BTRFS_EXTENT_DATA_KEY; key.offset = btrfs_extent_data_ref_offset(leaf, dref); - if (inum && key.objectid != inum) { + if (sc && sc->inum && key.objectid != sc->inum) { ret = BACKREF_FOUND_SHARED; break; } @@ -1019,7 +1077,7 @@ static int add_keyed_refs(struct btrfs_fs_info *fs_info, root = btrfs_extent_data_ref_root(leaf, dref); ret = add_indirect_ref(fs_info, preftrees, root, &key, 0, bytenr, count, - GFP_NOFS); + sc, GFP_NOFS); break; } default: @@ -1039,20 +1097,23 @@ static int add_keyed_refs(struct btrfs_fs_info *fs_info, * indirect refs to their parent bytenr. * When roots are found, they're added to the roots list * - * NOTE: This can return values > 0 - * * If time_seq is set to SEQ_LAST, it will not search delayed_refs, and behave * much like trans == NULL case, the difference only lies in it will not * commit root. * The special case is for qgroup to search roots in commit_transaction(). * + * @sc - if !NULL, then immediately return BACKREF_FOUND_SHARED when a + * shared extent is detected. + * + * Otherwise this returns 0 for success and <0 for an error. + * * FIXME some caching might speed things up */ static int find_parent_nodes(struct btrfs_trans_handle *trans, struct btrfs_fs_info *fs_info, u64 bytenr, u64 time_seq, struct ulist *refs, struct ulist *roots, const u64 *extent_item_pos, - u64 root_objectid, u64 inum) + struct share_check *sc) { struct btrfs_key key; struct btrfs_path *path; @@ -1133,7 +1194,7 @@ again: } spin_unlock(&delayed_refs->lock); ret = add_delayed_refs(fs_info, head, time_seq, - &preftrees, &total_refs, inum); + &preftrees, &total_refs, sc); mutex_unlock(&head->mutex); if (ret) goto out; @@ -1155,11 +1216,11 @@ again: key.type == BTRFS_METADATA_ITEM_KEY)) { ret = add_inline_refs(fs_info, path, bytenr, &info_level, &preftrees, - &total_refs, inum); + &total_refs, sc); if (ret) goto out; ret = add_keyed_refs(fs_info, path, bytenr, info_level, - &preftrees, inum); + &preftrees, sc); if (ret) goto out; } @@ -1174,8 +1235,7 @@ again: WARN_ON(!RB_EMPTY_ROOT(&preftrees.indirect_missing_keys.root)); ret = resolve_indirect_refs(fs_info, path, time_seq, &preftrees, - extent_item_pos, total_refs, - root_objectid); + extent_item_pos, total_refs, sc); if (ret) goto out; @@ -1194,7 +1254,8 @@ again: node = rb_next(&ref->rbnode); WARN_ON(ref->count < 0); if (roots && ref->count && ref->root_id && ref->parent == 0) { - if (root_objectid && ref->root_id != root_objectid) { + if (sc && sc->root_objectid && + ref->root_id != sc->root_objectid) { ret = BACKREF_FOUND_SHARED; goto out; } @@ -1298,7 +1359,7 @@ static int btrfs_find_all_leafs(struct btrfs_trans_handle *trans, return -ENOMEM; ret = find_parent_nodes(trans, fs_info, bytenr, time_seq, - *leafs, NULL, extent_item_pos, 0, 0); + *leafs, NULL, extent_item_pos, NULL); if (ret < 0 && ret != -ENOENT) { free_leaf_list(*leafs); return ret; @@ -1341,7 +1402,7 @@ static int btrfs_find_all_roots_safe(struct btrfs_trans_handle *trans, ULIST_ITER_INIT(&uiter); while (1) { ret = find_parent_nodes(trans, fs_info, bytenr, time_seq, - tmp, *roots, NULL, 0, 0); + tmp, *roots, NULL, NULL); if (ret < 0 && ret != -ENOENT) { ulist_free(tmp); ulist_free(*roots); @@ -1397,6 +1458,11 @@ int btrfs_check_shared(struct btrfs_root *root, u64 inum, u64 bytenr) struct ulist_node *node; struct seq_list elem = SEQ_LIST_INIT(elem); int ret = 0; + struct share_check shared = { + .root_objectid = root->objectid, + .inum = inum, + .share_count = 0, + }; tmp = ulist_alloc(GFP_NOFS); roots = ulist_alloc(GFP_NOFS); @@ -1417,7 +1483,7 @@ int btrfs_check_shared(struct btrfs_root *root, u64 inum, u64 bytenr) ULIST_ITER_INIT(&uiter); while (1) { ret = find_parent_nodes(trans, fs_info, bytenr, elem.seq, tmp, - roots, NULL, root->objectid, inum); + roots, NULL, &shared); if (ret == BACKREF_FOUND_SHARED) { /* this is the only condition under which we return 1 */ ret = 1; -- cgit v1.2.3 From 01747e92a996cc2f2965c28fde485da932836ef8 Mon Sep 17 00:00:00 2001 From: Edmund Nadolski Date: Wed, 12 Jul 2017 16:20:11 -0600 Subject: btrfs: clean up extraneous computations in add_delayed_refs Repeating the same computation in multiple places is not necessary. Signed-off-by: Edmund Nadolski Signed-off-by: Jeff Mahoney Reviewed-by: David Sterba Signed-off-by: David Sterba --- fs/btrfs/backref.c | 30 +++++++++++++----------------- 1 file changed, 13 insertions(+), 17 deletions(-) (limited to 'fs/btrfs/backref.c') diff --git a/fs/btrfs/backref.c b/fs/btrfs/backref.c index 2a983a640069..6bae986bfcfb 100644 --- a/fs/btrfs/backref.c +++ b/fs/btrfs/backref.c @@ -769,7 +769,7 @@ static int add_delayed_refs(const struct btrfs_fs_info *fs_info, struct btrfs_key key; struct btrfs_key tmp_op_key; struct btrfs_key *op_key = NULL; - int sgn; + int count; int ret = 0; if (extent_op && extent_op->update_key) { @@ -788,15 +788,15 @@ static int add_delayed_refs(const struct btrfs_fs_info *fs_info, WARN_ON(1); continue; case BTRFS_ADD_DELAYED_REF: - sgn = 1; + count = node->ref_mod; break; case BTRFS_DROP_DELAYED_REF: - sgn = -1; + count = node->ref_mod * -1; break; default: BUG_ON(1); } - *total_refs += (node->ref_mod * sgn); + *total_refs += count; switch (node->type) { case BTRFS_TREE_BLOCK_REF_KEY: { /* NORMAL INDIRECT METADATA backref */ @@ -805,9 +805,8 @@ static int add_delayed_refs(const struct btrfs_fs_info *fs_info, ref = btrfs_delayed_node_to_tree_ref(node); ret = add_indirect_ref(fs_info, preftrees, ref->root, &tmp_op_key, ref->level + 1, - node->bytenr, - node->ref_mod * sgn, - sc, GFP_ATOMIC); + node->bytenr, count, sc, + GFP_ATOMIC); break; } case BTRFS_SHARED_BLOCK_REF_KEY: { @@ -816,9 +815,8 @@ static int add_delayed_refs(const struct btrfs_fs_info *fs_info, ref = btrfs_delayed_node_to_tree_ref(node); - ret = add_direct_ref(fs_info, preftrees, - ref->level + 1, ref->parent, - node->bytenr, node->ref_mod * sgn, + ret = add_direct_ref(fs_info, preftrees, ref->level + 1, + ref->parent, node->bytenr, count, sc, GFP_ATOMIC); break; } @@ -841,9 +839,8 @@ static int add_delayed_refs(const struct btrfs_fs_info *fs_info, } ret = add_indirect_ref(fs_info, preftrees, ref->root, - &key, 0, node->bytenr, - node->ref_mod * sgn, - sc, GFP_ATOMIC); + &key, 0, node->bytenr, count, sc, + GFP_ATOMIC); break; } case BTRFS_SHARED_DATA_REF_KEY: { @@ -852,10 +849,9 @@ static int add_delayed_refs(const struct btrfs_fs_info *fs_info, ref = btrfs_delayed_node_to_data_ref(node); - ret = add_direct_ref(fs_info, preftrees, 0, - ref->parent, node->bytenr, - node->ref_mod * sgn, - sc, GFP_ATOMIC); + ret = add_direct_ref(fs_info, preftrees, 0, ref->parent, + node->bytenr, count, sc, + GFP_ATOMIC); break; } default: -- cgit v1.2.3 From 3de28d579edbd35294bf44aee8402c804331bc37 Mon Sep 17 00:00:00 2001 From: Liu Bo Date: Fri, 18 Aug 2017 15:15:19 -0600 Subject: Btrfs: convert to use btrfs_get_extent_inline_ref_type Since we have a helper which can do sanity check, this converts all btrfs_extent_inline_ref_type to it. Signed-off-by: Liu Bo Reviewed-by: David Sterba Signed-off-by: David Sterba --- fs/btrfs/backref.c | 11 +++++++++-- fs/btrfs/extent-tree.c | 36 ++++++++++++++++++++++++++++++------ fs/btrfs/relocation.c | 13 +++++++++++-- 3 files changed, 50 insertions(+), 10 deletions(-) (limited to 'fs/btrfs/backref.c') diff --git a/fs/btrfs/backref.c b/fs/btrfs/backref.c index 6bae986bfcfb..b517ef1477ea 100644 --- a/fs/btrfs/backref.c +++ b/fs/btrfs/backref.c @@ -929,7 +929,11 @@ static int add_inline_refs(const struct btrfs_fs_info *fs_info, int type; iref = (struct btrfs_extent_inline_ref *)ptr; - type = btrfs_extent_inline_ref_type(leaf, iref); + type = btrfs_get_extent_inline_ref_type(leaf, iref, + BTRFS_REF_TYPE_ANY); + if (type == BTRFS_REF_TYPE_INVALID) + return -EINVAL; + offset = btrfs_extent_inline_ref_offset(leaf, iref); switch (type) { @@ -1776,7 +1780,10 @@ static int get_extent_inline_ref(unsigned long *ptr, end = (unsigned long)ei + item_size; *out_eiref = (struct btrfs_extent_inline_ref *)(*ptr); - *out_type = btrfs_extent_inline_ref_type(eb, *out_eiref); + *out_type = btrfs_get_extent_inline_ref_type(eb, *out_eiref, + BTRFS_REF_TYPE_ANY); + if (*out_type == BTRFS_REF_TYPE_INVALID) + return -EINVAL; *ptr += btrfs_extent_inline_ref_size(*out_type); WARN_ON(*ptr > end); diff --git a/fs/btrfs/extent-tree.c b/fs/btrfs/extent-tree.c index 794b06dd824a..51a691532fd8 100644 --- a/fs/btrfs/extent-tree.c +++ b/fs/btrfs/extent-tree.c @@ -1454,12 +1454,18 @@ static noinline u32 extent_data_ref_count(struct btrfs_path *path, struct btrfs_extent_data_ref *ref1; struct btrfs_shared_data_ref *ref2; u32 num_refs = 0; + int type; 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) { + /* + * If type is invalid, we should have bailed out earlier than + * this call. + */ + type = btrfs_get_extent_inline_ref_type(leaf, iref, BTRFS_REF_TYPE_DATA); + ASSERT(type != BTRFS_REF_TYPE_INVALID); + if (type == BTRFS_EXTENT_DATA_REF_KEY) { ref1 = (struct btrfs_extent_data_ref *)(&iref->offset); num_refs = btrfs_extent_data_ref_count(leaf, ref1); } else { @@ -1620,6 +1626,7 @@ int lookup_inline_extent_backref(struct btrfs_trans_handle *trans, int ret; int err = 0; bool skinny_metadata = btrfs_fs_incompat(fs_info, SKINNY_METADATA); + int needed; key.objectid = bytenr; key.type = BTRFS_EXTENT_ITEM_KEY; @@ -1711,6 +1718,11 @@ again: BUG_ON(ptr > end); } + if (owner >= BTRFS_FIRST_FREE_OBJECTID) + needed = BTRFS_REF_TYPE_DATA; + else + needed = BTRFS_REF_TYPE_BLOCK; + err = -ENOENT; while (1) { if (ptr >= end) { @@ -1718,7 +1730,12 @@ again: break; } iref = (struct btrfs_extent_inline_ref *)ptr; - type = btrfs_extent_inline_ref_type(leaf, iref); + type = btrfs_get_extent_inline_ref_type(leaf, iref, needed); + if (type == BTRFS_REF_TYPE_INVALID) { + err = -EINVAL; + goto out; + } + if (want < type) break; if (want > type) { @@ -1910,7 +1927,12 @@ void update_inline_extent_backref(struct btrfs_fs_info *fs_info, if (extent_op) __run_delayed_extent_op(extent_op, leaf, ei); - type = btrfs_extent_inline_ref_type(leaf, iref); + /* + * If type is invalid, we should have bailed out after + * lookup_inline_extent_backref(). + */ + type = btrfs_get_extent_inline_ref_type(leaf, iref, BTRFS_REF_TYPE_ANY); + ASSERT(type != BTRFS_REF_TYPE_INVALID); if (type == BTRFS_EXTENT_DATA_REF_KEY) { dref = (struct btrfs_extent_data_ref *)(&iref->offset); @@ -3195,6 +3217,7 @@ static noinline int check_committed_ref(struct btrfs_root *root, struct btrfs_extent_item *ei; struct btrfs_key key; u32 item_size; + int type; int ret; key.objectid = bytenr; @@ -3236,8 +3259,9 @@ static noinline int check_committed_ref(struct btrfs_root *root, goto out; iref = (struct btrfs_extent_inline_ref *)(ei + 1); - if (btrfs_extent_inline_ref_type(leaf, iref) != - BTRFS_EXTENT_DATA_REF_KEY) + + type = btrfs_get_extent_inline_ref_type(leaf, iref, BTRFS_REF_TYPE_DATA); + if (type != BTRFS_EXTENT_DATA_REF_KEY) goto out; ref = (struct btrfs_extent_data_ref *)(&iref->offset); diff --git a/fs/btrfs/relocation.c b/fs/btrfs/relocation.c index 1a532bb72eab..96f816aa9ed3 100644 --- a/fs/btrfs/relocation.c +++ b/fs/btrfs/relocation.c @@ -799,9 +799,17 @@ again: if (ptr < end) { /* update key for inline back ref */ struct btrfs_extent_inline_ref *iref; + int type; iref = (struct btrfs_extent_inline_ref *)ptr; - key.type = btrfs_extent_inline_ref_type(eb, iref); + type = btrfs_get_extent_inline_ref_type(eb, iref, + BTRFS_REF_TYPE_BLOCK); + if (type == BTRFS_REF_TYPE_INVALID) { + err = -EINVAL; + goto out; + } + key.type = type; key.offset = btrfs_extent_inline_ref_offset(eb, iref); + WARN_ON(key.type != BTRFS_TREE_BLOCK_REF_KEY && key.type != BTRFS_SHARED_BLOCK_REF_KEY); } @@ -3753,7 +3761,8 @@ int add_data_references(struct reloc_control *rc, while (ptr < end) { iref = (struct btrfs_extent_inline_ref *)ptr; - key.type = btrfs_extent_inline_ref_type(eb, iref); + key.type = btrfs_get_extent_inline_ref_type(eb, iref, + BTRFS_REF_TYPE_DATA); if (key.type == BTRFS_SHARED_DATA_REF_KEY) { key.offset = btrfs_extent_inline_ref_offset(eb, iref); ret = __add_tree_block(rc, key.offset, blocksize, -- cgit v1.2.3 From d278850eff3053ef166cf64c16f798dfe36278a2 Mon Sep 17 00:00:00 2001 From: Josef Bacik Date: Fri, 29 Sep 2017 15:43:57 -0400 Subject: btrfs: remove delayed_ref_node from ref_head This is just excessive information in the ref_head, and makes the code complicated. It is a relic from when we had the heads and the refs in the same tree, which is no longer the case. With this removal I've cleaned up a bunch of the cruft around this old assumption as well. Signed-off-by: Josef Bacik Reviewed-by: David Sterba Signed-off-by: David Sterba --- fs/btrfs/backref.c | 4 +- fs/btrfs/delayed-ref.c | 126 +++++++++++++++++++------------------------ fs/btrfs/delayed-ref.h | 49 ++++++----------- fs/btrfs/disk-io.c | 12 ++--- fs/btrfs/extent-tree.c | 90 ++++++++++++------------------- include/trace/events/btrfs.h | 13 ++--- 6 files changed, 119 insertions(+), 175 deletions(-) (limited to 'fs/btrfs/backref.c') diff --git a/fs/btrfs/backref.c b/fs/btrfs/backref.c index b517ef1477ea..33cba1abf8b6 100644 --- a/fs/btrfs/backref.c +++ b/fs/btrfs/backref.c @@ -1178,7 +1178,7 @@ again: head = btrfs_find_delayed_ref_head(delayed_refs, bytenr); if (head) { if (!mutex_trylock(&head->mutex)) { - refcount_inc(&head->node.refs); + refcount_inc(&head->refs); spin_unlock(&delayed_refs->lock); btrfs_release_path(path); @@ -1189,7 +1189,7 @@ again: */ mutex_lock(&head->mutex); mutex_unlock(&head->mutex); - btrfs_put_delayed_ref(&head->node); + btrfs_put_delayed_ref_head(head); goto again; } spin_unlock(&delayed_refs->lock); diff --git a/fs/btrfs/delayed-ref.c b/fs/btrfs/delayed-ref.c index 93ffa898df6d..b9b41c838da4 100644 --- a/fs/btrfs/delayed-ref.c +++ b/fs/btrfs/delayed-ref.c @@ -96,15 +96,15 @@ static struct btrfs_delayed_ref_head *htree_insert(struct rb_root *root, u64 bytenr; ins = rb_entry(node, struct btrfs_delayed_ref_head, href_node); - bytenr = ins->node.bytenr; + bytenr = ins->bytenr; while (*p) { parent_node = *p; entry = rb_entry(parent_node, struct btrfs_delayed_ref_head, href_node); - if (bytenr < entry->node.bytenr) + if (bytenr < entry->bytenr) p = &(*p)->rb_left; - else if (bytenr > entry->node.bytenr) + else if (bytenr > entry->bytenr) p = &(*p)->rb_right; else return entry; @@ -133,15 +133,15 @@ find_ref_head(struct rb_root *root, u64 bytenr, while (n) { entry = rb_entry(n, struct btrfs_delayed_ref_head, href_node); - if (bytenr < entry->node.bytenr) + if (bytenr < entry->bytenr) n = n->rb_left; - else if (bytenr > entry->node.bytenr) + else if (bytenr > entry->bytenr) n = n->rb_right; else return entry; } if (entry && return_bigger) { - if (bytenr > entry->node.bytenr) { + if (bytenr > entry->bytenr) { n = rb_next(&entry->href_node); if (!n) n = rb_first(root); @@ -164,17 +164,17 @@ int btrfs_delayed_ref_lock(struct btrfs_trans_handle *trans, if (mutex_trylock(&head->mutex)) return 0; - refcount_inc(&head->node.refs); + refcount_inc(&head->refs); spin_unlock(&delayed_refs->lock); mutex_lock(&head->mutex); spin_lock(&delayed_refs->lock); - if (!head->node.in_tree) { + if (RB_EMPTY_NODE(&head->href_node)) { mutex_unlock(&head->mutex); - btrfs_put_delayed_ref(&head->node); + btrfs_put_delayed_ref_head(head); return -EAGAIN; } - btrfs_put_delayed_ref(&head->node); + btrfs_put_delayed_ref_head(head); return 0; } @@ -183,15 +183,10 @@ static inline void drop_delayed_ref(struct btrfs_trans_handle *trans, struct btrfs_delayed_ref_head *head, struct btrfs_delayed_ref_node *ref) { - if (btrfs_delayed_ref_is_head(ref)) { - head = btrfs_delayed_node_to_head(ref); - rb_erase(&head->href_node, &delayed_refs->href_root); - } else { - assert_spin_locked(&head->lock); - list_del(&ref->list); - if (!list_empty(&ref->add_list)) - list_del(&ref->add_list); - } + assert_spin_locked(&head->lock); + list_del(&ref->list); + if (!list_empty(&ref->add_list)) + list_del(&ref->add_list); ref->in_tree = 0; btrfs_put_delayed_ref(ref); atomic_dec(&delayed_refs->num_entries); @@ -380,8 +375,8 @@ again: head->processing = 1; WARN_ON(delayed_refs->num_heads_ready == 0); delayed_refs->num_heads_ready--; - delayed_refs->run_delayed_start = head->node.bytenr + - head->node.num_bytes; + delayed_refs->run_delayed_start = head->bytenr + + head->num_bytes; return head; } @@ -469,20 +464,16 @@ add_tail: */ static noinline void update_existing_head_ref(struct btrfs_delayed_ref_root *delayed_refs, - struct btrfs_delayed_ref_node *existing, - struct btrfs_delayed_ref_node *update, + struct btrfs_delayed_ref_head *existing, + struct btrfs_delayed_ref_head *update, int *old_ref_mod_ret) { - struct btrfs_delayed_ref_head *existing_ref; - struct btrfs_delayed_ref_head *ref; int old_ref_mod; - existing_ref = btrfs_delayed_node_to_head(existing); - ref = btrfs_delayed_node_to_head(update); - BUG_ON(existing_ref->is_data != ref->is_data); + BUG_ON(existing->is_data != update->is_data); - spin_lock(&existing_ref->lock); - if (ref->must_insert_reserved) { + spin_lock(&existing->lock); + if (update->must_insert_reserved) { /* if the extent was freed and then * reallocated before the delayed ref * entries were processed, we can end up @@ -490,7 +481,7 @@ update_existing_head_ref(struct btrfs_delayed_ref_root *delayed_refs, * the must_insert_reserved flag set. * Set it again here */ - existing_ref->must_insert_reserved = ref->must_insert_reserved; + existing->must_insert_reserved = update->must_insert_reserved; /* * update the num_bytes so we make sure the accounting @@ -500,22 +491,22 @@ update_existing_head_ref(struct btrfs_delayed_ref_root *delayed_refs, } - if (ref->extent_op) { - if (!existing_ref->extent_op) { - existing_ref->extent_op = ref->extent_op; + if (update->extent_op) { + if (!existing->extent_op) { + existing->extent_op = update->extent_op; } else { - if (ref->extent_op->update_key) { - memcpy(&existing_ref->extent_op->key, - &ref->extent_op->key, - sizeof(ref->extent_op->key)); - existing_ref->extent_op->update_key = true; + if (update->extent_op->update_key) { + memcpy(&existing->extent_op->key, + &update->extent_op->key, + sizeof(update->extent_op->key)); + existing->extent_op->update_key = true; } - if (ref->extent_op->update_flags) { - existing_ref->extent_op->flags_to_set |= - ref->extent_op->flags_to_set; - existing_ref->extent_op->update_flags = true; + if (update->extent_op->update_flags) { + existing->extent_op->flags_to_set |= + update->extent_op->flags_to_set; + existing->extent_op->update_flags = true; } - btrfs_free_delayed_extent_op(ref->extent_op); + btrfs_free_delayed_extent_op(update->extent_op); } } /* @@ -523,23 +514,23 @@ update_existing_head_ref(struct btrfs_delayed_ref_root *delayed_refs, * only need the lock for this case cause we could be processing it * currently, for refs we just added we know we're a-ok. */ - old_ref_mod = existing_ref->total_ref_mod; + old_ref_mod = existing->total_ref_mod; if (old_ref_mod_ret) *old_ref_mod_ret = old_ref_mod; existing->ref_mod += update->ref_mod; - existing_ref->total_ref_mod += update->ref_mod; + existing->total_ref_mod += update->ref_mod; /* * If we are going to from a positive ref mod to a negative or vice * versa we need to make sure to adjust pending_csums accordingly. */ - if (existing_ref->is_data) { - if (existing_ref->total_ref_mod >= 0 && old_ref_mod < 0) + if (existing->is_data) { + if (existing->total_ref_mod >= 0 && old_ref_mod < 0) delayed_refs->pending_csums -= existing->num_bytes; - if (existing_ref->total_ref_mod < 0 && old_ref_mod >= 0) + if (existing->total_ref_mod < 0 && old_ref_mod >= 0) delayed_refs->pending_csums += existing->num_bytes; } - spin_unlock(&existing_ref->lock); + spin_unlock(&existing->lock); } /* @@ -550,14 +541,13 @@ update_existing_head_ref(struct btrfs_delayed_ref_root *delayed_refs, static noinline struct btrfs_delayed_ref_head * add_delayed_ref_head(struct btrfs_fs_info *fs_info, struct btrfs_trans_handle *trans, - struct btrfs_delayed_ref_node *ref, + struct btrfs_delayed_ref_head *head_ref, struct btrfs_qgroup_extent_record *qrecord, u64 bytenr, u64 num_bytes, u64 ref_root, u64 reserved, int action, int is_data, int *qrecord_inserted_ret, int *old_ref_mod, int *new_ref_mod) { struct btrfs_delayed_ref_head *existing; - struct btrfs_delayed_ref_head *head_ref = NULL; struct btrfs_delayed_ref_root *delayed_refs; int count_mod = 1; int must_insert_reserved = 0; @@ -593,26 +583,21 @@ add_delayed_ref_head(struct btrfs_fs_info *fs_info, delayed_refs = &trans->transaction->delayed_refs; - /* first set the basic ref node struct up */ - refcount_set(&ref->refs, 1); - ref->bytenr = bytenr; - ref->num_bytes = num_bytes; - ref->ref_mod = count_mod; - ref->type = 0; - ref->action = 0; - ref->is_head = 1; - ref->in_tree = 1; - ref->seq = 0; - - head_ref = btrfs_delayed_node_to_head(ref); + refcount_set(&head_ref->refs, 1); + head_ref->bytenr = bytenr; + head_ref->num_bytes = num_bytes; + head_ref->ref_mod = count_mod; head_ref->must_insert_reserved = must_insert_reserved; head_ref->is_data = is_data; INIT_LIST_HEAD(&head_ref->ref_list); INIT_LIST_HEAD(&head_ref->ref_add_list); + RB_CLEAR_NODE(&head_ref->href_node); head_ref->processing = 0; head_ref->total_ref_mod = count_mod; head_ref->qgroup_reserved = 0; head_ref->qgroup_ref_root = 0; + spin_lock_init(&head_ref->lock); + mutex_init(&head_ref->mutex); /* Record qgroup extent info if provided */ if (qrecord) { @@ -632,17 +617,14 @@ add_delayed_ref_head(struct btrfs_fs_info *fs_info, qrecord_inserted = 1; } - spin_lock_init(&head_ref->lock); - mutex_init(&head_ref->mutex); - - trace_add_delayed_ref_head(fs_info, ref, head_ref, action); + trace_add_delayed_ref_head(fs_info, head_ref, action); existing = htree_insert(&delayed_refs->href_root, &head_ref->href_node); if (existing) { WARN_ON(ref_root && reserved && existing->qgroup_ref_root && existing->qgroup_reserved); - update_existing_head_ref(delayed_refs, &existing->node, ref, + update_existing_head_ref(delayed_refs, existing, head_ref, old_ref_mod); /* * we've updated the existing ref, free the newly @@ -821,7 +803,7 @@ int btrfs_add_delayed_tree_ref(struct btrfs_fs_info *fs_info, * insert both the head node and the new ref without dropping * the spin lock */ - head_ref = add_delayed_ref_head(fs_info, trans, &head_ref->node, record, + head_ref = add_delayed_ref_head(fs_info, trans, head_ref, record, bytenr, num_bytes, 0, 0, action, 0, &qrecord_inserted, old_ref_mod, new_ref_mod); @@ -888,7 +870,7 @@ int btrfs_add_delayed_data_ref(struct btrfs_fs_info *fs_info, * insert both the head node and the new ref without dropping * the spin lock */ - head_ref = add_delayed_ref_head(fs_info, trans, &head_ref->node, record, + head_ref = add_delayed_ref_head(fs_info, trans, head_ref, record, bytenr, num_bytes, ref_root, reserved, action, 1, &qrecord_inserted, old_ref_mod, new_ref_mod); @@ -920,7 +902,7 @@ int btrfs_add_delayed_extent_op(struct btrfs_fs_info *fs_info, delayed_refs = &trans->transaction->delayed_refs; spin_lock(&delayed_refs->lock); - add_delayed_ref_head(fs_info, trans, &head_ref->node, NULL, bytenr, + add_delayed_ref_head(fs_info, trans, head_ref, NULL, bytenr, num_bytes, 0, 0, BTRFS_UPDATE_DELAYED_HEAD, extent_op->is_data, NULL, NULL, NULL); diff --git a/fs/btrfs/delayed-ref.h b/fs/btrfs/delayed-ref.h index ce88e4ac5276..1ce11858d727 100644 --- a/fs/btrfs/delayed-ref.h +++ b/fs/btrfs/delayed-ref.h @@ -26,15 +26,6 @@ #define BTRFS_ADD_DELAYED_EXTENT 3 /* record a full extent allocation */ #define BTRFS_UPDATE_DELAYED_HEAD 4 /* not changing ref count on head ref */ -/* - * XXX: Qu: I really hate the design that ref_head and tree/data ref shares the - * same ref_node structure. - * Ref_head is in a higher logic level than tree/data ref, and duplicated - * bytenr/num_bytes in ref_node is really a waste or memory, they should be - * referred from ref_head. - * This gets more disgusting after we use list to store tree/data ref in - * ref_head. Must clean this mess up later. - */ struct btrfs_delayed_ref_node { /*data/tree ref use list, stored in ref_head->ref_list. */ struct list_head list; @@ -91,8 +82,9 @@ struct btrfs_delayed_extent_op { * reference count modifications we've queued up. */ struct btrfs_delayed_ref_head { - struct btrfs_delayed_ref_node node; - + u64 bytenr; + u64 num_bytes; + refcount_t refs; /* * the mutex is held while running the refs, and it is also * held when checking the sum of reference modifications. @@ -115,6 +107,14 @@ struct btrfs_delayed_ref_head { */ int total_ref_mod; + /* + * This is the current outstanding mod references for this bytenr. This + * is used with lookup_extent_info to get an accurate reference count + * for a bytenr, so it is adjusted as delayed refs are run so that any + * on disk reference count + ref_mod is accurate. + */ + int ref_mod; + /* * For qgroup reserved space freeing. * @@ -234,15 +234,18 @@ static inline void btrfs_put_delayed_ref(struct btrfs_delayed_ref_node *ref) case BTRFS_SHARED_DATA_REF_KEY: kmem_cache_free(btrfs_delayed_data_ref_cachep, ref); break; - case 0: - kmem_cache_free(btrfs_delayed_ref_head_cachep, ref); - break; default: BUG(); } } } +static inline void btrfs_put_delayed_ref_head(struct btrfs_delayed_ref_head *head) +{ + if (refcount_dec_and_test(&head->refs)) + kmem_cache_free(btrfs_delayed_ref_head_cachep, head); +} + int btrfs_add_delayed_tree_ref(struct btrfs_fs_info *fs_info, struct btrfs_trans_handle *trans, u64 bytenr, u64 num_bytes, u64 parent, @@ -282,36 +285,18 @@ int btrfs_check_delayed_seq(struct btrfs_fs_info *fs_info, struct btrfs_delayed_ref_root *delayed_refs, u64 seq); -/* - * a node might live in a head or a regular ref, this lets you - * test for the proper type to use. - */ -static int btrfs_delayed_ref_is_head(struct btrfs_delayed_ref_node *node) -{ - return node->is_head; -} - /* * helper functions to cast a node into its container */ static inline struct btrfs_delayed_tree_ref * btrfs_delayed_node_to_tree_ref(struct btrfs_delayed_ref_node *node) { - WARN_ON(btrfs_delayed_ref_is_head(node)); return container_of(node, struct btrfs_delayed_tree_ref, node); } static inline struct btrfs_delayed_data_ref * btrfs_delayed_node_to_data_ref(struct btrfs_delayed_ref_node *node) { - WARN_ON(btrfs_delayed_ref_is_head(node)); return container_of(node, struct btrfs_delayed_data_ref, node); } - -static inline struct btrfs_delayed_ref_head * -btrfs_delayed_node_to_head(struct btrfs_delayed_ref_node *node) -{ - WARN_ON(!btrfs_delayed_ref_is_head(node)); - return container_of(node, struct btrfs_delayed_ref_head, node); -} #endif diff --git a/fs/btrfs/disk-io.c b/fs/btrfs/disk-io.c index f971d5680e6f..69ce738c00d0 100644 --- a/fs/btrfs/disk-io.c +++ b/fs/btrfs/disk-io.c @@ -4121,12 +4121,12 @@ static int btrfs_destroy_delayed_refs(struct btrfs_transaction *trans, head = rb_entry(node, struct btrfs_delayed_ref_head, href_node); if (!mutex_trylock(&head->mutex)) { - refcount_inc(&head->node.refs); + refcount_inc(&head->refs); spin_unlock(&delayed_refs->lock); mutex_lock(&head->mutex); mutex_unlock(&head->mutex); - btrfs_put_delayed_ref(&head->node); + btrfs_put_delayed_ref_head(head); spin_lock(&delayed_refs->lock); continue; } @@ -4147,16 +4147,16 @@ static int btrfs_destroy_delayed_refs(struct btrfs_transaction *trans, if (head->processing == 0) delayed_refs->num_heads_ready--; atomic_dec(&delayed_refs->num_entries); - head->node.in_tree = 0; rb_erase(&head->href_node, &delayed_refs->href_root); + RB_CLEAR_NODE(&head->href_node); spin_unlock(&head->lock); spin_unlock(&delayed_refs->lock); mutex_unlock(&head->mutex); if (pin_bytes) - btrfs_pin_extent(fs_info, head->node.bytenr, - head->node.num_bytes, 1); - btrfs_put_delayed_ref(&head->node); + btrfs_pin_extent(fs_info, head->bytenr, + head->num_bytes, 1); + btrfs_put_delayed_ref_head(head); cond_resched(); spin_lock(&delayed_refs->lock); } diff --git a/fs/btrfs/extent-tree.c b/fs/btrfs/extent-tree.c index 628ae71094f2..423d89145bac 100644 --- a/fs/btrfs/extent-tree.c +++ b/fs/btrfs/extent-tree.c @@ -912,7 +912,7 @@ search_again: head = btrfs_find_delayed_ref_head(delayed_refs, bytenr); if (head) { if (!mutex_trylock(&head->mutex)) { - refcount_inc(&head->node.refs); + refcount_inc(&head->refs); spin_unlock(&delayed_refs->lock); btrfs_release_path(path); @@ -923,7 +923,7 @@ search_again: */ mutex_lock(&head->mutex); mutex_unlock(&head->mutex); - btrfs_put_delayed_ref(&head->node); + btrfs_put_delayed_ref_head(head); goto search_again; } spin_lock(&head->lock); @@ -932,7 +932,7 @@ search_again: else BUG_ON(num_refs == 0); - num_refs += head->node.ref_mod; + num_refs += head->ref_mod; spin_unlock(&head->lock); mutex_unlock(&head->mutex); } @@ -2337,7 +2337,7 @@ static void __run_delayed_extent_op(struct btrfs_delayed_extent_op *extent_op, static int run_delayed_extent_op(struct btrfs_trans_handle *trans, struct btrfs_fs_info *fs_info, - struct btrfs_delayed_ref_node *node, + struct btrfs_delayed_ref_head *head, struct btrfs_delayed_extent_op *extent_op) { struct btrfs_key key; @@ -2359,14 +2359,14 @@ static int run_delayed_extent_op(struct btrfs_trans_handle *trans, if (!path) return -ENOMEM; - key.objectid = node->bytenr; + key.objectid = head->bytenr; if (metadata) { key.type = BTRFS_METADATA_ITEM_KEY; key.offset = extent_op->level; } else { key.type = BTRFS_EXTENT_ITEM_KEY; - key.offset = node->num_bytes; + key.offset = head->num_bytes; } again: @@ -2383,17 +2383,17 @@ again: path->slots[0]--; btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]); - if (key.objectid == node->bytenr && + if (key.objectid == head->bytenr && key.type == BTRFS_EXTENT_ITEM_KEY && - key.offset == node->num_bytes) + key.offset == head->num_bytes) ret = 0; } if (ret > 0) { btrfs_release_path(path); metadata = 0; - key.objectid = node->bytenr; - key.offset = node->num_bytes; + key.objectid = head->bytenr; + key.offset = head->num_bytes; key.type = BTRFS_EXTENT_ITEM_KEY; goto again; } @@ -2562,7 +2562,7 @@ static int cleanup_extent_op(struct btrfs_trans_handle *trans, return 0; } spin_unlock(&head->lock); - ret = run_delayed_extent_op(trans, fs_info, &head->node, extent_op); + ret = run_delayed_extent_op(trans, fs_info, head, extent_op); btrfs_free_delayed_extent_op(extent_op); return ret ? ret : 1; } @@ -2597,39 +2597,37 @@ static int cleanup_ref_head(struct btrfs_trans_handle *trans, spin_unlock(&delayed_refs->lock); return 1; } - head->node.in_tree = 0; delayed_refs->num_heads--; rb_erase(&head->href_node, &delayed_refs->href_root); + RB_CLEAR_NODE(&head->href_node); spin_unlock(&delayed_refs->lock); spin_unlock(&head->lock); atomic_dec(&delayed_refs->num_entries); - trace_run_delayed_ref_head(fs_info, &head->node, head, - head->node.action); + trace_run_delayed_ref_head(fs_info, head, 0); if (head->total_ref_mod < 0) { struct btrfs_block_group_cache *cache; - cache = btrfs_lookup_block_group(fs_info, head->node.bytenr); + cache = btrfs_lookup_block_group(fs_info, head->bytenr); ASSERT(cache); percpu_counter_add(&cache->space_info->total_bytes_pinned, - -head->node.num_bytes); + -head->num_bytes); btrfs_put_block_group(cache); if (head->is_data) { spin_lock(&delayed_refs->lock); - delayed_refs->pending_csums -= head->node.num_bytes; + delayed_refs->pending_csums -= head->num_bytes; spin_unlock(&delayed_refs->lock); } } if (head->must_insert_reserved) { - btrfs_pin_extent(fs_info, head->node.bytenr, - head->node.num_bytes, 1); + btrfs_pin_extent(fs_info, head->bytenr, + head->num_bytes, 1); if (head->is_data) { - ret = btrfs_del_csums(trans, fs_info, - head->node.bytenr, - head->node.num_bytes); + ret = btrfs_del_csums(trans, fs_info, head->bytenr, + head->num_bytes); } } @@ -2637,7 +2635,7 @@ static int cleanup_ref_head(struct btrfs_trans_handle *trans, btrfs_qgroup_free_delayed_ref(fs_info, head->qgroup_ref_root, head->qgroup_reserved); btrfs_delayed_ref_unlock(head); - btrfs_put_delayed_ref(&head->node); + btrfs_put_delayed_ref_head(head); return 0; } @@ -2751,10 +2749,10 @@ static noinline int __btrfs_run_delayed_refs(struct btrfs_trans_handle *trans, switch (ref->action) { case BTRFS_ADD_DELAYED_REF: case BTRFS_ADD_DELAYED_EXTENT: - locked_ref->node.ref_mod -= ref->ref_mod; + locked_ref->ref_mod -= ref->ref_mod; break; case BTRFS_DROP_DELAYED_REF: - locked_ref->node.ref_mod += ref->ref_mod; + locked_ref->ref_mod += ref->ref_mod; break; default: WARN_ON(1); @@ -3087,33 +3085,16 @@ again: spin_unlock(&delayed_refs->lock); goto out; } + head = rb_entry(node, struct btrfs_delayed_ref_head, + href_node); + refcount_inc(&head->refs); + spin_unlock(&delayed_refs->lock); - while (node) { - head = rb_entry(node, struct btrfs_delayed_ref_head, - href_node); - if (btrfs_delayed_ref_is_head(&head->node)) { - struct btrfs_delayed_ref_node *ref; - - ref = &head->node; - refcount_inc(&ref->refs); - - spin_unlock(&delayed_refs->lock); - /* - * Mutex was contended, block until it's - * released and try again - */ - mutex_lock(&head->mutex); - mutex_unlock(&head->mutex); + /* Mutex was contended, block until it's released and retry. */ + mutex_lock(&head->mutex); + mutex_unlock(&head->mutex); - btrfs_put_delayed_ref(ref); - cond_resched(); - goto again; - } else { - WARN_ON(1); - } - node = rb_next(node); - } - spin_unlock(&delayed_refs->lock); + btrfs_put_delayed_ref_head(head); cond_resched(); goto again; } @@ -3171,7 +3152,7 @@ static noinline int check_delayed_ref(struct btrfs_root *root, } if (!mutex_trylock(&head->mutex)) { - refcount_inc(&head->node.refs); + refcount_inc(&head->refs); spin_unlock(&delayed_refs->lock); btrfs_release_path(path); @@ -3182,7 +3163,7 @@ static noinline int check_delayed_ref(struct btrfs_root *root, */ mutex_lock(&head->mutex); mutex_unlock(&head->mutex); - btrfs_put_delayed_ref(&head->node); + btrfs_put_delayed_ref_head(head); return -EAGAIN; } spin_unlock(&delayed_refs->lock); @@ -7235,9 +7216,8 @@ static noinline int check_ref_cleanup(struct btrfs_trans_handle *trans, * at this point we have a head with no other entries. Go * ahead and process it. */ - head->node.in_tree = 0; rb_erase(&head->href_node, &delayed_refs->href_root); - + RB_CLEAR_NODE(&head->href_node); atomic_dec(&delayed_refs->num_entries); /* @@ -7256,7 +7236,7 @@ static noinline int check_ref_cleanup(struct btrfs_trans_handle *trans, ret = 1; mutex_unlock(&head->mutex); - btrfs_put_delayed_ref(&head->node); + btrfs_put_delayed_ref_head(head); return ret; out: spin_unlock(&head->lock); diff --git a/include/trace/events/btrfs.h b/include/trace/events/btrfs.h index 77437f545c63..bfe2f23b578c 100644 --- a/include/trace/events/btrfs.h +++ b/include/trace/events/btrfs.h @@ -798,11 +798,10 @@ DEFINE_EVENT(btrfs_delayed_data_ref, run_delayed_data_ref, DECLARE_EVENT_CLASS(btrfs_delayed_ref_head, TP_PROTO(const struct btrfs_fs_info *fs_info, - const struct btrfs_delayed_ref_node *ref, const struct btrfs_delayed_ref_head *head_ref, int action), - TP_ARGS(fs_info, ref, head_ref, action), + TP_ARGS(fs_info, head_ref, action), TP_STRUCT__entry_btrfs( __field( u64, bytenr ) @@ -812,8 +811,8 @@ DECLARE_EVENT_CLASS(btrfs_delayed_ref_head, ), TP_fast_assign_btrfs(fs_info, - __entry->bytenr = ref->bytenr; - __entry->num_bytes = ref->num_bytes; + __entry->bytenr = head_ref->bytenr; + __entry->num_bytes = head_ref->num_bytes; __entry->action = action; __entry->is_data = head_ref->is_data; ), @@ -828,21 +827,19 @@ DECLARE_EVENT_CLASS(btrfs_delayed_ref_head, DEFINE_EVENT(btrfs_delayed_ref_head, add_delayed_ref_head, TP_PROTO(const struct btrfs_fs_info *fs_info, - const struct btrfs_delayed_ref_node *ref, const struct btrfs_delayed_ref_head *head_ref, int action), - TP_ARGS(fs_info, ref, head_ref, action) + TP_ARGS(fs_info, head_ref, action) ); DEFINE_EVENT(btrfs_delayed_ref_head, run_delayed_ref_head, TP_PROTO(const struct btrfs_fs_info *fs_info, - const struct btrfs_delayed_ref_node *ref, const struct btrfs_delayed_ref_head *head_ref, int action), - TP_ARGS(fs_info, ref, head_ref, action) + TP_ARGS(fs_info, head_ref, action) ); #define show_chunk_type(type) \ -- cgit v1.2.3 From c995ab3cda3f4178c1f1a47926bea5f8372880cb Mon Sep 17 00:00:00 2001 From: Zygo Blaxell Date: Fri, 22 Sep 2017 13:58:45 -0400 Subject: btrfs: add a flag to iterate_inodes_from_logical to find all extent refs for uncompressed extents The LOGICAL_INO ioctl provides a backward mapping from extent bytenr and offset (encoded as a single logical address) to a list of extent refs. LOGICAL_INO complements TREE_SEARCH, which provides the forward mapping (extent ref -> extent bytenr and offset, or logical address). These are useful capabilities for programs that manipulate extents and extent references from userspace (e.g. dedup and defrag utilities). When the extents are uncompressed (and not encrypted and not other), check_extent_in_eb performs filtering of the extent refs to remove any extent refs which do not contain the same extent offset as the 'logical' parameter's extent offset. This prevents LOGICAL_INO from returning references to more than a single block. To find the set of extent references to an uncompressed extent from [a, b), userspace has to run a loop like this pseudocode: for (i = a; i < b; ++i) extent_ref_set += LOGICAL_INO(i); At each iteration of the loop (up to 32768 iterations for a 128M extent), data we are interested in is collected in the kernel, then deleted by the filter in check_extent_in_eb. When the extents are compressed (or encrypted or other), the 'logical' parameter must be an extent bytenr (the 'a' parameter in the loop). No filtering by extent offset is done (or possible?) so the result is the complete set of extent refs for the entire extent. This removes the need for the loop, since we get all the extent refs in one call. Add an 'ignore_offset' argument to iterate_inodes_from_logical, [...several levels of function call graph...], and check_extent_in_eb, so that we can disable the extent offset filtering for uncompressed extents. This flag can be set by an improved version of the LOGICAL_INO ioctl to get either behavior as desired. There is no functional change in this patch. The new flag is always false. Signed-off-by: Zygo Blaxell Reviewed-by: David Sterba [ minor coding style fixes ] Signed-off-by: David Sterba --- fs/btrfs/backref.c | 63 ++++++++++++++++++++++++++----------------- fs/btrfs/backref.h | 8 +++--- fs/btrfs/inode.c | 2 +- fs/btrfs/ioctl.c | 2 +- fs/btrfs/qgroup.c | 8 +++--- fs/btrfs/scrub.c | 6 ++--- fs/btrfs/send.c | 2 +- fs/btrfs/tests/qgroup-tests.c | 30 ++++++++++++++------- 8 files changed, 73 insertions(+), 48 deletions(-) (limited to 'fs/btrfs/backref.c') diff --git a/fs/btrfs/backref.c b/fs/btrfs/backref.c index 33cba1abf8b6..523d2dba7745 100644 --- a/fs/btrfs/backref.c +++ b/fs/btrfs/backref.c @@ -40,12 +40,14 @@ static int check_extent_in_eb(const struct btrfs_key *key, const struct extent_buffer *eb, const struct btrfs_file_extent_item *fi, u64 extent_item_pos, - struct extent_inode_elem **eie) + struct extent_inode_elem **eie, + bool ignore_offset) { u64 offset = 0; struct extent_inode_elem *e; - if (!btrfs_file_extent_compression(eb, fi) && + if (!ignore_offset && + !btrfs_file_extent_compression(eb, fi) && !btrfs_file_extent_encryption(eb, fi) && !btrfs_file_extent_other_encoding(eb, fi)) { u64 data_offset; @@ -84,7 +86,8 @@ static void free_inode_elem_list(struct extent_inode_elem *eie) static int find_extent_in_eb(const struct extent_buffer *eb, u64 wanted_disk_byte, u64 extent_item_pos, - struct extent_inode_elem **eie) + struct extent_inode_elem **eie, + bool ignore_offset) { u64 disk_byte; struct btrfs_key key; @@ -113,7 +116,7 @@ static int find_extent_in_eb(const struct extent_buffer *eb, if (disk_byte != wanted_disk_byte) continue; - ret = check_extent_in_eb(&key, eb, fi, extent_item_pos, eie); + ret = check_extent_in_eb(&key, eb, fi, extent_item_pos, eie, ignore_offset); if (ret < 0) return ret; } @@ -419,7 +422,7 @@ static int add_indirect_ref(const struct btrfs_fs_info *fs_info, static int add_all_parents(struct btrfs_root *root, struct btrfs_path *path, struct ulist *parents, struct prelim_ref *ref, int level, u64 time_seq, const u64 *extent_item_pos, - u64 total_refs) + u64 total_refs, bool ignore_offset) { int ret = 0; int slot; @@ -472,7 +475,7 @@ static int add_all_parents(struct btrfs_root *root, struct btrfs_path *path, if (extent_item_pos) { ret = check_extent_in_eb(&key, eb, fi, *extent_item_pos, - &eie); + &eie, ignore_offset); if (ret < 0) break; } @@ -510,7 +513,8 @@ next: static int resolve_indirect_ref(struct btrfs_fs_info *fs_info, struct btrfs_path *path, u64 time_seq, struct prelim_ref *ref, struct ulist *parents, - const u64 *extent_item_pos, u64 total_refs) + const u64 *extent_item_pos, u64 total_refs, + bool ignore_offset) { struct btrfs_root *root; struct btrfs_key root_key; @@ -581,7 +585,7 @@ static int resolve_indirect_ref(struct btrfs_fs_info *fs_info, } ret = add_all_parents(root, path, parents, ref, level, time_seq, - extent_item_pos, total_refs); + extent_item_pos, total_refs, ignore_offset); out: path->lowest_level = 0; btrfs_release_path(path); @@ -616,7 +620,7 @@ static int resolve_indirect_refs(struct btrfs_fs_info *fs_info, struct btrfs_path *path, u64 time_seq, struct preftrees *preftrees, const u64 *extent_item_pos, u64 total_refs, - struct share_check *sc) + struct share_check *sc, bool ignore_offset) { int err; int ret = 0; @@ -661,7 +665,7 @@ static int resolve_indirect_refs(struct btrfs_fs_info *fs_info, } err = resolve_indirect_ref(fs_info, path, time_seq, ref, parents, extent_item_pos, - total_refs); + total_refs, ignore_offset); /* * we can only tolerate ENOENT,otherwise,we should catch error * and return directly. @@ -1107,13 +1111,17 @@ static int add_keyed_refs(struct btrfs_fs_info *fs_info, * * Otherwise this returns 0 for success and <0 for an error. * + * If ignore_offset is set to false, only extent refs whose offsets match + * extent_item_pos are returned. If true, every extent ref is returned + * and extent_item_pos is ignored. + * * FIXME some caching might speed things up */ static int find_parent_nodes(struct btrfs_trans_handle *trans, struct btrfs_fs_info *fs_info, u64 bytenr, u64 time_seq, struct ulist *refs, struct ulist *roots, const u64 *extent_item_pos, - struct share_check *sc) + struct share_check *sc, bool ignore_offset) { struct btrfs_key key; struct btrfs_path *path; @@ -1235,7 +1243,7 @@ again: WARN_ON(!RB_EMPTY_ROOT(&preftrees.indirect_missing_keys.root)); ret = resolve_indirect_refs(fs_info, path, time_seq, &preftrees, - extent_item_pos, total_refs, sc); + extent_item_pos, total_refs, sc, ignore_offset); if (ret) goto out; @@ -1282,7 +1290,7 @@ again: btrfs_tree_read_lock(eb); btrfs_set_lock_blocking_rw(eb, BTRFS_READ_LOCK); ret = find_extent_in_eb(eb, bytenr, - *extent_item_pos, &eie); + *extent_item_pos, &eie, ignore_offset); btrfs_tree_read_unlock_blocking(eb); free_extent_buffer(eb); if (ret < 0) @@ -1350,7 +1358,7 @@ static void free_leaf_list(struct ulist *blocks) static int btrfs_find_all_leafs(struct btrfs_trans_handle *trans, struct btrfs_fs_info *fs_info, u64 bytenr, u64 time_seq, struct ulist **leafs, - const u64 *extent_item_pos) + const u64 *extent_item_pos, bool ignore_offset) { int ret; @@ -1359,7 +1367,7 @@ static int btrfs_find_all_leafs(struct btrfs_trans_handle *trans, return -ENOMEM; ret = find_parent_nodes(trans, fs_info, bytenr, time_seq, - *leafs, NULL, extent_item_pos, NULL); + *leafs, NULL, extent_item_pos, NULL, ignore_offset); if (ret < 0 && ret != -ENOENT) { free_leaf_list(*leafs); return ret; @@ -1383,7 +1391,8 @@ static int btrfs_find_all_leafs(struct btrfs_trans_handle *trans, */ static int btrfs_find_all_roots_safe(struct btrfs_trans_handle *trans, struct btrfs_fs_info *fs_info, u64 bytenr, - u64 time_seq, struct ulist **roots) + u64 time_seq, struct ulist **roots, + bool ignore_offset) { struct ulist *tmp; struct ulist_node *node = NULL; @@ -1402,7 +1411,7 @@ static int btrfs_find_all_roots_safe(struct btrfs_trans_handle *trans, ULIST_ITER_INIT(&uiter); while (1) { ret = find_parent_nodes(trans, fs_info, bytenr, time_seq, - tmp, *roots, NULL, NULL); + tmp, *roots, NULL, NULL, ignore_offset); if (ret < 0 && ret != -ENOENT) { ulist_free(tmp); ulist_free(*roots); @@ -1421,14 +1430,15 @@ static int btrfs_find_all_roots_safe(struct btrfs_trans_handle *trans, int btrfs_find_all_roots(struct btrfs_trans_handle *trans, struct btrfs_fs_info *fs_info, u64 bytenr, - u64 time_seq, struct ulist **roots) + u64 time_seq, struct ulist **roots, + bool ignore_offset) { int ret; if (!trans) down_read(&fs_info->commit_root_sem); ret = btrfs_find_all_roots_safe(trans, fs_info, bytenr, - time_seq, roots); + time_seq, roots, ignore_offset); if (!trans) up_read(&fs_info->commit_root_sem); return ret; @@ -1483,7 +1493,7 @@ int btrfs_check_shared(struct btrfs_root *root, u64 inum, u64 bytenr) ULIST_ITER_INIT(&uiter); while (1) { ret = find_parent_nodes(trans, fs_info, bytenr, elem.seq, tmp, - roots, NULL, &shared); + roots, NULL, &shared, false); if (ret == BACKREF_FOUND_SHARED) { /* this is the only condition under which we return 1 */ ret = 1; @@ -1877,7 +1887,8 @@ static int iterate_leaf_refs(struct btrfs_fs_info *fs_info, int iterate_extent_inodes(struct btrfs_fs_info *fs_info, u64 extent_item_objectid, u64 extent_item_pos, int search_commit_root, - iterate_extent_inodes_t *iterate, void *ctx) + iterate_extent_inodes_t *iterate, void *ctx, + bool ignore_offset) { int ret; struct btrfs_trans_handle *trans = NULL; @@ -1903,14 +1914,15 @@ int iterate_extent_inodes(struct btrfs_fs_info *fs_info, ret = btrfs_find_all_leafs(trans, fs_info, extent_item_objectid, tree_mod_seq_elem.seq, &refs, - &extent_item_pos); + &extent_item_pos, ignore_offset); if (ret) goto out; ULIST_ITER_INIT(&ref_uiter); while (!ret && (ref_node = ulist_next(refs, &ref_uiter))) { ret = btrfs_find_all_roots_safe(trans, fs_info, ref_node->val, - tree_mod_seq_elem.seq, &roots); + tree_mod_seq_elem.seq, &roots, + ignore_offset); if (ret) break; ULIST_ITER_INIT(&root_uiter); @@ -1943,7 +1955,8 @@ out: int iterate_inodes_from_logical(u64 logical, struct btrfs_fs_info *fs_info, struct btrfs_path *path, - iterate_extent_inodes_t *iterate, void *ctx) + iterate_extent_inodes_t *iterate, void *ctx, + bool ignore_offset) { int ret; u64 extent_item_pos; @@ -1961,7 +1974,7 @@ int iterate_inodes_from_logical(u64 logical, struct btrfs_fs_info *fs_info, extent_item_pos = logical - found_key.objectid; ret = iterate_extent_inodes(fs_info, found_key.objectid, extent_item_pos, search_commit_root, - iterate, ctx); + iterate, ctx, ignore_offset); return ret; } diff --git a/fs/btrfs/backref.h b/fs/btrfs/backref.h index e410335841aa..0c2fab8514ff 100644 --- a/fs/btrfs/backref.h +++ b/fs/btrfs/backref.h @@ -43,17 +43,19 @@ int tree_backref_for_extent(unsigned long *ptr, struct extent_buffer *eb, int iterate_extent_inodes(struct btrfs_fs_info *fs_info, u64 extent_item_objectid, u64 extent_offset, int search_commit_root, - iterate_extent_inodes_t *iterate, void *ctx); + iterate_extent_inodes_t *iterate, void *ctx, + bool ignore_offset); int iterate_inodes_from_logical(u64 logical, struct btrfs_fs_info *fs_info, struct btrfs_path *path, - iterate_extent_inodes_t *iterate, void *ctx); + iterate_extent_inodes_t *iterate, void *ctx, + bool ignore_offset); int paths_from_inode(u64 inum, struct inode_fs_paths *ipath); int btrfs_find_all_roots(struct btrfs_trans_handle *trans, struct btrfs_fs_info *fs_info, u64 bytenr, - u64 time_seq, struct ulist **roots); + u64 time_seq, struct ulist **roots, bool ignore_offset); char *btrfs_ref_to_path(struct btrfs_root *fs_root, struct btrfs_path *path, u32 name_len, unsigned long name_off, struct extent_buffer *eb_in, u64 parent, diff --git a/fs/btrfs/inode.c b/fs/btrfs/inode.c index 3f1b53f85735..eb20239284a2 100644 --- a/fs/btrfs/inode.c +++ b/fs/btrfs/inode.c @@ -2457,7 +2457,7 @@ static noinline bool record_extent_backrefs(struct btrfs_path *path, ret = iterate_inodes_from_logical(old->bytenr + old->extent_offset, fs_info, path, record_one_backref, - old); + old, false); if (ret < 0 && ret != -ENOENT) return false; diff --git a/fs/btrfs/ioctl.c b/fs/btrfs/ioctl.c index 847d318756d4..2497a5d45d9c 100644 --- a/fs/btrfs/ioctl.c +++ b/fs/btrfs/ioctl.c @@ -4560,7 +4560,7 @@ static long btrfs_ioctl_logical_to_ino(struct btrfs_fs_info *fs_info, } ret = iterate_inodes_from_logical(loi->logical, fs_info, path, - build_ino_list, inodes); + build_ino_list, inodes, false); if (ret == -EINVAL) ret = -ENOENT; if (ret < 0) diff --git a/fs/btrfs/qgroup.c b/fs/btrfs/qgroup.c index e172d4843eae..168fd03ca3ac 100644 --- a/fs/btrfs/qgroup.c +++ b/fs/btrfs/qgroup.c @@ -1441,7 +1441,7 @@ int btrfs_qgroup_trace_extent_post(struct btrfs_fs_info *fs_info, u64 bytenr = qrecord->bytenr; int ret; - ret = btrfs_find_all_roots(NULL, fs_info, bytenr, 0, &old_root); + ret = btrfs_find_all_roots(NULL, fs_info, bytenr, 0, &old_root, false); if (ret < 0) return ret; @@ -2031,7 +2031,7 @@ int btrfs_qgroup_account_extents(struct btrfs_trans_handle *trans, /* Search commit root to find old_roots */ ret = btrfs_find_all_roots(NULL, fs_info, record->bytenr, 0, - &record->old_roots); + &record->old_roots, false); if (ret < 0) goto cleanup; } @@ -2042,7 +2042,7 @@ int btrfs_qgroup_account_extents(struct btrfs_trans_handle *trans, * root. It's safe inside commit_transaction(). */ ret = btrfs_find_all_roots(trans, fs_info, - record->bytenr, SEQ_LAST, &new_roots); + record->bytenr, SEQ_LAST, &new_roots, false); if (ret < 0) goto cleanup; if (qgroup_to_skip) { @@ -2570,7 +2570,7 @@ qgroup_rescan_leaf(struct btrfs_fs_info *fs_info, struct btrfs_path *path, num_bytes = found.offset; ret = btrfs_find_all_roots(NULL, fs_info, found.objectid, 0, - &roots); + &roots, false); if (ret < 0) goto out; /* For rescan, just pass old_roots as NULL */ diff --git a/fs/btrfs/scrub.c b/fs/btrfs/scrub.c index cd1b791d9706..b2f871d80982 100644 --- a/fs/btrfs/scrub.c +++ b/fs/btrfs/scrub.c @@ -883,7 +883,7 @@ static void scrub_print_warning(const char *errstr, struct scrub_block *sblock) swarn.dev = dev; iterate_extent_inodes(fs_info, found_key.objectid, extent_item_pos, 1, - scrub_print_warning_inode, &swarn); + scrub_print_warning_inode, &swarn, false); } out: @@ -1047,7 +1047,7 @@ static void scrub_fixup_nodatasum(struct btrfs_work *work) * can be found. */ ret = iterate_inodes_from_logical(fixup->logical, fs_info, path, - scrub_fixup_readpage, fixup); + scrub_fixup_readpage, fixup, false); if (ret < 0) { uncorrectable = 1; goto out; @@ -4390,7 +4390,7 @@ static void copy_nocow_pages_worker(struct btrfs_work *work) } ret = iterate_inodes_from_logical(logical, fs_info, path, - record_inode_for_nocow, nocow_ctx); + record_inode_for_nocow, nocow_ctx, false); if (ret != 0 && ret != -ENOENT) { btrfs_warn(fs_info, "iterate_inodes_from_logical() failed: log %llu, phys %llu, len %llu, mir %u, ret %d", diff --git a/fs/btrfs/send.c b/fs/btrfs/send.c index 13b98a554aab..c10e4c70f02d 100644 --- a/fs/btrfs/send.c +++ b/fs/btrfs/send.c @@ -1423,7 +1423,7 @@ static int find_extent_clone(struct send_ctx *sctx, extent_item_pos = 0; ret = iterate_extent_inodes(fs_info, found_key.objectid, extent_item_pos, 1, __iterate_backrefs, - backref_ctx); + backref_ctx, false); if (ret < 0) goto out; diff --git a/fs/btrfs/tests/qgroup-tests.c b/fs/btrfs/tests/qgroup-tests.c index 0f4ce970d195..90204b166643 100644 --- a/fs/btrfs/tests/qgroup-tests.c +++ b/fs/btrfs/tests/qgroup-tests.c @@ -240,7 +240,8 @@ static int test_no_shared_qgroup(struct btrfs_root *root, * we can only call btrfs_qgroup_account_extent() directly to test * quota. */ - ret = btrfs_find_all_roots(&trans, fs_info, nodesize, 0, &old_roots); + ret = btrfs_find_all_roots(&trans, fs_info, nodesize, 0, &old_roots, + false); if (ret) { ulist_free(old_roots); test_msg("Couldn't find old roots: %d\n", ret); @@ -252,7 +253,8 @@ static int test_no_shared_qgroup(struct btrfs_root *root, if (ret) return ret; - ret = btrfs_find_all_roots(&trans, fs_info, nodesize, 0, &new_roots); + ret = btrfs_find_all_roots(&trans, fs_info, nodesize, 0, &new_roots, + false); if (ret) { ulist_free(old_roots); ulist_free(new_roots); @@ -275,7 +277,8 @@ static int test_no_shared_qgroup(struct btrfs_root *root, old_roots = NULL; new_roots = NULL; - ret = btrfs_find_all_roots(&trans, fs_info, nodesize, 0, &old_roots); + ret = btrfs_find_all_roots(&trans, fs_info, nodesize, 0, &old_roots, + false); if (ret) { ulist_free(old_roots); test_msg("Couldn't find old roots: %d\n", ret); @@ -286,7 +289,8 @@ static int test_no_shared_qgroup(struct btrfs_root *root, if (ret) return -EINVAL; - ret = btrfs_find_all_roots(&trans, fs_info, nodesize, 0, &new_roots); + ret = btrfs_find_all_roots(&trans, fs_info, nodesize, 0, &new_roots, + false); if (ret) { ulist_free(old_roots); ulist_free(new_roots); @@ -337,7 +341,8 @@ static int test_multiple_refs(struct btrfs_root *root, return ret; } - ret = btrfs_find_all_roots(&trans, fs_info, nodesize, 0, &old_roots); + ret = btrfs_find_all_roots(&trans, fs_info, nodesize, 0, &old_roots, + false); if (ret) { ulist_free(old_roots); test_msg("Couldn't find old roots: %d\n", ret); @@ -349,7 +354,8 @@ static int test_multiple_refs(struct btrfs_root *root, if (ret) return ret; - ret = btrfs_find_all_roots(&trans, fs_info, nodesize, 0, &new_roots); + ret = btrfs_find_all_roots(&trans, fs_info, nodesize, 0, &new_roots, + false); if (ret) { ulist_free(old_roots); ulist_free(new_roots); @@ -370,7 +376,8 @@ static int test_multiple_refs(struct btrfs_root *root, return -EINVAL; } - ret = btrfs_find_all_roots(&trans, fs_info, nodesize, 0, &old_roots); + ret = btrfs_find_all_roots(&trans, fs_info, nodesize, 0, &old_roots, + false); if (ret) { ulist_free(old_roots); test_msg("Couldn't find old roots: %d\n", ret); @@ -382,7 +389,8 @@ static int test_multiple_refs(struct btrfs_root *root, if (ret) return ret; - ret = btrfs_find_all_roots(&trans, fs_info, nodesize, 0, &new_roots); + ret = btrfs_find_all_roots(&trans, fs_info, nodesize, 0, &new_roots, + false); if (ret) { ulist_free(old_roots); ulist_free(new_roots); @@ -409,7 +417,8 @@ static int test_multiple_refs(struct btrfs_root *root, return -EINVAL; } - ret = btrfs_find_all_roots(&trans, fs_info, nodesize, 0, &old_roots); + ret = btrfs_find_all_roots(&trans, fs_info, nodesize, 0, &old_roots, + false); if (ret) { ulist_free(old_roots); test_msg("Couldn't find old roots: %d\n", ret); @@ -421,7 +430,8 @@ static int test_multiple_refs(struct btrfs_root *root, if (ret) return ret; - ret = btrfs_find_all_roots(&trans, fs_info, nodesize, 0, &new_roots); + ret = btrfs_find_all_roots(&trans, fs_info, nodesize, 0, &new_roots, + false); if (ret) { ulist_free(old_roots); ulist_free(new_roots); -- cgit v1.2.3 From 0e0adbcfdc908684317c99a9bf5e13383f03b7ec Mon Sep 17 00:00:00 2001 From: Josef Bacik Date: Thu, 19 Oct 2017 14:16:00 -0400 Subject: btrfs: track refs in a rb_tree instead of a list If we get a significant amount of delayed refs for a single block (think modifying multiple snapshots) we can end up spending an ungodly amount of time looping through all of the entries trying to see if they can be merged. This is because we only add them to a list, so we have O(2n) for every ref head. This doesn't make any sense as we likely have refs for different roots, and so they cannot be merged. Tracking in a tree will allow us to break as soon as we hit an entry that doesn't match, making our worst case O(n). With this we can also merge entries more easily. Before we had to hope that matching refs were on the ends of our list, but with the tree we can search down to exact matches and merge them at insert time. Signed-off-by: Josef Bacik Signed-off-by: David Sterba --- fs/btrfs/backref.c | 5 ++- fs/btrfs/delayed-ref.c | 108 +++++++++++++++++++++++++------------------------ fs/btrfs/delayed-ref.h | 5 +-- fs/btrfs/disk-io.c | 10 +++-- fs/btrfs/extent-tree.c | 21 ++++++---- 5 files changed, 82 insertions(+), 67 deletions(-) (limited to 'fs/btrfs/backref.c') diff --git a/fs/btrfs/backref.c b/fs/btrfs/backref.c index 523d2dba7745..7d0dc100a09a 100644 --- a/fs/btrfs/backref.c +++ b/fs/btrfs/backref.c @@ -773,6 +773,7 @@ static int add_delayed_refs(const struct btrfs_fs_info *fs_info, struct btrfs_key key; struct btrfs_key tmp_op_key; struct btrfs_key *op_key = NULL; + struct rb_node *n; int count; int ret = 0; @@ -782,7 +783,9 @@ static int add_delayed_refs(const struct btrfs_fs_info *fs_info, } spin_lock(&head->lock); - list_for_each_entry(node, &head->ref_list, list) { + for (n = rb_first(&head->ref_tree); n; n = rb_next(n)) { + node = rb_entry(n, struct btrfs_delayed_ref_node, + ref_node); if (node->seq > seq) continue; diff --git a/fs/btrfs/delayed-ref.c b/fs/btrfs/delayed-ref.c index 8c7d7db01f7a..83be8f9fd906 100644 --- a/fs/btrfs/delayed-ref.c +++ b/fs/btrfs/delayed-ref.c @@ -143,6 +143,34 @@ static struct btrfs_delayed_ref_head *htree_insert(struct rb_root *root, return NULL; } +static struct btrfs_delayed_ref_node* tree_insert(struct rb_root *root, + struct btrfs_delayed_ref_node *ins) +{ + struct rb_node **p = &root->rb_node; + struct rb_node *node = &ins->ref_node; + struct rb_node *parent_node = NULL; + struct btrfs_delayed_ref_node *entry; + + while (*p) { + int comp; + + parent_node = *p; + entry = rb_entry(parent_node, struct btrfs_delayed_ref_node, + ref_node); + comp = comp_refs(ins, entry, true); + if (comp < 0) + p = &(*p)->rb_left; + else if (comp > 0) + p = &(*p)->rb_right; + else + return entry; + } + + rb_link_node(node, parent_node, p); + rb_insert_color(node, root); + return NULL; +} + /* * find an head entry based on bytenr. This returns the delayed ref * head if it was able to find one, or NULL if nothing was in that spot. @@ -212,7 +240,8 @@ static inline void drop_delayed_ref(struct btrfs_trans_handle *trans, struct btrfs_delayed_ref_node *ref) { assert_spin_locked(&head->lock); - list_del(&ref->list); + rb_erase(&ref->ref_node, &head->ref_tree); + RB_CLEAR_NODE(&ref->ref_node); if (!list_empty(&ref->add_list)) list_del(&ref->add_list); ref->in_tree = 0; @@ -229,24 +258,18 @@ static bool merge_ref(struct btrfs_trans_handle *trans, u64 seq) { struct btrfs_delayed_ref_node *next; + struct rb_node *node = rb_next(&ref->ref_node); bool done = false; - next = list_first_entry(&head->ref_list, struct btrfs_delayed_ref_node, - list); - while (!done && &next->list != &head->ref_list) { + while (!done && node) { int mod; - struct btrfs_delayed_ref_node *next2; - - next2 = list_next_entry(next, list); - - if (next == ref) - goto next; + next = rb_entry(node, struct btrfs_delayed_ref_node, ref_node); + node = rb_next(node); if (seq && next->seq >= seq) - goto next; - + break; if (comp_refs(ref, next, false)) - goto next; + break; if (ref->action == next->action) { mod = next->ref_mod; @@ -270,8 +293,6 @@ static bool merge_ref(struct btrfs_trans_handle *trans, WARN_ON(ref->type == BTRFS_TREE_BLOCK_REF_KEY || ref->type == BTRFS_SHARED_BLOCK_REF_KEY); } -next: - next = next2; } return done; @@ -283,11 +304,12 @@ void btrfs_merge_delayed_refs(struct btrfs_trans_handle *trans, struct btrfs_delayed_ref_head *head) { struct btrfs_delayed_ref_node *ref; + struct rb_node *node; u64 seq = 0; assert_spin_locked(&head->lock); - if (list_empty(&head->ref_list)) + if (RB_EMPTY_ROOT(&head->ref_tree)) return; /* We don't have too many refs to merge for data. */ @@ -304,22 +326,13 @@ void btrfs_merge_delayed_refs(struct btrfs_trans_handle *trans, } spin_unlock(&fs_info->tree_mod_seq_lock); - ref = list_first_entry(&head->ref_list, struct btrfs_delayed_ref_node, - list); - while (&ref->list != &head->ref_list) { +again: + for (node = rb_first(&head->ref_tree); node; node = rb_next(node)) { + ref = rb_entry(node, struct btrfs_delayed_ref_node, ref_node); if (seq && ref->seq >= seq) - goto next; - - if (merge_ref(trans, delayed_refs, head, ref, seq)) { - if (list_empty(&head->ref_list)) - break; - ref = list_first_entry(&head->ref_list, - struct btrfs_delayed_ref_node, - list); continue; - } -next: - ref = list_next_entry(ref, list); + if (merge_ref(trans, delayed_refs, head, ref, seq)) + goto again; } } @@ -402,25 +415,19 @@ again: * Return 0 for insert. * Return >0 for merge. */ -static int -add_delayed_ref_tail_merge(struct btrfs_trans_handle *trans, - struct btrfs_delayed_ref_root *root, - struct btrfs_delayed_ref_head *href, - struct btrfs_delayed_ref_node *ref) +static int insert_delayed_ref(struct btrfs_trans_handle *trans, + struct btrfs_delayed_ref_root *root, + struct btrfs_delayed_ref_head *href, + struct btrfs_delayed_ref_node *ref) { struct btrfs_delayed_ref_node *exist; int mod; int ret = 0; spin_lock(&href->lock); - /* Check whether we can merge the tail node with ref */ - if (list_empty(&href->ref_list)) - goto add_tail; - exist = list_entry(href->ref_list.prev, struct btrfs_delayed_ref_node, - list); - /* No need to compare bytenr nor is_head */ - if (comp_refs(exist, ref, true)) - goto add_tail; + exist = tree_insert(&href->ref_tree, ref); + if (!exist) + goto inserted; /* Now we are sure we can merge */ ret = 1; @@ -451,9 +458,7 @@ add_delayed_ref_tail_merge(struct btrfs_trans_handle *trans, drop_delayed_ref(trans, root, href, exist); spin_unlock(&href->lock); return ret; - -add_tail: - list_add_tail(&ref->list, &href->ref_list); +inserted: if (ref->action == BTRFS_ADD_DELAYED_REF) list_add_tail(&ref->add_list, &href->ref_add_list); atomic_inc(&root->num_entries); @@ -593,7 +598,7 @@ add_delayed_ref_head(struct btrfs_fs_info *fs_info, head_ref->ref_mod = count_mod; head_ref->must_insert_reserved = must_insert_reserved; head_ref->is_data = is_data; - INIT_LIST_HEAD(&head_ref->ref_list); + head_ref->ref_tree = RB_ROOT; INIT_LIST_HEAD(&head_ref->ref_add_list); RB_CLEAR_NODE(&head_ref->href_node); head_ref->processing = 0; @@ -685,7 +690,7 @@ add_delayed_tree_ref(struct btrfs_fs_info *fs_info, ref->is_head = 0; ref->in_tree = 1; ref->seq = seq; - INIT_LIST_HEAD(&ref->list); + RB_CLEAR_NODE(&ref->ref_node); INIT_LIST_HEAD(&ref->add_list); full_ref = btrfs_delayed_node_to_tree_ref(ref); @@ -699,7 +704,7 @@ add_delayed_tree_ref(struct btrfs_fs_info *fs_info, trace_add_delayed_tree_ref(fs_info, ref, full_ref, action); - ret = add_delayed_ref_tail_merge(trans, delayed_refs, head_ref, ref); + ret = insert_delayed_ref(trans, delayed_refs, head_ref, ref); /* * XXX: memory should be freed at the same level allocated. @@ -742,7 +747,7 @@ add_delayed_data_ref(struct btrfs_fs_info *fs_info, ref->is_head = 0; ref->in_tree = 1; ref->seq = seq; - INIT_LIST_HEAD(&ref->list); + RB_CLEAR_NODE(&ref->ref_node); INIT_LIST_HEAD(&ref->add_list); full_ref = btrfs_delayed_node_to_data_ref(ref); @@ -758,8 +763,7 @@ add_delayed_data_ref(struct btrfs_fs_info *fs_info, trace_add_delayed_data_ref(fs_info, ref, full_ref, action); - ret = add_delayed_ref_tail_merge(trans, delayed_refs, head_ref, ref); - + ret = insert_delayed_ref(trans, delayed_refs, head_ref, ref); if (ret > 0) kmem_cache_free(btrfs_delayed_data_ref_cachep, full_ref); } diff --git a/fs/btrfs/delayed-ref.h b/fs/btrfs/delayed-ref.h index 1ce11858d727..a43af432f859 100644 --- a/fs/btrfs/delayed-ref.h +++ b/fs/btrfs/delayed-ref.h @@ -27,8 +27,7 @@ #define BTRFS_UPDATE_DELAYED_HEAD 4 /* not changing ref count on head ref */ struct btrfs_delayed_ref_node { - /*data/tree ref use list, stored in ref_head->ref_list. */ - struct list_head list; + struct rb_node ref_node; /* * If action is BTRFS_ADD_DELAYED_REF, also link this node to * ref_head->ref_add_list, then we do not need to iterate the @@ -92,7 +91,7 @@ struct btrfs_delayed_ref_head { struct mutex mutex; spinlock_t lock; - struct list_head ref_list; + struct rb_root ref_tree; /* accumulate add BTRFS_ADD_DELAYED_REF nodes to this ref_add_list. */ struct list_head ref_add_list; diff --git a/fs/btrfs/disk-io.c b/fs/btrfs/disk-io.c index d1f396f72979..efce9a2fa9be 100644 --- a/fs/btrfs/disk-io.c +++ b/fs/btrfs/disk-io.c @@ -4113,7 +4113,7 @@ static int btrfs_destroy_delayed_refs(struct btrfs_transaction *trans, while ((node = rb_first(&delayed_refs->href_root)) != NULL) { struct btrfs_delayed_ref_head *head; - struct btrfs_delayed_ref_node *tmp; + struct rb_node *n; bool pin_bytes = false; head = rb_entry(node, struct btrfs_delayed_ref_head, @@ -4129,10 +4129,12 @@ static int btrfs_destroy_delayed_refs(struct btrfs_transaction *trans, continue; } spin_lock(&head->lock); - list_for_each_entry_safe_reverse(ref, tmp, &head->ref_list, - list) { + while ((n = rb_first(&head->ref_tree)) != NULL) { + ref = rb_entry(n, struct btrfs_delayed_ref_node, + ref_node); ref->in_tree = 0; - list_del(&ref->list); + rb_erase(&ref->ref_node, &head->ref_tree); + RB_CLEAR_NODE(&ref->ref_node); if (!list_empty(&ref->add_list)) list_del(&ref->add_list); atomic_dec(&delayed_refs->num_entries); diff --git a/fs/btrfs/extent-tree.c b/fs/btrfs/extent-tree.c index fc9720e28005..673ac4e01dd0 100644 --- a/fs/btrfs/extent-tree.c +++ b/fs/btrfs/extent-tree.c @@ -2519,7 +2519,7 @@ select_delayed_ref(struct btrfs_delayed_ref_head *head) { struct btrfs_delayed_ref_node *ref; - if (list_empty(&head->ref_list)) + if (RB_EMPTY_ROOT(&head->ref_tree)) return NULL; /* @@ -2532,8 +2532,8 @@ select_delayed_ref(struct btrfs_delayed_ref_head *head) return list_first_entry(&head->ref_add_list, struct btrfs_delayed_ref_node, add_list); - ref = list_first_entry(&head->ref_list, struct btrfs_delayed_ref_node, - list); + ref = rb_entry(rb_first(&head->ref_tree), + struct btrfs_delayed_ref_node, ref_node); ASSERT(list_empty(&ref->add_list)); return ref; } @@ -2593,7 +2593,7 @@ static int cleanup_ref_head(struct btrfs_trans_handle *trans, spin_unlock(&head->lock); spin_lock(&delayed_refs->lock); spin_lock(&head->lock); - if (!list_empty(&head->ref_list) || head->extent_op) { + if (!RB_EMPTY_ROOT(&head->ref_tree) || head->extent_op) { spin_unlock(&head->lock); spin_unlock(&delayed_refs->lock); return 1; @@ -2740,7 +2740,8 @@ static noinline int __btrfs_run_delayed_refs(struct btrfs_trans_handle *trans, actual_count++; ref->in_tree = 0; - list_del(&ref->list); + rb_erase(&ref->ref_node, &locked_ref->ref_tree); + RB_CLEAR_NODE(&ref->ref_node); if (!list_empty(&ref->add_list)) list_del(&ref->add_list); /* @@ -3138,6 +3139,7 @@ static noinline int check_delayed_ref(struct btrfs_root *root, struct btrfs_delayed_data_ref *data_ref; struct btrfs_delayed_ref_root *delayed_refs; struct btrfs_transaction *cur_trans; + struct rb_node *node; int ret = 0; cur_trans = root->fs_info->running_transaction; @@ -3170,7 +3172,12 @@ static noinline int check_delayed_ref(struct btrfs_root *root, spin_unlock(&delayed_refs->lock); spin_lock(&head->lock); - list_for_each_entry(ref, &head->ref_list, list) { + /* + * XXX: We should replace this with a proper search function in the + * future. + */ + for (node = rb_first(&head->ref_tree); node; node = rb_next(node)) { + ref = rb_entry(node, struct btrfs_delayed_ref_node, ref_node); /* If it's a shared ref we know a cross reference exists */ if (ref->type != BTRFS_EXTENT_DATA_REF_KEY) { ret = 1; @@ -7141,7 +7148,7 @@ static noinline int check_ref_cleanup(struct btrfs_trans_handle *trans, goto out_delayed_unlock; spin_lock(&head->lock); - if (!list_empty(&head->ref_list)) + if (!RB_EMPTY_ROOT(&head->ref_tree)) goto out; if (head->extent_op) { -- cgit v1.2.3