From: Edmund Nadolski <enadolski@suse.com>
To: enadolski@suse.com, linux-btrfs@vger.kernel.org
Subject: [PATCH 12/13] btrfs: allow backref search checks for shared extents
Date: Tue, 20 Jun 2017 10:06:52 -0600 [thread overview]
Message-ID: <20170620160653.19907-13-enadolski@suse.com> (raw)
In-Reply-To: <20170620160653.19907-1-enadolski@suse.com>
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 <enadolski@suse.com>
Signed-off-by: Jeff Mahoney <jeffm@suse.com>
---
fs/btrfs/backref.c | 165 ++++++++++++++++++++++++++++++++++++-----------------
1 file changed, 112 insertions(+), 53 deletions(-)
diff --git a/fs/btrfs/backref.c b/fs/btrfs/backref.c
index e95049a..7f02c51 100644
--- a/fs/btrfs/backref.c
+++ b/fs/btrfs/backref.c
@@ -139,6 +139,25 @@ struct preftrees {
struct preftree indirect; /* BTRFS_[TREE_BLOCK|EXTENT_DATA]_REF_KEY */
};
+/*
+ * 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)
@@ -199,14 +218,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;
@@ -238,12 +269,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;
release_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);
@@ -307,7 +346,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;
@@ -352,31 +392,31 @@ 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)
{
return add_prelim_ref(fs_info, &preftrees->indirect, root_id, key,
- level, 0, wanted_disk_byte, count, gfp_mask);
+ level, 0, wanted_disk_byte, count, sc, 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,
@@ -572,7 +612,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;
@@ -609,7 +649,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) {
release_pref(ref);
ret = BACKREF_FOUND_SHARED;
goto out;
@@ -651,11 +692,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();
@@ -710,7 +755,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;
@@ -752,7 +797,7 @@ static int add_delayed_refs(const struct btrfs_fs_info *fs_info,
&op_key, ref->level + 1,
node->bytenr,
node->ref_mod * sgn,
- GFP_ATOMIC);
+ sc, GFP_ATOMIC);
break;
}
case BTRFS_SHARED_BLOCK_REF_KEY: {
@@ -764,7 +809,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: {
@@ -780,15 +825,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: {
@@ -800,26 +845,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;
@@ -876,7 +930,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;
@@ -886,13 +940,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;
@@ -906,7 +960,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;
}
@@ -915,7 +969,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:
@@ -931,11 +985,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;
@@ -968,7 +1024,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 */
@@ -980,14 +1036,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 */
@@ -1003,7 +1059,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;
}
@@ -1011,7 +1067,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:
@@ -1031,20 +1087,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;
@@ -1124,17 +1183,13 @@ static int find_parent_nodes(struct btrfs_trans_handle *trans,
}
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;
} else {
spin_unlock(&delayed_refs->lock);
}
-
- /*
- * TODO - implement short circuit for BACKREF_FOUND_SHARED
- */
}
if (path->slots[0]) {
@@ -1150,11 +1205,11 @@ static int find_parent_nodes(struct btrfs_trans_handle *trans,
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;
}
@@ -1167,8 +1222,7 @@ static int find_parent_nodes(struct btrfs_trans_handle *trans,
goto out;
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;
@@ -1187,7 +1241,8 @@ static int find_parent_nodes(struct btrfs_trans_handle *trans,
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;
}
@@ -1290,7 +1345,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;
@@ -1333,7 +1388,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);
@@ -1389,6 +1444,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);
@@ -1408,9 +1468,8 @@ int btrfs_check_shared(struct btrfs_root *root, u64 inum, u64 bytenr)
ULIST_ITER_INIT(&uiter);
while (1) {
- /* TODO - short-circuit when only checking for shared... */
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;
--
2.10.2
next prev parent reply other threads:[~2017-06-20 16:06 UTC|newest]
Thread overview: 23+ messages / expand[flat|nested] mbox.gz Atom feed top
2017-06-20 16:06 [PATCH 00/13] use rbtrees for preliminary backrefs Edmund Nadolski
2017-06-20 16:06 ` [PATCH 01/13] btrfs: struct-funcs, constify readers Edmund Nadolski
2017-06-20 16:06 ` [PATCH 02/13] btrfs: constify tracepoint arguments Edmund Nadolski
2017-06-20 16:06 ` [PATCH 03/13] btrfs: backref, constify some arguments Edmund Nadolski
2017-06-20 16:06 ` [PATCH 04/13] btrfs: backref, add unode_aux_to_inode_list helper Edmund Nadolski
2017-06-20 16:06 ` [PATCH 05/13] btrfs: backref, cleanup __ namespace abuse Edmund Nadolski
2017-06-20 16:06 ` [PATCH 06/13] btrfs: btrfs_check_shared should manage its own transaction Edmund Nadolski
2017-06-27 15:40 ` David Sterba
2017-06-20 16:06 ` [PATCH 07/13] btrfs: remove ref_tree implementation from backref.c Edmund Nadolski
2017-06-27 15:48 ` David Sterba
2017-06-20 16:06 ` [PATCH 08/13] btrfs: convert prelimary reference tracking to use rbtrees Edmund Nadolski
2017-06-26 17:07 ` Jeff Mahoney
2017-06-27 20:09 ` Jeff Mahoney
2017-06-27 21:11 ` [PATCH] btrfs: backref, properly iterate the missing keys Jeff Mahoney
2017-06-27 16:49 ` [PATCH 08/13] btrfs: convert prelimary reference tracking to use rbtrees David Sterba
2017-06-27 21:10 ` Jeff Mahoney
2017-07-04 17:02 ` David Sterba
2017-06-20 16:06 ` [PATCH 09/13] btrfs: add a node counter to each of the rbtrees Edmund Nadolski
2017-06-20 16:06 ` [PATCH 10/13] btrfs: backref, add tracepoints for prelim_ref insertion and merging Edmund Nadolski
2017-06-20 16:06 ` [PATCH 11/13] btrfs: add cond_resched() calls when resolving backrefs Edmund Nadolski
2017-06-20 16:06 ` Edmund Nadolski [this message]
2017-06-20 16:06 ` [PATCH 13/13] btrfs: clean up extraneous computations in add_delayed_refs Edmund Nadolski
2017-06-27 17:06 ` [PATCH 00/13] use rbtrees for preliminary backrefs David Sterba
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=20170620160653.19907-13-enadolski@suse.com \
--to=enadolski@suse.com \
--cc=linux-btrfs@vger.kernel.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.