[lkml]   [2010]   [Aug]   [13]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
Messages in this thread
Patch in this message
Subject[PATCH] Fixed a mismatch between the users of radix_tree and the implementation.
This matters for the lockless page cache, in particular find_get_pages implementation.

In the following case, we get can get a deadlock:

0. The radix tree contains two items, one has the index 0.
1. The reader (in this case find_get_pages) takes the rcu_read_lock.
2. The reader acquires slot(s) for item(s) including the index 0 item.
3. The non-zero index item is deleted, and as a consequence the other item
is moved to the root of the tree. The place where it used to be is
queued for deletion after the readers finish.
4. The reader looks at the index 0 slot, and finds that the page has 0 ref count
5. The reader looks at it again, hoping that the item will either be freed
or the ref count will increase. This never happens, as the slot it
is looking at will never be updated. Also, this slot can never be reclaimed
because the reader is holding rcu_read_lock and is in an infinite loop.

This can be reproduced with reliably by running dbench followed by compilebench under
autotest. I have not been able to construct a small targeted repro case.

There is also a similar potential issue with insertion. Storing the first
element in the root and then moving it to a new slot on insertion of a
second element would potentially lead to a similar problem.

Both of these issues have been fixed in this change.

Signed-off-by: Salman Qazi <>
lib/radix-tree.c | 9 ++-------
1 files changed, 2 insertions(+), 7 deletions(-)

diff --git a/lib/radix-tree.c b/lib/radix-tree.c
index e907858..035d5aa 100644
--- a/lib/radix-tree.c
+++ b/lib/radix-tree.c
@@ -252,11 +252,6 @@ static int radix_tree_extend(struct radix_tree_root *root, unsigned long index)
while (index > radix_tree_maxindex(height))

- if (root->rnode == NULL) {
- root->height = height;
- goto out;
- }
do {
unsigned int newheight;
if (!(node = radix_tree_node_alloc(root)))
@@ -278,7 +273,7 @@ static int radix_tree_extend(struct radix_tree_root *root, unsigned long index)
rcu_assign_pointer(root->rnode, node);
root->height = newheight;
} while (height > root->height);
return 0;

@@ -1154,7 +1149,7 @@ EXPORT_SYMBOL(radix_tree_gang_lookup_tag_slot);
static inline void radix_tree_shrink(struct radix_tree_root *root)
/* try to shrink tree height */
- while (root->height > 0) {
+ while (root->height > 1) {
struct radix_tree_node *to_free = root->rnode;
void *newptr;

 \ /
  Last update: 2010-08-13 09:19    [W:0.095 / U:14.940 seconds]
©2003-2018 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site