radix-tree: fix RCU bug

Salman Qazi describes the following radix-tree bug:

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.
3b. The zero item is deleted, removing it from the direct slot, it remains in
    the rcu-delayed indirect node.
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.

The fix is to re-use the same "indirect" pointer case that requires a slot
lookup retry into a general "retry the lookup" bit.

Signed-off-by: Nick Piggin <npiggin@kernel.dk>
Reported-by: Salman Qazi <sqazi@google.com>
Cc: <stable@kernel.org>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>

1 files changed, 58 insertions, 25 deletions

diff --git a/lib/radix-tree.c b/lib/radix-tree.c
index 6f412ab4c24f..5086bb962b4d 100644
--- a/lib/radix-tree.c
+++ b/lib/radix-tree.c
@@ -82,6 +82,16 @@ struct radix_tree_preload {
 };
 static DEFINE_PER_CPU(struct radix_tree_preload, radix_tree_preloads) = { 0, };
 
+static inline void *ptr_to_indirect(void *ptr)
+{
+        return (void *)((unsigned long)ptr | RADIX_TREE_INDIRECT_PTR);
+}
+
+static inline void *indirect_to_ptr(void *ptr)
+{
+        return (void *)((unsigned long)ptr & ~RADIX_TREE_INDIRECT_PTR);
+}
+
 static inline gfp_t root_gfp_mask(struct radix_tree_root *root)
 {
         return root->gfp_mask & __GFP_BITS_MASK;
@@ -265,7 +275,7 @@ static int radix_tree_extend(struct radix_tree_root *root, unsigned long index)
                         return -ENOMEM;
 
                 /* Increase the height.  */
-                node->slots[0] = radix_tree_indirect_to_ptr(root->rnode);
+                node->slots[0] = indirect_to_ptr(root->rnode);
 
                 /* Propagate the aggregated tag info into the new root */
                 for (tag = 0; tag < RADIX_TREE_MAX_TAGS; tag++) {
@@ -276,7 +286,7 @@ static int radix_tree_extend(struct radix_tree_root *root, unsigned long index)
                 newheight = root->height+1;
                 node->height = newheight;
                 node->count = 1;
-                node = radix_tree_ptr_to_indirect(node);
+                node = ptr_to_indirect(node);
                 rcu_assign_pointer(root->rnode, node);
                 root->height = newheight;
         } while (height > root->height);
@@ -309,7 +319,7 @@ int radix_tree_insert(struct radix_tree_root *root,
                         return error;
         }
 
-        slot = radix_tree_indirect_to_ptr(root->rnode);
+        slot = indirect_to_ptr(root->rnode);
 
         height = root->height;
         shift = (height-1) * RADIX_TREE_MAP_SHIFT;
@@ -325,8 +335,7 @@ int radix_tree_insert(struct radix_tree_root *root,
                                 rcu_assign_pointer(node->slots[offset], slot);
                                 node->count++;
                         } else
-                                rcu_assign_pointer(root->rnode,
-                                        radix_tree_ptr_to_indirect(slot));
+                                rcu_assign_pointer(root->rnode, ptr_to_indirect(slot));
                 }
 
                 /* Go a level down */
@@ -374,7 +383,7 @@ static void *radix_tree_lookup_element(struct radix_tree_root *root,
                         return NULL;
                 return is_slot ? (void *)&root->rnode : node;
         }
-        node = radix_tree_indirect_to_ptr(node);
+        node = indirect_to_ptr(node);
 
         height = node->height;
         if (index > radix_tree_maxindex(height))
@@ -393,7 +402,7 @@ static void *radix_tree_lookup_element(struct radix_tree_root *root,
                 height--;
         } while (height > 0);
 
-        return is_slot ? (void *)slot:node;
+        return is_slot ? (void *)slot : indirect_to_ptr(node);
 }
 
 /**
@@ -455,7 +464,7 @@ void *radix_tree_tag_set(struct radix_tree_root *root,
         height = root->height;
         BUG_ON(index > radix_tree_maxindex(height));
 
-        slot = radix_tree_indirect_to_ptr(root->rnode);
+        slot = indirect_to_ptr(root->rnode);
         shift = (height - 1) * RADIX_TREE_MAP_SHIFT;
 
         while (height > 0) {
@@ -509,7 +518,7 @@ void *radix_tree_tag_clear(struct radix_tree_root *root,
 
         shift = (height - 1) * RADIX_TREE_MAP_SHIFT;
         pathp->node = NULL;
-        slot = radix_tree_indirect_to_ptr(root->rnode);
+        slot = indirect_to_ptr(root->rnode);
 
         while (height > 0) {
                 int offset;
@@ -579,7 +588,7 @@ int radix_tree_tag_get(struct radix_tree_root *root,
 
         if (!radix_tree_is_indirect_ptr(node))
                 return (index == 0);
-        node = radix_tree_indirect_to_ptr(node);
+        node = indirect_to_ptr(node);
 
         height = node->height;
         if (index > radix_tree_maxindex(height))
@@ -666,7 +675,7 @@ unsigned long radix_tree_range_tag_if_tagged(struct radix_tree_root *root,
         }
 
         shift = (height - 1) * RADIX_TREE_MAP_SHIFT;
-        slot = radix_tree_indirect_to_ptr(root->rnode);
+        slot = indirect_to_ptr(root->rnode);
 
         /*
          * we fill the path from (root->height - 2) to 0, leaving the index at
@@ -897,7 +906,7 @@ radix_tree_gang_lookup(struct radix_tree_root *root, void **results,
                 results[0] = node;
                 return 1;
         }
-        node = radix_tree_indirect_to_ptr(node);
+        node = indirect_to_ptr(node);
 
         max_index = radix_tree_maxindex(node->height);
 
@@ -916,7 +925,8 @@ radix_tree_gang_lookup(struct radix_tree_root *root, void **results,
                         slot = *(((void ***)results)[ret + i]);
                         if (!slot)
                                 continue;
-                        results[ret + nr_found] = rcu_dereference_raw(slot);
+                        results[ret + nr_found] =
+                                indirect_to_ptr(rcu_dereference_raw(slot));
                         nr_found++;
                 }
                 ret += nr_found;
@@ -965,7 +975,7 @@ radix_tree_gang_lookup_slot(struct radix_tree_root *root, void ***results,
                 results[0] = (void **)&root->rnode;
                 return 1;
         }
-        node = radix_tree_indirect_to_ptr(node);
+        node = indirect_to_ptr(node);
 
         max_index = radix_tree_maxindex(node->height);
 
@@ -1090,7 +1100,7 @@ radix_tree_gang_lookup_tag(struct radix_tree_root *root, void **results,
                 results[0] = node;
                 return 1;
         }
-        node = radix_tree_indirect_to_ptr(node);
+        node = indirect_to_ptr(node);
 
         max_index = radix_tree_maxindex(node->height);
 
@@ -1109,7 +1119,8 @@ radix_tree_gang_lookup_tag(struct radix_tree_root *root, void **results,
                         slot = *(((void ***)results)[ret + i]);
                         if (!slot)
                                 continue;
-                        results[ret + nr_found] = rcu_dereference_raw(slot);
+                        results[ret + nr_found] =
+                                indirect_to_ptr(rcu_dereference_raw(slot));
                         nr_found++;
                 }
                 ret += nr_found;
@@ -1159,7 +1170,7 @@ radix_tree_gang_lookup_tag_slot(struct radix_tree_root *root, void ***results,
                 results[0] = (void **)&root->rnode;