Re: [PATCH 08/13] btrfs: convert prelimary reference tracking to use rbtrees

From: Jeff Mahoney <jeffm@suse.com>
To: Edmund Nadolski <enadolski@suse.com>, linux-btrfs@vger.kernel.org
Subject: Re: [PATCH 08/13] btrfs: convert prelimary reference tracking to use rbtrees
Date: Tue, 27 Jun 2017 16:09:34 -0400	[thread overview]
Message-ID: <e3778e1b-c1c1-03b9-5abe-e70cc2c19f6c@suse.com> (raw)
In-Reply-To: <be7f16ca-6a91-1e3b-cc5a-6e5454c6c3cc@suse.com>

[-- Attachment #1.1: Type: text/plain, Size: 3043 bytes --]

On 6/26/17 1:07 PM, Jeff Mahoney wrote:
> On 6/20/17 12:06 PM, Edmund Nadolski wrote:
>> 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 pair 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>
> [...]
> 
>> @@ -504,37 +665,22 @@ static int resolve_indirect_refs(struct btrfs_fs_info *fs_info,
>>  	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 rb_node *node = rb_first(&preftrees->indirect.root);
>> +
>> +	while (node) {
>> +		ref = rb_entry(node, struct prelim_ref, rbnode);
>> +		node = rb_next(&ref->rbnode);
>> +		if (WARN(ref->parent, "BUG: direct ref found in indirect tree"))
>> +			return -EINVAL;
>>  
>> -	list_for_each_entry(ref, head, list) {
>> -		if (ref->parent)
>> -			continue;
>>  		if (ref->key_for_search.type)
>>  			continue;
>>  		BUG_ON(!ref->wanted_disk_byte);
> 
> Hi Ed -
> 
> I missed this in earlier review, but this can't work.  We're modifying
> the ref in a way that the comparator will care about -- so the node
> would move in the tree.
> 
> It's not a fatal flaw and, in fact, leaves us an opening to fix a
> separate locking issue.

Ed and I discussed this offline.  It turns out that this is a code bug
but not a functional bug.  Once we hit add_missing_keys, we don't do any
more inserts or searches.  We only iterate over every node and remove
each as we go, so the tree order doesn't matter.  I'll post a fix shortly.

-Jeff

-- 
Jeff Mahoney
SUSE Labs

[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 819 bytes --]