From: Rik van Riel <riel@redhat.com>
To: Michel Lespinasse <walken@google.com>
Cc: Andrew Morton <akpm@linux-foundation.org>,
Hugh Dickins <hughd@google.com>,
Sasha Levin <levinsasha928@gmail.com>,
linux-kernel@vger.kernel.org, linux-mm@kvack.org
Subject: Re: [PATCH 1/3] mm: ensure safe rb_subtree_gap update when inserting new VMA
Date: Mon, 12 Nov 2012 08:39:59 -0500 [thread overview]
Message-ID: <50A0FC2F.9030207@redhat.com> (raw)
In-Reply-To: <1352721091-27022-2-git-send-email-walken@google.com>
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@oracle.com>
> Signed-off-by: Michel Lespinasse <walken@google.com>
Reviewed-by: Rik van Riel <riel@redhat.com>
--
All rights reversed
--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>
next prev parent reply other threads:[~2012-11-12 14:04 UTC|newest]
Thread overview: 10+ messages / expand[flat|nested] mbox.gz Atom feed top
2012-11-12 11:51 [PATCH 0/3] fix missing rb_subtree_gap updates on vma insert/erase Michel Lespinasse
2012-11-12 11:51 ` [PATCH 1/3] mm: ensure safe rb_subtree_gap update when inserting new VMA Michel Lespinasse
2012-11-12 13:39 ` Rik van Riel [this message]
2012-11-12 11:51 ` [PATCH 2/3] mm: ensure safe rb_subtree_gap update when removing VMA Michel Lespinasse
2012-11-12 13:40 ` Rik van Riel
2012-11-12 11:51 ` [PATCH 3/3] mm: debug code to verify rb_subtree_gap updates are safe Michel Lespinasse
2012-11-12 13:40 ` Rik van Riel
2012-11-12 20:54 ` [PATCH 0/3] fix missing rb_subtree_gap updates on vma insert/erase Sasha Levin
2012-11-27 1:16 ` Sasha Levin
2012-11-27 4:55 ` Michel Lespinasse
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=50A0FC2F.9030207@redhat.com \
--to=riel@redhat.com \
--cc=akpm@linux-foundation.org \
--cc=hughd@google.com \
--cc=levinsasha928@gmail.com \
--cc=linux-kernel@vger.kernel.org \
--cc=linux-mm@kvack.org \
--cc=walken@google.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).