Deadlock in ctree.c?

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

Quoted 29 lines · 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:

Quoted 8 lines

         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.

Quoted 39 lines · Josef Bacik

Quoted 37 lines · 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

Quoted 3 lines

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.

Quoted 5 lines · Jan Schmidt

Quoted 3 lines · Josef Bacik

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.

Quoted 4 lines

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,