Deadlock in ctree.c?

Deadlock in ctree.c?

[Jan Schmidt]

While debugging my tree mod log, after several hours of successful iteration I
finally reached a dead lock. I got stacks with btrfs_next_leaf and
push_leaf_left and looked into those.

If I'm not mistaken, there is at least one deadlock situation between those two
(I'm currently thinking about a second one). Basically, the problem is that
btrfs_next_leaf has a leaf locked and wants a lock for the next (right) leaf,
while push_leaf_left has a lock on another leaf and wants a lock for the
previous (left) leaf.

Assume that we've got two roots (subvolumes), both referencing the same two
leafs in two really small trees:

          r1     r2
          |  \ /  |
          |   X   |
          |  / \  |
          l1     l2

Commented pseudo code that is meant to summarize the relevant code from ctree.c:

Thread A in push_leaf_left, path is currently r2->l2:
	btrfs_assert_tree_locked(path->nodes[1]); /* r2 */
	/* also holds a lock at path->nodes[0] -> l2 */
	left = read_node_slot(root, path->nodes[1], slot - 1); /* l1 */
	btrfs_tree_lock(left);
-> blocking to get lock on l1

Thread B in btrfs_next_leaf, path is currently r1->l1:
        path->keep_locks = 1;
	btrfs_search_slot(...); /* locks r1, l1 */
        level = 1;
        while ...
                slot = path->slots[level] + 1;
                next = read_block_for_search(... slot ...);
                btrfs_tree_read_lock(next); /* l2 */
-> blocking to get lock on l2

Any ideas on this one? Preferably hints to why I'm wrong :-)

Thanks!
-Jan

Re: Deadlock in ctree.c?

[Josef Bacik]

On 06/22/2012 07:00 AM, Jan Schmidt wrote:
> While debugging my tree mod log, after several hours of successful iteration I
> finally reached a dead lock. I got stacks with btrfs_next_leaf and
> push_leaf_left and looked into those.
>
> If I'm not mistaken, there is at least one deadlock situation between those two
> (I'm currently thinking about a second one). Basically, the problem is that
> btrfs_next_leaf has a leaf locked and wants a lock for the next (right) leaf,
> while push_leaf_left has a lock on another leaf and wants a lock for the
> previous (left) leaf.
>
> Assume that we've got two roots (subvolumes), both referencing the same two
> leafs in two really small trees:
>
>            r1     r2
>            |  \ /  |
>            |   X   |
>            |  / \  |
>            l1     l2
>
> Commented pseudo code that is meant to summarize the relevant code from ctree.c:
>
> Thread A in push_leaf_left, path is currently r2->l2:
> 	btrfs_assert_tree_locked(path->nodes[1]); /* r2 */
> 	/* also holds a lock at path->nodes[0] -> l2 */
> 	left = read_node_slot(root, path->nodes[1], slot - 1); /* l1 */
> 	btrfs_tree_lock(left);
> -> blocking to get lock on l1
>
> Thread B in btrfs_next_leaf, path is currently r1->l1:
>          path->keep_locks = 1;
> 	btrfs_search_slot(...); /* locks r1, l1 */
>          level = 1;
>          while ...
>                  slot = path->slots[level] + 1;
>                  next = read_block_for_search(... slot ...);
>                  btrfs_tree_read_lock(next); /* l2 */
> -> blocking to get lock on l2

l2 shouldn't be locked anymore, if we're in push_leaf_left it's because 
we cow'ed l2 and are holding a lock on it, so really it has a lock on 
l2' and the btrfs_next_leaf is trying to get a lock on l2 which it 
should be free to do.  Thanks,

Josef

Re: Deadlock in ctree.c?

[Jan Schmidt]

On Fri, June 22, 2012 at 15:30 (+0200), Josef Bacik wrote:
> On 06/22/2012 07:00 AM, Jan Schmidt wrote:
>> While debugging my tree mod log, after several hours of successful iteration I
>> finally reached a dead lock. I got stacks with btrfs_next_leaf and
>> push_leaf_left and looked into those.
>>
>> If I'm not mistaken, there is at least one deadlock situation between those two
>> (I'm currently thinking about a second one). Basically, the problem is that
>> btrfs_next_leaf has a leaf locked and wants a lock for the next (right) leaf,
>> while push_leaf_left has a lock on another leaf and wants a lock for the
>> previous (left) leaf.
>>
>> Assume that we've got two roots (subvolumes), both referencing the same two
>> leafs in two really small trees:
>>
>>            r1     r2
>>            |  \ /  |
>>            |   X   |
>>            |  / \  |
>>            l1     l2
>>
>> Commented pseudo code that is meant to summarize the relevant code from ctree.c:
>>
>> Thread A in push_leaf_left, path is currently r2->l2:
>>     btrfs_assert_tree_locked(path->nodes[1]); /* r2 */
>>     /* also holds a lock at path->nodes[0] -> l2 */
>>     left = read_node_slot(root, path->nodes[1], slot - 1); /* l1 */
>>     btrfs_tree_lock(left);
>> -> blocking to get lock on l1
>>
>> Thread B in btrfs_next_leaf, path is currently r1->l1:
>>          path->keep_locks = 1;
>>     btrfs_search_slot(...); /* locks r1, l1 */
>>          level = 1;
>>          while ...
>>                  slot = path->slots[level] + 1;
>>                  next = read_block_for_search(... slot ...);
>>                  btrfs_tree_read_lock(next); /* l2 */
>> -> blocking to get lock on l2
> 
> l2 shouldn't be locked anymore, if we're in push_leaf_left it's because we
> cow'ed l2 and are holding a lock on it, so really it has a lock on l2' and the
> btrfs_next_leaf is trying to get a lock on l2 which it should be free to do. 

Each tree block is cowed only once per transaction, right? Lets assume l2 was
cowed before any of the above threads started, we should end up with a lock on
l2 even in push_leaf_left, because should_cow_block returns 0.

Thanks,
-Jan

Re: Deadlock in ctree.c?

[Josef Bacik]

On 06/22/2012 09:38 AM, Jan Schmidt wrote:
> On Fri, June 22, 2012 at 15:30 (+0200), Josef Bacik wrote:
>> On 06/22/2012 07:00 AM, Jan Schmidt wrote:
>>> While debugging my tree mod log, after several hours of successful iteration I
>>> finally reached a dead lock. I got stacks with btrfs_next_leaf and
>>> push_leaf_left and looked into those.
>>>
>>> If I'm not mistaken, there is at least one deadlock situation between those two
>>> (I'm currently thinking about a second one). Basically, the problem is that
>>> btrfs_next_leaf has a leaf locked and wants a lock for the next (right) leaf,
>>> while push_leaf_left has a lock on another leaf and wants a lock for the
>>> previous (left) leaf.
>>>
>>> Assume that we've got two roots (subvolumes), both referencing the same two
>>> leafs in two really small trees:
>>>
>>>             r1     r2
>>>             |  \ /  |
>>>             |   X   |
>>>             |  / \  |
>>>             l1     l2
>>>
>>> Commented pseudo code that is meant to summarize the relevant code from ctree.c:
>>>
>>> Thread A in push_leaf_left, path is currently r2->l2:
>>>      btrfs_assert_tree_locked(path->nodes[1]); /* r2 */
>>>      /* also holds a lock at path->nodes[0] -> l2 */
>>>      left = read_node_slot(root, path->nodes[1], slot - 1); /* l1 */
>>>      btrfs_tree_lock(left);
>>> -> blocking to get lock on l1
>>>
>>> Thread B in btrfs_next_leaf, path is currently r1->l1:
>>>           path->keep_locks = 1;
>>>      btrfs_search_slot(...); /* locks r1, l1 */
>>>           level = 1;
>>>           while ...
>>>                   slot = path->slots[level] + 1;
>>>                   next = read_block_for_search(... slot ...);
>>>                   btrfs_tree_read_lock(next); /* l2 */
>>> -> blocking to get lock on l2
>>
>> l2 shouldn't be locked anymore, if we're in push_leaf_left it's because we
>> cow'ed l2 and are holding a lock on it, so really it has a lock on l2' and the
>> btrfs_next_leaf is trying to get a lock on l2 which it should be free to do.
>
> Each tree block is cowed only once per transaction, right? Lets assume l2 was
> cowed before any of the above threads started, we should end up with a lock on
> l2 even in push_leaf_left, because should_cow_block returns 0.
>

Except you'd never get to l2 in the case that it had already been 
cow'ed.  Thanks,

Josef

Re: Deadlock in ctree.c?

[Jan Schmidt]

On Fri, June 22, 2012 at 16:23 (+0200), Josef Bacik wrote:
> On 06/22/2012 09:38 AM, Jan Schmidt wrote:
>> On Fri, June 22, 2012 at 15:30 (+0200), Josef Bacik wrote:
>>> l2 shouldn't be locked anymore, if we're in push_leaf_left it's because we
>>> cow'ed l2 and are holding a lock on it, so really it has a lock on l2' and the
>>> btrfs_next_leaf is trying to get a lock on l2 which it should be free to do.
>>
>> Each tree block is cowed only once per transaction, right? Lets assume l2 was
>> cowed before any of the above threads started, we should end up with a lock on
>> l2 even in push_leaf_left, because should_cow_block returns 0.
>>
> 
> Except you'd never get to l2 in the case that it had already been cow'ed.  Thanks,

Thank you :-) That's the missing bit.

-Jan