On 11/12/2012 06:51 AM, Michel Lespinasse wrote:
Using the trinity fuzzer, Sasha Levin uncovered a case where rb_subtree_gap wasn't correctly updated. Digging into this, the root cause was that vma insertions and removals require both an rbtree insert or erase operation (which may trigger tree rotations), and an update of the next vma's gap (which does not change the tree topology, but may require iterating on the node's ancestors to propagate the update). The rbtree rotations caused the rb_subtree_gap values to be updated in some of the internal nodes, but without upstream propagation. Then the subsequent update on the next vma didn't iterate as high up the tree as it should have, as it stopped as soon as it hit one of the internal nodes that had been updated as part of a tree rotation. The fix is to impose that all rb_subtree_gap values must be up to date before any rbtree insertion or erase, with the possible exception that the node being erased doesn't need to have an up to date rb_subtree_gap. This change: during vma insertion, make sure to update the rb_subtree_gap values for both the current and next vmas prior to rebalancing the rbtree to account for the just-inserted vma. (Thanks to Sasha Levin for uncovering the problem and to Hugh Dickins for coming up with a simpler test case) Reported-by: Sasha Levin <sasha.levin@xxxxxxxxxx> Signed-off-by: Michel Lespinasse <walken@xxxxxxxxxx>
Reviewed-by: Rik van Riel <riel@xxxxxxxxxx> -- All rights reversed -- To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to majordomo@xxxxxxxxx. For more info on Linux MM, see: http://www.linux-mm.org/ . Don't email: <a href=mailto:"dont@xxxxxxxxx";> email@xxxxxxxxx </a>