linux-toradex.git/fs/btrfs/delayed-ref.c, branch v5.0

btrfs: introduce delayed_refs_rsv

2018-12-17T13:51:46+00:00

Traditionally we've had voodoo in btrfs to account for the space that
delayed refs may take up by having a global_block_rsv.  This works most
of the time, except when it doesn't.  We've had issues reported and seen
in production where sometimes the global reserve is exhausted during
transaction commit before we can run all of our delayed refs, resulting
in an aborted transaction.  Because of this voodoo we have equally
dubious flushing semantics around throttling delayed refs which we often
get wrong.

So instead give them their own block_rsv.  This way we can always know
exactly how much outstanding space we need for delayed refs.  This
allows us to make sure we are constantly filling that reservation up
with space, and allows us to put more precise pressure on the enospc
system.  Instead of doing math to see if its a good time to throttle,
the normal enospc code will be invoked if we have a lot of delayed refs
pending, and they will be run via the normal flushing mechanism.

For now the delayed_refs_rsv will hold the reservations for the delayed
refs, the block group updates, and deleting csums.  We could have a
separate rsv for the block group updates, but the csum deletion stuff is
still handled via the delayed_refs so that will stay there.

Historical background:

The global reserve has grown to cover everything we don't reserve space
explicitly for, and we've grown a lot of weird ad-hoc heuristics to know
if we're running short on space and when it's time to force a commit.  A
failure rate of 20-40 file systems when we run hundreds of thousands of
them isn't super high, but cleaning up this code will make things less
ugly and more predictible.

Thus the delayed refs rsv.  We always know how many delayed refs we have
outstanding, and although running them generates more we can use the
global reserve for that spill over, which fits better into it's desired
use than a full blown reservation.  This first approach is to simply
take how many times we're reserving space for and multiply that by 2 in
order to save enough space for the delayed refs that could be generated.
This is a niave approach and will probably evolve, but for now it works.

Signed-off-by: Josef Bacik 
Reviewed-by: David Sterba  # high-level review
[ added background notes from the cover letter ]
Signed-off-by: David Sterba

btrfs: only track ref_heads in delayed_ref_updates

2018-12-17T13:51:46+00:00

We use this number to figure out how many delayed refs to run, but
__btrfs_run_delayed_refs really only checks every time we need a new
delayed ref head, so we always run at least one ref head completely no
matter what the number of items on it.  Fix the accounting to only be
adjusted when we add/remove a ref head.

In addition to using this number to limit the number of delayed refs
run, a future patch is also going to use it to calculate the amount of
space required for delayed refs space reservation.

Reviewed-by: Nikolay Borisov 
Signed-off-by: Josef Bacik 
Signed-off-by: David Sterba

btrfs: add btrfs_delete_ref_head helper

2018-12-17T13:51:46+00:00

We do this dance in cleanup_ref_head and check_ref_cleanup, unify it
into a helper and cleanup the calling functions.

Reviewed-by: Omar Sandoval 
Reviewed-by: Nikolay Borisov 
Signed-off-by: Josef Bacik 
Reviewed-by: David Sterba 
Signed-off-by: David Sterba

btrfs: delayed-ref: extract find_first_ref_head from find_ref_head

2018-10-17T17:21:00+00:00

The find_ref_head shouldn't return the first entry even if no exact match
is found. So move the hidden behavior to higher level.

Besides, remove the useless local variables in the btrfs_select_ref_head.

Reviewed-by: Nikolay Borisov 
Signed-off-by: Lu Fengqi 
[ reformat comment ]
Signed-off-by: David Sterba

btrfs: switch return_bigger to bool in find_ref_head

2018-10-15T15:23:41+00:00

Using bool is more suitable than int here, and add the comment about the
return_bigger.

Signed-off-by: Lu Fengqi 
Reviewed-by: Nikolay Borisov 
Reviewed-by: David Sterba 
Signed-off-by: David Sterba

btrfs: delayed-ref: pass delayed_refs directly to btrfs_delayed_ref_lock

2018-10-15T15:23:41+00:00

Since trans is only used for referring to delayed_refs, there is no need
to pass it instead of delayed_refs to btrfs_delayed_ref_lock().

No functional change.

Reviewed-by: Nikolay Borisov 
Signed-off-by: Lu Fengqi 
Reviewed-by: David Sterba 
Signed-off-by: David Sterba

btrfs: delayed-ref: pass delayed_refs directly to btrfs_select_ref_head

2018-10-15T15:23:40+00:00

Since trans is only used for referring to delayed_refs, there is no need
to pass it instead of delayed_refs to btrfs_select_ref_head().  No
functional change.

Signed-off-by: Lu Fengqi 
Reviewed-by: Nikolay Borisov 
Reviewed-by: David Sterba 
Signed-off-by: David Sterba

Btrfs: delayed-refs: use rb_first_cached for ref_tree

2018-10-15T15:23:33+00:00

rb_first_cached() trades an extra pointer "leftmost" for doing the same
job as rb_first() but in O(1).

Functions manipulating href->ref_tree need to get the first entry, this
converts href->ref_tree to use rb_first_cached().

For more details about the optimization see patch "Btrfs: delayed-refs:
use rb_first_cached for href_root".

Tested-by: Holger Hoffstätte 
Signed-off-by: Liu Bo 
Reviewed-by: David Sterba 
Signed-off-by: David Sterba

Btrfs: delayed-refs: use rb_first_cached for href_root

2018-10-15T15:23:33+00:00

rb_first_cached() trades an extra pointer "leftmost" for doing the same
job as rb_first() but in O(1).

Functions manipulating href_root need to get the first entry, this
converts href_root to use rb_first_cached().

This patch is first in the sequenct of similar updates to other rbtrees
and this is analysis of the expected behaviour and improvements.

There's a common pattern:

while (node = rb_first) {
        entry = rb_entry(node)
        next = rb_next(node)
        rb_erase(node)
        cleanup(entry)
}

rb_first needs to traverse the tree up to logN depth, rb_erase can
completely reshuffle the tree. With the caching we'll skip the traversal
in rb_first.  That's a cached memory access vs looped pointer
dereference trade-off that IMHO has a clear winner.

Measurements show there's not much difference in a sample tree with
10000 nodes: 4.5s / rb_first and 4.8s / rb_first_cached. Real effects of
caching and pointer chasing are unpredictable though.

Further optimzations can be done to avoid the expensive rb_erase step.
In some cases it's ok to process the nodes in any order, so the tree can
be traversed in post-order, not rebalancing the children nodes and just
calling free. Care must be taken regarding the next node.

Tested-by: Holger Hoffstätte 
Signed-off-by: Liu Bo 
Reviewed-by: David Sterba 
[ update changelog from mail discussions ]
Signed-off-by: David Sterba

btrfs: Streamline memory allocation failure handling in btrfs_add_delayed_tree_ref

2018-08-06T11:12:39+00:00

Currently the function uses 2 goto labels to properly handle allocation
failures. This could be simplified by simply re-arranging the code so
that allocations are the in the beginning of the function. This allows
to use simple return statements. No functional changes.

Signed-off-by: Nikolay Borisov 
Reviewed-by: Su Yue 
Signed-off-by: David Sterba