btrfs: quota: Skip unmodified tree blocks for balance
Subsystems (2)
cover btrfs: quota: Skip unmodified tree blocks for balance
This patchset can be fetched from github:
https://github.com/adam900710/linux/tree/qgroup_balance_skip_trees
The base commit is v4.19-rc1 tag.
There are a lot of reports of system hang for balance on quota enabled fs.
It's most obvious for large fs.
The hang is caused by tons of unmodified extents marked as qgroup dirty. One of the unmodified extent source is tree blocks.
(BTW, other sources includes unmodified file extent items, and tree reloc tree drop subtree)
E.g.
OO = Old tree blocks from file tree
NN = New tree blocks from tree reloc tree
file tree tree reloc tree
OO (a) NN (a)
/ \ / \
(b) OO OO (c) (b) NN NN (c)
/ \ / \ / \ / \
OO OO OO OO OO OO OO NN
(d) (e) (f) (g) (d) (e) (f) (g)
In above case, balance will modify nodeptr in OO(a) to point NN(b) and NN(c), and modify NN(a) to point to OO(B) and OO(c).
Before this patch, quota will mark the whole subtree from its parent down to the leaves as dirty.
So btrfs quota need to trace all tree block from (a) to (g).
However tree blocks (d) (e) (f) are shared between both trees, thus there is no need to trace those 3 tree blocks.
This patchset will change how this work by only tracing modified tree blocks in tree reloc tree, and their counter parts in file tree.
Nodeptr swap will happen for tree blocks (b) and (c) in both tree.
For tree block (b), in tree reloc tree we could find that all its children's generation is smaller than last_snapshot, thus no need to trace them, only need to trace NN(b), and its counter part OO(b).
For tree block (c), in tree reloc tree, we find its child NN(g) need tracing, and for tree block NN(g), there is no child need to trace.
So for subtree starting at tree block NN(c), we need to trace NN(c) and NN(g), along with its counter part OO(c) and OO(c).
With this patch, we could skip tree blocks OO(d)~OO(f) in above example, thus reduce some some overhead caused by qgroup.
The improvement is mostly related to metadata relocation.
If there is some high level tree blocks get relocated but its children are still unmodified, we could save a lot of time.
Even for the worst case, it should be no worse than original full subtree marking method.
Qu Wenruo (4):
btrfs: qgroup: Introduce trace event to analyse the number of dirty
extents accounted
btrfs: qgroup: Introduce function to trace two swaped extents
btrfs: qgroup: Introduce function to find all new tree blocks of tree
reloc tree
btrfs: qgroup: Use generation aware subtree swap to mark dirty extents
fs/btrfs/qgroup.c | 327 +++++++++++++++++++++++++++++++++++ fs/btrfs/qgroup.h | 10 ++ fs/btrfs/relocation.c | 11 +- include/trace/events/btrfs.h | 21 +++ 4 files changed, 361 insertions(+), 8 deletions(-)
Signature · 1 line
2.18.0
PATCH 1/4 btrfs: qgroup: Introduce trace event to analyse the number of dirty extents accounted
Number of qgroup dirty extents is directly linked to the performance overhead, so add a new trace event, trace_qgroup_num_dirty_extents(), to record how many dirty extents is processed in btrfs_qgroup_account_extents().
This will be pretty handy to analyse later balance performance improvement.
--- fs/btrfs/qgroup.c | 4 ++++ include/trace/events/btrfs.h | 21 +++++++++++++++++++++ 2 files changed, 25 insertions(+)
fs/btrfs/qgroup.c +4 -0
@@ -2133,6 +2133,7 @@ int btrfs_qgroup_account_extents(struct btrfs_trans_handle *trans)struct btrfs_delayed_ref_root *delayed_refs;struct ulist *new_roots =NULL ;struct rb_node *node; +u64 num_dirty_extents =0 ;u64 qgroup_to_skip;int ret =0 ;
@@ -2142,6 +2143,7 @@ int btrfs_qgroup_account_extents(struct btrfs_trans_handle *trans) record = rb_entry(node, struct btrfs_qgroup_extent_record, node); + num_dirty_extents++;trace_btrfs_qgroup_account_extents (fs_info, record);if (!ret) {
@@ -2187,6 +2189,8 @@ int btrfs_qgroup_account_extents(struct btrfs_trans_handle *trans)kfree (record); } +trace_qgroup_num_dirty_extents (fs_info, trans->transid, + num_dirty_extents);return ret; }
include/trace/events/btrfs.h +21 -0
@@ -1575,6 +1575,27 @@ DEFINE_EVENT(btrfs_qgroup_extent, btrfs_qgroup_trace_extent,TP_ARGS (fs_info, rec) ); +TRACE_EVENT (qgroup_num_dirty_extents, + + TP_PROTO(const struct btrfs_fs_info *fs_info, u64 transid, + u64 num_dirty_extents), + +TP_ARGS (fs_info, transid, num_dirty_extents), + +TP_STRUCT__entry_btrfs ( + __field( u64, transid ) +__field ( u64, num_dirty_extents ) + ), + +TP_fast_assign_btrfs (fs_info, + __entry->transid = transid; + __entry->num_dirty_extents = num_dirty_extents; + ), + +TP_printk_btrfs ("transid=%llu num_dirty_extents=%llu" , + __entry->transid, __entry->num_dirty_extents) +); + TRACE_EVENT(btrfs_qgroup_account_extent, TP_PROTO(const struct btrfs_fs_info *fs_info, u64 transid, u64 bytenr,
Signature · 1 line
2.18.0
PATCH 2/4 btrfs: qgroup: Introduce function to trace two swaped extents
In reply to Qu WenruoIntroduce a new function, qgroup_trace_extent_swap(), which will be used later for balance qgroup speedup.
The basis idea of balance is swapping tree blocks between tree reloc tree and the real file tree.
The swap will happen in highest tree block, but there may be a lot of tree blocks involved.
For example:
OO = Old tree blocks
NN = New tree blocks allocated during balance
File tree (257) Tree reloc tree for 257
L2 OO NN
/ \ / \
L1 OO OO (a) OO NN (a)
/ \ / \ / \ / \
L0 OO OO OO OO OO OO NN NN
(b) (c) (b) (c)When calling qgroup_trace_extent_swap(), we will pass:
@src_eb = OO(a)
@dst_path = [ nodes[1] = NN(a), nodes[0] = NN(c) ] @dst_level = 0
@root_level = 1
In that case, qgroup_trace_extent_swap() will search from OO(a) to reach OO(c), then mark both OO(c) and NN(c) as qgroup dirty.
The main work of qgroup_trace_extent_swap() can be split into 3 parts:
1) Tree search from @src_eb
It should acts as a simplified btrfs_search_slot().
The key for search can be extracted from @dst_path->nodes[dst_level] (first key).
2) Mark the final tree blocks in @src_path and @dst_path qgroup dirty
NOTE: In above case, OO(a) and NN(a) won't be marked qgroup dirty. They should be marked during preivous (@dst_level = 1) iteration.
3) Mark file extents in leaves dirty
We don't have good way to pick out new file extents only. So we still follow the old method by scanning all file extents in the leave.
This function can free us from keeping two pathes, thus later we only need to care about how to iterate all new tree blocks in tree reloc tree.
--- fs/btrfs/qgroup.c | 115 ++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 115 insertions(+)
fs/btrfs/qgroup.c +115 -0
@@ -1713,6 +1713,121 @@ static int adjust_slots_upwards(struct btrfs_path *path, int root_level)return 0 ; } +/* +* helper function to trace a subtree tree block swap. +* +* The swapped tree block is marked by @dst_path->nodes[level]. +* Thus @dst_path should have been populated already. +* +* While for src tree block, we only need the root eb as @src_eb. +* The needed path and search will done by this function. +*/ +static int qgroup_trace_extent_swap (struct btrfs_trans_handle * trans, +struct extent_buffer *src_eb, +struct btrfs_path *dst_path, +int dst_level,int root_level) +{ +struct btrfs_key key; +struct btrfs_path *src_path; +struct btrfs_fs_info *fs_info = trans->fs_info; +u32 nodesize = fs_info->nodesize; +int cur_level = root_level; +int ret; + +BUG_ON (dst_level > root_level); +/* Level mismatch */ +if (btrfs_header_level (src_eb) != root_level) +return -EINVAL ; + + src_path =btrfs_alloc_path (); +if (!src_path) { + ret = -ENOMEM ; + goto out; + } + +if (dst_level) +btrfs_node_key_to_cpu (dst_path->nodes[dst_level], &key,0 ); +else +btrfs_item_key_to_cpu (dst_path->nodes[dst_level], &key,0 ); + +/* For src_path */ +extent_buffer_get (src_eb); + src_path->nodes[root_level] = src_eb; + src_path->slots[root_level] =0 ; + src_path->locks[root_level] =0 ; + +/* A simplified version of btrfs_search_slot() */ +while (cur_level >= dst_level) { +if (src_path->nodes[cur_level] ==NULL ) { +struct btrfs_key first_key; +struct extent_buffer *eb; +int parent_slot; +u64 child_gen; +u64 child_bytenr; + + eb = src_path->nodes[cur_level +1 ]; + parent_slot = src_path->slots[cur_level +1 ]; + child_bytenr =btrfs_node_blockptr (eb, parent_slot); + child_gen =btrfs_node_ptr_generation (eb, parent_slot); +btrfs_node_key_to_cpu (eb, &first_key, parent_slot); + + eb =read_tree_block (fs_info, child_bytenr, child_gen, + cur_level, &first_key); +if (IS_ERR (eb)) { + ret =PTR_ERR (eb); + goto out; + }else if (!extent_buffer_uptodate (eb)) { +free_extent_buffer (eb); + ret = -EIO ; + goto out; + } + + src_path->nodes[cur_level] = eb; + +btrfs_tree_read_lock (eb); +btrfs_set_lock_blocking_rw (eb,BTRFS_READ_LOCK ); + src_path->locks[cur_level] =BTRFS_READ_LOCK_BLOCKING ; + } + ret =btrfs_bin_search (src_path->nodes[cur_level], &key, + cur_level, &src_path->slots[cur_level]); +if (ret <0 ) + goto out; + +/* Can't find the final slot, something went wrong */ +if (cur_level == dst_level && ret >0 ) { + ret = -ENOENT ; + goto out; + } + cur_level--; + } + +/* +* Now both @dst_path and @src_path have been populated, record the tree +* blocks for qgroup accounting. +*/ + ret =btrfs_qgroup_trace_extent (trans, + src_path->nodes[dst_level]->start, + nodesize,GFP_NOFS ); +if (ret <0 ) + goto out; + ret =btrfs_qgroup_trace_extent (trans, + dst_path->nodes[dst_level]->start, + nodesize,GFP_NOFS ); +if (ret <0 ) + goto out; + +/* Record leaf file extents */ +if (dst_level ==0 ) { + ret =btrfs_qgroup_trace_leaf_items (trans, src_path->nodes[0 ]); +if (ret <0 ) + goto out; + ret =btrfs_qgroup_trace_leaf_items (trans, dst_path->nodes[0 ]); + } +out: +btrfs_free_path (src_path); +return ret; +} +int btrfs_qgroup_trace_subtree (struct btrfs_trans_handle *trans,struct extent_buffer *root_eb,u64 root_gen,int root_level)
Signature · 1 line
2.18.0
PATCH 3/4 btrfs: qgroup: Introduce function to find all new tree blocks of tree reloc tree
In reply to Qu WenruoIntroduce new function, qgroup_trace_new_subtree_blocks(), to iterate all new tree blocks in a tree reloc tree.
So that qgroup could skip unrelated tree blocks during balance, which should hugely speedup balance speed when quota is enabled.
The function qgroup_trace_new_subtree_blocks() itself only cares about new tree blocks in tree reloc tree.
All its main works are:
1) Read out tree blocks according to parent pointers
2) Do recursive depth-first search
Will call the same function on all its children tree blocks, with search level set to current level -1.
And will also skip all children whose generation is smaller than @last_snapshot.
3) Call qgroup_trace_extent_swap() to trace tree blocks
So although we have parameter list related to source file tree, it's not used at all, but only passed to qgroup_trace_extent_swap(). Thus despite the tree read code, the core should be pretty short and all about recursive depth-first search.
--- fs/btrfs/qgroup.c | 114 ++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 114 insertions(+)
fs/btrfs/qgroup.c +114 -0
@@ -1828,6 +1828,120 @@ static int qgroup_trace_extent_swap(struct btrfs_trans_handle* trans,return ret; } +/* +* Helper function to do recursive generation aware depth-first search, to +* locate all new tree blocks in a subtree of tree reloc tree. +* +* E.g. (OO = Old tree blocks, NN = New tree blocks, whose gen == last_snapshot) +* Tree reloc tree +* L2 NN (a) +* / \ +* L1 OO NN (b) +* / \ / \ +* L0 OO OO OO NN +* (c) (d) +* If we pass: +* @dst_path = [ nodes[1] = NN(b), nodes[0] = NULL ], +* @cur_level = 1 +* @root_level = 1 +* +* We will iterate through tree blocks NN(b), NN(d) and info qgroup to trace +* above tree blocks along with their counter parts in file tree. +* While during search, old tree blocsk OO(c) will be skiped as tree block swap +* won't affect OO(c). +*/ +static int qgroup_trace_new_subtree_blocks (struct btrfs_trans_handle * trans, +struct extent_buffer *src_eb, +struct btrfs_path *dst_path, +int cur_level,int root_level, +u64 last_snapshot) +{ +struct btrfs_fs_info *fs_info = trans->fs_info; +struct extent_buffer *eb; +bool need_cleanup = false; +int ret =0 ; +int i; + +/* Read the tree block if needed */ +if (dst_path->nodes[cur_level] ==NULL ) { +struct btrfs_key first_key; +int parent_slot; +u64 child_gen; +u64 child_bytenr; + +/* +* We need to get child blockptr/gen from parent before +* we can read it. +*/ + eb = dst_path->nodes[cur_level +1 ]; + parent_slot = dst_path->slots[cur_level +1 ]; + child_bytenr =btrfs_node_blockptr (eb, parent_slot); + child_gen =btrfs_node_ptr_generation (eb, parent_slot); +btrfs_node_key_to_cpu (eb, &first_key, parent_slot); + +/* This node is old, no need to trace */ +if (child_gen < last_snapshot) + goto out; + + eb =read_tree_block (fs_info, child_bytenr, child_gen, + cur_level, &first_key); +if (IS_ERR (eb)) { + ret =PTR_ERR (eb); + goto out; + }else if (!extent_buffer_uptodate (eb)) { +free_extent_buffer (eb); + ret = -EIO ; + goto out; + } + + dst_path->nodes[cur_level] = eb; + dst_path->slots[cur_level] =0 ; + +btrfs_tree_read_lock (eb); +btrfs_set_lock_blocking_rw (eb,BTRFS_READ_LOCK ); + dst_path->locks[cur_level] =BTRFS_READ_LOCK_BLOCKING ; + need_cleanup = true; + } + +/* Now record this tree block and its counter part for qgroups */ + ret =qgroup_trace_extent_swap (trans, src_eb, dst_path, cur_level, + root_level); +if (ret <0 ) + goto cleanup; + + eb = dst_path->nodes[cur_level]; + +if (cur_level >0 ) { +/* Iterate all children tree blocks */ +for (i =0 ; i <btrfs_header_nritems (eb); i++) { +/* Skip old tree blocks as they won't be swapped */ +if (btrfs_node_ptr_generation (eb, i) < last_snapshot) +continue ; + dst_path->slots[cur_level] = i; + +/* Recursive call (at most 7 times) */ + ret =qgroup_trace_new_subtree_blocks (trans, src_eb, + dst_path, cur_level -1 , root_level, + last_snapshot); +if (ret <0 ) + goto cleanup; + } + } + +cleanup: +if (need_cleanup) { +/* Clean up */ +btrfs_tree_unlock_rw (dst_path->nodes[cur_level], + dst_path->locks[cur_level]); +free_extent_buffer (dst_path->nodes[cur_level]); + dst_path->nodes[cur_level] =NULL ; + dst_path->slots[cur_level] =0 ; + dst_path->locks[cur_level] =0 ; + } +out: +return ret; +} +int btrfs_qgroup_trace_subtree (struct btrfs_trans_handle *trans,struct extent_buffer *root_eb,u64 root_gen,int root_level)
Signature · 1 line
2.18.0
PATCH 4/4 btrfs: qgroup: Use generation aware subtree swap to mark dirty extents
In reply to Qu WenruoBefore this patch, for quota enabled balance, btrfs needs to mark the whole subtree dirty for quota.
E.g.
OO = Old tree blocks (from file tree)
NN = New tree blocks (from tree reloc tree)
File tree (src) Tree reloc tree (dst)
OO (a) NN (a)
/ \ / \
(b) OO OO (c) (b) NN NN (c)
/ \ / \ / \ / \
OO OO OO OO (d) OO OO OO NN (d)
For old balance + quota case, quota will mark the whole src and dst tree dirty, including all the 3 old tree blocks in tree reloc tree.
It's doable for small file tree or new tree blocks are all located at lower level.
But for large file tree or new tree blocks are all located at higher level, this will lead to mark the whole tree dirty, and be unbelievably slow.
This patch will change how we handle such balance with quota enabled case.
Now we will search from (b) and (c) for any new tree blocks whose generation is equal to @last_snapshot, and only mark them dirty.
In above case, we only need to trace tree blocks NN(b), NN(c) and NN(d). (NN(a) will be traced when CoW happens for nodeptr modification). And also for tree blocks OO(b), OO(c), OO(d). (OO(a) will be traced when CoW happens for nodeptr modification)
For above case, we could skip 3 tree blocks, but for larger tree, we can skip tons of unmodified tree blocks, and hugely speed up balance.
This patch will introduce a new function, btrfs_qgroup_trace_subtree_swap(), which will do the following main work:
1) Read out real root eb
And setup basic dst_path for later calls
2) Call qgroup_trace_new_subtree_blocks()
To trace all new tree blocks in tree reloc tree and their counter parts in file tree.
--- fs/btrfs/qgroup.c | 94 +++++++++++++++++++++++++++++++++++++++++++ fs/btrfs/qgroup.h | 10 +++++ fs/btrfs/relocation.c | 11 ++--- 3 files changed, 107 insertions(+), 8 deletions(-)
fs/btrfs/qgroup.c +94 -0
@@ -1942,6 +1942,100 @@ static int qgroup_trace_new_subtree_blocks(struct btrfs_trans_handle* trans,return ret; } +/* +* For balance subtree swap. +* +* Will go down the tree block pointed by @dst_eb (pointed by @dst_parent and +* @dst_slot), and find any tree blocks whose generation is at @last_snapshot, +* and then go down @src_eb (pointed by @src_parent and @src_slot) to find +* the conterpart of the tree block, then mark both tree blocks as qgroup dirty, +* and skip all tree blocks whose generation is smaller than last_snapshot. +* +* This would skip tons of tree blocks of original btrfs_qgroup_trace_subtree(), +* which is the culprit of super slow balance if the file tree is large. +* +* @src_parent, @src_slot: pointer to src (file tree) eb. +* @dst_parent, @dst_slot: pointer to dst (tree reloc tree) eb. +*/ +int btrfs_qgroup_trace_subtree_swap (struct btrfs_trans_handle *trans, +struct extent_buffer *src_parent,int src_slot, +struct extent_buffer *dst_parent,int dst_slot, +u64 last_snapshot) +{ +struct btrfs_fs_info *fs_info = trans->fs_info; +struct btrfs_path *dst_path =NULL ; +struct btrfs_key first_key; +struct extent_buffer *src_eb =NULL ; +struct extent_buffer *dst_eb =NULL ; +u64 child_gen; +u64 child_bytenr; +int level; +int ret; + +if (!test_bit (BTRFS_FS_QUOTA_ENABLED , &fs_info->flags)) +return 0 ; + +/* Wrong parameter order */ +BUG_ON (btrfs_node_ptr_generation (src_parent, src_slot) > +btrfs_node_ptr_generation (dst_parent, dst_slot)); + +/* Read out real @src_eb, pointed by @src_parent and @src_slot */ + child_bytenr =btrfs_node_blockptr (src_parent, src_slot); + child_gen =btrfs_node_ptr_generation (src_parent, src_slot); +btrfs_node_key_to_cpu (src_parent, &first_key, src_slot); + + src_eb =read_tree_block (fs_info, child_bytenr, child_gen, +btrfs_header_level (src_parent) -1 , &first_key); +if (IS_ERR (src_eb)) { + ret =PTR_ERR (src_eb); + goto out; + } + +/* Read out real @dst_eb, pointed by @src_parent and @src_slot */ + child_bytenr =btrfs_node_blockptr (dst_parent, dst_slot); + child_gen =btrfs_node_ptr_generation (dst_parent, dst_slot); +btrfs_node_key_to_cpu (dst_parent, &first_key, dst_slot); + + dst_eb =read_tree_block (fs_info, child_bytenr, child_gen, +btrfs_header_level (dst_parent) -1 , &first_key); +if (IS_ERR (dst_eb)) { + ret =PTR_ERR (dst_eb); + goto out; + } + +if (!extent_buffer_uptodate (src_eb) || !extent_buffer_uptodate (dst_eb)) { + ret = -EINVAL ; + goto out; + } + + level =btrfs_header_level (dst_eb); + dst_path =btrfs_alloc_path (); +if (!dst_path) { + ret = -ENOMEM ; + goto out; + } +/* For dst_path */ +extent_buffer_get (dst_eb); + dst_path->nodes[level] = dst_eb; + dst_path->slots[level] =0 ; + dst_path->locks[level] =0 ; + +/* Do the generation aware breadth-first search */ + ret =qgroup_trace_new_subtree_blocks (trans, src_eb, dst_path, level, + level, last_snapshot); +if (ret <0 ) + goto out; + ret =0 ; + +out: +free_extent_buffer (src_eb); +free_extent_buffer (dst_eb); +btrfs_free_path (dst_path); +if (ret <0 ) + fs_info->qgroup_flags |=BTRFS_QGROUP_STATUS_FLAG_INCONSISTENT ; +return ret; +} +int btrfs_qgroup_trace_subtree (struct btrfs_trans_handle *trans,struct extent_buffer *root_eb,u64 root_gen,int root_level)
fs/btrfs/qgroup.h +10 -0
@@ -236,6 +236,16 @@ int btrfs_qgroup_trace_leaf_items(struct btrfs_trans_handle *trans,int btrfs_qgroup_trace_subtree (struct btrfs_trans_handle *trans,struct extent_buffer *root_eb,u64 root_gen,int root_level); + +/* +* Inform qgroup to trace subtree swap used in balance. +* Unlike btrfs_qgroup_trace_subtree(), this function will only trace +* new tree blocks whose generation is equal to (or larger than) @last_snapshot. +*/ +int btrfs_qgroup_trace_subtree_swap (struct btrfs_trans_handle *trans, +struct extent_buffer *src_parent,int src_slot, +struct extent_buffer *dst_parent,int dst_slot, +u64 last_snapshot);int btrfs_qgroup_account_extent (struct btrfs_trans_handle *trans,u64 bytenr,u64 num_bytes,struct ulist *old_roots,struct ulist *new_roots);
fs/btrfs/relocation.c +3 -8
@@ -1879,14 +1879,9 @@ int replace_path(struct btrfs_trans_handle *trans,* and tree block numbers, if current trans doesn't free * data reloc tree inode. */ - ret =btrfs_qgroup_trace_subtree (trans, parent, -btrfs_header_generation (parent), -btrfs_header_level (parent)); -if (ret <0 ) -break ; - ret =btrfs_qgroup_trace_subtree (trans, path->nodes[level], -btrfs_header_generation (path->nodes[level]), -btrfs_header_level (path->nodes[level])); + ret =btrfs_qgroup_trace_subtree_swap (trans, parent, slot, + path->nodes[level], path->slots[level], + last_snapshot);if (ret <0 )break ;
Signature · 1 line
2.18.0