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 <enadol...@suse.com>
>> Signed-off-by: Jeff Mahoney <je...@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
signature.asc
Description: OpenPGP digital signature
