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
--
To unsubscribe from this list: send the line "unsubscribe linux-btrfs"
in
the body of a message to majordomo@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
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 l2l2 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 -- To unsubscribe from this list: send the line "unsubscribe linux-btrfs" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
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 -- To unsubscribe from this list: send the line "unsubscribe linux-btrfs" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
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 -- To unsubscribe from this list: send the line "unsubscribe linux-btrfs" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
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 -- To unsubscribe from this list: send the line "unsubscribe linux-btrfs" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html