btrfs: convert prelimary reference tracking to use rbtrees
authorEdmund Nadolski <enadolski@suse.com>
Wed, 12 Jul 2017 22:20:06 +0000 (16:20 -0600)
committerDavid Sterba <dsterba@suse.com>
Wed, 16 Aug 2017 14:11:55 +0000 (16:11 +0200)
commit86d5f994425252d8a40e2184c94a2682ae8ecfbf
tree4b6014e8e13e66a102745af0d9ef761f8a4e4105
parentf6954245d9e17902a66a1253d2a3afc05e335172
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 <enadolski@suse.com>
Signed-off-by: Jeff Mahoney <jeffm@suse.com>
Reviewed-by: Liu Bo <bo.li.liu@oracle.com>
Signed-off-by: David Sterba <dsterba@suse.com>
fs/btrfs/backref.c