From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from psmtp.com (na3sys010amx108.postini.com [74.125.245.108]) by kanga.kvack.org (Postfix) with SMTP id 27AA06B004D for ; Mon, 12 Nov 2012 06:51:46 -0500 (EST) Received: by mail-pa0-f41.google.com with SMTP id fa10so4654845pad.14 for ; Mon, 12 Nov 2012 03:51:45 -0800 (PST) From: Michel Lespinasse Subject: [PATCH 0/3] fix missing rb_subtree_gap updates on vma insert/erase Date: Mon, 12 Nov 2012 03:51:28 -0800 Message-Id: <1352721091-27022-1-git-send-email-walken@google.com> Sender: owner-linux-mm@kvack.org List-ID: To: Andrew Morton , Rik van Riel , Hugh Dickins , Sasha Levin Cc: linux-kernel@vger.kernel.org, linux-mm@kvack.org 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. These 3 patches apply on top of the stack I previously sent (or equally, on top of the last published mmotm). Michel Lespinasse (3): mm: ensure safe rb_subtree_gap update when inserting new VMA mm: ensure safe rb_subtree_gap update when removing VMA mm: debug code to verify rb_subtree_gap updates are safe mm/mmap.c | 121 +++++++++++++++++++++++++++++++++++++------------------------ 1 files changed, 73 insertions(+), 48 deletions(-) -- 1.7.7.3 -- 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: email@kvack.org From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from psmtp.com (na3sys010amx186.postini.com [74.125.245.186]) by kanga.kvack.org (Postfix) with SMTP id 6832B6B005D for ; Mon, 12 Nov 2012 06:51:47 -0500 (EST) Received: by mail-pb0-f41.google.com with SMTP id xa7so574764pbc.14 for ; Mon, 12 Nov 2012 03:51:46 -0800 (PST) From: Michel Lespinasse Subject: [PATCH 1/3] mm: ensure safe rb_subtree_gap update when inserting new VMA Date: Mon, 12 Nov 2012 03:51:29 -0800 Message-Id: <1352721091-27022-2-git-send-email-walken@google.com> In-Reply-To: <1352721091-27022-1-git-send-email-walken@google.com> References: <1352721091-27022-1-git-send-email-walken@google.com> Sender: owner-linux-mm@kvack.org List-ID: To: Andrew Morton , Rik van Riel , Hugh Dickins , Sasha Levin Cc: linux-kernel@vger.kernel.org, linux-mm@kvack.org 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 Signed-off-by: Michel Lespinasse --- mm/mmap.c | 27 +++++++++++++++------------ 1 files changed, 15 insertions(+), 12 deletions(-) diff --git a/mm/mmap.c b/mm/mmap.c index 619b280505fe..14859b999a9f 100644 --- a/mm/mmap.c +++ b/mm/mmap.c @@ -339,17 +339,7 @@ static void vma_gap_update(struct vm_area_struct *vma) static inline void vma_rb_insert(struct vm_area_struct *vma, struct rb_root *root) { - /* - * vma->vm_prev wasn't known when we followed the rbtree to find the - * correct insertion point for that vma. As a result, we could not - * update the vma vm_rb parents rb_subtree_gap values on the way down. - * So, we first insert the vma with a zero rb_subtree_gap value - * (to be consistent with what we did on the way down), and then - * immediately update the gap to the correct value. - */ - vma->rb_subtree_gap = 0; rb_insert_augmented(&vma->vm_rb, root, &vma_gap_callbacks); - vma_gap_update(vma); } static void vma_rb_erase(struct vm_area_struct *vma, struct rb_root *root) @@ -494,12 +484,25 @@ static int find_vma_links(struct mm_struct *mm, unsigned long addr, void __vma_link_rb(struct mm_struct *mm, struct vm_area_struct *vma, struct rb_node **rb_link, struct rb_node *rb_parent) { - rb_link_node(&vma->vm_rb, rb_parent, rb_link); - vma_rb_insert(vma, &mm->mm_rb); + /* Update tracking information for the gap following the new vma. */ if (vma->vm_next) vma_gap_update(vma->vm_next); else mm->highest_vm_end = vma->vm_end; + + /* + * vma->vm_prev wasn't known when we followed the rbtree to find the + * correct insertion point for that vma. As a result, we could not + * update the vma vm_rb parents rb_subtree_gap values on the way down. + * So, we first insert the vma with a zero rb_subtree_gap value + * (to be consistent with what we did on the way down), and then + * immediately update the gap to the correct value. Finally we + * rebalance the rbtree after all augmented values have been set. + */ + rb_link_node(&vma->vm_rb, rb_parent, rb_link); + vma->rb_subtree_gap = 0; + vma_gap_update(vma); + vma_rb_insert(vma, &mm->mm_rb); } static void __vma_link_file(struct vm_area_struct *vma) -- 1.7.7.3 -- 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: email@kvack.org From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from psmtp.com (na3sys010amx119.postini.com [74.125.245.119]) by kanga.kvack.org (Postfix) with SMTP id CB3346B0062 for ; Mon, 12 Nov 2012 06:51:48 -0500 (EST) Received: by mail-da0-f41.google.com with SMTP id i14so2953927dad.14 for ; Mon, 12 Nov 2012 03:51:48 -0800 (PST) From: Michel Lespinasse Subject: [PATCH 2/3] mm: ensure safe rb_subtree_gap update when removing VMA Date: Mon, 12 Nov 2012 03:51:30 -0800 Message-Id: <1352721091-27022-3-git-send-email-walken@google.com> In-Reply-To: <1352721091-27022-1-git-send-email-walken@google.com> References: <1352721091-27022-1-git-send-email-walken@google.com> Sender: owner-linux-mm@kvack.org List-ID: To: Andrew Morton , Rik van Riel , Hugh Dickins , Sasha Levin Cc: linux-kernel@vger.kernel.org, linux-mm@kvack.org 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 removal, remove VMA from the rbtree before we remove it from the linked list. The implication is the next vma's rb_subtree_gap value becomes stale when next->vm_prev is updated, and we want to make sure vma_rb_erase() runs before there are any such stale rb_subtree_gap values in the rbtree. (I don't know of a reproduceable test case for this particular issue) Signed-off-by: Michel Lespinasse --- mm/mmap.c | 6 +++--- 1 files changed, 3 insertions(+), 3 deletions(-) diff --git a/mm/mmap.c b/mm/mmap.c index 14859b999a9f..c60ac9fe2d7e 100644 --- a/mm/mmap.c +++ b/mm/mmap.c @@ -578,12 +578,12 @@ static inline void __vma_unlink(struct mm_struct *mm, struct vm_area_struct *vma, struct vm_area_struct *prev) { - struct vm_area_struct *next = vma->vm_next; + struct vm_area_struct *next; - prev->vm_next = next; + vma_rb_erase(vma, &mm->mm_rb); + prev->vm_next = next = vma->vm_next; if (next) next->vm_prev = prev; - vma_rb_erase(vma, &mm->mm_rb); if (mm->mmap_cache == vma) mm->mmap_cache = prev; } -- 1.7.7.3 -- 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: email@kvack.org From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from psmtp.com (na3sys010amx186.postini.com [74.125.245.186]) by kanga.kvack.org (Postfix) with SMTP id EE8E26B005D for ; Mon, 12 Nov 2012 06:51:49 -0500 (EST) Received: by mail-pb0-f41.google.com with SMTP id xa7so574764pbc.14 for ; Mon, 12 Nov 2012 03:51:49 -0800 (PST) From: Michel Lespinasse Subject: [PATCH 3/3] mm: debug code to verify rb_subtree_gap updates are safe Date: Mon, 12 Nov 2012 03:51:31 -0800 Message-Id: <1352721091-27022-4-git-send-email-walken@google.com> In-Reply-To: <1352721091-27022-1-git-send-email-walken@google.com> References: <1352721091-27022-1-git-send-email-walken@google.com> Sender: owner-linux-mm@kvack.org List-ID: To: Andrew Morton , Rik van Riel , Hugh Dickins , Sasha Levin Cc: linux-kernel@vger.kernel.org, linux-mm@kvack.org 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: introduce validate_mm_rb() to verify that the rbtree does not include any stale rb_subtree_gap values before node insertion or erase, so as to avoid the issue where a subsequent vma_gap_update() would fail to propagate the rb_subtree_gap updates as high up as necessary. Signed-off-by: Michel Lespinasse --- mm/mmap.c | 88 ++++++++++++++++++++++++++++++++++++++----------------------- 1 files changed, 55 insertions(+), 33 deletions(-) diff --git a/mm/mmap.c b/mm/mmap.c index c60ac9fe2d7e..408d330aca6c 100644 --- a/mm/mmap.c +++ b/mm/mmap.c @@ -319,39 +319,6 @@ static long vma_compute_subtree_gap(struct vm_area_struct *vma) return max; } -RB_DECLARE_CALLBACKS(static, vma_gap_callbacks, struct vm_area_struct, vm_rb, - unsigned long, rb_subtree_gap, vma_compute_subtree_gap) - -/* - * Update augmented rbtree rb_subtree_gap values after vma->vm_start or - * vma->vm_prev->vm_end values changed, without modifying the vma's position - * in the rbtree. - */ -static void vma_gap_update(struct vm_area_struct *vma) -{ - /* - * As it turns out, RB_DECLARE_CALLBACKS() already created a callback - * function that does exacltly what we want. - */ - vma_gap_callbacks_propagate(&vma->vm_rb, NULL); -} - -static inline void vma_rb_insert(struct vm_area_struct *vma, - struct rb_root *root) -{ - rb_insert_augmented(&vma->vm_rb, root, &vma_gap_callbacks); -} - -static void vma_rb_erase(struct vm_area_struct *vma, struct rb_root *root) -{ - /* - * Note rb_erase_augmented is a fairly large inline function, - * so make sure we instantiate it only once with our desired - * augmented rbtree callbacks. - */ - rb_erase_augmented(&vma->vm_rb, root, &vma_gap_callbacks); -} - #ifdef CONFIG_DEBUG_VM_RB static int browse_rb(struct rb_root *root) { @@ -385,6 +352,18 @@ static int browse_rb(struct rb_root *root) return bug ? -1 : i; } +static void validate_mm_rb(struct rb_root *root, struct vm_area_struct *ignore) +{ + struct rb_node *nd; + + for (nd = rb_first(root); nd; nd = rb_next(nd)) { + struct vm_area_struct *vma; + vma = rb_entry(nd, struct vm_area_struct, vm_rb); + BUG_ON(vma != ignore && + vma->rb_subtree_gap != vma_compute_subtree_gap(vma)); + } +} + void validate_mm(struct mm_struct *mm) { int bug = 0; @@ -412,9 +391,52 @@ void validate_mm(struct mm_struct *mm) BUG_ON(bug); } #else +#define validate_mm_rb(root, ignore) do { } while (0) #define validate_mm(mm) do { } while (0) #endif +RB_DECLARE_CALLBACKS(static, vma_gap_callbacks, struct vm_area_struct, vm_rb, + unsigned long, rb_subtree_gap, vma_compute_subtree_gap) + +/* + * Update augmented rbtree rb_subtree_gap values after vma->vm_start or + * vma->vm_prev->vm_end values changed, without modifying the vma's position + * in the rbtree. + */ +static void vma_gap_update(struct vm_area_struct *vma) +{ + /* + * As it turns out, RB_DECLARE_CALLBACKS() already created a callback + * function that does exacltly what we want. + */ + vma_gap_callbacks_propagate(&vma->vm_rb, NULL); +} + +static inline void vma_rb_insert(struct vm_area_struct *vma, + struct rb_root *root) +{ + /* All rb_subtree_gap values must be consistent prior to insertion */ + validate_mm_rb(root, NULL); + + rb_insert_augmented(&vma->vm_rb, root, &vma_gap_callbacks); +} + +static void vma_rb_erase(struct vm_area_struct *vma, struct rb_root *root) +{ + /* + * All rb_subtree_gap values must be consistent prior to erase, + * with the possible exception of the vma being erased. + */ + validate_mm_rb(root, vma); + + /* + * Note rb_erase_augmented is a fairly large inline function, + * so make sure we instantiate it only once with our desired + * augmented rbtree callbacks. + */ + rb_erase_augmented(&vma->vm_rb, root, &vma_gap_callbacks); +} + /* * vma has some anon_vma assigned, and is already inserted on that * anon_vma's interval trees. -- 1.7.7.3 -- 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: email@kvack.org From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from psmtp.com (na3sys010amx131.postini.com [74.125.245.131]) by kanga.kvack.org (Postfix) with SMTP id 704C26B004D for ; Mon, 12 Nov 2012 08:40:37 -0500 (EST) Message-ID: <50A0FC50.4060203@redhat.com> Date: Mon, 12 Nov 2012 08:40:32 -0500 From: Rik van Riel MIME-Version: 1.0 Subject: Re: [PATCH 3/3] mm: debug code to verify rb_subtree_gap updates are safe References: <1352721091-27022-1-git-send-email-walken@google.com> <1352721091-27022-4-git-send-email-walken@google.com> In-Reply-To: <1352721091-27022-4-git-send-email-walken@google.com> Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 7bit Sender: owner-linux-mm@kvack.org List-ID: To: Michel Lespinasse Cc: Andrew Morton , Hugh Dickins , Sasha Levin , linux-kernel@vger.kernel.org, linux-mm@kvack.org 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: introduce validate_mm_rb() to verify that the rbtree does > not include any stale rb_subtree_gap values before node insertion or > erase, so as to avoid the issue where a subsequent vma_gap_update() would > fail to propagate the rb_subtree_gap updates as high up as necessary. > > Signed-off-by: Michel Lespinasse Reviewed-by: Rik van Riel -- 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: email@kvack.org From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from psmtp.com (na3sys010amx197.postini.com [74.125.245.197]) by kanga.kvack.org (Postfix) with SMTP id D0BF76B005A for ; Mon, 12 Nov 2012 09:04:16 -0500 (EST) Message-ID: <50A0FC41.5020802@redhat.com> Date: Mon, 12 Nov 2012 08:40:17 -0500 From: Rik van Riel MIME-Version: 1.0 Subject: Re: [PATCH 2/3] mm: ensure safe rb_subtree_gap update when removing VMA References: <1352721091-27022-1-git-send-email-walken@google.com> <1352721091-27022-3-git-send-email-walken@google.com> In-Reply-To: <1352721091-27022-3-git-send-email-walken@google.com> Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 7bit Sender: owner-linux-mm@kvack.org List-ID: To: Michel Lespinasse Cc: Andrew Morton , Hugh Dickins , Sasha Levin , linux-kernel@vger.kernel.org, linux-mm@kvack.org 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 removal, remove VMA from the rbtree before we > remove it from the linked list. The implication is the next vma's > rb_subtree_gap value becomes stale when next->vm_prev is updated, > and we want to make sure vma_rb_erase() runs before there are any > such stale rb_subtree_gap values in the rbtree. > > (I don't know of a reproduceable test case for this particular issue) > > Signed-off-by: Michel Lespinasse Reviewed-by: Rik van Riel -- 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: email@kvack.org From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from psmtp.com (na3sys010amx192.postini.com [74.125.245.192]) by kanga.kvack.org (Postfix) with SMTP id C2EEB6B004D for ; Mon, 12 Nov 2012 09:04:16 -0500 (EST) Message-ID: <50A0FC2F.9030207@redhat.com> Date: Mon, 12 Nov 2012 08:39:59 -0500 From: Rik van Riel MIME-Version: 1.0 Subject: Re: [PATCH 1/3] mm: ensure safe rb_subtree_gap update when inserting new VMA References: <1352721091-27022-1-git-send-email-walken@google.com> <1352721091-27022-2-git-send-email-walken@google.com> In-Reply-To: <1352721091-27022-2-git-send-email-walken@google.com> Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 7bit Sender: owner-linux-mm@kvack.org List-ID: To: Michel Lespinasse Cc: Andrew Morton , Hugh Dickins , Sasha Levin , linux-kernel@vger.kernel.org, linux-mm@kvack.org 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 > Signed-off-by: Michel Lespinasse Reviewed-by: Rik van Riel -- 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: email@kvack.org From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from psmtp.com (na3sys010amx120.postini.com [74.125.245.120]) by kanga.kvack.org (Postfix) with SMTP id CE17C6B002B for ; Mon, 12 Nov 2012 15:55:04 -0500 (EST) Received: by mail-vb0-f41.google.com with SMTP id v13so101347vbk.14 for ; Mon, 12 Nov 2012 12:55:03 -0800 (PST) Message-ID: <50A16212.8090507@gmail.com> Date: Mon, 12 Nov 2012 15:54:42 -0500 From: Sasha Levin MIME-Version: 1.0 Subject: Re: [PATCH 0/3] fix missing rb_subtree_gap updates on vma insert/erase References: <1352721091-27022-1-git-send-email-walken@google.com> In-Reply-To: <1352721091-27022-1-git-send-email-walken@google.com> Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 7bit Sender: owner-linux-mm@kvack.org List-ID: To: Michel Lespinasse Cc: Andrew Morton , Rik van Riel , Hugh Dickins , linux-kernel@vger.kernel.org, linux-mm@kvack.org 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. > > These 3 patches apply on top of the stack I previously sent (or equally, > on top of the last published mmotm). > > Michel Lespinasse (3): > mm: ensure safe rb_subtree_gap update when inserting new VMA > mm: ensure safe rb_subtree_gap update when removing VMA > mm: debug code to verify rb_subtree_gap updates are safe > > mm/mmap.c | 121 +++++++++++++++++++++++++++++++++++++------------------------ > 1 files changed, 73 insertions(+), 48 deletions(-) > Looking good: old warnings gone, no new warnings. Thanks, Sasha -- 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: email@kvack.org From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from psmtp.com (na3sys010amx103.postini.com [74.125.245.103]) by kanga.kvack.org (Postfix) with SMTP id 1C8046B0070 for ; Mon, 26 Nov 2012 20:16:49 -0500 (EST) Received: by mail-qc0-f169.google.com with SMTP id t2so10630884qcq.14 for ; Mon, 26 Nov 2012 17:16:48 -0800 (PST) Message-ID: <50B4145C.3010406@gmail.com> Date: Mon, 26 Nov 2012 20:16:12 -0500 From: Sasha Levin MIME-Version: 1.0 Subject: Re: [PATCH 0/3] fix missing rb_subtree_gap updates on vma insert/erase References: <1352721091-27022-1-git-send-email-walken@google.com> <50A16212.8090507@gmail.com> In-Reply-To: <50A16212.8090507@gmail.com> Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 7bit Sender: owner-linux-mm@kvack.org List-ID: To: Michel Lespinasse Cc: Andrew Morton , Rik van Riel , Hugh Dickins , linux-kernel@vger.kernel.org, linux-mm@kvack.org On 11/12/2012 03:54 PM, Sasha Levin wrote: > 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. >> >> These 3 patches apply on top of the stack I previously sent (or equally, >> on top of the last published mmotm). >> >> Michel Lespinasse (3): >> mm: ensure safe rb_subtree_gap update when inserting new VMA >> mm: ensure safe rb_subtree_gap update when removing VMA >> mm: debug code to verify rb_subtree_gap updates are safe >> >> mm/mmap.c | 121 +++++++++++++++++++++++++++++++++++++------------------------ >> 1 files changed, 73 insertions(+), 48 deletions(-) >> > > Looking good: old warnings gone, no new warnings. I've built today's -next, and got the following BUG pretty quickly (2-3 hours): [ 1556.479284] BUG: unable to handle kernel paging request at 0000000000412000 [ 1556.480036] IP: [] validate_mm+0x34/0x130 [ 1556.480036] PGD 31739067 PUD 4fbc4067 PMD 1c936067 PTE 0 [ 1556.480036] Oops: 0000 [#1] PREEMPT SMP DEBUG_PAGEALLOC [ 1556.480036] Dumping ftrace buffer: [ 1556.480036] (ftrace buffer empty) [ 1556.480036] CPU 0 [ 1556.480036] Pid: 10274, comm: trinity-child29 Tainted: G W 3.7.0-rc6-next-20121126-sasha-00015-gb04382b-dirty #201 [ 1556.480036] RIP: 0010:[] [] validate_mm+0x34/0x130 [ 1556.480036] RSP: 0018:ffff88004fbc7d08 EFLAGS: 00010206 [ 1556.480036] RAX: 0000000000412000 RBX: 0000000000000000 RCX: 0000000000000000 [ 1556.512120] RDX: 0000000000000000 RSI: ffff88001c1a6008 RDI: ffff88001c1a6000 [ 1556.512120] RBP: ffff88004fbc7d38 R08: ffff8800371e7808 R09: ffff88004fb56cf0 [ 1556.512120] R10: 0000000000000001 R11: 0000000000001000 R12: ffff88001c1a6000 [ 1556.512120] R13: ffff8800371e7b00 R14: 0000000000000000 R15: ffff88001c1a6000 [ 1556.512120] FS: 00007f4e0f8e3700(0000) GS:ffff8800bfc00000(0000) knlGS:0000000000000000 [ 1556.512120] CS: 0010 DS: 0000 ES: 0000 CR0: 0000000080050033 [ 1556.512120] CR2: 0000000000412000 CR3: 000000002faec000 CR4: 00000000000406f0 [ 1556.512120] DR0: 0000000000000000 DR1: 0000000000000000 DR2: 0000000000000000 [ 1556.512120] DR3: 0000000000000000 DR6: 00000000ffff0ff0 DR7: 0000000000000400 [ 1556.512120] Process trinity-child29 (pid: 10274, threadinfo ffff88004fbc6000, task ffff88004fbb0000) [ 1556.512120] Stack: [ 1556.512120] ffff8800bf80aa80 ffff88001c1a6000 ffff88004fb56cf0 ffff8800371e7818 [ 1556.512120] ffff8800371e7808 ffff88001c1a6000 ffff88004fbc7d88 ffffffff8123843c [ 1556.512120] 0000000000000001 ffff88004fb56da8 ffff880000000000 ffff8800371e7818 [ 1556.512120] Call Trace: [ 1556.512120] [] vma_link+0xcc/0xf0 [ 1556.512120] [] mmap_region+0x40c/0x5a0 [ 1556.512120] [] do_mmap_pgoff+0x2ab/0x310 [ 1556.512120] [] ? vm_mmap_pgoff+0x6c/0xb0 [ 1556.512120] [] vm_mmap_pgoff+0x84/0xb0 [ 1556.512120] [] sys_mmap_pgoff+0x193/0x1a0 [ 1556.512120] [] ? trace_hardirqs_on_caller+0x118/0x140 [ 1556.512120] [] sys_mmap+0x1d/0x20 [ 1556.512120] [] tracesys+0xe1/0xe6 [ 1556.512120] Code: 31 f6 41 55 41 54 49 89 fc 53 31 db 48 83 ec 08 4c 8b 2f 4d 85 ed 74 75 0f 1f 80 00 00 00 00 49 8b 85 88 00 00 00 48 85 c0 74 0e <48> 8b 38 31 f6 48 83 c7 08 e8 0e bc a4 02 49 8b 45 78 4d 8d 7d [ 1556.512120] RIP [] validate_mm+0x34/0x130 [ 1556.512120] RSP [ 1556.512120] CR2: 0000000000412000 [ 1557.729958] ---[ end trace d2a29e98cc9e2568 ]--- The bit that's failing is: struct vm_area_struct *vma = mm->mmap; // mm->mmap = 0x412000 while (vma) { struct anon_vma_chain *avc; vma_lock_anon_vma(vma); // BOOM! Thanks, Sasha -- 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: email@kvack.org From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from psmtp.com (na3sys010amx163.postini.com [74.125.245.163]) by kanga.kvack.org (Postfix) with SMTP id D60046B004D for ; Mon, 26 Nov 2012 23:55:22 -0500 (EST) Received: by mail-vc0-f169.google.com with SMTP id gb30so6806642vcb.14 for ; Mon, 26 Nov 2012 20:55:21 -0800 (PST) MIME-Version: 1.0 In-Reply-To: <50B4145C.3010406@gmail.com> References: <1352721091-27022-1-git-send-email-walken@google.com> <50A16212.8090507@gmail.com> <50B4145C.3010406@gmail.com> Date: Mon, 26 Nov 2012 20:55:21 -0800 Message-ID: Subject: Re: [PATCH 0/3] fix missing rb_subtree_gap updates on vma insert/erase From: Michel Lespinasse Content-Type: text/plain; charset=ISO-8859-1 Sender: owner-linux-mm@kvack.org List-ID: To: Sasha Levin Cc: Andrew Morton , Rik van Riel , Hugh Dickins , linux-kernel@vger.kernel.org, linux-mm@kvack.org On Mon, Nov 26, 2012 at 5:16 PM, Sasha Levin wrote: > I've built today's -next, and got the following BUG pretty quickly (2-3 hours): > > [ 1556.479284] BUG: unable to handle kernel paging request at 0000000000412000 > [ 1556.480036] IP: [] validate_mm+0x34/0x130 > [ 1556.480036] PGD 31739067 PUD 4fbc4067 PMD 1c936067 PTE 0 > [ 1556.480036] Oops: 0000 [#1] PREEMPT SMP DEBUG_PAGEALLOC > [ 1556.480036] Dumping ftrace buffer: > [ 1556.480036] (ftrace buffer empty) > [ 1556.480036] CPU 0 > [ 1556.480036] Pid: 10274, comm: trinity-child29 Tainted: G W 3.7.0-rc6-next-20121126-sasha-00015-gb04382b-dirty #201 > [ 1556.480036] RIP: 0010:[] [] validate_mm+0x34/0x130 > [ 1556.480036] RSP: 0018:ffff88004fbc7d08 EFLAGS: 00010206 > [ 1556.480036] RAX: 0000000000412000 RBX: 0000000000000000 RCX: 0000000000000000 > [ 1556.512120] RDX: 0000000000000000 RSI: ffff88001c1a6008 RDI: ffff88001c1a6000 > [ 1556.512120] RBP: ffff88004fbc7d38 R08: ffff8800371e7808 R09: ffff88004fb56cf0 > [ 1556.512120] R10: 0000000000000001 R11: 0000000000001000 R12: ffff88001c1a6000 > [ 1556.512120] R13: ffff8800371e7b00 R14: 0000000000000000 R15: ffff88001c1a6000 > [ 1556.512120] FS: 00007f4e0f8e3700(0000) GS:ffff8800bfc00000(0000) knlGS:0000000000000000 > [ 1556.512120] CS: 0010 DS: 0000 ES: 0000 CR0: 0000000080050033 > [ 1556.512120] CR2: 0000000000412000 CR3: 000000002faec000 CR4: 00000000000406f0 > [ 1556.512120] DR0: 0000000000000000 DR1: 0000000000000000 DR2: 0000000000000000 > [ 1556.512120] DR3: 0000000000000000 DR6: 00000000ffff0ff0 DR7: 0000000000000400 > [ 1556.512120] Process trinity-child29 (pid: 10274, threadinfo ffff88004fbc6000, task ffff88004fbb0000) > [ 1556.512120] Stack: > [ 1556.512120] ffff8800bf80aa80 ffff88001c1a6000 ffff88004fb56cf0 ffff8800371e7818 > [ 1556.512120] ffff8800371e7808 ffff88001c1a6000 ffff88004fbc7d88 ffffffff8123843c > [ 1556.512120] 0000000000000001 ffff88004fb56da8 ffff880000000000 ffff8800371e7818 > [ 1556.512120] Call Trace: > [ 1556.512120] [] vma_link+0xcc/0xf0 > [ 1556.512120] [] mmap_region+0x40c/0x5a0 > [ 1556.512120] [] do_mmap_pgoff+0x2ab/0x310 > [ 1556.512120] [] ? vm_mmap_pgoff+0x6c/0xb0 > [ 1556.512120] [] vm_mmap_pgoff+0x84/0xb0 > [ 1556.512120] [] sys_mmap_pgoff+0x193/0x1a0 > [ 1556.512120] [] ? trace_hardirqs_on_caller+0x118/0x140 > [ 1556.512120] [] sys_mmap+0x1d/0x20 > [ 1556.512120] [] tracesys+0xe1/0xe6 > [ 1556.512120] Code: 31 f6 41 55 41 54 49 89 fc 53 31 db 48 83 ec 08 4c 8b 2f 4d 85 ed 74 75 0f 1f 80 00 00 00 00 49 8b 85 88 00 00 > 00 48 85 c0 74 0e <48> 8b 38 31 f6 48 83 c7 08 e8 0e bc a4 02 49 8b 45 78 4d 8d 7d > [ 1556.512120] RIP [] validate_mm+0x34/0x130 > [ 1556.512120] RSP > [ 1556.512120] CR2: 0000000000412000 > [ 1557.729958] ---[ end trace d2a29e98cc9e2568 ]--- > > The bit that's failing is: > > struct vm_area_struct *vma = mm->mmap; // mm->mmap = 0x412000 > while (vma) { > struct anon_vma_chain *avc; > vma_lock_anon_vma(vma); // BOOM! > > > Thanks, > Sasha Thanks for the report. I believe we actually have mm->mmap = ffff8800371e7b00 (r13); That first vma has its anon_vma field pointing to 0000000000412000 (rax) and we fault while trying to read anon_vma->root. I don't see what could cause vma->anon_vma to be an invalid non-null value. This looks very much like there might be some kind of memory corruption occuring, but I can't tell where it would come from. Going back into your previous reports, we also never really identified the root cause of your two reports at the start of the thread with subject: "mm: NULL ptr deref in anon_vma_interval_tree_verify" (on Oct 18th and Oct 25th). At some point we thought that taking the anon_vma lock in validate_mm would prevent a race and fix the issue, but further inspection convinced us that this shouldn't be necessary - so, in the end, we still don't know what caused us to crash in these two cases either (and, I was tempted to suggest memory corruption at the time too). So, I'm not sure what to do. One thing to keep in mind is that CONFIG_DEBUG_VM_RB was only recently introduced (between v3.6 and v3.7-rc1); before that the code existed only as an #ifdef in mm/mmap.c. So, it might help if you could run your trinity test on these few kernel versions: - first, on v3.6, after editing mm/mmap.c to replace #undef DEBUG_MM_RB with #define DEBUG_MM_RB; (if this fails here, then what we have is a latent bug that CONFIG_DEBUG_VM_RB just happened to reveal) - then, on v3.7-rc1 with no further changes (if this fails here, then the issue is likely with my rbtree intervals stuff that made it into v3.7-rc1) - finally, on the akpm-base branch in linux-next tree (if this fails here, then the issue may be some corruption caused by one of the trees other than -mm) Sorry to request this; I'm really not sure what else to try at this point :/ -- Michel "Walken" Lespinasse A program is never fully debugged until the last user dies. -- 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: email@kvack.org From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1753246Ab2KLLvx (ORCPT ); Mon, 12 Nov 2012 06:51:53 -0500 Received: from mail-pb0-f46.google.com ([209.85.160.46]:54766 "EHLO mail-pb0-f46.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1750888Ab2KLLvr (ORCPT ); Mon, 12 Nov 2012 06:51:47 -0500 From: Michel Lespinasse To: Andrew Morton , Rik van Riel , Hugh Dickins , Sasha Levin Cc: linux-kernel@vger.kernel.org, linux-mm@kvack.org Subject: [PATCH 1/3] mm: ensure safe rb_subtree_gap update when inserting new VMA Date: Mon, 12 Nov 2012 03:51:29 -0800 Message-Id: <1352721091-27022-2-git-send-email-walken@google.com> X-Mailer: git-send-email 1.7.7.3 In-Reply-To: <1352721091-27022-1-git-send-email-walken@google.com> References: <1352721091-27022-1-git-send-email-walken@google.com> Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org 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 Signed-off-by: Michel Lespinasse --- mm/mmap.c | 27 +++++++++++++++------------ 1 files changed, 15 insertions(+), 12 deletions(-) diff --git a/mm/mmap.c b/mm/mmap.c index 619b280505fe..14859b999a9f 100644 --- a/mm/mmap.c +++ b/mm/mmap.c @@ -339,17 +339,7 @@ static void vma_gap_update(struct vm_area_struct *vma) static inline void vma_rb_insert(struct vm_area_struct *vma, struct rb_root *root) { - /* - * vma->vm_prev wasn't known when we followed the rbtree to find the - * correct insertion point for that vma. As a result, we could not - * update the vma vm_rb parents rb_subtree_gap values on the way down. - * So, we first insert the vma with a zero rb_subtree_gap value - * (to be consistent with what we did on the way down), and then - * immediately update the gap to the correct value. - */ - vma->rb_subtree_gap = 0; rb_insert_augmented(&vma->vm_rb, root, &vma_gap_callbacks); - vma_gap_update(vma); } static void vma_rb_erase(struct vm_area_struct *vma, struct rb_root *root) @@ -494,12 +484,25 @@ static int find_vma_links(struct mm_struct *mm, unsigned long addr, void __vma_link_rb(struct mm_struct *mm, struct vm_area_struct *vma, struct rb_node **rb_link, struct rb_node *rb_parent) { - rb_link_node(&vma->vm_rb, rb_parent, rb_link); - vma_rb_insert(vma, &mm->mm_rb); + /* Update tracking information for the gap following the new vma. */ if (vma->vm_next) vma_gap_update(vma->vm_next); else mm->highest_vm_end = vma->vm_end; + + /* + * vma->vm_prev wasn't known when we followed the rbtree to find the + * correct insertion point for that vma. As a result, we could not + * update the vma vm_rb parents rb_subtree_gap values on the way down. + * So, we first insert the vma with a zero rb_subtree_gap value + * (to be consistent with what we did on the way down), and then + * immediately update the gap to the correct value. Finally we + * rebalance the rbtree after all augmented values have been set. + */ + rb_link_node(&vma->vm_rb, rb_parent, rb_link); + vma->rb_subtree_gap = 0; + vma_gap_update(vma); + vma_rb_insert(vma, &mm->mm_rb); } static void __vma_link_file(struct vm_area_struct *vma) -- 1.7.7.3 From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1753225Ab2KLLvv (ORCPT ); Mon, 12 Nov 2012 06:51:51 -0500 Received: from mail-da0-f46.google.com ([209.85.210.46]:50803 "EHLO mail-da0-f46.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1751602Ab2KLLvp (ORCPT ); Mon, 12 Nov 2012 06:51:45 -0500 From: Michel Lespinasse To: Andrew Morton , Rik van Riel , Hugh Dickins , Sasha Levin Cc: linux-kernel@vger.kernel.org, linux-mm@kvack.org Subject: [PATCH 0/3] fix missing rb_subtree_gap updates on vma insert/erase Date: Mon, 12 Nov 2012 03:51:28 -0800 Message-Id: <1352721091-27022-1-git-send-email-walken@google.com> X-Mailer: git-send-email 1.7.7.3 Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org 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. These 3 patches apply on top of the stack I previously sent (or equally, on top of the last published mmotm). Michel Lespinasse (3): mm: ensure safe rb_subtree_gap update when inserting new VMA mm: ensure safe rb_subtree_gap update when removing VMA mm: debug code to verify rb_subtree_gap updates are safe mm/mmap.c | 121 +++++++++++++++++++++++++++++++++++++------------------------ 1 files changed, 73 insertions(+), 48 deletions(-) -- 1.7.7.3 From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1752600Ab2KLLyo (ORCPT ); Mon, 12 Nov 2012 06:54:44 -0500 Received: from mail-pa0-f46.google.com ([209.85.220.46]:63980 "EHLO mail-pa0-f46.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1753194Ab2KLLvu (ORCPT ); Mon, 12 Nov 2012 06:51:50 -0500 From: Michel Lespinasse To: Andrew Morton , Rik van Riel , Hugh Dickins , Sasha Levin Cc: linux-kernel@vger.kernel.org, linux-mm@kvack.org Subject: [PATCH 3/3] mm: debug code to verify rb_subtree_gap updates are safe Date: Mon, 12 Nov 2012 03:51:31 -0800 Message-Id: <1352721091-27022-4-git-send-email-walken@google.com> X-Mailer: git-send-email 1.7.7.3 In-Reply-To: <1352721091-27022-1-git-send-email-walken@google.com> References: <1352721091-27022-1-git-send-email-walken@google.com> Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org 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: introduce validate_mm_rb() to verify that the rbtree does not include any stale rb_subtree_gap values before node insertion or erase, so as to avoid the issue where a subsequent vma_gap_update() would fail to propagate the rb_subtree_gap updates as high up as necessary. Signed-off-by: Michel Lespinasse --- mm/mmap.c | 88 ++++++++++++++++++++++++++++++++++++++----------------------- 1 files changed, 55 insertions(+), 33 deletions(-) diff --git a/mm/mmap.c b/mm/mmap.c index c60ac9fe2d7e..408d330aca6c 100644 --- a/mm/mmap.c +++ b/mm/mmap.c @@ -319,39 +319,6 @@ static long vma_compute_subtree_gap(struct vm_area_struct *vma) return max; } -RB_DECLARE_CALLBACKS(static, vma_gap_callbacks, struct vm_area_struct, vm_rb, - unsigned long, rb_subtree_gap, vma_compute_subtree_gap) - -/* - * Update augmented rbtree rb_subtree_gap values after vma->vm_start or - * vma->vm_prev->vm_end values changed, without modifying the vma's position - * in the rbtree. - */ -static void vma_gap_update(struct vm_area_struct *vma) -{ - /* - * As it turns out, RB_DECLARE_CALLBACKS() already created a callback - * function that does exacltly what we want. - */ - vma_gap_callbacks_propagate(&vma->vm_rb, NULL); -} - -static inline void vma_rb_insert(struct vm_area_struct *vma, - struct rb_root *root) -{ - rb_insert_augmented(&vma->vm_rb, root, &vma_gap_callbacks); -} - -static void vma_rb_erase(struct vm_area_struct *vma, struct rb_root *root) -{ - /* - * Note rb_erase_augmented is a fairly large inline function, - * so make sure we instantiate it only once with our desired - * augmented rbtree callbacks. - */ - rb_erase_augmented(&vma->vm_rb, root, &vma_gap_callbacks); -} - #ifdef CONFIG_DEBUG_VM_RB static int browse_rb(struct rb_root *root) { @@ -385,6 +352,18 @@ static int browse_rb(struct rb_root *root) return bug ? -1 : i; } +static void validate_mm_rb(struct rb_root *root, struct vm_area_struct *ignore) +{ + struct rb_node *nd; + + for (nd = rb_first(root); nd; nd = rb_next(nd)) { + struct vm_area_struct *vma; + vma = rb_entry(nd, struct vm_area_struct, vm_rb); + BUG_ON(vma != ignore && + vma->rb_subtree_gap != vma_compute_subtree_gap(vma)); + } +} + void validate_mm(struct mm_struct *mm) { int bug = 0; @@ -412,9 +391,52 @@ void validate_mm(struct mm_struct *mm) BUG_ON(bug); } #else +#define validate_mm_rb(root, ignore) do { } while (0) #define validate_mm(mm) do { } while (0) #endif +RB_DECLARE_CALLBACKS(static, vma_gap_callbacks, struct vm_area_struct, vm_rb, + unsigned long, rb_subtree_gap, vma_compute_subtree_gap) + +/* + * Update augmented rbtree rb_subtree_gap values after vma->vm_start or + * vma->vm_prev->vm_end values changed, without modifying the vma's position + * in the rbtree. + */ +static void vma_gap_update(struct vm_area_struct *vma) +{ + /* + * As it turns out, RB_DECLARE_CALLBACKS() already created a callback + * function that does exacltly what we want. + */ + vma_gap_callbacks_propagate(&vma->vm_rb, NULL); +} + +static inline void vma_rb_insert(struct vm_area_struct *vma, + struct rb_root *root) +{ + /* All rb_subtree_gap values must be consistent prior to insertion */ + validate_mm_rb(root, NULL); + + rb_insert_augmented(&vma->vm_rb, root, &vma_gap_callbacks); +} + +static void vma_rb_erase(struct vm_area_struct *vma, struct rb_root *root) +{ + /* + * All rb_subtree_gap values must be consistent prior to erase, + * with the possible exception of the vma being erased. + */ + validate_mm_rb(root, vma); + + /* + * Note rb_erase_augmented is a fairly large inline function, + * so make sure we instantiate it only once with our desired + * augmented rbtree callbacks. + */ + rb_erase_augmented(&vma->vm_rb, root, &vma_gap_callbacks); +} + /* * vma has some anon_vma assigned, and is already inserted on that * anon_vma's interval trees. -- 1.7.7.3 From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1752999Ab2KLLzI (ORCPT ); Mon, 12 Nov 2012 06:55:08 -0500 Received: from mail-pb0-f46.google.com ([209.85.160.46]:43575 "EHLO mail-pb0-f46.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1752021Ab2KLLvs (ORCPT ); Mon, 12 Nov 2012 06:51:48 -0500 From: Michel Lespinasse To: Andrew Morton , Rik van Riel , Hugh Dickins , Sasha Levin Cc: linux-kernel@vger.kernel.org, linux-mm@kvack.org Subject: [PATCH 2/3] mm: ensure safe rb_subtree_gap update when removing VMA Date: Mon, 12 Nov 2012 03:51:30 -0800 Message-Id: <1352721091-27022-3-git-send-email-walken@google.com> X-Mailer: git-send-email 1.7.7.3 In-Reply-To: <1352721091-27022-1-git-send-email-walken@google.com> References: <1352721091-27022-1-git-send-email-walken@google.com> Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org 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 removal, remove VMA from the rbtree before we remove it from the linked list. The implication is the next vma's rb_subtree_gap value becomes stale when next->vm_prev is updated, and we want to make sure vma_rb_erase() runs before there are any such stale rb_subtree_gap values in the rbtree. (I don't know of a reproduceable test case for this particular issue) Signed-off-by: Michel Lespinasse --- mm/mmap.c | 6 +++--- 1 files changed, 3 insertions(+), 3 deletions(-) diff --git a/mm/mmap.c b/mm/mmap.c index 14859b999a9f..c60ac9fe2d7e 100644 --- a/mm/mmap.c +++ b/mm/mmap.c @@ -578,12 +578,12 @@ static inline void __vma_unlink(struct mm_struct *mm, struct vm_area_struct *vma, struct vm_area_struct *prev) { - struct vm_area_struct *next = vma->vm_next; + struct vm_area_struct *next; - prev->vm_next = next; + vma_rb_erase(vma, &mm->mm_rb); + prev->vm_next = next = vma->vm_next; if (next) next->vm_prev = prev; - vma_rb_erase(vma, &mm->mm_rb); if (mm->mmap_cache == vma) mm->mmap_cache = prev; } -- 1.7.7.3 From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1752685Ab2KLNkj (ORCPT ); Mon, 12 Nov 2012 08:40:39 -0500 Received: from mx1.redhat.com ([209.132.183.28]:34585 "EHLO mx1.redhat.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1751508Ab2KLNki (ORCPT ); Mon, 12 Nov 2012 08:40:38 -0500 Message-ID: <50A0FC50.4060203@redhat.com> Date: Mon, 12 Nov 2012 08:40:32 -0500 From: Rik van Riel User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:15.0) Gecko/20120827 Thunderbird/15.0 MIME-Version: 1.0 To: Michel Lespinasse CC: Andrew Morton , Hugh Dickins , Sasha Levin , linux-kernel@vger.kernel.org, linux-mm@kvack.org Subject: Re: [PATCH 3/3] mm: debug code to verify rb_subtree_gap updates are safe References: <1352721091-27022-1-git-send-email-walken@google.com> <1352721091-27022-4-git-send-email-walken@google.com> In-Reply-To: <1352721091-27022-4-git-send-email-walken@google.com> Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 7bit Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org 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: introduce validate_mm_rb() to verify that the rbtree does > not include any stale rb_subtree_gap values before node insertion or > erase, so as to avoid the issue where a subsequent vma_gap_update() would > fail to propagate the rb_subtree_gap updates as high up as necessary. > > Signed-off-by: Michel Lespinasse Reviewed-by: Rik van Riel -- All rights reversed From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1753332Ab2KLOEU (ORCPT ); Mon, 12 Nov 2012 09:04:20 -0500 Received: from mx1.redhat.com ([209.132.183.28]:55496 "EHLO mx1.redhat.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1752039Ab2KLOES (ORCPT ); Mon, 12 Nov 2012 09:04:18 -0500 Message-ID: <50A0FC41.5020802@redhat.com> Date: Mon, 12 Nov 2012 08:40:17 -0500 From: Rik van Riel User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:15.0) Gecko/20120827 Thunderbird/15.0 MIME-Version: 1.0 To: Michel Lespinasse CC: Andrew Morton , Hugh Dickins , Sasha Levin , linux-kernel@vger.kernel.org, linux-mm@kvack.org Subject: Re: [PATCH 2/3] mm: ensure safe rb_subtree_gap update when removing VMA References: <1352721091-27022-1-git-send-email-walken@google.com> <1352721091-27022-3-git-send-email-walken@google.com> In-Reply-To: <1352721091-27022-3-git-send-email-walken@google.com> Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 7bit Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org 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 removal, remove VMA from the rbtree before we > remove it from the linked list. The implication is the next vma's > rb_subtree_gap value becomes stale when next->vm_prev is updated, > and we want to make sure vma_rb_erase() runs before there are any > such stale rb_subtree_gap values in the rbtree. > > (I don't know of a reproduceable test case for this particular issue) > > Signed-off-by: Michel Lespinasse Reviewed-by: Rik van Riel -- All rights reversed From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1753252Ab2KLOET (ORCPT ); Mon, 12 Nov 2012 09:04:19 -0500 Received: from mx1.redhat.com ([209.132.183.28]:10028 "EHLO mx1.redhat.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1751628Ab2KLOES (ORCPT ); Mon, 12 Nov 2012 09:04:18 -0500 Message-ID: <50A0FC2F.9030207@redhat.com> Date: Mon, 12 Nov 2012 08:39:59 -0500 From: Rik van Riel User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:15.0) Gecko/20120827 Thunderbird/15.0 MIME-Version: 1.0 To: Michel Lespinasse CC: Andrew Morton , Hugh Dickins , Sasha Levin , 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 References: <1352721091-27022-1-git-send-email-walken@google.com> <1352721091-27022-2-git-send-email-walken@google.com> In-Reply-To: <1352721091-27022-2-git-send-email-walken@google.com> Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 7bit Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org 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 > Signed-off-by: Michel Lespinasse Reviewed-by: Rik van Riel -- All rights reversed From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1753510Ab2KLUzG (ORCPT ); Mon, 12 Nov 2012 15:55:06 -0500 Received: from mail-vc0-f174.google.com ([209.85.220.174]:53393 "EHLO mail-vc0-f174.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1753392Ab2KLUzE (ORCPT ); Mon, 12 Nov 2012 15:55:04 -0500 Message-ID: <50A16212.8090507@gmail.com> Date: Mon, 12 Nov 2012 15:54:42 -0500 From: Sasha Levin User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:16.0) Gecko/20121024 Thunderbird/16.0.1 MIME-Version: 1.0 To: Michel Lespinasse CC: Andrew Morton , Rik van Riel , Hugh Dickins , linux-kernel@vger.kernel.org, linux-mm@kvack.org Subject: Re: [PATCH 0/3] fix missing rb_subtree_gap updates on vma insert/erase References: <1352721091-27022-1-git-send-email-walken@google.com> In-Reply-To: <1352721091-27022-1-git-send-email-walken@google.com> Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 7bit Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org 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. > > These 3 patches apply on top of the stack I previously sent (or equally, > on top of the last published mmotm). > > Michel Lespinasse (3): > mm: ensure safe rb_subtree_gap update when inserting new VMA > mm: ensure safe rb_subtree_gap update when removing VMA > mm: debug code to verify rb_subtree_gap updates are safe > > mm/mmap.c | 121 +++++++++++++++++++++++++++++++++++++------------------------ > 1 files changed, 73 insertions(+), 48 deletions(-) > Looking good: old warnings gone, no new warnings. Thanks, Sasha From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1755838Ab2K0BQu (ORCPT ); Mon, 26 Nov 2012 20:16:50 -0500 Received: from mail-qc0-f174.google.com ([209.85.216.174]:43178 "EHLO mail-qc0-f174.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1755101Ab2K0BQs (ORCPT ); Mon, 26 Nov 2012 20:16:48 -0500 Message-ID: <50B4145C.3010406@gmail.com> Date: Mon, 26 Nov 2012 20:16:12 -0500 From: Sasha Levin User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:16.0) Gecko/20121112 Thunderbird/16.0.1 MIME-Version: 1.0 To: Michel Lespinasse CC: Andrew Morton , Rik van Riel , Hugh Dickins , linux-kernel@vger.kernel.org, linux-mm@kvack.org Subject: Re: [PATCH 0/3] fix missing rb_subtree_gap updates on vma insert/erase References: <1352721091-27022-1-git-send-email-walken@google.com> <50A16212.8090507@gmail.com> In-Reply-To: <50A16212.8090507@gmail.com> Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 7bit Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org On 11/12/2012 03:54 PM, Sasha Levin wrote: > 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. >> >> These 3 patches apply on top of the stack I previously sent (or equally, >> on top of the last published mmotm). >> >> Michel Lespinasse (3): >> mm: ensure safe rb_subtree_gap update when inserting new VMA >> mm: ensure safe rb_subtree_gap update when removing VMA >> mm: debug code to verify rb_subtree_gap updates are safe >> >> mm/mmap.c | 121 +++++++++++++++++++++++++++++++++++++------------------------ >> 1 files changed, 73 insertions(+), 48 deletions(-) >> > > Looking good: old warnings gone, no new warnings. I've built today's -next, and got the following BUG pretty quickly (2-3 hours): [ 1556.479284] BUG: unable to handle kernel paging request at 0000000000412000 [ 1556.480036] IP: [] validate_mm+0x34/0x130 [ 1556.480036] PGD 31739067 PUD 4fbc4067 PMD 1c936067 PTE 0 [ 1556.480036] Oops: 0000 [#1] PREEMPT SMP DEBUG_PAGEALLOC [ 1556.480036] Dumping ftrace buffer: [ 1556.480036] (ftrace buffer empty) [ 1556.480036] CPU 0 [ 1556.480036] Pid: 10274, comm: trinity-child29 Tainted: G W 3.7.0-rc6-next-20121126-sasha-00015-gb04382b-dirty #201 [ 1556.480036] RIP: 0010:[] [] validate_mm+0x34/0x130 [ 1556.480036] RSP: 0018:ffff88004fbc7d08 EFLAGS: 00010206 [ 1556.480036] RAX: 0000000000412000 RBX: 0000000000000000 RCX: 0000000000000000 [ 1556.512120] RDX: 0000000000000000 RSI: ffff88001c1a6008 RDI: ffff88001c1a6000 [ 1556.512120] RBP: ffff88004fbc7d38 R08: ffff8800371e7808 R09: ffff88004fb56cf0 [ 1556.512120] R10: 0000000000000001 R11: 0000000000001000 R12: ffff88001c1a6000 [ 1556.512120] R13: ffff8800371e7b00 R14: 0000000000000000 R15: ffff88001c1a6000 [ 1556.512120] FS: 00007f4e0f8e3700(0000) GS:ffff8800bfc00000(0000) knlGS:0000000000000000 [ 1556.512120] CS: 0010 DS: 0000 ES: 0000 CR0: 0000000080050033 [ 1556.512120] CR2: 0000000000412000 CR3: 000000002faec000 CR4: 00000000000406f0 [ 1556.512120] DR0: 0000000000000000 DR1: 0000000000000000 DR2: 0000000000000000 [ 1556.512120] DR3: 0000000000000000 DR6: 00000000ffff0ff0 DR7: 0000000000000400 [ 1556.512120] Process trinity-child29 (pid: 10274, threadinfo ffff88004fbc6000, task ffff88004fbb0000) [ 1556.512120] Stack: [ 1556.512120] ffff8800bf80aa80 ffff88001c1a6000 ffff88004fb56cf0 ffff8800371e7818 [ 1556.512120] ffff8800371e7808 ffff88001c1a6000 ffff88004fbc7d88 ffffffff8123843c [ 1556.512120] 0000000000000001 ffff88004fb56da8 ffff880000000000 ffff8800371e7818 [ 1556.512120] Call Trace: [ 1556.512120] [] vma_link+0xcc/0xf0 [ 1556.512120] [] mmap_region+0x40c/0x5a0 [ 1556.512120] [] do_mmap_pgoff+0x2ab/0x310 [ 1556.512120] [] ? vm_mmap_pgoff+0x6c/0xb0 [ 1556.512120] [] vm_mmap_pgoff+0x84/0xb0 [ 1556.512120] [] sys_mmap_pgoff+0x193/0x1a0 [ 1556.512120] [] ? trace_hardirqs_on_caller+0x118/0x140 [ 1556.512120] [] sys_mmap+0x1d/0x20 [ 1556.512120] [] tracesys+0xe1/0xe6 [ 1556.512120] Code: 31 f6 41 55 41 54 49 89 fc 53 31 db 48 83 ec 08 4c 8b 2f 4d 85 ed 74 75 0f 1f 80 00 00 00 00 49 8b 85 88 00 00 00 48 85 c0 74 0e <48> 8b 38 31 f6 48 83 c7 08 e8 0e bc a4 02 49 8b 45 78 4d 8d 7d [ 1556.512120] RIP [] validate_mm+0x34/0x130 [ 1556.512120] RSP [ 1556.512120] CR2: 0000000000412000 [ 1557.729958] ---[ end trace d2a29e98cc9e2568 ]--- The bit that's failing is: struct vm_area_struct *vma = mm->mmap; // mm->mmap = 0x412000 while (vma) { struct anon_vma_chain *avc; vma_lock_anon_vma(vma); // BOOM! Thanks, Sasha From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1758001Ab2K0EzY (ORCPT ); Mon, 26 Nov 2012 23:55:24 -0500 Received: from mail-vc0-f174.google.com ([209.85.220.174]:45023 "EHLO mail-vc0-f174.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1757957Ab2K0EzW (ORCPT ); Mon, 26 Nov 2012 23:55:22 -0500 MIME-Version: 1.0 In-Reply-To: <50B4145C.3010406@gmail.com> References: <1352721091-27022-1-git-send-email-walken@google.com> <50A16212.8090507@gmail.com> <50B4145C.3010406@gmail.com> Date: Mon, 26 Nov 2012 20:55:21 -0800 Message-ID: Subject: Re: [PATCH 0/3] fix missing rb_subtree_gap updates on vma insert/erase From: Michel Lespinasse To: Sasha Levin Cc: Andrew Morton , Rik van Riel , Hugh Dickins , linux-kernel@vger.kernel.org, linux-mm@kvack.org Content-Type: text/plain; charset=ISO-8859-1 Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org On Mon, Nov 26, 2012 at 5:16 PM, Sasha Levin wrote: > I've built today's -next, and got the following BUG pretty quickly (2-3 hours): > > [ 1556.479284] BUG: unable to handle kernel paging request at 0000000000412000 > [ 1556.480036] IP: [] validate_mm+0x34/0x130 > [ 1556.480036] PGD 31739067 PUD 4fbc4067 PMD 1c936067 PTE 0 > [ 1556.480036] Oops: 0000 [#1] PREEMPT SMP DEBUG_PAGEALLOC > [ 1556.480036] Dumping ftrace buffer: > [ 1556.480036] (ftrace buffer empty) > [ 1556.480036] CPU 0 > [ 1556.480036] Pid: 10274, comm: trinity-child29 Tainted: G W 3.7.0-rc6-next-20121126-sasha-00015-gb04382b-dirty #201 > [ 1556.480036] RIP: 0010:[] [] validate_mm+0x34/0x130 > [ 1556.480036] RSP: 0018:ffff88004fbc7d08 EFLAGS: 00010206 > [ 1556.480036] RAX: 0000000000412000 RBX: 0000000000000000 RCX: 0000000000000000 > [ 1556.512120] RDX: 0000000000000000 RSI: ffff88001c1a6008 RDI: ffff88001c1a6000 > [ 1556.512120] RBP: ffff88004fbc7d38 R08: ffff8800371e7808 R09: ffff88004fb56cf0 > [ 1556.512120] R10: 0000000000000001 R11: 0000000000001000 R12: ffff88001c1a6000 > [ 1556.512120] R13: ffff8800371e7b00 R14: 0000000000000000 R15: ffff88001c1a6000 > [ 1556.512120] FS: 00007f4e0f8e3700(0000) GS:ffff8800bfc00000(0000) knlGS:0000000000000000 > [ 1556.512120] CS: 0010 DS: 0000 ES: 0000 CR0: 0000000080050033 > [ 1556.512120] CR2: 0000000000412000 CR3: 000000002faec000 CR4: 00000000000406f0 > [ 1556.512120] DR0: 0000000000000000 DR1: 0000000000000000 DR2: 0000000000000000 > [ 1556.512120] DR3: 0000000000000000 DR6: 00000000ffff0ff0 DR7: 0000000000000400 > [ 1556.512120] Process trinity-child29 (pid: 10274, threadinfo ffff88004fbc6000, task ffff88004fbb0000) > [ 1556.512120] Stack: > [ 1556.512120] ffff8800bf80aa80 ffff88001c1a6000 ffff88004fb56cf0 ffff8800371e7818 > [ 1556.512120] ffff8800371e7808 ffff88001c1a6000 ffff88004fbc7d88 ffffffff8123843c > [ 1556.512120] 0000000000000001 ffff88004fb56da8 ffff880000000000 ffff8800371e7818 > [ 1556.512120] Call Trace: > [ 1556.512120] [] vma_link+0xcc/0xf0 > [ 1556.512120] [] mmap_region+0x40c/0x5a0 > [ 1556.512120] [] do_mmap_pgoff+0x2ab/0x310 > [ 1556.512120] [] ? vm_mmap_pgoff+0x6c/0xb0 > [ 1556.512120] [] vm_mmap_pgoff+0x84/0xb0 > [ 1556.512120] [] sys_mmap_pgoff+0x193/0x1a0 > [ 1556.512120] [] ? trace_hardirqs_on_caller+0x118/0x140 > [ 1556.512120] [] sys_mmap+0x1d/0x20 > [ 1556.512120] [] tracesys+0xe1/0xe6 > [ 1556.512120] Code: 31 f6 41 55 41 54 49 89 fc 53 31 db 48 83 ec 08 4c 8b 2f 4d 85 ed 74 75 0f 1f 80 00 00 00 00 49 8b 85 88 00 00 > 00 48 85 c0 74 0e <48> 8b 38 31 f6 48 83 c7 08 e8 0e bc a4 02 49 8b 45 78 4d 8d 7d > [ 1556.512120] RIP [] validate_mm+0x34/0x130 > [ 1556.512120] RSP > [ 1556.512120] CR2: 0000000000412000 > [ 1557.729958] ---[ end trace d2a29e98cc9e2568 ]--- > > The bit that's failing is: > > struct vm_area_struct *vma = mm->mmap; // mm->mmap = 0x412000 > while (vma) { > struct anon_vma_chain *avc; > vma_lock_anon_vma(vma); // BOOM! > > > Thanks, > Sasha Thanks for the report. I believe we actually have mm->mmap = ffff8800371e7b00 (r13); That first vma has its anon_vma field pointing to 0000000000412000 (rax) and we fault while trying to read anon_vma->root. I don't see what could cause vma->anon_vma to be an invalid non-null value. This looks very much like there might be some kind of memory corruption occuring, but I can't tell where it would come from. Going back into your previous reports, we also never really identified the root cause of your two reports at the start of the thread with subject: "mm: NULL ptr deref in anon_vma_interval_tree_verify" (on Oct 18th and Oct 25th). At some point we thought that taking the anon_vma lock in validate_mm would prevent a race and fix the issue, but further inspection convinced us that this shouldn't be necessary - so, in the end, we still don't know what caused us to crash in these two cases either (and, I was tempted to suggest memory corruption at the time too). So, I'm not sure what to do. One thing to keep in mind is that CONFIG_DEBUG_VM_RB was only recently introduced (between v3.6 and v3.7-rc1); before that the code existed only as an #ifdef in mm/mmap.c. So, it might help if you could run your trinity test on these few kernel versions: - first, on v3.6, after editing mm/mmap.c to replace #undef DEBUG_MM_RB with #define DEBUG_MM_RB; (if this fails here, then what we have is a latent bug that CONFIG_DEBUG_VM_RB just happened to reveal) - then, on v3.7-rc1 with no further changes (if this fails here, then the issue is likely with my rbtree intervals stuff that made it into v3.7-rc1) - finally, on the akpm-base branch in linux-next tree (if this fails here, then the issue may be some corruption caused by one of the trees other than -mm) Sorry to request this; I'm really not sure what else to try at this point :/ -- Michel "Walken" Lespinasse A program is never fully debugged until the last user dies.