Skip to contentSkip to conversation

radix-tree: Fix private list warnings

PATCH In review Matthew Wilcox 3 participants 5 messages Jan 12, 2017 – Jan 18, 2017 Library code

lore
Share & tools
lore

Matthew Wilcox

author
#0 lore raw

PATCH 1/1 radix-tree: Fix private list warnings

From: Matthew Wilcox <[email protected]>

The newly introduced warning in radix_tree_free_nodes() was testing the wrong variable; it should have been 'old' instead of 'node'. Rather than replace that one instance, I noticed that we can simply put the WARN_ON_ONCE in radix_tree_node_free() and it will be just as effective.

Fixes ea07b862ac8e ("mm: workingset: fix use-after-free in shadow node shrinker")
Signed-off-by Matthew Wilcox <[email protected]>
---
 lib/radix-tree.c | 4 +---
 1 file changed, 1 insertion(+), 3 deletions(-)
lib/radix-tree.c +1 -3
index 4a4ed3ee4222..3c4577cabc57 100644
@@ -449,6 +449,7 @@ static void radix_tree_node_rcu_free(struct rcu_head *head)
 static inline void
 radix_tree_node_free(struct radix_tree_node *node)
 {
+	WARN_ON_ONCE(!list_empty(&node->private_list));
 	call_rcu(&node->rcu_head, radix_tree_node_rcu_free);
 }
 

@@ -734,7 +735,6 @@ static inline void radix_tree_shrink(struct radix_tree_root *root,
 				update_node(node, private);
 		}
 
-		WARN_ON_ONCE(!list_empty(&node->private_list));
 		radix_tree_node_free(node);
 	}
 }

@@ -766,7 +766,6 @@ static void delete_node(struct radix_tree_root *root,
 			root->rnode = NULL;
 		}
 
-		WARN_ON_ONCE(!list_empty(&node->private_list));
 		radix_tree_node_free(node);
 
 		node = parent;

@@ -868,7 +867,6 @@ static void radix_tree_free_nodes(struct radix_tree_node *node)
 			struct radix_tree_node *old = child;
 			offset = child->offset + 1;
 			child = child->parent;
-			WARN_ON_ONCE(!list_empty(&node->private_list));
 			radix_tree_node_free(old);
 			if (old == entry_to_node(node))
 				return;
Signature · 1 line
2.11.0.296.g5800ad326.dirty
#1 lore raw
Quoted 9 lines · Matthew Wilcox

From: Matthew Wilcox <[email protected]>

The newly introduced warning in radix_tree_free_nodes() was testing the wrong variable; it should have been 'old' instead of 'node'. Rather than replace that one instance, I noticed that we can simply put the WARN_ON_ONCE in radix_tree_node_free() and it will be just as effective.

Fixes ea07b862ac8e ("mm: workingset: fix use-after-free in shadow node shrinker")
Signed-off-by Matthew Wilcox <[email protected]>

Thanks for the fix in radix_tree_free_nodes(). But I intentionally spread out the warnings to retain the line numbers. The inlining in that code will obscure which tree operation ends up triggering.

#2 lore raw

From: Johannes Weiner [mailto:[email protected]]

Quoted 6 lines · Matthew Wilcox
Quoted 5 lines

The newly introduced warning in radix_tree_free_nodes() was testing the wrong variable; it should have been 'old' instead of 'node'. Rather than replace that one instance, I noticed that we can simply put the WARN_ON_ONCE in radix_tree_node_free() and it will be just as effective.

Quoted 7 lines
Quoted 1 line
Fixes ea07b862ac8e ("mm: workingset: fix use-after-free in shadow node

shrinker")

Quoted 1 line
Signed-off-by Matthew Wilcox <[email protected]>

Thanks for the fix in radix_tree_free_nodes(). But I intentionally spread out the warnings to retain the line numbers. The inlining in that code will obscure which tree operation ends up triggering.

The backtrace should make that fairly obvious though; even if radix_tree_node_free() gets inlined, the caller of radix_tree_free_nodes() probably doesn't also call radix_tree_shrink() or delete_node(). You're really looking for the caller in the backtrace that's outside of radix-tree.c.

By the way, if you'd run the radix tree test-suite, the WARN_ON_ONCE would have triggered (that's how I spotted the bug). The test-suite is getting pretty useful these days; would you mind running it in future?

#3 lore raw
Quoted 15 lines · Matthew Wilcox

From: Johannes Weiner [mailto:[email protected]]

Quoted 6 lines · Matthew Wilcox
Quoted 5 lines

The newly introduced warning in radix_tree_free_nodes() was testing the wrong variable; it should have been 'old' instead of 'node'. Rather than replace that one instance, I noticed that we can simply put the WARN_ON_ONCE in radix_tree_node_free() and it will be just as effective.

Quoted 7 lines
Quoted 1 line
Fixes ea07b862ac8e ("mm: workingset: fix use-after-free in shadow node

shrinker")

Quoted 1 line
Signed-off-by Matthew Wilcox <[email protected]>

Thanks for the fix in radix_tree_free_nodes(). But I intentionally spread out the warnings to retain the line numbers. The inlining in that code will obscure which tree operation ends up triggering.

Quoted 5 lines

The backtrace should make that fairly obvious though; even if radix_tree_node_free() gets inlined, the caller of radix_tree_free_nodes() probably doesn't also call radix_tree_shrink() or delete_node(). You're really looking for the caller in the backtrace that's outside of radix-tree.c.

Distinguishing between the radix_tree_shrink() and the delete_node() sites was essential to find the bug whose fix added these warnings. The former gets inlined into the latter. Not impossible to figure out which one triggered from a full dump, but certainly less robust.

Quoted 4 lines

By the way, if you'd run the radix tree test-suite, the WARN_ON_ONCE would have triggered (that's how I spotted the bug). The test-suite is getting pretty useful these days; would you mind running it in future?

Thanks, I'll keep that in mind for future radix tree changes.

#4 lore raw
Quoted 22 lines · Johannes Weiner
Quoted 15 lines · Matthew Wilcox

From: Johannes Weiner [mailto:[email protected]]

Quoted 6 lines · Matthew Wilcox
Quoted 5 lines

The newly introduced warning in radix_tree_free_nodes() was testing the wrong variable; it should have been 'old' instead of 'node'. Rather than replace that one instance, I noticed that we can simply put the WARN_ON_ONCE in radix_tree_node_free() and it will be just as effective.

Quoted 7 lines
Quoted 1 line
Fixes ea07b862ac8e ("mm: workingset: fix use-after-free in shadow node

shrinker")

Quoted 1 line
Signed-off-by Matthew Wilcox <[email protected]>

Thanks for the fix in radix_tree_free_nodes(). But I intentionally spread out the warnings to retain the line numbers. The inlining in that code will obscure which tree operation ends up triggering.

Quoted 5 lines

The backtrace should make that fairly obvious though; even if radix_tree_node_free() gets inlined, the caller of radix_tree_free_nodes() probably doesn't also call radix_tree_shrink() or delete_node(). You're really looking for the caller in the backtrace that's outside of radix-tree.c.

Quoted 4 lines

Distinguishing between the radix_tree_shrink() and the delete_node() sites was essential to find the bug whose fix added these warnings. The former gets inlined into the latter. Not impossible to figure out which one triggered from a full dump, but certainly less robust.

This?

Quoted 1 line

From 669b5ed6e32386d634023fee29b0b8562951e734 Mon Sep 17 00:00:00 2001

From: Matthew Wilcox <[email protected]>
Date: Thu, 12 Jan 2017 17:28:23 -0800
Subject: [PATCH] radix-tree: Fix private list warnings

The newly introduced warning in radix_tree_free_nodes() was testing the wrong variable; it should have been 'old' instead of 'node'.

Fixes ea07b862ac8e ("mm: workingset: fix use-after-free in shadow node shrinker")
Signed-off-by Matthew Wilcox <[email protected]>
Signed-off-by Johannes Weiner <[email protected]>
---
 lib/radix-tree.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)
lib/radix-tree.c +1 -1
index 0b92d605fb69..84812a9fb16f 100644
@@ -769,7 +769,7 @@ static void radix_tree_free_nodes(struct radix_tree_node *node)
 			struct radix_tree_node *old = child;
 			offset = child->offset + 1;
 			child = child->parent;
-			WARN_ON_ONCE(!list_empty(&node->private_list));
+			WARN_ON_ONCE(!list_empty(&old->private_list));
 			radix_tree_node_free(old);
 			if (old == entry_to_node(node))
 				return;
Signature · 1 line
2.11.0